Flashcards
Flow and Congestion Control
Cards in this deck (35)
- 1Flow ControlWhy limit flow control?
>Source may send packets/frames at a rate that is faster than the processing speed of the host
>Buffer at destination could be full because {higher level protocol not ready, outgoing I/O ports not ready, destination protocols cannot process PDU as fast}
>Basically limits the amount of data being transmitted so the dest can cope - 2Important Flow Control PrinciplesStop and Wait Protocol
Sliding Window Protocol {then use Go-back-N or Select-reject when dealing with error} - 3Stop and Wait Protocol>>Source transmits then waits for ACK
>>Upon receipt of frame, dest sends an ACK
>>Dest can stop flow by not sending ACK
>>Two types of errors:
-Frame errors
-ACK errors - 4Stop and Wait Protocol (Frame Damaged)If an error is detected in the frame's sequence check, then the frame is discarded.
The source is equipped with a timer and a buffer to store one frame - the source will thus resend a frame if it does not receive an ACK BEFORE the timer expires - 5Stop and Wait Protocol (ACK Damaged)ACK is damaged on transit from A to B
>>A will transmit frame after timeout
>>B receives two copies of the same frame (frames labeled 0 or 1)
ACKs:
ACK0 = ACK for frame 1 and ready for frame 0
ACK1 = ACK for frame 0 and ready for frame 1 - 6Link utilisation IQuantitative description of link utilisation:
>Tframe = time to transmit a frame (time for transmitter to send out all bits of frame)
>Tprop = propagation time between A and B
>Tack - time to transmit an ACK - 7Link utilisation IHOST A can send frames at rate 1/Tframe without ACK
HOST A sends frames with ACK, so max throughput is:
1/(Tframe + 2 * Tprop + Tack) - 8Stop and Wait Error Free IT = time to transmit one frame, receive ACK and get ready for next frame:
>T = Tframe + Tprop + TACK + Tprop
Also assume TACK is small compared to data frame so then just becomes:
>T = Tframe + 2*Tprop
Total time to send n frames = n*T - 9Stop and Wait Error Free II
- 10Stop and Wait Error Free IIIUseful to define a paramater A:
A = Tprop/Tframe
So then: {S = 1/1+2A}
S is max possible normalised throughput for Stop and Wait - 11Determine utilisationIF a>1 (Tprop > Tframe) then link is under-utilised.
IF a<1 (Tprop < Tframe) then link is fine - 12Stop and Wait ErrorS = 1-P/1+2a
P is probability of error in a single frame - 13Sliding Window Protocol ISTOP and WAIT inefficient if Tpropr>Tframe
Increase efficiency by allowing multiple frames to propagate from A to B (sliding window)
>A is allowed to send N frames without waiting for ACKs
>B has a buffer size N and accepts N frames, and A also has buffer size N
>Each frame labeled with a number % of some max - 14Sliding Window Protocol II-B ACKs frame by indicating implicitly that it can accept the next N frames
-A maintains the list of sequence numbers it is allowed to send
-B maintains a list of sequence number it is prepared to receive
-Each of these lists are a WINDOW of frames - 15Go-back-N ARQ (Automatic Repeat Request) IError control protocol that auto transmits a call to retransmits a frame if it is damaged. (More complex protocol)
-Station A sends a series of frames sequentially
-Station B ACKs incoming frames with an RR (receiver ready)
-If B detects an error in frame k, then it sends a REJ (reject) and discards all frames greater than k until k is correctly received
AKA if 3 is error, and received 7, then 3,4,5,6,7 will resend until 3 is correct. - 16Go-back-N ARQ (Automatic Repeat Request) IIStation A transmits k in all succeeding frames that were transmitted (N) in the interim period.
A needs to go back N frames to retransmit them all again - 17Go-back-N ARQ (Automatic Repeat Request) III
- 18Go-back-N ARQ (Automatic Repeat Request) IV
- 19Go-back-N ARQ (Automatic Repeat Request) VElements:
Frame
ACK - Each frame sends a corresponding ACK
REJ - when detect error, send a REJ, as soon as REJ received, start transmitting back from damaged frame - 20Go-back-N ARQ (Automatic Repeat Request) VI [Damaged Frame]Damaged Frame:
>B detects error i frame (i)
>B sends REJ (i)
>A retransmits frame (i) and subsequent frames since (i)
Frame lost in transit:
>A sends out frame (i+1) and so on...
>When B receives frame (i+1) out of order, sends REJ (i)
>A retransmits frame (i) + remaining
Frame (i) lost and is last:
>B receives nothing and does not send REJ or RR
>A's timer expires and it requests and RR from B indicating next frame expected. Then retransmits (i) - 21Go-back-N ARQ (Automatic Repeat Request) VII [Damaged RR]RR(i) means all frames up to i-1 are ACKed
>if RR(i+1) is lost, A might receive RR(i+2) before timer expires. No frame up to i+2 needs to be retransmitted
A's timer expires and it requests an RR from B indicating that next frame expected and a new timer set. If no response received after tries, A will initiate reset. - 22Go-back-N ARQ (Automatic Repeat Request) VIII [Damaged REJ]A's timer expires and it requests RR from B indicating the next frame expected. It then retransmits (i)
- 23Selective-reject ARQOnly frames retransmitted are those that receive an NAK or SREJ, or time out
>B sends NAK(i) if frame (i) is in error or lost
>B is required to buffer frames in order until correct frame arrives
>Complex logic required to send out of sequence frames and insert into appropriate places - 24Performances [Sliding Window Error Free]The throughput depends on window size W as well as parameter A.
A:
A = Tprop/Tframe
So:
IF W>= 2A+1:
ACK1 reaches A before A has exhausted window thus S = 1.0<<<
IF W<2a+1:
A exhausts window at t=W and cannot send anymore frames until t=2A+1
thus S = W/2A+1<<< - 25Performances [Selective-reject ARQ]W>=2A+1:
S = 1-P
W<2A+1:
S = W(1-P)/2A+1 - 26Performances [Go back N ARQ]W >= 2A+1:
1-P/1+2AP
W < 2A +1:
S = W(1-P)/(2A+1)(1-P+WP) - 27Congestion ControlWhen one part of the subnet (one or more routers in area) becomes overloaded, congestion occurs
Because routers are receiving packets faster than they can forward them, one of two things must happen:
>Subnet must prevent additional packets from entering congested region until those already present can be processed
>Congested routers can discard queued packets to make room for those that are arriving - 28Factors that cause congestion>Packets arrive at rates that exceed outgoing link capacity
>Insufficient mem to store arriving packets
>Bursty traffic
>Slow processor - 29Congestion Control vs Flow ControlCongestion Control is a global issue - making sure the subnet is abled to carry the offered traffic; involves hosts, routers, store and forwarding processes etc. within subnet
Flow control - scope is point to point, involves just a sender and a receiver. - 30Congestion ControlConcerned with efficiently using network at high load
Methods:
-Warning bit
-Chock packets
-Load shedding
-Random early discard (RED)
First three are congestion detection then avoidance - 31Warning Bit>Special bit in packet set by router to warn source of congestion when detected
>Bit piggy backs on ACK sent to sender
>Sender monitors number of ACKS received with warning bits and adjusts transmission rates accordingly - 32Choke Points>Control Packet generated at congested node and transmitted to restrict traffic flow
>Source on receiving the choke packet must reduce transmission rate by %
>E.g. ICMP Quench Packet - 33Hop By Hop Choke Packets>Over long distances high speed choke packets not very effective
> More effective to send these packets hop by hop - requires each hop to reduce transmission even before choke packet arrives at source - 34Load Shedding>When buffer becomes full, routers simply discard packets
>Victim packet depends on app and on error strategy that data link layer is using
WINE POLICY: file transfer, cannot discard older packets since cause gap in received data; for real time voice - better to throw away old data - 35Random Early Discard>Proactive approach which router discards one or more packet before buffer becomes completely full
>Each time packet arrives, calcs average queue length (avg)
>If avg is lower then some threshold, then congestion assumed to be minimal;
>If higher than another threshold then congestion assumed serious and packet discarded
>If avg between thresholds then prob of congestion calculated
Information
- Description
- Flashcards on Flow and Congestion Control, created by Eric Wojcik on 14/06/2018.
- Created by
- Eric Wojcik
- Views
- 1
- Rating