tech-invite   World Map     

3GPP     Specs     Glossaries     Architecture     IMS     UICC       IETF     RFCs     Groups     SIP     ABNFs       Search

RFC 2642

 
 
 

Cabletron's VLS Protocol Specification

Part 2 of 4, p. 23 to 51
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 23 
4. Neighbor Data Structure

   Each switch conducts a conversation with its neighboring switches and
   each conversation is described by a neighbor data structure.  A
   conversation is associated with a switch interface, and is identified
   by the neighboring switch ID.

   Note that if two switches have multiple attached links in common,
   multiple conversations ensue, each described by a unique neighbor
   data structure.  Each separate conversation is treated as a separate
   neighbor.

   The neighbor data structure contains all information relevant to any
   adjacency formed between the two neighbors.  Remember, however, that
   not all neighbors become adjacent.  An adjacency can be thought of as
   a highly developed conversation between two switches.

   State

      The functional level of the neighbor conversation.  See Section
      4.1 for a complete description of neighbor states.

   Inactivity timer

      A one-shot timer used to determine when to declare the neighbor
      down if no Hello packet is received from this (multi-access)
      neighbor.  The length of the timer is SwitchDeadInterval seconds,
      as contained in the neighbor's Hello packet.  This timer is not
      used on point-to-point links.

   Master/slave flag

      A flag indicating whether the local switch is to act as the master
      or the slave in the database exchange process (see Section 7.2).
      The master/slave relationship is negotiated when the conversation
      changes to the ExStart state.

   Sequence number

      A 4-octet number identifying individual Database Description
      packets. When the neighbor state ExStart is entered and the
      database exchange process is started, the sequence number is set
      to a value not previously seen by the neighboring switch. (One
      possible scheme is to use the switch's time of day counter.)  The
      sequence number is then incremented by the master with each new
      Database Description packet sent.  See Section 7.2 for more
      information on the database exchange process.

Top      Up      ToC       Page 24 
   Neighbor ID

      The switch ID of the neighboring switch, as discovered by the
      VlanHello protocol [IDhello] or contained in the neighbor's Hello
      packets.

   Neighbor priority

      The switch priority of the neighboring switch, as contained in the
      neighbor's Hello packets.  Switch priorities are used when
      selecting the designated switch for the attached multi-access
      link.  Priority is not used on point-to-point links.

   Interface identifier

      A 10-octet value that uniquely identifies the interface over which
      this conversation is being held.  This value consists of the 6-
      octet base MAC address of the neighbor switch, followed by the 4-
      octet local port number of the interface.

   Neighbor's designated switch

      The switch ID identifying the neighbor's idea of the designated
      switch, as contained in the neighbor's Hello packets.  This value
      is used in the local selection of the designated switch.  It is
      not used on point-to-point links.

   Neighbor's backup designated switch

      The switch ID identifying the neighbor's idea of the backup
      designated switch, as contained in the neighbor's Hello packets.
      This value is used in the local selection of the backup designated
      switch.  It is not used on point-to-point links.

   Link state retransmission list

      The list of link state advertisements that have been forwarded
      over but not acknowledged on this adjacency.  The local switch
      retransmits these link state advertisements at periodic intervals
      until they are acknowledged or until the adjacency is destroyed.
      (For more information on retransmitting link state advertisements,
      see Section 8.2.5.)

Top      Up      ToC       Page 25 
   Database summary list

      The set of link state advertisement headers that summarize the
      local link state database.  When the conversation changes to the
      Exchange state, this list is sent to the neighbor via Database
      Description packets.  (For more information on the synchronization
      of databases, see Section 7.)

   Link state request list

      The list of link state advertisements that must be received in
      order to synchronize with the neighbor switch's link state
      database.  This list is created as Database Description packets
      are received, and is then sent to the neighbor in Link State
      Request packets.  (For more information on the synchronization of
      databases, see Section 7.)

4.1 Neighbor States

   This section describes the various states of a conversation with a
   neighbor switch.  The states are listed in order of progressing
   functionality.  For example, the inoperative state is listed first,
   followed by a list of the intermediate states through which the
   conversation passes before attaining the final, fully functional
   state.  The specification makes use of this ordering by references
   such as "those neighbors/adjacencies in state greater than X".

   Figure 2 represents the neighbor state machine.  The arrows on the
   graph represent the events causing each state change.  These events
   are described in Section 4.2.  The neighbor state machine is
   described in detail in Section 4.3.

   Down

      This is the initial state of a neighbor conversation.

   Init

      In this state, the neighbor has been discovered, but bidirectional
      communication has not yet been established. All neighbors in this
      state or higher are listed in the VLS Hello packets sent by the
      local switch over the associated (multi-access) interface.

Top      Up      ToC       Page 26 
          +----------+     KillNbr, LLDown,   +-----------+
          |   Down   | <--------------------- | any state |
          +----------+   or Inactivity Timer  +-----------+
               |
         Hello |
          Rcvd |
               |
               V
   +-----< [pt-to-pt?]
   | yes       |
   |           | no
   |           V
   |      +----------+   1-Way   +----------+
   |      |   Init   | <-------- | >= 2-way |
   |      +----------+           +----------+
   |           |
   |     2-Way |
   |      Rcvd |                  +-------+   AdjOK? +------------+
   |           +----------------> | 2-Way | <------- | >= ExStart |
   |           | (no adjacency)   +-------+     no   +------------+
   |           |
   |           V
   |      +---------+   Seq Number Mismatch  +-------------+
   +----> | ExStart | <--------------------- | >= Exchange |
          +---------+       or BadLSReq      +-------------+
               |
   Negotiation |
       Done    |
               V
          +----------+
          | Exchange |
          +----------+
               |
      Exchange |                        +--------+
        Done   +----------------------> |  Full  |
               | (request list empty)   +--------+
               |                             ^
               V                             |
          +---------+      Loading Done      |
          | Loading | ----------------------->
          +---------+

                  Figure 2: Neighbor State Machine

Top      Up      ToC       Page 27 
   2-Way

      In this state, communication between the two switches is
      bidirectional.  This is the most advanced state short of beginning
      to establish an adjacency.  On a multi-access link, the designated
      switch and the backup designated switch are selected from the set
      of neighbors in state 2-Way or greater.

   ExStart

      This state indicates that the two switches have begun to establish
      an adjacency by determining which switch is the master, as well as
      the initial sequence number for Database Descriptor packets.
      Neighbor conversations in this state or greater are called
      adjacencies.

   Exchange

      In this state, the switches are exchanging Database Description
      packets.  (See Section 7.2 for a complete description of this
      process.)  All adjacencies in the Exchange state or greater are
      used by the distribution procedure (see Section 8.2), and are
      capable of transmitting and receiving all types of VLSP routing
      packets.

   Loading

      In this state, the local switch is sending Link State Request
      packets to the neighbor asking for the more recent advertisements
      that were discovered in the Exchange state.

   Full

      In this state, the two switches are fully adjacent.  These
      adjacencies will now appear in switch link and network link
      advertisements generated for the link.

4.2 Events Causing Neighbor State Changes

   The state of a neighbor conversation changes due to neighbor events.
   This section describes these events.

   Neighbor events are shown as arrows in Figure 2, the graphic
   representation of the neighbor state machine.  For more information
   on the neighbor state machine, see Section 4.3.

Top      Up      ToC       Page 28 
   Hello Received

      This event is generated when a Hello packet has been received from
      a neighbor.

   2-Way Received

      This event is generated when the local switch sees its own switch
      ID listed in the neighbor's Hello packet, indicating that
      bidirectional communication has been established between the two
      switches.

   Negotiation Done

      This event is generated when the master/slave relationship has
      been successfully negotiated and initial packet sequence numbers
      have been exchanged.  This event signals the start of the database
      exchange process (see Section 7.2).

   Exchange Done

      This event is generated when the database exchange process is
      complete and both switches have successfully transmitted a full
      sequence of Database Description packets.  (For more information
      on the database exchange process, see Section 7.2.)

   BadLSReq

      This event is generated when a Link State Request has been
      received for a link state advertisement that is not contained in
      the database.  This event indicates an error in the
      synchronization process.

   Loading Done

      This event is generated when all Link State Updates have been
      received for all out-of-date portions of the database.  (See
      Section 7.3.)

   AdjOK?

      This event is generated when a decision must be made as to whether
      an adjacency will be established or maintained with the neighbor.
      This event will initiate some adjacencies and destroy others.

Top      Up      ToC       Page 29 
   Seq Number Mismatch

      This event is generated when a Database Description packet has
      been received with any of the following conditions:

      o  The packet contains an unexpected sequence number.
      o  The packet (unexpectedly) has the Init bit set.
      o  The packet has a different Options field than was
         previously seen.

      These conditions all indicate that an error has occurred during
      the establishment of the adjacency.

   1-Way

      This event is generated when bidirectional communication with the
      neighbor has been lost.  That is, a Hello packet has been received
      from the neighbor in which the local switch is not listed.

   KillNbr

      This event is generated when further communication with the
      neighbor is impossible.

   Inactivity Timer

      This event is generated when the inactivity timer has expired,
      indicating that no Hello packets have been received from the
      neighbor in SwitchDeadInterval seconds.  This timer is used only
      on broadcast (multi-access) links.

   LLDown

      This event is generated by the lower-level switch discovery
      protocols and indicates that the neighbor is now unreachable.

4.3 Neighbor State Machine

   This section presents a detailed description of the neighbor state
   machine.

   Neighbor states (see Section 4.1) change as the result of various
   events (see Section 4.2).  However, the effect of each event can
   vary, depending on the current state of the conversation with the
   neighbor.  For this reason, the state machine described in this
   section is organized according to the current neighbor state and the
   occurring event.  For each state/event pair, the new neighbor state
   is listed, along with a description of the required processing.

Top      Up      ToC       Page 30 
   Note that when the neighbor state changes as a result of an interface
   Neighbor Change event (see Section 3.2), it may be necessary to rerun
   the designated switch selection algorithm. In addition, if the
   interface associated with the neighbor conversation is in the DS
   state (that is, the local switch is the designated switch), changes
   in the neighbor state may cause a new network link advertisement to
   be originated (see Section 8.1).

   When the neighbor state machine must invoke the interface state
   machine, it is invoked as a scheduled task.  This simplifies
   processing, by ensuring that neither state machine executes
   recursively.

   State(s):  Down
   Event:  Hello Received
   New state:  Depends on the interface type
   Action:
      If the interface type of the associated link is point-to-point,
      change the neighbor state to ExStart.  Otherwise, change the
      neighbor state to Init and start the inactivity timer for the
      neighbor.  If the timer expires before another Hello packet is
      received, the neighbor switch is declared dead.

   State(s):  Init or greater
   Event:  Hello Received
   New state:  No state change
   Action:
      If the interface type of the associated link is point-to-point,
      determine whether this notification is for a different neighbor
      than the one previously seen. If so, generate an Interface Down
      event for the associated interface, reset the interface type to
      broadcast and generate an Interface Up event.

   Note:  This procedure of generating an Interface Down event and
   changing the interface type to broadcast is also executed if the
   neighbor for whom the notification was received is running an older
   version of the protocol software (see Section 6.1).  In previous
   versions of the protocol, all interfaces were treated as if they were
   broadcast.

      If the interface type is broadcast, reset the inactivity timer for
      the neighbor.

Top      Up      ToC       Page 31 
   State(s):  Init
   Event:  2-Way Received
   New state:  Depends on action routine
   Action:
      Determine whether an adjacency will be formed with the neighbor
      (see Section 6.4).  If no adjacency is to be formed, change the
      neighbor state to 2-Way.

      Otherwise, change the neighbor state to ExStart.  Initialize the
      sequence number for this neighbor and declare the local switch to
      be master for the database exchange process.  (See Section 7.2.)

   State(s):  ExStart
   Event:  Negotiation Done
   New state:  Exchange
   Action:
      The Negotiation Done event signals the start of the database
      exchange process.  See Section 7.2 for a detailed description of
      this process.

   State(s):  Exchange
   Event:  Exchange Done
   New state:  Depends on action routine
   Action:
      If the neighbor Link state request list is empty, change the
      neighbor state to Full.  This is the adjacency's final state.

      Otherwise, change the neighbor state to Loading.  Begin sending
      Link State Request packets to the neighbor requesting the most
      recent link state advertisements, as discovered during the
      database exchange process.  (See Section 7.2.) These
      advertisements are listed in the link state request list
      associated with the neighbor.

   State(s):  Loading
   Event:  Loading Done
   New state:  Full
   Action:
      No action is required beyond changing the neighbor state to Full.
      This is the adjacency's final state.

Top      Up      ToC       Page 32 
   State(s):  2-Way
   Event:  AdjOK?
   New state:  Depends on action routine
   Action:
      If no adjacency is to be formed with the neighboring switch (see
      Section 6.4), retain the neighbor state at 2-Way. Otherwise,
      change the neighbor state to ExStart.  Initialize the sequence
      number for this neighbor and declare the local switch to be master
      for the database exchange process.  (See Section 7.2.)

   State(s):  ExStart or greater
   Event:  AdjOK?
   New state:  Depends on action routine
   Action:
      If an adjacency should still be formed with the neighboring switch
      (see Section 6.4), no state change and no further action is
      necessary.  Otherwise, tear down the (possibly partially formed)
      adjacency.  Clear the link state retransmission list, database
      summary list and link state request list and change the neighbor
      state to 2-Way.

   State(s):  Exchange or greater
   Event:  Seq Number Mismatch
   New state:  ExStart
   Action:
      Tear down the (possibly partially formed) adjacency.  Clear the
      link state retransmission list, database summary list and link
      state request list.  Change the neighbor state to ExStart and make
      another attempt to establish the adjacency.

   State(s):  Exchange or greater
   Event:  BadLSReq
   New state:  ExStart
   Action:
      Tear down the (possibly partially formed) adjacency.  Clear the
      link state retransmission list, database summary list and link
      state request list.  Change the neighbor state to ExStart and make
      another attempt to establish the adjacency.

   State(s):  Any state
   Event:  KillNbr
   New state:  Down
   Action:
      Terminate the neighbor conversation.  Disable the inactivity timer
      and clear the link state retransmission list, database summary
      list and link state request list.

Top      Up      ToC       Page 33 
   State(s):  Any state
   Event:  LLDown
   New state:  Down
   Action:
      Terminate the neighbor conversation.  Disable the inactivity timer
      and clear the link state retransmission list, database summary
      list and link state request list.

   State(s):  Any state
   Event:  Inactivity Timer
   New state:  Down
   Action:
      Terminate the neighbor conversation.  Disable the inactivity timer
      and clear the link state retransmission list, database summary
      list and link state request list.

   State(s):  2-Way or greater
   Event:  1-Way Received
   New state:  Init
   Action:
      Tear down the adjacency between the switches, if any.  Clear the
      link state retransmission list, database summary list and link
      state request list.

   State(s):  2-Way or greater
   Event:  2-Way received
   New state:  No state change
   Action:
      No action required.

   State(s):  Init
   Event:  1-Way received
   New state:  No state change
   Action:
            No action required.

5. Area Data Structure

   The area data structure contains all the information needed to run
   the basic routing algorithm.  One of its components is the link state
   database -- the collection of all switch link and network link
   advertisements generated by the switches.

   The area data structure contains the following items:

Top      Up      ToC       Page 34 
   Area ID

      A 4-octet value identifying the area.  Since VLSP does not support
      multiple areas, the value here is always zero.

   Associated switch interfaces

      A list of interface IDs of the local switch interfaces connected
      to network links.

   Link state database

      The collection of all current link state advertisements for the
      switch fabric.  This collection consists of the following:

   Switch link advertisements

      A list of the switch link advertisements for all switches in the
      fabric.  Switch link advertisements describe the state of each
      switch's interfaces.

   Network link advertisements

      A list of the network link advertisements for all multi-access
      network links in the switch fabric.  Network link advertisements
      describe the set of switches currently connected to each link.

   Best path(s)

      A set of end-to-end hop descriptions for all equal-cost best paths
      from the local switch to every other switch in the fabric.  Each
      hop is specified by the interface ID of the next link in the path.
      Best paths are derived from the collected switch link and network
      link advertisements using the Dijkstra algorithm. [Perlman]

5.1 Adding and Deleting Link State Advertisements

   The link state database within the area data structure must contain,
   at most, a single instance of each link state advertisement.  To keep
   the database current, a switch adds link state advertisements to the
   database under the following conditions:

   o  When a link state advertisement is received during the
      distribution process

      o  When the switch itself generates a link state advertisement

Top      Up      ToC       Page 35 
   (See Section 8.2.4 for information on installing link state
   advertisements.)

   Likewise, a switch deletes link state advertisements from the
   database under the following conditions:

   o  When a link state advertisement has been superseded by a newer
      instance during the flooding process

   o  When the switch generates a newer instance of one of its self-
      originated advertisements

   Note that when an advertisement is deleted from the link state
   database, it must also be removed from the link state retransmission
   list of all neighboring switches.

5.2 Accessing Link State Advertisements

   An implementation of the VLS protocol must provide access to
   individual link state advertisements, based on the advertisement's
   type, link state identifier, and advertising switch [1].  This lookup
   function is invoked during the link state distribution procedure and
   during calculation of the set of best paths.  In addition, a switch
   can use the function to determine whether it has originated a
   particular link state advertisement, and if so, with what sequence
   number.

5.3 Best Path Lookup

   An implementation of the VLS protocol must provide access to multiple
   equal-cost best paths, based on the base MAC addresses of the source
   and destination switches.  This lookup function should return up to
   three equal-cost paths.  Paths should be returned as lists of end-
   to-end hop information, with each hop specified as a interface ID of
   the next link in the path -- the 6-octet base MAC address of the next
   switch and the 4-octet local port number of the link interface.

6. Discovery Process

   The first operational stage of the VLS protocol is the discovery
   process.  During this stage, each switch dynamically detects its
   neighboring switches and establishes a relationship with each of
   these neighbors.  This process has the following component steps:

Top      Up      ToC       Page 36 
   o  Neighboring switches are detected on each functioning network
      interface.

   o  Bidirectional communication is established with each neighbor
      switch.

   o  A designated switch and backup designated switch are selected for
      each multi-access network link.

   o  An adjacent relationship is established with selected neighbors on
      each link.

6.1 Neighbor Discovery

   When the switch first comes on line, VLSP assumes all network links
   are point-to-point and no more than one neighboring switch will be
   discovered on any one port.  Therefore, at startup, VLSP relies on
   the VlanHello protocol [IDhello] for the discovery of its neighbor
   switches.

   As each neighbor is detected, VlanHello triggers a Found Neighbor
   event, notifying VLSP that a new neighbor has been discovered.  (See
   [IDhello] for a description of the Found Neighbor event and the
   information passed.)  VLSP enters the neighbor switch ID in the list
   of known neighbors and creates a new neighbor data structure with a
   neighbor status of Down.  A Hello Received neighbor event is then
   generated, which changes the neighbor state to ExStart.

   There are two circumstances under which VLSP will change the type of
   an interface to broadcast:

   o  If VLSP receives a subsequent notification from VlanHello,
      specifying a second (different) neighbor switch on the port., the
      interface is then known to be multi-access.  VLSP generates an
      Interface Down event for the interface, resets the interface type
      to broadcast, and then generates an Interface Up event.

   o  If the functional level of the neighbor switch is less than 2, the
      neighbor is running a previous version of the VLSP software in
      which all links were treated as broadcast links. VLSP immediately
      changes the interface type to broadcast and generates an Interface
      Up event.

      In both cases, VLSP assumes control of communication over the
      interface by exchanging its own VLSP Hello packets with the
      neighbors on the link.

Top      Up      ToC       Page 37 
   Note:  These Hello packets are in addition to the Interswitch
   Keepalive messages sent by VlanHello.  VlanHello still continues to
   monitor the condition of the interface and notifies VLSP of any
   change.

   Each Hello packet contains the following data used during the
   discovery process on multi-access links:

   o  The switch ID and priority of the sending switch

   o  Values specifying the interval timers to be used for sending Hello
      packets and deciding whether to declare a neighbor switch Down.

   o  The switch ID of the designated switch and the backup designated
      switch for the link, as understood by the sending switch

   o  A list of switch IDs of all neighboring switches seen so far on
      the link

   For a detailed description of the Hello packet format, see Section
   10.6.1.

   When VLSP receives a Hello packet (on a broadcast link), it first
   attempts to identify the sending switch by matching its switch ID to
   one of the known neighbors listed in the interface data structure.
   If this is the first Hello packet received from the switch, the
   switch ID is entered in the list of known neighbors and a new
   neighbor data structure is created with a neighbor status of Down.

   At this point, the remainder of the Hello packet is examined and the
   appropriate interface and neighbor events are generated.  In all
   cases, a neighbor Hello Received event is generated.  Other events
   may also be generated, triggering further steps in the discovery
   process or other actions, as appropriate.

   For a detailed description of the interface state machine, see
   Section 3.3.  For a detailed description of the neighbor state
   machine, see Section 4.3.

6.2 Bidirectional Communication

   Before a conversation can proceed with a neighbor switch,
   bidirectional communication must be established with that neighbor.
   Bidirectional communication is detected in one of two ways:

Top      Up      ToC       Page 38 
   o  On a point-to-point link, the VlanHello protocol sees its own
      switch ID listed in an Interswitch Keepalive message it has
      received from the neighbor.

   o  On a multi-access link, VLSP sees its own switch ID listed in a
      VLSP Hello packet it has received from the neighbor.

   In either case, a neighbor 2-Way Received neighbor event is
   generated.

   Once bidirectional communication has been established with a
   neighbor, the local switch determines whether an adjacency will be
   formed with the neighbor.  However, if the link is a multi-access
   link, a designated switch and a backup designated switch must first
   be selected for the link.  The next section contains a description of
   the designated switch, the backup designated switch, and the
   selection process.

6.3 Designated Switch

   Every multi-access network link has a designated switch.  The
   designated switch performs the following functions for the routing
   protocol:

   o  The designated switch originates a network link advertisement on
      behalf of the link, listing the set of switches (including the
      designated switch itself) currently attached to the link. For a
      detailed description of network link advertisements, see Section
      11.3.

   o  The designated switch becomes adjacent to all other switches on
      the link.  Since the link state databases are synchronized across
      adjacencies, the designated switch plays a central part in the
      synchronization process.  For a description of the synchronization
      process, see Section 7.

   Each multi-access network link also has a backup designated switch.
   The primary function of the backup designated switch is to act as a
   standby for the designated switch.  If the current designated switch
   fails, the backup designated switch becomes the designated switch.

   To facilitate this transition, the backup designated switch forms an
   adjacency with every other switch on the link.  Thus, when the backup
   designated switch must take over for the designated switch, its link
   state database is already synchronized with the databases of all
   other switches on the link.

Top      Up      ToC       Page 39 
   Note:  Point-to-point network links have neither a designated switch
   or a backup designated switch.

6.3.1 Selecting the Designated Switch

   When a multi-access link interface first becomes functional, the
   switch sets a one-shot Wait timer (with a value of SwitchDeadInterval
   seconds) for the interface.  The purpose of this timer is to ensure
   that all switches attached to the link have a chance to establish
   bidirectional communication before the designated switch and backup
   designated switch are selected for the link.

   When the Wait timer is set, the interface enters the Waiting state.
   During this state, the switch exchanges Hello packets with its
   neighbors attempting to establish bidirectional communication.  The
   interface leaves the Waiting state under one of the following
   conditions:

   o  The Wait timer expires.

   o  A Hello packet is received indicating that a designated switch or
      a backup designated switch has already been specified for the
      interface.

   At this point, if the switch sees that a designated switch has
   already been selected for the link, the switch accepts that
   designated switch, regardless of its own switch priority and MAC
   address.  This situation typically means the switch has come up late
   on a fully functioning link.  Although this makes it harder to
   predict the identity of the designated switch on a particular link,
   it ensures that the designated switch does not change needlessly,
   necessitating a resynchronization of the databases.

   If no designated switch is currently specified for the link, the
   switch begins the actual selection process.  Note that this selection
   algorithm operates only on a list of neighbor switches that are
   eligible to become the designated switch.  A neighbor is eligible to
   be the designated switch if it has a switch priority greater than
   zero and its neighbor state is 2-Way or greater.  The local switch
   includes itself on the list of eligible switches as long as it has a
   switch priority greater than zero.

   The selection process includes the following steps:

   1. The current values of the link's designated switch and backup
      designated switch are saved for use in step 6.

   2. The new backup designated switch is selected as follows:

Top      Up      ToC       Page 40 
      a) Eliminate from consideration those switches that have declared
         themselves to be the designated switch.

      b) If one or more of the remaining switches have declared
         themselves to be the backup designated switch, eliminate from
         consideration all other switches.

      c) From the remaining list of eligible switches, select the switch
         having the highest switch priority as the backup designated
         switch.  If multiple switches have the same (highest) priority,
         select the switch with the highest switch ID as the backup
         designated switch.

   3. The new designated switch is selected as follows:

      a) If one or more of the switches have declared themselves to be
         the designated switch, eliminate from consideration all other
         switches.

      b) From the remaining list of eligible switches, select the switch
         having the highest switch priority as the designated switch.
         If multiple switches have the same (highest) priority, select
         the switch with the highest switch ID as the designated switch.

   4. If the local switch has been newly selected as either the
      designated switch or the backup designated switch, or is now no
      longer the designated switch or the backup designated switch,
      repeat steps 2 and 3, above, and then proceed to step 5.

      If the local switch is now the designated switch, it will
      eliminate itself from consideration at step 2a when the selection
      of the backup designated switch is repeated. Likewise, if the
      local switch is now the backup designated switch, it will
      eliminate itself from consideration at step 3a when the selection
      of the designated switch is repeated. This ensures that no switch
      will select itself as both backup designated switch and designated
      switch [2].

   5. Set the interface state to the appropriate value, as follows:

   o  If the local switch is now the designated switch, set the
      interface state to DS.

   o  If the local switch is now the backup designated switch, set the
      interface state to Backup.

   o  Otherwise, set the interface state to DS Other.

Top      Up      ToC       Page 41 
   6. If either the designated switch or backup designated switch has
      now changed, the set of adjacencies associated with this link must
      be modified.  Some adjacencies may need to be formed, while others
      may need to be broken.  Generate the neighbor AdjOK? event for all
      neighbors with a state of 2-Way or higher to trigger a
      reexamination of adjacency eligibility.

   Caution:  If VLSP is implemented with configurable parameters, care
   must be exercised in specifying the switch priorities.  Note that if
   the local switch is not itself eligible to become the designated
   switch (i.e., it has a switch priority of 0), it is possible that
   neither a backup designated switch nor a designated switch will be
   selected by the above procedure.  Note also that if the local switch
   is the only attached switch that is eligible to become the designated
   switch, it will select itself as designated switch and there will be
   no backup designated switch for the link.  For this reason, it is
   advisable to specify a default switch priority of 1 for all switches.

6.4 Adjacencies

   VLSP creates adjacencies between neighboring switches for the purpose
   of exchanging routing information.  Not every two neighboring
   switches will become adjacent.  On a multi-access link, an adjacency
   is only formed between two switches if one of them is either the
   designated switch or the backup designated switch.

   Note that an adjacency is bound to the network link that the two
   switches have in common.  Therefore, if two switches have multiple
   links in common, they may also have multiple adjacencies between
   them.

   The decision to form an adjacency occurs in two places in the
   neighbor state machine:

   o  When bidirectional communication is initially established with the
      neighbor.

   o  When the designated switch  or backup designated switch on the
      attached link changes.

   The rules for establishing an adjacency between two neighboring
   switches are as follows:

   o  On a point-to-point link, the two neighboring switches always
      establish an adjacency.

   o  On a multi-access link, an adjacency is established with the
      neighboring switch under one of the following conditions:

