Method and apparatus to improve network routing

• US 7,257,643 B2
• Filed: 05/16/2002
• Issued: 08/14/2007
• Est. Priority Date: 05/16/2002
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Vipat, Harshawardhan, Mathew, Philip P., Lewin, Michael R., Singh, Ranjeeta
• Primary Examiner(s): Cardone; Jason
• Assistant Examiner(s): Pollack; Melvin H.
• Application Number:
  US10/150,315
• Publication Number:
  US 20030217175A1
• Time in Patent Office: 1,916 Days
• Field of Search: 709/239, 709242-247, 709236-238, 709/232, 709/249, 711/202, 711/206, 711/207, 711/212, 711/220, 3703953-39532, 370/395.5, 370/409, 370/470, 370/471
• US Class Current: 709/238
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

A method and apparatus to route information in a network is described. A technique is described to search for routine information that uses a first technique on at least a portion of a first value of a network address and a second technique on at least a portion of a second section of an address. In particular, the first value is associated with an aggregation identifier, and compared to a unique prefix. In this way, address identifiers may be generated, and this identifier is used to search for routing information.

Claims

1. A method to search for routing information, comprising:

receiving a packet having a network address comprising a plurality of aggregation identifiers and an interface identifier;

retrieving a first value from said network address, said first value associated with one or more of said aggregation identifiers based on a level of aggregation at which said packet is received;

comparing said first value with a predetermined value comprising a unique prefix based on the level of aggregation;

retrieving a second value from said network address if said first value matches said predetermined value, said second value comprising at least all of said interface identifier and one or more of said plurality of aggregation identifiers not associated with said first value;

generating an address identifier based on said network address using only said second value if said first value matches said predetermined value, said address identifier comprising fewer bits than said network address; and

searching for routing information for said packet using said address identifier instead of said network address.

2. The method of claim 1, further comprising generating said address identifier using said first value and said second value if said first value fails to match said predetermined value.

3. The method of claim 1, wherein said network address comprises a 128-bit address assigned in accordance with Internet Protocol Version Six.

4. The method of claim 1, wherein said first value comprises a prefix based on an aggregation identifier.

5. The method of claim 4, wherein said aggregation identifier comprises at least one of a top-level aggregation identifier (TLA), next-level aggregation identifier (NLA) and site-level aggregation identifier (SLA).

6. The method of claim 1, wherein said interface identifier comprises a media access control (MAC) layer identifier.

7. The method of claim 1, wherein said interface identifier comprises 64 bits.

8. The method of claim 1, wherein said predetermined value comprises a prefix based on an aggregation identifier.

9. The method of claim 8, wherein said aggregation identifier comprises at least one of a top-level aggregation identifier (TLA), next-level aggregation identifier (NLA) and site-level aggregation identifier (SLA).

10. The method of claim 1, further comprising sending said packet using said routing information.

11. A routing apparatus, comprising:

a receive interface to receive a packet with a network address comprising a plurality of aggregation identifiers and an interface identifier;

an address identifier generator to retrieve a first value from said network address, said first value associated with one or more of said aggregation identifiers based on a level of aggregation at which said packet is received, to compare said first value with a predetermined value comprising a unique prefix based on the level of aggregation, to retrieve a second value from said network address if said first value matches said predetermined value, said second value comprising at least all of said interface identifier and one or more of said plurality of aggregation identifiers not associated with said first value, and to generate an address identifier based on said network address using only said second value if said first value matches said predetermined value, said address identifier comprising fewer bits than said network address; and

a routing module to retrieve routing information using said address identifier instead of said network address.

12. The apparatus of claim 11, further comprising a transmit interface to transmit said packet using said routing information.

13. The apparatus of claim 11, wherein said address identifier generator comprises:

an address extraction module to extract a prefix from said network address;

a comparator module to compare said prefix with a predetermined value; and

a decision module to generate said address identifier using part of said network address if said prefix matches said predetermined value, otherwise generating said address identifier using said entire network address.

14. A system to perform routing in a network, comprising:

a source node to send a packet using a network address comprising a plurality of aggregation identifiers and an interface identifier;

a destination node corresponding to said network address to receive said packet; and

an intermediate node to route said packet between said source node and said destination node, said intermediate node having an address identifier generator to retrieve a first value from said network address, said first value associated with one or more of said aggregation identifiers based on a level of aggregation at which said packet is received, to compare said first value with a predetermined value comprising a unique prefix based on the level of aggregation, to retrieve a second value from said network address if said first value matches said predetermined value, said second value comprising at least all of said interface identifier and one or more of said plurality of aggregation identifiers not associated with said first value, and to generate an address identifier based on said network address using only said second value if said first value matches said predetermined value, said address identifier comprising fewer bits than said network address, said intermediate node further having a routing apparatus to route said packet using said address identifier instead of said network address.

15. An article comprising:

a storage medium;

said storage medium including stored instructions that, when executed by a processor, result in searching for routing information by receiving a packet having a network address comprising a plurality of aggregation identifiers and an interface identifier, retrieving a first value from said network address, said first value associated with one or more of said aggregation identifiers based on a level of aggregation at which said packet is received, comparing said first value with a predetermined value comprising a unique prefix based on the level of aggregation, retrieving a second value from said network address if said first value matches said predetermined value, said second value comprising at least all of said interface identifier and one or more of said plurality of aggregation identifiers not associated with said first value, generating an address identifier based on said network address using only said second value if said first value matches said predetermined value, said address identifier comprising fewer bits than said network address, and searching for routing information for said packet using said address identifier instead of said network address.

16. The article of claim 15, wherein the stored instructions, when executed by a processor, further result in sending said packet using said routing information.