Transcript Part 2
Providing QoS in IP Networks Future: next generation Internet with QoS guarantees Integrated Services: firm guarantees Differentiated Services: differential guarantees simple model for sharing and congestion studies: Principles for QoS Guarantees Example: 1Mbps IP phone, FTP share 1.5 Mbps link. bursts of FTP can congest router, cause audio packets to be excessively delayed or lost want to give priority to audio over FTP Principle 1 packet marking/classification needed for router to distinguish among packets belonging to different classes of traffic; new router policy needed to treat packets accordingly Principles for QoS Guarantees what if applications misbehave (e.g. audio sends higher than declared rate)? Principle 2 provide protection (isolation) for one class from others policing: force the flow to adhere to certain criteria Token bucket Packet classification/marking and policing done at network edge (in the host or at an edge router) Principles for QoS Guarantees Another way to provide flow isolation: allocating fixed (non- sharable) bandwidth to each flowinefficient use of bandwidth if flow doesn’t use its allocation Principle 3 While providing isolation among flows, it is desirable to use resources as efficiently as possible Principles for QoS Guarantees Basic fact of life: can not support traffic demands beyond link capacity Principle 4 Call Admission: flow declares its QoS requirement, network either accepts the flow or blocks the flow Scheduling Mechanisms scheduling: choose next packet to send on link FIFO (first in first out) scheduling: send in order of arrival to queue Drawbacks of FIFO scheduling No special treatment is given to packets from flows that are of higher priority or are more delay sensitive A greedy TCP connection can crowd out other well-behaved connections Scheduling Mechanisms Priority scheduling: Multiple priority classes, each has its own queue A packet’s priority class may depend on an explicit marking or other header info, e.g. source/dest IP address, source/dest port number, protocol ID. Transmit a packet from the highest priority class that has a nonempty queue Scheduling Mechanisms Round Robin scheduling: one queue for each flow cyclically scan the queues, serving one packet from each queue (if available) No advantage in being greedy Work-conserving queuing discipline: never allow the link to remain idle whenever there are packets queued for transmission Drawback: flow with shorter average packet size is penalized Scheduling Mechanisms Byte-by-byte round robin: One queue for each flow Scan the queues repeatedly, byte-for-byte, until find the tick on which each packet will be finished Packets sorted in order of finishing time and sent in that order Drawback: all flows are given the same bandwidth Scheduling Mechanisms Weighted Fair Queuing (WFQ): approximate fluid fair queuing (FFQ) FFQ: allows different flows to have different service shares. A separate FIFO queue for each flow sharing the link. When there are N nonempty queues, the server serves the N packets at the head of the queues simultaneously At any time t, the service rate for a nonempty queue i is wi c wj jB ( t ) where wi is the weight associated with queue i, B(t) is the set of nonempty queues, and C is the link speed. WFQ FFQ is impractical because Only one queue can receive service at a time An entire packet must be served before another packet can be served WFQ: When the server is ready to transmit the next packet at time t, it picks the first packet that would complete service in the corresponding FFQ system if no additional packets were to arrive after time t Policing Mechanisms Goal: regulate the rate at which a flow is allowed to inject packets into the network Three policing criteria: (Long term) Average Rate: how many packets can be sent per time interval crucial question: what is the interval length? Peak Rate: max. number of packets that can be sent over a short period of time. Burst Size: max. number of packets that can be sent consecutively (with no intervening idle) Policing Mechanisms Token Bucket: limit input to specified Burst Size and Average Rate. bucket can hold b tokens tokens generated at rate r token/sec Token added to bucket if bucket not full, ignored otherwise A packet must remove a token from the token bucket before it is transmitted into the network Policing Mechanisms For a token-bucket-policed flow: The max. burst size is b packets Over interval of length t: max. number of packets admitted is (r t + b) r limits the long term average rate Byte-count token bucket: Each token represents the right to send k bytes A packet can be transmitted if enough tokens are available to cover its length in bytes If a flow’s guaranteed rate is greater than or equal to the flow’s average rate, then Token bucket + WFQ = guaranteed upper bound on end-to-end delay and delay jitter, i.e., QoS guarantee!