Tech-invite3GPPspaceIETFspace
959493929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 2178

OSPF Version 2

Pages: 211
Obsoletes:  1583
Obsoleted by:  2328
Part 4 of 8 – Pages 76 to 107
First   Prev   Next

ToP   noToC   RFC2178 - Page 76   prevText
10.3.  The Neighbor state machine

   A detailed description of the neighbor state changes follows.  Each
   state change is invoked by an event (Section 10.2).  This event may
   produce different effects, depending on the current state of the
   neighbor.  For this reason, the state machine below is organized by
   current neighbor state and received event.  Each entry in the state
   machine describes the resulting new neighbor state and the required
   set of additional actions.
ToP   noToC   RFC2178 - Page 77
   When a neighbor's state changes, it may be necessary to rerun the
   Designated Router election algorithm.  This is determined by whether
   the interface NeighborChange event is generated (see Section 9.2).
   Also, if the Interface is in DR state (the router is itself
   Designated Router), changes in neighbor state may cause a new
   network-LSA to be originated (see Section 12.4).

   When the neighbor state machine needs to invoke the interface state
   machine, it should be done as a scheduled task (see Section 4.4).
   This simplifies things, by ensuring that neither state machine will
   be executed recursively.


    State(s):  Down

       Event:  Start

   New state:  Attempt

      Action:  Send an Hello Packet to the neighbor (this neighbor
               is always associated with an NBMA network) and start
               the Inactivity Timer for the neighbor.  The timer's
               later firing would indicate that communication with
               the neighbor was not attained.


    State(s):  Attempt

       Event:  HelloReceived

   New state:  Init

      Action:  Restart the Inactivity Timer for the neighbor, since
               the neighbor has now been heard from.


    State(s):  Down

       Event:  HelloReceived

   New state:  Init

      Action:  Start the Inactivity Timer for the neighbor.  The
               timer's later firing would indicate that the neighbor
               is dead.
ToP   noToC   RFC2178 - Page 78
    State(s):  Init or greater

       Event:  HelloReceived

   New state:  No state change.

      Action:  Restart the Inactivity Timer for the neighbor, since
               the neighbor has again been heard from.


    State(s):  Init

       Event:  2-WayReceived

   New state:  Depends upon action routine.

      Action:  Determine whether an adjacency should be established
               with the neighbor (see Section 10.4).  If not, the
               new neighbor state is 2-Way.

               Otherwise (an adjacency should be established) the
               neighbor state transitions to ExStart.  Upon
               entering this state, the router increments the DD
               sequence number in the neighbor data structure.  If
               this is the first time that an adjacency has been
               attempted, the DD sequence number should be assigned
               some unique value (like the time of day clock).  It
               then declares itself master (sets the master/slave
               bit to master), and starts sending Database
               Description Packets, with the initialize (I), more
               (M) and master (MS) bits set.  This Database
               Description Packet should be otherwise empty.  This
               Database Description Packet should be retransmitted
               at intervals of RxmtInterval until the next state is
               entered (see Section 10.8).


    State(s):  ExStart

       Event:  NegotiationDone

   New state:  Exchange

      Action:  The router must list the contents of its entire area
               link state database in the neighbor Database summary
               list.  The area link state database consists of the
               router-LSAs, network-LSAs and summary-LSAs contained
               in the area structure, along with the AS-external-
ToP   noToC   RFC2178 - Page 79
               LSAs contained in the global structure.  AS-
               external-LSAs are omitted from a virtual neighbor's
               Database summary list.  AS-external-LSAs are omitted
               from the Database summary list if the area has been
               configured as a stub (see Section 3.6).  LSAs whose
               age is equal to MaxAge are instead added to the
               neighbor's Link state retransmission list.  A
               summary of the Database summary list will be sent to
               the neighbor in Database Description packets.  Each
               Database Description Packet has a DD sequence
               number, and is explicitly acknowledged.  Only one
               Database Description Packet is allowed outstanding
               at any one time.  For more detail on the sending and
               receiving of Database Description packets, see
               Sections 10.8 and 10.6.


    State(s):  Exchange

       Event:  ExchangeDone

   New state:  Depends upon action routine.

      Action:  If the neighbor Link state request list is empty,
               the new neighbor state is Full.  No other action is
               required.  This is an adjacency's final state.

               Otherwise, the new neighbor state is Loading.  Start
               (or continue) sending Link State Request packets to
               the neighbor (see Section 10.9).  These are requests
               for the neighbor's more recent LSAs (which were
               discovered but not yet received in the Exchange
               state).  These LSAs are listed in the Link state
               request list associated with the neighbor.


    State(s):  Loading

       Event:  Loading Done

   New state:  Full

      Action:  No action required.  This is an adjacency's final
               state.
ToP   noToC   RFC2178 - Page 80
    State(s):  2-Way

       Event:  AdjOK?

   New state:  Depends upon action routine.

      Action:  Determine whether an adjacency should be formed with
               the neighboring router (see Section 10.4).  If not,
               the neighbor state remains at 2-Way.  Otherwise,
               transition the neighbor state to ExStart and perform
               the actions associated with the above state machine
               entry for state Init and event 2-WayReceived.


    State(s):  ExStart or greater

       Event:  AdjOK?

   New state:  Depends upon action routine.

      Action:  Determine whether the neighboring router should
               still be adjacent.  If yes, there is no state change
               and no further action is necessary.

               Otherwise, the (possibly partially formed) adjacency
               must be destroyed.  The neighbor state transitions
               to 2-Way.  The Link state retransmission list,
               Database summary list and Link state request list
               are cleared of LSAs.


    State(s):  Exchange or greater

       Event:  SeqNumberMismatch

   New state:  ExStart

      Action:  The (possibly partially formed) adjacency is torn
               down, and then an attempt is made at
               reestablishment.  The neighbor state first
               transitions to ExStart.  The Link state
               retransmission list, Database summary list and Link
               state request list are cleared of LSAs.  Then the
               router increments the DD sequence number in the
               neighbor data structure, declares itself master
               (sets the master/slave bit to master), and starts
               sending Database Description Packets, with the
               initialize (I), more (M) and master (MS) bits set.
