Title: Theory / Unimportant / CS / Hardware / Computer Network - Tanenbaum / 3 Data link layer
Tags: hasSeenConjDef examplesSwitchExample1

Name: A wire-like channel
Definition: A channel delivering bit in the order in which they are emitted
Page: 193
Chapter: 3
Context: Network

Name: Data link layer
Definition: Providing a well-defined service interface to the network layer.
Page: 193
Chapter: 3
Section: 1
Context: Network
Definition2: Dealing with transmission errors.
Conjdef: Layer of the network, which
Definition3: Regulating the flow of data so that slow receivers are not swamped by fast senders.

Name: frame
Definition: A header
Page: 193
Chapter: 3
Section: 1
Context: Network, data link
Definition2: A payload field
Conjdef: A tuple with
Definition3: A trailer

Question: Possibilities that we can consider for data link
Answer: Unacknowledged connectionless service.
Page: 195
Chapter: 3
Section: 1.1
Context: Network, data link
Answer2: Acknowledged connectionless service.
Answer3: Acknowledged connection-oriented service.

Name: Unacknowledged connectionless service.
Definition: having the source machine send independent frames to the destination machine without having the destination machine acknowledge them.
Page: 195
Chapter: 3
Section: 1.1
Context: Network, data link
Example: Ethernet

Question: In which case Unacknowledged connectionless service appropriate ?
Answer: error rate very low
Page: 196
Chapter: 3
Section: 1.1
Context: Network, data link
Answer2: real-time traffic, in which late data are worse than bad data

Question: In which case Acknowledged connectionless service appropriate ?
Answer: Unreliable channel
Page: 196
Chapter: 3
Section: 1.1
Context: Network, data link

Name: Acknowledged connectionless service
Definition: A connection channel, there are still no logical connections used, but each frame sent is individually acknowledged.
Page: 196
Chapter: 3
Section: 1.1
Context: Network, data link
Example: Wifi

Question: Why do we want that data link detect bad/lost frame (instead of leaving this to higher level)
Answer: Detecting an error at higher level means that one must send each frame again, consuming more bandwidth.
Page: 196
Chapter: 3
Section: 1.1
Context: Network, data link
Answer2: if there the network is so bad that there are bad frames in each unit of higher level, it will take a lot of try before all frames are sent correctly !

Name: Connection-oriented service
Definition: The source and destination machines establish a connection
Page: 196
Chapter: 3
Section: 1.1
Context: Network, data link
Definition2: Each frame sent over the connection is numbered, and the data link layer guarantees that each frame sent is indeed received.
Conjdef: A communication such that
Definition3: Furthermore, it guarantees that each frame is received exactly once and that all frames are received in the right order.

Question: How to ensure that there are no bit error when transmitting frame
Answer: Take the bit to transmits. Break them in discrete frames. Compute the checksum of the frames. Send the frame and its checksum. The recipient compute the checksum and check whether both are equals.
Page: 197
Chapter: 3
Section: 1.1
Context: Network, data link

Name: Byte count
Definition: A frame start by giving the length of the frame, in byte. The recipient then look for this number of byte, and construct a frame from it.
Page: 197
Chapter: 3
Section: 1.1
Context: Network, data link

Question: Problem with Byte count
Answer: A single bit error in the byte number breaks synchronisation. Position of start of next frame is unkown
Page: 197
Chapter: 3
Section: 1.1
Context: Network, data link

Name: Flag byte
Definition: A byte to start/end frame, and delimit their boundaries
Page: 198
Chapter: 3
Section: 1.1
Context: Network, data link

Name: Flag byte with byte stuffing
Definition: Transmission adding a flag byte to start/end each frame
Page: 198
Chapter: 3
Section: 1.1
Context: Network, data link
Definition2: Byte stuffing
Conjdef: Transmission of a stream of byte, with

Question: What is the problem with Flag byte with byte stuffing
Answer: The flag byte can occur in the normal stream of byte
Page: 198
Chapter: 3
Section: 1.2

Name: Byte stuffing
Definition: Adding an «escape byte» before the accidental occurrence of the flag byte or of the escape byte in normal stream of bytes
Page: 198
Chapter: 3
Section: 1.2

Name: Point-to-Point Protocol
Definition: Protocol used to carry packets over communications links
Page: 198
Chapter: 3
Section: 1.2
Context: Network
Abbreviation: PPP

Name: High-Level Data Link Control
Page: 199
Chapter: 3
Section: 1.2
Context: Network
Abbreviation: HDLC