Top      Up      ToC       Page 42 
      o  The local switch itself is the designated switch.
      o  The local switch itself is the backup designated switch.
      o  The neighboring switch is the designated switch.
      o  The neighboring switch is the backup designated switch.

   If no adjacency is formed between two neighboring switches, the state
   of the neighbor conversation remains set to 2-Way.

7. Synchronizing the Databases

   In an SPF-based routing algorithm, it is important for the link state
   databases of all switches to stay synchronized.  VLSP simplifies this
   process by requiring only adjacent switches to remain synchronized.

   The synchronization process begins when the switches attempt to bring
   up the adjacency.  Each switch in the adjacency describes its
   database by sending a sequence of Database Description packets to its
   neighbor.  Each Database Description packet describes a set of link
   state advertisements belonging to the database.  When the neighbor
   sees a link state advertisement that is more recent than its own
   database copy, it makes a note to request this newer advertisement.

   During this exchange of Database Description packets (known as the
   database exchange process), the two switches form a master/slave
   relationship.  Database Description packets sent by the master are
   known as polls, and each poll contains a sequence number.  Polls are
   acknowledged by the slave by echoing the sequence number in the
   Database Description response packet.

   When all Database Description packets have been sent and
   acknowledged, the database exchange process is completed.  At this
   point, each switch in the exchange has a list of link state
   advertisements for which its neighbor has more recent instances.
   These advertisements are requested using Link State Request packets.

   Once the database exchange process has completed and all Link State
   Requests have been satisfied, the databases are deemed synchronized
   and the neighbor states of the two switches are set to Full,
   indicating that the adjacency is fully functional. Fully functional
   adjacencies are advertised in the link state advertisements of the
   two switches [3].

