2 - 3 - 6 - 8 - A - B - C - D - E - F - G - H - I - L - M - N - O - P - Q - R - S - T - U - V - W - X
tree
Click on the red underlined text to get to the source
... topological database, each router constructs a tree of shortest
paths with itself as root. This shortest-path tree ...
... tree of shortest
paths with itself as root. This shortest-path tree gives the
route to each destination ...
... Autonomous System. Externally
derived routing information appears on the tree as leaves.
OSPF ...
... The shortest-path tree ...
... router generates its
routing table from this graph by calculating a tree of shortest
paths with the router itself as root ...
... router itself as root. Obviously, the shortest-
path tree depends on the router doing the calculation. The
shortest-path tree ...
... tree depends on the router doing the calculation. The
shortest-path tree for Router RT6 in our example is depicted in
Figure 5.
...
... 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
...
... algorithm, and its discussion is postponed until we consider the
tree-building process in more detail.
With equal cost multipath, a router ...
... When interface costs vary based on TOS, a separate shortest path
tree is calculated for each TOS (see Section 2.1). In addition,
external costs can vary based on TOS ...
... networks
external to the area. After the SPF tree is calculated for the
area, routes to all other networks are calculated by examining
...
... Routers RT3 and RT4 as an example, the procedure
goes as follows: They first calculate the SPF tree for the
backbone. This gives the distances to all other area border
routers ...
... database each router
calculates a shortest-path tree, with itself as root. This
shortest-path tree ...
... tree, with itself as root. This
shortest-path tree in turn yields a routing table for the protocol.
...
... link state
advertisements, routers incapable of certain functions can be
avoided when building the shortest path tree. An example of
this is the TOS routing ...
... forward packets. Virtual links are brought up and down through
the building of the shortest-path trees for the Transit area.
List of external routes
...
... link becomes active,
through the building of the shortest path tree for Area 2, it
becomes an interface to the backbone ...
... Autonomous System, yet external to the area.
Shortest-path tree
The shortest-path tree for the area, with this router ...
... data traffic that
neither originates nor terminates in the area itself. This
parameter is calculated when the area's shortest-path tree is
built (see Section 16.1, and is used as an input to a subsequent
step of the routing table ...
... router. The advertisement is discovered during the shortest-
path tree calculation (see Section 16.1). Multiple
advertisements may reference the destination, however a tie-
...
... (2) The intra-area routes are calculated by building the shortest-
path tree for each attached area. In particular, all routing
table entries whose Destination Type is "area border router ...
... area border router" are
calculated in this step. This step is described in two parts.
At first the tree is constructed by only considering those links
between routers ...
... networks. Then the stub networks
are incorporated into the tree. During the area's shortest-path
tree calculation, the area's TransitCapability is also
...
... are incorporated into the tree. During the area's shortest-path
tree calculation, the area's TransitCapability is also
calculated for later use in Step 4.
...
... Calculating the shortest-path tree for an area ...
... with an area (called hereafter Area A). A router calculates the
shortest-path tree using itself as the root.[21] The formation
...
... root.[21] The formation
of the shortest path tree is done here in two stages. In the
first stage, only links between routers ...
... networks are
considered. Using the Dijkstra algorithm, a tree is formed from
this subset of the link state database. In the second stage,
...
... this subset of the link state database. In the second stage,
leaves are added to the tree by considering the links to stub
networks ...
... that is closest to the root are guaranteed to be shortest; this
vertex is added to the shortest-path tree, removed from the
candidate ...
... The following steps describe the algorithm in detail. Remember
that we are computing the shortest path tree for Area A. All
references to link state database lookup ...
... data structures. Clear the list
of candidate vertices. Initialize the shortest-path tree to
only the root (which is the router ...
... Set Area A's TransitCapability to FALSE.
(2) Call the vertex just added to the tree vertex V. Examine
the link state advertisement associated with vertex V. This
...
... 22]
(c) If vertex W is already on the shortest-path tree,
examine the next link in the advertisement.
...
... (3) If at this step the candidate list is empty, the shortest-
path tree (of transit vertices) has been completely built
and this stage of the procedure terminates. Otherwise,
choose the vertex belonging to the candidate ...
... candidate list that is
closest to the root, and add it to the shortest-path tree
(removing it from the candidate ...
... links advertisement) that
points back to the root of the shortest-path tree;
equivalently, this is the interface that points back to
...
... interface that points back to
ABR's parent vertex on the shortest-path tree (similar to
the calculation in Section 16.1.1).
...
...
The stub networks are added to the tree in the procedure's
second stage. In this stage, all router vertices are again
...
... The specification does not require that the above two stage
method be used to calculate the shortest path tree. However, if
another algorithm is used, an identical tree ...
... shortest path tree. However, if
another algorithm is used, an identical tree must be produced.
For this reason, it is important to note that links between
...
... transit vertices must be bidirectional in ordered to be included
in the above tree. It should also be mentioned that more
efficient algorithms exist for calculating the tree ...
... tree. It should also be mentioned that more
efficient algorithms exist for calculating the tree; for
example, the incremental SPF algorithm described in [BBN ...
... to the destination is discovered. This can happen in either
stage of the shortest-path tree calculation (see Section
16.1). In stage 1 of the shortest-path tree calculation a
...
... stage of the shortest-path tree calculation (see Section
16.1). In stage 1 of the shortest-path tree calculation a
shorter path is found as the destination is added to the
...
... next hops to use for the destination may be
recalculated several times during the shortest-path tree
calculation, as shorter and shorter paths are discovered.
In the end, the destination ...
... N1 into Area 1.
After the shortest-path tree has been calculated for the
backbone in Section 16.1, Router ...
... TOS are omitted from the calculation.
Calculating the shortest-path tree (Section 16.1).
Routers that do not support TOS ...
... TOS-based routing should be
omitted from the shortest-path tree calculation. These
routers are identified as those having the T-bit ...
... advertisements be examined when adding the stub networks to
the tree. In particular, if the T-bit is reset in the
calculating router ...
... router links advertisement, it does
not run the shortest-path tree calculation for non-zero TOS
...
... By keeping more information in the routing table, it is possible for an implementation to recalculate the shortest path tree only for a single area. In fact, there are incremental algorithms that allow an implementation to recalculate only a portion of a single area's shortest path tree ...
... routing table, it is possible for an implementation to recalculate the shortest path tree only for a single area. In fact, there are incremental algorithms that allow an implementation to recalculate only a portion of a single area's shortest path tree ...
... Strictly speaking, because of equal-cost multipath, the algorithm does not create a tree. We continue to use the "tree" terminology because that is what occurs most often in the existing literature. ...
... algorithm does not create a tree. We continue to use the "tree" terminology because that is what occurs most often in the existing literature. ...
... From the link state database, each router constructs a shortest path
tree with itself as root. This yields a routing table (see Section
...
... virtual links (i.e.,
is a transit area). This discovery is done during the
calculation of Area A's shortest-path tree (see Section
16.1).
...