Connected: An Internet Encyclopedia
13. The Flooding Procedure

Up: Connected: An Internet Encyclopedia
Up: Requests For Comments
Up: RFC 1583
Prev: 12.4.5. AS external links
Next: 13.1. Determining which link state is newer

13. The Flooding Procedure

13. The Flooding Procedure

Link State Update packets provide the mechanism for flooding link state advertisements. A Link State Update packet may contain several distinct advertisements, and floods each advertisement one hop further from its point of origination. To make the flooding procedure reliable, each advertisement must be acknowledged separately. Acknowledgments are transmitted in Link State Acknowledgment packets. Many separate acknowledgments can also be grouped together into a single packet.

                                +
                                |
                      +---+.....|.EGP
                      |RTA|-----|.....+---+
                      +---+     |-----|RTX|
                                |     +---+
                      +---+     |
                      |RTB|-----|
                      +---+     |
                                |
                      +---+     |
                      |RTC|-----|
                      +---+     |
                                |
                                +

               Figure 16: Forwarding address example

The flooding procedure starts when a Link State Update packet has been received. Many consistency checks have been made on the received packet before being handed to the flooding procedure (see Section 8.2). In particular, the Link State Update packet has been associated with a particular neighbor, and a particular area. If the neighbor is in a lesser state than Exchange, the packet should be dropped without further processing.

All types of link state advertisements, other than AS external link advertisements, are associated with a specific area. However, link state advertisements do not contain an area field. A link state advertisement's area must be deduced from the Link State Update packet header.

For each link state advertisement contained in the packet, the following steps are taken:

  1. Validate the advertisement's LS checksum. If the checksum turns out to be invalid, discard the advertisement and get the next one from the Link State Update packet.

  2. Examine the link state advertisement's LS type. If the LS type is unknown, discard the advertisement and get the next one from the Link State Update Packet. This specification defines LS types 1-5 (see Section 4.3).

  3. Else if this is a AS external link advertisement (LS type = 5), and the area has been configured as a stub area, discard the advertisement and get the next one from the Link State Update Packet. AS external link advertisements are not flooded into/throughout stub areas (see Section 3.6).

  4. Else if the advertisement's LS age is equal to MaxAge, and there is currently no instance of the advertisement in the router's link state database, then take the following actions:

    1. Acknowledge the receipt of the advertisement by sending a Link State Acknowledgment packet back to the sending neighbor (see Section 13.5).

    2. Purge all outstanding requests for equal or previous instances of the advertisement from the sending neighbor's Link State Request list (see Section 10).

    3. If the sending neighbor is in state Exchange or in state Loading, then install the MaxAge advertisement in the link state database. Otherwise, simply discard the advertisement. In either case, examine the next advertisement (if any) listed in the Link State Update packet.

  5. Otherwise, find the instance of this advertisement that is currently contained in the router's link state database. If there is no database copy, or the received advertisement is more recent than the database copy (see Section 13.1 below for the determination of which advertisement is more recent) the following steps must be performed:

    1. 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) and examine the next advertisement (if any) listed in the Link State Update packet.

    2. Otherwise immediately flood the new advertisement out some subset of the router's interfaces (see Section 13.3). In some cases (e.g., the state of the receiving interface is DR and the advertisement was received from a router other than the Backup DR) the advertisement will be flooded back out the receiving interface. This occurrence should be noted for later use by the acknowledgment process (Section 13.5).

    3. Remove the current database copy from all neighbors' Link state retransmission lists.

    4. Install the new advertisement in the link state database (replacing the current database copy). This may cause the routing table calculation to be scheduled. In addition, timestamp the new advertisement with the current time (i.e., the time it was received). The flooding procedure cannot overwrite the newly installed advertisement until MinLSInterval seconds have elapsed. The advertisement installation process is discussed further in Section 13.2.

    5. Possibly acknowledge the receipt of the advertisement by sending a Link State Acknowledgment packet back out the receiving interface. This is explained below in Section 13.5.

    6. If this new link state advertisement indicates that it was originated by the receiving router itself (i.e., is considered a self-originated advertisement), the router must take special action, either updating the advertisement or in some cases flushing it from the routing domain. For a description of how self-originated advertisements are detected and subsequently handled, see Section 13.4.

  6. Else, if there is an instance of the advertisement on the sending neighbor's Link state request list, an error has occurred in the Database Exchange process. In this case, restart the Database Exchange process by generating the neighbor event BadLSReq for the sending neighbor and stop processing the Link State Update packet.

  7. Else, if the received advertisement is the same instance as the database copy (i.e., neither one is more recent) the following two steps should be performed:

    1. If the advertisement is listed in the Link state retransmission list for the receiving adjacency, the router itself is expecting an acknowledgment for this advertisement. The router should treat the received advertisement as an acknowledgment, by removing the advertisement from the Link state retransmission list. This is termed an "implied acknowledgment". Its occurrence should be noted for later use by the acknowledgment process (Section 13.5).

    2. Possibly acknowledge the receipt of the advertisement by sending a Link State Acknowledgment packet back out the receiving interface. This is explained below in Section 13.5.

  8. Else, the database copy is more recent. Note an unusual event to network management, discard the advertisement and process the next link state advertisement contained in the Link State Update packet.


Next: 13.1. Determining which link state is newer

Connected: An Internet Encyclopedia
13. The Flooding Procedure