Zusammenfassung
Summary Computer Networks CSE1405 TU Delft
- Kurs
- Hochschule
A summary of the course Computer Networks (CSE1405) of TU Delft, part of the bachelor Computer Science and Engineering.
[ Mehr anzeigen ]vorschau 3 aus 30 Seiten
Vorschau 3 aus 30 Seiten
In den Einkaufswagen
In den Einkaufswagen
Verkäufer
Folgen
sachakorte
Deine Reviews
Inhaltsvorschau
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.
Alle Vorteile der Zusammenfassungen von Stuvia auf einen Blick:
Garantiert gute Qualität durch Reviews
Stuvia Verkäufer haben mehr als 700.000 Zusammenfassungen beurteilt. Deshalb weißt du dass du das beste Dokument kaufst.
Schnell und einfach kaufen
Man bezahlt schnell und einfach mit iDeal, Kreditkarte oder Stuvia-Kredit für die Zusammenfassungen. Man braucht keine Mitgliedschaft.
Konzentration auf den Kern der Sache
Deine Mitstudenten schreiben die Zusammenfassungen. Deshalb enthalten die Zusammenfassungen immer aktuelle, zuverlässige und up-to-date Informationen. Damit kommst du schnell zum Kern der Sache.
Häufig gestellte Fragen
Was bekomme ich, wenn ich dieses Dokument kaufe?
Du erhältst eine PDF-Datei, die sofort nach dem Kauf verfügbar ist. Das gekaufte Dokument ist jederzeit, überall und unbegrenzt über dein Profil zugänglich.
Zufriedenheitsgarantie: Wie funktioniert das?
Unsere Zufriedenheitsgarantie sorgt dafür, dass du immer eine Lernunterlage findest, die zu dir passt. Du füllst ein Formular aus und unser Kundendienstteam kümmert sich um den Rest.
Wem kaufe ich diese Zusammenfassung ab?
Stuvia ist ein Marktplatz, du kaufst dieses Dokument also nicht von uns, sondern vom Verkäufer sachakorte. Stuvia erleichtert die Zahlung an den Verkäufer.
Werde ich an ein Abonnement gebunden sein?
Nein, du kaufst diese Zusammenfassung nur für 5,49 €. Du bist nach deinem Kauf an nichts gebunden.
Kann man Stuvia trauen?
4.6 Sterne auf Google & Trustpilot (+1000 reviews)
45.681 Zusammenfassungen wurden in den letzten 30 Tagen verkauft
Gegründet 2010, seit 14 Jahren die erste Adresse für Zusammenfassungen