Turning Heterogeneity into an Advantagein Overlay RoutingZhichen XuHewlett-Packard Laboratories1501 Page Mill RdPalo Alto, CA 94304Email: [email protected] MahalingamVMware Inc.3145 Porter DrivePalo Alto CA 94304Email: [email protected] KarlssonHewlett-Packard Laboratories1501 Page Mill RdPalo Alto, CA 94304Email: [email protected]— Distributed hash table (DHT)-based overlay net-works, represented by Pastry, CAN, and Chord, offer anadministration-free and fault-tolerant application-level overlaynetwork. While elegant from a theoretical perspective, thesesystems have some disadvantages. First, they rely on application-level routing, which may be inefficient with respect to networkdelays and bandwidth consumption. Second, they typically con-struct a homogeneously structured overlay even though nodes inthese networks usually have varying physical connectivity andpacket-forwarding capacities.In this paper, we propose two approaches for constructingan auxiliary expressway network to take advantage of thedifferent connectivity, forwarding capacities, and availabilitiesof the nodes. As a result, we are able to reconcile the conflictof presenting the applications with a homogeneous structuredoverlay to simplify management, while at the same time tak-ing advantage of the inherent heterogeneity of the underlyingphysical network to speed up routing. Our simulation resultsshow that our expressway can achieve close to optimal routingperformance (on average, 1.07 and 1.41 times optimal routingfor an Internet-like topology and a large synthesized transit-stubgraph, respectively) in overlay networks.I. INTRODUCTIONPeer-to-peer (P2P) systems are gaining popularity quicklydue to their scalability, fault-tolerance, and self-organizingnature. Progress in P2P has been made in applications suchas storage [1], [2], DNS, media streaming [3], collaborativeWeb server [4], distributed content-based search [5], and evendistributed firewalls [6].Distributed hash table (DHT)-based systems such as CAN[7], Chord [8], and Pastry [9] present applications with ahomogeneously structured application-level overlay network.Nodes in these networks collectively contribute towards anadministration-free storage space. Retrieving an object in thesesystems amounts to routing to the node that is responsiblefor storing that object. Providing a simple and homogeneousabstraction has several desirable properties. It provides stabil-ity by hiding the underlying dynamism and heterogeneity ofthe system, and simplifies the management of the large-scaledistributed system by e.g., providing a uniform storage spaceto avoid hot-spots.While elegant from a theoretical perspective, these systemshave two limitations. First, they rely on application-levelrouting that to a great extent ignores the characteristics ofthe underlying physical networks, which can lead to exces-sive routing delays. Second, they construct a homogeneousstructured overlay network, while in reality, the nodes usuallyhave different capacities and constraints such as load, packet-forwarding capacities, network connections, and availability.In fact, for different nodes, the number of nodes that arephysically close to them in network distance can vary signifi-cantly. We support this claim by constructing an AutonomousSystem (AS) graph from BGP routing tables [10], that showsthat the fan-out of an AS can range from 1 to 2621. Weargue that for a system to function efficiently, it is importantto make discriminative use of the nodes in the system. Thequestion we try to answer is how we can take advantage ofthe heterogeneity of nodes to improve routing performancewithout altering the abstraction presented to the application.In this paper, we describe two approaches for constructingan auxiliary network called an expressway, that takes physicalproximity, forwarding capacity, node availability, and nodeconnectivity into account, to significantly increase routingperformance. The first approach uses the AS-level topologyextracted from BGP reports, and the second approach usesa novel landmark numbering strategy that can deal withchanging network conditions.Systems such as Pastry [9] and Tapestry [11] account forphysical proximity when an overlay is constructed. Theyassume the topology satisfies the triangle inequality, and relyon the ability to find the physically closest node at node join.Savage et al.[12] have shown that triangle inequality maynot hold in Internet topology. Topologically-Aware CAN [13]uses landmark ordering to cluster nodes that are physicallyclose into logical vicinity during overlay construction. Thoughthis yields good performance improvements, it may causesignificant imbalances in the distribution of the nodes in theCAN space that leads to hot-spots [14] and does not handlechanging network conditions. Chord, on the other hand, doesnot consider physical topology when constructing the overlay.Instead, a message is forwarded to the topologically closestnode among the next hop candidates in the routing table. Thechoices for each routing hop, unfortunately, are limited to en-tries in the routing table. All the above systems are constrainedby the logical structure of the default overlay, possibly limitingthe maximum performance that can be achieved.0-7803-7753-2/03/$17.00 (C) 2003 IEEE 1499Brocade [15] removes some of the constraints in previoussystems by constructing a secondary overlay network of su-pernodes that are situated near the network access points suchas routers. Though Brocade improves performance, it still useslogical routing in the secondary network, which incurs severalphysical hops for every logical hop. Brocade, to some extent,pushes the problem to an auxiliary network of a smaller size.Our proposal decouples the homogeneous overlay abstrac-tion from routing altogether. It allows nodes to have a variablenumber of neighbors in an expressway, leaving the homoge-neous structure of the default overlay network intact. In anexpressway, nodes that are situated near gateways or routers,have good fan-outs, have good forwarding capacity and/or arehighly available establish connections with each other in a waythat preserves physical proximity. These nodes collectivelyform an expressway that is used to improve routing perfor-mance by propagating route information. To our knowledge,our expressway is the first unconstrained auxiliary networkthat takes full advantage of heterogeneity and proximity inthe underlying network.The
View Full Document
Unlocking...