Congestion Control 1 Principles of Congestion Control Congestion: informally: “too many sources sending too much data too fast for network to handle” different from flow control! manifestations: lost packets (buffer overflow at routers) long delays (queueing in router buffers) a top-10 problem! Transport Layer 3-2 Causes/costs of congestion: scenario 1 Host A two senders, two receivers one router, infinite buffers no retransmission Host B lout lin : original data unlimited shared output link buffers large delays when congested maximum achievable throughput Transport Layer 3-3 Causes/costs of congestion: scenario 2 one router, finite buffers sender retransmission of lost packet Host A Host B lin : original data l'in : original data, plus retransmitted data lout finite shared output link buffers Transport Layer 3-4 Causes/costs of congestion: scenario 2 (goodput) = l out in “perfect” retransmission only when loss: always: l l > lout in retransmission of delayed (not lost) packet makes (than perfect case) for same R/2 l in lout R/2 larger R/2 lin a. R/2 lout lout lout R/3 lin b. R/2 R/4 lin R/2 c. “costs” of congestion: more work (retrans) for given “goodput” unneeded retransmissions: link carries multiple copies of pkt Transport Layer 3-5 Causes/costs of congestion: scenario 3 four senders Q: what happens as l in and l increase ? multihop paths timeout/retransmit in Host A lin : original data lout l'in : original data, plus retransmitted data finite shared output link buffers Host B Transport Layer 3-6 Causes/costs of congestion: scenario 3 H o s t A l o u t H o s t B another “cost” of congestion: when packet dropped, any “upstream transmission capacity used for that packet was wasted! Transport Layer 3-7 Approaches towards congestion control two broad approaches towards congestion control: end-end congestion control: no explicit feedback from network congestion inferred from end-system observed loss, delay approach taken by TCP network-assisted congestion control: routers provide feedback to end systems single bit indicating congestion (SNA, DECbit, TCP/IP ECN, ATM) explicit rate sender should send at Transport Layer 3-8 Network assisted congestion control Active Queue Management monitor queue, do not just drop upon overflow more intelligent decisions maintain low average queue length, alleviate phase effects, enforce fairness Explicit Congestion Notification (ECN) Instead of dropping, set a bit; reduced loss - major benefit! Explicit Congestion Control (ECN) Receiver informs sender about bit; sender behaves as if a packet was dropped actual communication between end nodes and the network Typical incentives: sender = server; efficiently use connection, fairly distribute bandwidth use ECN as it was designed receiver = client; goal = high throughput, does not care about others ignore ECN flag, do not inform sender about it Need to make it impossible for receiver to lie about ECN flag when it was set Solution: nonce = random number from sender, deleted by router when setting ECN Sender believes “no congestion” if correct nonce is sent back ECN Bits in IP Header 2 bits => 4 ECN Codepoints Source: http://www.cis.udel.edu/~yackoski/856_ecn.ppt Value Name 00 Not-ECT (Not ECN Capable Transport) 10 ECT(0) (ECN Capable Transport (0) ) 01 ECT(1) (ECN Capable Transport(1) ) 11 CE (Congestion Experienced) ECN Bits in TCP Header ECE flag - ECN-Echo flag CWR flag - Congestion Window Reduced flag Source: http://www.cis.udel.edu/~yackoski/856_ecn.ppt ECN in action ACKs S ende r R eceive r C ong estion 1 S end pack et w ith E C T = 1, C E = 0, no nc e = rand om 2 E C T = 1, so d on ’t drop up da te : C E = 1 no nc e = 0 3 R ed uce cw nd , set C W R = 1 O n ly se t E C E = 1 in A C K s aga in w h en C E = 1 D ata packets 4 S et E C E = 1 in su bseq ue nt A C K s eve n if C E = 0 5 Nonce provided by bit combination: ECT(0): ECT=1, CE=0 ECT(1): ECT=0, CE=1 Nonce usage specification still experimental Case study: ATM ABR congestion control ABR: available bit rate: “elastic service” RM (resource management) cells: if sender’s path sent by sender, interspersed “underloaded”: sender should use available bandwidth if sender’s path congested: sender throttled to minimum guaranteed rate with data cells bits in RM cell set by switches (“network-assisted”) NI bit: no increase in rate (mild congestion) CI bit: congestion indication RM cells returned to sender by receiver, with bits intact Transport Layer 3-14 Case study: ATM ABR congestion control two-byte ER (explicit rate) field in RM cell congested switch may lower ER value in cell sender’ send rate thus maximum supportable rate on path EFCI bit in data cells: set to 1 in congested switch if data cell preceding RM cell has EFCI set, sender sets CI bit in returned RM cell Transport Layer 3-15 Questions?