Connected: An Internet Encyclopedia
13.3. Next step in the flooding procedure
Up:
Connected: An Internet Encyclopedia
Up:
Requests For Comments
Up:
RFC 1583
Up:
13. The Flooding Procedure
Prev: 13.2. Installing link state advertisements in the database
Next: 13.4. Receiving self-originated link state
13.3. Next step in the flooding procedure
13.3. Next step in the flooding procedure
When a new (and more recent) advertisement has been received, it
must be flooded out some set of the router's interfaces. This
section describes the second part of flooding procedure (the
first part being the processing that occurred in Section 13),
namely, selecting the outgoing interfaces and adding the
advertisement to the appropriate neighbors' Link state
retransmission lists. Also included in this part of the
flooding procedure is the maintenance of the neighbors' Link
state request lists.
This section is equally applicable to the flooding of an
advertisement that the router itself has just originated (see
Section 12.4). For these advertisements, this section provides
the entirety of the flooding procedure (i.e., the processing of
Section 13 is not performed, since, for example, the
advertisement has not been received from a neighbor and
therefore does not need to be acknowledged).
Depending upon the advertisement's LS type, the advertisement
can be flooded out only certain interfaces. These interfaces,
defined by the following, are called the eligible interfaces:
- AS external link advertisements (LS Type = 5)
-
AS external link advertisements are flooded throughout the
entire AS, with the exception of stub areas (see Section
3.6). The eligible interfaces are all the router's
interfaces, excluding virtual links and those interfaces
attaching to stub areas.
- All other LS types
-
All other types are specific to a single area (Area A). The
eligible interfaces are all those interfaces attaching to
the Area A. If Area A is the backbone, this includes all
the virtual links.
Link state databases must remain synchronized over all
adjacencies associated with the above eligible interfaces. This
is accomplished by executing the following steps on each
eligible interface. It should be noted that this procedure may
decide not to flood a link state advertisement out a particular
interface, if there is a high probability that the attached
neighbors have already received the advertisement. However, in
these cases the flooding procedure must be absolutely sure that
the neighbors eventually do receive the advertisement, so the
advertisement is still added to each adjacency's Link state
retransmission list. For each eligible interface:
- Each of the neighbors attached to this interface are
examined, to determine whether they must receive the new
advertisement. The following steps are executed for each
neighbor:
- If the neighbor is in a lesser state than Exchange, it
does not participate in flooding, and the next neighbor
should be examined.
- Else, if the adjacency is not yet full (neighbor state
is Exchange or Loading), examine the Link state request
list associated with this adjacency. If there is an
instance of the new advertisement on the list, it
indicates that the neighboring router has an instance of
the advertisement already. Compare the new
advertisement to the neighbor's copy:
- If the new advertisement is less recent, then
examine the next neighbor.
- If the two copies are the same instance, then delete
the advertisement from the Link state request list,
and examine the next neighbor.[17]
- Else, the new advertisement is more recent. Delete
the advertisement from the Link state request list.
- If the new advertisement was received from this
neighbor, examine the next neighbor.
- At this point we are not positive that the neighbor has
an up-to-date instance of this new advertisement. Add
the new advertisement to the Link state retransmission
list for the adjacency. This ensures that the flooding
procedure is reliable; the advertisement will be
retransmitted at intervals until an acknowledgment is
seen from the neighbor.
- The router must now decide whether to flood the new link
state advertisement out this interface. If in the previous
step, the link state advertisement was NOT added to any of
the Link state retransmission lists, there is no need to
flood the advertisement out the interface and the next
interface should be examined.
- If the new advertisement was received on this interface, and
it was received from either the Designated Router or the
Backup Designated Router, chances are that all the neighbors
have received the advertisement already. Therefore, examine
the next interface.
- If the new advertisement was received on this interface, and
the interface state is Backup (i.e., the router itself is
the Backup Designated Router), examine the next interface.
The Designated Router will do the flooding on this
interface. If the Designated Router fails, this router will
end up retransmitting the updates.
- If this step is reached, the advertisement must be flooded
out the interface. Send a Link State Update packet (with
the new advertisement as contents) out the interface. The
advertisement's LS age must be incremented by InfTransDelay
(which must be > 0) when copied into the outgoing Link State
Update packet (until the LS age field reaches its maximum
value of MaxAge).
On broadcast networks, the Link State Update packets are
multicast. The destination IP address specified for the
Link State Update Packet depends on the state of the
interface. If the interface state is DR or Backup, the
address AllSPFRouters should be used. Otherwise, the
address AllDRouters should be used.
On non-broadcast, multi-access networks, separate Link State
Update packets must be sent, as unicasts, to each adjacent
neighbor (i.e., those in state Exchange or greater). The
destination IP addresses for these packets are the
neighbors' IP addresses.
Next: 13.4. Receiving self-originated link state
Connected: An Internet Encyclopedia
13.3. Next step in the flooding procedure