Link Layer

Peter Wood

Link Layer

Link Layer Services

Transmission Errors

Parity Bits

Checksumming Methods

Cyclic Redundancy Checks

Error Correction

Hamming Distance

  • a fixed size unit of data comprising data and check bits is called a codeword
  • the number of bit positions in which two codewords differ is called the Hamming distance
  • if two codewords are distance d apart, it will require d single-bit errors to convert one to the other
  • in the parity example below

    Parity codewords

    the distance between any pair of codewords is 2
  • so minimum Hamming distance dmin is 2
  • the maximum number e of bit errors that can be detected is: e = dmin - 1

Error Correction with RAC Parity

  • let each dataword comprise k bits
  • assume r bits are added to form a codeword
  • this is called an (n,k) encoding scheme, where n = k + r
  • assume each dataword comprises k = 12 bits
  • think of the bits arranged into 3 rows and 4 columns

    Row and column parity

  • the example RAC (row and column) encoding is a (20,12) encoding
  • a single-bit error can be corrected as follows

    Correction using row and column parity

Point-to-point Communication

  • early communication systems had each communication channel, e.g. a leased circuit, connecting exactly two computers
  • also the case for a dial-up link from a residential host
  • known as point-to-point communication and has three useful properties:
    • each connection is independent and can use appropriate hardware
    • the two end points have exclusive access and can decide how to send data across the connection
    • since only two computers have access to the channel, it is easy to enforce security and privacy
  • one common protocol is the point-to-point protocol (PPP)

Point-to-Point Protocol

PPP data frame format

  • every PPP frame starts and ends with a one-byte flag field with a value of 01111110 (0x7E hexadecimal)
  • the address and control fields are always set to the same values (allows for future development)
  • the protocol field tells the PPP receiver the upper-layer protocol to which the encapsulated data belongs (IP has value 0x21)
  • the information field is of variable length and carries the encapsulated data
  • the check field is a two- or four-byte CRC

Byte Stuffing

  • a protocol such a PPP uses a specific bit pattern (0x7E) to delimit a frame
  • what happens if this pattern appears as data within the frame
  • a technique called byte stuffing resolves this problem
  • another (escape) sequence is used to mark occurrences of reserved sequences in the data
  • PPP uses 01111101 (0x7D), as illustrated below

    Byte stuffing

  • if 0x7D appears in the original data, it must also be preceded by 0x7D

Multiple Access

  • recall that an alternative to a point-to-point link is a broadcast link
  • as typically used for LANs
  • the problem now is how to coordinate the access of multiple sending and receiving nodes to a shared broadcast channel
  • this is called the multiple access problem
  • co-ordination requires communication, and the time to communicate depends on distance
  • so this mechanism does not scale over long distances

Multiple Access Protocols

  • many multiple access protocols have been developed over the years
  • can essentially be divided into three categories:
    • channel partitioning protocols
    • random access protocols
    • taking-turns protocols
  • ideally, a multiple access protocol for a broadcast channel of rate R bits per second should have the following characteristics:
    • when only one node has data to send, that node has throughput R bps
    • when M nodes have data to send, each has a throughput of R/M bps
    • the protocol is decentralised, i.e., no master node
    • the protocol is simple

Channel Partitioning Protocols

  • a channel can be partitioned using multiplexing
  • four basic approaches to multiplexing:
    • frequency division multiplexing
    • time division multiplexing
    • wavelength division multiplexing (used for optical fibre)
    • code division multiplexing (used for mobile phones)
  • we will consider only the first two

Frequency Division Multiplexing

  • Frequency Division Multiplexing (FDM) is used for broadcast radio
  • radio stations can transmit signals simultaneously
  • provided they each use a separate channel (i.e. carrier frequency)
  • same principle can be used for data communications, as illustrated below

    Frequency division multiplexing

  • there is a practical limit on set of frequencies that can be used for channels
  • if they are too close, interference can occur
  • a set of carrier frequencies is chosen with a gap, known as a guard band, between them
  • the problem is that the throughput drops when fewer than N nodes are sending data

Time Division Multiplexing

  • Time Division Multiplexing (TDM) is simpler than FDM
  • simply means transmitting an item from one source, then from another, and so on, as shown below

    Time division multiplexing

  • figure shows items being sent in a round-robin order
  • problem:
    • the throughput drops when fewer than N nodes are sending data
    • each node must wait for its turn

Taking-Turns Protocols

  • we will mention just two such protocols
  • in the polling protocol
    • one node is designated as a master node
    • the master node polls each of the nodes in a round-robin manner
    • each node is offered the chance to send some maximum number of frames
    • problems: polling delay and master can fail
  • in the token-passing protocol
    • no master node
    • a special frame known as a token is passed among the nodes in some fixed order
    • a node holds onto the token if it has frames to send
    • otherwise it forwards the token to the next node
    • problems: if a node fails or neglects to pass the token

