The Autonomous System

Previous

1.1.- The Autonomous System

Figure 1 shows a sample AS. The rectangle H1 indicates a host connected to router RT12 through a SLIP connection. RT12 is therefore advertising a host route. Lines between routers indicate physical P2P networks. Only the P2P network between routers RT6 and RT10 has assigned interface addresses. Router RT5 and RT7 have BGP connections to other ASs.

A cost is associated with the output side of each router interface being configurable by the system administrator. The lower the cost, the more likely the interface is to be used to forward data traffic.

The directed graph resulting from the AS in figure 1 is shown in figure 2. Arcs between routers and routers and between routers and networks are labelled with the cost of the corresponding router output interface. Arcs leading from networks to routers (no from routers to networks) always have a cost of zero. There are no arcs between networks and networks; they link always together through one or more connecting router(s).

The LS-database of each router is pieced together from the LSAs generated by itself and the other routers. For example, figure 3 shows two of this LSAs. The RT12's router-LSA and the N9's network-LSA. These are two different types of LSA. The Router-LSA shows arcs labelled from the router to its neighboring routers and networks. Network-LSA shows arcs labelled from the network to its attached routers. Network-LSAs are generated by the Designated Router for the network.

Based on its LS-database graph (created previously by piecing together all those LSAs) each router generates its routing table by calculating first a tree of shortest paths with the router itself as root of the tree. The shortest-path tree for router RT6 is depicted in figure 4. The tree gives the entire path to any destination network or host. However, only the next hop to the destination is used in the forwarding process. Note also that the best route to any router has also been calculated.

Reading the router RT6's tree of shortest path we have:

RT6 connects directly with routers RT5, RT3 and RT10 with costs 6, 6 and 7, respectively.
Because interface Ib on router RT10 is addresed, then router RT6 connects to it as stub network with a cost of 7 (addresed interfaces on P2P networks are considered stub networks for OSPF).
From router RT5, router RT6 connects to network N12, N13 and N14 with costs 8, 8 and 8, respectively.
From router RT3, router RT6 connects to networks N4 with cost 2 and N3 with cost 1.
From network N3, router RT6 connects to router RT4, RT2 and RT1 with no cost (cost from networks to their attached routers are always zero).
From router RT2, router RT6 connects to network N2 with cost 3.
From router RT1, router RT6 connects to network N1 with cost 3.
From router RT10, router RT6 connects to network N8 with a cost of 3 and through this network with router RT11 with no additional cost. Also, from router RT10, router RT6 connects with its own address interface (Ia) with a cost of 5, and with network N6 with a cost of 1.
From router RT11, router RT6 connects to network N9 with cost 1 and from this, with routers RT9 and RT12 with no additional cost. From router RT9 connects to network N11 with a cost of 3 and with network N10 and host H1 with costs 2 and 10 respectively.
From network N6, router RT6 connects to router RT7 with no cost, and from this, to networks N12 and N15 with costs of 2 and 9 respectively; and to router RT8 with no cost, and from this, to networks N7 with cost of 4.

Note: when you are building the shortest path tree for say, router X, observe that the only direct links that you must include between routers, are those from the own router X and its direct neighbors. Except for these direct links between routers, no other direct link between routers should appear in the diagram. For example, the shortest path tree of the router RT6 above, contains the direct links from router RT6 to its neighbors, RT3, RT5 and RT10. Except for these 3 links (neighbor's link), the rest of the links are from routers to networks and from networks to routers, but never from routers to routers. In the shortest-path tree diagram above, adding direct links from router RT5 to routers RT4 and RT7, or even to RT6 itself, is an error. L.B.

From the tree of shortest path the router constructs its own routing table to every network. For router RT6 the table is shown below, in table 1.1.1.

The routing table tells the router the destination network, the next hop (router) to be used to forward packets to this network, and the total cost to reach it. This, for destination networks within the AS. For external networks, like N12, N13, N14 and N15, the routing table points out to the router advertising these external networks; i.e., RT5 for networks N12, N13 and N14, and router RT7 for networks N12 and N15. Observe also that there is a separate route for each end of a numbered P2P network, like the serial line between routers RT6 and RT10.

Then, OSPF process that seems to be very complicated is really very easy. Every router using its own LSAs and LSAs from other routers builds its LS-database. When the database is done, it builds a tree of shortest path to networks and routers, with itself as the root of the tree, using the information taken from the database. When the tree is done, it builds its own routing table from information taken from the tree. Finally, it uses the routing table to forward packets to any destination. This table is the same (unique) routing table that you could configure statically using a specific tool, like iproute2 in Linux, or the command ip route in Cisco.

Note: In GateD (a routing protocol daemon for Linux, that runs OSPF), this table is built independently on a separate object; then resulting values are downloaded by the software to the current kernel routing table. L.B.

But, with OSPF, the routing configuration process is done dynamically. When topology changes in someplace, routers affected by this change flood new topology information using LSAs. These advertisements are received by other routers and they recalculate their own LS-databases and flood new LSAs to their neighbors. Finally, the process converges when LSA exchanges permit to all routers to have a new LS-database. When LS-databases are ready, each router creates its own routing table, building again the tree of shortest path and from this, the routing table.

What's the problem with OSPF? Well, the exchange information process between routers is really complex and it takes more than a half of the RFC specification to be explained. Such explanation is very hard and one, sooner than later, begin to feel lost. Solution is then trying to concentrate on basic concepts leaving implementation details to one side.

Previous

Content

Next