RFC2642 - Cabletrons VLS Protocol Specification

Network Working Group L. Kane
Request for Comments: 2642 Cabletron Systems Incorporated
Category: Informational August 1999
Cabletron"s VLS Protocol Specification
Status of this Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (1999). All Rights Reserved.
Abstract
The Virtual LAN Link State Protocol (VLSP) is part of the InterSwitch
Message Protocol (ISMP) which provides interswitch communication
between switches running Cabletron"s SecureFast VLAN (SFVLAN)
prodUCt. 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
1. Introduction............................................ 3
1.1 Acknowledgments..................................... 3
1.2 Data Conventions.................................... 3
1.3 ISMP Overview....................................... 4
2. VLS Protocol Overview................................... 5
2.1 Definitions of Commonly Used Terms.................. 6
2.2 Differences Between VLSP and OSPF................... 7
2.2.1 Operation at the Physical Layer............... 8
2.2.2 All Links Treated as Point-to-Point........... 8
2.2.3 Routing Path Information...................... 9
2.2.4 Configurable Parameters....................... 9
2.2.5 Features Not supported........................ 9
2.3 Functional Summary.................................. 10
2.4 Protocol Packets.................................... 11
2.5 Protocol Data Structures............................ 12
2.6 Basic Implementation Requirements................... 12
2.7 Organization of the Remainder of This Document...... 13
3. Interface Data Structure................................ 14
3.1 Interface States.................................... 16
3.2 Events Causing Interface State Changes.............. 18
3.3 Interface State Machine............................. 21
4. Neighbor Data Structure................................. 23
4.1 Neighbor States..................................... 25
4.2 Events Causing Neighbor State Changes............... 27
4.3 Neighbor State Machine.............................. 29
5. Area Data Structure..................................... 33
5.1 Adding and Deleting Link State Advertisements....... 34
5.2 Accessing Link State Advertisements................. 35
5.3 Best Path Lookup.................................... 35
6. Discovery Process....................................... 35
6.1 Neighbor Discovery.................................. 36
6.2 Bidirectional Communication......................... 37
6.3 Designated Switch................................... 38
6.3.1 Selecting the Designated Switch............... 39
6.4 Adjacencies......................................... 41
7. Synchronizing the Databases............................. 42
7.1 Link State Advertisements........................... 43
7.1.1 Determining Which
Link State Advertisement Is Newer............. 44
7.2 Database Exchange Process........................... 44
7.2.1 Database Description Packets.................. 44
7.2.2 Negotiating the Master/Slave Relationship..... 45
7.2.3 Exchanging Database Description Packets....... 46
7.3 Updating the Database............................... 48
7.4 An Example.......................................... 49
8. Maintaining the Databases............................... 51
8.1 Originating Link State Advertisements............... 52
8.1.1 Switch Link Advertisements.................... 52
8.1.2 Network Link Advertisements................... 55
8.2 Distributing Link State Advertisements.............. 56
8.2.1 Overview...................................... 57
8.2.2 Processing an
Incoming Link State Update Packet............. 58
8.2.3 Forwarding Link State Advertisements.......... 60
8.2.4 Installing Link
State Advertisements in the Database.......... 62
8.2.5 Retransmitting Link State Advertisements...... 63
8.2.6 Acknowledging Link State Advertisements....... 64
8.3 Aging the Link State Database....................... 66
8.3.1 Premature Aging of Advertisements............. 66
9. Calculating the Best Paths.............................. 67
10. Protocol Packets........................................ 67
10.1 ISMP Packet Format................................. 68
10.1.1 Frame Header................................ 69
10.1.2 ISMP Packet Header.......................... 70
10.1.3 ISMP Message Body........................... 71
10.2 VLSP Packet Processing............................. 71
10.3 Network Layer Address Information.................. 72
10.4 VLSP Packet Header................................. 73
10.5 Options Field...................................... 75
10.6 Packet Formats..................................... 76
10.6.1 Hello Packets............................... 76
10.6.2 Database Description Packets................ 78
10.6.3 Link State Request Packets.................. 80
10.6.4 Link State Update Packets................... 82
10.6.5 Link State Acknowledgment Packets........... 83
11. Link State Advertisement Formats........................ 84
11.1 Link State Advertisement Headers................... 84
11.2 Switch Link Advertisements......................... 86
11.3 Network Link Advertisements........................ 89
12. Protocol Parameters..................................... 89
12.1 Architectural Constants............................ 90
12.2 Configurable Parameters............................ 91
13. End Notes............................................... 93
14. Security Considerations................................. 94
15. References.............................................. 94
16. Author"s Address........................................ 94
17. Full Copyright Statement................................ 95
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 [RFC2328], written by John Moy, formerly of Proteon, Inc.,
Westborough, Massachusetts. Much of the current memo has been drawn
from [RFC2328]. Therefore, this author wishes to acknowledge the
contribution Mr. Moy has (unknowingly) made to this document.
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.
1.3 ISMP Overview
The InterSwitch Message Protocol (ISMP) provides a consistent method
of encapsulating and transmitting control messages exchanged between
switches running Cabletron"s SecureFast VLAN (SFVLAN) product, as
described in [IDsfvlan]. ISMP provides the following services:
o Topology services. Each switch maintains a distributed topology
of the switch fabric by exchanging the following interswitch
control messages with other switches:
o Interswitch Keepalive messages are sent by each switch to announce
its existence to its neighboring switches and to establish the
topology of the switch fabric. (Interswitch Keepalive messages
are exchanged in accordance with Cabletron"s VlanHello protocol,
described in [IDhello].)
o Interswitch Spanning Tree BPDU messages and Interswitch Remote
Blocking messages 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 that are (potentially) sent to all switches in the switch
fabric.
o 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.
o Address resolution services. Interswitch Resolve messages 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 are used to provide end-station
address mobility between switches.
o Tag-based flooding. A tag-based broadcast method 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.
o Call tapping services. Interswitch Tap messages are used to
monitor traffic moving between two end stations. Traffic can be
monitored in one or both directions along the connection path.
Note: Previous versions of VLSP treated all links as if they were
broadcast (multi-access). Thus, if VLSP determines that a neighbor
switch is running an older version of the protocol software (see
Section 6.1), it will change the interface type to broadcast and
begin exchanging Hello packets with the single neighbor switch.
2. 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 switch"s 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.
2.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:
o Point-to-point links that join a single pair of switches. A
serial line is an example of a point-to-point network link.
o 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. At startup,
all links are assumed to be point-to-point. A link is
determined to be multi-access when more than one neighboring
switch is discovered on the link.
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.
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.
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 selected during the discovery process. 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. This optimizes the
failover time when the backup designated switch must take over for
the (failed) designated switch.
The backup designated switch is selected during the Discovery
process. A backup designated switch is not selected for a point-
to-point network link.
2.2 Differences Between VLSP and OSPF
The VLS protocol is derived from the OSPF link-state routing protocol
described in [RFC2328].
2.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:
o VLSP does not support features (such as fragmentation) that are
typically provided by network layer service providers.
o 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.
o As mentioned in Section 10.1.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 10.3). This information is
unbundled and packets are then processed as if they had been sent
or received on that multicast address.
2.2.2 All Links Treated as Point-to-Point
When the switch first comes on line, VLSP assumes all network links
are point-to-point and no more than one neighboring switch will be
discovered on any one port. Therefore, at startup, VLSP does not
send its own Hello packets over its network ports, but instead,
relies on the VlanHello protocol [IDhello] for the discovery of its
neighbor switches. If a second neighbor is detected on a link, the
link is then deemed multi-access and the interface type is changed to
broadcast. At that point, VLSP exchanges its own Hello packets with
the switches on the link in order to select a designated switch and
designated backup switch for the link.
This method eliminates unnecessary duplication of message traffic and
processing, thereby increasing the overall efficiency of the switch
fabric.
Note: Previous versions of VLSP treated all links as if they were
broadcast (multi-access). Thus, if VLSP determines that a neighbor
switch is running an older version of the protocol software (see
Section 6.1), it will change the interface type to broadcast and
begin exchanging Hello packets with the single neighbor switch.
2.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.
2.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:
o All switches are assigned a switch priority of 1. This forces the
selection of the designated switch to be based solely on base MAC
address.
o Authentication is not supported.
2.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:
o Periodic refresh of link state advertisements. (This optimizes
performance by eliminating unnecessary traffic between the
switches.)
o Routing based on non-zero type of service (TOS).
o Use of external routing information for destinations outside the
switch fabric.
2.3 Functional Summary
There are essentially four operational stages of the VLS protocol.
o Discovery Process The discovery process involves two steps:
o Neighboring switches are detected by the VlanHello protocol
[IDhello] which then notifies VLSP of the neighbor.
o If more than one neighbor switch is detected on a single port,
the link is determined to be multi-access. VLSP then sends its
own Hello packets over the link in order to discover the full
set of neighbors on the link and select a designated switch and
designated backup switch for the link. Note that this
selection process is unnecessary on point-to-point links.
The discovery process is described in more detail in Section 6.
o 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.
The process of synchronizing the databases is described in more
detail in Section 7.
o 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.
The process of maintaining the databases is described in more
detail in Section 8.
o Calculating the Best Paths
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.
The process of recalculating the set of best paths is described in
more detail in Section 9.
2.4 Protocol Packets
In addition to the frame header and the ISMP packet header described
in Section 10.1, all VLS protocol packets share a common protocol
header, described in Section 10.4.
The VLSP packet types are listed below in Table 1. Their formats are
described in Section 10.6.
Type Packet Name Protocol Function
1 Hello Select DS and Backup DS
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 select the designated switch and the
backup designated switch on multi-access links. 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
2.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 3
Neighbor Data Structure Section 4
Area Data Structure Section 5
Table 3: VLSP Data Structures
2.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.
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.
2.7 Organization of the Remainder of This Document
The remainder of this document is organized as follows:
o Section 3 through Section 5 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.
o Section 6 through Section 9 describe the four operational stages
of the protocol: the discovery process, synchronizing the
databases, maintaining the databases, and calculating the set of
best paths.
o Section 10 describes the processing of VLSP packets and presents
detailed descriptions of their formats.
o Section 11 presents detailed descriptions of link state
advertisements.
o Section 12 summarizes the protocol parameters.
3. 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). This data item is
initialized to point-to-point when the interface becomes
operational. If a second neighbor is detected on the link after
the first neighbor has been discovered, the link interface type is
changed to broadcast. The type remains as broadcast until the
interface is declared down, at which time the type reverts to
point-to-point.
Note: Previous versions of VLSP treated all links as if they were
multi-access. Thus, if VLSP determines that a neighbor switch is
running an older version of the protocol software (see Section 6.1),
it will change the interface type to broadcast.
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 3.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 VLSP Hello
packets over the interface. This parameter is not used on point-
to-point links.
SwitchDeadInterval
The length of time, in seconds, that neighboring switches will
wait before declaring the local switch dNeighboring switches
A list of the neighboring switches attached to this network link.
This list is created during the discovery process. 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.
3.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 3.2. The interface state machine is described
in detail in Section 3.3.
Down
This is the initial state of the interface. In this state, 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.
+-------+
any Interface +----------+ Unloop Ind +----------+
state -----------> Down <----------- Loopback
+-------+ Down +----------+ +----------+
^
Interface Up
+-------+ [pt-to-pt]
Point <------------type? Loop Ind
to
Point [broadcast]
+-------+ V +-------+
+-----------+ any
Waiting state
+-----------+ +-------+