ToP   noToC   RFC2178 - Page 81
               This Database Description Packet should be otherwise
               empty (see Section 10.8).


    State(s):  Exchange or greater

       Event:  BadLSReq

   New state:  ExStart

      Action:  The action for event BadLSReq is exactly the same as
               for the neighbor event SeqNumberMismatch.  The
               (possibly partially formed) adjacency is torn down,
               and then an attempt is made at reestablishment.  For
               more information, see the neighbor state machine
               entry that is invoked when event SeqNumberMismatch
               is generated in state Exchange or greater.


    State(s):  Any state

       Event:  KillNbr

   New state:  Down

      Action:  The Link state retransmission list, Database summary
               list and Link state request list are cleared of
               LSAs.  Also, the Inactivity Timer is disabled.


    State(s):  Any state

       Event:  LLDown

   New state:  Down

      Action:  The Link state retransmission list, Database summary
               list and Link state request list are cleared of
               LSAs.  Also, the Inactivity Timer is disabled.
ToP   noToC   RFC2178 - Page 82
    State(s):  Any state

       Event:  InactivityTimer

   New state:  Down

      Action:  The Link state retransmission list, Database summary
               list and Link state request list are cleared of
               LSAs.


    State(s):  2-Way or greater

       Event:  1-WayReceived

   New state:  Init

      Action:  The Link state retransmission list, Database summary
               list and Link state request list are cleared of
               LSAs.


    State(s):  2-Way or greater

       Event:  2-WayReceived

   New state:  No state change.

      Action:  No action required.


    State(s):  Init

       Event:  1-WayReceived

   New state:  No state change.

      Action:  No action required.


10.4.  Whether to become adjacent

   Adjacencies are established with some subset of the router's
   neighbors.  Routers connected by point-to-point networks, Point-to-
   MultiPoint networks and virtual links always become adjacent.  On
   broadcast and NBMA networks, all routers become adjacent to both the
   Designated Router and the Backup Designated Router.
ToP   noToC   RFC2178 - Page 83
   The adjacency-forming decision occurs in two places in the neighbor
   state machine.  First, when bidirectional communication is initially
   established with the neighbor, and secondly, when the identity of the
   attached network's (Backup) Designated Router changes.  If the
   decision is made to not attempt an adjacency, the state of the
   neighbor communication stops at 2-Way.

   An adjacency should be established with a bidirectional neighbor when
   at least one of the following conditions holds:

   o   The underlying network type is point-to-point

   o   The underlying network type is Point-to-MultiPoint

   o   The underlying network type is virtual link

   o   The router itself is the Designated Router

   o   The router itself is the Backup Designated Router

   o   The neighboring router is the Designated Router

   o   The neighboring router is the Backup Designated Router

10.5.  Receiving Hello Packets

   This section explains the detailed processing of a received Hello
   Packet.  (See Section A.3.2 for the format of Hello packets.)  The
   generic input processing of OSPF packets will have checked the
   validity of the IP header and the OSPF packet header.  Next, the
   values of the Network Mask, HelloInterval, and RouterDeadInterval
   fields in the received Hello packet must be checked against the
   values configured for the receiving interface.  Any mismatch causes
   processing to stop and the packet to be dropped.  In other words, the
   above fields are really describing the attached network's
   configuration.  However, there is one exception to the above rule: on
   point-to-point networks and on virtual links, the Network Mask in the
   received Hello Packet should be ignored.

   The receiving interface attaches to a single OSPF area (this could be
   the backbone).  The setting of the E-bit found in the Hello Packet's
   Options field must match this area's ExternalRoutingCapability.  If
   AS-external-LSAs are not flooded into/throughout the area (i.e, the
   area is a "stub") the E-bit must be clear in received Hello Packets,
   otherwise the E-bit must be set.  A mismatch causes processing to
   stop and the packet to be dropped.  The setting of the rest of the
   bits in the Hello Packet's Options field should be ignored.
ToP   noToC   RFC2178 - Page 84
   At this point, an attempt is made to match the source of the Hello
   Packet to one of the receiving interface's neighbors.  If the
   receiving interface connects to a broadcast, Point-to-MultiPoint or
   NBMA network the source is identified by the IP source address found
   in the Hello's IP header.  If the receiving interface connects to a
   point-to-point link or a virtual link, the source is identified by
   the Router ID found in the Hello's OSPF packet header.  The
   interface's current list of neighbors is contained in the interface's
   data structure.  If a matching neighbor structure cannot be found,
   (i.e., this is the first time the neighbor has been detected), one is
   created.  The initial state of a newly created neighbor is set to
   Down.

   When receiving an Hello Packet from a neighbor on a broadcast,
   Point-to-MultiPoint or NBMA network, set the neighbor structure's
   Neighbor ID equal to the Router ID found in the packet's OSPF header.
   When receiving an Hello on a point-to-point network (but not on a
   virtual link) set the neighbor structure's Neighbor IP address to the
   packet's IP source address.

   Now the rest of the Hello Packet is examined, generating events to be
   given to the neighbor and interface state machines.  These state
   machines are specified either to be executed or scheduled (see
   Section 4.4).  For example, by specifying below that the neighbor
   state machine be executed in line, several neighbor state transitions
   may be effected by a single received Hello:

   o   Each Hello Packet causes the neighbor state machine to be
       executed with the event HelloReceived.

   o   Then the list of neighbors contained in the Hello Packet is
       examined.  If the router itself appears in this list, the
       neighbor state machine should be executed with the event 2-
       WayReceived.  Otherwise, the neighbor state machine should
       be executed with the event 1-WayReceived, and the processing
       of the packet stops.

   o   Next, the Hello Packet's Router Priority field is examined.
       If this field is different than the one previously received
       from the neighbor, the receiving interface's state machine
       is scheduled with the event NeighborChange.  In any case,
       the Router Priority field in the neighbor data structure
       should be updated accordingly.

   o   Next the Designated Router field in the Hello Packet is
       examined.  If the neighbor is both declaring itself to be
       Designated Router (Designated Router field = Neighbor IP
       address) and the Backup Designated Router field in the
ToP   noToC   RFC2178 - Page 85
       packet is equal to 0.0.0.0 and the receiving interface is in
       state Waiting, the receiving interface's state machine is
       scheduled with the event BackupSeen.  Otherwise, if the
       neighbor is declaring itself to be Designated Router and it
       had not previously, or the neighbor is not declaring itself
       Designated Router where it had previously, the receiving
       interface's state machine is scheduled with the event
       NeighborChange.  In any case, the Neighbors' Designated
       Router item in the neighbor structure is updated
       accordingly.

   o   Finally, the Backup Designated Router field in the Hello
       Packet is examined.  If the neighbor is declaring itself to
       be Backup Designated Router (Backup Designated Router field
       = Neighbor IP address) and the receiving interface is in
       state Waiting, the receiving interface's state machine is
       scheduled with the event BackupSeen.  Otherwise, if the
       neighbor is declaring itself to be Backup Designated Router
       and it had not previously, or the neighbor is not declaring
       itself Backup Designated Router where it had previously, the
       receiving interface's state machine is scheduled with the
       event NeighborChange.  In any case, the Neighbor's Backup
       Designated Router item in the neighbor structure is updated
       accordingly.

   On NBMA networks, receipt of an Hello Packet may also cause an Hello
   Packet to be sent back to the neighbor in response. See Section 9.5.1
   for more details.

