HLP: A Next Generation Inter-domain Routing Protocol
Lakshminarayanan Subramanian, Matthew Caesar, Cheng Tien Ee, Mark
Handley, Morley Mao, Scott Shenker, Ion Stoica

SIGCOMM 2005

* problem

- BGP has many deficiencies
  - scalability: large routing tables
  - convergence and stability: many routes flap continuously, convergence
    times are large
  - isolation: many routing events are visible globally

- deficiencies are due to flat routing, genreic policies, prefix-based
  routing, path-vector routing

* solution

- HLP - hybrid link-state and path-vector protocol
- hierarchical routing based on AS instead of prefixes, optimize for common
  policies, with others treated as exceptions

* details

- design issues
  - information hiding is good - helps reduce visibility of routing events
    and this leads to faster stabilization
  - default policy based on two common guidelines
    1) don't forward routes advertised by one peer or provider to another
       peer or provider
    2) prefer customer routes over peer or provider routes
  - route to AS instead of prefixes, which reduces churn
    - mapping from AS to address is fairly stable, while topology changes
      that affect prefixes are fairly dynamic
  - hybrid routing helps reduce visibility of routing changes and provides
    greater stability
    - path vector has long convergence times
    - distance vector hides too much, hinders policy routing
    - link state has fast convergence but provides complete visibility
    
- HLP
  - follow the AS hierarchy
    - an AS that is not a customer of another AS is at the top of a routing
      hierarchy
    - no cycles in provider-customer hierarchy, otherwise treat certain
      links differently to break the cycle
    - use link-state routing at the granularity of AS's inside the AS hierarchy
    - use path vector only among these top-level AS's
      - use fragmented AS paths at this level
      - omit the portion of the AS path within an AS hierarchy
      - include a cost metric
  - Figure 2 example
    - link change occurs within an AS hierarchy
    - at the top level, simply modify the cost without changing the AS path
    - if no other path exists, withdraw the route

  - can prove that HLP avoids routing loops and count to infinity given
    some basic assumptions

  - explicit information hiding
    - needed for scalability
    - propagate a route update only when necessary
    - three cases
      - minor cost changes of customer routes across peering links
      - minor cost changes of peer routes to customers
      - hiding failure of one of several parallel peer links between a pair
        of AS's
    - see Figure 3

  - by limiting the types of information hiding, can prove that HLP still
    avoids routing loops and count to infinity

  - complex relationships
    - sibling relationships
    - two AS's with different relationships for different destinations or
      at different geographical locations
    - modeled explictly as peer-peer links

  - policy variations
    - export policy exceptions: prefer to forward advertisements from one
      provider/peer to another provider/peer
    - prefer customer exception: prefer a non-customer route over a customer
      route
    - should be very rare -- 1% of policies in current BGP
    - for export policy execptions
      - convert LSA into an FPV
      - Figure 4
    - for prfer customer exceptions
      - withdraw customer route to providers and peers
      - propagate an FPV to customers with desired route - same as
        if destination was not a customer

- analysis
  - 400 fold reduction in churn rate compared to BGP
  - for 50% of inter-AS links, HLP isolates events to a region 100 times
    smaller than BGP
  - churn and isolation improve as multihoming increases
  - improves worst-case convergence time by constraining length of FPVs
    - convergence time is lineary for about 90% of destinations

- traffic engineering
  - prefix-level route selection
    - can do it easily within or between AS hierarchies
    - can only choose from available customer routes
    - no advertisements to peers or providers
    - done statically, rather than dynamically like in BGP
    - see Figure 10

  - cost-based inbound traffic engineering
    - in BGP, an AS that wants to make a path less preferred will often
      prepend its AS number to the path multiple times!
    - in HLP, simply manipulate costs of paths

- internal HLP

- HLP implementation
  - uses more than 90% of XORP BGP code
 
- transition plan

- conclusions