Access list key compression

• US 7,367,052 B1
• Filed: 12/04/2002
• Issued: 04/29/2008
• 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): HENEGHAN, MATTHEW E
• Application Number:
  US10/313,751
• Time in Patent Office: 1,973 Days
• Field of Search: 726/3
• 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. A method of composing an access list key for accessing information associated with a packet from an access list, the packet having 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, comprising:

obtaining an IP source address from the IP source address field of the packet;

obtaining an IP destination address from the IP destination address field of the packet;

generating a modified IP source address 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, wherein generating the modified IP source address includes removing one or more bits from the obtained IP source address;

generating a modified IP destination address 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, wherein generating the modified IP destination address includes removing one or more bits from the obtained IP destination address;

composing the access list key from the modified IP source address and the modified IP destination address;

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

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

2. The method as recited in claim 1, further comprising:

classifying the packet prior to composing the access list key, thereby enabling the access list key to be composed according to an access list key format.

3. The method as recited in claim 2, 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.

4. The method as recited in claim 1, further comprising:

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;

handling the packet in hardware when the packet is classified as being compatible with one of the first set of one or more protocols; and

handling the packet in software when the packet is classified as being compatible with one of the second set of one or more protocols.

5. The method as recited in claim 4, 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.

6. The method as recited in claim 1, wherein generating a 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, wherein the middle consecutive 16 bits of the Interface_ID portion does not include the first or last bits of the Interface_ID portion.

7. The method as recited in claim 1, 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, wherein the middle consecutive 16 bits of the Interface_ID portion does not include the first or last bits of the Interface_ID portion.

8. The method as recited in claim 1, wherein generating a modified IP destination address comprises removing the first 16 bits of the obtained IP destination address and generating a modified IP source address comprises removing the first 16 bits of the obtained IP source address.

9. The method as recited in claim 8, 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.

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

11. The method as recited in claim 8, wherein the modified IP destination address includes a destination port number and the modified IP source address includes a source port number.

12. The method as recited in claim 8, wherein the access list key includes a SPI.

13. The method as recited in claim 8, 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.

14. The method as recited in claim 1, wherein generating a 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 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, wherein the middle consecutive 16 bits of the Interface_ID portion does not include the first or last bits of the Interface_ID portion.

15. The method as recited in claim 14, wherein the access list key includes a source port number and a destination port number.

16. The method as recited in claim 14, wherein the modified IP destination address includes a destination port number and the modified IP source address includes a source port number.

17. The method as recited in claim 14, wherein the access list key includes a SPI.

18. The method as recited in claim 14, 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.

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

20. The method as recited in claim 1, wherein the access list key is a policy access list key for accessing a policy access list.

21. The method as recited in claim 1, wherein the access list key is a QoS access list key for accessing a quality of service access list.

22. The method as recited in claim 1, wherein the access list key consists of 276 bits.

23. The method as recited in claim 1, wherein the access list key consists of 278 bits.

24. The method as recited in claim 1, further comprising:

accessing an access list using the access list key.

25. The method as recited in claim 1, further comprising:

accessing a TCAM using the access list key.

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

27. The method 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.

28. A method of composing an access list key for accessing information associated with a packet from an access list, the packet having 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, comprising:

obtaining an IP source address from the IP source address field of the packet;

obtaining an IP destination address from the IP destination address field of the packet;

generating a modified IP source address 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, wherein generating the modified IP source address includes removing one or more bits from the obtained IP source address;

generating a modified IP destination address 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, wherein generating the modified IP destination address includes removing one or more bits from the obtained IP destination address;

composing the access list key from the modified IP source address and the modified IP destination address;

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

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

classifying the packet prior to composing the access list key, thereby enabling the access list key to be composed according to an access list key format;

wherein classifying the packet comprises;

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;

wherein composing the 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.

29. A method of composing an access list key for accessing information associated with a packet from an access list, the packet having 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, comprising:

obtaining an IP source address from the IP source address field of the packet;

obtaining an IP destination address from the IP destination address field of the packet;

generating a modified IP source address 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;

generating a modified IP destination address 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;

composing the access list key from the modified IP source address and the modified IP destination address;

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

routing the packet according to information in the entry in the access list, wherein the modified IP destination address comprises a zone_ID.

30. The method as recited in claim 29, wherein the zone_ID replaces a multicast prefix of the obtained IP destination address when the IP destination address is a multicast address.

31. The method as recited in claim 29, wherein the zone_ID replaces a local use prefix of the obtained IP destination address when the IP destination address is a local use unicast address.

32. The method as recited in claim 29, wherein the zone_ID identifies a link local zone or a site local zone.

33. A method of composing an access list key for accessing information associated with a packet from an access list, the packet having 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, comprising:

obtaining an IP source address from the IP source address field of the packet;

