USOO7161506B2
`
`United States Patent
`
`(12)
`(10) Patent No.:
`US 7,161,506 B2
`
`Fallon
`(45) Date of Patent:
`*Jan. 9, 2007
`
`(54) SYSTEMS AND METHODS FOR DATA
`COMPRESSION SUCH AS CONTENT
`DEPENDENT DATA COMPRESSION
`
`(75)
`
`Inventor:
`
`James J. Fallon, Armonk, NY (US)
`
`(73) Assignee: Realtime Data LLC, New York, NY
`(Us)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`
`4,574,351 A
`4,593,324 A
`4,682,150 A
`4,730,348 A
`
`4304959 A
`4,870,415 A
`
`4371009 A
`4,876,541 A
`4,888,812 A
`
`3/1986 Dang et al.
`6/1986 Ohkubo et al.
`7/1987 Mathes et 31.
`3/1988 MacCrisken
`
`2/1989 MakanSi et 31~
`9/1989 Van Maren et al.
`
`10/1989 TSUkiyama et 31~
`10/1989 Storer
`12/1989 Dinan et al.
`
`4906995 A
`
`3/1990 swanson
`
`This patent is subject to a terminal dis-
`Clalmer‘
`
`DE
`
`FOREIGN PATENT DOCUMENTS
`4127518
`2/1992
`
`(21) Appl. No.: 10/668,768
`
`(22)
`
`Filed:
`
`Sep. 22, 2003
`
`(65)
`
`Prior Publication Data
`US 2004/0056783 A1
`Mar. 25 2004
`5
`
`Related US. Application Data
`(63) Continuation of application No. 10/016,355, filed on
`Oct. 29, 2001, now Pat. No. 6,624,761, wh1ch 1s a
`.
`.
`.
`.
`.
`cont1nuatlon-1n-part of apphcat1on No. 09/705,446,
`filed on Nov. 3, 2000, now Pat. No. 6,309,424, which
`is a continuation of application No. 09/210,491, filed
`on Dec. 11, 1998, now Pat. No. 6,195,024.
`
`(51)
`
`Int. Cl.
`(2006.01)
`H03M 7/34
`(52) US. Cl.
`......................................... .. 341/51 341/79
`(58) Field of Classification Search
`5341/50
`79 75’
`See application file for complete search h’isto’ry ’
`.
`References Cited
`
`56
`
`U’S’ PATENT DOCUMENTS
`4,127,518 A
`11/1978 Coy et 31.
`4,302,775 A
`11/1981 Widergren et 31.
`4,394,774 A
`7/ 1983 Widergren et al.
`
`(Continued)
`OTHER PUBLICATIONS
`
`Jack Venbrux, A VLSI Chip Set for High—Speed Lossless Data
`Compression , IEEE Trans. On Circuits and System for Video
`Technology, Vol. 2, N0. 4, Dec. 1992, pp. 381-391.
`
`(Continued)
`Primary ExamineriLinh Nguyen
`.
`.
`(74) Attorney, Agent, or FirmiFlsh & Neave 1P Group of
`R0 es & Gra LLP
`p
`y
`(57)
`
`ABSTRACT
`
`rovidin fast and efficient data
`S stems and methods for
`g
`P
`y
`compression using a combination of content independent
`data Compression and Content dependent data Compression-
`In one aspect, a method for compressing data comprises the
`steps of: analyzing a data block of an input data stream to
`identify a data type of the data block, the input data stream
`comprising a plurality of disparate data types; performing
`P
`P
`content de endent data com ression on the data block, if the
`data type of the data block is identified; performing content
`independent data compression on the data block, if the data
`type Of the data blOCk is not identified.
`
`99 Claims, 34 Drawing Sheets
`
`M
` ls
`wMFREssIuN
`
`mmoOF M LEAST uNE
`ENcaDEDmuemcx
`mmmm
`THRESHmW
`
`
`No
`yes0
`
`v SELECTENCOD
`ED
`:22
`APPENDNULL
`mu BLOCKwum
`DESCRIPIORTO
`GREATESY
`UNENCODED mpur
`muBLOCK
`cowasssmN RAer
`PPEND
`connespowume
`“32¢
`DESCRVFTOR
`OUTPuT UNENODDED
`OUTPUI ENCODED
`l
`DATABLOCK WITH
`"H _/320
`
`nsscwmk
`
` l A
`
`3111
`
`
` v DATABLOCKw NULL DESCRIPTOR
`
`
`
`YES
`
`muBLOCKS 1»: mm
`
`J7332
`
`rsmwm mu
`RECEWE NEXT DATAPUT
`commasst
`BLOCKFROM 1N
`PROCESS
`STREAM
`
`
`lB
`
`NetApp;Rackspace
`
`Exhibit1001
`
`Page1
`
`NetApp; Rackspace Exhibit 1001 Page 1
`
`

`