Top      Up      ToC       Page 43 
7.1 Link State Advertisements

   Link state advertisements form the core of the database from which a
   switch calculates the set of best paths to the other switches in the
   fabric.

   Each link state advertisement begins with a standard header. This
   header contains three data items that uniquely identify the link
   state advertisement.

   o  The link state type.  Possible values are as follows:

      1   Switch link advertisement -- describes the collected states of
         the switch's interfaces.

      2   Network link advertisement -- describes the set of switches
         attached to the network link.

   o  The link state ID, defined as follows:

      o  For a switch link advertisement -- the switch ID of the
         originating switch

      o  For a network link advertisement -- the switch ID of the
         designated switch for the link

   o  The switch ID of the advertising switch -- the switch that
      generated the advertisement

   The link state advertisement header also contains three data items
   that are used to determine which instance of a particular link state
   advertisement is the most current.  (See Section 7.1.1 for a
   description of how to determine which instance of a link state
   advertisement is the most current.)

   o  The link state sequence number

   o  The link state age, stored in seconds

   o  The link state checksum, a 16-bit unsigned value calculated for
      the entire contents of the link state advertisement, with the
      exception of the age field

   The remainder of each link state advertisement contains data specific
   to the type of the advertisement.  See Section 11 for a detailed
   description of the link state header, as well as the format of a
   switch link or network link advertisement.