Backup Seen
Wait Timer


+----------+ Neighbor V Neighbor +----------+
DS <------------> [ ] <------------> DS Other
+----------+ Change ^ Change +----------+


Neighbor Change

V
+----------+
Backup
+----------+
Figure 1: Interface State Machine
Loopback
In this state, the switch interface is looped back, either in
hardware or in software. The interface is unavailable for regular
data traffic.
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.
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.
DS Other
In this state, the interface is operational and is connected to a
multi-access broadcast 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.
Backup
In this state, the switch itself is the backup designated switch
on the attached multi-access broadcast 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 6.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 multi-access broadcast 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 6.3 for more information on the functions performed
by the designated switch.)
3.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 3.3.
Interface Up
This event is generated by the VlanHello protocol [IDhello] when
it discovers a neighbor switch on the interface. The interface is
now operational. This event causes the interface to change out of
the Down state. The state it enters is determined by the
interface type. If the interface type is broadcast (multi-
access), this event also causes the switch to begin sending
periodic Hello packets out over the interface.
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 on a multi-access link.
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:
o A Hello packet has been received from a neighbor that claims to
be the backup designated switch.
o 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 4.1 for information on neighbor states.)
o Bidirectional communication has been established with a
neighbor -- the state of the neighbor has changed to 2-Way or
higher.
o Bidirectional communication with a neighbor has been lost --
the state of the neighbor has changed to Init or lower.
o A bidirectional neighbor has just declared itself to be either
the designated switch or the backup designated switch, as
detected by examination of that neighbor"s Hello packets.
o 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.
o 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.
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 under the following two circumstances:
o The VlanHello [IDhello] protocol has determined that the
interface is no longer functional.
o The neighbor state machine has detected a second neighboring
switch on a link presumed to be of type point-to-point. In
addition to generating the Interface Down event, the
neighbor state machine changes the interface type to
broadcast.
In both instances, this event forces the interface state to Down.
However, when the event is generated by the neighbor state
machine, it is immediately followed by an Interface Up event.
(See Section 4.3.)
3.3 Interface State Machine
This section presents a detailed description of the interface state
machine.
Interface states (see Section 3.1) change as the result of various
events (see Section 3.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 8.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 4.3.
State(s): Down
Event: Interface Up
New state: Depends on action routine
Action:
If the interface is a point-to-point link, set the interface state
to Point-to-Point. Otherwise, start the Hello interval timer,
enabling the periodic sending of Hello packets over the interface.
If the switch is not eligible to become the designated switch,
change the interface state to DS Other. Otherwise, set the
interface state to Waiting and start the one-shot wait timer.
Create a new neighbor data structure for the neighbor switch,
initialize all neighbor parameters and set the stateof the
neighbor to Down.
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 6.3.1. As a result of this
selection, set the new state of the interface to 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 6.3.1. As a result of this
selection, set the new state of the interface to 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 6.3.1. As a result of
this selection, set the new state of the interface to either DS
Other, Backup or DS.
State(s): Any State
Event: Interface Down
New state: Down
Action:
Reset all variables in the interface data structure and disable
all timers. In addition, destroy all neighbor connections
associated with the interface 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:
Reset all variables in the interface data structure and disable
all timers. In addition, destroy all neighbor connections
associated with the interface by 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.
4. Neighbor Data Structure
Each switch conducts a conversation with its neighboring switches and
each conversation is described by a neighbor data structure. A
conversation is associated with a switch interface, and is identified
by the neighboring switch ID.
Note that if two switches have multiple attached links in common,
multiple conversations ensue, each described by a unique neighbor
data structure. Each separate conversation is treated as a separate
neighbor.
The neighbor data structure contains all information relevant to any
adjacency formed between the two neighbors. Remember, however, that
not all neighbors become adjacent. An adjacency can be thought of as
a highly developed conversation between two switches.
State
The functional level of the neighbor conversation. See Section
4.1 for a complete description of neighbor states.
Inactivity timer
A one-shot timer used to determine when to declare the neighbor
down if no Hello packet is received from this (multi-access)
neighbor. The length of the timer is SwitchDeadInterval seconds,
as contained in the neighbor"s Hello packet. This timer is not
used on point-to-point links.
Master/slave flag
A flag indicating whether the local switch is to act as the master
or the slave in the database exchange process (see Section 7.2).
The master/slave relationship is negotiated when the conversation
changes to the ExStart state.
Sequence number
A 4-octet number identifying individual Database Description
packets. When the neighbor state ExStart is entered and the
database exchange process is started, the sequence number is set
to a value not previously seen by the neighboring switch. (One
possible scheme is to use the switch"s time of day counter.) The
sequence number is then incremented by the master with each new
Database Description packet sent. See Section 7.2 for more
information on the database exchange process.
Neighbor ID
The switch ID of the neighboring switch, as discovered by the
VlanHello protocol [IDhello] or contained in the neighbor"s Hello
packets.
Neighbor priority
The switch priority of the neighboring switch, as contained in the
neighbor"s Hello packets. Switch priorities are used when
selecting the designated switch for the attached multi-access
link. Priority is not used on point-to-point links.
Interface identifier
A 10-octet value that uniquely identifies the interface over which
this conversation is being held. This value consists of the 6-
octet base MAC address of the neighbor switch, followed by the 4-
octet local port number of the interface.
Neighbor"s designated switch
The switch ID identifying the neighbor"s idea of the designated
switch, as contained in the neighbor"s Hello packets. This value
is used in the local selection of the designated switch. It is
not used on point-to-point links.
Neighbor"s backup designated switch
The switch ID identifying the neighbor"s idea of the backup
designated switch, as contained in the neighbor"s Hello packets.
This value is used in the local selection of the backup designated
switch. It is not used on point-to-point links.
Link state retransmission list
The list of link state advertisements that have been forwarded
over but not acknowledged on this adjacency. The local switch
retransmits these link state advertisements at periodic intervals
until they are acknowledged or until the adjacency is destroyed.
(For more information on retransmitting link state advertisements,
see Section 8.2.5.)
Database summary list
The set of link state advertisement headers that summarize the
local link state database. When the conversation changes to the
Exchange state, this list is sent to the neighbor via Database
Description packets. (For more information on the synchronization
of databases, see Section 7.)
Link state request list
The list of link state advertisements that must be received in
order to synchronize with the neighbor switch"s link state
database. This list is created as Database Description packets
are received, and is then sent to the neighbor in Link State
Request packets. (For more information on the synchronization of
databases, see Section 7.)
4.1 Neighbor States
This section describes the various states of a conversation with a
neighbor switch. The states are listed in order of progressing
functionality. For example, the inoperative state is listed first,
followed by a list of the intermediate states through which the
conversation passes before attaining the final, fully functional
state. The specification makes use of this ordering by references
such as "those neighbors/adjacencies in state greater than X".
Figure 2 represents the neighbor state machine. The arrows on the
graph represent the events causing each state change. These events
are described in Section 4.2. The neighbor state machine is
described in detail in Section 4.3.
Down
This is the initial state of a neighbor conversation.
Init
In this state, the neighbor has been discovered, but bidirectional
communication has not yet been established. All neighbors in this
state or higher are listed in the VLS Hello packets sent by the
local switch over the associated (multi-access) interface.
+----------+ KillNbr, LLDown, +-----------+
Down <--------------------- any state
+----------+ or Inactivity Timer +-----------+

Hello
Rcvd

V
+-----< [pt-to-pt?]
yes
no
V
+----------+ 1-Way +----------+
Init <-------- >= 2-way
+----------+ +----------+

2-Way
Rcvd +-------+ AdjOK? +------------+
+----------------> 2-Way <------- >= ExStart
(no adjacency) +-------+ no +------------+

V
+---------+ Seq Number Mismatch +-------------+
+----> ExStart <--------------------- >= Exchange
+---------+ or BadLSReq +-------------+

Negotiation
Done
V
+----------+
Exchange
+----------+

Exchange +--------+
Done +----------------------> Full
(request list empty) +--------+
^
V
+---------+ Loading Done
Loading ----------------------->
+---------+
Figure 2: Neighbor State Machine
2-Way
In this state, communication between the two switches is
bidirectional. This is the most advanced state short of beginning
to establish an adjacency. On a multi-access link, the designated
switch and the backup designated switch are selected from the set
of neighbors in state 2-Way or greater.
ExStart
This state indicates that the two switches have begun to establish
an adjacency by determining which switch is the master, as well as
the initial sequence number for Database Descriptor packets.
Neighbor conversations in this state or greater are called
adjacencies.
Exchange
In this state, the switches are exchanging Database Description
packets. (See Section 7.2 for a complete description of this
process.) All adjacencies in the Exchange state or greater are
used by the distribution procedure (see Section 8.2), and are
capable of transmitting and receiving all types of VLSP routing
packets.
Loading
In this state, the local switch is sending Link State Request
packets to the neighbor asking for the more recent advertisements
that were discovered in the Exchange state.
Full
In this state, the two switches are fully adjacent. These
adjacencies will now appear in switch link and network link
advertisements generated for the link.
4.2 Events Causing Neighbor State Changes
The state of a neighbor conversation changes due to neighbor events.
This section describes these events.
Neighbor events are shown as arrows in Figure 2, the graphic
representation of the neighbor state machine. For more information
on the neighbor state machine, see Section 4.3.
Hello Received
This event is generated when a Hello packet has been received from
a neighbor.
2-Way Received
This event is generated when the local switch sees its own switch
ID listed in the neighbor"s Hello packet, indicating that
bidirectional communication has been established between the two
switches.
Negotiation Done
This event is generated when the master/slave relationship has
been successfully negotiated and initial packet sequence numbers
have been exchanged. This event signals the start of the database
exchange process (see Section 7.2).
Exchange Done
This event is generated when the database exchange process is
complete and both switches have successfully transmitted a full
sequence of Database Description packets. (For more information
on the database exchange process, see Section 7.2.)
BadLSReq
This event is generated when a Link State Request has been
received for a link state advertisement that is not contained in
the database. This event indicates an error in the
synchronization process.
Loading Done
This event is generated when all Link State Updates have been
received for all out-of-date portions of the database. (See
Section 7.3.)
AdjOK?
This event is generated when a decision must be made as to whether
an adjacency will be established or maintained with the neighbor.
This event will initiate some adjacencies and destroy others.
Seq Number Mismatch
This event is generated when a Database Description packet has
been received with any of the following conditions:
o The packet contains an unexpected sequence number.
o The packet (unexpectedly) has the Init bit set.
o The packet has a different Options field than was
previously seen.
These conditions all indicate that an error has occurred during
the establishment of the adjacency.
1-Way
This event is generated when bidirectional communication with the
neighbor has been lost. That is, a Hello packet has been received
from the neighbor in which the local switch is not listed.
KillNbr
This event is generated when further communication with the
neighbor is impossible.
Inactivity Timer
This event is generated when the inactivity timer has expired,
indicating that no Hello packets have been received from the
neighbor in SwitchDeadInterval seconds. This timer is used only
on broadcast (multi-access) links.
LLDown
This event is generated by the lower-level switch discovery
protocols and indicates that the neighbor is now unreachable.
4.3 Neighbor State Machine
This section presents a detailed description of the neighbor state
machine.
Neighbor states (see Section 4.1) change as the result of various
events (see Section 4.2). However, the effect of each event can
vary, depending on the current state of the conversation with the
neighbor. For this reason, the state machine described in this
section is organized according to the current neighbor state and the
occurring event. For each state/event pair, the new neighbor state
is listed, along with a description of the required processing.
Note that when the neighbor state changes as a result of an interface
Neighbor Change event (see Section 3.2), it may be necessary to rerun
the designated switch selection algorithm. In addition, if the
interface associated with the neighbor conversation is in the DS
state (that is, the local switch is the designated switch), changes
in the neighbor state may cause a new network link advertisement to
be originated (see Section 8.1).
When the neighbor state machine must invoke the interface state
machine, it is invoked as a scheduled task. This simplifies
processing, by ensuring that neither state machine executes
recursively.
State(s): Down
Event: Hello Received
New state: Depends on the interface type
Action:
If the interface type of the associated link is point-to-point,
change the neighbor state to ExStart. Otherwise, change the
neighbor state to Init and start the inactivity timer for the
neighbor. If the timer expires before another Hello packet is
received, the neighbor switch is declared dead.
State(s): Init or greater
Event: Hello Received
New state: No state change
Action:
If the interface type of the associated link is point-to-point,
determine whether this notification is for a different neighbor
than the one previously seen. If so, generate an Interface Down
event for the associated interface, reset the interface type to
broadcast and generate an Interface Up event.
Note: This procedure of generating an Interface Down event and
changing the interface type to broadcast is also executed if the
neighbor for whom the notification was received is running an older
version of the protocol software (see Section 6.1). In previous
versions of the protocol, all interfaces were treated as if they were
broadcast.
If the interface type is broadcast, reset the inactivity timer for
the neighbor.
State(s): Init
Event: 2-Way Received
New state: Depends on action routine
Action:
Determine whether an adjacency will be formed with the neighbor
(see Section 6.4). If no adjacency is to be formed, change the
neighbor state to 2-Way.
Otherwise, change the neighbor state to ExStart. Initialize the
sequence number for this neighbor and declare the local switch to
be master for the database exchange process. (See Section 7.2.)
State(s): ExStart
Event: Negotiation Done
New state: Exchange
Action:
The Negotiation Done event signals the start of the database
exchange process. See Section 7.2 for a detailed description of
this process.
State(s): Exchange
Event: Exchange Done
New state: Depends on action routine
Action:
If the neighbor Link state request list is empty, change the
neighbor state to Full. This is the adjacency"s final state.
Otherwise, change the neighbor state to Loading. Begin sending
Link State Request packets to the neighbor requesting the most
recent link state advertisements, as discovered during the
database exchange process. (See Section 7.2.) These
advertisements are listed in the link state request list
associated with the neighbor.
State(s): Loading
Event: Loading Done
New state: Full
Action:
No action is required beyond changing the neighbor state to Full.
This is the adjacency"s final state.
State(s): 2-Way
Event: AdjOK?
New state: Depends on action routine
Action:
If no adjacency is to be formed with the neighboring switch (see
Section 6.4), retain the neighbor state at 2-Way. Otherwise,
change the neighbor state to ExStart. Initialize the sequence
number for this neighbor and declare the local switch to be master
for the database exchange process. (See Section 7.2.)
State(s): ExStart or greater
Event: AdjOK?
New state: Depends on action routine
Action:
If an adjacency should still be formed with the neighboring switch
(see Section 6.4), no state change and no further action is
necessary. Otherwise, tear down the (possibly partially formed)
adjacency. Clear the link state retransmission list, database
summary list and link state request list and change the neighbor
state to 2-Way.
State(s): Exchange or greater
Event: Seq Number Mismatch
New state: ExStart
Action:
Tear down the (possibly partially formed) adjacency. Clear the
link state retransmission list, database summary list and link
state request list. Change the neighbor state to ExStart and make
another attempt to establish the adjacency.
State(s): Exchange or greater
Event: BadLSReq
New state: ExStart
Action:
Tear down the (possibly partially formed) adjacency. Clear the
link state retransmission list, database summary list and link
state request list. Change the neighbor state to ExStart and make
another attempt to establish the adjacency.
State(s): Any state
Event: KillNbr
New state: Down
Action:
Terminate the neighbor conversation. Disable the inactivity timer
and clear the link state retransmission list, database summary
list and link state request list.
State(s): Any state
Event: LLDown
New state: Down
Action:
Terminate the neighbor conversation. Disable the inactivity timer
and clear the link state retransmission list, database summary
list and link state request list.
State(s): Any state
Event: Inactivity Timer
New state: Down
Action:
Terminate the neighbor conversation. Disable the inactivity timer
and clear the link state retransmission list, database summary
list and link state request list.
State(s): 2-Way or greater
Event: 1-Way Received
New state: Init
Action:
Tear down the adjacency between the switches, if any. Clear the
link state retransmission list, database summary list and link
state request list.
State(s): 2-Way or greater
Event: 2-Way received
New state: No state change
Action:
No action required.
State(s): Init
Event: 1-Way received
New state: No state change
Action:
No action required.
5. Area Data Structure
The area data structure contains all the information needed to run
the basic routing algorithm. One of its components is the link state
database -- the collection of all switch link and network link
advertisements generated by the switches.
The area data structure contains the following items:
Area ID
A 4-octet value identifying the area. Since VLSP does not support
multiple areas, the value here is always zero.
Associated switch interfaces
A list of interface IDs of the local switch interfaces connected
to network links.
Link state database
The collection of all current link state advertisements for the
switch fabric. This collection consists of the following:
Switch link advertisements
A list of the switch link advertisements for all switches in the
fabric. Switch link advertisements describe the state of each
switch"s interfaces.
Network link advertisements
A list of the network link advertisements for all multi-access
network links in the switch fabric. Network link advertisements
describe the set of switches currently connected to each link.
Best path(s)
A set of end-to-end hop descriptions for all equal-cost best paths
from the local switch to every other switch in the fabric. Each
hop is specified by the interface ID of the next link in the path.
Best paths are derived from the collected switch link and network
link advertisements using the Dijkstra algorithm. [Perlman]
5.1 Adding and Deleting Link State Advertisements
The link state database within the area data structure must contain,
at most, a single instance of each link state advertisement. To keep
the database current, a switch adds link state advertisements to the
database under the following conditions:
o When a link state advertisement is received during the
distribution process
o When the switch itself generates a link state advertisement
(See Section 8.2.4 for information on installing link state
advertisements.)
Likewise, a switch deletes link state advertisements from the
database under the following conditions:
o When a link state advertisement has been superseded by a newer
instance during the flooding process
o When the switch generates a newer instance of one of its self-
originated advertisements
Note that when an advertisement is deleted from the link state
database, it must also be removed from the link state retransmission
list of all neighboring switches.
5.2 Accessing Link State Advertisements
An implementation of the VLS protocol must provide access to
individual link state advertisements, based on the advertisement"s
type, link state identifier, and advertising switch [1]. This lookup
function is invoked during the link state distribution procedure and
during calculation of the set of best paths. In addition, a switch
can use the function to determine whether it has originated a
particular link state advertisement, and if so, with what sequence
number.
5.3 Best Path Lookup
An implementation of the VLS protocol must provide access to multiple
equal-cost best paths, based on the base MAC addresses of the source
and destination switches. This lookup function should return up to
three equal-cost paths. Paths should be returned as lists of end-
to-end hop information, with each hop specified as a interface ID of
the next link in the path -- the 6-octet base MAC address of the next
switch and the 4-octet local port number of the link interface.
6.