CS 218- QoS Routing + CAC Fall 2003The ingredients of QoS supportCall Admission Control Styles1. Resource Allocation CAC2. Measurement Based CAC3. Hybrid SchemeHybrid CAC (cont)Slide 8Slide 9Slide 13Slide 14Slide 15Slide 16CAC Styles: Lessons LearnedQoS Routing and ForwardingMultiple constraints QoS RoutingSlide 20Slide 21Benefits of QoS RoutingThe components of QoS RoutingSlide 24Slide 25Slide 26Implementation of OSPF in the QoS SimulatorBellman-Ford AlgorithmB/F Algorithm propertiesCAC and packet forwardingApplication I: IP TelephonySlide 33Slide 34Simulation ResultsSlide 36Slide 37Slide 38Slide 39Slide 40Slide 41ConclusionsCS 218- QoS Routing + CACFall 2003•M. Gerla et al: “Resource Allocation and Admission Control Styles in QoS DiffServ Networks,” QoS-IP 2001, Rome, Italy.•A. Dubrovsky, M. Gerla, S. S. Lee, and D. Cavendish,Internet QoS Routing with IP Telephony and TCP Traffic, In Proceedings of ICC 2000. •L. Breslau et al “Comments on the performance of Measurement Based Admission Control” Infocom 2000The ingredients of QoS support•Call Admission Control•QoS routing•Policing•SchedulingCall Admission Control StylesAssumptions:•Intradomain scenario•Flow Aggregation in Classes (a la DiffServ)•QoS Routing (Q-OSPF):(a) traffic and delay measured at routers(b) link measurements advertised to nodes(c ) sources compute feasible paths•MPLS used to “pin” the path1. Resource Allocation CACFor each call request:•examine traffic descriptors (rate, loss Prob, Burst Length) and delay Dmax•compute equiv Bdw and Buffer for each link (Mitra & Elwalid model)•With Q-OSPF find feasible paths (bdw&buffer) •using RSVP-like signaling, update the resource allocation along the path2. Measurement Based CAC•When a call request comes in, the edge router examines delay and residual bdw measmts advertised for path to destination•Call admitted/rejected at edge router based on measurements •No resource allocation/bookkeeping in core routers3. Hybrid SchemeSo far we have seen:•Res All CAC: enforces determin. bounds, but is too conservative (link utilization); also, bookkeeping required at core routers•Measmt CAC: is more aggressive, no bookkeeping; but, violates QoS constraintsIs there a “middle of the road” approach?Hybrid CAC (cont)•Hybrid CAC: (a) edge router estimates number of flows (from Q-OSPF trunk traffic measurements) (b) from number of flows it computes aggregate equiv bdw(c) It accepts/rejects call based on Bdw and Buffer availability (no explicit signaling)•Expected result: performance similar to Res CAC, without core router bookkeeping O/HSourcesDestinationsCapacity: all 45 MbpsProp. delay: all 0.1 msRouter buffers: 562KB12.5 KBEquiv. Buffer allocation1 MbpsEquiv. Bdw allocation60 sec of exponential dist.Connection duration1 per second at each sourceConnection request arrival4.4 MbpsTraffic peak rate0.64 MbpsTraffic average rateMPEG video traceTraffic typeBottleneck Link Load0 %5042400H-CAC0.39 %8642400M-CAC0 %4652400RA-CAC% of pkt. lost# of conn. admitted# of conn. requestsSchemeConnections Admitted &Pkt lossConnections AdmittedDelay DistributionCAC Styles: Lessons Learned•RA-CAC (with determin. bounds) overly conservative (and expensive)•RA-CAC requires per class “state” at core routers (bdw, buf allocation)•“state” is drawback in dynamic networks•“Stateless” options: M-CAC and H-CAC•Can mix M-CAC and H-CAC (need WFQ)Mario Gerla, Gianluca Reali Scott Lee, Claudio Casetti Computer Science DepartmentUniversity of California, Los Angeles (UCLA)www.cs.ucla.edu/NRL/QoS Routing and ForwardingMultiple constraints QoS RoutingGiven:- a (real time) connection request with specified QoS requirements (e.g., Bdw, Delay, Jitter, packet loss, path reliability etc)Find:- a min cost (typically min hop) path which satisfies such constraints- if no feasible path found, reject the connectionExample of QoS RoutingABD = 30, BW = 20D = 25, BW = 55D = 5, BW = 90D = 3, BW = 105D = 5, BW = 90D = 1, BW = 90D = 5, BW = 90D = 2, BW = 90D = 5, BW = 90D = 14, BW = 90Constraints: Delay (D) <= 25, Available Bandwidth (BW) >= 302 Hop Path --------------> Fails (Total delay = 55 > 25 and Min. BW = 20 < 30)3 Hop Path ----------> Succeeds!! (Total delay = 24 < 25, and Min. BW = 90 > 30)5 Hop Path ----------> Do not consider, although (Total Delay = 16 < 25, Min. BW = 90 > 30) ABD = 30, BW = 20D = 25, BW = 55D = 5, BW = 90D = 3, BW = 105D = 5, BW = 90D = 1, BW = 90D = 5, BW = 90D = 2, BW = 90D = 5, BW = 90D = 14, BW = 90Constraints: Delay (D) <= 25, Available Bandwidth (BW) >= 30We look for feasible path with least number of hopsBenefits of QoS Routing•Without QoS routing: •must probe path & backtrack; non optimal path, control traffic and processing OH, latency With QoS routing:•optimal route; “focused congestion” avoidance•more efficient Call Admission Control (at the source)•more efficient bandwidth allocation (per traffic class)•resource renegotiation easierThe components of QoS Routing•Q-OSPF: link state based protocol; it disseminates link state updates (including QoS parameters) to all nodes; it creates/maintains global topology map at each node•Bellman-Ford constrained path computation algorithm: it computes constrained min hop paths to all destinations at each node based on topology map•(Call Acceptance Control)•Packet Forwarding: source route or MPLSOSPF Overview5 Message Types1) “Hello” - lets a node know who the neighbors are2) Link State Update - describes sender’s cost to its neighbors3) Link State Ack. - acknowledges Link State Update4) Database description - lets nodes determine who has the most recent link state information5) Link State Request - requests link state informationOSPF Overview(cont)ABCDE1122233“Link State Update Flooding”OSPF Overview (cont)- “Hello” message is sent every 10 seconds and only between neighboring routers - Link State Update is sent every 30 minutes or upon a change in a cost of a path- Link State Update is the only OSPF message which is acknowledged- Routers on the same LAN use “Designated Router” schemeImplementation of OSPF in the QoS Simulator- Link State Update is sent every 2 seconds- No acknowledgement is generated for Link State Updates- Link State Update may include (for example): - Queue size of each outgoing queue (averaged over 10s sliding window) - Avg delay on each link - Throughput on each outgoing link (averaged over 10s sliding
View Full Document
Unlocking...