Adapting Routing to the TrafficGoals of Today’s LectureDo IP Networks Manage Themselves?Slide 4Adapting the Routing to the TrafficLoad-Sensitive Routing ProtocolsPacket-Based Load-Sensitive RoutingOriginal ARPANET Algorithm (1969)Performance of ARPANET AlgorithmProblem: Out-of-Date InformationProblem: Frequent UpdatesSecond ARPANET Algorithm (1979)Problem of Long Alternate PathsLoad-Sensitive RoutingReducing Effects of Out-of-Date InfoTraffic Engineering as a Network-Management Problem: Case StudyUsing Traditional Routing ProtocolsApproaches for Setting the Link WeightsExample of Tuning the Link WeightsMeasure, Model, and ControlTraffic Engineering ProblemKey Ingredients of the ApproachFormalizing the Optimization ProblemMultiple Shortest Paths: Even SplittingDefining the Objective FunctionComplexity of the Optimization ProblemOptimization Based on Local SearchMaking the Search EfficientIncorporating Operational RealitiesApplication to AT&T’s BackboneExample from AT&T’s Operations CenterExample ContinuedWhat About Interdomain Routing?Interdomain Traffic EngineeringOutbound Traffic: Pick a BGP RouteOutbound Traffic: Shortest AS PathOutbound Traffic: Load BalancingBalancing Load, Performance, and CostA Fundamental ProblemConclusions1Adapting Routing to the TrafficCOS 461: Computer NetworksSpring 2007 (MW 1:30-2:50 in Friend 004)Jennifer RexfordTeaching Assistant: Ioannis Avramopoulos http://www.cs.princeton.edu/courses/archive/spring07/cos461/2Goals of Today’s Lecture•Challenges–Reacting quickly to alleviate congestion–Avoiding over-reacting and causing oscillations–Limiting bandwidth & CPU overhead on routers•Load-sensitive routing–Routers adapt to link load in a distributed fashion–At the packet level, or on “group of packets”•Traffic engineering–Centralized computation of routing parameters–Network-wide measurements of offered traffic3Do IP Networks Manage Themselves?•TCP congestion control–Senders react to congestion–Decrease sending rate–But… the TCP sessions receive lower throughput•IP routing protocols–Routers react to failures–Compute new paths–But… the new paths may be congested422113145342211314534Do IP Networks Manage Themselves?•In some sense, yes:–TCP senders send less traffic during congestion–Routing protocols adapt to topology changes•But, does the network run efficiently?–Congested link when idle paths exist?–High-delay path when a low-delay path exists?422113145342211314535Adapting the Routing to the Traffic•Goal: modify the routes to steer traffic through the network in most effective way•Approach #1: load-sensitive protocols–Distribute traffic & performance measurements–Routers compute paths based on load•Approach #2: adaptive management system –Collect measurements of traffic and topology–Management system optimizes the parameters •Debates still today about the right answer6Load-Sensitive Routing Protocols•Advantages–Efficient use of network resources–Satisfying the performance needs of end users–Self-managing network takes care of itself•Disadvantages–Higher overhead on the routers–Long alternate paths consume extra resources–Instability from out-of-date feedback information7Packet-Based Load-Sensitive Routing•Packet-based routing–Forward packets based on forwarding table•Load-sensitive–Compute table entries based on load or delay•Questions–What link metrics to use?–How frequently to update the metrics?–How to propagate the metrics?–How to compute the paths based on metrics?8Original ARPANET Algorithm (1969)•Routing algorithm–Shortest-path routing based on link metrics–Instantaneous queue length plus a constant–Distributed shortest-path algorithm (Bellman-Ford)3221131520congested link9Performance of ARPANET Algorithm•Light load–Delay dominated by transmission & propagation–So, link metrics don’t fluctuate much•Medium load–Queuing delay is no longer negligible–Moderate traffic shifts to avoid congestion•Heavy load–Very high metrics on congested links–Busy links look bad to all of the routers–All routers avoid the busy links–Routers may send packets on longer paths10Problem: Out-of-Date Information•Routers make decisions based on old information–Propagation delay in flooding link metrics–Thresholds applied to limit number of updates•Old information leads to bad decisions–All routers avoid the congested links–… leading to congestion on other links–… and the whole things repeatsLincoln TunnelHolland TunnelNJ NYC“Backup at Lincoln” on radio triggers congestion at Holland11Problem: Frequent Updates•Update messages–Link keeps track of its metric (e.g., queuing delay)–Link transmits updates when the metric changes•Frequency of updates–Frequent changes to the metric lead to frequent updates–Significantly increases the overhead of the protocol•Oscillation makes the problem worse–Oscillation leads to wild swings in the link metrics–Forcing very frequent update messages–… that add to the load on the links in the network12Second ARPANET Algorithm (1979)•Link-state protocol–Old: Distributed path computation leads to loops–New: Better to flood metrics and have each router compute the shortest paths•Averaging of the link metric over time–Old: Instantaneous delay fluctuates a lot–New: Averaging reduces the fluctuations•Reduce frequency of updates–Old: Sending updates on each change is too much–New: Send updates if change passes a threshold13Problem of Long Alternate Paths•Picking alternate paths–Long path chosen by one router consumes resource that other packets could have used–Leads other routers to pick other alternate paths•Solution: limit path length–Bound the value of the link metric–“This link is busy enough to go two extra hops”•Extreme case–Limit path selection to the shortest paths–Pick least-loaded shortest path in the network14Load-Sensitive Routing•Timescales–What timescale of routing decisions?–What timescale of feedback about link loads?•Load-sensitive routing at packet level–Routers receive feedback on load and delay–Routers re-compute their forwarding tables –Fundamental problems with oscillation•Load-sensitive routing for groups of packets–Routers receive feedback on load and delay–Router compute a path for the next flow or circuit–Less oscillation, as long as circuits last for a while15Reducing Effects of
View Full Document
Unlocking...