nyman 2002

BANANAS: A Connectionless Approach to Intra- and Inter-Domain Traffic Engineering: 

BANANAS: A Connectionless Approach to Intra- and Inter-Domain Traffic Engineering Hema T. Kaur, Shiv Kalyanaraman, Rensselaer Polytechnic Institute hema@networks.ecse.rpi.edu, shivkuma@ecse.rpi.edu http://www.ecse.rpi.edu/Homepages/shivkuma

Acknowledgements : 

Acknowledgements Biplab Sikdar (faculty colleague) Andreas Weiss (MS) Shifalika Kanwar (MS) Mehul Doshi (MS) Ayesha Gandhi (MS) Niharika Mateti (MS) Also thanks to: Satish Raghunath (PhD) Jayasri Akella (PhD) Hemang Nagar (MS) Work funded in part by DARPA-ITO, NMS Program. Contract number: F30602-00-2-0537

The Question: 

The Question Can we emulate a subset of MPLS properties without signaling? Key: Can we do source routing ? without signaling without variable per-packet overhead being backward compatible with OSPF & BGP allowing incremental network upgrades

Why cannot we do it today? : 

Why cannot we do it today? Connectionless TE today uses a parametric approach: Eg: changing link weights in OSPF, IS-IS or parameters of BGP-4 (LOCAL_PREF, MED etc) Performance limited by the single shortest/policy path Alt: Connection-oriented/signaled approach (eg: MPLS) Complex to extend MPLS-TE across multiple areas. Not a solution for inter-AS issues. MPLS also needs the support of all the nodes along the path

MPLS Signaling and Forwarding Model: 

MPLS Signaling and Forwarding Model Miami Seattle San Francisco (Ingress) New York (Egress) MPLS label is swapped at each hop along the LSP Labels = LOCAL IDENTIFIERS … Signaling maps global identifiers (addresses, path spec) to local identifiers 1321 5 120

Global Path Identifiers: 

Global Path Identifiers Instead of using local path identifiers (Labels in MPLS), we propose the use of global path identifiers

Global Path Identifier: Key Ideas: 

Global Path Identifier: Key Ideas i k j m-1 1 2 w1 w2 wm Key ideas: 1. Swap global pathids instead of local labels! 2. Unlike source-routing that is simple (IP) or signaled (MPLS), upgraded intermediate nodes need to locally compute the valid PathIDs.

Global Path Identifier (continued): 

Global Path Identifier (continued) Path = {i, w1, 1, w2, 2, …, wk, k, wk+1, … , wm, j} Sequence of globally known node IDs & Link weights Global Path ID is a hash of this sequence => locally computable without the need for signaling! Potential hash functions: [j, { h(1) + h(2) + …+h(k)+ … +h(m-1) } mod 2b ]: node ID sum MD5 one-way hash, XOR, 32-bit CRC etc… We propose the use of MD5 hashing of the subsequence of nodeIDs followed by a CRC-32 to get a 32-bit hash value Very low collision (i.e. non-uniqueness) probability

Abstract Forwarding Paradigm: 

Abstract Forwarding Paradigm Forwarding table (Eg; at Node k): [Destination Prefix, ]  [Next-Hop, ] [j, ]  [k+1, ] Incoming Packet Hdr: Destination address (j) & PathID = H{k, k+1, … , m-1} Outgoing Packet Hdr: [j, PathID = H{k+1, … , m-1} ] Longest prefix match + exact label match + label swap! PathID mismatch => map to shortest (default) path, and set PathID = 0 No signaling because of globally meaningful pathIDs!

BANANAS TE: Explicit, Multi-Path Forwarding: 

BANANAS TE: Explicit, Multi-Path Forwarding Explicit Source-Directed Routing: Not limited by the shortest path nature of IGP Different PathIds => different next-hops (multi-paths) No signaling required to set-up the paths Traffic splitting is decoupled from route computation 10 Miami Seattle 9 San Francisco (Ingress) New York (Egress) 18 1 5 4 3 5 IP 4

BANANAS TE: Partial Deployment: 

BANANAS TE: Partial Deployment Only “red” routers are upgraded Non-upgraded routers forward everything on the shortest path (default path): forming a “virtual hop” 10 Miami Seattle 9 San Francisco (Ingress) New York (Egress) 28 1 5 4 30 1 IP 4 27 1 3 2 X

Route Computation: All-Paths Under Partial Upgrades (AP-PU): 

