CS 6390 Advanced Computer NetworksTraffic EngineeringTraffic Engineering under Shortest Path Routing: Tuning Link WeightsLimitations of Conventional Intra-Domain RoutingMPLS – BackgroundWhat is it good for?MPLS TerminologyForwarding Equivalence Class (FEC)MPLS Message FormatDestination Based ForwardingDestination Based Forwarding (cont’d)Slide 12Slide 13Slide 14RemarksRemarks (contd)Placement of “labels”What have we gained (IP over ATM)ATM switches as LSRsAdv. of MPLS vs overlayExplicit RoutingExplicit Route AdvantagesVirtual Private Networks“Layer 2” tunnelEmulate a VCDemultiplexing LabelSlide 27Emulate a VC (steps)Traffic Engineering FrameworkTraffic Engineering Framework (cont’d)Traffic Engineering as a Global Optimization ProblemTraffic Engineering Example: minimize maximum link utilizationTraffic Engineering: LP FormulationTraffic Engineering w/ MPLSTraffic Engineering w/o MPLSEffect of link weightsShortest Path Routing and Link Weight Assignment ProblemSummaryCS 6390Advanced Computer NetworksTraffic Engineeringand Multi-Protocol Label Switching(MPLS)Traffic EngineeringGoal: configure routes to meet traffic demandsbalanced load, low latency, service agreementsOperates at coarse timescalesNot to adapt to short-term sudden traffic changesMay take potential failures into considerationInput to traffic engineering: Topology: connectivity & capacity of routers & linksTraffic matrix: offered load between points in the networkTraffic Engineering: network-wide optimizationSubject to protocol mechanisms, configurable parameters and other practical constraints, ….Traffic Engineering under Shortest Path Routing: Tuning Link WeightsProblem: congestion along the blue pathSecond or third link on the path is overloadedSolution: move some traffic to green pathE.g., by decreasing the weight of the second link32211314533Limitations of Conventional Intra-Domain RoutingOverhead of hop-by-hop forwardingLarge routing tables and expensive look-upsPaths depend only on the destinationRather than differentiating by source or classOnly the shortest path(s) are usedEven if a longer path has enough resourcesTransient disruptions during convergenceCannot easily prepare in advance for changesLimited control over paths after failureDepends on the link weights and remaining graphMPLS – BackgroundIt was meant to improve routing performance in the InternetRouting is difficult using CIDR (longest prefix matching)MPLS is similar to virtual circuitsOnly a fixed-sized label is used (like a VCID) with local scopeIt is very datagram oriented thoughIt uses IP addressing and IP routing protocolsOnly pkt forwarding is different, i.e., based on fixed labels rather than longest prefix matchWhat is it good for?To enable IP capability on devices that cannot handle IP trafficForward packets along “explicit routes” (pre-calculated routes not used in “regular” routing)To support certain virtual private network servicesNote: “performance” is not aboveRouter hardware-software have improved so much; performance is not an issue anymoreMPLS Terminology•LDP: Label Distribution Protocol •LSP: Label Switched Path•FEC: Forwarding Equivalence Class•LSR: Label Switching Router•LER: Label Edge Router (Useful term not in standards)•MPLS “multi-protocol” both in terms of protocols it supports ABOVE and BELOW in protocol stack!Forwarding Equivalence Class (FEC)FEC – rule for grouping IP packetsPackets that should be treated the same way, e.g, forwarded over same path, with same forwarding treatmentIdentified just once, at the edge of the networkExample FECsdestination prefix longest-prefix match in forwarding table at entry pointuseful for conventional destination-based forwardingsame src and dst addresses5-tuple flows (src/dst addr, src/dst port, and protocol)five-tuple match at entry pointuseful for fine-grain control over the trafficQoS class A label is just a locally-significant identifier for a FECMPLS Message FormatLabel (20 bits) Res(3) B TTL(8)IP HeaderB = 1: Stack bottom (no more MPLS headers below)TTL: Copied from IP TTL and used in the same way as in IPDestination Based ForwardingLabel Switching Routers (LSR)Destination Based Forwarding (cont’d)A router with MPLS capability is called Label Switching Router (LSR)A label is allocated for each prefix in its tableThe label is chosen locallyThink of them as indices into the routing tableA router advertises the label to its neighbors“label distribution protocol” (LDP)Packets addressed to the prefix should, for efficiency, be tagged with the label.The label of an incoming packet is “swapped” before being forwarded to the next router.Label Edge Router (LER)RemarksRather than longest prefix-matching we use label matchingLabels can be very efficient, simply an index into the routing tableRegular IP routing is still usedE.g., we could use OSPF to determine the routesThen we use labels for efficiency in per-hop forwardingRemarks (contd)We can use ATM switches for IPATMVirtual circuit orientedFixed packet (small 53 bytes), known as cellsSpecial hardware for fast switching from input line to output lineATM networks use very similar label switching for cell forwardingWe can turn “ATM Cell switches” into “label switching routers” usually only by changing the software and not the hardware of the switch.Placement of “labels” Where to put MPLS labels?What have we gained (IP over ATM)Without MPLS, every router to have a VC over an ATM network to every other routerKnown as an “overlay” networkR1 has 5 neighborsATM switches as LSRsATM switches are now “peers” of MPLS routersR1 has 1 neighborAdv. of MPLS vs overlayEach MPLS router has fewer “adjacencies” (i.e. neighbors)This reduces the OSPF traffic to the router significantlyIn OSPF you receive the topology of the entire network via each of your neighbors.Each router now has a view of the entire topologyNot possible in overlay networksRouters have better control of paths in case of link failuresIn overlay networks, the ATM switches would do the reroutingATM switches may still support native ATM if desired.Explicit RoutingSimilar to “source routing” but done by a router“Fish” network due to its shapeR1 -> R7 : R1
View Full Document