Top      Up      ToC       Page 44 
7.1.1 Determining Which Link State Advertisement Is Newer

   At various times while synchronizing or updating the link state
   database, a switch must determine which instance of a particular link
   state advertisement is the most current.  This decision is made as
   follows:

   o  The advertisement having the greater sequence number is the most
      current.

   o  If both instances have the same sequence number, then:

      o  If the two instances have different checksum values, then the
         instance having the larger checksum is considered the most
         current [4].

   o  If both instances have the same sequence number and the same
      checksum value, then:

      o  If one (and only one) of the instances is of age MaxAge, then
         the instance of age MaxAge is considered the most current [5].

      o  Else, if the ages of the two instances differ by more than
         MaxAgeDiff, the instance having the smaller (younger) age is
         considered the most current [6].

      o  Else, the two instances are considered identical.

7.2 Database Exchange Process

   There are two stages to the database exchange process:

   o  Negotiating the master/slave relationship
   o  Exchanging database summary information

7.2.1 Database Description Packets

   Database Description packets are used to describe a switch's link
   state database during the database exchange process.  Each Database
   Description packet contains a list of headers of the link state
   advertisements currently stored in the sending switch's database.
   (See Section 11.1 for a description of a link state advertisement
   header.)

   In addition to the link state headers, each Database Description
   packet contains the following data items:

Top      Up      ToC       Page 45 
   o  A flag (the M-bit) indicating whether or not more packets are to
      follow.  Depending on the size of the local database and the
      maximum size of the packet, the list of headers in any particular
      Database Description packet may be only a partial list of the
      total database.  When the M-bit is set, the list of headers is
      only a partial list and more headers are to follow in subsequent
      packets.

   o  A flag (the I-bit) indicating whether or not this is the first
      Database Description packet sent for this execution of the
      database exchange process.

   o  A flag (the MS-bit) indicating whether the sending switch thinks
      it is the master or the slave in the database exchange process.
      If the flag is set, the switch thinks it is the master.

   o  A 4-octet sequence number for the packet.

   While the switches are negotiating the master/slave relationship,
   they exchange "empty" Database Description packets.  That is, packets
   that contain no link summary information.  Instead, the flags and
   sequence number constitute the information required for the
   negotiation process.

   See Section 10.6.2 for a more detailed description of a Database
   Description packet.

7.2.2 Negotiating the Master/Slave Relationship

   Before two switches can begin the actual exchange of database
   information, they must decide between themselves who will be the
   master in the exchange process and who will be the slave.  They must
   also agree on the starting sequence number for the Database
   Description packets.

   Once a switch has decided to form an adjacency with a neighboring
   switch, it sets the neighbor state to ExStart and begins sending
   empty Database Description packets to its neighbor.  These packets
   contain the starting sequence number the switch plans to use in the
   exchange process.  Also, the I-bit and M-bit flags are set, as well
   as the MS-bit.  Thus, each switch in the exchange begins by believing
   it will be the master.

   Empty Database Description packets are retransmitted every
   RxmtInterval seconds until the neighbor responds.

