Slotted ALOHA Protocol Quiz

Chapter 5: Link Layer

• PowerPoint slides are freely available to faculty, students, and readers
• Slides can be modified and content changed to meet needs
• If used in class, the source must be mentioned
• If posted online, the adapted/identical nature and copyright must be noted

Chapter 5: Link Layer Goals

• Understand principles behind link layer services
• Error detection and correction
• Sharing a broadcast channel (multiple access)
• Link layer addressing
• Local area networks (Ethernet, VLANs)
• Instantiation and implementation of various link layer technologies

Link layer, LANs: outline

• Introduction, services
• Error detection, correction
• Multiple access protocols
• LANs (addressing, ARP, Ethernet, switches, VLANs)
• Link virtualization: MPLS
• Data center networking
• A day in the life of a web request

Link Layer: Introduction

• Hosts and routers are nodes
• Communication channels connect adjacent nodes along the communication path (links).
• Links include wired links, wireless links, and LANs
• Layer-2 packet: frame, encapsulates datagram
• Data-link layer is responsible for transferring datagram from one node to a physically adjacent node over a link

Link Layer: Context

• Different link protocols transfer datagram over different links (e.g., Ethernet on the first link and frame relay on intermediate links)
• Each link protocol provides different services (e.g., may or may not provide reliable data transfer (RDT) over link)

Link Layer Services

• Framing and link access: Encapsulating datagram into frame, adding header and trailer
• Channel access if shared medium
• MAC addresses for identifying source and destination, different from IP addresses
• Reliable delivery between adjacent nodes (described in Chapter 3) is seldom used for low-error links (e.g., fiber or some twisted pair)
• Wireless links experience high error rates
• Why both link level and end-end reliability?

Link Layer Services (more)

• Flow control: pacing between adjacent sending and receiving nodes
• Error detection: errors caused by signal attenuation or noise; receiver detects errors, signals sender for retransmission or drops frames
• Error correction: receiver identifies and corrects bit errors without retransmission
• Half-duplex and full-duplex: with half-duplex, nodes at both ends of a link can transmit but not at the same time.

Where is the Link Layer Implemented?

• Implemented in each host network adapter (NIC) or chip
• Ethernet card, 802.11 card; Ethernet chipset implements link and physical layers
• Attaches to host system buses
• Combination of hardware, software, and firmware

Adaptors Communicating

• Sending side: encapsulates datagram in frame, adds error checking bits, RDT, and flow control.
• Receiving side: looks for errors, performs RDT, flow control, and extracts datagram to upper layer.

Error Detection

• EDC (Error Detection and Correction) bits provide redundancy
• Data is protected by error checking.
• Protocols may miss some errors, but rarely, and larger EDC fields provide better detection and correction.

Parity Checking

• Single bit parity: detects single bit errors
• Two-dimensional bit parity: detects and corrects single bit errors

Internet Checksum (review)

• Goal: detect errors (e.g., flipped bits) in transmitted packets (used at transport layer only)
• Sender: treats segment contents as sequence of 16-bit integers, calculates checksum (addition's one's complement sum) of segments, puts checksum value in UDP checksum field.
• Receiver: computes checksum of received segment, checks if computed checksum equals checksum field value (NO=error detected).

Cyclic Redundancy Check

• More powerful error-detection coding
• Uses data bits (D) and CRC bits (R)
• Goal: ensure <D, R> is exactly divisible by G (modulo 2)
• Widely used (Ethernet, 802.11, WiFi, ATM)
• Can detect all burst errors with length less than r+1 bits
• D*2^r XOR R = nG

CRC Example

• Calculation of remainder (R) when dividing D^2^r by G

Multiple Access Links, Protocols

• Point-to-point: PPP for dial-up, point-to-point link between Ethernet switch and host
• Broadcast: old-fashioned Ethernet, upstream HFC, 802.11 wireless LAN
• Shared wire (e.g., wired Ethernet)
• Shared RF (e.g., 802.11 WiFi)
• Shared RF (satellite)
• Human(s) at a cocktail party

Multiple Access Protocols

• Single shared broadcast channel, two or more simultaneous transmissions by nodes.
• Interference and collisions (if a node receives two or more signals at the same time).
• Distributed algorithm determines how nodes share the channel; determines when a node can transmit
• Communication must use the channel itself (no out-of-band channel for coordination)

An Ideal Multiple Access Protocol

• A broadcast channel with rate (R bps)
• If one node wants to transmit, it can send at rate R, and when M nodes want to transmit, rate R/M.
• Fully decentralized, no special node or synchronization of clocks or slots, and simple
• MAC protocols: channel partitioning, random access, taking turns

MAC Protocols: Taxonomy

