Summary
Summary Computer Networks CSE1405 TU Delft
- Course
- Institution
A summary of the course Computer Networks (CSE1405) of TU Delft, part of the bachelor Computer Science and Engineering.
[Show more]
Seller
Follow
sachakorte
Reviews received
Content preview
Lecture 2/3: The Data Link LayerOverview
1. Data Link Layer functions and services
2. Framing methods: byte count, flag bytes with byte stuffing, flag bit with bit stuffing.
3. Error correction: hamming codes.
4. Error detection: parity, checksum, cyclic redundancy check (CRC).
5. Protocols: stop-and-wait, Automatic Repeat Request (ARQ), 1-bit sliding window, Go-Back-N, selective
repeat
Functions & Services
Functions of the data link layer:
1. Providing a well-defined service interface to the network layer.
2. Dealing with transmission errors.
3. Regulating the flow of data so that slow receivers are not swamped by fast senders.
4. Group bits into frames
Physical Layer (recap): responsible for transferring bits over a wire like medium.
Data Link Layer: responsible for transferring frames over a single link.
Possible services
1. Unacknowledged connectionless service: frame is sent with no connection/error recovery.
2. Acknowledged connectionless service: frame is retransmitted if needed.
3. Acknowledged connection-oriented service: connection is established (rare).
Framing methods
Four methods for breaking up bit streams into frames:
1. Byte count
2. Flag bytes with byte stuffing Side effect: length of frame depends on
3. Flag bits with bit stuffing content of data
4. Physical layer coding violations
Byte count
Field in header specifies number of bytes in frame.
Problem: count can be garbled by a transmission error
Flag bytes with byte stuffing
Flag byte is used as both the starting and ending delimiter.
Problem: flag byte occurring in the data interfere with the framing
Solution: sender should insert escape byte before each flag byte in the data → byte stuffing.
• Escape byte in the data is stuffed with an escape byte.
• Destuffing takes place on receiver.
Flag bits with bit stuffing
Overcomes disadvantage of byte stuffing, which is that it is tied to the use of 8-bit bytes → space inefficient.
Each frame begins and ends with a special bit patter: 01111110 (protocol can decide this pattern).
Bit stuffing: when the sender encounters 5 consecutive 1s in the data, it stuffs a 0 bit in the outgoing stream
When receiver sees 5 consecutive 1s followed by a 0, it deletes the 0 bit.
, Errors
2 strategies for dealing with errors:
1. (noisy channel) Add enough redundant information to enable the receiver to deduce what the
transmitted data must have been → error correction codes.
2. (highly reliable channel) Add only enough redundant information to allow the receiver to deduce that
an error has occurred (but not which) and have it request a retransmission → error detecting codes.
For a message of 𝑚 bits send an extra 𝑟 redundant bits. Send 𝑛 = 𝑚 + 𝑟 to the receiver → systematic code
Code rate = 𝑚/𝑛. Codeword: 𝑛-bit unit containing data and check bits.
Hamming distance: number of bit positions in which 2 codewords differ.
In most data transmission applications, all 2𝑚 possible data messages are legal, but not all 2𝑛 possible
codewords are used, due to the way the check bits are computed.
Hamming distance of complete code (all legal codewords) = the smallest hamming distance between 2
codewords.
Detect 𝑑 errors → 𝑑 + 1 distance code → 𝑑 single bit errors can’t change a valid codeword into another
Correct 𝑑 errors → 2𝑑 + 1 distance code → valid codewords are so far apart that even with 𝑑 changes the
original codeword is still closer than any other.
Error correction codes
4 methods of error correction: hamming codes, binary convolutional codes, Reed-Solomon codes and low-
density parity check codes.
Hamming codes
Hamming distance of 3 → can detect 2 errors, can correct 1 error.
Bit of the codeword are numbered (from left to right: 1, 2, 3, 4, …). The bits that are powers of 2 are check
bits (1, 2, 4, 8, … ). The rest is filled with data bits.
Each check bit forces the modulo 2 sum of some collections of bits to be even/uneven.
• For check bit at position 𝑘: all bits that have 2𝑘 in their expansion are checked.
• Checks 𝑘 bits, skips 𝑘 bits, checks 𝑘 bits, skips 𝑘 bits etc.
A bit may be included in several check bit computations, to see in which we write the bit’s positions as
powers of 2. Example: bit 11 is checked by checking bit 1, 2 and 8, since (11)10 = (1011)2 = 1 + 2 + 8.
Receiver redoes the check bit computation.
If all check bits match → no error. Otherwise, position of error is sum of positions where check bit differs.
Error syndrome → set of check results → 0 for correct check bit, 1 for incorrect check bit.
• Example: error syndrome = 0101, means check bits at position 1 and 4 wrong.
• Error syndrome indicates position of bit error (0101)2 = 52 , error at position 5.
Binary Convolutional Codes
Operates on a stream of bits, keeping internal state. Output stream is function of all preceding input bits.
Bits are decoded with the Viterbi algorithm.
, Error detection codes
3 methods of error detection: parity checksum and cyclic redundancy check (CRC)
Parity
Add single bit such that: the sum of the data bits modulo 2 is 0 → the number of 1s is even.
Problem: long burst errors are hard to detect (probability of 50%).
Odds of detection can be improved if each block to be send is regarded as a rectangular matrix 𝑛 bits wide
and 𝑘 bits high. Now, if we compute and send 1 parity bit for each row, up to 𝑘 bit errors will be reliable
detected as long as there is at most one error per row. However, a better protecting against burst errors
would be to calculate a parity bit for each of the 𝑛 columns → interleaving. This method uses 𝑛 parity bits
on blocks of 𝑘𝑛 data bits to detect a single burst error of length 𝑛 or less.
Checksum
Checksum treats data as 𝑁-bit words and adds 𝑁 check bits that are the modulo 2𝑁 sum of the words.
• Improved error detection over parity bits.
• Detect burst up to 𝑁 errors.
• Vulnerable to systematic errors (e.g. added zeros).
Example: The Internet-16 1s complement checksum → checksum is calculated by taking the 1s
complement of the sum of all words (16-bit numbers). Sender adds checksum to the end of the transmitted
sequence, receiver adds everything including the checksum, takes the complement, this should be 0.
Cyclic Redundancy Check (CRC)
In modulo 2 arithmetic both + and – are identical to XOR.
In advance, sender and receiver must agree upon a generator polynomial → 𝐺(𝑥)
To compute CRC for some frame with 𝑚 bit corresponding to the polynomial 𝑀(𝑋), the frame must be
longer than the generator polynomial 𝐺(𝑥).
Idea: append a CRC to the end of frame in such a way that the polynomial represented by the check
summed frame is divisible by 𝐺(𝑥). If there is a remainder (on receiver) → transmission error occurred.
Algorithm for computing CRC:
1. Let 𝑟 be the degree of 𝐺(𝑥). Append 𝑟 zero bits to the lower-end of the frame so it contains 𝑚 + 𝑟
bits and corresponds to the polynomial 𝑥 𝑟 𝑀(𝑥)
2. Divide the bit string corresponding to 𝐺(𝑥) into the bit string corresponding to 𝑥 𝑟 𝑀(𝑥), using modulo
2 division.
3. Subtract the remainder (which is always 𝑟 or fewer bits) from the bit string corresponding to 𝑥 𝑟 𝑀(𝑥)
using modulo 2 subtraction. The result is the checksummed frame to be transmitted 𝑇(𝑥).
Stronger detection than checksums:
• Can detect all double bit errors, odd bit errors.
• Detect all burst errors ≤ 𝑟 bits.
• Not vulnerable to systematic errors.
• However, errors that happen to correspond to polynomials containing 𝐺(𝑥) as a factor will slip by; all
other errors will be caught.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller sachakorte. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.89. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
67474 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now