Better by a HAIR: Hardware-Amenable Internet Routing

Better by a HAIR: Hardware-Amenable Internet Routing

Better by a HAIR: Hardware-Amenable Internet Routing Brent Mochizuki University of Illinois at Urbana-Champaign Joint work with: Firat Kiyak (Illinois) Eric Keller (Princeton) Matthew Caesar (Illinois) 1 Router Design Today Control Plane Maintains routing table Implemented in software

Data Plane Forwards packets Implemented in hardware 2 Routing Faces Scaling Challenges Routers are experiencing scaling challenges

The Internet is still growing New protocols and IPv6 require larger address spaces Large bursts of updates occur when links go down or come back up 3 Some Workarounds Use timers (MRAI) to mask instability Slows convergence leading to longer instances of black holes and routing loops Use flap damping to disallow less stable routes

Limit Harms availability, leading to black holes which routes are advertised Places constraints on policies 4 Our Approach Routing is conventionally done in software Hardware has clear performance benefits Specialized circuits would allow routing to be done more quickly Hardware is inherently parallel We

investigate using the extreme design point of an all-hardware router Target is FPGA (reprogrammable hardware) 5 Implementing BGP in Hardware A full-hardware router can speed up BGP processing, however: It seems that BGP was designed to be processed in software The protocol makes it difficult to process in hardware

Our design is very complex Slow processing speed 6 Implementing BGP in Hardware Why is it complex to implement BGP in hardware? What parts of the design would perform poorly? Can we design a new protocol with the functionality of BGP without these

problems? 7 Sources of Complexity in BGP 1. No total ordering of routes Computing the best route Must compare each advertised route Route 1 Route 2 Route 3 BGP allows the MED attribute Every route must be considered when choosing

the best route (instead of the advertised route and the previously-best route) 8 Sources of Complexity in BGP 2. IP Prefix Addressing Translating an IP prefix to a physical memory address in the routing table (RIB) is difficult to implement Trie lookup structure Not a regular structure Requires extra memory IP Lookup

Memory Address RIB 9 Sources of Complexity in BGP (cont.) 3. Long and variable length fields Variable length fields add processing complexity Parser states are not predictable since

Depends on the length of variable-length fields Depends on the presence of optional fields Tradeoff between design complexity and performance 10 HAIR: Hardware-Amenable Internet Routing 1.Provides for a total ordering of routes 2.Simplifies route lookup by using virtual addressing instead of IP addresses 3.Uses shorter, fixed-length fields 11 HAIR Total ordering of routes HAIR

avoids the MED ordering problem The best route can be chosen by comparing only the newly advertised and previously-best routes BGP HAIR New Route New Route Best Route Best Route Route 3 Route 4 Route 5 Best Route Route 3

Best Route Route 4 Route 5 12 HAIR Destination Address HAIR operates on a virtual address space Each destination network is enumerated with a unique fixed identifier on a global scale This identifier is used to directly index into the RIB BGP IP Lookup HAIR Destination IP:

12.0.0.0/24 1 1 0 Memory Address RIB Virtual Address RIB 13 HAIR Fixed and Shorter Length Fields Requiring

fixed length fields allows a very simple parsing design The parser state is predictable This makes processing speeds predictable as well BGP HAIR Amt Parsed < Length clk Length Parse clk END

Parse0 clk clk ParseN clk END 14 HAIR Path Attribute Labels Policy decides which route is best by comparing path attributes Each router will only see a relatively small number of unique sets of path attributes We use labels to enumerate each of these

sets Attributes: Origin = 1 (EGP) LocalPref = 50 Label Table Label: 001 15 HAIR Path Attribute Labels Each set of labels is defined locally Label translation performed at each router to avoid collisions and fragmentation of the label space Inbound Label

Label Table Outbound Label 16 HAIR Path Attribute Labels Since there is a total ordering of routes, each label can be ranked by routing preference Computing the best route is as easy as comparing ranks 17 Advertisement in BGP BGP Update

Advertise: 12.1.1.0/24 Attributes: Origin = 1 (EGP) LocalPref = 50 IP Lookup Memory Address RIB Route Info Best Route Logic

New Route 18 Label Advertisement in HAIR Label Mapping Label Update Label Table Inbound Label Label Packet Generator Label Outbound Packet Label

Label Translation HAIR Label Update Label: 002 Attributes: Origin = exterior LocalPref = 50 19 Route Advertisement in HAIR Inbound Label Virtual Address Label Translation

Outbound Label Rank RIB Route Info. New Route HAIR Route Update Advertise: 3128 Label: 002 20 Analysis - Methodology Ran update traces on 3 designs:

Quagga open-source software router Hardware implementation of BGP processor 3GHz CPU 125MHz NetFPGA target Hardware implementation of HAIR processor 125MHz NetFPGA target 21 Analysis Performance Metrics

Compare throughput High throughput handles bursts well Compare delay Low delay means faster convergence 22 Analysis - Throughput BGP in Hardware increases throughput by up to 3

orders of magnitude. HAIR increases throughput by 1 more order of magnitude. 23 Analysis - Delay BGP in Hardware reduces delay by 4 orders of magnitude HAIR reduces delay by 1 more

24 Analysis Throughput higher and delay lower for hardware designs Due to lack of OS, increased parallelization, and direct access to memory Performance is even better for HAIR Our changes to the protocol not only make it easier to implement, but also improve performance 25 Conclusions We challenge the assumption that routing protocols must be processed in software

BGP in hardware is difficult to implement We propose HAIR, a hardware-amenable protocol with similar functionality to BGP Allows for simple and high-performing hardware designs Future Work: Determining optimal division of labor between hardware and software in router design, examining other protocols 26

Recently Viewed Presentations

  • DISTRIBUTED OBJECTS AND REMOTE INVOCATION DISTRIBUTED OBJECTS AND

    DISTRIBUTED OBJECTS AND REMOTE INVOCATION DISTRIBUTED OBJECTS AND

    Arial Wingdings Times New Roman StarSymbol Office Theme Slide 1 Topics Introduction Introduction Introduction Introduction Introduction Introduction Introduction Introduction Introduction Introduction Introduction Basic Communication Primitives External Data Representation & Marshalling External Data Representation & Marshalling Remote Method ...
  • 2014 Loss of Load Probability Assessment for NERC

    2014 Loss of Load Probability Assessment for NERC

    Then, the interface limits between the bubbles modeled in the 2014 LOLP study were estimated by subtracting the MW amount of the STP units from the AC transfer limit since the LOLP study assumed the STP units inside the Houston...
  • GSA Fleet

    GSA Fleet

    GSA Fleet - On June 28, 2015, GSA Fleet reorganized from a regional structure to a zonal structure. Each zone has similar vehicle numbers and will help to make today's GSA Fleet the best ever by providing consistency to our...
  • Directly Rendering Spectral Elements using Texture Shaders Bernard

    Directly Rendering Spectral Elements using Texture Shaders Bernard

    Texture Shader - a programmable part of the hardware that takes texture coordinates and maps them to colors on a texture map. Overview We directly render high-order polynomials using Texture Shaders on modern graphics hardware such as nVidia's GeForce3.
  • A Guide to Providing Ethical and Legal References

    A Guide to Providing Ethical and Legal References

    For a statement to be defamatory, it must be shown that substantial evidence exists that the supervisor knowingly lied or had no idea (reckless disregard for the truth) whether the statement was true. Reckless disregard for the truth includes a...
  • &quot;The hero of the story is a narrative itself. . . . Narrative ...

    "The hero of the story is a narrative itself. . . . Narrative ...

    Creswell (Qualitative Inquiry & Research Design) speaks of Restorying. In our discipline, we analyze and construct narratives. To Challenge: "the Harvard narrative" To Critique: "the racial difference narrative" To Give Meaning: "the assessment narrative" What do we teach FYC students...
  • Infection Control Practices to Improve Patient Care

    Infection Control Practices to Improve Patient Care

    Infection Control Timeline Hotel-Dieu : Paris hospital founded in the 7th century Infection Control Timeline History: Ignaz Semmelweis At the Vienna Lying-in Hospital Women who delivered on the street had less risk of developing puerperal fever Much higher risk of...
  • SCITT Day 6 2018 GEOMETRY: IDENTIFYING KEY FEATURES

    SCITT Day 6 2018 GEOMETRY: IDENTIFYING KEY FEATURES

    SCITT Day 6 2018 GEOMETRY: IDENTIFYING KEY FEATURES OF SHAPE AND SPACE Resources Shapes 2d 3d Card scissors glue Squared paper Mathematical equipment