Foundations of Computer Networking chapter-3

Chapter 3 Data Link

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.

• Framing - Breaking bit stream of physical layer into recognizable groupings (e.g. adding start/stop bits).
• Error handling - Includes error detection and correction (e.g. data link layer computes parity).
• Flow control - Preventing a fast sender from overwhelming a slower receiver.
• Manage link -  Handle communication parameter negotiation (data rate, error handling method, etc.)

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.

• Unacknowledged connectionless -  Frames sent independently, appropriate where low error rates since if frame lost, damaged, or out of order, no recovery attempt is made. Used by most LANs
• Acknowledged connectionless  - Frames uniquely identified, sent independently and each acknowledged. Sender retransmit after waiting time for acknowledgment expires. May lead to duplicates and out of order frames received. Can be implemented at higher level. Used for wireless.
• Acknowledged connection-oriented - Each frame numbered/sequenced so connection appears to higher layers as a reliable bit stream.

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.

• Character count -  Has general format of:     Count <Count Characters> Count <Count Characters> ...
to send the ASCII message "ABCDEFGHI"  in three separate transmissions:  3ABC4DEFG3HI

The problem is that the message is transmitted in binary as (in hexadecimal):  0341424304344546470348494A
An error of any type in the Count field (e.g. a single bit error changes 2₁₀ = 00000010₂ to 130₁₀=10000010₂) can cause the receiver to loose count without hope of recovery.

• Character stuffing
  

• Special start/end characters can be used (e.g. STX to start and ETX to end a frame) but these characters cannot then occur in the message itself, only for framing.
• Character stuffing uses the special start/end characters for framing and allows those characters in the message also. The method is for the sender to stuff an extra special character whenever the start or end character occurs naturally so that within the message the special character always occurs in pairs. The receiver recognizes the single special character as start/end and removes from the message the first special character from pairs received. Using the special character of <DEL> and <STX> and <ETX> for start/end framing, the message:
  
              AB<DEL>C<STX><ETX>DE 
  
  would be sent as (stuffed characters are underlined):
<STX>AB<DEL><DEL>C<DEL><STX><DEL><ETX>DE<ETX>...<STX>
If the receiver loses track it can wait for the next <STX> to locate the next frame. <DEL><STX> would be recognized as data since a <DEL> in data is stuffed as <DEL><DEL>. One problem is the dependency on use of the 8-bit ASCII code.

How would the following data be sent using character stuffing?

• ABC
• <DEL><STX>A<DEL><ETX>

• Bit stuffing - Similar to character stuffing except a special bit pattern used to flag framing (e.g. 111111 marks the start of a frame). If that pattern naturally occurs (e.g. the data contains 6 1's, 111111) the sender stuffs in a 0 after natural 5 1's (11111 becomes 111110). To the receiver all 111111 are framing and all 111110 should have the 0 removed to become 11111. As with character stuffing, on a framing error the receiver can wait for the next framing bits to locate the next frame.

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

• 0000
• 1111111111
  

• Physical layer coding violations - The message itself is encoded as 0's and 1's. The framing information is some signal that does not correspond to a legal 0 or 1. With Manchester encoding below, 1 is High/Low and 0 is Low/High so framing flag could be Low/Low with no rise or fall, something that cannot occur in the message.

3.1.3 Error Control - Possible types of errors:

• Bit - where frame delivered but incomplete or contains errors.
• Frame - frame never arrives at destination.
• Acknowledgement - frame arrives at destination but acknowledgement lost or in error.

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

• feedback-based flow - receiver gives sender feedback to increase transmit rate or decrease when limit reached. Example is heating system with thermostat to control furnace, turning on when cool and off at some temperature limit. Used by TCP.
• rate-based flow - no feedback needed because protocol designed to limit the transmit rate. Example is design of doctor's office appointments which schedules patients to arrive at or below the designed carrying capacity of the system.

---

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).

• Code word - A data frame generally consists of:
  • m data bits (message)
  • r code bits
  • m + r = n bit code word.

• Hamming distance -  The number of bit positions two code words differ. 000 and 111 have a Hamming distance of 3, 101 and 000 have a distance of 2. The XOR (eXclusive OR) of two code word bits determines number of bits different. For example,

100010 XOR 011010 111000 Distance = 3

A B | A xor B 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 0

Significant in that for two codewords d distance apart, d single-bit errors can convert one to the other. For a distance of 1 a single error could convert one codeword into another, for example:


