Anycast addressing for internet protocol version six

• US 20050198367A1
• Filed: 12/29/2003
• Published: 09/08/2005
• Est. Priority Date: 12/29/2003
• Status: Active Grant

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Intel Corporation
• Inventors: Ettikan, Karuppiah Kandasamy
• Granted Patent: US 7,676,595 B2
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/167 Adaptation for transition between two IP versions, e.g. between IPv4 and IPv6 translation of Internet protocol [IP] addresses H04L61/2503

Abstract

A protocol associated with an Internet protocol version six (IPv6) network address included within a network packet provides both unicast and anycast addressing, while having the same bit locations and bit functions associated with a top-level aggregation identifier, a next-level aggregation identifier, and a site-level aggregation identifier. A prefix associated with the three most significant bits of the network address identifies the network address as being a unicast address, an anycast address, or both a unicast and an anycast address. The prefix that identifies the network address as being both a unicast and an anycast address allows routers to have smaller routing tables.

Claims

1. A network address, comprising:

prefix bits encoded to identify the network address as a selected one of a unicast network address, an anycast network address, and both the unicast and the anycast network address;

anycast scope identifier bits to identify an anycast scope, wherein the anycast scope corresponds to a network scope within which the anycast network address is recognized; and

anycast group identifier bits to identify an anycast group having one or more anycast members, wherein each of the one or more anycast members is associated with the same anycast network address.

2. The network address of claim 1, wherein the prefix bits include at least two prefix bits as the three most significant bits of the network address, and the anycast group identifier bits include at least thirty-two bits as the least significant bits of the network address.

3. The network address of claim 1, wherein the anycast scope bits include at least two bits adapted to identify a selected one of a node local scope, a link local scope, a site local scope, and a global scope.

4. The network address of claim 1, wherein the network address has a network address length of one hundred twenty eight bits, and the network address is compatible with Internet protocol version six (IPv6).

5. The network address of claim 4, wherein top level aggregation identifier, next-level aggregation identifier, and site-level aggregation identifier portions of the one hundred twenty eight network address bits are at the same bit locations and have the same function for both the anycast network address and for the unicast network address.

6. A network router including one or more routing tables having one or more entries, the entries comprising:

prefix bits encoded to identify the network address as a selected one of a unicast network address, an anycast network address, and both the unicast and the anycast network address;

anycast scope identifier bits to identify an anycast scope, wherein the anycast scope corresponds to a network scope within which the anycast network address is recognized; and

anycast group identifier bits to identify an anycast group having one or more anycast members, wherein each of the one or more anycast members is associated with the same anycast network address.

7. The network router of claim 6, wherein the prefix bits include at least two prefix bits as the three most significant bits of the network address, and the anycast group identifier bits include at least thirty-two bits as the least significant bits of the network address.

8. The network router of claim 6, wherein the anycast scope bits include at least two bits adapted to identify a selected one of a node local scope, a link local scope, a site local scope, and a global scope.

9. The network router of claim 6, wherein the network address has a network address length of one hundred twenty eight bits, and the network address is compatible with Internet protocol version six (IPv6).

10. The network router of claim 9, wherein top level aggregation identifier, next-level aggregation identifier, and site-level aggregation identifier portions of the one hundred twenty eight network address bits are at the same bit locations and have the same function for both the anycast network address and for the unicast network address.

11. A method of routing a network packet having a network address, comprising:

receiving the network packet; and

decoding prefix bits associated with the network address to identify the network address as being a selected one of a unicast network address and an anycast network address.

12. The method of claim 11, wherein the prefix bits include at least two bits encoded to indicate a selected one of the unicast network address, the anycast network address, and both the unicast network address and the anycast network address.

13. The method of claim 11, further including:

performing lookups associated with the network address in one or more routing tables;

identifying an output port from the successive lookups;

sending, if the output port is identified and if the network address is the unicast network address, the network packet to the identified output port; and

sending, if the output port is identified and if the network address is the anycast network address, the network packet to the identified output port.

14. The method of claim 13, further including:

if the output port is identified as more than one output port and if the network address is the anycast network address;

examining port metrics associated with the more than one output port;

identifying one output port from among the more than one output port based upon the metrics; and

sending the network packet to the identified output port.

15. The method of claim 13, wherein one of the one or more routing tables is associated with sixteen most significant bits of the network address.

16. The method of claim 13, wherein one of the one or more routing tables is associated with sixteen most significant bits of the network address and other ones of the one or more routing tables are associated with respective groups of eight bits of the network address.

