RFC 2642
Cabletron's VLS Protocol Specification
Pages: 95
Informational
Informational
Part 2 of 4 – Pages 23 to 51
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. 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 information7.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.
(page 51 continued on part 3)