Switches, learning bridges and VLANs

Why it exists

One shared Ethernet segment is one collision domain: every station hears every frame and they all compete for the cable. To grow a LAN, or to connect several, we need devices that separate the segments at the data link layer and forward frames only where they are needed. A learning bridge (a switch is a bridge with many ports) does it without being configured: it learns which station is on which port by watching the source addresses. But redundant links make loops, and a loop makes broadcast frames circle for ever; the spanning tree protocol switches off enough links to leave a tree. A VLAN then splits one physical switch into several logical LANs. GATE asks which device does what, how many collision and broadcast domains a drawing has, how a learning bridge acts on a sequence of frames, and what a spanning tree looks like.

Prerequisites

You need the Ethernet frame (source and destination MAC addresses, the broadcast address ff:ff:ff:ff:ff:ff) and CSMA/CD from Ethernet and the collision domain of medium access.

Precise definitions

Devices by layer.

A collision domain is the set of stations whose frames can collide. A broadcast domain is the set of stations that receive a broadcast frame. A hub extends a collision domain; a switch splits collision domains (and with full-duplex links to each station, no collision occurs at all, so CSMA/CD is not even used) but passes broadcasts to every port; a router blocks broadcasts.

The learning bridge. The bridge keeps an address table (MAC address, port) and for every arriving frame does:

1. Learn: record (source address, arrival port), replacing an older entry (entries expire after an ageing time).
2. Decide on the destination:
   • broadcast, or not in the table: flood: send out of every port except the arrival port;
   • in the table on the same port the frame came in: filter: discard (sender and receiver are on the same segment);
   • in the table on another port: forward to that port only.

A bridge is transparent: the stations do not know it exists. A switch may forward store-and-forward (receive the whole frame, check the CRC, then send) or cut-through (start as soon as the destination address is read).

Loops and the spanning tree. Redundant links between bridges create loops. A broadcast or a frame to an unknown destination is flooded, goes round the loop and comes back, multiplying: a broadcast storm; address tables also flap as the same source appears on two ports. The spanning tree protocol (STP, IEEE 802.1D) has the bridges exchange control messages (BPDUs) and block some ports so that the active topology is a tree. The rules (with a cost of 1 per hop):

1. The bridge with the lowest bridge ID is the root bridge.
2. Every other bridge picks its root port: the port with the lowest root path cost (ties: the neighbouring bridge with the lower ID, then the lower port number).
3. On every LAN the bridge with the lowest root path cost (ties: the lower ID) is the designated bridge and forwards on that LAN through its designated port.
4. Ports that are neither root nor designated are blocked: they receive but do not forward data frames.

The result: root ports and designated ports forward, forming a spanning tree of the bridges and LANs; if a link fails the protocol recomputes. (Real STP ports pass through the states blocking, listening, learning and forwarding, which takes tens of seconds; rapid STP is faster.)

VLANs. A virtual LAN divides the ports of one or more switches into separate logical LANs: each VLAN is its own broadcast domain (and normally its own IP subnet). Frames cannot pass between VLANs at layer 2; a router (or a layer-3 switch) connects them. An access port belongs to one VLAN. A trunk port carries the frames of several VLANs between switches, each frame carrying an IEEE 802.1Q tag of 4 bytes inserted after the source address: the tag protocol identifier 0x8100 (16 bits), then 3 bits of priority, 1 drop-eligible bit and the 12-bit VLAN ID. Identifiers 0 and 4095 are reserved, so $4094$ VLANs can be used. The tag lengthens the frame: the maximum becomes 1522 bytes (from 1518) and the minimum 68 (from 64). VLANs give broadcast containment, security and the freedom to place a group of users anywhere.

How it works

A learning switch with four ports; hosts A (port 1), B (port 2), D (port 4), and C and E sharing a hub on port 3. Watch the address table fill and the three actions: flood, forward, filter (frame 4: E and C are on the same port, so the switch does not forward it).

Counting domains. A hub, a switch, and a network with a hub, two switches and a router.

The spanning tree. Five bridges B1 to B5 and six LANs A to F; B1 has the lowest ID and is the root. Each other bridge picks its root port; on a LAN served by a nearer bridge the other bridges' ports are blocked.

The 802.1Q tag, byte by byte.

Broadcasts inside VLANs. A six-port switch with VLANs 10 (ports 1, 2), 20 (ports 3, 4), 30 (port 5) and a trunk (port 6).

Worked examples

#include <stdio.h>
#include <string.h>
 
#define PORTS 4
#define MAXHOST 8
 