10.6.  Receiving Database Description Packets

   This section explains the detailed processing of a received Database
   Description Packet.  The incoming Database Description Packet has
   already been associated with a neighbor and receiving interface by
   the generic input packet processing (Section 8.2).  Whether the
   Database Description packet should be accepted, and if so, how it
   should be further processed depends upon the neighbor state.

   If a Database Description packet is accepted, the following packet
   fields should be saved in the corresponding neighbor data structure
   under "last received Database Description packet": the packet's
   initialize(I), more (M) and master(MS) bits, Options field, and DD
   sequence number. If these fields are set identically in two
   consecutive Database Description packets received from the neighbor,
   the second Database Description packet is considered to be a
   "duplicate" in the processing described below.
ToP   noToC   RFC2178 - Page 86
   If the Interface MTU field in the Database Description packet
   indicates an IP datagram size that is larger than the router can
   accept on the receiving interface without fragmentation, the Database
   Description packet is rejected.  Otherwise, if the neighbor state is:

   Down
      The packet should be rejected.

   Attempt
      The packet should be rejected.

   Init
      The neighbor state machine should be executed with the event 2-
      WayReceived.  This causes an immediate state change to either
      state 2-Way or state ExStart. If the new state is ExStart, the
      processing of the current packet should then continue in this new
      state by falling through to case ExStart below.

   2-Way
      The packet should be ignored.  Database Description Packets are
      used only for the purpose of bringing up adjacencies.[7]

   ExStart
      If the received packet matches one of the following cases, then
      the neighbor state machine should be executed with the event
      NegotiationDone (causing the state to transition to Exchange), the
      packet's Options field should be recorded in the neighbor
      structure's Neighbor Options field and the packet should be
      accepted as next in sequence and processed further (see below).
      Otherwise, the packet should be ignored.

       o   The initialize(I), more (M) and master(MS) bits are set,
           the contents of the packet are empty, and the neighbor's
           Router ID is larger than the router's own.  In this case
           the router is now Slave.  Set the master/slave bit to
           slave, and set the neighbor data structure's DD sequence
           number to that specified by the master.

       o   The initialize(I) and master(MS) bits are off, the
           packet's DD sequence number equals the neighbor data
           structure's DD sequence number (indicating
           acknowledgment) and the neighbor's Router ID is smaller
           than the router's own.  In this case the router is
           Master.
ToP   noToC   RFC2178 - Page 87
   Exchange
      Duplicate Database Description packets are discarded by the
      master, and cause the slave to retransmit the last Database
      Description packet that it had sent. Otherwise (the packet is not
      a duplicate):

       o   If the state of the MS-bit is inconsistent with the
           master/slave state of the connection, generate the
           neighbor event SeqNumberMismatch and stop processing the
           packet.

       o   If the initialize(I) bit is set, generate the neighbor
           event SeqNumberMismatch and stop processing the packet.

       o   If the packet's Options field indicates a different set
           of optional OSPF capabilities than were previously
           received from the neighbor (recorded in the Neighbor
           Options field of the neighbor structure), generate the
           neighbor event SeqNumberMismatch and stop processing the
           packet.

       o   Database Description packets must be processed in
           sequence, as indicated by the packets' DD sequence
           numbers. If the router is master, the next packet
           received should have DD sequence number equal to the DD
           sequence number in the neighbor data structure. If the
           router is slave, the next packet received should have DD
           sequence number equal to one more than the DD sequence
           number stored in the neighbor data structure. In either
           case, if the packet is the next in sequence it should be
           accepted and its contents processed as specified below.

       o   Else, generate the neighbor event SeqNumberMismatch and
           stop processing the packet.

   Loading or Full
      In this state, the router has sent and received an entire sequence
      of Database Description Packets.  The only packets received should
      be duplicates (see above). In particular, the packet's Options
      field should match the set of optional OSPF capabilities
      previously indicated by the neighbor (stored in the neighbor
      structure's Neighbor Options field).  Any other packets received,
      including the reception of a packet with the Initialize(I) bit
      set, should generate the neighbor event SeqNumberMismatch.[8]
      Duplicates should be discarded by the master.  The slave must
      respond to duplicates by repeating the last Database Description
      packet that it had sent.
ToP   noToC   RFC2178 - Page 88
   When the router accepts a received Database Description Packet as the
   next in sequence the packet contents are processed as follows.  For
   each LSA listed, the LSA's LS type is checked for validity.  If the
   LS type is unknown (e.g., not one of the LS types 1-5 defined by this
   specification), or if this is an AS-external-LSA (LS type = 5) and
   the neighbor is associated with a stub area, generate the neighbor
   event SeqNumberMismatch and stop processing the packet.  Otherwise,
   the router looks up the LSA in its database to see whether it also
   has an instance of the LSA.  If it does not, or if the database copy
   is less recent (see Section 13.1), the LSA is put on the Link state
   request list so that it can be requested (immediately or at some
   later time) in Link State Request Packets.

   When the router accepts a received Database Description Packet as the
   next in sequence, it also performs the following actions, depending
   on whether it is master or slave:

   Master
      Increments the DD sequence number in the neighbor data structure.
      If the router has already sent its entire sequence of Database
      Description Packets, and the just accepted packet has the more bit
      (M) set to 0, the neighbor event ExchangeDone is generated.
      Otherwise, it should send a new Database Description to the slave.

   Slave
      Sets the DD sequence number in the neighbor data structure to the
      DD sequence number appearing in the received packet.  The slave
      must send a Database Description Packet in reply.  If the received
      packet has the more bit (M) set to 0, and the packet to be sent by
      the slave will also have the M-bit set to 0, the neighbor event
      ExchangeDone is generated.  Note that the slave always generates
      this event before the master.

10.7.  Receiving Link State Request Packets

   This section explains the detailed processing of received Link State
   Request packets.  Received Link State Request Packets specify a list
   of LSAs that the neighbor wishes to receive.  Link State Request
   Packets should be accepted when the neighbor is in states Exchange,
   Loading, or Full.  In all other states Link State Request Packets
   should be ignored.
ToP   noToC   RFC2178 - Page 89
   Each LSA specified in the Link State Request packet should be located
   in the router's database, and copied into Link State Update packets
   for transmission to the neighbor.  These LSAs should NOT be placed on
   the Link state retransmission list for the neighbor.  If an LSA
   cannot be found in the database, something has gone wrong with the
   Database Exchange process, and neighbor event BadLSReq should be
   generated.

10.8.  Sending Database Description Packets

   This section describes how Database Description Packets are sent to a
   neighbor. The Database Description packet's Interface MTU field is
   set to the size of the largest IP datagram that can be sent out the
   sending interface, without fragmentation.  Common MTUs in use in the
   Internet can be found in Table 7-1 of [Ref22]. Interface MTU should
   be set to 0 in Database Description packets sent over virtual links.

   The router's optional OSPF capabilities (see Section 4.5) are
   transmitted to the neighbor in the Options field of the Database
   Description packet.  The router should maintain the same set of
   optional capabilities throughout the Database Exchange and flooding
   procedures.  If for some reason the router's optional capabilities
   change, the Database Exchange procedure should be restarted by
   reverting to neighbor state ExStart.  One optional capability is
   defined in this specification (see Sections 4.5 and A.2). The E-bit
   should be set if and only if the attached network belongs to a non-
   stub area. Unrecognized bits in the Options field should be set to
   zero.  The sending of Database Description packets depends on the
   neighbor's state.  In state ExStart the router sends empty Database
   Description packets, with the initialize (I), more (M) and master
   (MS) bits set.  These packets are retransmitted every RxmtInterval
   seconds.

   In state Exchange the Database Description Packets actually contain
   summaries of the link state information contained in the router's
   database.  Each LSA in the area's link-state database (at the time
   the neighbor transitions into Exchange state) is listed in the
   neighbor Database summary list.  Each new Database Description Packet
   copies its DD sequence number from the neighbor data structure and
   then describes the current top of the Database summary list.  Items
   are removed from the Database summary list when the previous packet
   is acknowledged.

   In state Exchange, the determination of when to send a Database
   Description packet depends on whether the router is master or slave:
