DLL purpose? The goal of the data link layer is to provide reliable, efficient communication between adjacent machines connected by a single communication channel. Specifically:
At least, the above is what the OSI reference model suggests. As we will see later, not everyone agrees that the data link layer should perform all these tasks.
If we don't follow the OSI reference model as gospel, we can imagine providing several alternative service semantics:
Connection state keeps track of sending order and which frames require retransmission. For example, receiver state includes which frames have been received, which ones have not, etc.
When would such a service be appropriate?
Typically, each frame is assigned a unique sequence number, which the receiver returns in an acknowledgment frame to indicate which frame the ACK refers to. The sender must retransmit unacknowledged (e.g., lost or damaged) frames.
The DLL translates the physical layer's raw bit stream into discrete units (messages) called frames. How can the receiver detect frame boundaries? That is, how can the receiver recognize the start and end of a frame?
Disadvantage: Receiver loses synchronization when bits become garbled. If the bits in the count become corrupted during transmission, the receiver will think that the frame contains fewer (or more) bits than it actually does. Although checksum will detect the incorrect frames, the receiver will have difficulty resynchronizing to the start of a new frame. This technique is not used anymore, since better techniques are available.
Problem: What happens if the reserved delimiter happens to appear in the frame itself? If we don't remove it from the data, the receiver will think that the incoming frame is actually two smaller frames!
Solution: Use bit stuffing. Within the frame, replace every occurrence of two consecutive 1's with 110. E.g., append a zero bit after each pair of 1's in the data. This prevents 3 consecutive 1's from ever appearing in the frame.
Likewise, the receiver converts two consecutive 1's followed by a 0 into two 1's, but recognizes the 0111 sequence as the end of the frame.
Example: The frame ``1011101'' would be transmitted over the physical layer as ``0111101101010111''.
Note: When using bit stuffing, locating the start/end of a frame is easy, even when frames are damaged. The receiver simply scans arriving data for the reserved patterns. Moreover, the receiver will resynchronize quickly with the sender as to where frames begin and end, even when bits in the frame get garbled.
The main disadvantage with bit stuffing is the insertion of additional bits into the data stream, wasting bandwidth. How much expansion? The precise amount depends on the frequency in which the reserved patterns appear as user data.
Use reserved characters to indicate the start and end of a frame. For instance, use the two-character sequence DLE STX (Data-Link Escape, Start of TeXt) to signal the beginning of a frame, and the sequence DLE ETX (End of TeXt) to flag the frame's end.
Problem: What happens if the two-character sequence DLE ETX happens to appear in the frame itself?
Solution: Use character stuffing; within the frame, replace every occurrence of DLE with the two-character sequence DLE DLE. The receiver reverses the processes, replacing every occurrence of DLE DLE with a single DLE.
Example: If the frame contained ``A B DLE D E DLE'', the characters transmitted over the channel would be ``DLE STX A B DLE DLE D E DLE DLE DLE ETX''.
Disadvantage: character is the smallest unit that can be operated on; not all architectures are byte oriented.
The advantage of encoding violations is that no extra bandwidth is required as in bit-stuffing. The IEEE 802.4 standard uses this approach.
Finally, some systems use a combination of these techniques. IEEE 802.3, for instance, has both a length field and special frame start and frame end patterns.
Error control is concerned with insuring that all frames are eventually delivered (possibly in order) to a destination. How? Three items are required.
In some systems, the receiver also returns a negative acknowledgment (NACK) for incorrectly-received frames. This is nothing more than a hint to the sender so that it can retransmit a frame right away without waiting for a timer to expire.
Retransmission timers are used to resend frames that don't produce an ACK. When sending a frame, schedule a timer to expire at some time after the ACK should have been returned. If the timer goes off, retransmit the frame.
Flow control deals with throttling the speed of the sender to match that of the receiver. Usually, this is a dynamic process, as the receiving speed depends on such changing factors as the load, and availability of buffer space.
One solution is to have the receiver extend credits to the sender. For each credit, the sender may send one frame. Thus, the receiver controls the transmission rate by handing out credits.
In some cases, the data link layer service must be ``opened'' before use:
In data communication, line noise is a fact of life (e.g., signal attenuation, natural phenomenon such as lightning, and the telephone repairman). Moreover, noise usually occurs as bursts rather than independent, single bit errors. For example, a burst of lightning will affect a set of bits for a short time after the lightning strike.
Detecting and correcting errors requires redundancy -- sending additional information along with the data.
There are two types of attacks against errors:
To understand errors, consider the following:
To detect d 1-bit errors requires having a Hamming Distance of at least d+1 bits. Why?
To correct d errors requires 2d+1 bits. Intuitively, after d errors, the garbled messages is still closer to the original message than any other legal codeword.
For example, consider parity: A single parity bit is appended to each data block (e.g. each character in ASCII systems) so that the number of 1 bits always adds up to an even (odd) number.
The Hamming Distance for parity is 2, and it cannot correct even single-bit errors (but can detect single-bit errors).
As another example, consider a 10-bit code used to represent 4 possible values: ``00000 00000'', ``00000 11111'', ``11111 00000'', and ``11111 11111''. Its Hamming distance is 5, and we can correct 2 single-bit errors:
For instance, ``10111 00010'' becomes ``11111 00000'' by changing only two bits.
However, if the sender transmits ``11111 00000'' and the receiver sees ``00011 00000'', the receiver will not correct the error properly.
Finally, in this example we are guaranteed to catch all 2-bit errors, but we might do better: if ``00111 00111'' contains 4 single-bit errors, we will reconstruct the block correctly.
What's the fewest number of bits needed to correct single bit errors? Let us design a code containing n=m+r bits that corrects all single-bit errors (remember m is number of message (data) bits and r is number of redundant (check) bits):
Thus, each message requires n+1 bits dedicated to it (n that are one bit away and 1 that is the message).
This formula gives the absolute lower limit on the number of bits required to detect (and correct!) 1-bit errors.
Hamming developed a code that meets this lower limit:
For instance, consider the ascii character ``a'' = ``1100001''.
We know that:
Note: Hamming Codes correct only single bit errors. To correct burst errors, we can send b blocks, distributing the burst over each of the b blocks.
For instance, build a b-row matrix, where each row is one block. When actually sending the data, send it one column at a time. If a burst error occurs, each block (row) will see a fraction of the errors, and may be able to correct its block.
Error correction is most useful in three contexts:
Error correction is relatively expensive (computationally and in bandwidth).
For example, 10 redundancy bits are required to correct 1 single-bit error in a 1000-bit message. Detection? In contrast, detecting a single bit error requires only a single-bit, no matter how large the message.
The most popular error detection codes are based on polynomial codes or cyclic redundancy codes (CRCs).
Allows us to acknowledge correctly received frames and to discard incorrect ones.
The most popular error detection codes are based on polynomial codes or cyclic redundancy codes. Idea:
For example, represent the string ``11011'' as the polynomial:
The presence of a remainder indicates an error. What sort of errors will we catch?
Note: is not divisible by G(x) if it contains two or more terms. Thus, we can detect double-bit errors if G(x) does not divide for any k up to the message size.
Satisfactory generator polynomials can be found. , for instance, does not divide for .
What transmitted message will be an error but still generate a checksum of zero on receiving end? (T(x) + E(x))/G(x) so if E(x) = G(x).
There are currently three international standards:
Note: 16-bit CRCs detect all single and double errors, all errors with odd number of bits, all burst errors of length 16 bits, and 99.997% of 17-bit errors.
Is usually done in hardware!
Message-digest algorithm for compressing a large message.
Take a message and produce a 128-bit message digest. This compact form can be used to validate the received copy of the message.