1 - 2 - 3 - 6 - 8 - A - B - C - D - E - F - G - H - I - J - L - M - N - O - P - Q - R - S - T - U - V - W - X
routing
Click on the red underlined text to get to the source
... Gateway
Protocol (IGP). This means that it distributes routing information
between routers belonging to a single Autonomous System ...
... link-state technology. This is a departure
from the Bellman-Ford base used by traditional internet routing
protocols.
The OSPF protocol ...
... , including explicit support for IP subnetting,
TOS-based routing and the tagging of externally-derived routing
information. OSPF also provides for the authentication ...
... subnetting,
TOS-based routing and the tagging of externally-derived routing
information. OSPF also provides for the authentication of routing ...
... routing
information. OSPF also provides for the authentication of routing
updates, and utilizes IP multicast when sending/receiving ...
... In addition, much work has been done to produce a protocol that responds
quickly to topology changes, yet involves small amounts of routing
protocol traffic.
...
... they transit the Autonomous System. OSPF is a dynamic routing protocol.
It quickly detects topological changes in the AS (such as router
interface ...
... to each
destination in the Autonomous System. Externally derived routing
information appears on the tree as leaves.
...
... of an area is hidden from the rest of the
Autonomous System. This information hiding enables a significant
reduction in routing traffic. Also, routing within the area is
...
... reduction in routing traffic. Also, routing within the area is
determined only by the area's own topology, lending the area protection
...
... determined only by the area's own topology, lending the area protection
from bad routing data. An area is a generalization of an IP subnetted
network.
...
... trusted routers can participate in the Autonomous System's routing. A
variety of authentication schemes can be used; a single authentication ...
... authentication than others.
Externally derived routing data (e.g., routes learned from the Exterior
Gateway Protocol (EGP)) is passed transparently throughout the
...
... A group of routers exchanging routing information via a common
routing protocol. Abbreviated as AS ...
... Internal Gateway Protocol
The routing protocol spoken by the routers belonging to an
Autonomous system ...
... interface has state information associated with it, which is
obtained from the underlying lower level protocols and the routing
protocol itself. An interface to a network has associated with it a
...
... A relationship formed between selected neighboring routers for the
purpose of exchanging routing information. Not every pair of
neighboring routers become adjacent.
...
... router's interfaces and adjacencies. Each link
state advertisement is flooded throughout the routing domain. The
collected link state advertisements ...
... multi-access network. This in turn
reduces the amount of routing protocol traffic and the size of the
topological database ...
...
OSPF is an SPF-based routing protocol. Such protocols are also referred
to in the literature as link-state or distributed-database ...
...
The first SPF-based routing protocol was developed for use in the
ARPANET packet switching network. This protocol is described in
...
... Modifications to this protocol were proposed in [Perlman]. These
modifications dealt with increasing the fault tolerance of the routing
protocol through, among other things, adding a checksum to the link
state advertisements (thereby detecting database ...
... link
state advertisements (thereby detecting database corruption). The paper
also included means for reducing the routing traffic overhead in an
...
... has also been proposed for use as an ISO IS-IS
routing protocol. This protocol is described in [DEC]. The protocol
includes methods ...
... DEC]. The protocol
includes methods for data and routing traffic reduction when operating
over broadcast ...
... OSPF protocol. The Designated Router concept has been greatly
enhanced to further reduce the amount of routing traffic required.
Multicast capabilities are utilized for additional ...
... traffic required.
Multicast capabilities are utilized for additional routing bandwidth
reduction. An area routing ...
... routing bandwidth
reduction. An area routing scheme has been developed enabling
information hiding/protection/reduction. Finally, the algorithm has
...
... cost, the more likely the interface is to be used to forward data
traffic. Costs are also associated with the externally derived routing
data (e.g., the EGP-learned routes).
...
... networks to routers always have cost 0; they are
significant nonetheless. Note also that the externally derived routing
data appears on the graph as stubs.
...
... 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 ...
... , 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 ...
... dashed lines on the shortest path tree in Figure 5. Use of this
externally derived routing information is considered in the next
section.
...
... Use of external routing information ...
... After the tree is created the external routing information is examined.
This external routing information may originate from another routing
protocol ...
... created the external routing information is examined.
This external routing information may originate from another routing
protocol such as EGP, or be statically configured (static routes).
...
... routing information is examined.
This external routing information may originate from another routing
protocol such as EGP, or be statically configured (static routes).
Default routes can also be included as part of the ...
... Default routes can also be included as part of the Autonomous System's
external routing information.
External routing information ...
... routing information.
External routing information is flooded unaltered throughout the AS. In
our example, all the routers ...
... greater than the cost of any path internal to the AS. Use of Type 2
external metrics assumes that routing between AS'es is the major cost of
routing a packet, and eliminates the need for conversion of external
...
... external metrics assumes that routing between AS'es is the major cost of
routing a packet, and eliminates the need for conversion of external
costs to internal link state metrics.
...
... Router RT6, which is better than router RT5's 14
(6+8). Table 3 shows the entries that are added to the routing table
when external routes are examined:
...
... Router RTX. Suppose
further that RTX does not participate in OSPF routing, but does exchange
EGP information with the AS boundary ...
... router RT6 could become a route server, gaining
external routing information through a combination of static
configuration and external routing protocols. RT6 would then start ...
... external routing information through a combination of static
configuration and external routing protocols. RT6 would then start
advertising itself as an AS boundary ...
... header. This means that, for any destination, there can
potentially be multiple routing table entries, one for each IP TOS.
...
... TOS 0 path (see Appendix C), eliminating the need to calculate non-
zero TOS paths. This can be used to conserve routing table space and
processing resources in the router. These TOS ...
... networks, is called an area. Each area runs a
separate copy of the basic SPF routing algorithm. This means that each
area has its own topological database and corresponding graph, as
...
... detailed topology external to the area. This isolation of knowledge
enables the protocol to effect a marked reduction in routing traffic as
compared to treating the entire Autonomous System ...
... area topological databases.
Routing in the Autonomous System takes place on two levels, depending on
whether the source and destination ...
... destination of a packet reside in the same area
(intra-area routing is used) or different areas (inter-area routing is
...
... intra-area routing is used) or different areas (inter-area routing is
used). In intra-area routing ...
... routing is
used). In intra-area routing, the packet is routed solely on
information obtained within the area; no routing information obtained
...
... intra-area routing, the packet is routed solely on
information obtained within the area; no routing information obtained
from outside the area can be used. This protects intra-area routing ...
... routing information obtained
from outside the area can be used. This protects intra-area routing
from the injection of bad routing information. We discuss inter-area ...
... intra-area routing
from the injection of bad routing information. We discuss inter-area
routing in Section 3.2.
...
... from the injection of bad routing information. We discuss inter-area
routing in Section 3.2.
...
... costs are the intra-area distances between the two routers. The routing
protocol traffic that flows along the virtual link ...
...
The backbone is responsible for distributing routing information between
areas. The backbone itself has all of the properties of an area. The
...
... Inter-area routing ...
...
When routing a packet between two areas the backbone is used. The path
that the packet will travel can be broken up into three contiguous
...
...
Looking at this another way, inter-area routing can be pictured as
forcing a star configuration on the Autonomous System, with the backbone ...
... Before the introduction of areas, the only OSPF routers having a
specialized function were those advertising external routing
information, such as router RT5 in Figure 2. When the AS is split into
...
... interfaces also belong to this
category. These routers run a single copy of the basic routing
algorithm.
Area border routers
...
... routers
A router that exchanges routing information with routers belonging
to other Autonomous Systems ...
... database for the Area 1. The
figure completely describes that area's intra-area routing. It also
shows the complete view of the internet for the two internal routers ...
... RT3, RT4, RT7, RT10 and RT11 are area border routers. As
routers RT3 and RT4 did above, they have condensed the routing
information of their attached areas for distribution via the backbone;
these are the dashed stubs that appear in Figure 8. Remember that the
...
... OSPF allows certain
areas to be configured as "stub areas". External advertisements are not
flooded into/throughout stub areas; routing to AS external destinations
...
...
In order to take advantage of the OSPF stub area support, default
routing must be used in the stub area. This is accomplished as follows.
One or more of the stub area's area border routers must advertise a
...
... . When an area
becomes partitioned, each component simply becomes a separate area. The
backbone then performs routing between the new areas. Some destinations
reachable via intra-area ...
... destinations
reachable via intra-area routing before the partition will now require
inter-area ...
... before the partition will now require
inter-area routing.
In the previous section, an area was described as a list of address ...
... AS will then have multiple regions of the same color
(Area ID). The routing in the Autonomous System will continue to
function as long as these regions of same color are connected by the
...
...
A separate copy of OSPF's basic routing algorithm runs in each area.
Routers having interfaces to multiple areas run multiple copies of the
...
... having interfaces to multiple areas run multiple copies of the
algorithm. A brief summary of the routing algorithm follows.
When a router ...
... When a router starts, it first initializes the routing protocol data
structures. The router then waits for indications from the lower-level
...
... routers should become adjacent.
Adjacencies control the distribution of routing protocol packets.
Routing protocol packets are sent and received only on adjacencies. In
particular, distribution of topological ...
...
Adjacencies control the distribution of routing protocol packets.
Routing protocol packets are sent and received only on adjacencies. In
particular, distribution of topological database updates proceeds along
...
... with itself as root. This shortest-path tree in turn yields a routing
table for the protocol.
...
... Inter-area routing ...
... The previous section described the operation of the protocol within a
single area. For intra-area routing, no other routing information is
pertinent. In order to be able to route ...
... single area. For intra-area routing, no other routing information is
pertinent. In order to be able to route to destinations ...
... destinations outside of the
area, the area border routers inject additional routing information into
the area. This additional information is a distillation of the rest of
the Autonomous System ...
... can
flood this information throughout the AS. This external routing
information is distributed verbatim to every participating router.
There is one exception: external routing information ...
... routing
information is distributed verbatim to every participating router.
There is one exception: external routing information is not flooded into
"stub" areas (see Section 3.6).
...
... "stub" areas (see Section 3.6).
To utilize external routing information, the path to all routers
advertising external information must be known throughout the AS ...
... Routing protocol packets ...
... fragmentation should be avoided whenever possible.
Routing protocol packets should always be sent with the IP TOS field set
...
... IP TOS field set
to 0. If at all possible, routing protocol packets should be given
preference over regular IP data traffic ...
...
As mentioned above, OSPF routing packets (with the exception of Hellos)
are sent only over adjacencies. Note that this means that all protocol
packets travel a single IP ...
... broadcasts, this can lead to the synchronization of
routing packets (which should be avoided). If timers cannot be
implemented to avoid drift, small random amounts should be added
...
... capability mismatch prevents a neighbor relationship from forming). An
example of this is the external routing capability (see below).
Other capabilities can be negotiated during the database ...
... neighbors.
The routing table build process can also be affected by the
presence/absence of optional capabilities. For example, since the
optional capabilities are reported in link state advertisements ...
... incapable of certain functions can be avoided when building the shortest
path tree. An example of this is the TOS routing capability (see
below).
...
... A.2 for more information.
External routing capability
Entire OSPF areas can be configured as "stubs" (see Section 3.6).
...
... based on IP Type of Service. However, to save routing table space
and processing resources, an OSPF router can be configured to ignore
...
... routers. A virtual link uses the intra-
area routing of its transit area to forward packets. Virtual links
are brought up and down through the building of the shortest-path
...
... Autonomous System,
that have been gained either through direct experience with another
routing protocol (such as EGP), or through configuration
information, or through a combination of the two (e.g., dynamic
...
... advertisements have been self originated.
The routing table
Derived from the topological database. Each destination ...
... The area data structure contains all the information used to run the
basic routing algorithm. Remember that each area maintains its own
topological database. Router interfaces ...
... different areas.
External routing capability
Whether AS external advertisements will be flooded into/throughout
...
... AS external
advertisements are excluded from the area, the area is called a
"stub". Internal to stub areas, routing to external destinations
will be based solely on a default summary route ...
... creates adjacencies between neighboring routers for the purpose of
exchanging routing information. Not every two neighboring routers will
become adjacent. This section covers the generalities involved in
...
...
In an SPF-based routing algorithm, it is very important for all routers'
topological databases ...
... network has a Designated Router. The Designated
Router performs two main functions for the routing protocol:
o The Designated Router ...
... role, letting the Designated Router do more of the work.
This cuts down on the amount of local routing traffic. See Section 13.3
for more information.
...
... routers if they are adjacent. The graph of adjacencies describes
the flow of routing protocol packets, and in particular Link State
Updates, through the Autonomous System ...
...
This section discusses the general processing of routing protocol
packets. It is very important that the router topological databases ...
... router topological databases
remain synchronized. For this reason, routing protocol packets should
get preferential treatment over ordinary data packets, both in sending
...
... and receiving.
Routing protocol packets are sent along adjacencies only (with the
exception of Hello packets, which are used to discover the adjacencies).
This means that all protocol packets travel a single IP ...
... virtual links.
All routing protocol packets begin with a standard header. The sections
below give the details on how to fill in and verify this standard
...
...
When a router sends a routing protocol packet, it fills in the fields of
that standard header as follows. For more details on the header format ...
... link does
have an interface IP address (discovered during the routing table build
process) which is used as the IP source when sending packets ...
... interface can be considered to belong to the area that contains
the attached network. All routing protocol packets originated by the
router over this interface are labelled with the ...
... interface. This appears as the
IP source address in all routing protocol packets originated over
this interface. Interfaces ...
... The Area ID to which the attached network belongs. All routing
protocol packets originating from the interface are labelled with
this Area ID ...
... inserted directly into the OSPF header when originating routing
protocol packets, and there could be a separate password for each
network ...
... virtual links, the neighbor IP
address is learned during the routing table build process (see
Section 15).
...
... backbone). The setting of the E-bit found in the Hello Packet's
option field must match this area's external routing capability. If AS
external advertisements are not flooded into/throughout the area (i.e,
...
... The Routing Table Structure ...
...
The routing table data structure contains all the information necessary
to forward an IP data ...
... to forward an IP data packet toward its destination. Each routing table
entry describes the collection of best paths to a particular
destination. When forwarding an ...
... entry describes the collection of best paths to a particular
destination. When forwarding an IP data packet, the routing table entry
providing the best match for the packet's IP destination ...
... ________________________________________
The matching routing table entry then provides the next hop towards the
packet's destination ...
... IP destinations (although any other matching
entry is a better match). Finding the routing table entry that best
matches an IP destination ...
... destination is further described in Section 11.1.
There is a single routing table in each router. Two sample routing
tables are described in Sections 11.2 and 11.3. The building of the
...
... There is a single routing table in each router. Two sample routing
tables are described in Sections 11.2 and 11.3. The building of the
routing table is discussed in Section 16.
...
... in each router. Two sample routing
tables are described in Sections 11.2 and 11.3. The building of the
routing table is discussed in Section 16.
The rest of this section defines the fields found in a routing table ...
... routing table is discussed in Section 16.
The rest of this section defines the fields found in a routing table
entry. The first set of fields describes the routing table entry's
...
... The rest of this section defines the fields found in a routing table
entry. The first set of fields describes the routing table entry's
destination.
...
... other destinations are used solely as intermediate steps in the
routing table build process.
Network ...
... routers
originate summary link advertisements. These routing table
entries are used when calculating the inter-area routes (see
...
... entries are used when calculating the inter-area routes (see
Section 16.2). These routing table entries may also be
associated with configured virtual links.
...
... AS external link advertisements. These
routing table entries are used when calculating the AS external
routes (see Section 16.4).
...
... Type of
Service and the OSPF area to which the paths belong. This means that
there may be multiple routing table entries for the same destination,
depending on the values of the next two fields.
...
... This field indicates the area whose link state information has led
to the routing table entry's collection of paths. This is called
the entry's associated area. For sets of AS external paths, this
...
... destinations of type "area border
router", there may be separate sets of paths (and therefore separate
routing table entries) associated with each of several areas. This
will happen when two area border routers share multiple areas in
...
... is kept.
The rest of the routing table entry describes the set of paths to the
destination. The following fields pertain to the set of paths as a
whole. In other words, each one of the paths contained in a ...
... entry describes the set of paths to the
destination. The following fields pertain to the set of paths as a
whole. In other words, each one of the paths contained in a routing
table entry is of the same path-type and cost (see below).
Path-type
...
... When multiple paths of equal path-type and cost exist to a destination
(called elsewhere "equal-cost" paths), they are stored in a single
routing table entry. Each one of the "equal-cost" paths is
distinguished by the following fields:
...
... Routing table lookup ...
... When an IP data packet is received, an OSPF router finds the routing
table entry that best matches the packet's destination. This routing
table entry then provides the outgoing interface ...
... OSPF router finds the routing
table entry that best matches the packet's destination. This routing
table entry then provides the outgoing interface and next hop router ...
... router to
use in forwarding the packet. This section describes the process of
finding the best matching routing table entry. The process consists of a
number of steps, wherein the collection of routing table entries is
...
... finding the best matching routing table entry. The process consists of a
number of steps, wherein the collection of routing table entries is
progressively pruned. In the end, the single routing table entry
...
... number of steps, wherein the collection of routing table entries is
progressively pruned. In the end, the single routing table entry
remaining is the called best match.
...
... remaining is the called best match.
Note that the steps described below may fail to produce a best match
routing table entry (i.e., all existing routing table entries are pruned
for some reason or another). In this case, the packet's IP ...
...
Note that the steps described below may fail to produce a best match
routing table entry (i.e., all existing routing table entries are pruned
for some reason or another). In this case, the packet's IP destination ...
... returned to the packet's source.
(1) Select the complete set of "matching" routing table entries from the
routing table. Each routing table ...
... (1) Select the complete set of "matching" routing table entries from the
routing table. Each routing table entry describes a (set of)
path(s) to a range ...
... routing table entries from the
routing table. Each routing table entry describes a (set of)
path(s) to a range of IP addresses ...
... destination falls into an entry's range of IP addresses, the routing
table entry is called a match. (It is quite likely that multiple
entries will match the data packet. For example, a default route ...
... required to belong to one of these constituent networks. For this
reason, only matching routing table entries with path-type of
intra-area are considered (all others are pruned). If no such
...
... paths.
(4) Select the remaining routing table entry that provides the longest
(most specific) match. Another way of saying this is to choose the
remaining entry that specifies the narrowest range ...
... destinations.
(5) At this point, there may still be multiple routing table entries
remaining. Each routing entry will specify the same range ...
... (5) At this point, there may still be multiple routing table entries
remaining. Each routing entry will specify the same range of IP
addresses, but a different IP ...
... IP
addresses, but a different IP Type of Service. Select the routing
table entry whose TOS value matches the TOS found in the packet
header ...
... TOS value matches the TOS found in the packet
header. If there is no routing table entry for this TOS, select the
routing table ...
... routing table entry for this TOS, select the
routing table entry for TOS 0. In other words, packets requesting
TOS ...
... Sample routing table, without areas ...
... indicating that routes will not vary based on TOS. The calculation
router RT6's routing table proceeds as described in Section 2.1. The
resulting routing table is shown in Table 12. Destination ...
... router RT6's routing table proceeds as described in Section 2.1. The
resulting routing table is shown in Table 12. Destination types are
abbreviated: Network ...
... Sample routing table, with areas ...
... OSPF
area configuration is pictured in Figure 6. Router RT4's routing table
will be described for this area configuration. Router RT4 has a
...
... AS as the concatenation of the two graphs shown in Figures 7
and 8. The resulting routing table is displayed in Table 13.
Again, routers ...
... RT3, RT4,
RT7, RT10 and RT11 are area border routers. Note that there are two
routing entries (in this case having identical paths) for router RT7, in
its dual capacities as an area border router ...
... AS boundary router.
Note also that there are two routing entries for the area border router
RT3, since it has two areas in common with RT4 (Area 1 and the
...
... N N15 * type 1 external 17 RT10 RT7
Table 12: The routing table for Router RT6 (no configured areas).
...
... the case when the router is itself an area border router. Routing
information is condensed at area boundaries. In this example, we assume
that Area 3 has been defined so that networks N9-N11 and the host ...
... would not be an entry for these networks in router RT4's routing table.
In this example there are two equal-cost paths to network ...
... RT5).
Router RT4's routing table would improve (i.e., some of the paths in the
routing table would become shorter) if an additional virtual link were
...
... Router RT4's routing table would improve (i.e., some of the paths in the
routing table would become shorter) if an additional virtual link were
configured between router ...
... intra-area path through Area 1). This would yield a
cost of 1 for the virtual link. The routing table entries changes that
would be caused by the addition of this virtual link are shown in Table
...
... networks are interconnected. Summary link advertisements provide a
way of condensing an area's routing information. AS external
advertisements provide a way of transparently advertising externally-
...
... AS external
advertisements provide a way of transparently advertising externally-
derived routing information throughout the Autonomous System.
...
...
Table 13: Router RT4's routing table in the presence of areas.
Type Dest Area Path Type Cost Next Hop ...
... The age of a link state advertisement is never incremented past MaxAge.
Advertisements having age MaxAge are not used in the routing table
calculation. When an advertisement's age first reaches MaxAge, it is
reflooded. A link state advertisement ...
... checksums. An
instance of age MaxAge is then always accepted as most recent; this
allows old advertisements to be flushed quickly from the routing domain.
Otherwise, if the ages differ by more than MaxAgeDiff, the instance
...
... The E-bit represents OSPF's external routing capability. This bit
should be set in all advertisements associated with the backbone ...
... setting of the E-bit is for informational purposes only; it does not
affect the routing table calculation.
The T-bit ...
... link state advertisement's T-bit is examined when calculating
the routing table's non-zero TOS paths (see Section 16.9).
...
... inter-area routes, and enable the
condensation of routing information at
area borders. Originated by area border
routers, the Type 3 advertisements
...
...
This field identifies the piece of the routing domain that is being
described by the advertisement. Depending on the advertisement's LS
...
... sequence number past the maximum value of of N - 1
(0x7fffffff), the current instance of the advertisement must first be
flushed from the routing domain. This is done by prematurely aging the
advertisement (see Section 14.1) and reflooding it. As soon as this
...
... function is invoked during the link state
flooding procedure (Section 13) and the routing table calculation
(Section 16). In addition, using this lookup function the router ...
... router originates a newer instance of one of its
self-originated advertisements (Section 12.4) or c) the advertisement
ages out and is flushed from the routing domain (Section 14). Whenever
a link state advertisement ...
... unreachable destinations should not be refreshed, but should instead
be flushed from the routing domain (see Section 14.1).
...
... intra-area route has been added/deleted/modified in the routing
table. This may cause a new instance of a summary links
advertisement (for this route ...
... inter-area route has been added/deleted/modified in the routing
table. This may cause a new instance of a summary links
advertisement (for this route ...
... for all pertinent intra-area and inter-area routes in its routing
table. See Section 12.4.3 for more details.
The last event concerns AS boundary ...
... (8) An external route gained through direct experience with an external
routing protocol (like EGP) changes. This will cause the AS
boundary router ...
... advertisements. This enables paths to those types of routers to be
saved in the routing table, for later processing of summary link
advertisements and AS ...
... address of
the associated router interface (this is needed by the routing table
calculation, see Section 16.3). For links to stub networks ...
... links advertisement that it had
previously originated. This advertisement is no longer used in the
routing table calculation. It is flushed by prematurely incrementing
the advertisement's age to MaxAge and reflooding (see Section 14.1).
...
... area border routers. The
precise summary routes to advertise into an area are determined by
examining the routing table structure (see Section 11). Only intra-area
routes are advertised into the backbone ...
... routes are advertised into the other areas.
To determine which routes to advertise into an attached Area A, each
routing table entry is processed as follows:
o Only Destination ...
... router are
advertised in summary link advertisements. If the routing table
entry's Destination type is area border router ...
... AS external routes are never advertised in summary link
advertisements. If the routing table entry has Path-type type 1
external or type 2 external, examine the next routing table entry.
...
... advertisements. If the routing table entry has Path-type type 1
external or type 2 external, examine the next routing table entry.
o Else, if the area associated with this set of paths is the Area A
...
... AS boundary router's ID and metric equal
to the routing table entry's cost. These advertisements should not
be generated if area A has been configured as a stub area.
...
... network's address and metric equal to the
routing table cost.
o The one remaining case is an intra-area ...
... virtual links are being used to provide/increase connectivity of
the backbone, routing information concerning the backbone networks
should not be condensed before being summarized into the virtual
links ...
... then becomes unreachable, the router must then flush the advertisement
from the routing domain by setting its age to MaxAge and reflooding (see
Section 14.1). Also, if the destination ...
... backbone area; it would thus no longer be advertisable to
the backbone), the advertisement should also be flushed from the routing
domain.
...
... links
advertisements. Consider in particular router RT4. Its routing table
was calculated as the example in Section 11.3. RT4 originates summary
link advertisements into both the ...
... router). However, for a single destination there may be
separate sets of paths, and therefore separate routing table entries,
for each Type of Service. All these entries must be considered when
...
... link advertisement for each external route that it has learned, either
through another routing protocol (such as EGP), or through configuration
information.
...
... destination which then becomes unreachable, the router must then flush
the advertisement from the routing domain by setting its age to MaxAge
and reflooding (see Section 14.1).
...
... address (RTX). This
leads to a clear duplication of effort. If only one of RTA or RTB
originated the set of external advertisements, the routing would remain
the same, and the size of the link state database would decrease.
...
... (replacing the current database copy). This may cause the
routing table calculation to be scheduled. In addition,
timestamp the new advertisement with the current time (i.e., the
...
... result of flooding or a newly self originated advertisement, may cause
the routing table structure to be recalculated. The contents of the new
advertisement should be compared to the old instance, if present. If
there is no difference, there is no need to recalculate the routing
table ...
... routing table structure to be recalculated. The contents of the new
advertisement should be compared to the old instance, if present. If
there is no difference, there is no need to recalculate the routing
table. (Note that even if the contents are the same, the LS checksum
will probably be different, since the checksum ...
... sequence
number.)
If the contents are different, the following pieces of the routing table
must be recalculated, depending on the LS type field:
...
... network links
The entire routing table must be recalculated, starting with the
shortest path calculations for each area (not just the area whose
...
...
The reception of such an advertisement indicates that there are link
state advertisements in the routing domain that were originated before
the last time the router ...
... the destination. In this case, the advertisement should be flushed from
the routing domain by incrementing the advertisement's LS age to MaxAge
and reflooding (see Section 14.1).
...
...
An advertisement's age is never incremented past the value MaxAge.
Advertisements having age MaxAge are not used in the routing table
calculation. As a router ages its link state database ...
... 17] At this time, the router must
attempt to flush the advertisement from the routing domain. This is
done simply by reflooding the MaxAge advertisement just as if it was a
...
...
A link state advertisement can be flushed from the routing domain by
setting its age to MaxAge and reflooding the advertisement. This
...
... current advertisement instance (having LS sequence number of 0x7fffffff)
must be prematurely aged and flushed from the routing domain before a
new instance with sequence number ...
... previously advertised external routes is no longer reachable. In this
circumstance, the router can flush its external advertisement from the
routing domain via premature aging. This procedure is preferable to the
alternative, which is to originate a new advertisement for the
...
... router, the cost and viability of the virtual link is
discovered by examining the routing table entry for the other endpoint
router. (The entry's associated area must be the configured transit
...
...
router. (The entry's associated area must be the configured transit
area). Actually, there may be a separate routing table entry for each
Type of Service. These are called the virtual link's corresponding
...
... Type of Service. These are called the virtual link's corresponding
routing table entries. The Interface Up event occurs for a virtual link
...
... link
when its corresponding TOS 0 routing table entry becomes reachable.
Conversely, the Interface Down event occurs when its TOS ...
... Conversely, the Interface Down event occurs when its TOS 0 routing table
entry becomes unreachable.[18] In other words, the virtual link ...
... area border
routers. This cost appears in the virtual link's corresponding
routing table entry. When the cost of a virtual link changes, a new
router ...
... o Just as the virtual link's cost and viability are determined by the
routing table build process (through construction of the routing
table entry for the other endpoint), so are the IP interface ...
... link's cost and viability are determined by the
routing table build process (through construction of the routing
table entry for the other endpoint), so are the IP interface address ...
... Calculation Of The Routing Table ...
...
This section details the OSPF routing table calculation. Using its
attached areas' link state databases ...
... router runs the
following algorithm, building its routing table step by step. At each
step, the router must access individual pieces of the link state ...
... link state advertisement
whose LS age is equal to MaxAge. Such an advertisement should not be
used in the routing table calculation, and is treated just as if the
lookup process had failed.
...
...
The OSPF routing table's organization is explained in Section 11. Two
examples of the routing table build process are presented in Sections
...
... OSPF routing table's organization is explained in Section 11. Two
examples of the routing table build process are presented in Sections
11.2 and 11.3. This process can be broken into the following steps:
...
... 11.2 and 11.3. This process can be broken into the following steps:
(1) The present routing table is invalidated. The routing table is
built again from scratch. The old routing table ...
...
(1) The present routing table is invalidated. The routing table is
built again from scratch. The old routing table is saved so that
...
... routing table is invalidated. The routing table is
built again from scratch. The old routing table is saved so that
changes in routing table entries can be identified.
...
... built again from scratch. The old routing table is saved so that
changes in routing table entries can be identified.
(2) The intra-area ...
... (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 ...
... advertisements are examined.
(4) For those routing entries whose next hop is over a virtual link, a
...
... Section 16.9.
Changes made to routing table entries as a result of these calculations
can cause the OSPF protocol to take further actions. For example, a
...
... Section 16.7 for a complete list of the OSPF protocol actions resulting
from routing table table changes.
...
... process).
(4) Possibly modify the routing table. For those routing table entries
modified, the associated area will be set to Area A, the path type
...
...
(4) Possibly modify the routing table. For those routing table entries
modified, the associated area will be set to Area A, the path type
will be set to intra-area ...
...
If the newly added vertex is an area border router, a routing table
entry is added whose destination type is "area border router ...
... router links advertisement is
copied into the routing table entry's Optional capabilities field.
If the newly added vertex is an AS boundary ...
... If the newly added vertex is an AS boundary router, the routing
table entry of type "AS boundary router" for the destination ...
... router, each set using a different area. However, the AS
boundary router's routing table entry must indicate a set of paths
which utilize a single area. The area leading to the routing table
...
... router's routing table entry must indicate a set of paths
which utilize a single area. The area leading to the routing table
entry is selected as follows: A set of intra-area paths having no
...
... whenever an AS boundary router's routing table entry is
added/modified, the Options found in the associated router links ...
... router links
advertisement is copied into the routing table entry's Optional
capabilities field.
...
...
If the newly added vertex is a transit network, the routing table
entry for the network is located. The entry's destination ...
... associated network links advertisement). If the routing table entry
already exists (i.e., there is already an intra-area route ...
... route to the
destination installed in the routing table), multiple vertices have
mapped to the same IP network. For example, this can occur when a
...
... new Designated Router is being established. In this case, the
current routing table entry should be overwritten if and only if the
newly found path is just as short and the current routing table
...
... current routing table entry should be overwritten if and only if the
newly found path is just as short and the current routing table
entry's Link State Origin has a smaller Link State ...
... link state advertisement.
If there is no routing table entry for the network (the usual case),
a routing table ...
... routing table entry for the network (the usual case),
a routing table entry for the IP network should be added. The
routing table ...
... routing table entry for the IP network should be added. The
routing table entry's Link State origin should be set to the newly
added vertex' link state advertisement ...
... network. This is done by looking up the network's current routing
table entry. If the calculated distance D is larger, go on to
examine the next stub network link ...
...
(3) If this step is reached, the stub network's routing table entry must
be updated. Calculate the set of next hops that would result from
...
... network) and the parent vertex (the router vertex). If the distance
D is the same as the current routing table cost, simply add this set
of next hops to the routing table ...
... routing table cost, simply add this set
of next hops to the routing table entry's list of next hops. In
this case, the routing table ...
... routing table entry's list of next hops. In
this case, the routing table already has a Link State origin. If
this Link State ...
... links advertisement.
Otherwise D is smaller than the routing table cost. Overwrite the
current routing table entry by setting the routing table ...
... Otherwise D is smaller than the routing table cost. Overwrite the
current routing table entry by setting the routing table entry's
cost to D, and by setting the entry's list of next hops ...
... routing table cost. Overwrite the
current routing table entry by setting the routing table entry's
cost to D, and by setting the entry's list of next hops to the newly
...
... cost to D, and by setting the entry's list of next hops to the newly
calculated set. Set the routing table entry's Link State origin to
V's router ...
... link.
For all routing table entries added/modified in the second stage, the
associated area will be set to Area A and the path type will be set to
intra-area. When the list of reachable ...
... list is modified (Step 2e of Stage
1). In stage 2 a shorter path is discovered each time the destination's
routing table entry is modified (Step 3 of Stage 2).
The set of next hops ...
... tree calculation, as shorter and
shorter paths are discovered. In the end, the destination's routing
table entry will always reflect the next hops resulting from the
absolute shortest path(s).
...
... (4) Else, call the destination described by the advertisement N, and the
area border originating the advertisement BR. Look up the routing
table entry for BR having A as its associated area. If no such
entry exists for router BR (i.e., BR is unreachable in Area A), do
...
... inter-area path IAC.
(5) Next, look up the routing table entry for the destination N. (The
entry's Destination ...
... preferred).
(7) Else, the paths present in the routing table are also inter-area
paths. Install the new path through BR if it is cheaper, overriding
...
... inter-area
paths. Install the new path through BR if it is cheaper, overriding
the paths in the routing table. Otherwise, if the new path is the
same cost, add it to the list of paths that appear in the routing
table entry.
...
... the paths in the routing table. Otherwise, if the new path is the
same cost, add it to the list of paths that appear in the routing
table entry.
...
... having configured
virtual links. In these routers, some of the routing table entries may
have virtual next hops. That is, one or more of the next hops ...
... next hop is replaced by a real next hop.
In the process a new routing table distance is calculated that may be
smaller than the previously calculated distance. In this case, the list
of next hops ...
... of next hops is pruned so that only those giving rise to the new
shortest distance are included, and the routing table entry's distance
is updated accordingly.
...
... Network or AS Boundary router. Suppose that one of a routing table
entry's next hops is a virtual link ...
... next hops is a virtual link. This is determined by the
following combination: the routing table entry's path type is either
intra-area or inter-area, the area associated with the ...
... entry's path type is either
intra-area or inter-area, the area associated with the routing table
entry must be the backbone, yet the next hop ...
... (1) Call the border router that originated the advertisement BR. If
there is no routing table entry for BR having A as associated area
(i.e., BR is unreachable through Area A), examine the next
advertisement.
...
... calculated should be less than or equal to the cost originally specified
in destination N's routing table entry. This same calculation should be
done for all of N's virtual next hops, and then N's new cost set to the
...
... (3) Call the destination described by the advertisement N. Look up the
routing table entry for the AS boundary router (ASBR ...
... ASBR
itself. Otherwise, look up the forwarding address in the routing
table.[24] An intra-area or inter-area ...
... advertisement and consider the next in the list.
Call the routing table distance to the forwarding address X (when
the forwarding address ...
... external metric.
(4) Next, look up the routing table entry for the destination N. If no
entry exists for N, install the AS ...
...
If the new path is shorter, it replaces the present paths in the
routing table entry. If the new path is the same cost, it is added
to the routing table entry's list of paths.
...
... routing table entry. If the new path is the same cost, it is added
to the routing table entry's list of paths.
...
... When a new summary link advertisement is received, it is not necessary
to recalculate the entire routing table. Call the destination described
by the summary link ...
... advertisement belongs.
Look up the routing table entry for N. If the next hop to N is a
virtual link ...
... link advertisements whose destination is N. Before this
procedure is performed, the present routing table entry for N should be
invalidated (but kept for comparison purposes). If this procedure leads
...
... AS external link advertisement is received, it is not
necessary to recalculate the entire routing table. Call the destination
described by the AS ...
... link advertisements whose destination is N.
Before this procedure is performed, the present routing table entry for
N should be invalidated.
...
... Events generated as a result of routing table changes ...
...
Changes to routing table entries sometimes cause the OSPF area border
routers to take additional actions. These routers ...
... area border
routers to take additional actions. These routers need to act on the
following routing table changes:
o The cost or path type of a routing table ...
... routing table changes:
o The cost or path type of a routing table entry has changed. If the
destination described by this entry is a Network ...
... been deleted, or is no longer advertisable to a particular area, the
advertisement must be flushed from the routing domain by setting its
age to MaxAge and reflooding (see Section 14.1).
...
...
o A routing table entry associated with a configured virtual link has
changed. The destination ...
... link has
changed. The destination of such a routing table entry is an area
border router. The change indicates a modification to the virtual
link ...
... the backbone must be originated. This in turn may cause further
routing table changes.
...
... OSPF protocol maintains multiple equal-cost routes to all
destinations. This can be seen in the steps used above to calculate the
routing table, and in the definition of the routing table structure.
...
... destinations. This can be seen in the steps used above to calculate the
routing table, and in the definition of the routing table structure.
Each one of the multiple routes ...
...
TOS (see Section 2.4). Support for TOS-based routing is optional.
TOS-capable and non-TOS-capable ...
... links advertisement.
The above sections detailing the routing table calculations handle the
TOS 0 case only. In general, for routers supporting ...
... TOS 0 case only. In general, for routers supporting TOS-based routing,
each piece of the routing table calculation must be rerun separately for
...
... TOS-based routing,
each piece of the routing table calculation must be rerun separately for
the non-zero TOS ...
... forwarding packets (see Section 11.1).
The following lists the modifications needed when running the routing
table calculation for a non-zero TOS value (called TOS ...
... Routers that do not support TOS-based routing should be omitted from
the shortest-path tree calculation. These routers ...
... McQuillan, J.M., Richer, I. and Rosen, E.C. ARPANET Routing Algorithm Improvements. BBN Technical Report 3803, April 1978. ...
... Digital Equipment Corporation. Information processing systems -- Data communications -- Intermediate System to Intermediate System Intra-Domain Routing Protocol. October 1987. ...
... McQuillan, J. et.al. The New Routing Algorithm for the Arpanet. IEEE Transactions on Communications, May 1980. ...
... Perlman, Radia. Fault-Tolerant Broadcast of Routing Information. Computer Networks, Dec. 1983. ...
... neighbor is up and running. Likewise, existence of the neighbor on virtual links is indicated by the routing table calculation. However, in both these cases, the Hello Protocol is still used. This ensures that communication between the neighbors is bidirectional ...
... neighbors is bidirectional, and that each of the neighbors has a functioning routing protocol layer. ...
... MaxAgeDiff is an architectural constant. It indicates the maximum dispersion of ages, in seconds, that can occur for a single
link state instance as it is flooded throughout the routing domain. If two advertisements differ by more than this, they are assumed to be different instances of the same advertisement. This
can occur when a router restarts ...
... There is one instance where a lookup must be done based on partial information. This is during the routing table calculation, when a network links advertisement must be found based solely on its Link State ...
... 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 the shortest path tree ...
... Only the TOS 0 routes are important here. This is because all routing protocol packets are sent with TOS= 0. See Appendix A. ...
... destinations do not vary based on TOS. For these destinations, the routing calculation need not be repeated for each TOS value. In addition, there need only be a single routing table entry for these destinations ...
... destinations, the routing calculation need not be repeated for each TOS value. In addition, there need only be a single routing table entry for these destinations (instead of a separate entry for each TOS value). ...
... is described. This field describes various
capabilities that may or may not be supported by pieces of the OSPF
routing domain. It is contained both in OSPF protocol packets and in
...
... TOS of 0. The OSPF
protocol supports TOS-based routing. Routes to any particular
destination may vary based on TOS ...
... destination may vary based on TOS. However, all OSPF routing
protocol packets are sent with the DTR bits in the IP header's TOS ...
... RFC791]) set to 0.
o Routing protocol packets are sent with IP precedence set to
Internetwork Control. OSPF protocol ...
... traffic around reduced functionality routers, by
excluding them from parts of the routing table calculation.
Two capabilities are currently defined. For each capability, the effect
...
... Database Description packets and link state advertisements is specified
below. For example, the external routing capability (below called the
E-bit) has meaning only in OSPF Hello ...
... In other words, routers incapable of TOS routing will be avoided as
much as possible when forwarding data traffic requesting a non-zero ...
... packets implement the flooding of advertisements throughout the OSPF
routing domain. Because of this, OSPF protocol packets cannot be parsed
...
... OSPF, the source and
destination of a routing protocol packet are the two ends of an
(potential) adjacency.
...
... Each link state advertisement describes a piece of the OSPF routing
domain. Every router originates a ...
... link state
advertisements may also be originated (see Section 12.4). All link
state advertisements are then flooded throughout the OSPF routing
domain. The flooding ...
... router constructs a shortest path
tree with itself as root. This yields a routing table (see Section 11).
For the details of the routing table build process, see Section 16.
...
... root. This yields a routing table (see Section 11).
For the details of the routing table build process, see Section 16.
...
... ).
Multiple instances of the link state advertisement may exist in the
routing domain at the same time. It is then necessary to determine
which instance is more recent. This is accomplished by examining the LS
...
... Options
The optional capabilities supported by the described portion of the
routing domain. OSPF's optional capabilities are documented in
...
... IP interface address.
This latter piece of information is needed during the routing table
build process, when calculating the IP address of the next hop ...
... retransmission lists. Advertisements having age MaxAge are not used
in the routing table calculation. The value of MaxAge must be
greater than LSRefreshTime. The value of MaxAge is set to 1 hour.
...
... default route. This route is
used when no other matching routing table entry can be found. The
default destination can only be advertised in AS ...
... inability for adjacencies to form between them, with a resulting
hindrance to the flow of routing protocol traffic. The following items
must be configured for an area:
...
... belonging to multiple areas, depending on their attached networks'
area membership. Routing information is condensed at area
boundaries. External to the area, a single route is advertised for
...
... authentication types.
External routing capability
Whether AS external advertisements will be flooded into/throughout
...
... the area. If AS external advertisements are excluded from the area,
the area is called a "stub". Internal to stub areas, routing to
external destinations will be based solely on a default summary
...
... attached to a common network. The smaller the hello interval, the
faster topological changes will be detected, but more routing
traffic will ensue. Sample value for a X.25 ...
... inserted directly into the OSPF header when originating routing
protocol packets. There could be a separate password for each
network ...
... IP source in protocol packets it sends along the
virtual link, and is set dynamically during the routing table build
process. Interface output cost is also set dynamically on virtual links ...
... to the internet, the actual configured cost(s) in many cases is
unimportant (i.e., will have no effect on routing).
...
... link state retransmissions over the last hour. Also falling into this
category are dumps of the various routing data structures.
...
... A logging message should be produced on every significant protocol
event. The major events are listed below. Most of these events
indicate a topological change in the routing domain. However, some
number of logging messages can be expected even when the routing ...
... routing domain. However, some
number of logging messages can be expected even when the routing domain
remains intact for long periods of time. For example, link state ...
... Link State Update
packets. This will cause recalculation of the routing table. The
logging message produced should indicate the advertisement's LS
type, Link State ...
... from whom the advertisement was received.
T6 An entry in the routing table has changed (see Section 11). The
logging message produced should indicate the Destination type,
...
... link state database has
aged to MaxAge (see Section 14). At this point, the advertisement
is no longer included in the routing table calculation, and is
reflooded. The message should list the advertisement's LS type,
Link State ...
...
These statistics display collections of the routing data structures.
They should be able to be obtained interactively, through some kind of
network management facility.
...
...
All the following statistics displays, with the exception of the area
list, routing table and the AS external links, are specific to a single
...
... 12.4.1.
(6) A listing of the entire routing table. Several examples are shown
in Section 11. The routing table is calculated from the combined
...
... (6) A listing of the entire routing table. Several examples are shown
in Section 11. The routing table is calculated from the combined
databases of each attached area (see Section 16). It may be
...
... databases of each attached area (see Section 16). It may be
desirable to sort the routing table by Type of Service, or by
destination ...
...
Use of this authentication type means that routing exchanges in the area
are not authenticated. The 64-bit ...
... OSPF areas where there is only a single
exit/entry that is used by all externally addressed packets, or to cases
where some sub-optimality of external routing is acceptable.
Therefore, an OSPF ...
...
In OSPF there is conceptually a separate routing table for each TOS; the
calculations detailed in steps 1-5 of Section 16 must be done separately
...
... to route based on TOS. However, producing a separate routing table for
each TOS may prove costly, both in terms of memory and processor ...
... system administrator
to configure routers to calculate/use only a single routing table (the
TOS 0 table). When this is done, some traffic may take non-optimal
...
... TOS 0 table). When this is done, some traffic may take non-optimal
routes. But all packets will still be delivered, and routing will
remain loop free (see Section 2.4).
...
... remain loop free (see Section 2.4).
In order to avoid routing loops, a router (router X) using a single
...
... It is still mandatory for all OSPF implementations to be able to
construct separate routing tables for each TOS value, if desired by the
system administrator.
...
... Y) , and only one OSPF router (call it
router X) exchanges routing information with Y. The OSPF routers on the
LAN other than X will forward packets destined for Y and beyond through
...
... setting it to an actual router address incurs additional cost during the
routing table build process (Section 16.4).
Besides preventing extra-hops, there are two other applications for this
...
... router in the middle of the Autonomous System can gather
external routing information and originate AS external advertisements
that specify the correct exit route ...
... This is a method for flushing a link state advertisement from the
routing domain: the advertisement's age is set to MaxAge and
advertisement is reflooded just as if it were a newly received
...
... with this occurrence. Without this paragraph, retransmissions of MaxAge
advertisements could possibly delay their being flushed from the routing
domain.
...
... F.2.4 Routing table lookup explained ...
... looks up the packet's IP
destination in the routing table. This determines the packet's next
hop. A new section (Section 11.1) has been added describing the routing
table lookup ...
... destination in the routing table. This determines the packet's next
hop. A new section (Section 11.1) has been added describing the routing
table lookup (instead of just specifying a "best match"). This section
clarifies OSPF ...
... lookup (instead of just specifying a "best match"). This section
clarifies OSPF's four level routing hierarchy (i.e., intra-area, inter-
area, external type 1 and external type 2 routes). It also specifies
...
... area, external type 1 and external type 2 routes). It also specifies
the effect of TOS on routing.
...
... link state advertisement's sequence number
decreases when it is flushed from the routing domain via premature-
aging, and then reoriginated with the smallest sequence number ...
... traffic around reduced
functionality router, by excluding them from parts of the routing table
calculation. See Section A.2 for more details.
...
... Additional functionality will probably be added to OSPF in the future.
One example of this is a multicast routing capability, which is
currently under development. In order to be able to add such features
in a backward-compatible ...