Traffic Engineering in IP NetworksA Little About Me…OutlineInternet ArchitecturePath Traversing Multiple ASesInterdomain Routing: Border Gateway ProtocolIntradomain Routing: OSPF or IS-ISMotivating Problem: Congested LinkTraffic Engineering in an ISP BackboneModeling Traffic DemandsTraffic MatrixProblem: Hot Potato RoutingTraffic Demand: Multiple Egress PointsTraffic Mapping: Ingress MeasurementTraffic Mapping: Egress Point(s)Traffic Mapping: Combining the DataApplication on the AT&T BackboneThree Traffic Demands in San FranciscoUnderpinnings of the OptimizationWeight OptimizationIncorporating Operational RealitiesApplication to AT&T’s Backbone NetworkConclusionsStepping Back: IP Network ManagementTo Learn More…Traffic Engineering in IP NetworksTraffic Engineering in IP NetworksJennifer RexfordComputer Science DepartmentPrinceton University; Princeton, NJhttp://www.cs.princeton.edu/~jrexA Little About Me…A Little About Me…Technical interests: data networking–Network measurement–Network operations–Internet routing and infrastructureJob history–2005-onward: Professor in Computer Science at Princeton –1996-2005: AT&T Labs—Research»Technology transfer of tools for measurement, configuration, troubleshooting, and traffic engineering to network operatorsDARPA involvement–Member of the ISAT study group–Knowledge Plane seedling project–NetVision2012 workshopsOutlineOutlineInternet routing protocolsTraffic engineering using traditional protocols–Optimizing configuration to the traffic–Needs topology, routing, and traffic dataTraffic demands–Volume of load between edges of the network–Measuring the traffic demandsRoute optimization–Tuning the link weights to the traffic–Satisfying the operational constraintsConclusionsInternet ArchitectureInternet ArchitectureDivided into Autonomous Systems–Regions of administrative control–Routers and links managed by an institution–Service provider, company, university, …Hierarchy of Autonomous Systems–Tier-1 provider with nationwide backbone–Medium-sized regional provider–Campus or corporate networkInteraction between Autonomous Systems–Internal topology is not shared–… but, ASes interact to coordinate routingPath Traversing Multiple ASesPath Traversing Multiple ASes1234567ClientWeb serverPath: 6, 5, 4, 3, 2, 1Interdomain Routing: Border Gateway ProtocolInterdomain Routing: Border Gateway ProtocolASes exchange info about who they can reach–IP prefix: block of destination IP addresses–AS path: sequence of ASes along the pathPolicies configured by the AS’s network operator–Path selection: which of the paths to use?–Path export: which neighbors to tell?12 312.34.158.5“I can reach 12.34.158.0/24”“I can reach 12.34.158.0/24 via AS 1”Intradomain Routing: OSPF or IS-ISIntradomain Routing: OSPF or IS-ISShortest path routing based on link weights–Routers flood the link-state information to each other–Routers compute the “next hop” to reach other routersWeights configured by the AS’s network operator–Simple heuristics: link capacity or physical distance–Traffic engineering: tuning the link weights to the traffic3221131453Motivating Problem: Congested LinkMotivating Problem: Congested LinkDetecting that a link is congested–Utilization statistics suggest overloaded link –Probe traffic suffers degraded performance–Customers complain (via the phone network?)Reasons why the link might be congested–Increase in the offered traffic–Routing change due to equipment failure–Routing change due to a change in another ASChallenges–Know the cause, not just the manifestations–Predict the effects of possible changes to link weightsTraffic Engineering in an ISP BackboneTraffic Engineering in an ISP BackboneNetwork topology–Connectivity and capacity of routers and linksTraffic demands–Offered load between points in the networkRouting configuration–Link weights for selecting pathsPerformance objective–Balanced load, low latency, …Question: Given the topology and traffic demands in an IP network, what link weights should be used?Modeling Traffic DemandsModeling Traffic DemandsVolume of traffic V(s,d,t)–From a source s–To a destination d–Over a time period tTime period–Performance debugging – minutes–Traffic engineering – hours or days–Network design – days to weeksSources and destinations–Hosts – interesting, but huge, and hard to measure–IP prefixes – still big, and not seen by any one AS –Edge routers – hmmm….Traffic MatrixTraffic MatrixinoutTraffic matrix: V(in,out,t) for all pairs (in,out)Problem: Hot Potato RoutingProblem: Hot Potato RoutingAS is in the middle of the Internet–Multiple connections to multiple other ASes–Egress point depends on intradomain routingProblem with point-to-point models–Want to predict impact of changing intradomain routing–But, a change in weights may change the egress point!1234Traffic Demand: Multiple Egress PointsTraffic Demand: Multiple Egress PointsDefinition: V(in, {out}, t)–Entry link (in)–Set of possible egress links ({out})–Time period (t)–Volume of traffic (V(in,{out},t))Computing the traffic demands–Measure the traffic where it enters the ISP backbone–Identify the set of egress links where traffic could leave–Sum over all traffic with same in, {out}, and tTraffic Mapping: Ingress MeasurementTraffic Mapping: Ingress MeasurementPacket measurement (e.g., Netflow, sampling)–Ingress point i–Destination prefix d–Traffic volume VididingressdestinationTraffic Mapping: Egress Point(s)Traffic Mapping: Egress Point(s)Routing data (e.g., forwarding tables)–Destination prefix d–Set of egress points edddestinationTraffic Mapping: Combining the DataTraffic Mapping: Combining the DataCombining multiple types of data–Traffic: Vid (ingress i, destination prefix d)–Routing: ed (set ed of egress links toward d)–Combining: sum over Vid with same ediingressegress setApplication on the AT&T BackboneApplication on the AT&T BackboneMeasurement data–Netflow data (ingress traffic)–Forwarding tables (sets of egress points)–Configuration files (topology and link weights)Effectiveness–Ingress traffic could be matched with egress sets–Simulated flow of traffic consistent with link loadsChallenges–Loss of Netflow records during delivery (can correct for it!)–Egress