Read "Streaming Systems" 1&2, Streaming 101 Read "F1, a distributed SQL database that scales" Read "Zanzibar, Google’s Consistent, Global Authorization System" Read "Spanner, Google's Globally-Distributed Database" Read "Designing Data-intensive applications" 12, The Future of Data Systems IOS development with Swift Read "Designing Data-intensive applications" 10&11, Batch and Stream Processing Read "Designing Data-intensive applications" 9, Consistency and Consensus Read "Designing Data-intensive applications" 8, Distributed System Troubles Read "Designing Data-intensive applications" 7, Transactions Read "Designing Data-intensive applications" 6, Partitioning Read "Designing Data-intensive applications" 5, Replication Read "Designing Data-intensive applications" 3&4, Storage, Retrieval, Encoding Read "Designing Data-intensive applications" 1&2, Foundation of Data Systems Three cases of binary search TAMU Operating System 2 Memory Management TAMU Operating System 1 Introduction Overview in cloud computing 2 TAMU Operating System 7 Virtualization TAMU Operating System 6 File System TAMU Operating System 5 I/O and Disk Management TAMU Operating System 4 Synchronization TAMU Operating System 3 Concurrency and Threading TAMU Computer Networks 5 Data Link Layer TAMU Computer Networks 4 Network Layer TAMU Computer Networks 3 Transport Layer TAMU Computer Networks 2 Application Layer TAMU Computer Networks 1 Introduction Overview in distributed systems and cloud computing 1 A well-optimized Union-Find implementation, in Java A heap implementation supporting deletion TAMU Advanced Algorithms 3, Maximum Bandwidth Path (Dijkstra, MST, Linear) TAMU Advanced Algorithms 2, B+ tree and Segment Intersection TAMU Advanced Algorithms 1, BST, 2-3 Tree and Heap TAMU AI, Searching problems Factorization Machine and Field-aware Factorization Machine for CTR prediction TAMU Neural Network 10 Information-Theoretic Models TAMU Neural Network 9 Principal Component Analysis TAMU Neural Network 8 Neurodynamics TAMU Neural Network 7 Self-Organizing Maps TAMU Neural Network 6 Deep Learning Overview TAMU Neural Network 5 Radial-Basis Function Networks TAMU Neural Network 4 Multi-Layer Perceptrons TAMU Neural Network 3 Single-Layer Perceptrons Princeton Algorithms P1W6 Hash Tables & Symbol Table Applications Stanford ML 11 Application Example Photo OCR Stanford ML 10 Large Scale Machine Learning Stanford ML 9 Anomaly Detection and Recommender Systems Stanford ML 8 Clustering & Principal Component Analysis Princeton Algorithms P1W5 Balanced Search Trees TAMU Neural Network 2 Learning Processes TAMU Neural Network 1 Introduction Stanford ML 7 Support Vector Machine Stanford ML 6 Evaluate Algorithms Princeton Algorithms P1W4 Priority Queues and Symbol Tables Stanford ML 5 Neural Networks Learning Princeton Algorithms P1W3 Mergesort and Quicksort Stanford ML 4 Neural Networks Basics Princeton Algorithms P1W2 Stack and Queue, Basic Sorts Stanford ML 3 Classification Problems Stanford ML 2 Multivariate Regression and Normal Equation Princeton Algorithms P1W1 Union and Find Stanford ML 1 Introduction and Parameter Learning

TAMU Computer Networks 5 Data Link Layer

2018-04-25

Introduction

Data-link layer has responsibility of transferring IP datagram from one node to adjacent node over a single link.

MAC (Media Access Control) layer = data-link layer = layer 2

  • Hosts and routers are nodes
  • Communication channels that connect adjacent nodes are layer-3 links
  • Each link may contain multiple layer-2 devices (e.g., switches)

Services:

  • Framing
    • Add header, trailer to IP packet
    • Data-link addresses (completely independent of IP addresses) used in frame headers to identify source, dest
  • Link access
    • Channel access if shared medium
  • Flow control
    • Pacing between adjacent sending and receiving nodes
  • Error detection
    • Errors caused by signal attenuation, noise
    • Receiver detects presence of errors and signals data-link layer of adjacent node for retransmission or drops frame
  • Forward Error Correction (FEC)
    • Receiver identifies and corrects bit error(s) without resorting to retransmission
  • Reliable delivery (rdt) between adjacent nodes
    • Rdt 3.0 is a common technique
    • Seldom used on low bit error links (fiber, twisted pair), but may be implemented in wireless networks

Terminology:

  • In half-duplex mode, nodes at both ends of link can transmit, but not at the same time
  • In full-duplex, bidirectional transfer happens concurrently