Random Access Protocols

  • in a random access protocol, each node transmits at the full rate of the channel
  • now transmitted frames can collide
  • when there is a collision, none of the receiving nodes can make sense of any of the transmitted frames
  • all the frames involved in a collision are lost
  • the broadcast channel is wasted during the collision interval
  • when there is a collision, each node retransmits after a random delay
  • there are many random access protocols, but we will consider only Ethernet

Ethernet

  • original standard was published by Digital Equipment Corporation, Intel Corporation, and Xerox Corporation in 1982
  • IEEE currently controls Ethernet standards
  • in its original form, an Ethernet LAN consisted of a single coaxial cable called the ether, but often referred to as a segment
  • thus Ethernet used a so-called bus topology:

    Bus topology

  • a segment was limited to 500 m in length, with a minimum separation of 3 m between each pair of connections
  • it operated at 10 Mbps
  • a later version, Fast Ethernet, operated at 100 Mbps
  • newer versions include Gigabit Ethernet, operating at 1,000 Mbps or 1 Gbps, and 10 Gigabit Ethernet, operating at 10 Gbps

Ethernet Hub-Based Star Topology

  • by the late 1990s most organisations had moved to a hub-based star topology

    Ethernet hub-based star topology

  • each host and router is directly connected to a hub
  • hub is a physical-layer device that acts on bits rather than frames
  • when a bit arrives on one interface, it is transmitted on all other interfaces
  • so this is also a broadcast LAN environment

CSMA/CD

  • all computers attached to the Ethernet use CSMA/CD to co-ordinate their activities
  • CSMA/CD = Carrier Sense Multiple Access/Collision Detection
  • a computer wishing to transmit checks for electrical activity on the cable, informally called a carrier
  • if there is no carrier, the computer can transmit
  • if a carrier is present, the computer waits for the sender to finish before proceeding

Collisions

  • it is possible for two or more computers to detect the lack of carrier and start transmission (almost) simultaneously
  • the signals then interfere with one another
  • this interference is called a collision:

    Two colliding transmissions

Detecting Collisions

  • a sending computer monitors the signal on the cable
  • if the signal differs from the signal it is sending, then a collision has occurred and the computer stops transmitting:

    Collision detection

Handling Collisions

  • following a collision, a computer waits for the cable to become idle before retransmitting
  • however, if the computers start transmitting as soon as the cable becomes free, another collision will occur
  • Ethernet requires each computer to delay after a collision
  • the standard specifies a maximum delay, d, and requires each computer to choose a random delay less than d
  • in this case, the computer choosing the shortest delay will transmit first
  • if subsequent collisions still occur, the computers double the maximum delay (2d, 4d, ...) until the range is large enough for one computer to choose a short delay and transmit without a collision
  • this technique is called binary exponential backoff

Link-Layer Addressing

  • each computer (interface) on the LAN is assigned a unique physical address
  • also called a hardware address or Media Access address (MAC address)
  • MAC addresses are 6 bytes (48 bits) long, usually written in hexadecimal, e.g., 1A-23-F9-CD-06-9B

    MAC addresses

  • IEEE manages the MAC address space, allocating blocks of addresses to manufacturers

Address Resolution Protocol

  • addressing on LANs is via MAC addresses
  • addressing at the network layer is via, e.g., IP addresses
  • so we need to be able to translate between them
  • this is done by the Address Resolution Protocol (ARP)
  • ARP takes an IP address on the same LAN and returns the corresponding MAC address

    MAC addresses

How ARP Works

  • each node (host or router) has an ARP table in memory, containing mappings
  • how does the node determine the mappings?
  • it sends an ARP query packet to the broadcast MAC address FF-FF-FF-FF-FF-FF
  • the packet contains the desired IP address and the MAC address of the sender
  • the one node with the matching IP address sends a response ARP packet with its MAC address

Ethernet Frame

Ethernet frame

  • the 64-bit preamble consists of alternating ones and zeros allowing the receiver to synchronise with the incoming signal
  • followed by the header consisting of a 48-bit destination address, a 48-bit source address, and a 16-bit frame type
  • payload can vary in length from a minimum of 46 bytes to a maximum of 1,500 bytes
  • payload is followed by a 32-bit CRC
  • Ethernet standard specifies the values that can be used in the header fields; for example
    • 48-bit address FF:FF:FF:FF:FF:FF (hexadecimal), i.e. all 1s, is reserved for broadcast
    • frame type value of 0800 (hexadecimal) is reserved for IPv4 traffic

Ethernet Header Example

Ethernet header example

