How packet switching works

This page looks at the technical side of packet switching. It is assumed you have 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 which was introduced in 1983 but there is a gradual shift towards IP version 6, which amoungst other things allows for a vastly increased number of devices on the network. This article focuses on IP where a particular packet switching 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 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 enable the receiver to re-assembe it in the correct order.

Simple network

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 1 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 are most familair with is called the shared memory switch. This is essentially nothing more than a PC with 2 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 2 or more network connections. Such devices are cheap and work well with small to medium volumes of traffic but they do not scale well so you won' 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 telehpone 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 interchangably 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 physically 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.

Crosspoint matrix

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. Here we see 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 cross point to allow the transmit wire of one line to be connected to the receive of another. In the diagram, lines 2 and 3 are connected. In early crosspoint systems these switches were large electromechanical switches called Crossbars and Crossbar technology was extensively used in the telephone network around the world from the 1950's into the 90's. Later systems introduced in the 60''s used reed relays at the crosspoints. The principle was exactly the same but the reed relays were much smaller and lighter. Modern digital telephone switches and packet switches such as IP routers use the same principle but the crosspoints switches are made from transistors on integrated circuits (chips).

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 matrixes 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.

Crossbar electromechanical switch from a 1960's telephone exchange

Banyan Networks

Banyan switching network for 8 lines

The simplest multistage matrix switch is called a Banyan Network after the East Indian Banyan tree whch has a similar twisty looking structure. In a Banyan Network there is exactly one path from any input line to any output line but that path is not exclusively for that pair of lines, hence a phenomenon called blocking can occur. This is where a packet needs to use the path to get from one line to another, say line 1 to 3, but another pair of lines is currently using that path, hence 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 the binary number, the first switch uses the first digit, the second switch uses the second digit and so on.

So far we have 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 the router to update its own knowledge about the state of the network and we will look at this in a later article along with technologies such as the Domain Name System (DNS) which allows humans to use easy to remember names like rather than the more cryptic numerical IP addresses.