Computer Networking Error Detection Methods

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the primary purpose of error detection codes (EDC)?

To provide redundancy for error correction (correct)

To ensure data is transmitted faster

To encrypt data during transmission

To optimize routing in a network

Which method is used to detect and correct single bit errors?

Cyclic redundancy check

Internet checksum

Two-dimensional bit parity (correct)

Single bit parity

In the context of internet checksum, what action is taken by the receiver?

Add an error detection code to the segment

Compute a checksum of the received segment (correct)

Modify the segment contents

Transmit a new checksum to the sender

What characteristic of cyclic redundancy check (CRC) makes it more powerful than other error-detection methods?

It allows multiple errors to be detected Signup and view all the answers

What happens if a computed checksum does not match the checksum field value at the receiver?

An error is detected Signup and view all the answers

What is the maximum number of bits that can be detected for burst errors using CRC?

r+1 bits Signup and view all the answers

Which of the following is NOT a characteristic of an ideal multiple access protocol?

Requires a centralized coordination node Signup and view all the answers

Which type of link is exemplified by older Ethernet or 802.11 wireless LAN connections?

Broadcast links Signup and view all the answers

In the context of CRC, what does the expression R = remainder[D.2r / G] signify?

R is the output of the CRC algorithm Signup and view all the answers

What protocol is commonly used for dial-up access as a point-to-point link?

PPP Signup and view all the answers

What is the probability of a given node successfully transmitting in Pure ALOHA?

$p(1-p)^{2(N-1)}$ Signup and view all the answers

In CSMA, what happens when the channel is sensed to be busy?

The node waits and defers transmission. Signup and view all the answers

What is a significant drawback of using CSMA in communication?

Collisions can still occur due to propagation delay. Signup and view all the answers

What is the main advantage of CSMA/CD over CSMA?

It detects collisions and aborts the transmission. Signup and view all the answers

Why is collision detection difficult in wireless LANs compared to wired LANs?

Local transmission strength overwhelms received signal strength. Signup and view all the answers

What is the efficiency of Pure ALOHA at its optimum probability p?

1/(2e) Signup and view all the answers

In the context of networking, what does a higher collision probability indicate?

Lower successful packet transmission rates. Signup and view all the answers

What is the key feature of unslotted ALOHA?

Transmission occurs immediately upon frame arrival. Signup and view all the answers

What is the primary function of a MAC address in a local area network?

To get a frame from one interface to another in the same network Signup and view all the answers

Which of the following describes the method of time division multiple access (TDMA) used in upstream channels?

Certain time slots are assigned while others are for contention Signup and view all the answers

What does the term 'token' refer to in the context of network protocols?

A mechanism to ensure only one user can transmit at a time Signup and view all the answers

What is the primary purpose of the Address Resolution Protocol (ARP)?

To resolve a device's MAC address from its IP address Signup and view all the answers

In a cable access network, what type of channels are used for transmitting data upstream?

Multiple time-slotted channels that are contended Signup and view all the answers

Which access method is employed by Ethernet as part of its MAC protocol?

Carrier Sense Multiple Access with Collision Detection (CSMA/CD) Signup and view all the answers

What technology is used for managing multiple access in wireless networks?

Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) Signup and view all the answers

Study Notes

Chapter 5: Link Layer

This chapter discusses the principles behind data link layer services, including error detection and correction, sharing a broadcast channel, and link layer addressing.
It also covers the instantiation and implementation of various link layer technologies, such as Ethernet, switched LANs, VLANs, and virtualized networks (MPLS).
Finally, it includes a synthesis of a day in the life of a web request, walking through the various protocols involved.

Note on the Use of PPT Slides

Slides are freely available for faculty, students, and readers.
They are in PowerPoint format, allowing animations and modifications.
Users are only asked to cite the source of the slides and note the copyright when using or posting them online.

Link Layer, LANs: Outline

Section 5.1: Introduction, services
Section 5.2: Error detection, correction
Section 5.3: Multiple access protocols
Section 5.4: LANs (addressing, ARP, Ethernet, switches, VLANs)
Section 5.5: Link virtualization (MPLS)
Section 5.6: Data center networking
Section 5.7: A day in the life of a web request

Link Layer: Introduction

Hosts and routers are nodes.
Communication channels connect adjacent nodes, forming links.
Links encompass wired and wireless connections, including LANs.
A layer-2 packet is called a frame; it encapsulates a datagram.
The data link layer is responsible for transferring datagrams between physically adjacent nodes over a link.

