Network Working Group Alex Zinin Internet Draft Cisco Systems Expiration Date: January 2001 July 2000 File name: draft-ietf-ospf-refresh-guide-01.txt Guidelines for Efficient LSA Refreshment in OSPF draft-ietf-ospf-refresh-guide-01.txt Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute working documents as Internet Drafts. Internet Drafts are draft documents valid for a maximum of six months. Internet Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a "working draft" or "work in progress". The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract OSPF, an IGP widely deployed in IP networks today, requires each LSA to be refreshed by the originating router every 30 minutes. This method increases the protocol's robustness and solves potential problems that may be caused by software bugs, as well as some properties of the protocol itself. Though OSPF expects each LSA to be refreshed independently, ABRs and ASBRs tend to originate Type 3/4/5 LSAs within a short period of time, thus causing periodical network resource exhaustion by LSA refreshments. This document discusses the techniques that can be used to remedy this problem and provide smooth protocol operation. It must be noted that discussed methods can be applied to other link-state routing protocols, such as IS-IS. Zinin [Page 1]
INTERNET DRAFT Guidelines for LSA Refreshment July 2000 1 Introduction The requirement for each LSA to be refreshed every 30 minutes is really important for OSPF [Ref1]. Not only because OSPF allows LSAs to live no longer than one hour, but also because LSA refreshment provides an automatic method for problem correction. Possible problems solved by periodical LSA refreshments include those caused by the software bugs and those caused by the features of OSPF itself. This document does not describe the first type of problems, the reader could easily think them out. Examples include lost LSAs, not installed routes, etc. The description of a protocol feature that can potentially cause problems follows. OSPF uses the Fletcher checksum (see Section 12.1.7 of [Ref1]) to insure that the information transferred and stored in LSAs is not corrupted. But this is not the only function of the LS checksum. It is also used during the LSDB synchronization and LSA flooding processes to understand whether the newly received LSA and an LSA with the same Link State ID and Advertising Router already installed in the LSDB are the same when other parameters (LS Sequence Number and LS Age) do not allow to make the right decision (see Section 13.1 of [Ref1]). Equal values of the LS checksum indicate that LSAs contain identical information, so the received LSA is not processed any further. In the overwhelming majority of cases this really indicates that LSAs are the same and that another copy of already installed LSA is received due to the redundancy of the flooding protocol. However, in some situations, for example when the originating router was reloaded, it is possible that the new LSA (with the same values of the LS ID and Advertising Router fields) will contain different information, but will still have the same checksum as the old one. This is because of the nature of the checksumming process---a small number of bits is used to characterize the contents of a big informational block. The probability of having the same checksum for two different data blocks depends on the mean size of the data blocks, the number of bits used to calculate and store the checksum, and (the last, but definitely not least) the algorithm used to calculate it. Since the probability of this event for OSPF Link State checksum is sufficiently low, the protocol itself relies on the periodical LSA refreshments to solve potential LSDB inconsistency. So, the periodical LSA refreshments insure that the protocol converges within a finite period of time. The most straightforward approach to refresh LSAs could be to have a single timer firing every 30 minutes and causing reorigination of all self-originated LSAs. This method proved itself as a non-scalable solution causing periodical CPU and link bandwidth exhaustion in the networks. Having a separate timer for each LSA does not mean solving Zinin [Page 2]
INTERNET DRAFT Guidelines for LSA Refreshment July 2000 all problems. First of all, a router may have a lot of self-originated LSAs in its LSDB, so it may very often be not efficient to keep one timer per each LSA in terms of memory and CPU resources. Second, ABRs tend to originate Type-3 and 4 LSAs within a short period of time. This is caused by the fact that in some implementations Dijkstra is not scheduled every time a change in the LSDB is observed, but only after the LSDB has been quiet for some period of time, preventing excessive CPU load. This may very likely lead to the situation when all intra- area routes are announced in summary-LSAs at once. Even though these originated LSAs have separate timers, these timers fire approximately simultaneously. The same effect can be seen when external routing information is injected into an OSPF domain by an ASBR. If the external routes are available at the moment the ASBR is instructed to advertise them, LSAs will be originated almost at once, causing periodical refreshments to be grouped into big chunks and leading to periodical congestion. Similar logic can be applied to the NSSA ASBRs, NSSA translating ABRs, as well as OSPF routers originating Opaque-LSAs. The graph show in Figure 1 depicts the number of self-originated LSAs as a function of time. This graph is greatly simplified assuming that the originating router is an ASBR and injects static routing information with stable topology. Zinin [Page 3]
INTERNET DRAFT Guidelines for LSA Refreshment July 2000 SelfLSAs() ^ | | | | | |- - - - - - - - - - - - - - - - ________..._________| | ^ | | | # of ASE-LSAs | | | | | | V | |- - - - _________...___________| | | | | | | | | | | | | | | ___| | / | | |__| | +------- ---------...-----------|--------...---------|----> t | | | LSRefreshTime | LSRefreshTime | | |<--------------------->|<------------------>| t1 t2 t3 t4 Figure 1. Graph of SelfLSAs(t) --- number of self-originated LSAs At moment t1, the router originates its router-LSA. Then, at t2, the router is instructed to inject external routing information into the OSPF domain. At t3 (t3 - t2 == LSRefreshTime) the router reoriginates the AS-external-LSAs and floods them to its neighbors (reorigination of the router-LSAs is not illustrated). It can be seen that the router introduces periodical traffic bursts into the network, also causing excessive CPU utilization in other OSPF routers. The customers of such a network can suffer from this behavior, experiencing periodical network congestion and increased response time. The following sections of this document discuss the methods of implementing OSPF LSA refreshment feature so that it does not disrupt network operation. Zinin [Page 4]
INTERNET DRAFT Guidelines for LSA Refreshment July 2000 2 Consideration of possible approaches 2.1 Dispersing LSA origination One of the most obvious techniques to avoid LSA refresh grouping could be dispersion of LSA originations. If LSAs were originated with some interval, their refreshes wouldn't group. Though this method seems to be a very easy solution, it has several disadvantages. The most important one is that the time of routing information propagation is increased, i.e., it may take a lot of time (protocol- wise) until the last LSA in the origination queue gets served. However, introducing a minor dispersion in the initial origination process is encouraged. 2.2 Increasing LSA refresh period Another "easy" way to solve the problem is to increase the refresh interval up to some value near the MaxAge value. This would, on the one hand, decrease the frequency of the updates and, on the other hand, would let the protocol function properly without changes in the aging mechanism. This solution is not ideal, because it does not eliminate periodical LSA refresh bursts, though making them less frequent. This method also increases the time of protocol self- correction in case of problems described in Section 1. 2.3 Avoiding periodical refreshes Another proposal is to avoid periodic LSA refreshes at all by making all or some subset of LSAs be DoNotAge as in [Ref2]. This approach does solve the refresh burst problem (there are no refreshments at all), but it also decreases the protocol robustness by removing one of the automatic survival features, thus making the protocol less bullet-proof and attractive. 2.4 Further increasing the refresh period using DNA LSAs The DNA method mentioned above could be used to increase the LSA refresh interval beyond the MaxAge value. This is possible because DNA LSAs are not aged by the routers, so the originating router can refresh its LSAs at whatever rate it chooses. This seems to be a potentially advantageous possibility. However, neither DNA LSAs, nor the refresh interval increase per se can be considered as a sufficient method to prevent the periodical LSA burst problem. More than that, as it was already mentioned, increasing the refresh interval may lead to potentially longer nonoperational periods. A wide range of methods can be used to implement LSA refreshments efficiently. The following section describes an approach, called Zinin [Page 5]
INTERNET DRAFT Guidelines for LSA Refreshment July 2000 "LSA Refreshment Dispersion", implemented in Zebra routing software, as an example of such a technique. 3 LSA Refreshment Dispersion Optimization of the LSA refreshment process described here is based on the observation that if the first refreshment interval is randomized rather than set exactly to LSRefreshTime, subsequent LSA refreshes will also be dispersed. If LSAs are refreshed using individual timers, randomization of the first interval for self- originated LSAs prevents LSA refreshment events from grouping and causing network congestion. Individual LSA refreshments are distributed within the LSRefreshTime period evenly. The described method results in distribution of LSA origination events shown in Figure 2. SelfLSAs() ^ | | __ | __| | __| | | __| | __| | | __| | __| | | __| | _| | | | | | | | | | | | | ___| | / | |__| | +------- ---------...-----------|-----> t | | | LSRefreshTime | | |<--------------------->| t1 t2 t3 Figure 1. Graph of SelfLSAs(t) when Refreshment Dispersion is used The effect of the LSA refreshment dispersion is that OSPF does not put high load on the networks, but instead uses network resources evenly, allowing routers to adapt to its traffic and network Zinin [Page 6]
INTERNET DRAFT Guidelines for LSA Refreshment July 2000 administrators to predict necessary resources in more effective manner. In order to use this technique, the implementation should schedule the LSA refreshment as shown in pseudocode in Figure 3. if ((LSA_SEQ (lsa) == OSPF_INITIAL_SEQUENCE_NUMBER) && (LSA_AGE (lsa) == 0)) delay = OSPF_LS_REFRESH_SHIFT + (random () % OSPF_LS_REFRESH_TIME); else { delay = OSPF_LS_REFRESH_TIME - LSA_AGE(lsa); if (delay < 0) delay = 0; /* Add jitter to avoid syncing */ delay = delay + (random () % OSPF_LS_REFRESH_JITTER) +1; } schedule_lsa_refresh (lsa, delay); Figure 3. Pseudocode for refreshment delay calculation The constants used in the algorithm are defined as follows: OSPF_INITIAL_SEQUENCE_NUMBER is the InitialSequenceNumber constant as defined in [Ref1] OSPF_LS_REFRESH_TIME is the LSRefreshTime constant as defined in [Ref1] OSPF_LS_REFRESH_SHIFT is the length of the silent period, i.e., the minimum time that must elapse after LSA origination before the first LSA refresh. OSPF_LS_REFRESH_JITTER is the limit for the pseudo-random number added to the LSA refresh interval to avoid synchronization, i.e., to introduce additional minor dispersion. Zinin [Page 7]
INTERNET DRAFT Guidelines for LSA Refreshment July 2000 As it was mentioned before, maintaining a separate timer for each LSA can be costly. A simple way of solving this problem is to group LSAs that must be refreshed approximately at the same time and maintain a single timer for them. This may be implemented by having an LSA accumulation group and a periodic timer. The LSA group is used to list all LSAs originated (or reoriginated) between two consecutive timer expirations (within OSPF_REFRESH_GROUP_TIME seconds). The group is flushed either on the timer expiration or when the size of the group reaches a predefined limit (OSPF_REFRESH_GROUP_LIMIT). When a group is flushed, a refresh event is scheduled as shown in the pseudocode in Figure 3. The event handling routine is supposed to submit the LSAs in the group for reorigination. Note that this is really necessary to limit the maximum number of LSAs in the LSA group and flush the group when this limit is reached in order to achieve acceptable results in the refresh event dispersion. Even when refresh events are dispersed using the method described above, there can still happen some situations where a big number of LSAs must be refreshed within a short period of time. This may lead to high CPU load in the originating router and protocol traffic bursts in the network. It is possible to avoid these problems if the OSPF implementation maintains an LSA refresh queue, which is served not faster than some predefined number of LSAs per second (OSPF_REFRESH_QUEUE_RATE). Note that the value of the OSPF_REFRESH_QUEUE_RATE should not be very low, because this may lead to the reorigination queue being never served completely and some LSAs remaining unrefreshed for a long period. This may also affect the initial dispersion in the refresh events introduced by randomizing the first refresh interval. The recommended value for the OSPF_REFRESH_QUEUE_RATE constant is several times the OSPF_REFRESH_GROUP_LIMIT per second. The described algorithm provides desired results in situations when a router receives self-originated LSAs during adjacency establishment after a reload and decides to accept them as correct (and consequently does not originate the new instances). In this case after the received LSAs are identified as self-originated and approved for future use, they are registered in the refreshment module as if they were originated. Such LSAs are also supposed to be bundled into refreshment groups, but in addition to the periodic timer and maximum group size the implementation should care about the ages of the LSAs being grouped. Generally, if the absolute difference between the age of an LSA being added to the group and the first LSA in the group is larger than a certain acceptable value (OSPF_REFRESH_GROUP_AGE_DIF), the group should be unconditionally flushed and the new LSA must start the new group. Note that it is perfectly possible for the received self-originated LSAs to be not Zinin [Page 8]
INTERNET DRAFT Guidelines for LSA Refreshment July 2000 grouped by their age at all when they are transmitted in the database description and link-state update packets. In the worst case each refreshment group will contain a single LSA. However, even in this worst case, LSAs will be grouped by the age again after the first refreshment cycle, so the grouping algorithm presented above is self-optimizing. Below goes the functional specification of the refreshment algorithm. 1. Each originated (reoriginated) or received self-originated LSA is passed for registration to the LSA refreshment module 2. The LSA refreshment module bundles the LSAs submitted for registration into refresh groups. The LSAs in one group share the same timer. A group is flushed (see item 3) whenever one of the following three events happens: a) the periodical timer expires (every OSPF_REFRESH_GROUP_TIME seconds) b) after an LSA has been added to the group, the size of the group reaches OSPF_REFRESH_GROUP_LIMIT c) the age of the LSA to be added to the group differs from the age of the first LSA in the group more than OSPF_REFRESH_GROUP_AGE_DIF 3. when a group is flushed, perform the following action: a) calculate the delay for the refreshment event as presented in Figure 3 b) schedule the refreshment event with the delay calculated in the previous step, passing the LSA refresh group as the parameter to the event handling routine c) create a new LSA refresh group 4. When a refresh event is processed, put the LSAs in the refresh group associated with the event to the reorigination queue. 5 The reorigination queue is served not faster than OSPF_REFRESH_QUEUE_RATE LSAs per second The following table gives recommended values for the constants used in the algorithm description: Zinin [Page 9]
INTERNET DRAFT Guidelines for LSA Refreshment July 2000 Constant Recommended Value _________________________________________________ OSPF_LS_REFRESH_SHIFT 60 OSPF_LS_REFRESH_JITTER 10 OSPF_REFRESH_GROUP_TIME 1 OSPF_REFRESH_GROUP_LIMIT 10 OSPF_REFRESH_GROUP_AGE_DIF 3 OSPF_REFRESH_QUEUE_RATE 70 Table 1. Recommended values for constants used in algorithm Note that the constants shown above can be implemented as configur- able variables. However, the default values should be taken from the above table. It is also worth noting that presented algorithm can be used along with the extended LSA refresh period described in subsection 2.4 of this document. However, this would require all routers in the net- work to support DoNotAge LSAs, which may not be the case for some already deployed networks. LSA Refreshment Dispersion per se, in contrast, will possibly require software upgrade only on ASBRS and other routers originating a lot of LSAs. For more information on the described algorithm, please refer to the source code of Zebra routing software (governed by GNU GPL), avail- able at http://www.zebra.org. 4 Security Considerations The algorithm specified in this document does not raise any security issues that are not already covered in [Ref1]. 5 References [Ref1] J. Moy. OSPF version 2. Technical Report RFC 2328, Internet Engineering Task Force, 1998. ftp://ftp.isi.edu/in-notes/rfc2328.txt. [Ref2] J. Moy. Extending OSPF to Support Demand Circuits, Standards Track RFC 1793, Internet Engineering Task Force, 1998. ftp://ftp.isi.edu/in-notes/rfc1793.txt. Zinin [Page 10]
INTERNET DRAFT Guidelines for LSA Refreshment July 2000 6 Author's Address Alex D. Zinin Cisco Systems 150 West Tasman Dr. San Jose,CA 95134 E-mail: azinin@cisco.com Zinin [Page 11]