17. A method of generating a routing table associated with a network packet having a network address, comprising:

receiving the network packet;

decoding prefix bits associated with the network address to identify the network address as being a selected one of a unicast network address and an anycast network address;

performing lookups associated with selected ones of the bits of the network address in one or more routing tables to identify a matching route stored in the one or more routing tables;

changing, if the matching route is identified and if the matching route corresponds to the unicast network address and if the network address is the anycast network address, the prefix bits associated with the matching route stored in the one or more routing tables to indicate that the matching route corresponds to both the unicast network address and the anycast network address; and

changing, if the matching route is identified and if the matching route corresponds to an anycast network address and if the network address is the unicast network address, the prefix bits associated with the matching route stored in the one or more routing tables to indicate that the matching route corresponds to both the unicast network address and the anycast network address.

18. The method of claim 17, wherein the selected ones of the bits of the network address correspond to sixty-one bits.

19. The method of claim 17, wherein the prefix bits include at least two bits encoded to indicate a selected one of the unicast network address, the anycast network address, and both the unicast network address and the anycast network address.

20. The method of claim 17, wherein one of the one or more routing tables is associated with sixteen most significant bits of the network address.

21. The method of claim 17, wherein one of the one or more routing tables is associated with sixteen most significant bits of the network address and other ones of the one or more routing tables are associated with respective groups of eight bits of the network address.

22. A computer readable medium having computer readable code thereon for routing a network packet having a network address, comprising:

instruction for receiving the network packet; and

instructions for decoding prefix bits associated with the network address to identify the network address as being a selected one of a unicast network address and an anycast network address.

23. The computer readable medium of claim 22, wherein the prefix bits include at least two bits encoded to indicate a selected one of the unicast network address, the anycast network address, and both the unicast network address and the anycast network address.

24. The computer readable medium of claim 22, further including:

instructions for performing lookups associated with the network address in one or more routing tables;

instructions for identifying an output port from the successive lookups;

instruction for deciding if the output port is identified and if the network address is the unicast network address, and in response thereto, instructions for sending the network packet to the identified output port; and

instruction for deciding if the output port is identified and if the network address is the anycast network address, and in response thereto, instructions for sending the network packet to the identified output port.

25. The computer programmable medium of claim 24, further including:

instruction for deciding if the output port is identified as more than one output port and if the network address is the anycast network address, and in response thereto;

instructions for examining port metrics associated with the more than one output port,

instructions for identifying one output port from among the more than one output port based upon the metrics; and

instructions for sending the network packet to the identified output port.

26. The computer readable medium of claim 24, wherein one of the one or more routing tables is associated with sixteen most significant bits of the network address.

27. The computer readable medium of claim 24, wherein one of the one or more routing tables is associated with sixteen most significant bits of the network address and other ones of the one or more routing tables are associated with respective groups of eight bits of the network address.

28. A computer readable medium having computer readable code thereon for generating a routing table associated with a network packet having a network address, comprising:

instructions for receiving the network packet;

instructions for decoding prefix bits associated with the network address to identify the network address as being a selected one of a unicast network address and an anycast network address;

instructions for performing lookups associated with selected ones of the bits of the network address in one or more routing tables to identify a matching route stored in the one or more routing tables;

instructions for deciding if the matching route is identified and if the matching route corresponds to the unicast network address and if the network address is the anycast network address, and in response thereto for changing the prefix bits associated with the matching route stored in the one or more routing tables to indicate that the matching route corresponds to both the unicast network address and the anycast network address; and

instructions for deciding if the matching route is identified and if the matching route corresponds to the anycast network address and if the network address is the unicast network address, and in response thereto for changing the prefix bits associated with the matching route stored in the one or more routing tables to indicate that the matching route corresponds to both the unicast network address and the anycast network address.

29. The computer readable medium of claim 28, wherein the selected ones of the bits of the network address correspond to sixty-one bits.

30. The computer readable medium of claim 28, wherein the prefix bits include at least two bits encoded to indicate a selected one of the unicast network address, the anycast network address, and both the unicast network address and the anycast network address.

31. The computer readable medium of claim 28, wherein one of the one or more routing tables is associated with sixteen most significant bits of the network address.

32. The computer readable medium of claim 28, wherein one of the one or more routing tables is associated with sixteen most significant bits of the network address and other ones of the one or more routing tables are associated with respective groups of eight bits of the network address.