Link Layer and Slotted ALOHA Quizzes

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Match the link layer services with their descriptions:

Flow control = Pacing between adjacent sending and receiving nodes Error detection = Detects errors caused by signal attenuation and noise Error correction = Identifies and corrects bit errors without retransmission Full-duplex = Both nodes can transmit simultaneously

Match the terms with their definitions regarding link layer implementations:

Adaptor = Network interface card (NIC) Ethernet card = Used for wired local area networks 802.11 card = Used for wireless local area networks Bus = Interconnects components within the host system

Match the components in the data transmission process:

Sending side = Encapsulates datagram in a frame Receiving side = Looks for errors and performs flow control Datagram = The main unit of data being transmitted Frame = The encapsulation of datagram for transmission

Match the types of links with their characteristics:

Low bit-error link = Seldom used for unreliable delivery Wireless links = Often have high error rates Half-duplex = Nodes can transmit, but not simultaneously End-to-end reliability = Ensures data integrity across the entire transmission path Signup and view all the answers

Match the terms related to error handling with their roles:

Retransmission = Signals sender to resend corrupted data Error checking bits = Added to frames for detecting errors Flow control = Regulates data transmission rate Bit error correction = Corrects errors without needing a retransmission Signup and view all the answers

Match the following error detection methods with their descriptions:

Parity Checking = Detect single bit errors or correct single bit errors Internet Checksum = Detect errors in transmitted packets by computing a checksum Cyclic Redundancy Check = Detect errors using a generator and checking for divisibility Error Detection and Correction (EDC) = Add redundancy to protect data from errors Signup and view all the answers

Match the following protocols with their primary function:

ARP = Address Resolution Protocol for mapping IP addresses to MAC addresses Ethernet = Protocol for LAN communication using frames MPLS = Multiprotocol Label Switching for efficient data forwarding VLANs = Virtual Local Area Networks for segmenting network traffic Signup and view all the answers

Match the following checksum types with their features:

Single Bit Parity = Detects single bit errors only Two-Dimensional Bit Parity = Detects and corrects single bit errors 16-bit Integer Checksum = Sum of segment contents for error detection Cyclic Redundancy Check = Uses division by a generator to detect errors Signup and view all the answers

Match the following link layer services with their purposes:

Error Detection = Identify and potentially correct errors in data transmission Multiple Access Protocols = Manage how multiple devices access the same network medium Data Center Networking = Facilitate communication within and between data centers Link Virtualization = Abstract physical links to optimize network performance Signup and view all the answers

Match the following components with their roles in network communication:

Sender = Computes checksum before transmission Receiver = Checks received data against checksum Data Field = Contains actual transmitted information Checksum Field = Holds the computed checksum for validation Signup and view all the answers

Match the random access MAC protocols with their characteristics:

Slotted ALOHA = Synchronized transmission slots ALOHA = Uncoordinated transmission CSMA/CD = Collision detection CSMA/CA = Collision avoidance Signup and view all the answers

Match the pros of Slotted ALOHA with their descriptions:

Single active node = Continuous transmission at full channel rate Highly decentralized = Only synchronization needed is for slots Simple = Easier implementation Efficient under load = Max efficiency at 1/e Signup and view all the answers

Match the terms with their definitions regarding collisions:

Collision = Two or more nodes transmitting simultaneously Retransmission = Sending a frame again after a collision Synchronization = Coordinating time slots for transmission Idle slots = Time periods without successful transmissions Signup and view all the answers

Match the aspects of Slotted ALOHA with their features:

Time slots = Equal size for frame transmission Frame size = All frames are the same size Probability p = Transmission probability for nodes Collision detection = Nodes detect collision in the slot Signup and view all the answers

Match the following statements to their effects in Slotted ALOHA:

Idle slots = Wasted time due to no transmissions Successful transmission = Slot utilized without collision Busy slots = Slots with ongoing transmissions Collisions = Result in retransmission delays Signup and view all the answers

Match the characteristics of Slotted ALOHA with their implications:

Decentralized nature = No central coordination required Collision detection = All nodes can sense if a collision occurs Synchronized nodes = Necessary for time slot alignment Probability mechanism = Allows for variable retransmission attempts Signup and view all the answers

Match the concepts with their associated problems in Slotted ALOHA:

