[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
INTERNET-DRAFT               EXPIRES NOVEMBER 1997      INTERNET-DRAFT
Network Working Group                                        L. Kane
INTERNET-DRAFT                                            K. Dobbins
Category:  Informational                              R. Soczewinski
                                      Cabletron Systems Incorporated
                                                            May 1997



                    VLS Protocol Specification
                    <draft-rfced-info-kane-00.txt>

Status of this Memo

   This document is an Internet-Draft.  Internet-Drafts are working
   documents of the Internet Engineering task Force (IETF), its areas,
   and its working groups.  Note that other groups may also distribute
   working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six
   months and may be updated, replaced, or obsoleted by other
   documents at any time.  It is inappropriate to use Internet-Drafts
   as reference material or to cite them other than as "work in
   progress".

   To learn the current status of any Internet-Draft, please check the
   "1id-abstract.txt" listing contained in the Internet-Drafts Shadow
   Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
   munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
   ftp.isi.edu (US West Coast).


Abstract

   The Virtual LAN Link State Protocol (VLSP) is part of the
   InterSwitch Message Protocol (ISMP).  ISMP was designed to
   facilitate interswitch communication within distributed
   connection-oriented switching networks.  VLSP is used to
   determine and maintain a fully connected mesh topology graph of
   the switch fabric.  Each switch maintains an identical database
   describing the topology.  Call-originating switches use the
   topology database to determine the path over which to route a
   call connection.

   VLSP provides support for equal-cost multipath routing, and
   recalculates routes quickly in the face of topological changes,
   utilizing a minimum of routing protocol traffic.


Table of Contents

   Status of this Memo                                        1
   Abstract                                                   1
   1.  Introduction                                           3
       1.1  Acknowledgments                                   3
       1.2  Data Conventions                                  4
   2.  ISMP Overview                                          4
   3.  General ISMP Packet Format                             5
       3.1  Frame Header                                      5
       3.2  ISMP Packet Header                                6
       3.3  ISMP Message Body                                 7
   4.  VLS Protocol Overview                                  8
       4.1  Definitions of Commonly Used Terms                8
       4.2  Differences Between VLSP and OSPF                10
            4.2.1  Operation at the Physical Layer           10
            4.2.2  All Links Treated as Broadcast            10
            4.2.3  Routing Path Information                  11
            4.2.4  Configurable Parameters                   11
            4.2.5  Features Not Supported                    11


L. Kane, et. al.                                           [Page 1]


I-D                VLS Protocol Specification            May 1997


       4.3  Functional Summary                               12
            4.3.1  Discovery Process                         12
            4.3.2  Synchronizing the Databases               12
            4.3.3  Maintaining the Databases                 12
            4.3.4  Calculating the Routing Table             12
       4.4  Protocol Packets                                 13
       4.5  Protocol Data Structures                         14
       4.6  Basic Implementation Requirements                14
       4.7  Organization of the Remainder of This Document   15
   5.  Interface Data Structure                              15
       5.1  Interface States                                 18
       5.2  Events Causing Interface State Changes           20
       5.3  Interface State Machine                          22
   6.  Neighbor Data Structure                               24
       6.1  Neighbor States                                  26
       6.2  Events Causing Neighbor State Changes            29
       6.3  Neighbor State Machine                           31
   7.  Area Data Structure                                   34
       7.1  Adding and Deleting Link State Advertisements    35
       7.2  Accessing Link State Advertisements              36
   8.  Routing Table                                         36
       8.1  Routing Table Lookup                             37
   9.  Discovery Process                                     38
       9.1  Hello Packets                                    38
       9.2  Bidirectional Communication                      39
       9.3  Designated Switch                                39
            9.3.1  Selecting the Designated Switch           40
       9.4  Adjacencies                                      43
   10. Synchronizing the Databases                           44
       10.1 Link State Advertisements                        44
            10.1.1 Determining Which Link State
                   Advertisement Is Newer                    45
       10.2 Database Exchange Process                        46
            10.2.1 Database Description Packets              46
            10.2.2 Negotiating the Master/Slave Relationship 47
            10.2.3 Exchanging Database Description Packets   48
       10.3 Updating the Database                            50
       10.4 An Example                                       51
   11. Maintaining the Databases                             53
       11.1 Originating Link State Advertisements            53
            11.1.1 Switch Link Advertisements                54
            11.1.2 Network Link Advertisements               57
       11.2 Distributing Link State Advertisements           58
            11.2.1 Overview                                  58
            11.2.2 Processing an Incoming Link State
                   Update Packet                             60
            11.2.3 Forwarding a Link State Update Packet     62
            11.2.4 Installing Link State Advertisements
                   in the Database                           64
            11.2.5 Retransmitting Link State Advertisements  64
            11.2.6 Acknowledging Link State Advertisements   65



L. Kane, et. al.                                           [Page 2]


I/D               VLS Protocol Specification            May 1997


       11.3 Aging the Link State Database                    67
            11.3.1 Premature Aging of Advertisements         68
   12. Calculating the Routing Table                         68
   13. Protocol Packets                                      69
       13.1 Packet Processing                                70
       13.2 Network Layer Address Information                70
       13.3 VLSP Packet Header                               72
       13.4 Options Field                                    74
       13.5 Packet Formats                                   75
            13.5.1 Hello Packets                             75
            13.5.2 Database Description Packets              77
            13.5.3 Link State Request Packets                79
            13.5.4 Link State Update Packets                 80
            13.5.5 Link State Acknowledgment Packets         81
   14. Link State Advertisement Formats                      82
       14.1 Link State Advertisement Headers                 82
       14.2 Switch Link Advertisements                       85
       14.3 Network Link Advertisements                      87
   15. Protocol Parameters                                   88
       15.1 Architectural Constants                          88
       15.2 Configurable Parameters                          89
   Footnotes                                                 91
   References                                                92
   Security Considerations                                   92
   Authors Addresses                                        92


1.  Introduction

   This memo is being distributed to members of the Internet
   community in order to solicit reactions to the proposals
   contained herein.  While the specification discussed here may
   not be directly relevant to the research problems of the
   Internet, it may be of interest to researchers and
   implementers.


1.1  Acknowledgments

   VLSP is derived from the OSPF link-state routing protocol
   described in [RFC1583], written by John Moy, formerly of
   Proteon, Inc., Westborough, Massachusetts.  Much of the current
   RFC has been drawn from [RFC1583].  Therefore, this author
   wishes to acknowledge the contribution Mr. Moy has
   (unknowingly) made to this document.









L. Kane, et. al.                                           [Page 3]


I/D              VLS Protocol Specification            May 1997


1.2  Data Conventions

   The methods used in this memo to describe and picture data
   adhere to the standards of Internet Protocol documentation
   [RFC1700].  In particular:

      The convention in the documentation of Internet
      Protocols is to express numbers in decimal and to
      picture data in "big-endian" order.  That is, fields
      are described left to right, with the most
      significant octet on the left and the least
      significant octet on the right.

      The order of transmission of the header and data
      described in this document is resolved to the octet
      level.  Whenever a diagram shows a group of octets,
      the order of transmission of those octets is the
      normal order in which they are read in English.

      Whenever an octet represents a numeric quantity the
      left most bit in the diagram is the high order or
      most significant bit.  That is, the bit labeled 0 is
      the most significant bit.

      Similarly, whenever a multi-octet field represents a
      numeric quantity the left most bit of the whole field
      is the most significant bit.  When a multi-octet
      quantity is transmitted the most significant octet is
      transmitted first.


2.  ISMP Overview

   The InterSwitch Message Protocol (ISMP) is used for interswitch
   communication within distributed connection-oriented switching
   networks.  ISMP provides the following services:

   -  Topology services.  Each switch maintains a distributed
      topology of the switch fabric by exchanging the following
      interswitch messages with other switches:

      -  Interswitch Keepalive messages (SNDM protocol) are sent by
         each switch to announce its existence to its neighboring
         switches and to establish the topology of the switch
         fabric.

      -  Interswitch Spanning Tree BPDU messages and Interswitch
         Remote Blocking messages (LSMP protocol) are used to
         determine and maintain a loop-free flood path between all
         network switches in the fabric.  This flood path is used
         for all undirected interswitch messages -- that is,
         messages of the ARLD, SBCD, and SFCT protocols.


L. Kane, et. al.                                           [Page 4]


I/D              VLS Protocol Specification            May 1997


      -  Interswitch Link State messages (VLS protocol) are used to
         determine and maintain a fully connected mesh topology
         graph of the switch fabric.  Call-originating switches use
         the topology graph to determine the path over which to
         route a call connection.

   -  Address resolution services.  Interswitch Resolve messages
      (ARLD protocol) are used to resolve a packet destination
      address when the packet source and destination pair does not
      match a known connection.  Interswitch New User messages
      (also part of the ARLD protocol) are used to provide end-
      station address mobility between switches.

   -  Tag-based flooding.  A tag-based broadcast method (SBCD
      protocol) is used to restrict the broadcast of unresolved
      packets to only those ports within the fabric that belong to
      the same VLAN as the source.

   -  Call tapping services.  Interswitch Tap messages (SFCT
      protocol) are used to monitor traffic moving between two end
      stations.  Traffic can be monitored in one or both
      directions along the connection path.


                                 NOTE


            This document describes the VLS protocol.
            Other ISMP protocols are described in other
            RFCs.  See the References section for a
            list of these related RFCs.



3.  General ISMP Packet Format

   ISMP packets are of variable length and have the following
   general structure:

   -  Frame header
   -  ISMP packet header
   -  ISMP message body


3.1  Frame Header

   ISMP packets are encapsulated within an IEEE 802-compliant
   frame using a standard header as shown below:







L. Kane, et. al.                                           [Page 5]


I/D                VLS Protocol Specification            May 1997


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
00 |                                                               |
   +      Destination address      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
04 |                               |                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+        Source address         +
08 |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
12 |             Type              |                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
16 |                                                               |
   +                                                               +
   :                                                               :

   Destination address

      This 6-octet field contains the Media Access Control (MAC)
      address of the multicast channel over which all switches in
      the fabric receive ISMP packets.  The destination address of
      all ISMP packets contain a value of 01-00-1D-00-00-00.

   Source address

      This 6-octet field contains the physical (MAC) address of
      the switch originating the ISMP packet.

   Type

      This 2-octet field identifies the type of data carried
      within the frame.  The type field of ISMP packets contains
      the value 0x81FD.


3.2  ISMP Packet Header

   The ISMP packet header consists of 6 octets, as shown below:


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
00
|///////////////////////////////////////////////////////////////|
   ://////// Frame header /////////////////////////////////////////:
   +//////// (14 octets)  /////////+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
12 |///////////////////////////////|            Version            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
16 |       ISMP message type       |        Sequence number        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
20 |                                                               |
   +                                                               +
   :                                                               :


L. Kane, et. al.                                           [Page 6]


I/D                 VLS Protocol Specification            May 1997


   Frame header

      This 14-octet field contains the frame header.

   Version

      This 2-octet field contains the version number of the
      InterSwitch Message Protocol to which this ISMP packet
      adheres.  This document describes ISMP Version 2.0.

   ISMP message type

      This 2-octet field contains a value indicating which type of
      ISMP message is contained within the message body.  Valid
      values are as follows:

      1    (reserved)
      2    Interswitch Keepalive messages (SNDM protocol)
      3    Interswitch Link State messages (VLS protocol)
      4    Interswitch Spanning Tree BPDU messages and Remote
           Blocking messages (LSMP protocol)
      5    Interswitch Resolve and New User messages (ARLD
           protocol)
      6    (reserved)
      7    Tag-Based Flood messages (SBCD protocol)
      8    Interswitch Tap messages (SFCT protocol)

      VLS protocol messages have a message type of 3.

   Sequence number

      This 2-octet field contains an internally generated sequence
      number used by the various protocol handlers for internal
      synchronization of messages.


3.3  ISMP Message Body

   The ISMP message body is a variable-length field containing the
   actual data of the ISMP message.  The length and content of
   this field are determined by the value found in the message
   type field.












L. Kane, et. al.                                           [Page 7]


I/D               VLS Protocol Specification            May 1997


4.  VLS Protocol Overview

   VLSP is a dynamic routing protocol.  It quickly detects
   topological changes in the switch fabric (such as, switch
   interface failures) and calculates new loop-free routes after a
   period of convergence.  This period of convergence is short and
   involves a minimum of routing traffic.

   All switches in the fabric run the same algorithm and maintain
   identical databases describing the switch fabric topology.
   This database contains each switchs local state, including its
   usable interfaces and reachable neighbors.  Each switch
   distributes its local state throughout the switch fabric by
   flooding.  From the topological database, each switch
   constructs a set of best path trees (using itself as the root)
   that specify routes to all other switches in the fabric.


4.1  Definitions of Commonly Used Terms

   This section contains a collection of definitions for terms
   that have a specific meaning to the protocol and that are used
   throughout the text.

   Switch ID

      A 10-octet value that uniquely identifies the switch within
      the switch fabric.  The value consists of the 6-octet base
      MAC address of the switch, followed by 4 octets of zeroes.

   Network link

      The physical connection between two switches.  A link is
      associated with a switch interface.
      There are two physical types of network links supported by
      VLSP:

      -  Point-to-point links that join a single pair of switches.
         A serial line is an example of a point-to-point network
         link.

      -  Multi-access broadcast links that support the attachment
         of multiple switches, along with the capability to address
         a single message to all the attached switches.  An
         attached ethernet is an example of a multi-access
         broadcast network link.

      A single topology can contain both types of links.  Note,
      however, the current version of VLSP treats all links as if
      they were multi-access.




L. Kane, et. al.                                           [Page 8]


I/D               VLS Protocol Specification            May 1997


   Interface

      The port over which a switch accesses one of its links.
      Interfaces are identified by their interface ID, a 10-octet
      value consisting of the 6-octet base MAC address of the
      switch, followed by the 4-octet local port number of the
      interface.

   Neighboring switches

      Two switches attached to a common link.  Neighbors are
      dynamically discovered by the Hello protocol.

   Adjacency

      A relationship formed between selected neighboring switches
      for the purpose of exchanging routing information.  Not
      every pair of neighboring switches become adjacent.

   Link state advertisement

      Describes the local state of a switch or a link.  Each link
      state advertisement is flooded throughout the switch fabric.
      The collected link state advertisements of all switches and
      links form the protocol's topological database.

   Hello protocol

      That part of VLSP used to establish and maintain neighbor
      relationships.

   Designated switch

      Each multi-access network link has a designated switch.  The
      designated switch generates a link state advertisement for
      the link and has other special responsibilities in the
      running of the protocol.

      The use of a designated switch permits a reduction in the
      number of adjacencies required on multi-access links.  This
      in turn reduces the amount of routing protocol traffic and
      the size of the topological database.

      The designated switch is elected by the Hello protocol.  A
      designated switch is not selected for a point-to-point
      network link.

   Backup designated switch

      Each multi-access network link has a backup designated
      switch.  The backup designated switch maintains adjacencies
      with the same switches on the link as the designated switch.


L. Kane, et. al.                                           [Page 9]


I/D                VLS Protocol Specification            May 1997


      This optimizes the failover time when the backup designated
      switch must take over for the (failed) designated switch.

      The backup designated switch is elected by the Hello
      protocol.  A backup designated switch is not selected for a
      point-to-point network link.


4.2  Differences Between VLSP and OSPF

   The VLS protocol is derived from the OSPF link-state routing
   protocol described in [RFC1583].


4.2.1  Operation at the Physical Layer

   The primary differences between the VLS and OSPF protocols stem
   from the fact that OSPF runs over the IP layer, while VLSP runs
   at the physical MAC layer.  This difference has the following
   repercussions:

   -  VLSP does not support features (such as fragmentation) that
      are typically provided by network layer service providers.

   -  Due to the unrelated nature of MAC address assignments, VLSP
      provides no summarization of the address space (such as,
      classical IP subnet information) or level 2 routing (such
      as, IS-IS Phase V DECnet).  Thus, VLSP does not support
      grouping switches into areas.  All switches exist in a
      single area.  Since a single domain exists within any switch
      fabric, there is no need for VLSP to provide interdomain
      reachability.

   -  As mentioned in Section 3.1, ISMP uses a single well-known
      multicast address for all packets.  However, parts of the
      VLS protocol (as derived from OSPF) are dependent on certain
      network layer addresses -- in particular, the AllSPFSwitches
      and AllDSwitches multicast addresses that drive the
      distribution of link state advertisements throughout the
      switch fabric.  In order to facilitate the implementation of
      the protocol at the physical MAC layer, network layer
      address information is encapsulated in the protocol packets
      (see Section 13.2).  This information is unbundled and
      packets are then processed as if they had been sent or
      received on that multicast address.


4.2.2  All Links Treated as Broadcast

   The current version of VLSP treats all network links as multi-
   access broadcast media, regardless of whether the link is
   actually point-to-point or multi-access.


L. Kane, et. al.                                           [Page 10]


I/D                 VLS Protocol Specification            May 1997


4.2.3  Routing Path Information

   Instead of providing the next hop to a destination, VLSP
   calculates and maintains complete end-to-end path information.
   On request, a list of individual port identifiers is generated
   describing a complete path from the source switch to the
   destination switch.  If multiple equal-cost routes exist to a
   destination switch, up to three paths are calculated and
   returned.


4.2.4  Configurable Parameters

   OSPF supports (and requires) configurable parameters.  In fact,
   even the default OSPF configuration requires that IP address
   assignments be specified.  On the other hand, no configuration
   information is ever required for the VLS protocol.  Switches
   are uniquely identified by their base MAC addresses and ports
   are uniquely identified by the base MAC address of the switch
   and a port number.

   While a developer is free to implement configurable parameters
   for the VLS protocol, the current version of VLSP supports
   configurable path metrics only.  Note that this has the
   following repercussions:

   -  All switches have a switch priority of 1.  This forces the
      selection of the designated switch to be based solely on
      base MAC address.

   -  Authentication is not supported.


4.2.5  Features Not supported

   In addition to those features mentioned in the previous
   sections, the following OSPF features are not supported by the
   current version of VLSP:

   -  Periodic refresh of link state advertisements.  (This
      optimizes performance by eliminating unnecessary traffic
      between the switches.)

   -  Routing based on non-zero type of service (TOS).

   -  Use of external routing information for destinations outside
      the switch fabric.







L. Kane, et. al.                                           [Page 11]


I/D                 VLS Protocol Specification            May 1997


4.3  Functional Summary

   There are essentially four operational stages of the VLS
   protocol.


4.3.1  Discovery Process

   When a switch comes on-line, it initializes its routing data
   structures.  It then waits for notification from the SNDM
   protocol [RFCxxxx] that its interfaces are functional.

   Once the switch learns that its interfaces are functional, it
   uses the Hello protocol to dynamically discover its neighbors
   by sending Hello packets over its outports and receiving Hello
   packets back in return.  The Hello protocol is also used to
   select a designated switch for each multi-access network link.
   The designated switch on each link determines which switches
   will become adjacent.


4.3.2  Synchronizing the Databases

   Adjacencies are used to simplify and speed up the process of
   synchronizing the topological database (also known as the link
   state database) maintained by each switch in the fabric.  Each
   switch is only required to synchronize its database with those
   neighbors to which it is adjacent.  This reduces the amount of
   routing protocol traffic across the fabric, particularly for
   multi-access links with multiple switches.


4.3.3  Maintaining the Databases

   Each switch advertises its state (also known as its link state)
   any time its link state changes.  Link state advertisements are
   distributed throughout the switch fabric using a reliable
   flooding algorithm that ensures that all switches in the fabric
   are notified of any link state changes.


4.3.4  Calculating the Routing Table

   The link state database consists of the collection of link
   state advertisements received from each switch.  Each switch
   uses its link state database to calculate a set of best paths,
   using itself as root, to all other switches in the fabric.







L. Kane, et. al.                                           [Page 12]


I/D                 VLS Protocol Specification            May 1997


4.4  Protocol Packets

   In addition to the frame header and the ISMP packet header
   described in Section 3, all VLS protocol packets share a common
   protocol header, described in Section 13.3.

   The VLSP packet types are listed below in Table 1.  Their
   formats are described in Section 13.5.


     Type    Packet Name              Protocol Function

     1       Hello                    Discover/maintain neighbors
     2       Database Description     Summarize database contents
     3       Link State Request       Database download
     4       Link State Update        Database update
     5       Link State Ack           Flooding acknowledgment

                     Table 1: VLSP Packet Types


   The Hello packets are used to discover and maintain neighbor
   relationships.  The Database Description and Link State Request
   packets are used to form  adjacencies.  Link State Update and
   Link State Acknowledgment packets are used to update the
   topological database.

   Each Link State Update packet carries a set of link state
   advertisements.  A single Link State Update packet may contain
   the link state advertisements of several switches.  There are
   two different types of link state advertisement, as shown below
   in Table 2.


     LS    Advertisement    Advertisement Description
     Type  Name

     1     Switch link      Originated by all switches. This
           advertisements   advertisement describes the collected
                            states of the switch's interfaces.

     2     Network link     Originated by the designated switch.
           advertisements   This advertisement contains the list of
                            switches connected to the network link.

             Table 2: VLSP Link State Advertisements








L. Kane, et. al.                                           [Page 13]


I/D                  VLS Protocol Specification            May 1997


4.5  Protocol Data Structures

   The VLS protocol is described in this specification in terms of
   its operation on various protocol data structures.  Table 3
   lists the primary VLSP data structures, along with the section
   in which they are described in detail.


          Structure Name                        Description

          Interface Data Structure              Section 5
          Neighbor Data Structure               Section 6
          Area Data Structure                   Section 7
          Routing Table                         Section 8

                    Table 3: VLSP Data Structures


4.6  Basic Implementation Requirements

   An implementation of the VLS protocol requires the following
   pieces of system support:

   Timers

      Two types of timer are required.  The first type, known as a
      one-shot timer, expires once and triggers an event.  The
      second type, known as an interval timer, expires at preset
      intervals.  Interval timers are used to trigger events at
      periodic intervals. The granularity of both types of timers
      is one second.

      Interval timers should be implemented in such a way as to
      avoid drift.  In some switch implementations, packet
      processing can affect timer execution.  For example, on a
      multi-access link with multiple switches, regular broadcasts
      can lead to undesirable synchronization of routing packets
      unless the interval timers have been implemented to avoid
      drift.  If it is not possible to implement drift-free
      timers, small random amounts of time should be added to or
      subtracted from the timer interval at each firing.

   List manipulation primitives

      Much of the functionality of VLSP is described here in terms
      of its operation on lists of link state advertisements.  Any
      particular advertisement may be on many such lists.
      Implementation of VLSP must be able to manipulate these
      lists, adding and deleting constituent advertisements as
      necessary.




L. Kane, et. al.                                           [Page 14]


I/D                VLS Protocol Specification            May 1997


   Tasking support

      Certain procedures described in this specification invoke
      other procedures.  At times, these other procedures should
      be executed in-line -- that is, before the current procedure
      has finished.  This is indicated in the text by instructions
      to "execute" a procedure.  At other times, the other
      procedures are to be executed only when the current
      procedure has finished.  This is indicated by instructions
      to "schedule" a task.  Implementation of VLSP must provide
      these two types of tasking support.


4.7  Organization of the Remainder of This Document

   The remainder of this document is organized as follows:

   -  Section 5 through Section 8 describe the primary data
      structures used by the protocol.  Note that this
      specification is presented in terms of these data structures
      in order to make explanations more precise.  Implementations
      of the protocol must support the functionality described,
      but need not use the exact data structures that appear in
      this specification.

   -  Section 9 through Section 12 describe the four operational
      stages of the protocol:  the discovery process,
      synchronizing the databases, maintaining the databases, and
      calculating the routing table.

   -  Section 13 describes the processing of VLSP packets and
      presents detailed descriptions of their formats.

   -  Section 14 presents detailed descriptions of link state
      advertisements.

   -  Section 15 summarizes the protocol parameters.


5.  Interface Data Structure

   The port over which a switch accesses a network link is known
   as the link interface.  Each switch maintains a separate
   interface data structure for each network link.

   The following data items are associated with each interface:

   Type

      The type of network to which the interface is attached --
      point-to-point or broadcast (multi-access).  Note that the
      current version of VLSP treats all links as broadcast media.


L. Kane, et. al.                                           [Page 15]


I/D                VLS Protocol Specification            May 1997


   State

      The functional level of the interface.  The state of the
      interface is included in all switch link advertisements
      generated by the switch, and is also used to determine
      whether full adjacencies are allowed on the interface.  See
      Section 5.1 for a complete description of interface states.

   Interface identifier

      A 10-octet value that uniquely identifies the interface.
      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.

   Area ID

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

   HelloInterval

      The interval, in seconds, at which the switch sends Hello
      packets over the interface.

   SwitchDeadInterval

      The length of time, in seconds, that neighboring switches
      will wait before declaring the local switch down once they
      stop receiving Hello packets from the local switch.

   InfTransDelay

      The estimated number of seconds it should take to transmit a
      Link State Update packet over this interface.  Link state
      advertisements contained in the update packet will have
      their age incremented by this amount before transmission.
      This value must be greater than zero and must take into
      account transmission and propagation delays.

   Switch priority

      An 8-bit unsigned integer.  When two switches attached to
      the same network link contend for selection as the
      designated switch, the switch with the highest priority
      takes precedence.  If both switches have the same priority,
      the switch with the highest base MAC address becomes the
      designated switch.  A switch whose switch priority is set to
      zero is ineligible to become the designated switch on the
      attached link.




L. Kane, et. al.                                           [Page 16]


I/D                 VLS Protocol Specification            May 1997


   Hello timer

      The interval timer used to regulate the transmission of
      Hello packets over the interface.  This timer expires every
      HelloInterval seconds.

   Wait timer

      The one-shot timer used to time the Waiting state.  When
      this timer expires, the interface exits the Waiting state
      and begins selection of the designated switch on the link.
      The length of the timer is switchDeadInterval seconds.

   Neighboring switches

      A list of the neighboring switches attached to this network
      link.  This list is created by the Hello protocol.
      Adjacencies are formed to one or more of these neighbors.
      The set of adjacent neighbors can be determined by examining
      the states of the neighboring switches as shown in their
      link state advertisements.

   Designated switch

      The designated switch selected for the multi-access network
      link.  (A designated switch is not selected for a point-to-
      point link.)  This data item is initialized to zero when the
      switch comes on-line, indicating that no designated switch
      has been chosen for the link.

   Backup designated switch

      The backup designated switch selected for the multi-access
      network link.  (A backup designated switch is not selected
      for a point-to-point link.)  This data item is initialized
      to zero when the switch comes on-line, indicating that no
      backup designated switch has been chosen for the link.

   Interface output cost(s)

      The cost of sending a packet over the interface.  The link
      cost is expressed in the link state metric and must be
      greater than zero.

   RxmtInterval

      The number of seconds between link state advertisement
      retransmissions, for adjacencies belonging to this
      interface.  This value is also used to time the
      retransmission of Database Description and Link State
      Request packets.



L. Kane, et. al.                                           [Page 17]


I/D                 VLS Protocol Specification            May 1997


5.1  Interface States

   This section describes the various states of a switch
   interface.  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 interface passes before attaining the final, fully
   functional state.  The specification makes use of this ordering
   by references such as "those interfaces in state greater than
   X".

   Figure 1 represents the interface state machine, showing the
   progression of interface state changes.  The arrows on the
   graph represent the events causing each state change.  These
   events are described in Section 5.2.  The interface state
   machine is described in detail in Section 5.3.

   Down

      This is the initial state of the interface.  In this state,
      the SNDM protocol [RFCxxxx] has indicated that the interface
      is unusable, and no protocol traffic is sent or received on
      the interface.  In this state, interface parameters are set
      to their initial values, all interface timers are disabled,
      and no adjacencies are associated with the interface.

   Loopback

      In this state, the switch interface is looped back, either
      in hardware or in software.  The interface is unavailable
      for regular data traffic.

   Waiting

      In this state, the switch is attempting to identify the
      backup designated switch for the link by monitoring the
      Hello packets it receives.  The switch does not attempt to
      select a designated switch or a backup designated switch
      until it changes out of this state, thereby preventing
      unnecessary changes of the designated switch and its backup.

   Point-to-Point

      In this state, the interface is operational and is connected
      to a physical point-to-point link.  On entering this state,
      the switch attempts to form an adjacency with the
      neighboring switch.







L. Kane, et. al.                                           [Page 18]


I/D                 VLS Protocol Specification            May 1997


                                 Note

               In the current version of VLSP, network
               links are always considered to be multi-
               access, regardless of the physical nature
               of the link, and this state is not used.




      +-------+  Interface   +----------+  Unloop Ind  +----------+
      |  any  | -----------> |   Down   | <----------- | Loopback |
      | state |    Down      +----------+              +----------+
      +-------+                   |                         ^
                                  | Interface Up            |
        +----------------+        |                         |
        | Point-to-Point | <------+                Loop Ind |
        +----------------+        |                         |
                                  V                         |
                            +-----------+               +-------+
                            |  Waiting  |               |  any  |
                            +-----------+               | state |
                                  |                     +-------+
                      Backup Seen |
                                  | Wait Timer
                                  |
                                  |
     +----------+    Neighbor     V     Neighbor    +----------+
     |    DS    | <------------> [ ] <------------> | DS Other |
     +----------+     Change      ^      Change     +----------+
                                  |
                                  |
                  Neighbor Change |
                                  |
                                  V
                             +----------+
                             |  Backup  |
                             +----------+


                   Figure 1: Interface State Machine



   DS Other

      In this state, the interface is operational and is connected
      to a link on which other switches have been selected as the
      designated switch and the backup designated switch.   On
      entering this state, the switch attempts to form adjacencies
      with both the designated switch and the backup designated
      switch.


L. Kane, et. al.                                           [Page 19]


I/D                  VLS Protocol Specification            May 1997


   Backup

      In this state, the switch itself is the backup designated
      switch on the attached link.  It will be promoted to
      designated switch if the current designated switch fails.
      The switch establishes adjacencies with all other switches
      attached to the link.  (See Section 9.3 for more information
      on the functions performed by the backup designated switch.)

   DS

      In this state, this switch itself is the designated switch
      on the attached link.  The switch establishes adjacencies
      with all other switches attached to the link.  The switch is
      responsible for originating network link advertisements for
      the link, containing link information for all switches
      attached to the link, including the designated switch
      itself.   (See Section 9.3 for more information on the
      functions performed by the designated switch.)


5.2  Events Causing Interface State Changes

   The state of an interface changes due to an interface event.
   This section describes these events.

   Interface events are shown as arrows in Figure 1, the graphic
   representation of the interface state machine.  For more
   information on the interface state machine, see Section 5.3.

   Interface Up

      This event is generated by the SNDM protocol [RFCxxxx] and
      indicates that the interface is now operational.  This event
      causes the interface to change out of the Down state.

   Wait Timer

      This event is generated when the one-shot Wait timer
      expires, triggering the end of the required waiting period
      before the switch can begin the process of selecting a
      designated switch and a backup designated switch.

   Backup Seen

      This event is generated when the switch has detected the
      existence or non-existence of a backup designated switch for
      the link, as determined in one of the following two ways:

      -  A Hello packet has been received from a neighbor that
         claims to be the backup designated switch.



L. Kane, et. al.                                           [Page 20]


I/D                 VLS Protocol Specification            May 1997


      -  A Hello packet has been received from a neighbor that
         claims to be the designated switch.  In addition, the
         packet indicated that there is no backup.

      In either case, the interface must have bidirectional
      communication with its neighbor -- that is, the local switch
      must be listed in the neighbor's Hello packet.

      This event signals the end of the Waiting state.

   Neighbor change

      This event is generated when there has been one of the
      following changes in the set of bidirectional neighbors
      associated with the interface.  (See Section 6.1 for
      information on neighbor states.)

      -  Bidirectional communication has been established with a
         neighbor -- the state of the neighbor has changed to 2-Way
         or higher.

      -  Bidirectional communication with a neighbor has been lost
         --  the state of the neighbor has changed to Init or
         lower.

      -  A bidirectional neighbor has just declaring itself to be
         either the designated switch or the backup designated
         switch, as detected by examination of that neighbor's
         Hello packets.

      -  A bidirectional neighbor is no longer declaring itself to
         be either the designated switch or the backup designated
         switch, as detected by examination of that neighbor's
         Hello packets.

      -  The advertised switch priority of a bidirectional neighbor
         has changed, as detected by examination of that neighbor's
         Hello packets.

      When this event occurs, the designated switch and the backup
      designated switch must be reselected.

   Loop Ind

      This event is generated when an interface enters the
      Loopback state.  This event can be generated by either the
      network management service or by the lower-level protocols.







L. Kane, et. al.                                           [Page 21]


I/D                 VLS Protocol Specification            May 1997


   Unloop Ind

      This event is generated when an interface leaves the
      Loopback state.  This event can be generated by either the
      network management service or by the lower-level protocols.

   Interface Down

      This event is generated by the SNDM protocol [RFCxxxx] and
      indicates that the interface is no longer functional.  This
      event forces the interface state to Down.


5.3  Interface State Machine

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

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

   Note that when the state of an interface changes, it may be
   necessary to originate a new switch link advertisement.  See
   Section 11.1 for more information.

   Some of the processing described here includes generating
   events for the neighbor state machine.  For example, when an
   interface becomes inoperative, all neighbor connections
   associated with the interface must be destroyed.  For more
   information on the neighbor state machine, see Section 6.3.

   State(s):  Down
   Event:  Interface Up
   New state:  Depends on action routine
   Action:
      Start the Hello interval timer, enabling the periodic
      sending of Hello packets over the interface.  If the
      interface is attached to a physical point-to-point link, the
      interface state is set to Point-to-Point.  Otherwise, the
      attached link is a multi-access link.  If the switch is not
      eligible to become the designated switch, the interface
      state changes to DS Other.  Otherwise, the interface state
      is set to Waiting and the one-shot wait timer is started.





L. Kane, et. al.                                           [Page 22]


I/D                  VLS Protocol Specification            May 1997


                                Note

               In the current version of VLSP, network
               links are always considered to be multi-
               access, regardless of the physical nature
               of the link.


   State(s):  Waiting
   Event:  Backup Seen
   New state:  Depends on action routine
   Action:
      Select the designated switch and backup designated switch
      for the attached link, as described in Section 9.3.1.  As a
      result of this selection, the new state of the interface
      will be either DS Other, Backup or DS.

   State(s):  Waiting
   Event:  Wait Timer
   New state:  Depends on action routine
   Action:
      Select the designated switch and backup designated switch
      for the attached link, as described in Section 9.3.1.  As a
      result of this selection, the new state of the interface
      will be either DS Other, Backup or DS.

   State(s):  DS Other, Backup or DS
   Event:  Neighbor Change
   New state:  Depends on action routine
   Action:
      Reselect the designated switch and backup designated switch
      for the attached link, as described in Section 9.3.1.  As a
      result of this selection, the new state of the interface
      will be either DS Other, Backup or DS.

   State(s):  Any State
   Event:  Interface Down
   New state:  Down
   Action:
      All variables in the interface data structure are reset and
      all timers are disabled.  In addition, all neighbor
      connections associated with the interface are destroyed by
      generating the KillNbr event on all neighbors listed in the
      interface data structure.

   State(s):  Any State
   Event:  Loop Ind
   New state:  Loopback
   Action:
      All variables in the interface data structure are reset and
      all timers are disabled.  In addition, all neighbor
      connections associated with the interface are destroyed by


L. Kane, et. al.                                           [Page 23]


I/D                 VLS Protocol Specification            May 1997


      generating the KillNbr event on all neighbors listed in the
      interface data structure.

   State(s):  Loopback
   Event:  Unloop Ind
   New state:  Down
   Action:
      No action is necessary beyond changing the interface state
      to Down because the interface was reset on entering the
      Loopback state.


6.  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 6.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
      neighbor.  The length of the timer is SwitchDeadInterval
      seconds, as contained in the neighbors Hello packet.

   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 10.2).  The master/slave relationship is negotiated
      when the conversation changes to the ExStart state.






