chapter 12 congestion in data networks

chapter 12 congestion in data networks

اسلاید 1: William Stallings Data and Computer CommunicationsChapter 12Congestion in Data Networks

اسلاید 2: What Is Congestion?Congestion occurs when the number of packets being transmitted through the network approaches the packet handling capacity of the networkCongestion control aims to keep number of packets below level at which performance falls off dramaticallyData network is a network of queuesGenerally 80% utilization is criticalFinite queues mean data may be lost

اسلاید 3: Queues at a Node

اسلاید 4: Effects of CongestionPackets arriving are stored at input buffersRouting decision madePacket moves to output bufferPackets queued for output transmitted as fast as possibleStatistical time division multiplexingIf packets arrive to fast to be routed, or to be output, buffers will fillCan discard packetsCan use flow controlCan propagate congestion through network

اسلاید 5: Interaction of Queues

اسلاید 6: Ideal Performance

اسلاید 7: Practical PerformanceIdeal assumes infinite buffers and no overheadBuffers are finiteOverheads occur in exchanging congestion control messages

اسلاید 8: Effects of Congestion - No Control

اسلاید 9: Mechanisms for Congestion Control

اسلاید 10: BackpressureIf node becomes congested it can slow down or halt flow of packets from other nodesMay mean that other nodes have to apply control on incoming packet ratesPropagates back to sourceCan restrict to logical connections generating most trafficUsed in connection oriented that allow hop by hop congestion control (e.g. X.25)Not used in ATM nor frame relayOnly recently developed for IP

اسلاید 11: Choke PacketControl packet Generated at congested nodeSent to source nodee.g. ICMP source quenchFrom router or destinationSource cuts back until no more source quench messageSent for every discarded packet, or anticipatedRather crude mechanism

اسلاید 12: Implicit Congestion SignalingTransmission delay may increase with congestionPacket may be discardedSource can detect these as implicit indications of congestionUseful on connectionless (datagram) networkse.g. IP based(TCP includes congestion and flow control - see chapter 17)Used in frame relay LAPF

اسلاید 13: Explicit Congestion SignalingNetwork alerts end systems of increasing congestionEnd systems take steps to reduce offered loadBackwardsCongestion avoidance in opposite direction to packet requiredForwardsCongestion avoidance in same direction as packet required

اسلاید 14: Categories of Explicit SignalingBinaryA bit set in a packet indicates congestionCredit basedIndicates how many packets source may sendCommon for end to end flow controlRate basedSupply explicit data rate limite.g. ATM

اسلاید 15: Traffic ManagementFairnessQuality of serviceMay want different treatment for different connectionsReservationse.g. ATMTraffic contract between user and network

اسلاید 16: Congestion Control in Packet Switched NetworksSend control packet to some or all source nodesRequires additional traffic during congestionRely on routing informationMay react too quicklyEnd to end probe packetsAdds to overheadAdd congestion info to packets as they cross nodesEither backwards or forwards

اسلاید 17: ATM Traffic ManagementHigh speed, small cell size, limited overhead bitsStill evolvingRequirementsMajority of traffic not amenable to flow controlFeedback slow due to reduced transmission time compared with propagation delayWide range of application demandsDifferent traffic patternsDifferent network servicesHigh speed switching and transmission increases volatility

اسلاید 18: Latency/Speed EffectsATM 150Mbps~2.8x10-6 seconds to insert single cellTime to traverse network depends on propagation delay, switching delayAssume propagation at two-thirds speed of lightIf source and destination on opposite sides of USA, propagation time ~ 48x10-3 secondsGiven implicit congestion control, by the time dropped cell notification has reached source, 7.2x106 bits have been transmittedSo, this is not a good strategy for ATM

اسلاید 19: Cell Delay VariationFor ATM voice/video, data is a stream of cellsDelay across network must be shortRate of delivery must be constantThere will always be some variation in transitDelay cell delivery to application so that constant bit rate can be maintained to application

اسلاید 20: Time Re-assembly of CBR Cells

اسلاید 21: Network Contribution to Cell Delay VariationPacket switched networksQueuing delaysRouting decision timeFrame relayAs above but to lesser extentATMLess than frame relayATM protocol designed to minimize processing overheads at switchesATM switches have very high throughputOnly noticeable delay is from congestionMust not accept load that causes congestion

