What is the responsibility of the data-link layer? What is its packet called?
Transferring a datagram from one node to a physically adjacent node over a link. Its layer-2 packet is a frame, which encapsulates the datagram.
Link-layer terminology: nodes and links.
Nodes: hosts and routers. Links: communication channels that connect adjacent nodes along the communication path (wired links, wireless links, LANs).
Link-layer transportation analogy: what do the tourist, the transport segment, the transportation mode and the travel agent stand for?
Tourist = datagram; transport segment = communication link; transportation mode = link layer protocol; travel agent = routing algorithm.
Framing and link access: what happens, and how are source and destination identified?
The datagram is encapsulated into a frame, adding header and trailer; channel access if shared medium; "MAC" addresses in frame headers identify source and dest — different from IP address!
When is reliable delivery between adjacent nodes seldom used, and where is it needed?
Seldom used on low bit-error links (fiber, some twisted pair); wireless links have high error rates.
Error detection vs error correction at the link layer.
Detection: the receiver detects the presence of errors (caused by signal attenuation, noise) and signals the sender for retransmission or drops the frame. Correction: the receiver identifies and corrects bit error(s) without resorting to retransmission.
What does half duplex mean?
Nodes at both ends of the link can transmit, but not at the same time.
Where is the link layer implemented?
In each and every host, in an "adaptor" (network interface card, NIC) or on a chip (Ethernet card, 802.11 card, Ethernet chipset); it implements the link and physical layers, attaches to the host's system buses, and is a combination of hardware, software, firmware.
What are EDC and D, and is error detection 100% reliable?
EDC = Error Detection and Correction bits (redundancy); D = data protected by error checking (may include header fields). Not 100% reliable: the protocol may miss some errors, but rarely; a larger EDC field yields better detection and correction.
Single bit parity vs two-dimensional bit parity.
Single bit parity: detect single bit errors. Two-dimensional bit parity: detect and correct single bit errors.
At which layer is the Internet checksum used?
At the transport layer only.
CRC: what are G, r and R, and what property must <D,R> have?
G: an r+1 bit pattern (the generator). R: r CRC bits chosen so that <D,R> is exactly divisible by G (modulo 2).
How does a CRC receiver detect errors, and which burst errors are always detected? Where is CRC used?
It divides <D,R> by G; a non-zero remainder means error detected. It detects all burst errors less than r+1 bits. Widely used: Ethernet, 802.11 WiFi, ATM.
Write the formula for the CRC bits R.
R = remainder[ D·2^r / G ] (from D·2^r XOR R = nG).
Two types of links, with examples.
Point-to-point: PPP for dial-up access; link between Ethernet switch and host. Broadcast (shared wire or medium): old-fashioned Ethernet, upstream HFC, 802.11 wireless LAN.
What is CSMA?
Carrier sense multiple access: listen before transmit. If the channel is sensed idle, transmit the entire frame; if busy, defer transmission ("don't interrupt others!").
Why can collisions still occur with CSMA, and what is wasted?
Propagation delay means two nodes may not hear each other's transmission. A collision wastes the entire packet transmission time; distance and propagation delay affect collision probability.
What does CSMA/CD add, and why is collision detection easy in wired but difficult in wireless LANs?
Collisions are detected within a short time and colliding transmissions are aborted, reducing channel wastage. Wired: measure and compare transmitted and received signal strengths. Wireless: received signal strength is overwhelmed by local transmission strength.
Ethernet CSMA/CD: what does the NIC do when it detects another transmission while transmitting?
It aborts and sends a jam signal, then enters binary (exponential) backoff.
Binary (exponential) backoff after the mth collision.
The NIC chooses K at random from {0, 1, 2, …, 2^m − 1}, waits K·512 bit times, and returns to Step 2 (sense the channel). More collisions → longer backoff interval.
IP address vs MAC address: size and use.
IP: 32 bits, network-layer address used for layer 3 forwarding. MAC: 48 bits (most LANs), used "locally" to get a frame from one interface to another physically-connected interface (same network); burned in NIC ROM.
Who administers MAC addresses, and what analogy contrasts MAC and IP?
IEEE administers allocation (manufacturers buy portions of the address space). MAC address: like a Social Security Number (flat, portable). IP address: like a postal address (hierarchical, not portable — depends on the subnet).
What does an ARP table entry contain, and what is its TTL?
< IP address; MAC address; TTL >. TTL (Time To Live): time after which the mapping is forgotten — typically 20 min.
ARP on the same LAN: how are the query and the reply sent?
Query: broadcast, dest MAC FF-FF-FF-FF-FF-FF, containing B's IP address; all nodes receive it. Reply: B sends its MAC address to A's MAC address (unicast).
What is "soft state", and why is ARP "plug-and-play"?
Soft state: information that times out (goes away) unless refreshed — like cached ARP entries. ARP is plug-and-play because nodes create their ARP tables without intervention from the net administrator.
Sending from A to B via router R: which addresses stay the same and which change?
IP source A and IP destination B stay the same end to end. The frame from A has R's MAC address as destination; R removes the datagram and sends a new frame with B's MAC address as destination (and R's own MAC on that side as source).
Why did Ethernet become the "dominant" wired LAN technology?
Cheap ($20 for NIC); first widely used LAN technology; simpler, cheaper than token LANs and ATM; kept up with speed race: 10 Mbps – 10 Gbps.
Bus vs star Ethernet topology.
Bus (popular through mid 90s, coaxial cable): all nodes in the same collision domain. Star (prevails today): active switch in center; each "spoke" runs a separate Ethernet protocol, so nodes do not collide with each other.
Ethernet frame fields in order, and the purpose of the preamble.
Preamble, dest. address, source address, type, data (payload), CRC. Preamble: 7 bytes of 10101010 then one byte 10101011, used to synchronize receiver and sender clock rates.
When does an Ethernet adapter pass a frame up, and what do "type" and CRC do?
It passes the data up if the destination address matches its own or is a broadcast address (e.g., ARP); otherwise it discards the frame. Type: higher layer protocol (mostly IP). CRC: checked at the receiver; error detected → frame dropped.
Why is Ethernet "connectionless" and "unreliable", and what is its MAC protocol?
Connectionless: no handshaking between NICs. Unreliable: the receiving NIC sends no acks or nacks; dropped data is recovered only if the sender uses higher-layer rdt (e.g., TCP). MAC protocol: unslotted CSMA/CD with binary backoff.
What do the different 802.3 Ethernet standards share, and how do they differ?
They share a common MAC protocol and frame format; they differ in speed (2 Mbps, 10 Mbps, 100 Mbps, 1 Gbps, 10 Gbps) and physical layer media (fiber, cable — e.g., 100BASE-TX copper, 100BASE-FX fiber).
Three properties of an Ethernet switch.
Link-layer device that takes an active role (stores and forwards frames, selectively forwarding by MAC address); transparent (hosts are unaware of switches); plug-and-play, self-learning (no configuration needed).
Why are there no collisions on a switched Ethernet, and what can happen simultaneously?
Hosts have dedicated, direct connections to the switch; links are full duplex; each link is its own collision domain. So A-to-A' and B-to-B' can transmit simultaneously, without collisions.
What is in a switch table entry, and how does the switch learn it?
(MAC address of host, interface to reach host, time stamp). When a frame arrives, the switch learns the sender's location from the incoming LAN segment and records the sender/location pair.
Switch frame filtering/forwarding rules.
Record incoming link and source MAC; look up the destination MAC. Found on the arrival segment → drop; found on another interface → forward on that interface; not found → flood on all interfaces except the arriving one.
Switches vs routers: layer and how the forwarding table is built.
Both are store-and-forward with forwarding tables. Routers: network-layer devices; compute tables using routing algorithms and IP addresses. Switches: link-layer devices; learn tables using flooding, learning and MAC addresses.