Routing Basics

Each computer in the Internet is identified by its IP address. For our purposes, let us assume that addresses are unique, that is each IP address identifies one machine. An IP address is a 32-bit positive integer. For convenience it is usually decomposed into four 8-bit parts. If we then sequentially write all the parts as decimal numbers and put dots between them, we get the address written in the popular Internet dot notation, such as 192.168.16.2.

A network is a range of IP addresses. It is often referred to by a prefix. A prefix is simply an IP address prefix of a certain size [3]. It is denoted similarly to IP addresses, with its size (in bits) added after the ``/'' mark, for example 192.168.8.0/21.

Data in the Internet are sent in portions called packets. Each packet contains, among others, its sender's and receiver's IP addresses. After leaving the sender's machine, packets are shipped between routers until they reach their destination.

Routers connect the Internet together. Each router has a direct connection to two or more peer routers or local area networks. When a router receives a packet, it examines its destination IP address to determine which peer router the packet should be sent to. It does so using a locally maintained routing table, which contains a list of prefixes. Each prefix is associated with a list of peer routers that accept the traffic heading to the prefix. One of these peer routers is then selected to receive the packet.