Chapter 3: Data-link layer Flashcards
Data-link verification implications
Data that is sent over a network needs to have attributes that allow it to be investigated for errors, without data content itself being relevant.
Framing
A data stream is separated into discrete sections
4 types of framing
Byte count
Flag bytes with byte stuffing
Flag bits with bit stuffing
Physical layer coding violations
(what kind of names are these ???)
Simplex protocol
Any protocol that allows for unidirectional transmission
Often incorporated into complex protocols that allow for bidirectional transmission
Duplex protocols
Protocols with bidirectional transmission.
Sliding window protocols
Protocols that make use of a control window to determine who gets to send what data when.
Two main functions of a data-link layer
Error detection and correction
Flow control
Error detection and correction
EMI, attenuation and other events can cause data corruption. There must be a method to check for errors to then request for corrections
Flow control
The possibility exists that the sender sends faster than the receiver. The data link layer uses various techniques to limit traffic.
Frames
In error detection and correction, data is received as discrete segments. This makes sending requests easier. These sections of data are called frames.
Frame technique: Byte count
Define the size of the frame based on a set number of bytes. One problem is that if a delay occurs, every frame received after the delay is corrupted.
How Byte count corrupts after delay
It lies in how the physical layer distinguishes between bits, namely to check for changes in the state of the channel (wave changes) within a specified time frame.
If data arrives late, the receiver will insert additional bits into the delay period. This makes all the frames incorrect.
Framing: flag bytes with byte stuffing
Specify a byte that indicates the start and end of a frame. This is the byte flag, which protects against delay errors. Every new frame must start with the byte flag, and the receiver knows exactly which frames need repairs. As the flag byte is inserted by the data-link layer, it also needs to be removed, but sometimes it forms part of the data being sent.
Escape byte
Is defined in the protocol of “flag bytes with byte stuffing”. It precedes a flag byte and looks like a flag byte but isnt actually one. This byte is why this framing is called byte stuffing
Framing: flag bits with bit stuffing
Flag bytes cost a lot of bandwidth. To reduce this, rather look for bit patterns, and use the bit patterns as flags.
Example, if we have 111110, a 0 is injected after five 1s. If another set of 111110 is found, remove the 0 to keep integrity.
Thus making a bit stuffing more bandwidth efficient.
Framing: Physical layer coding violations
This method makes use of reserved signals on the physical layer. But it isn’t used often.
Simplex protocol
These protocols transmit frames to a receiver
Utopian simplex protocol
This assumes that the channel is perfect, and there is no noise and the receiver can receive data at any speed.
Not very useful, but it introduces the basic structure of functional simplex protocol.
Stop-and-wait protocol for noise-free
This addresses the fact that a receiver may not be able to keep up with the speed of the sender. It still assumes that data cannot be corrupted in any way.
Stop and wait protocol for noise
Most complex simplex protocol, it addresses data corruption and manages data flow.
Utopian simplex protocol expanded
All it does is get data from the network layer, creates frames, and then sends the frames to the physical layer.U
Utopian simplex protocol receiver side
It receives data from the physical layer, reconstructs the data from the frames and sends the data to the network layer.
SEE FLOW DIAGRAM ON EFUNDI
Stop and wait protocol for an error free channel
Stop-and-wait includes a measure of flow control and gets its name from how it achieves this.
The protocol sends frames one-by-one, and waits for the receiver, after each frame, to tell it that it’s okay to send the next.
When the receiver received the frame, it sends a dummy frame called an acknowledgement (ACK), through the physical layer to the sender to let it know the frame was received.
SEE EFUNDI FOR FLOW DIAGRAMS
Stop-and-wait protocol for a noisy channel
Extension of the previous that includes provisions for a noisy channel.
Two main issues of stop-and-wait for noisy channel
- There is always the chance that a frame is damaged so badly that it needs to be resent.
- There is also always the possibility that a frame may be lost completely, and therefore never arrived.
SW-noisy: First issue
This is easily solved using acknowledgements. If the frame is severely damaged, the receiver must notify the sender to resend the frame.
SW-noisy: Second issue
The receiver never receives the frame, and never sends an acknowledgement back. The sender enters an idle state. The same occurs when the acknowledgement is lost. One obvious solution is to add a timer
SW-noisy: timeout
When a sender never receivers an ACK, and after a timer runs out, resends the frame. It is a common strategy used in network protocols.
One problem is that if the channel is slow, then the sender times out even if the frame is received later. This leads to data corruption.
SW-noisy: Sequence number
Solves the problem of a slow channel. A receiver checks a frame’s sequence number to ensure that it is the correct frame, and sends back the sequence number as an acknowledgement.
If the sender receives a mismatched sequence number, then it resends the frame.
SW-noisy: Sequence number requirement
Only a 1-bit sequence number is needed, as the receiver only needs to check if the same frame has been received.
SEE FLOW DIAGRAM ON EFUNDI
Piggybacking
Instead of using a reverse channel to send an ACK, we use the same channel the sender used.
ACK’s are hooked onto the next outgoing frames instead of being sent immediately.
Improves bandwidth efficiency, as you don’t need a whole frame for ACK’s. Can result in timeout errors.
Minimising channel idle
Waiting for the entire SW-noisy process to complete for one frame each time can be very time-consuming. The solution is to let multiple frames travel one way at a time.
Sliding window protocol basic idea
Both the sender and receiver have a set number of sequence numbers, and both have a sliding window that delimits the sequence numbers.
This sliding window determines the sequence numbers of frames that may be sent or received, introducing flow control. SM-noisy uses 1 bit window sizes, but this is slow. Best solution is increase bit sizes
Retransmission of larger window sizes: Go-Back-N
A frame should only be accepted as valid if it is itself valid (not corrupted), and that all previous frames were valid.
Here, a damaged from is discarded, and the previous ACK is resent. The sender discards all other frames and sends the one needed.
Has a lot of wasted frames.
Selective repeat
Buffers all undamaged frames in memory when they are received.
When a damaged or lost frame is encountered that needs to be retransmitted, the receiver makes use of Negative Acknowledgments (NAK) to let the sender know which frames should be retransmitted.