Route Computation: All-Paths Under Partial Upgrades (AP-PU) Assume 1-bit in LSA’s to advertise that an upgraded router is “multi-path capable” (MPC) Two phase algorithm: (assume m upgraded nodes) 1. (N-m) Dijkstra’s for non-upgraded nodes or one all-pairs shortest path (Floyd Warshall) 2. DFS to discover valid paths to destinations. Explore all neighbors of upgraded nodes Explore only shortest-path next-hop of non-upgraded nodes Visited bit set to avoid loops Computes all possible valid paths under PU constraints in a fully distributed manner (global consistency)

Zebra/Click Implementation on Linux (Tested on Utah Emulab): 

Zebra/Click Implementation on Linux (Tested on Utah Emulab) Part of table at node1: (PathID= Link Weights, for simplicity) 3 9 6 7 4 5 8 1 2 10 53 13 75 4 51 45 83 21 3 67 93 5 67 38 51

SSFnet Simulation Results: 

A C B E D SSFnet Simulation Results Flat OSPF Area, 19 Nodes; Only 3 Active-MPC nodes

Heterogeneous Route Computation: 

Heterogeneous Route Computation Goal: Upgraded nodes (eg: A, D, E) can use any route computation algorithm, so long as it computes the shortest (default) path! Eg: k shortest-paths from a given source s to each vertex in the graph, in total time O(E + V log V + kV): lower complexity than AP-PU Issue: Forwarding for k-shortest paths may not exist Need to validate the forwarding availability for paths!

Two-Phase Path Validation Algorithm: 

Two-Phase Path Validation Algorithm Concept: Forwarding for path exists only if the forwarding for each of its suffixes exists. Phase 1 (cont’d): compute {k-shortest} paths for all other upgraded nodes, and 1-shortest paths for non-upgraded nodes. Sort computed paths by hopcount Phase 2: Validate paths starting from hopcount = 1. All 1-hop paths valid. p-hop paths valid if the (p-1)-hop path suffix is valid Throw out invalid paths as they are found Polynomial complexity to discover all valid paths in the network & validation can be done in the background Validation algorithm correct by mathematical induction

Linux/Zebra/Emulab Results: 

Linux/Zebra/Emulab Results D B C Flat OSPF Area, 3 Active-MPC nodes; Upto k-shortest, validated paths

Inter-domain TE: 

Inter-domain TE Outbound TE: Multi-exit (or Explicit-exit) routing Useful to manage peering vs transit costs Hash = (Exit ASBR, destination address) Forwarding paradigm: Connectionless tunneling thru the AS Inbound TE: NOT ADDRESSED DIRECTLY Multi-AS-Path or Explicit AS-Path routing: Framework similar to IGP: e-PathID concept

BGP Explicit-Exit Routing: Route Selection: 

BGP Explicit-Exit Routing: Route Selection Explicit-Exit routing is easier than Explicit-Path Routing Only the “source” and “exit” nodes need upgrades ! Explicit exit routing easily extended to “multi-exit” routing

BGP Explicit-Exit Routing: Forwarding: 

BGP Explicit-Exit Routing: Forwarding IBGP locally installs explicit & default exits for chosen prefix Dest-Prefix Exit-ASBR Next-Hop Dest-Prefix Default-Next-Hop Next-hop refers to the IGP next hop to reach Exit-ASBR Default-Next-Hop: regular IBGP function

Explicit-Exit Routing Example: 

Explicit-Exit Routing Example Default (AS Path , Exit) to d = (1-3-4, ASBR3) Now, ABR1 can have explicit exits ASBR4 (implied ASPath = 1-2-4), ASBR2 (implied ASPath =1-3-4) as well!!

Inter-AS Explicit AS-Path Choice: 

Inter-AS Explicit AS-Path Choice Allow AS0 to explicitly choose an AS-PATH: e.g. 0-1-2-4 or 0-1-3-4, Explicit AS-Path choice encoded as an e-PathID = Hash{1,2,4} e-PathID is updated only when the packet leaves the AS at Exit border routers. At ASBR1, this explicit AS-path choice is mapped to an exit ASBR. Within an upgraded AS, the packet is tunneled using the routing header as explained earlier. Only selected EBGP nodes need be upgraded & synchronized

Re-advertisements of Multi-AS-Paths: 

Re-advertisements of Multi-AS-Paths Issue: in path-vector algorithms, without re-advertisements (of a subset of paths), remote AS’s cannot see the availability of multiple paths But, re-advertisements adds control traffic overhead An AS may choose to re-advertise only, and not support multi-path forwarding (I.e. interpreting e-PathID or Address Stack fields)

Summary: 

Summary TE: “Towards Better routing performance”: Key: Decoupling route availability and setup issues from traffic mapping issues, without signaling BANANAS-TE can leverage the rich interconnectivity and multi-homed nature of the Internet, with manageable increase in complexity TE spectrum Shortest Path MPLS …

Extra Slides : 