ToP   noToC   RFC2178 - Page 90
   Master
      Database Description packets are sent when either a) the slave
      acknowledges the previous Database Description packet by echoing
      the DD sequence number or b) RxmtInterval seconds elapse without
      an acknowledgment, in which case the previous Database Description
      packet is retransmitted.

   Slave
      Database Description packets are sent only in response to Database
      Description packets received from the master.  If the Database
      Description packet received from the master is new, a new Database
      Description packet is sent, otherwise the previous Database
      Description packet is resent.

   In states Loading and Full the slave must resend its last Database
   Description packet in response to duplicate Database Description
   packets received from the master.  For this reason the slave must
   wait RouterDeadInterval seconds before freeing the last Database
   Description packet.  Reception of a Database Description packet from
   the master after this interval will generate a SeqNumberMismatch
   neighbor event.

10.9.  Sending Link State Request Packets

   In neighbor states Exchange or Loading, the Link state request list
   contains a list of those LSAs that need to be obtained from the
   neighbor.  To request these LSAs, a router sends the neighbor the
   beginning of the Link state request list, packaged in a Link State
   Request packet.

   When the neighbor responds to these requests with the proper Link
   State Update packet(s), the Link state request list is truncated and
   a new Link State Request packet is sent.  This process continues
   until the Link state request list becomes empty.  Unsatisfied Link
   State Request packets are retransmitted at intervals of RxmtInterval.
   There should be at most one Link State Request packet outstanding at
   any one time.

   When the Link state request list becomes empty, and the neighbor
   state is Loading (i.e., a complete sequence of Database Description
   packets has been sent to and received from the neighbor), the Loading
   Done neighbor event is generated.
