Transcript ppt
Congestion Control Computer Networks Spring 2000 John Kristoff 1 Where are we? Spring 2000 John Kristoff 2 Recall Data Link Layer Link level specific transmission Network Layer End-to-End host addressing and routing Transport Layer End-to-End application multiplexing and message flow-control The expert: Sally Floyd http://www.aciri.org/floyd/ Spring 2000 John Kristoff 3 Note Flow control is a subset of congestion control. The former attempts to properly match the rate of the sender with that of the network and receiver. The later deals with the sustained overload of intermediate network elements such as internetwork routers. Spring 2000 John Kristoff 4 Congestion Collapse As the network load increases, packet drops and thus packet retransmissions increase Fragments dropped are especially annoying, the remaining fragments get sent, but cannot be used As retransmissions increase, less actual work gets done Spring 2000 John Kristoff 5 Some Congestion Fixes When congestion increases, slow down! Additive Increase, Multiplicative Decrease is used in TCP Setup reservations or service classes Packets failing to adhere to their class or reservation are simply discarded or put onto a low priority queue/link Discover end-to-end MTU if fragments are getting dropped Spring 2000 John Kristoff 6 Fairness Equal share bandwidth to end stations Fair share based on application Fair share based on timeliness of data Fair share based on value of data Fair share based on price paid ...and so on Spring 2000 John Kristoff 7 Active Congestion Control Mechanisms Eligible discard Queue management Network Signaling and Notification End station avoidance Class of service signaling Quality of service reservations Spring 2000 John Kristoff 8 Eligible Discard Frames, cells or packets are marked according to a drop priority Source or edge intermediate device may mark based on some policy watermark/threshold reached data type source destination cost Usually implemented at data link or network layer Spring 2000 John Kristoff 9 Eligible Discard Illustrated Spring 2000 John Kristoff 10 Queue Management First in, first dropped (FIFO) Tail drop (LIFO) Leaky bucket Token bucket Random early detection (RED) Weighted Fair Queueing Usually implemented in intermediate devices such as routers and switches Spring 2000 John Kristoff 11 First In, First Out Illustrated Queue pointers need to be updated Sender learns of drop sooner Spring 2000 John Kristoff 12 Last In, First Out Illustrated Simple - no queue pointers to update Source cannot react as quick Spring 2000 John Kristoff 13 Leaky Bucket Illustrated Title: (05-W.eps) Creator: Adobe Illus trator(TM) 5.0 Prev iew : This EPS picture w as not s av ed w ith a preview inc luded in it. Comment: This EPS picture w ill print to a Pos tSc ript printer, but not to other ty pes of printers. From Tanenbaum Figure 5-24, graphic will print to a Postscript printer Spring 2000 John Kristoff 14 Token Bucket Illustrated Title: (05-X.eps) Creator: Adobe Illus trator(TM) 5.0 Prev iew : This EPS picture w as not s av ed w ith a preview inc luded in it. Comment: This EPS picture w ill print to a Pos tSc ript printer, but not to other ty pes of printers. From Tanenbaum Figure 5-26, graphic will print to a Postscript printer Spring 2000 John Kristoff 15 RED Illustrated Probability marking applied to each packet based on queue length, packet being dropped Spring 2000 John Kristoff 16 Weighted Fair Queueing Spring 2000 John Kristoff 17 Network Signaling and Notification Also called choke packets In Frame Relay Forward Explicit Congestion Notification (FECN) Backward Explicit Congestion Notification (BECN) Bit in frame set Experimental Internet mechanism Explicit Congestion Notification (ECN) Bits set in packets to hosts Spring 2000 John Kristoff 18 End Station Avoidance Also called end-to-end control TCP Slow start Congestion avoidance Fast Retransmit Fast Recovery Spring 2000 John Kristoff 19 Class of Service Signaling Packets marked to a particular traffic class IEEE 802.1p Differentiated Services (DiffServ) Re-defines IP Type of Service (ToS) bit fields Asynchronous Transfer Mode Spring 2000 John Kristoff 20 Quality of Service Reservations Resource ReSerVation Protocol Reserve resources in routers Requires stateful path Asynchronous Transfer Protocol (ATM) Spring 2000 John Kristoff 21