DOC PREVIEW
Berkeley COMPSCI 294 - Exploiting Routing Redundancy via Structured Peer-to-Peer Overlays

This preview shows page 1-2-21-22 out of 22 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 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 22 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 22 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 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Exploiting Routing Redundancy via Structured Peer-to-Peer OverlaysContentsMotivationSlide 4Resilient Overlay RoutingBasicsFailure DetectionSlide 8How many paths?Failure RecoverySlide 11PowerPoint PresentationRouting Redundancy MaintenanceInterface with legacy applicationsTunnelingRedundant Proxy ManagementDeploymentSimulation Result SummarySlide 19Microbenchmark SummarySelf RepairComparison1Exploiting Routing Redundancy via Structured Peer-to-Peer OverlaysSep. 17, 2003Byung-Gon Chun2Contents•Motivation•Resilient Overlay Routing•Interface with legacy applications•Evaluation•Comparison3Motivation•Frequent disconnection and high packet loss in the Internet •Network layer protocol’s response to failures is slow Quick recovery from route failures using structured P2P overlay4Motivation5Resilient Overlay Routing•Basics•Route failure detection•Route failure recovery•Routing redundancy maintenance6Basics•Use the KBR of structured P2P overlays [API]•Backup links maintained for fast failover•Proximity-based neighbor selection•Proximity routing with constraints•Note that all packets go through multiple overlay hops.7Failure Detection•Failure recovery time ~ failure detection time when backup paths are precomputed•Periodic beaconing–Backup link probe interval = Primary link probe interval*2•Number of beacons per period per node - log(N) vs. O(<D>) for unstructured overlay•Routing state updates – log2Nvs. O(E) for link state protocol8Failure Detection•Link quality estimation using loss rate–Ln = (1-alpha) Ln-1 + alpha Lp •TBC - metric to capture the impact on the physical network –TBC = beacons/sec * bytes/beacon * IP hops•PNS incurs a lower TBCStructured overlays can do frequent beaconing for fast failure detection ?9How many paths?•Recall the geometry paper–Ring - (log N)! Tree – 1•Tree with backup links10Failure Recovery•Exploit backup links•Two polices presented in [Bayeux]•First reachable link selection (FRLS)–First route whose link quality is above a defined threshold11Failure Recovery•Constrained multicast (CM)–Duplicate messages to multiple outgoing links–Complementary to FRLS. Triggered when no link meets the threshold–Duplicate message drop at the path-converged nodes•Path convergence !1213Routing Redundancy Maintenance•Replace the failed route and restore the pre-failure level of path redundancy•Find additional nodes with a prefix constraint•When to repair? –After certain number of probes failed–Compare with the lazy repair in Pastry• Thermodynamics analogy – active entropy reduction [K03]14Interface with legacy applications•Transparent tunneling via structured overlays15Tunneling•Legacy node A, B, Proxy P•Registration–Register an ID - P(A) (e.g. P-1)–Establish a mapping from A’s IP to P(A)•Name resolution and Routing–DNS query–Source daemon diverts traffic with destination IP reachable by overlay–Source proxy locates the destination overlay ID–Route through overlay–Destination proxy forwards to the destination daemon16Redundant Proxy Management•Register with multiple proxies•Iterative routing between the source proxy and a set of destination proxies•Path diversity17Deployment•What’s the incentive of ISPs?–Resilient routing as a value-added service•Cross-domain deployment–Merge overlays–Peering points between ISP’s overlays•Hierarchy - Brocade18Simulation Result Summary•2 backup links•PNS reduces TBC (up to 50%)•Latency cost of backup paths is small (mostly less than 20%)•Bandwidth overhead of constrained multicast is low (mostly less than 20%)•Failures close to destination are costly.•Tapestry finds different routes when the physical link fails.19Small gap with2 backup links?20Microbenchmark Summary•200 nodes on PlanetLab•Alpha ~ between 0.2 and 0.4•Route switch time –Around 600ms when the beaconing period is 300ms•Latency cost ~ 0–Sometimes reduced latency in the backup paths – artifacts of small network•CM –Bandwidth*Delay increases less than 30%•Beaconing overhead–Less than 7KB/s for beacon period of 300ms21Self Repair22Comparison•RON–Use one overlay hop (IP) for normal op. and one indirect hop for failover–Endpoints choose routes–O(<D>) probes D=O(N)–O(E) messages E=O(N2)–Average of k samples–Probe interval 12s–Failure detection 19s–33Kbps probe overhead for 50 nodes (extrapolation: 56kbps around 70 nodes)•Tapestry ( L=3 )–Use (multiple) overlay hops for all packet routing–Prefixed routes–O(logN) probes–O(log2N) messages–EWMA–Probe interval 300ms–Failure detection 600ms–< 56Kbps probe overhead for 200


View Full Document

Berkeley COMPSCI 294 - Exploiting Routing Redundancy via Structured Peer-to-Peer Overlays

Documents in this Course
"Woo" MAC

"Woo" MAC

11 pages

Pangaea

Pangaea

14 pages

Load more
Download Exploiting Routing Redundancy via Structured Peer-to-Peer Overlays
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 Exploiting Routing Redundancy via Structured Peer-to-Peer Overlays 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 Exploiting Routing Redundancy via Structured Peer-to-Peer Overlays 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?