My homework in a course about computer network, coded in javascript in order to put it on my blog and give it a HTML UI to show the detailed process.

Just a simple version of selective repeat ARQ, but maybe helpful for you to understand the algorithm further.

Selective Repeat ARQ Simulation

First of all, you may wanna check the final result of the simulation: Portal to the final result

Theory

To understand how selective repeat ARQ algorithm was implemented in my program, I recommend you understand the algorithm itself first, so that the following content can be much easier to understand.

I'll show this algorithm in the following example of two host communicating

Host A and Host B are connected with each other, and A has some data that needs to send to B

Framing

  • Because the data is too long to be sent at one time (just assume so), A slice the data into several pieces, and give those data sequence numbers in order to tell the proper order to combine the data, in case that the datum are not received in original order
  • Because the message could be corrupted when transferring, the message should contain some verification code related to the message content like CRC (Cyclic Redundancy Check)
  • Because B only have information in binary, B needs to know where is the start of the message and so does the end. There should be flags wrapping the whole message and the flag never appear in the middle of the message
  • Because B would like to know the sender of the message in order to do some further communication, the sender information should be contained in the message
  • Because B maybe not the receiver of the message but only the router to transmit the message, the true receiver information should be contained in the message

So far, the message should be something like this:

| flag | destination | source | sequence | data | CRC | flag |

After such process, the message should be called as frame, which is a unit of communication in data link layer.

As for how to make flags only appear in the start and the end of a frame:

In my case, flag is 01111110 that occupies one byte of the frame. To deal with such type of flag, since there are six successive '1's in the flag, we can append a '0' every time the content of the frame appears five successive '1's. And in the decoding part, when five successive '1's was found, remove the '0' behind them, so makes the flag only appears in the start and the end of a frame

Window & Control Frame

But the sequence number could increase to infinite if A keeps sending messages, so sequence number should be limited in a specific range (usually in the range of 2^n, which makes best use of all bits).

However, when sequence numbers are in a specific range, imagine such situation:

  • A send a frame with sequence X to B

  • frame corrupted when transmitting

  • B found it corrupted by doing CRC and dropped it

  • A keeps sending following frames, and comes with another frame with sequence X

  • Under such situation, B could take this frame and think it the frame that B found corrupted

In order to make the algorithm work properly, control frame and window are introduced. Here's how these things make A stop sending frames when frames are corrupted:

  • With window and ACK (Acknowledge character) frame implemented, pretend sequence number takes 3 bits, and windows size is 3. The following text indicates sequence of sender(L) and receiver(R), contents in brackets indicates frames that are in current window:

    • At the beginning:

      { |0|1|2| } |3|4|5|6|7|0|1|2|3|... => { |?|?|?| }

    • A sends frame 0 and starts a timer for frame 0

    • B received it properly

      { |0|1|2| } |3|4|5|6|7|0|1|2|3|... => { |0|?|?| }

    • Because frame 0 is in the correct order, B transmits frame 0 to upper layer to do further process and removes frame 0 from its buffer (in order to make the process clearer, the frame 0 is still texted in the buffer), at the same time, B shifts its window forward and sends ACK frame 0 to A

      { |0|1|2| } |3|4|5|6|7|0|1|2|3|... => |0| { |?|?|?| }

    • A received ACK frame 0, so A removes frame 0 from its buffer, stops timer for frame 0, and shifts the window forward

      |0| { |1|2|3| } |4|5|6|7|0|1|2|3|... => |0| { |?|?|?| }

    • A sends frame 1 and starts a timer for frame 1

    • frame 1 corrupted when transmitting

    • B received corrupted frame and drops it

    • A sent frame 2, frame3, and B received them properly and sent ACK frame 2, 3 to A. But due to the first element in the window is not received, B could not shift the window

      |0| { |1|2|3| } |4|5|6|7|0|1|2|3|... => |0| { |?|2|3| }

    • Also, because the first element in the window didn't receive an ACK frame, A cannot move the window neither. Because A finished sending mission in the window, A stops sending the next frame, which is frame 4, and waits for B to send ACK frame 1

    • Timer for frame 1 found frame 1 overtime, so A sends frame 1 again

    • B received it properly

      |0| { |1|2|3| } |4|5|6|7|0|1|2|3|... => |0| { |1|2|3| }

    • B shifts the window, transmits frame 1, 2, 3 to upper layer, and sends ACK frame 1 to A

      |0| { |1|2|3| } |4|5|6|7|0|1|2|3|... => |0|1|2|3| { |?|?|?| }

    • A removes frame 1, 2, 3 from buffer and shifts the window

      |0|1|2|3| { |4|5|6| } |7|0|1|2|3|... => |0|1|2|3| { |?|?|?| }

  • Under such implementation, there is nearly no problems for A and B can communicate with each other. But the overtime machinic seems too time consuming if ever time a frame is corrupted A will wait for a certain period. So we can make B send a NAK (Negative Acknowledgment) frame to make A resend faster (if B can recognize the sender and sequence number of the corrupted frame)