Name: Bit stuffing
Definition: Add a 0 after each "11111" when sending data. Use 01111110 as flag byte
Page: 199
Chapter: 3
Section: 1.2
Context: Network

Name: Preamble
Definition: A pattern starting a frame to allow receiver to prepare itself
Page: 114
Chapter: 2
Section: 3.2
Context: Network

Question: What may occur if a protocol state to send a request and wait for an answer
Answer: The wait may never halts if the request or answer are lost, even if after that the hardware works perfectly
Page: 201
Chapter: 3
Section: 1.3

Name: feedback-based flow control
Definition: The process where the receiver sends back information to the sender giving it permission to send more data, or at least telling the sender how the receiver is doing
Page: 201
Chapter: 3
Section: 1.4

Name: rate-based flow control
Definition: the protocol has a built-in mechanism that limits the rate at which senders may transmit data, without using feedback from the receiver.
Page: 201
Chapter: 3
Section: 1.4

Name: Network Interface Cards
Page: 201
Chapter: 3
Section: 1.4
Abbreviation: NICs

Name: Running at wire speed
Definition: being able to handle frames as fast as they can arrive on the link
Page: 202
Chapter: 3
Section: 1.4

Name: error-correcting codes
Definition: A code which allow to correct a given amount of error in a transmitted message
Page: 203
Chapter: 3
Section: 2

Name: error-detecting codes
Definition: A code which allow to detect that data has a fault, assuming that there is a limit on the actual number of faults
Page: 203
Chapter: 3
Section: 2

Name: Forward Error Correction
Definition: The use of error-correcting code
Page: 203
Chapter: 3
Section: 2
Abbreviation: FEC

Question: When to prefer error-correcting or error-detecting code
Answer: Correction when they are a lot of errors, and thus each resending of the data probably also have errors. Detection otherwise, in which case few frames should be resent, and thus resending small frame is better than sending big frames
Page: 203
Chapter: 3
Section: 2

Name: Erasure channel
Definition: A channel in which bits may be lost
Page: 203
Chapter: 3
Section: 2
Extra: Erasure ?

Name: A block code
Definition: A code in which the redundant bits are computed as a function of the data bit only
Page: 203
Chapter: 3
Section: 2
Variables: \(m\) data bits
\(r\) redundant bits
Context: Error-correcting code
Counterexample: Convolutional code

Name: A systematic code
Definition: A code in which the \(m\) data bits are sent as is and not encoded
Page: 203
Chapter: 3
Section: 2
Variables: \(m\) data bits
\(r\) redundant bits
Context: Error-correcting code

Name: A linear code
Definition: A code in which the \(r\) redundant bits is a linear-combination of the \(m\) data bits
Page: 203
Chapter: 3
Section: 2
Variables: \(m\) data bits
\(r\) redundant bits
Context: Error-correcting code

Name: A \((n,m)\)-code
Definition: A code encoding \(m\) bits into a sequence of \(n\) bits
Page: 203
Chapter: 3
Section: 2
Variables: \(m\) data bits
\(r\) redundant bits
Context: Error-correcting code

Name: A codeword
Definition: The encoding of a message using a error-correcting/detecting code
Page: 203
Chapter: 3
Section: 2
Variables: \(m\) data bits
\(r\) redundant bits
Context: Error-correcting code

Name: The code rate of \(C\)
Definition: \(\frac mn\)
Page: 203
Chapter: 3
Section: 2
Variables: \(m\) data bits
\(r\) redundant bits
\(n=r+m\) the size of codeword
\(C\) a \((n,m)\)-code
Context: Error-correcting code

