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

Unformatted text preview:

Brocade: Landmark Routing on Overlay NetworksMotivationBrocade: Discrimination JustifiedBrocade ArchitecturePowerPoint PresentationCase Study - Brocade On TapestryGet onto the Super HighwaySlide 8Simulation ResultsOptimizing Object Location on BrocadeConclusion and Future workReferencesBrocade: Landmark Routing on Overlay NetworksTo P2P or not to P2P?http://www.cs.berkeley.edu/~duan/prjs/cs262/CS262A Fall 2001Yitao Duan and Ling [email protected], [email protected]•Problems with existing P2P Network–Constrained by the theoretical approach adopted, nodes are treated uniformly[1, 2, 3, 4]–Routing algorithms are decoupled from underlying topology and node capability–Result: inefficient routing•Reality: Nodes are not born equal–Bandwidth, Connectivity, Storage, Processing Power.–Administrative ConstraintsBrocade: Discrimination Justified•A philosophy: A system is more efficient when it is organized – e.g., IP routing on Internet •Respect the differences and take advantage of those that are more powerful – Supernodes!–Fast/well-connected/situated near network access points–Supernodes have better knowledge of underlying network characteristics. Benefit from aggregation.•Construct a hierarchy out of flat networkBrocade ArchitectureAS-2P2P NetworkAS-1AS-3BrocadeS DOriginal RouteBrocade Route• Overlay nodes are grouped by their supernodes – Cover Set• Supernodes treat their overlay nodes as objects that they possess• Routing on Brocade => Object Location. Use your favorite mechanism: Tapestry[1], CAN[3], Chord[2], Pastry[4] … • Message filtering: only send inter-domain messages to Brocade.Case Study - Brocade On Tapestry•Tapestry: A novel wide-area fault-tolerant location and routing infrastructure[1]•Construction–Gateway routers or machines close by as supernodes–Existing connections among supernodes as Brocade links•Routing: object location Tapestry style –Each supernode advertises the IDs of overlay nodes in its cover set as IDs of objects it “stores”.–Destination’s supernode can be found using Tapestry’s object location mechanism •Remaining issue: How to get onto Brocade?Get onto the Super Highway•Naïve Brocade: Tapestry routing unchanged. Message gets onto the Brocade overlay if a supernode is encountered on its route.–Advantage: simple, no modification to ordinary nodes. –Disadvantage: possibility of hitting a supernode in Tapestry routing small.•IP Snooping Brocade: Supernodes snoop IP packets to intercept Tapestry messages.–Advantage:•No modification to ordinary nodes.•High possibility of encountering supernodes because supernodes are situated near the edge of local networks. –Disadvantage: Difficult to implement• Directed Brocade: Each overlay node keep info about its supernode and decides by its own whether to send a message to supernode directly.– Feasible: only local information required– Decision Engine:Destination is in my cover set?Send to supernodeOrdinary Tapestry RoutingNoYes• A small cache storing most frequently used nodes in its cover set will do the trick.• Query locality will make hit rate high• Consequences of mistakes aren’t expensiveSimulation ResultsFig 1. Hops Based RDP Fig 2. Aggregate bandwidth used per messageOptimizing Object Location on Brocade• Routing latency could be high if latencies on Brocade links are high and object location on Brocade is not optimized(Fig 3)• Optimization: Bloom Filter - Membership query and group ID problem Fig 3. Weighted latency RDP w/o optimization Fig 4. Weighted latency RDP with Bloom FilterBrocade link latency/Ordinary link latency = 8 : 1•Brocade: powerful idea that can achieve near optimal performance•General enough to be applied to other (P2P) networks•Future research:–Study the effect of different supernodes selection and distribution –Further optimization of object location on Brocade overlay –Latent Brocade•Brocade benefits from aggregation of info•Bias some nodes in the network so they will be favored by others while selecting route - an implicit Brocade Conclusion and Future workReferences[1] ZHAO, B. Y., KUBIATOWICZ, J. D., AND JOSEPH, A. D. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Tech. Rep. UCB/CSD-01-1141, University of California at Berkeley, Computer Science Division, April 2001.[2] STOICA, I., MORRIS, R., KARGER, D., KAASHOEK, M. F., AND BALAKRISHNAN, H. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of SIGCOMM (August2001), ACM.[3] RATNASAMY, S., FRANCIS, P., HANDLEY, M., KARP, R., AND SCHENKER, S. A scalable content-addressable network. In Proceedings of SIGCOMM (August 2001), ACM.[4] ROWSTRON, A., AND DRUSCHEL, P. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Proceedings of IFIP/ACM Middleware 2001 (November 2001).[5] TSUCHIYA, P. F. The landmark hierarchy: A new hierarchy for routing in very large networks. Computer Communication Review 18, 4 (August 1988),


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?