The Data Link Layer Flashcards
Link layer: introduction
terminology:
- nodes: hosts and routers
- links: communication channels that connect adjacent nodes along a communication path
* wired links
* wireless links
* LANs
- frame: a layer-2 packet that encapsulates a datagram
data-link layer has responsibility of transferring a datagram from one node to another phy-layer-adjacent node over 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
- e.g., Ethernet on first link, frame relay on
- each link protocol may provide quite different
services- e.g., may or may not provide reliability
transportation analogy:
- trip from Lancaster to Lausanne
* Lancaster to MCR: taxi
* MCR to Geneva: plane
* Geneva to Lausanne: train
- datagram = tourist
- communication link = transport segment
- link-layer protocol = transportation mode
- routing algorithm = travel agent
Link layer sub-layers
logical link control (LLC) sublayer
- abstraction of passing a datagram over a link
- “higher” level mechanisms like flow control, reliability
Link layer sub-layers
medium access control (MAC) sublayer
- interfaces directly with the hardware
- e.g. mediates access to a physical broadcast medium
- MAC addresses are used in frame headers to identify source, destination
Where is the link layer implemented?
- in each and every node!
- in an “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 bus
- combination of hardware, software, firmware
Two main types of “links”
- point-to-point
- PPP for dial-up access
- point-to-point link between Ethernet switch, host
- frame relay
- broadcast (shared wire or medium)
- old-fashioned Ethernet
- 802.11 wireless LAN
- this is our focus…
MAC protocols for broadcast media
Taxonomy: we’ll look at two main classes:
- channel partitioning
- divide channel into smaller “pieces” (time slots, frequency bands)
- allocate a piece to a broadcast link’s channel for exclusive use by a node
- random access
- channel not divided, allow collisions
- … and then “recover” from collisions
Channel partitioning MAC protocols: TDMA
TDMA: time division multiple access
§ access to channel is structured in “rounds” of time
§ each node, or “station”, gets a fixed length slot in each round (slot length = frame transmission time)
§ example: 6-station LAN, 1,3,4 have frames to send, slots 2,5,6 idle
Channel partitioning MAC protocols: FDMA
FDMA: frequency division multiple access
- channel spectrum is divided into frequency bands
- each station is assigned a fixed frequency band
- example: 6-station LAN, 1,3,4 have packet to send, frequency bands 2,5,6 idle
Random-access protocols
- when a node has a frame to send
- transmit at full channel rate R
- no 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 (e.g., via delayed retransmissions)
- examples of random access MAC protocols:
- CSMA/CD
- but also ALOHA, CSMA, CSMA/CA, …
CSMA (carrier sense multiple access)
CSMA: listen before transmit:
if channel sensed idle: transmit entire frame
if channel sensed busy: defer transmission
human analogy: don’t interrupt others when
they’re talking!
CSMA collisions
§ collisions can still occur: propagation delay means two nodes may not hear each other’s
transmissions
§ collision: entire frame transmission time wasted
- plus, frame is not delivered – will need to
be re-sent by higher-level protocol if reliability is needed
CSMA/CD (collision detection)
CSMA/CD: carrier sensing, deferral as in CSMA
* collisions detected within short time
* colliding transmissions are aborted, thereby reducing channel wastage
- collision detection:
- easy in wired LANs: compare transmitted, received signals
- difficult in wireless LANs: received signal strength is overwhelmed by local transmission strength
- human analogy: the polite conversationalist
CSMA/CD (collision detection)
Ethernet
the “dominant” wired LAN technology:
- single chip, multiple speeds (e.g., Broadcom BCM5761)
- first widely used LAN technology
- simple, cheap
- has managed to keep up with speed race: 10 Mbps – 10 Gbps
Ethernet CSMA/CD algorithm
- NIC receives datagram from network layer,
creates frame - If NIC senses channel idle, starts frame
transmission. If NIC senses channel busy,
waits until channel idle, then transmits - If NIC transmits entire frame without detecting another transmission, NIC is done with frame !
- If NIC detects another transmission while
transmitting, aborts and sends jam signal - After aborting, NIC enters binary (exponential) backoff:
- waits to try again – and there’s a random
element to wait time: minimise probability of
another collision
- waits to try again – and there’s a random
Ethernet: physical topology
- bus: popular through mid 90s
- all nodes in same collision domain (can collide with each other)
- star: prevails today
- active switch in center
- each “spoke” runs a (separate) Ethernet protocol instance (nodes do not collide with each other)
Ethernet frame structure
sending NIC encapsulates an IP datagram in an Ethernet frame
preamble: 8 byte pattern used to synchronize receiver, sender clock rates
- other fields…
Ethernet frame structure (more)
- addresses: 6 byte source, destination MAC addresses
- if NIC receives frame with matching destination address, or with broadcast address (e.g. ARP packet – see later), it passes data in frame up to network layer protocol
- otherwise, NIC discards frame
- type: indicates higher layer protocol (usually IP)
- CRC: cyclic redundancy check at receiver
- error detected => frame is dropped
Ethernet: connectionless, unreliable
- connectionless: no handshaking between sending and receiving NICs
- unreliable: receiving NIC doesn’t send acks or nacks to sending NIC
- data in dropped frames is recovered only if sender uses a reliable protocol on top (e.g., TCP), otherwise dropped data is lost
MAC addresses in LANs
- we already know about IP addresses…
- 32 bits
- network-layer address for interface
- function: layer 3 (network layer) forwarding
- MAC (or LAN or physical or Ethernet) address:
- function: used ‘locally” to get a frame from one interface to another phy-connected interface (i.e., across a single network, in the IP-addressing sense)
- for most LANs, this is a 48 bit MAC address burned into the NIC’s ROM
- e.g.: 1A-2F-BB-76-09-AD
ARP: address resolution protocol
Question: how to determine an interface’s MAC address, knowing its IP address?
ARP table: each IP node (host, router) on LAN has a table
* IP/MAC address mappings for local LAN
nodes:
< IP address; MAC address; TTL>
* TTL (Time To Live): time after which address
mapping will be forgotten (typically 20
min)
ARP protocol: same LAN
- A wants to send a datagram to B
- B’s MAC address not in A’s ARP table.
- A broadcasts an ARP query packet, containing B’s IP address
- destination MAC address = FF-FF-FF-FF-FF-FF
- broadcast: all nodes on the LAN receive ARP query
- when B receives the ARP packet, it replies to A with its (B’s) MAC address
- frame sent to A’s MAC address (unicast)
- A caches saves the IP-toMAC address pair in its ARP table until information becomes old (times out)
- soft state: information that times out (goes away) unless refreshed
- ARP is “plug-and-play” :
- nodes create their ARP tables without intervention from net administrator
Addressing: routing to another LAN
walkthrough: send datagram from A to B via R
- focus on addressing – at IP (datagram) and MAC layer (frame)
- assume A knows B’s IP address
- assume A knows IP address of first hop router, R
- assume A knows R’s MAC address
- A creates IP datagram with IP source A, destination B
- A creates link-layer frame with R’s MAC address as destination address,
frame contains A-to-B IP datagram - 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 destination address, frame contains A-to-B IP datagram
Summary
- a link layer protocol (layer-2 protocol) is
implemented in all “nodes” (i.e. all hosts and routers) - there may be many different link layer protocols underlying an end-to-end route through the internet
- many link layer protocols are LAN-based and employ broadcast media
- of these, there are many design options for how to share the media among multiple nodes (“stations”)
- we’ve had a look at Ethernet…