ToP   noToC   RFC2178 - Page 91
10.10.  An Example

   Figure 14 shows an example of an adjacency forming.  Routers RT1 and
   RT2 are both connected to a broadcast network.  It is assumed that
   RT2 is the Designated Router for the network, and that RT2 has a
   higher Router ID than Router RT1.

   The neighbor state changes realized by each router are listed on the
   sides of the figure.

   At the beginning of Figure 14, Router RT1's interface to the network
   becomes operational.  It begins sending Hello Packets, although it
   doesn't know the identity of the Designated Router or of any other
   neighboring routers.  Router RT2 hears this hello (moving the
   neighbor to Init state), and in its next Hello Packet indicates that
   it is itself the Designated Router and that it has heard Hello
   Packets from RT1.  This in turn causes RT1 to go to state ExStart, as
   it starts to bring up the adjacency.

   RT1 begins by asserting itself as the master.  When it sees that RT2
   is indeed the master (because of RT2's higher Router ID), RT1
   transitions to slave state and adopts its neighbor's DD sequence
   number.  Database Description packets are then exchanged, with polls
   coming from the master (RT2) and responses from the slave (RT1).
   This sequence of Database Description Packets ends when both the poll
   and associated response has the M-bit off.

   In this example, it is assumed that RT2 has a completely up to date
   database.  In that case, RT2 goes immediately into Full state.  RT1
   will go into Full state after updating the necessary parts of its
   database.  This is done by sending Link State Request Packets, and
   receiving Link State Update Packets in response.  Note that, while
   RT1 has waited until a complete set of Database Description Packets
   has been received (from RT2) before sending any Link State Request
   Packets, this need not be the case.  RT1 could have interleaved the
   sending of Link State Request Packets with the reception of Database
   Description Packets.
ToP   noToC   RFC2178 - Page 92
            +---+                                         +---+
            |RT1|                                         |RT2|
            +---+                                         +---+

            Down                                          Down
                            Hello(DR=0,seen=0)
                       ------------------------------>
                         Hello (DR=RT2,seen=RT1,...)      Init
                       <------------------------------
            ExStart        D-D (Seq=x,I,M,Master)
                       ------------------------------>
                           D-D (Seq=y,I,M,Master)         ExStart
                       <------------------------------
            Exchange       D-D (Seq=y,M,Slave)
                       ------------------------------>
                           D-D (Seq=y+1,M,Master)         Exchange
                       <------------------------------
                           D-D (Seq=y+1,M,Slave)
                       ------------------------------>
                                     ...
                                     ...
                                     ...
                           D-D (Seq=y+n, Master)
                       <------------------------------
                           D-D (Seq=y+n, Slave)
             Loading   ------------------------------>
                                 LS Request                Full
                       ------------------------------>
                                 LS Update
                       <------------------------------
                                 LS Request
                       ------------------------------>
                                 LS Update
                       <------------------------------
             Full


                Figure 14: An adjacency bring-up example
ToP   noToC   RFC2178 - Page 93
11.  The Routing Table Structure

   The routing table data structure contains all the information
   necessary to forward an IP data packet toward its destination.  Each
   routing table entry describes the collection of best paths to a
   particular destination.  When forwarding an IP data packet, the
   routing table entry providing the best match for the packet's IP
   destination is located.  The matching routing table entry then
   provides the next hop towards the packet's destination.  OSPF also
   provides for the existence of a default route (Destination ID =
   DefaultDestination, Address Mask = 0x00000000).  When the default
   route exists, it matches all IP destinations (although any other
   matching entry is a better match). Finding the routing table entry
   that best matches an IP destination is further described in Section
   11.1.

   There is a single routing table in each router.  Two sample routing
   tables are described in Sections 11.2 and 11.3.  The building of the
   routing table is discussed in Section 16.

   The rest of this section defines the fields found in a routing table
   entry.  The first set of fields describes the routing table entry's
   destination.

   Destination Type
      Destination type is either "network" or "router". Only network entries
      are actually used when forwarding IP data traffic.  Router routing
      table entries are used solely as intermediate steps in the routing
      table build process.

      A network is a range of IP addresses, to which IP data traffic may be
      forwarded.  This includes IP networks (class A, B, or C), IP subnets,
      IP supernets and single IP hosts.  The default route also falls into
      this category.

      Router entries are kept for area border routers and AS boundary
      routers.  Routing table entries for area border routers are used when
      calculating the inter-area routes (see Section 16.2), and when
      maintaining configured virtual links (see Section 15).  Routing table
      entries for AS boundary routers are used when calculating the AS
      external routes (see Section 16.4).

   Destination ID
      The destination's identifier or name.  This depends on the
      Destination Type.  For networks, the identifier is their associated IP
      address.  For routers, the identifier is the OSPF Router ID.[9]
ToP   noToC   RFC2178 - Page 94
   Address Mask
      Only defined for networks.  The network's IP address together with its
      address mask defines a range of IP addresses.  For IP subnets, the
      address mask is referred to as the subnet mask.  For host routes, the
      mask is "all ones" (0xffffffff).

   Optional Capabilities
      When the destination is a router this field indicates the optional
      OSPF capabilities supported by the destination router.  The only
      optional capability defined by this specification is the ability to
      process AS-external-LSAs.  For a further discussion of OSPF's optional
      capabilities, see Section 4.5.

   The set of paths to use for a destination may vary based on the OSPF
   area to which the paths belong.  This means that there may be
   multiple routing table entries for the same destination, depending on
   the values of the next field.

   Area
      This field indicates the area whose link state information has led
      to the routing table entry's collection of paths.  This is called
      the entry's associated area.  For sets of AS external paths, this
      field is not defined.  For destinations of type "router", there
      may be separate sets of paths (and therefore separate routing
      table entries) associated with each of several areas. For example,
      this will happen when two area border routers share multiple areas
      in common.  For destinations of type "network", only the set of
      paths associated with the best area (the one providing the
      preferred route) is kept.

   The rest of the routing table entry describes the set of paths to the
   destination.  The following fields pertain to the set of paths as a
   whole.  In other words, each one of the paths contained in a routing
   table entry is of the same path-type and cost (see below).

   Path-type
      There are four possible types of paths used to route traffic to
      the destination, listed here in order of preference: intra-area,
      inter-area, type 1 external or type 2 external.  Intra-area paths
      indicate destinations belonging to one of the router's attached
      areas.  Inter-area paths are paths to destinations in other OSPF
      areas.  These are discovered through the examination of received
      summary-LSAs.  AS external paths are paths to destinations
      external to the AS.  These are detected through the examination of
      received AS-external-LSAs.
ToP   noToC   RFC2178 - Page 95
   Cost
      The link state cost of the path to the destination.  For all paths
      except type 2 external paths this describes the entire path's
      cost.  For Type 2 external paths, this field describes the cost of
      the portion of the path internal to the AS.  This cost is
      calculated as the sum of the costs of the path's constituent
      links.

   Type 2 cost
      Only valid for type 2 external paths.  For these paths, this field
      indicates the cost of the path's external portion.  This cost has
      been advertised by an AS boundary router, and is the most
      significant part of the total path cost.  For example, a type 2
      external path with type 2 cost of 5 is always preferred over a
      path with type 2 cost of 10, regardless of the cost of the two
      paths' internal components.

   Link State Origin
      Valid only for intra-area paths, this field indicates the LSA
      (router-LSA or network-LSA) that directly references the
      destination.  For example, if the destination is a transit
      network, this is the transit network's network-LSA.  If the
      destination is a stub network, this is the router-LSA for the
      attached router.  The LSA is discovered during the shortest-path
      tree calculation (see Section 16.1).  Multiple LSAs may reference
      the destination, however a tie-breaking scheme always reduces the
      choice to a single LSA. The Link State Origin field is not used by
      the OSPF protocol, but it is used by the routing table calculation
      in OSPF's Multicast routing extensions (MOSPF).

   When multiple paths of equal path-type and cost exist to a
   destination (called elsewhere "equal-cost" paths), they are stored in
   a single routing table entry.  Each one of the "equal-cost" paths is
   distinguished by the following fields:

   Next hop
      The outgoing router interface to use when forwarding traffic to
      the destination.  On broadcast, Point-to-MultiPoint and NBMA
      networks, the next hop also includes the IP address of the next
      router (if any) in the path towards the destination.

   Advertising router
      Valid only for inter-area and AS external paths.  This field
      indicates the Router ID of the router advertising the summary-LSA
      or AS-external-LSA that led to this path.
ToP   noToC   RFC2178 - Page 96
11.1.  Routing table lookup

   When an IP data packet is received, an OSPF router finds the routing
   table entry that best matches the packet's destination.  This routing
   table entry then provides the outgoing interface and next hop router
   to use in forwarding the packet. This section describes the process
   of finding the best matching routing table entry. The process
   consists of a number of steps, wherein the collection of routing
   table entries is progressively pruned.  In the end, the single
   routing table entry remaining is called the "best match".

   Before the lookup begins, "discard" routing table entries should be
   inserted into the routing table for each of the router's active area
   address ranges (see Section 3.5).  (An area range is considered
   "active" if the range contains one or more networks reachable by
   intra-area paths.) The destination of a "discard" entry is the set of
   addresses described by its associated active area address range, and
   the path type of each "discard" entry is set to "inter-area".[10]

   Note that the steps described below may fail to produce a best match
   routing table entry (i.e., all existing routing table entries are
   pruned for some reason or another), or the best match routing table
   entry may be one of the above "discard" routing table entries. In
   these cases, the packet's IP destination is considered unreachable.
   Instead of being forwarded, the packet should be discarded and an
   ICMP destination unreachable message should be returned to the
   packet's source.

   (1) Select the complete set of "matching" routing table entries
       from the routing table.  Each routing table entry describes
       a (set of) path(s) to a range of IP addresses. If the data
       packet's IP destination falls into an entry's range of IP
       addresses, the routing table entry is called a match. (It is
       quite likely that multiple entries will match the data
       packet.  For example, a default route will match all
       packets.)

   (2) Reduce the set of matching entries to those having the most
       preferential path-type (see Section 11). OSPF has a four
       level hierarchy of paths. Intra-area paths are the most
       preferred, followed in order by inter-area, type 1 external
       and type 2 external paths.

   (3) Select the remaining routing table entry that provides the
       most specific (longest) match. Another way of saying this is
       to choose the remaining entry that specifies the narrowest
       range of IP addresses.[11] For example, the entry for the
       address/mask pair of (128.185.1.0, 0xffffff00) is more
ToP   noToC   RFC2178 - Page 97
       specific than an entry for the pair (128.185.0.0,
       0xffff0000). The default route is the least specific match,
       since it matches all destinations.

11.2.  Sample routing table, without areas

   Consider the Autonomous System pictured in Figure 2.  No OSPF areas
   have been configured.  A single metric is shown per outbound
   interface.  The calculation of Router RT6's routing table proceeds as
   described in Section 2.2.  The resulting routing table is shown in
   Table 12.  Destination types are abbreviated: Network as "N", Router
   as "R".

   There are no instances of multiple equal-cost shortest paths in this
   example.  Also, since there are no areas, there are no inter-area
   paths.

   Routers RT5 and RT7 are AS boundary routers.  Intra-area routes have
   been calculated to Routers RT5 and RT7.  This allows external routes
   to be calculated to the destinations advertised by RT5 and RT7 (i.e.,
   Networks N12, N13, N14 and N15).  It is assumed all AS-external-LSAs
   originated by RT5 and RT7 are advertising type 1 external metrics.
   This results in type 1 external paths being calculated to
   destinations N12-N15.

11.3.  Sample routing table, with areas

   Consider the previous example, this time split into OSPF areas.  An
   OSPF area configuration is pictured in Figure 6.  Router RT4's
   routing table will be described for this area configuration.  Router
   RT4 has a connection to Area 1 and a backbone connection.  This
   causes Router RT4 to view the AS as the concatenation of the two
   graphs shown in Figures 7 and 8.  The resulting routing table is
   displayed in Table 13.
ToP   noToC   RFC2178 - Page 98
      Type   Dest   Area   Path  Type    Cost   Next     Adv.
                                                Hop(s)   Router(s)
      ____________________________________________________________
      N      N1     0      intra-area    10     RT3      *
      N      N2     0      intra-area    10     RT3      *
      N      N3     0      intra-area    7      RT3      *
      N      N4     0      intra-area    8      RT3      *
      N      Ib     0      intra-area    7      *        *
      N      Ia     0      intra-area    12     RT10     *
      N      N6     0      intra-area    8      RT10     *
      N      N7     0      intra-area    12     RT10     *
      N      N8     0      intra-area    10     RT10     *
      N      N9     0      intra-area    11     RT10     *
      N      N10    0      intra-area    13     RT10     *
      N      N11    0      intra-area    14     RT10     *
      N      H1     0      intra-area    21     RT10     *
      R      RT5    0      intra-area    6      RT5      *
      R      RT7    0      intra-area    8      RT10     *
      ____________________________________________________________
      N      N12    *      type 1 ext.   10     RT10     RT7
      N      N13    *      type 1 ext.   14     RT5      RT5
      N      N14    *      type 1 ext.   14     RT5      RT5
      N      N15    *      type 1 ext.   17     RT10     RT7


               Table 12: The routing table for Router RT6
                         (no configured areas).

   Again, Routers RT5 and RT7 are AS boundary routers.  Routers RT3,
   RT4, RT7, RT10 and RT11 are area border routers.  Note that there are
   two routing entries for the area border router RT3, since it has two
   areas in common with RT4 (Area 1 and the backbone).

   Backbone paths have been calculated to all area border routers.
   These are used when determining the inter-area routes.  Note that all
   of the inter-area routes are associated with the backbone; this is
   always the case when the calculating router is itself an area border
   router.  Routing information is condensed at area boundaries.  In
   this example, we assume that Area 3 has been defined so that networks
   N9-N11 and the host route to H1 are all condensed to a single route
   when advertised into the backbone (by Router RT11).  Note that the
   cost of this route is the maximum of the set of costs to its
   individual components.
ToP   noToC   RFC2178 - Page 99
   There is a virtual link configured between Routers RT10 and RT11.
   Without this configured virtual link, RT11 would be unable to
   advertise a route for networks N9-N11 and Host H1 into the backbone,
   and there would not be an entry for these networks in Router RT4's
   routing table.

   In this example there are two equal-cost paths to Network N12.
   However, they both use the same next hop (Router RT5).


   Type   Dest        Area   Path  Type    Cost   Next      Adv.
                                                  Hops(s)   Router(s)
   __________________________________________________________________
   N      N1          1      intra-area    4      RT1       *
   N      N2          1      intra-area    4      RT2       *
   N      N3          1      intra-area    1      *         *
   N      N4          1      intra-area    3      RT3       *
   R      RT3         1      intra-area    1      *         *
   __________________________________________________________________
   N      Ib          0      intra-area    22     RT5       *
   N      Ia          0      intra-area    27     RT5       *
   R      RT3         0      intra-area    21     RT5       *
   R      RT5         0      intra-area    8      *         *
   R      RT7         0      intra-area    14     RT5       *
   R      RT10        0      intra-area    22     RT5       *
   R      RT11        0      intra-area    25     RT5       *
   __________________________________________________________________
   N      N6          0      inter-area    15     RT5       RT7
   N      N7          0      inter-area    19     RT5       RT7
   N      N8          0      inter-area    18     RT5       RT7
   N      N9-N11,H1   0      inter-area    36     RT5       RT11
   __________________________________________________________________
   N      N12         *      type 1 ext.   16     RT5       RT5,RT7
   N      N13         *      type 1 ext.   16     RT5       RT5
   N      N14         *      type 1 ext.   16     RT5       RT5
   N      N15         *      type 1 ext.   23     RT5       RT7

                  Table 13: Router RT4's routing table
                       in the presence of areas.


   Router RT4's routing table would improve (i.e., some of the paths in
   the routing table would become shorter) if an additional virtual link
   were configured between Router RT4 and Router RT3.  The new virtual
   link would itself be associated with the first entry for area border
   router RT3 in Table 13 (an intra-area path through Area 1).  This
   would yield a cost of 1 for the virtual link.  The routing table
   entries changes that would be caused by the addition of this virtual