Collisions = Lead to wasted transmission slots Clock synchronization = Requires accurate timing across nodes Transmission attempts = Dependent on node's probability p for activation Infinite nodes = Can affect maximum efficiency calculations Signup and view all the answers

Match the efficiency terms with their explanations:

Max efficiency = Achieved at $1/e$ Probability $p$ = Transmits in slot with this probability Successful slots = Fraction of slots with successful transmissions Limit process = Analyzing behavior as $N$ approaches infinity Signup and view all the answers

Match the following network protocols with their descriptions:

Pure ALOHA = Transmits immediately when a frame arrives without synchronization CSMA = Listens before transmitting and defers if the channel is busy CSMA/CD = Detects collisions and aborts transmission to reduce wastage Slotted ALOHA = Uses synchronization for transmitting frames and reducing collisions Signup and view all the answers

Match the following terms with their associated probabilities:

P(success by given node) = $p(1-p)^{2(N-1)}$ Collision probability in unslotted ALOHA = $P(node transmits) imes P(no other node transmits)$ Optimum success in ALOHA = $rac{1}{2e}$ Successful transmission probability = $p(1-p)^{N-1}$ Signup and view all the answers

Match the following protocols with their characteristics:

Pure ALOHA = Higher collision probability due to no synchronization CSMA = Defers transmission if the channel is busy CSMA/CD = Aborts transmission upon detecting collisions Slotted ALOHA = Lower collision probability compared to Pure ALOHA Signup and view all the answers

Match the following properties with their respective access methods:

Carrier Sensing = Listen before transmit in CSMA Collision Detection = Measure signal strength in CSMA/CD Immediate Transmission = Characteristic of Pure ALOHA Deferred Transmission = Characteristic of CSMA protocol Signup and view all the answers

Match the following scenarios with the suitable access method:

Wireless LANs = Difficult collision detection Wired LANs = Easy to measure signal strengths Unslotted ALOHA = Frames collide if sent in overlapping time slots CSMA = Prevents interruption during active transmission Signup and view all the answers

Match the following definitions with their corresponding terms:

Propagation Delay = Time taken for a signal to travel from sender to receiver Channel Idle = State when no transmission is occurring Collision = When two frames are sent simultaneously leading to interference Frame Transmission Time = Time it takes to send an entire data frame Signup and view all the answers

Match the following efficiency ratings with their respective ALOHA types:

Pure ALOHA = 18% efficiency Slotted ALOHA = More efficient than Pure ALOHA CSMA = Generally has better efficiency than ALOHA CSMA/CD = Improves efficiency by reducing collision losses Signup and view all the answers

Study Notes

Chapter 5: Link Layer

PowerPoint slides are freely available for faculty, students, and readers
Slides can be modified, added to, and deleted as needed.
Use requirements: if using these slides in a class, mention their source. If posting on a website note that slides are adapted and copyright belongs to Kurose and Ross.

Link Layer Introduction

Terminology: Hosts and routers are nodes. Communication channels connecting nodes are links (wired/wireless).
Layer-2 packet: Frame encapsulates the datagram.
Data-link layer is responsible for moving datagrams from one node to its physically adjacent neighbour on a link.

Link Layer Context

Datagrams are transferred by different link protocols over different links (e.g., Ethernet on first link, frame relay on intermediate links, 802.11 on last link)
Each link protocol provides different services (e.g., some may or may not provide reliable data transfer)

Link Layer Services

Framing, Link Access: encapsulates datagram into a frame, adding header and trailer. Channel access if shared medium.
MAC addresses for source and destination used in frame headers. MAC address is different from IP address
Reliable delivery between adjacent nodes: useful for high error rate links.
Flow Control: pacing between adjacent sending and receiving nodes
Error Detection: errors from signal attenuation, noise detected by receiver (signals sender to retransmit or drop frame).
Error Correction: receiver identifies and corrects bit errors without resorting to retransmission.
Half-duplex and Full-duplex: With half-duplex, nodes transmit but not at the same time.

Where Link Layer is Implemented

Implemented in each host's network adapter (NIC) or on a chip
Ethernet card, 802.11 card, Ethernet chipset implement link and physical layer.
Attaches to host system buses
Combination of hardware, software, and firmware

Adaptors Communicating

Sending side encapsulates datagram in a frame, adds error checking bits, rdt, and flow control.
Receiving side looks for errors, rdt, and flow control, extracts datagram and passes it to the upper layer.