L. Kane, et. al.                                           [Page 24]


I/D                  VLS Protocol Specification            May 1997


   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 10.2 for more information on the database
      exchange process.

   Neighbor ID

      The switch ID of the neighboring switch, as contained in the
      neighbors 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 link.

   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 neighbors idea of the
      designated switch, as contained in the neighbors 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 neighbors idea of the backup
      designated switch, as contained in the neighbors 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


L. Kane, et. al.                                           [Page 25]


I/D                  VLS Protocol Specification            May 1997


      retransmitting link state advertisements, see Section
      11.2.5.)

   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
      10.)

   Link state request list

      The list of link state advertisements that must be received
      in order to synchronize with the neighbor switchs 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
      10.)


6.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 6.2.  The neighbor state
      machine is described in detail in Section 6.3.

   Down

      This is the initial state of a neighbor conversation.  In
      this state, there has been no recent information received
      from the neighbor.










L. Kane, et. al.                                           [Page 26]


I/D                  VLS Protocol Specification            May 1997


       +----------+     KillNbr, LLDown,   +-----------+
       |   Down   | <--------------------- | any state |
       +----------+   or Inactivity Timer  +-----------+
            |
 Hello Rcvd |
            |
            V
       +----------+   1-Way   +----------+
       |   Init   | <-------- | >= 2-way |
       +----------+           +----------+
            |
            |
 2-Way Rcvd |                  +-------+   AdjOK?/no  +------------+
            +----------------> | 2-Way | <----------- | >= ExStart |
            | (no adjacency)   +-------+              +------------+
            |
            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



   Init

      In this state, a Hello packet has been received from the
      neighbor.  However, bidirectional communication has not yet
      been established with the neighbor -- that is, the local
      switch has not yet appeared in the neighbor's Hello packets.
      All neighbors in this state (or higher) are listed in the
      Hello packets sent by the local switch over the associated
      interface.



