# Building the Routing Table- Ciscco Certifed Support Technici

Routers build routing tables from a variety of sources, but the primary ones are

• Including the IP address of each connected interface

• Manual configuration, or static routes

• Dynamic routing protocols

Including the connected interfaces is obvious: the router knows about these networks because it has direct local configuration information.

Static routes are a little more difficult, but still simple. Since the operator of the network in Figure 3-10 has a drawing of the network (a network diagram) and all the IP addresses, they can manually configure routing table entries in B’s routing table.

These are called static routes.

The third option is the most complex and most common. Each router in the network is a specialized computer. Routers, like all other computers, can run software of various kinds, even though they do not normally have keyboards and monitors attached to them. One of the pieces of software almost all routers run is an application called a routing protocol.

The various methods used to build routing tables, all combined, are often called the control plane.

Let’s return to the real world for a few moments to understand how routing protocols work; Figure 3-11 illustrates.

Figure 3-11 A Physical World Routing Protocol Illustration

In Figure 3-11, there is a small network of paths with labeled intersections. We are trying to find a path between Y and Z, each located in a cul-de-sac. The idea is someone standing at Y should be able to get a package to Z without moving. The person can hand off the package to one of the runners illustrated at each intersection, who can then hand off the package to another runner at an adjacent intersection, etc., until the package is delivered.

There are many different ways we could find a route through this network of paths; for instance:

• Because we have a picture (a network diagram), we can just trace out the route and tell each runner where they should go and to whom they should hand off the package.

• We can have one runner, say at the beginning, wander down every possible path, recording where they end up, and use this information to tell each of the runners stationed at an

intersection where to take the package when they receive it.

Note

Some routing systems do, in fact, send a packet (called an explorer) through every path in the network. The originator, Y in this illustration, can then choose a path through the network. This is called source routing.

We are going to use a slightly different method, though, because we would prefer not to have any single runner move farther away from their intersection than an immediately adjacent intersection. Runner A should only ever go to B and C, runner C should only ever go to A and D, etc.

Each runner is given a way to record and copy notes—a pad of note paper and a copying machine, in effect. Once equipped, every runner will carry a copy of what they know about the network to the intersections they can reach. There are two different versions of this information.

For distance-vector routing protocols, the runner carries information about destinations they can reach and the cost, from their perspective of reaching that destination. In Figure 3-11, assuming the cost is the hop count:

• Runner F tells E they know how to reach Z, which is directly connected.

• Runner E tells D it knows how to reach Z with a cost of 1.

• Runner D tells C and B it can reach Z with a cost of 2.

• Runner C tells A it can reach Z with a cost of 3.

• Runner A tells B it can reach Z with a cost of 4.

At the end of this process, B will know it can reach Z in two different ways: through D with a cost of 2 and through A with a cost of 4. Because the path through D is the shorter path (and therefore cannot be a loop), the runner at B will give the package to D when they receive a package from Y.

This same process can be performed for the path from Z back to Y, and for any other pair of points in the networks. In network engineering, this algorithm is called Bellman-Ford, after the names of its inventors. A variant of Bellman-Ford is called the diffusing update algorithm (DUAL).

For link-state protocols, the runner carries information about who the neighboring intersections are and any directly

connected destinations. In Figure 3-11:

• Runner A tells runners B and C their adjacent intersections (neighbors) are B and C.

• Runner B tells runners A and D their neighbors are A and D, and they can reach Y.

• Runner C tells runners A and D their neighbors are A and D.

• Runner D tells runners B, C, and E their neighbors are B, C, and E.

• Runner E tells runners E and F their neighbors are D and F.

• Runner F tells runner E it has one neighbor, E, and it can reach Z.

Each runner keeps a copy of this information on their pads; this is called the Link State Database (LSDB). Using the information in their LSDB, each runner can use an algorithm called

Dijkstra’s Shortest Path First to find the lowest cost (in this case least number of hops) through the network. Dijkstra’s Shortest Path First is often called Dijkstra or Shortest Path First (SPF).

The graph of the network resulting from running SPF is called the Shortest Path Tree (SPT).

Essentially, runner B can see it is connected to D, D is connected to E, E is connected to F, and F is connected to the destination they are trying to reach, Z.

It might seem a little odd that the runners tell a neighbor they can reach that neighbor. Why does runner A care B can reach A? There are two reasons:

• It is simpler to implement a link-state routing protocol when every router tells all its neighbors the same thing.

• If A knows B can reach A, then A can be certain the link (or path) between A and B is working correctly, so packages can be carried over the path. This is called the back-link check.

For path-vector protocols:

• Runner F tells E they can reach Z.

• Runner D tells C and B they can reach Z via the path [F].

• Runner C tells A they can reach Z via the path [D,E,F].

• Runner A tells B they can reach Z via the path [C,D,E,F].

Runner B now has two paths, neither of which can be a loop because they pass through different nodes to reach the destination. B can choose one of the two paths based on local policy, such as “choose the path with the shortest hop count.”

Some common routing protocols are

• Routing Information Protocol (RIP), which has two versions: RIPv1 and RIPv2. RIP is a distance-vector protocol and uses the Bellman-Ford method of finding the routes through a network.

• Enhanced Interior Gateway Routing Protocol (EIGRP), which is a distance-vector protocol using the DUAL method of finding the routes through the network.

• Open Shortest Path First (OSPF), which has two versions: OSPFv2 and OSPFv3. OSPF is (surprisingly enough!) a link-state protocol and uses Dijkstra’s SPF to find routes through the network.

• Intermediate System to Intermediate System (IS-IS), which uses Dijkstra’s SPF to find routes through the network.

• Border Gateway Protocol (BGP), currently in version 4 (BGPv4), which is a path-vector protocol. BGPv4 currently provides routing information for the global Internet.

Metrics

Up to this point the illustrations have all used hop count as the only metric. Most routing protocols use some more sophisticated metrics, such as

• RIP uses the hop count as its metric.

• EIGRP uses the bandwidth of the slowest link in the path as one element of its metric.

• EIGRP uses the sum of the delays across every link in the path as one element of its metric.

• OSPF uses the sum of the inverse of the bandwidths of every link in the path.

• IS-IS uses a metric like the hop count by default, but most implementations can be configured to use the sum of the inverse of the bandwidths of every link in the path.

• BGP uses the operator’s preference on how packets should exit the provider’s network as one metric. This is called the local preference.

• BGP uses the operator’s preference on how packets should enter the provider’s network as one metric. This is called the multiple exit discriminator.

• BGP uses the number of networks (a network is close to an autonomous system, or AS) a packet will pass through to reach a given destination as a metric. This is called the AS Path Length.