As per Relevance of the word designated, we have this rfc below:
Network Working Group J. Moy,
Request for Comments: 1245 Proteon, Inc
July 1991
OSPF protocol
Status of this
This memo provides information for the Internet community. It does
specify any Internet standard. Distribution of this memo is unlimited
Please send comments to ospf@trantor.umd.edu
This is the first of two reports on the OSPF protocol. These reports
required by the IAB/ IESG in order for an Internet routing protocol
advance to Draft Standard Status. OSPF is a TCP/IP routing protocol
designed to be used internal to an Autonomous System (in other words
OSPF is an Interior Gateway Protocol).
Version 1 of the OSPF protocol was published in RFC 1131. Since
OSPF version 2 has been developed. Version 2 has been documented in
1247. The changes between version 1 and version 2 of the OSPF
are explained in Appendix F of RFC 1247. It is OSPF Version 2 that
the subject of this report
This report attempts to summarize the key features of OSPF V2. It
attempts to analyze how the protocol will perform and scale in
Internet
1.0
This document addresses, for OSPF V2, the requirements set forth by
IAB/IESG for an Internet routing protocol to advance to Draft
state. This requirements are briefly summarized below. The
sections of this report document how OSPF V2 satisfies
requirements
o What are the key features and algorithms of the protocol
o How much link bandwidth, router memory and router CPU cycles does
protocol consume under normal conditions
o For these metrics, how does the usage scale as the
environment grows? This should include topologies at least an
[Moy] [Page 1]
RFC 1245 OSPF protocol analysis July 1991
of magnitude larger than the current environment
o What are the limits of the protocol for these metrics? (I.e.,
will the routing protocol break?)
o For what environments is the protocol well suited, and for what is
not suitable
1.1
The OSPF protocol has been developed by the OSPF Working Group of
Internet Engineering Task Force
2.0 Key features of the OSPF
This section summarizes the key features of the OSPF protocol. OSPF
an Internal gateway protocol; it is designed to be used internal to
single Autonomous System. OSPF uses link-state or SPF-based
(as compared to the distance-vector or Bellman-Ford technology found
routing protocols such as RIP). Individual link state
(LSAs) describe pieces of the OSPF routing domain (Autonomous System).
These LSAs are flooded throughout the routing domain, forming the
state database. Each router has an identical link state database
synchronization of link state databases is maintained via a
flooding algorithm. From this link state database, each router builds
routing table by calculating a shortest-path tree, with the root of
tree being the calculating router itself. This calculation is
referred to as the Dijkstra procedure
Link state advertisements are small. Each advertisement describes
small pieces of the OSPF routing domain, namely either: the
of a single router, the neighborhood of a single transit network,
single inter-area route (see below) or a single external route
The other key features of the OSPF protocol are
o Adjacency bringup. Certain pairs of OSPF routers become "adjacent".
As an adjacency is formed, the two routers synchronize their
state databases by exchanging database summaries in the form of
Database Exchange packets. Adjacent routers then maintain syn
chronization of their link state databases through the
flooding algorithm. Routers connected by serial lines always
adjacent. On multi-access networks (e.g., ethernets or X.25 PDNs),
all routers attached to the network become adjacent to both
Designated Router and the Backup Designated router
o Designated router. A Designated Router is elected on all multi-
networks (e.g., ethernets or X.25 PDNs). The network's
[Moy] [Page 2]
RFC 1245 OSPF protocol analysis July 1991
Router originates the network LSA describing the network's
environment. It also plays a special role in the flooding algorithm
since all routers on the network are synchronizing their link
databases by sending and receiving LSAs to/from the Designated
during the flooding process
o Backup Designated Router. A Backup Designated Router is elected
multi-access networks to speed/ease the transition of
Routers when the current Designated Router disappears. In that event
the Backup DR takes over, and does not need to go through
adjacency bringup process on the LAN (since it already had done
in its Backup capacity). Also, even before the disappearance of
Designated Router is noticed, the Backup DR will enable the
flooding algorithm to proceed in the DR's absence
o Non-broadcast multi-access network support. OSPF treats
networks (e.g., X.25 PDNs) pretty much as if they were LANs (i.e.,
DR is elected, and a network LSA is generated).
configuration information is needed however for routers attached
these network to initially find each other
o OSPF areas. OSPF allows the Autonomous Systems to be broken up
regions call areas. This is useful for several reasons. First,
provides an extra level of routing protection: routing within an
is protected from all information external to the area. Second,
splitting an Autonomous System into areas the cost of the
procedure (in terms of CPU cycles) is reduced
o Flexible import of external routing information. In OSPF,
external route is imported into the Autonomous System in a
LSA. This reduces the amount of flooding traffic (since
routes change often, and you want to only flood the changes). It
enables partial routing table updates when only a single
route changes. OSPF external LSAs also provide the
features. A forwarding address can be included in the external LSA
eliminating extra-hops at the edge of the Autonomous System.
are two levels of external metrics that can be specified, type 1
type 2. Also, external routes can be tagged with a 32-bit number (
external route tag; commonly used as an AS number of the route'
origin), simplifying external route management in a
Autonomous System
o Four level routing hierarchy. OSPF has a four level
hierarchy, or trust model: intra-area, inter-area, external type 1
and external type 2 routes. This enables multiple levels of
protection, and simplifies routing management in an
System
[Moy] [Page 3]
RFC 1245 OSPF protocol analysis July 1991
o Virtual links. By allowing the configuration of virtual links,
removes topological restrictions on area layout in an
System
o Authentication of routing protocol exchanges. Every time an
router receives a routing protocol packet, it authenticates
packet before processing it further
o Flexible routing metric. In OSPF, metric are assigned to
router interfaces. The cost of a path is then the sum of the path'
component interfaces. The routing metric itself can be assigned
the system administrator to indicate any combination of
characteristics (e.g., delay, bandwidth, dollar cost, etc.).
o Equal-cost multipath. When multiple best cost routes to a
exist, OSPF finds them and they can be then used to load
traffic to the destination
o TOS-based routing. Separate sets of routes can be calculated for
IP type of service. For example, low delay traffic could be routed
one path, while high bandwidth traffic is routed on another. This
done by (optionally) assigning, to each outgoing router interface
one metric for each IP TOS
o Variable-length subnet support. OSPF includes support for variable
length subnet masks by carrying a network mask with each
destination
o Stub area support. To support routers having insufficient memory
areas can be configured as stubs. External LSAs (often making up
bulk of the Autonomous System) are not flooded into/throughout
areas. Routing to external destinations in stub areas is based
on default
3.0 Cost of the
This section attempts to analyze how the OSPF protocol will perform
scale in the Internet. In this analysis, we will concentrate on
following four areas
o Link bandwidth. In OSPF, a reliable flooding mechanism is used
ensure that router link state databases are remained synchronized
Individual components of the link state databases (the LSAs)
refreshed infrequently (every 30 minutes), at least in the absence
topological changes. Still, as the size of the database increases
the amount of link bandwidth used by the flooding procedure
increases
[Moy] [Page 4]
RFC 1245 OSPF protocol analysis July 1991
o Router memory. The size of an OSPF link state database can get
large, especially in the presence of many external LSAs. This
requirements on the amount of router memory available
o CPU usage. In OSPF, this is dominated by the length of time it
to run the shortest path calculation (Dijkstra procedure). This is
function of the number of routers in the OSPF system
o Role of the Designated Router. The Designated router receives
sends more packets on a multi-access networks than the other
connected to the network. Also, there is some time involved
cutting over to a new Designated Router after the old one
(especially when both the Backup Designated Router and the
Router fail at the same time). For this reason, it is possible
you may want to limit the number of routers connected to a
network
The remaining section will analyze these areas, estimating how
resources the OSPF protocol will consume, both now and in the future.
aid in this analysis, the next section will present some data that
been collected in actual OSPF field deployments
3.1 Operational
The OSPF protocol has been deployed in a number of places in
Internet. For a summary of this deployment, see [1]. Some
have been gathered from this operational experience, via local
management facilities. Some of these statistics are presented in
following table
TABLE 1. Pertinent operational
Statistic BARRNet NSI
___________________________________________________________________
Data gathering (duration) 99 hrs 277 hrs 28
Dijkstra frequency 50 min 25 min 13
External incremental frequency 1.2 min .98 min not
Database turnover 29.7 min 30.9 min 28.2
LSAs per packet 3.38 3.16 2.99
Flooding retransmits 1.3% 1.4% .7%
The first line in the above table show the length of time
statistics were gathered on the three networks. A brief description
the other statistics follows
[Moy] [Page 5]
RFC 1245 OSPF protocol analysis July 1991
o Dijkstra frequency. In OSPF, the Dijkstra calculation involves
those routers and transit networks belonging to the AS. The
is run only when something in the system changes (like a serial
between two routers goes down). Note that in these
systems, the Dijkstra process runs only infrequently (the
frequent being every 13 minutes).
o External incremental frequency. In OSPF, when an external
changes only its entry in the routing table is recalculated.
are called external incremental updates. Note that these happen
more frequently than the Dijkstra procedure. (in other words
incremental updates are saving quite a bit of processor time).
o Database turnover. In OSPF, link state advertisements are
at a minimum of every 30 minutes. New advertisement instances
sent out more frequently when some part of the topology changes.
table shows that, even taking topological changes into account,
average an advertisement is updated close to only every 30 minutes
This statistic will be used in the link bandwidth calculations below
Note that NSI actually shows advertisements updated every 30.7 (> 30)
minutes. This probably means that at one time earlier in
measurement period, NSI had a smaller link state database that it
at the end
o LSAs per packet. In OSPF, multiple LSAs can be included in
Link State Update or Link State Acknowledgment packets.The
shows that, on average, around 3 LSAs are carried in a single packet
This statistic is used when calculating the header overhead in
link bandwidth calculation below. This statistic was derived
diving the number of LSAs flooded by the number of (non-hello
multicasts sent
o Flooding retransmits. This counts both retransmission of LS
packets and Link State Acknowledgment packets, as a percentage of
original multicast flooded packets. The table shows that flooding
working well, and that retransmits can be ignored in the
bandwidth calculation below
3.2 Link
In this section we attempt to calculate how much link bandwidth
consumed by the OSPF flooding process. The amount of link
consumed increases linearly with the number of advertisements present
the OSPF database.We assume that the majority of advertisements in
database will be AS external LSAs (operationally this is true, see [1]).
From the statistics presented in Section 3.1, any
advertisement is flooded (on average) every 30 minutes. In addition
[Moy] [Page 6]
RFC 1245 OSPF protocol analysis July 1991
three advertisements fit in a single packet. (This packet could
either a Link State Update packet or a Link State Acknowledgment packet
in this analysis we select the Link State Update packet, which is
larger). An AS external LSA is 36 bytes long. Adding one third of
packet header (IP header plus OSPF Update packet) yields 52 bytes
Transmitting this amount of data every 30 minutes gives an average
of 23/100 bits/second
If you want to limit your routing traffic to 5% of the link's
bandwidth, you get the following maximums for database size
TABLE 2. Database size as a function of link speed (5% utilization
Speed # external
_____________________________________
9.6 Kb 2087
56 Kb 12,174
Higher line speeds have not been included, because other factors
then limit database size (like router memory) before line speed
a factor. Note that in the above calculation, the size of the data
header was not taken into account. Also, note that while the
database is likely to be mostly external LSAs, other LSAs have a
also. As a ballpark estimate, router links and network links
generally three times as large as an AS external link, with summary
advertisements being the same size as external link LSAs
OSPF consumes considerably less link bandwidth than RIP. This has
shown experimentally in the NSI network. See Jeffrey Burgan's "
Sciences Internet" report in [3].
3.3 Router
Memory requirements in OSPF are dominated by the size of the link
database. As in the previous section, it is probably safe to assume
most of the advertisements in the database are external LSAs. While
external LSA is 36 bytes long, it is generally stored by an
implementation together with some support data. So a good estimate
router memory consumed by an external LSA is probably 64 bytes. So
database having 10,000 external LSAs will consume 640K bytes of
memory. OSPF definitely requires more memory than RIP
Using the Proteon P4200 implementation as an example, the P4200
2Mbytes of memory. This is shared between instruction, data and
buffer memory. The P4200 has enough memory to store 10, 000
[Moy] [Page 7]
RFC 1245 OSPF protocol analysis July 1991
LSAs, and still have enough packet buffer memory available to run
reasonable number of interfaces
Also, note that while the OSPF database is likely to be mostly
LSAs, other LSAs have a size also. As a ballpark estimate, router
and network links consume generally three times as much memory as an
external link, with summary link advertisements being the same size
external link LSAs
3.4 Router
Assume that, as the size of the OSPF routing domain grows, the number
interfaces per router stays bounded. Then the Dijkstra calculation is
order (n * log (n)), where n is the number of routers in the
domain. (This is the complexity of the Dijkstra algorithm in a
network). Of course, it is implementation specific as to how
the Dijkstra really is
We have no experimental numbers for the cost of the Dijkstra
in a real OSPF implementation. However, Steve Deering presented
for the Dijkstra calculation in the "MOSPF meeting report" in [3].
Steve's calculation was done on a DEC 5000 (10 mips processor),
the Stanford internet as a model. His graphs are based on numbers
networks, not number of routers. However, if we extrapolate that
ratio of routers to networks remains the same, the time to run
for 200 routers in Steve's implementation was around 15 milliseconds
This seems a reasonable cost, particularly when you notice that
Dijkstra calculation is run very infrequently in
deployments. In the three networks presented in Section 3.1,
was run on average only every 13 to 50 minutes. Since the Dijkstra
run so infrequently, it seems likely that OSPF overall consumes less
than RIP (because of RIP's frequent updates, requiring routing
lookups).
As another example, the routing algorithm in MILNET is SPF-based
MILNET's current size is 230 nodes, and the routing calculation
consumes less than 5% of the MILNET switches' processor bandwidth [4].
Because the routing algorithm in the MILNET adapts to network load,
runs the Dijkstra process quite frequently (on the order of seconds
compared to OSPF's minutes). However, it should be noted that
routing algorithm in MILNET incrementally updates the SPF-tree,
OSPF rebuilds it from scratch at each Dijkstra
OSPF's Area capability provides a way to reduce Dijkstra overhead, if
becomes a burden. The routing domain can be split into areas. The
of the Dijkstra calculation (and its complexity) is limited to a
[Moy] [Page 8]
RFC 1245 OSPF protocol analysis July 1991
area at a time
3.5 Role of Designated
This section explores the number of routers that can be attached to
single network. As the number of routers attached to a network grows,
does the amount of OSPF routing traffic seen on the network. Some
this is Hello traffic, which is generally multicast by each router
10 seconds. This burden is borne by all routers attached to the network
However, because of its special role in the flooding process,
Designated router ends up sending more Link State Updates than the
routers on the network. Also, the Designated Router receives Link
Acknowledgments from all attached routers, while the other routers
receive them from the DR. (Although it is important to note that
rate of Link State Acknowledgments will generally be limited to one
second from each router, because acknowledgments are generally delayed.)
So, if the amount of protocol traffic on the LAN becomes a
factor, the limit is likely to be detected in the Designated
first. However, such a limit is not expected to be reached in practice
The amount of routing protocol traffic generated by OSPF has been
to be small (see Section 3.2). Also, if need be OSPF's hello timers
be configured to reduce the amount of protocol traffic on the network
Note that more than 50 routers have been simulated attached to a
LAN (see [1]). Also, in interoperability testing 13 routers have
attached to a single ethernet with no problems encountered
Another factor in the number of routers attached to a single network
the cutover time when the Designated Router fails. OSPF has a
Designated Router so that the cutover does not have to wait for the
DR to synchronize (the adjacency bring-up process mentioned earlier
with all the other routers on the LAN; as a Backup DR it had
synchronized. However, in those rare cases when both DR and Backup
crash at the same time, the new DR will have to synchronize (via
adjacency bring-up process) with all other routers before
functional. Field experience show that this synchronization
takes place in a timely fashion (see the OARnet report in [1]). However
this may be an issue in systems that have many routers attached to
single network
In the unlikely event that the number of routers attached to a
becomes a problem, either due to the amount of routing protocol
or the cutover time, the LAN can be split into separate pieces (
to splitting up the AS into separate areas).
[Moy] [Page 9]
RFC 1245 OSPF protocol analysis July 1991
3.6
In summary, it seems like the most likely limitation to the size of
OSPF system is available router memory. We have given as 10,000 as
number of external LSAs that can be supported by the memory available
one configuration of a particular implementation (the Proteon P4200).
Other implementations may vary; nowadays routers are being built
more and more memory. Note that 10,000 routes is considerably
than the largest field implementation (BARRNet; which at 1816
LSAs is still very large).
Note that there may be ways to reduce database size in a routing domain
First, the domain can make use of default routing, reducing the
of external routes that need to be imported. Secondly, an EGP can
used that will transport its own information through the AS instead
relying on the IGP (OSPF in this case) to do transfer the
for it (the EGP). Thirdly, routers having insufficient memory may
able to be assigned to stub areas (whose databases are
smaller). Lastly, if the Internet went away from a flat address
the amount of external information imported into an OSPF domain could
reduced drastically
While not as likely, there could be other issues that would limit
size of an OSPF routing domain. If there are slow lines (like 9600
baud), the size of the database will be limited (see Section 3.2).
Dijkstra may get to be expensive when there are hundreds of routers
the OSPF domain; although at this point the domain can be split
areas. Finally, when there are many routers attached to a
network, there may be undue burden imposed upon the Designated Router
although at that point a LAN can be split into separate LANs
4.0 Suitable
Suitable environments for the OSPF protocol range from large to small
OSPF is particular suited for transit Autonomous Systems for
following reasons. OSPF can accommodate a large number of
routes. In OSPF the import of external information is very flexible
having provisions for a forwarding address, two levels of
metrics, and the ability to tag external routes with their AS number
easy management. Also OSPF's ability to do partial updates when
information changes is very useful on these networks
OSPF is also suited for smaller, either stand alone or stub
Systems, because of its wide array of features: fast convergence
equal-cost-multipath, TOS routing, areas, etc
[Moy] [Page 10]
RFC 1245 OSPF protocol analysis July 1991
5.0 Unsuitable
OSPF has a very limited ability to express policy. Basically, its
policy mechanisms are in the establishment of a four level
hierarchy: intra-area, inter-area, type 1 and type 2 external routes.
system wanting more sophisticated policies would have to be split
into separate ASes, running a policy-based EGP between them
6.0 Reference
The following documents have been referenced by this report
[1] Moy, J., "Experience with the OSPF protocol", RFC 1246, July 1991.
[2] Moy, J., "OSPF Version 2", RFC 1247, July 1991.
[3] Corporation for National Research Initiatives, "Proceedings of
Eighteenth Internet Engineering Task Force", University of
Columbia, July 30-August 3, 1990.
[Moy] [Page 11]
RFC 1245 OSPF protocol analysis July 1991
Security
Security issues are not discussed in this memo
Author's
John
Proteon Inc
2 Technology
Westborough, MA 01581
Phone: (508) 898-2800
Email: jmoy@proteon.
[Moy] [Page 12]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
