F. An algorithm for assigning Link State IDs

In RFC 1247, the Link State ID in AS external link advertisements and summary link advertisements is set to the described network's IP address. This memo relaxes that requirement, allowing one or more of the network's host bits to be set in the Link State ID. This allows the router to originate separate advertisements for networks having the same addresses, yet different masks. Such networks can occur in the presence of supernetting and subnet 0s (see Section E.2 for more information).

This appendix gives one possible algorithm for setting the host bits in Link State IDs. The choice of such an algorithm is a local decision. Separate routers are free to use different algorithms, since the only advertisements affected are the ones that the router itself originates. The only requirement on the algorithms used is that the network's IP address should be used as the Link State ID (the RFC 1247 behavior) whenever possible.

The algorithm below is stated for AS external link advertisements. This is only for clarity; the exact same algorithm can be used for summary link advertisements. Suppose that the router wishes to originate an AS external link advertisement for a network having address NA and mask NM1. The following steps are then used to determine the advertisement's Link State ID:

1. Determine whether the router is already originating an AS external link advertisement with Link State ID equal to NA (in such an advertisement the router itself will be listed as the advertisement's Advertising Router). If not, set the Link State ID equal to NA (the RFC 1247 behavior) and the algorithm terminates. Otherwise,

2. Obtain the network mask from the body of the already existing AS external link advertisement. Call this mask NM2. There are then two cases:
   • NM1 is longer (i.e., more specific) than NM2. In this case, set the Link State ID in the new advertisement to be the network [NA,NM1] with all the host bits set (i.e., equal to NA or'ed together with all the bits that are not set in NM1, which is network [NA,NM1]'s broadcast address).

   • NM2 is longer than NM1. In this case, change the existing advertisement (having Link State ID of NA) to reference the new network [NA,NM1] by incrementing the sequence number, changing the mask in the body to NM1 and using the cost for the new network. Then originate a new advertisement for the old network [NA,NM2], with Link State ID equal to NA or'ed together with the bits that are not set in NM2 (i.e., network [NA,NM2]'s broadcast address).

The above algorithm assumes that all masks are contiguous; this ensures that when two networks have the same address, one mask is more specific than the other. The algorithm also assumes that no network exists having an address equal to another network's broadcast address. Given these two assumptions, the above algorithm always produces unique Link State IDs. The above algorithm can also be reworded as follows: When originating an AS external link state advertisement, try to use the network number as the Link State ID. If that produces a conflict, examine the two networks in conflict. One will be a subset of the other. For the less specific network, use the network number as the Link State ID and for the more specific use the network's broadcast address instead (i.e., flip all the "host" bits to 1). If the most specific network was originated first, this will cause you to originate two link state advertisements at once.

As an example of the algorithm, consider its operation when the following sequence of events occurs in a single router (Router A).

1. Router A wants to originate an AS external link advertisement for [10.0.0.0,255.255.255.0]:
   1. A Link State ID of 10.0.0.0 is used.

2. Router A then wants to originate an AS external link advertisement for [10.0.0.0,255.255.0.0]:
   1. The advertisement for [10.0.0,0,255.255.255.0] is reoriginated using a new Link State ID of 10.0.0.255.

   2. A Link State ID of 10.0.0.0 is used for [10.0.0.0,255.255.0.0].

3. Router A then wants to originate an AS external link advertisement for [10.0.0.0,255.0.0.0]:
   1. The advertisement for [10.0.0.0,255.255.0.0] is reoriginated using a new Link State ID of 10.0.255.255.

   2. A Link State ID of 10.0.0.0 is used for [10.0.0.0,255.0.0.0].

   3. The network [10.0.0.0,255.255.255.0] keeps its Link State ID of 10.0.0.255.