اسلاید 22: Cell Delay Variation At The UNIApplication produces data at fixed rateProcessing at three layers of ATM causes delayInterleaving cells from different connectionsOperation and maintenance cell interleavingIf using synchronous digital hierarchy frames, these are inserted at physical layerCan not predict these delays

اسلاید 23: Origins of Cell Delay Variation

اسلاید 24: Traffic and Congestion Control FrameworkATM layer traffic and congestion control should support QoS classes for all foreseeable network servicesShould not rely on AAL protocols that are network specific, nor higher level application specific protocolsShould minimize network and end to end system complexity

اسلاید 25: Timings ConsideredCell insertion timeRound trip propagation timeConnection durationLong termDetermine whether a given new connection can be accommodatedAgree performance parameters with subscriber

اسلاید 26: Traffic Management and Congestion Control TechniquesResource management using virtual pathsConnection admission controlUsage parameter controlSelective cell discardTraffic shaping

اسلاید 27: Resource Management Using Virtual PathsSeparate traffic flow according to service characteristicsUser to user applicationUser to network applicationNetwork to network applicationConcern with:Cell loss ratioCell transfer delayCell delay variation

اسلاید 28: Configuration of VCCs and VPCs

اسلاید 29: Allocating VCCs within VPCAll VCCs within VPC should experience similar network performanceOptions for allocation:Aggregate peak demandStatistical multiplexing

اسلاید 30: Connection Admission ControlFirst line of defenceUser specifies traffic characteristics for new connection (VCC or VPC) by selecting a QoSNetwork accepts connection only if it can meet the demandTraffic contractPeak cell rateCell delay variationSustainable cell rateBurst tolerance

اسلاید 31: Usage Parameter ControlMonitor connection to ensure traffic cinforms to contractProtection of network resources from overload by one connectionDone on VCC and VPCPeak cell rate and cell delay variationSustainable cell rate and burst toleranceDiscard cells that do not conform to traffic contractCalled traffic policing

اسلاید 32: Traffic ShapingSmooth out traffic flow and reduce cell clumpingToken bucket

اسلاید 33: Token Bucket

اسلاید 34: ATM-ABR Traffic ManagementSome applications (Web, file transfer) do not have well defined traffic characteristicsBest effortsAllow these applications to share unused capacityIf congestion builds, cells are droppedClosed loop controlABR connections share available capacityShare varies between minimum cell rate (MCR) and peak cell rate (PCR)ARB flow limited to available capacity by feedbackBuffers absorb excess traffic during feedback delayLow cell loss

اسلاید 35: Feedback MechanismsTransmission rate characteristics:Allowed cell rateMinimum cell ratePeak cell rateInitial cell rateStart with ACR=ICRAdjust ACR based on feedback from networkResource management cellsCongestion indication bitNo increase bitExplicit cell rate field

اسلاید 36: Variations in Allowed Cell Rate

اسلاید 37: Cell Flow

اسلاید 38: Rate Control FeedbackEFCI (Explicit forward congestion indication) markingRelative rate markingExplicit rate marking

اسلاید 39: Frame Relay Congestion Control Minimize discardsMiantain agreed QoSMinimize probability of one end user monoplySimple to implementLittle overhead on network or userCreate minimal additional trafficDistribute resources fairlyLimit spread of congestionOperate effectively regardless of traffic flowMinimum impact on other systemsMinimize variance in QoS

اسلاید 40: TechniquesDiscard strategyCongestion avoidanceExplicit signalingCongestion recoveryImplicit signaling mechanism

اسلاید 41: Traffic Rate ManagementMust discard frames to cope with congestionArbitrarily, no regard for sourceNo reward for restraint so end systems transmit as fast as possibleCommitted information rate (CIR)Data in excess of this liable to discardNot guaranteedAggregate CIR should not exceed physical data rateCommitted burst sizeExcess burst size

اسلاید 42: Operation of CIR

اسلاید 43: Relationship Among Congestion Parameters

اسلاید 44: Explicit SignalingNetwork alerts end systems of growing congestionBackward explicit congestion notificationForward explicit congestion notificationFrame handler monitors its queuesMay notify some or all logical connectionsUser response Reduce rate

اسلاید 45: Required ReadingStallings chapter 12