Computer Networking Chapter 5 The Link Layer: Links, Access Network

terminology:

  • hosts and routers: nodes
  • communication channels that connect adjacent nodes along communication path: links
    • wired links
    • wireless links
    • LANs
  • layer-2 packet: frame, encapsulates datagram ### 5.1.1 The Services Provided by the Link Layer

  • framing
    • encapsulate datagram into frame, adding header, trailer
  • Link access
    • channel access if shared medium
    • "MAC" addresses used in frame header to identify source, dest
      • different from IP address
  • Reliable delivery
    • seldom used on low bit-error link (fiber, some twisted pair)
    • wireless links: high error rates
  • Error detection and corrections
    • errors caused by signal attenuation, noise
    • receiver detects presence of errors
      • signals sender for retransmission or drops frame
    • receiver identifies and corrects bit error(s) without resorting to retransmission
  • in each and every host
  • link layer implemented in "adaptor" (aka network interface card NIC) or on a chip
    • Ethernet card, 802.11 card; Ethernet chipset
    • implements link, physical layer
  • attaches into host's system buses
  • combination of hardware, software, firmware

5.2 Error-Detection and -Correct0ion Techniques

  • terminology:
  • EDC: Error Detection and Correction bits (redundancy)
  • D: Data protected by error checking, may include header fields
  • Error detection not 100% reliable
    • larger EDC field yields better detection and correction
    • protocol may miss some errors, but rarely
Figure 5.1 Error-detection and -correction scenario
Figure 5.1 Error-detection and -correction scenario

5.2.1 Parity Checks

  • Even parity scheme
    • one additional bit
    • total number of 1s in the d + 1 bits (the original information plus a parity bit) is even
  • Odd parity scheme
    • one additional bit
    • total number of 1s in the d + 1 bits (the original information plus a parity bit) is odd

5.2.2 Checksumming Methods

  • sender
    • treat segment contents as sequence of 16-bit integers
    • checksum: addition of segment contents
    • sender puts checksum value into UDP checksum field
  • receiver
    • compute checksum of received segment
    • check if computed checksum equals checksum field value:
      • NO - error detected
      • YES - no error detected

5.2.3 Cyclic Redundancy Check (CRC)

  • more powerful error-detection coding
  • view data bits, D, as a binary number
  • choose r+1 bit pattern (generator), G
  • goal: choose r CRC bits, R, such that
    • <D, R> exactly divisible by G (modulo 2, XOR)
    • receiver knows G, divides <D, R> by G. If non-zero remainder: error detected
    • can detect all burst errors less than r+1 bits
  • widely used in practice (Ethernet, 802.11 WiFi, ATM)
Figure 5.2 CRC
Figure 5.2 CRC
  • channel partitioning
    • divide channel into smaller "pieces" (time slots, frequency, code)
    • allocate piece to node for exclusive use
  • random access
    • channel not divided, allow collisions
    • "recover" from collisions
  • "taking turns"
    • nodes take turns, but nodes with more to send can take longer turns

5.3.1 Channel Partitioning Protocols

  • TDMA (time division multiple access)
    • access to channel in "round"
    • each station gets fixed length slot (length = pkt trans time) in each round
    • unused slots go idle
  • FDMA (frequency division multiple access)
    • channel spectrum divided into frequency bands
    • each station assigned fixed frequency band
    • unused transmission time in frequency bands go idle
  • CDMA (code division multiple access)
    • different code to each node
    • Chapter 6

5.3.2 Random Access Protocols

  • when node has packet to send
    • transmit at full channel data rate R.
    • no a a priori coordination among nodes
  • two or more transmitting nodes -> collision
  • random access MAC protocol specifies:
    • how to detect collisions
    • how to recover from collisions

Slotted ALOHA

  • assumptions:
    • all frames same size (L bits)
    • time divided into equal size slot (time to transmit 1 frame)
    • nodes start to transmit only slot beginning
    • nodes are synchronized
    • if 2 or more nodes transmit in slot, all nodes detect collision
  • operation
    • when node obtains fresh frame, transmit in next slot
    • if no collision: node can send new frame in next slot
    • if collision: node retransmits frame in each subsequent slot with prob. p until success