L. Kane, et. al.                                           [Page 27]


I/D                 VLS Protocol Specification            May 1997


   2-Way

      In this state, communication between the two switches is
      bidirectional -- that is, the local switch has seen its own
      switch ID listed in the neighbor switchs Hello packets.
      This is the most advanced state short of beginning to
      establish an adjacency.  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 10.2 for a complete
      description of this process.)  All adjacencies in the
      Exchange state or greater are used by the distribution
      procedure (see Section 11.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.















L. Kane, et. al.                                           [Page 28]


I/D                 VLS Protocol Specification            May 1997


6.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 6.3.


   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 neighbors 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 10.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
      10.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 10.3.)





L. Kane, et. al.                                           [Page 29]


I/D                VLS Protocol Specification            May 1997


   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.

   Seq Number Mismatch

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

      -  The packet contains an unexpected sequence number.
      -  The packet (unexpectedly) has the Init bit set.
      -  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.

   LLDown

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












L. Kane, et. al.                                           [Page 30]


I/D                 VLS Protocol Specification            May 1997


6.3  Neighbor State Machine

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

   Neighbor states (see Section 6.1) change as the result of
   various events (see Section 6.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.

   Note that when the neighbor state changes as a result of an
   interface Neighbor Change event (see Section 5.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
   11.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:  Init
   Action:
      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:
      Reset the inactivity timer for the neighbor.

   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 9.4).  If no adjacency is to be
      formed, the neighbor state changes to 2-Way.

      Otherwise, the neighbor state changes to ExStart.  The
      switch initializes the sequence number for this neighbor.


L. Kane, et. al.                                           [Page 31]


I/D                 VLS Protocol Specification            May 1997


      It then declares itself master for the database exchange
      process.  (See Section 10.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 10.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, the
      neighbor state changes to Full.  This is the adjacency's
      final state.

      Otherwise, the neighbor state changes to Loading.  The
      switch begins sending Link State Request packets to the
      neighbor requesting the most recent link state
      advertisements, as discovered during the database exchange
      process.  (See Section 10.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.

   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 9.4), the neighbor state remains at 2-Way.
      Otherwise, the neighbor state changes to ExStart.  The
      switch initializes the sequence number for this neighbor.
      It then declares itself master for the database exchange
      process.  (See Section 10.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 9.4), no state change and no further
      action is necessary.


L. Kane, et. al.                                           [Page 32]


I/D                 VLS Protocol Specification            May 1997


      Otherwise, the (possibly partially formed) adjacency is torn
      down.  The link state retransmission list, database summary
      list and link state request list are cleared of link state
      advertisements.  The neighbor state changes to 2-Way.

   State(s):  Exchange or greater
   Event:  Seq Number Mismatch
   New state:  ExStart
   Action:
      The (possibly partially formed) adjacency is torn down.  The
      link state retransmission list, database summary list and
      link state request list are cleared of link state
      advertisements.  The neighbor state then changes to ExStart
      and another attempt is made to establish the adjacency.

   State(s):  Exchange or greater
   Event:  BadLSReq
   New state:  ExStart
   Action:
      The (possibly partially formed) adjacency is torn down.  The
      link state retransmission list, database summary list and
      link state request list are cleared of link state
      advertisements.  The neighbor state then changes to ExStart
      and another attempt is made to establish the adjacency.

   State(s):  Any state
   Event:  KillNbr
   New state:  Down
   Action:
      The neighbor conversation is terminated.  The inactivity
      timer is disabled, and the link state retransmission list,
      database summary list and link state request list are
      cleared of link state advertisements.

   State(s):  Any state
   Event:  LLDown
   New state:  Down
   Action:
      The neighbor conversation is terminated.  The inactivity
      timer is disabled, and the link state retransmission list,
      database summary list and link state request list are
      cleared of link state advertisements.

   State(s):  Any state
   Event:  Inactivity Timer
   New state:  Down
   Action:
      The neighbor conversation is terminated.  The inactivity
      timer is disabled, and the link state retransmission list,
      database summary list and link state request list are
      cleared of link state advertisements.



L. Kane, et. al.                                           [Page 33]


I/D                 VLS Protocol Specification            May 1997


   State(s):  2-Way or greater
   Event:  1-Way Received
   New state:  Init
   Action:
      The adjacency between the switches, if any, is torn down.
      The link state retransmission list, database summary list
      and link state request list are cleared of link state
      advertisements.

   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.


7.  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:

   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 switchs interfaces.


L. Kane, et. al.                                           [Page 34]


I/D                 VLS Protocol Specification            May 1997


      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]


7.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:

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

   -  When the switch itself generates a link state advertisement

   (See Section 11.2.4 for information on installing link state
   advertisements.)

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

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

   -  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.









L. Kane, et. al.                                           [Page 35]


I/D                 VLS Protocol Specification            May 1997


7.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
   routing table.  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.


8.  Routing Table

   The routing table contains all the information necessary to
   forward a data packet toward its destination.  There is a
   single routing table in each switch.  Each routing table entry
   describes the collection of best paths to a particular
   destination switch, using the local switch as the start of the
   path.

   Each entry in the routing table contains the following data
   items:

   Destination ID

      The interface ID of the destination switch, as known by its
      adjacent designated switch.  That is, the value here
      consists of the 6-octet base MAC address of the destination
      switch, followed by the 4-octet port number of the
      interface, local to the designated switch of the network
      link.

   Destination type

      The type of the destination switch.  The value here is
      always Network.

   Type of service

      The type of service (TOS) of the paths.  Note that since the
      current version of VLSP does not support routing based on
      non-zero TOS, the value here is always zero.

   Area ID

      The 4-octet identifier of the area.  Since VLSP does not
      support multiple areas, the value here is always zero.






L. Kane, et. al.                                           [Page 36]


I/D                  VLS Protocol Specification            May 1997


   Cost metric

      The link state cost of the path(s), calculated as the sum of
      the costs of a path's constituent links.  Note that even
      when multiple paths to the destination are calculated, there
      is only one path cost because, by definition, such multiple
      paths are of equal cost.

   Link state ID

      The link state identifier of the network link advertisement
      that references the destination switch.  This value consists
      of the interface ID of the network link, as known by the
      designated switch of the link.

   Advertising switch

      The switch ID of the designated switch that originated the
      network link advertisement specified by the link state ID
      data item.

   Next hop(s)

      The interface ID(s) of the local outgoing interface(s) over
      which to forward traffic to the destination switch.  When
      multiple paths of equal cost exist to the destination
      switch, their initial hops are all stored here.  End-to-end
      path information for all equal-cost paths are stored in the
      area data structure (see Section 7).


8.1  Routing Table 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.













L. Kane, et. al.                                           [Page 37]


I/D                 VLS Protocol Specification            May 1997


9.  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:

   -  Neighboring switches are discovered through the exchange of
      Hello packets over each functioning interface.

   -  Bidirectional communication is established with each
      neighbor switch.

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

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

   The following subsections describe each of these steps in
   detail.


9.1  Hello Packets

   Each functioning switch in the fabric periodically sends a
   Hello packet out each of its functioning switch interfaces.
   Each Hello packet contains the following data used during the
   discovery process:

   -  The switch ID and priority of the sending switch

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

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

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

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

   When a switch receives a Hello packet, 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


L. Kane, et. al.                                           [Page 38]


I/D                  VLS Protocol Specification            May 1997


   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 5.3.  For a detailed description of the neighbor state
   machine, see Section 6.3.


9.2  Bidirectional Communication

   When a switch sees its own switch ID listed in a Hello packet
   received from one of its neighbors, bidirectional communication
   has been established with that neighbor.  A neighbor 2-Way
   Received 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, before that decision can
   be made, a designated switch and a backup designated switch
   must be selected for the link, if the link is a multi-access
   link.  The next section contains a description of the
   designated switch, the backup designated switch, and the
   selection process.


9.3  Designated Switch

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

   -  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 14.3.

   -  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 10.

   Each multi-access network link also has a backup designated
   switch.  The primary function of the backup designated switch


L. Kane, et. al.                                           [Page 39]


I/D                  VLS Protocol Specification            May 1997


   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.


                               Note

             Point-to-point network links have neither a
             designated switch or a backup designated
             switch.  However, in the current version of
             VLSP, network links are always treated as
             multi-access, regardless of the physical
             nature of the link.  Therefore, all network
             links have both a designated switch and a
             backup designated switch.


9.3.1  Selecting the Designated Switch

   When a 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:

   -  The Wait timer expires.

   -  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


L. Kane, et. al.                                           [Page 40]


I/D                 VLS Protocol Specification            May 1997


   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:

      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.




L. Kane, et. al.                                           [Page 41]


I/D                  VLS Protocol Specification            May 1997


      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:

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

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

      -  Otherwise, set the interface state to DS Other.

   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.









L. Kane, et. al.                                           [Page 42]


I/D                  VLS Protocol Specification            May 1997


9.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 have multiple adjacencies
   between them.

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

   -  When bidirectional communication is initially established
      with the neighbor

   -  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:

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

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

      -  The local switch itself is the designated switch.

      -  The local switch itself is the backup designated switch.

      -  The neighboring switch is the designated switch.

      -  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.












L. Kane, et. al.                                           [Page 43]


I/D                 VLS Protocol Specification            May 1997


10.  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]


