2 - 4 - 8 - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W
database
Click on the red underlined text to get to the source
... switches in the fabric run the same algorithm and maintain
identical databases describing the switch fabric topology. This
...
... switch fabric topology. This
database contains each switch's local state, including its usable
...
... switch fabric by flooding. From the
topological database, each switch constructs a set of best path trees
...
... The discovery process is described in more detail in Section 6.
o Synchronizing the Databases
Adjacencies are used to simplify and speed up the process of
...
...
Adjacencies are used to simplify and speed up the process of
synchronizing the topological database (also known as the link
state database) maintained by each switch in the fabric. Each
...
... Adjacencies are used to simplify and speed up the process of
synchronizing the topological database (also known as the link
state database) maintained by each switch in the fabric. Each
switch ...
... switch in the fabric. Each
switch is only required to synchronize its database with those
neighbors to which it is adjacent. This reduces the amount of
...
... switches.
The process of synchronizing the databases is described in more
detail in Section 7.
...
... link state changes.
The process of maintaining the databases is described in more
detail in Section 8.
...
... o Calculating the Best Paths
The link state database consists of the collection of link state
advertisements received from each switch. Each switch ...
... switch. Each switch uses its
link state database to calculate a set of best paths, using itself
as root, to all other switches ...
... switch on multi-access links. The Database
Description and Link State Request packets are used to form
adjacencies. Link State ...
... Link State Acknowledgment packets
are used to update the topological database.
Each Link State ...
... o Section 6 through Section 9 describe the four operational stages
of the protocol: the discovery process, synchronizing the
databases, maintaining the databases, and calculating the set of
best paths.
...
... of the protocol: the discovery process, synchronizing the
databases, maintaining the databases, and calculating the set of
best paths.
...
... interface. This
value is also used to time the retransmission of Database
Description and Link State Request packets.
...
... 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 ...
... 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 ...
... 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.
...
... Database Description packet sent. See Section 7.2 for more
information on the database exchange process.
Neighbor ...
... see Section 8.2.5.)
Database summary list
The set of link state advertisement ...
... 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 ...
... Exchange state, this list is sent to the neighbor via Database
Description packets. (For more information on the synchronization
of databases ...
... Database
Description packets. (For more information on the synchronization
of databases, see Section 7.)
Link state ...
... order to synchronize with the neighbor switch's link state
database. This list is created as Database Description packets
...
... 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.)
...
... switch is the master, as well as
the initial sequence number for Database Descriptor packets.
Neighbor conversations in this state ...
... 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 ...
... 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
...
... 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.)
...
... sequence of Database Description packets. (For more information
on the database exchange process, see Section 7.2.)
BadLSReq
...
... received for a link state advertisement that is not contained in
the database. This event indicates an error in the
synchronization process.
...
... 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.)
...
... Seq Number Mismatch
This event is generated when a Database Description packet has
been received with any of the following conditions:
...
... neighbor and declare the local switch to
be master for the database exchange process. (See Section 7.2.)
State ...
... The Negotiation Done event signals the start of the database
exchange process. See Section 7.2 for a detailed description of
this process.
...
... 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
...
... neighbor and declare the local switch to be master
for the database exchange process. (See Section 7.2.)
State ...
... adjacency. Clear the link state retransmission list, database
summary list and link state request list and change the neighbor ...
... link state retransmission list, database summary list and link
state request list. Change the neighbor state ...
... link state retransmission list, database summary list and link
state request list. Change the neighbor state ...
... and clear the link state retransmission list, database summary
list and link state request list.
...
... and clear the link state retransmission list, database summary
list and link state request list.
...
... and clear the link state retransmission list, database summary
list and link state request list.
...
... 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 ...
...
The link state database within the area data structure must contain,
at most, a single instance ...
... single instance of each link state advertisement. To keep
the database current, a switch adds link state advertisements to the
...
... switch adds link state advertisements to the
database under the following conditions:
o When a link state advertisement ...
... deletes link state advertisements from the
database under the following conditions:
o When a link state advertisement ...
...
Note that when an advertisement is deleted from the link state
database, it must also be removed from the link state retransmission ...
... the link. Since the link state databases are synchronized across
adjacencies, the designated switch plays a central part in the
...
... designated switch must take over for the designated switch, its link
state database is already synchronized with the databases of all
other switches ...
... 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 ...
... it ensures that the designated switch does not change needlessly,
necessitating a resynchronization of the databases.
If no designated switch ...
... Synchronizing the Databases ...
... 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 ...
... up the adjacency. Each switch in the adjacency describes its
database by sending a sequence of Database Description packets to its
neighbor ...
... switch in the adjacency describes its
database by sending a sequence of Database Description packets to its
neighbor. Each Database Description ...
... Database Description packets to its
neighbor. Each Database Description packet describes a set of link
state advertisements belonging to the database. When the neighbor ...
... neighbor. Each Database Description packet describes a set of link
state advertisements belonging to the database. When the neighbor
sees a link state advertisement ...
... 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 ...
... 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 ...
... During this exchange of Database Description packets (known as the
database exchange process), the two switches form a master/slave
relationship. Database Description ...
... 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.
...
... response packet.
When all Database Description packets have been sent and
acknowledged, the database exchange process is completed. At this
...
... 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 ...
... Link State Request packets.
Once the database exchange process has completed and all Link State
Requests have been satisfied, the databases ...
... 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 ...
...
Link state advertisements form the core of the database from which a
switch calculates the set of best paths to the other switches ...
...
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
...
... Database Exchange Process ...
...
There are two stages to the database exchange process:
o Negotiating the master/slave relationship
...
...
o Negotiating the master/slave relationship
o Exchanging database summary information
...
... Database Description Packets ...
...
Database Description packets are used to describe a switch's link
state database during the database ...
... 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 ...
... 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 ...
... 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 ...
... 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
...
... 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
...
... 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 ...
... Database Description packet may be only a partial list of the
total database. When the M-bit is set, the list of headers is
...
... 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.
...
... 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.
...
... 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
...
... negotiation process.
See Section 10.6.2 for a more detailed description of a Database
Description packet.
...
...
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 ...
... neighbor state to ExStart and begins sending
empty Database Description packets to its neighbor. These packets
contain the starting ...
... 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 ...
...
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 ...
... 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 ...
... neighbor state to Exchange and waits for the first
non-empty Database Description packet from the master.
o If the switch ...
...
o If the switch is to be the master of the database exchange, it
waits to receive an acknowledgment from its neighbor -- that is,
...
... waits to receive an acknowledgment from its neighbor -- that is,
an empty Database Description packet with the MS-bit and I-bit ...
... neighbor state to Exchange and
begin the actual exchange of Database Description packets.
Note that during the negotiation ...
... Exchanging Database Description Packets ...
... state changes to Exchange, the switches begin the
exchange of Database Description packets containing link state
summary data. The process proceeds as follows:
...
... link state headers.
If the packet contains only a portion of the unexchanged database
-- that is, more Database Description packets are to follow -- the
...
... 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 and returning the
packet to the master. (Note that the slave acknowledges all
Database Description packets that it receives, even those that are
duplicates.)
...
... 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.
...
...
3. When the master receives the first acknowledgment for a particular
Database Description packet, it processes the acknowledgment as
follows:
...
... 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 ...
... information, if any.
Subsequent acknowledgments for the Database Description packet
(those with the same sequence number) are discarded.
...
... 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.
...
... 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
...
... 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
...
... Updating the Database ...
... neighbor cannot locate a particular link state advertisement
in its database, something has gone wrong with the synchronization
process. The switch ...
... 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 ...
... 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 ...
... state. S1 will change to
the Full state after updating its database by sending Link State
Request packets and receiving ...
... 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.
...
... Maintaining the Databases ...
... 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 ...
... 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.
...
...
o Section 8.2.4 describes how advertisements are installed into the
local database.
o Section 8.2.5 describes the retransmission ...
...
2. If the advertisement's age is equal to MaxAge and there is
currently no instance of the advertisement in the local link state
database, then do the following:
a) Acknowledge the advertisement by sending a Link State ...
... c) If the neighbor is Exchange or Loading, install the
advertisement in the link state database (see Section 8.2.4).
Otherwise, discard the advertisement.
...
...
3. If the advertisement's age is equal to MaxAge and there is an
instance of the advertisement in the local link state database,
then do the following:
...
...
4. If the advertisement's age is less than MaxAge, attempt to locate
an instance of the advertisement in the local link state database.
If there is no database copy of this advertisement, or the
...
... an instance of the advertisement in the local link state database.
If there is no database copy of this advertisement, or the
received advertisement is more recent than the database copy (see
...
... If there is no database copy of this advertisement, or the
received advertisement is more recent than the database copy (see
Section 7.1.1), do the following:
...
... Section 7.1.1), do the following:
a) If there is already a database copy, and if the database copy
was installed less than MinLSInterval seconds ago, discard the
...
...
a) If there is already a database copy, and if the database copy
was installed less than MinLSInterval seconds ago, discard the
new advertisement without acknowledging it.
...
... neighbors.
d) Install the new advertisement in the link state database,
replacing the current database copy. (Note that this may cause
...
... d) Install the new advertisement in the link state database,
replacing the current database copy. (Note that this may cause
the calculation of the set of best paths to be scheduled. See
Section 9.) Timestamp ...
... switch was restarted.)
5. If the received advertisement is the same instance as the database
copy (as determined by the algorithm described in Section 7.1.1),
...
... (See Section 8.2.6.)
If the database copy of the advertisement is more recent than the
instance just received, do the following:
...
... neighbor link
state request list. If so, an error has occurred in the
database exchange process. Restart the database exchange
...
... database exchange process. Restart the database exchange
process by generating a neighbor BadLSReq event for the sending
...
... Installing Link State Advertisements in the Database ...
...
When a new link state advertisement is installed into the link state
database, as the result of either originating or receiving a new
instance of an advertisement, the switch ...
... Note also that the older instance of the advertisement must be
removed from the link state database when the new advertisement is
installed. The older instance must also be removed from the link
state ...
... needless retransmissions will ensue. If the value is too high, the
speed with which the databases synchronize across adjacencies may be
affected if there are lost packets.
...
... Advertisement is Delayed ack sent Delayed ack
more recent than if advertisement sent
database copy, but received from DS,
was not forwarded else do nothing
...
... equal to MaxAge and sent sent
no current instance
found in database
Table 6: Sending Link State ...
... Aging the Link State Database ...
... of Exchange or Loading, remove the advertisement from the local
link state database.
...
... Once an adjacency has been formed and the two switches have
synchronized their databases, each switch in the adjacency calculates
the best path(s) to all other switches ...
... DS/Backup DS Section 10.6.1
2 Database Summarize database
Description contents Section 10.6.2
3 LS Request Database ...
... DS Section 10.6.1
2 Database Summarize database
Description contents Section 10.6.2
3 LS Request Database download Section 10.6.3
...
... Database Summarize database
Description contents Section 10.6.2
3 LS Request Database download Section 10.6.3
4 LS Update Database ...
... Database download Section 10.6.3
4 LS Update Database update Section 10.6.4
5 LS Ack Flooding ...
...
Since it is important that the link state databases remain
synchronized throughout the switch fabric, processing of both
...
... switch.
o Database Description packets and Link State Request are always
addressed directly to the other switch ...
... addressed directly to the other switch participating in the
database exchange process.
VLSP header ...
...
1 Hello
2 Database Description
3 Link State Request
...
...
Hello packets and Database Description packets, as well as link state
advertisements, contain a 1-octet options field. Using this field, a
...
... Database Description Packets ...
...
Database Description packets are exchanged while an adjacency is
being formed between two neighboring switches and are used to
...
... being formed between two neighboring switches and are used to
describe the contents of the topological database. For a complete
description of the database exchange process, see Section 7.2.
...
... describe the contents of the topological database. For a complete
description of the database exchange process, see Section 7.2.
The format of a Database Description ...
... database exchange process, see Section 7.2.
The format of a Database Description packet is shown below.
0 1 2 3
...
... This 1-octet field contains a set of bit flags that are used to
coordinate the database exchange process. The format of this
octet is as follows:
...
...
The M-bit is set to indicate that more Database Description
packets to follow.
...
... bit is set, the sending switch is the master
during the database exchange process. If the bit is clear, the
switch ...
... Sequence number
This 4-octet field is used to sequence the Database Description
packets during the database exchange process. The two switches ...
... This 4-octet field is used to sequence the Database Description
packets during the database exchange process. The two switches
involved in the exchange process agree on the initial value of the
...
... sequence number during the master/slave negotiation. The number
is then incremented for each Database Description packet in the
exchange.
...
... exchange.
To acknowledge each Database Description packet sent by the
master, the slave sends a Database Description packet that echoes
...
... To acknowledge each Database Description packet sent by the
master, the slave sends a Database Description packet that echoes
the sequence number of the packet being acknowledged.
...
... link state headers
that describe a portion of the master's topological database.
Each header uniquely identifies a link state advertisement ...
... Link State Request packets are used to request those pieces of the
neighbor's database that the sending switch has discovered (during
the database ...
... database that the sending switch has discovered (during
the database exchange process) are more up-to-date than instances in
its own database. Link State ...
... the database exchange process) are more up-to-date than instances in
its own database. Link State Request packets are sent as the last
step in bringing up an adjacency. (See Section 7.3.)
...
... fabric.) This collection of advertisements, known as the link state
(or topological) database, is used to calculate a set of best paths
to all other switches in the fabric.
...
... removed from the
originating switch's database. Advertisements having age MaxAge
are not used to calculate the set of best paths. The value of
MaxAge must be greater than LSRefreshTime. The value of MaxAge is
...
... retransmissions for adjacencies established on this interface.
This value is also used when retransmitting Database Description
packets and Link State Request packets. This value must be greater
...
... [5] An instance of an advertisement is originated with an age of
MaxAge only when it is to be flushed from the database. This is done
either when the advertisement has naturally aged to MaxAge, or (more
typically) when the sequence number ...
... sequence number must wrap. Therefore, a received
instance with an age of MaxAge must be processed as the most recent
in order to flush it properly from the database.
[6 ...