Traffic Engineering and RoutingTopicsTraffic Engineering with MPLS: MethodsMPLS-multiprotocol label switchingConstraint-Based RoutingEnhanced Link State IGP (interior gateway protocol)Deploying MPLS System (GlobeCenter)Voice over IP IssuesRSVP RoutingVirtual Private NetworksDirect and Alternate Routing PoliciesDifferently Routed Calls with Trunk ReservationRouting Policies with Integrated Services ModelFeatures of NetscopeUtility of NetscopeDataVisualizationQoS Routing Issues for High Speed NetworksRoutingSlide 20Routing StrategiesFuture DirectionsQoS Routing for MultimediaBandwidth and Delay as MetricsPath Computation AlgorithmsReferencesTraffic Engineering and RoutingHansen BowTopics•Traffic Engineering with MPLS•Issues Concerning Voice over IP•Features of Netscope •QoS Routing for High-Speed Networks•QoS Routing for MultimediaTraffic Engineering with MPLS:Methods•MPLS – multiprotocol label switching•Constraint-based routing•Enhanced link state IGPMPLS-multiprotocol label switching•forwarding scheme•at ingress of MPLS network, IP packets are classified, tagged, and routed•at next router, tag is used to determine destination•before leaving, tag is removedConstraint-Based Routing•computes bounded routes•reservable bandwidth of a link is an approximation•can be done online or offlineEnhanced Link State IGP (interior gateway protocol)•distribute link information•flood network to obtain informationDeploying MPLS System (GlobeCenter)•Statistics Collection•Deploy LSP (label-switched path) with bandwidth constraint•Periodic update of LSP Bandwidth•Offline Constraint-Based RoutingVoice over IP Issues•modify capacity management and routing methods in IP to support IP telephony–delay less than 300ms–loss rate <1%•First Model: RSVP•Second Model: voice service uses Virtual Private NetworkRSVP Routing•Shortest Path First•Shortest Available Path First•Widest Available Path FirstVirtual Private Networks•interconnects telephony switches•Direct Path Only•Success to the Top•State-Dependent Routing•Approximate State-Dependent RoutingDirect and Alternate Routing PoliciesDifferently Routed Calls with Trunk ReservationRouting Policies with Integrated Services Model•not much difference between SPF, SAPF, WAPF•fewer blocked calls for a given network capacity because of better sharing of network capacityFeatures of Netscope•traffic measurement and network modeling•provide global views of configuration and useage dataUtility of Netscope•realizing customer SLAs•tuning parameters of network components•unite configuration•experiment with possible solutions to variable complex trafficData•Network components•Modeling Traffic•Routing–multiple shortest pathsVisualization•Objects•Statistics•Traffic and Links•Changing RoutesQoS Routing Issues for High Speed Networks•Goals–satisfy QoS requirements for admitted connection–global efficiency•Classes–Source routing–Distributed routing–Hierarchical routingRouting•Collection of State Information–local and global state–aggregated global stateRouting•Finding Feasible Path–Unicast•link optimization•link constrained•path optimization•path constrained–Dijkstra’s algorithm•http://www.cs.uwa.edu.au/undergraduate/courses/230.300/readings/graphapplet/graph.html–Multicast•Steiner TreeRouting Strategies•Source routing–centralized problem, loop-free–need global state, computation overhead•Distributed routing–routing response faster, scalable–need global state, more messages, loops•Hierarchical routing–scales well, computation shared–imprecision because aggregate state, complicated with constraints,Future Directions•Efficient Routing Algorithms •Routing with imprecise state information•Multipath Routing•ReroutingQoS Routing for Multimedia•Metric Selection–Efficient algorithms must exist for path computation–Reflect basic information of network–orthogonal•Multiple Metrics–additive, multiplicative, concaveBandwidth and Delay as Metrics•finding path subject to two or more additive and multiplicative metrics is NP-complete•only feasible combination is bandwidth and, for example, delayPath Computation Algorithms•Source Routing •Hop-by-hop–compute best path to every destination–shortest-widest path is free of loopsReferences•“NetScope: Traffic Engineering for IP Networks,” A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford, IEEE Network, Mar./Apr. 2000, pp. 11-19•“Traffic Engineering with MPLS in the Internet,” X. Xiao, A. Hannan, B. Bailey, and L.M. Ni, Ibid., pp. 28-33•“Capacity Management and Routing Policies for Voice over IP Traffic,” P.P. Mishra, and H. Saran, Ibid, pp. 20-27•“Quality-of-Service Routing for Supporting Multimedia Applications,” Z. Wang, and J. Crowcroft, IEEE Journal on Selected Areas in Communications, Vol. 14, No. 7, Sept. 1996•“An Overview of Quality of Service Routhing for Next-Generation High-Speed Networks: Problems and Solutions,” S. Chen and K. Nahrstedt, IEEE Network, Nov./Dec. 1998, pp.