10.1  Link State Advertisements

   Link state advertisements form the core of the database from
   which a switch builds its routing table and 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:






L. Kane, et. al.                                           [Page 44]


I/D                  VLS Protocol Specification            May 1997


   -  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.

   -  The link state ID, defined as follows:

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

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

   -  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
   10.1.1 for a description of how to determine which instance of
   a link state advertisement is the most current.)

   -  The link state sequence number

   -  The link state age, stored in seconds

   -  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 14 for
   a detailed description of the link state header, as well as the
   format of a switch link or network link advertisement.


10.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:

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

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




L. Kane, et. al.                                           [Page 45]


I/D                  VLS Protocol Specification            May 1997


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

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

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

      -  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]

      -  Else, the two instances are considered identical.


10.2  Database Exchange Process

   There are two stages to the database exchange process:

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

   In both these stages, the neighboring switches exchange
   Database Description packets.


10.2.1  Database Description Packets

   Database Description packets are used to describe a switchs
   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
   switchs database.   (See Section 14.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:

   -  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.

   -  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.


L. Kane, et. al.                                           [Page 46]


I/D                 VLS Protocol Specification            May 1997


   -  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.

   -  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 13.5.2 for a more detailed description of a
   Database Description packet.


10.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.

   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:

   -  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 masters sequence number and has
      the MS-bit and the I-bit cleared.






L. Kane, et. al.                                           [Page 47]


I/D                  VLS Protocol Specification            May 1997


      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.

   -  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.

      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 6.3 for
   more information.


10.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.

   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:

      -  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.




L. Kane, et. al.                                           [Page 48]


I/D                 VLS Protocol Specification            May 1997


      -  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 10.1.1 for a description of how to
         determine which instance of a link state advertisement is
         the newest.

      -  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:

      -  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.

      -  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.

   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 10.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.



L. Kane, et. al.                                           [Page 49]


I/D                  VLS Protocol Specification            May 1997


      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 10.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 6.3 for more information.


10.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
   advertisements type, link state ID, and advertising switch.
   (For a detailed description of the Link State Request packet,
   see Section 13.5.3.)  The switch continues to retransmit this
   packet every RxmtInterval seconds until it receives a reply
   from the neighbor.

   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 6.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.






L. Kane, et. al.                                           [Page 50]


I/D                  VLS Protocol Specification            May 1997


10.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.

   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.














L. Kane, et. al.                                           [Page 51]


I/D                 VLS Protocol Specification            May 1997


       +--------+                                     +--------+
       | 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)
                <-------------------------------------
      Exchange
                   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


L. Kane, et. al.                                           [Page 52]


I/D                  VLS Protocol Specification            May 1997


11.  Maintaining the Databases

   Each switch advertises its state (also known as its link state)
   by originating switch link advertisements.  In addition, the
   designated switch on each network link advertises the state of
   the link by originating network link advertisements.

   As described in Section 10.1, link state advertisements are
   uniquely identified by their type, link state ID, and
   advertising switch.

   Link state advertisements are distributed throughout the switch
   fabric using a reliable flooding algorithm that ensures that
   all switches in the fabric are notified of any link state
   changes.


11.1  Originating Link State Advertisements

   A new instance of each link state advertisement is originated
   any time the state of the switch or link changes.  When a new
   instance of a link state advertisement is originated, its
   sequence number is incremented, its age is set to zero, and its
   checksum is calculated.  The advertisement is then installed
   into the local link state database and forwarded out all fully
   operational interfaces (that is, those interfaces with a state
   greater than Waiting) for distribution throughout the switch
   fabric.  See Section 11.2.4 for a description of the
   installation of the advertisement into the link state database
   and Section 11.2.3 for a description of how advertisements are
   forwarded.

   A switch originates a new instance of a link state
   advertisement as a result of the following events:

   1) The state of one of the switchs interfaces changes such
      that the contents of the associated switch link
      advertisement changes.

   2) The designated switch on any of the switchs attached
      network links changes.  The switch originates a new switch
      link advertisement.  Also, if the switch itself is now the
      designated switch, it originates a new network link
      advertisement for the link.

   3) One of the switchs neighbor states changes to or from Full.
      If this changes the contents of the associated switch link
      advertisement, a new instance is generated.  Also, if the
      switch is the designated switch for the attached network
      link, it originates a new network link advertisement for the
      link.



L. Kane, et. al.                                           [Page 53]


I/D                 VLS Protocol Specification            May 1997


   Two instances of the same link state advertisement must not be
   originated within the time period MinLSInterval.  Note that
   this may require that the generation of the second instance to
   be delayed up to MinLSInterval seconds.


11.1.1  Switch Link Advertisements

   A switch link advertisement describes the collected states of
   all functioning links attached to the originating switch --
   that is, all attached links with an interface state greater
   than Down.  A switch originates a switch link advertisement
   when it first becomes functional.  It then generates a new
   instance of the advertisement each time one of its interfaces
   changes state.

   Each link in the advertisement is assigned a type, based on the
   state of interface, as shown in Table 4.


                               Note

            A stub link is a link that is unavailable
            for network traffic.



      Interface state     Link type     Description

      Down                (n/a)         (n/a)
      Loopback            3             Stub link
      Waiting             3             Stub link
      Point-to-Point      1             Point-to-point link
      DS Other*           2             Multi-access link
      Backup*             2             Multi-access link
      DS**                2             Multi-access link

        *If a full adjacency has been formed with the designated
         switch.  Otherwise, the link type is 3 until the
         adjacency has been established.

       **If a full adjacency has been formed with at least one
         other switch on the link.  Otherwise, the link type is 3
         until an adjacency has been established.

          Table 4: Link Types in a Switch Link Advertisement


   Each link in the advertisement is also assigned a link
   identifier based on its link type.  In general, this value
   identifies another switch that also originates advertisements
   for the link, thereby providing a key for accessing other link


L. Kane, et. al.                                           [Page 54]


I/D                  VLS Protocol Specification            May 1997


   state advertisements for the link.  The relationship between
   link type and ID is shown in Table 5.


      Link type   Description               Link ID

      1           Point-to-point link       Switch ID of neighbor
                                            switch
      2           Multi-access link         Switch ID of
                                            designated switch
      3           Stub link                 (n/a)

           Table 5: Link IDs in a Switch Link Advertisement


   In addition to a type and an identifier, the description of
   each link specifies the interface ID of the associated network
   link.

   Finally, each link description includes the cost of sending a
   packet over the link.  This output cost is expressed in the
   link state metric and must be greater than zero.

   To illustrate the format of a switch link advertisement,
   consider the switch fabric shown in Figure 4.


                           00-00-1d-22-23-c5
                               +-------+
                               |  SW2  |
                               +-------+
                                   |
                                   | Point-to-Point
                                   |
                                   | 01
      +-------+    Waiting     +-------+
      |  SW3  |----------------|  SW1  | 00-00-1d-1f-05-81
      +-------+             02 +-------+
  00-00-1d-17-35-a4                | 03
                                   |
                                   | DS Other
                                   |
         +-------------------------+-------------------------+
      DS |                         |                         |
         |                         |                         |
     +-------+                 +-------+                 +-------+
     |  SW4  |                 |  SW5  |                 |  SW6  |
     +-------+                 +-------+                 +-------+
   00-00-1d-4a-26-b3       00-00-1d-4a-27-1c       00-00-1d-7e-84-2e


                    Figure 4: Sample Switch Fabric


L. Kane, et. al.                                           [Page 55]