000000 is a distance of 1 from 000001, a single error changes 000000 to 000001

What is the Hamming distance between 000000 and 111100?

Parity Example

No parity				Even parity
00		m=2, r=0, d=1		000	valid		m=2, r=1, d=2
01		The change of any one		001	invalid		Adding parity doubles
10		bit results in a valid		010	invalid		the number of codewords, but
11		codeword. No error		011	valid		only half are valid. Any single bit
		can be detected.		100	invalid		error produces an invalid code.
				101	valid
				110	valid
				111	invalid

• What is the odd parity for the ASCII data: 11111111 and 11111110?
• Is data and parity bit 111100001 valid for even parity?
• Suppose that one million bits were sent with a single parity bit for error detection. Would a 1-bit error be detected? Would all errors in two bits be detected?

• Error correcting codes - To correct d errors requires a distance of 2d+1. d errors transform the codeword sent to one that is still one bit closer to the original than any other possible legal codes. The following codewords have a distance of 3, so a one bit error can be corrected. For example, if 000000 was sent and one error occurs, 100000 might be received. The closest codeword to 100000 is the original 000000 so could be corrected. Two errors might result in 110000 which would be closer to 111000, leading to an erroneous correction.
Codewords for correcting a 1-bit error

000000

000111

111000

111111

• What was sent if 000011 is received and we assume a 1-bit error occurred?
• How many errors occurred at a minimum if 011001 is received? Can it be corrected reliably? Then what to do on receiving 000011?

• Error correcting code construction - We want to construct an error correcting code with minimum check bits as overhead. For single bit error correction the limit for:

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 (0000₂-1111₂), and r=3 check bits. There are seven bits numbered from 1 to 7 with four data bits (m₃, m₂, m₁, m₀) and three check bits (p₂, p₁, p₀). Note that check bits are placed at positions numbered as a power of 2 (e.g. check bit p₂ is at position 4 = 2²) between data bits. Data bits can be in any order but below are arranged in standard high bit at left order. The m data (m₃m₂m₁m₀) and r check bits (p₂p₁p₀) 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

The p check bit values are computed from the data bits by forming the Exclusive-OR of all data bits checked by that bit as follows (note xor here is Exclusive OR):


p2 = m2 xor m1 xor m0  p1 = m3 xor m1 xor m0 p0 = m3 xor m2 xor m0

Note that the sender computes p0, p1, p2. For example: p2 = m2 xor m1 xor m0 = 1 xor 0 xor 0 = 1

The receiver can then perform the same calculation for the p check bits and if any differ a transmission  error occurred.
Error position vector: The binary representation of the error position is given by the vector (C₂, C₁, C₀), where:


C0 = p0 xor m3 xor m2 xor m0 C1 = p1 xor m3 xor m1 xor m0 C2 = p2 xor m2 xor m1xor m0

Note that the receiver computes C0, C1, C2. From the above computation of p2 = 1 and no errors in p2, m2, m1, m0 C2 = p2 xor m2 xor m1xor m0 = 1 xor 1 xor 0 xor 0 = 0

 
Example: The sender would compute the check bits and transmit both data and check bits as in the vector above. The receiver would compute the error position vector using the received data and check bit vector. For example, to send data 1100₂ the vector transmitted would be 0111100₂. Should a one bit error occur in position 4 the received vector would be 0110100₂.

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 (4₁₀ = 100₂ of the received frame is in error and should be inverted to correct the error. 

C0 = 0 xor 1 xor 1xor 0 = 0 C1 = 1 xor 1 xor 0 xor 0 = 0 C2 = 0 xor 1 xor 0 xor 0 = 1

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.

Parity


The ASCII code uses 8 data bits, so that all possible valid 8-bit codes are used. The distance is one, since each valid code is 1 bit from another valid code. Hence one error transforms any valid code to another valid code.

ASCII code with parity, 8 data bits and 1 bit parity for error checking has a distance of two, meaning each valid code + parity is at least 2 bits different from any other valid code. All valid codes are transformed by a 1 bit error into an invalid code. The invalid code is detected as an error.
Using even parity (there is an even number of 1 bits in the data and parity bit) the letter A=00100001 0 (the last bit is parity calculated by the sender). A 1-bit error anywhere in data or parity will transform the codeword to an invalid code. Suppose the parity is changed from 0 to 1, then the received code is 00100001 1. The receiver calculates the parity and recognizes the codeword to be invalid so an error occurred somewhere in the data or parity.
Note that more than one error has only a 50% chance of detection. For 11110000 0 sent, two errors could produce 11000000 0 which is still a valid code and would not be detected as an error by the receiver. Three errors producing 10000000 0 would be detected. Four errors producing 11000011 0 would not, etc. An odd number of bit errors is detected.

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 <= 2^r or 1000+10+1=1011<= 2¹⁰=1024).

