Patent Document

BACKGROUND 
       [0001]    With the advent of globalization, networked services have a global audience, both in the consumer and enterprise spaces. For example, a large corporation today may have branch offices at dozens of cities around the globe. In such a setting, the corporation&#39;s information technology (IT) administrators and network planners face a dilemma. On the one hand, they could centralize or concentrate the servers that power the corporation&#39;s IT services (such as e-mail and file servers) at one or a small number of locations. This would keep administration costs low but may drive up network costs and also hurt performance, because what would have normally been local-area network (LAN) traffic becomes wide-area network (WAN) traffic. On the other hand, the servers and services could be distributed to be closer to clients. However, this would likely drive up the complexity and cost of developing and administering the services. 
         [0002]    Having both would be ideal, specifically, having the operational benefits of centralization along with the performance benefits of distribution. In recent years, protocol-independent redundancy elimination (RE) has emerged as a powerful technique to help bridge the gap by making WAN communication more efficient through elimination of redundancy in traffic. Such compression is typically applied at the internet protocol (IP) or transmission control protocol (TCP) layer. For example, this compression can use a pair of middleboxes placed at either end of a WAN link connecting a corporation&#39;s data center and a branch office. Each box stores the payload from any flow traversing the link between them in a cache, irrespective of the application or protocol. When one box detects chunks of data that match entries in its cache (by computing “fingerprints” of incoming data and matching them against cached data), it encodes the matched data with tokens. The box at the far end reconstructs the original data using its own cache and the encoded tokens. Recently, this approach has seen increasing commercial deployment as part of a suite of optimizations in middleboxes called WAN optimizers. In fact, many enterprises today use WAN optimizers that are deployed across WAN access links to eliminate redundancy in network traffic and reduce WAN access costs. 
         [0003]    These middlebox-based solutions, however, have two key drawbacks that impact their overall usefulness in the long term. First, with the standardization of secure transmission protocols, there is a growing shift toward end-to-end encryption of data. Unfortunately, middleboxes do not cope well with traffic encrypted end-to-end and many leave such data uncompressed. A small fraction of middleboxes employ tricks (such as connection termination and sharing of encryption keys) to accommodate secured socket layer (SSL) and secure shell (SSH) traffic, but these weaken end-to-end semantics of enterprise transactions considerably. Second, in-network middleboxes do nothing to improve performance over last-hop links of mobile and wireless devices, and these devices are beginning to overrun the enterprise workplace. If end-to-end encryption does become ubiquitous, and the adoption of resource constrained mobile and wireless devices continues its upward trend, then RE will eventually be forced out of middleboxes and directly into end host stacks. 
       SUMMARY 
       [0004]    This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter. 
         [0005]    Embodiments of the end host redundancy elimination system and method provide redundancy elimination as an end system service. Unlike middleboxes, embodiments of the system and method benefit both end-to-end encrypted traffic as well as traffic on last-hop wireless links to mobile devices. Embodiments of the system and method are fast, adaptive and parsimonious in memory usage in order to opportunistically leverage resources on end hosts. 
         [0006]    While client processing and memory are paramount, servers that are used in embodiments of the system and method need to do other things as well (unlike middleboxes). This means that server central processing unit (CPU) and memory are also crucial bottlenecks in the asymmetric design used in embodiments of the system and method. In order to address these bottlenecks, embodiments of the system and method include a load-adaptive fingerprinting technique that is much faster than Rabin fingerprinting that is used in many existing redundancy elimination techniques (while still delivering similar compression). However, unlike the Rabin fingerprinting technique, the load-adaptive fingerprinting technique used in embodiments of the system and method can also adapt its CPU usage depending on server load. Embodiments of the load-adaptive fingerprinting technique are also tunable in that a sampling period can be adjusted to reduce server processing if the server is busy (at the cost of reduced compression gains). 
         [0007]    Effective protocol-independent end-host redundancy elimination involves finding small redundant chunks of the order of 32-64 bytes (because most transfers involve just a few packets each). Existing techniques algorithms for such fine-scale redundancy are quite expensive in terms of memory and processing, especially on resource-constrained clients such as smartphones. Embodiments of the end host redundancy elimination system and method use an asymmetric design that systematically offloads from clients to servers as much of processing and memory as possible. Clients do no more than perform basic first-in first-out (FIFO) queue management of a small amount of memory and do simple pointer lookups in a client packet cache maintained on the client to decode compressed data sent by the server. 
         [0008]    Embodiments of the end host redundancy elimination system and method include optimization techniques that reduce server memory footprint as compared to existing approaches. For server storage, embodiments of the system and method use a suite of highly-optimized data structures for managing metadata and cached payloads. For example, an optimized asymmetric max-match technique included in embodiments of the end host redundancy elimination system and method require 33% less memory as compared to existing max-match techniques. Moreover, an optimized asymmetric chunk-match technique included in embodiments of the end host redundancy elimination system and method cut down the aggregate memory requirements at the server by up to four times as compared to existing chunk-match techniques, while sacrificing a small amount of redundancy. 
         [0009]    Embodiments of the end host redundancy elimination system and method operate above the transmission control protocol (TCP) layer, thereby reducing the number of roundtrips needed for data transfer. Similarly, on mobile smartphones, the low decoding overhead on clients can help translate bandwidth savings into an equivalent amount of energy savings as compared to no compression. 
         [0010]    It should be noted that alternative embodiments are possible, and that steps and elements discussed herein may be changed, added, or eliminated, depending on the particular embodiment. These alternative embodiments include alternative steps and alternative elements that may be used, and structural changes that may be made, without departing from the scope of the invention. 
     
    
     
       DRAWINGS DESCRIPTION 
         [0011]    Referring now to the drawings in which like reference numbers represent corresponding parts throughout: 
           [0012]      FIG. 1  is a block diagram illustrating a general overview of embodiments of the end host redundancy elimination system and method implemented in a computer network. 
           [0013]      FIG. 2  is a block diagram illustrating the module and data used in embodiments of the fingerprinting module shown in  FIG. 1 . 
           [0014]      FIG. 3  is a block diagram illustrating modules and data used in embodiments of the matching and encoding module shown in  FIG. 1 . 
           [0015]      FIG. 4  is a flow diagram illustrating the general operation of embodiments of the end host redundancy elimination system shown in  FIGS. 1-3 . 
           [0016]      FIG. 5  is a flow diagram illustrating the operational details of embodiments of the byte sampling module shown in  FIG. 2 . 
           [0017]      FIG. 6  is a flow diagram illustrating the operational details of embodiments of the asymmetric max-match module shown in  FIG. 3 . 
           [0018]      FIG. 7  illustrates an example of a suitable computing system environment in which embodiments of the end host redundancy elimination system and method shown in  FIGS. 1-6  may be implemented. 
       
    
    
     DETAILED DESCRIPTION 
       [0019]    In the following description of embodiments of the end host redundancy elimination system and method reference is made to the accompanying drawings, which form a part thereof, and in which is shown by way of illustration a specific example whereby embodiments of the end host redundancy elimination system and method may be practiced. It is to be understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the claimed subject matter. 
       I. System Overview 
       [0020]      FIG. 1  is a block diagram illustrating a general overview of embodiments of the end host redundancy elimination system  100  and method implemented in a computer network. The computer network includes at least one server computing device  105  and at least one client computing device  110  in communication with each other over a wide-area network  115 . In general, embodiments of the end host redundancy elimination system  100  and method process a data block from an application and reduce any redundancies. The majority of the processing is performed by the server computing device  105 . In addition, the entire redundancy elimination technique contained in embodiments of the system  100  and method are applied before any encryption, such as is used in HTTPS SSL and IPSec. 
         [0021]    More specifically, embodiments of the end host redundancy elimination system  100  shown in  FIG. 1  include a server-side module  120 , which resides on the server computing device  105 , and a client-side module  125 , which resides on the client computing device  110 . The server-side module  120  includes a fingerprinting module  130 , a server packet cache  133 , and a matching and encoding module  135 . The fingerprinting module  130  identifies representative regions of a data block and includes fingerprints and markers. The server packet cache  133  maintains a cache of payload from previous traffic exchanged between the server computing device  120  and the client computing device  110 . The matching and encoding module  135  finds and removes any redundant data in the data block and encodes the resultant data. 
         [0022]    The client-side module  125  includes a client packet cache  140  and a decoding module  145 . The client packet cache  140 , which is maintained by the client computing device  110 , contains a simple cache of metadata that allows redundant data to be identified. This metadata includes payload from past traffic exchanged between the client computing device  110  and the server computing device  120 . The client packet cache  140  and the server packet cache  133  are synchronized with each other. This synchronization is illustrated in  FIG. 1  by the dashed and dotted line. The decoding module  145  decodes the encoded data that is sent from the server computing device  105 . An application  150  sends a data block containing redundancies  155  over the wide-area network  115  to the server computing device  105 . As explained in detail below, the server-side module  120  processes the data block containing redundancies  155  to generate an encoded non-redundant data block  160 . 
         [0023]    The non-redundant data block  160  is sent by the server computing device  105  over the wide-area network  115  to the client computing device  110 . The non-redundant data block  160  is processed and decoded by the client-side module  125  to generate a non-redundant data block  165 . This non-redundant data block  165  is used by the application  150 . 
         [0024]      FIG. 2  is a block diagram illustrating the module and data used in embodiments of the fingerprinting module  130  shown in  FIG. 1 . In general, embodiments of the fingerprinting module  130  include a module for generating markers and fingerprints from a collection of data. More specifically, embodiments of the fingerprinting module  130  input the data block containing redundancies  155  for processing. Embodiments of the module  130  include a byte sampling module  200  that samples bytes of data from the data block containing redundancies  155  to obtain markers and fingerprints of the data block  210 . From these markers and fingerprints embodiments of the module  130  identify and then output the identified representative regions  220 . 
         [0025]      FIG. 3  is a block diagram illustrating modules and data used in embodiments of the matching and encoding module  135  shown in  FIG. 1 . In general, embodiments of the matching and encoding module  135  input the identified representative regions  220  (box  300 ) and output the encoded non-redundant data block  160 . More specifically, embodiments of the matching and encoding module  135  include an asymmetric max-match module  310 , which uses an optimized max-match technique. 
         [0026]    The identified representative regions  220  are processed by embodiments of the module  310  to identify maximal matches around the representative regions that are repeated across data blocks (box  320 ). Embodiments of the matching and encoding module  135  then remove any identified redundant data (box  330 ). Next, the remaining non-redundant data is encoded (box  340 ). The output from embodiments of the matching and encoding module  135  is the encoded non-redundant data block  160 . 
       II. Operational Overview 
       [0027]      FIG. 4  is a flow diagram illustrating the general operation of embodiments of the end host redundancy elimination system  100  shown in  FIGS. 1-3 . Referring to  FIG. 4 , the method begins by inputting a new data block to a server (box  400 ). In addition, a server packet cache  133  is input to the server (box  410 ). The server packet cache  133  contains previous data blocks that have been exchanged between the server and a client on the computer network. 
         [0028]    Next, embodiments of the system  100  identify contiguous strings of repeated (or redundant) content in the new data block (box  420 ). As explained in detail below, this is achieved by comparing the content to content in the prior data cache using a fingerprinting technique. It should be noted that this comparison and computation is performed by the server. 
         [0029]    Embodiments of the system  100  then encode any identified contiguous strings of repeated data (box  430 ). This encoding, which is performed by the server, produces encoded contiguous strings of repeated data. The encoded data then is sent to a client (box  440 ). At the client, the encoded data is received and decoded box  450 ). 
       III. System and Operational Details 
       [0030]    Embodiments of the end host redundancy elimination system  100  and method are designed to optimize data transfers in the direction from servers in a remote data center to clients in the enterprise. This captures a majority of enterprise traffic. Embodiments of the system  100  and method introduce redundancy elimination modules into the network stacks of clients and remote servers. Because it is desirable to be transparent to applications, embodiments of the system  100  and method can be implemented either at the IP layer or at the socket layer (above the transmission control protocol (TCP) layer). 
         [0031]    Implementing embodiments of the end host redundancy elimination system  100  and method at either the IP layer or the socket layer offers key performance benefits over an IP layer approach, and shields embodiments of the system  100  from network-level events (such as packet losses and reordering). This increases the ease of installation. 
         [0032]    As noted above, there are two sets of modules in embodiments of the end host redundancy elimination system  100  and method: those belonging on servers and those on clients. The server-side module  120  is responsible for identifying redundancy in network data by comparing against a cache of prior data contained in the server packet cache  133 , and encoding the redundant data with shorter metadata. In some embodiments this metadata is essentially a set of (offset, length) tuples that are computed with respect to the server packet cache  133 . 
         [0033]    The client-side module  125  includes the client packet cache  140  and the decoding module  145 . In some embodiments the client packet cache  140  and the server packet cache  133  include a fixed-size circular first-in first out (FIFO) log of packets. Moreover, in some embodiments the decoding module  145  is a simple logic to decode the metadata by “dereferencing” the offsets sent by the server. 
         [0034]    Thus, the complexity in redundancy elimination is mainly on the server computing device  105 . In particular, when a new data block is received by the server-side module  120  which efficiently identifies and encodes contiguous strings of repeated content in the data block with respect to a cache of prior data in the server packet cache  133 . Since it is desirable that this process be fast, embodiments of the system  100  and method accomplish this using the following two broad steps. 
         [0035]    First, a fingerprinting step is used. This involves selecting a few “representative regions” for the current block of data handed down by the application  150 . Second, matching and encoding steps are used. Once the representative regions are identified, one of two approaches may be used for identification of redundant content. As described in detail below, one of these techniques is an asymmetric chunk-match technique that identifies chunks of representative regions that repeat in full across data blocks. As also described in detail below, another technique is an asymmetric max-match technique that identifies maximal matches around the identified representative regions that are repeated across data blocks. These two approaches differ in the trade-off between the memory overhead imposed on the server and the effectiveness of redundancy elimination. 
         [0036]    The system and the operational details of embodiments of the end host redundancy elimination system  100  and method now will be discussed. These embodiments include embodiments of the byte sampling module  200  and the asymmetric max-match module  310 . The system and operational details of each of these modules now will be discussed in detail. 
       III.A. Byte Sampling Module 
       [0037]    Embodiments of the byte sampling module  200  takes the data block containing redundancies  155  and obtains markers and fingerprints of the data contained therein. Using these markers and fingerprints, embodiments of the module  200  identify representative regions. These identified representative regions are used to reduce the amount of redundant data sent over the wide-area network  115 . 
       III.A.1. Fingerprinting Notation and Terminology 
       [0038]    Before discussing the details of the byte sampling module  200 , some notation and terminology are introduced to help explain the approach. A “data block” (or simply a “block”) is a certain amount of data handed down by the application  150  to embodiments of the system  100  and method at the socket layer. Each data block can range from a few bytes to tens of kilobytes in size. 
         [0039]    Mathematically, let ù represent the size of the minimum redundant string (contiguous bytes) to identify. For a data block of size S bytes, where S≧ù, a total of S−ù+1 strings of size ù are potential candidates for finding a match. Typical values for ù range from 12 to 64 bytes. In some embodiments a default value of ù=32 bytes is selected in order to maximize effectiveness of redundancy elimination. 
         [0040]    Since S&gt;&gt;ù, the number of such candidate strings is on the order of the number of bytes in the data block or cache. Because it is impractical to match and store all possible candidates, a fraction 1/p “representative” candidates are chosen. 
         [0041]    “Markers” are defined as the first byte of these selected candidate strings and chunks as the string of bytes between two markers. In addition, “fingerprints” are defined as a pseudo-random hash of fixed ù-byte strings beginning at each marker and “chunk-hashes” are defined as hashes of variable-sized chunks. Note that while two fingerprints may have overlapping bytes, by definition chunks are disjoint. Existing fingerprinting techniques vary primarily in the manner in which they choose the markers. From the markers, embodiments of the byte sampling module  200  can derive chunks, fingerprints, and chunk-hashes. 
       III.A.2. Existing Fingerprinting Techniques 
       [0042]    Before discussing the details of the byte sampling module  200 , it is instructive to discuss in general terms three existing fingerprinting techniques. In some embodiments of the fingerprinting module  130 , any one of these three techniques may be used. 
         [0000]    III.A.2.i. MODP Fingerprinting Technique 
         [0043]    The MODP fingerprinting technique selects a set of fingerprints by first computing a Rabin-Karp hash over sliding windows of ù contiguous bytes of the data block. A fraction 1/p are chosen whose fingerprint value is 0 mod p. Choosing fingerprints in this manner has the advantage that the set of representative fingerprints for a block remains mostly the same despite small amount of insertions, deletions, and reorderings since the markers and fingerprints are chosen based on content rather than position. 
         [0044]    However, it should be noted that the two distinct operations of marker identification and fingerprinting are both handled by the same hash function. While this appears elegant it comes at a cost. Specifically, the per block computational cost is independent of the sampling period, p. Thus, this approach cannot adapt to server CPU load conditions (such as by varying p). 
         [0000]    III.A.2.ii. MAXP Fingerprinting Technique 
         [0045]    Apart from the conflation of marker identification and fingerprinting, one shortcoming of the MODP fingerprinting technique is that the fingerprints and markers are chosen based on a global property. In other words, fingerprints have to take certain pre-determined values to be chosen. The markers for a given block may be clustered and there may be large intervals without any markers, which can limit redundancy identification opportunities. 
         [0046]    In order to guarantee that an adequate number of fingerprints and markers are selected uniformly from each block, the MAXO fingerprinting technique selects markers as those bytes that are the local-maxima over each region of p bytes of the data block. Then, once the marker byte is chosen, an efficient hash function (such as Jenkins Hash) can be used for computing the fingerprint. In addition, by increasing p fewer maxima-based markers need to be identified. This in turn reduces CPU overhead. 
         [0000]    III.A.2.iii. FIXED Fingerprinting Technique 
         [0047]    Markers in both the MODP and MAXP fingerprinting techniques are selected based on content of the data block and use Rabin hashes and local maxima. However, the computation of Rabin hashes and local maxima can be expensive. The FIXED fingerprinting technique is a simpler approach that is content agnostic. 
         [0048]    Specifically, the FIXED fingerprinting technique selects every p th  byte as a marker. Marker identification incurs no computational cost, because markers are chosen by position. Once markers are chosen, S/p fingerprints are computed using a Jenkins Hash technique, as is done in the MAXP fingerprinting technique. 
       III.A.3. Byte Sampling Fingerprinting Technique 
       [0049]    The MAXP and MODP fingerprinting techniques are content-based and thus robust to small changes in content, while FIXED is content agnostic but computationally efficient. The byte sampling fingerprinting technique is designed to combine the robustness of a content-based approach with the computational efficiency of the FIXED fingerprinting technique. The byte sampling fingerprinting technique is content-based (albeit based on a single byte) and retains the content-skipping and computational characteristics of the FIXED fingerprinting technique. 
         [0050]      FIG. 5  is a flow diagram illustrating the operational details of embodiments of the byte sampling module  200  shown in  FIG. 2 . Embodiments of the module  200  begin by inputting a data block containing redundancies (box  500 ). In addition, embodiments of the module  200  define a minimum redundant string of contiguous bytes in the data block (box  505 ). Next, a sampling period for sampling the bytes of the data block is defined (box  510 ). The sampling period can be determined by the load at the server. If the server has a high application load, then the sampling period can be increased so that redundancy elimination does not affect the application. 
         [0051]    Embodiments of the module  200  use a lookup table. The lookup table is generated by first inputting training data (box  515 ) and then generating the lookup table from the training data (box  520 ). In some embodiments, the lookup table is a 256-entry lookup table with a few predefined positions set. 
         [0052]    Once the lookup table has been generated, embodiments of the module  200  select one byte at a time from the data block to analyze. As shown in  FIG. 5 , a first byte is selected from the data block obtain a selected byte (box  525 ). A determination then is made as to whether there is an entry corresponding to the selected byte in the lookup table that is set (box  530 ). As the data block is scanned byte-by-byte, a byte is designated as a marker if the corresponding entry in the lookup table is set (box  535 ). 
         [0053]    Once a marker is selected a fingerprint is computed for the selected byte using a hashing technique and the marker (box  540 ). In some embodiments this hashing technique is performed by hashing a contiguous windows of bytes of the new data block that begins at the marker. Another determination is made as to whether there are more bytes in the data block (box  545 ). If so, then a configurable number of bytes of content in the data block are skipped as controlled by the sampling period (box  550 ). In other words, the configurable number of bytes of content is controlled by the sampling period. In some embodiments, the configurable number of bytes of content is determined as half of the sampling period (p/2). After the specified number of bytes of content is skipped, another byte of the data block is selected at this point (box  555 ) and the process repeats with determining whether an entry corresponding to a selected byte in the lookup table is set for the selected byte (box  530 ). If there are no more bytes in the data block, then embodiments of the module  200  identify representative regions from a stored fingerprint hash table of the markers and the fingerprint (box  560 ). The data block then is copied to the server packet cache (box  565 ). The fingerprint and an offset of the marker are stored in the server packet cache in the fingerprint hash table on the server (box  570 . The fingerprint hash table is generated and maintained on the server computing device  120  and contains fingerprints and marker offsets from previous data blocks in the server packet cache  133 . Finally, the identified representative regions  220  then are output (box  575 ). 
         [0054]    One point of interest is whether embodiments of the byte sampling module  200  will either over-sample or under-sample. First, note that the MODP technique with 32-64 byte rolling hashes was originally used in file systems where chunk sizes were large (on the order of 2-4 kilobytes). Given that sampling may occur as frequently as every 32-64 bytes, sampling chunk boundaries based on 1-byte content values is not as radical as it might first seem. Also, note that if the x entries of the 256-entry lookup table are randomly set (where 256/x=p), then the expected sampling frequency is indeed 1/p. 
         [0055]    In addition, embodiments of the byte sampling module  200  skip the configurable number of bytes of content after each marker selection to avoid oversampling when the content bytes of data block are not uniformly distributed (such as when the same content byte is repeated contiguously). In some embodiments this configurable number of bytes of content is equal to half of the sampling period (p/2), While a purely random selection of 256/x entries does indeed perform well, a lookup table is used that is derived based on the heuristic described below. This approach has been found to outperform the random approach and has been effective after extensive testing on traces. 
         [0056]    Since the number of unique lookup tables is large (2 256 ), embodiments of the byte sampling module  200  use an offline, greedy approach to generate this table. In some embodiments, training data is obtained and then the MAXP technique is run to identify redundant content. Next, the characters are sorted by decreasing order of their presence in the identified redundant content. Embodiments of the byte sampling module  200  then add these characters one at a time and set the corresponding entries in the lookup table to 1. This process is stopped when see diminishing gains in compression are identified. 
         [0057]    The intuition behind this approach is that it is desirable to increase the probability of being selected as markers to those characters that are more likely to be part of redundant content. In some embodiments the characters selected in this process from the training data are 0, 32, 48, 101, 105, 115, 116, 255. Because embodiments of the byte sampling module  200  skip i/2 bytes after every marker selection, the fraction of markers chosen is upper-bounded by 2/p irrespective of the number of entries set in the table. By increasing p, fewer markers and fingerprints are chosen, which results in a reduced computational overhead. 
       III.B. Matching and Encoding Module 
       [0058]    Once the markers and fingerprints are identified by embodiments of the fingerprinting module  130 , then the matching and encoding module  135  identifies redundant content. This is accomplished using an asymmetric max-match technique contained in embodiments of the asymmetric chunk-match module  310 , which identifies maximal matches around fingerprints that are repeated across data blocks. 
         [0059]    The asymmetric max-match technique used by embodiments of the matching and encoding module  135  contains several features that improve overhead. A first feature leverages the asymmetry between servers and clients. This asymmetry involves the fact that clients seem to offload most of the computationally intensive operations (such as hash computations) and memory management tasks to the server. A second feature is to exploit the inherent structure within the data maintained at the servers and clients to optimize memory usage. 
       III.B.1. Asymmetric Max-Match Module 
       [0060]    The matching and encoding module  135  includes an asymmetric max-match module  310 .  FIG. 6  is a flow diagram illustrating the operational details of embodiments of the asymmetric max-match module  310  shown in  FIG. 3 . In general, embodiments of the asymmetric max-match module  310  compute fingerprints for a data block. These fingerprints serve as random “hooks” into the data block payload around which more redundancies can be identified. 
         [0061]    Specifically, embodiments of the asymmetric max-match module  310  input the identified representative regions  220  and define fixed-size windows for computing fingerprints over a data block (box  600 ). Next, one of the fixed-size windows is selected (box  605 ). Fingerprints are computed on the server over the selected fixed-size window using the identified representative regions (box  610 ). 
         [0062]    Embodiments of the module  310  then generate an optimized representation of a fingerprint hash table that maps a fingerprint has value to an offset value (box  615 ). The computed fingerprints for a data block then are compared with a “fingerprint store” (or fingerprint hash table) that holds fingerprints of all the past data blocks (box  620 ). A determination then is made as to whether any of the computed fingerprints match (box  625 ). For each fingerprint of the data block that is matched against the fingerprint hash table, a matching previous data block is retrieved from the server packet cache  133  (box  630 ). 
         [0063]    A matching region then is determined (box  635 ). This matching region is where the current data block and the previous data block match. Next, the matching region is expanded one byte at a time (or byte-by-byte) in both directions to obtain a maximal region of redundant bytes (box  640 ). Matched regions then are encoded with tuples that identify the matching region in the server packet cache  133  (box  645 ). In some embodiments the tuples is an (offset, length) tuples. 
         [0064]    Embodiments of the module  310  then compute hash values for the computed fingerprints to obtain current fingerprint hash values (box  650 ). This is performed using a hash function that generates a few bytes of hash value as a fingerprint. The current fingerprint hash values then are stored in the fingerprint hash table by overwriting a previous entry in the table with the current fingerprint and a marker offset value (box  655 ). In addition, embodiments of the module  310  avoid explicitly deleting any stale fingerprints and marker offset values in the fingerprint hash table. 
         [0065]    Another determination then is made as to whether there are more fixed-size windows (box  660 ). If so, then another fixed-size window is selected (box  665 ) and the process repeats by computing on the server fingerprints over the selected fixed-size window using the identified representative regions  220  (box  610 ). If not, then, embodiments of the module  310  generate the non-redundant data (box  670 ) and output the non-redundant data  675 . 
         [0066]    Embodiments of the asymmetric max-match module  310  employ two techniques to improve the server computation and storage overhead. These two techniques will now be discussed. 
         [0000]    III.B.1.i. Overwriting Technique 
         [0067]    The asymmetric max-match module  310  includes an overwriting technique. This technique overwrites fingerprint value to reduce bookkeeping. In particular, since embodiments of the asymmetric max-match module  310  rely on a byte-by-byte comparison between the bytes in the data block and those in the server packet cache  133 , fingerprint collisions are not costly. In other words, any collisions will be recovered by using an extra memory lookup. This allows embodiments of the module  310  to significantly limit fingerprint store maintenance overhead for fingerprint techniques since fingerprint values are simply overwritten without separate bookkeeping for deletion. Moreover, a relatively simple hash function that generates a few bytes of hash value as a fingerprint is sufficient. In some embodiments this hash function is a Jenkins Hash function. 
         [0000]    III.B.1.ii. Optimized Representation Technique 
         [0068]    The asymmetric max-match module  310  also includes an optimized representation technique. This technique uses an optimized representation of the fingerprint hash table that reduces storage needs significantly. Since the mapping is from a fingerprint (hash value) to an offset value, the fingerprint itself need not be stored in the table in its entirety. 
         [0069]    Embodiments of the module  310  use an index of the fingerprint hash table to implicitly represent all or part of the fingerprint. Only remaining bits of the fingerprint, if there are any, which are not covered by the index can be stored in the hash table. In an extreme case when the index represents all of the fingerprint, the fingerprint hash table is simply an offset table. The offset table is a contiguous set of offset values indexed by the fingerprint hash value. 
         [0070]    Recall from the discussion above that the client packet cache  140  and the server packet cache are synchronized with each other. In some embodiments of the system  100  and method the synchronized cache size of both the client packet cache  140  and the server packet cache  133  is adaptively tuned based on the available memory at the server. Thus, the lower the server memory the lower the synchronized cache size and the memory that is used for the client packet cache  140  and the server packet cache  133 . 
         [0071]    By way of example, assume a fingerprint store for a synchronized cache size of 16 MB and a sampling period, p, of 64. In this case, the number of fingerprints to index the entire cache is 2 24 /64 or 2 18 . Using a table size of 2 18  implies that 18 bits of the fingerprint is implicitly stored as the index of the table. The offset size needed to represent the entire cache is 24 bits. 
         [0072]    Continuing the example, if it is assumed that an additional 8 bits of the fingerprint is stored as part of the table, the entire fingerprint table can be compactly stored in a table of size 2 18 *4 bytes, or 6% of the cache size. A sampling period of 32 would double this to 12% of the cache size. This representation is a significant reduction in fingerprint metadata size compared to prior techniques. 
       IV. Exemplary Operating Environment 
       [0073]    Embodiments of the end host redundancy elimination system  100  and method are designed to operate in a computing environment. The following discussion is intended to provide a brief, general description of a suitable computing environment in which embodiments of the end host redundancy elimination system  100  and method may be implemented. 
         [0074]      FIG. 7  illustrates an example of a suitable computing system environment in which embodiments of the end host redundancy elimination system  100  and method shown in  FIGS. 1-6  may be implemented. The computing system environment  700  is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Neither should the computing environment  700  be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment. 
         [0075]    Embodiments of the end host redundancy elimination system  100  and method are operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well known computing systems, environments, and/or configurations that may be suitable for use with embodiments of the end host redundancy elimination system  100  and method include, but are not limited to, personal computers, server computers, hand-held (including smartphones), laptop or mobile computer or communications devices such as cell phones and PDA&#39;s, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like. 
         [0076]    Embodiments of the end host redundancy elimination system  100  and method may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types. Embodiments of the end host redundancy elimination system  100  and method may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices. With reference to  FIG. 7 , an exemplary system for embodiments of the end host redundancy elimination system  100  and method includes a general-purpose computing device in the form of a computer  710 . 
         [0077]    Components of the computer  710  may include, but are not limited to, a processing unit  720  (such as a central processing unit, CPU), a system memory  730 , and a system bus  721  that couples various system components including the system memory to the processing unit  720 . The system bus  721  may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus also known as Mezzanine bus. 
         [0078]    The computer  710  typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by the computer  710  and includes both volatile and nonvolatile media, removable and non-removable media. By way of example, and not limitation, computer readable media may comprise computer storage media and communication media. Computer storage media includes volatile and nonvolatile removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. 
         [0079]    Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by the computer  710 . By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Combinations of any of the above should also be included within the scope of computer readable media. 
         [0080]    The system memory  730  includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM)  731  and random access memory (RAM)  732 . A basic input/output system  733  (BIOS), containing the basic routines that help to transfer information between elements within the computer  710 , such as during start-up, is typically stored in ROM  731 . RAM  732  typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit  720 . By way of example, and not limitation,  FIG. 7  illustrates operating system  734 , application programs  735 , other program modules  736 , and program data  737 . 
         [0081]    The computer  710  may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only,  FIG. 7  illustrates a hard disk drive  741  that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive  751  that reads from or writes to a removable, nonvolatile magnetic disk  752 , and an optical disk drive  755  that reads from or writes to a removable, nonvolatile optical disk  756  such as a CD ROM or other optical media. 
         [0082]    Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive  741  is typically connected to the system bus  721  through a non-removable memory interface such as interface  740 , and magnetic disk drive  751  and optical disk drive  755  are typically connected to the system bus  721  by a removable memory interface, such as interface  750 . 
         [0083]    The drives and their associated computer storage media discussed above and illustrated in  FIG. 7 , provide storage of computer readable instructions, data structures, program modules and other data for the computer  710 . In  FIG. 7 , for example, hard disk drive  741  is illustrated as storing operating system  744 , application programs  745 , other program modules  746 , and program data  747 . Note that these components can either be the same as or different from operating system  734 , application programs  735 , other program modules  736 , and program data  737 . Operating system  744 , application programs  745 , other program modules  746 , and program data  747  are given different numbers here to illustrate that, at a minimum, they are different copies. A user may enter commands and information (or data) into the computer  710  through input devices such as a keyboard  762 , pointing device  761 , commonly referred to as a mouse, trackball or touch pad, and a touch panel or touch screen (not shown). 
         [0084]    Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, radio receiver, or a television or broadcast video receiver, or the like. These and other input devices are often connected to the processing unit  720  through a user input interface  760  that is coupled to the system bus  721 , but may be connected by other interface and bus structures, such as, for example, a parallel port, game port or a universal serial bus (USB). A monitor  791  or other type of display device is also connected to the system bus  721  via an interface, such as a video interface  790 . In addition to the monitor, computers may also include other peripheral output devices such as speakers  797  and printer  796 , which may be connected through an output peripheral interface  795 . 
         [0085]    The computer  710  may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer  780 . The remote computer  780  may be a personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer  710 , although only a memory storage device  781  has been illustrated in  FIG. 7 . The logical connections depicted in  FIG. 7  include a local area network (LAN)  771  and a wide area network (WAN)  773 , but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet. 
         [0086]    When used in a LAN networking environment, the computer  710  is connected to the LAN  771  through a network interface or adapter  770 . When used in a WAN networking environment, the computer  710  typically includes a modem  772  or other means for establishing communications over the WAN  773 , such as the Internet. The modem  772 , which may be internal or external, may be connected to the system bus  721  via the user input interface  760 , or other appropriate mechanism. In a networked environment, program modules depicted relative to the computer  710 , or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation,  FIG. 7  illustrates remote application programs  785  as residing on memory device  781 . It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used. 
         [0087]    The foregoing Detailed Description has been presented for the purposes of illustration and description. Many modifications and variations are possible in light of the above teaching. It is not intended to be exhaustive or to limit the subject matter described herein to the precise form disclosed. Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims appended hereto.

Technology Category: 5