I/D                 VLS Protocol Specification            May 1997


   In this example, switch SW1 has 5 neighboring switches (shown
   as boxes) distributed over 3 network links (shown as lines).
   The base MAC address of each switch is also shown adjacent to
   each box.  On switch SW1, ports 01 and 02 attach to point-to-
   point network links, while port 03 attaches to a multi-access
   network link with three attached switches.  The interface state
   of each port is shown next to the line representing the
   corresponding link.

   The switch link advertisement generated by switch SW1 would
   contain the following data items:

   ; switch link advertisement for switch SW1

   LS age = 0                 ; always true on origination
   Options = (T-bit|E-bit)    ; options
   LS type = 1                ; this is a switch link advertisement
                              ; SW1s switch ID
   Link State ID = 00-00-1d-1f-05-81-00-00-00-00
   Advertising switch = 00-00-1d-1f-05-81-00-00-00-00
   # links = 3

      ; link on interface port 1
      Link ID = 00-00-1d-22-23-c5-00-00-00-00      ; switch ID
      Link Data = 00-00-1d-1f-05-81-00-00-00-01    ; interface ID
      Type = 1                                     ; pt-to-pt link
      # other metrics = 0                          ; TOS 0 only
      TOS 0 metric = 1

      ; link on interface port 2
      Link ID = 00-00-1d-17-35-a4-00-00-00-00      ; switch ID
      Link Data = 00-00-1d-1f-05-81-00-00-00-02    ; interface ID
      Type = 3                                     ; stub link
      # other metrics = 0                          ; TOS 0 only
      TOS 0 metric = 1

      ; link on interface port 3
      Link ID = 00-00-1d-4a-26-b3-00-00-00-00      ; switch ID of DS
      Link Data = 00-00-1d-1f-05-81-00-00-00-03    ; interface ID
      Type = 1                                     ; multi-ax link
      # other metrics = 0                          ; TOS 0 only
      TOS 0 metric = 2

   (See Section 14.2 for a detailed description of the format of a
   switch link advertisement.)









L. Kane, et. al.                                           [Page 56]


I/D                 VLS Protocol Specification            May 1997


11.1.2  Network Link Advertisements

   Network link advertisements are used to describe the switches
   attached to each multi-access network link.


                               Note

         Network link advertisements are not generated for
         point-to-point links.  However, in the current
         version of VLSP, network links are always treated
         as multi-access, regardless of the physical nature
         of the link.  Therefore, network link advertisements
         are generated for all network links, regardless of
         physical type.


   A network link advertisement is originated by the designated
   switch for the associated link once the switch has established
   a full adjacency with at least one other switch on the link.
   Each advertisement lists the switch IDs of those switches that
   are fully adjacent to the designated switch.  The designated
   switch includes itself in this list.

   To illustrate the format of a network link advertisement,
   consider again the switch fabric shown in Figure 4.  In this
   example, network link advertisements will be generated only
   switch SW4, the designated switch of the multi-access network
   link between switches SW1 and SW4.

   The network link advertisement generated by switch SW4 would
   contain the following data items:

   ; network link advertisement for switch SW4

   LS age = 0                 ; always true on origination
   Options = (T-bit|E-bit)    ; options
   LS type = 2                ; this is a switch link advertisement
                              ; SW4s switch ID
   Link State ID = 00-00-1d-4a-26-b3-00-00-00-00
   Advertising switch = 00-00-1d-4a-26-b3-00-00-00-00

      Attached switch = 00-00-1d-4a-26-b3-00-00-00-00
      Attached switch = 00-00-1d-1f-05-81-00-00-00-00
      Attached switch = 00-00-1d-4a-27-1c-00-00-00-00
      Attached switch = 00-00-1d-7e-84-2e-00-00-00-00

   (See Section 14.3 for a detailed description of the format of a
   network link advertisement.)





L. Kane, et. al.                                           [Page 57]


I/D                 VLS Protocol Specification            May 1997


11.2  Distributing Link State Advertisements

   Link state advertisements are distributed throughout the switch
   fabric encapsulated within Link State Update packets.  A single
   Link State Update packet may contain several distinct
   advertisements.

   To make the distribution process reliable, each advertisement
   must be explicitly acknowledged in a Link State Acknowledgment
   packet.  Note, however, that multiple acknowledgments can be
   grouped together into a single Link State Acknowledgment
   packet.  A sending switch retransmits unacknowledged Link State
   Update packets at regular intervals until they are
   acknowledged.

   The remainder of this section is structured as follows:

   -  Section 11.2.1 presents an overview of the distribution
      process.

   -  Section 11.2.2 describes how an incoming Link State Update
      packet is processed.

   -  Section 11.2.3 describes how a Link State Packet is
      forwarded -- both by the originating switch and an
      intermediate receiving switch.

   -  Section 11.2.4 describes how advertisements are installed
      into the local database.

   -  Section 11.2.5 describes the retransmission of
      unacknowledged advertisements.

   -  Section 11.2.6 describes how advertisements are acknowledged.


11.2.1  Overview

   The philosophy behind the distribution of link state
   advertisements is based on the concept of adjacencies -- that
   is, each switch is only required to remain synchronized with
   its adjacent neighbors.

   When a switch originates a new instance of a link state
   advertisement, it formats the advertisement into a Link State
   Update packet and floods the packet out each fully operational
   interface -- that is, each interface with a state greater than
   Waiting.  However, only those neighbors that are adjacent to
   the sending switch need to process the packet.

   The sending switch indicates which of its neighbor switches
   should process the advertisement by specifying a particular


L. Kane, et. al.                                           [Page 58]


I/D                  VLS Protocol Specification            May 1997


   multicast destination in the network layer address information
   (see Section 13.2).  The sending switch sets the value of the
   network layer destination switch ID field according to the
   state of the interface over which the packet is sent:

   -  If the interface state is Point-to-Point, DS, or Backup, the
      switch is adjacent to all other switches on the link and all
      neighboring switches must process the packet.  Therefore,
      the destination field is set to the multicast switch ID
      AllSPFSwitches.

   -  If the interface state is DS Other, the switch is only
      adjacent to the designated switch and the backup designated
      switch and only those two neighboring switches must process
      the packet.  Therefore, the destination field is set to the
      multicast switch ID AllDSwitches.

   A similar logic is used when a switch receives a Link State
   Update packet containing a new instance of a link state
   advertisement.  After processing and acknowledging the packet,
   the receiving switch forwards the Link State Update packet as
   follows:

   -  On the interface over which the original Link State Update
      packet was received:

      -  If the receiving switch is the designated switch for the
         attached network link, the packet is forwarded to all
         other switches on the link.  (The destination field is set
         to AllSPFSwitches.)  The originating switch will recognize
         that it was the advertisement originator and discard the
         packet.

      -  If the receiving switch is not the designated switch for
         the attached network link, the packet is not sent back out
         the interface over which it was received.

   -  On all other interfaces:

      -  If the receiving switch is the designated switch for the
         attached network link, the packet is forwarded to all
         switches on the link.  (The destination field is set to
         AllSPFSwitches.)

      -  If the receiving switch is neither the designated switch
         or the backup designated switch for the attached network
         link, the packet is forwarded only to the designated
         switch and the backup designated switch.  (The destination
         field is set to AllDSwitches.)

   Each Link State Update packet is forwarded and processed in
   this fashion until all switches in the fabric have received


L. Kane, et. al.                                           [Page 59]


I/D                  VLS Protocol Specification            May 1997


   notification of the new instance of the link state
   advertisement.


11.2.2  Processing an Incoming Link State Update Packet

   When the a Link State Update packet is received, it is first
   subjected to a number of consistency checks.  In particular,
   the Link State Update packet is associated with a specific
   neighbor.  If the state of that neighbor is less than Exchange,
   the entire Link State Update packet is discarded.

   Each link state advertisement contained in the packet is
   processed as follows:

   1) Validate the advertisement's link state checksum and type.
      If the checksum is invalid or the type is unknown, discard
      the advertisement without acknowledging it.

   2) If the advertisement's age is equal to MaxAge and there is
      currently no instance of the advertisement in the local link
      state database, then do the following:

      a) Acknowledge the advertisement by sending a Link State
         Acknowledgment packet to the sending neighbor (see Section
         11.2.6).

      b) Purge all outstanding requests for equal or previous
         instances of the advertisement from the sending neighbor's
         Link State Request list.

      c) If the neighbor is Exchange or Loading, install the
         advertisement in the link state database (see Section
         11.2.4).  Otherwise, discard the advertisement.

   3) If the advertisements age is equal to MaxAge and there is
      an instance of the advertisement in the local link state
      database, then do the following:

      a) If the advertisement is listed in the link state
         retransmission list of any neighbor, remove the
         advertisement from the retransmission list(s) and delete
         the database copy of the advertisement.

      b) Discard the received (MaxAge) advertisement without
         acknowledging it.

   4) If the advertisement's age is less than MaxAge, attempt to
      locate an instance of the advertisement in the local link
      state database.  If there is no database copy of this




L. Kane, et. al.                                           [Page 60]


I/D                  VLS Protocol Specification            May 1997


      advertisement, or the received advertisement is more recent
      than the database copy (see Section 10.1.1), do the
      following:

      a) If there is already a database copy, and if the database
         copy was installed less than MinLSInterval seconds ago,
         discard the new advertisement without acknowledging it.

      b) Otherwise, forward the new advertisement out some subset
         of the local interfaces (see Section 11.2.3).  Note
         whether the advertisement was sent back out the receiving
         interface for later use by the acknowledgment process.

      c) Remove the current database copy from the Link state
         retransmission lists of all neighbors.

      d) Install the new advertisement in the link state database,
         replacing the current database copy.  (Note that this may
         cause the routing table calculation to be scheduled.  See
         Section 12.)  Timestamp the new advertisement with the
         time that it was received to prevent installation of
         another instance within MinLSInterval seconds.

      e) Acknowledge the advertisement, if necessary, by sending a
         Link State Acknowledgment packet back out the receiving
         interface.  (See Section 11.2.6.)

      f) If the link state advertisement was initially advertised
         by the local switch itself, advance the advertisement
         sequence number and issue a new instance of the
         advertisement.  (Receipt of a newer instance of an
         advertisement means that the local copy of the
         advertisement is left over from before the last time the
         switch was restarted.)

   5) If the received advertisement is the same instance as the
      database copy (as determined by the algorithm described in
      Section 10.1.1), do the following:

      a) If the advertisement is listed in the neighbors link
         state retransmission list, the local switch is expecting
         an acknowledgment for this advertisement.  Treat the
         received advertisement as an implied acknowledgment, and
         remove the advertisement from the link state
         retransmission list.  Note this implied acknowledgment for
         later use by the acknowledgment process (Section 11.2.6).

      b) Acknowledge the advertisement, if necessary, by sending a
         Link State Acknowledgment packet back out the receiving
         interface.  (See Section 11.2.6.)




L. Kane, et. al.                                           [Page 61]


I/D                 VLS Protocol Specification            May 1997


   6) If the database copy of the advertisement is more recent
      than the instance just received, do the following:

      a) Determine whether the instance is listed in the neighbor
         link state request list.  If so, an error has occurred in
         the database exchange process.  Restart the database
         exchange process by generating a neighbor BadLSReq event
         for the sending neighbor and terminate processing of the
         Link State Update packet.

      b) Otherwise, generate an unusual event to network management
         and discard the advertisement.


11.2.3  Forwarding Link State Advertisements

   When a new instance of an advertisement is originated or after
   an incoming advertisement has been processed, the switch must
   decide over which interfaces and to which neighbors the
   advertisement will be forwarded.  In some instances, the switch
   may decide not to forward the advertisement over a particular
   interface because it is able to determine that the neighbors on
   that attached link have or will receive the advertisement from
   another switch on the link.

   The decision of whether to forward an advertisement over each
   of the switchs interfaces is made as follows:

   1) Each neighboring switch attached to the interface is
      examined to determine whether it should receive and process
      the new advertisement.  For each neighbor, the following
      steps are executed:

      a) If the neighbor state is less than Exchange, the neighbor
         need not receive or process the new advertisement.

      b) If the neighbor state is Exchange or Loading, examine the
         link state request list associated with the neighbor.  If
         an instance of the new advertisement is on the list, the
         neighboring switch already has an instance of the
         advertisement.  Compare the new advertisement to the
         neighbor's copy:

         -  If the new advertisement is less recent, the neighbor
            need not receive or process the new advertisement.

         -  If the two copies are the same instance, delete the
            advertisement from the link state request list.  The
            neighbor need not receive or process the new
            advertisement.[7]




L. Kane, et. al.                                           [Page 62]


I/D                 VLS Protocol Specification            May 1997


         -  Otherwise, the new advertisement is more recent.
            Delete the advertisement from the link state request
            list.  The neighbor may need to receive and process the
            new advertisement.

      c) If the new advertisement was received from this neighbor,
         the neighbor need not receive or process the
         advertisement.

      d) Add the new advertisement to the link state retransmission
         list for the neighbor.

   2) The switch must now decide whether to forward the new
      advertisement out the interface.

      a) If the link state advertisement was not added to any of
         the link state retransmission lists for neighbors attached
         to the interface, there is no need to forward the
         advertisement out the interface.

      b) If the new advertisement was received on this interface,
         and it was received from either the designated switch or
         the backup designated switch, there is no need to forward
         the advertisement out the interface.  Chances are all
         neighbors on the attached network link have also received
         the advertisement already.

      c) If the new advertisement was received on this interface
         and the state of the interface is Point-to-Point, there is
         no need to forward the advertisement since the received
         advertisement was originated by the neighbor switch.

      d) If the new advertisement was received on this interface,
         and the interface state is Backup -- that is, the switch
         itself is the backup designated switch -- there is no need
         to forward the advertisement out the interface.  The
         designated switch will distribute advertisements on the
         attached network link.

      e) Otherwise, the advertisement must be forwarded out the
         interface.

      To forward a link state advertisement, the switch first
      increments the advertisements age by InfTransDelay seconds
      to account for the transmission time over the link.  The
      switch then copies the advertisement into a Link State
      Update packet

      Forwarded advertisements are sent to all adjacent switches
      associated with the interface.  If the interface state is
      Point-to-Point, DS, or Backup, the destination switch ID
      field of the network layer address information is set to the


L. Kane, et. al.                                           [Page 63]


