Routing & Switching — How Packets Find Their Way

What you'll learn

• How an Ethernet switch learns where every device is and decides to forward, flood or filter each frame
• How VLANs split one physical switch into several separate networks, and what an 802.1Q tag looks like
• How ARP finds the MAC address that belongs to an IP address, and when a host talks to its default gateway instead
• How a router reads its routing table, and the difference between static and dynamic routing
• The ideas behind RIP, OSPF and BGP, the protocols that keep the Internet's routes up to date
• You will build three tools: a learning switch, a host's ARP logic and an OSPF shortest-path calculator

The office receptionist and the road signs 🚦

Inside an office building, a receptionist delivers internal mail. On day one she knows nobody, so she walks a letter around every floor. But every time someone hands her mail, she notes which office they sit in, and after a few days she delivers straight to the right door. That is a switch: it moves frames inside one network, using MAC addresses, and it learns by watching.

Mail for another city leaves the building. Now nobody knows the exact door; the post only follows road signs: "Riyadh: take exit 4", "everything else: highway north". That is a router: it moves packets between networks, using IP addresses and a table of signs called the routing table. Remember the one-line summary: switches connect devices into a network; routers connect networks to each other.

Switching: learn, then forward, flood or filter

A switch keeps a MAC address table (also called the CAM table or forwarding database): which MAC address was last seen on which port. For every frame that arrives it does two things:

1. Learn: write down "the source MAC lives behind the port this frame came in on", with the current time.
2. Decide for the destination MAC:
   • broadcast (ff:ff:ff:ff:ff:ff) or multicast (the lowest bit of the first byte is 1): send it out of every other port (flood);
   • unknown unicast: also flood, and let the reply teach the switch where that device is;
   • known, on a different port: forward it out of that one port only;
   • known, on the same port it came in on: filter (drop) it, because the destination already received it on that segment.

           +------------------------------------+
           |  port 1   port 2   port 3   port 4 |
           +----|--------|--------|--------|----+
                A        B        C        D

MAC table after A -> B and B -> A:
  02:00:00:00:00:0a   port 1   seen at t=0
  02:00:00:00:00:0b   port 2   seen at t=1

Entries age out when a device stays silent: the IEEE 802.1D default ageing time is 300 seconds. That keeps the table small and lets a laptop that moved to another port be found again. On Linux you can see a software bridge's table with bridge fdb show; on a Cisco switch the command is show mac address-table.

Two consequences matter in practice. First, every switch port is its own collision domain and runs full duplex, so the old Ethernet collisions are gone. Second, all ports still share one broadcast domain: one ARP broadcast reaches every device. And if someone connects two switches with two cables, a broadcast circles forever and multiplies (a broadcast storm), because Ethernet frames have no TTL. The Spanning Tree Protocol (IEEE 802.1D, with the faster RSTP variant) prevents this by putting redundant links into a blocking state until they are needed.

VLANs: several networks on one switch

Often you want the guests, the staff and the cameras on separate networks, without buying three switches. A VLAN (virtual LAN, IEEE 802.1Q) does that: the switch keeps a separate MAC table and a separate broadcast domain per VLAN, so a frame in VLAN 10 can never reach a port in VLAN 20. To get from one VLAN to another, traffic must go through a router (or a "layer 3 switch" that routes internally), where a firewall can check it.

Ports come in two kinds:

• An access port belongs to one VLAN. The device plugged in sends ordinary, untagged frames and has no idea VLANs exist.
• A trunk port carries many VLANs between switches (or to a router), so each frame gets a 4-byte 802.1Q tag that says which VLAN it belongs to. Frames of one VLAN, the native VLAN, cross the trunk untagged.

The tag is inserted right after the source MAC:

untagged:  | dst MAC (6) | src MAC (6) | EtherType (2) | payload ...
tagged:    | dst MAC (6) | src MAC (6) | 0x8100 (2) | TCI (2) | EtherType (2) | payload ...

TCI = 16 bits:  PCP (3)  |  DEI (1)  |  VLAN ID (12)
                priority    drop        1 to 4094 usable (0 and 4095 are reserved)

0x8100 (the TPID) sits where the EtherType would be, which is how a receiver knows a tag follows. PCP is a priority (0-7) used for quality of service, such as giving voice traffic precedence. The 12-bit VLAN ID allows 4094 usable VLANs. A security note: leave the native VLAN unused by real devices, and never trust the VLAN alone to separate sensitive systems; misconfigured trunks allow VLAN hopping.

ARP: from IP address to MAC address

Your laptop wants to send a packet to 192.168.1.20. The packet needs an Ethernet frame around it, and the frame needs a destination MAC. Where does that come from? From ARP (Address Resolution Protocol, RFC 826). But first the host makes one decision, using its own address and mask:

• Same subnet (destination AND mask == my network): the destination is on-link, so the host needs the destination's own MAC.
• Different subnet: the packet must go to the default gateway (the router), so the host needs the gateway's MAC, even though the IP header still says the final destination.

Then it checks its ARP cache. If the MAC is unknown it broadcasts a question and waits for a unicast answer:

192.168.1.10 -> ff:ff:ff:ff:ff:ff   ARP request:  who has 192.168.1.20? tell 192.168.1.10
192.168.1.20 -> 192.168.1.10        ARP reply:    192.168.1.20 is at 02:00:00:00:00:20