Error Detection

EDC (Error Detection and Correction bits) used for redundancy
Data (D) protected by error checking, can include header fields
Error detection may not be 100% reliable. Larger EDC field yields better detection and correction
Parity checking – detect single bit errors

Parity Checking

Single Bit Parity: detects single bit errors.
Two-Dimensional Bit Parity: detects and corrects single bit errors (shows how parity rows and columns are used to find errors)

Internet Checksum (Review)

Goal: detects errors (e.g., flipped bits) in transmitted data packets (used in transport layer only)
Sender treats segment contents as sequence of 16-bit integers, performs checksum calculation (addition of I's complement sum of segment contents), puts checksum value into UDP checksum field
Receiver computes checksum of received segment. Checks if computed checksum equals checksum value, reports error if not equal.

Cyclic Redundancy Check (CRC)

More powerful error-detection coding
Viewed as binary format, goal is to choose a certain amount of CRC bits so that the concatenation of the data bits and CRC bits is exactly divisible by a certain divisor (G). If non-zero remainder, error detected. Can detect all burst errors less than a certain amount of bits. Widely used in practice (Ethernet, 802.11, WiFi, ATM).

MAC Protocols: Taxonomy

Channel Partitioning: divide channel into pieces (time slots, frequency, code) and allocate piece to node for exclusive use.
- TDMA: Time Division Multiple Access, channel access in rounds, each station gets a fixed length slot (length = packet transmission time) in each round. Unused slots go idle.
- FDMA: Frequency Division Multiple Access, channel spectrum divided into frequency bands, each station gets a fixed frequency band, unused time in frequency bands is idle.
Random Access: Channel not divided, allows collisions.
- Slotted ALOHA: Nodes start transmitting at the beginning of a slot. If two or more nodes transmit in a slot, all nodes detect collision. Single active node continuously transmits at full channel rate, highly decentralized; only slots in nodes need to be in sync, simple.
- Pure ALOHA: Simpler, no synchronization. When frame arrives, transmit immediately.
Taking Turns:
- Polling: master node invites slave nodes to transmit in turn.
- Token Passing: control token passed from one node to next sequentially.

Multiple Access Links and Protocols

Two types of links: point-to-point, broadcast (shared wire). - PPP dial-up access - Point-to-point (link between Ethernet switch, host) - Old-fashioned Ethernet - Upstream HFC 802.11 wireless LAN - Shared wire (e.g., wired Ethernet) - Shared RF (e.g., 802.11 WiFi) - Shared RF (e.g., satellite), human at a cocktail party

Ethernet CSMA/CD Algorithm (Collision Detection)

NIC receives datagram from Network layer, creates frame
If NIC senses channel idle, starts frame transmission; if busy it waits for channel to idle, then transmits
NIC transmits entire frame without another transmission; NIC is done with frame
If collision detected, aborts transmission, sends jam signal; enters binary (exponential) backoff

CSMA/CD Efficiency

Efficiency is 1/(1+5(tprop/ttrans))
Efficiency goes to 1 as tprop/ttrans approaches 0, and goes to infinity as ttrans goes to infinity

Ethernet: Unreliable, Connectionless

Connectionless: no handshaking between sending and receiving NICs
Unreliable: receiving NIC doesn't send acks or nacks
Sending NIC recovers dropped frames only if initial sender uses higher layer rdt (e.g., TCP); otherwise, dropped data is lost.

Ethernet Switch

Functionality: takes active role, examines incoming frame MAC address, selectively forwards frame to one or more outgoing links using CSMA/CD to segment access.
Transparent: hosts unaware of presence of switches, plug-and-play, self-learning; switches don't need to be configured.

Switch Forwarding Table

Q: How does the switch know A' reachable via interface 4, B' reachable via interface 5? Each switch has a table. Each entry: (MAC address of host, interface to reach host, time stamp). Looks like a routing table.
Q: How are entries created and maintained in table? Something like a routing protocol.

Switch: Self-Learning

Switch learns which hosts can be reached through which interfaces.
When frame received, switch learns sender's location (Incoming LAN segment).
Records sender/location pair in switch table.

Switch Frame Filtering/Forwarding

Record incoming link, MAC address of sending host.
Index switch table using MAC destination address
If entry found for destination
- If destination on segment, drop frame
- Else forward on interface indicated by entry
Else flood (forward on all interfaces except arriving interface)

Interconnecting Switches

Switches can be connected together.
Self-learning works in the same way as single-switch case.

Cable Access Network

Internet frames, TV channels, control transmitted downstream at different frequencies.
Multiple 40 Mbps downstream (broadcast) channels, single CMTS transmits into channels. Multiple 30 Mbps upstream channels.

DOCSIS

Data over cable service interface specification (FDM) over upstream and downstream channels. TDm upstream uses some slots and assigning slots and contention. Request for upstream slots (and data) transmitted using random access (binary backoff) in selected slots.

VLANs

Motivation: CS user moves office to Electrical Engineering department, but wants to connect to the Computer Science switch. Single broadcast domain: all layer-2 broadcast traffic (ARP, DHCP), destination MAC address must cross entire LAN.

VLANs Spanning Multiple Switches

Trunk port: carries frames between VLANs defined over multiple physical switches.
Frames forwarded must carry VLAN ID info. 802.1q protocol adds/removes additional header fields for frames forwarded between trunk ports.

VLAN Frame Format

2-byte tag protocol identifier (81-00), recomputed CRC (cyclic redundancy check).

Multiprotocol Label Switching (MPLS)

Initial Goal: high-speed IP forwarding using fixed-length labels (instead of IP address)
Fast lookup with fixed length identifier (rather than shortest prefix matching)
Borrowing ideas from Virtual Circuits (VC) approach
IP datagram still contains IP address.

MPLS Capable Routers

Forward packet to outgoing interface based only on label value (don't inspect IP address)
MPLS forwarding table distinct from IP forwarding tables
Uses destination and source addresses to route flows to the same destination differently.

MPLS Versus IP Paths

IP routing: path to destination determined by destination address alone.
MPLS routing: path to destination can be based on source and destination address. Fast reroute: precompute backup routes in case of link failure.

MPLS Signaling

Modifies OSPF, IS-IS link-state flooding protocols to carry information used by MPLS routing.
RSVP-TE signaling protocol sets up MPLS forwarding at downstream routers.

MPLS Forwarding Tables

Shows tables with labeled data to help understand how data is forwarded.

Data Center Networks

10's to 100's of thousands of hosts often closely coupled in close proximity.
E.g., e-business, content servers, search engines, data mining.
Challenges: managing/balancing load, avoiding processing, and networking data bottlenecks.

Data Center Networks (Load Balancers)

Load balancer: receives external client requests, directs workload within data center, returns results to external client (hiding data center internals from client).

Data Center Networks (Interconnection)

Rich interconnection among switches, racks increases throughput and reliability.

Synthesis: A Day in the Life of a Web Request

Journey down protocol stack complete (except PHY).
Goal: identify and review protocols at all layers involved in simple scenario (e.g., student requests www.google.com).
- Scenario breakdown: student attaches laptop to campus network, requests/receives www.google.com.

A Day in the Life... Scenario

Breakdown of scenario for web requests (e.g., student requesting www.google.com).

A Day in the Life... Connecting to the Internet

Connecting a laptop to the internet involves processes to get IP address, first hop address, and DNS addresses (DHCP)

A Day in the Life... ARP (DNS, HTTP)

before sending HTTP request, need IP address
DNS query, encapsulates UDP --> IP
ARP query, broadcast, receives (reply) from router with MAC address of first-hop router, so can send frame with DNS query (unicast).

A Day in the Life... using DNS

IP datagram containing DNS query forwarded via LAN switch

A Day in the Life... TCP Connection Carrying HTTP

Client opens TCP socket to web server;
TCP SYN segment, inter-domain routed to web server;
Web server responds SYNACK;
TCP connection is established.

A Day in the Life... HTTP Request/Reply

HTTP request is sent into TCP socket
IP datagram containing HTTP request routed to web server, which responds HTTP reply
IP datagram containing HTTP reply routed back to client.

Chapter 5 Summary

Principles behind data link layer services
Instantiation and implementation of various link layer technologies (Ethernet, switched LANs, VLANs, virtualized networks) and synthesis of a day in the life of a web request

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Test your understanding of link layer implementations and Slotted ALOHA protocols with this comprehensive quiz. Match terms with their definitions, error detection methods with descriptions, and various components involved in data transmission. Enhance your knowledge of networking concepts and error handling techniques.