I/D                  VLS Protocol Specification            May 1997


      multicast switch ID AllSPFSwitches.  If the interface state
      is DS Other, the destination switch ID field is set to the
      multicast switch ID AllDSwitches.


11.2.4  Installing Link State Advertisements in the Database

   When a new link state advertisement is installed into the link
   state database, as the result of either originating or
   receiving a new instance of an advertisement, the switch must
   determine whether the routing table and best paths need to be
   recalculated.  To make this determination, do the following:

   1) Compare the contents of the new instance with the contents
      of the old instance (assuming the older instance is
      available).  Note that this comparison does not include any
      data from the link state header.  Differences in fields
      within the header (such as the sequence number and checksum,
      which are guaranteed to be different in different instances
      of an advertisement) are of no consequence when deciding
      whether or not to recalculate the routing table.

   2) If there are no differences in the contents of the two
      advertisement instances, there is no need to recalculate the
      routing table.

   3) Otherwise, the entire routing table must be recalculated,
      starting with the best path calculations

   Note also that the older instance of the advertisement must be
   removed from the link state database when the new advertisement
   is installed.  The older instance must also be removed from the
   link state retransmission lists of all neighbors.


11.2.5  Retransmitting Link State Advertisements

   When a switch sends a link state advertisement to an adjacent
   neighbor, it records the advertisement in the neighbors link
   state retransmission list.  To ensure the reliability of the
   distribution process, the switch continues to periodically
   retransmit the advertisements specified in the list until they
   are acknowledged.

   The interval timer used to trigger retransmission of the
   advertisements is set to RxmtInterval seconds, as found in the
   interface data structure.  Note that if this value is too low,
   needless retransmissions will ensue.  If the value is too high,
   the speed with which the databases synchronize across adjacencies
   may be affected if there are lost packets.




L. Kane, et. al.                                           [Page 64]


I/D                 VLS Protocol Specification            May 1997


   When the interval timer expires, entries in the retransmission
   list are formatted into one or more Link State Update packets.
   (Remember that multiple advertisements can fit into a single
   Link State Update packet.)  The age field of each advertisement
   is incremented by InfTransDelay, as found in the interface data
   structure, before the advertisement is copied into the outgoing
   packet.

   Link State Update packets containing retransmitted
   advertisements are always sent directly to the adjacent switch.
   That is, the destination field of the network layer addressing
   information is set to the switch ID of the neighboring switch.

   If the adjacent switch goes down, retransmissions will continue
   until the switch failure is detected and the adjacency is torn
   down by the VLSP Hello protocol.  When the adjacency is torn
   down, the link state retransmission list is cleared.


11.2.6  Acknowledging Link State Advertisements

   Each link state advertisement received by a switch must be
   acknowledged.  In most cases, this is done by sending a Link
   State Acknowledgment packet.  However, acknowledgments can also
   be done implicitly by sending Link State Update packets (see
   step 4a of Section 11.2.2).

   Multiple acknowledgments can be grouped together into a single
   Link State Acknowledgment packet.

Sending an acknowledgment

   Link State Acknowledgment packets are sent back out the
   interface over which the advertisement was received.  The
   packet can be sent immediately to the sending neighbor, or it
   can be delayed and sent when an interval timer expires.

   -  Sending delayed acknowledgments facilitates the formatting
      of multiple acknowledgments into a single packet.  This
      enables a single packet to send acknowledgments to several
      neighbors at once by using a multicast switch ID in the
      destination field of the network layer addressing
      information (see below).  Delaying acknowledgments also
      randomizes the acknowledgment packets sent by the multiple
      switches attached to a multi-access network link.

      Note that the interval used to time delayed acknowledgments
      must be short (less than RxmtInterval) or needless
      retransmissions will ensue.

      Delayed acknowledgments are sent to all adjacent switches
      associated with the interface.  If the interface state is


L. Kane, et. al.                                           [Page 65]


I/D                 VLS Protocol Specification            May 1997


      Point-to-Point, DS, or Backup, the destination field of the
      network layer addressing information is set to the multicast
      switch ID AllSPFSwitches.  If the interface state is DS Other,
      the destination field is set to the multicast switch ID
      AllDSwitches.

   -  Immediate acknowledgments are sent directly to a specific
      neighbor in response to the receipt of duplicate link state
      advertisements.  These acknowledgments are sent immediately
      when the duplicate is received.

   The method used to send a Link State Acknowledgment packet --
   either delayed or immediate -- depends on the circumstances
   surrounding the receipt of the advertisement, as shown in
   Table 6.  Note that switches with an interface state of Backup
   send acknowledgments differently than other switches because
   they play a slightly different role in the distribution
   process (see Section 11.2.3).



                                  Acknowledgment type by state
    Circumstance                Backup                 All others

    Advertisement was           None                   None
    forwarded back out
    receiving interface

    Advertisement more          Delayed if advert      Delayed
    recent than database        received from DS,
    copy, but was not           else do nothing
    forwarded back out
    receiving interface

    Advertisement was a         Delayed if advert      None
    duplicate treated           received from DS,
    as an implied acknow-       else do nothing
    ledgment (step 4a of
    Section 11.2.2)

    Advertisement was a         Immediate              Immediate
    duplicate not treated
    as an implied acknow-
    ledgment

    Advertisement age           Immediate              Immediate
    equal to MaxAge and
    no current instance
    found in database

                Table 6: Sending Link State Acknowledgments



L. Kane, et. al.                                           [Page 66]


I/D                 VLS Protocol Specification            May 1997


Receiving an acknowledgment

   When the a Link State Acknowledgment packet is received, it is
   first subjected to a number of consistency checks.  In
   particular, the packet is associated with a specific neighbor.
   If the state of that neighbor is less than Exchange, the entire
   Link State Acknowledgment packet is discarded.

   Each acknowledgment contained in the packet is processed as
   follows:

   -  If the advertisement being acknowledged has an instance in
      the link state retransmission list for the sending neighbor,
      do the following:

      -  If the acknowledgment is for the same instance as that
         specified in the list (as determined by the procedure
         described in Section 10.1.1), remove the instance from the
         retransmission list.

      -  Otherwise, log the acknowledgment as questionable.


11.3  Aging the Link State Database

   Each link state advertisement has an age field, containing the
   advertisements age, expressed in seconds.  When the
   advertisement is copied into a Link State Update packet for
   forwarding out a particular interface, the age is incremented
   by InfTransDelay seconds to account for the transmission time
   over the link.  An advertisement's age is never incremented
   past the value MaxAge. Advertisements with an age of MaxAge are
   not used to build the routing table or calculate best paths.

   If a link state advertisements age reaches MaxAge, the switch
   flushes the advertisement from the switch fabric by doing the
   following:

   -  Originate a new instance of the advertisement with the age
      field set to MaxAge.  The distribution process will
      eventually result in the advertisement being removed from
      the retransmission lists of all switches in the fabric.

   -  Once the advertisement is no longer contained in the link
      state retransmission list of any neighbor and no neighbor is
      in a state of Exchange or Loading, remove  the advertisement
      from the local link state database.







L. Kane, et. al.                                           [Page 67]


I/D                 VLS Protocol Specification            May 1997


11.3.1  Premature Aging of Advertisements

   A link state advertisement can be prematurely flushed from the
   switch fabric by forcing its age to MaxAge and redistributing
   the advertisement.

   A switch that was previously the designated switch for a multi-
   access network link but has lost that status due to a failover
   to the backup designated switch prematurely ages the network
   link advertisements it originated for the link.

   Premature aging also occurs when an advertisement's sequence
   number must wrap -- that is, when the current advertisement
   instance has a sequence number of 0x7fffffff.  In this
   circumstance, the advertisement is prematurely aged so that the
   next instance of the advertisement can be originated with a
   sequence number of 0x80000001 and be recognized as the most
   recent instance.

   A switch may only prematurely age those link state
   advertisements for which it is the advertising switch.


12.  Calculating the Routing Table

   Once an adjacency has been formed and the two switches have
   synchronized their databases, each switch in the adjacency
   builds its routing table and calculates the best path(s) to all
   other switches in the fabric, using itself as the root of each
   path.  In this context, "best" path means that path with the
   lowest total cost metric across all hops.  If there are
   multiple paths with the same (lowest) total cost metric, they
   are all calculated.  Best paths are stored in the area data
   structure.

   Paths are calculated using the well-known Dijkstra algorithm.
   For a detailed description of this algorithm, the reader is
   referred to [Perlman], or any of a number of standard textbooks
   dealing with network routing.

   Note that whenever there is a change in an adjacency
   relationship, or any change that alters the topology of the
   switch fabric, the routing table must be rebuilt and the best
   paths recalculated.










L. Kane, et. al.                                           [Page 68]


I/D                VLS Protocol Specification            May 1997


13.  Protocol Packets

   This section describes VLS protocol packets and link state
   advertisements.


                             Note

         All VLSP packets are encapsulated in a standard ISMP
         packet, as described in Section 3.  In the current
         section, the term "packet" refers to the payload of
         the ISMP packet -- that is, the ISMP message body.
         It is understood that the packet format descriptions
         that follow are preceded by the ISMP frame header and
         ISMP packet header, as described in Sections 3.1 and
         3.2.


   There are five distinct VLSP packet types, as listed in Table 7.


      Type  Packet Name            Function               Section

       1    Hello                  Discover/maintain
                                   neighbors              13.5.1
       2    Database Description   Summarize database
                                   contents               13.5.2
       3    Link State Request     Database download      13.5.3
       4    Link State Update      Database update        13.5.4
       5    Link State Ack         Flooding acknow-
                                   ledgment               13.5.5

                    Table 7: VLSP Packet Types



   Since it is important that the link state databases remain
   synchronized throughout the switch fabric, processing of both
   incoming and outgoing routing protocol packets should take
   priority over ordinary data packets.  Section 13.1 discusses
   packet processing.

   All VLSP packets begin with network layer addressing
   information, described in Section 13.2, followed by a standard
   header, described in Section 13.3.

   With the exception of Hello packets, all VLSP packets deal with
   lists of link state advertisements.  The format of a link state
   advertisement is described in Section 14.





L. Kane, et. al.                                           [Page 69]


I/D               VLS Protocol Specification            May 1997


13.1  Packet Processing

   Note that with the exception of Hello packets, VLSP packets are
   sent only between adjacent neighbors.  Therefore, all packets
   travel a single hop.

   VLSP does not support fragmentation and reassembly of packets.
   Therefore, packets containing lists of link state
   advertisements or advertisement headers must be formatted such
   that they contain only as many advertisements or headers as
   will fit within the size constraints of a standard ethernet
   frame.

   When a protocol packet is received by a switch, it must first
   pass the following criteria before being accepted for further
   processing:

   -  The checksum and protocol version number must be correct.

   -  The destination switch ID (as found in the network layer
      address information) must be the switch ID of the receiving
      switch, or one of the multicast switch IDs AllSPFSwitches or
      AllDSwitches.

      If the destination switch ID is the multicast switch ID
      AllDSwitches, the state of the receiving interface must be
      Point-to-Point, DS, or Backup.

   -  The source switch ID (as found in the network layer address
      information) must not be that of the receiving switch.
      (That is, locally originated packets should be discarded.)

   At this point, if the packet is a Hello packet, it is accepted
   for further processing.

   Since all other packet types are only sent between adjacent
   neighbors, the packet must have been sent by one of the
   switch's active neighbors.  If the source switch ID matches the
   switch ID of one of the receiving switchs active neighbors (as
   stored in the interface data structure associated with the
   inport interface), the packet is accepted for further
   processing.  Otherwise, the packet is discarded.


13.2  Network Layer Address Information

   As mentioned in Section 4.2.1, portions of the VLS protocol (as
   derived from OSPF) are dependent on certain network layer
   addresses -- in particular, the AllSPFSwitches and AllDSwitches
   multicast addresses that drive the distribution of link state
   advertisements throughout the switch fabric.  In order to
   facilitate the implementation of the protocol at the physical


L. Kane, et. al.                                           [Page 70]


I/D               VLS Protocol Specification            May 1997


   MAC layer, network layer address information is encapsulated in
   the VSLP packets.  This information immediately follows the
   ISMP frame and packet header and immediately precedes the VLSP
   packet header, as shown below:


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   :                  frame header / ISMP header                   :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
00 |                                                               |
   :                       Unused (16 octets)                      :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
16 |                                                               |
   +                     Destination switch ID                     +
20 |                                                               |
   +                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
24 |                               |                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
28 |                                                               |
   +                       Source switch ID                        +
32 |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
36 |                                                               |
   :                          VLSP header                          :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Destination switch ID

      This 10-octet field contains the switch ID of the packet
      destination.  The value here is set as follows:

      -  Hello packets are addressed to the multicast switch ID
         AllSPFSwitches.

      -  The designated switch and the backup designated switch
         address initial Link State Update packets and Link State
         Acknowledgment packets to the multicast switch ID
         AllSPFSwitches.

      -  All other switches address initial Link State Update
         packets and Link State Acknowledgment packets to the
         multicast switch ID AllDSwitches.

      -  Retransmissions of Link State Update packets are always
         addressed directly to the nonresponding switch.


L. Kane, et. al.                                           [Page 71]


I/D                 VLS Protocol Specification            May 1997


      -  Database Description packets and Link State Request are
         always addressed directly to the other switch
         participating in the database exchange process.

   Source switch ID

      This 10-octet field contains the switch ID of the sending
      switch.


13.3  VLSP Packet Header

   Every VLSP packet starts with a common 30-octet header.  This
   header, along with the data found in the network layer address
   information, contains all the data necessary to determine
   whether the packet should be accepted for further processing.
   (See Section 13.1.)

   The format of the VLSP header is shown below.  Note that the
   header starts at offset 36 of the ISMP message body, following
   the network layer address information.


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   :                  frame header / ISMP header                   :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
00 |                                                               |
   :               Network layer address information               :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
