Phase 1: Connection is established by initializing variables and counters. Phase 2: One or more frames are transmitted. Phase 3: Connection is released, freeing up resources.
Single bit and Burst Error.
To keep a fast sender from overloading a slow receiver with data.
It is a service where source and destination machines establish a connection before data transfer, ensuring each frame is numbered and received exactly once in the correct order.
The kr check bits make blocks of km data bits immune to a single burst error of length k or less.
The data is divided into chunks of 4 bits: 0111, 0011, and 0101.
The code can correct double (2) errors.
Flag bytes indicate the starting and ending of a frame in data link layer protocols.
011100101010
The Hamming code can correct one error per codeword, allowing the entire block to be restored even if a burst error of length k affects at most 1 bit in each of the k codewords.
A parity bit is appended to the data to ensure that the number of 1 bits in the codeword is either even or odd, allowing for the detection of single-bit errors.
10 check bits are needed at 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 bit locations.
101
Packets are encapsulated into frames for transmission over the physical network, and each frame contains the packet along with additional information such as source and destination addresses.
Error-correcting codes are used to detect and correct errors in data transmission or storage.
The three stages are: (a) the original data, (b) the data as they appear on the transmission line, and (c) the data as they are stored in the receiver’s memory after destuffing.
Framing refers to a method where a frame is delimited by flag bytes.
If the counts match, it is assumed that the complete transmission was received without errors.
To provide a service interface to the network layer.
0000, indicating no error.
The appropriate delimiter must be present at the end position, and the checksum must be correct.
Position 1 checks bits 1, 3, 5, 7, 9, 11 for even parity, confirming that 0 in position 1 is correct.
The CRC is used to create a frame check sequence that ensures the outgoing frame is precisely divisible by a fixed number, allowing for error detection.
The sender starts a timer that is set to expire after an interval long enough for the frame to reach the destination and for the acknowledgement to return.
The receiver divides the data into n bit chunks, including the checksum, resulting in K + 1 chunks.
In CRC, a k-bit message is taken, and the transmitter creates an (n – k) bit sequence called the frame check sequence, resulting in an n-bit outgoing frame.
Byte stuffing is used to ensure that flag bytes do not appear in the data.
Unacknowledged connectionless service, Acknowledged connectionless service, Acknowledged connection-oriented service.
The DLL breaks the bit stream into discrete frames and computes a checksum for each frame.
To ensure all frames are eventually delivered to the network layer at the destination and in the proper order.
The main idea is to use redundant bits, utilizing only 2m out of 2n code words.
Redundancy, which involves sending extra bits with the data.
It regulates data flow to ensure slow receivers are not overwhelmed by fast senders.
The receiver calculates CRC bits from the entire received code word without adding any padding bits.
It is useful over unreliable channels, such as wireless systems, because individual frames can be acknowledged and retransmitted, ensuring that entire packets get through faster even if some frames are lost.
Error detection and correction ensure the integrity of data transmitted over the network by identifying and correcting errors.
_ _ 1 _ 0 0 1 _ 1 0 1 0
An n-bit codeword consists of m data bits and r redundant or check bits, with a total length of n (n = m + r).
The receiver discards the data because there is an error.
The DLL knows that an error has occurred and may discard the bad frame and send back an error report.
By having the receiver send back special control frames with positive or negative acknowledgements about the incoming frames.
It specifies the number of characters in the frame, allowing the destination DLL to determine where the end of the frame is.
Polynomial arithmetic is done modulo 2, with addition and subtraction being identical to exclusive OR.
2 -n
The hardware checks the frame for errors.
Bit stuffing is a technique used to ensure that certain bit patterns do not appear in the data stream, by inserting non-information bits into the original data.
Bit stuffing involves adding a 0 bit into the outgoing bit stream whenever 5 consecutive 1s are detected, to prevent confusion with flag bytes.
The final data that will be sent is 011100110101.
By arranging a sequence of k consecutive codewords as a matrix and transmitting one column at a time.
Pad (n - 1) 0’s to the message bits, where ‘n’ is the number of bits in the code generator. For code generator 1101 (4 bits), append 000 to the data 10110.
Networks rarely guarantee timing, which can lead to gaps being squeezed out or other gaps being inserted during transmission.
CRC can detect all burst errors that affect an odd number of bits, all burst errors of length less than or equal to the degree of the polynomial, and with high probability, burst errors of length greater than the degree of the polynomial.
0
Frame 1101011011
It uses error-detecting codes to include only enough redundancy to allow the receiver to deduce that an error occurred and request a retransmission.
0.5
The first step is to verify each check bit and identify which parity bits are incorrect.
Feedback-based flow control and rate-based flow control.
Flag bytes with byte stuffing are used to indicate the start and end of a frame, ensuring that escape bytes within the data are properly handled.
The checksum is 0101.
The number of bit positions in which two codewords differ.
The result is called the checksummed frame, referred to as T(x).
It will require 'd' single-bit errors to convert one codeword into the other.
By checking bits 8, 9, 10, 11, and 12 for Odd Parity, it is determined that a 1 must be added to position 8, indicating an error.
G(x) = x^4 + x + 1
1
A checksum is a count of the number of bits in a transmission unit included with the unit, allowing the receiver to check if the same number of bits have arrived.
Divide data into K chunks of n bit each.
A distance d + 1 code is required to detect d errors.
The main services include framing, error control, and flow control.
Acknowledged connection-oriented service.
A distance 2d + 1 code is required to correct d errors.
Flow control is used to manage the rate of data transmission between sender and receiver to prevent overflow.
Packets are units of data that are routed between an origin and a destination across a network, while frames are units of data that are transmitted over a specific link layer.
The key metrics include how many errors can be corrected or detected and the burst length.
It allows a source machine to send independent frames to a destination machine without requiring acknowledgment, with no logical connection established.
They must agree upon a generator polynomial, G(x), in advance.
Data link layer design issues include error detection and correction, sliding window protocols, and high-level data link control (HDLC) protocols.
In connectionless service, a lost acknowledgement can lead to a packet being sent multiple times and thus received multiple times.
The purpose of a CRC is to detect errors in digital data by generating a fixed-size checksum based on the data being transmitted.
The Checksum can detect all errors involving an odd number of bits as well as most errors involving an even number of bits.
Append r zero bits to the low-order end of the frame so it now contains m + r bits.
Hamming codes can only correct single errors.
(n-1) zero bits are appended to the data, where n is the number of bits in the generator.
Four examples of byte sequences before and after stuffing illustrate how certain byte sequences are modified to avoid confusion with flag bytes.
In Phase 1, the connection is established by having both sides initialize the variables and counters needed to track received and not received frames.
An acknowledged connectionless service does not establish logical connections; each frame is individually acknowledged, allowing the sender to know if a frame has arrived correctly. If a frame is not received within a specified time, it can be retransmitted.
One copy of the data link layer software handles all the lines with different tables and data structures for each.
It is suitable for environments with a low error rate and for real-time traffic, such as voice, where late data is more detrimental than bad data.
10110101
Transfers data from the network layer on the source machine to the network layer on the destination machine.
Inserting time gaps between frames, similar to spaces between words in text.
The CRC generator should not contain 'x'. If (x+1) is the generator, it can detect an odd number of errors. If the generator is xn, then it can detect the last n bit errors.
Position 2 checks bits 2, 3, 6, 7, 10, 11 for even parity, indicating that 0 must be added to position 2 and is incorrect.
A common error-correcting code is the Hamming code.
You can exclusive OR the two codewords and count the number of 1 bits in the result to determine how many bits differ.
It represents a six-term polynomial with coefficients 1, 1, 0, 0, 0, and 1: x^5 + x^4 + x^0.
Take the complement of the result after performing 1's complement addition.
The character count is used to locate the end of the frame when it arrives.
The distance is 2, meaning that any single-bit error will produce a codeword with the wrong parity, allowing for the detection of single errors.
Not adding padding bits ensures that the CRC calculation is based solely on the actual received code word, allowing for accurate error detection.
The receiver divides the received data (data + CRC) by the generator G(x).
To provide redundancy in the encoding on the physical medium, making it easier for the receiver to locate bit boundaries.
The key to the Hamming Code is the use of extra parity bits to allow the identification of a single error.
(a) Virtual Communication. (b) Actual Communication.
Parity bits are marked at positions that are powers of two (1, 2, 4, 8, 16, etc.), while all other positions are for the data to be encoded.
By verifying each check bit and writing down all the incorrect parity bits, you can determine the location of the bad bit by adding the positions that are wrong.
The error rate is 10^-6 per bit.
It is better to use error-correcting codes on channels such as wireless links that make many errors, rather than relying on a retransmission, which itself may be in error.
It knows how many characters follow the character count, which helps identify the end of the frame.
They indicate the beginning and end of a data frame, using a special bit pattern (01111110).
The probability is only 0.5, which is hardly acceptable.
The parity bit checks the sequence of bits based on its position; it can check and skip bits alternately to determine if the total number of ones is odd or even.
It checks to see if this is the expected frame and, if so, gives the packet in the payload field to the routing software.
The flag byte's bit pattern may occur in the binary data being transmitted, such as object programs or floating-point numbers.
To determine if the bit in position 4 is correct using Odd Parity.
If the remainder is zero after dividing the received data by the generator, the data is correctly received.
Three bits (000) are appended to the data 10110 because the code generator has 4 bits, and we pad (n - 1) 0’s.
The FLAG byte serves as both the starting and ending delimiter for frames, allowing the receiver to resynchronize after an error by searching for the FLAG byte.
If the checksummed frame, when divided by G(x), leaves a remainder.
Multiple copies of the data link layer software are present, but one copy manages all lines with separate tables and structures.
A k-bit frame is regarded as the coefficient list for a polynomial with k terms, ranging from x^(k-1) to x^0, making it a polynomial of degree k - 1.
The receiver automatically destuffs the 0 bit when it sees 5 consecutive 1 bits followed by a 0 bit, ensuring that the original flag pattern is preserved.
A disadvantage is that it is closely tied to the use of 8-bit characters, which limits its applicability since not all character codes use 8-bit characters, such as UNICODE which uses 16-bit characters.
The error will not be corrected properly.
A CRC is a polynomial code that treats bit strings as representations of polynomials with coefficients of 0 and 1.
The sender appends the data with the generator G(x) using modulo 2 division, and the remainder of (n-1) bits will be the CRC.
Position 1 checks bits 1, 3, 5, 7, 9, 11. With even parity, position 1 is set to 0.
If one or more bits of a segment are damaged and the corresponding bit or bits of opposite value in a second segment are also damaged, the sum of those columns will not change, and the receiver will not detect an error.
The character count can be garbled by a transmission error, leading to synchronization issues at the destination.
Set the parity bit to 1 if the total number of ones in the positions it checks is odd, and set it to 0 if the total number of ones is even.
By using 2 physical bits, where a 1 bit is represented as a high-low pair and a 0 bit as a low-high pair.
Two consecutive FLAG bytes indicate the end of one frame and the start of the next frame.
A CRC works by treating the data as a polynomial and dividing it by a predetermined polynomial, with the remainder serving as the checksum to verify data integrity.
By regarding each block as a rectangular matrix and computing a parity bit for each column, affixed as the last row.
If either the frame or the acknowledgement is lost, the timer expires, alerting the sender to retransmit the frame. Sequence numbers are assigned to outgoing frames to distinguish retransmissions from originals.
Errors tend to come in bursts rather than singly.
Because if the character count is incorrect, the destination cannot locate the start of the next frame or know how many characters to skip for retransmission.
Bit stuffing involves adding a 0 bit after 5 consecutive 1 bits to prevent confusion with the flag pattern, allowing for unambiguous frame boundaries.
The sender's DLL inserts a special escape byte (ESC) before each accidental flag byte in the data, which is then removed by the DLL on the receiving end.
If the error rate is low, errors may occur in only 1 or 2 blocks, making it easier to manage.
1
