Network interface device for error detection using partial CRCS of variable length message portions

• US 7,185,266 B2
• Filed: 02/12/2003
• Issued: 02/27/2007
• Est. Priority Date: 02/12/2003
• Status: Expired due to Fees

• Current Assignee: Alacritech, Inc.
• Original Assignee: Alacritech, Inc.
• Inventors: Philbrick, Clive M., Blightman, Stephen E. J., Starr, Daryl D.
• Primary Examiner(s): Lamarre; Guy
• Assistant Examiner(s): RIZK, SAMIR WADIE
• Application Number:
  US10/367,147
• Publication Number:
  US 20040158793A1
• Time in Patent Office: 1,476 Days
• Field of Search: 371/30, 371/35, 371/53, 371/48, 710/52, 714/766
• US Class Current: 714/776
• CPC Class Codes: H04L 69/10 Streamlined, light-weight or high-speed protocols, e.g. express transfer protocol [XTP] or byte stream
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A device and method are disclosed for calculating a CRC on a message or block of data that has been divided into portions, by calculating a partial CRC corresponding to each of the portions and then combining the partial CRCs. The device and method are operable for portions that may have different lengths, and which may be received out of order.

Claims

1. A method for receiving data by a host and an interface device, the method comprising:

receiving, by the interface device, a plurality of data portions that form a message when concatenated;

dividing, by the interface device, each of the portions by a divisor to create a portion remainder corresponding to each of the portions;

weighting, by the host, the portion remainders by factors based on dividing a length of the message data following the corresponding portion by the divisor, to form a plurality of weighted portion remainders;

adding, by the host, the weighted portion remainders to form a sum; and

dividing, by the host, the sum by the divisor to determine a remainder for the message.

2. The method of claim 1, further comprising calculating at least one of the factors by dividing the length by the divisor to obtain a length remainder.

3. The method of claim 1, wherein weighting the portion remainders by factors includes retrieving the factors from a table.

4. The method of claim 1, wherein weighting the portion remainders includes multiplying by the corresponding factors.

5. The method of claim 1, further comprising comparing the remainder for the message with a predetermined remainder.

6. The method of claim 1, further comprising determining whether the data portions are in a correct order to form the message when concatenated, prior to weighting the portion remainders by corresponding length remainders.

7. The method of claim 1, wherein the divisor is a polynomial.

8. The method of claim 1, wherein each of the remainders is a polynomial.

9. The method of claim 1, further comprising comparing the message remainder to a data digest.

10. A method for detecting errors, the method comprising:

receiving a plurality of portions in a first sequence that, when arranged in a second sequence, form a message;

determining whether the first sequence is identical to the second sequence; and

choosing, based at least in part upon whether the first sequence is identical to the second sequence, whether to perform a cyclic redundancy check in accordance with a first process or in accordance with a second process.

11. The method of claim 10, further comprising at least one of:

performing the cyclic redundancy check in accordance with the first process when the first sequence is identical to the second sequence; and

performing the cyclic redundancy check in accordance with the second process when the first sequence is not identical to the second sequence.

12. The method of claim 10, wherein determining whether the first sequence is identical to the second sequence includes performing Transmission Control Protocol (TCP) processing on a plurality of headers that correspond to the plurality of portions.

13. The method of claim 10, wherein at least one of the first and second processes includes computing a cyclic redundancy calculation on at least one of the portions, including dividing a numerical value corresponding to the portion by a divisor to detennine a remainder corresponding to the one portion.

14. The method of claim 13, wherein the first sequence is identical to the second sequence, and the first process includes:

prepending a portion consecutive to the one portion with the remainder to form a seeded portion; and

computing a cyclic redundancy calculation on the seeded portion.

15. The method of claim 13, wherein the first sequence is not identical to the second sequence, and the second process includes:

weighting the remainder according to a position of the one portion relative to a consecutive portion in the message, thereby creating a weighted remainder for the one portion; and

computing a cyclic redundancy calculation on the weighted remainder.

16. The method of claim 10, wherein the first sequence is not identical to the second sequence, and the second process includes:

computing a cyclic redundancy calculation on each of the portions, including dividing a numerical value corresponding to each said portion by a divisor to determine a partial remainder corresponding to each said portion;

weighting each partial remainder according to a factor remainder that is based on a position of the corresponding portion relative to at least one subsequent portion in the message, thereby creating a weighted remainder for each said portion.

17. The method of claim 16, wherein weighting each partial remainder according to a factor remainder includes multiplying each partial remainder by a remainder resulting from a cyclic redundancy calculation for a degree of the corresponding portion.

18. The method of claim 16, wherein weighting each partial remainder according to a factor remainder includes multiplying the partial remainder by a factor determined from a table.

19. The method of claim 10, further comprising concatenating the message to form a block of data.

20. The method of claim 10, further comprising receiving, with one of the portions, a data digest for the message.

21. A method for detecting errors, the method comprising:

receiving a plurality of portions in a first sequence that, when arranged in a second sequence, form a message;

performing a cyclic redundancy calculation on each of the portions to obtain a partial remainder corresponding to each of the portions;

determining whether the first sequence is identical to said second sequence; and

choosing, based upon whether the first sequence is identical to the second sequence, whether to perform a cyclic redundancy check in accordance with a first process or in accordance with a second process.

22. The method of claim 21, wherein determining whether the first sequence is identical to the second sequence includes performing Transmission Control Protocol (TCP) processing on a plurality of headers that correspond to the plurality of portions.