Alternatively, 20 check bits could correct a 1 bit error for 1,000,00 data bits for a total of 1,000,020 bits (i.e. m+r+1 <= 2r or 1,000,00+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.

•  Polynomial codes - CRC (cyclic redundancy check) codes can be constructed that provide significantly better error detection than parity. The sender computes a checksum sent with the data. The receiver recomputes the checksum on the received data using the same method, if the received and computed checksums differ, an error has been detected, retransmit the data. 
• The method is roughly based on:
  1. Divide the data by an agreed upon divisor, the remainder is the checksum.
  2. Transmit the data and checksum remainder.
  3. Divide the received data by the agreed upon divisor. The computed and received remainder should be equal.
• The method is straightforward and is illustrated below by an example.
1. Convert data to binary: 'a'=61h=01100001

M(x)=0x⁷+1x⁶+1x⁵+0x⁴+0x³+0x²+0x¹+1x⁰ = 01100001

2. To compute checksum, divide data M(x) by a selected generator polynomial G(x). Append 0 bits to M(x) for the degree of G(x).
   

G(x)=x4+x+1 = 10011 xrM(x) = 01100001  0000                 M(x)          xr

3. Divide x^rM(x) by G(x) to get checksum, the remainder R(x). Use Exclusive OR rather than binary subtraction where a divisor divides the dividend if the same number of bits.

Q(x)  G(x)/   T(x)  R(x)= 1110

1101010 10011/011000010000 xor 10011 10110 xor 10011 10110 xor 10011 10100 xor 10011 1110 R(x)

4. The message to be transmitted, T(x), consists of the data and checksum:



T(x) = x^rM(x) xor R(x)

xrM(x)          011000010000 xor   R(x)      xor 000000001110       T(x)          011000011110

Note that the exclusive OR operation is effectively subtraction so the dividend T(x) is 011000010000 - 1110, what is left over is divisible by G(x). Example: 123/10 has remainder 3. (123-3)/10 has 0 remainder.
 

5. The receiver recomputes the checksum of T(x), the remainder is 0 when no errors detected, again because after subtracting the remainder from the dividend to form T(x), T(x) is divisible by G(x).

1101010 10011/011000011110   xor 10011 10110 xor 10011    10111 xor 10011 10011 xor 10011 00 00 0 remainder implies no error

• CRC generator selection - Selected for robustness of error detection. For example, G(x) with x+1 as a prime factor detects all odd numbers of errors. Three polynomials are international standards, one is:

            CRC-12 = x¹²+x¹¹+x³+x²+x+1 = 1100000001111 Will CRC-12 detect all odd numbers of errors?

---

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

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.   to_physical_layer(frame s) - Send the frame s to physical layer of this machine. from_physical_layer(frame r) - Receive the frame r from physical layer of this machine. to_network_layer(packet p) - Deliver a packet to the network layer. from_network_layer(packet p) - Receive a packet from network layer, assumes a packet is always available. 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. 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. stop_timer(seq_nr k) -  Stop timer number k. packet - Raw network layer data as an array of bytes or a String. frame - The data link frame that is passed to the physical layer is composed of four fields: kind - One of data, ack, or nak. seq - Frame sequence number. ack - Frame acknowledgment number. 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? Flow control? Simplex? 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:

• Receiver never gets behind, it can process incoming data infinitely fast.

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:

• Simplex - Data communication is one direction only.

The assumption dropped:

• Reliable channel - The communication channel never introduces errors (i.e. no duplicate, no missing, or damaged frames).

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.

• Sender frame - The seq and info field are used : 
• Receiver frame - The ack field is used : 

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

• As in Protocol 3, a timer determines when to retransmit unacknowledged frames.
• The sender must be able to buffer all unacknowledged frames transmitted before a timeout occurs, the number of frames buffered is termed the sender window size. Ideally, the timeout is slightly longer than the round trip time to prevent resending a frame that is about to be acknowledged. Some sliding window implementations (e.g. TCP/IP) modify the window size dynamically making it smaller when timeouts occur so fewer frames are outstanding.

Receiver Window

• The receiver must ensure that its network layer is passed data in the same sequence passed by the sender's network layer.
• The sender and receiver window do not need to be the same size but for optimal performance, the number of receiver buffers should be at least one larger than the sender window. Optimal performance under errors occurs when only the lost frame is resent.

A 1-bit Sliding Window Protocol - Protocol 4
Assumptions:

• Still assume that network layer always has data available to send.

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.

• Sender frame - The seq, ack and info field are used : 
• Receiver frame - The seq, ack and info field are used : 

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:

• The frame 1 timer is started on A when the last bit of frame 1 is output by A.
• The acknowledgement of frame 1 from B is received at A at the same time frame 4 is completely transmitted.
• Receiving the frame 1 acknowledgement stops the timer.

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

 

What is the cost of one error in frames, that is how many frames were retransmitted? What is the channel utilization? What is the effect of reducing the timeout interval? 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

What is the cost of the one frame error? Does this selective repeat improve channel utilization over go back n? 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

What was the cost of the one frame error? What is the channel utilization? Are 4 sender buffers enough given that frame 5 is sent before 1 is acknowledged? 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

What is the cost of the two frame errors? 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:

• Frame size - 1000 bits
• Transmission rate - 1 Mbps
• Distance - 1000 km. one way
• Propagation rate - 20 msec/km.

Example

• RTT = 2*distance*propagation rate = 2000 km*20 msec/km = 2*10³ * 2*10^-5sec = 4*10^-2=0.04 second
• Frame size in seconds = frame size/Transmission rate = 1000 bits/1,000,000 bits/second = 0.001 second
• Maximum frames on channel = total channel time in seconds/frame size in seconds = 0.04 seconds/0.001 seconds = 40 frames
• Sender Window size = Maximum frames on channel + 1 current frame = 40 + 1 = 41

Example

• Maximum frames on channel = 2
• Sender Window size = Maximum frames on channel + 1 frame at receiver = 2 + 1 = 3
• Sender buffer size = 2 * Window size + 1 (by observation, the text does not specify).

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:

• Transition - A change from one state to another. 
• State - Signifies a unique state of the machine. 

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 loose 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:

• 000 - Initial state, the Sender frame_to_send is  0, the Receiver expects frame 0, and the Channel delivers frame 0.
• 01A - Transition 1, the Sender frame_to_send is 0, the Receiver expects frame 1, the Channel delivers the Acknowledgement.
• 111 - Transition 2, the Sender frame_to_send is 1, the Receiver expects frame 1, and the Channel delivers frame 1.
• 10A - Transition 3, the Sender frame_to_send is 1, the Receiver expects frame 0, the Channel delivers the Acknowledgement.
• 000 - Transition 4, the Sender frame_to_send is  0, the Receiver expects frame 0, and the Channel delivers frame 0.

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:

• 000 - Transition 4 and 7, the Sender frame_to_send is  0, the Receiver expects frame 0, and the Channel delivers frame 0.
• 01A - Transition 1 and 5, the Sender frame_to_send is 0, the Receiver expects frame 1, the Channel delivers the Acknowledgement.
• 111 - Transition 2 and 8, the Sender frame_to_send is 1, the Receiver expects frame 1, and the Channel delivers frame 1.
• 10A - Transition 3 and 6, the Sender frame_to_send is 1, the Receiver expects frame 0, the Channel delivers the Acknowledgement.
• 00_  - Transition 0, the Sender frame_to_send is 0, the Receiver expects frame 0, and the Channel loses the frame.
• 01_ - Transition 0, the Sender frame_to_send is 0, the Receiver expects frame 1, and the Channel loses the frame.
• 11_ - Transition 0, the Sender frame_to_send is 1, the Receiver expects frame 1, and the Channel loses the frame.
• 10_ - Transition 0, the Sender frame_to_send is 1, the Receiver expects frame 0, and the Channel loses the frame.
• 010 - Transition 7, the Sender frame_to_send is 0, the Receiver expects frame 1, and the Channel delivers frame 0.
• 101 - Transition 8, the Sender frame_to_send is 1, the Receiver expects frame 0, and the Channel delivers frame 1.

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 loosing 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

---