Computer Networks Lecture #9

Computer Networks Lecture #9

• Lecture covered Information-centric networking, Link layer and LANs, Error detection and correction, and Multiple access protocols.

Introduction to the Link Layer and LANs

• Link layer is responsible for transferring datagram from one node to physically adjacent node over a link.
• Nodes include hosts and routers.
• Links are communication channels connecting adjacent nodes along a communication path.
• Links can be wired, wireless, or LANs.
• Frames are layer-2 packets that encapsulate datagrams.

Link Layer Context

• Datagrams are transferred by different link protocols over different links (e.g., WiFi, Ethernet).
• Each link protocol provides different services—may or may not provide reliable data transfer.
• Analogy: a trip from Princeton to Lausanne by limo, plane, or train, illustrates how a datagram is transferred.

Link Layer Services

• Framing and link access: encapsulate datagram into frame/add header and trailer, channel access on shared medium.
• MAC addresses in frame headers identify source/destination nodes (different from IP addresses).
• Reliable delivery between adjacent nodes.
• Rarely used on low-bit error links.
• Used in wireless links that have high error rates.
• Both link level and end-to-end reliability mechanisms are used.

Link Layer Services (continued)

• Flow control: pacing between adjacent sending and receiving nodes.
• Error detection: errors caused by signal attenuation, noise. Receivers can detect errors, retransmit signals, or drop frames.
• Error correction: receivers identify and correct bit errors without retransmission.
• Half-duplex/Full-duplex: with half-duplex nodes at both ends can transmit, but not at the same time.

Where is the Link Layer Implemented?

• Implemented in Network Interface Card (NIC) or on a chip (Ethernet, WiFi card or chip).
• Implements link and physical layer.
• Attaches into host's system bus.
• Combination of hardware, software, and firmware.

Interfaces Communicating

• Sending side: encapsulates datagram in frame, adds error checking bits, reliable data transfer, flow control, etc.
• Receiving side: checks errors, reliable data transfer, flow control, extracts datagram and passes to upper later.

Error Detection and Correction

• Error detection is not 100% reliable; protocols may miss errors, but rarely.
• Larger EDC (Error Detection and Correction) field yields better detection and correction.
• EDC: error detection and correction bits (e.g., redundancy).
• Data protected by error checking, may include header fields.

Parity Checking

• Single bit parity: detect a single bit error.
• Two-dimensional bit parity: Detect and correct single-bit errors.
• Even parity: Number of 1's in data bits is even.

Recap: Internet Checksum

