Access list key compression

• US 8,782,739 B2
• Filed: 03/19/2008
• Issued: 07/15/2014
• Est. Priority Date: 12/04/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: DeSanti, Claudio
• Primary Examiner(s): HENNING, MATTHEW T
• Application Number:
  US12/051,666
• Publication Number:
  US 20080165783A1
• Time in Patent Office: 2,309 Days
• US Class Current: 726/3
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/101 Access control lists [ACL]
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04L 69/325 in the network layer [OSI layer 3], e.g. X.25 H04L69/16 takes precedence

Abstract

Methods and apparatus for implementing an access list key for accessing information associated with a packet from an access list are disclosed. The packet includes an IP source address field and an IP destination address field, the IP source address field including an IP source address and the IP destination address field including an IP destination address, the IP source address and the IP destination address each having a number of bits (e.g., 128 bits in the case of IPv6). An IP source address is obtained from the IP source address field of the packet and an IP destination address is obtained from the IP destination address field of the packet. A modified IP source address is generated from the obtained IP source address such that the number of bits in the modified IP source address is less than the number of bits in the obtained IP source address. In addition, a modified IP destination address is generated from the obtained IP destination address such that the number of bits in the modified IP destination address is less than the number of bits in the obtained IP destination address. The access list key is then composed from the modified IP source address and the modified IP destination address.

Claims

1. An apparatus, comprising:

a processor; and

a memory, at least one of the processor or the memory being adapted for;

obtaining a packet, the packet including an IP source address and an IP destination address;

composing a compressed access list key, at least in part, from

     1) a modified IP source address that has been generated from the IP source address but excludes a subset of bits from the IP source address and that includes a first Zone_ID replacing the subset of bits from the IP source address such that the modified IP source address includes fewer bits than the IP source address and/or from

     2) a modified IP destination address that has been generated from the IP destination address but excludes a subset of bits from the IP destination address and that includes a second Zone_ID replacing the subset of bits from the IP destination address such that the modified IP destination address includes fewer bits than the IP destination address; and

routing the packet using the compressed access list key.

2. The apparatus as recited in claim 1, wherein composing the compressed access list key comprises:

generating the modified IP source address including a subset of bits from the IP source address of the packet, wherein the modified IP source address does not include all bits from the IP source address; and

/or

generating the modified IP destination address including a subset of bits from the IP destination address of the packet, wherein the modified IP destination address does not include all bits from the IP destination address, wherein the compressed access list key includes the modified IP source address and the modified IP destination address.

3. The apparatus as recited in claim 2, wherein the IP source address and IP destination address are IPv6 addresses.

4. The apparatus as recited in claim 2, wherein generating the modified IP destination address comprises removing a consecutive 16 bits of the obtained IP destination address such that the modified IP destination address includes bits in the obtained IP destination address that have not been removed and generating the modified IP source address comprises removing a consecutive 16 bits of the obtained IP source address such that the modified IP source address includes bits in the obtained IP source address that have not been removed.

5. The apparatus as recited in claim 4, wherein the obtained IP destination address is an IPv6 address that is IPv4 compatible or mapped and wherein the obtained IP source address is an IPv6 address that is IPv4 compatible or mapped.

6. The apparatus as recited in claim 4, wherein the compressed access list key includes a source port number and a destination port number.

7. The apparatus as recited in claim 4, wherein the modified IP destination address includes a destination port number and the modified IP source address includes a source port number.

8. The apparatus as recited in claim 4, wherein the compressed access list key includes a SPI.

9. The apparatus as recited in claim 4, wherein the modified IP destination address includes a first half of a SPI and the modified IP source address comprises a second half of the SPI, the first half and the second half of the SPI together being a SPI used in the ESP protocol.

10. The apparatus as recited in claim 2, wherein generating a modified IP destination address comprises removing the middle 16 bits of the Interface_ID portion of the obtained IP destination address when the IP destination address is a unicast address such that the modified IP destination address includes bits in the obtained IP destination address that have not been removed and wherein generating a modified IP source address comprises removing the middle consecutive 16 bits of the Interface_ID portion of the obtained IP source address when the IP source address is a unicast address such that the modified IP source address includes bits in the obtained IP source address that have not been removed, wherein the middle consecutive 16 bits of the Interface_ID portion does not include the first or last bits of the Interface_ID portion.

11. The apparatus as recited in claim 10, wherein the compressed access list key includes a source port number and a destination port number.

12. The apparatus as recited in claim 10, wherein the modified IP destination address includes a destination port number and the modified IP source address includes a source port number.

13. The apparatus as recited in claim 10, wherein the compressed access list key includes a SPI.

14. The apparatus as recited in claim 1, wherein the protocol is one of the following protocols:

TCP, UDP, SCTP, ESP, and ICMP.

15. The apparatus as recited in claim 10, wherein the modified IP destination address includes a first half of a SPI and the modified IP source address comprises a second half of the SPI, the first half and the second half of the SPI together being a SPI used in the ESP protocol.

16. The apparatus as recited in claim 1, at least one of the processor or the memory being further adapted for:

classifying the packet to identify a protocol of the packet prior to composing the compressed access list key, thereby enabling the compressed access list key to be composed according to an access list key format.

17. The apparatus as recited in claim 16, wherein classifying the packet comprises:

obtaining contents of a Next_Header field of the packet to determine the protocol of the packet, wherein the protocol determines the access list key format.

18. The apparatus as recited in claim 1, at least one of the processor or the memory being further adapted for:

classifying the packet as being compatible with one of a first set of one or more protocols or a second set of one or more protocols; and

routing the packet in hardware when the packet is classified as being compatible with one of the first set of one or more protocols, wherein the packet is not routed in hardware when the packet is classified as being compatible with one of the second set of one or more protocols.

19. The apparatus as recited in claim 18, wherein the packet is classified as being compatible with one of the second set of protocols when the packet is not classified as being compatible with one of the first set of protocols.

20. The apparatus as recited in claim 1, at least one of the processor or the memory being further adapted for:

generating the modified IP destination address including a subset of bits from the IP destination address of the packet;

wherein composing the compressed access list key comprises generating the compressed access list key based, at least in part, on the modified IP destination address, wherein the modified IP destination address comprises the second zone_ID.

21. The apparatus as recited in claim 20, wherein the second zone_ID replaces a multicast prefix of the IP destination address when the IP destination address is a multicast address.

22. The apparatus as recited in claim 20, wherein the second zone_ID replaces a local use prefix of the IP destination address when the IP destination address is a local use unicast address.

23. The apparatus as recited in claim 20, wherein the second zone_ID identifies a link local zone or a site local zone.

24. The apparatus as recited in claim 1, wherein the IP source address and the IP destination address are IPv6 addresses.

25. The apparatus as recited in claim 1, wherein routing the packet using the compressed access list key comprises:

identifying an entry in an access list using the compressed access list key that has been composed; and

routing the packet according to information in the entry in the access list.

26. The apparatus as recited in claim 25, wherein the compressed access list key is a policy access list key, and wherein the access list is a policy access list.

27. The apparatus as recited in claim 25, wherein the compressed access list key is a QoS access list key, and wherein the access list is a quality of service access list.

28. The apparatus as recited in claim 25, the compressed access list key including a key bit indicating whether the compressed access list key is a compressed policy access list key for accessing a policy access list or a compressed QoS access list key for accessing a quality of service access list.

29. The apparatus as recited in claim 25, wherein the access list is implemented in a TCAM.

30. The apparatus as recited in claim 1, wherein the IP source address and the IP destination address are each 128 bits long.

31. The apparatus as recited in claim 1, wherein the packet is an IPv6 packet, the IP source address is an IPv6 address and the IP destination address is an IPv6 address.

32. The apparatus as recited in claim 1, at least one of the processor or the memory being further adapted for:

generating the modified IP source address including a subset of bits from the IP source address of the packet such that the modified IP source address includes fewer bits than the IP source address;

wherein composing the compressed access list key comprises generating the compressed access list key based, at least in part, on the modified IP source address.

33. The apparatus as recited in claim 32, wherein the modified IP source address comprises the first zone_ID.

34. The apparatus as recited in claim 33, wherein the first zone_ID replaces a local use prefix of the obtained IP source address when the IP source address is a local use unicast address.

35. The apparatus as recited in claim 33, wherein the first zone_ID identifies a link local zone or a site local zone.

36. The apparatus as recited in claim 32, wherein the compressed access list key includes the modified IP source address.

37. The apparatus as recited in claim 32, wherein generating the modified IP source address comprises removing the middle consecutive 16 bits of the Interface_ID portion of the obtained IP source address when the IP source address is a unicast address such that the modified IP source address includes bits in the obtained IP source address that have not been removed, wherein the middle consecutive 16 bits of the Interface_ID portion does not include the first or last bits of the Interface_ID portion.

38. The apparatus as recited in claim 32, wherein generating the modified IP source address comprises:

removing one or more bits from the obtained IP source address such that the modified IP source address is generated to include bits in the obtained IP source address that have not been removed.

39. The apparatus as recited in claim 1, at least one of the processor or the memory being further adapted for:

generating the modified IP destination address including a subset of bits from the IP destination address of the packet such that the modified IP destination address includes fewer bits than the IP destination address;

wherein composing the compressed access list key comprises generating the compressed access list key based, at least in part, on the modified IP destination address.

