rfc1245.txt

著名的RFC文档,其中有一些文档是已经翻译成中文的的.

RFC 1245                 OSPF protocol analysis                July 1991


three advertisements fit in a single packet. (This packet could be
either a Link State Update packet or a Link State Acknowledgment packet;
in this analysis we select the Link State Update packet, which is the
larger). An AS external LSA is 36 bytes long.  Adding one third of a
packet header (IP header plus OSPF Update packet) yields 52 bytes.
Transmitting this amount of data every 30 minutes gives an average rate
of 23/100 bits/second.

If you want to limit your routing traffic to 5% of the link's total
bandwidth, you get the following maximums for database size:

TABLE 2. Database size as a function of link speed (5% utilization)


                 Speed    # external advertisements
                 _____________________________________
                 9.6 Kb   2087
                 56 Kb    12,174


Higher line speeds have not been included, because other factors will
then limit database size (like router memory) before line speed becomes
a factor. Note that in the above calculation, the size of the data link
header was not taken into account. Also, note that while the OSPF
database is likely to be mostly external LSAs, other LSAs have a size
also. As a ballpark estimate, router links and network links are
generally three times as large as an AS external link, with summary link
advertisements being the same size as external link LSAs.

OSPF consumes considerably less link bandwidth than RIP. This has been
shown experimentally in the NSI network. See Jeffrey Burgan's "NASA
Sciences Internet" report in [3].


3.3  Router memory

Memory requirements in OSPF are dominated by the size of the link state
database. As in the previous section, it is probably safe to assume that
most of the advertisements in the database are external LSAs. While an
external LSA is 36 bytes long, it is generally stored by an OSPF
implementation together with some support data. So a good estimate of
router memory consumed by an external LSA is probably 64 bytes. So a
database having 10,000 external LSAs will consume 640K bytes of router
memory. OSPF definitely requires more memory than RIP.

Using the Proteon P4200 implementation as an example, the P4200 has
2Mbytes of memory. This is shared between instruction, data and packet
buffer memory. The P4200 has enough memory to store 10, 000 external



[Moy]                                                           [Page 7]

RFC 1245                 OSPF protocol analysis                July 1991


LSAs, and still have enough packet buffer memory available to run a
reasonable number of interfaces.

Also, note that while the OSPF database is likely to be mostly external
LSAs, other LSAs have a size also. As a ballpark estimate, router links
and network links consume generally three times as much memory as an AS
external link, with summary link advertisements being the same size as
external link LSAs.


3.4  Router CPU

Assume that, as the size of the OSPF routing domain grows, the number of
interfaces per router stays bounded. Then the Dijkstra calculation is of
order (n * log (n)), where n is the number of routers in the routing
domain. (This is the complexity of the Dijkstra algorithm in a sparse
network). Of course, it is implementation specific as to how expensive
the Dijkstra really is.

We have no experimental numbers for the cost of the Dijkstra calculation
in a real OSPF implementation. However, Steve Deering presented results
for the Dijkstra calculation in the "MOSPF meeting report" in [3].
Steve's calculation was done on a DEC 5000 (10 mips processor), using
the Stanford internet as a model. His graphs are based on numbers of
networks, not number of routers. However, if we extrapolate that the
ratio of routers to networks remains the same, the time to run Dijkstra
for 200 routers in Steve's implementation was around 15 milliseconds.

This seems a reasonable cost, particularly when you notice that the
Dijkstra calculation is run very infrequently in operational
deployments. In the three networks presented in Section 3.1, Dijkstra
was run on average only every 13 to 50 minutes. Since the Dijkstra is
run so infrequently, it seems likely that OSPF overall consumes less CPU
than RIP (because of RIP's frequent updates, requiring routing table
lookups).