`US 7,161,506 B2
`
`Page 2
`
`US. PATENT DOCUMENTS
`
`4,929,946
`4,965,675
`5,028,922
`5,045,848
`5,045,852
`5,046,027
`5,049,881
`5,097,261
`5,113,522
`5,121,342
`5,150,430
`5,159,336
`5,175,543
`5,179,651
`5,187,793
`5,191,431
`5,204,756
`5,209,220
`5,212,742
`5,226,176
`5,227,893
`5,231,492
`5,237,460
`5,237,675
`5,243,341
`5,243,348
`5,247,638
`5,247,646
`5,263,168
`5,270,832
`5,287,420
`5,293,379
`5,307,497
`5,309,555
`5,355,498
`5,357,614
`5,379,036
`5,379,757
`5,381,145
`5,394,534
`5,396,228
`5,400,401
`5,403,639
`5,406,278
`5,406,279
`5,412,384
`5,414,850
`5,420,639
`5,452,287
`5,461,679
`5,467,087
`5,471,206
`5,479,587
`5,486,826
`5,495,244
`5,506,844
`5,506,872
`5,530,845
`5,533,051
`5,535,356
`5,537,658
`5,557,551
`5,557,668
`5,557,749
`5,561,824
`5,574,952
`5,574,953
`5,583,500
`5,590,306
`5,596,674
`5,604,824
`
`>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
`
`5/1990
`10/1990
`7/1991
`9/1991
`9/1991
`9/1991
`9/1991
`3/1992
`5/1992
`6/1992
`9/1992
`10/1992
`12/1992
`1/1993
`2/1993
`3/1993
`4/1993
`5/1993
`5/1993
`7/1993
`7/1993
`7/1993
`8/1993
`8/1993
`9/1993
`9/1993
`9/1993
`9/1993
`11/1993
`12/1993
`2/1994
`3/1994
`4/1994
`5/1994
`10/1994
`10/1994
`1/1995
`1/1995
`1/1995
`2/1995
`3/1995
`3/1995
`4/1995
`4/1995
`4/1995
`5/1995
`5/1995
`5/1995
`9/1995
`10/1995
`11/1995
`11/1995
`12/1995
`1/1996
`2/1996
`4/1996
`4/1996
`6/1996
`7/1996
`7/1996
`7/1996
`9/1996
`9/1996
`9/1996
`10/1996
`11/1996
`11/1996
`12/1996
`12/1996
`1/1997
`2/1997
`
`O’Brien et al.
`Hori et al.
`Huang
`Fascenda
`Mitchell et al.
`Taaffe et al.
`Gibson et al.
`Langdon, Jr. et al.
`Dinwiddie, Jr. et al.
`Szymborski
`Chu
`Rabin et al.
`Lantz
`Taaffe et al.
`Keith et al.
`Hasegawa et al.
`CheVion et al.
`Hiyama et al.
`Normile et al.
`Westaway et al.
`Ett
`Dangi et al.
`Miller et al.
`Hannon, Jr.
`Seroussi et al.
`Jackson
`O’Brien et al.
`Osterlund et al.
`Toms et al.
`Balkanski et al.
`Barrett
`Carr
`Feigenbaum et al.
`Akins et al.
`Provino et al.
`Pattisam et al.
`Storer
`Hiyama et al.
`Allen et al.
`Kulakowski et al.
`Garahi
`Wasilewski et al.
`Belsan et al.
`Graybill et al.
`Anderson et al.
`Chang et al.
`Whiting
`Perkins
`DiCecco
`Normile et al.
`Chu
`Allen et al.
`Campbell et al.
`Remillard
`Jeong et al.
`Rao
`Mohler
`Hiatt et al.
`James
`Kim et al.
`Bakke et al.
`Craft
`Brady
`Norris
`Carreiro et al.
`Brady et al.
`Rust et al.
`Allen et al.
`Watanabe et al.
`Bhandari et al.
`Chui et al.
`
`5,606,706
`5,612,788
`5,613,069
`5,615,017
`5,621,820
`5,623,623
`5,623,701
`5,627,534
`5,627,995
`5,629,732
`5,630,092
`5,635,632
`5,635,932
`5,642,506
`5,649,032
`5,652,795
`5,652,857
`5,652,917
`5,654,703
`5,655,138
`5,666,560
`5,668,737
`5,671,389
`5,675,333
`5,694,619
`5,696,927
`5,703,793
`5,715,477
`5,717,393
`5,717,394
`5,719,862
`5,721,958
`5,724,475
`5,729,228
`5,748,904
`5,757,852
`5,771,340
`5,778,411
`5,781,767
`5,784,572
`5,787,487
`5,796,864
`5,799,110
`5,805,932
`5,808,660
`5,809,176
`5,809,337
`5,812,789
`5,818,368
`5,818,369
`5,818,530
`5,819,215
`5,825,424
`5,832,037
`5,832,126
`5,836,003
`5,838,996
`5,839,100
`5,841,979
`5,847,762
`5,861,824
`5,861,920
`5,867,167
`5,870,036
`5,870,087
`5,872,530
`5,883,975
`5,886,655
`5,889,961
`5,915,079
`5,917,438
`5,920,326
`5,936,616
`
`>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
`
`2/1997
`3/1997
`3/1997
`3/1997
`4/1997
`4/1997
`4/1997
`5/1997
`5/1997
`5/1997
`5/1997
`6/1997
`6/1997
`6/1997
`7/1997
`7/1997
`7/1997
`7/1997
`8/1997
`8/1997
`9/1997
`9/1997
`9/1997
`10/1997
`12/1997
`12/1997
`12/1997
`2/1998
`2/1998
`2/1998
`2/1998
`2/1998
`3/1998
`3/1998
`5/1998
`5/1998
`6/1998
`7/1998
`7/1998
`7/1998
`7/1998
`8/1998
`8/1998
`9/1998
`9/1998
`9/1998
`9/1998
`9/1998
`10/1998
`10/1998
`10/1998
`10/1998
`10/1998
`11/1998
`11/1998
`11/1998
`11/1998
`11/1998
`11/1998
`12/1998
`1/1999
`1/1999
`2/1999
`2/1999
`2/1999
`2/1999
`3/1999
`3/1999
`3/1999
`6/1999
`6/1999
`7/1999
`8/1999
`
`Takamoto et al.
`Stone
`Walker
`Choi et al.
`Rynderman et al.
`Kim et al.
`Bakke et al.
`Craft
`Miller et al.
`Moskowitz et al.
`Carreiro et al.
`Fay et al.
`Shinagawa et al.
`Lee
`Burt et al.
`Dillon et al.
`Shimoi et al.
`Maupin et al.
`Clark, 11
`Kikinis
`Moertl et al.
`Iler
`Saliba
`Boursier et al.
`Konno
`MacDonald et al.
`Wise et al.
`Kikinis
`Nakano et al.
`Schwartz et al.
`Lee et al.
`Kikinis
`Kirsten
`Franaszek et al.
`Huang et al.
`KericeVic et al.
`Nakazato et al.
`DeMoss et al.
`Inoue et al.
`Rostoker et al.
`Hashimoto et al.
`Callahan
`Israelsen et al.
`Kawashima et al.
`Sekine et al.
`Yajima
`Hannah et al.
`Diaz
`Langley
`Withers .................... .. 341/107
`Canfield et al.
`Dobson et al.
`Canfield et al.
`Park
`Tanaka
`Sadeh
`deCarmo
`Wegener
`Schulhof et al.
`Canfield et al.
`Ryu et al.
`Mead et al.
`Deering
`Franaszek et al.
`Chau
`Domyo et al.
`Narita et al.
`Rust
`Dobbek
`Vondran, Jr. et al.
`Ando
`Rentschler et al.
`Torborg, Jr. et al.
`
`341/51
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 2
`
`NetApp; Rackspace Exhibit 1001 Page 2
`
`

`

