Brocade Landmark Routing on Overlay Networks CS262A Fall 2001 Yitao Duan Ling Huang University of California Berkeley duan cs berkeley edu hlion newton berkeley edu Abstract Peer to peer networks offer attractive features such as decentralized computing fault tolerance sharing and aggregating of resources e g SETI home A common and limiting assumption on peer to peer network is that in order to achieve fair sharing and fault tolerance all computers in the network should be considered equal and there should be no server nor explicit structuring in the network Many theories and algorithms used by existing peer to peer infrastructures such as Tapestry 12 Chord 9 Pastry 7 and CAN 4 comply with this tenet However such systems often show sub optimal performance due to the asymmetry of nodes in reality and the lack of structure among them In this paper we argue that a peer to peer system does not have to operate in a pure peer to peer fashion to obtain the advantages mentioned above We believe that such system can benefit from some form of internal organization and differentiation among its nodes thus enjoying the efficiency of a well organized system while still providing users with the P2P features As a proof of our belief we proposed and simulated Brocade a secondary overlay to be layered on top of these systems Brocade exploits knowledge of underlying network characteristics and recognizes the differences among the nodes 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 the benefits of scalable wide area lookup services for Internet applications These architectures make use of name based routing to route requests for objects or files to a nearby replica Applications built on such systems 2 3 8 depend on reliable 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 are uniform in resources such as network bandwidth and storage They also make no differentiation with regard to each node s position in the network In addition the routing algorithms used in these systems are decoupled from the underlying network topology The result is messages being routed on the overlay with minimum consideration to actual network 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 nodes while leaving the more powerful ones under utilized and 2 it doesn t take advantage of the aggregated knowledge about the network structure it could have used While the first point seems obvious the second one deserves some elaboration It comes from the intuition that a system is more efficient if its components even though they are equal in power are organized For example a B tree offers far superior searching performance than sequential scan because elements are organized in the first case The same argument applies to network It would be clear in the following sections that even though we do not assume the existence of any powerful nodes we could still benefit from better organization In this project we propose Brocade a secondary overlay to be layered on top of these systems Brocade exploits knowledge of underlying network characteristics and recognizes the differences among the nodes The secondary overlay builds a location layer between supernodes nodes that are situated near network access points such as gateways to administrative domains By associating local nodes with their nearby supernode messages across the wide area can take advantage of the highly connected network infrastructure between these supernodes to shortcut across distant network domains greatly improve point to point routing distance and reducing overall network bandwidth usage In this paper we present the initial architecture of a Brocade secondary overlay on top of a Tapestry network and demonstrate 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 we discuss related and future work and conclude in Section 5 2 Tapestry Routing and Location Our architecture leverages Tapestry an overlay location and routing layer presented by Zhao Kubiatowicz and Joseph in 12 The Tapestry location and routing infrastructure is one of several recent projects exploring the value of widearea decentralized location services 4 7 9 It allows messages to locate objects and route to them across an arbitrarilysized network while using a routing map with size logarithmic to the network namespace at each hop We present here a brief overview of the relevant characteristics of Tapestry A detailed discussion of Tapestry algorithms its faulttolerant mechanisms 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 forward messages and client origins of requests Also objects and nodes have names independent of their location and semantic properties in the form of random fixed length bit sequences represented by a common base e g 40 Hex digits representing 160 bits The system assumes entries are roughly evenly distributed in both node and object namespaces 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 the destination ID digit by digit e g 8 98 598 4598 where s represent wildcards This approach is similar to longest prefix routing in the CIDR IP address allocation architecture 5 A node N has a neighbor map with multiple levels where each level represents a matching suffix up to a digit position in the ID A given level of the neighbor map contains a number of entries equal to the base of the ID where the ith entry in the jth level is the ID and location of the closest node which ends in i suffix N j 1 For example the 9th entry of the 4th level for node 325AE is the node closest to 325AE in network distance which ends in 95AE When routing the nth hop shares a