static char host[MAXHOST];
static int where[MAXHOST], nhost;
 
static int lookup(char h) {
    for (int i = 0; i < nhost; i++)
        if (host[i] == h) return where[i];
    return 0;
}
 
static void learn(char h, int port) {
    for (int i = 0; i < nhost; i++)
        if (host[i] == h) { where[i] = port; return; }
    host[nhost] = h;
    where[nhost++] = port;
}
 
static void frame(char src, char dst, int in_port) {
    learn(src, in_port);
    int out = dst == '*' ? 0 : lookup(dst);                /* '*' is the broadcast address */
    printf("%c -> %c on port %d: ", src, dst, in_port);
    if (out == 0) {
        printf("flood to ports");
        for (int p = 1; p <= PORTS; p++)
            if (p != in_port) printf(" %d", p);
        printf("\n");
    } else if (out == in_port) {
        printf("filter (same port)\n");
    } else {
        printf("forward to port %d\n", out);
    }
}
 
int main(void) {
    int port_of[128] = {0};
    port_of['A'] = 1; port_of['B'] = 2; port_of['C'] = 3; port_of['E'] = 3; port_of['D'] = 4;
    const char pairs[7][2] = {{'A', 'B'}, {'B', 'A'}, {'C', 'A'}, {'E', 'C'}, {'A', 'E'}, {'D', '*'}, {'B', 'D'}};
    for (int i = 0; i < 7; i++) frame(pairs[i][0], pairs[i][1], port_of[(int)pairs[i][0]]);
    printf("table:");
    for (int p = 1; p <= PORTS; p++)
        for (int i = 0; i < nhost; i++)
            if (where[i] == p) printf(" %c:%d", host[i], p);
    printf("\n");
    return 0;
}

A -> B on port 1: flood to ports 2 3 4
B -> A on port 2: forward to port 1
C -> A on port 3: forward to port 1
E -> C on port 3: filter (same port)
A -> E on port 1: forward to port 3
D -> * on port 4: flood to ports 1 2 3
B -> D on port 2: forward to port 4
table: A:1 B:2 C:3 E:3 D:4

Cheat box

Traps and GATE patterns

Connections

A bridge works with the MAC addresses of Ethernet and replaces the shared cable and the collisions of medium access by one collision domain per port. ARP broadcasts are flooded by the switch to its whole broadcast domain, which is what VLANs contain; a VLAN is usually one IP subnet (IPv4 addressing), and a router joins them.

PYQs

Consider the diagram shown below where a number
of LANs are connected by (transparent) bridges. In
order to avoid packets looping through circuits in the
graph, the bridges organize themselves in a spanning
tree. First, the root bridge is identified as the bridge
with the least serial number. Next, the root sends out
(one or more) data units to enable the setting up of the
spanning tree of shortest paths from the root bridge to
each bridge.

Each bridge identifies a port (the root port) through
which it will forward frames to the root bridge. Port
conflicts are always resolved in favour of the port
with the lower index value. When there is a
possibility of multiple bridges forwarding to the same
LAN (but not through the root port), ties are broken
as follows: bridges closest to the root get preference
and between such bridges, the one with the lowest
serial number is preferred.

For the given connection of LANs by bridges, which
one of the following choices represents the depth first
traversal of the spanning tree of bridges?

COMPUTER NETWORK

Consider the correct spanning tree for the previous
question. Let host H1 send out a broadcast ping
packet. Which of the following options represents

the correct forwarding table on B3?

In a network of LANs connected by bridges, packets
are sent from one LAN to another through
intermediate bridges. Since more than one path may
exist between two LANs, packets may have to be
routed through multiple bridges. Why is the spanning
tree algorithm used for bridge-routing?

Node X has a TCP connection open to node Y. The
packets from X to Y go through an intermediate IP
router R. Ethernet switch S is the first switch on the
network path between X and R. Consider a packet
sent
from
X
to
Y
over
this
connection.
Which of the following statements is/are TRUE about
the destination IP and MAC addresses on this packet
at the time it leaves X?

Consider that 15 machines need to be connected in
a LAN using 8-port Ethernet switches. Assume that
these switches do not have any separate uplink
ports. The minimum number of switches needed is
_______.

In the diagram shown below, L1 is an Ethernet
LAN and L2 is a Token-Ring LAN. An IP packet
originates from sender S and traverses to R, as
shown. The links within each ISP and across the
two ISPs, are all point-to-point optical links. The
initial value of the TTL field is 32. The maximum
possible value of the TTL field when R receives the
datagram is __________.

Self-check

Revision card

References