1、BANANAS: A Connectionless Approach to Intra- and Inter-Domain Traffic Engineering,Hema T. Kaur, Shiv Kalyanaraman, Rensselaer Polytechnic Institute hemanetworks.ecse.rpi.edu, shivkumaecse.rpi.edu http:/www.ecse.rpi.edu/Homepages/shivkuma,Acknowledgements,Biplab Sikdar (faculty colleague) Andreas Wei
2、ss (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,Can we emulate a subset of MPLS properties
3、 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?,Connectionless TE today uses a parametric approach: Eg: changing link weights in OSPF,
4、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 p
5、ath,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,Instead of using
6、 local path identifiers (Labels in MPLS), we propose the use of global path identifiers,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 nee
7、d to locally compute the valid PathIDs.,Global Path Identifier (continued),Path = i, w1, 1, w2, 2, , wk, k, wk+1, , wm, jSequence of globally known node IDs & Link weightsGlobal Path ID is a hash of this sequence = locally computable without the need for signaling!Potential hash functions: j, h(1) +
8、 h(2) + +h(k)+ +h(m-1) mod 2b : node ID sumMD5 one-way hash, XOR, 32-bit CRC etcWe propose the use of MD5 hashing of the subsequence of nodeIDs followed by a CRC-32 to get a 32-bit hash valueVery low collision (i.e. non-uniqueness) probability,Abstract Forwarding Paradigm,Forwarding table (Eg; at No
9、de k): Destination Prefix, Next-Hop, j, k+1, ,Incoming Packet Hdr: Destination address (j) & PathID = Hk, k+1, , m-1 Outgoing Packet Hdr: j, PathID = Hk+1, , m-1 Longest prefix match + exact label match + label swap! PathID mismatch = map to shortest (default) path, and set PathID = 0 No signaling b
10、ecause of globally meaningful pathIDs!,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 rout
11、e computation,10,Miami,Seattle,9,27,San Francisco (Ingress),New York (Egress),18,1,5,4,3,5,IP,4,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 (Ingres
12、s),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),Assume 1-bit in LSAs to advertise that an upgraded router is “multi-path capable” (MPC)Two phase algorithm: (assume m upgraded nodes) 1. (N-m) Dijkstras for non-upgraded nodes or one all-pa
13、irs shortest path (Floyd Warshall)2. DFS to discover valid paths to destinations. Explore all neighbors of upgraded nodesExplore only shortest-path next-hop of non-upgraded nodesVisited bit set to avoid loopsComputes all possible valid paths under PU constraints in a fully distributed manner (global
14、 consistency),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,A,C,B,E,D,SSFnet Simulation Results,Flat OSPF Area, 19 Nodes; Only 3 Active-MPC nodes,Heterogeneous
15、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 f
16、or k-shortest paths may not exist Need to validate the forwarding availability for paths!,Two-Phase Path Validation Algorithm,Concept: Forwarding for path exists only if the forwarding for each of its suffixes exists. Phase 1 (contd): compute k-shortest paths for all other upgraded nodes, and 1-shor
17、test paths for non-upgraded nodes. Sort computed paths by hopcountPhase 2: Validate paths starting from hopcount = 1. All 1-hop paths valid.p-hop paths valid if the (p-1)-hop path suffix is validThrow out invalid paths as they are found Polynomial complexity to discover all valid paths in the networ
18、k & validation can be done in the background Validation algorithm correct by mathematical induction,Linux/Zebra/Emulab Results,D,B,C,Flat OSPF Area, 3 Active-MPC nodes; Upto k-shortest, validated paths,Inter-domain TE,Outbound TE: Multi-exit (or Explicit-exit) routing Useful to manage peering vs tra
19、nsit costs Hash = (Exit ASBR, destination address) Forwarding paradigm: Connectionless tunneling thru the ASInbound TE: NOT ADDRESSED DIRECTLYMulti-AS-Path or Explicit AS-Path routing: Framework similar to IGP: e-PathID concept,BGP Explicit-Exit Routing: Route Selection,Explicit-Exit routing is easi
20、er 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,IBGP locally installs explicit & default exits for chosen prefix Dest-Prefix Exit-ASBR Next-Hop Dest-Prefix Default-Nex
21、t-Hop Next-hop refers to the IGP next hop to reach Exit-ASBR Default-Next-Hop: regular IBGP function,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
22、 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 = Hash1,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 upg
23、raded 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,Issue: in path-vector algorithms, without re-advertisements (of a subset of paths), remote ASs cannot see the availability of m
24、ultiple 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,TE: “Towards Better routing performance”: Key: Decoupling route availability and setup issues f
25、rom traffic mapping issues, without signaling BANANAS-TE can leverage the rich interconnectivity and multi-homed nature of the Internet, with manageable increase in complexityTE spectrum,Shortest Path,MPLS,Extra Slides,BGP Explicit Exit: SSFnet Simulation Example,AS 2,AS 5,AS 4,AS 3,0.0.0.48/29,0.0.
26、0.0/27,0.0.0.56/29,0.0.0.32/28,1,1,1,1,2,2,4,3,2,2,3,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,AS 2,94/32,18/32,10/32,2/32,14/32,1/32,2,4
27、,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,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
28、,2,2,4,3,2,2,3,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,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,Forwardi
29、ng Table at Router 1 of AS2,Outgoing Packet at 1 of AS2,Upgraded,Upgraded,AS 1,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
30、/32,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,AS 3,90/32,37/32,38/32,33/32,42/32,1,3,Upgraded,AS 5
31、,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,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-AS
32、5,Forwarding Table at Router 3 of AS3,Outgoing Packet from Router 3 of AS3,Simulation/Implementation/Testing Platforms,Utahs Emulab Testbed: Experiments with Linux/Zebra/Click implementation,MITs Click Modular Router On Linux: Forwarding Plane,SSFnet Simulation for OSPF/BGP Dynamics,Modular,Router,E
33、ven 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
34、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,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 Moys OSPF book),