Link Layer: Context

Different link protocols handle datagram transfers across various links (e.g., Ethernet, frame relay).
Each link protocol provides distinct services.

Link Layer Services

Framing and link access: encapsulate datagram into frame, adding header and trailer; channel access if shared medium; identifying source and destination using MAC addresses (different from IP addresses).
Reliable delivery between adjacent nodes is covered in Chapter 3. Wireless links typically have high error rates.

Link Layer Services (More)

Flow control ensures pacing between adjacent sending and receiving nodes.
Error detection identifies errors (caused by signal attenuation or noise) based on the presence of errors, signaling retransmission or dropping frames, depending on the protocol in use.
Error correction identifies and corrects bit errors without retransmission.
Half-duplex and full-duplex describe differing transmission capabilities; in half-duplex, transmission happens one at a time at both ends, whereas in full-duplex, both ends can transmit concurrently.

Where is the Link Layer Implemented?

The link layer resides in each host's network interface card (NIC) or a chip.
Implementations include Ethernet card and chipset.
The link layer integrates into host system buses.
It is a complex interplay of hardware, software, and firmware.

Adaptors Communicating

The sending side encapsulates the datagram in a frame, adding error checking bits, flow control, and other relevant information.
The receiving side then handles error detection and flow control, extracting and passing the datagram to higher-layer protocols.

Error Detection

Error detection and correction (EDC) bits provide redundancy.
Data (D) is protected by error checking; the EDC field yields better detection/correction for larger fields.
Protocols may miss some errors; larger EDC fields lead to better error handling.

Parity Checking

Single-bit parity detects single bit errors.
Two-dimensional parity detects and corrects single-bit errors by checking rows and columns.

Internet Checksum (Review)

