13-06-2014, 04:31 PM
Data Link Layer Protocols
Data Link.doc (Size: 52.5 KB / Downloads: 11)
Motivation
Look at successive data link protocols of increasing complexity to provide realiable, in order message delivery to the network layer
Environment
Assume DLL executes as a process with routines to communicate with the Network Layer above and the Physical Layer below.
Deal with messages (packets)--bit strings
frames are the unit of transmission. Consists of data plus control bits (header information).
procedure wait (var event: EvType);
{wait for an event; return event type in 'event'}
Look at data structures in Fig. 3-8
Utopia/Unrestricted Simplex Protocol
• data transmission in one direction only (simplex)
• no errors take place on the physical channel
• the sender/receiver can generate/consume an infinite amount of data.
• always ready for sending/receiving
Simplex Stop-and-Wait Protocol
Drop assumption that receiver can process incoming data infinitely fast
stop-and-wait--protocols where the sender sends one frame and then waits for acknowledgement.
In this protocol, the contents of the acknowledgement frame are unimportant.
Data transmission is one directional, but must have bidirectional line. Could have a half-duplex (one direction at a time) physical channel.
Simplex Protocol for a Noisy Channel
What if the channel is noisy and we can lose frames (checksum incorrect).
Simple approach, add a time out to the sender so it retransmits after a certain period and retransmit the frame.
Scenario of what could happen:
• A transmits frame one
• B receives A1
• B generates ACK
• ACK is lost
• A times out, retransmits
• B gets duplicate copy (sending on to network layer)
One Bit Sliding Window Protocol
Two-way communication. One-way is not realistic.
Have two kinds of frames (kind field):
1. Data
2. Ack (sequence number of last correctly received frame)
piggybacking--add acknowledgement to data frames going in reverse direction.
For better use of bandwidth. How long to wait for outgoing data frame before sending the ACK on its own.
Example of a sliding window protocol. Contains a sequence number whose maximum value MaxSeq is .
For stop-and-wait sliding window protocol n=1.
• Essentially protocol 3, except ACKs are numbered, which solves early time out problem.
• protocol works, all frames delivered in correct order
• requires little buffer space
• poor line utilization (next page)
Problem with stop and wait protocols is that sender can only have one unACKed frame outstanding.
Pipelining
Sender does not wait for each frame to be ACK'ed. Rather it sends many frames with the assumption that they will arrive. Must still get back ACKs for each frame.
Example 1: Use a 3-bit sequence number (0-7). Now we can transmit 7 frames (seq. nr. 0-6) before receiving an ACK.
Example 2: What if we allow the sender to send 8 (0-7) instead of 7 (0-6) frames?
Potential problem of window sizes (receiver window size of one):
MaxSeq is 7 (0 through 7) is valid. How big can sender window be?
1. Send 0-7.
2. Receive 0-7 (one at a time) and send ACKS
3. All ACKS are lost
4. Message 0 times out and is retransmitted
5. Receiver accepts frame 0 (why?--because that is next frame) and passes it to NL.
Window Size Rule: The sender window size (number of buffers) plus the receiver window size (number of buffers) must be where n is the number of bits in the sequence number.
Example 3: Provides more efficient use of space and works well if we follow the window size rule and do not get errors. What if an error occurs?
What if 7 frames transmitted (seq nr 0-6), and sequence number 1 has an error. Frames 2-6 will be ignored at receiver side? Sender will have to retransmit.
Protocol Performance
Protocol Performance
What is the channel efficiency of a stop-and-wait protocol?
• F = frame size = D + H = data + header bits
• C = channel capacity (bps)
• I = propagation delay and IMP service time (seconds)
• A = ack size (bits)
Draw picture
time between frames: F/C + 2I + A/C
time spent sending data: D/C
efficiency: