CS 414 – Multimedia Systems Design Lecture 17 – Multimedia Transport Subsystem (Part 3)Administrative OutlinePerformance GuaranteesRate Control Earliest Due Date (EDD) [Ferrari]Delay EDDWeighted Fair QueuingWFQ vs FQComparison between WFQ and Jitter Control Jitter Control Non-Work-Conserving SchemesImplementation of Stop-and-GoJitter-EDDError Control Design of Error Correction CodesError Control Go-back-N Retransmission Jitter Control in Slack Automatic Repeat Request SchemeAdaptationConclusionCS 414 - Spring 2011CS 414 – Multimedia Systems DesignLecture 17 –Multimedia Transport Subsystem (Part 3)Klara NahrstedtSpring 2011CS 414 - Spring 2011 HW1 due March 2 Midterm, MONDAY, March 7, 11-11:50 in classAdministrativeOutline Establishment Phase Negotiation, Translation Admission, Reservation Transmission Phase Traffic Shaping Isochronous Traffic Shaping – Leaky Bucket Shaping Bursty Traffic – Token Bucket Rate Control Error Control AdaptationCS 414 - Spring 2011Performance Guarantees Every traffic management needs QUEUE MANAGEMENT (QM) Statistical versus Deterministic Guarantees Conservation of Work QM schemes differentiate if they are work conserving or not Work conserving system – sends packet once the server has completed service (examples – FIFO, LIFO) Non-work conserving scheme – server waits random amount of time before serving the next packet in queue, even if packets are waiting in the queueCS 414 - Spring 2011Rate Control Multimedia networks use rate-based mechanisms (conventional networks use window-based flow control and FIFO)CS 414 - Spring 2011Work-conserving schemes Non-work-conserving schemesFair Queuing Jitter Earliest-Due-DateVirtual Clock Stop-and-GoDelay Earliest-Due-Data Hierarchical Round-RobinEarliest Due Date (EDD) [Ferrari] Based on Earliest Deadline First Scheduling Policy EDD works for periodic message models Packet has end-to-end deadline Di EDD partitions end-to-end deadline Diinto local deadlines Di,kduring connection establishment procedureCS 414 - Spring 2011Delay EDD Upon arrival of Packet j of connection i: Determine effective arrival time: aei,j= max(aei,j-1+ pi, ai,j) Stamp packet with local deadline: di,j= aei,j + Di,k Process packets in EDF order Delay EDD is greedy Problem with EDD: jitterCS 414 - Spring 2011Weighted Fair QueuingCS 414 - Spring 2011WFQ vs FQ Both in WFQ and FQ, each data flow has a separate FIFOqueue. In FQ, with a link data rate of R, at any given time the Nactive data flows (the ones with non-empty queues) are serviced simultaneously, each at an average data rate of R / N. Since each data flow has its own queue, an ill-behaved flow (who has sent larger packets or more packets per second than the others since it became active) will only punish itself and not other sessions. WFQ allows different sessions to have different service shares. If N data flows currently are active, with weights w1,w2...wN, data flow number i will achieve an average data rate of R * wi/(w1+w2+…+wn)CS 414 - Spring 2011Comparison between WFQ and Jitter Control WFQ guarantees packet delay less than a given value D, but as long as delay is within bound it does not guarantee what the delay will be Example: send packet at time t0 over a path whose minimum delay is d WFQ guarantees that packet arrives no later than t0+d, but packets can arrive any time t0+ x between[t0+d, t0+D] . x is jitterCS 414 - Spring 2011Jitter Control Non-Work-Conserving SchemesCS 414 - Spring 2011Implementation of Stop-and-GoCS 414 - Spring 2011Jitter-EDD Delay-EDD: does not control jitter. This has effect on buffer requirements. Jitter-EDD is non-greedy. Jitter-EDD maintains Ahead Time ahi,j, which is the difference between local relative deadline Di,k-1and actual delay at switch k-1. Ahead time is stored in packet header Upon receiving j-th packet of connection i with ahi,jat time ai,j: Calculate ready time at switch k: aei,j=max(aei,j-1+ pi, ai,j) ri,j= max(aei,j, ai,j+ ahi,j) Stamp packet with deadline di,j=ri,j+Di,kand process according to EDF starting from ready time ri,j.CS 414 - Spring 2011Error Control Error Detection Ability to detect the presence of errors caused by noise or other impairments during transmission from sender to receiver Traditional mechanisms: check-summing, PDU sequencing Checksum of a message is an arithmetic sum of message code words of a certain word length (e.g., byte) CRC – Cyclic Redundancy Check – function that takes as input a data stream of any length and produces as output a value (commonly a 32-bit integer) – can be used as a checksum to detect accidental alteration of data during transmission or storage Multimedia mechanisms: byte error detection at application PDU, time detection CS 414 - Spring 2011Design of Error Correction Codes Automatic repeat-request (ARQ) Transmitter sends the data and also an error detection code, which the receiver uses to check for errors, and requests retransmission for erroneous data The receiver sends ACK (acknowledgement of correctly received data) Forward Error Correction (FEC) Transmitted encodes the data with an error-correcting code (ECC) and sends the coded msg. No ACK exists. CS 414 - Spring 2011Error Control Error Correction Traditional mechanisms: retransmission using acknowledgement schemes, window-based flow control Multimedia mechanisms: Go-back-N Retransmission Selective retransmission Partially reliable streams Forward error correction Priority channel coding Slack Automatic Repeat RequestCS 414 - Spring 2011Go-back-N Retransmission CS 414 - Spring 2011Jitter Control in Slack Automatic Repeat Request SchemeCS 414 - Spring 2011Adaptation Transmission Phase needs traffic management with rate control and error control It also needs monitoring and adaptation Network adaptation Source adaptation Feedback from network to source or feedback from out source Adaptive rate control Traffic shapingCS 414 - Spring 2011Conclusion Establishment Phase Negotiation, Translation Admission, Reservation Transmission Phase Traffic Shaping Isochronous Traffic Shaping Shaping Bursty Traffic Rate Control Error Control Adaptation Next: Case Studies of Multimedia ProtocolsCS 414 - Spring
View Full Document
Unlocking...