Top      Up      ToC       Page 46 
   When a switch receives an empty Database Description packet from its
   neighbor, it determines which switch will be the master by comparing
   the switch IDs.  The switch with the highest switch ID becomes the
   master of the exchange.  Based on this determination, the switch
   proceeds as follows:

   o  If the switch is to be the slave of the database exchange process,
      it acknowledges that it is the slave by sending another empty
      Database Description packet to the master. This packet contains
      the master's sequence number and has the MS-bit and the I-bit
      cleared.

   o  The switch then generates a neighbor event of Negotiation Done to
      change its neighbor state to Exchange and waits for the first
      non-empty Database Description packet from the master.

   o  If the switch is to be the master of the database exchange, it
      waits to receive an acknowledgment from its neighbor -- that is,
      an empty Database Description packet with the MS-bit and I-bit
      cleared and containing the sequence number it (the master)
      previously sent.

   o  When it receives the acknowledgment, it generates a neighbor event
      of Negotiation Done to change its neighbor state to Exchange and
      begin the actual exchange of Database Description packets.

   Note that during the negotiation process, the receipt of an
   inconsistent packet will result in a neighbor event of Seq Number
   Mismatch, terminating the process.  See Section 4.3 for more
   information.

7.2.3 Exchanging Database Description Packets

   Once the neighbor state changes to Exchange, the switches begin the
   exchange of Database Description packets containing link state
   summary data.  The process proceeds as follows:

   1. The master sends a packet containing a list of link state headers.
      If the packet contains only a portion of the unexchanged database
      -- that is, more Database Description packets are to follow -- the
      packet has the M-bit set.  The MS-bit is set and the I-bit is
      clear.

      If the slave does not acknowledge the packet within RxmtInterval
      seconds, the master retransmits the packet.

Top      Up      ToC       Page 47 
   2. When the slave receives a packet, it first checks the sequence
      number to see if the packet is a duplicate.  If so, it simply
      acknowledges the packet by clearing the MS-bit and returning the
      packet to the master.  (Note that the slave acknowledges all
      Database Description packets that it receives, even those that are
      duplicates.)

      Otherwise, the slave processes the packet by doing the following:

      o  For each link state header listed in the packet, the slave
         searches its own link state database to determine whether it
         has an instance of the advertisement.

      o  If the slave does not have an instance of the link state
         advertisement, or if the instance it does have is older than
         the instance listed in the packet, it creates an entry in its
         link state request list in the neighbor data structure.  See
         Section 7.1.1 for a description of how to determine which
         instance of a link state advertisement is the newest.

      o  When the slave has examined all headers, it acknowledges the
         packet by turning the MS-bit off and returning the packet to
         the master.


   3. When the master receives the first acknowledgment for a particular
      Database Description packet, it processes the acknowledgment as
      follows:

      o  For each link state header listed in the packet, the master
         checks to see if the slave has indicated it has an instance of
         the link state advertisement that is newer than the instance
         the master has in its own database.  If so, the master creates
         an entry in its link state request list in the neighbor data
         structure.

      o  The master then increments the sequence number and sends
         another packet containing the next set of link state summary
         information, if any.

      Subsequent acknowledgments for the Database Description packet
      (those with the same sequence number) are discarded.

      When the master sends the last portion of its database summary
      information, it clears the M-bit in the packet to indicate that no
      more packets are to be sent.