Answers are cached for a short while (typically seconds to minutes, depending on the system) and confirmed again when they go stale; see the cache with ip neigh on Linux or arp -a on Windows. A gratuitous ARP, an announcement nobody asked for, lets a device tell everyone its mapping, for example after a failover. IPv6 does the same job with the Neighbor Discovery Protocol (NDP, RFC 4861), using ICMPv6 instead of broadcasts.

Notice what this means for a packet that crosses routers, which you met in the OSI lesson: the IP addresses stay the same from end to end, while the MAC addresses are rewritten at every hop. Each router ARPs for the next hop on each link. And notice the weakness: ARP has no authentication. Any device on the LAN can answer "the gateway is at my MAC". You will see that attack, ARP spoofing, and its defences in the network security lesson.

Routing: static and dynamic

A router receives a packet, looks the destination up in its routing table with longest-prefix match (you implemented that in the IP lesson), decrements the TTL, and sends the packet out of the chosen interface towards the next hop. If the TTL reaches 0 the packet is dropped and an ICMP "time exceeded" message goes back to the sender; that rule stops a packet from looping forever, and it is exactly what traceroute uses. A Linux host's table looks like this:

$ ip route
default via 192.168.1.1 dev eth0 proto dhcp metric 100
10.20.0.0/16 via 192.168.1.254 dev eth0
192.168.1.0/24 dev eth0 proto kernel scope link src 192.168.1.10

The last line is a connected route (the subnet of an interface). The middle line is a static route, added by hand with ip route add 10.20.0.0/16 via 192.168.1.254. The first is the default route. ip route get 203.0.113.5 asks the kernel which route it would pick.

Static routes are simple and predictable, but nobody updates them when a link fails, and typing hundreds of them does not scale. So routers run dynamic routing protocols that discover routes and react to failures. When two sources offer the same prefix, the router prefers the more trusted source; Cisco calls this administrative distance (by default connected 0, static 1, eBGP 20, OSPF 110, RIP 120, iBGP 200), and then compares the protocol's own metric.

Three families of routing protocols

• Distance vector (RIP, RFC 2453): each router tells its neighbours "I can reach X at cost N", and they add their link cost. RIP counts hops, treats 16 as infinity and sends updates every 30 seconds. Simple, but slow to converge, and after a failure routers can "count to infinity" while bad news spreads.
• Link state (OSPF, RFC 2328 for IPv4 and RFC 5340 for IPv6; and IS-IS): every router floods a description of its own links (LSAs) to the whole area, so every router builds the same map, then runs Dijkstra's shortest-path-first algorithm from itself. Link costs are configurable; Cisco's default derives them from a 100 Mbit/s reference bandwidth. Large networks are split into areas around a backbone area 0. OSPF converges fast and is the usual choice inside a company.
• Path vector (BGP-4, RFC 4271): the routing protocol between organisations. Each autonomous system (an ISP, a cloud, a large company, identified by an AS number) announces the prefixes it can reach, together with the AS path, the list of ASes on the way. A router rejects a path that already contains its own AS, which prevents loops, and operators choose routes by policy (cost, contracts), not just by distance. BGP runs over TCP port 179. A mistaken or malicious announcement can pull traffic for someone else's prefix (a route leak or hijack); RPKI (RFC 6480) lets networks check that an AS is authorised to originate a prefix.

Inside one organisation you use an IGP such as OSPF; between organisations, the EGP of the Internet is BGP.

Putting it together

Follow one packet from a laptop in VLAN 10 to a web server on the Internet:

1. The laptop sees the server is off-link, so it ARPs for its gateway and builds a frame to the gateway's MAC.
2. The access switch learns the laptop's MAC, looks up the gateway's MAC and forwards the frame up the trunk with a VLAN 10 tag.
3. The router (or layer 3 switch) strips the frame, finds the destination with longest-prefix match, decrements the TTL, and ARPs for its own next hop: a new frame, new MACs, same IP addresses.
4. Across the Internet, routers chosen by OSPF inside each network and BGP between networks repeat step 3 until the packet arrives.

When something breaks, ask the same questions in the same order: Is the port up and in the right VLAN (ip link, show interfaces)? Does the switch know the MAC (bridge fdb show, show mac address-table)? Does the host have the right ARP entry (ip neigh)? Does the routing table choose the expected route (ip route get)? The next lesson turns this into a complete troubleshooting method.

Recap

• A switch learns source MACs per port and then forwards known unicast, floods broadcast, multicast and unknown unicast, and filters frames for the port they came from. Entries age out (300 s by default); STP prevents loops.
• VLANs create separate broadcast domains on one switch; trunks carry a 4-byte 802.1Q tag with a 12-bit VLAN ID. Traffic between VLANs needs a router.
• A host sends on-link traffic to the destination's MAC and everything else to the gateway's MAC, found with ARP (NDP in IPv6). ARP has no authentication.
• Routers use longest-prefix match and the TTL. Static routes are fixed; RIP (distance vector), OSPF (link state, Dijkstra) and BGP (path vector, between autonomous systems) keep routes up to date.

Practice next: run ip route, ip neigh and ip route get for a few destinations on your own machine and explain each line. Then move on to the troubleshooting toolkit.