Multiple access protocols

Two types of links:

  • Point-to-point
    • PPP for dial-up and DSL access
    • Dedicated cable between Ethernet switch and host
  • Broadcast (shared wire/medium)
    • Traditional Ethernet
    • Upstream HFC
    • 802.11 wireless LAN, satellite

For a single shared broadcast channel,

  • Two or more simultaneous transmissions by nodes is called interference or collision
  • Link access protocol
    • Distributed algorithm that determines how nodes share channel
    • Communication about channel sharing must use the channel itself!

MAC Protocols, 3 broad classes:

  • Channel Partitioning
    • Divide channel into smaller “pieces” (time slots, frequency, wavelengths)
    • Allocate piece to node for exclusive use
    • Share channel efficiently and fairly at high load
    • Inefficient at low load: delay in channel access, 1/N bandwidth allocated even if only 1 active node!
  • Random Access
    • Channel not divided, allow collisions
    • Recover from collisions
    • Efficient at low load: single node can fully utilize channel
    • High load: potentially huge collision overhead
  • Taking turns
    • Nodes take turns, but nodes with more to send can take longer turns

Channel Partitioning MAC protocols

  • TDMA, Time Division Multiple Access
    • Access to channel in “rounds” (time frames)
    • Maximum throughput for a single user is R / N
  • FDMA: frequency division multiple access
    • Channel spectrum divided into frequency bands

Random Access Protocols

  • When node has packet to send
    • Transmit at full channel data rate R
  • Two or more transmitting nodes cause collision
  • Random access MAC protocol specifies
    • How to detect collisions
    • How to recover from collisions (e.g., via delayed retransmissions)
  • Examples of random access MAC protocols
    • ALOHA, Slotted ALOHA
    • CSMA, CSMA/CD

Slotted ALOHA

Assumption:

  • All frames same size
  • Time is divided into equal size slots, time to transmit 1 frame
  • Nodes start transmission only at beginning of slots
  • If 2 or more nodes transmit in slot, all nodes detect collision

Operation:

  • When node obtains fresh frame from IP, it transmits in the next time slot
  • No collision, node can send new frame in next slot
  • If collision, node retransmits frame in each subsequent slot with probability p until success

Pros:

  • Single active node can continuously transmit at full rate of channel
  • Reasonably decentralized: only slots need to be in sync
  • Simple

Cons:

  • Collisions
  • Idle/empty slots
  • Full slot wasted on collision
  • Accurate clock synchronization is still a headache

Efficiency is the long-term fraction of successful slots when there are many nodes, each with many frames to send.

  • Optimal p is 1 / N with N nodes
  • Efficiency is 1 / e = 0.37

CSMA, Carrier Sense Multiple Access

  • Remove slots and allow transmission at any time
  • If channel sensed idle, transmit entire frame
  • If channel sensed busy, defer transmission
  • If collision is detected at the end of transfer, wait a random period of time, then retransmit

CSMA/CD, Collision Detection

  • carrier sensing, deferral as in CSMA
  • But now collisions are detected immediately
  • Colliding transmissions aborted, reducing channel waste

Collision detection:

  • Easy in wired LANs: measure signal strengths, compare transmitted, received signals
  • Difficult in wireless LANs: receiver shut off while transmitting

Taking Turns MAC Protocols

  • Polling
    • Master node invites slave nodes to transmit in turn
    • Concerns
      • Polling overhead
      • Latency
      • Single point of failure (master)
  • Token passing
    • Control token passed from one node to next sequentially
    • Can send only if holding token
    • Concerns
      • Token overhead
      • Latency
      • Single point of failure (token)

Network address:

  • Transport layer
    • 16-bit port
    • Find correct application within a host
  • Network layer
    • 32-bit IPv4, 128-bit IPv6
    • Find correct subnet and host on the Internet
  • MAC (or LAN, physical, Ethernet)
    • 48-bit number in the adapter ROM
    • Find correct interface within a subnet

LAN address

  • Each adapter in a LAN must have a unique LAN address
  • Broadcast address = FF-FF-FF-FF-FF-FF
  • MAC address allocation administered by IEEE
  • Manufacturer buys portion of MAC address space
  • Flat MAC addresses achieve portability
  • Hierarchical IP addresses NOT portable

ARP, Address Resolution Protocol:

  • Each IP node (host, router) on LAN has an ARP table
    • Contains IP/MAC address mappings for known LAN nodes
      • <IP address; MAC address; TTL>
      • TTL typically 20 min