Top      Up      ToC       Page 48 
   4. When the slave receives a Database Description packet with the M-
      bit clear, it processes the packet, as described above in step 2.
      After it has completed processing and has acknowledged the packet
      to the master, it generates an Exchange Done neighbor event and
      its neighbor state changes to Loading.

      The database exchange process is now complete for the slave, and
      it begins the process of requesting those link state
      advertisements for which the master has more current instances
      (see Section 7.3).

   5. When the master receives an acknowledgment for the final Database
      Description packet, it processes the acknowledgment as described
      above in step 3.  Then it generates an Exchange Done neighbor
      event and its neighbor state changes to Loading.

      The database exchange process is now complete for the master, and
      it begins the process of requesting those link state
      advertisements for which the slave has more current instances (see
      Section 7.3).

   Note that during this exchange, the receipt of an inconsistent packet
   will result in a neighbor event of Seq Number Mismatch, terminating
   the process.  See Section 4.3 for more information.

7.3 Updating the Database

   When either switch completes the database exchange process and its
   neighbor state changes to Loading, it has a list of link state
   advertisements for which the neighboring switch has a more recent
   instance.  This list is stored in the neighbor data structure as the
   link state request list.

   To complete the synchronization of its database with that of its
   neighbor, the switch must obtain the most current instances of those
   link state advertisements.

   The switch requests these advertisements by sending its neighbor a
   Link State Request packet containing the description of one or more
   link state advertisement, as defined by the advertisement's type,
   link state ID, and advertising switch.  (For a detailed description
   of the Link State Request packet, see Section 10.6.3.)  The switch
   continues to retransmit this packet every RxmtInterval seconds until
   it receives a reply from the neighbor.

Top      Up      ToC       Page 49 
   When the neighbor switch receives the Link State Request packet, it
   responds with a Link State Update packet containing its most current
   instance of each of the requested advertisements.  (Note that the
   neighboring switch can be in any of the Exchange, Loading or Full
   neighbor states when it responds to a Link State Request packet.)

   If the neighbor cannot locate a particular link state advertisement
   in its database, something has gone wrong with the synchronization
   process.  The switch generates a BadLSReq neighbor event and the
   partially formed adjacency is torn down. See Section 4.3 for more
   information.

   Depending on the size of the link state request list, it may take
   more than one Link State Request packet to obtain all the necessary
   advertisements.  Note, however, that there must at most one Link
   State Request packet outstanding at any one time.

7.4 An Example

   Figure 3 shows an example of an adjacency being formed between two
   switches -- S1 and S2 -- connected to a network link.  S2 is the
   designated switch for the link and has a higher switch ID than S1.

   The neighbor state changes that each switch goes through are listed
   on the sides of the figure.

Top      Up      ToC       Page 50 
   +--------+                                     +--------+
   | Switch |                                     | Switch |
   |   S1   |                                     |   S2   |
   +--------+                                     +--------+
      Down                                           Down
                     Hello (DS=0, seen=0)
            ------------------------------------->
                                                     Init
                  Hello (DS=S2, seen=...,S1)
            <-------------------------------------
   ExStart
             DB Description (Seq=x, I, M, Master)
            ------------------------------------->
                                                     ExStart
             DB Description (Seq=y, I, M, Master)
            <-------------------------------------
   xchange
               DB Description (Seq=y, M, Slave)
            ------------------------------------->
                                                     Exchange
             DB Description (Seq=y+1, M, Master)
            <-------------------------------------
              DB Description (Seq=y+1, M, Slave)
            ------------------------------------->
                              .
                              .
                              .

               DB Description (Seq=y+n, Master)
            <-------------------------------------
                DB Description (Seq=y+n, Slave)
            ------------------------------------->
   Loading                                           Full
                       Link State Request
            <-------------------------------------
                       Link State Update
            ------------------------------------->
                              .
                              .
                              .

                       Link State Request
            <-------------------------------------
                       Link State Update
            ------------------------------------->
    Full

         Figure 3: An Example of Bringing Up an Adjacency

Top      Up      ToC       Page 51 
   At the top of Figure 3, S1's interface to the link becomes
   operational, and S1 begins sending Hello packets over the interface.
   At this point, S1 does not yet know the identity of the designated
   switch or of any other neighboring switches.  S2 receives the Hello
   packet from S1 and changes its neighbor state to Init.  In its next
   Hello packet, S2 indicates that it is itself the designated switch
   and that it has received a Hello packet from S1.  S1 receives the
   Hello packet and changes its state to ExStart, starting the process
   of bringing up the adjacency.

   S1 begins by asserting itself as the master.  When it sees that S2 is
   indeed the master (because of S2's higher switch ID), S1 changes to
   slave and adopts S2's sequence number.  Database Description packets
   are then exchanged, with polls coming from the master (S2) and
   acknowledgments from the slave (S1).  This sequence of Database
   Description packets ends when both the poll and associated
   acknowledgment have the M-bit off.

   In this example, it is assumed that S2 has a completely up-to-date
   database and immediately changes to the Full state. S1 will change to
   the Full state after updating its database by sending Link State
   Request packets and receiving Link State Update packets in response.

   Note that in this example, S1 has waited until all Database
   Description packets have been received from S2 before sending any
   Link State Request packets.  However, this need not be the case.  S1
   could interleave the sending of Link State Request packets with the
   reception of Database Description packets.



(page 51 continued on part 3)

Next RFC Part