Data Link Layer Flow Control

Simplex Protocols
1. Description
  1. Allows you to not to worry about directional loading of a network
  2. But without some for of ACK, traffic can be lost without the sender's knowledge.
  3. But with some form of ACK, the sender knows about the traffic.
    1. The ACK messages can consume a large amount of bandwidth with every little return on the investment.
2. Unrestricted
  1. Send All and Wait
  2. No flow control for one-way communication
  3. Assumptions
    1. Error free data lines
    2. Receiver is never process limited
      1. Can always process anything it is sent
  4. Process
    1. Sender immediately dumps any input from the network layer to the plysical layer and assumes it will get to the receiver.
3. Stop-and-Wait
  1. Description
    1. Send part and Wait
    2. Limited (one-way) flow control that takes into account the receiver's buffer size.
  2. Assumptions
    1. Error free data lines
    2. Receive's buffer size is know and never changes.
  3. Process
    1. Sender checks to see if it has an 'all-clear' to send, and if so, immediately dumps input from the network layer to the physical layer up to the receiver's buffer size.
    2. The sender then waits for the receiver to reset its 'all-clear' flag and then, sends the next buffer full data.
4. Noisy channel
  1. Send part and a tag, wait for the tag
  2. A positive ACK with retransmission protocol
  3. Assumptions
    1. Receiver can always ACK in sequence order.
  4. Process
    1. Sender checks to see if it has an 'all-clear' to send, and if so, it adds a seq number to the network layer data (packet or part of a packet) and dumps it to the physical layer.
    2. Sender waits for an ACK (with the correct seq number) from the receiver.
      1. If it gets one, it increments the seq number and sends the next packet (or part of packet).
      2. If it times out, it resends the seq number and packet.
Duplex Protocols
1. Description
  1. Forces you to consider directional loading.
  2. Allows you to save bandwidth by bundling the ACK with the data of return messages.
  3. Frames are numbered modulo-n from 0 to n-1
  4. Terminology
    1. SWS
      1. Sender's Window Size
    2. RWS
      1. Receiver's Window Size
    3. ACK
      1. Acknowledgement
    4. NAK
      1. Non-Acknowledgement
    5. SEQ NO
      1. Sequnce Number
    6. LFA
      1. Last frame Acknowledged
    7. LAF
      1. Largest Acceptable Frame
    8. LFR
      1. Last Frame Received
2. Sliding Window Protocol
  1. Description
    1. Sender keeps copies of the transmitted frames until all of them are acknowldeged.
    2. In addition to ACK frames, receiver also has an option of NAK frames, if the data has been received damaged.
    3. Sliding window is a continuous transmission mechanism, both ACK and NAK frames must be numbered for identification.
      1. ACK frames carry the number of the next frame expected.
      2. Ex: ACK(5) tells sender that all frames upto frame 5 are received.
      3. NAK frames carry the number of the damaged frame itself.
      4. Ex: If frame 4 and 5 are damaged, NAK(4) and NAK(5) must be sent
    4. Requires to send data frames sequentially.
    5. Window size is controlled by:
      1. Number of bits.
      2. Number of slots.
      3. Sender can use same number or more than receiver.
      4. Window size = BW * RTT / Data Size
      5. Constraints on Window Size
      6. For n bits seq number; SWS + RWS <= 2^n
  2. Protocols
    1. One-Bit Protocol
      1. Description
      2. SWS = RWS = 1
      3. Both sender and receiver use a windows size of one.
      4. Assumptions
      5. No transmission latency.
      6. Advantages
      7. Simple
      8. Small SEQ NO size (1 bit)
      9. Disadvantages
      10. Both sides must be in lock step.
      11. i.e. A sends then B sends and then A sends...
      12. End up in sending a lot of dummy messages or you wait around for the other side to have something useful to send.
    2. Go Back N
      1. Description
      2. Sender uses an N size window.
      3. Receiver use a window size one.
      4. SWS = N RWS = 1
      5. The sender keeps transmitting until the number of unacknowledged frames equals its window size, then starts re-sending everything in the window.
      6. If one frame is lost or damaged, all frames sent since the LFA are re-transmitted.
      7. Assumptions
      8. A pipeline is a good idea.
      9. Continuing to send frames when the past frames have not yet been acknowledged.
      10. Advantages
      11. Fairly simple and fast.
      12. Frames are always received in order.
      13. Disadvantages
      14. When the pipeline breaks, a lot of retransmission is needed.
      15. You need a lot of timers.
      16. Can be solved with multiple virtual timers.
    3. Selective Repeat
      1. Description
      2. Both sender and receiver use a window size of > 1
      3. SWS > 1 RWS > 1
      4. Sender Keeps transmitting until it gets and a NAK, then starts re-sending everything not acknowledged.
      5. The Receiver can buffer (and reorder) frames after sending NAK. If so, it can skip forward to the ack message for the end of the buffer.
      6. This causes the sender not to resend the buffered frames.
      7. Only specific damaged or lost frame is re-transmitted.
      8. ACK number is the acknowledgement of the frame received, rather than the next expected frame.
      9. Assumptions
      10. Pipeline is a good idea.
      11. Unique SEQ NO can be generated and sent.
      12. Advantages
      13. Very fast
      14. When pipeline breaks, less retransmission is needed.
      15. Disadvantages
      16. Frames are not always received in order.
      17. Need to control the way the SEQ NO's are used.
Description
1. Ensuring the sending entity does not overwhelm the receiving entity.
  1. Preventing buffer overflow
2. Transmission time
  1. Time taken to emit all bits into medium.
3. Propagation time
  1. Time for a bit to traverse the link.