Goal: Detects errors (e.g., flipped bits) in packets.
Used only at the transport layer.
Sender treats segment contents as 16-bit integers, and calculates checksum (one's complement sum of segment contents).
Sender puts checksum value into UDP checksum field.
Receiver computes received segment checksum and checks for equality with checksum field value.

Cyclic Redundancy Check

A powerful error-detection coding technique.
Treating data bits (D) as numbers and using a generator (G), r CRC bits are generated ensuring a resultant value that’s exactly divisible by G.
Widely used protocols (Ethernet, 802.11 WiFi, ATM) utilize CRCs.

CRC Example

Demonstrates the calculation of the remainder (R) when a dividend (D) is divided by a divisor (G).

Multiple Access Protocols

Protocols allow sharing of a single shared broadcast channel by multiple nodes.
Interference occurs when simultaneous transmissions occur, leading to collision, where a node receives signals from two or more nodes simultaneously.
Distributed algorithm defines how nodes share a channel, determining how a node can transmit, requiring channel usage for the communication itself.

An ideal multiple access protocol

An ideal multiple access protocol should permit each node to transmit at its full rate (R) in a given scenario, with M nodes averaging at R/M rate.

MAC Protocols: Taxonomy

Channel partitioning divides the channel into pieces (e.g., time slots, frequencies, or codes) for exclusive use by nodes.
Random access methods accept collisions and protocols define how to handle them, such as delayed transmission.
"Taking turns" protocols involve nodes taking turns, sometimes with those having more to send taking longer.

Channel Partitioning MAC Protocols: TDMA

TDMA (Time Division Multiple Access) access channel in rounds; each station has a fixed-length slot at each round.
Unused slots remain idle.

Channel Partitioning MAC Protocols: FDMA

FDMA (Frequency Division Multiple Access) divides channel into frequency bands; each station uses one band with idle periods available in unused bands.

Random Access Protocols

When a node needs to transmit, it occurs at full channel rate (R).
If more than one node transmits, a collision occurs.
Random access protocols manage and recover from collisions, like slotted ALOHA, ALOHA, and CSMA/CD, CSMA/CA protocols.

Slotted ALOHA

All frames are of the same size.
Time is divided into equal-size slots (time to transmit one frame).
Nodes synchronize with beginning slots, transmitting only in a designated slot.

Slotted ALOHA: Efficiency

The long-run fraction of successful slots is optimized; efficiency reaches a maximum value at 1/e.

Pure (Unslotted) ALOHA

Unslotted Aloha operates without synchronization, transmitting immediately when a frame arrives.
Collision probability increases as sending immediately following another frame's transmission.

Pure ALOHA Efficiency

Probability of success for a given node is determined by the node's transmission probability and probability that no other nodes transmit in a certain slot.

CSMA (Carrier Sense Multiple Access)

The CSMA protocol dictates that before transmitting, a node listens to the channel. If the channel is idle, the node transmits the entire frame; if busy, it defers transmission to a later time

CSMA Collisions

Propagation delay can result in collisions because two nodes may not hear each other's transmissions, resulting in wasted entire packet transmission time, depending on the distance and propagation delay between nodes.

CSMA/CD (Collision Detection)

CSMA/CD detects collisions within a short time.
Collisions result in aborted transmissions.
Collision detection is easy for wired LANs (comparing transmitted and received signals).

Ethernet CSMA/CD Algorithm

Ethernet CSMA/CD algorithm describes how a NIC receives a datagram from the network layer and creates a frame.
The NIC listens to the channel. If idle, it transmits the frame; if busy, it waits until idle, then transmits.
If a transmission is interrupted, the NIC aborts.
Exponential binary backoff is employed in collision recovery.

CSMA/CD Efficiency

Efficiency is determined by the ratio of propagation delay (Tprop) to transmission time (ttrans) in a wired LAN.

“Taking Turns” MAC Protocols

Channel partitioning protocols perform well at high loads but inefficient at low loads, and delay in access occurs when only one node is active.
Random access protocols perform effectively at low loads (fully utilized when a single active node exists) but suffer overhead due to collisions at high loads.

Polling

A master node in a polling system invites slave nodes to transmit in turn; typically used with dumb slave devices.

Token Passing

A control token sequentially passes between nodes, enabling them to transmit when possessing the token; overhead and latency are potential concerns.

Cable Access Network

Internet frames and TV channels are transmitted over cable systems at various frequencies.
The CMTS (cable modem termination system) transmits downstream information and receives upstream information, with users contending for upstream channels.

DOCSIS (Data over Cable Service Interface Specification)

DOCSIS manages upstream and downstream channels using time divisions.
FDM over upstream and downstream channels.

Summary of MAC Protocols

Channel partitioning uses time, frequency, or code divisions for efficient channel sharing at high loads.
Random access methods use strategies that handle conflicts.
"Taking turns" protocols, like polling and token passing, utilize a coordinated approach.

MAC Addresses and ARP

32-bit IP addresses are network layer addresses for interfaces, used for layer 3 forwarding.
48-bit MAC addresses provide' locally addressing within networks.
ARP (Address Resolution Protocol) facilitates mapping between IP and MAC addresses, enabling communication within a local network.

LAN Addresses and ARP

Each adapter on a LAN has a unique LAN address.

LAN Addresses (More)

IEEE assigns MAC addresses; these are portable (can be moved to another LAN).
IP addresses are hierarchical; portability depends on the subnet.

ARP: Address Resolution Protocol

ARP determines a network interface’s MAC address when its IP address is known.
Each IP node (host or router) maintains an ARP table with mappings of IP addresses to MAC addresses.
TTL (Time to Live) determines how long an entry in ARP table remains valid before it’s automatically removed.

ARP Protocol: Same LAN

A sends an ARP query if B's MAC address is not in its table.
All LAN nodes receive the query.
B replies with its MAC address.
A caches the information for use later.

Addressing: Routing to Another LAN

A sends a datagram (using IP addresses) to B, traversing through a router (R).
The process involves encapsulating the IP datagram into a link-layer frame with R’s MAC address as the destination.

Addressing: Routing to Another LAN (Continued)

A's frame is received at R, with the IP datagram extracted and processed by the IP layer.
R forwards the datagram in a new frame with B's MAC address as the destination.

Ethernet

Ethernet is a dominant wired LAN technology.
It's inexpensive and widely adopted.
Its simple MAC protocol and frame formats are designed to allow transmission and processing at high speeds, from 10 Mbps up to 10 Gbps.

Ethernet Physical Topology

Ethernet topology has evolved over time from "bus" structures (coaxial cable-based) to the more prevalent "star" topology (using switches) that isolates collision domains.

Ethernet Frame Structure

The Ethernet frame structure includes a preamble, destination and source addresses, type field, and data (payload) and a CRC (Cyclic Redundancy Check).

Ethernet Frame Structure (More)

The preamble synchronizes sender and receiver clock rates.
The type field identifies the higher-layer protocol.
The CRC field allows for error detection.

Ethernet: Unreliable, Connectionless

Ethernet is considered unreliable, and connectionless because it operates without prior communication between sender and receiver NICs.
Receiving NICs do not provide acknowledgment (ack) or negative acknowledgment (nack).
Recovering data in dropped frames requires higher-layer protocols to manage error handling (e.g., TCP).

802.3 Ethernet Standards

802.3 defines various Ethernet standards including speed and supporting physical medium types (cable, fiber optic).

Ethernet Switch

An Ethernet switch is a link-layer device taking an active role in forwarding frames.
Frames are examined.
If destination is known, the frame is forwarded to the relevant port and protocol is used to access the relevant segment.
If not known, a flood mechanism is employed across all other segment ports.
Switches are transparent to hosts and use self-learning mechanisms.

Switch: Multiple Simultaneous Transmissions

Hosts connect directly to a switch (rather than a shared bus).
Each connection to a switch operates in full-duplex mode, permitting simultaneous transmission from various sources to the switch, without collisions.

Switch Forwarding Table

Switches maintain forwarding tables to determine the appropriate outgoing port for a frame based on the destination MAC address.
Entries in the table record MAC addresses, interfaces for reach, and time stamps.

Switch: Self-Learning

Switches "learn" host locations to send frames selectively.
Frame reception triggers the recording of sender information in a table, for use in future forwarding.

Switch: Frame Filtering/Forwarding

Switch logic for receiving, recording, and forwarding or discarding frames based on whether destination is found on the same segment (or not), or whether the MAC address for destination is found in the switch table.

Self-Learning, Forwarding: Example

Frames destined to unknown locations are flooded to other ports; known locations are sent selectively.

Interconnecting Switches

Switches can be interconnected via additional switches (R1 to R4 to R6 connection example), with forwarding table entries based on sender’s location.

Data Center Networks

Data centers house thousands of hosts/servers.
Applications, such as e-commerce or cloud computing, reside in data centers.
Challenges involve balancing load, avoiding processing/networking bottlenecks, and ensuring reliability.

Data Center Networks: Load Balancer

Load balancers distribute incoming client requests to multiple servers within the data center.
They hide internal data center structures/operations from clients.

Data Center Networks: Interconnections

Rich interconnections between switches and racks/servers enable greater throughput and reliability.

Summary of Link Layer Protocols

The summary reviews data link layer services by time/frequency/code division by random access, taking turns (polling/token passing) approaches.

Synthesis: A Day in the Life of a Web Request

This section details a web request scenario, from the initial browser request/operation to the final display of the requested web page.
This involves application layer services/operations, transport, network, and link layers.

A Day in the Life: Scenario

The scenario details the flow of a web request from a browser to retrieving/displaying a webpage on a laptop through campus network routing.

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

DHCP dynamically assigns IP addresses, router, and DNS server addresses to the client.

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

Before sending HTTP requests, the client requires IP addresses using a DNS query for www.google.com, with further encapsulation into UDP, IP, and Ethernet protocols.
ARP queries broadcast on a LAN to locate the MAC address corresponding to the router interface, enabling replies containing router information.

A Day in the Life... Using DNS

IP datagram containing DNS query forwarded via campus LAN switch to first hop router/server.
The datagram is forwarded from the campus to the Comcast network and is routed up to the DNS server for processing and reply to client’s request.

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

HTTP requests are embedded within a TCP connection, with initial TCP SYN segment, 3-way handshake, and TCP reply containing the requested web page.

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

HTTP request encapsulated into TCP socket routed to web server (on Google's network); web server constructs and sends back HTTP replies (containing website pages) that are routed from servers back to client’s device.

Chapter 5: Summary

The summary highlights the various aspects of the Data Link Layer, which covers error detection/correction, channel sharing (using broadcast methods), link layer addressing.
Included are the various technologies including Ethernet, Switched LANs, VLANs, and virtualized networks.

Chapter 5: Let's Take a Breath

This section presents interesting topics for further study.
Topics include wireless functionality, multimedia, security, and network management.

Studying That Suits You

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

Description

This quiz explores various error detection codes and methods used in computer networking, such as checksums and cyclic redundancy checks. Test your knowledge on how these systems work to ensure data integrity over communication channels.