Patent ID: 9699231
Date: 2017-07-04
CPC Classifications: H04L

Claim:
1. Apparatus operative in a data deduplication system, the system comprising a sending peer entity, and a receiving peer entity, the sending and receiving peer entities comprising overlay network content servers, wherein each entity supports a deduplication engine that provides stream-based data deduplication by examining data that flows through the peer entity and replacing blocks of the data with references that point into a data dictionary, the apparatus comprising: a data structure in association with the sending peer entity, the data structure representing temporal and ordered relationships among blocks of data that have been seen in the data stream by the sending peer entity, the data structure being a directed cyclic graph comprising one or more nodes, wherein a node represents a block of data and has associated therewith a label denoting a fingerprint associated with the block of data; and an encoding mechanism that uses information in the directed cyclic graph to replace one or more references to blocks of data that have been seen in the data stream by the sending peer entity by a compact data representation; wherein replacement of the one or more references is based on temporal locality at the sending peer of ordered blocks of data within the blocks of data that have been seen in the data stream.