3.3 Simple Data Link protocol (sample code)

Sample code in C.

Protocol Simulator sample code for Data Link Layer

Machine A sends to B. Reliable, connection-oriented service.

NA = Network layer on A.
DA = Data Link layer on A.

NB = Network layer on B.
DB = Data Link layer on B.

Definitions for Tanenbaum's sample code.

DA gets packets from NA. Puts them in frame. Calls to_physical_layer to send frame. Hardware computes checksum, appends, and sends.

DB waits for data: wait_for_event
Instead of busy loop would be suspended pending interrupt.

When frame arrives, hardware computes checksum. If error it generates event = cksum_err
If ok, event = frame_arrival and DB can then use from_physical_layer to acquire frame. Strip down to packet. Pass packet only to NB. NB is never given any frame info. Frame format can be changed without Network layer knowing.

seq_nr numbers frames 0 .. MAX_SEQ and then back to 0 again
Packet here is of fixed length MAX_PKT
Frame has 3 control fields (header) and 1 data field (packet).
Header = (frame kind, sequence no, ack no)
Frame kind - some frames contain only control info. Their data field is not used.

For error recovery, we need acks and timeouts.
Need start, stop timer.
If timer already running, start_timer resets it to cause the next timeout after another full period.
If no reply after timeout, event = timeout

NA might not have packets ready to send, or DA might not be ready to process them
enable_network_layer - NA can interrupt when it has a packet to send
disable_network_layer - NA cannot interrupt, can't send packets until DA is ready and enables again

3.3.1 Unrestricted simplex protocol

Simplex - One-way.
NA and NB always ready.
No errors. No acks or sequence nos.

Unrestricted simplex protocol.

3.3.2 Simplex stop-and-wait

NB can't process incoming data infinitely quickly.
Still one-way. No errors.

Simplex stop-and-wait.

Flow control - How to stop fast sender A swamping slow receiver B?
Can't fix speed in advance - Speed required may change as traffic and load changes.
B provides feedback. Once it has passed packet to NB, it sends back dummy frame to give permission for next.
A has to wait for this ack before sending next.
1-way in terms of actual data, but 2-way in terms of frames, so need 2-way line. But strict-alternating. So half-duplex will work.

Sender code now has wait_for_event
Note sender does not even look at incoming frame - it is always an ack.
Note receiver does not put any particular info into ack frame. Its existence is enough.

3.3.3 Simplex with error recovery

If error, assume detected via checksum.

Possible solution to errors: Add timer. Receiver only sends ack if no error. If no ack, sender re-sends.
Problem: Good frame sent and received, passed to NB. Ack sent, but ack lost. Sender sends same frame again. Don't want this to be passed to NB - NB already got it.
Solution: Sequence no. Can tell original frame apart from re-transmit.

The only ambiguity is between a frame m and its successor m+1
Sender keeps sending m until gets ack
Then, depending on whether ack got through, it sends m or m+1
So only need 1 bit sequence no. and flip it between 0 and 1 to express the frame no. we're expecting right now.

Wait for ack before sending next item: PAR (Positive Acknowledgement with Retransmission) or ARQ (Automatic repeat request).

Simplex with error recovery (re-transmit).

Sender maintains next_frame_to_send
Receiver maintains frame_expected

Look at sender:
- if event = timeout
  - just loop round, will send this one again
  else:
  - if ack = next_frame_to_send
    - then set up next one, loop round, will send it
    else (wrong or damaged ack)
    - just loop round, will send this one again
Look at receiver:
- let frame_expected = m
- if frame = m
  - then pass it to NB, increment to m+1, ack m, and wait for m+1 to come
  else didn't get m, got m-1 again
  - ack m-1, and wait for m
For example:
- if seq = expected = 0
  - expected = 1
  - ack = 0
- else
  - expected = 0 (unchanged)
  - ack = 1 (re-ack previous one)

Data Link layer service to higher layers

NB never sees duplicates or damaged frames. Data Link layer entirely hides errors from Network layer, and provides it with a reliable service for sending packets to another machine's Network layer.

Timeout should be chosen with the line in mind (allow enough time for frame to get to B and ack to get back). Again we see: Most of Data Link layer is hardware-specific, and it hides details of hardware from Network and higher layers.