Figure 5.3 Nodes 1,2, and 3 collide in the first slot. Node 2 finally succeeds in the fourth slot, node 1 in the eighth slot, and node 3 in the ninth slot
Figure 5.3 Nodes 1,2, and 3 collide in the first slot. Node 2 finally succeeds in the fourth slot, node 1 in the eighth slot, and node 3 in the ninth slot
  • Pros
    • single active node can continuously transmit at full rate of channel
    • highly decentralized: only slot in nodes need to be in sync
    • simple
  • Cons
    • collisions, wasting slots
    • idle slots
    • nodes may be able to detect collision in less than time to transmit packet
    • clock synchronization
  • Efficiency
    • suppose: N nodes with many frames to send, each transmits in slot with probability p
    • prob that given node has success in a slot = \(p(1-p)^{N-1}\)
    • prob that any code has a success = \(Np(1-p)^{N-1}\)
    • max efficiency: find p* that maximizes \(Np(1-p)^{N-1}\)
    • for many nodes, take limit of \(Np^*(1-p^*)^{N-1}\) as N goes to infinity, gives: max efficiency = 1/e = 0.37
    • at best: channel used for useful transmissions 37% of time

ALOHA

  • unslotted ALOHA: simple, no synchgronizatrion
  • when frame first arrives
    • transmit immediately
  • collision probability increases:
    • frame sent at t0 collides with other frame sent in [t0-1, t0+1]
Figure 5.4 Interfering transmissions in pure ALOHA
Figure 5.4 Interfering transmissions in pure ALOHA
  • efficiency

    \[\begin{aligned}P(success \ by \ given \ node) &= P(node \ transmit) \cdot P(no \ other \ node \ tramsmits \ in \ [t_0-1,t_0])^2 \\ &=p \cdot (1-p)^{2(N-1)} \\ &\dots choosing \ optimum \ p \ and \ then \ letting \ n \rightarrow \infin \\ &= 1/(2e) \\ &=0.18 \end{aligned}\]

Carrier Sense Multiple Access (CSMA)

  • listen before transmit
    • if channel sensed idle: transmit entire frame
    • if channel sensed busy, defer transmission
  • collisions can still occur
    • propagation delay means two nodes may not hear each other's transmission
  • collision: entire packet transmission time wasted
    • distance & propagation delay play role in determining collision probability

Carrier Sense Multiple Access with Collision Detection (CSMA/CD)

  • CSMA: carrier sensing, deferral as in CSMA
    • collisions detected within short time
    • colliding transmissions aborted, reducing channel wastage
  • collision detection:
    • easy in wired LANs: measure signal strengths, compare transmitted, received signals
    • difficult in wireless LANs: received signal strength over whelmed by local transmission strength
  • algorithm:
    1. NIC receives datagram from network layer, creates frame
    2. if NIC senses channel idle, starts frame transmission. if NIC senses channel busy, waits until channel idle, then transmit
    3. if NIC transmits entire frame without detecting another transmission, NIC is done with frame
    4. if NIC detects another transmission while transmitting, aborts and sends jam signal
    5. After aborting, NIC enters binary (exponential backoff):
      • after mth collision, NIC choose K at random from {0, 1, 2, ..., 2m-1}. NIC waits K*512 bit times, returns to Step 2
      • longer backoff interval with more collisions
  • efficiency:
    • Tprop = max prop delay between 2 nodes in a LAN
    • Ttrans = time to transmit max-size frame
    • \(efficiency=\frac1{1+5t_{prop}/t_{trans}}\)
    • efficiency goes to 1
      • as tprop goes to 0
      • as ttrans goes to infinity
    • better performance than ALOHA: and simple, cheap, decentralized

5.3.3 Taking-Turns Protocols

polling protocol

  • master node "invites" slave nodes to transmit in turn
  • typically used with "dumb" slave devices
  • concerns:
    • polling overhead
    • latency
    • single point of failure

token-passing protocol

  • control token passed from one node to next sequentially
  • token message
  • concerns:
    • token overhead
    • latency
    • single point of failure
Figure 5.5 Upstream and downstream channels between CMTS and cable modems
Figure 5.5 Upstream and downstream channels between CMTS and cable modems
  • multiple 40Mbps downstream (broadcast channels)
    • single CMTS transmits into channels
  • multiple 30Mbps upstream channels
    • multiple access: all users contend for certain upstream channel time slots (other assigned)

DOCSIS: data over cable service interface spec

  • FDM over upstream, downstream frequency channels
  • TDM upstream: some slots assigned, some have contention
    • downstream MAP frame: assigned upstream slots
    • request for upstream slots (and data) transmitted random access (binary backoff) in selected slots

5.4 Switched Local Area Networks

MAC Addresses

