DATA SEGMENTATION USING SHIFT-VARYING PREDICATE FUNCTION FINGERPRINTING

• US 20080159331A1
• Filed: 12/29/2006
• Published: 07/03/2008
• Est. Priority Date: 12/29/2006
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: Riverbed Technology Incorporated
• Inventors: Mace, James E, McCanne, Steven, Anderson, David B.
• Granted Patent: US 7,733,910 B2
• Time in Patent Office: Days
• US Class Current: 370/473
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/365 Dynamic adaptation of the packet size

Abstract

Shift-varying segmentation uses a shift-varying predicate function to evaluate input data within a sliding window to determine if the current sliding window position should be a segment boundary. The shift-varying predicate function is a function of both the input data within the sliding window and the position of the sliding window relative to a previous segment boundary or the beginning of the input data. The shift-varying predicate function includes a containment property and may compute a hash value from the input data in the sliding window. The hash value is compared to a threshold value that is a function of the sliding window position. As the sliding window position advances away from a previous segment boundary, the probability of a segment boundary at the window position increases. Shift-varying segmentation can be used in compression, transaction acceleration, and data storage applications.

Claims

1. A method of segmenting data for data processing, the method comprising:

initializing a data buffer including input data;

specifying a first value of a sliding window position in the data buffer;

selecting a portion of the input data corresponding with the sliding window;

determining if the sliding window position should be a segment boundary based on the selected portion of the input data and the first value of the sliding window position;

setting the segment boundary at the first value of the sliding window in response to the determination that the sliding window position should be the segment boundary; and

specifying a second value of the sliding window position in response to the determination that the sliding window position should not be the segment boundary.

2. The method of claim 1, wherein the first value of the sliding window position corresponds with a first potential segment size and the second value of the sliding window corresponds with a second potential segment size, and wherein the second potential segment size is greater than the first potential segment size.

3. The method of claim 2, wherein a probability of the first value of the sliding window position being set as the segment boundary is less than or equal to a probability of the second value of the sliding window position being set as the segment boundary.

4. The method of claim 2, wherein the first potential segment size is measured from a previous segment boundary to the first value of the sliding window position and the second potential segment size is measured from the previous segment boundary to the second value of the sliding window position.

5. The method of claim 2, wherein the first potential segment size is measured from a beginning of the input buffer to the first value of the sliding window position and the second potential segment size is measured from the beginning of the input buffer to the second value of the sliding window position.

6. The method of claim 1, wherein determining if the sliding window should be the segment boundary comprises:

determining a hash of the selected portion of the input data;

comparing the hash with a threshold value specified by a threshold function, wherein the threshold function is a function of the sliding window position;

specifying that the sliding window position should be the segment boundary in response to the comparison satisfying a condition; and

specifying that the sliding window position should not be the segment boundary in response to the comparison not satisfying the condition.

7. The method of claim 6, wherein the condition is that the hash is less than or equal to the threshold value and wherein the threshold function is a non-decreasing function of the sliding window position.

8. The method of claim 6, wherein the condition is that the hash is greater than or equal to the threshold value and wherein the threshold function is a non-increasing function of the sliding window position.

9. The method of claim 6, wherein the hash is determined using a rolling hash function.

10. The method of claim 6, wherein at least a portion of the threshold function is defined using a lookup table.

11. The method of claim 6, wherein at least a portion of the threshold function is defined using a stair-step function.

12. The method of claim 6, wherein the threshold function has a threshold value equal to a maximum possible value of the hash when the sliding window position corresponds with a maximum segment size.

13. The method of claim 6, wherein comparing the hash with the threshold value comprises performing a modulo operation on the hash value.

14. The method of claim 13, wherein the operand of the modulo operation is a function of the sliding window position.

15. The method of claim 13, wherein the operand of the modulo operation is a constant.

16. The method of claim 1, wherein determining if the sliding window position should be a segment boundary includes a containment property, such that if it is determined that the sliding window position should be the segment boundary for the selected portion of the input data and the first value of the sliding window position, it will also be determined that the sliding window position should be the segment boundary for another portion of the input data identical to the portion of the input data and any other value of the sliding window position greater than the first value of the sliding window position.

17. The method of claim 1, further comprising:

providing the segment boundary to a data compression module including logic adapted to represent the input data as a set of segments and references thereto.

18. The method of claim 1, further comprising:

providing the segment boundary to a communications acceleration module including logic adapted to communicate the input data to a second communications acceleration module as a set of segments and references thereto, such that the second communications acceleration module can create a reconstructed version of the input data.

19. The method of claim 1, wherein the second value of the sliding window position is one data unit greater than the first value of the sliding window position.

20. The method of claim 1, wherein the second value of the sliding window position is at least two data units greater than the first value of the sliding window position.

21. The method of claim 1, wherein initializing the data buffer comprises:

receiving at least a portion of a stream of input data and storing the portion of the stream of input data in the data buffer.

22. The method of claim 1, wherein initializing the data buffer comprises:

receiving at least a portion of a data file of input data and storing the portion of the data file of input data in the data buffer.

23. The method of claim 1, wherein the input data is binary data.