Page: 205
Section: 2
Variables: \(w,w'\) two binary words of the same length
Chapter: 3
Name: The Hamming distance between \(w\) and \(w'\)
Definition: The number of position which differs in \(w\) and \(w'\)
Commutative: Yes
Context: Error-correcting code
Codomain: \(\mathbb N\)

Name: A distance \(d\) code
Definition: A code (set of words) in which the Hamming-distance between two words is at least \(d\)
Page: 205
Chapter: 3
Section: 2
Variables: \(d\in\mathbb N\)
Context: Error-correcting code

Question: To detect \(d\) errors, a distance \(f(d)\) code must be used, with \(f()\) being
Answer: \(2d+1\)
Page: 205
Chapter: 3
Section: 2
Variables: \(d\in\mathbb N\)
Context: Error-correcting code

Page: 205
Implementation: Using \(\lceil\log_2(m)\rceil\) check bits.
The check bits are at position \(2^i\) (with first bit at position 1) and is the xor of the bit at each position \(j\) whose \(i\)-th bit is 1.
Section: 2
Chapter: 3
Variables: \(m\) a number of data bit to send
Name: Hamming code
Returns: Allow to correct up to one error
Context: Error-correcting code

Page: 205
Implementation: switch the \(\sum_{w[2^i]=1}2^i\)-th bit and remove  (with first bit being position 1)
Return \(w\) without the bit in positions \(2^i\)
Section: 2
Chapter: 3
Effect: Allow to correct up to one error
Variables: \(m\) a number of data bit to send
Context: Error-correcting code
Input: \(w\) a message which is supposed to be encoded using Hamming code and potentially one error

Name: Error syndrome
Definition: The xor of the check bit expected and the check bit received
Page: 205
Chapter: 3
Section: 2
Context: Error-correcting code

Name: Constraint length of a code
Definition: The number of bit used to comput an output bit
Page: 205
Chapter: 3
Section: 2
Context: Error-correcting code

Name: The NASA binary convolutional code
Page: 205
Chapter: 3
Section: 2
Context: Error-correcting code
Intuition: Voyager space missions starting in 1977

Name: Soft-decision decoding
Definition: A decoding algorithm taking probability into account
Page: 208
Chapter: 3
Section: 2
Context: Error-correcting code
Example: If instead of receiving 1 volt, we receive .9 we can say there is a high probability that it is 1 which should have been received

Name: Hard-decision decoding
Definition: A decoding algorithm where the value of a bit is fixed before considering following bit
Page: 208
Chapter: 3
Section: 2
Context: Error-correcting code

Question: Agains which kind of error is Reed-Salomon efficient
Answer: Burst error, with plenty of successive bit modified
Page: 209

Question: Agains which kind of error is convoluted code efficient
Answer: Sparse error. In case of burst of error, the entire sum is compromised
Page: 209

Name: Generator polynomial of degree \(t\)
Definition: \(\prod_{i=1}^{2t}(x-\alpha^i)\) with \(\alpha\) primitive
Page: 208  https://en.wikipedia.org/wiki/Reed–Solomon_error_correction
Chapter: 3
Section: 2
Variables: \(t\) a distance (number of error to accept)
\(k\) the number of bit to encode
\(k+2t=2^m-1\)
Context: Reed-Solomon code
Extra: TODO ???

Name: Low-Density Parity Check
Page: 209
Chapter: 3
Section: 2
Variables: \(t\) a distance (number of error to accet)
\(k\) the number of bit to encode
\(k+2t=2^m-1\)
Context: Error correcting code
Abbreviation: LDPC
Intuition: A code which improve received data until it becomes a legal code word

Name: Parity bit code
Definition: The check word \(c\)'s \(i\)-th letter is the xor of the bits in position \(\equiv i\mod k\)
Page: 210
Chapter: 3
Section: 2.2
Variables: \(m\) bits to send
\(k\) check bit
Intuition: Allow to detect a burst of length at most \(2k-1\)
DefType: Error detection code

Name: Internet checksum
Definition: Taking the sum of each words of length \(16\) in one's complement arithmetic (i.e. the overflow is added to the result)
Page: 210
Chapter: 3
Section: 2.2
Variables: \(m\) bits to send
DefType: Code detection error with \(16\) check bits

Question: What can of error may Internet checksum miss ?
Answer: Adding/removing words composed only of 0s.
Page: 212
Chapter: 3
Section: 2.2
Variables: \(m\) bits to send
Answer2: Switching two words

Name: Fletcher's checksum
Definition: For \(W=w_0\dots w_n\) a word to encode, with \(w_i\) of length 16 bit, returning \(\sum_{i=0}^niw_i\), with one-complement sum
Page: 212
Chapter: 3
Section: 2.2
Variables: \(m\) bits to send

Name: Cyclic Redundancy Check
Definition: A word \(w_{k-1}\dots w_0\) represents the polynomial \(\sum_{i=0}^{k-1}w_ix^i\). For a generator polynomial \(G(x)\) fixed, the check bit ensure that the whole code-word is a multiple of \(G(x)\)
Page: 212
Chapter: 3
Section: 2.2
Variables: \(m\) bits to send
Name2: polynomial code
Abbreviation: CRC