Brocade: Landmark Routing on Overlay NetworksCS262A Fall 2001Yitao Duan, Ling HuangUniversity of California, [email protected], [email protected] networks offer attractive features such as decentralized computing, fault tolerance, sharing and aggregatingof resources (e.g., SETI@home). A common (and limiting) assumption on peer-to-peer network is that, in order toachieve fair sharing and fault tolerance, all computers in the network should be considered equal and there should be noserver nor explicit structuring in the network. Many theories and algorithms used by existing peer-to-peerinfrastructures (such as Tapestry [12], Chord [9], Pastry [7] and CAN [4]) comply with this tenet. However, suchsystems often show sub-optimal performance due to the asymmetry of nodes in reality and the lack of structure amongthem.In this paper, we argue that a peer-to-peer system does not have to operate in a pure peer-to-peer fashion to obtainthe advantages mentioned above. We believe that such system can benefit from some form of internal organization anddifferentiation among its nodes, thus enjoying the efficiency of a well-organized system, while still providing users withthe P2P features.As a proof of our belief, we proposed and simulated Brocade, a secondary overlay to be layered on top of thesesystems. Brocade exploits knowledge of underlying network characteristics and recognizes the differences among thenodes. Simulations were run on the GT-ITM [11] transit stub topology and showed encouraging results.1 Introduction Existing peer-to-peer overlay infrastructures such as Tapestry [12], Chord [9], Pastry [7] and CAN [4] demonstrated thebenefits of scalable, wide-area lookup services for Internet applications. These architectures make use of name-basedrouting to route requests for objects or files to a nearby replica. Applications built on such systems [2, 3, 8], depend onreliable and fast message routing to a destination node, given some unique identifier.Due to the theoretical approach taken in these systems, however, they assume that most nodes in the system areuniform in resources such as network bandwidth and storage. They also make no differentiation with regard to eachnode’s position in the network. In addition, the routing algorithms used in these systems are decoupled from theunderlying network topology. The result is messages being routed on the overlay with minimum consideration to actualnetwork topology and differences between node resources.In reality, nodes in a network are asymmetric in terms of processing power, network bandwidth and connectivity.Given this, a flat, uniform operation model suffers from two aspects: (1) it tends to overload the less powerful nodeswhile leaving the more powerful ones under utilized and (2) it doesn’t take advantage of the aggregated knowledgeabout the network structure it could have used. While the first point seems obvious, the second one deserves someelaboration. It comes from the intuition that a system is more efficient if its components, even though they are equal inpower, are organized. For example, a B+ tree offers far superior searching performance than sequential scan becauseelements are organized in the first case. The same argument applies to network. It would be clear in the followingsections that even though we do not assume the existence of any powerful nodes, we could still benefit from betterorganization.In this project, we propose Brocade, a secondary overlay to be layered on top of these systems. Brocade exploitsknowledge of underlying network characteristics and recognizes the differences among the nodes. The secondaryoverlay builds a location layer between "supernodes," nodes that are situated near network access points, such asgateways to administrative domains. By associating local nodes with their nearby "supernode," messages across thewide-area can take advantage of the highly connected network infrastructure between these supernodes to shortcutacross distant network domains, greatly improve point-to-point routing distance and reducing overall networkbandwidth usage.In this paper, we present the initial architecture of a Brocade secondary overlay on top of a Tapestry network, anddemonstrate its potential performance benefits by simulation. Section 2 briefly describes Tapestry routing and location,Section 3 describes the design of a Tapestry Brocade, and Section 4 present preliminary simulation results. Finally, wediscuss related and future work and conclude in Section 5.2 Tapestry Routing and LocationOur architecture leverages Tapestry, an overlay location and routing layer presented by Zhao, Kubiatowicz and Josephin [12]. The Tapestry location and routing infrastructure is one of several recent projects exploring the value of wide-area decentralized location services [4, 7, 9]. It allows messages to locate objects and route to them across an arbitrarily-sized network, while using a routing map with size logarithmic to the network namespace at each hop. We present herea brief overview of the relevant characteristics of Tapestry. A detailed discussion of Tapestry algorithms, its faulttolerantmechanisms and simulation results can be found in [12].Each Tapestry node or machine can take on the roles of server (where objects are stored), router (which forwardmessages), and client (origins of requests). Also, objects and nodes have names independent of their location andsemantic properties, in the form of random fixed-length bit-sequences represented by a common base (e.g., 40 Hexdigits representing 160 bits). The system assumes entries are roughly evenly distributed in both node and object names-paces, which can be achieved by using the output of secure one-way hashing algorithms, such as SHA-1 [6].2.1 Routing Layer Tapestry uses local routing maps at each node, called neighbor maps, to incrementally route overlay messages to thedestination ID digit by digit (e.g., ***8 => **98 => *598 => 4598 where *'s represent wildcards). This approach issimilar to longest prefix routing in the CIDR IP address allocation architecture [5]. A node N has a neighbor map withmultiple levels, where each level represents a matching suffix up to a digit position in the ID. A given level of theneighbor map contains a number of entries equal to the base of the ID, where the ith entry in the jth level is the ID