24. The method of claim 1, wherein the input data is character data.

25. The method of claim 1, wherein the input data is payload data for at least one network packet.

26. The method of claim 1, wherein the input data is a database object.

27. The method of claim 1, wherein the input data is XML data.

28. The method of claim 1, wherein the input data is a database object.

29. A computer readable storage medium including instructions adapted to direct a computer to perform an operation, the operation comprising:

initializing a data buffer including input data;

specifying a first value of a sliding window position in the data buffer;

selecting a portion of the input data corresponding with the sliding window;

determining if the sliding window position should be a segment boundary based on the selected portion of the input data and the first value of the sliding window position;

setting the segment boundary at the first value of the sliding window in response to the determination that the sliding window position should be the segment boundary; and

specifying a second value of the sliding window position in response to the determination that the sliding window position should not be the segment boundary.

30. The computer readable storage medium of claim 29, wherein the first value of the sliding window position corresponds with a first potential segment size and the second value of the sliding window corresponds with a second potential segment size, and wherein the second potential segment size is greater than the first potential segment size.

31. The computer readable storage medium of claim 30, wherein a probability of the first value of the sliding window position being set as the segment boundary is less than or equal to a probability of the second value of the sliding window position being set as the segment boundary.

32. The computer readable storage medium of claim 30, wherein the first potential segment size is measured from a previous segment boundary to the first value of the sliding window position and the second potential segment size is measured from the previous segment boundary to the second value of the sliding window position.

33. The computer readable storage medium of claim 30, wherein the first potential segment size is measured from a beginning of the input buffer to the first value of the sliding window position and the second potential segment size is measured from the beginning of the input buffer to the second value of the sliding window position.

34. The computer readable storage medium of claim 29, wherein determining if the sliding window should be the segment boundary comprises:

determining a hash of the selected portion of the input data;

comparing the hash with a threshold value specified by a threshold function, wherein the threshold function is a function of the sliding window position;

specifying that the sliding window position should be the segment boundary in response to the comparison satisfying a condition; and

specifying that the sliding window position should not be the segment boundary in response to the comparison not satisfying the condition.

35. The computer readable storage medium of claim 34, wherein the condition is that the hash is less than or equal to the threshold value and wherein the threshold function is a non-decreasing function of the sliding window position.

36. The computer readable storage medium of claim 34, wherein the condition is that the hash is greater than or equal to the threshold value and wherein the threshold function is a non-increasing function of the sliding window position.

37. The computer readable storage medium of claim 34, wherein the hash is determined using a rolling hash function.

38. The computer readable storage medium of claim 34, wherein at least a portion of the threshold function is defined using a lookup table.

39. The computer readable storage medium of claim 34, wherein at least a portion of the threshold function is defined using a stair-step function.

40. The computer readable storage medium of claim 34, wherein the threshold function has a threshold value equal to a maximum possible value of the hash when the sliding window position corresponds with a maximum segment size.

41. The computer readable storage medium of claim 34, wherein comparing the hash with the threshold value comprises performing a modulo operation on the hash value.

42. The computer readable storage medium of claim 41, wherein the operand of the modulo operation is a function of the sliding window position.

43. The computer readable storage medium of claim 41, wherein the operand of the modulo operation is a constant.

44. The computer readable storage medium of claim 29, wherein determining if the sliding window position should be a segment boundary includes a containment property, such that if it is determined that the sliding window position should be the segment boundary for the selected portion of the input data and the first value of the sliding window position, it will also be determined that the sliding window position should be the segment boundary for another portion of the input data identical to the portion of the input data and any other value of the sliding window position greater than the first value of the sliding window position.

45. The computer readable storage medium of claim 29, further comprising:

providing the segment boundary to a data compression module including logic adapted to represent the input data as a set of segments and references thereto.

46. The computer readable storage medium of claim 29, further comprising:

providing the segment boundary to a communications acceleration module including logic adapted to communicate the input data to a second communications acceleration module as a set of segments and references thereto, such that the second communications acceleration module can create a reconstructed version of the input data.

47. The computer readable storage medium of claim 29, wherein the second value of the sliding window position is one data unit greater than the first value of the sliding window position.

48. The computer readable storage medium of claim 29, wherein the second value of the sliding window position is at least two data units greater than the first value of the sliding window position.

49. The computer readable storage medium of claim 29, wherein initializing the data buffer comprises:

receiving at least a portion of a stream of input data and storing the portion of the stream of input data in the data buffer.

50. The computer readable storage medium of claim 29, wherein initializing the data buffer comprises:

receiving at least a portion of a data file of input data and storing the portion of the data file of input data in the data buffer.

51. The computer readable storage medium of claim 29, wherein the input data is binary data.

52. The computer readable storage medium of claim 29, wherein the input data is character data.

53. The computer readable storage medium of claim 29, wherein the input data is payload data for at least one network packet.

54. The computer readable storage medium of claim 29, wherein the input data is a database object.

55. The computer readable storage medium of claim 29, wherein the input data is XML data.

56. The computer readable storage medium of claim 29, wherein the input data is a database object.