36 |   Version #   |     Type      |         Packet length         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
40 |                                                               |
   +                       Source switch ID                        +
44 |                                                               |
   +                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
48 |                               |         Area ID . . .         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
52 |         Area ID . . .         |           Checksum            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
56 |            Autype             |                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+        Authentication         +
60 |                                                               |

   +                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
64 |                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+




L. Kane, et. al.                                           [Page 72]


I/D                 VLS Protocol Specification            May 1997


   Version #

      This 1-octet field contains the version number of the VLS
      protocol to which this packet adheres.  This document
      describes VLSP Version 1.

   Type

      This 1-octet field contains the packet type.  Possible
      values are as follows:

         1   Hello
         2   Database Description
         3   Link State Request
         4   Link State Update
         5   Link State Acknowledgment

   Packet length

      This 2-octet field contains the length of the protocol
      packet, in bytes, calculated from the start of the VLSP
      header, at offset 20 of the ISMP message body.  If the
      packet length is not an integral number of 16-bit words, the
      packet is padded with an octet of zero (see the description
      of the checksum field, below).

   Switch ID

      This 10-octet field contains the switch ID of the sending
      switch.

   Area ID

      This 4-octet field contains the area identifier.  Since VLSP
      does not support multiple areas, the value here is always
      zero.

   Checksum

      This 2-octet field contains the packet checksum value.  The
      checksum is calculated as the 16-bit one's complement of the
      one's complement sum of all the 16-bit words in the packet,
      beginning with the VLSP header, excluding the authentication
      field.  If the packet length is not an integral number of
      16-bit words, the packet is padded with an octet of zero
      before calculating the checksum.

   AuType

      This 2-octet field identifies the authentication scheme to
      be used for the packet.  Since authentication is not
      supported by this version of VLSP, this field contains zero.


L. Kane, et. al.                                           [Page 73]


I/D               VLS Protocol Specification            May 1997


   Authentication

      This 8-octet field is reserved for use by the authentication
      scheme.  Since authentication is not supported by this
      version of VLSP, this field contains zeroes.


13.4  Options Field

   Hello packets and Database Description packets, as well as link
   state advertisements, contain a 1-octet options field.  Using
   this field, a switch can communicate its optional capabilities
   to other VLSP switches.  The receiving switch can then choose
   whether or not to support those optional capabilities.  Thus,
   switches of differing capabilities potentially can be mixed
   within a single VLSP routing domain.

   Two optional capabilities are currently defined in the options
   field:  routing based on Type of Service (TOS) and support for
   external routing beyond the local switch fabric.  These two
   capabilities are specified in the options field as shown below.


                       +-+-+-+-+-+-+-+-+
                       |0|0|0|0|0|0|E|T|
                       +-+-+-+-+-+-+-+-+

                       The options field


   T-bit

      The T-bit specifies the switchs Type of Service (TOS)
      capability.  If the T-bit is set, the switch supports
      routing based on nonzero types of service.

   E-bit

      The E-bit specifies the switchs external routing
      capability.  If the E-bit is set, the switch supports
      external routing.


                               Note

            The current version of VLSP supports
            neither of these capabilities.  Therefore,
            both the T-bit and the E-bit are clear and
            the options field contains a value of zero.





L. Kane, et. al.                                           [Page 74]


I/D                 VLS Protocol Specification            May 1997


13.5  Packet Formats

   This section contains detailed descriptions of the five VLS
   protocol packets.


13.5.1  Hello Packets

   Hello packets are sent periodically over all switch interfaces
   in order to discover and maintain neighbor relationships.
   Since all switches connected to a common network link must
   agree on certain interface parameters, these parameters are
   included in each Hello packet.  A switch receiving a Hello
   packet that contains parameters inconsistent with its own view
   of the interface will not establish a neighbor relationship
   with the sending switch.

   The format of a Hello packet is shown below.


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
00 |                                                               |
   :              Network layer addressing / VLSP header           :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
66 |                      (unused - must be 0)                     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
70 |         HelloInt              |    Options    |   Priority    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
74 |                            DeadInt                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
78 |                                                               |
   +                      Designated switch ID                     +
82 |                                                               |
   +                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
86 |                               |                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
90 |                                                               |
   +                   Backup designated switch ID                 +
94 |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
98 |                                                               |
   +                                                               +
   :                          Neighbor list                        :
   +                                                               +
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+





L. Kane, et. al.                                           [Page 75]


I/D                 VLS Protocol Specification            May 1997


   Network layer addressing / VLSP header

      This 66-octet field contains the network layer addressing
      information and the standard VLS protocol packet header.
      The packet header type field contains a value of 1.

   HelloInt

      This 2-octet field contains the interval, in seconds, at
      which this switch sends Hello packets.

   Options

      This 1-octet field contains the optional capabilities
      supported by the switch, as described in Section 13.4.

   Priority

      This 1-octet field contains the switch priority used in
      selecting the designated switch and backup designated switch
      (see Section 9.3.1).  If the value here is zero, the switch
      is ineligible to become the designated switch or the backup
      designated switch.

   DeadInt

      This 4-octet field contains the length of time, in seconds,
      that neighboring switches will wait before declaring the
      interface down once they stop receiving Hello packets over
      the interface.  The value here is equal to the value of
      SwitchDeadInterval, as found in the interface data
      structure.

   Designated switch

      This 10-octet field contains the switch ID of the designated
      switch for this network link, as currently understood by the
      sending switch.  This value is set to zero if the designated
      switch selection process has not yet begun.

   Backup designated switch

      This 10-octet field contains the switch ID of the backup
      designated switch for this network link, as currently
      understood by the sending switch.  This value is set to zero
      if the backup designated switch selection process has not
      yet begun.

   Neighbor list

      This variable-length field contains a list of switch IDs of
      each switch from which the sending switch has received a


L. Kane, et. al.                                           [Page 76]


I/D                 VLS Protocol Specification            May 1997


      valid Hello packet within the last SwitchDeadInterval
      seconds.


13.5.2  Database Description Packets

   Database Description packets are exchanged while an adjacency
   is being formed between two neighboring switches and are used
   to describe the contents of the topological database.  For a
   complete description of the database exchange process, see
   Section 10.2.

   The format of a Database Description packet is shown below.


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
00 |                                                               |
   :              Network layer addressing / VLSP header           :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
66 |     (unused - must be 0)      |    Options    |     Flags     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
70 |                        Sequence number                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
74 |                                                               |
   +                                                               +
   :                 Link state advertisement headers              :
   +                                                               +
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Network layer addressing / VLSP header

      This 66-octet field contains the network layer addressing
      information and the standard VLS protocol packet header.
      The packet header type field contains a value of 2.

   Options

      This 1-octet field contains the optional capabilities
      supported by the switch, as described in Section Section
      13.4.

   Flags

      This 1-octet field contains a set of bit flags that are used
      to coordinate the database exchange process.  The format of
      this octet is as follows:



L. Kane, et. al.                                           [Page 77]


I/D                 VLS Protocol Specification            May 1997


                       +-+-+-+-+-+-+-+-+
                       |0|0|0|0|0|I|M|MS
                       +-+-+-+-+-+-+-+-+

      I-bit (Init)

         The I-bit is used to signal the start of the exchange.  It
         is set while the two switches negotiate the master/slave
         relationship and the starting sequence number.

      M-bit (More)

         The M-bit is set to indicate that more Database
         Description packets to follow.

      MS-bit (Master/Slave)

         The MS-bit is used to indicate which switch is the master
         of the exchange.  If the bit is set, the sending switch is
         the master during the database exchange process.  If the
         bit is clear, the switch is the slave.

   Sequence number

      This 4-octet field is used to sequence the Database
      Description packets during the database exchange process.
      The two switches involved in the exchange process agree on
      the initial value of the sequence number during the
      master/slave negotiation.  The number is then incremented
      for each Database Description packet in the exchange.

      To acknowledge each Database Description packet sent by the
      master, the slave sends a Database Description packet that
      echoes the sequence number of the packet being acknowledged.

   Link state advertisement headers

      This variable-length field contains a list of link state
      headers that describe a portion of the masters topological
      database.  Each header uniquely identifies a link state
      advertisement and its current instance.  (See Section 14.1
      for a detailed description of a link state advertisement
      header.)  The number of headers included in the list is
      calculated implicitly from the length of the packet, as
      stored in the VLSP packet header (see Section 13.3).









L. Kane, et. al.                                           [Page 78]


I/D               VLS Protocol Specification            May 1997


13.5.3  Link State Request Packets

   Link State Request packets are used to request those pieces of
   the neighbor's database that the sending switch has discovered
   (during the database exchange process) are more up-to-date than
   instances in its own database.  Link State Request packets are
   sent as the last step in bringing up an adjacency.  (See
   Section 10.3.)

   The format of a Link State Request packet is shown below.


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
00 |                                                               |
   :              Network layer addressing / VLSP header           :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
66 |                        Link state type                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
70 |                                                               |
   +                         Link state ID                         +
74 |                                                               |
   +                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
78 |                               |                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
82 |                                                               |
   +                      Advertising switch ID                    +
86 |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
90 |                                                               |
   :                            . . .                              :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Network layer addressing / VLSP header

      This 66-octet field contains the network layer addressing
      information and the standard VLS protocol packet header.
      The packet header type field contains a value of 3.

   Link state type

      This 4-octet field contains the link state type of the
      requested link state advertisement, as stored in the
      advertisement header.






L. Kane, et. al.                                           [Page 79]


I/D               VLS Protocol Specification            May 1997


   Link state ID

      This 10-octet field contains the link state ID of the
      requested link state advertisement, as stored in the
      advertisement header.

   Advertising switch

      This 10-octet field contains the switch ID of advertising
      switch for the requested link state advertisement, as stored
      in the advertisement header.

   Note that the last three fields uniquely identify the
   advertisement, but not its instance.  The receiving switch will
   respond with its most recent instance of the specified
   advertisement.

   Multiple link state advertisements can be requested in a single
   Link State Request packet by repeating the link state type, ID,
   and advertising switch for each requested advertisement.  The
   number of advertisements requested is calculated implicitly
   from the length of the packet, as stored in the VLSP packet
   header.


13.5.4  Link State Update Packets

   Link State Update packets are used to respond to a Link State
   Request packet or to advertise a new instance of one or more
   link state advertisements.  Link State Update packets are
   acknowledged with Link State Acknowledgment packets.  For more
   information on the use of Link State Update packets, see
   Section 10 and Section 11.

   The format of a Link State Update packet is shown below.


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
00 |                                                               |
   :              Network layer addressing / VLSP header           :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
66 |                        # advertisements                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
70 |                                                               |
   +                                                               +
   :                    Link state advertisements                  :
   +                                                               +
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


L. Kane, et. al.                                           [Page 80]


I/D                 VLS Protocol Specification            May 1997


   Network layer addressing / VLSP header

      This 66-octet field contains the network layer addressing
      information and the standard VLS protocol packet header.
      The packet header type field contains a value of 4.

   # advertisements

      This 4-octet field contains the number of link state
      advertisements included in the packet.

   Link state advertisements

      This variable-length field contains a list of link state
      advertisements.  For a detailed description of the different
      types of link state advertisements, see Section 14.


13.5.5  Link State Acknowledgment Packets

   Link State Acknowledgment Packets are used to explicitly
   acknowledge one or more Link State Update packets, thereby
   making the distribution of link state advertisements reliable.
   (See Section 11.2.6.)

   The format of a Link State Acknowledgment packet is shown
   below.


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
00 |                                                               |
   :              Network layer addressing / VLSP header           :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
66 |                                                               |
   +                                                               +
   :                 Link state advertisement headers              :
   +                                                               +
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Network layer addressing / VLSP header

      This 66-octet field contains the network layer addressing
      information and the standard VLS protocol packet header.
      The packet header type field contains a value of 5.





L. Kane, et. al.                                           [Page 81]


I/D                 VLS Protocol Specification            May 1997


   Link state advertisement headers

      This variable-length field contains a list of link state
      headers that are being acknowledged by this packet.  Each
      header uniquely identifies a link state advertisement and
      its current instance.  (See Section 14.1 for a detailed
      description of a link state advertisement header.)  The
      number of headers included in the list is calculated
      implicitly from the length of the packet, as stored in the
      VLSP packet header (see Section 13.3).


14.  Link State Advertisement Formats

   Link state advertisements are used to describe various pieces
   of the routing topology within the switch fabric.  Each switch
   in the fabric maintains a complete set of all link state
   advertisements generated throughout the fabric.  (Section 11.1
   describes the circumstances under which a link state
   advertisement is originated.  Section 11.2 describes how
   advertisements are distributed throughout the switch fabric.)
   This collection of advertisements, known as the link state (or
   topological) database, is used to build the switchs routing
   table and calculate a set of best paths to all other switches
   in the fabric.

   There are two types of link state advertisement, as listed in
   Table 8.


      Type   Name              Function                    Section

      1      Switch link       Lists all network links
             advertisement     attached to a switch        14.2

      2      Network link      Lists all adjacencies on
             advertisement     a network link              14.3

               Table 8: Link State Advertisement Types


   Each link state advertisement begins with a standard header,
   described in Section 14.1.


14.1  Link State Advertisement Headers

   All link state advertisements begin with a common 32-octet
   header.  This header contains information that uniquely
   identifies the advertisement -- its type, link state ID, and
   the switch ID of its advertising switch.  Also, since multiple
   instances of a link state advertisement can exist concurrently


L. Kane, et. al.                                           [Page 82]


I/D                 VLS Protocol Specification            May 1997


   in the switch fabric, the header contains information that
   permits a switch to determine which instance is the most recent
   -- the age, sequence number and checksum.

   The format of the link state advertisement header is shown
   below.


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
00 |              Age              |    Options    |    LS Type    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
04 |                                                               |
   +                         Link state ID                         +
08 |                                                               |
   +                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
