Elliot Schwartz <>

The Problem

How do we get packets from A to B?


So, we can view the network as an arbitrary topology of subnets connected by routers.

High Level Solution

Note: This approach is called Next Hop Routing, since each router only knows and uses the next hop that the packet is going to take, and does a lookup based on the destination address. An alternative approach might be to carry a multi-hop route in the packet, which could be placed by either the source node or an intermediate router.
Now that you have an idea of the basic solution, we'll explain how this is actually done under IPv4.

IPv4 Addressing

Example Network

We'll use this example network for illustrating points. On the left side, we've got hosts a, b, and Z on a subnet numbered This means that all the hosts on this subnet have addresses start with 10.0.1. A network like this might be an Ethernet. This network is connected to another subnet, 172.20/16, by the router Z. Similarly, on the right hand side, there's another subnet numbered 192.168.1/24, which has one host d and a router Y that connects it to 172.20/16. On 172.20/16 is a host c and a router X that routes to a point-to-point link with host e, numbered

Filling the Table

The next question is how do the hosts get routes in their routing tables. All hosts (including routers) get them from the following methods:

Routing Protocols

The routers on the Internet need a way to communicate toplogical information (how various subnets are connected) and reachability information (what links/subnets are up or down) among themselves. To do this, they use a bunch of routing protocols. Some hosts also participate in routing protocols, mostly by eavesdropping on them to figure out where to send a particular packet, but this is considered a bad thing. The routing protocols provide dynamically updated routing, adjustment of routing tables during failures, "optimal" paths, policy routing, and reduced administration.

There are two main kinds of routing protocols on the Internet: Internal and External. Internal routing protocols are used within an Autonomous System or AS, which is a set of routers under a common administrative control (for example, MITnet). External routing protocols are used to communicate between autonomous systems. Internal routing is largely concerned with optimizing the path length to reduce delay, since within an organization one generally wants to achieve the best connectivity one can, regardless of where the packets go. Common Internal routing protocols are RIP [RFC1058], RIPv2 [RFC1723], OSPF [RFC2178], and ISIS. External routing is largely concerned with enforcing policy. For example, only an ISP's customers should be able to use its infrastructure for through-traffic. The External routing protocol currently used on the Internet is BGP4 [RFC1771]. The following diagram illustrates the role of Internal and External routing protocols:

Addressing/Routing Dynamics

The way one measures the effectiveness of an addressing and routing system is not by looking at the design, but rather by seeing what impact the system has on the Internet and how it makes it perform. There are a number of different dynamic characteristics we can look at to consider performance: These all argue for minimizing the number of routes!

Hierarchical Addressing

To minimize the number of addresses, we use an approach called hierarchicial addressing.