Elementary data link protocols

Elementary data link protocols :--

Assumptions:
• The physical layer, data link layer, and network layer are independent processes.
• The network layer contacts the data link layer by generating proper events.
There exist suitable library procedures for the data link layer to delivery a packet ( ), and to fetch a packet ( ).
• The data link layer provides a reliable, connection-oriented service to the network layer.
• The physical layer computes/checks checksums in outgoing/incoming frames, and contacts the data link layer by generating proper events.
There exist suitable library procedures for the data link layer to send a frame ( ), and to fetch a frame ( ).
Fig. shows some declarations (in ) common to many of the protocols to be discussed later.
#define MAX_PKT 1024 /* determines packet size in bytes */

typedef enum {false, true} boolean; /* boolean type */
typedef unsigned int seq_nr; /* sequence or ack numbers */
typedef struct {unsigned char data[MAX_PKT];} packet; /* packet def. */
typedef enum {data, ack, nak} frame_kind; /* frame_kind definition */

typedef struct { /* frames are transported in this layer */
frame_kind kind; /* what kind of a frame is it ? */
seq_nr seq; /* sequence number */
seq_nr ack; /* acknowledgement number */
packet info; /* the network layer packet */
} frame;

/* Wait for an event to happen; return its type in event. */
void wait_for_event(event_type *event);

/* Fetch/pass a packet from/to the network layer */
void from_network_layer(packet *p);
void to_network_layer(packet *r);

/* Fetch/pass an inbound/outbound frame from/to the physical layer. */
void from_physical_layer(frame *r);
void to_physical_layer(frame *s);

/* Start/stop the clock running and enable/disable the timeout event */
void start_timer(seq_nr k);
void stop_timer(seq_nr k);

/* Start/stop an auxiliary timer and enable/disable the ack_timeout event */
void start_ack_timer(void);
void stop_ack_timer(void);

/* Allow/disallow the network layer to cause a network_layer_ready event */
void enable_network_layer(void);
void disable_network_layer(void);

/* Macro inc is expanded in-line: Increment k circularly */
#define inc(k) if(k < MAX_SEQ) k = k + 1; else k = 0
3.3.1. An unrestricted simplex protocol
Assumptions:
• Data transmission in one direction only.
• Channel is error free.
• The receiver is able to process incoming data infinitely fast.
/* Protocol 1 (utopia) provides for data transmission in one direction
only, from the sender to receiver. The communication channel is assumed
to be error free, and the receiver is assumed to be able to process all
the input infinitely fast. Consequently, the sender just sits in a loop
pumping data out onto the line as fast as it can */

typedef enum {frame_arrival} event_type;
#include "protocol.h"

void sender1(void)
{
frame s; /* buffer for an outbound frame */
packet buffer; /* buffer for an outbound packet */

while (true) {
from_network_layer(&buffer);/* get something to send */
s.info = buffer; /* copy it into s for transmission */
to_physical_layer(&s); /* send it on its way */
}
}

void receiver1(void)
{
frame r;
event_type event /* filled in by wait, but not used here */

while(true) {
wait_for_event(&event); /* only possiblity is frame_arrival */
from_physical_layer(&r); /* go get the inbound frame */
to_network_layer(&r.info); /* pass the data to the network layer */
3.3.2. A simplex stop-and-wait protocol
Assumptions:
• Data transmission in one direction only.
• Channel is error free.
How to prevent the sender from flooding the receiver with data ?
A general solution:
• After finishing the process of an incoming frame, the receiver sends a dummy frame back to the sender.
• Only when the sender has got the acknowledgement (a dummy frame) from the receiver, does the sender transmit another frame.
The above strategy is called stop-and-wait.
Data traffic is still simplex, but frames do travel in both directions.
The communication channel needs to be capable of bidirectional information transfer (a half-duplex physical channel suffices here).
/* Protocol 2 (stop-and-wait) also provides for a one-directional flow of
data from sender to receiver. The communication channel is once agian
assumed to be error free. However, the receiver has only a finite buffer
capacity and a finite processing speed, so the protocol must explicitly
prevent the sender from flooding the receiver with data faster than it
can be handled. */

typedef enum {frame_arrival} event_type;
#include "protocol.h"

void sender2(void)
{
frame s; /* buffer for an outbound frame */
packet buffer; /* buffer for an outbound packet */
event_type event; /* frame_arrival is the only possiblity */

while (true) {
from_network_layer(&buffer);/* get something to send */
s.info = buffer; /* copy it into s for transmission */
to_physical_layer(&s); /* send it on its way */
wait_for_event(&event); /* do not proceed until given the go ahead */
}
}

void receiver2(void)
{
frame r, s; /* buffers for frames */
event_type event /* filled in by wait, but not used here */

while(true) {
wait_for_event(&event); /* only possiblity is frame_arrival */
from_physical_layer(&r); /* go get the inbound frame */
to_network_layer(&r.info); /* pass the data to the network layer */
to_physical_layer(&s); /* send a dummy frame to awaken sender */

}
Assumptions:
• Data transmission in one direction only.
• Channel is NOT error free, but a damaged frame can be detected by the receiver hardware by computing the checksum.
A scheme using timer and acknowledgement:
• The sender starts a timer after sending a frame.
• The receiver sends back an acknowledgement only when the incoming frame were correctly received.
• The sender will retransmit the frame if the timer expired before receiving an acknowledgement.
What is the fatal flaw in the above scheme ?
Loss of an acknowledgement duplicated frame.
How to distinguish a frame being seen for the first time from a retransmission ?
Use a sequence number in the header of each frame.
What is the minimum number of bits needed for the sequence number ?
A 1-bit sequence number (0 or 1) suffices here.
/*Protocol 3 (par) */
#define MAX_SEQ 1 /* must be 1 for protocol 3 */
typedef enum {frame_arrival, cksum_err, timeout} event_type;
#include "protocol.h"

void sender3(void) {
seq_nr next_frame_to_send; /* seq number of next outgoing frame */
frame s; /* buffer for an outbound frame */
packet buffer; /* buffer for an outbound packet */
event_type event; /* frame_arrival is the only possiblity */
next_frame_to_send = 0; /* initialize outbound sequence numbers */
from_network_layer(&buffer); /* fetch first packet */
while (true) {
s.info = buffer; /* construct a frame for transmission */
s.seq = next_frame_to_send; /* insert sequence number in frame */
to_physical_layer(&s); /* send it on its way */
start_timer(s.seq); /* if answer takes too long, time out */
wait_for_event(&event); /* frame_arrival, cksum_err, timeout */
if(event == frame_arrival) {
from_network_layer(&buffer);/* get the next one to send */
inc(next_frame_to_send); /* invert next_frame_to_send */
}
}
}
void receiver3(void) {
seq_nr frame_expected;
frame r, s; /* buffers for frames */
event_type event; /* filled in by wait, but not used here */
frame_expected = 0;
while(true) {
wait_for_event(&event); /* frame_arrival, cksum_err */
if(event == frame_arrival) { /* a valid frame has arrived */
from_physical_layer(&r); /* go get the inbound frame */
if(r.seq == frame_expected){
to_network_layer(&r.info);/*pass the data to the network layer*/
inc(frame_expected); /* next time expect the other seq nr */
}
to_physical_layer(&s); /* none of the fields are used */
}
}
}