ToP   noToC   RFC2178 - Page 100
   link are shown in Table 14.

12.  Link State Advertisements (LSAs)

   Each router in the Autonomous System originates one or more link
   state advertisements (LSAs).  This memo defines five distinct types
   of LSAs, which are described in Section 4.3.  The collection of LSAs
   forms the link-state database.  Each separate type of LSA has a
   separate function. Router-LSAs and network-LSAs describe how an
   area's routers and networks are interconnected.  Summary-LSAs provide
   a way of condensing an area's routing information. AS-external-LSAs
   provide a way of transparently advertising externally-derived routing
   information throughout the Autonomous System.

   Each LSA begins with a standard 20-byte header.  This LSA header is
   discussed below.

    Type   Dest        Area   Path  Type   Cost   Next     Adv.
                                                  Hop(s)   Router(s)
    ________________________________________________________________
    N      Ib          0      intra-area   16     RT3      *
    N      Ia          0      intra-area   21     RT3      *
    R      RT3         0      intra-area   1      *        *
    R      RT10        0      intra-area   16     RT3      *
    R      RT11        0      intra-area   19     RT3      *
    ________________________________________________________________
    N      N9-N11,H1   0      inter-area   30     RT3      RT11


                  Table 14: Changes resulting from an
                        additional virtual link.