12 |                               |                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
16 |                                                               |
   +                      Advertising switch ID                    +
20 |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
24 |                         Sequence number                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
28 |           Checksum            |             Length            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Age

      This 2-octet field contains the time, in seconds, since this
      instance of the link state advertisement was originated.

   Options

      This 1-octet field contains the optional capabilities
      supported by the advertising switch, as described in Section
      13.4.

   LS type

      This 1-octet field contains the type of the link state
      advertisement.  Possible values are:

         1   Switch link advertisement
         2   Network link advertisement







L. Kane, et. al.                                           [Page 83]


I/D               VLS Protocol Specification            May 1997


   Link state ID

      This 10-octet field identifies the switch that originates
      advertisements for the link.  The content of this field
      depends on the advertisement's type.

      -  For a switch link advertisement, this field contains the
         switch ID of the originating switch

      -  For a network link advertisement, this field contains the
         switch ID of the designated switch for the link


                                  Note

            In VLSP, the link state ID of an advertisement is
            always the same as the advertising switch.  This level
            of redundancy results from the fact that OSPF uses
            additional types of link state advertisements for
            which the originating switch is not the advertising
            switch.


   Advertising switch

      This 10-octet field contains the switch ID of the switch
      that originated the link state advertisement.

   Sequence number

      This 4-octet field is used to sequence the instances of a
      particular link state advertisement.  The number is
      incremented for each new instance.

   Checksum

      This 2-octet field contains the checksum of the complete
      contents of the link state advertisement, excluding the age
      field.  The checksum used is commonly referred to as the
      Fletcher checksum and is documented in [RFC905].  Note that
      since this checksum is calculated for each separate
      advertisement, a protocol packet containing lists of
      advertisements or advertisement headers will contain
      multiple checksum values.

   Length

      This 2-octet field contains the total length, in octets, of
      the link state advertisement, including the header.





L. Kane, et. al.                                           [Page 84]


I/D                 VLS Protocol Specification            May 1997


14.2  Switch Link Advertisements

   A switch link advertisement is used to describe all functioning
   network links of a switch, including the cost of using each
   link.

   Each functioning switch in the fabric originates one, and only
   one, switch link advertisement -- all of the switch's links
   must be described in a single advertisement.  A switch
   originates its first switch link advertisement (containing no
   links) when it first becomes functional.  It then originates a
   new instance of the advertisement each time any of its neighbor
   states changes such that the contents of the advertisement
   changes.

   The format of a switch link advertisement is shown below.


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
00 |                                                               |
   :                       Link state header                       :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
32 |      (unused - must be 0)     |            # links            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
36 |                                                               |
   +                            Link ID                            +
40 |                                                               |
   +                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
44 |                               |                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
48 |                                                               |
   +                           Link data                           +
52 |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
56 |   Link type   |     # TOS     |         TOS 0 metric          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
60 |                                                               |
   :                            . . .                              :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Link state header

      This 32-octet field contains the standard link state
      advertisement header.  The type field contains a 1, and the
      link state ID field contains the switch ID of the
      advertising switch.



L. Kane, et. al.                                           [Page 85]


I/D                 VLS Protocol Specification            May 1997


   # links

      This 2-octet field contains the number of links described by
      this advertisement.  This value must be equal to the total
      number of functioning network links attached to the switch.

   Link ID

      This 10-octet field identifies the other switch that
      originates link state advertisements for the link, providing
      a key for accessing other link state advertisements for the
      link.  The value here is based on the link type, as follow:

      -  For point-to-point links, this field contains the switch
         ID of the neighbor switch connected to the other end of
         the link.

      -  For multi-access links, this field contains the switch ID
         of the designated switch for the link.

      -  For stub links, this field does not apply.

   Link data

      This 10-octet field contains additional data necessary to
      build the routing table and calculate the set of best paths.
      Typically, this field contains the interface ID of the link.

   Link type

      This 1-octet field contains the type of link being
      described.  Possible values are as follows:

         1   Point-to-point link
         2   Multi-access link
         3   Stub link (unavailable for network traffic)

   # TOS

      This 1-octet field contains the number of nonzero type of
      service metrics specified for the link.  Since the current
      version of VLSP does not support routing based on nonzero
      types of service, this field contains a value of zero.

   TOS 0 metric

      This 2-octet field contains the cost of using this link for
      the zero TOS.  This value is expressed in the link state
      metric and must be greater than zero.

   Note that the last five fields are repeated for all functioning
   network links attached to the advertising switch.  If the


L. Kane, et. al.                                           [Page 86]


I/D                 VLS Protocol Specification            May 1997


   interface state of attached link changes, the switch must
   originate a new instance of the switch link advertisement.


14.3  Network Link Advertisements

   A network link advertisement is originated by the designated
   switch of each multi-access network link.  The advertisement
   describes all switches attached to the link that are currently
   fully adjacent to the designated switch, including the
   designated switch itself.

   Network link advertisements are not generated for point-to-
   point network links.

   The format of a network link advertisement is show below.


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
00 |                                                               |
   :                       Link state header                       :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
32 |                           (unused)                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
36 |                                                               |
   +                                                               +
   :                          Switch list                          :
   +                                                               +
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Link state header

      This 32-octet field contains the standard link state
      advertisement header.  The type field contains a 2, and the
      link state ID field contains the switch ID of the designated
      switch.

   Switch list

      The switch IDs of all switches attached to the network link
      that are currently fully adjacent to the designated switch.
      The designated switch includes itself in this list.







L. Kane, et. al.                                           [Page 87]


I/D                  VLS Protocol Specification            May 1997


15.  Protocol Parameters

   This section contains a compendium of the parameters used in
   the VLS protocol.


15.1  Architectural Constants

   Several VLS protocol parameters have fixed architectural
   values.  The name of each architectural constant follows,
   together with its value and a short description of its
   function.

   AllSPFSwitches

      The multicast switch ID to which Hello packets and certain
      other protocol packets are addressed, as specified in the
      destination switch ID field of the network layer address
      information (see Section 13.2).  The value of AllSPFSwitches
      is E0-00-00-05-00-00-00-00.

   AllDSwitches

      The multicast switch ID to which Link State Update packets
      and Link State Acknowledgment packets are addressed, as
      specified in the destination switch ID field of the network
      layer address information (see Section 13.2), when they are
      destined for the designated switch or the backup designated
      switch of a network link.  The value of AllDSwitches is
      E0-00-00-06-00-00-00-00.

   LSRefreshTime

      The interval at which the routing table is rebuilt and the
      set of best paths recalculated if no other state changes
      have forced a recalculation.  The value of LSRefreshTime is
      set to 1800 seconds (30 minutes).

   MinLSInterval

      The minimum time between distinct originations of any
      particular link state advertisement.  The value of
      MinLSInterval is set to 5 seconds.

   MaxAge

      The maximum age that a link state advertisement can attain.
      When an advertisement's age reaches MaxAge, it is
      redistributed throughout the switch fabric.  When the
      originating switch receives an acknowledgment for the
      advertisement, indicating that the advertisement has been
      removed from all neighbor Link state retransmission lists,


L. Kane, et. al.                                           [Page 88]


I/D                 VLS Protocol Specification            May 1997


      the advertisement is removed from the originating switchs
      database.  Advertisements having age MaxAge are not used in
      the routing table calculation.  The value of MaxAge must be
      greater than LSRefreshTime.  The value of MaxAge is set to
      3600 seconds (1 hour).

   MaxAgeDiff

      The maximum time disparity in ages that can occur for a
      single link state instance as it is distributed throughout
      the switch fabric.  Most of this time is accounted for by
      the time the advertisement sits on switch output queues (and
      therefore not aging) during the distribution process. The
      value of MaxAgeDiff is set to 900 seconds (15 minutes).

   LSInfinity

      The link state metric value indicating that the destination
      is unreachable.  It is defined to be a binary value of all
      ones.


15.2  Configurable Parameters

   Many of the switch interface parameters used by VLSP may be
   made configurable if the implementer so desires.  These
   parameters are listed below.  Sample default values are given
   for some of the parameters.

   Note that some of these parameters specify properties of the
   individual interfaces and their attached network links.  These
   parameters must be consistent across all the switches attached
   to that link.

   Interface output cost(s)

      The cost of sending a packet over the interface, expressed
      in the link state metric.  This is advertised as the link
      cost for this interface in the switch's switch link
      advertisement.  The interface output cost must always be
      greater than zero.

   RxmtInterval

      The number of seconds between link state advertisement
      retransmissions for adjacencies established on this
      interface.  This value is also used when retransmitting
      Database Description packets and Link State Request packets.
      This value must be greater than the expected round-trip
      delay between any two switches on the attached link.




L. Kane, et. al.                                           [Page 89]


I/D                 VLS Protocol Specification            May 1997


      However, the value should be conservative or needless
      retransmissions will result.  A typical value for a local
      area network would be 5 seconds.

   InfTransDelay

      The estimated number of seconds it takes to transmit a Link
      State Update packet over this interface.  Link state
      advertisements contained in the Link State Update packet
      must have their age incremented by this amount before
      transmission.  This value must take into account the
      transmission and propagation delays for the interface and
      must be greater than zero.  A typical value for a local area
      network would be 1 second.

   Switch priority

      An 8-bit unsigned integer.  When two switches attached to
      the same network link contend for selection as the
      designated switch, the switch with the highest priority
      takes precedence.  If both switches have the same priority,
      the switch with the highest base MAC address becomes the
      designated switch.  A switch whose switch priority is set to
      zero is ineligible to become the designated switch on the
      attached link.

   HelloInterval

      The length of time, in seconds, between the Hello packets
      that the switch sends over the interface.  This value is
      advertised in the switch's Hello packets.  It must be the
      same for all switches attached to a common network link.
      The smaller this value is set, the faster topological
      changes will be detected.  However, a smaller interval will
      also generate more routing traffic.  A typical value for a
      local area network would be 10 seconds.

   SwitchDeadInterval

      The length of time, in seconds, that neighboring switches
      will wait before declaring the interface down once they stop
      receiving Hello packets over the interface.  This value is
      advertised in the switch's Hello packets.  It must be the
      same for all switches attached to a common network link and
      should be some multiple of the HelloInterval parameter.  A
      typical value would be 4 times HelloInterval.








L. Kane, et. al.                                           [Page 90]


I/D                 VLS Protocol Specification            May 1997


Footnotes

   [1]During calculation of the routing table, a network link
      advertisement must be located based solely on its link state
      ID.  Note, however, that the lookup in this case is still well
      defined, since no two network advertisements can have the same
      link state ID.

   [2]It is instructive to see what happens when the designated
      switch for a network link fails.  Call the designated switch
      for the link S1 and the backup designated switch S2.  If
      switch S1 fails (or its interface to the link goes down), the
      other switches on the link will detect S1's absence within
      switchDeadInterval seconds.  All switches may not detect this
      condition at precisely the same time.  The switches that
      detect S1's absence before S2 does will temporarily select S2
      as both designated switch and backup designated switch.  When
      S2 detects that S1 is down, it will move itself to designated
      switch and a new backup designated switch is selected.

   [3]Note that it is possible for a switch to resynchronize any
      of its fully established adjacencies by setting the neighbor
      state back to ExStart.  This causes the switch on the other
      end of the adjacency to process a SeqNumberMismatch event and
      also revert to the ExStart state.

   [4]When two advertisements have different checksum values, they
      are assumed to be separate instances.  This can occur when a
      switch restarts and loses track of its previous sequence
      number.  In this case, since the two advertisements have the
      same sequence number, it is not possible to determine which
      advertisement is actually newer.  If the wrong advertisement
      is accepted as newer, the originating switch will originate
      another instance.

   [5]An instance of an advertisement is originated with an age of
      MaxAge only when it is to be flushed from the database.  This
      is done either when the advertisement has naturally aged to
      MaxAge, or (more typically) when the sequence number must
      wrap.  Therefore, a received instance with an age of MaxAge
      must be processed as the most recent in order to flush it
      properly from the database.

   [6]MaxAgeDiff is an architectural constant that defines the
      maximum disparity in ages, in seconds, that can occur for a
      single link state instance as it is distributed throughout the
      switch fabric.  If two advertisements differ by more than this
      amount, they are assumed to be different instances of the same
      advertisement.  This can occur when a switch restarts and
      loses track of its previous sequence number.




L. Kane, et. al.                                           [Page 91]


I/D                 VLS Protocol Specification            May 1997


   [7]This is how the link state request list is emptied, causing
      the neighbor state to change to Full.


References

   [Perlman]   Perlman, Radia.  Interconnections: Bridges and
               Routers.  Addison-Wesley Publishing Company.  1992.

   [RFC905]    McKenzie, A., ISO Transport Protocol specification
               ISO DP 8073. April 1984.

   [RFC1583]   Moy, J.  OSPF Version 2.  March 1994.

   [RFC1700]   Reynolds, S.J., Postel, J.  Assigned Numbers.
               October 1994.

   [RFCxxxx]   Dobbins, K., et. al.  ARLD Protocol Specification

   [RFCxxxx]   Dobbins, K., et. al.  LSMP Protocol Specification

   [RFCxxxx]   Dobbins, K., et. al.  SBCD Protocol Specification

   [RFCxxxx]   Dobbins, K., et. al.  SFCT Protocol Specification

   [RFCxxxx]   Dobbins, K., et. al.  SNDM Protocol Specification


Security Considerations

   Security issues are not discussed in this document.


Authors Addresses

   Cabletron Systems, Inc., is located at:

      Post Office Box 5005
      Rochester, NH  03866-5005
      (603) 332-9400

   Laura Kane         Email:  lkane@ctron.com
   Kurt Dobbins       Email:  dobbins@ctron.com
   Rich Soczewinski   Email:  soczew@ctron.com










L. Kane, et. al.                                           [Page 92]

INTERNET-DRAFT           EXPIRES: NOVEMBER 1997        INTERNET-DRAFT