DOC PREVIEW
Berkeley COMPSCI 262A - Brocade - Landmark Routing on Overlay Networks

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Brocade: Landmark Routing on Overlay Networks CS262A Fall 2001 Yitao Duan, Ling Huang University of California, Berkeley [email protected], [email protected] 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 shortcutacross 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 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 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 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 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


View Full Document

Berkeley COMPSCI 262A - Brocade - Landmark Routing on Overlay Networks

Download Brocade - Landmark Routing on Overlay Networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Brocade - Landmark Routing on Overlay Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Brocade - Landmark Routing on Overlay Networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?