Noiseless and Noise Channel Protocols
November 1, 2016
Categorised in: Data Communicaiton & Wireless Sensor Networks
Taxonomy of Protocols
The design of the simplest protocol with no flow or error control
The sender sends a sequence of frames without even thinking about the receiver.
To send three frames, three events occur at the sender site and three events at the receiver site.
Note that the data frames are shown by tilted boxes; the height of the box defines the transmission time difference between the first bit and the last bit in the frame.
Design of Stop-and-Wait Protocol
The sender sends one frame and waits for feedback from the receiver.
When the ACK arrives, the sender sends the next frame.
Although the Stop-and-Wait Protocol gives us an idea of how to add flow control to its predecessor, noiseless channels are nonexistent. We discuss three protocols in this section that use error control.
- Stop-and-Wait Automatic Repeat Request
- Go-Back-N Automatic Repeat Request
- Selective Repeat Automatic Repeat Request
Error correction in Stop-and-Wait ARQ is done by keeping a copy of the sent frame and retransmitting of the frame when the timer expires.
Frames from a sender are numbered sequentially.
We need to set a limit since we need to include the sequence number of each frame in the header.
If the header of the frame allows m bits for sequence number, the sequence numbers range from 0 to 2 m – 1. for m = 3, sequence numbers are: 1, 2, 3, 4, 5, 6, 7.
We can repeat the sequence number.
Sequence numbers are:
0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, …
Note: In Stop-and-Wait ARQ, we use sequence numbers to number the frames. The sequence numbers are based on modulo-2 arithmetic.
In Stop-and-Wait ARQ, the acknowledgment number always announces in modulo-2 arithmetic the sequence number of the next frame expected.
Design of the Stop-and-Wait ARQ Protocol
Stop-and-Wait ARQ Protocol
Frame 0 is sent and acknowledged.
Frame 1 is last and resent after the time-out.
The resent frame 1 is acknowledged and the timer stops.
Frame 0 is sent and acknowledged, but the acknowledgement is lost.
The sender has no idea if the frame or the acknowledgment is lost, so after the time-out, it resends frame 0, which is acknowledged.
Note: In the Go-Back-N Protocol, the sequence numbers are modulo 2m, where m is the size of the sequence number field in bits.
Send (sliding) window for Go-Back-N ARQ
Note: The send window is an abstract concept defining an imaginary box of size 2m − 1 with three variables: Sf, Sn, and Ssize.
The send window can slide one or more slots when a valid acknowledgment arrives.
Receive (sliding) window for Go-Back-N ARQ
Note: The receive window is an abstract concept defining an imaginary box of size 1 with one single variable Rn. The window slides when a correct frame has arrived; sliding occurs one slot at a time.
Design of Go-Back-N ARQ
Window size for Go-Back-N ARQ
Note: In Go-Back-N ARQ, the size of the send window must be less than 2m; the size of the receiver window is always 1.
This is an example of a case where the forward channel is reliable, but the reverse is not.
No data frames are lost, but some ACKs are delayed and one is lost.
The example also shows how cumulative acknowledgments can help if acknowledgments are delayed or lost.
After initialization, there are seven sender events.
Request events are triggered by data from the network layer; arrival events are triggered by acknowledgement from the physical layer.
There is no time-out event here because all outstanding frames are acknowledged before the timer expires. Note that although ACK 2 is lost, ACK 3 serves as both ACK 2 and ACK 3.
Note: Stop-and-Wait ARQ is a special case of Go- Back-N ARQ in which the size of the send window is 1.
Send window for Selective Repeat ARQ
Receive window for Selective Repeat ARQ
Design of Selective Repeat ARQ
Selective Repeat ARQ, window size
Note: In Selective Repeat ARQ, the size of the sender and receiver window must be at most one-half of 2m.