Chapter 3 - The Data Link Layer

3.1 Data Link Layer Design Issues

Between the physical layer and the network layer. Takes packets from network layer and encapsulates into frames for transmission by physical layer. Provides virtual path between source and destination network layer and provides following services to network layer.

It is important to recognize that it is sometimes, though not always,  the responsibility of the data link layer to provide the network layer with what appears to be reliable bit stream, no errors, no duplicates, no out of sequence bits.

OSI Reference Model

 

3.1.1 Services Provided to the Network Layer - Recall that lower layers provide services to higher layers that implement the actual physical path. The higher layer on the source communicates to the same layer on the destination via a virtual path created by the lower layers.

 

3.1.2 Framing - Recall RS-232 use of start and stop bit for framing the data bits between start and stop bits. The start bit serves to synchronize the receiver with the remaining bits from the sender. The sender and receiver use the same baud rate but, due to clock drift, must resynchronize on each data transmission.

Typically, the receiver tries to sample the signal at the expected middle of each bit. When the transition from 1 to 0 is detected, the receiver counts (typically 16 times the baud rate) 8 times before sampling the start bit, 16 times to the sample at the middle of the first data bit, 16 times to the next, etc.

                                           _      _____
Volts  _______|  |___|        |  |  |   |        |_____________
       1  1  1  1  0  1  1  0  0  1  0  1  0   0   1  1  1  1  1  1  1
      No data    |B|  Data 'S' ASCII code |P | E|    No data          
                                time-->                  
                                   
          B = Start bit (opposite of no data representation).
          P = Parity bit (0 as even number of 1's in ASCII 'S' code).
          E = Stop bit (same as no data representation).

It is important to note that the data link layer of the sender adds the framing information, which is used and removed by the receiver's data link layer. From the network layer view, framing is transparent as the message appears to travel directly from the sender's network layer to the receiver's, since the framing information was added and removed by the corresponding data link layers. The following are common framing methods.

How would the following data be sent using character stuffing?

How would the following data be sent using bit stuffing as described above using a framing flag of 111111?

3.1.3 Error Control - Possible types of errors:

3.1.4 Flow Control - When fast sender overwhelms slow receiver, either of which could be a host or router. Solutions:

3.2 Error Detection and Correction

Error detection is generally cheaper (in terms of additional bits in overhead) to do than error correction. Neither are always needed, audio and video can often have some errors without noticeably affecting the perceived transmission quality. Error detection makes sense whenever the data must be absolutely reliable (an ATM cash machine transaction) or when the medium is very error prone (phone lines, wireless). Error correction is reasonable when retransmitting the data is not feasible (e.g. a probe designed to crash land on Saturn) or very expensive. Much of the current practice in error detection and correction is based on work by the mathematician Hamming. Applications include not only data transmission but data storage (e.g. use of a checksum to verify data integrity on a storage device).

3.2.1 Error Correcting Codes - Codes that allow the original data to be reconstructed in the face of incurring one or more errors. Generally the more errors that can be corrected, the larger the correcting code required (in bits). 

       100010
XOR 011010
       111000    Distance = 3   
 
A B | A xor B
0 0 |    0
0 1 |    1
1 0 |    1
1 1 |    0

What is the Hamming distance between 000000 and 111100?

  • m data bits
  • r check bits
  • m+r+1 <= 2r
  • r=3 can correct one error in m=4 data bits, since m+3+1<=23 = 8, or m=4. 
  • r=4 can correct one error in m=11 data bits, since m+4+1<=24 = 16, or m=11. 
  • r=5 can correct one error in m=26 data bits, since m+5+1<=25 = 32, or m=26. 

The following is an example of a method by Hamming for constructing a minimal single bit error correcting code. The code has m=4 data bits, thus can encode 16 data values (00002-11112), and r=3 check bits. There are seven bits numbered from 1 to 7 with four data bits (m3, m2, m1, m0) and three check bits (p2, p1, p0). Note that check bits are placed at positions numbered as a power of 2 (e.g. check bit p2 is at position 4 = 22) between data bits. Data bits can be in any order but below are arranged in standard high bit at left order. The m data (m3m2m1m0) and r check bits (p2p1p0) are then organized into a vector as follows:

POSITION 1 2 3 4 5 6 7
BIT  p0  p1 m3 p2 m2 m1 m0

Data bits are checked by check bits whose position sum is equal to the position of the data bit. In this example:

m3 = p0 + p1            Position of m3 = Position of p0 + Position of p1 = 3
m2 = p0 + p2              Position of m2 = Position of p0 + Position of p2 = 5
m1 = p1 + p2              Position of m1 = Position of p1 + Position of p2  = 6
m0 = p2  + p1 + p0    Position of m0 = Position of p2 + Position of p1 + Position of p0 =7
POSITION 1 2 3 4 5 6 7
BIT  p0  p1 m3 p2 m2 m1 m0
TRANSMIT 0 1 1 1 1 0 0
RECEIVED 0 1 1 0 1 0 0

Computing the error vector yields (1, 0, 0) indicating that POSITION 4 (410 = 1002 of the received frame is in error and should be inverted to correct the error. 

3.2.2 Error Detecting Codes - To detect d errors requires a distance of d+1, no d number of  errors can change a valid code into another valid code.

It is generally cheaper to detect an error and retransmit data than to send error correcting codes.

Sending 1,000,000 data bits in frames of 1000 bits using error correcting Hamming codes requires 10 check bits per 1000 data bit frames or 10,000 extra bit to correct single bit errors, a total of 1,010,000 bits transmitted (i.e. m+r+1 <= 2r or 1000+10+1=1011<= 210=1024).

  • Alternatively, 20 check bits could correct a 1 bit error for 1,000,000 data bits for a total of 1,000,020 bits (i.e. m+r+1 <= 2r or 1,000,000+20+1<= 220=1,048,576). Why is this a bad idea?
  • A single parity bit can detect one error in a 1,000,000 bit message but the message would be retransmitted when an error was detected. Under what conditions is this a bad idea or a good idea?

Using error detection and retransmit on a detected error requires 1 parity bit per 1000 data bits or 1000 check bits for the data plus 1 additional check bit for the 1000 parity bits, a total of 1,001,001 bits transmitted error free. For 1 error per million bits, error detection and retransmit requires 1,002,002 bits to be transmitted (i.e. an additional 1001 bits retransmitted).

One key problem is the lack of robustness to error detection using parity as it can detect 100% of single bit errors but only 1/2 of more than 1 bit errors. This can be improved by observing that most errors occur in bursts and reorganizing how blocks of data are sent.

Suppose that we send two 3 bit numbers 101 and 001 with even parity, 1010 and 0011. Sending as 1010 0011, a two bit error burst might transform the underlined bits to 1100 0011 which is not detected as an error by a parity check bit. Instead of sending all of one message data bits and parity bit at once which can only detect a one bit error, a more robust approach sends the first bit of each message, then the second, etc. This provides error detection of a 2 bit burst since only one bit in each column would be changed but not any 2 bit error, better than before but not good enough. The data and parity of both is sent as:
 

10  First bit
00  Second bit
11  Third bit
01  parity

Sending 1010 0011 would be transmitted as: 10001101. A two bit error burst in the underlined bits would be received as 10111101.

A two bit error burst, such as in the underlined bits, would be detected by the parity bits when the message was reconstructed by the receiver. In general, n frames with a parity bit can detect a single n bit error burst.

3.3 Elementary Data Link Protocols

Key assumptions:

  1. Physical, data link, and network layer are independent processes that communicate by passing messages -  Each layer can operate simultaneously with the other.
  2. A reliable, connection-oriented service between machines is desired  - Essentially, the network layers of two machines can communicate on the assumption that whatever sent is received correctly (i.e. same sequence, no duplicates, no other errors).
  3. The sender always has an infinite supply of data to send - When the data link layer of the sender asks for data, the network layer always has some available.
  4. Data link assumes that the entire packet from network layer is data - When the data link layer receives a network layer packet it only need add header information for communication with the receiving machine's data link layer.

Communication between A and B machines physically occurs vertically through the network, data link, and physical layers but logically through the virtual connections between peer layers.  Transmitting the message "Hello" from A to B network layer is illustrated in the following diagram, note the header information added to the message at each layer for communication with its peer.

Software Model - The text presents a series of data link protocol examples that meet the initial assumptions above. One of our homeworks will implement some of these protocols in Java. All protocols are based upon a library of functions that implement data link services used by the network layer and in turn, access services provided by the physical layer. The examples progress from very simple protocol where messages may be lost to implementing reliable communications.

The important elements regarding the data link software are:

Data Link Software
  1. Events - Possible asynchronous events are:
    • chsum_err - The physical layer hardware detected a checksum error.
    • frame_arrival - A frame has been correctly received at the physical layer.
    • timeout - A previously set timer has run down.

  2. to_physical_layer(frame s) - Send the frame s to physical layer of this machine.

  3. from_physical_layer(frame r) - Receive the frame r from physical layer of this machine.

  4. to_network_layer(packet p) - Deliver a packet to the network layer.

  5. from_network_layer(packet p) - Receive a packet from network layer, assumes a packet is always available.

  6. wait_for_event(event e) - Wait for any event to occur. Function blocks caller execution until some event occurs, event e returns the event that occurred.

  7. start_timer(seq_nr k) - Start timer number k running for some preset time period in milliseconds and enable timer event. When timer runs out a timeout event is generated.

  8. stop_timer(seq_nr k) -  Stop timer number k.

  9. packet - Raw network layer data as an array of bytes or a String.

  10. frame - The data link frame that is passed to the physical layer is composed of four fields:
    1. kind - One of data, ack, or nak.
    2. seq - Frame sequence number.
    3. ack - Frame acknowledgment number.
    4. info - The data received/sent from/to the network layer.

3.3.1 An Unrestricted Simplex Protocol - Protocol 1

Assumptions

  1. Simplex - Communication is one direction only.
  2. Reliable channel - The communication channel never introduces errors (i.e. no duplicate, no missing, or damaged frames).
  3. Receiver never gets behind, it can process incoming data infinitely fast (no need for flow control).

Important points of note are:

  1. Independent processes - Both sender and receiver are independent processes whether running on different or the same machine.
  2. Infinite execution - Both processes are assumed to start at the same time (in reality, receiver B must start before sender A to avoid missing frames sent by A), and run forever due the while(true) execution loop in each.
  3. Frame - The data link layer passes frames between the physical layer. A frame contains a network layer packet.
  4. Packet - The data link layer passes packets between the network layer. A packet is network layer data.

The frame sent uses only an info field containing the network packet: 
Equivalent code as text and state diagram is:
 

Protocol 1 - Simplex 
Process A Process B
void sender1(void) {
 frame s;
 packet buffer;
 while (true) {
  from_network_layer(buffer); 1. get packet 
  s.info = buffer; 
  to_physical_layer(s);          2. send frame
 }
}
 
void receiver1(void) {
 frame r;
 event_type event;
 while(true) {
   wait_for_event(event);      1. wait
   from_physical_layer(r);      2. receive frame 
   to_network_layer(r.info);   3. put packet 
 }
}

 

 

 

 

The channel utilization from A to B can reach 100% as delay between sending frames is 0. The diagram below assumes 1 frame occupies the channel completely for 1 time unit to send "Hi0". The frame requires 1 time unit to transmit from A, the first bit arriving at B after 1 time unit, after 2 time units the last bit of the frame arrives at B. The arrows point between the time when a specific bit was sent and when it arrives.

 

What are some of the problems using this protocol?
  1. Flow control?
  2. Simplex?
  3. Lost frames?

3.3.2 A Simplex Stop-and-Wait Protocol - Protocol 2

The key assumptions are:

  1. Simplex - Communication is one direction only.
  2. Reliable channel - The communication channel never introduces errors (i.e. no duplicate, no missing, or damaged frames).

The most unrealistic assumption that is dropped:

The main problem then is to prevent the sender from overwhelming the receiver, this is commonly known as flow control. A simple solution is to require that the sender never transmits a new frame until the receiver has confirmed it has processed the previous frame. Data is still only sent in one direction but an empty frame is transmitted by the receiver as confirmation requiring the sender to wait before sending another data frame.

sender frame uses only the info field containing the network packet: 

receiver frame sent is empty: 

Equivalent code and state diagram as the text is:  

Protocol 2 - Stop and Wait
Process A Process B
void sender2(void) {
 frame s;
 packet buffer;
 event_type event;
 while (true) {
  from_network_layer(buffer); 1. get packet
  s.info = buffer; 
  to_physical_layer(s);           2. send frame
  wait_for_event(event);        3. confirm wait
  }
}
 
void receiver2(void) {
 frame r; 
 frame s;
 event_type event;
 while(true) {
  wait_for_event(event);     1. wait
  from_physical_layer(r);     2. receive frame 
  to_network_layer(r.info);  3. put packet
  to_physical_layer(s);        4. send confirm
 }
}

Improvements:

  1. Flow control by requiring sender to wait for a confirmation from receiver.

Problems:

  1. Deadlock when either transmit or confirmation frame lost. No way to stop waiting on either sender2 or receiver2.
  2. Delay while sender2 waits for confirmation, under-utilizing the channel.

To see why delay is a problem consider the following, assume the channel has a propagation rate of 1 time unit and all frames are 1 time unit long (e.g. a propagation rate of 1 second from A to B holds frames 1 second long). The first bit transmitted from A arrives at B 1 time unit later, the last bit arrives 2 time units after the first bit was transmitted. B cannot respond until the frame has completely arrived, it then sends a complete empty frame, which also requires 2 time units to completely arrive at A. A total of 4 time units are required to transmit 1 time unit of data frame, a channel utilization of 1/4 or 25%; wasted channel capacity of 75%.

Sending larger data frames helps; a 100 time unit long frame would require 101 seconds to fully arrive. The one time unit confirmation would be received at A after 103 time units (100 time units to send + 1 time unit before the last bit arrived at receiver + 1 time unit to emit confirm frame + 1 time unit for the last confirm bit to arrive at A) improving the utilization to  100/103 or about 97%.

Long messages make more efficient use of the channel. Why are very long messages not always a good idea?

3.3.3 A Simplex Protocol for a Noisy Channel - Protocol 3

The assumption is:

The assumption dropped:

Deadlock was possible in Protocol 2 over an unreliable channel where lost frames can occur. Protocol 3 does not deadlock in the face of errors but does still force the sender to wait until a confirmation arrives. There are two essential implications:

  1. After a fixed wait the sender will timeout and retransmit the data. This avoids deadlock when frames are lost.
  2. Each frame sent is numbered 0 or 1 and a new data frame is not sent until the previous frame is confirmed. This prevents lost or out of sequence data frames.
Protocol 3 - Positive Acknowledgment with Retransmission Protocol
Process A Process B
void sender3(void) {
 seq_nr next_frame_to_send;
 frame r;
 frame s;
 packet buffer;
 event_type event;
 next_frame_to_send = 0;
 from_network_layer(buffer);
 while (true) {
  s.info = buffer;
  s.seq = next_frame_to_send;
  to_physical_layer(s);          // send frame
  start_timer(r.seq);
  wait_for_event(event);       // ack wait
  if( event == frame_arrival) { 
   from_physical_layer(r);      // no timeout
                                         // ack'ed?
   if(r.ack == next_frame_to_send) { 
     from_network_layer(buffer);
     next_frame_send =          // 0->1, 1->0
       (next_frame_to_send+1) % 2; 
   }
  }
 }
}			
void receiver3(void) {
 seq_nr frame_expected;
 frame r;
 frame s;
 event_type event;
 frame_expected = 0;




 while (true) {
   wait_for_event(event);            // receive wait
   if( event == frame_arrival) {
    from_physical_layer(r);
    if(r.seq == frame_expected) { // expects 0 1 0 1...
      to_network_layer(r.info); 
      frame_expected =                // 0->1, 1->0
         (frame_expected+1) % 2; 
    }
    s.ack = 1 - frame_expected;    // s.ack = r.seq
    to_physical_layer(s);              // send ack
  }
 }
}

Improvements:

  1. No deadlock due to the use of a timer on the sender. If the sender does not receive a confirmation within the allocated time, the same frame is resent.
  2. No duplicates due to the use of sequence numbers (0 and 1). If the sender receives a confirmation to a frame sequence number different than the most recently transmitted, the same frame is resent. Using a binary sequence number allows only one outstanding frame at a time.

Problems:

  1. With only one outstanding frame, the utilization of the channel is not optimal (below 100%).
  2. Timeout should be longer than the round trip time (the time a frame travels to the receiver and a confirmation returns). Otherwise, time wasted sending duplicate messages unnecessarily.

Example:  The following diagram illustrates the successful transmission of two frames from A to B. Note that A sends a sequence number of 0 and B acknowledges 0. The illustration shows the contents of the channels assuming that:

  1. the first bit of the frame arrives at B the same time the last bit is transmitted at A (i.e. the channel can hold one frame),
  2. sender and receiver frames are the same size,
  3. the frame must be fully received before it can be processed (before an acknowledgement can be sent),
  4. a process on A or B can send and receive simultaneously, and
  5. processing on either end takes zero time, a rather generous assumption.

Under those assumptions, the channel utilization is only 25%. The arrows point between the time when a specific bit was sent and when it arrives. Each block corresponds to a unit of time. If the channel can hold a one second long frame, the time from when the first bit is sent until the last bit arrives is two seconds (1 second before the last bit is sent + 1 second on channel to deliver the bit). The confirmation requires the same amount of time, 2 seconds. Only 1 second of frame data is actually transmitted in 4 seconds, the channel utilization is 25%. 

 As noted before, longer frames may provide better utilization of the channel under low error rate conditions, smaller frames are generally lower utilization.

The following diagram illustrates the effect when a frame frame is lost by the physical layer. The sender A, times out and retransmits a duplicate. Receiver B acknowledges the correct frame. Note that setting the sender timeout too short (e.g. acknowledges are on the way but have not arrived) results in sending duplicates, which must be ignored by the receiver.

3.4 Sliding Window Protocols

The main problem addressed by sliding window protocols is the poor channel utilization due to the need of the sender to await confirmation to the one outstanding frame before another can be transmitted. The solution is to have several frames outstanding at a time rather than only one, the optimum number dependent upon the round trip time for the frame to travel from the sender and its acknowledgement to return. For example, if the full round trip time was 10 seconds and only a single frame was outstanding at a time, the wait would be 10 seconds for the acknowledgement to fully arrive, utilization would be only 10% for a frame of one second duration. With multiple outstanding frames and acknowledgments, for one second long frames the channel could hold 5 one second long frames from the sender and 5 acknowledgments coming back to completely fill the channel, utilization would be 100%.

Utilization Examples - Consider sending frames under the stop-and-wait regime of Protocol 2.

  1. Suppose all frames are 1 second long and channel time is 10 seconds. Emitting a frame is 1 second, transmit time 10 seconds before the last bit reaches the receiver, 1 second to emit an acknowledgement, and 10 seconds for the last acknowledgement bit to reach the sender. The total time for sending a 1 second frame and receiving the acknowledgement would be 22 seconds, the utilization would be 1 second/22 seconds or about 4.5%.
  2. Suppose that a long frame were sent and an equal size acknowledgement, one that filled the channel completely or 10 seconds. Then one frame takes 10 seconds to emit, 10 seconds before the last bit is received, 10 seconds to emit acknowledgement, and 10 seconds before the last acknowledgement bit reaches the sender. The total time between sending frames is 40 seconds, the utilization would be 10 seconds/40 seconds or 25%. In general, sending longer frames improves utilization.
  3. Suppose that a really long frame were sent, a 5 second long frame on a channel with propagation time of 1 second. The first sender bit would arrive at the receiver after 1 second. The last bit of the sent frame would arrive after 6 seconds. If the receiver instantly transmitted a one bit acknowledgement it would arrive at the sender 7 seconds after it had sent the first bit. To send 5 seconds of data requires 7 seconds. Utilization would be 5/7 or about 71%.


Sender Window

Receiver Window

A 1-bit Sliding Window Protocol - Protocol 4

Assumptions:

The protocol is symmetric so both ends are sender and receiver. Both ends must have data to send before acknowledging data received. Obviously this must be ignored for the first frame numbered 0 on each end when both must send a bogus confirmation.

Protocol 4 - A 1-bit Sliding Window Protocol 
void protocol4(void) {
  seq_nr next_frame_to_send, frame_expected;
  frame r;
  frame s;
  packet buffer;
  event_type event;
  next_frame_to_send = 0;                 // Send frame 0
  frame_expected = 0;                       // Expecting to receive frame 0
  from_network_layer(buffer);
  while (true) {
    s.info = buffer;                             // Send new frame or resend old
    s.seq = next_frame_to_send;         // frame if no ACK due to timeout
    s.ack = 1 - frame_expected;           // ACK last frame number received
    to_physical_layer(s);                   // >>
    start_timer(s.seq);                        // Start timer for this send frame
    wait_for_event(event);

    if( event == frame_arrival) {          // not a timeout
     from_physical_layer(r);                      // <
     if(r.seq == frame_expected) {            // If correct frame pass to network
       to_network_layer(r.info);                    // ^
       frame_expected =                             // Update next frame expected 
          (frame_expected+1)%2;                 //    (0->1 or 1->0)
     }
     if(r.ack == next_frame_to_send) {     // If correct ACK received get new
       from_network_layer(buffer);               // packet to send
       next_frame_to_send =                      // Update next frame to send 
          (next_frame_to_send+1)%2;          //     (0->1 or 1->0)
     }
    } 
  }
}

Exchange of Duplicate Frames Due to Start-up Conditions

A

next_frame
_to_send		 frame
_expected		 s.ack s.seq s.info r.ack r.seq r.info
0 0 >1 >0 A1 <1 <0 ^B1
0 1 >>0 >>0 A1 <0 <0 B1
1 1 >>0 >>1 A2 <0 <1 ^B2
1 0 >>1 >>1 A2 <1 <1 B2
0 0 >>1 >>0 A3 <1 <0 ^B3
0 1 >>0 >>0 A3 <0 <0 B3

B

next_frame
_to_send		 frame
_expected		 s.ack s.seq s.info r.ack r.seq r.info
0 0 >1 >0 B1 <1 <0 ^A1
0 1 >>0 >>0 B1 <0 <0 A1
1 1 >>0 >>1 B2 <0 <1 ^A2
1 0 >>1 >>1 B2 <1 <1 A2
0 0 >>1 >>0 B3 <1 <0 ^A3
0 1 >>0 >>0 B3 <0 <0 A3

Improvements:

  1. Data is bi-directional.
  2. Sender and receiver are symmetrical.

Problems:

  1. With only one outstanding frame, the utilization of the channel is not optimal (below 100%).
  2. Timeout should be slightly longer than the round trip time (the time a frame travels to the receiver and a confirmation returns). Otherwise, time wasted sending duplicate messages unnecessarily.
  3. As the above tables indicate, the two processes continue to alternate sending duplicates.
    Why?
    Would changing the initial s.ack=1 to s.ack=0 prevent the cycle?
    Would it create another problem? Consider that each must initially acknowledge a frame not yet received.

No Errors Example - If no errors occur, the channel utilization can approach 100% given the assumption that the network layer always has data available and the sender has sufficient memory to buffer multiple unacknowledged frames. The interaction is illustrated in the following diagram where the channel holds exactly one frame in either direction. 

The timeout interval is 3 for the following assumptions:

Go Back N Example:    The following diagram illustrates a go back n Sliding Window Protocol when the receiver window is size 1 and a sender window of 4. The sender has a timeout interval of 3 so must at least buffer three unacknowledged frames and the one frame in error. The arrows point to the time interval when a frame is received. When errors occur, the receiver discards all frames received until the frame with the sequence number following the last correctly received frame number arrives. The sender must go back to the oldest unacknowledged frame and start resending all subsequent frames. If the sender's timeout interval is 3 frames long allowing 4 frames to be unacknowledged, all 4 frames will necessarily need to be resent in the face of an error.

  1. Each frame has a timer.
  2. Sender A sends frame 0, 1, 2, and 3 starting a timer for each after frame completely sent.
  3. Sender A receives an acknowledgement of frame 0 before the 3 frames long timeout occurs. Timeout would occur at the end of sending frame 3 if frame 0 not acknowledged.
  4. Frame 1 is not received so no acknowledgement is returned. A timeout occurs for frame 1 on the sender after frame 4 is completely sent.
  5. Receiver B discards frames 2-4 as they arrive because frame 1 must be delivered to the network layer first and the receiver window holds only 1 frame.
  6. Sender A resends unacknowledged frames 1-4 as the timeout occurs for each.
  7. Frame 5 is sent after an acknowledgement of frame 2 is received since the timeout interval is 3 frames long and 3-5 is within the interval.

Go Back N

  1. What is the cost of one error in frames, that is how many frames were retransmitted?
  2. What is the channel utilization?
  3. What is the effect of reducing the timeout interval?
  4. What is the effect of increasing the timeout interval?

Selective Repeat Example:    The following diagram illustrates a selective repeat Sliding Window Protocol when the receiver window size is large, able to buffer at least 4 frames in the case where the sender timeout interval is 3 frames (4 frame buffer required for the 3 frames sent during timeout interval + 1 frame being transmitted). The arrows point to the time interval when a frame is received.

  1. A sends frame 0, 1, 2, and 3 starting a timer for each after being completely sent.
  2. A receives an acknowledgement of frame 0 before the 3 frame long timeout occurs so sends frame 4.
  3. Frame 1 is not received so frame 0 acknowledgement (i.e. last correctly received frame) is returned with data from B and a sender timeout occurs for frame 1 on A.
  4. B buffers frame 2-4 because frame 1 must be delivered to the network layer first.
  5. A resends unacknowledged frame 1.
  6. B receives frame 1 and acknowledges frames 1-4 by acknowledging frame 4. 

Selective Repeat with 1 error and 4 buffers

  1. What is the cost of the one frame error?
  2. Does this selective repeat improve channel utilization over go back n?
  3. What can you say about the number of buffers available on the sender for the above diagram?

Even though frame 1 timed out and must be retransmitted, the text algorithm optimistically assumes that frames 2, 3, etc. will be acknowledged later. This is only possible where ample buffers are available on the sender.

  1. A sends frame 0, 1, 2, and 3 starting a timer for each after being completely sent.
  2. A receives an acknowledgement of frame 0 before the 3 frame long timeout occurs so sends frame 4.
  3. Frame 1 is not received so frame 0 acknowledgement (i.e. last correctly received frame) is returned with data from B and a sender timeout occurs for frame 1 on A.
  4. B buffers frame 2-4 because frame 1 must be delivered to the network layer first.
  5. A resends unacknowledged frame 1 followed by frame 5 and resets the timers on 1-4.
  6. B receives frame 1 and acknowledges frames 1-4 when acknowledging frame 4. Delivers frames 1-4 to network layer.
  7. Ack 4 arrives at A before frame 1 timeout.
  8. B receives, acknowledges and delivers to network layer frame 5, 6, 7, ...

Selective Repeat with 1 error and more than 4 buffers on Sender and Reciever

  1. What was the cost of the one frame error?
  2. What is the channel utilization?
  3. Are 4 sender buffers enough given that frame 5 is sent before 1 is acknowledged?
  4. What can you say about the number of buffers available on the sender for the above diagram?

Selective repeat with 2 errors and more than 4 buffers

  1. What is the cost of the two frame errors?
  2. What is the minimum number of buffers available on the sender for the above diagram?

Improvements:

  1. Piggyback data - Data is always sent along with an acknowledgement, possible only because of assumption that network layer always has data available.
  2. Bidirectional - No longer simplex data.
  3. Symmetric - The same algorithm runs on both processes. Problem is how to start both at same instant without sending duplicates or acknowledging frame not yet received.

Problems:

  1. Blocks - Blocks receive network layer when send network layer has no data.

It is important to note that go back n and selective repeat have the same utilization characteristics when no errors, the sender's window size determines the utilization when errors. If the sender has sufficient buffers to hold all outstanding frames, utilization can be 100%. They differ in utilization when errors occur and frames must be resent.

Sender Window Size Calculation - The sender window defines the frames sent but not acknowledged (i.e. frames buffered before timeout occurs). How large a window size is required at a minimum to buffer outstanding frames on the sender? The relevant parameters usually known are number of bits per frame, transmission rate, propagation rate, and distance. Consider the following:

Example

Example

Receiver buffer size for selective repeat - The number of buffers on the receiver is equal to the window size of the sender + 1 for receiving. With a sender window size of 3 the receiver will require 4 buffers at a minimum.

Sender buffer size for selective repeat - We observed that when the number of sender buffers are limited to 4 for a window size of 3 the selective repeat performs no better than go back n. By observation, we determined that 7 sender buffers are needed for a window size of 3 for 1 or 2 errors occurring in the window.


3.5 Protocol Specification and Verification


3.5.1 Finite State Machines - Common concept used in computer science and for protocol models. A state diagram is used to represent finite state machine operation. A finite state machine diagram consists of:

A finite state machine with a transition Z from state X to state Y is represented by: 

Example: Protocol 1 - Each state is labeled by three characters SRC (S = Sender, R = Receiver, C = Channel) which can each have the value of D for data or _ for empty. The initial state is D_D where the sender is transmitting Data, the channel holds Data, and the receiver has not received Data. Transition 0 consists of the channel delivering its contents to the receiver, a state where all have data. Since the channel is assumed to never lose data, transition 1 returns to the DDD state.

Example: Protocol 3 where no frame is ever lost - The states are labeled by SRC and have S = 0 or 1 for the frame_to_send, R = 0 or 1 for the frame_expected, and C = 0 or 1 for the sequence number or A for an acknowledgement. The states and transitions have the following meaning:

Example:    Protocol 3 where the channel may lose frames. The states are labeled by SRC and have S = 0 or 1 for the frame_to_send, R = 0 or 1 for the frame_expected, and C = 0 or 1 for the sequence number, A for an acknowledgement, or _ for empty when the channel loses the frame. The states and transitions have the following meaning:

Trace the transitions for sending and receiving 2 frames with no errors.

Trace the transitions given that in state 10A the frame is lost.

Transitions

Transition Who
runs?		 Frame
accepted		 Frame
emitted		 To
Network
0   Lost Lost  
1 R 0 A Yes
2 S A 1  
3 R 1 A Yes
4 S A 0  
5 R 0 A No
6 R 1 A No
7 S timeout 0  
8 S timeout 1  

The normal operation, without losing frames, the transitions are 1-2-3-4 which delivers 2 packets to the network layer of the receiver. If a frame is lost at state 111 the transitions are 0-8,  transition 0 when the frame 1 is lost, then 8 when the sender times out and resends frame 1.

A lost acknowledgement is somewhat more complex since it could be due to the frame or acknowledgement being lost. In state 10A the receiver has acknowledged frame 1 and is now expecting frame 0 next. A lost acknowledgement takes transitions 0-8-6 to state 10_, 101 on sender timeout, and back to 10A to recover.

Protocol 3 - Positive Acknowledgment with Retransmission Protocol
Process A Process B Sender Receiver Channel
void sender3(void) {
 seq_nr next_frame_to_send;
 frame r;
 frame s;
 packet buffer;
 event_type event;
 next_frame_to_send = 0;
 from_network_layer(buffer);
 while (true) {
  s.info = buffer;
  s.seq = next_frame_to_send;
  to_physical_layer(s);         
  start_timer(r.seq);
  wait_for_event(event);     
  if( event == frame_arrival) { 
   from_physical_layer(r);    
                                          
   if(r.ack == next_frame_to_send) {   
     from_network_layer(buffer);
     next_frame_send =       
       (next_frame_to_send+1) % 2; 
   }
  }
 }
}
 
void receiver3(void) {
 seq_nr frame_expected;
 frame r;
 frame s;
 event_type event;
 frame_expected = 0;



 while (true) {
   wait_for_event(event);          
   if( event == frame_arrival) {
    from_physical_layer(r);
    if(r.seq == frame_expected) {     
      to_network_layer(r.info); 
      frame_expected =                
         (frame_expected+1) % 2; 
    }
    s.ack = 1 - frame_expected;  
    to_physical_layer(s);            
  }
 }
}
 S = 0 or 1 for the frame_to_send
R = 0 or 1 for the frame_expected
C = 0 or 1 for the sequence number or A for an acknowledgement.

 

 

 


3.6 Example Data Link Protocols

3.6.2 The Data Link Layer in the Internet - LANs use broadcast protocols (Ethernet) to connect many hosts but interconnection of LANs into larger networks is primary done through routers running a point-to-point protocol. In the case of the Internet, point-to-point protocol is also used to connect host to router in the form of an Internet Service Provider. Two point-to-point protocols widely ised on the Internet are SLIP and PPP.

SLIP - Serial Line Internet Protocol. Designed to connect hosts to the Internet over serial communications.

  1. Send raw IP packets over serial (possibly modem) line with C0 hex at end for framing, if occurs in IP packet uses character stuffing.
  2. Recent versions use TCP and IP header compression by omitting when multiple packets going to same destination.
  3. No error detection/correction, responsibility of higher layers.
  4. Supports only IP.
  5. No authentication (though could be handled by higher layers).
  6. Fixed IPs, both must know each others in advance (not a problem if yours and ISP never change).

PPP - Point-to-Point Protocol. Fixes many of SLIPs problems and is an official Internet protocol RFC 1663.

  1. Supports multiple protocols (foreign protocols are tunneled inside PPP by placing a foreign packet inside a  PPP packet payload). Network Control Protocol.
  2. Allows negotiation of IP at connection time (dynamic allocation by Internet host). Link Control Protocol used for negotiation.
  3. Error detection by checksum.
  4. Permits authentication.
Flag frame
01111110		 Address
11111111		 Control
00000011		 Protocol of payload
LCP, NCP, IP, IPX, Appletalk		 Payload
default 1500 bytes		 Checksum Flag frame
01111110

Document last modified: