view Side-By-Side changes

   Internet Engineering Task Force                 Gagan L. Choudhury
   Internet Draft                                  Vera D. Sapozhnikova
   Expires in May, September, 2003                      AT&T
   draft-ietf-ospf-scalability-02.txt
   Category: Best Current Practice
   draft-ietf-ospf-scalability-03.txt              Anurag S. Maunder
                                                   Sanera Systems

                                                   Vishwas Manral
                                                   Netplane Systems

                                                   November, 2002


    Explicit Marking and

                                                   March, 2003


           Prioritized Treatment of Specific OSPF 
           Packets
      for Faster Convergence and Improved Network Scalability and
                                 Stability Congestion Avoidance


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 and may be updated, replaced, or obsoleted by other documents
   at any time.  It is inappropriate to use Internet-Drafts as
   reference material or to cite them other than as "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.
   Distribution of this memo is unlimited.


Abstract

   In this draft we propose the following mechanisms

   This document proposes methods that are intended to improve the 
   scalability and stability of OSPF-based network:

   (1) Process the Hello packets large networks using OSPF protocol.
   The methods include processing OSPF Hellos and LSA Acknowledgements 
   at a higher priority compared to other OSPF packets.  In order to facilitate this, explicitly mark the 
       Hello packets, to differentiate them from and other OSPF packets.
       One way
   congestion avoidance procedures. Simulation results in support of special marking is to use a different Diffserv 
   some of the proposals are given in the appendix sections.
   
  
  

   Choudhury et. al.     Best Current Practice               [Page 1]

   Internet Draft          Explicit Marking                 May,        Prioritized Treatment        September, 2003


       codepoint for Hello packets compared to other

Table of Contents

   1. Motivation.....................................................2
   2. The Proposals..................................................3
   3. Security Considerations........................................4
   4. Acknowledgments................................................4
   5. References.....................................................5
   6. Authors' Addresses.............................................5
   Appendix A. LSA Storm: Causes and Impact..........................6
   Appendix B. Simulation Study......................................8
   Appendix B.1. The Network Under Simulation........................8
   Appendix B.2. Simulation Results.................................11
   Appendix B.3. Observations on Simulation Results.................15
   Appendix C. Other Proposals......................................15


1. Motivation  

   A large network running OSPF packets.

   (2) In [Ref1] or OSPF-TE [Ref2] protocol may 
   occasionally experience the absence simultaneous or near-simultaneous update 
   of special marking, a large number of link-state-advertisement messages, or LSAs.  
   We call this event, an LSA storm and it may be initiated by an
   unscheduled failure or a scheduled maintenance or upgrade event. 
   The failure may be hardware, software, or procedural in addition nature.
 
   The LSA storm causes high CPU and memory utilization at the node
   processors causing incoming packets to it, use 
       other mechanisms be delayed or dropped.  
   Delayed acknowledgements (beyond the retransmission timer value) 
   results in order not to miss retransmissions, and delayed Hello packets. One example
       is to treat any packet received over a link as a surrogate for packets (beyond the 
   router-dead interval) results in links being declared down. 
   The retransmissions and additional LSA generations result in further 
   CPU and memory usage, essentially causing a Hello packet (an implicit Hello) for positive feedback loop,
   which, in the purpose of keeping extreme case, may drive the link alive.

   (3) network to an unstable 
   state.

   The same type default value of explicit marking retransmission timer is 5 seconds and prioritized treatment may
       be beneficial to other OSPF packets as well.  One important 
       example is LSA acknowledgment packet that can reduce 
       retransmissions during periods of congestion.  Other examples 
       include (a) Database description (DBD) packet from a slave that 
   the router-dead interval is used as an acknowledgement, 40 seconds.  However, recently there 
   has been a lot of interest in significantly reducing OSPF convergence
   time and (b) LSAs carrying intra-area 
       topology change information.
   
   It is possible as part of that some implementations are already using one or plan much shorter (subsecond) Hello and
   router-dead intervals have been proposed [Ref3].  In such a scenario
   it will be more of likely for Hello packets to be delayed beyond
   the above mechanisms router-dead interval during a network congestion event
   caused by an LSA storm.

   Appendix A explains in more detail LSA storm generation scenarios,
   its impact, and points out a few real-life examples of control-message
   storm generation.  Appendix B presents a simulation study on this 
   phenomenon.



  
   Choudhury et. al.     Best Current Practice               [Page 2]

   Internet Draft        Prioritized Treatment        September, 2003

   In order not to miss improve the processing scalability and stability of networks we
   propose steps for prioritizing critical OSPF packets during periods of and avoiding
   congestion.  However, we suggest
   the above mechanisms to be included as part The details of the standard so that
   all implementations can benefit from them.


Table of Contents

   1. Introduction...................................................2 proposals are given
   in Section 2. The Network Under Simulation...................................5
   3. Simulation Results ............................................7
   4. Observations  We also do a simulation study on Simulation Results ...........................11
   5. Need for Prioritized Treatment a subset of Critical OSPF Packets and 
      Special Marking to Facilitate That............................12
   6. Summary.......................................................13
   7. Acknowledgments...............................................14
   8. References....................................................14
   9. Authors' Addresses............................................15


1. Introduction

   Due to world-wide increased traffic demand, data networks are ever 
   increasing in size the
   proposals in terms of number of nodes, number of links,
   adjacencies per node Appendix B and Link State Database size.  Our motivation
   is to show that they indeed improve the ability 
   scalability and stability of large networks using OSPF protocol.

   Appendix C provides some further proposals with similar goals.
  

2. The Proposals

   The proposals below are intended to withstand improve the simultaneous or near-simultaneous update scalability
   and stability of a large number networks using OSPF protocol.  During
   periods of
   link-state-advertisement messages, or LSAs.  We call this event, network congestion they would reduce retransmissions,
   avoid an
   LSA storm.  An LSA storm may be initiated due interface to many reasons.  Here
   are some examples:  

   (a) one or more link failures be declared down due to fiber cuts,

          
   Choudhury et. al.                                         [Page 2]

   Internet Draft          Explicit Marking                 May, 2003


   (b) one Hello packets 
   being delayed beyond the RouterDeadInterval, and take other
   congestion avoidance steps.

   Either all, or more node failures a subset of the proposals may be implemented by 
   a Router.  It is also possible for some reason, e.g., software
       crash routers to implement
   them fully or some type of disaster partially, and others to not implement them at
   all.
  

   (1) Classify all OSPF packets in an office complex hosting 
       many nodes,

   (c) requirement two classes: a "high priority"
       class comprising of taking down OSPF Hello packets and Link State 
       Acknowledgement packets, and later bringing back many 
       nodes during a software/hardware upgrade, 

   (d) near-synchronization of the once-in-30-minutes refresh instants
       of some types of LSAs, 

   (e) refresh "low priority" class
       comprising of all LSAs in other packets. The classification is
       accomplished by examining the system during OSPF packet header. While
       receiving a change in software 
       version.  

   In addition packet from a neighbor and while transmitting
       a packet to the LSAs generated as a direct result of link/node 
   failures, there may be other indirect LSAs as well.  One example 
   in MPLS networks is traffic engineering LSAs generated at other 
   links as neighbor, try to process a result of significant change in reserved bandwidth 
   resulting from rerouting "high priority" 
       packet ahead of Label Switched Paths (LSPs) a "low priority" packet.

   (2) Reset the Inactivity Timer for an interface whenever any OSPF
       packet is received over that went 
   down during interface (currently this is
       done only for the link/node failure.
 
   The LSA storm causes high CPU and memory utilization at Hello packet).
       So OSPF would declare the node
   processors causing incoming packets interface to be delayed down only if no
       OSPF packet is received over that interface for a period
       equaling or dropped.  
   Delayed acknowledgements (beyond exceeding the retransmission timer value) 
   results in retransmissions, and delayed Hello packets (beyond RouterDeadInterval.

   (3) Use an Exponential Backoff algorithm for determining the value
       of the 
   Router-Dead interval) results in links being declared down.  A
   trunk-down event causes Router LSA generation by its end-point
   nodes.  If traffic engineering LSAs are retransmission interval (RxmtInterval).  Let R(i) 
       represent the RxmtInterval value used for each link then
   that type during the i-th 
       retransmission of LSAs would also be generated by an LSA.  Use the end-point nodes
   and potentially elsewhere as well due following algorithm to significant changes in
   reserved bandwidths at other links caused by the failure 
       compute R(i)

                    R(1) = Rmin
                    R(i+1) = Min(KR(i),Rmax)  for i>=1



   Choudhury et. al.     Best Current Practice               [Page 3]

   Internet Draft        Prioritized Treatment        September, 2003

       where K, Rmin and Rmax are constants and reroute
   of LSPs originally using the failed trunk.  Eventually, when function
       Min(.,.) represents the
   link recovers that would also trigger additional Router minimum value of its two arguments.
       Example values for K, Rmin and traffic
   engineering LSAs.

   The retransmissions Rmax may be 2, 5 
       seconds and additional LSA generations result in further 
   CPU 40 seconds respectively.

   (4) Implicit Congestion Detection and memory usage, essentially causing Action Based on That:
       If there is control message congestion at a positive feedback loop.  
   We define the LSA storm size as node, its 
       neighbors do not know about that explicitly.  However, they 
       can implicitly detect it based on the number of unacknowledged
       LSAs in the original 
   storm and not counting any additional LSAs resulting from the  
   feedback loop described above. to this node.  If the LSA storm is too large this number exceeds a certain "high
       water mark" then the positive feedback loop mentioned above may be large enough rate at which LSAs are sent to 
   indefinitely sustain this node
       should be reduced.  At a large CPU and memory utilization at many 
   network nodes, thereby driving future time, if the network number of 
       unacknowledged LSAs to an unstable state.

   In this node falls below a certain "low
       water mark" then the past, network
   outage events have been reported in IP and ATM networks using 
   link-state protocols such as OSPF, IS-IS, PNNI or some proprietary 
   variants.  See, for example [Ref1-Ref4].  In many of these examples,
   large scale flooding normal rate of sending LSAs or other similar control messages 
   (either naturally or triggered by some bug or inappropriate 

          
   Choudhury et. al.                                         [Page 3]

   Internet Draft          Explicit Marking                 May, 2003


   procedure) have been partly or fully responsible for network 
   instability and outage. 

   It has been suggested [Ref5] to reduce this
       node should be resumed.  An example value for the Hello interval "high
       water mark" may be 20 unacknowledged LSAs and
   Router-Dead interval significantly in order that for OSPF to detect
   link failures and recoveries faster. Reduction of Router-Dead
   interval would make it even more likely the "low
       water mark" may be 10 unacknowledged LSAs.  An example
       value for links to the rate on exceeding the "high water mark" may be declared down
   due
       50% the normal rate.

   (5) Throttling Adjacencies to missed Hellos.

   We use be Brought Up Simultaneously:
       If a simulation model node tries to show that there is bring up a certain LSA storm
   size threshold above which the network may show unstable behavior 
   caused by large number of retransmissions, link failures due adjacencies to 
   missed Hello packets and subsequent link recoveries.  We also show
       its neighbors simultaneously then that the LSA storm size causing instability may be substantially
   increased by providing prioritized treatment cause severe
       congestion due to Hello database synchronization and LSA 
   Acknowledgment packets.  Furthermore, if we prioritize Hello 
   packets then even when the network operates somewhat above the 
   stability threshold, links are not declared down due to missed 
   Hellos.  This implies that even though there flooding
       activities.  It is 
   control plane congestion due to many retransmissions, the data plane
   stays up and no new LSAs are generated (besides the ones in the 
   original storm and the refreshes).  Based on these observations
   we propose prioritized treatment of Hello, LSA acknowledgment
   and other critical OSPF packets and a special marking to facilitate
   that.

   One might argue recommended that the scalability issue of large networks during such a situation
       no more than "n" adjacencies should be solved solely by dividing the network hierarchically into 
   multiple areas so that flooding brought up
       simultaneously.  Once a subset of LSAs remains localized within 
   areas.  However, this approach increases the network management 
   and design complexity and may result in less optimal routing between 
   areas. Also, ASE LSAs are flooded throughout the AS and it adjacencies have been brought 
       up successfully, newer adjacencies may be
   a problem if there are large numbers of them.  Furthermore, 
   a large brought up as long as 
       the number of summary LSAs simultaneous adjacencies being brought up does not
       exceed "n". An example value for "n" may need to be flooded across
   Areas and their numbers would increase significantly if 
   multiple Area Border Routers are employed 4. 
       
3. Security Considerations
   
   This memo does not create any new security issues for the purpose of
   reliability. Thus it is important to allow OSPF
   protocol.  Security considerations for the network to grow 
   towards as large a size as possible under a single area.  
   
   Our proposal here is synergistic with a broader set of scalability 
   and stability improvement proposals. [Ref6, Ref7] proposes flooding
   overhead reduction base OSPF protocol are
   covered in case more than one interface goes [Ref1].

4. Acknowledgments

   We would like to acknowledge the same
   neighbor.  [Ref8] proposes a mechanism for 
   greatly reducing LSA refreshes in stable topologies. [Ref9] compares
   several restricted flooding algorithms in terms support of their ability to
   withstand large LSA storms OSPF WG chairs
   Rohit Dube, Acee Lindem, and robustness to failure conditions.
   [Ref10] proposes a wide range of congestion control John Moy.  We also acknowledge 
   Jerry Ash, Margaret Chiosi, Elie 
   Francis, Jeff Han, Beth Munson, Roshan Rao, Moshe Segal, Mike
   Wardlow, and failure 
   recovery mechanisms. Pat Wirth for collaboration and encouragement in 
   our scalability improvement efforts for Link-State-Protocol based 
   networks. 






   Choudhury et. al.     Best Current Practice               [Page 4]

   Internet Draft          Explicit Marking                 May,        Prioritized Treatment        September, 2003


   Section 2 describes the network under simulation and Section 3
   provides the simulation results.  Section 4 gives the basic
   observations based on the simulation results.  Section 5 explains
   the need for prioritized treatment of certain critical


5. References

   [Ref1] J. Moy, "OSPF Version 2", RFC 2328, April, 1998.

   [Ref2] D. Katz, D. Yeung, K. Kompella, "Traffic Engineering
   Extension to OSPF packets Version 2," Work in Progress.

   [Ref3] C. Alaettinoglu, V. Jacobson and special marking to facilitate that.  Section 6 gives the summary.
          

2. The H. Yu, "Towards Milli-
   second IGP Convergence," Work in Progress.

   [Ref4] Pappalardo, D., "AT&T, customers grapple with ATM net 
   outage," Network Under Simulation

   We generate a random network over a rectangular grid using a  
   modified version World, February 26, 2001.

   [Ref5] "AT&T announces cause of Waxman's algorithm [Ref11] that ensures that 
   the frame-relay network is connected and has a pre-specified number of nodes, 
   links, maximum number of neighbors per node, outage," AT&T 
   Press Release, April 22, 1998.

   [Ref6] Cholewka, K., "MCI Outage Has Domino Effect," Inter@ctive 
   Week, August 20, 1999.

   [Ref7] Jander, M., "In Qwest Outage, ATM Takes Some Heat," Light
   Reading, April 6, 2001.

   [Ref8] A. Zinin and maximum number  
   of adjacencies per node. The rectangular grid resembles the 
   continental U.S.A. with maximum one-way propagation delay of 30 ms M. Shand, "Flooding Optimizations in the East-West direction and maximum one-way propagation delay of 
   15 ms Link-State
   Routing Protocols," Work in the North-South direction.  We consider two different 
   network sizes Progress.

   [Ref9] J. Moy, "Flooding over Parallel Point-to-Point Links," Work in
   progress.

   [Ref10] P. Pillay-Esnault, "OSPF Refresh and flooding reduction in  
   stable topologies," Work in progress.

   [Ref11] J. Ash, G. Choudhury, V. Sapozhnikova, M. Sherif, A.  
   Maunder, V. Manral, "Congestion Avoidance & Control for OSPF 
   Networks", Work in Progress.

   [Ref12] B. M. Waxman, "Routing of Multipoint Connections," IEEE
   Journal on Selected Areas in Communications, 6(9):1617-1622, 1988.

   
6. Authors' Addresses

   Gagan L. Choudhury
   AT&T
   Room D5-3C21
   200 Laurel Avenue
   Middletown, NJ, 07748
   USA
   Phone: (732)420-3721
   email: gchoudhury@att.com


   Choudhury et. al.     Best Current Practice               [Page 5]

   Internet Draft        Prioritized Treatment        September, 2003

   Vera D. Sapozhnikova
   AT&T
   Room C5-2C29
   200 Laurel Avenue
   Middletown, NJ, 07748
   USA
   Phone: (732)420-2653
   email: sapozhnikova@att.com

   Anurag S. Maunder
   Sanera Systems
   370 San Aleso Ave.
   Second Floor
   Sunnyvale, CA 94085
   Phone: (408)734-6123
   email: amaunder@sanera.net

   Vishwas Manral
   NetPlane
   189, Prashasan Nagar,
   Road Number 72
   Jubilee Hills, Hyderabad
   India
   email: Vishwasm@netplane.com




Appendix A. LSA Storm: Causes and Impact

   An LSA storm may be initiated due to many reasons.  Here
   are some examples:  

   (a) one or more link failures due to fiber cuts,

   (b) one or more node failures for some reason, e.g., software
       crash or some type of disaster (including power outage)
       in an office complex hosting many nodes,

   (c) Link/node flapping,

   (d) requirement of taking down and later bringing back many 
       nodes during a software/hardware upgrade, 

   (e) near-synchronization of the once-in-30-minutes refresh instants
       of a subset of LSAs, 

   (f) refresh of all LSAs in the system during a change in software 
       version,  



   Choudhury et. al.     Best Current Practice               [Page 6]

   Internet Draft        Prioritized Treatment        September, 2003
 
   (g) injecting a large number of external routes to OSPF due to
       a procedural error.

   In addition to the LSAs generated as explained a direct result of link/node 
   failures, there may be other indirect LSAs as well.  One example 
   in MPLS networks is traffic engineering LSAs generated at other 
   links as a result of significant change in reserved bandwidth 
   resulting from rerouting of Label Switched Paths (LSPs) that went 
   down during the link/node failure.

   The LSA storm causes high CPU and memory utilization at the node
   processors causing incoming packets to be delayed or dropped.  
   Delayed acknowledgements (beyond the retransmission timer value) 
   results in retransmissions, and delayed Hello packets (beyond the 
   Router-Dead interval) results in Section 3.

   The network has a flat, single-area topology.

   Each node is a links being declared down.  A
   trunk-down event causes Router and LSA generation by its end-point
   nodes.  If traffic engineering LSAs are used for each link is a point-to-point then
   that type of LSAs would also be generated by the end-point nodes
   and potentially elsewhere as well due to significant changes in
   reserved bandwidths at other links caused by the failure and reroute
   of LSPs originally using the failed trunk.  Eventually, when the
   link 
   connecting two routers.

   We assume recovers that node would also trigger additional Router and traffic
   engineering LSAs.

   The retransmissions and additional LSA generations result in further 
   CPU and memory (not usage, essentially causing a positive feedback loop.  
   We define the link bandwidth) is LSA storm size as the 
   main bottleneck number of LSAs in the original 
   storm and not counting any additional LSAs resulting from the  
   feedback loop described above.  If the LSA flooding process.  This will typically storm is too large then

   the positive feedback loop mentioned above may be true large enough to 
   indefinitely sustain a large CPU and memory utilization at many 
   network nodes, thereby driving the network to an unstable state.
   In the past, network
   outage events have been reported in IP and ATM networks using 
   link-state protocols such as OSPF, IS-IS, PNNI or some proprietary 
   variants.  See, for high speed links (e.g., OC3 example [Ref4-Ref7].  In many of these examples,
   large scale flooding of LSAs or other similar control messages 
   (either naturally or triggered by some bug or inappropriate 
   procedure) have been partly or above) and/or links 
   where OSPF traffic gets an adequate Quality of Service (QoS) 
   compared to other traffic.
 
   Different Timers: 
     LSA refresh interval = 1800 seconds, 
     Hello refresh interval = 10 Seconds, 
     Router-Dead interval = 40 seconds, 
     LSA retransmission interval: two values are considered, 10 seconds fully responsible for network 
   instability and 5 Seconds (note that outage.

   In Appendix B, we use a retransmission simulation model to show that there 
   is disabled on the 
       receipt of either an explicit acknowledgment or a duplicate certain LSA
       over the same interface that acts as an implicit acknowledgment) 
     Minimum time between successive generation of storm
   size threshold above which the same LSA = 5 
       seconds, 
     Minimum time between successive Dijkstra SPF calculations 
       is 1 second.

   Packing network may show unstable behavior 
   caused by large number of LSAs: It is assumed retransmissions, link failures due to 
   missed Hello packets and subsequent link recoveries.  We also show
   that for any given node, the LSAs 
   generated over a 1-second period are packed together LSA storm size causing instability may be substantially
   increased by providing prioritized treatment to form Hello and LSA 
   Acknowledgment packets and by using an LSU 
   but no more than 3 LSAs are packed in one LSU.

   LSU/Ack/Hello Processing Times: All processing times are expressed  
   in terms of the parameter T.  Two values of T are considered, 1 ms exponential backoff


   Choudhury et. al.     Best Current Practice               [Page 5] 7]

   Internet Draft          Explicit Marking                 May,        Prioritized Treatment        September, 2003

   algorithm for determining the LSA retransmission interval.  
   Furthermore, if we prioritize Hello 
   packets then even when the network operates somewhat above the 
   stability threshold, links are not declared down due to missed 
   Hellos.  This implies that even though there is 
   control plane congestion due to many retransmissions, the data plane
   stays up and 0.5 ms.

   In no new LSAs are generated (besides the case of a dedicated processor for processing OSPF packets ones in the 
   processing time reported represents 
   original storm and the true processing time. If refreshes).  These observations are the 
   processor does other work and only a fraction
   basis of its capacity can be 
   dedicated to OSPF processing then we have to inflate the processing 
   time appropriately to get the effective processing time and first three proposals in that 
   case it is assumed Section 2.

   One might argue that the inflation factor is already taken scalability issue of large networks should
   be solved solely by dividing the network hierarchically into 
   account as part 
   multiple areas so that flooding of LSAs remains localized within 
   areas.  However, this approach increases the reported processing time. 

   The fixed time to send or receive any LSU, Ack or Hello packet is T.
   In addition, a variable processing time is used for LSU network management 
   and Ack 
   depending on the number design complexity and types of may result in less optimal routing between 
   areas. Also, ASE LSAs packed.  No variable 
   processing time is used for Hello.
   Variable processing time per Router LSA is (0.5 + 0.17L)T where L is 
   the number of adjacencies advertised by are flooded throughout the Router LSA.  For other 
   LSA types (e.g., ASE LSA or AS and it may be
   a "Link" LSA carrying traffic 
   engineering information about problem if there are large numbers of them.  Furthermore, 
   a link), the variable processing time  
   per LSA is 0.5T.

   Variable processing time for an Ack is 25% that large number of the corresponding 
   LSA.

   It is summary LSAs may need to be noted that flooded across
   Areas and their numbers would increase significantly if 
   multiple LSAs Area Border Routers are packed in a single LSU 
   packet then employed for the fixed processing time purpose of
   reliability. Thus it is needed only once but important to allow the 
   variable processing time network to grow 
   towards as large a size as possible under a single area.  
   
   Our proposal here is needed for every component synergistic with a broader set of the 
   packet.
 
   The processing time values we use are roughly scalability 
   and stability improvement proposals. [Ref8, Ref9] proposes flooding
   overhead reduction in case more than one interface goes to the same
   neighbor.  [Ref10] proposes a mechanism for 
   greatly reducing LSA refreshes in stable topologies.
   [Ref11] proposes a wide range of 
   what has been observed in an operational network.

   LSU/Ack/Hello Priority: Two non-preemptive priority levels congestion control and
   three priority scenarios are considered. Within each priority level 
   processing is FIFO with new packets failure 
   recovery mechanisms.   

Appendix B. Simulation Study

   The main motivation of lower priority being
   dropped when the lower priority queue this study is full.  The higher priority
   packets are never dropped.    
      In Priority scenario 1, all LSUs/Acks/Hellos received at a node 
      are queued at to show the lower priority.
      In Priority scenario 2, Hellos received at a node are queued at network congestion
   and instability caused by large LSA storms and the higher priority but LSUs/Acks are queued at lower priority.
      In Priority scenario 3, Hellos improvement in
   stability and Acks received at scalability that can be achieved by following the
   proposals in this memo.

Appendix B.1. The Network Under Simulation

   We generate a random network over a node are 
      queued at the higher priority but LSUs are queued at lower 
      priority. 
   All packets generated internally to rectangular grid using a node (usually triggered by  
   modified version of Waxman's algorithm [Ref12] that ensures that 
   the network is connected and has a timer) are processed at pre-specified number of nodes, 
   links, maximum number of neighbors per node, and maximum number  
   of adjacencies per node. The rectangular grid resembles the higher priority.  This includes 
   continental U.S.A. with maximum one-way propagation delay of 30 ms 
   in the 
   initial LSA storm, LSA refresh, Hello refresh, LSA retransmission East-West direction and new LSA generation after detection maximum one-way propagation delay of 
   15 ms in the North-South direction.  We consider two different 
   network sizes as explained in Section B.2.

   The network has a failure or recovery.

   Buffer Size for Incoming LSUs/Acks/Hellos (lower priority): Buffer flat, single-area topology.

   Choudhury et. al.     Best Current Practice               [Page 6] 8]

   Internet Draft          Explicit Marking                 May,        Prioritized Treatment        September, 2003


   size
 
   Each node is assumed to be 2000 packets where a packet is either an Ack, 
   LSU, or Hello. 

   LSA Refresh: Each LSA Router and each link is refreshed once in 1800 seconds a point-to-point link 
   connecting two routers.

   We assume that node CPU and memory (not the 
   refresh instants of various LSAs link bandwidth) is the 
   main bottleneck in the LSDB are assumed to LSA flooding process.  This will typically 
   be 
   uniformly distributed over the 1800 seconds period, i.e., they are 
   completely unsynchronized.  If however, true for high speed links (e.g., OC3 or above) and/or links 
   where OSPF traffic gets an LSA is generated as part adequate Quality of the initial Service (QoS) 
   compared to other traffic.

   Different Timers: 
     LSA storm then it goes on a new refresh schedule of 
   once in interval = 1800 seconds starting from its generation time. seconds, 
     Hello refresh interval = 10 Seconds, 
     Router-Dead interval = 40 seconds, 
     LSA Storm Generation: As defined earlier, "LSA storm" is the 
   simultaneous or near simultaneous generation of a large number of 
   LSAs. In the case of only Router retransmission interval: two values are considered, 10 seconds 
       and ASE LSAs we normally assume 5 Seconds (note that the number of ASE LSAs in the storm a retransmission is about 4 times that of  
   the Router LSAs, but disabled on the ratio is allowed to change if 
       receipt of either the  
   Router an explicit acknowledgment or a duplicate LSA
       over the ASE LSAs have reached their maximum possible value.   
   In the case of only Router and Link LSAs (carrying traffic  
   engineering information) we normally assume same interface that the number acts as an implicit acknowledgment) 
     Minimum time between successive generation of Link  
   LSAs in the storm same LSA = 5 
       seconds, 
     Minimum time between successive Dijkstra SPF calculations 
       is about 4 times that 1 second.

   Packing of the Router LSAs, but the  
   ratio LSAs: It is allowed to change if either the Router or the Link LSAs  
   have reached their maximum possible value.  For assumed that for any given LSA storm  
   we keep generating LSAs starting from Node index 1 and moving  
   upwards and stop until node, the correct number of LSAs of each type have  
   been generated.  The LSAs 
   generated at any given node is assumed over a 1-second period are packed together to  
   start at form an instant uniformly distributed between 20 LSU 
   but no more than 3 LSAs are packed in one LSU.

   LSU/Ack/Hello Processing Times: All processing times are expressed  
   in terms of the parameter T.  Two values of T are considered, 1 ms
   and 30 seconds 
   from 0.5 ms.

   In the start case of a dedicated processor for processing OSPF packets the simulation.  Successive LSA generations at 
   processing time reported represents the true processing time. If the 
   processor does other work and only a  
   node are assumed to fraction of its capacity can be spaced apart by 400 ms. It is 
   dedicated to be noted  
   that during OSPF processing then we have to inflate the period of observation there are other LSAs  
   generated besides processing 
   time appropriately to get the ones effective processing time and in the storm.  These include refresh of  
   LSAs that are not 
   case it is assumed that the inflation factor is already taken into 
   account as part of the storm and LSAs generated due reported processing time. 

   The fixed time to  
   possible link failures and subsequent possible link recoveries.

   Failure/Recovery of Links: If no send or receive any LSU, Ack or Hello packet is received over T.
   In addition, a link (due 
   to CPU/memory congestion) for longer than Router-Dead Interval then
   the link variable processing time is declared down.  At a later time, if Hellos are received
   then used for LSU and Ack 
   depending on the link would be declared up.  Whenever a link number and types of LSAs packed.  No variable 
   processing time is declared
   up or down, one used for Hello.
   Variable processing time per Router LSA is generated by each Router on (0.5 + 0.17L)T where L is 
   the
   two sides number of adjacencies advertised by the point-to-point link.  If "Link LSAs" Router LSA.  For other 
   LSA types (e.g., ASE LSA or a "Link" LSA carrying traffic 
   engineering information about a link), the variable processing time  
   per LSA is used then it 0.5T.

   Variable processing time for an Ack is assumed 25% that each
   Router would also generate a Link of the corresponding 
   LSA.  In this case it


   Choudhury et. al.     Best Current Practice               [Page 9]

   Internet Draft        Prioritized Treatment        September, 2003

   It is also 
   assumed that due to rerouting of LSPs, three other links in the 
   network (selected randomly in the simulation) would have significant 
   change in reserved bandwidth which would result be noted that if multiple LSAs are packed in one Link LSA 
   being generated by a single LSU 
   packet then the routers on fixed processing time is needed only once but the two ends 
   variable processing time is needed for every component of each such link.


3. Simulation Results

   In this section the 
   packet.
 
   The processing time values we study use are roughly in the relative performance same range of the 
   what has been observed in an operational network.

   LSU/Ack/Hello Priority: Two non-preemptive priority levels and
   three 

          
   Choudhury et. al.                                         [Page 7]

   Internet Draft          Explicit Marking                 May, 2003


   Priority priority scenarios defined earlier (no are considered. Within each priority to Hello or Ack, level 
   processing is FIFO with new packets of lower priority to Hello only, being
   dropped when the lower priority queue is full.  The higher priority
   packets are never dropped.    
      In Priority scenario 1, all LSUs/Acks/Hellos received at a node 
      are queued at the lower priority.
      In Priority scenario 2, Hellos received at a node are queued at 
      the higher priority but LSUs/Acks are queued at lower priority.
      In Priority scenario 3, Hellos and Acks received at a node are 
      queued at the higher priority but LSUs are queued at lower 
      priority. 
   All packets generated internally to both Hello and Ack) with a 
   range of Network sizes, node (usually triggered by 
   a timer) are processed at the higher priority.  This includes the 
   initial LSA retransmission timer values, storm, LSA types, 
   processing time values and Hello/Router-Dead-Interval values:
   
   Network size: Two networks are considered.  Network 1 has 100 nodes, 
   1200 links, maximum number of neighbors per node is 30 and maximum 
   number of adjacencies per node is 50 (same neighbor may have more 
   than one adjacencies).   Network 2 has 50 nodes, 600 links, maximum 
   number of neighbors per node is 25 refresh, Hello refresh, LSA retransmission 
   and maximum number new LSA generation after detection of adjacencies 
   per node is 48. Dijkstra SPF calculation time a failure or recovery.

   Buffer Size for Network 1 Incoming LSUs/Acks/Hellos (lower priority): Buffer 
   size is assumed to be 100 ms and that for Network 2 2000 packets where a packet is assumed to be 70 ms. either an Ack, 
   LSU, or Hello. 

   LSA Type: Refresh: Each node has 1 Router LSA (Total of 100 for Network 1 is refreshed once in 1800 seconds and 
   50 for Network 2). There are no Network the 
   refresh instants of various LSAs since all links in the LSDB are 
   point-to-point links and no Summary LSAs since assumed to be 
   uniformly distributed over the network has only 
   one area. Regarding other 1800 seconds period, i.e., they are 
   completely unsynchronized.  If however, an LSA is generated as part 
   of the initial LSA storm then it goes on a new refresh schedule of 
   once in 1800 seconds starting from its generation time.   

   LSA types we consider two situations. Storm Generation: As defined earlier, "LSA storm" is the 
   simultaneous or near simultaneous generation of a large number of 
   LSAs. In  
   Situation 1 we assume that there are no ASE LSAs and each link has  
   one "Link" LSA carrying traffic engineering information (Total the case of  
   2400 for Network 1 only Router and 1200 for Network 2). In Situation 2 ASE LSAs we normally assume  
   that there are no "Link" LSAs and half of the nodes are ASA-Border  
   nodes and each border node has 10 number of ASE LSAs (Total of 500 for  
   Network 1 and 250 for Network 2).  We identify Situation 1 as "Link  
   LSAs" and Situation 2 as "ASE LSAs".

   LSA retransmission timer value: Two values are considered, 10 
   seconds and 5 seconds (default value).

   Processing time values: Processing times for LSUs, Acks and Hello 
   packets have been previously expressed in terms of a common  
   parameter T.  Two values are considered for T, which are 1 ms 
   and 0.5 ms respectively.
   
   Hello/Router-Dead-Interval: It the storm is assumed about 4 times that Router-Dead interval of  
   the Router LSAs, but the ratio is four times allowed to change if either the Hello interval.  
   Router or the ASE LSAs have reached their maximum possible value.   
   In one the case it of only Router and Link LSAs (carrying traffic  
   engineering information) we normally assume that the number of Link  
   LSAs in the storm is assumed about 4 times that
   Hello interval of the Router LSAs, but the  
   ratio is 10 seconds allowed to change if either the Router or the Link LSAs  
   have reached their maximum possible value.  For any given LSA storm  
   we keep generating LSAs starting from Node index 1 and Router-Dead-Interval is 40
   seconds (default values), moving  
   upwards and in stop until the other case it correct number of LSAs of each type have  
   been generated.  The LSAs generated at any given node is assumed that 
   Hello interval is 2 seconds and Router-Dead-Interval is 8 seconds. 

   Based on Network size, LSA type to  
   start at an instant uniformly distributed between 20 and processing time values we 
   develop 6 Test cases as follows:

   Case 1: Network 1, Link LSAs, retransmission timer = 10 sec., 
           T = 1 ms, Hello/Router-Dead-Interval = 10/40 sec.

   Case 2: Network 1, ASE LSAs, retransmission timer = 10 sec., 
           T = 1 ms, Hello/Router-Dead-Interval = 10/40 sec.

   Case 3: Network 1, Link LSAs, retransmission timer = 5 sec., 30 seconds 

   Choudhury et. al.     Best Current Practice               [Page 8] 10]

   Internet Draft          Explicit Marking                 May,        Prioritized Treatment        September, 2003


           T = 1 ms, Hello/Router-Dead-Interval = 10/40 sec.

   Case 4: Network 1, Link LSAs, retransmission timer = 10 sec., 
           T = 0.5 ms, Hello/Router-Dead-Interval = 10/40 sec.

   Case 5: Network 1, Link LSAs, retransmission timer = 10 sec., 
           T = 1 ms, Hello/Router-Dead-Interval = 2/8 sec.

   Case 6: Network 2, Link LSAs, retransmission timer = 10 sec., 
           T = 1 ms, Hello/Router-Dead-Interval = 10/40 sec.


   For each case and for each Priority scenario we study

   from the start of the simulation.  Successive LSA generations at a  
   node are assumed to be spaced apart by 400 ms. It is to be noted  
   that during the period of observation there are other LSAs  
   generated besides the ones in the network 
   stability as a function storm.  These include refresh of  
   LSAs that are not part of the size storm and LSAs generated due to  
   possible link failures and subsequent possible link recoveries.

   Failure/Recovery of Links: If no Hello is received over a link (due 
   to CPU/memory congestion) for longer than Router-Dead Interval then
   the LSA storm.  The stability link is determined by looking at declared down.  At a later time, if Hellos are received
   then the number of non-converged LSUs as link would be declared up.  Whenever a   
   function of time. An example link is shown in Table 1 for Case 1 and 
   Priority scenario 1 (No priority to Hellos declared
   up or Acks).
   
=========|==========================================================
         | Number of Non-Converged LSUs in the Network at Time(in sec)
    LSA  |                    
   STORM |====|=====|=====|=====|=====|=====|=====|=====|========|==
   SIZE  |10s | 20s | 30s | 35s | 40s | 50s | 60s | 80s | 100s   |
=========|====|=====|=====|=====|=====|=====|=====|=====|========|==
    100  | 0  |  0  | 24  | 29  | 24  |  1  |  0  |  1  |  1     |
 (Stable)|    |     |     |     |     |     |     |     |        |
---------|----|-----|-----|-----|-----|-----|-----|-----|--------|--
    140  | 0  |  0  | 35  | 48  | 46  | 27  | 14  |  1  |  1     |
 (Stable)|    |     |     |     |     |     |     |     |        |
---------|----|-----|-----|-----|-----|-----|-----|-----|--------|--
    160  | 0  |  0  | 38  | 57  | 55  | 40  | 26  | 65  | 203    |
(Unstable)    |     |     |     |     |     |     |     |        |
=========|==========================================================

           Table 1: Network Stability Vs. down, one Router LSA Storm 
              (Case 1, No priority is generated by each Router on the
   two sides of the point-to-point link.  If "Link LSAs" carrying
   traffic engineering information is used then it is assumed that each
   Router would also generate a Link LSA.  In this case it is also 
   assumed that due to Hello/Ack)

   

   The rerouting of LSPs, three other links in the 
   network (selected randomly in the simulation) would have significant 
   change in reserved bandwidth which would result in one Link LSA storm starts a little after 20 seconds and so for some 
   period 
   being generated by the routers on the two ends of time after that each such link.


Appendix B.2. Simulation Results

   In this section we study the number relative performance of non-converged LSUs should
   stay high the three 
   priority scenarios defined earlier (no priority to Hello or Ack, 
   priority to Hello only, and then come down for priority to both Hello and Ack) with a stable network. 
   This happens for LSA storms 
   range of sizes 100 and 140.  With an Network sizes, LSA storm retransmission timer values, LSA types, 
   processing time values and Hello/Router-Dead-Interval values:

   Network size: Two networks are considered.  Network 1 has 100 nodes, 
   1200 links, maximum number of size 160, the neighbors per node is 30 and maximum 
   number of non-converged LSUs stay high indefinitely
   due to repeated retransmissions, link failures due to missed Hellos  
   for adjacencies per node is 50 (same neighbor may have more 
   than the Router-Dead interval which generates additional 
   LSAs and also due to subsequent link recoveries which again 
   generate additional LSAs.  We define network stability threshold as
   the one adjacencies).   Network 2 has 50 nodes, 600 links, maximum 
   number of neighbors per node is 25 and maximum allowable LSA storm size for which the number of 

          
   Choudhury et. al.                                         [Page 9]

   Internet Draft          Explicit Marking                 May, 2003


   non-converged LSUs come down adjacencies 
   per node is 48. Dijkstra SPF calculation time for Network 1 is  
   assumed to a low level after some time. It 
   turns out be 100 ms and that for this example the stability threshold Network 2 is
   150. 

   The network behavior as a function of the LSA storm size can assumed to be categorized as follows:

   (1) If the 70 ms.

   LSA storm is well below the stability threshold then
       the CPU/memory congestion lasts only Type: Each node has 1 Router LSA (Total of 100 for a short period Network 1 and
       during this period there 
   50 for Network 2). There are very few retransmissions, very
       few dropped OSPF packets and no link
       failures due to missed Hellos.  This type of LSA storms Network LSAs since all links are
       observed routinely in operational networks 
   point-to-point links and networks
       recover from them easily.

   (2) If no Summary LSAs since the network has only 
   one area. Regarding other LSA storm is just below the stability threshold then
       the CPU/memory congestion lasts for a longer period and during
       this period types we consider two situations.  In  
   Situation 1 we assume that there may be considerable amount of retransmissions
       and dropped OSPF packets.  If Hello packets are not given
       priority then there may also be some link failures due to
       missed Hellos.  However, the network does go back to a stable
       state eventually. This type of LSA storm may happen rarely in
       operational networks and they recover from it with some
       difficulty. 

   (3) If the no ASE LSAs and each link has  
   one "Link" LSA storm is above the stability threshold then
       the CPU/memory congestion may last indefinitely unless
       some special procedure carrying traffic engineering information (Total of  
   2400 for relieving congestion is followed. 
       During this period Network 1 and 1200 for Network 2). In Situation 2 we assume
   that there are considerable amount of 
       retransmissions no "Link" LSAs and dropped OSPF packets.  If Hello packets half of the nodes are
       not given priority then there would also be link failures due 
       to missed Hellos.  This type ASA-Border  
   nodes and each border node has 10 ASE LSAs (Total of LSA storm may happen very 
       rarely in operational networks 500 for  
   Network 1 and usually some manual procedure
       such 250 for Network 2).  We identify Situation 1 as taking down adjacencies in heavily congested nodes is
       needed.

   (4) If "Link  
   LSAs" and Situation 2 as "ASE LSAs".

   LSA retransmission timer value: Two values are considered, 10 
   seconds and 5 seconds (default value).

   Choudhury et. al.     Best Current Practice               [Page 11]

   Internet Draft        Prioritized Treatment        September, 2003
   
   Processing time values: Processing times for LSUs, Acks and Hello 
   packets are given priority then the network stability
       threshold increases, i.e., the network can withstand have been previously expressed in terms of a larger
       LSA storm. Furthermore, even if the network operates at or 
       somewhat above this higher stability threshold, Hellos common  
   parameter T.  Two values are 
       still not missed considered for T, which are 1 ms 
   and 0.5 ms respectively.

   Hello/Router-Dead-Interval: It is assumed that Router-Dead interval
   is four times the Hello interval.  In one case it is assumed that
   Hello interval is 10 seconds and so there are no link failures.  So even 
       if there Router-Dead-Interval is congestion 40
   seconds (default values), and in the control plane due to increased 
       retransmissions requiring some special procedures for congestion
       reduction, the data plane remains unaffected.
        
   (5) If both other case it is assumed that 
   Hello and Acknowledgement packets are given priority
       then the stability threshold increases even further.       
   


          
   Choudhury et. al.                                         [Page 10]

   Internet Draft          Explicit Marking                 May, 2003


   In Table interval is 2 we show the network stability threshold for the five  
   different cases seconds and for the three different priority scenarios
   defined earlier.  

|===========|========================================================|
|           |    Maximum Allowable Router-Dead-Interval is 8 seconds. 

   Based on Network size, LSA Storm Size For                |
|   Case    |=================|==================|===================|
|  Number   | No Priority to  |Priority to Hello | Priority to Hello |
|           |  Hello or Ack   |      Only        | type and Ack         |
|===========|=================|==================|===================|
| processing time values we 
   develop 6 Test cases as follows:

   Case 1: Network 1, Link LSAs, retransmission timer = 10 sec., 
           T = 1  |        150      |        190       |        250        |
|___________|_________________|__________________|___________________|
| ms, Hello/Router-Dead-Interval = 10/40 sec.

   Case 2  |        185      |        215       |        285        |
|___________|_________________|__________________|___________________|
| 2: Network 1, ASE LSAs, retransmission timer = 10 sec., 
           T = 1 ms, Hello/Router-Dead-Interval = 10/40 sec.

   Case 3  |        115      |        127       |        170        |
|___________|_________________|__________________|___________________|
| 3: Network 1, Link LSAs, retransmission timer = 5 sec., 
           T = 1 ms, Hello/Router-Dead-Interval = 10/40 sec.

   Case 4  |        320      |        375       |        580        |
|___________|_________________|__________________|___________________|
| 4: Network 1, Link LSAs, retransmission timer = 10 sec., 
           T = 0.5 ms, Hello/Router-Dead-Interval = 10/40 sec.

   Case 5  |        120      |        175       |        225        |
|___________|_________________|__________________|___________________|
| 5: Network 1, Link LSAs, retransmission timer = 10 sec., 
           T = 1 ms, Hello/Router-Dead-Interval = 2/8 sec.

   Case 6  |        185      |        224       |        285        |
|___________|_________________|__________________|___________________|

       Table 2: Maximum Allowable LSA Storm for a Stable 6: Network


4. Observations on Simulation Results

   Table 2 shows that in all cases prioritizing Hello packets increases
   the network stability threshold, 2, Link LSAs, retransmission timer = 10 sec., 
           T = 1 ms, Hello/Router-Dead-Interval = 10/40 sec.

   For each case and in addition, prioritization of  
   LSA Acknowledgment packets increases the stability threshold even
   further.  The reasons for each Priority scenario we study the above observations are network 
   stability as follows.
   The main sources of sustained CPU/memory congestion (or positive
   feedback loop) following an LSA storm are (1) LSA retransmissions 
   and (2) links being declared down due to missed Hellos which in 
   turn causes further LSA generation and future recovery a function of the link   
   causing even more LSA generation. 
   Prioritizing Hello packets avoids and practically eliminates the
   second source size of congestion.  Prioritizing Acknowledgements 
   significantly reduces the first source of congestion, i.e., LSA retransmissions.  It storm.  The stability
   is to be noted that retransmissions can
   not be completely eliminated due to the following reasons. Firstly,
   only the explicit Acknowledgments are prioritized but duplicate
   LSAs carrying implicit Acknowledgments are still served at the 
   lower priority.  Secondly, LSAs may get greatly delayed or dropped determined by looking at the input queue number of receivers and therefore Acknowledgments may
   not even get generated non-converged LSUs as a   
   function of time. An example is shown in which case prioritizing Acks would not   
   help. Another factor Table 1 for Case 1 and 
   Priority scenario 1 (No priority to keep in mind is that since Hellos and Acks  
   are prioritized, the LSAs see bigger delay and potential for or Acks).















   Choudhury et. al.     Best Current Practice               [Page 11] 12]

   Internet Draft          Explicit Marking                 May,        Prioritized Treatment        September, 2003


   dropping. However, the simulation results show that on the whole 
   prioritizing Hello and LSA Acks are always beneficial and 
   significantly improve the network stability threshold.    

   Our simulation study also showed that in each of the cases, instead
   
   
=========|==========================================================
         | Number of prioritizing Hello packets if we treat any packet received over 
   a link as a surrogate for a Hello packet (an implicit Hello) then
   we get about the same stability threshold as obtained with
   prioritizing Hello packets.

   If we prioritize Hello packets then even when the network operates
   somewhat above Non-Converged LSUs in the stability threshold, links are not declared
   down due to missed Hellos.  This implies that even though there is 
   control plane congestion due Network at Time(in sec)
    LSA  |                    
   STORM |====|=====|=====|=====|=====|=====|=====|=====|========|==
   SIZE  |10s | 20s | 30s | 35s | 40s | 50s | 60s | 80s | 100s   |
=========|====|=====|=====|=====|=====|=====|=====|=====|========|==
    100  | 0  |  0  | 24  | 29  | 24  |  1  |  0  |  1  |  1     |
 (Stable)|    |     |     |     |     |     |     |     |        |
---------|----|-----|-----|-----|-----|-----|-----|-----|--------|--
    140  | 0  |  0  | 35  | 48  | 46  | 27  | 14  |  1  |  1     |
 (Stable)|    |     |     |     |     |     |     |     |        |
---------|----|-----|-----|-----|-----|-----|-----|-----|--------|--
    160  | 0  |  0  | 38  | 57  | 55  | 40  | 26  | 65  | 203    |
(Unstable)    |     |     |     |     |     |     |     |        |
=========|==========================================================

           Table 1: Network Stability Vs. LSA Storm 
              (Case 1, No priority to many retransmissions, the data plane
   stays up and no new LSAs are generated (besides the ones in the 
   original Hello/Ack)

   The LSA storm starts a little after 20 seconds and the refreshes)   


5. Need so for Prioritized Treatment some 
   period of Critical OSPF Packets and
   Special Marking to Facilitate That 

   The observations in the previous section clearly show time after that
   prioritizing Hello the number of non-converged LSUs should
   stay high and then come down for a stable network. 
   This happens for LSA Acknowledgment packets are greatly
   beneficial in improving the scalability storms of sizes 100 and stability 140.  With an LSA storm
   of large
   networks.  In addition to these packets it may be beneficial
   to treat certain other OSPF packets at the higher priority as well.
   One example (during size 160, the database exchange process between neighbors
   following a number of non-converged LSUs stay high indefinitely
   due to repeated retransmissions, link recovery) is the Database Description packet from 
   a slave that is used as an acknowledgment failures due to missed Hellos  
   for more than the previous Database
   Description packet sent from the master. Another example is an LSA 
   carrying a change information Router-Dead interval which may trigger SPF calculation generates additional 
   LSAs and rerouting of Label Switched Paths. It is preferable also due to transmit  
   this information faster than other LSAs in the subsequent link recoveries which again 
   generate additional LSAs.  We define network that are  
   just once-in-30-minutes refreshes and typically would not trigger
   any route computation or route change.

   Given that there is a need stability threshold as
   the maximum allowable LSA storm size for providing prioritized treatment
   to certain OSPF packets, which the next natural question is how number of 
   non-converged LSUs come down to
   facilitate a low level after some time. It 
   turns out that for this prioritization.  

   If it example the stability threshold is possible to
   examine
   150. 

   The network behavior as a function of the packet header (for LSA storm size can
   be categorized as follows:

   (1) If the purpose of prioritization) 
   much faster than processing LSA storm is well below the whole packet stability threshold then prioritized
   treatment is possible without any protocol changes.

   However, we also propose that a special marking be used
       the CPU/memory congestion lasts only for
   categorizing all a short period and
       during this period there are very few retransmissions, very
       few dropped OSPF packets into one of two priority classes.
   It is also important and no link
       failures due to separately mark OSPF packets missed Hellos.  This type of LSA storms are
       observed routinely in operational networks and networks
       recover from other
   IP packets.  One way to do this them easily.

   (2) If the LSA storm is to reserve two diffserv

          
   Choudhury et. al.                                         [Page 12]

   Internet Draft          Explicit Marking                 May, 2003


   codepoints, one just below the stability threshold then
       the CPU/memory congestion lasts for higher priority OSPF packets a longer period and another
   one for lower priority OSPF packets.  With during
       this special
   marking it would period there may be easy for OSPF implementers to
   treat Hello, LSA acknowledgment, considerable amount of retransmissions
       and other critical dropped OSPF packets.  If Hello packets at a higher are not given
       priority and thereby significantly
   improve the scalability and stability of networks using
   OSPF.     


6. Summary

   In this draft we point out that then there may also be some link failures due to


   Choudhury et. al.     Best Current Practice               [Page 13]

   Internet Draft        Prioritized Treatment        September, 2003

       missed Hellos.  However, the node processors of a large network may be subjected does go back to a sustained CPU/Memory congestion
   as a result stable
       state eventually. This type of a large LSA storm caused by may happen rarely in
       operational networks and they recover from it with some type of 
   failure/recovery of nodes/links or synchronization among refreshes.
   There is a certain
       difficulty. 

   (3) If the LSA storm size threshold is above which the network stability threshold then
       the CPU/memory congestion may show unstable behavior caused by large number last indefinitely unless
       some special procedure for relieving congestion is followed. 
       During this period there are considerable amount of 
   retransmissions, 
       retransmissions and dropped OSPF packets.  If Hello packets are
       not given priority then there would also be link failures due 
       to missed Hello packets and
   subsequent link recoveries.  Using a simulation study we show that
   the Hellos.  This type of LSA storm size causing instability may be substantially
   increased by providing prioritized treatment to Hello happen very rarely
       in operational networks and LSA 
   Acknowledgment packets.  Furthermore, if we prioritize usually some manual procedure such 
       as taking down adjacencies in heavily congested nodes is needed.

   (4) If Hello packets are given priority then the network stability
       threshold increases, i.e., the network can withstand a larger
       LSA storm. Furthermore, even when if the network operates at or 
       somewhat above the this higher stability threshold, links Hellos are 
       still not declared down due to missed 
   Hellos.  This implies that and so there are no link failures.  So even though 
       if there is congestion in the control plane congestion due to many retransmissions, the data plane
   stays up and no new LSAs are generated (besides the ones in the 
   original storm and the refreshes).

   Based on the above observations we propose the following:

   (1) Process increased 
       retransmissions requiring some special procedures for congestion
       reduction, the data plane remains unaffected.
        
   (5) If both Hello and Acknowledgement packets at a higher are given priority compared to other
       OSPF packets.
       then the stability threshold increases even further.       
   
   In order to facilitate this, explicitly mark Table 2 we show the 
       Hello packets, to differentiate them from other OSPF packets.
       One way of special marking is to use a network stability threshold for the five  
   different Diffserv 
       codepoint cases and for Hello packets compared to other OSPF packets.
       
   (2) In the absence of special marking, or in addition three different priority scenarios
   defined earlier.  

|===========|========================================================|
|           |    Maximum Allowable LSA Storm Size For                |
|   Case    |=================|==================|===================|
|  Number   | No Priority to it, use 
       other mechanisms in order not  |Priority to miss Hello packets. One example
       is | Priority to treat any packet received over a link as a surrogate for
       a Hello packet (an implicit Hello) for the purpose of keeping 
       the link alive.  Our simulation study shows that this mechanism
       is just as effective as explicitly prioritizing |
|           |  Hello
       packets.

   (3) The same type of explicit marking or Ack   |      Only        |   and prioritized treatment may
       be beneficial to other OSPF packets as well.  One important 
       example is LSA acknowledgment packet that can reduce 
       retransmissions during periods of congestion.  Our simulation Ack         |
|===========|=================|==================|===================|
|   Case 1  |        150      |        190       |        250        |
|___________|_________________|__________________|___________________|
|   Case 2  |        185      |        215       |        285        |
|___________|_________________|__________________|___________________|
|   Case 3  |        115      |        127       |        170        |
|___________|_________________|__________________|___________________|
|   Case 4  |        320      |        375       |        580        |
|___________|_________________|__________________|___________________|
|   Case 5  |        120      |        175       |        225        |
|___________|_________________|__________________|___________________|
|   Case 6  |        185      |        224       |        285        |
|___________|_________________|__________________|___________________|

       Table 2: Maximum Allowable LSA Storm for a Stable Network

   Choudhury et. al.     Best Current Practice               [Page 13] 14]

   Internet Draft          Explicit Marking                 May,        Prioritized Treatment        September, 2003


       study


   We also considered one more scenario with priority to Hello and Ack
   and with a truncated binary exponential backoff of the 
   retransmission interval with an upper limit of 40 seconds (for the 
   same LSA, each successive retransmission interval
   is doubled but not to exceed 40 seconds).  The maximum allowed
   LSA storm size for this scenario significantly exceeded the numbers 
   given in the third column.

Appendix B.3. Observations on Simulation Results

   Table 2 shows that prioritization of both in all cases prioritizing Hello packets increases
   the network stability threshold, and in addition, prioritization of  
   LSA Acknowledgment packets is considerably more effective than
       just prioritizing Hello packets.  Other examples 
       include (a) Database description (DBD) packet from a slave that 
       is used increases the stability threshold even
   further.  The reasons for the above observations are as follows.
   The main sources of sustained CPU/memory congestion (or positive
   feedback loop) following an acknowledgement, LSA storm are (1) LSA retransmissions 
   and (b) LSAs carrying intra-area 
       topology change information. (2) links being declared down due to missed Hellos which in 
   turn causes further LSA generation and future recovery of the link   
   causing even more LSA generation. 
   Prioritizing Hello packets avoids and practically eliminates the
   second source of congestion.  Prioritizing Acknowledgements 
   significantly reduces the first source of congestion, i.e.,
   LSA retransmissions.  It is possible to be noted that some implementations retransmissions can
   not be completely eliminated due to the following reasons. Firstly,
   only the explicit Acknowledgments are already using one prioritized but duplicate
   LSAs carrying implicit Acknowledgments are still served at the 
   lower priority.  Secondly, LSAs may get greatly delayed or
   more of dropped
   at the above mechanisms input queue of receivers and therefore Acknowledgments may
   not even get generated in order which case prioritizing Acks would not   
   help. Another factor to miss keep in mind is that since Hellos and Acks  
   are prioritized, the processing of
   critical packets during periods of congestion. LSAs see bigger delay and potential for 
   dropping. However, we suggest
   the above mechanisms to be included as part of the standard so simulation results show that
   all implementations can benefit from them.


7. Acknowledgments

   We would like to acknowledge Jerry Ash, Margaret Chiosi, Elie 
   Francis, Jeff Han, Beth Munson, Roshan Rao, Moshe Segal, Mike
   Wardlow, on the whole 
   prioritizing Hello and Pat Wirth for collaboration LSA Acks are always beneficial and encouragement 
   significantly improve the network stability threshold.    

   As stated in 
   our scalability improvement efforts for Link-State-Protocol based 
   networks. 


8. References


   [Ref1] Pappalardo, D., "AT&T, customers grapple with ATM net 
   outage," Network World, February 26, 2001.

   [Ref2] "AT&T announces cause Section B.2, exponenetial backoff of frame-relay LSA retransmission
   interval further increases the network outage," AT&T 
   Press Release, April 22, 1998.

   [Ref3] Cholewka, K., "MCI Outage Has Domino Effect," Inter@ctive 
   Week, August 20, 1999.

   [Ref4] Jander, M., "In Qwest Outage, ATM Takes Some Heat," Light
   Reading, April 6, 2001.

   [Ref5] C. Alaettinoglu, V. Jacobson and H. Yu, "Towards Milli-
   second IGP Convergence," Work in Progress.

   [Ref6] A. Zinin and M. Shand, "Flooding Optimizations in Link-State
   Routing Protocols," Work stability threshold. 

   Our simulation study also showed that in Progress.

   [Ref7] J. Moy, "Flooding each of the cases, instead 
   of prioritizing Hello packets if we treat any packet received over Parallel Point-to-Point Links," Work in
   progress.

   [Ref8] P. Pillay-Esnault, "OSPF Refresh 
   a link as a surrogate for a Hello packet (an implicit Hello) then
   we get about the same stability threshold as obtained with
   prioritizing Hello packets.


Appendix C. Other Proposals
 
   (1) Explicit Marking:  In Section 2 we proposed that OSPF packets
       be classified to "high" and flooding reduction in "low" priority classes based on
       examining the OSPF packet header.  In some cases (particularly

   Choudhury et. al.     Best Current Practice               [Page 14] 15]

   Internet Draft          Explicit Marking                 May,        Prioritized Treatment        September, 2003


   stable topologies," Work

       in progress.

   [Ref9] G. Choudhury, V. Manral, "LSA Flooding Optimization
   Algorithms the receiver) this examination may be computationally
       costly.  An alternative would be the
       use of different TOS (DSCP) bits marking for high and Their Simulation Study," Work in progress.

   [Ref10] J. Ash, G. Choudhury, V. Sapozhnikova, M. Sherif, A.  
   Maunder, V. Manral, "Congestion Avoidance & Control low 
       priority OSPF packets respectively.  The exact specification
       of this marking is for further study.

   (2) Other High Priority OSPF 
   Networks", Work Packets: Besides the packets designated
       as high priority in Progress.

   [Ref11] B. M. Waxman, "Routing Section 2 there may be other packets with
       a need for high priority designation.  One example is the
       Database Description (DBD) packet from a slave (during the
       database synchronization process) that is used as an
       acknowledgement.  A second example is an LSA carrying
       intra-area topology change information (this may trigger
       SPF calculation and rerouting of Multipoint Connections," IEEE
   Journal on Selected Areas in Communications, 6(9):1617-1622, 1988.

   
9. Authors' Addresses

   Gagan L. Choudhury
   AT&T
   Room D5-3C21
   200 Laurel Avenue
   Middletown, NJ, 07748
   USA
   Phone: (732)420-3721
   email: gchoudhury@att.com


   Vera D. Sapozhnikova
   AT&T
   Room C5-2C29
   200 Laurel Avenue
   Middletown, NJ, 07748
   USA
   Phone: (732)420-2653
   email: sapozhnikova@att.com


   Anurag S. Maunder
   Sanera Systems
   370 San Aleso Ave.
   Second Floor
   Sunnyvale, CA 94085
   Phone: (408)734-6123
   email: amaunder@sanera.net

   Vishwas Manral
   NetPlane
   189, Prashasan Nagar,
   Road Number 72
   Jubilee Hills, Hyderabad
   India
   email: Vishwasm@netplane.com Label Switched paths and so
       fast processing of this packet may improve OSPF/LDP convergence
       times).
      



































   Choudhury et. al.     Best Current Practice               [Page 15] 16]
----