`US 7,161,506 B2
`
`Page 3
`
`5,949,355 A *
`5,955,976 A
`5,960,465 A
`5,964,842 A
`5,968,149 A
`5,973,630 A
`5,974,471 A
`5,982,723 A
`5,991,515 A
`5,996,033 A
`6,000,009 A
`6,002,411 A
`6,003,115 A
`6,011,901 A
`6,014,694 A
`6,026,217 A
`6,028,725 A
`6,031,939 A
`6,032,148 A
`6,061,398 A
`6,073,232 A
`6,075,470 A
`6,094,634 A
`6,097,520 A
`6,104,389 A
`6,105,130 A
`6,128,412 A
`6,141,053 A
`6,145,069 A
`6,169,241 B1
`6,172,936 B1
`6,173,381 B1
`6,182,125 B1
`6,192,082 B1
`6,195,024 B1
`
`9/1999 Panaoussis ................. .. 341/51
`9/1999 Heath
`9/1999 Adams
`10/1999 Packard
`10/1999 Jaquette et al.
`10/1999 Heath
`10/1999 Belt
`11/1999 Kamatani
`11/1999 Fall et al.
`11/1999 Chiu-Hao
`12/1999 Brady
`12/1999 Dye
`12/1999 Spear et al.
`1/2000 Kirsten
`1/2000 Aharoni et al.
`2/2000 Adiletta
`2/2000 Blumenau
`2/2000 Gilbert et al.
`2/2000 Wilkes
`5/2000 Satoh et al.
`6/2000 Kroeker et al.
`.
`6/2000 Little et al.
`.
`7/2000 Yahagi et al.
`.
`8/2000 Kadnier
`8/2000 Ando
`8/2000 Wu et al.
`10/2000 Satoh
`10/2000 Saukkonen
`11/2000 Dye.
`.
`1/2001 Shimizu
`.
`.
`1/2001 Kitazaki
`1/2001 Dye
`1/2001 Borella et al.
`.
`2/2001 Moriarty et al.
`2/2001 Fallon
`
`6,226,667 B1
`6,226,740 B1
`
`5/2001 Matthews et al.
`5/2001 Iga
`
`6,272,627 B1
`6,272,628 B1
`6,282,641 B1
`6,309,424 B1
`6,317,714 B1
`6,330,622 B1
`6,345,307 B1
`6,421,387 B1
`6,434,168 B1
`6,434,695 B1
`6,442,659 B1
`6,449,682 B1
`6,452,602 B1
`6,463,509 B1
`6,487,640 B1
`6,489,902 B1
`6,513,113 B1
`6,529,633 131
`6,539,456 131
`6,542,644 B1
`6,590,609 Bl
`6,601,104 Bl
`6,604,158 B1*
`6,606,040 B1*
`
`8/2001 Mann
`8/2001 Aguilar et a1.
`8/2001 Christensen
`10/2001 Fallon
`11/2001 Del Castillo et a1.
`12/2001 Schaefer
`2/2002 Booth
`7/2002 Rhee
`8/2002 Kari
`8/2002 Esfahani et a1.
`8/2002 Blumenau
`9/2002 Toorians
`9/2002 Morein
`10/2002 Teoman et a1.
`11/2002 Lipasti
`12/2002 Heath
`1/2003 Kobayashi
`3/2003 EaSWélr et 31.
`3/2003 Stewart
`4/2003 satoh
`7/2003 Kltade et 3L
`7/2003 Fallon
`8/2003 Fallon ....................... .. 710/65
`8/2003 Abdat
`....................... .. 341/87
`
`6,606,413 B1
`6,609,223 B1
`6,618,728 B1
`6,624,761 B1*
`6,661,839 B1
`6,704,840 B1
`6,711,709 B1*
`6,745,282 B1
`6,748,457 B1
`2001/0032128 A1
`2002/0037035 A1
`2002/0104891 A1
`2002/0126755 A1
`2003/0034905 A1*
`2003/0084238 A1
`2003/0142874 A1
`
`8/2003 Zeineh
`8/2003 Wolfgang
`9/2003 Rail
`9/2003 Fallon ....................... .. 341/51
`12/2003 Ishida et al.
`3/2004 Nalawadi et a1.
`3/2004 York ........................ .. 714/748
`6/2004 Okada
`6/2004 Fallon
`10/2001 Kepecs
`3/2002 Singh
`8/2002 Otto
`9/2002 Li et a1.
`2/2003 Anton et al.
`5/2003 Okada et al.
`7/2003 Schwartz
`
`................ .. 341/51
`
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`GB
`JP
`JP
`W0
`W0
`W0
`WO
`
`FOREIGN PATENT DOCUMENTS
`0164677
`12/1985
`0185098
`6/1986
`0283798
`9/1988
`0405572 A2
`1/1991
`0405572 A3
`3/1991
`0493130
`7/1992
`0587437
`3/1994
`0595406
`5/1994
`0718751 A2
`6/1996
`0718751 A3
`2/1997
`9188009
`7/1997
`2162025
`1/1986
`6051989
`2/1994
`11149376
`6/1999
`W0 9414273
`6/1994
`W0 9429652
`12/1994
`W0 9502873
`1/1995
`WO 9748212
`12/1997
`
`Pen-Shu Yeh, The CCSDS Lossless Data Compression Recommen—
`dation for Space Applications, Chapter 16, Lossless Compression
`Handbook, ElseVier Science (USA), 2003, pp. 311-326.
`Robert F. Rice, Some Practical Universal Noiseless Coding Tech—
`niques , Jet Propulsion Laboratory, Pasadena, California, JPL Pub-
`lication 79-22, Mar. 15, 1979.
`K. Murashita et al., High-Speed Statistical Compression using
`Self-organized Rules and Predetermined Code Tables, IEEE, 1996
`Data Compression, conference, no month.
`IBM, Fast Dos Soft Boot, Feb. 1, 1994, vol. 37, Issue 28, pp.
`185-186.
`J. Anderson et al. Codeo squeezes color teleconferencing through
`telephone lines, Electronics 1984, pp. 13-15, no month.
`Robert Rice, “Lossless Coding Standards For Space Data Systems”,
`IEEE 1058-6393/97, pp. 577-585, no month.
`Coene, W et al. “A Fast Route For Application of Rate-distortion
`Optimal Quantization in an MPEG Video Encoder” Proceedings of
`the International Conference on Image Processing, US., New York,
`IEEE, Sep. 16, 1996, pp. 825-828.
`“Operating System Platform Abstraction Method”, IBM Technical
`Disclosure Bulletin, Feb. 1995, vol. 38, Issue No. 2, pp. 343-344.
`
`* cited by examiner
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 3
`
`NetApp; Rackspace Exhibit 1001 Page 3
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 1 0134
`
`US 7,161,506 B2
`
`INPUT DATA STREAM
`
`'—
`
`I I I
`
`I
`
`I I I I |
`
`,.__
`
`IDENTIFY INPUT DATA TYPE AND
`GENERATE DATASI'IS’RPPELIDENTIFICATION
`
`DATA TYPE
`ID SIGNAL
`
`
`
`
`COMPRESS DATA IN ACCORDANCE WITH
`IDENTIFIED DATA TYPE
`
`2
`
`3
`
`COMPRESSED DATA STREAM
`
`RETRIEVE DATA TYPE
`INFORMAgflXgiggAhfi/IPRESSED
`
`WITH IDENTIFIED DATA TYPE
`
`DECOMPRESS DATA IN ACCORDANCE
`
`I I |
`
`l
`
`I I I I I
`
`FIG. 1
`
`PRIOR ART
`
`NetApp;Rackspace
`
`Exhibit1001
`
`Page4
`
`NetApp; Rackspace Exhibit 1001 Page 4
`
`

