Brocade Landmark Routing on Overlay Networks To P2P or not to P2P http www cs berkeley edu duan prjs cs262 CS262A Fall 2001 Yitao Duan and Ling Huang duan cs berkeley edu hlion newton berkeley edu Motivation 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 Constraints Brocade 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 network Brocade Architecture Brocade Original Route Brocade Route AS 3 AS 1 S D AS 2 P2P Network 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 A small cache storing most frequently used nodes in its cover set will do the trick Destination is in my cover set No Send to supernode Yes Ordinary Tapestry Routing Query locality will make hit rate high Consequences of mistakes aren t expensive Simulation Results Fig 1 Hops Based RDP Fig 2 Aggregate bandwidth used per message Optimizing 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 Filter Brocade link latency Ordinary link latency 8 1 Conclusion and Future work 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 References 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 35 42