Transcript talk
Slick Packets Giang Nguyen†, Rachit Agarwal†, Junda Liu‡, Matthew Caesar†, P. Brighten Godfrey†, Scott Shenker‡ † University of Illinois at Urbana-Champaign ‡ University of California, Berkeley SIGMETRICS 2011 Approaches to packet routing • Network-controlled routing (NCR): the network controls the route – Analogy: taking a bus, one travels route determined by transit agency – Standard IP next-hop routing/forwarding • Source-controlled routing (SCR): users have some or total control of the route – Analogy: when driving, one determines own route – More flexible enables better performing routes, increases network provider competition, etc. 2 Failures in the network • Daily occurrences: 60% of the time, some link fails in next 10 minutes [Iannaccone02] • Cause “routing convergence” tens of seconds of packet loss while underlying network remains connected [Kushman07, Wang06] • Adversely affect real-time applications (e.g., VoIP, video conferencing, online games) 3 Fast failure reaction • Within network-controlled routing paradigm: – Reduce routing convergence period – “Fast reroute” : use alternate paths to forward packets during routing convergence (e.g., MPLS Fast Reroute, SafeGuard, R-BGP) • Within source-controlled routing paradigm: – Sources monitor path quality: too low switch path (e.g., Path Splicing, Pathlet Routing) • Takes on order of RTT to react – No “fast reroute” technique 4 SlickPackets • Source-controlled routing protocol with alternate paths in packet headers • Best of both worlds – Flexibility of source-controlled routing – Fast failure reaction of network-controlled routing using alternate paths 5 Design 6 Design overview 7 Design overview R2 Src R1 R5 R3 Dst R4 8 Key steps • Dissemination of network map – Leverage past work (NIRA, Pathlet Routing) • Selection of the forwarding subgraph • Encoding of forwarding subgraph in packet header • Forwarding of packet 9 Forwarding subgraph (FS) • Represents subset of network along which routers can forward packet – Is a DAG to avoid forwarding loops • Source may select FS with enough redundancy to avoid failures • Use case: shortest paths & avoid single-link failures – Selects a shortest “primary path” – Selects for each node on primary path a shortest “alternate path” to destination in case its primary nexthop link fails 10 FS selection example R2 R2 R1 R5 R3 R1 R5 R4 Network map Forwarding subgraph Suppose s selects R1R2R5 as primary path 11 FS selection example R2 R2 R1 R5 R3 R4 Network map R1 R5 R4 Forwarding subgraph For R1, s selects R1R4R5 as alternate path 12 FS selection example R2 R2 R1 R5 R3 R4 Network map R1 R5 R4 Forwarding subgraph For R2, s selects R2R4R5 as alternate path 13 Forwarding subgraph encoding Designed two formats • “Direct”: directly serializes the forwarding subgraph – A more general format • “Default”: encodes “segments,” one for each primary node – More efficient in most of cases we evaluate 14 Failure notification • So far, SlickPackets enables packets to slip around failed links – But packets reach failure might be sub-optimal • “Reactive” notification – Router adjacent to failed link sends control message to source of packet that tries to use link – Or, destination can notify source end-to-end 15 Evaluation 16 Encoding size eval methodology Topologies: • Latency-annotated Sprint ISP (315 nodes, 972 links) • Unweighted AS-map of the Internet (>30,000 nodes, >75,000 links) • Unweighted router-level map of the Internet (>190,000 nodes, >600,000 links) 17 Encoding size for AS-level map 1 CDF 0.8 0.6 0.4 • 99% less than 26 bytes 0.2 • Maximum of 50 bytes 0 0 10 • Reasonable for large packets 30 40 20 Encoding size (bytes) 18 Failure reaction simulation • Metric: packet stretch (= ratio of packet life time to latency of shortest available path) • Simulation run for each link: – All nodes send packets to all other nodes every 1ms – Fail the link evaluate all connected src-dst pairs • Protocols: “Vanilla” source routing, SafeGuard, SlickPackets 19 Vanilla source routing ICMP-style control packet Data packet Src • Dropped packets resent when src knows of failure Dst Failed link 20 SafeGuard Control packet (i.e., LSA) Data packet Src • No dropped packets Dst • All routers upstream from failure redirect packets 21 SlickPackets ICMP-style control packet Data packet Src • No dropped packets Dst • Only router adjacent to failure redirects packets 22 Average stretch for Sprint ISP Average packet stretch 6 5 4 Vanilla Source Routing 3 2 1 1 51 101 151 201 Packet number 251 301 23 Average stretch for Sprint ISP Average packet stretch 1.1 1.08 1.06 Vanilla Source Routing 1.04 SafeGuard 1.02 1 0 50 100 150 200 Packet number 250 300 24 Average stretch for Sprint ISP Average packet stretch 1.1 1.08 1.06 Vanilla Source Routing SafeGuard SlickPackets achieves packet 1.04 SlickPackets stretch comparable to 1.02 SafeGuard, an NCR protocol 1 0 50 100 150 200 Packet number 250 300 25 Conclusion SlickPackets • Is a source-controlled routing protocol • Enables fast reroute • Specifies alternate paths in packet header • Has reasonable packet header overhead Future work: • Hardware implementation • Congestion as a failure 26