`

`U.S. Patent
`
`Jan.9,2007
`
`Sheet2 of34
`
`US 7,161,506 B2
`
`E.{QQMQOUZN
`
`\\S_31m.th
`
`KOklEOmMQ
`
`Emuuam
`
`rmmFZDOO
`
`Emuubm
`
`mmmHZDOO
`
`rmmmooozm
`
`mmmmDOOZm
`
`3‘(mmkm«R«G
`
`
`
`ZOGmMKQEODZO_mmmmn=200F3QZ.<F<D
`
`ZOPQEwaOmmwkZDOOEmu.“lemmHZDOO
`
`
`
`mat\ZOPMu/HQMmeOEmu.qummmwQOOZw<F<DXOOJm
`zomEEEOO..
`
`
`N.OE
`
`Ewmmnm
`
`camt/500
`
`cmmmDOozw
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 5
`
`NetApp; Rackspace Exhibit 1001 Page 5
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 3 0f 34
`
`US 7,161,506 B2
`
`B
`
`RECEPVE INITJAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`BUFFER DATA BLOCK
`
`COUNT SIZE OF
`DATA BLOCK
`
`300
`
`302
`
`304
`
`COMPRESS DATA
`BLOCK WiTH
`
`ENABLED ENCODERS
`
`BUFFER ENCODED
`DATA BLOCK OUTPUT
`FROM EACH
`ENCODER
`
`BLOCKS
`
`COUNT SIZE OF
`ENCODED DATA
`
`CALCULATE
`COMPRESSTON
`
`RATIOS
`THRESHOLD LlMiT
`
`COMPARE
`COMPRESSION
`RATIOS WITH
`
`308
`
`310
`
`312
`
`314
`
`FIG. 3a
`
`NetApp;Rackspace
`
`Exhibit1001
`
`Page6
`
`NetApp; Rackspace Exhibit 1001 Page 6
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 4 0f 34
`
`US 7,161,506 B2
`
`316
`
`
`
`IS
`
`COMPRESSION
`
`RATIO OF AT LEAST ONE
`
`ENCODED DATA BLOCK
`GREATER THAN
`THRESHOLD?
`
`
`
`
`NO
`
`
`
`APPEND NULL
`SELECT ENCODED
`
`
`DESCRIPTOR TO
`DATA BLOCK WITH
`
`
`GREATEST
`UNENCODED INPUT
`
`
`DATA BLOCK
`COMPRESSION RATIO
`
`
`
`
`
`
`
`318
`
`320
`
`APPEND
`
`
`CORRESPONDING
`
`DESCRIPTOR
`
`
`OUTPUT UNENCODED
` OUTPUT ENCODED
`
`
`DATA BLOCK WITH
`DATA BLOCK WITH
`
`
`NULL DESCRIPTOR
`DESCRIPTOR
`
`
`
`
`MORE
`
`
`DATA BLOCKS IN INPUT
`STREAM?
`
`
`
`
`
`
`
`TERMINATE DATA
`
`COMPRESSION
`
`PROCESS
`
`
`
`330
`
`RECEIVE NEXT DATA
`BLOCK FROM INPUT
`STREAM
`
`
`
`FIG. 3b
`
`NetApp;Rackspace
`
`Exhibit1001
`
`Page?
`
`NetApp; Rackspace Exhibit 1001 Page 7
`
`

`

`U.S. Patent
`
`n
`
`9
`
`ehS
`
`43M
`
`S
`
`61,
`
`2BM
`
`<K<QQMQOOZM
`
`.meEKOWWQwaFZDOO
`
`nJa§:EEmEmu.qummmmooozm
`
`bmmmmDm
`
`mehZDOO
`
`mewooozm
`
`Eqmmkw<k<Q
`
`
`
`ZOGmMEQEOO ZOQE<QEOOMzo_k%bwwrummo\zo_._.<z_§mm._.mommwkzaoommmmaoozm092¢Emu.quJ,ZOEmmEmEOO
`
`
`
`
`
`M,v..OE
`
`7ow
`
`
`
`UZOF<Z=2KMFMDGEOFUxxm
`
`
`
`mOMMDOEKMQOUZM
`
`
`
`.CENS.>.:1:m<m_wm0
`
`5cmmkzaoocfl\mmuquMMMQODZw
`
`0von
`
`FDQZ.
`
`<F<Q
`
`mwuuam
`
`<F<D
`
`XOOAm
`
`KMFZDOO
`
`NebApp;Rackspace
`
`EXMbfl1001
`
`Page8
`
`NetApp; Rackspace Exhibit 1001 Page 8
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 6 0f 34
`
`US 7,161,506 B2
`
`B
`
`500
`
`502
`
`504
`
`
`
`RECEIVE INITIAL
`
`
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`
`DATA BLOCK
`COUNT SIZE OF
`
`BUFFER DATA BLOCK
`
`COMPRESS DATA
`
`
`BLOCK WITH
`ENABLED ENCODERS
`
`
`
`
`APPEND CORRESPONDING
`
`
`DESIRABILITY FACTORS TO
`ENCODED DATA BLOCKS
`
`
`BUFFER ENCODED DATA
`
`
`BLOCK OUTPUT
`FROM EACH ENCODER
`
`
`508
`
`510
`
`COUNT SIZE OF
`
`
`
`ENCODED DATA
`BLOCKS
`
`
`CALCULATE
`COMPRESSION
`
`RATIOS
`
`512
`
`514
`
`
`
`COMPARE COMPRESSION
`RATIOS WITH THRESHOLD
`
`
`LIMIT
`
`
`516
`
`A
`FIG. 5a
`
`NetApp;Rackspace
`
`Exhibit1001
`
`Page9
`
`NetApp; Rackspace Exhibit 1001 Page 9
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 7 of 34
`
`US 7,161,506 B2
`
`518
`IS
`
`
`COMPRESSION
`
`
`RATIO OF AT LEAST ONE
`ENCODED DATA BLOCK
`
`GREATER THAN
`THRESHOLD?
`
`
`
`
`
`CALCULATE FIGURE OF
`APPEND NULL
`
`
`DESCRIPTOR TO
`MERIT FOR EACH ENCODED
`
`
`DATA BLOCK WHICH EXCEED
`UNENCODED INPUT
`
`
`DATA BLOCK
`THRESHOLD
`
`
`
`SELECT ENCODED DATA
`
`BLOCK WITH GREATEST
`FIGURE OF MERIT
`
`
`520
`
`522
`
`
`OUTPUT UNENCODED
`APPEND
`
`
`
`DATA BLOCK WITH
`CORRESPONDING
`
`
`NULL DESCRIPTOR
`DESCRIPTOR
`
`
`
`
`
`
`
`OUTPUT ENCODED
`DATA BLOCK WITH
`DESCRIPTOR
`
`MORE
`
`
`DATA BLOCKS IN
`INPUT STREAM?
`
`
`PROCESS
`
`TERMINATE DATA
`COMPRESSION
`
`YES
`
`
`
`RECEIVE NEXT DATA
`
`
`BLOCK FROM INPUT
`
`STREAM
`
`
`534
`
`B
`
`FIG. 5b
`
`NebApp;Rackspace
`
`Exmbfl1001
`
`Page10
`
`NetApp; Rackspace Exhibit 1001 Page 10
`
`

`

`U.S. Patent
`
`Jan.9,2007
`
`Sheet8 0f34
`
`US 7,161,506 B2
`
`
`
`«RedQNQOOZM
`
`\xSEq‘mwfim
`
`KOHQEQMMQ
`
`20—wwmmn2200
`
`mat.
`
`ZOFEKOmwO
`\ZO_._.<Z_§mm._.mo
`
`ZOwE<n=200
`
`ZOEmmeEOO
`
`0F<m
`
`Em".qu
`
`_.mmFZDOO
`
`Ewnfinm
`
`NKMFZDOO
`
`EmmmDm
`
`mKMFZDOO
`
`EwmmDm
`
`cme2300
`
`rmmwOOOZm
`
`NmmeOOZm
`
`mmmmooozm
`
`.
`
`cmmmooozm
`
`0.0E
`
`FDQZ
`
`<._.<D
`
`mmumDm
`
`<F<Q
`
`x0015
`
`mmFZDOU
`
`Evmmhm.E.«G
`
`om
`
`-mwmj
`
`
`
`NEE.thamlm
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 11
`
`NetApp; Rackspace Exhibit 1001 Page 11
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 9 of 34
`
`US 7,161,506 B2
`
`700
`
`70
`
`704
`
`706
`
`708
`
`INPUT INITIAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`COUNT SIZE OF
`DATA BLOCK
`
`BUFFER DATA BLOCK
`
`ENCODERS
`
`INITIALIZE TIMER
`
`BEGIN
`COMPRESSING
`DATA BLOCK WITH
`
`710
`
`
`
`
`
`TIME EXPIRED?
`
`
`
`
`NO
`
`NO
`
`ENCODING
`
`COMPLETE?
`
`
`
`
` STOP
`
`ENCODING
`
`PROCESS
`
`
`718
`
`BUFFER ENCODED
`
`BUFFER
`
`
`DATA BLOCK FOR EACH
`
`ENCODED DATA
`
`
`ENCODER THAT
`
`BLOCK OUTPUT
`
`COMPLETED ENCODING
`
`
`FROM EACH
`
`PROCESS
`
`ENCODER
`
`WITHIN TIME LIMIT
`
`
`
`COUNT SIZE OF
` 720
`
`ENCODED DATA
`
`
`BLOCKS
`
`
`
`CALCULATE
`
`
`COMPRESSION
`RATIOS
`
`722
`
`COMPARE COMPRESSION
`
`
`RATIOS WITH THRESHOLD
`LIMIT
`
`
`
`724
`
`FIG. 7a
`
`NetApp;Rackspace
`
`Exhibit1001
`
`Page12
`
`NetApp; Rackspace Exhibit 1001 Page 12
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 10 0f 34
`
`US 7,161,506 B2
`
`726
`
`IS
`
`
`COMPRESSION
`RATIO OF AT LEAST ONE
`
`ENCODED DATA BLOCK
`GREATER THAN
`THRESHOLD?
`
`NO
`
`
`
`
`APPEND NULL
`SELECT ENCODED
`
`
`DESCRIPTOR TO
`DATA BLOCK WITH
`
`
`GREATEST
`UNENCODED INPUT
`
`
`COMPRESSION RATIO
`DATA BLOCK
`
`
`
`
`
`
`
`
`APPEND
`
`
`CORRESPONDING
`DESCRIPTOR
`
`
`
`
`
`728
`
`730
`
`OUTPUT UNENCODED
`OUTPUT ENCODED
`
`DATA BLOCK WITH
`DATA BLOCK WITH
`
`NULL DESCRIPTOR
`DESCRIPTOR
`
`
`
`
`
`
`MORE
`
`
`DATA BLOCKS IN INPUT
`STREAM?
`
`TERMINATE DATA
`
`COMPRESSION
`
`
`PROCESS
`
`
`
`740
`
`RECEIVE NEXT DATA
`BLOCK FROM INPUT
`STREAM
`
`
`
`FIG. 7b
`
`NetApp;Rackspace
`
`Exhibit1001
`
`Page13
`
`NetApp; Rackspace Exhibit 1001 Page 13
`
`

`

`U.S. Patent
`
`hS
`
`f0
`
`S
`
`61,
`
`2BM
`
`78
`
`M,wGE
`
`«EB3805
`
`,zo_mmmmms_oo5%:9.zo_mwmmas_oo<205%n«EnigmaNmmhzaoo
`nJaEEEEwEmulammmmmooozm
`9.21Rm...qu<20x005Romwmoommmmg
`
`
`
`
`\zoEszEmommmkzaoommmmooozmmmutzm2055200.«9238mzQEEommo
`
`
`ow9
`
`\mwmuam
`
`vmeZDOO
`
`Pwmmooozw
`
`Eqmmhqu<Q
`
`ucmmkzsoomEmtamcmmmooozm
`
`
`U20.22.25th305$
`tam:53.3%meom
`
`
`
`
`
`noMEREmmooozm
`
`3-mmm:
`
`438mug?msE8&6QO
`
`NebApp;Rackspace
`
`EXMbfl1001
`
`Page14
`
`NetApp; Rackspace Exhibit 1001 Page 14
`
`
`
`
`

`

`U.S. Patent
`
`f
`
`1
`
`2B60
`
`SE§<mEmUEE8805
`7,motiome
`
`8
`
`5I
`maOE
`
`:N05...
`
`nJazoammmmzoo
`
`1-mmm:a20.22.5950mEms.
`
`7om0zomEEsao.m\.mmuuam$5300
`SC.E...
`9,zOrEZSmmEo:m9m...<2050.5
`
`M0%08ESE..HEEQuixoQO
`n.GEE.512.Ska
`
`
`
`c;0.5...Simwtb(.35
`
`29Ex80
`
`MEN>...:_m<m_mm_o8Mzo_mmmm¢s_oommooozm
`
`$055
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 15
`
`NetApp; Rackspace Exhibit 1001 Page 15
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 13 of 34
`
`US 7,161,506 B2
`
`100
`
`102
`
`B
`
`104
`
`105
`
`108
`
`RECEIVE INITIAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`COUNT SIZE OF
`DATA BLOCK
`
`
`
`TIME EXPIRED?
`
`(110
`
`
`116
`
`NO
`
`APPLY OUTPUT
`
`OF COMPLETED
`
`ENCODING
`
`STAGE TO NEXT
`
`ENCODING
`
`STAGE IN
`
`
`CASCADE PATH
`
`
`
`
`BUFFER DATA
`BLOCK
`
`
`
`INITIALIZE TIMER
`ENCODER PATHS
`
`APPLY INPUT DATA
`BLOCK TO FIRST
`ENCODING STAGE
`IN CASCADED
`
`BUFFER
`
`ENCODED DATA
`BLOCK OUTPUT
`
`FROM
`COMPLETED
`ENCODING
`STAGE
`
`112 YES
`
`ENCODING
`
`
`STAGE
`
`
`COMPLETE?
`
`
`
`
`
`
`
`
`
`STOP ENCODING
`PROCESS
`
`SELECT BUFFERED OUTPUT OF LAST
`ENCODING STAGE IN ENCODER
`CASCADE THAT COMPLETED ENCODING
`PROCESS WITHIN TIME LIMIT
`
`
`
`
`COUNT SIZE OF
`
`
`122
`ENCODED DATA
`
`
`BLOCKS
`
`
` CALCULATE
`
`
`COMPRESSION
`RATIOS
`
`
`COMPARE COMPRESSION
`
`
`RATIOS WITH THRESHOLD
`LIMIT
`
`124
`
`126
`
`
`
`FIG. 103
`
`A
`
`NebApp;RaCkspace
`
`Exmbfl1001
`
`Page16
`
`NetApp; Rackspace Exhibit 1001 Page 16
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 14 0f 34
`
`US 7,161,506 B2
`
`128
`
`IS
`
`
`COMPRESSION
`
`
`RATIO OF AT LEAST ONE
`
`ENCODED DATA BLOCK
`GREATER THAN
`
`THRESHOLD?
`
`
`
`134
`
`136
`
`APPENDNULL
`CALCULATE FIGURE OF
`
`
`
`130
`MERIT FOR EACH ENCODED
`DESCRWTORTO
`
`
`
`UNENCODEDINPUT
`DATA BLOCK WHICH EXCEED
`
`
`THRESHOLD
`DAEABLOCK
`
`
`
`
`SELECT ENCODED DATA
`
`BLOCK WITH GREATEST
`FIGURE OF MERIT
`
`
`132
`
`140
`
`DATA BLOCKS IN
`INPUT STREAM?
`
`
`YES
`
`APPEND
`OUTPUT UNENCODED
`
`
`
`CORRESPONDING
`DATA BLOCK WITH
`138
`
`
`
`DESCRIPTOR
`NULL DESCRIPTOR
`
`
`
`OUTPUT ENCODED
`
`DATA BLOCK WITH
`DESCRIPTOR
`
`PROCESS
`
`TERMINATE DATA
`COMPRESSION
`
`RECEVENEXTDAIA
`BLOCK FROM INPUT
`STREAM
`
`
`144
`
`
`
`
`3 FIG. 10b
`
`NetApp;Rackspace
`
`Exhibit1001
`
`Page17
`
`NetApp; Rackspace Exhibit 1001 Page 17
`
`

`

`51aehS
`
`43
`
`1.}7SU
`
`2B60
`
`,m5mmooomo
`
`3:
`
`5Imrr0E
`
`U.S. Patent
`
`m
`
`9,
`
`0
`
`J5$0080
`
`m8$0080
`
`.332\\SE.<Q
`
`mOhmiome
`
`7<56Sago
`
`mummam
`
`$me<205&88$880
`
`mOFuiowmo
`
`ZOE.O<w:.Xm
`
`
`
`mmuquXOOJm
`
`<F<DFDQZ
`EfimmkwHF(Q
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 18
`
`NetApp; Rackspace Exhibit 1001 Page 18
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 16 0f 34
`
`US 7,161,506 B2
`
`RECEIVE INITIAL
`
`
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`
`
`
`BUFFER DATA BLOCK
`
` EXTRACT DATA
`
`COMPRESSION TYPE
`DESCRIPTOR
`
`1200
`
`1202
`
`1204
`
`IS DATA
`
`
`COMPRESSION
`
`TYPE DESCRIPTO
`
`NULL?
`
`
`1 206
`
`
`
`
`SELECT DECODER{S)
`CORRESPONDING TO
`
`DESCRIPTOR
`1208
`
`RECEIVE NEXT
`OUTPUT
`
`
`
`DATA BLOCK IN
`UNDECODED
`
`
`
`DECODE DATA BLOCK USING
`INPUT STREAM
`DATA BLOCK
`
`
`
`
`SELECTED DECODER(S)
`
`
`
`
`
`OUTPUT DECODED
`DATA BLOCK
`
`MORE DATA
`
`
`BLOCKS IN INPUT
`
`STREAM?
`
`
`
`
`NO
`
`TERMINATE
`DECODING PROCESS
`
`1218
`
`FIG. 12
`
`NetApp;Rackspace
`
`Exhibit1001
`
`Page19
`
`NetApp; Rackspace Exhibit 1001 Page 19
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 17 of 34
`
`US 7,161,506 B2
`
`_.
`
`EmuoocmEmccmawoE980 Q#685
`
`
`
`
`
`E0Lmuoocm
`
`mohouoocm
`
`
`
`NDhmuoocm..(0N9,
`
`“COVCOOEmQ
`
`
`
`EmucwqmoEmaSQExoo_mEmaEmgm
`
`
`
`emuoucmcog—58mm
`
`
`
`
`
`EmucmqwugEmEoOozmamaLmtsm5:500
`
`rmgmvoocm
`
`mm5805
`
`mmEuoocw
`
`cm5683
`
`0:98
`
`85883.
`
`Eegtomz8$5:
`
`w
`
`or?
`
`<2wmswi
`
`omor
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 20
`
`NetApp; Rackspace Exhibit 1001 Page 20
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan.9,2007
`
`Sheet18 of34
`
`US 7,161,506 B2
`
`umuoocm
`
`
`865me8685500co_mwmano
`5?9mm23%mEEEEQ
`
`8303mm
`
`56.5me
`
`623%5
`
`
`
`mmrmEDOE
`
`EDw..9c:00>.wt3m
`
`MDmLmHCDOOEmtSm
`
`v0whmeJOOtmu—wzm
`
`NDmgmHCDOOtmtDm
`
`(own?
`
`Em§a300tmt§
`
`mmmgmwcsootmtsm
`
`mmmeHCJOOtmtSm
`
`CmmLmEDOOtthm
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 21
`
`NetApp; Rackspace Exhibit 1001 Page 21
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 19 0f 34
`
`US 7,161,506 B2
`
`
`
`Receive Initial
`Data Block From
`
`
`~ 1400
`
`Input Data
`Stream
`
`Count Size of
`Data Block
`
`~14”
`
`
`
`
`
`
`Buffer Data Block ~1404
`
`
`Apply Content
`Dependent Data
`Recognition
`
`
`
`~1406
`
`Recognize Data
`Stream Content
`
`
`
`?
`
`No—> B
`
`FIGURE 14A
`
`NetApp;Rackspace
`
`Exhibit1001
`
`Page 22
`
`NetApp; Rackspace Exhibit 1001 Page 22
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 20 of 34
`
`US 7,161,506 B2
`
`
` Compress Data
`
`
`
`Block with
`
`Enabled Content
`
`~141O
`
`
`independent
`
`
`Encoders
`
`
`
`
`
`
`Buffer Encoded
`Data Block Output
`
`»~1412
`From Each
`
`
`
`Encoder
`
`
`
`Count Size of
`~1414
`Encoded Data
`
`
`Blocks
`
`
`
`
`
` Calculate
`
`~1416
`Compression
`
`Ratio
`
`
`Compare
`Compression
`
`
`Ratios with
`
`
`
`Threshold Limit
`
` D
`
`HGURE14B
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 23
`
`NetApp; Rackspace Exhibit 1001 Page 23
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 21 0f 34
`
`US 7,161,506 B2
`
`
`
`Compression Ratio
`
`of at Least One Encoded Data
`Block Greater Than Content
`
`
`
`
`
`Independent Threshold
`1420 ~
`
`
`
`
`
`Output Encoded
`Data Block with
`
`Output Unencoded
`Data Block with
`
`
`
`
`
`
`Append Null
`Select Encoded
`Data Block with
`Descriptor to
`
`
`
`Greatest
`Unencoded Input
`
`Data Block
` 1422 ~
`Compression Ratio
`
`
`
`Append
`Corresponding
`1424 ~
`
`Encoding
`Descriptor
`
`
`
`
`
`
`
`
`Receive Next
`
`More Data
`
`Terminate
`
`
`
`Data Block From
`Biocks in Input
`
`
`Data Compression
`
`Stream
`Process
`
`
`?
`
`
`Input Stream
`
`
`
`Yes
`
`1430
`
`FIGURE 14C
`
`NetApp;Rackspace
`
`Exhibit1001
`
`Page 24
`
`Descriptor
`
`Null Descriptor
`
`
`
`NetApp; Rackspace Exhibit 1001 Page 24
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 22 0f 34
`
`US 7,161,506 B2
`
`Select Recognized
`1434~ Data Type/File or Block
`in List or Algorithm
`
`Algorithm(s)
`
`Select Content
`
`1436 ~
`
`Dependent
`
`Compress Data Block
`1438 ~ with Enabled Content
`
`
`Dependent Encoder(s)
`
`
`1440 ~
`
`Buffer Encoded Data
`Block From Each
`Encoder
`
`1442 ~ Count Size of Data
`Blocks
`
`Calculate
`1444 ~ Compression Ratio
`
`
`
`No" F
`
`
`Compression
`Ratio of at Least One
`
`Encoded Data Block
`
`
`
`
`
`
`Greater Than
`
`Content Dependent
`Threshold
`?
`
`
`
`~1448
`
`Yes
`
`+ E
`
`FIGURE 14D
`
`NetApp;Rackspace
`
`Exhibit1001
`
`Page 25
`
`NetApp; Rackspace Exhibit 1001 Page 25
`
`

`

`U.S. Patent
`
`Jan.9,2007
`
`Sheet23 of34
`
`US 7,161,506 B2
`
`
`
`$885E3580E950
`
`MDLGUOUCm
`
`5Lmnoocm
`
`
`
`NDLmUoocm\(Ova
`
`ED$805985:35:500
`
`
`
`EmucwamoEmaSac.xoo_mSam88%
`
`6280$3
`
`coEcmoomm
`
`2Est
`
`cozEmoomm
`
`5Eu:
`
`@555?
`
`owmw
`
`<mrm130E
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 26
`
`NetApp; Rackspace Exhibit 1001 Page 26
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 24 0f 34
`
`US 7,161,506 B2
`
`umuoocm
`
`53>Ema
`
`Batome
`
`05mmco_mmm.ano
`
`Eocmem>on<E980momLchootmtam2on?
`
`
`
`
`
`5mhmycsootmtzm
`
`
`
`563.5800Emucmamo
`83.:280an0nom§caoo\.mt:m
`
`
`
`
`
`83:8829595.
`
`82.
`
`EDwLmuCDOOtthm
`
`
`
`
`
`29395.32mm03mmCosme.:80
`
`
`
`rmemgcsootmtsmrmLmuoocm
`
`
`
`
`
`mhmnoucmEmucmamugEmEoo
`
`8385800
`
`32:28
`
`mm;meOE EocweE.\ozmm
`mmmauczootmtsmmm508cm
`mmemuczootwtzmmmLmuoocm
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 27
`
`NetApp; Rackspace Exhibit 1001 Page 27
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 25 of 34
`
`US 7,161,506 B2
`
`Receive Initial
`
`
`
`
`
`Data Block From
`
`~1600
`
`Input Data
`Stream
`
`Count Size of
`Data Block
`
`~ 1602
`
`Buffer Data Block ~1604
`
`
`
`
`
`
`
`
`Apply Content
`Dependent Data
`Recognition
`
`
`
`~1606
`
`
`
`Recognize Data
`Stream Content
`?
`
`No+ B
`
`YES
`'5
`
`C
`
`FIGURE 16A
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 28
`
`NetApp; Rackspace Exhibit 1001 Page 28
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 26 of 34
`
`US 7,161,506 B2
`
`Compress Data
`Block with Enabled
`
`Content Independent
`Encoders
`
`Buffer Encoded Data
`
`Block Output From
`Each Encoder
`
`
`
`Count Size of
`
`Encoded Data Blocks
`
`Calculate
`
`Compression
`Ratio
`
`Compare
`Compression Ratios
`with Threshold Limit
`
`D
`
`FlGURE 1GB
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 29
`
`NetApp; Rackspace Exhibit 1001 Page 29
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 27 0f 34
`
`US 7,161,506 B2
`
`
`
`Compression Ratio
`of at Least One Encoded Data
`Block Greater Than Content
`
`
`
`
`
`Append Null
`
`Select Encoded
`Descriptor to
`Data Block with
`
`
`
`Unencoded Input
`Greatest
`
`
`Data Block
`
`
`
`Compression Ratio
`
`1624 ~
`
`Output Unencoded
`Data Block with
`
`
`
`Append
`
`Corresponding
`
`Encoding
`Descriptor
`
`
`
`
`
`Output Encoded
`Data Block with
`
`
`Null Descriptor
`
`
`
`Descriptor
`
`
`
`
`
`
`
`Receive Next
`More Data
`Terminate
`
`
`Data Block From 7
`Blocks in Input
`
`
`Data Compression
`
`Process
`Stream
`
`
`?
`
`
`
`Input Stream
`
`
`
`Yes
`
`1630
`
`FIGURE 16C
`
`NetApp;Rackspace
`
`Exhibit1001
`
`Page 30
`
`NetApp; Rackspace Exhibit 1001 Page 30
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 28 of 34
`
`US 7,161,506 B2
`
`Select Recognized
`1634~ Data Type/File or Block
`in List or Algorithm
`
`1636 ~
`
`Select Content
`
`Dependent
`Algorithm(s)
`
`Compress Data Block
`1638 ~ with Enabled Content
`
`
`
`
`Dependent Encoder(s)
`
`1640 ~
`
`1642 N
`
`Buffer Encoded Data
`
`Block From Each
`Encoder
`
`Blocks
`
`Count Size of Data
`
`1644 ~
`
`Compression Ratio
`
`Calculate
`
`
`
`
`
`Compression
`Ratio of at Least
`
`One Encoded Data
`
`Block Greater Than
`
`
`
`Content Dependent
`Threshold
`
`
`
`Nov B
`
`FIGURE 16D
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 31
`
`NetApp; Rackspace Exhibit 1001 Page 31
`
`

`

`U.S. Patent
`
`Jan.9,2007
`
`Sheet29 of34
`
`US 7,161,506 B2
`
`
`
`$385#5288E980
`
`m0gmboocm
`
`5$805
`
`NDL303m.2ON?
`
`Emucwamug
`
`m.qu
`
`EoEoo
`
`EDhmuoocm«uth
`
`
`282882mm59:xogm9mmEmgm
`
`
`
`
`
`
`
`emuoocmEmucmamngE980coacmoomm
`
`rmLmvoocm
`
`
`
`8:.QEES
`
`vancozEmoomm
`
`
`
`Eczema8353
`
`$332563Lo
`
`or:w
`
`
`
`<5.mmDOE
`
`53m$2500
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 32
`
`NetApp; Rackspace Exhibit 1001 Page 32
`
`
`
`
`

`

`U.S. Patent
`
`n.aJ
`
`9,
`
`ae
`
`4
`
`161.}7
`
`2BM
`
`58:88co_mmm5Eoomc_E.§mn_
`
`
`
`7£3,Ema.mvmvoocwEDm.§c:00\._mt3m
`
`
`
`coiwmtano
`
`
`
`«umLoatowmflAvmwfiWM—mE33.
`
`
`
`HmmBmEsooEtzm0ommrovmwmEemwcsootmtsm
`
`5,mtmEDOE
`
`Wcmewuczootmtzm
`
`mmwhmycsoOtmtsmAllm
`
`80v
`
`NetApp; RaCkspace
`
`Exhibit 1001
`
`Page 33
`
`nowhmwczoOtwtzm
`
`5emaczootmtzm
`
`
`
`NDmhmgczoogtzm20m?
`
`NetApp; Rackspace Exhibit 1001 Page 33
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 31 0f 34
`
`US 7,161,506 B2
`
`
`
`
`Receive Initial
`
`Data Block From
`
`Input Data
`Stream
`
`~1800
`
`Count Size of
`Data Block
`
`~1802
`
`
`
`
`Buffer Data Block ~1804
`
`
`
`
`Apply Content
`Dependent /
`Independent Data
`Recognition
`
`
`
`
`~1806
`
`
`
`Recognize Data
`Stream Content
`
`No-> B
`
`?
`
`Yes
`
`+ C
`
`FIGURE 18A
`
`NetApp;Rackspace
`
`Exhibit1001
`
`Page 34
`
`NetApp; Rackspace Exhibit 1001 Page 34
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 32 of 34
`
`US 7,161,506 B2
`
`Estimate Optimum
`Encoder(s) From
`Estimation Algorithms
`
`Compress Data
`Block with Enabled
`
`Content Independent
`Encoders
`
`Buffer Encoded Data
`
`Block Output From
`Each Encoder
`
`Count Size of
`
`Encoded Data Blocks
`
`
`
`Calculate
`
`Compression
`Ratio
`
`Compare
`Compression Ratios
`with Threshold Limit
`
`D
`
`FIGURE 188
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 35
`
`NetApp; Rackspace Exhibit 1001 Page 35
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 33 of 34
`
`US 7,161,506 B2
`
`
`
`Compression Ratio
`
`of at Least One Encoded Data
`
`Block Greater Than Content
`
`
`
`Independent Threshold
`1820 ~
`
`
`
`
`
`Append Null
`
`Select Encoded
`Descriptor to
`Data Block with
`
`
`Unencoded Input
`Greatest
`
`
`
`Data Block
` 1822 ~
`
`Compression Ratio
`
`
`
`
`Append
`Corresponding
`
`1824 ~
`Encoding
`
`Descriptor
`
`
`
`
`
`Output Unencoded
`Output Encoded
`Data Block with
`Data Block with
`
`
`Null Descriptor
`
`Descriptor
`
`
`
`
`
`Receive Next
`
`
`
`Terminate
`More Data
`
`
`Data Block From
`Data Compression
`
`
`
`Blocks in Input
`Process
`Stream
`
`
`
`?
`
`
`
`Input Stream
`
`
`
`Yes
`
`1830
`
`FIGURE 180
`
`NetApp; Rackspace
`
`Exhibit 1001
`
`Page 36
`
`NetApp; Rackspace Exhibit 1001 Page 36
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 34 0f 34
`
`US 7,161,506 B2
`
`1838~
`
`
`
`Select Recognized
`
`
`Data Type/File or Block
`in List or Algorithm
`
`
`Select or Estimate
`
`1840 ~ Content Dependent
`
`Algorithm(s)
`
`Dependent Encoder(s)
`
`
`Compress Data Block
`1842 ~ with Enabled Content
`
`No» F
`
`1844 ~
`
`1646 ”
`
`Buffer Encoded Data
`Block From Each
`Encoder
`
`Count Size of Data
`Blocks
`
`1848
`
`
`
`Calculate
`-
`-
`Compressron Ratio
`
`
`
`Content Dependent
`Threshold
`
`
`
`~ 1850
`
`Yes
`
`v E
`
`FIGURE 18D
`
`NetApp;Rackspace
`
`Exhibit1001
`
`Page 37
`
`
`
`
` Compression
`
`Ratio of at Least
`
`
`One Encoded Data
`Block Greater Than
`
`
`
`NetApp; Rackspace Exhibit 1001 Page 37
`
`

`

`US 7,161,506 B2
`
`1
`SYSTEMS AND METHODS FOR DATA
`COMPRESSION SUCH AS CONTENT
`DEPENDENT DATA COMPRESSION
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a Continuation of US. application Ser.
`No. 10/016,355 filed on Oct. 29, 2001, is a US. Pat. No.
`6,624,761, which is a Continuation-In-Part of US. patent
`application Ser. No. 09/705,446, filed on Nov. 3, 2000, now
`US. Pat. No. 6,309,424, issued on Oct. 30, 2001, which is
`a Continuation of US. patent application Ser. No. 09/210,
`491, filed on Dec. 11, 1998, which is now US. Pat. No.
`6,195,024, issued on Feb. 27, 2001.
`
`BACKGROUND
`
`1. Technical Field
`
`The present invention relates generally to a data compres-
`sion and decompression and, more particularly, to systems
`and methods for data compression using content indepen-
`dent and content dependent data compression and decom-
`pression.
`2. Description of Related Art
`Information may be represented in a variety of manners.
`Discrete information such as text and numbers are easily
`represented in digital data. This type of data representation
`is known as symbolic digital data. Symbolic digital data is
`thus an absolute representation of data such as a letter,
`figure, character, mark, machine code, or drawing.
`Continuous information such as speech, music, audio,
`images and video, frequently exists in the natural world as
`analog information. As is well known to those skilled in the
`art, recent advances in very large scale integration (VLSI)
`digital computer technology have enabled both discrete and
`analog information to be represented with digital data.
`Continuous information represented as digital data is often
`referred to as diffuse data. Diffuse digital data is thus a
`representation of data that is of low information density and
`is typically not easily recognizable to humans in its native
`form.
`
`There are many advantages associated with digital data
`representation. For instance, digital data is more readily
`processed, stored, and transmitt