Question? Leave a message!




Traffic Engineering

Traffic Engineering
Traffic Engineering Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 1Overview  Introductions:course description calendar  Answers to frequently asked questions  Prerequisites  Informal Quiz Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 2Without Traffic Engineering Cars: SFOLAX SANSMF LAXSFO SMFSAN No Traffic Engineering analogy to Human Drivers Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 3Traffic Engineering: Analogy Cars: SFOLAX SANSMF LAXSFO SMFSAN Traffic Engineering analogy Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 4Motivation  TE: “…that aspect of Internet network engineering dealing with the issue of performance evaluation and performance optimization of operational IP networks …’’  90’s approach to TE was by changing link weights in IGP (OSPF, ISIS) or EGP (BGP4)  Performance limited by the shortest/policy path nature  Assumptions: Quasistatic traffic, knowledge of demand matrix B B B 11 11 1 4 2 22 A A D D D EE E 1 2 A 1 1 2 2 Links AB and BD are overloaded C C C LiC nk an s AC not a dnd o t C hD is a w re ov ith O eS rlPF oaded Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 5Fundamental Requirements  Need the ability to:  Map traffic to an LSP  Monitor and measure traffic  Specify explicit path of an LSP Partial explicit route Full explicit route  Characterize an LSP Bandwidth Priority/ Preemption Affinity (Link Colors)  Reroute or select an alternate LSP Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 6Traffic Engineering Steps  First, determine how to lay out traffic on the physical topology Measure traffic (e.g., citypairwise) Crunch numbers  Second, do something to convince the packets to follow your plan Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 7Traffic Engineering Options  BGP – play with communities, filtering  IGP – play with metrics Linear programming can help  Source routing ATM MPLS Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 8Routing Solution to Traffic Engineering R2 R3 R1  Construct routes for traffic streams within a service provider in such a way, as to avoid causing some parts of the provider’s network to be overutilized, while others parts remain underutilized (I.e. loadbalance) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 9Linear Programming  TE among N cities: N² city pairs  Set up N² by N² matrix for LP  Matrix multiplication/inversion is O(M³) for M x M matrix; simplex is O(M³) matrix operations 12  So, LP problem is O(N )  Also can’t deal with “looped routes” Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 10The “Overlay” Solution L3 L3 L3 L3 L2 L2 L3 L2 L3 L3 L3 L2 L2 L2 L3 L3 L3 L3 Physical Logical  Routing at layer 2 (ATM or FR) is used for traffic engineering  Analogy to direct highways between SFOLAX SANSMF. Nobody enters the highway in between. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 11Traffic engineering with overlay R2 R3 R1 PVC for R2 to R3 traffic PVC for R1 to R3 traffic Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 12Connectionless Routing Today  Internet connectionless routing protocols originally designed to find one route Eg: shortest route or policy route)  Connectionless routing relies upon a global consistency criterion (GCC) The GCC is constructed using globally known identifiers (Eg: ASNs, link weights) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 13DV: Global Consistency Criterion  The subset of a shortest path is also the shortest path between the two intermediate nodes.  If the shortest path from node i to node j, with distance D(i,j) passes through neighbor k, with link cost c(i,k), then: D(i,j) = c(i,k) + D(k,j)  D(i,) is a distance vector at node i. j i k Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 14Link State (LS): Global Consistency Criterion  The link state (Dijkstra) approach is iterative, but it pivots around destinations j, and their predecessors k = p(j)  Alternative version of the consistency condition: D(i,j) = D(i,k) + c(k,j) j i k  Each node i collects all link states c(,) first and runs the complete Dijkstra algorithm locally. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 15PathVector: BGP’s Consistency Criterion Policybased routing: Arbitrary preference among a menu of available routes (based upon routes’ attributes) 135.207.0.0/16 ASPATH = 3 2 1 AS 1 AS 3 AS 4 AS 2 135.207.0.0/16 IP Packet Dest = 135.207.44.66  Consistency: If AS2 announces a route, it is actively using the route, and will honor forwarding requests on that route Acknowledgement: Based upon Dr. Tim Griffin’s SIGCOMM Tutorial Slides Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 16Limitations of Today’s Connectionless TE  Traffic mapping coupled with route availability Changing parameters changes routes AND changes the traffic mapped to the routes  Priority rules only: LOCALPREF, MED, longestprefix match Cannot split traffic to same destination among two paths Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 17Signaled Approach (eg: MPLS)  Nice features: In MPLS, choice of a route (and its setup) is orthogonal to the problem of traffic mapping onto the route Signaling maps global IDs (addresses, path specification) to local IDs (labels) Nice label stacking, tunneling features Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 18LabelSwitched Forwarding  San Francisco prepends MPLS header to the IP packet  MPLS label is swapped at each hop along the LSP  Forwarding is done based on a label table Seattle New York (Egress) IP 0 IP 1321 5 San IP 120 Francisco 1321 (Ingress) 120 Miami IP Label Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 19What Does MPLS Offer  Tunnels Drop a packet in, and out it comes at the other end without being IP routed  Explicit (source) routing (circuits)  Label stack 2label stack: “outer” label defines the tunnel; “inner” label demultiplexes  Layer 2 independence Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 20Why Tunnels  Can’t IP route NonIP packets IP packets with private addresses  Don’t want to IP route “BGPfree” core  Don’t like IP multicast model Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 21Tunnel Comparison MPLS (LDP) tunnels IP tunnels  Small header  Big header  Label stacking  No stacking ()  Signaling for demux  No signaling (yet)  Automagic tunnels  Configured tunnels  Tracks IP routing  Duh  Harder to spoof  Spoofable  No data security  IPSec Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 22Bottom Line on Tunnels  Don’t need MPLS for tunnels  But MPLS tunnels have some nice properties  Decision (should be) based on cost of deploying new protocol vs. benefits Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 23MPLS Signaling and Forwarding Model  MPLS label is swapped at each hop along the LSP  Labels = LOCAL IDENTIFIERS …  Signaling maps global identifiers (addresses, path spec) to local identifiers Seattle New York (Egress) IP 0 IP 1321 5 San IP 120 Francisco 1321 (Ingress) 120 Miami IP Label Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 24Limitations of Signaled TE Approach  Requires extensive upgrades in the network  Hard to internetwork beyond area boundaries  Very hard to go beyond AS boundaries Even within the same organization/ISP Note: large ISPs (eg: ATT) have several AS’es  Impossible for interdomain routing across multiple organizations Interdomain TE has to be connectionless Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 25Traffic Engineering w/o Signaling  Finegrained Traffic Engineering needs some form of source routing  Specific incremental changes much easier with source routing Change a single citypair flow Reacting to a link failure  Can we do sourcerouting efficiently in connectionless protocols Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 26Idea  Instead of using local path identifiers (Labels in MPLS), use global path identifiers Seattle New York (Egress) IP IP 36 IP 0 San IP 27 Francisco (Ingress) Miami IP PathId Routers have capability to compute multiple paths using map from IGP (OSPF/ISIS) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 27Global Path Identifiers  Instead of using local path identifiers (Labels in MPLS), we propose the use of global path identifiers Seattle New York (Egress) IP IP 36 IP 0 San IP 27 Francisco (Ingress) Miami IP PathId Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 28Global Path Identifier IP PathId(1,j) j w m 2 k w 2 w i 1 m1 1 IP PathId(i,j) Central idea: Swap global pathids instead of local labels Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 29Global Path Identifier (contd) j w m 2 w 2 w i 1 m1 1 k  Path = i, w , 1, w , 2, …, w , k, w , … , w , j 1 2 k k+1 m  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: b  j, h(1) + h(2) + …+h(k)+ … +h(m1) mod 2 : node ID sum  MD5 oneway hash, XOR, 32bit CRC etc…  We propose the use of MD5 hashing of the subsequence of nodeIDs followed by a CRC32 to get a 32bit hash value  Very low collision (I.e. nonuniqueness) probability Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 30Abstract Forwarding Paradigm  Forwarding table (Eg; at Node k):  Destination Prefix,  NextHop, PathID SuffixPathID  j,  k+1, Hk, k+1, … , m1 Hk+1, … , m1 Incoming Packet Hdr: Destination address (j) PathID = Hk, k+1, … , m1 Outgoing Packet Hdr: j, PathID = Hk+1, … , m1 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 w j m 2 w 2 w 1 i m1 1 k Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 31BANANAS TE: Explicit, MultiPath Forwarding…  Explicit SourceDirected Routing: Not limited by the shortest path nature of IGP  Different PathIds = different nexthops (multipaths)  No signaling required to setup the paths  Traffic splitting is decoupled from route computation Seattle IP 0 New York (Egress) IP 5 IP IP 36 San IP 0 IP 27 Francisco (Ingress) Miami IP PathId Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 32BANANAS TE: Partial Deployment  Only “red” routers are upgraded  Link State Advertisements (LSAs) may indicate (with 1 bit) which routers are upgraded  Nonupgraded routers forward everything on the shortest path (default path): forming a “virtual hop” Seattle IP 0 New York (Egress) IP 5 IP 27 IP 27 San IP 0 Francisco (Ingress) X Miami IP 27 IP 27 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 33Multiplicity Paradigm  Unlike telephony, data networking can get statistical multiplexing gains from simultaneously using:  Multiple transmission modes (802.11a/b, 3G etc)  Multiple exits (USB, Firewire, Ethernet, modem)  Multiple paths (routes)  Lightweight distributed QoS on each path  Can then quickly meet the performance thresholds of highquality multimedia apps Phone modem USB/802.11a/b 802.11a Firewire/802.11a/b WiFi Ethernet Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 34Eg: Multipath MPEG using Multiband 802.11a/b Community Wireless Networks “Slow” path “Fast” path P I Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 35