23. The method of claim 21, further comprising at least one of:

performing said cyclic redundancy check in accordance with the first process by seeding the partial remainders when the first sequence is identical to the second sequence; and

performing said cyclic redundancy check in accordance with the second process by weighting the partial remainders when the first sequence is not identical to said second sequence.

24. The method of claim 21, wherein the first sequence is identical to said second sequence, and the first process includes:

prepending a portion consecutive to the one portion with the remainder to form a seeded portion; and

computing a cyclic redundancy calculation on the seeded portion.

25. The method of claim 24, wherein the first sequence is not identical to the second sequence, and the second process includes:

weighting the remainder according to a position of the one portion relative to a consecutive portion in the message, thereby creating a weighted remainder for said one portion; and

computing a cyclic redundancy calculation on said weighted remainder.

26. The method of claim 21, wherein said message is a block of data.

27. The method of claim 21, wherein said cyclic redundancy check is part of a data digest.

28. A method for detecting errors by a first device and a second device, the method comprising:

receiving, by the first device, a plurality of portions in a first sequence that, when arranged in a second sequence, form a message;

computing, by the first device, a cyclic redundancy calculation on each of the portions, including dividing a numerical value corresponding to each said portion by a divisor to determine a remainder corresponding to each said portion,

weighting, by the second device, at least one of the remainders by a factor that is based on dividing a length of at least one portion subsequent to the corresponding portion by the divisor, thereby creating a weighted remainder for the portions;

adding, by the second device, the weighted remainders for the portions to obtain a sum of the weighted remainders;

dividing, by the second device, the sum by the divisor to obtain a cyclic redundancy remainder of the portions; and

comparing, by the second device, the cyclic redundancy remainder of the portions with a cyclic redundancy check accompanying one of the portions to determine whether the message has an error.

29. The method of claim 28, further comprising determining, prior to the weighting, that the first sequence is different than the second sequence.

30. The method of claim 28, wherein weighting at least one of the remainders by a factor includes retrieving the factor from a table.

31. The method of claim 28, wherein computing the cyclic redundancy calculation is performed on the portions prior to said weighting each said remainder.

32. The method of claim 28, wherein dividing said sum by said divisor to obtain a cyclic redundancy calculation of said subsequent portion is performed prior to adding said weighted remainders of all of said portions.

33. The method of claim 28, wherein adding said weighted remainders of said consecutive portions is performed on all of said remainders prior to said dividing said sum by said divisor.

34. The method of claim 28, wherein weighting each said remainder according to a position of its corresponding portion includes weighting each said remainder by a factor determined from a table.

35. The method of claim 28, wherein said first sequence is different than said second sequence.

36. The method of claim 28, wherein said divisor is a polynomial.

37. The method of claim 28, wherein said message is a block of data.

38. The method of claim 28, wherein said cyclic redundancy check is part of a data digest.

39. A method for detecting errors by a host and an interface device, the method comprising:

creating, for a series of numbers each representative of a consecutive order of magnitude, a series of factors each representing a remainder resulting from dividing one of the numbers by a divisor to obtain a remainder;

receiving, by the interface device, a plurality of segments in a first sequence that, when arranged in a second sequence, form a message;

computing, by the interface device, a cyclic redundancy calculation on at least one of the segments, including dividing a numerical value corresponding to the segment by the divisor to determine a remainder corresponding to the segment; and

multiplying, by the host, the segment remainder by a factor corresponding to the order of magnitude of the segment, thereby creating a weighted remainder for the segment.

40. The method of claim 39, further comprising computing a cyclic redundancy calculation on one other of the segments to obtain a partial remainder of the other segment, and adding the partial remainder to the weighted remainder.

41. The method of claim 39, further comprising determining that the first sequence is not identical to the second sequence, prior to the weighting.

42. The method of claim 39, further comprising:

receiving a plurality of parts in a third sequence that, when arranged in a fourth sequence, form a second message;

computing a cyclic redundancy calculation on at least one of the parts, including dividing a numerical value corresponding to the one part by the divisor to determine a partial remainder corresponding to the one part;

prepending the partial remainder to a part that is consecutive to the one part in the message, thereby forming a seeded consecutive part; and

computing a cyclic redundancy calculation on the seeded consecutive part.

43. The method of claim 39, further comprising determining that the third sequence is identical to the fourth sequence, prior to the prepending.

44. The method of claim 39, further comprising retrieving the factor from a table, prior to multiplying the segment remainder by the factor.

45. The method of claim 39, wherein the divisor is a polynomial.

46. The method of claim 39, wherein the message is a block of data.

47. The method of claim 39, further comprising receiving an iSCSI header along with the plurality of segments.

48. A method for detecting errors by a host and an interface device, the method comprising:

receiving, by the interface device, a plurality of portions in a first sequence that, when arranged in a second sequence, form a message;

computing, by the interface device, a cyclic redundancy check on each of the portions, including dividing a numerical value corresponding to each said portion by a divisor to determine a partial remainder corresponding to each said portion;

weighting, by the host, the partial remainder corresponding to a first portion of the second sequence by a remainder resulting from dividing by the divisor a degree of the first portion within the message to create a first weighted remainder,

adding the first weighted remainder to a remainder corresponding to the second portion to obtain a weighted sum of partial remainders;

dividing the sum by said divisor to obtain an overall remainder for the portions; and

comparing said overall remainder with a cyclic redundancy check prepended to one of said portions to determine whether said message has an error.