As another example, the routing algorithm in MILNET is SPF-based.
MILNET's current size is 230 nodes, and the routing calculation still
consumes less than 5% of the MILNET switches' processor bandwidth [4].
Because the routing algorithm in the MILNET adapts to network load, it
runs the Dijkstra process quite frequently (on the order of seconds as
compared to OSPF's minutes). However, it should be noted that the
routing algorithm in MILNET incrementally updates the SPF-tree, while
OSPF rebuilds it from scratch at each Dijkstra calculation

OSPF's Area capability provides a way to reduce Dijkstra overhead, if it
becomes a burden. The routing domain can be split into areas. The extent
of the Dijkstra calculation (and its complexity) is limited to a single



[Moy]                                                           [Page 8]

RFC 1245                 OSPF protocol analysis                July 1991


area at a time.


3.5  Role of Designated Router

This section explores the number of routers that can be attached to a
single network. As the number of routers attached to a network grows, so
does the amount of OSPF routing traffic seen on the network.  Some of
this is Hello traffic, which is generally multicast by each router every
10 seconds. This burden is borne by all routers attached to the network.
However, because of its special role in the flooding process, the
Designated router ends up sending more Link State Updates than the other
routers on the network. Also, the Designated Router receives Link State
Acknowledgments from all attached routers, while the other routers just
receive them from the DR. (Although it is important to note that the
rate of Link State Acknowledgments will generally be limited to one per
second from each router, because acknowledgments are generally delayed.)

So, if the amount of protocol traffic on the LAN becomes a limiting
factor, the limit is likely to be detected in the Designated Router
first. However, such a limit is not expected to be reached in practice.
The amount of routing protocol traffic generated by OSPF has been shown
to be small (see Section 3.2). Also, if need be OSPF's hello timers can
be configured to reduce the amount of protocol traffic on the network.
Note that more than 50 routers have been simulated attached to a single
LAN (see [1]). Also, in interoperability testing 13 routers have been
attached to a single ethernet with no problems encountered.

Another factor in the number of routers attached to a single network is
the cutover time when the Designated Router fails. OSPF has a Backup
Designated Router so that the cutover does not have to wait for the new
DR to synchronize (the adjacency bring-up process mentioned earlier)
with all the other routers on the LAN; as a Backup DR it had already
synchronized. However, in those rare cases when both DR and Backup DR
crash at the same time, the new DR will have to synchronize (via the
adjacency bring-up process) with all other routers before becoming
functional. Field experience show that this synchronization process
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 a
single network.

In the unlikely event that the number of routers attached to a LAN
becomes a problem, either due to the amount of routing protocol traffic
or the cutover time, the LAN can be split into separate pieces (similar
to splitting up the AS into separate areas).






[Moy]                                                           [Page 9]

RFC 1245                 OSPF protocol analysis                July 1991


3.6  Summary

In summary, it seems like the most likely limitation to the size of an
OSPF system is available router memory. We have given as 10,000 as the
number of external LSAs that can be supported by the memory available in
one configuration of a particular implementation (the Proteon P4200).
Other implementations may vary; nowadays routers are being built with
more and more memory.  Note that 10,000 routes is considerably larger
than the largest field implementation (BARRNet; which at 1816 external
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 number
of external routes that need to be imported. Secondly, an EGP can be
used that will transport its own information through the AS instead of
relying on the IGP (OSPF in this case) to do transfer the information
for it (the EGP). Thirdly, routers having insufficient memory may be
able to be assigned to stub areas (whose databases are drastically
smaller). Lastly, if the Internet went away from a flat address space
the amount of external information imported into an OSPF domain could be
reduced drastically.

While not as likely, there could be other issues that would limit the
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 in
the OSPF domain; although at this point the domain can be split into
areas. Finally, when there are many routers attached to a single
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 environments

Suitable environments for the OSPF protocol range from large to small.
OSPF is particular suited for transit Autonomous Systems for the
following reasons. OSPF can accommodate a large number of external
routes. In OSPF the import of external information is very flexible,
having provisions for a forwarding address, two levels of external
metrics, and the ability to tag external routes with their AS number for
easy management. Also OSPF's ability to do partial updates when external
information changes is very useful on these networks.

OSPF is also suited for smaller, either stand alone or stub Autonomous
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 environments

OSPF has a very limited ability to express policy. Basically, its only
policy mechanisms are in the establishment of a four level routing
hierarchy: intra-area, inter-area, type 1 and type 2 external routes.  A
system wanting more sophisticated policies would have to be split up
into separate ASes, running a policy-based EGP between them.


6.0  Reference Documents

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 the
    Eighteenth Internet Engineering Task Force", University of British
    Columbia, July 30-August 3, 1990.






























[Moy]                                                          [Page 11]

RFC 1245                 OSPF protocol analysis                July 1991


Security Considerations

Security issues are not discussed in this memo.


Author's Address

John Moy
Proteon Inc.
2 Technology Drive
Westborough, MA 01581

Phone: [phone]
Email:  [e-mail]





































[Moy]                                                          [Page 12]