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

Top: Connected: An Internet Encyclopedia
Up: Requests For Comments
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

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|   |    |    |  |
               *                                *
                    RT12's router links            N9's network links
                       advertisement                  advertisement

                      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
RFC 1583 - 2.1. The shortest-path tree