MAC (or LAN or physical or Ethernet) address:

  • function: used 'locally' to get frame from one interface to another physically-connected interface (same network, in IP addressing sense)
  • 48 bit MAC address (for most LANs) burned in NIC ROM, also sometimes software settable
  • MAC address allocation administered by IEEE
  • manufacturer buys portion of MAC address space (to assure uniqueness)

Address Resolution Protocol (ARP)

  • ARP table: each IP node on LAN has table
    • IP/MAC address mappings for some LAN nodes: <IP address; MAC address; TTL>
    • TTL (Time To Live): time after which address mapping will be forgotten (typically 20 min)
  • same LAN
    1. A wants to send datagram to B
      • B's MAC address not in A's ARP table.
    2. A broadcasts ARP query packet, containing B's IP address
      • dest MAC address = FF-FF-FF-FF-FF-FF
      • all nodes on LAN receive ARP query
    3. B receives ARP packet, replies to A with its (B's) MAC address
      • frame sent to A’s MAC address (unicast)
    4. A caches (saves) IP-to-MAC address pair in its ARP table until information becomes old (times out)
      • soft state: information that times out (goes away) unless refreshed

Sending a Datagram off the Subnet

Figure 5.6 routing to another LAN
Figure 5.6 routing to another LAN

sending datagram from A to B via R

  • frame sent from A to R
  • frame received at R, datagram removed, passed up to IP
  • R forwards datagram with IP source A, destination B
  • R creates link-layer frame with B's MAC address as dest, frame contains A-to-B datagram

5.4.2 Ethernet

Ethernet Frame Structure

sending adapter encapsulates IP datagram (or other network layer protocol packet) in Ethernet frame

Figure 5.7 Ethernet frame structure
Figure 5.7 Ethernet frame structure
  • preamble
    • 7 bytes with pattern 10101010 followed by one byte with pattern 10101011
    • used to synchronize receiver, sender clock rates
  • addresses: 6 byte source, destination MAC addresses
    • if adapter receives frame with matching destination address, or with broadcast address, it passes data in frame to network layer protocol
    • otherwise, adaptor discards frame
  • type: indicates higher layer protocol (mostly IP but others possible)
  • CRC: cyclic redundancy check at receiver
    • error detected: frame is dropped

Ethernet: unreliable, connectionless

  • connectionless: no handshaking between sending and receiving NICs
  • unreliable: receiving NIC doesn't send acks or nacks to sending NIC
    • data in dropped frames recovered only if initial sender uses higher layer rdt, otherwise dropped data lost
  • Ethernet's MAC protocol: unslotted CSMA/CD with binary backoff
  • linker-layer device: takes an active role
    • store, forward Ethernet frames
    • examine incoming frame's MAC address, selectively forward frame to one-or-more outgoing links 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

Forwarding and Filtering

  • filter: whether a frame should be forwarded to some interface or been dropped
  • forward: which interfaces a frame should be directed to
  • in a switch table
Figure 5.8 Portion of a switch table for the uppermost switch
Figure 5.8 Portion of a switch table for the uppermost switch
  • three possible cases that frame from interface x:
    • no entry in the table for dest's MAC: the switch broadcast the frame
    • an entry in the table associating dest's MAC with interface x: drop it
    • an entry in the table associating dest's MAC with interface y≠x: forward it to the LAN segment attached to interface

Self-Learning

  • switch learns which hosts can be reached through which interfaces
    • when frame received, switch "learns" location of sender: incoming LAN segment
    • records sender / location pair in switch table
  • when frame received at switch:
    1. initial empty table
    2. record incoming link, MAC address of sending host, arrival time
    3. after aging time, delete an address if no frames are received with that address
  • plug and play
  • Elimination of collisions
  • Heterogeneous links
  • Management

Switches Versus Routers

  • both are store-and-forward
    • routers: network-layer devices (examine network-layer header)
    • switches: link-layer devices (examine link-layer headers)
  • both have forwarding tables
    • routers: compute tables using routing algorithms, IP addresses
    • switches: learn forwarding table using flooding learning, MAC addresses

5.4.4 Virtual Local Area Networks (VLANs)

switch(es) supporting VLAN capabilities can be configured to define multiple virtual LANs over single physical LAN infrastructure

port-based VLAN:

  • switch ports grouped
  • single physical switch operates as multiple virtual switches
  • traffic isolation: frames to/from ports 1-8 can only reach ports 1-8
    • can also define VLAN based on MAC addresses of endpoints, rather than switch port
  • dynamic membership: ports can be dynamically assigned among VLANs
  • forwarding between VLANs: done via routing (just as with separate switches)
    • in practice vendors sell combined switches plus routers
  • trunk port: carries frame between VLANs defined over multiple physical switches
    • frames forwarded within VLAN between switches can't be vanilla 802.1 frames (must carry VLAN ID info)
    • 802.1 q protocol adds/removed additional header fields for frames forwarded between trunk ports
Figure 5.9 Original Ethernet frame (top), 802.1 Q-tagged Ethernet VLAN frame (below)
Figure 5.9 Original Ethernet frame (top), 802.1 Q-tagged Ethernet VLAN frame (below)

5.5.1 Multiprotocol Label Switching (MPLS)

  • initial goal: high-speed IP forwarding using fixed length label (instead of IP address)
    • fast lookup using fixed length identifier (rather than shortest prefix matching)
    • borrowing ideas from Virtual Circuit (VC) approach
    • but IP datagram still keeps IP address
Figure 5.10 MPLS header: Located between link- and network-layer headers
Figure 5.10 MPLS header: Located between link- and network-layer headers
  • MPLS capable routers
    • a.k.a label-switched router
    • forward packets to outgoing interface based only on label value (don't inspect IP address)
      • MPLS forwarding table distinct from IP forwarding tables
    • flexibility: MPLS forwarding decisions can differ from those of IP
      • use destination and source addresses to route flows to same destination differently (traffic engineering)
      • re-route flows quickly if link fails: pre-computed backup paths (useful for VoIP)

5.6 Data Center Networking

  • 10's and 100's of thousands of hosts, often closely coupled, in close proximity:
    • e-business
    • content-servers
    • search engines, data mining
  • challenges:
    • multiple applications, each serving massive numbers of clients
    • managing / balancing load, avoiding processing, networking, data bottlenecks

Local Balancing

  • receives external client requests
  • directs workload within data center
  • returns results to external client (hiding data center internals from client)

Hierarchical Architecture

Figure 5.11 A data center network with a hierarchical topology
Figure 5.11 A data center network with a hierarchical topology
  • fully connected topology
    • host-to-host traffic never has to rise above the switch tiers
    • with n tier-1 switches, between any two tier-2 switches there are n disjoint paths
  • modular data center

5.7 Retrospective: A Day in the Life of a Web Page Request

Figure 5.12 A day in the life of a Web page request: network setting and actions
Figure 5.12 A day in the life of a Web page request: network setting and actions

5.7.1 Getting Started: DHCP, UDP, IP, and Ethernet

  1. connecting laptop needs to get its own IP address, addr of first-hop router, addr of DNS server: use DHCP
  2. DHCP request encapsulated in UDP, encapsulated in IP, encapsulated in 802.3 Ethernet
  3. Ethernet frame broadcast (dest: FFFFFFFFFFFF) on LAN, received at router running DHCP server
  4. Ethernet demuxed to IP demuxed, UDP demuxed to DHCP
  5. DHCP server formulates DHCP ACK containing client's IP address, IP address of first-hop router for client, name & IP address of DNS server
  6. encapsulation at DHCP server, frame forwarded (switch learning) through LAN, demultiplexing at client
  7. DHCP client receives DHCP ACK reply

5.7.2 Still Getting Started: DNS and ARP

  1. before sending HTTP request, need IP address of www.google.com: DNS
  2. DNS query created, encapsulated in UDP, encapsulated in IP, encapsulated in Eth. To send frame to router, need MAC address of router interface: ARP
  3. ARP query broadcast received by router, which replies with ARP reply giving MAC address of router interface
  4. client now knows MAC address of first hop router, so can now send frame containing DNS query

5.7.3 Still Getting Started: Intra-Domain Routing to the DNS Server

  1. IP datagram containing DNS query forwarded via LAN switch from client to 1st hop router
  2. IP datagram forwarded from campus network into comcast network, routed (tables created by RIP, OSPF, IS-IS and/or BGP routing protocols) to DNS server
  3. demux'ed to DNS server
  4. DNS server replies to client with IP address of www.google.com

5.7.4 Web Client-Server Interaction: TCP and HTTP

  1. to send HTTP request, client first opens TCP socket to web server
  2. TCP SYN segment (step 1 in 3-way handshake) inter-domain routed to web server
  3. web server responds with TCP SYNACK (step 2 in 3-way handshake)
  4. TCP connection established
  5. HTTP request sent into TCP socket
  6. IP datagram containing HTTP request routed to www.google.com
  7. web server responds with HTTP reply (containing web page)
  8. IP datagram containing HTTP reply routed back to client

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×