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:

  1. 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:

    1. If the neighbor is in a lesser state than Exchange, it does not participate in flooding, and the next neighbor should be examined.

    2. 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.

    3. If the new advertisement was received from this neighbor, examine the next neighbor.

    4. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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