Samenvatting
Summary Computer Networks CSE1405 TU Delft
A summary of the course Computer Networks (CSE1405) of TU Delft, part of the bachelor Computer Science and Engineering.
[Meer zien]Voorbeeld 3 van de 30 pagina's
Voorbeeld 3 van de 30 pagina's
In winkelwagengesponsord bericht van onze partner
Voorbeeld van de inhoud
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.
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper sachakorte. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €5,49. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 53022 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen