Connected: An Internet Encyclopedia
2.1. The shortest-path tree

Up: Connected: An Internet Encyclopedia
Up: RFC 1583
Up: 2. The Topological Database
Prev: 2. The Topological Database
Next: 2.2. Use of external routing information

### 2.1. The shortest-path tree

2.1. The shortest-path tree

When no OSPF areas are configured, each router in the Autonomous System has an identical topological database, leading to an identical graphical representation. A router generates its routing table from this graph by calculating a tree of shortest paths with the router itself as root. Obviously, the shortest- path tree depends on the router doing the calculation. The shortest-path tree for Router RT6 in our example is depicted in Figure 5.

```                 +
| 3+---+                     N12      N14
N1|--|RT1|\ 1                    \ N13 /
|  +---+ \                     8\ |8/8
+         \ ____                 \|/
/    \   1+---+8    8+---+6
*  N3  *---|RT4|------|RT5|--------+
\____/    +---+      +---+        |
+         /   |                  |7         |
| 3+---+ /    |                  |          |
N2|--|RT2|/1    |1                 |6         |
|  +---+    +---+8            6+---+        |
+           |RT3|--------------|RT6|        |
+---+              +---+        |
|2               Ia|7         |
|                  |          |
+---------+             |          |
N4                  |          |
|          |
|          |
N11                         |          |
+---------+                     |          |
|                          |          |    N12
|3                         |          |6 2/
+---+                        |        +---+/
|RT9|                        |        |RT7|---N15
+---+                        |        +---+ 9
|1                   +     |          |1
_|__                  |   Ib|5       __|_
/    \      1+----+2   |  3+----+1   /    \
*  N9  *------|RT11|----|---|RT10|---*  N6  *
\____/       +----+    |   +----+    \____/
|                    |                |
|1                   +                |1
+--+   10+----+                N8              +---+
|H1|-----|RT12|                                |RT8|
+--+SLIP +----+                                +---+
|2                                    |4
|                                     |
+---------+                            +--------+
N10                                    N7

Figure 2: A sample Autonomous System
```

```                                **FROM**

|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|
|1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|N3|N6|N8|N9|
----- ---------------------------------------------
RT1|  |  |  |  |  |  |  |  |  |  |  |  |0 |  |  |  |
RT2|  |  |  |  |  |  |  |  |  |  |  |  |0 |  |  |  |
RT3|  |  |  |  |  |6 |  |  |  |  |  |  |0 |  |  |  |
RT4|  |  |  |  |8 |  |  |  |  |  |  |  |0 |  |  |  |
RT5|  |  |  |8 |  |6 |6 |  |  |  |  |  |  |  |  |  |
RT6|  |  |8 |  |7 |  |  |  |  |5 |  |  |  |  |  |  |
RT7|  |  |  |  |6 |  |  |  |  |  |  |  |  |0 |  |  |
*   RT8|  |  |  |  |  |  |  |  |  |  |  |  |  |0 |  |  |
*   RT9|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |0 |
T  RT10|  |  |  |  |  |7 |  |  |  |  |  |  |  |0 |0 |  |
O  RT11|  |  |  |  |  |  |  |  |  |  |  |  |  |  |0 |0 |
*  RT12|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |0 |
*    N1|3 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
N2|  |3 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
N3|1 |1 |1 |1 |  |  |  |  |  |  |  |  |  |  |  |  |
N4|  |  |2 |  |  |  |  |  |  |  |  |  |  |  |  |  |
N6|  |  |  |  |  |  |1 |1 |  |1 |  |  |  |  |  |  |
N7|  |  |  |  |  |  |  |4 |  |  |  |  |  |  |  |  |
N8|  |  |  |  |  |  |  |  |  |3 |2 |  |  |  |  |  |
N9|  |  |  |  |  |  |  |  |1 |  |1 |1 |  |  |  |  |
N10|  |  |  |  |  |  |  |  |  |  |  |2 |  |  |  |  |
N11|  |  |  |  |  |  |  |  |3 |  |  |  |  |  |  |  |
N12|  |  |  |  |8 |  |2 |  |  |  |  |  |  |  |  |  |
N13|  |  |  |  |8 |  |  |  |  |  |  |  |  |  |  |  |
N14|  |  |  |  |8 |  |  |  |  |  |  |  |  |  |  |  |
N15|  |  |  |  |  |  |9 |  |  |  |  |  |  |  |  |  |
H1|  |  |  |  |  |  |  |  |  |  |  |10|  |  |  |  |

Figure 3: The resulting directed graph

Networks and routers are represented by vertices.
An edge of cost X connects Vertex A to Vertex B iff
the intersection of Column A and Row B is marked
with an X.
```

```                     **FROM**                       **FROM**

|RT12|N9|N10|H1|             |RT9|RT11|RT12|N9|
*  --------------------          *  ----------------------
*  RT12|    |  |   |  |          *   RT9|   |    |    |0 |
T    N9|1   |  |   |  |          T  RT11|   |    |    |0 |
O   N10|2   |  |   |  |          O  RT12|   |    |    |0 |
*    H1|10  |  |   |  |          *    N9|   |    |    |  |
*                                *

Figure 4: Individual link state components

Networks and routers are represented by vertices.
An edge of cost X connects Vertex A to Vertex B iff
the intersection of Column A and Row B is marked
with an X.
```

The tree gives the entire route 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. For the processing of external data, we note the next hop and distance to any router advertising external routes. The resulting routing table for Router RT6 is pictured in Table 2. Note that there is a separate route for each end of a numbered serial line (in this case, the serial line between Routers RT6 and RT10).

Routes to networks belonging to other AS'es (such as N12) appear as dashed lines on the shortest path tree in Figure 5. Use of this externally derived routing information is considered in the next section.

Next: 2.2. Use of external routing information

Connected: An Internet Encyclopedia
2.1. The shortest-path tree