For X to send a datagram to Y, X doesn’t know Y’s MAC address

  1. X broadcasts ARP query, containing Y’s IP address
  2. Y receives ARP packet, replies to X with its MAC address (unicast)
  3. X caches IP/MAC mapping in ARP table

For X, in order to send datagram to Y in another LAN. X knows Y’s IP address. The inter router R has two interface, R1 for X, R2 for Y.

  1. X broadcasts ARP with IP_R1, receive R1 MAC
  2. X sends packet to R
    • MAC_X, MAC_R1, IP_X, IP_Y
  3. R changes interface to R2
  4. R2 broadcasts ARP, get Y MAC
  5. R sends packet to Y
    • MAC_R2, MAC_Y, IP_X, IP_Y

DHCP, Dynamic Host Configuration Protocol

  • Assigns IP address, netmask, DNS server, default router, and other parameters to end-hosts
  • UDP (ports 67-68), using MAC-layer broadcasts to find available servers
    • Steps: Discovery –> Offer –> Request –> Lease (4 packets exchanged)
    • Client may receive multiple offers, must choose one
    • Leased IPs carry some TTL (expiration time)
    • Routers and switches may implement DHCP
  • Routers may be configured to forward broadcast DHCP packets between subnets
    • One DHCP server may cover multiple LANs

Ethernet

  • Dominant wired LAN technology
  • Ethernet data rates
    • 10 GE [802.3ae]: 10 Gbps (2003 fiber, 2006 twisted pair)
    • 40/100 GE [IEEE 802.3ba]: 2010

Frame structure:

  • 8-byte preamble (physical layer)
    • 7 bytes 10101010 followed by one byte 10101011
    • synchronizes receiver-sender clock rates
  • 6-byte MAC addresses
    • dest first, then source
  • 2-byte protocol type
    • IPv4(0x800), IPv6(0x86DD), ARP(0x806)
  • 32-bit CRC checksum
  • Minimum payload 46 bytes
  • inter-frame gap 12 bytes

Ethernet CSMA/CD

  • No slots
  • carrier sense (CS)
    • Doesn’t transmit if sensing other is transmitting
  • collision detection (CD)
    • Transmitting adapter aborts when sensing other is transmitting
  • Before attempting a retransmission, adapter waits a random time, that is, random access
  • Connectionless, no handshaking
  • Unreliable, NO ACKs

Bit time is 1/ speed.

Exponential Backoff:

  • Goal: adapt retransmission attempts to estimated load
    • Heavy load: random wait should be longer
  • After m-th collision in a row
    • Choose integer ;
    • then wait bit times before retx

Efficiency:

  • is max propagation delay between any two nodes in LAN
  • is time to transmit frame

Ethernet Technology:

  • Notation: [speed]Base[medium]
  • Examples
    • 10base5 (thick coax 500m), 1000BaseLX (long-range fiber 5km)
  • Now: 10GBaseT over CAT6 (55m), CAT6a (100m)
  • Coax networks were daisy-chained, while copper and fiber run the star topology

Hubs and switches

Hubs

  • Hubs were physical-layer repeaters
    • Bits coming from one link went out all other links
  • No frame buffering
    • No CSMA/CD at hub: host adapters must detect collisions
  • Backbone hubs interconnected other hubs
    • Increased max distance between nodes
  • Additional limitations
    • No management functionality
    • All ports had to be same speed
  • Similar to daisy-chaining, but with all connections in one place

Switches

  • Link layer device
    • Stores and forwards Ethernet frames
    • Examines frame header and selectively forwards frame based on MAC dest address
    • When frame is to be forwarded on segment, uses CSMA/CD to access segment
  • Transparent
    • Hosts are unaware of presence of switches
  • Plug-and-play, self-learning
    • Switches do not need to be configured
  • Modern switches can perform some IP functionality

Functions:

  • A switch has a switch table
    • Entry: (MAC Address, Interface, TTL)
  • Switch learns which hosts can be reached through which interfaces
    • When frame received, switch “learns” location of sender: incoming LAN segment
  • If the entry is not found for destination, flood all but the source interface

Dedicated Access:

  • Dedicated: hosts have direct connection to switch
    • No collisions; full duplex
  • Switching: two unrelated transfers can be simultaneous, no collisions
  • Buffering: two transfers towards the same destination can be simultaneous, no collisions
  • Combinations of shared/dedicated and diverse (10/100/1000 Mbps) interfaces are possible

Reference

This is my class notes while taking CSCE 612 at TAMU. Credit to the instructor Dr. Loguinov.


Creative Commons License
Melon blog is created by melonskin. This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
© 2016-2019. All rights reserved by melonskin. Powered by Jekyll.