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].
What is CSMA?
A random access protocol based on two principles:
- If some other node’s frame is being transmitted, then don’t transmit.
- Stop transmitting if another node begins transmitting.
These are detected by signal energy appearing at the node.
What is the binary exponential backoff algorithm?
When a frame has already experienced n collisions, a node chooses a random K from {0, 1, 2, …, 2^n - 1} and waits K * 512 bit times. Ethernet caps n as 10.
What is the efficiency of CSMA?
Efficiency = 1/(1 + 5*d_prop/d_trans)
How does the polling protocol work?
A taking-turns protocol where a master node tells nodes in a round-robin that they can transmit F frames.
What is the token-passing protocol?
A token is exchanged among the nodes in some order. Each node sends up to a maximum number of frames and then passes on the node.
What is the DOCSIS protocol for cable access?
Downstream is easy: there is only one sender.
Upstream is more challenging:
the CMTS sends a control message known as a MAP message to specify which modem can send in each mini slot.
It knows which modems need slots as the modems sends mini-slot request frames upstream. If the modem gets no response, it is assumed to have collided. Binary exponential backoff is then used to retransmit.
How many possible MAC addresses are there?
2^48.
How is it ensured that no MAC address is reused?
IEEE manages the address space and companies purchase from them. Each device’s MAC never changes.
Why are MAC addresses needed alongside IP addresses?
To handle other network-level protocols.
How does a sending host determine the MAC address for a host with a given IP address on the same subnet?
The host broadcasts an ARP request to the subnet with the IP address.
The correct IP sends an ARP reply backwards.
The host fills its ARP table with the IP <-> MAC conversion and a TTL.
How does a sending host determine the MAC address for a host with a given IP address on a different subnet?
It uses ARP to get the MAC address of the router.
It creates a frame with the IP address, but the MAC of the router.
The router’s forwarding table passes it to its adapter and sends a new frame into subnet 2.
[Assuming the router has already ARPed the MAC address of the required IP.]
What does an Ethernet frame header contain?
8 bytes: Preamble (used to synch clocks)
6 bytes: Destination address
6 bytes: Source address
2 bytes: Type
4 bytes: CRC
Is there a need for a MAC Ethernet protocol? Why or why not?
No. Most uses of Ethernet is a switch-based star topology.
What are the fields in a link-layer switch table?
MAC address.
Switch interface to that MAC address.
The time the entry was added.
What does a switch do if a frame’s destination MAC is:
a) Not in the table
b) Corresponding to the interface it was received on.
c) Other
a) It broadcasts the frame, adding the record to a table.
b) It drops the frame
c) It forwards the frame
What are some benefits of switches over hubs?
Elimination of collisions
Heterogeneous links
Easier management
What are the advantages and disadvantages of switches over routers?
Advantages:
- plug-and-play
- high filtering/forwarding rates
Disadvantages:
- Structure must be a tree.
- Large networks would require large ARP tables.
- Susceptible to broadcast storms.