12.1.  The LSA Header

   The LSA header contains the LS type, Link State ID and Advertising
   Router fields.  The combination of these three fields uniquely
   identifies the LSA.

   There may be several instances of an LSA present in the Autonomous
   System, all at the same time.  It must then be determined which
   instance is more recent.  This determination is made by examining the
   LS sequence, LS checksum and LS age fields.  These fields are also
   contained in the 20-byte LSA header.

   Several of the OSPF packet types list LSAs.  When the instance is not
   important, an LSA is referred to by its LS type, Link State ID and
   Advertising Router (see Link State Request Packets).  Otherwise, the
   LS sequence number, LS age and LS checksum fields must also be
ToP   noToC   RFC2178 - Page 101
   referenced.

   A detailed explanation of the fields contained in the LSA header
   follows.

12.1.1.  LS age

   This field is the age of the LSA in seconds.  It should be processed
   as an unsigned 16-bit integer.  It is set to 0 when the LSA is
   originated.  It must be incremented by InfTransDelay on every hop of
   the flooding procedure.  LSAs are also aged as they are held in each
   router's database.

   The age of an LSA is never incremented past MaxAge.  LSAs having age
   MaxAge are not used in the routing table calculation.  When an LSA's
   age first reaches MaxAge, it is reflooded. An LSA of age MaxAge is
   finally flushed from the database when it is no longer needed to
   ensure database synchronization.  For more information on the aging
   of LSAs, consult Section 14.

   The LS age field is examined when a router receives two instances of
   an LSA, both having identical LS sequence numbers and LS checksums.
   An instance of age MaxAge is then always accepted as most recent;
   this allows old LSAs to be flushed quickly from the routing domain.
   Otherwise, if the ages differ by more than MaxAgeDiff, the instance
   having the smaller age is accepted as most recent.[12] See Section
   13.1 for more details.

12.1.2.  Options

   The Options field in the LSA header indicates which optional
   capabilities are associated with the LSA.  OSPF's optional
   capabilities are described in Section 4.5. One optional capability is
   defined by this specification, represented by the E-bit found in the
   Options field.  The unrecognized bits in the Options field should be
   set to zero.  The E-bit represents OSPF's ExternalRoutingCapability.
   This bit should be set in all LSAs associated with the backbone, and
   all LSAs associated with non-stub areas (see Section 3.6).  It should
   also be set in all AS-external-LSAs.  It should be reset in all
   router-LSAs, network-LSAs and summary-LSAs associated with a stub
   area.  For all LSAs, the setting of the E-bit is for informational
   purposes only; it does not affect the routing table calculation.
ToP   noToC   RFC2178 - Page 102
12.1.3.  LS type

   The LS type field dictates the format and function of the LSA.  LSAs
   of different types have different names (e.g., router-LSAs or
   network-LSAs).  All LSA types defined by this memo, except the AS-
   external-LSAs (LS type = 5), are flooded throughout a single area
   only.  AS-external-LSAs are flooded throughout the entire Autonomous
   System, excepting stub areas (see Section 3.6).  Each separate LSA
   type is briefly described below in Table 15.

12.1.4.  Link State ID

   This field identifies the piece of the routing domain that is being
   described by the LSA.  Depending on the LSA's LS type, the Link State
   ID takes on the values listed in Table 16.

   Actually, for Type 3 summary-LSAs (LS type = 3) and AS-external-LSAs
   (LS type = 5), the Link State ID may additionally have one or more of
   the destination network's "host" bits set. For example, when
   originating an AS-external-LSA for the network 10.0.0.0 with mask of
   255.0.0.0, the Link State ID can be set to anything in the range
   10.0.0.0 through 10.255.255.255 inclusive (although 10.0.0.0 should
   be used whenever possible). The freedom to set certain host bits
   allows a router to originate separate LSAs for two networks having
   the same address but different masks. See Appendix E for details.
ToP   noToC   RFC2178 - Page 103
            LS Type   LSA description
            ________________________________________________
            1         These are the router-LSAs.
                      They describe the collected
                       states of the router's
                      interfaces. For more information,
                      consult Section 12.4.1.
            ________________________________________________
            2         These are the network-LSAs.
                      They describe the set of routers
                      attached to the network. For
                      more information, consult
                      Section 12.4.2.
            ________________________________________________
            3 or 4    These are the summary-LSAs.
                      They describe inter-area routes,
                      and enable the condensation of
                      routing information at area
                      borders. Originated by area border
                      routers, the Type 3 summary-LSAs
                      describe routes to networks while the
                      Type 4 summary-LSAs describe routes to
                      AS boundary routers.
            ________________________________________________
            5         These are the AS-external-LSAs.
                      Originated by AS boundary routers,
                      they describe routes
                      to destinations external to the
                      Autonomous System. A default route for
                      the Autonomous System can also be
                      described by an AS-external-LSA.

            Table 15: OSPF link state advertisements (LSAs).

            LS Type   Link State ID
            _______________________________________________
            1         The originating router's Router ID.
            2         The IP interface address of the
                      network's Designated Router.
            3         The destination network's IP address.
            4         The Router ID of the described AS
                      boundary router.
            5         The destination network's IP address.


                   Table 16: The LSA's Link State ID.