40. The apparatus as recited in claim 39, wherein the compressed access list key includes the modified IP destination address.

41. The apparatus as recited in claim 39, wherein generating the modified IP destination address comprises:

removing one or more bits from the obtained IP destination address such that the modified IP destination address is generated to include bits in the obtained IP destination address that have not been removed.

42. The apparatus as recited in claim 39, wherein the modified IP destination address further comprises a multicast-unicast bit that indicates whether the modified IP destination address is multicast or unicast.

43. The apparatus as recited in claim 39, wherein the modified IP destination address comprises a set of bits that indicate whether the corresponding address is a link-local, site local, or global scoped address.

44. The apparatus as recited in claim 39, wherein generating the modified IP destination address comprises removing the middle consecutive 16 bits of the Interface_ID portion of the obtained IP destination address when the IP destination address is a unicast address such that the modified IP destination address includes bits in the obtained IP destination address that have not been removed, wherein the middle consecutive 16 bits of the Interface_ID portion does not include the first or last bits of the Interface_ID portion.

45. The apparatus as recited in claim 1, wherein composing the compressed access list key is performed based, at least in part, upon 1) a subset of bits from the IP destination address but not all bits from the IP destination address or 2) a subset of bits from the IP source address but not all bits from the IP source address.

46. The apparatus as recited in claim 1, wherein composing the compressed access list key comprises:

determining an access list key format of the compressed access list key to be composed based, at least in part, upon a protocol of the packet;

generating the compressed access list key according to the access list key format.

47. The apparatus as recited in claim 1, wherein the subset of bits from the IP source address is a prefix of the IP source address and wherein the subset of bits from the IP destination address is a prefix of the IP destination address.

48. The apparatus as recited in claim 1, wherein composing a compressed access list key is performed according to a protocol of the packet.

49. The apparatus as recited in claim 1, wherein the packet is transmitted via IPv6.

50. An apparatus, comprising:

a processor; and

a memory, at least one of the processor or the memory being adapted for;

ascertaining a protocol of a packet, the packet including an IP source address and an IP destination address;

determining whether the packet is compatible with one of a first set of protocols including TCP, UDP, and SCTP, a second set of protocols including ICMP, or a third set of protocols including ESP;

composing a compressed access list key according to the protocol of the packet, wherein composing the compressed access list key is performed according to an access list key format, the access list key format being a first format when the packet is compatible with one of the first set of protocols or the third set of protocols, a second format when the packet is compatible with one of the second set of protocols, or a third format when the packet is not classified as being compatible with one of the first, second, or third set of protocols; and

routing the packet using the compressed access list key.

51. An apparatus, comprising:

a processor; and

a memory, at least one of the processor or the memory being adapted for;

obtaining a packet, the packet including an IP source address and an IP destination address;

composing a compressed access list key based, at least in part, upon at least a subset of bits in the IP source address and/or at least a subset of bits in the IP destination address;

identifying an entry in an access list using the compressed access list key that has been composed; and

routing the packet according to information in the entry in the access list, the compressed access list key including a key bit indicating whether the compressed access list key is a compressed policy access list key for accessing a policy access list or a compressed QoS access list key for accessing a quality of service access list.

52. A non-transitory computer-readable medium for storing thereon computer-readable instructions, comprising:

instructions for composing a compressed access list key based, at least in part, upon at least a subset of bits in an IP source address of a packet and/or at least a subset of bits in an IP destination address of the packet;

instructions for identifying an entry in an access list using the compressed access list key that has been composed; and

instructions for routing the packet according to information in the entry in the access list, the compressed access list key including a key bit indicating whether the compressed access list key is a compressed policy access list key for accessing a policy access list or a compressed QoS access list key for accessing a quality of service access list.

53. An apparatus, comprising:

a processor; and

a memory, at least one of the processor or the memory being adapted for;

obtaining a packet, the packet including an IP source address and an IP destination address;

generating a modified IP destination address including first subset of bits in the IP destination address, wherein the modified IP destination address does not include a second subset of bits from the IP destination address, wherein the modified IP destination address includes one or more bits that replace the second subset of bits;

composing a compressed access list key based, at least in part, from the modified IP destination address that has been generated from the IP destination address;

identifying an entry in an access list using the compressed access list key; and

routing the packet according to information in the entry in the access list;

wherein the number of bits in the modified IP destination address is less than the number of bits in the IP destination address.

54. The apparatus as recited in claim 53, wherein the access list key is composed based, at least in part, upon a protocol of the packet.

55. The apparatus as recited in claim 53, wherein the one or more bits in the modified IP destination address includes 1) a multicast-unicast bit that indicates whether the modified IP destination address is multicast or unicast and/or 2) a set of bits that indicates whether the modified IP destination address is a link-local, site local, or global scoped address.