# US 8,782,739 B2 · Access list key compression > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,782,739 B2 - Document ID: US8782739B2 - Status: Granted - Kind: B2 - Application number: 12/051,666 - Filed: 2008-03-19 - Published: 2008-07-10 - Granted: 2014-07-15 - Earliest claimed: 2002-12-04 - Assignees: Cisco Technology, Inc. - Applicants: Claudio DeSanti - Inventors: Claudio DeSanti - Web page: https://patentgrep.com/patent/US8782739B2 ## CPC - H04L 63/101: {Access control lists [ACL]} - H04L 63/06: {for supporting key management in a packet data network (cryptographic mechanisms or cryptographic arrangements for key management H04L9/08)} - H04L 69/04: Protocols for data compression, e.g. ROHC - H04L 69/325: in the network layer [OSI layer 3], e.g. X.25 (H04L69/16 takes precedence) - H04L 45/16: Multipoint routing - H04L 49/3009: {Header conversion, routing tables or routing tags} - H04L 69/22: Parsing or analysis of headers - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## 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 ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 2) The apparatus as recited in claim 2, wherein the IP source address and IP destination address are IPv6 addresses. ### Claim 4 (depends on 2) 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. ### Claim 5 (depends on 4) 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. ### Claim 6 (depends on 4) The apparatus as recited in claim 4, wherein the compressed access list key includes a source port number and a destination port number. ### Claim 7 (depends on 4) 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. ### Claim 8 (depends on 4) The apparatus as recited in claim 4, wherein the compressed access list key includes a SPI. ### Claim 9 (depends on 4) 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. ### Claim 10 (depends on 2) 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. ### Claim 11 (depends on 10) The apparatus as recited in claim 10, wherein the compressed access list key includes a source port number and a destination port number. ### Claim 12 (depends on 10) 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. ### Claim 13 (depends on 10) The apparatus as recited in claim 10, wherein the compressed access list key includes a SPI. ### Claim 14 (depends on 1) The apparatus as recited in claim 1, wherein the protocol is one of the following protocols: TCP, UDP, SCTP, ESP, and ICMP. ### Claim 15 (depends on 10) 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. ### Claim 16 (depends on 1) 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. ### Claim 17 (depends on 16) 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. ### Claim 18 (depends on 1) 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. ### Claim 19 (depends on 18) 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. ### Claim 20 (depends on 1) 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. ### Claim 21 (depends on 20) 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. ### Claim 22 (depends on 20) 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. ### Claim 23 (depends on 20) The apparatus as recited in claim 20, wherein the second zone_ID identifies a link local zone or a site local zone. ### Claim 24 (depends on 1) The apparatus as recited in claim 1, wherein the IP source address and the IP destination address are IPv6 addresses. ### Claim 25 (depends on 1) 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. ### Claim 26 (depends on 25) 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. ### Claim 27 (depends on 25) 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. ### Claim 28 (depends on 25) 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. ### Claim 29 (depends on 25) The apparatus as recited in claim 25, wherein the access list is implemented in a TCAM. ### Claim 30 (depends on 1) The apparatus as recited in claim 1, wherein the IP source address and the IP destination address are each 128 bits long. ### Claim 31 (depends on 1) 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. ### Claim 32 (depends on 1) 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. ### Claim 33 (depends on 32) The apparatus as recited in claim 32, wherein the modified IP source address comprises the first zone_ID. ### Claim 34 (depends on 33) 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. ### Claim 35 (depends on 33) The apparatus as recited in claim 33, wherein the first zone_ID identifies a link local zone or a site local zone. ### Claim 36 (depends on 32) The apparatus as recited in claim 32, wherein the compressed access list key includes the modified IP source address. ### Claim 37 (depends on 32) 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. ### Claim 38 (depends on 32) 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. ### Claim 39 (depends on 1) 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. ### Claim 40 (depends on 39) The apparatus as recited in claim 39, wherein the compressed access list key includes the modified IP destination address. ### Claim 41 (depends on 39) 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. ### Claim 42 (depends on 39) 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. ### Claim 43 (depends on 39) 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. ### Claim 44 (depends on 39) 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. ### Claim 45 (depends on 1) 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. ### Claim 46 (depends on 1) 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. ### Claim 47 (depends on 1) 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. ### Claim 48 (depends on 1) The apparatus as recited in claim 1, wherein composing a compressed access list key is performed according to a protocol of the packet. ### Claim 49 (depends on 1) The apparatus as recited in claim 1, wherein the packet is transmitted via IPv6. ### Claim 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. ### Claim 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. ### Claim 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. ### Claim 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. ### Claim 54 (depends on 53) 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. ### Claim 55 (depends on 53) 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.