ToP   noToC   RFC2178 - Page 104
   When the LSA is describing a network (LS type = 2, 3 or 5), the
   network's IP address is easily derived by masking the Link State ID
   with the network/subnet mask contained in the body of the LSA.  When
   the LSA is describing a router (LS type = 1 or 4), the Link State ID
   is always the described router's OSPF Router ID.

   When an AS-external-LSA (LS Type = 5) is describing a default route,
   its Link State ID is set to DefaultDestination (0.0.0.0).

12.1.5.  Advertising Router

   This field specifies the OSPF Router ID of the LSA's originator.  For
   router-LSAs, this field is identical to the Link State ID field.
   Network-LSAs are originated by the network's Designated Router.
   Summary-LSAs originated by area border routers.  AS-external-LSAs are
   originated by AS boundary routers.

12.1.6.  LS sequence number


   The sequence number field is a signed 32-bit integer.  It is used to
   detect old and duplicate LSAs.  The space of sequence numbers is
   linearly ordered.  The larger the sequence number (when compared as
   signed 32-bit integers) the more recent the LSA.  To describe to
   sequence number space more precisely, let N refer in the discussion
   below to the constant 2**31.

   The sequence number -N (0x80000000) is reserved (and unused).  This
   leaves -N + 1 (0x80000001) as the smallest (and therefore oldest)
   sequence number; this sequence number is referred to as the constant
   InitialSequenceNumber. A router uses InitialSequenceNumber the first
   time it originates any LSA.  Afterwards, the LSA's sequence number is
   incremented each time the router originates a new instance of the
   LSA.  When an attempt is made to increment the sequence number past
   the maximum value of N - 1 (0x7fffffff; also referred to as
   MaxSequenceNumber), the current instance of the LSA must first be
   flushed from the routing domain.  This is done by prematurely aging
   the LSA (see Section 14.1) and reflooding it.  As soon as this flood
   has been acknowledged by all adjacent neighbors, a new instance can
   be originated with sequence number of InitialSequenceNumber.

   The router may be forced to promote the sequence number of one of its
   LSAs when a more recent instance of the LSA is unexpectedly received
   during the flooding process. This should be a rare event.  This may
   indicate that an out-of-date LSA, originated by the router itself
   before its last restart/reload, still exists in the Autonomous
   System.  For more information see Section 13.4.
ToP   noToC   RFC2178 - Page 105
12.1.7.  LS checksum

   This field is the checksum of the complete contents of the LSA,
   excepting the LS age field.  The LS age field is excepted so that an
   LSA's age can be incremented without updating the checksum.  The
   checksum used is the same that is used for ISO connectionless
   datagrams; it is commonly referred to as the Fletcher checksum.  It
   is documented in Annex B of [Ref6]. The LSA header also contains the
   length of the LSA in bytes; subtracting the size of the LS age field
   (two bytes) yields the amount of data to checksum.

   The checksum is used to detect data corruption of an LSA.  This
   corruption can occur while an LSA is being flooded, or while it is
   being held in a router's memory.  The LS checksum field cannot take
   on the value of zero; the occurrence of such a value should be
   considered a checksum failure.  In other words, calculation of the
   checksum is not optional.

   The checksum of an LSA is verified in two cases: a) when it is
   received in a Link State Update Packet and b) at times during the
   aging of the link state database.  The detection of a checksum
   failure leads to separate actions in each case.  See Sections 13 and
   14 for more details.

   Whenever the LS sequence number field indicates that two instances of
   an LSA are the same, the LS checksum field is examined.  If there is
   a difference, the instance with the larger LS checksum is considered
   to be most recent.[13] See Section 13.1 for more details.

12.2.  The link state database

   A router has a separate link state database for every area to which
   it belongs. All routers belonging to the same area have identical
   link state databases for the area.

   The databases for each individual area are always dealt with
   separately.  The shortest path calculation is performed separately
   for each area (see Section 16).  Components of the area link-state
   database are flooded throughout the area only.  Finally, when an
   adjacency (belonging to Area A) is being brought up, only the
   database for Area A is synchronized between the two routers.

   The area database is composed of router-LSAs, network-LSAs and
   summary-LSAs (all listed in the area data structure).  In addition,
   external routes (AS-external-LSAs) are included in all non-stub area
   databases (see Section 3.6).
ToP   noToC   RFC2178 - Page 106
   An implementation of OSPF must be able to access individual pieces of
   an area database.  This lookup function is based on an LSA's LS type,
   Link State ID and Advertising Router.[14] There will be a single
   instance (the most up-to-date) of each LSA in the database.  The
   database lookup function is invoked during the LSA flooding procedure
   (Section 13) and the routing table calculation (Section 16).  In
   addition, using this lookup function the router can determine whether
   it has itself ever originated a particular LSA, and if so, with what
   LS sequence number.

   An LSA is added to a router's database when either a) it is received
   during the flooding process (Section 13) or b) it is originated by
   the router itself (Section 12.4).  An LSA is deleted from a router's
   database when either a) it has been overwritten by a newer instance
   during the flooding process (Section 13) or b) the router originates
   a newer instance of one of its self-originated LSAs (Section 12.4) or
   c) the LSA ages out and is flushed from the routing domain (Section
   14).

   Whenever an LSA is deleted from the database it must also be removed
   from all neighbors' Link state retransmission lists (see Section 10).

12.3.  Representation of TOS

   For backward compatibility with previous versions of the OSPF
   specification ([Ref9]), TOS-specific information can be included in
   router-LSAs, summary-LSAs and AS-external-LSAs.  The encoding of TOS
   in OSPF LSAs is specified in Table 17. That table relates the OSPF
   encoding to the IP packet header's TOS field (defined in [Ref12]).
   The OSPF encoding is expressed as a decimal integer, and the IP
   packet header's TOS field is expressed in the binary TOS values used
   in [Ref12].
ToP   noToC   RFC2178 - Page 107
                    OSPF encoding   RFC 1349 TOS values
                    ___________________________________________
                    0               0000 normal service
                    2               0001 minimize monetary cost
                    4               0010 maximize reliability
                    6               0011
                    8               0100 maximize throughput
                    10              0101
                    12              0110
                    14              0111
                    16              1000 minimize delay
                    18              1001
                    20              1010
                    22              1011
                    24              1100
                    26              1101
                    28              1110
                    30              1111

                  Table 17: Representing TOS in OSPF.



(page 107 continued on part 5)

Next Section