Idea on Routing and Forwarding

Today

• Client looks up IP address for URL using DNS
• Client generates IP-Packet for data transfer
• Routers use forwarding table to retrieve next hop for IP destination address
  • Forwarding table is populated by a routing protocol (I just focus on inter-domain routing here: (e)BGP)
  • BGP builds an AS-path for every prefix which is announced by any BGP router
  • Policies restrict the announcement of prefixes and the choice of shortest AS-path
  • Paths of equal length are sorted by a weight/MED
  • Shortest Path with lowest weight/MED goes into the forwarding table
  • Currently we see up to 2*10⁵ routes in the forwarding table due to "more specifics" caused by multi-homing
    • Global anycast can not be supported

Idea

Basis: Use AS-like IDs as locators and give only one(!) IP address to every node

• Prerequisite:
  • Every node is connected to / associated with one or more IP service providers
  • Each IP service provider has a unique ID
    • Assumption: an AS is a cohesive domain; a splitted AS gets a multiple more specific identifiers for its subparts
  • Eliminate the need to assign multiple IP addresses to one node
  • The IP address does not have to be part of the IP address range of the provider, since the IP address is not a locator anymore

• Hopes:
  • To reduce the size of the routing and forwarding table
    • Thereby the convergence phase shortens
  • To delay the path decision as long as possible for increased resilience
    • Exploit redundancy at the receiver side
    • Having multiple options increases resilience in the case of a challenge, i.e. link breaks, congestion, etc.
  • Ease mobility: preserve your fixed IP address and only change your locator
    • change DNS entry (dynamic DNS updates which must be trusted)
    • update the locator for existing flows
  • Enable Anycast
    • All anycast responders have a common IP address
    • DNS returns the locators of all anycast responders

• Fears:
  • Complicate the forwarding process (see Outline)
    • Multiple looks per packet might be needed
    • Path decision includes elimination of other possible paths
  • Using different forwarding paths for packets of a flow cause packet reordering (TCP throughput drops) and makes path delay measurements complicated (RTT calculation over an unknown set of paths)
  • How to realize TE with this approach? A provider today can announce more specific routes on some BGP speakers than on others.
  • Are header modifications feasible in high speed environments?
  • AS path length is not a suitable metric for routing; it only guarantees a loop-free path

Outline

• Client looks up IP address and AS ID using DNS
  • If a node is connected to more than one provider all AS-like IDs are returned by DNS
• Client generates the IP packet for data transfer and prepends an ID header containing one or more provider IDs
  • Note: no changes to IP are needed for this approach
• A router receiving a packet with one provider ID in the ID header forwards the packet to this provider
  • Paths are calculated by a path vector algorithm using a modified version of BGP
  • mBGP routers announce their provider ID to all neighbours according to its policies
  • When the packet reaches its destination provider the ID header is striped and IP forwarding is used to get the packet to the destination IP
• A router receiving a packet with more than one provider ID in the AS header:
  • Selects an provider ID and all provider IDs with the same next hop provider, removes all other provider IDs from the ID header, and forwards the packet to the next hop provider
  • Special cases:
    • Selects one provider ID, remove all other provider IDs from the ID header, and use the above scheme
    • router has only one upstream provider and leaves ID header unchanged

Example

The figure shows the three possible paths from the sender (S) to the receiver (R). S is single-homed at ASX. R is multi-homed at AS1, AS2, and AS3.

If S wants to send an IP-packet to R the DNS lookup would return the IP-address of R and a list of locators (AS1, AS2, AS3). Sends sends the packet to ASX. The modified forwarding process of a router in ASX gets two next-AS hops from the forwarding table: AS3 via the lower path (it is depicted dotted since ASx and AS3 might be connected directly or by other non-shown ASes) or AS1 and AS2 via the upper path. Let's assume the router decides to go for the upper path. He removes AS3 from the list of locators and sends the packet in direction of ASY. At ASY the same process is executed and one of the remaining locators is removed from the packet. If the packet finally reaches the remaining locator AS the router will uses IP-routing to forward the packet to the receiver.