• Three broad classes: channel partitioning, divide channel into smaller pieces and allocate each piece to node for exclusive use
• Random access: channels not divided; allow collisions & "recover" from them
• Taking turns: nodes take turns, but those with more to send take longer turns

Channel Partitioning MAC Protocols: TDMA

• TDMA (time division multiple access)
• Access to channel in "rounds"
• Each station gets a fixed length slot in each round.
• Unused slots are idle.
• Example: 6-station LAN with 1, 3, and 4 having packets, slots 2, 5, and 6 are idle

Channel Partitioning MAC Protocols: FDMA

• FDMA (frequency division multiple access)
• Channel spectrum divided into frequency bands
• Each station is assigned a fixed frequency.
• Unused transmission time in frequency bands goes idle.

Random Access Protocols

• When a node has a packet to send, it transmits at full channel data rate.
• Two or more transmitting nodes generate collisions
• Random access MAC protocol specifies how to detect and recover from collisions (e.g., via delayed retransmission).
• Examples: slotted ALOHA, ALOHA, CSMA, CSMA/CD, CSMA/CA

Slotted ALOHA

• Assumptions: all frames same size, time divided into equal size slots. Nodes start transmitting only at beginning of slot, nodes synchronized.
• Operation: when a node obtains a fresh frame, it transmits in the next slot. If no collision, node can send a new frame in the next slot. If a collision occurs, the node retransmits the frame in each subsequent slot with a probability (p) until success.

Slotted ALOHA: Efficiency

• Long-run fraction of successful slots, given many nodes each with many frames to send.
• Probability of success = Np(1-p)^N-1 (N nodes, probability p for transmission in a slot)

Pure (Unslotted) ALOHA:

• Simpler than slotted ALOHA, no synchronization
• Transmits immediately when a frame arrives
• Collision probability increases when multiple frames sent in same time slot

Pure ALOHA Efficiency

• Probability of success, given other nodes don't transmit in the frame's time slot.
• Using optimum (p) and larger (n) generates even worse efficiency than slotted ALOHA

CSMA (Carrier Sense Multiple Access)

• Listen before transmit
• If channel sensed idle, transmit entire frame.
• If channel sensed busy, defer transmission
• Human analogy: don't interrupt others.

CSMA Collisions

• Collisions can occur due to propagation delay.
• Two nodes may not hear each other's transmissions.
• Collision means entire packet transmission time is wasted.
• Distance and propagation delay determine the probability of collision

CSMA/CD (Collision Detection)

• Carrier sensing, deferral, and collision detection within a short time.
• Colliding transmissions aborted, reducing channel wastage
• Easy in wired LANs (measure signal strengths).
• Difficult in wireless LANs (received signal strength overwhelmed by local transmission strength)
• Human analogy: being a polite conversationalist

Ethernet CSMA/CD Algorithm

• NIC receives datagram from network layer; creates frame.
• If NIC senses channel idle, starts frame transmission. If busy, waits until idle.
• If NIC transmits entire frame without detecting another transmission, it completes.
• If any collision occurs during transmission, the NIC sends a jam signal and enters into binary exponential back-off.

CSMA /CD Efficiency

• Efficiency = 1 / (1 + 5 * Tprop/ Ttrans), where Tprop = maximum propagation delay between two nodes and Ttrans = time to transmit.
• Efficiency tends toward 1 as Ttrans goes to infinity, and toward 0 as Tprop approaches 0.

“Taking Turns” MAC Protocols

• Channel partitioning MAC: efficient at high load, but inefficient at low load. Delay in channel access when only one or few active nodes.
• Random access MAC: efficient at low load, but has collision overhead at high load.
• Taking turns protocols look for a balance of both world

Polling

• Master node invites slave nodes to transmit in turn.
• Typically used with "dumb" slave devices, but problems include polling overhead, latency, and single point of failure.

Token Passing

• Control token passed from one node to the next sequentially.
• Concerns: token overhead, latency, and potential single point of failure

Cable Access Network

• Internet frames, TV channels, and control transmitted downstream.
• Multiple downstream (broadcast) channels using a single CMTS (Cable Modem Termination System).
• Multiple upstream channels for users to contend for certain upstream channel time slots.
• DOCSIS (data over cable service interface specification) uses FDM over upstream and downstream channels. TDM upstream: assigned and contention; MAP frame assigns upstream slots, and request for up/down stream slots are made and transmitted in random access (binary backoff) in selected slots.

Ethernet Switch

• Link-layer device, takes an active role
• Stores and forwards Ethernet frames
• Examines incoming frame MAC addresses and selectively forwards to one or more outgoing links.
• Uses CSMA/CD to access the segment
• Transparent: hosts unaware of switches.
• Plug-and-play, self-learning; switches don't need configuration.

