Slotted ALOHA Protocol Quiz

Chapter 5: Link Layer

• The link layer is responsible for transferring datagrams from one node to another physically adjacent node over a link.
• It encapsulates datagrams in frames.
• Hosts and routers are nodes.
• Communication channels that connect adjacent nodes along communication paths are links (wired links, wireless links).
• Link layer services cover framing, link access for encapsulating datagrams into frames, adding headers, and trailers, channel access if needed, and MAC addresses in frame headers to identify source and destination.
• Reliable delivery is between adjacent nodes.
• Flow control paces adjacent sending and receiving nodes.
• Link layer services include error detection, error correction, and half-duplex and full-duplex.
• Error detection and correction are crucial for handling signal attenuation, noise.
• Receivers detect and signal for retransmission or drop frames.
• Receivers identify and correct bit errors (without resorting to retransmission) with flow control.

Link Layer Implementation

• Link layer is implemented in network interface cards (NICs) or on a chip in each host.
• Ethernet cards, 802.11 cards, and Ethernet chipsets implement link and physical layers.
• These attach to the host's system buses.
• They combine hardware, software, and firmware.

Adaptors Communication

• Sending side encapsulates datagrams in frames, adds error checking bits, rdt, flow control, etc.
• Receiving side looks for errors, rdt, flow control, etc. Extracts the datagram, and passes it up to the receiver’s upper layer.

MAC Protocols: Taxonomy

• Three classes of MAC protocols include channel partitioning, random access, and taking turns.
• Channel partitioning divides the channel into smaller pieces (time slots, frequency, code).
• Random access allows collisions.
• Taking turns involves nodes taking turns; nodes with more to send might take longer turns.

Channel Partitioning MAC Protocols: TDMA and FDMA

• TDMA (Time Division Multiple Access) access channel in rounds. Each station receives a fixed length slot in each round, and unused slots are idle.
• FDMA (Frequency Division Multiple Access) divides the channel spectrum into frequency bands with each station assigned to a fixed frequency band. Unused time goes idle.

Random Access Protocols

• When a node wants to send a packet, it transmits at full channel data rate R; no prior coordination.
• Two or more nodes transmitting → collision. Random access MAC protocol specifies how to detect and recover from collisions.

Slotted ALOHA

• All frames have the same size, and time is divided into equal size slots (time for transmitting one frame).
• Nodes start to transmit at the beginning of a slot.
• Nodes are synchronized.
• If two or more nodes transmit in the same slot, all nodes detect collision.

Slotted ALOHA Efficiency

• Maximizes efficiency by finding the probability that maximizes the long run fraction of successful slots given many nodes with many frames to send.
• The max efficiency is 1/e = .37

Pure (Unslotted) ALOHA

• Simpler than slotted ALOHA with no synchronization.
• When a frame arrives, the node transmits immediately.
• Collision probability increases when the frame sent at t₀ collides with other frames sent in [to-1,t₀+1].

Pure ALOHA Efficiency

• Probability of success by a given node is the probability of no other node transmitting in [t₀-1,t₀].
• The efficiency is worse than Slotted ALOHA with a value of 1/(2e) = .18.

CSMA (Carrier Sense Multiple Access)

• Listen before transmission.
• If the channel is sensed idle, transmit the entire frame, otherwise, defer the transmission to prevent collisions from occurring.
• Human analogy: don’t interrupt others.

CSMA Collisions

• Collisions can occur because propagation delays occur.
• Two nodes may not hear each other's transmission, and thus, the entire packet transmission time is wasted.

CSMA/CD (Collision Detection)

• Collisions are detected in a short time.
• Colliding transmissions are aborted, reducing channel wastage.
• Easily done with wired LANs.
• Difficult with wireless LANs.

Ethernet CSMA/CD Algorithm

• Step 1: NIC receives, creates frame.
• Step 2: If NIC senses idle, transmits; if busy, waits until idle and transmits.
• Step 3: If NIC transmits the entire frame and no more transmissions occur, NIC is done with frame.
• Step 4: If NIC detects transmission while transmitting, it aborts the transmission.
• Step 5: After aborting the transmission, the NIC enters binary (exponential) backoff.

CSMA/CD Efficiency

• The efficiency is 1/(1+5 * (propagation delay / transmission time))
• Efficiency increases as propagation delay decreases and transmission time increases.
• Better performance than ALOHA.

"Taking Turns" MAC Protocols

• Channel partitioning MAC protocols share the channel efficiently in a high load.
• Inefficient at low load due to delays in channel access.
• Random access MAC protocols are efficient at low load because a single node fully utilizes the channel.
• High load with collision overhead.

Polling

• The master node invites slave nodes to transmit in turn.
• Typically used with dumb slave devices.
• Concerns include polling overhead, latency, and single point of failure.

Token Passing

• Control token is passed sequentially.
• Considers token overhead and latency, and single point of failure.

Cable Access Network

• Internet frames, TV channels, and controls are transmitted downstream at different frequencies.
• Multiple 40 Mbps downstream channels and single CMTS transmissions are present.
• Multiple 30 Mbps upstream channels allow multiple access.

DOCSIS

• Data over Cable Service Interface Specification uses FDM over the upstream and downstream channels.
• TDM over upstream channels allows some slots for assignment with some contention.
• Downstream MAP frame assigns upstream slots, and requests for upstream slots (and data) are transmitted through random access (binary backoff).

Virtual LANs

• A switch (or switches) supports VLAN capabilities to define multiple virtual LANs over a single physical LAN infrastructure to group the ports.
• Port-based VLAN groups switch ports, so that single physical switches operate as multiple virtual switches. Using a combination of ports and MAC addresses of endpoints enables dynamic membership among VLANs.

Ethernet Switch

• A link-layer device takes on an active role, storing and forwarding Ethernet frames.
• It examines incoming frame MAC addresses.
• Selectively forwards frames based on outgoing links.
• It uses CSMA/CD to gain access to the segment.
• It is transparent, hosts are not aware of its presence, and plug-and-play.

Switch Forwarding Table

• A switch maintains a table to determine if a host is reachable through a specific interface.
• The table contains the MAC address of the host, the interface to reach the host, and a timestamp.

Switch (Self-Learning)

• Switches learn which hosts are reachable and through which interfaces.
• The switch learns this when frames arrive; the location of the sender is recorded.
• The sender/location pair is then stored in the switch table.

Self-Learning, Forwarding, Example

• When a frame’s destination location is unknown, the switch floods the frame to all ports.
• If the destination’s location is known, the switch selectively sends the frame on a single link.

Interconnecting Switches

• Switches can be connected together.
• The protocols enable self-learning to work exactly as in the single-switch case.

Data Center Networks

• Data center networks involve thousands of closely coupled hosts.
• Challenges involve managing/balancing the load among the applications.
• Load balancers are crucial for directing external requests to the appropriate workloads.

Synthesis: a Day in the Life of a Web Request

• Journey down the protocol stack is complete.
• A solid understanding of networking principles along with the practice can be gained by revisiting the protocols involved in a seemingly simple scenario, such as the request to receive www.google.com.
• A student connects to the campus network and requests a webpage from www.google.com