Manchester Encoding

  • Ethernet frames are transmitted using Manchester Encoding
  • uses the fact that hardware can detect a change in voltage more easily than a fixed value
  • technically, the hardware is edge triggered, with the changes known as rising or falling edges
  • the sender transmits
    • a falling edge to encode a 1
    • a rising edge to encode a 0
    as illustrated below

    Manchester encoding

  • the voltage change that encodes a bit occurs exactly half-way through the time slot
  • if two contiguous bits have the same value, an additional change in voltage occurs at the edge of the time slot

Manchester Encoding Preamble

  • Manchester Encoding uses a preamble to allow for synchronisation
  • preamble consists of 64 alternating 1s and 0s sent before the frame
  • these produce a square wave with transitions exactly in the middle of each slot
  • receiving hardware uses the preamble to synchronise with the time slots
  • the last two bits of the preamble are both 1s to signal the end of the preamble

Extending LANs

  • this section covers the concepts of repeaters, bridges, and switches
  • a maximum length specification is a fundamental part of LAN technologies
  • LAN hardware is engineered for a fixed maximum length cable
  • the hardware may not work correctly over a cable exceeding this length

Repeaters

  • one distance limitation in LANs arises because electrical signals become weaker as they travel along a cable
  • some LAN technologies allow two cables to be joined together by a device called a repeater
  • when a repeater detects a signal on one cable, it transmits an amplified signal on the other cable, as illustrated below

    Single repeater

  • the maximum size of an original Ethernet segment was 500m, so a single repeater could double the effective length of an Ethernet to 1,000m

Limitations of Repeaters

  • unfortunately, adding repeaters cannot be continued indefinitely
  • the Ethernet standard requires low delay for CSMA/CD to work
  • if the delay is too large, the scheme fails
  • the most important disadvantage of a repeater is that it does not understand frames; it simply amplifies the electrical signal
  • if a collision or electrical interference occurs on one segment, repeaters cause the same problem to occur on all other segments

Bridges

  • a bridge is an electronic device connecting two LAN segments that uses conventional interfaces and therefore handles complete frames
  • the bridge listens to each segment in promiscuous mode
  • promiscuous mode means that a node processes every frame, not just those addressed to it
  • when a bridge receives a frame, it verifies that it arrived intact and forwards it to the other segment if necessary
  • thus, two LAN segments connected via a bridge behave like a single LAN:

    Bridged LAN segments

  • bridges are popular because they help isolate problems
  • they only forward complete, correct frames and not collisions or electrical interference

Frame Filtering

  • a bridge also performs frame filtering - it only forwards frames if necessary
  • it uses the source MAC addresses to build up a table of computers attached to each segment
  • figure below illustrates how such an adaptive or learning bridge learns the locations of computers

    Bridge events

  • A, B and C are on segment 1; X, Y and Z are on segment 2
  • the first time computer A sends to B, the bridge has to forward the frame to segment 2
  • when B sends to A, the bridge discovers that they are both on the same segment so does not forward the frame

Spanning Bridges

  • a bridged network can span many segments, as illustrated below

    Spanning bridges

  • one bridge is required to connect each segment to the rest of the bridged network
  • although each bridge introduces a small delay, the network will correctly forward a frame from a computer on one segment to a computer on any other segment
  • bridges also forward broadcast frames
  • therefore, a broadcast frame from a computer on segment a will be propagated to all other segments

Distributed Spanning Tree

  • broadcast frames cause problems if a network contains bridges connected in a cycle, as illustrated below

    Cyclic bridges

  • this time, a broadcast frame from a computer on segment a will cycle indefinitely, both B1 -> B3 -> B4 -> B2 and B2 -> B4 -> B3 -> B1
  • to prevent the problem of infinite loops, a bridged network must not allow the following two conditions to occur simultaneously
    • all bridges forward all frames
    • the network contains a cycle
  • to prevent loops, some bridges automatically agree not to forward frames
  • when a bridge first boots, it communicates with other bridges on the segments to which it connects and the bridges compute a Distributed Spanning Tree (DST) to determine which bridges will not forward frames
  • after the DST algorithm completes, the bridges that agree to forward frames form a tree, i.e. a graph without cycles

Switches

  • an Ethernet switch is an electronic device that resembles a hub
  • like a hub, a switch has multiple ports that each attach to a single computer or a LAN segment
  • a switch simulates a bridged LAN, as illustrated below

    Switched LAN

  • the switch provides each computer with the illusion of a separate LAN segment connected to other segments via bridges
  • the advantage of a switched LAN over a hub is parallelism:
    • a hub can only support one transmission at a time
    • a switch with N ports can transfer up to N/2 frames simultaneously, provided they are independent
    • a switch can also learn which computers are on which port

Links to more information

See Chapter 5 of [Kurose and Ross], Chapters 13 to 15 and 17 of [Comer] and parts of Chapters 3 and 4 of [Tanenbaum].