Forwarding of packets in a network based on multiple compact forwarding identifiers represented in a single internet protocol version 6 (IPv6) address

Abstract

In one embodiment, packets are forwarded in a network based on multiple compact forwarding identifiers represented in a single 128-bit Internet Protocol Version 6 (IPv6) address, such as, but not limited to being in the destination address field of the IPv6 header (e.g., possibly in an extended IPv6 header). One embodiment follows the forwarding order of these multiple compact forwarding identifiers by respectively placing them in the single IPv6 address from high-order to lower-order bit positions. In one embodiment, a compact forwarding identifier prefix is part of the address represented by each compact forwarding identifier, typically with the compact forwarding identifier prefix stored in the highest-order bit positions. One embodiment uses a longest prefix matching operation to match the compact forwarding identifier to be used in determining how to next process the packet.

What is claimed is: 
     
       1. A method, comprising:
 receiving, by a first network node, an Internet Protocol version 6 (IPv6) packet with an IPv6 header including a particular destination address of length 128 bits in the a destination address field of the IPv6 header, with the particular destination address including encoded therein a first destination address and a second destination address, with the first destination address corresponding to the first network node and the second destination address corresponding to a second network node; 
 changing, by the first network node, the particular destination address to an updated particular destination address of length 128 bits, with the updated particular destination address including encoded therein the second destination address; and 
 sending, from the first network node, the IPv6 packet with the destination address field in the destination address field of the IPv6 header including the updated particular destination address. 
 
     
     
       2. The method of  claim 1 , wherein the particular destination address includes a compact forwarding identifier prefix, a first compact forwarding identifier, and a second compact forwarding identifier; wherein the first destination address includes the compact forwarding identifier prefix and the first compact forwarding identifier, and the second destination address includes the compact forwarding identifier prefix and the second compact forwarding identifier. 
     
     
       3. The method of  claim 2 , wherein the particular destination address includes the compact forwarding identifier prefix concatenated with the first compact forwarding identifier; and the updated particular destination address includes the compact forwarding identifier prefix concatenated with the second compact forwarding identifier. 
     
     
       4. The method of  claim 3 , wherein the particular destination address includes, in the following order: the compact forwarding identifier prefix, a first compact forwarding identifier, and a second compact forwarding identifier. 
     
     
       5. The method of  claim 2 , wherein the compact forwarding identifier prefix identifies an encoding format for the particular destination address and the updated particular destination address. 
     
     
       6. The method of  claim 2 , further comprising the limitations of:
 programming, by the first network node, one or more forwarding data structures with a first entry including the compact forwarding identifier prefix and the first compact forwarding identifier, and with a second entry including the compact forwarding identifier prefix and the second compact forwarding identifier; 
 processing, by the first network node, the IPv6 packet in response to a first lookup operation performed in at least one of said forwarding data structures based on the particular destination address resulting in a match of the first entry; and 
 performing a second lookup operation in at least one of said forwarding data structures based on the updated particular destination address resulting in a match of the second entry based on which the first network node determines to perform said sending the IPv6 packet; 
 wherein said processing includes said changing the particular destination address, said performing the second lookup operation, and said sending the IPv6 packet. 
 
     
     
       7. The method of  claim 6 , further comprising the limitations of:
 the first network node advertising that it is associated with a first 128-bit IPv6 address including the compact forwarding identifier prefix and the first compact forwarding identifier; and 
 the first network node performing said programming of the second entry responsive to a received advertisement that the second network node is associated with a second 128-bit IPv6 address including the compact forwarding identifier prefix and the second compact forwarding identifier. 
 
     
     
       8. The method of  claim 7 , wherein the a highest-order bits of the first 128-bit IPv6 address are the compact forwarding identifier prefix followed by the first compact forwarding identifier; wherein the highest-order bits of the second 128-bit IPv6 address are the compact forwarding identifier prefix followed by the second compact forwarding identifier; and wherein each of the first and second lookup operations is a longest prefix matching operation. 
     
     
       9. The method of  claim 2 , further comprising the limitations of:
 programming, by the first network node, one or more forwarding data structures with a first entry including the compact forwarding identifier prefix and the first compact forwarding identifier, and with a second entry including the compact forwarding identifier prefix and the second compact forwarding identifier; 
 processing, by the first network node, the IPv6 packet in response to a first lookup operation performed in at least one of said forwarding data structures based on the first destination address resulting in a match of the first entry; and 
 performing a second lookup operation in at least one of said forwarding data structures based on the second destination address resulting in a match of the second entry based on which the first network node determines to perform said sending the IPv6 packet; 
 wherein said processing includes said changing the particular destination address, said performing the second lookup operation, and said sending the IPv6 packet. 
 
     
     
       10. The method of  claim 2 , further comprising the limitations of:
 programming, by the first network node, one or more forwarding data structures with an entry including the compact forwarding identifier prefix and the second compact forwarding identifier; and 
 determining, by the first network node, to said send the IPv6 packet based on a lookup operation in at least one of said forwarding data structures based on the updated particular destination address resulting in a match of the entry. 
 
     
     
       11. The method of  claim 10 , wherein the first network node performs said programming of the entry responsive to a received advertisement that the second network node is associated with a 128-bit IPv6 address including the compact forwarding identifier prefix and the second compact forwarding identifier. 
     
     
       12. The method of  claim 11 , wherein the a highest-order bits of the 128-bit IPv6 address are the compact forwarding identifier prefix followed by the second compact forwarding identifier; and wherein the lookup operation is a longest prefix matching operation. 
     
     
       13. The method of  claim 2 , wherein the first compact forwarding identifier is associated with a first list position indication included in the particular destination address; and wherein the second compact forwarding identifier is associated with a second list position indication included in the particular destination address and in the updated particular destination address. 
     
     
       14. The method of  claim 1 , wherein the particular destination address includes encoded therein the first destination address, the second destination address, and a third destination address corresponding to a third network node; and wherein the updated particular destination address includes encoded therein the second destination address and the third destination address. 
     
     
       15. A method, comprising:
 receiving, by a first network node, an Internet Protocol version 6 (IPv6) packet with a particular address, with the particular address including encoded therein a first destination address and a second destination address, with the particular address being 128 bits in length and located in a 128-bit address field of the IPv6 packet, and with the first destination address corresponding to the first network node and the second destination address corresponding to a second network node; 
 determining a forwarding result based on performing a lookup operation in at least one of one or more forwarding data structures based on the second destination address or search key including the second destination address encoded therein; and 
 based on the forwarding result, sending the IPv6 packet from the first network node. 
 
     
     
       16. The method of  claim 15 , wherein theparticular address in the received IPv6 packet includes a compact forwarding identifier prefix, a first compact forwarding identifier, and a second compact forwarding identifier; wherein the first destination address includes the compact forwarding identifier prefix and the first compact forwarding identifier, and the second destination address includes the compact forwarding identifier prefix and the second compact forwarding identifier. 
     
     
       17. The method of claim  15   16 , wherein the a highest-order bits of the particular address in said received IPv6 packet are the compact forwarding identifier prefix followed by the first compact forwarding identifier; wherein the highest-order bits of the particular address in said sent IPv6 packet are the compact forwarding identifier prefix followed by the second compact forwarding identifier; wherein the search key is the particular address in said sent IPv6 packet; wherein the lookup operation is a longest prefix matching operation; and wherein the method includes modifying the particular address in said received IPv6 packet to the particular address in said sent IPv6 packet. 
     
     
       18. A packet switching device, comprising:
 a plurality of hardware interfaces sending and receiving packets; and 
 one or more network processors with memory associated therewith; 
 wherein the packet switching device performs packet processing operations, with said packet processing operations including: 
 receiving via one of the plurality of hardware interfaces a packet with a first particular value, with the first particular value including encoded therein a first destination address and a second destination address, with the first particular value being 128 bits in length and located in a 128-bit Internet Protocol Version 6 (IPv6) address field of the packet, and with the first destination address corresponding to the 0 first network node and the second destination address corresponding to a second network node; 
 modifying the particular value to become a second particular value of length 128 bits, with the second particular destination address including encoded therein the second destination address; 
 performing a lookup operation in one or more data structures based on the second particular value or the second destination address resulting in the determination of a lookup result; and 
 responsive to the lookup result, sending the packet with the second particular value from the packet switching device via one or more of the plurality of hardware interfaces. 
 
     
     
       19. The packet switching device of  claim 18 , wherein the first particular value includes a compact forwarding identifier prefix, a first compact forwarding identifier, and a second compact forwarding identifier; wherein the first destination address includes the compact forwarding identifier prefix and the first compact forwarding identifier, and the second destination address includes the compact forwarding identifier prefix and the second compact forwarding identifier but not the first compact forwarding identifier. 
     
     
       20. The packet switching device of  claim 18 , wherein the first particular value in said received packet includes a compact forwarding identifier prefix, a first compact forwarding identifier, and a second compact forwarding identifier; wherein the first destination address includes the compact forwarding identifier prefix and the first compact forwarding identifier, and the second destination address includes the compact forwarding identifier prefix and the second compact forwarding identifier; wherein the a highest-order bits of the first particular value in said received packet are the compact forwarding identifier prefix followed by the first compact forwarding identifier; and wherein the highest-order bits of the second particular value in said sent packet are the compact forwarding identifier prefix followed by the second compact forwarding identifier. 
     
     
       21. A packet switching device, comprising:
 a plurality of hardware interfaces operative to send and receive packets; and   one or more network processors with memory associated therewith;   wherein the packet switching device performs packet processing operations including:   receiving, via one of the plurality of hardware interfaces, an Internet Protocol version 6 (IPv6) packet with an IPv6 header including a 128-bit destination address in a destination address field of the IPv6 header, the 128-bit destination address comprising a compact forwarding identifier prefix, and a plurality of compact forwarding identifiers including a first compact forwarding identifier, a second compact forwarding identifier and zero or more additional compact forwarding identifiers; wherein the 128-bit destination address comprises a first destination address encoded therein, wherein the first destination address includes the compact forwarding identifier prefix concatenated with the first compact forwarding identifier;   changing the 128-bit destination address to an updated 128-bit destination address, with the updated 128-bit destination address including encoded therein a second destination address comprising the compact forwarding identifier prefix and the second compact forwarding identifier, with said changing including removing the first compact forwarding identifier such that a highest-order bits of the updated 128-bit destination address are the compact forwarding identifier prefix concatenated with the second compact forwarding identifier followed by said zero or more additional compact forwarding identifiers;   adding padding bits to the updated 128-bit destination address after the second compact forwarding identifier and said zero or more additional compact forwarding identifiers;   performing a lookup operation in one or more data structures based on the updated 128-bit destination address resulting in a lookup result and   forwarding, based on the lookup result, the IPv6 packet with the updated 128-bit destination address in the destination address field of the IPv6 header.   
     
     
       22. The packet switching device of  claim 21 , wherein the first compact forwarding identifier is said removed by shifting the compact forwarding identifiers of the plurality of compact forwarding identifiers after the first compact identifier, with said shifted compact forwarding identifiers including the second compact forwarding identifier. 
     
     
       23. The packet switching device of  claim 21 , wherein the 128-bit destination address of the received IPv6 packet includes, in the following order: the compact forwarding identifier prefix, the first compact forwarding identifier, and the second compact forwarding identifier. 
     
     
       24. The packet switching device of  claim 21 , wherein the compact forwarding identifier prefix identifies an encoding format for the 128-bit destination address and the updated 128-bit destination address. 
     
     
       25. The packet switching device of  claim 21 , wherein the packet processing operations further include programming at least one of the one or more data structures with an entry including the compact forwarding identifier prefix and the second compact forwarding identifier. 
     
     
       26. The packet switching device of  claim 25 , wherein the programming of the entry is responsive to a received advertisement from a remote network node that is associated with an Internet Protocol (IP) route including the compact forwarding identifier prefix and the second compact forwarding identifier. 
     
     
       27. The packet switching device of  claim 21 , wherein the highest-order bits of the updated 128-bit destination address are the compact forwarding identifier prefix followed by the second compact forwarding identifier; and wherein the lookup operation is a longest prefix matching operation. 
     
     
       28. The packet switching device of  claim 21 , wherein said zero or more additional compact forwarding identifiers includes a third compact forwarding identifier; and
 wherein a third destination address includes the compact forwarding identifier prefix and the third compact forwarding identifier;   wherein the destination address of the received IPv6 packet includes encoded therein the first destination address, the second destination address, and a third destination address; and   wherein the updated destination address includes encoded therein the second destination address and the third destination address.   
     
     
       29. The packet switching device of  claim 21 , wherein the compact forwarding identifier prefix identifies an address space. 
     
     
       30. The packet switching device of  claim 21 , wherein the packet processing operations further include transmitting one or more messages advertising that the packet switching device is associated with an an Internet Protocol (IP) route including the compact forwarding identifier prefix and the first compact forwarding identifier. 
     
     
       31. The packet switching device of  claim 21 , wherein the packet processing operations further include:
 programming at least one of the one or more data structures with a first entry including the compact forwarding identifier prefix and the first compact forwarding identifier, and with a second entry including the compact forwarding identifier prefix and the second compact forwarding identifier;   processing the received IPv6 packet in response to a first lookup operation performed in at least one of said forwarding data structures based on the destination address resulting in a match of the first entry;   wherein the second lookup operation matched the second entry in identifying the lookup result:   wherein the lookup operation in one or more data structures based on the updated 128-bit destination address results in a match of the second entry, with the lookup result determined based on the match of the second entry; and   wherein said processing the received IPv6 packet includes said changing the destination address, said performing the lookup operation in one or more data structures based on the updated 128-bit destination address resulting in the lookup result, and said forwarding the IPv6 packet.   
     
     
       32. A method, comprising:
 receiving, via a network interface, an Internet Protocol version 6 (IPv6) packet with an IPv6 header including a 128-bit destination address in a destination address field of the IPv6 header, the 128-bit destination address comprising a compact forwarding identifier prefix, and a plurality of compact forwarding identifiers including a first compact forwarding identifier, a second compact forwarding identifier and zero or more additional compact forwarding identifiers; wherein the 128-bit destination address comprises a first destination address encoded therein, wherein the first destination address includes the compact forwarding identifier prefix concatenated with the first compact forwarding identifier;   changing the 128-bit destination address to an updated 128-bit destination address, with the updated 128-bit destination address including encoded therein a second destination address comprising the compact forwarding identifier prefix and the second compact forwarding identifier, with said changing including removing the first compact forwarding identifier such that a highest-order bits of the updated 128-bit destination address are the compact forwarding identifier prefix concatenated with the second compact forwarding identifier followed by said zero or more additional compact forwarding identifiers;   adding padding bits to the updated 128-bit destination address after the second compact forwarding identifier and said zero or more additional compact forwarding identifiers;   performing a lookup operation in one or more data structures based on the updated 128- bit destination address resulting in a lookup result and   forwarding, based on the lookup result, the IPv6 packet with the updated 128-bit destination address in the destination address field of the IPv6 header.   
     
     
       33. The method of  claim 32 , wherein the first compact forwarding identifier is said removed by shifting the compact forwarding identifiers of the plurality of compact forwarding identifiers after the first compact identifier, with said shifted compact forwarding identifiers including the second compact forwarding identifier. 
     
     
       34. The method of  claim 32 , wherein the 128-bit destination address of the received IPv6 packet includes, in the following order: the compact forwarding identifier prefix, the first compact forwarding identifier, and the second compact forwarding identifier. 
     
     
       35. The method of  claim 32 , wherein the compact forwarding identifier prefix identifies an encoding format for the 128-bit destination address and the updated 128-bit destination address. 
     
     
       36. The method of  claim 32 , further comprising programming at least one of the one or more data structures with an entry including the compact forwarding identifier prefix and the second compact forwarding identifier. 
     
     
       37. The method of  claim 36 , wherein the programming of the entry is responsive to a received advertisement from a remote network node that is associated with an Internet Protocol (IP) route including the compact forwarding identifier prefix and the second compact forwarding identifier. 
     
     
       38. The method of  claim 32 , wherein the highest-order bits of the updated 128-bit destination address are the compact forwarding identifier prefix followed by the second compact forwarding identifier; and wherein the lookup operation is a longest prefix matching operation. 
     
     
       39. The method of  claim 32 , wherein said zero or more additional compact forwarding identifiers includes a third compact forwarding identifier; and
 wherein a third destination address includes the compact forwarding identifier prefix and the third compact forwarding identifier;   wherein the destination address of the received IPv6 packet includes encoded therein the first destination address, the second destination address, and a third destination address; and   wherein the updated destination address includes encoded therein the second destination address and the third destination address.   
     
     
       40. The method of  claim 32 , wherein the compact forwarding identifier prefix identifies an address space. 
     
     
       41. The method of  claim 32 , further comprising transmitting one or more messages advertising that a packet switching device including the network interface is associated with an an Internet Protocol (IP) route including the compact forwarding identifier prefix and the first compact forwarding identifier. 
     
     
       42. The method of  claim 32 , further comprising:
 programming at least one of the one or more data structures with a first entry including the compact forwarding identifier prefix and the first compact forwarding identifier, and with a second entry including the compact forwarding identifier prefix and the second compact forwarding identifier;   processing the received IPv6 packet in response to a first lookup operation performed in at least one of said forwarding data structures based on the destination address resulting in a match of the first entry;   wherein the second lookup operation matched the second entry in identifying the lookup result:   wherein the lookup operation in one or more data structures based on the updated 128-bit destination address results in a match of the second entry, with the lookup result determined based on the match of the second entry; and   wherein said processing the received IPv6 packet includes said changing the destination address, said performing the lookup operation in one or more data structures based on the updated 128-bit destination address resulting in the lookup result, and said forwarding the IPv6 packet.