Extra Slides

BGP Explicit Exit: SSFnet Simulation Example: 

BGP Explicit Exit: SSFnet Simulation Example

Slide27: 

AS 2 AS 5 AS 4 AS 3 0.0.0.48/29 0.0.0.0/27 0.0.0.56/29 0.0.0.32/28 1 1 1 1 2 2 4 3 2 2 3

Slide28: 

Outgoing Packet from AS2 router 1 AS 2 94/32 18/32 10/32 2/32 14//32 1/32 4 3 16/32 12/32 17/32 Dest address is pushed to stack @ AS2 (1); like MPLS => tunneling emulation! 1 Forwarding Table@ AS2 (Router 1) 2

Slide29: 

AS 2 94/32 18/32 10/32 2/32 14//32 1/32 2 4 3 16/32 12/32 17/32 AS 3 2 90/32 42/32 33/32 38/32 Destination address is popped back from Address Stack at AS2 (2) Outgoing packet from AS2 router 2 Forwarding Table@ AS2 (Router 2) 1 1

Slide30: 

AS1-AS2-AS4-AS3-AS5 AS 1 AS 2 AS 5 AS 4 AS 3 0.0.0.64/29 0.0.0.48/29 0.0.0.0/27 0.0.0.56/29 0.0.0.32/28 1 1 1 1 1 2 2 4 3 2 2 3

Slide31: 

AS 2 94/32 18/32 10/32 22/32 2/32 14//32 1/32 5/32 1 1 2 AS1-AS2-AS4-AS3-AS5 4 3 16/32 11/32 Forwarding Table at Router 1 of AS1 Outgoing Packet at 1 of AS1 Upgraded Upgraded AS 1

Slide32: 

AS 2 94/32 18/32 10/32 22/32 2/32 14//32 1/32 5/32 1 1 2 AS1-AS2-AS4-AS3-AS5 4 3 16/32 11/32 12/32 Forwarding Table at Router 1 of AS2 Outgoing Packet at 1 of AS2 Upgraded Upgraded AS 1

Slide33: 

94/32 18/32 10/32 22/32 2/32 14//32 1/32 5/32 1 2 3 16/32 11/32 12/32 Upgraded 81/32 1 2 86/32 0.0.0.56/29 17//32 Non Upgraded Forwarding Table at Router 3 of AS2 AS1-AS2-AS4-AS3-AS5 Outgoing Packet at 3 of AS2 AS 2 AS 4 83/32

Slide34: 

81/32 1 2 AS 3 90/32 37/32 38/32 33/32 42/32 1 3 87/32 AS1-AS2-AS4-AS3-AS5 Forwarding Table at Router 1 of AS4 Forwarding Table at Router 2 of AS4 *Outgoing Packet from router 1 & 2 of AS4 AS 4 Upgraded Non Upgraded 83/32 *No change in ePathID

Slide35: 

AS 3 90/32 37/32 38/32 33/32 42/32 1 3 Upgraded AS 5 85/32 58/32 77/32 1 2 0.0.0.48/29 0.0.0.32/28 Non Upgraded Forwarding Table at Router 2 of AS3 2 AS1-AS2-AS4-AS3-AS5 Incoming and Outgoing Packet from Router 2 of AS3

Slide36: 

AS 3 90/32 37/32 38/32 33/32 42/32 1 3 Upgraded AS 5 85/32 58/32 77/32 1 2 0.0.0.48/29 0.0.0.32/28 Non Upgraded 2 AS1-AS2-AS4-AS3-AS5 Forwarding Table at Router 3 of AS3 Outgoing Packet from Router 3 of AS3

Simulation/Implementation/Testing Platforms: 

Simulation/Implementation/Testing Platforms Utah’s Emulab Testbed: Experiments with Linux/Zebra/Click implementation MIT’s Click Modular Router On Linux: Forwarding Plane SSFnet Simulation for OSPF/BGP Dynamics Modular Router

Managing Complexity: Active/Passive MPC Routers: 

Even a few A-MPC routers makes appreciable number of paths available in the network! P-MPCs (eg: edge-routers) could act as “sources” Managing Complexity: Active/Passive MPC Routers Issue: DFS computation complexity and number of paths grow exponentially as a function of MPC nodes Solution 1: Divide upgraded routers into two sets: Passive MPC routers (P-MPC) and Active MPC (A-MPC) Only A-MPC routers set the MPC bit in LSAs Effective maximum number of MPC routers “seen” = Number of A-MPC routers + 1

Slide39: 

Router LSA Modifications MPC-Bit: Unused Bit #7 of options ki value used at router i: Unused 8 Bits after Router Type (reproduced from John Moy’s OSPF book)