Method and apparatus for assigning ipv6 link state identifiers

Abstract

In one embodiment, a link state advertisement is generated. A first value and a second value are read from the link state advertisement. The first value and the second value are combined to create a combined value. The combined value is input to a hash algorithm that performs a hash function on the combined value to produce a resulting value. The resulting value is used as a link state identifier of the link state advertisement.

1 . A method comprising:
 generating a link state advertisement;
 reading a first value from the link state advertisement; 
 reading a second value from the link state advertisement; 
 combining the first value and the second value to create a combined value; 
 inputting the combined value to a hash algorithm executed by a processing unit, which performs a hash function on the combined value to produce a resulting value; and 
 using at least a portion of the resulting value as a link state identifier of the link state advertisement. 
   
     
     
         2 . The method of  claim 1 , further comprising:
 determining whether the at least a portion of the resulting value is a unique link state identifier; and   in response to the at least a portion of the resulting value not being a unique link state identifier, updating the at least a portion of the resulting value.   
     
     
         3 . The method of  claim 2 , wherein the determining further comprises:
 comparing the at least a portion of the resulting value to a plurality of stored link state identifiers.   
     
     
         4 . The method of  claim 2 , wherein the updating further comprises:
 performing a second hash function on the combined value and replacing the at least a portion of the resulting value based on results of the second hash function.   
     
     
         5 . The method of  claim 2 , wherein the updating further comprises:
 changing the at least a portion of the resulting value to be outside of a range of results of the hash function.   
     
     
         6 . The method of  claim 1 , wherein the second value is a N-bit integer, and wherein the combining further comprises:
 taking the first N bits of a binary representation of the prefix and appending one or more zero bits to the first N bits.   
     
     
         7 . The method of  claim 6 , wherein the combining further comprises:
 appending a binary representation of the N-bit integer to the first N bits and one or more zero bits.   
     
     
         8 . The method of  claim 1 , wherein the using further comprises:
 inserting the link state identifier into the link state advertisement; and   transmitting the link state advertisement over a network.   
     
     
         9 . The method of  claim 1 , wherein the first value is a prefix and the second value is a prefix length. 
     
     
         10 . The method of  claim 9 , wherein the prefix is a 128-bit Internet Protocol version 6 (Ipv6) address, the prefix length is an integer value in a range between 0 and 128 indicating a network portion of the Ipv6 address, and the link state advertisement is a Open Shortest Path First (OSPF) link state advertisement. 
     
     
         11 . The method of  claim 1 , wherein the combined value has a binary representation that has a first number of bits, and the link state identifier has a binary representation that has a second number of bits, wherein the first number of bits is greater than the second number of bits. 
     
     
         12 . The method of  claim 1 , wherein the processing unit is a processing unit of a routing system that includes one or more ports and one or more memories, and the generating, reading a first value, reading a second value, combining, inputing and using are performed by the routing system. 
     
     
         13 . Software encoded on one or more computer readable media and when executed operable to:
 generate a link state advertisement;   read one or more values from the link state advertisement;   perform a hash function on the one or more values to produce a resulting value;   use at least a portion of the resulting value as a link state identifier of the link state advertisement;   insert the link state identifier into the link state advertisement; and   transmit the link state advertisement over a network.   
     
     
         14 . The software of  claim 13  when executed further operable to:
 compare the at least a portion of the resulting value to a plurality of stored link state identifiers to determine whether the at least a portion of the resulting value is a unique link state identifier; and 
 in response to the at least a portion of the resulting value not being a unique link state identifier, update the at least a portion of the resulting value. 
 
     
     
         15 . An apparatus comprising:
 one or more ports;   a processing unit; and   a memory configured to store instructions for generating a link state advertisement, the instructions when executed by the processing unit operable to:
 determine a first value of the link state advertisement, 
 determine a second value of the link state advertisement, 
 combine the first value and the second value to create a combined value, 
 perform a hash function on the combined value to produce a resulting value, and 
 use at least a portion of the resulting value as a link state identifier of the link state advertisement. 
   
     
     
         16 . The apparatus of  claim 15 , wherein the instructions further comprise instructions that when executed by the processing unit are operable to:
 determine whether the at least a portion of the resulting value is a unique link state identifier, and   in response to the at least a portion of the resulting value not being a unique link state identifier, updating the at least a portion of the resulting value.   
     
     
         17 . The apparatus of  claim 16 , wherein the instructions further comprise instructions that when executed by the processing unit are operable to:
 compare the at least a portion of the resulting value to a plurality of stored link state identifiers.   
     
     
         18 . The apparatus of  claim 16 , wherein the instructions operable to update further comprise instructions that when executed by the processing unit are operable to:
 perform a second hash function on the combined value and replace the at least a portion of the resulting value based on results of the second hash function.   
     
     
         19 . The apparatus of  claim 16 , wherein the instructions operable to update further comprise instructions that when executed by the processing unit are operable to:
 change the at least a portion of the resulting value to be outside of a range of results of the hash function.   
     
     
         20 . The apparatus of  claim 15 , wherein the first value is a prefix and the second value is a prefix length.