obtaining an IP destination address from the IP destination address field of the packet;

generating a modified IP source address 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;

generating a modified IP destination address 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;

composing the access list key from the modified IP source address and the modified IP destination address;

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

routing the packet according to information in the entry in the access list, wherein the modified IP destination address includes a multicast-unicast bit that indicates whether the modified IP destination address is multicast or unicast.

34. A method of composing an access list key for accessing information associated with a packet from an access list, the packet having 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, comprising:

obtaining an IP source address from the IP source address field of the packet;

obtaining an IP destination address from the IP destination address field of the packet;

generating a modified IP source address 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, wherein generating the modified IP source address includes removing one or more bits from the obtained IP source address;

generating a modified IP destination address 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, wherein generating the modified IP destination address includes removing one or more bits from the obtained IP destination address;

composing the access list key from the modified IP source address and the modified IP destination address;

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

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

wherein the modified IP source address and modified IP destination address each include two bits used to indicate whether the corresponding address is a link-local, site local, or global scoped address.

35. A method of composing an access list key for accessing information associated with a packet from an access list, the packet having 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, comprising:

obtaining an IP source address from the IP source address field of the packet;

obtaining an IP destination address from the IP destination address field of the packet;

generating a modified IP source address 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, wherein generating the modified IP source address includes removing one or more bits from the obtained IP source address;

generating a modified IP destination address 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, wherein generating the modified IP destination address includes removing one or more bits from the obtained IP destination address;

composing the access list key from the modified IP source address and the modified IP destination address;

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

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

wherein the modified IP source address comprises a zone_ID.

36. A method of composing an access list key for accessing information associated with a packet from an access list, the packet having 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, comprising:

obtaining an IP source address from the IP source address field of the packet;

obtaining an IP destination address from the IP destination address field of the packet;

generating a modified IP source address 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;

generating a modified IP destination address 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;

composing the access list key from the modified IP source address and the modified IP destination address;

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

routing the packet according to information in the entry in the access list, wherein the modified IP source address includes a zone_ID, wherein the zone_ID replaces a local use prefix of the obtained IP source address when the IP source address is a local use unicast address.

37. A method of composing an access list key for accessing information associated with a packet from an access list, the packet having 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, comprising:

obtaining an IP source address from the IP source address field of the packet;

obtaining an IP destination address from the IP destination address field of the packet;

generating a modified IP source address 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;

generating a modified IP destination address 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;

composing the access list key from the modified IP source address and the modified IP destination address;

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

routing the packet according to information in the entry in the access list, wherein the modified IP source address includes a zone_ID and wherein the zone_ID identifies a link local zone or a site local zone.

38. A method of composing an access list key for accessing information associated with a packet from an access list, the packet having 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, comprising:

obtaining an IP source address from the IP source address field of the packet;

obtaining an IP destination address from the IP destination address field of the packet;

generating a modified IP source address 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;

generating a modified IP destination address 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;

composing the access list key from the modified IP source address and the modified IP destination address;

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

routing the packet according to information in the entry in the access list, the access list key including a key bit indicating whether the access list key is a policy access list key or a QoS access list key.

39. A computer-readable medium storing thereon computer-readable instructions for composing an access list key for accessing information associated with a packet from an access list, the packet having 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, comprising:

instructions for obtaining an IP source address from the IP source address field of the packet;

instructions for obtaining an IP destination address from the IP destination address field of the packet;

instructions for generating a modified IP source address 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, wherein generating the modified IP source address includes removing one or more bits from the obtained IP source address;

instructions for generating a modified IP destination address 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, wherein generating the modified IP destination address includes removing one or more bits from the obtained IP destination address;

instructions for composing the access list key from the modified IP source address and the modified IP destination address;

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

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

40. An apparatus for composing an access list key for accessing information associated with a packet from an access list, the packet having 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, comprising:

a processor; and

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

obtaining an IP source address from the IP source address field of the packet;

obtaining an IP destination address from the IP destination address field of the packet;

generating a modified IP source address 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, wherein generating the modified IP source address includes removing one or more bits from the obtained IP source address;

generating a modified IP destination address 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, wherein generating the modified IP destination address includes removing one or more bits from the obtained IP destination address;

composing the access list key from the modified IP source address and the modified IP destination address;

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

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

41. An apparatus for composing an access list key for accessing information associated with a packet from an access list, the packet having 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, comprising:

means for obtaining an IP source address from the IP source address field of the packet;

means for obtaining an IP destination address from the IP destination address field of the packet;

means for generating a modified IP source address 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, wherein generating the modified IP source address includes removing one or more bits from the obtained IP source address;

means for generating a modified IP destination address 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, wherein generating the modified IP destination address includes removing one or more bits from the obtained IP destination address;

means for composing the access list key from the modified IP source address and the modified IP destination address;

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

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