Test 2 Flashcards
What is the Sliding Window Algorithm: Sender- Variables
Variables:
send window size (SWS) : the upper bound on the no. of un-ACK frames the sender can trans
- last ACK received (LAR) :
- last frame sent (LFS) :
- expiry timer : one for each frame sent, starts decr-ing when sender trans
- Relationship between variables : LFS - LAR <= SWS
What is the Sliding Window Algorithm: Sender-Process
Process:
- Sender assigns a sequence number (seqNum) to each frame
- When an ACK arrives, sender incr LAR. Sender can now send another frame
- If a frame expiry timer expires, sender retrans frame and re-starts timer
- requires buffer size of (frame_size x SWS)
To prevent To prevent network congestion and not to over-run the receiver, there can be
at most how many outstanding messages, for Sliding window?
SWS (Sender Window Size)
What is the Sliding Window Algorithm: Receiver- Variables
Receiver keeps the following vars:
- receive window size (RWS) : the upper bound on the no. of out-of-order frames the receiver is willing to accept
- largest acceptable frame (LAF) :
- last frame received (LFR) :
- Relationship between variables : LAW - LFR <= RWS
- seqNumToACK : the largest seq no. not yet ACK by receiver (aka ALL frames <= this have been received and ACK)… when sent by receiver, the receiver is ACK the receipt of all frames up to that seq num… this is a cumulative acknowledgement
What is the Sliding Window Algorithm: Receiver-Process
- When receiver gets a frame and seqNum <= LFR or seqNum > LAF [aka frame is outside the receiver’s window], the receiver will discard the frame
- When receiver gets a frame and LFR < seqNum <= LAF [aka the frame is within window], frame is accepted.
- After a frame is accepted, receiver will send a seqNumToACK in an cumACK to sender. Then sets LFR = seqNumToACK and LAF = (LFR + RWS)
- actually, this step may be skipped sometimes
Sliding Window: When timing out, should the sender retransmit everything from LAR+1 up
to LFS, or just retransmit LAR+1?
Both things will work, however, the general consensus is just to retransmit LAR+1 if RWS =
SWS.
If RWS = 1, then you might as well retransmit everything from LAR+1
up to LFS.
Sliding Window (cumulative ack)-- Sender Event : if LFS < LAR + SWS What is the response?
resp: LFS := LFS + 1; send frame(LFS) to receiver
Sliding Window (cumulative ack)- Sender Event: receive ack(i) from receiver What is the response?
resp: LAR := max(LAR, i)
Sliding Window (cumulative ack)-- Sender Event: if LAR < LFS What is the response?
resp: send frame(LAR + 1) to receiver
Sliding Window (cumulative ack)-- Receiver Event: receive frame(j) from sender What is the response?
if j < NFE
then akn := true {old message}
elseif j ≥ NFE + RWS
then skip {no buffer space}
elseif NFE ≤ j < NFE + RWS
then rcvd[j mod RWS] := true; {place data in buffer}
while rcvd[NFE mod RWS] do
{deliver frame(NFE) }
rcvd[NFE mod RWS] := false;
NFE := NFE + 1;
akn := true
end while
end ifCumulative acknowledgment with small sequence number and message reorder in the Sliding Window protocol:
Does not work.
Individual Acknowledgment with small sequence number and message reorder in the Sliding Window Protocol:
Does Work.
In Cumulative Acknowledgement, at all times:
within(LAR+r1, NFE, LFS+r1) AND within(LAR, LFS, LAR+rSWS)
For Cumulative Acknowledgement w/ bounded seq Nos.,
to prevent confusion at the receiver:
r >= SWS + RWS
ALOHA: Maximum Propagation Time equation:
Tp = (maxDistanceBetweenStations)/(SignalPropagationSpeed)
ALOHA: Back-off time equation:
TB = (ARandomNumber:R)x Tp
or
R x Tfr(Average transmission time for a frame).
ALOHA: Average Frame Transmission Tim Equation:
NumOfBitsperFrame/kbps of the channel.
