Method and apparatus for managing network traffic using cyclical redundancy check hash functions

• US 20050108617A1
• Filed: 11/13/2003
• Published: 05/19/2005
• Est. Priority Date: 11/13/2003
• Status: Active Grant

• Current Assignee: Nokia Corporation
• Original Assignee: Nokia, Inc. (Nokia Corporation)
• Inventors: Lappin, James B. Jr.
• Granted Patent: US 7,047,453 B2
• Time in Patent Office: Days
• US Class Current: 714/781
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Methods, apparatus and systems are directed to managing network traffic using a variable length Cyclical Redundancy Check (CRC) index to hash an address header. The invention copies an address header of a data packet to a CRC generator. A CRC index is determined based, in part, on the address header. A subset of bits is determined from the CRC index based, in part, on a predetermined bit mask. The address header and the data payload are then combined with the subset of bits from the CRC index. The modified data packet is subsequently forwarded over a network. In one embodiment, the invention is implemented on a hardware circuit residing on a traffic device.

Claims

1. An apparatus for managing a signal over a network, comprising:

a Cyclical Redundancy Check (CRC) circuit configured to receive at least a portion of the signal and determine a CRC index based, in part, on the portion of the signal;

a scaling circuit, coupled to the CRC circuit, that is configured to determine at least one bit from the CRC index; and

a reinsertion circuit, coupled to the scaling circuit, that is configured to determine a modified signal by combining the at least one bit selected from the CRC index with the signal, wherein the at least one bit selected from the CRC index enables routing of the modified signal over the network.

2. The apparatus of claim 1, wherein the portion of the signal further comprises an address header.

3. The apparatus of claim 1, wherein the at least one bit further comprises at least one bit determined by AND'"'"'ing the CRC index with a predetermined bit mask.

4. The apparatus of claim 1, wherein the at least one bit further comprises at least one of a non-consecutive number of bits, at least two bits, a consecutive number of bits, and all of the bits.

5. The apparatus of claim 1, wherein the portion of the signal further comprises at least one of a source address, a destination address, a source port, a destination port, and a protocol.

6. The apparatus of claim 1, wherein the CRC circuit further comprises a circuit that is arranged to perform actions, including at least one of a 32-bit CRC polynomial computation and a 128-bit CRC polynomial computation.

7. The apparatus of claim 1, wherein the CRC circuit further comprises at least one of a shift register, a memory, and an XOR-FlipFlop chain.

8. The apparatus of claim 1, wherein the scaling circuit further comprises:

a hash length store configured to hold a predetermined bit mask; and

an AND'"'"'ing circuit, coupled to the hash length store, that is arranged to select the at least one bit from the CRC index by combining the CRC index with the predetermined bit mask.

9. The apparatus of claim 8, wherein the hash length store further comprises at least one of a register and a memory.

10. The apparatus of claim 1, wherein the reinsertion circuit further comprising:

a buffer configured to hold the signal; and

a combination device, coupled to the buffer, that is configured to determine the modified signal, in part, by combining the at least one bit selected from the CRC index with the signal.

11. The apparatus of claim 10, wherein the buffer further comprises a First-In-First-Out (FIFO) buffer.

12. The apparatus of claim 10, wherein the combination device further comprises at least one of a multiplexer, a comparator, a memory, and an encoder.

13. A device for managing traffic over a network, comprising:

a transceiver that is arranged to perform actions, including;

receiving a data packet in a flow of data packets;

determining an address header associated with the data packet; and

forwarding the address header; and

an indexing device, coupled to the transceiver, that is arranged to perform actions, including;

receiving the address header;

determining a CRC index based, in part, on the address header;

determining a subset of bits from the CRC index; and

determining a modified data packet by combining the determined subset of bits from the CRC index with the data packet, wherein the subset of bits from the CRC index enables routing of the data packet over the network.

14. The device of claim 13, further comprising a reinsertion circuit that is coupled to the indexing device, and arranged to perform actions including:

reinserting the data packet into a data stream.

15. The device of claim 13, wherein the address header further comprises at least one of a source address, a destination address, a source port, a destination port, and a protocol.

16. The device of claim 13, wherein the device is operable in at least one of a load-balancer, a router, a firewall, a proxy, a bridge, and a network translation device.

17. The device of claim 13, wherein the subset of bits from the CRC index further comprises at least one of a non-consecutive number of bits, at least two bits, a consecutive number of bits, and all of the bits.

18. A method for routing traffic over a network, comprising:

receiving a data packet in a flow of data packets;

determining an address header associated with the data packet;

determining a CRC index based, in part, on the address header;

selecting at least one bit from the CRC index; and

determining a modified data packet by combining the at least one selected bit from the CRC index with the data packet, wherein the at least one selected bit from the CRC index enables routing of the data packet over the network.

19. The method of claim 18, further comprising:

reinserting the modified data packet into a data stream.

20. The method of claim 18, wherein the method is operable in at least one of a load-balancer, a router, a firewall, a proxy, a bridge, and a network translation device.

21. The method of claim 18, wherein the address header further comprises at least one of a source address, a destination address, a source port, a destination port, and a protocol.

22. The method of claim 18, further comprising:

determining a destination of the data packet by comparing the at least one selected bit from the CRC index to information in a routing table.

23. The method of claim 18, wherein determining the modified data packet further comprises at least one of prepending, appending, and encrypting the address header of the data packet with the at least one selected bit from the CRC index.

24. A device for routing a data packet over a network, comprising:

a means for receiving a data packet in a flow of data packets;

a means for determining an address header associated with the data packet;

a means for determining a CRC index based, in part, on the address header;

a means for selecting at least one bit from of the CRC index; and

a means for determining a modified data packet based, in part, on combining the at least one selected bit from the CRC index with the address header of the data packet, wherein the at least one selected bit from the CRC index enables routing of the data packet over the network.

25. A system for managing traffic over a network, comprising:

a first network device, configured to perform actions, comprising;

receiving a data packet in a flow of data packets;

determining an address header associated with the data packet;

determining a CRC index based, in part, on the address header;

selecting at least one bit from of the CRC index; and

determining a modified data packet by combining the at least one selected bit from the CRC index with the data packet; and

a second network device, in communication with the first network device, configured to perform actions, comprising;

receiving the modified data packet; and

routing the modified data packet based, in part, on the at least one selected bit from the CRC index.