Inter-domain collaborative routing (IDCR): Server selection for optimal client performance

Communication between institutions, or domains, residing in the Internet requires a route to be created between the routing domains. Each of these domains is controlled by a single administrative authority, and is referred to as an autonomous system (AS). Control of routes that move the data in the Internet between ASes is problematic. If an AS requires certain route characteristics beyond the selection of the first hop, the AS must pay for some type of special service from its Internet service provider (ISP). The ISP can provide integrity of the data using end-to-end encryption, but the customer AS still does not have control over the route. In other words, an organization is unable to prevent its data from passing through certain parts of the Internet. We believe that a service allowing an AS to select from alternate routes, on behalf of an organization, could meet this need for route customization. The alternate routes could be created to meet the requirements of the source AS, such as the avoidance of another AS. The service must minimize the incremental cost (in hops) of the alternate routes and maximize the probability that an alternate route will be found. We measure the effectiveness of several algorithms as they are used to select ASes to deploy a solution, called inter-domain collaborative routing (IDCR), that allows "friend" routers to collaboratively determine a route. Key to the performance of IDCR is the placement of "friend" routers in the Internet. We explore the trade-off between placing "friend" routers in various levels of the hierarchy of routers in the Internet. In order to measure the effectiveness of IDCR as the set of ASes deploying the service is varied, we track the probability of routing success and monitor the incremental cost in hops as the service creates alternate routes in several small but representative network models. We evaluate three algorithms used to determine which routers should support the IDCR service. The first, called the degree algorithm, categorizes the routers into a hierarchy, based only on the nodal degree of the router [1]. The second, called the factor algorithm, calculates an IDCR factor for each router and uses that to rank select routers to provide the service. Finally, the greedy algorithm, serving as the baseline, iterates across all candidate routers, selecting routers one at a time based on the performance of the service.