How packet switching works

How packet switching works

This page looks at the technical side of packet switching. It's assumed you've already read History of Packet Switching & The Internet.

There are various packet switching protocols in existence, but by far the most common is the Internet Protocol (IP). Currently the majority of networks use IP version 4, introduced in 1983, but there's a gradual shift towards IP version 6, which, among other things, allows for a vastly increased number of devices on the network. This article focuses on IP where a particular protocol is mentioned, but for the most part tries to describe general packet switching principles applicable to any protocol.

Every device on a packet switched network has an address. The data to be transmitted is split up into small chunks (packets), and each packet is labelled with the address of the sender and the address of the recipient. You can think of the data (known as the payload) as a letter on a sheet of paper, and the address data (known as the header) as akin to the envelope used for posting. The header may also contain some additional data — for example, the data to be sent is usually split over multiple packets, so each packet needs a sequence number to let the receiver reassemble it in the correct order.

The simple network, on the right, is made of routers connected together, and each router has an address (A–D). Each computer has an address, 1 or 2, which is a sub-address of its router — for example, A.1 and A.2. Each computer has a routing table within its operating system which it uses to decide how to send packets. Because each computer in the network only has one network connection, any packet destined for another machine will be sent along that link (its default route).

Suppose computer A.1 wishes to send data to computer D.1. Computer A.1 splits the data up into packets, addresses each one with a destination of D.1, and sends them out on its default route to router A. Router A looks at the destination address. It knows it doesn't have a direct link to router D — in fact it only has one link, to router B — so it sends them to router B. Router B looks at the destination address. Router B does have a direct link to router D, but it also has a direct link to router C which it can use to reach router D.

Which should it choose? It could choose either. Typically router B will know — either because the network administrator told it, or because it worked it out for itself — that the direct link is quicker. But it may be that a fault on that link has slowed it to a crawl, so it will opt instead to go via router C.

What's in a router?

There are two basic types of router. The simplest, and the one you're most familiar with, is called the shared memory switch. This is essentially nothing more than a PC with two or more network ports (maybe one is a wireless antenna, one a DSL phone line), and the routing is done entirely in the CPU of the device. It reads a packet in, works out where to send it, and writes it out on the appropriate port. Shared memory routers can be special embedded devices, such as the one on the end of your phone line routing packets in and out of your house, or they can be a standard PC-type server with two or more network connections. Such devices are cheap and work well with small to medium volumes of traffic, but they don't scale well, so you won't find them in the backbone of the internet. For the heavy traffic demands of large networks and Internet Service Providers, a hardware-based switch is needed. These devices are more like a traditional digital telephone exchange in their implementation — they have dedicated hardware circuits called a "switching fabric" which do the actual routing.

The terms "router" and "switch" are often used somewhat interchangeably, and the difference between the two is somewhat of a grey area. The term "switch" has been around the longest, and was initially used to refer to the equipment in a telephone exchange — early automatic exchanges consisted of electromechanical switches which connected one line to another. IP networks generally use the term "router." Technically speaking, switching is the physical process of transferring data from an input port to an output port, whereas routing is the overall process of working out the correct output port and switching the data through the hardware.

Most hardware switching fabrics are based on the crosspoint matrix principle first introduced with Crossbar electromechanical telephone exchanges. The simplest crosspoint matrix consists of input and output lines arranged in a grid, such as the one on the left — a crosspoint matrix switch for four lines. Each line has been split into a receive wire and a transmit wire, and physically laid out with switches at the "crosspoints" where the lines pass over one another. The control system can close the switch at any crosspoint to connect the transmit wire of one line to the receive wire of another. In the diagram, lines 2 and 3 are connected. In early crosspoint systems these switches were large electromechanical switches called Crossbars, extensively used in telephone networks worldwide from the 1950s into the '90s. Later systems, introduced in the '60s, used reed relays at the crosspoints — the principle exactly the same, but the reed relays much smaller and lighter. Modern digital telephone switches and packet switches such as IP routers use the same principle, but the crosspoint switches are made from transistors on integrated circuits.

In switches of any serious size, the number of lines is such that one big matrix would be far too impractical and costly. Switching fabrics are therefore made from several smaller matrices, wired together in stages.

The use of hardware switches, rather than doing everything in a central processor, allows very fast packet switching rates to be achieved in a router serving many high-speed lines.

Banyan Networks

The simplest multistage matrix switch is called a Banyan Network, after the East Indian banyan tree, which has a similarly twisty-looking structure. In a Banyan Network there's exactly one path from any input line to any output line, but that path isn't exclusively for that pair of lines, so a phenomenon called blocking can occur — where a packet needs to use a path to get from one line to another, say line 1 to 3, but another pair of lines is currently using that path, so the packet must wait. The delays are only milliseconds, but in a large system they can soon cause problems unless the layout of the switching network is carefully designed.

As a packet enters the router, the central processor works out which output line it needs to be switched to. Each line is numbered sequentially, and the binary number of that line is prepended to the packet. Each crosspoint in the Banyan network switches the packet to one of its two outputs using that binary number — the first switch uses the first digit, the second switch uses the second digit, and so on.

So far we've assumed each router in the network is manually configured to know about the state of its output lines — which one gives the best route to a particular destination. In large, continually changing networks, dynamic routing allows a router to update its own knowledge about the state of the network; we'll look at this in a later article, along with technologies such as the Domain Name System (DNS), which lets humans use easy-to-remember names like communicationsmuseum.org.uk rather than the more cryptic numerical IP addresses.