We call ACK frames and NAK frames as control frames, and normal frames that sending data are called data frames

I think you may have a brief knowledge to selective repeat ARQ after my explanation, now I propose following principles to enhance your knowledge:

  • Sender will not shift window until the first frames in the window receives ACK frame
  • Receiver will not transmit data to upper layer nor shift the window until the frames in the window are received in the right order
  • Control frames are dropped once confirmed
  • Every frame has its timer, they are started once the frame is sent or resent

Details

  • Notice that the control frames should be sent with the highest priority. Imaging the frame sending buffer has a lot of data frames queuing to be sent. If let the control frames queue behind them, they will never get sent due to the window limit.

  • In order to tell the frame type, it's better to add a segment in frame. In my program, the frame is coded as following:

    |  flag  | type  | destination | source | sequence |      data       |  CRC   |  flag  |

    | 1 byte | 1 bit |   2 bits    | 2 bits |  4 bits  | at least 1 byte | 1 byte | 1 byte |

    So the minimal length of the frame is 41 bits. And in order to make timeout a short time to wait, the maximal length shouldn't be too long. In my program, I set max length to 65 bits, which means the data has max length of 4 bytes. When the data size is bigger than max length, the data is sliced into pieces.

  • When corruption rate of the channel is rather a big number, the max length of the frame should be shorter in order to avoid resending.

Error Control

In order to deal with flipping bit that may occur in any part of the frame, discuss every possible situation is necessary for robustness of the program

  • How receiver's binary buffer deal with flags

    If everything goes right, the binary buffer should receive: 01111110 ... 01111110, then receiver will take it out from the buffer as a frame and delete those bits in buffer

    When the binary buffer receives following stuff: ... 01111110, which means flag appears after some data. In such situation. The bin buffer should drop all the data before the flag and wait for following data

    When the binary buffer receives following stuff:01111110 ...(only a few bits)... 01111110, which means the second flag appears before the frame reaches it's minimal length. The bin buffer should drop all bits before the second flag and wait for following data

  • Start Flag

    When a bit was flipped in the start flag, receiver cannot recognize a frame anymore, the related frame drops, only waiting for timeout

  • End Flag

    When a bit was flipped in the end flag, receiver will take the start flag of the next frame as the end flag of the former one, which will break the current frame and the next frame

    However, the receiver can still get the sender address and the sequence of the first frame, so receiver will send NAK frame about the first frame to sender, but directly drop the next frame without sending NAK frame, only waiting for timeout

  • Destination

    When a bit was flipped in the destination, the receiver could not receive the frame at all, only waiting for timeout

  • Source

    When a bit was flipped in the source, the receiver will find CRC doesn't match and may send a NAK frame to a wrong host. If the wrong host happen to have connection to the receiver, it's also not a big deal since the worst situation is that the wrong host will send a frame to the receiver

  • Sequence

    When a bit was flipped in the sequence, the receiver will find CRC doesn't match and send a NAK frame about a wrong frame to the sender. Not a big deal since the worst situation is that the sender will repeat a frame and wait for the flipped frame until timeout

  • Data

    When a bit was flipped in the sequence, the receiver will find CRC doesn't match and send a NAK frame to the sender

  • CRC

    When a bit was flipped in the sequence, the receiver will find CRC doesn't match and send a NAK frame to the sender

Source

For ARQ_Simulator.js

For index.html

Postscript

I highly recommend using emoji or something intuitive in your log text when possible, which can increase your reading speed of log text significantly

Comments

⬆︎TOP