Transcript set_9
Computer Networks Set 9 Congestion in Data Networks What Is Congestion? Ñ Congestion occurs when the number of packets being transmitted through the network approaches the packet handling capacity of the network Ñ Congestion control aims to keep number of packets below level at which performance falls off dramatically Ñ Data network is a network of queues Ñ Generally 80% utilization is critical Ñ Finite queues mean data may be lost Queues at a Node Effects of Congestion Ñ Packets arriving are stored at input buffers Ñ Routing decision made Ñ Packet moves to output buffer Ñ Packets queued for output transmitted as fast as possible Ñ Statistical time division multiplexing Ñ If packets arrive to fast to be routed, or to be output, buffers will fill Ñ Can discard packets Ñ Can use flow control Ñ Can propagate congestion through network Interaction of Queues Ideal Performance Practical Performance Ñ Ideal assumes infinite buffers and no overhead Ñ Buffers are finite Ñ Overheads occur in exchanging congestion control messages Effects of Congestion No Control Congestion control Ñ Many policies affect congestion control: acks, retransmits, routing algorithms, Virtual circuits... Ñ Two major families fo congestion control: Openloop, closed-loop. Ñ Open-loop: Prevent conditions that lead to congestion, e.g. Leacky bucket, token bucket: Traffic shaping. Ñ Closed-loop: Deal with congestion when it happens: Use current information about network to deal with congestion. Mechanisms for Congestion Control Backpressure Ñ If node becomes congested it can slow down or halt flow of packets from other nodes Ñ May mean that other nodes have to apply control on incoming packet rates Ñ Propagates back to source Ñ Can restrict to logical connections generating most traffic Ñ Used in connection oriented that allow hop by hop congestion control (e.g. X.25) Ñ Not used in ATM nor frame relay Ñ Only recently developed for IP Choke Packet Ñ Warning is either generated by monitoring outgoing line utilization or queue lengths (weighted). Ñ Control packet Ñ Generated at congested node Ñ Sent to source node Ñ e.g. ICMP source quench Ñ From router or destination Ñ Source cuts back until no more source quench message Ñ Sent for every discarded packet, or anticipated Ñ Rather crude mechanism Implicit Congestion Signaling Ñ Transmission delay may increase with congestion Ñ Packet may be discarded Ñ Source can detect these as implicit indications of congestion Ñ Useful on connectionless (datagram) networks Ñ e.g. IP based Ñ (TCP includes congestion and flow control - see chapter 17) Ñ Used in frame relay LAPF Explicit Congestion Signaling Ñ Network alerts end systems of increasing congestion Ñ End systems take steps to reduce offered load Ñ Backwards Ñ Congestion avoidance in opposite direction to packet required Ñ Forwards Ñ Congestion avoidance in same direction as packet required Categories of Explicit Signaling Ñ Binary Ñ A bit set in a packet indicates congestion Ñ Credit based Ñ Indicates how many packets source may send Ñ Common for end to end flow control Ñ Rate based Ñ Supply explicit data rate limit Ñ e.g. ATM Traffic Management Ñ Fairness Ñ Quality of service Ñ May want different treatment for different connections Ñ Reservations Ñ e.g. ATM Ñ Traffic contract between user and network Congestion Control in Packet Switched Networks Ñ Send control packet to some or all source nodes Ñ Requires additional traffic during congestion Ñ Rely on routing information Ñ May react too quickly Ñ End to end probe packets Ñ Adds to overhead Ñ Add congestion info to packets as they cross nodes Ñ Either backwards or forwards Required Reading Ñ Stallings chapter 12