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. 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:
o Neighboring switches are detected on each functioning network
interface.
o Bidirectional communication is established with each neighbor
switch.
o A designated switch and backup designated switch are selected for
each multi-access network link.
o An adjacent relationship is established with selected neighbors on
each link.
6.1 Neighbor Discovery
When the switch first comes on line, VLSP assumes all network links
are point-to-point and no more than one neighboring switch will be
discovered on any one port. Therefore, at startup, VLSP relies on
the VlanHello protocol [IDhello] for the discovery of its neighbor
switches.
As each neighbor is detected, VlanHello triggers a Found Neighbor
event, notifying VLSP that a new neighbor has been discovered. (See
[IDhello] for a description of the Found Neighbor event and the
information passed.) VLSP enters the neighbor switch ID in the list
of known neighbors and creates a new neighbor data structure with a
neighbor status of Down. A Hello Received neighbor event is then
generated, which changes the neighbor state to ExStart.
There are two circumstances under which VLSP will change the type of
an interface to broadcast:
o If VLSP receives a subsequent notification from VlanHello,
specifying a second (different) neighbor switch on the port., the
interface is then known to be multi-access. VLSP generates an
Interface Down event for the interface, resets the interface type
to broadcast, and then generates an Interface Up event.
o If the functional level of the neighbor switch is less than 2, the
neighbor is running a previous version of the VLSP software in
which all links were treated as broadcast links. VLSP immediately
changes the interface type to broadcast and generates an Interface
Up event.
In both cases, VLSP assumes control of communication over the
interface by exchanging its own VLSP Hello packets with the
neighbors on the link.
Note: These Hello packets are in addition to the Interswitch
Keepalive messages sent by VlanHello. VlanHello still continues to
monitor the condition of the interface and notifies VLSP of any
change.
Each Hello packet contains the following data used during the
discovery process on multi-access links:
o The switch ID and priority of the sending switch
o Values specifying the interval timers to be used for sending Hello
packets and deciding whether to declare a neighbor switch Down.
o The switch ID of the designated switch and the backup designated
switch for the link, as understood by the sending switch
o A list of switch IDs of all neighboring switches seen so far on
the link
For a detailed description of the Hello packet format, see Section
10.6.1.
When VLSP receives a Hello packet (on a broadcast link), it first
attempts to identify the sending switch by matching its switch ID to
one of the known neighbors listed in the interface data structure.
If this is the first Hello packet received from the switch, the
switch ID is entered in the list of known neighbors and a new
neighbor data structure is created with a neighbor status of Down.
At this point, the remainder of the Hello packet is examined and the
appropriate interface and neighbor events are generated. In all
cases, a neighbor Hello Received event is generated. Other events
may also be generated, triggering further steps in the discovery
process or other actions, as appropriate.
For a detailed description of the interface state machine, see
Section 3.3. For a detailed description of the neighbor state
machine, see Section 4.3.
6.2 Bidirectional Communication
Before a conversation can proceed with a neighbor switch,
bidirectional communication must be established with that neighbor.
Bidirectional communication is detected in one of two ways:
o On a point-to-point link, the VlanHello protocol sees its own
switch ID listed in an Interswitch Keepalive message it has
received from the neighbor.
o On a multi-access link, VLSP sees its own switch ID listed in a
VLSP Hello packet it has received from the neighbor.
In either case, a neighbor 2-Way Received neighbor event is
generated.
Once bidirectional communication has been established with a
neighbor, the local switch determines whether an adjacency will be
formed with the neighbor. However, if the link is a multi-access
link, a designated switch and a backup designated switch must first
be selected for the link. The next section contains a description of
the designated switch, the backup designated switch, and the
selection process.
6.3 Designated Switch
Every multi-access network link has a designated switch. The
designated switch performs the following functions for the routing
protocol:
o The designated switch originates a network link advertisement on
behalf of the link, listing the set of switches (including the
designated switch itself) currently attached to the link. For a
detailed description of network link advertisements, see Section
11.3.
o The designated switch becomes adjacent to all other switches on
the link. Since the link state databases are synchronized across
adjacencies, the designated switch plays a central part in the
synchronization process. For a description of the synchronization
process, see Section 7.
Each multi-access network link also has a backup designated switch.
The primary function of the backup designated switch is to act as a
standby for the designated switch. If the current designated switch
fails, the backup designated switch becomes the designated switch.
To facilitate this transition, the backup designated switch forms an
adjacency with every other switch on the link. Thus, when the backup
designated switch must take over for the designated switch, its link
state database is already synchronized with the databases of all
other switches on the link.
Note: Point-to-point network links have neither a designated switch
or a backup designated switch.
6.3.1 Selecting the Designated Switch
When a multi-access link interface first becomes functional, the
switch sets a one-shot Wait timer (with a value of SwitchDeadInterval
seconds) for the interface. The purpose of this timer is to ensure
that all switches attached to the link have a chance to establish
bidirectional communication before the designated switch and backup
designated switch are selected for the link.
When the Wait timer is set, the interface enters the Waiting state.
During this state, the switch exchanges Hello packets with its
neighbors attempting to establish bidirectional communication. The
interface leaves the Waiting state under one of the following
conditions:
o The Wait timer expires.
o A Hello packet is received indicating that a designated switch or
a backup designated switch has already been specified for the
interface.
At this point, if the switch sees that a designated switch has
already been selected for the link, the switch accepts that
designated switch, regardless of its own switch priority and MAC
address. This situation typically means the switch has come up late
on a fully functioning link. Although this makes it harder to
predict the identity of the designated switch on a particular link,
it ensures that the designated switch does not change needlessly,
necessitating a resynchronization of the databases.
If no designated switch is currently specified for the link, the
switch begins the actual selection process. Note that this selection
algorithm operates only on a list of neighbor switches that are
eligible to become the designated switch. A neighbor is eligible to
be the designated switch if it has a switch priority greater than
zero and its neighbor state is 2-Way or greater. The local switch
includes itself on the list of eligible switches as long as it has a
switch priority greater than zero.
The selection process includes the following steps:
1. The current values of the link's designated switch and backup
designated switch are saved for use in step 6.
2. The new backup designated switch is selected as follows:
a) Eliminate from consideration those switches that have declared
themselves to be the designated switch.
b) If one or more of the remaining switches have declared
themselves to be the backup designated switch, eliminate from
consideration all other switches.
c) From the remaining list of eligible switches, select the switch
having the highest switch priority as the backup designated
switch. If multiple switches have the same (highest) priority,
select the switch with the highest switch ID as the backup
designated switch.
3. The new designated switch is selected as follows:
a) If one or more of the switches have declared themselves to be
the designated switch, eliminate from consideration all other
switches.
b) From the remaining list of eligible switches, select the switch
having the highest switch priority as the designated switch.
If multiple switches have the same (highest) priority, select
the switch with the highest switch ID as the designated switch.
4. If the local switch has been newly selected as either the
designated switch or the backup designated switch, or is now no
longer the designated switch or the backup designated switch,
repeat steps 2 and 3, above, and then proceed to step 5.
If the local switch is now the designated switch, it will
eliminate itself from consideration at step 2a when the selection
of the backup designated switch is repeated. Likewise, if the
local switch is now the backup designated switch, it will
eliminate itself from consideration at step 3a when the selection
of the designated switch is repeated. This ensures that no switch
will select itself as both backup designated switch and designated
switch [2].
5. Set the interface state to the appropriate value, as follows:
o If the local switch is now the designated switch, set the
interface state to DS.
o If the local switch is now the backup designated switch, set the
interface state to Backup.
o Otherwise, set the interface state to DS Other.
6. If either the designated switch or backup designated switch has
now changed, the set of adjacencies associated with this link must
be modified. Some adjacencies may need to be formed, while others
may need to be broken. Generate the neighbor AdjOK? event for all
neighbors with a state of 2-Way or higher to trigger a
reexamination of adjacency eligibility.
Caution: If VLSP is implemented with configurable parameters, care
must be exercised in specifying the switch priorities. Note that if
the local switch is not itself eligible to become the designated
switch (i.e., it has a switch priority of 0), it is possible that
neither a backup designated switch nor a designated switch will be
selected by the above procedure. Note also that if the local switch
is the only attached switch that is eligible to become the designated
switch, it will select itself as designated switch and there will be
no backup designated switch for the link. For this reason, it is
advisable to specify a default switch priority of 1 for all switches.
6.4 Adjacencies
VLSP creates adjacencies between neighboring switches for the purpose
of exchanging routing information. Not every two neighboring
switches will become adjacent. On a multi-access link, an adjacency
is only formed between two switches if one of them is either the
designated switch or the backup designated switch.
Note that an adjacency is bound to the network link that the two
switches have in common. Therefore, if two switches have multiple
links in common, they may also have multiple adjacencies between
them.
The decision to form an adjacency occurs in two places in the
neighbor state machine:
o When bidirectional communication is initially established with the
neighbor.
o When the designated switch or backup designated switch on the
attached link changes.
The rules for establishing an adjacency between two neighboring
switches are as follows:
o On a point-to-point link, the two neighboring switches always
establish an adjacency.
o On a multi-access link, an adjacency is established with the
neighboring switch under one of the following conditions:
o The local switch itself is the designated switch.
o The local switch itself is the backup designated switch.
o The neighboring switch is the designated switch.
o The neighboring switch is the backup designated switch.
If no adjacency is formed between two neighboring switches, the state
of the neighbor conversation remains set to 2-Way.
7. Synchronizing the Databases
In an SPF-based routing algorithm, it is important for the link state
databases of all switches to stay synchronized. VLSP simplifies this
process by requiring only adjacent switches to remain synchronized.
The synchronization process begins when the switches attempt to bring
up the adjacency. Each switch in the adjacency describes its
database by sending a sequence of Database Description packets to its
neighbor. Each Database Description packet describes a set of link
state advertisements belonging to the database. When the neighbor
sees a link state advertisement that is more recent than its own
database copy, it makes a note to request this newer advertisement.
During this exchange of Database Description packets (known as the
database exchange process), the two switches form a master/slave
relationship. Database Description packets sent by the master are
known as polls, and each poll contains a sequence number. Polls are
acknowledged by the slave by echoing the sequence number in the
Database Description response packet.
When all Database Description packets have been sent and
acknowledged, the database exchange process is completed. At this
point, each switch in the exchange has a list of link state
advertisements for which its neighbor has more recent instances.
These advertisements are requested using Link State Request packets.
Once the database exchange process has completed and all Link State
Requests have been satisfied, the databases are deemed synchronized
and the neighbor states of the two switches are set to Full,
indicating that the adjacency is fully functional. Fully functional
adjacencies are advertised in the link state advertisements of the
two switches [3].
7.1 Link State Advertisements
Link state advertisements form the core of the database from which a
switch calculates the set of best paths to the other switches in the
fabric.
Each link state advertisement begins with a standard header. This
header contains three data items that uniquely identify the link
state advertisement.
o The link state type. Possible values are as follows:
1 Switch link advertisement -- describes the collected states of
the switch's interfaces.
2 Network link advertisement -- describes the set of switches
attached to the network link.
o The link state ID, defined as follows:
o For a switch link advertisement -- the switch ID of the
originating switch
o For a network link advertisement -- the switch ID of the
designated switch for the link
o The switch ID of the advertising switch -- the switch that
generated the advertisement
The link state advertisement header also contains three data items
that are used to determine which instance of a particular link state
advertisement is the most current. (See Section 7.1.1 for a
description of how to determine which instance of a link state
advertisement is the most current.)
o The link state sequence number
o The link state age, stored in seconds
o The link state checksum, a 16-bit unsigned value calculated for
the entire contents of the link state advertisement, with the
exception of the age field
The remainder of each link state advertisement contains data specific
to the type of the advertisement. See Section 11 for a detailed
description of the link state header, as well as the format of a
switch link or network link advertisement.
7.1.1 Determining Which Link State Advertisement Is Newer
At various times while synchronizing or updating the link state
database, a switch must determine which instance of a particular link
state advertisement is the most current. This decision is made as
follows:
o The advertisement having the greater sequence number is the most
current.
o If both instances have the same sequence number, then:
o If the two instances have different checksum values, then the
instance having the larger checksum is considered the most
current [4].
o If both instances have the same sequence number and the same
checksum value, then:
o If one (and only one) of the instances is of age MaxAge, then
the instance of age MaxAge is considered the most current [5].
o Else, if the ages of the two instances differ by more than
MaxAgeDiff, the instance having the smaller (younger) age is
considered the most current [6].
o Else, the two instances are considered identical.
7.2 Database Exchange Process
There are two stages to the database exchange process:
o Negotiating the master/slave relationship
o Exchanging database summary information
7.2.1 Database Description Packets
Database Description packets are used to describe a switch's link
state database during the database exchange process. Each Database
Description packet contains a list of headers of the link state
advertisements currently stored in the sending switch's database.
(See Section 11.1 for a description of a link state advertisement
header.)
In addition to the link state headers, each Database Description
packet contains the following data items:
o A flag (the M-bit) indicating whether or not more packets are to
follow. Depending on the size of the local database and the
maximum size of the packet, the list of headers in any particular
Database Description packet may be only a partial list of the
total database. When the M-bit is set, the list of headers is
only a partial list and more headers are to follow in subsequent
packets.
o A flag (the I-bit) indicating whether or not this is the first
Database Description packet sent for this execution of the
database exchange process.
o A flag (the MS-bit) indicating whether the sending switch thinks
it is the master or the slave in the database exchange process.
If the flag is set, the switch thinks it is the master.
o A 4-octet sequence number for the packet.
While the switches are negotiating the master/slave relationship,
they exchange "empty" Database Description packets. That is, packets
that contain no link summary information. Instead, the flags and
sequence number constitute the information required for the
negotiation process.
See Section 10.6.2 for a more detailed description of a Database
Description packet.
7.2.2 Negotiating the Master/Slave Relationship
Before two switches can begin the actual exchange of database
information, they must decide between themselves who will be the
master in the exchange process and who will be the slave. They must
also agree on the starting sequence number for the Database
Description packets.
Once a switch has decided to form an adjacency with a neighboring
switch, it sets the neighbor state to ExStart and begins sending
empty Database Description packets to its neighbor. These packets
contain the starting sequence number the switch plans to use in the
exchange process. Also, the I-bit and M-bit flags are set, as well
as the MS-bit. Thus, each switch in the exchange begins by believing
it will be the master.
Empty Database Description packets are retransmitted every
RxmtInterval seconds until the neighbor responds.
When a switch receives an empty Database Description packet from its
neighbor, it determines which switch will be the master by comparing
the switch IDs. The switch with the highest switch ID becomes the
master of the exchange. Based on this determination, the switch
proceeds as follows:
o If the switch is to be the slave of the database exchange process,
it acknowledges that it is the slave by sending another empty
Database Description packet to the master. This packet contains
the master's sequence number and has the MS-bit and the I-bit
cleared.
o The switch then generates a neighbor event of Negotiation Done to
change its neighbor state to Exchange and waits for the first
non-empty Database Description packet from the master.
o If the switch is to be the master of the database exchange, it
waits to receive an acknowledgment from its neighbor -- that is,
an empty Database Description packet with the MS-bit and I-bit
cleared and containing the sequence number it (the master)
previously sent.
o When it receives the acknowledgment, it generates a neighbor event
of Negotiation Done to change its neighbor state to Exchange and
begin the actual exchange of Database Description packets.
Note that during the negotiation process, the receipt of an
inconsistent packet will result in a neighbor event of Seq Number
Mismatch, terminating the process. See Section 4.3 for more
information.
7.2.3 Exchanging Database Description Packets
Once the neighbor state changes to Exchange, the switches begin the
exchange of Database Description packets containing link state
summary data. The process proceeds as follows:
1. The master sends a packet containing a list of link state headers.
If the packet contains only a portion of the unexchanged database
-- that is, more Database Description packets are to follow -- the
packet has the M-bit set. The MS-bit is set and the I-bit is
clear.
If the slave does not acknowledge the packet within RxmtInterval
seconds, the master retransmits the packet.
2. When the slave receives a packet, it first checks the sequence
number to see if the packet is a duplicate. If so, it simply
acknowledges the packet by clearing the MS-bit and returning the
packet to the master. (Note that the slave acknowledges all
Database Description packets that it receives, even those that are
duplicates.)
Otherwise, the slave processes the packet by doing the following:
o For each link state header listed in the packet, the slave
searches its own link state database to determine whether it
has an instance of the advertisement.
o If the slave does not have an instance of the link state
advertisement, or if the instance it does have is older than
the instance listed in the packet, it creates an entry in its
link state request list in the neighbor data structure. See
Section 7.1.1 for a description of how to determine which
instance of a link state advertisement is the newest.
o When the slave has examined all headers, it acknowledges the
packet by turning the MS-bit off and returning the packet to
the master.
3. When the master receives the first acknowledgment for a particular
Database Description packet, it processes the acknowledgment as
follows:
o For each link state header listed in the packet, the master
checks to see if the slave has indicated it has an instance of
the link state advertisement that is newer than the instance
the master has in its own database. If so, the master creates
an entry in its link state request list in the neighbor data
structure.
o The master then increments the sequence number and sends
another packet containing the next set of link state summary
information, if any.
Subsequent acknowledgments for the Database Description packet
(those with the same sequence number) are discarded.
When the master sends the last portion of its database summary
information, it clears the M-bit in the packet to indicate that no
more packets are to be sent.
4. When the slave receives a Database Description packet with the M-
bit clear, it processes the packet, as described above in step 2.
After it has completed processing and has acknowledged the packet
to the master, it generates an Exchange Done neighbor event and
its neighbor state changes to Loading.
The database exchange process is now complete for the slave, and
it begins the process of requesting those link state
advertisements for which the master has more current instances
(see Section 7.3).
5. When the master receives an acknowledgment for the final Database
Description packet, it processes the acknowledgment as described
above in step 3. Then it generates an Exchange Done neighbor
event and its neighbor state changes to Loading.
The database exchange process is now complete for the master, and
it begins the process of requesting those link state
advertisements for which the slave has more current instances (see
Section 7.3).
Note that during this exchange, the receipt of an inconsistent packet
will result in a neighbor event of Seq Number Mismatch, terminating
the process. See Section 4.3 for more information.
7.3 Updating the Database
When either switch completes the database exchange process and its
neighbor state changes to Loading, it has a list of link state
advertisements for which the neighboring switch has a more recent
instance. This list is stored in the neighbor data structure as the
link state request list.
To complete the synchronization of its database with that of its
neighbor, the switch must obtain the most current instances of those
link state advertisements.
The switch requests these advertisements by sending its neighbor a
Link State Request packet containing the description of one or more
link state advertisement, as defined by the advertisement's type,
link state ID, and advertising switch. (For a detailed description
of the Link State Request packet, see Section 10.6.3.) The switch
continues to retransmit this packet every RxmtInterval seconds until
it receives a reply from the neighbor.
When the neighbor switch receives the Link State Request packet, it
responds with a Link State Update packet containing its most current
instance of each of the requested advertisements. (Note that the
neighboring switch can be in any of the Exchange, Loading or Full
neighbor states when it responds to a Link State Request packet.)
If the neighbor cannot locate a particular link state advertisement
in its database, something has gone wrong with the synchronization
process. The switch generates a BadLSReq neighbor event and the
partially formed adjacency is torn down. See Section 4.3 for more
information.
Depending on the size of the link state request list, it may take
more than one Link State Request packet to obtain all the necessary
advertisements. Note, however, that there must at most one Link
State Request packet outstanding at any one time.
7.4 An Example
Figure 3 shows an example of an adjacency being formed between two
switches -- S1 and S2 -- connected to a network link. S2 is the
designated switch for the link and has a higher switch ID than S1.
The neighbor state changes that each switch goes through are listed
on the sides of the figure.
+--------+ +--------+
| Switch | | Switch |
| S1 | | S2 |
+--------+ +--------+
Down Down
Hello (DS=0, seen=0)
------------------------------------->
Init
Hello (DS=S2, seen=...,S1)
<-------------------------------------
ExStart
DB Description (Seq=x, I, M, Master)
------------------------------------->
ExStart
DB Description (Seq=y, I, M, Master)
<-------------------------------------
xchange
DB Description (Seq=y, M, Slave)
------------------------------------->
Exchange
DB Description (Seq=y+1, M, Master)
<-------------------------------------
DB Description (Seq=y+1, M, Slave)
------------------------------------->
.
.
.
DB Description (Seq=y+n, Master)
<-------------------------------------
DB Description (Seq=y+n, Slave)
------------------------------------->
Loading Full
Link State Request
<-------------------------------------
Link State Update
------------------------------------->
.
.
.
Link State Request
<-------------------------------------
Link State Update
------------------------------------->
Full
Figure 3: An Example of Bringing Up an Adjacency
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.
8. 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 7.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.
8.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 8.2.4 for a description of
the installation of the advertisement into the link state database
and Section 8.2.5 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:
o The state of one of the switch's interfaces changes such that the
contents of the associated switch link advertisement changes.
o The designated switch on any of the switch's 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.
o One of the switch's 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.
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.
8.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 an empty switch link advertisement when it first becomes
functional. It then generates a new instance of the advertisement
each time one of its interfaces reaches a fully functioning state
(Point-to-Point or better).
Each link in the advertisement is assigned a type, based on the state
of interface, as shown in Table 4.
Interface state Link type Description
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.
**If a full adjacency has been formed with at least one
other switch on the link.
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 state advertisements for the
link. The relationship between link type and ID is shown in Table 5.
Type Description Link ID
1 Point-to-point link Switch ID of neighbor switch
2 Multi-access link Switch ID of designated switch
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.
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.
00-00-1d-22-23-c5
+-------+
| SW2 |
+-------+
|
| Point-to-Point
|
| 01
+-------+ Loopback +-------+
| SW3 |----------------| SW1 | 00-00-1d-1f-05-81