• Goal: detect errors (flipped bits) in transmitted segments.
• Sender: treat UDP segment contents as a sequence of 16-bit integers; calculate checksum (addition, one's complement sum) of segment content; place checksum value in UDP checksum field.
• Receiver: compute checksum of received segment, check if computed checksum equals checksum field value; error detected if they are not equal.

Cyclic Redundancy Check (CRC)

• More powerful error detection coding.
• D: data bits; G: big pattern (generator), of r+1 bits.
• Choose r CRC bits R such that <D, R> is exactly divisible by G (mod 2).
• Receiver knows G in advance; divides <D, R> by G; non-zero remainder = error detected.
• Can detect all burst errors less than r+1 bits.

Multiple Access Protocols

• Two types of links: point-to-point and broadcast (shared wire/medium).
• Broadcast examples: old-fashioned ethernet, upstream HFC in cable-based access, IEEE 802.11 wireless LAN (4G/5G, satellite).
• Single shared broadcast channel; two or more simultaneous transmissions = interference and collisions .

Multiple Access Protocols (continued)

• Distributed algorithm determines nodes' channel sharing - i.e., when a node can transmit.
• Communication for channel sharing control must use channel itself.
• No out-of-band channel for coordination.

Ideal Multiple Access Protocol

• Given: multiple access channel of rate R bps.
• Desirable: fully utilized (single node transmits at R), fairly shared (N nodes transmit at R/N average), fully decentralized (no central node to coordinate), no synchronization of clocks/slots, simple.

Three Broad Classes of MAC Protocols

• Channel partitioning: divide channel into smaller pieces (time slots, frequency, code). Allocate piece to node for exclusive use.
• Random access: channel not divided; allow collisions; recover from collisions ("recover" from collisions).
• Taking turns: nodes take turns (nodes with more to send can take longer turns).

Channel Partitioning: TDMA

• Time Division Multiple Access (TDMA).
• Access to channel in "rounds".
• Each station gets fixed-length slot (during each round) equal to packet transmission time.
• Unused slots are idle.

Channel Partitioning: FDMA

• Frequency Division Multiple Access (FDMA).
• Channel spectrum is divided into frequency bands; each station is assigned a fixed frequency band.
• Unused transmission time in frequency bands is idle.

Random Access Protocols

• When a node has a packet to send, it transmits at a full channel data rate of R.
• No a priori coordination among nodes.
• Two or more transmitting nodes can create a collision; random access MAC protocol specifies how to detect collision and recover from collision (via delayed retransmissions).
• Example protocols: ALOHA, slotted ALOHA, CSMA, CSMA/CD, CSMA/CA.

Slotted ALOHA

• Assumptions: All frames of the same size; time is divided into equal-size slots (transmit 1 frame).
• Nodes start transmission only at beginning of slot.
• If two or more nodes transmit via the same slot, all nodes detect collision.

Slotted ALOHA (continued)

• When a node obtains a fresh frame, transmits it in the next slot, no collision.
• Collision: node retransmits in each subsequent slot with a probability p until success
• Pros: single active node can continuously transmit at full channel rate; highly decentralized; simple.
• Cons: collisions, wasting slots, and idle slots (for random backoff). Clock synchronization is required.

Efficiency of Slotted ALOHA

• Efficiency: long-run fraction of successful slots (many nodes, all with many frames to send).
• Simple analysis: N nodes, each transmits in a slot with probability p; probability that a given node has success in a slot is p(1-p)N-1; probability that any node has a success in a slot is Np(1-p)N-1. Find p* that maximizes Np(1-p)N-1.

Efficiency of Slotted ALOHA (continued)

• Find p* that maximizes Np(1-p)N-1—p* is obtained by taking the derivative of f(N) and setting = 0. With p*, Np*(1-p*)N-1 = (1-1/N)N-1.
• For many nodes, limit of (1-1/N)N−1 as N goes to infinity is 1/e (approximately 0.37).

Pure ALOHA

• Unslotted ALOHA: simpler, no synchronization; when a frame is generated, it is transmitted immediately.
• Collision probability increases with no synchronization.

Carrier Sense Multiple Access (CSMA)

• Simple CSMA: listen before transmit; if channel is idle transmit entire frame; defer transmission if channel is sensed busy.
• CSMA/CD (CSMA with Collision Detection): collision is detected within a short time; colliding transmission is aborted; reduce channel wastage. Collision detect is easy in wired, difficult in wireless.

Collision in CSMA

• Collision can still occur with carrier sensing.
• Propagation delay means that two nodes may not hear each other's just-started transmission.

CSMA/CD

• CSMA/CD reduces amount of time wasted in collision.

Ethernet CSMA/CD Algorithm

• Step 1: NIC receives datagram, creates frame.
• Step 2: If channel idle, start frame transmission.
• Step 3: If transmit entire frame without collision, done.
• Step 4: Collision detected, abort, send jam signal.
• Step 5: Enter binary (exponential) backoff, wait K × 512 bit times, return to Step 2.
• More collisions: longer backoff interval.

Efficiency of CSMA/CD

• Tprop = max propagation delay between two nodes; Ttrans = time to transmit max-size frame. Efficiency = 1 / (1 + 5Tprop / Ttrans).
• Efficiency goes to 1 as Tprop goes to 0, and goes to infinity as Ttrans goes to infinity.
• Better performance than ALOHA. Simple, cheap, and decentralized.

"Taking Turn" MAC Protocols

• Channel partitioning MAC protocols: at high load, share channel efficiently and fairly; at low load, inefficient (e.g., single active node with 1/N bandwidth allocated).
• Random access MAC protocols: at high load = collision overhead; at low load = efficient (single active node fully utilizes channel).
• "Taking turn" protocols: look for best of both worlds.

"Taking Turn" MAC Protocols (continued)

• Polling: master node "invites" other nodes to transmit in turn (typically with "dumb" devices)—concerns: polling overhead, latency; single point of failure (master node).
• Token passing: control token passed sequentially from one node to the next; concerns: token overhead, latency, single point of failure (token).

Cable Access Network

• FDM, TDM, and random access: multiple downstream (broadcast) FDM channels (up to 1.6 Gbps/channel); single CMTS transmits into channels; no multiple access problems; multiple upstream channels (up to 1 Gbps/channel).
• Multiple access: all users contend (random access) for certain upstream channel time slots. Others are assigned in the manner of TDM.
• Data Over Cable Service Interface Specification (DOCSIS).

Summary of MAC Protocols

• Channel partitioning by time, frequency, or code (TDMA, FDMA). Random access (dynamic)– ALOHA, Slotted ALOHA, CSMA, CSMA/CD, CSMA/CA. Carrier sensing: easy in some technologies, hard in others. CSMA/CD used in ethernet; CSMA/CA used in IEEE 802.11. Taking turns: polling, token passing (Bluetooth, FDDI, token ring).

This quiz covers key concepts from Lecture #9 of Computer Networks, focusing on Information-centric networking, the Link layer, and LANs. It includes topics such as error detection, correction methods, and various multiple access protocols utilized in networking. Test your understanding of how data is framed and transmitted between nodes in different networking scenarios.