- Published on
Sliding Window
- Authors
- Name
- Bowen Y
Frame Header
typedef uint8_t SwpSeqno;
typedef struct {
SwpSeqno SeqNum; /* sequence number of this frame */
SwpSeqno AckNum; /* ack of received frame */
uint8_t Flags; /* up to 8 bits worth of flags */
} SwpHdr;
Sliding Window Protocol State
typedef struct {
/* sender side state: */
SwpSeqno LAR; /* seqno of last ACK received */
SwpSeqno LFS; /* last frame sent */
Semaphore sendWindowNotFull;
SwpHdr hdr; /* pre-initialized header */
struct sendQ_slot {
Event timeout; /* event associated with send-timeout */
Msg msg;
} sendQ[SWS];
/* receiver side state: */
SwpSeqno NFE; /* seqno of next frame expected */
struct recvQ_slot {
int received; /* is msg valid? */
Msg msg;
} recvQ[RWS];
} SwpState;
A semaphore sendWindowNotFull is a synchronization primitive that supports semWait and semSignal operations. Every invocation of semSignal increments the semaphore by 1, and every invocation of semWait decrements s by 1, with the calling process blocked (suspended) should decrementing the semaphore cause its value to become less than 0.
Handle Messages
Receiver will destroy all the resending timers and events whose Sequence Number is lower(Not exactly correct, but advanced in a round) than ACK after receiving a ACK.
Sender will mark the message as received when it receives a new message, and then check if it receives all the messages in a line. If so, then send all the messages in the buffer to the higher protocol and remove all the cache. At last, send a message to the sender, including a ACK which stands for the highest Sequence Number that it has received without any vacant position in between.
static int
deliverSWP(SwpState state, Msg *frame)
{
SwpHdr hdr;
char *hbuf;
hbuf = msgStripHdr(frame, HLEN);
load_swp_hdr(&hdr, hbuf)
if (hdr->Flags & FLAG_ACK_VALID)
{
/* received an acknowledgment—do SENDER side */
if (swpInWindow(hdr.AckNum, state->LAR + 1, state->LFS))
{
do
{
struct sendQ_slot *slot;
slot = &state->sendQ[++state->LAR % SWS];
evCancel(slot->timeout);
msgDestroy(&slot->msg);
semSignal(&state->sendWindowNotFull);
} while (state->LAR != hdr.AckNum);
}
}
if (hdr.Flags & FLAG_HAS_DATA)
{
struct recvQ_slot *slot;
/* received data packet—do RECEIVER side */
slot = &state->recvQ[hdr.SeqNum % RWS];
if (!swpInWindow(hdr.SeqNum, state->NFE, state->NFE + RWS - 1))
{
/* drop the message */
return SUCCESS;
}
msgSaveCopy(&slot->msg, frame);
slot->received = TRUE;
if (hdr.SeqNum == state->NFE)
{
Msg m;
while (slot->received)
{
deliver(HLP, &slot->msg);
msgDestroy(&slot->msg);
slot->received = FALSE;
slot = &state->recvQ[++state->NFE % RWS];
}
/* send ACK: */
prepare_ack(&m, state->NFE - 1);
send(LINK, &m);
msgDestroy(&m);
}
}
return SUCCESS;
}
Three roles of the algorithm
The first role is the one we have been concentrating on in this section—to reliably deliver frames across an unreliable link.
The second role that the sliding window algorithm can serve is to preserve the order in which frames are transmitted.
The third role that the sliding window algorithm sometimes plays is to support flow control—a feedback mechanism by which the receiver is able to throttle the sender.
Ambiguity ??? How to differentiate different frames with the same sequence number?
Due to the limitation of sequence number is 2*n - 1. What will happen if they need to use the sequence number from 0 again in the second round?