Methods and apparatus for compression in packet classification

• US 8,675,648 B1
• Filed: 09/30/2008
• Issued: 03/18/2014
• Est. Priority Date: 09/30/2008
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Goel, Deepak, Panwar, Ramesh, Jagannadhan, Srinivasan
• Primary Examiner(s): RENNER, BRANDON M
• Application Number:
  US12/242,143
• Time in Patent Office: 1,995 Days
• Field of Search: 370/230, 370/230.1, 370/231, 370/389, 370/392, 709/232, 709/233
• US Class Current: 370/389
• CPC Class Codes: H04L 49/10 characterised by the switching fabric construction
• CPC Class Codes: H04L 49/118 Address processing within a device, e.g. using internal ID or tags for routing within a switch

Abstract

In one embodiment, a method includes receiving a policy vectors associated with a switch fabric, determining a compression scheme, and producing a compressed vector based on the policy vector and the compression scheme. The policy vector is represented by a bit sequence and has a plurality of policy bit values. A policy bit value from the plurality of policy bit vales is configured to trigger an action associated with a data packet in the switch fabric. The compression scheme is determined based on a portion of the policy vector.

Claims

1. A method, comprising:

receiving a policy vector associated with a switch fabric and represented by a bit sequence, the policy vector including a plurality of sectors and having a plurality of policy bit values, a policy bit value from the plurality of policy bit values configured to trigger an action associated with a data packet by the switch fabric;

producing a compressed vector for each sector in a subset of sectors from the plurality of sectors using a compression scheme that is based on a number of repeated policy bit values from the plurality of policy bit values in the policy vector;

matching the compressed vector for the each sector in the subset of sectors from the plurality of sectors to a portion of a data packet; and

forwarding at least the portion of a data packet, in addition to the compressed vector, to a decompression module.

2. The method of claim 1, wherein the compression scheme is a composite compression scheme that is further based at least in part on an address value of a pattern of policy bit values in the policy vector, the pattern stored in a memory at a location represented by the address value.

3. The method of claim 1, wherein the producing includes defining a sequence of policy bit values within the policy vector as a pattern.

4. The method of claim 1, further comprising associating a compression scheme identifier with the compressed vector for the each sector in the subset of sectors to produce a modified compressed vector for the each sector in the subset of sectors, the compression scheme identifier representing the compression scheme.

5. The method of claim 1, wherein the compression scheme is a first compression scheme, the subset of sectors of the policy vector is a first subset of sectors of the policy vector, and the compressed vector for the each sector in the subset of sectors is a first compressed vector for the each sector in the subset of sectors,

the method further comprising:

determining a second compression scheme different from the first compression scheme based on a second subset of sectors of the policy vector; and

producing a second compressed vector for each sector in the second subset of sectors of the policy vector based on the second compression scheme.

6. A method, comprising:

receiving at least a portion of a data packet, in addition to a compressed vector representing a sector from a plurality of sectors of a policy vector associated with a switch fabric, the compressed vector having been matched to the portion of the data packet, the policy vector having a plurality of policy bit values, a policy bit value from the plurality of policy bit values configured to trigger an action associated with a data packet by the switch fabric;

determining a compression scheme for the sector based on a compression scheme identifier associated with the compressed vector, the compression scheme based on an address value of a pattern of policy bit values in the policy vector, the pattern stored in a memory at a location represented by the address value; and

decompressing the sector based on the compressed vector and the compression scheme.

7. The method of claim 6, wherein the compression scheme is a composite compression scheme that is further based at least in part on a repeated policy bit value in the policy vector.

8. The method of claim 6, further comprising retrieving from a memory, before the decompressing, a pattern associated with the compressed vector, the decompressing including producing a decompressed policy vector having the pattern.

9. The method of claim 6, wherein the sector of the policy vector is a first sector of the policy vector, the compression scheme is a first compression scheme, and the compressed vector is a first compressed vector,

the method further comprising:

receiving a second compressed vector associated with a second sector of the policy vector;

determining a second compression scheme of the second compressed vector based on a compression scheme identifier associated with the second compressed vector, the compression scheme of the second compressed vector being different from the first compression scheme of the first compressed vector; and

decompressing the second sector of the policy vector based on the second compression scheme and the second compressed vector.

10. The method of claim 6, wherein the sector of the policy vector is a first sector of the policy vector, the compression scheme is a first compression scheme, and the compressed vector is a first compressed vector,

the method further comprising:

receiving a second compressed vector associated with a second sector of the policy vector;

determining a second compression scheme of the second compressed vector based on a compression scheme identifier associated with the second compressed vector;

decompressing second sector of the policy vector based on the compression scheme of the second compressed vector and the second compressed vector; and

reconstructing the policy vector based on the first sector of the policy vector and the second sector of the policy vector.

11. An apparatus, comprising:

a first decompression logic configured to apply a first compression scheme to decompress a first compressed vector received in addition to a data packet, the first compressed vector having been matched to a first portion of the data packet, the first compressed vector uniquely associated with a first subset of sectors of a policy vector at a first time, the policy vector being associated with a switch fabric, the policy vector being represented by a bit sequence, the first decompression logic configured to determine a placement of a repeated bit value in the bit sequence within the policy vector;

a first memory block operatively coupled to the first decompression logic, the first memory block being configured to store a bit sequence from the first subset of sectors of the policy vector;

a second decompression logic configured to apply a second compression scheme, different from the first compression scheme, to decompress a second compressed vector received with the data packet, the second compressed vector having been matched to a second portion of the data packet, the second compressed vector uniquely associated with a second subset of sectors of the policy vector at a second time, the second decompression logic configured to determine an address value of the bit sequence in the first memory block, the address value storing a pattern of policy bit values within the policy vector; and

a second memory block being operatively coupled to the second decompression logic, the second memory block being configured to store a bit sequence from the second subset of sectors of the policy vector.

12. The apparatus of claim 11, wherein:

the first decompression logic is configured to apply the first compression scheme to the first compressed vector based on a compression identifier associated with the first compressed vector; and

the second decompression logic is configured to apply the second compression scheme to the second compressed vector based on a compression identifier associated with the second compressed vector.

13. The apparatus of claim 11, wherein:

the first decompression logic is configured to apply one of a compression scheme based on a repeated bit value within the policy vector, a compression scheme based on an address value of the bit sequence in the first memory block, and a composite compression scheme based on a repeated bit value within the policy vector and an address value of the bit sequence in the first memory block; and

the second decompression logic is configured to apply one of a compression scheme based on a repeated bit value within the policy vector, a compression scheme based on an address value of the bit sequence in the first memory block, and a composite compression scheme based on a repeated bit value within the policy vector and an address value of the bit sequence in the second memory block.

14. The apparatus of claim 11, further comprising an output module configured to produce the policy vector based on the first compressed vector and the second compressed vector.

15. The apparatus of claim 11, wherein the first time is different than the second time.