Chapter 6: The Link Layer Flashcards
Where is the link layer implemented?
On chips known as network adapters or as network interface controllers (NICs)
What is a 1D parity check, and how does it detect bit errors?
The parity bit is the number of 1s in the data bits mod 2.
[When added, there should be an even number of 1s]
If afterwards, there is an odd number of bits, there has been an error.
What is a 2D parity check and how does it detect and correct errors?
The D bits are aligned into a rectangle, and a parity bit assigned for each column and row to make a larger rectangle.
If a single-bit is flipped, the parity bits for that row and column are wrong and so it can be identified.
It can also detect any 2 bit flips, but not correct.
What is a checksum and how does it detect bit errors?
The d bits of data is split into k-bit integers and added together. The 1s complement forms a checksum.
If the sum of the data bits and checksum is not 0, there has been an error.
What is CRC and how does it detect and correct bit errors?
The sender and receiver agree on a r + 1 bit pattern known as a generator, which we call G. The left-most bit needs to be a 1.
For a given piece of data, the sender chooses r additional bits and appends them to D, so the resulting d + r bit pattern is exactly divisible by G in mod2.
If the remainder is non-zero, the recipient knows an error has occurred.
The CRC standard can detect burst errors (consecutive) of r bits or fewer.
[And any size of odd bit errors]
How are addition and subtraction done in CRC?
Bit-wise XOR with no carries.
How are division and multiplication done in CRC?
Shift left by k-places for a multiplication of 2^k.
In CRC, we need to find an R such that D || R = n * G.
How is this R found?
D * 2^r XOR R = nG
D * 2^r = nG XOR R
Thus, R = remainder(D * 2^r/G)
What are the two types of network link?
Point-to-point and broadcast.
Give features of a multiple access protocol for a broadcast channel of rate R bits per second.
- When only one node has data to send, it has a throughput of R bps.
- When M node have data send, each has an average transmission R/M over some suitably defined interval of time.
- The protocol is decentralized (no single point of failure)
- The protocol is simple.
What is CDMA?
Code Division Multiple Access (CDMA) is a channel partitioning protocol where each node is given a different code.
Each node encodes its bits by that code, so that receivers can correctly receive a sender’s encoded data bits.
What is slotted ALOHA?
A random access protocol. When a node has a fresh frame to send, it waits until the next slot and transmits the entire frame in the slot.
If there isn’t a collision, the node has successfully transmitted its frame and thus need not consider retransmitting.
If there is a collision, the frame is transmitted in the next slot with probability p.
What are some pros and cons of slotted ALOHA?
Pros:
- single active node can continuously transmit at full rate of channel
- highly decentralised (only slots in nodes need to be in sync)
- simple
Cons:
- Wasted slots (collisions, iding)
- Detection of collision is faster than transmission time
- Clock sync is hard.
What is the maximum efficiency of slotted ALOHA?
Assume every one of the N nodes always has a frame to send in each slot with probability p.
The probability of success for 1 slot is p * (N-1)^(1-p).
The probability that any slot is successful is Np * (N-1)^(1-p).
As N -> inf, probability -> 1/e. [About 0.37]
What is the maximum efficiency of unslotted ALOHA?
If a node begins transmission at t0,
the probability that no other nodes begin a transmission in [t0 - 1, t0] of time is (1-p)^(N-1).
The probability no other nodes begin a transmission in [t0, t0 + 1] is (1-p)^(N-1).
Then, the maximum probability as N->inf is 1/(2e) [approx 0.19].