Switch: Multiple Simultaneous Transmissions

• Hosts have dedicated direct connections to switches
• Switches buffer packets
• Ethernet protocol used on each incoming link; no collisions
• Each link is its own collision domain
• Switching: A-to-A' and B-to-B' can transmit simultaneously without collisions

Switch Forwarding Table

• How switch knows A' reachable via interface 4, B' via 5.
• Each switch has a table. Each entry includes MAC address of host, interface to reach host, and time stamp, which makes it look like a routing table.

Switch: Self-Learning

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

Switch: Frame Filtering/Forwarding

• Records incoming link and MAC address of sending host.
• Indexes the switch table using the destination MAC address, and checks if an entry is found.
• If the destination is on the segment, the frame is dropped; otherwise, the frame is forwarded. The algorithm floods the frame on all interfaces except the one it arrived on.

Self-learning, Forwarding: Example

• Frame destination unknown; flood.
• Destination A location known; selectively send the frame on just one link.

Interconnecting Switches

• Switches can be interconnected.
• Self-learning mechanism works exactly the same as in the single-switch case.

Virtual LANs (VLANs)

• Motivation: CS user moves office to EE but wants access to CS switch.
• Single broadcast domain: all layer-2 broadcast traffic (ARP, DHCP, unknown destination MAC addresses) must cross entire LAN. Security/ privacy issues, and efficiency issues.

Port-Based VLAN

• Switch ports grouped (by management software).
• Single physical switch operates as multiple virtual switches.

Port-based VLAN (cont.)

• Traffic isolation: frames to/from ports 1-8 reach only ports 1-8.
• Dynamic membership: ports can be dynamically assigned to different VLANs.

VLANs Spanning Multiple Switches

• Trunk ports: carry frames between defined VLANs over multiple switches.
• Frames forwarded within VLANs between switches can use a vanilla 802.1 protocol. It adds/removes additional header fields for frames that are forwarded between trunk ports.

802.1Q VLAN Frame Format

• 2-byte Tag Protocol Identifier (value: 81-00)
• Tag Control Information (12-bit VLAN ID, 3-bit priority field).

Data Center Networks

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

Data Center Networks (load balancer)

• Load balancer receives external client requests, directs workload within the data center, and returns results to external clients (hiding data center internals).

Data Center Networks (Rich Interconnection)

• Rich interconnection among switches and racks result in increased throughput and reliability via redundancy.

Synthesis: A Day in the Life of a Web Request

• Journey down the protocol stack (application, transport, network, link layer).
• Putting-it-all-together: understanding protocols involved in seemingly simple scenarios.
• Scenarios like a student requesting www.google.com from their laptop connected to a campus network.

A Day in the Life… Scenario

• A diagram visualizing the process, including parts of the school network, Comcast network, the DNS server, and Google's network.

A Day in the Life… Connecting to the Internet

• DHCP assigns IP address, router address, and DNS server address.
• DHCP request encapsulated in UDP; encapsulated in IP, and encapsulated in 802.3 (Ethernet)
• Ethernet frame broadcast on LAN, received by DHCP server.

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

• Before sending HTTP request that requires IP address of www.google.com, a DNS query must be made.
• DNS query is encapsulated in UDP, encapsulated in IP, encapsulation into Eth. To send a frame to a router, the MAC address of the router interface is necessary (ARP).
• ARP query is broadcasted to the network.
• Router replies with an ARP reply containing the MAC address of the router interface.

A Day in the Life… Using DNS

• IP datagram that contains a DNS query is forwarded via LAN switch to the first-hop router.
• IP datagram forwarded from campus network into Comcast network
• Routed via RIP, OSPF, IS-IS or BGP routing protocols to DNS server
• Demuxed and responded to with IP address of www.google.com.

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

• Client initially opens TCP socket to web server to send HTTP request.
• TCP SYN segment is sent to web server, inter-domain routed.
• Web server responds with SYNACK segment in the 3-way handshake
• TCP connection established once the handshake is complete

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

• HTTP request sent to TCP socket, IP datagram containing HTTP request routed to web server at www.google.com
• Web server responds with HTTP reply. The reply, including the web page, is contained within the IP datagram and routed back to client.

Chapter 5 Summary

• Principles behind data link layers and their services, error detection, correction, sharing broadcast channels, and link-layer addressing.
• Installation and implementation of various link layer technologies (Ethernet, switched LANs, VLANs)
• Virtualized networks (MPLS)
• Synthesis: a day in the life of a web request.
• Summary of additional topics about the concepts in the lesson.

Chapter 5: Let's take a breath!

• Journey down protocol stack is complete (except PHY).
• Solid understanding of networking principles and practice.
• Potentially stopping here, but introducing topics like wireless, multimedia, security, network management.