United States Patent
`US 7,865,585 B2
`(10) Patent No.:
`(12)
`Samuels et al.
`(45) Date of Patent:
`Jan. 4, 2011
`
`
`US007865585B2
`
`(54) SYSTEMS AND METHODS FOR PROVIDING
`DYNAMIC AD HOC PROXY-CACHE
`HIERARCHIES
`
`(75)
`
`Inventors: Allen Samuels, San Jose, CA (US);
`Richard Jensen, San Jose, CA (US);
`Zubin Dittia, San Mateo, CA (US); Dan
`Decasper, San Mateo, CA (US);
`Michael Ovsiannikov, San Mateo, CA
`(US); Robert Plamondon,Blodgett, OR
`(US)
`
`(73) Assignee: Citrix Systems, Inc., Fort Lauderdale,
`FL (US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`US.C. 154(b) by 726 days.
`(21) Appl. No.: 11/685,153
`.
`Filed:
`
`(22)
`
`Mar. 12, 2007
`
`(65)
`
`Prior Publication Data
`US 200870228939 Al
`Sep. 18, 2008
`(51)
`Int. Cl.
`(2006.01)
`GO6F 15/173
`709/223: 709/217: 709/219:
`(52) US.C
`ee T1V/U1&: 711/125: 71 1137
`(58) Field ofClassification Search
`°
`709/223
`709/217. 21 95 1ti18 125 137
`S
`lication
`file
`7]
`'
`?
`?
`bhi f
`TOF COMPINE SEALCA
`NISIOFY:
`C6 APPNCATON
`TNE
`References Cited
`U.S. PATENT DOCUMENTS
`
`(56)
`
`4,779,189 A
`,
`,
`4.796.003 A
`5,057,996 A
`5,140,321 A
`
`10/1988 Legvoldet al.
`:
`1/1989 Bentley etal
`10/1991 Cutler et al.
`8/1992 Jung
`
`5,175,852 A
`5,249,290 A
`5,293,379 A
`5,297,283 A
`eastog ‘
`5.446.736 A
`—_
`
`12/1992 Johnsonetal.
`9/1993 Heizer
`3/1994. Carr
`3/1994 Kelly, Jr. et al.
`Whoo, Anderson etal.
`8/1995 Gleeson et al
`,
`
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`1587007 A2
`10/2005
`
`EP
`
`(Continued)
`OTHER PUBLICATIONS
`
`Faber, et. al., “Dynamic Time Windows Packet Admission Control
`with Feedback”, Aug. 1992.
`(Continued)
`Primary Examiner—Krisna Lim
`(74) Attorney, Agent, or Firm—Foley and Lardner LLP;
`Christopher McKenna
`
`ABSTRACT
`(57)
`Systems and methodsof storing previously transmitted data
`and using it to reduce bandwidth usage and accelerate future
`communications are described. By using algorithmsto iden-
`tify long compression history matches, a network device may
`improve compressionefficiently and speed. A network device
`may also use application specific parsing to improve the
`length and numberof compression history matches. Further,
`by sharing compression histories, compression history
`indexes and cachesacross multiple devices, devices can uti-
`lize data previously transmitted to other devices to compress
`networktraffic. Any combination ofthe systems and methods
`may beusedtoefficiently find long matches to stored data,
`synchronize the storage of previously sent data, and share
`‘
`‘
`previously sent data among one or more other devices.
`
`25 Claims, 29 Drawing Sheets
`
`
`1101
`-
`:
`-
`:
`receiving, by an appliance,a first request from a client for an
`
`NL object from a server
`
`¥
`
`1103
`
`NL identifying, by the appliance, the objectis not locatedinafirst
`cacheof the appliance
`
`¥
`1105
`the server
`NL forwarding, by the appliance,thefirst request for the object to
`
`
`¥
`
`1107
`
`
`
`
`NL transmitting, by the appliance prior to receiving a response to
`the forwarded request, a second request for the object toa
`second device
`
`1109
`NL receiving, by the appliance from at least one of the server or
`the second device, the object
`
`v
`1111
`NL transmitting, by the appliance, the object to the client
`
`|
`
`Data Co Exhibit 1054
`Data Co Exhibit 1054
`Data Co v. Bright Data
`
`Data Co v. Bright Data
`
`

`

`US 7,865,585 B2
`
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`7/2003 Bowman-Amuah
`6,601,192 Bl
`7/2003 Bowman-Amuah
`6,601,234 Bl
`8/2003 Deering
`6,603,470 BI
`10/1995 Clark, Il et al.
`5,455,576 A
`8/2003. Bowman-Amuah
`6,606,660 B1
`5/1996 Dimitri
`5,521,597 A
`8/2003 Mikurak
`6,606,744 Bl
`11/1996 Miller et al.
`5,572,206 A
`9/2003 Guheenet al.
`6,615,166 Bl
`9/1997 Pepeetal.
`5,673,322 A
`9/2003. Bowman-Amuah
`6,615,199 Bl
`2/1998 Moran et al.
`5,717,879 A
`9/2003 Bowman-Amuah
`6,615,253 Bl
`2/1998 Mattson
`5,717,893 A
`
`9/2003 Datta
`w.ccececcseeneeee 709/219
`6,622,168 B1*
`10/1998 Rhoads
`5,822,436 A
`9/2003 Possleyetal.
`6,624,766 Bl
`11/1998 Rhoads
`5,832,119 A
`9/2003 Corneliuset al.
`6,629,081 Bl
`11/1998 Griffiths
`5,838,963 A
`10/2003 Bowman-Amuah
`6,636,242 B2
`1/1998 Rhoads
`5,841,978 A
`10/2003 Hoffbergetal.
`6,640,145 B2
`1/1999 Rhoads
`5,862,260 A
`10/2003 Bowman-Amuah
`6,640,238 B1
`1/1999 Reedet al.
`5,862,325 A
`10/2003 Bowman-Amuah
`6,640,244 B1
`1/1999 Riddle
`5,864,678 A
`10/2003 Bowman-Amuah
`6,640,249 B1
`4/1999 Mawhinneyetal.
`5,898,674 A
`11/2003 Rhoads
`6,647,128 Bl
`5/1999 Gudmundsonetal.
`5,907,704 A
`11/2003 Rhoads
`6,647,130 B2
`7/2000 Reedet al.
`6,088,717 A
`12/2003 Emerson et al.
`6,664,969 B1
`7/2000 Weinsteinet al.
`6,094,485 A
`12/2003 Mikurak
`6,671,818 Bl
`8/2000 Rhoads
`6,111,954 A
`1/2004 Rhoads
`6,681,029 B1
`9/2000 Rhoads
`6,122,403 A
`2/2004 Bowman-Amuah
`6,697,824 Bl
`1/2001 Schusteretal.
`6,170,075 Bl
`3/2004 Rhoads
`6,700,990 BL
`1/2001 Chanetal. ou. 709/247
`6,178,461 BI*
`3/2004 de Vriesetal.
`6,704,738 Bl
`6/2001 Linckeetal.
`6,253,326 Bl
`3/2004: Bowman-Amuah
`6,715,145 Bl
`9/2001 Rhoads
`6,286,036 Bl
`
`6,289,382 Bl=9/2001 Bowman-Amuah 6,721,713 Bl 4/2004 Guheenet al.
`
`6,314,417 Bl
`11/2001 Bennett etal.
`6,742,015 Bl
`5/2004 Bowman-Amuah
`6,317,741 Bl
`11/2001 Burrows
`6,751,320 B2
`6/2004 Rhoads
`6,321,336 Bl
`11/2001 Applegate etal.
`6,757,710 B2
`6/2004 Reed
`6,324,573 Bl
`11/2001 Rhoads
`6,760,463 B2
`7/2004 Rhoads
`6,324,582 Bl
`11/2001 Sridhar etal.
`6,775,392 Bl
`8/2004 Rhoads
`6,332,163 Bl
`12/2001 Bowman-Amuah
`6,813,366 Bl
`11/2004 Rhoads
`
`6,339,832 Bl—1/2002 Bowman-Amuah 6,819,658 Bl 11/2004 Agarwalet al.
`
`6,343,318 Bl
`1/2002 Hawkinset al.
`6,834,276 Bl
`12/2004 Jensenet al.
`6,345,288 Bl
`2/2002 Reedet al.
`6,842,906 Bl
`1/2005 Bowman-Amuah
`6,381,341 Bl
`4/2002 Rhoads
`6,850,252 Bl
`2/2005 Hoffberg
`6,397,259 Bl
`§/2002 Linckeetal.
`6,856,651 B2
`2/2005 Singh
`6,400,996 Bl
`6/2002 Hoffberg et al.
`6,879,701 Bl
`4/2005 Rhoads
`6,408,331 Bl
`6/2002 Rhoads
`6,904,449 Bl
`6/2005 Quinones
`6,415,329 BL
`7/2002 Gelman etal.
`6,925,485 B1*
`8/2005 Wangetal. oc 709/202
`6,434,568 Bl
`8/2002, Bowman-Amuah
`6,938,051 Bl
`8/2005 Burgeret al.
`6,434,628 Bl
`8/2002 Bowman-Amuah
`6,947,483 B2
`9/2005 Engwer
`6,438,231 Bl
`8/2002 Rhoads
`6,957,186 B1
`10/2005 Guheenet al.
`6,438,594 Bl
`8/2002, Bowman-Amuah
`6,957,256 Bl
`10/2005 Bradley et al.
`6,442,748 Bl
`8/2002 Bowman-Amuah
`6,968,057 B2
`11/2005 Rhoads
`6,459,425 Bl
`10/2002 Holubetal.
`6,974,928 B2
`12/2005 Bloom
`6,460,047 BI
`10/2002 Ambroziak
`6,990,453 B2
`1/2006 Wanget al.
`6,473,794 Bl
`10/2002 Guheenetal.
`7,006,881 Bl
`2/2006 Hoffberg etal.
`
`6,477,580 BI=11/2002 Bowman-Amuah 7,025,209 B2 4/2006 Hawkins
`
`6,477,665 Bl
`11/2002 Bowman-Amuah
`7,026,954 B2
`4/2006 Slemmeretal.
`6,496,776 Bl
`12/2002 Blumbergetal.
`7,035,427 B2
`4/2006 Rhoads
`
`6,496,850 BI=12/2002 Bowman-Amuah 7,039,168 Bl 5/2006 Potts
`
`6,502,213 Bl
`12/2002 Bowman-Amuah
`7,047,485 B1*
`5/2006 Kleinetal. wee 715/205
`6,519,571 Bl
`2/2003 Guheenetal.
`7,051,126 Bl
`5/2006 Franklin
`6,522,342 Bl
`2/2003 Gagnonet al.
`7,054,465 B2
`5/2006 Rhoads
`6,529,909 BI
`3/2003 Bowman-Amuah
`7,058,697 B2
`6/2006 Rhoads
`
`6,529,948 Bl—3/2003 Bowman-Amuah 7,069,234 Bl 6/2006 Corneliusetal.
`
`6,536,037 Bl
`3/2003 Guheenetal.
`7,070,110 B2
`7/2006 Lapstun etal.
`6,539,112 Bl
`3/2003 Smith
`7,072,665 B1
`7/2006 Blumbergetal.
`6,539,396 Bl
`3/2003 Bowman-Amuah
`7,075,643 B2
`7/2006 Holub
`6,549,949 BI
`4/2003 Bowman-Amuah
`7,082,572 B2
`7/2006 Pea et al.
`6,550,057 Bl
`4/2003 Bowman-Amuah
`7,092,370 B2
`8/2006 Jiangetal.
`6,553,129 Bl
`4/2003 Rhoads
`7,096,418 B1*
`8/2006 Singhal etal. oo... 715/205
`6,567,533 Bl
`5/2003 Rhoads
`7,097,106 B2
`8/2006 Silverbrooketal.
`6,571,282 Bl
`5/2003 Bowman-Amuah
`7,098,815 Bl
`8/2006 Samuels et al.
`6,578,068 Bl
`6/2003 Bowman-Amuah
`7,103,068 B1
`9/2006 Gardneretal.
`6,580,808 B2
`6/2003 Rhoads
`7,103,197 B2
`9/2006 Rhoads
`6,584,507 BL
`6/2003 Bradleyetal.
`7,103,772 B2
`9/2006 Jorgensenet al.
`6,584,569 B2
`6/2003 Reshefetal.
`7,113,596 B2
`9/2006 Rhoads
`6,590,588 B2
`7/2003 Linckeet al.
`7,113,614 B2
`9/2006 Rhoads
`6,590,998 B2
`7/2003 Rhoads
`7,116,781 B2
`10/2006 Rhoads
`6,594,692 Bl
`7/2003 Reisman
`7,120,666 B2
`10/2006 McCanneetal.
`6,598,077 B2*
`7/2003 Primak etal.
`7,123,617 Bl
`10/2006 Abrol
`
`............. 709/219
`
`

`

`US 7,865,585 B2
` Page 3
`
`OTHER PUBLICATIONS
`
`.......... 707/103 R
`
`
`7,124,101 Bl=10/2006 Mikurak 2008/0046616 Al 2/2008 Verzunovetal.
`
`7,124,442 B2
`10/2006 Nash-Putnam
`2008/0049786 Al
`2/2008 Ram etal.
`7,128,265 B2
`10/2006 Silverbrooketal.
`2008/0225720 Al
`9/2008 Khemani et al.
`7,130,807 B1
`10/2006 Mikurak
`2008/0225748 Al
`9/2008 Khemanietal.
`7,131,596 B2
`11/2006 Lapstunetal.
`2008/0225753 Al
`9/2008 Khemanietal.
`7,135,991 B2
`11/2006 Slemmeretal.
`2008/0229381 Al
`9/2008 Sikkaetal.
`7,137,566 B2
`11/2006 Silverbrook etal.
`2008/0320151 Al
`12/2008 McCanneetal.
`7,140,044 B2
`11/2006 Redlich etal.
`FOREIGN PATENT DOCUMENTS
`7,143,153 Bl
`11/2006 Black etal.
`7,146,053 Bl=12/2006 Rijavec et al. wo WO-9748212 Al 12/1997
`
`
`
`7,146,644 B2
`12/2006 Redlich etal.
`WO
`WO-9967886 Al
`12/1999
`7,149,698 B2
`12/2006 Guheenetal.
`.
`WO
`WO-0051290 A2
`8/2000
`7,150,398 B2
`12/2006 Silverbrooketal.
`:
`WO
`WO-01/47185 A2
`6/2001
`7,159,777 B2
`1/2007 Silverbrooketal.
`WO
`WO-0209339 A2
`1/2002
`7,165,041 Bl
`1/2007 Guheenetal.
`WO
`WO-0232073 A2
`4/2002
`7,167,844 Bl
`1/2007 Leonget al.
`WO
`WO-02076114 Al
`9/2002
`7,171,016 BL
`1/2007 Rhoads
`WO WO-03088065 Al—10/2003
`
`7,171,440 B2
`1/2007 Hanner
`:
`WO
`WO-06061843 A2
`6/2006
`7,175,089 B2
`2/2007 Silverbrooketal.
`.
`WO
`WO-2006074072
`7/2006
`7,178,719 B2
`2/2007 Silverbrooketal.
`:
`WO
`WO-2008/112691 A2
`9/2008
`7,188,769 B2
`3/2007 Silverbrooketal.
`wo
`WO-2008112698 A?
`9/2008
`7,191,252 B2
`3/2007 Redlichetal.
`.
`7,197,374 B2
`3/2007 Silverbrooketal.
`7,207,483 B2
`4/2007 Silverbrooketal.
`7,207,485 B2
`4/2007 Silverbrook etal.
`7,231,405 B2
`6/2007 Xia
`7,251,372 B2
`7/2007 Wood
`7,313,402 BI
`12/2007 Rahman
`.........0... 709/217
`7,343,396 B2*
`3/2008 Kausik etal.
`7,546,353 B2
`6/2009 Hesselinket al.
`7,548,947 B2*
`6/2009 Kasriel etal.
`............. 709/203
`7,584,500 B2*
`9/2009 Dillonetal. ...... 726/3
`2001/0019630 Al
`9/2001 Johnson
`2001/0030970 Al
`10/2001 Wiryaman etal.
`2002/0033844 Al
`3/2002 Levyetal.
`2002/0049861 Al
`4/2002 Bunnetal.
`2002/0085631 Al
`7/2002 Engwer
`2002/0149617 Al
`10/2002 Becker
`2003/0009538 Al
`1/2003 Shah etal.
`2003/0014623 Al
`1/2003 Freed etal.
`2003/0014628 Al
`1/2003 Freedetal.
`2003/0058873 Al
`3/2003 Geigeretal.
`2003/0065743 Al
`4/2003 Jennyet al.
`2003/0069890 Al*
`4/2003 Benson etal.
`2003/0079040 Al
`4/2003 Jain etal.
`2003/0187917 A1l* 10/2003 Cohen ....... eee 709/203
`2003/0206554 Al
`11/2003 Dillon
`2003/0233423 Al
`12/2003 Dilley etal.
`2004/0098463 Al*
`5/2004 Shenetal. we. 709/213
`2004/0128346 Al*
`7/2004 Melamed etal.
`............ 709/203
`2005/0004954 Al
`1/2005 Soule
`2005/0063519 Al
`3/2005 James
`2005/0080850 Al
`4/2005 Salesky etal.
`2005/0097085 Al*
`5/2005 Shenetal. we. 707/3
`2005/0108517 Al*
`5/2005 Dillon etal... 713/150
`2005/0114296 Al
`5/2005 Farberet al.
`2005/0144186 Al
`6/2005 Hesselink etal.
`2005/0149481 Al
`7/2005 Hesselinket al.
`2005/0185677 Al
`8/2005 Christofferssonet al.
`2006/0034212 Al
`2/2006 Mutch
`2006/0069926 Al
`3/2006 Ginteret al.
`2006/0095588 Al
`§/2006 Van Lunteren
`2006/0123467 Al
`6/2006 Kumar etal.
`2006/0129689 Al
`6/2006 Hoetal.
`2006/0271705 Al™ 11/2006 Garcia-Luna-Aceves .... 709/242
`2006/0274828 Al
`12/2006 Siemenset al.
`2007/0002780 Al
`1/2007 Pessi
`2007/0156852 Al
`7/2007 Sundarrajan et al.
`2007/0179955 Al
`8/2007 Croft et al.
`2007/0234324 Al
`10/2007 Ananthakrishnan etal.
`2007/0245409 Al
`10/2007 Harrisetal.
`
`
`
`Fendick et. al., “Analysis of a Rate-Based Control Strategy with
`Delayed Feedback”, Aug. 1992.
`Kalampoukaset. al., “Improving TCP Throughput over Two-Way
`Asymmetric Links: Analysis and Solutions”, Jun. 1998.
`Santos et. al., “Increasing Effective Link Bandwidth by Suppressing
`Replicated Data”, Jun. 1999.
`Samaraweera, “Return Link Optimization for Internet Service Pro-
`vision Using DVB-S Networks”, Jul. 3, 1999.
`Spring et. al., “A Protocol-Independent Technique for Eliminating
`Redundant Network Traffic”, Aug. 2000.
`Cooper,et. al., “Internet Web Replication and Caching Taxonomy”,
`Jan. 2001.
`Border,et. al., “Performance Enhancing Proxies Intended to Mitigate
`Link-Related Degradations”, Jun. 2001.
`Ishac et. al., “On the Performance of TCP Spoofing in Satellite
`Networks”, Oct. 28, 2001.
`Dutta, et. al., “An Active Proxy Based Architecture for TCP in Het-
`erogeneous Variable Bandwidth Networks”, 2001.
`Feighery, “Frequently Asked Questions for Performance Enhancing
`Proxies”, Jun. 27, 2005.
`USPTOOffice Action for U.S. Appl. No. 11/685,157, mailed on Feb.
`4, 2008.
`USPTOOffice Action for U.S. Appl. No. 11/685,161, mailed on Feb.
`4, 2008.
`USPTOOffice Action for U.S. Appl. No. 11/685,170, mailed on Feb.
`4, 2008.
`Chankhunthod A. et. al., “A Hierarchical Internet Object Cache”,
`XP002285170, Jan. 1, 1996.
`Office action for app 11685157 (CTX-321) dated Feb. 4, 2008.
`Notice of allowance for app 11685165 (CTX-320) dated Apr. 23,
`2008.
`Notice of allowance for app 11685170 (CTX-336) dated Jul. 7, 2008.
`Notice of allowance for app 11685165 (CTX-320) dated Jul. 22,
`2008.
`Office action for app 11685157 (CTX-321) dated Jul. 31, 2008.
`Notice of allowance app 11685161 (CTX-312) dated Dec. 30, 2008.
`Barish et. al., “World Wide Web Caching: Trends and Techniques”,
`IEEE Communications Magazine, IEEE Service Center, Piscataway,
`US,vol. 38., No. 5, May 1, 2000, XP011091295, pp. 178-185, ISSN:
`0163-6804.
`Office action for app 11685157 (CTX-321) dated Jan. 8, 2009.
`International Search Report for PCT/US2008/056681, mailed Nov.
`12, 2009.
`Written Opinion for PCT/US2008/056681, mailed on Nov. 12, 2009.
`International Preliminary Report on Patentability for PCT/US2008/
`056681, issued Nov. 17, 2009.
`
`2008/0034416 Al 2/2008+Kumar etal. * cited by examiner
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 1 of 29
`
`US 7,865,585 B2
`
`8¢
`
`
` 000q90lJee8S
`U90D,=AaAuag
`=i=.
`
`B90,seAsag
`whsouelddyae—ZJOMj}3
`
`*HOMON002
`
`uojezIUdo
`
`eolAep
`
`NVM
`
`
`
`Jd
`
`002
`
`eouelddy
`
`NVM
`
`
`
`uoeziwizdo
`
`aolAep
`
`Vi‘Sls
`
`YOMJON
`UZOLward
`
`CZOLywalld
`qzOl=jywuala
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 2 of 29
`
`US 7,865,585 B2
`
`sourlddy
`
`
`
`Uo}e1a/8007
`
`(ao1aap
`
`‘Aemayeg)
`
`do|JeMaly
`
`NV1
`
`aourlddy
`
`NVM
`
`uoljzezIWdO
`
`eolAap
`
`
`
`
`
`Yjaouelddyeourtiddy
`
`al‘Sls
`
`(eo1Aep
`
`
`
`‘Kemayeg)NVM
`
`uole19|999'7aodlAap
`JO[JBMadyNonPaRAeO
`NW7
`
`yAOMIONnee
`
`ZOL3UaND
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 4
`
`’
`
`2011
`
`Sheet 3 of 29
`
`US 7,865,585 B2
`
`YIOMION
`YAOMJON
`eoueddySSj—
`
`NVM
`
`ZOLual
`
`
`
`90140AJ0suoljeziWIdo
`
`aolAap
`
`
`
`90}JeA1040[JeMellyuoljezIWydOs‘Kemoyed)ZOL3uald
`
`NVM
`
`«VOL
`
`
`
`yIOMJONyIOMJON
`
`
`
`aouelddyaouelddy
`
`(ea1Aep
`
`
`
`Udl}eIB/9D0Y9dIAEp
`
`JLSls
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 4 of 29
`
`US 7,865,585 B2
`
`OSL
`
`A
`
`yJOMION
`
`S02L91UI
`
`
`
`UONe||e1SU](s)eoinapOll
`
`901AaqTHLO
`
`Ke\dsiq
`
`eck
`
`SLLOLE
`u-epzj—Let9eb
`
`901Aeq
`
`Bunulodpueoghey
`
`G/L‘Sila
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 5 of 29
`
`US 7,865,585 B2
`
`
`
`
`
`
`44)
`
`Ort
`
`bor
`
`
`
`suse)JOSSOOOIg
`
`ule
`
`
`
`GOELKIOWA]Hog|10q|10g
`
`uIRepyAJOWS|O/T}O/T
`
`QO1AOC]
`
`OSL
`
`
`
`O/COL
`
`Ab‘Sls
`
`POEL
`
`Ol
`
`dd1Aaq]
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 6 of 29
`
`US 7,865,585 B2
`
`©O
`
`FJenleg
`
`aulbugAdog
`
`S6z
`
`06zWaisks
`
`AJSA8q
`
`
`
`UOHEZIWdOYIOMISN
`
`
`
`«oGeeulbug
`
`uoljealddy
`
`uoljeoddy
`flmn
`
`olyeyed
`
`Za
`
`yIOMJON
`
`
`
`gezeulbuguolssaiduiog
`
`
`
`
`
`ZeeoyoegjJabeuey|eyoe5
`
`SoeeulbuqAdlod
`
`Port N 266N
`
`
`
`Z9Z(s)49e1SYIOMJON
`
`Port 1 266A
`
`002soueljddy
`
`
`
`
`
`aulbuyuoVeziwUndoyomMeN
`
`0sz
`
`
`
`
`
`aulbuyBuissesolgexoeg
`
`Ore
`
`
`
`
`
`O1b210}99}9—PNVAWNV1
`
`LeJudWUOJIAUg
`
`Bunndwoy
`
`
`
`ZPquabyjual|9
`
`
`
`UOHEZILUNdOYJOMION
`
`
`
`9€zeulbuySoD
`
`
`
`0zz2Jal|o.UODMo|40Seeulbug
`
`PEtJojelajaooyJOD0}01gcob 3USHD
`
`udl
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 7 of 29
`
`US 7,865,585 B2
`
`deSls
`
`©O
`
`FJaAlag
`
`
`
`aulbuyAoyog
`
`SGL
`
`
`
`UOHeZILWUdOYIOMIeN
`
`
`
`«Oseeulbuy
`
`uoljeaddy
`
`alyeyed
`
`DELwajskswarOL
`_Oh
`uoljeoddyHOMION
`waAlsayaqjjome
`
`
`
`B
`
`Burndwoy
`
`
`UOIJEZILUdOYIOMJON
`be}UsWUOUIAUZ
`
`OcFjusbyjus!9
`cOL=JUaIID
`
`(oGeeulbuy
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 8 of 29
`
`US 7,865,585 B2
`
`
`
`
`
`
`
`
`
`
`
`
`ZREneiyaeuevesoo
`
`
`
`
`agpwebypass
`
`
`
`
`
`
`
`
`
`
`
`
`|44444i
`
`yloralan]
`IRIS
`£0){Uayo
`
`
`
`292
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 9 of 29
`
`US 7,865,585 B2
`
`uoIssaJduoo
`
`eJep
`
`YAOMJON
`
`voL
`
`POOP
`
`0Sz
`
`aulBug
`
`Aso\siy
`uo}eZIWI}dE
`
`0sz
`
`yIOMJON
`
`
`
`PZOLISD
`
`
`
`9ZOLJAD
`
`=:
`~Nq00r
`
`Ajoysi|UOlISsesduco
`VvSls
`0}ssouaJaja1pue
`—_——_.=:ooI:|eyep~eO00r
`
`UolssaJduooyIOMION
`200eulsuy
`
`Aloyslyuoneziwido
`
`uolssaidWico
`
`Aloysiy
`
`UOoISsaJdW0o
`
`Asoysiy
`
`
`
`suolyiodeyep
`
`aouelddy
`
`9002
`
`
`
`aourlddy
`
`e002
`
`
`
`qusl|d
`
`ezoL
`
`
`
`
`
`
`

`

`Jan. 4, 2011
`
`Sheet 10 of 29
`
`US 7,865,585 B2
`
`U.S. Patent
`
`
`
`
`
`
`
`eyeppayilusued)Ajsnoiaaid
`
`SOP
`
`
`
`Jepeeyyunyo
`
`uoIssaJdW0y
`
`Ayoysiy
`
`oor
`
`yunyo
`
`SOr
`
`av‘Sls
`
`TdSLV
`
`
`
`
`
`
`
`
`
`JaqulodyunuoyxeuJaljjuaplsnye}s
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 11 of 29
`
`US 7,865,585 B2
`
`oNoly_—Xapu|
`UvSls oor
`
`oO
`
`oO
`
`°O
`
`OL
`
`Lb
`
`cl
`
`
`
`Ajoysiyuoisseiduiog
`
`
`
`sayNUSp!UOHeD0|
`
`zy
`
`UDIssaidWiOy
`
`
`
`juawejsabeioig
`
`OSD
`
`yunya
`
`SOV
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 12 of 29
`
`US 7,865,585 B2
`
`O00
`
`oS
`
`JOYNUSP!UES]
`
`02r
`
`
`
`Xapu|UOIssaldwioD
`
`3o©
`
`OL
`
`LL
`
`cl
`
`
`
`quudue6bul+JSul4
`
`ulJUaWa]a
`
`a|6uiys
`
`OLS
`
`ulJUBLUE]9
`
`a|Burys
`
`qsal4
`
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 13 of 29
`
`US 7,865,585 B2
`
`aolAepeAq‘Bulysijqeise
`eyepyndulJosjuudiabuyJoJaquinue‘aso1aapay)Aq‘BulAjnuapl
`eBJosyuudiabuyspuodsaiosyey)AWowswUlxspulUe‘aGeJo}s
`
`
`
`psuluusajepaideMO|Saqs|qepUus}x9SIySIPUOByepsnonBbijUCS
`
`
`}Suly&0}Bulpuodsei09ssdipulBulaeyAsowawUlsyuUdiebuly
`
`
`
`ay}BulaeyaBeso}sulSued)BulAjusp!suayUEp!UOEI0}
`
`
`
`
`o}eyepyndulJoyoyewpayeujssueyey)JaIUSpP!UOI}ED0|
`
`
`
`ulAJoysiyuoiIssaidwioseBulaey
`
`PSYNUSPIJOJOquUINU9Uj}Wd‘BdIAep9uyAq‘BululWey}ep
`
`
`0}AlojsiyUOIssesdWod98y}JoeyepJoSUIOdJoAyyeunjd
`
`
`UlXOPUIBY}JOS8dIpUTJoAjyeun|deyosyuLdsebuyyoy
`
`
`eyepjosuoiwodJoAypeunjd
`
`AJOWOUW
`
`ploysedy)
`
`LOS
`
`€0S
`
`SOS
`
`60S
`
`elepyndul
`
`
`éplousosyy—uolsseidwiooSy}esnmojeqSAA
`9U}SS8JGLUOD0}AJO}SIY
`
`au}Aq‘Buiiwsue)
`
`ulpesseJduooun
`
`eyep9y}‘solAap
`
`8]0}ssuodsal
`
`UOI}EUILW9]9p
`
`L0G
`
`gs‘Sls
`
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 14 of 29
`
`US 7,865,585 B2
`
`COoOo|XtOL
`
`oOOOo
`
`LL
`
`cL
`
`V9‘Sls
`
`G
`
`9
`
`Z
`
`8
`
`6
`
`oNqoLyaXapu]
`
`UdIssaidWoy
`
`UOeD0|
`
`0cr0JayUap!
`
`O00v
`
`L
`
`ulcjuawaja
`
`S414
`
`a|Buiys
`
`
`€
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 15 of 29
`
`US 7,865,585 B2
`
`salaapeAq‘Bulysijqe}sa
`BulAJQusplsusyyUsp!UOEd0]0}AJO}sIyUOISSsidWODSu]Joeyep
`
`
`
`9uU0}se9]JeHulAeYyXSpuU!9yjUlSalWjUSJoAyjesnjdeyoyeWeyep
`
`
`
`ynduljosyudusbuyJoAyyjesnjdeyeu‘solAepayyAq‘BulAyquepl
`
`
`eyepo}eyepIndul9}JoUOIodJsulle‘adIAapay)Aq‘Bulyoyew
`
`
`JosuoiyodjoAyyesnjdejosyuldssbulysouodss.o09yeu}XEpul
`
`
`
`au)AqpaynusplAJojsIyUdISSeJdLUOS84)UlUOI}e90]}SJlUl
`
`
`
`
`ue‘AJo\siyuolsseidwooeBulAey
`
`saljuejoAyjeunjdayyjoAujusue‘solAepauyAq‘Bunosyjas
`
`
`eyepjosuonodjoAypesnjdoy}BuiaeyysIpUcSuOe90|
`
`
`
`
`
`sJalJUSp!UO!}Eo0|JoJequinujsema]eBulAey
`
`
`
`Jayusp!UOVeIO|
`
`g9‘Sls
`
`
`
`Aquapayoajas
`
`LO9
`
`€09
`
`S09
`
`209
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 16 of 29
`
`US 7,865,585 B2
`
` V2‘9lh
`
`
`
`ejepuoljeo|ddeeyepuoneoddeejepuoljeoydde
`
`
`
`eulbueuolsseidwios
`
`gee
`
`
`
`
`
`
`O0°90eyepuoleoddeWyeyepuoyeoddeeyepuoleoydde
`20ZZYYq0zZe0zL
`
`
`
`eyepuoeodde
`
`weads
`
`002
`
`
`
`HdVvHdIVJake]uoneoydde
`
`
`
`
`
`0bq0Ld(HdTv)Jepeeyjooojoid
`
`POLZ
`
`
`
`2022qoeZe022
`
`
`
`
`
`007Aloj}siyUcIsseidu04eouenjddy
`
`002
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 17 of 29
`
`US 7,865,585 B2
`
`uolsseiduo9 2012GOLZ
`
`aZSls
`
`
`
`BLEZ Zjalgo
`
`
`goez1pelgoeLezZzyelqo
`
`
`
`eyepuoneoyddeeyepuoneodde
`q0eL|pelqo|eogs|pelga
`aulbue
`
`
`
`eyepuoljeslddeeyepuoneoydde
`Hd1¥HdT¥
`
`00PrAlojsiyUolssaidwo5
`
`
`(HdTv)Jepesyjooojoud
`
`
`
`
`
`ejyepuoyeodde
`
`weais
`
`002
`
`8ec
`
`
`
`eyepuoneoydde
`
`eoueljddy
`
`00z
`
`
`
`JaAe]uaneoyjdde
`
`POLL
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 18 of 29
`
`US 7,865,585 B2
`
`JZ‘SlA
`
`)
`
`LOZ
`
`€02
`
`JsulyeAq‘Bulalsoo
`UoIsseJdWooe0]soUaNbaspuoDss9]PUesoUSNbesJsIl)8y)
`
`
`uoljeoddejosouenbssjsuyeUsaMjaqJapesyjosojoOJdJaAe|
`
`
`
`
`
`Bulsliduicopauiqwooe‘aolAapjsulyau)Aq‘Buuojssouenbas
`
`
`
`uoneoddesuo1sea]yeBulsiuidwooweeseyepuaeoldde
`
`
`
`
`ay}‘weedsBJepUoIeo|ddeue‘sdIAap
`
`
`dy)PUBsoUSNbassiBuy‘AdIAapISuHoy)Aq‘BHulAyQuap!
`
`weajjseyepuoneo|ddeau)wousouanbespucses
`
`
`
`
`ejepuoieoddejosousnbaspuosssepukeejep
`
`
`
`Asoysiy
`
`)
`
`GOL
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 19 of 29
`
`US 7,865,585 B2
`
`QZSih
`
`
`
`Ajo\siyuolssasduooeJoUolod
`
`ysuljeAq‘Bulalsoal
`eBsayoyeBOUeNbespuooaspuesoUSNbesJsiJay}Bulslidwioo
`
`
`
`UONEWUOJU!‘SdIA9PPUODESB0}SOIASPjsulyay}Aq‘Bulywsuey
`
`
`
`uoleo|ddejosauanbasjsulleUVaMJ9qJopesy|Coo}O/dJaAe|
`
`
`
`
`
`uoneoddesuojseg]yeBuisudwooweedseyepuoneoyjdde
`
`
`
`
`
`a0UsNbasPsUuIquoDejeu)‘BOIANPjs4yeu}Aq‘HululWajap
`
`
`
`au}‘WesseyepUoNeoddeue‘sainap
`
`AjoysiyUolsseidluooay}JoUoKJodpeyoyewau}BulAjQuepl
`
`
`
`ay}puesouenbesjsuyau}‘BdIAapysulya4}Aq‘BulAyquap!
`
`
`weajseyepuoleol|ddeay}WolysouUenbespucoes
`
`
`
`
`eyepuoleoddejosouenbsspuocossepueeyep
`
`
`
`
`)
`
`LZ
`
`eSZ
`
`)
`
`GGL
`
`2£G2
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 20 of 29
`
`US 7,865,585 B2
`
`
`
`QLogAlojsiyuolssesduoo
`
`
`
`‘eJEPSOAIB0OL/S}ILUISUCI}
`
`esuleyulel
`
`
`
`pasnAjuaoal}se9|Aqpayios
`
`‘syunyoJosi]SuleyuleW
`
`q€08
`
`jsB9|JOJaquunuesajajap
`
`
`
`syunyopesnAjusoes
`
`
`
`
`
`JoJAqUUNU[eyo]S}IWSUeL}
`
`
`
`Bulurewassyunyo
`
`
`
`
`
`yunYopueBj}ep
`EL—I==Ha|
`
`souelddyaouel|ddy
`q00ze002
`
`
`slayjuep!
`
`
`
`Hululewiadsyunyojoyaquunu
`
`
`
`BulApnuep!Uo}eWUOJUl
`
`
`
`BLOgAlojsiyucissaiduooe
`
`
`
`‘eyepS2AI909/S}ILUSURL}
`
`Bulureyureul
`
`
`
`pasnAjusoajsea]Aqpayos
`
`
`
`
`
`‘syuNUoJO}SI]SUIEJUIELU
`
`
`
`UOHEWUOJU!SBAIBOOI
`
`e€08
`
`
`
`syunypsjoJequunuBuldyyuepl
`
`sogOululewas
`
`V8‘Sis
`
`
`
`208Alojsiyuolsseidtuoo
`
`uoulsyuNypJoJaquuinu
`
`
`
`8B0UBDSa|0SqoJO}sJoales
`
`
`
`pasnAjuadedJse9]JoJequunu
`
`qoozpueegozey}ossyunyo
`
`
`
`JOJAQLUNUaLUeSBU}BABYJIM
`
`
`
`uolssaJdiuodwlouyulSyuNYyo
`
`608sauojsiy
`
`
`
`
`
`UU}SS9]|S$!JOqLUNUSeUILUJe}ep
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 21 of 29
`
`US 7,865,585 B2
`
`UOISSOJGLUODJSe‘SOIAapyseAq‘Buloys
`eyepJouoliodoes‘aolAappuocosseOo}payLUsUedA[snolAaid
`
`
`
`‘SJOIUSP!UONELIO|JoSI]SU}WO‘soUsosajasqoJo}GuNjosjes
`
`
`paJeploay}JOpusUeyeSJaljQUSp!UONEIO]JoJUNOWEjSJLOU}
`
`
`eyepjosuoodJoAyyesnjdeBuisiudwooAyolsiyuoissesdwioo
`
`
`ejepJosuojodpesseoseAjjUaoa/jse9]0}Bulpuodse.uos31]
`
`
`
`
`UOISSAJCLUODISJIJBU}JOSUBYHUSP!UONedo]JoAUeNbeUeY)
`
`
`sse|siAUeNbpanlsoesBu]‘BdIAEpjs4yEU)Aq‘BululWsejep
`
`
`
`@pessao0eJSP]SIIASPISI)94)Blu]eAqpasepsosJaljnuspl
`
`
`
`
`Jaluap!yoesoO}Bulpuodsai09UoNes0|&UIeyepJoUOTOd
`
`
`
`2JosJaynuUap!UoHeso]JoAyQUuenbeBulAyjuap!UOeWOJUI
`
`
`puoses9u}UOAJojsiyUoIssesduuo9puosesBulpuodseco
`
`
`
`au}‘AJOJSIU
`UOIEIO]JOJsl]PAs9POUe‘BoIASpJsuy.BuyAq‘Bulyeauo
`
`
`
`SIIASPPUDDASBU}WIJSdlAapJsdlyBy)Aq‘BuIAISOaI
`
`
`
`
`
`
`JoyyusplUoWeoo]eBulaey
`
`LO8
`
`£08
`
`S08
`
`sdlAep
`
`)
`
`a8‘Sls
`
`
`
`junoweysuyeAqAlojysiy
`
`)
`
`408
`
`608
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 22 of 29
`
`US 7,865,585 B2
`
`
`
`
`
`AJo}siyUOISSaJdWodpsAlsoaoy}Buisn
`
`900Zsouelddewoyasuodsa
`
`2POL
`
`sessaiduiooepqoogsauel|dde(¢
`
`so|
`44OMJON
`aouelddy
`
`
`
`e00z90uel|dde
`eoupldde(2
`
`spues400d
`
`eZOL
`
`yuayde007
`
`‘aouelddy
`
`Let
`
`
`
`
`
`spuasegozaoueiidde(gJo}ysenbal
`
`
`
`
`
`eyepAloysiyuolssaiduuo0ouolssaJduioa
`
`jUusI|D
`
`qzoL
`
`9002
`
`
`
`qoozeoueldde0}0}e}epAJojsiy
`
`
`
`
`
`V6‘Sla4
`
`
`
`e00Zsouel|ddeyimpaseys
`
`
`
`AJoysiyUOISSaJdLUOD0}
`
`JOMJON
`
`er0L
`
`
`
`
`
`
`
`soyo}elusjoojep900gsouel|dde(g
`
`
`
`
`
`ysonbaqzo|}USI|O0}asuodsol
`
`
`
`90)J@AIaSLUOUy
`
`
`
`Bulaiaoaysulbeq900¢aouel|dde(p
`
`
`
`
`
`eouel|ddy
`
`9002
`
`JOAIBS
`
`901
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 23 of 29
`
`US 7,865,585 B2
`
`a6‘Sis
`
`
`
`a0lAappuaves
`
`LOG
`
`c06
`
`
`
`a0lAappuaves
`
`/
`
`ISUeAq‘Bunjwwisuedy
`UONESIPUIUE‘BOIASPPIU}OU}LUOJJSOIASPJsulyBUAq‘BUIAISO04
`
`
`
`
`eyeppuosesujJOUONJOd&yeu)‘SdIASpJsu)By)Aq‘BulAjnUep!
`
`
`
`JO}pepusjulWesjseyepPUdDASB‘edlAapPysuyeAq‘BUIAIeoe1
`
`
`
`}SJJ©0}Bulpsoo0epasseJdwiooWiesd)seyepJsulyBy)‘Wess
`
`
`
`
`
`8]PUBSsdIAEpJsJIJBY]UBEMJeqpasesAJO}sIyUCISsedU0O
`
`
`
`
`
`eyepJsdl)&‘BO|AapPUOdaseO}BDIASP
`
`UOISSaJCWODSJBY}JOUOJOdayyHulAyQuap!UOPeLUJOJUI
`
`
`AJoISIYUCISSOJGWODJsSJl}OU]JOUOIOdeBsoyoyewWLUeEL)S
`
`
`
`94]SEYIOMIJSUBLSBU]UOP9}e00]$IBOIASPpul]eJeUy
`‘QOIAQPPUCDSS9U}O}BOIASPJsJyOyAq‘Huiwsuey
`
`
`
`SSIASPPJIY}OU}
`
`/
`
`£06
`
`GO6
`
`206
`
`Asojsiy
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 24 of 29
`
`US 7,865,585 B2
`
`‘Buljiwsuey
`}SJJ@‘AD|ABPPUODSSBpPUesOIASPJsulyBUBamjag
`
`
`
`paljyUSP!OU)‘SdIASPPly]BU}O}BOIAEPJs4yOUAq‘BuWsUeH
`
`
`
`pesseidluooWeeJj}seVepJSJlyOl]‘WeedseyeppueSdIASpSdOU}USEANjoqposeysAJO}sIyUOISSesCWOD}suy&0}Bulpsoo0e
`
`
`
`
`
`
`
`
`
`
`
`UONEWJOJU!‘BOIASPPAIY)CWO}SdIASPJSJJOyAq‘Hulaleoes
`
`
`
`
`
`
`AjO}SIYUOISSBJGWOD}SJBY)JOUONOdeBulAynuepr
`
`
`
`SBdIASPPUODESOU}
`
`LL6
`
`L6
`
`GL6
`
`
`
`
`
`AJOYSIUUOISSAIGWODJSJIJBY)JOUONJOd
`
`J6‘Sid
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 25 of 29
`
`US 7,865,585 B2
`
`LE6 /
`sul]@Aq‘BUIAISO9/
`pJly]@PUBSdIASPJSJIJBY)UBEMIEqpeseUsAJO\sIYUOISSEsdLUOD
`
`
`
`
`
`Jo}jsenbade‘eolAapply]BU}0}SOIASPJsuly94Aq‘Buimiwisuey
`
`
`Byepe‘SdIABpPUOISS&WOSdIAaP
`
`OU]‘SOIASPPIU]SU}WOI,SOIABPsly94)Ag‘BulAlsoel
`
`
`
`20}BulpsoooepassaidwioosWesseyepoy)‘Wess
`
`
`
`
`
`
`weedseyepoy)‘solAepisd94)Aq‘Buisseiduios9p
`
`
`
`@01A@pplu}OU)‘@dIAapJs4ya4)Aq‘BulAyQUap!
`
`
`
`Ajoysiyuolssaidwiosau]Jouolodpalsanbas
`
`SolAap
`
`L26
`
`d6‘Sls
`
`Buliwisuey
`jual|9&O}Wealjseeppessajdwooepau)
`
`
`)
`
`
`
`AjoysiyUoIssaidWod9)JoUoIode
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 26 of 29
`
`US 7,865,585 B2
`
`eZOL
`
`spuasode
`
`
`
`
`
`spuesego0zeauel|dde(6Jo}ysanbad
`
`
`
`
`
`eyepAlojsiyuolsseidioouolssaudwioo
`
`
`
`qoozsoueldde0}0}eyepAsoysiy
`
`
`
`eB00Zeouel|dde
`
`jual|9
`
`azoL
`
`eouel|ddy
`
`9002
`
`
`
`
`
`pueqoozsouelddeojyoyewjo
`
`'''!!!!'!'!!!!
`
`
`
`
`
`Bulpiosoeasuodsaisassaidiuoo
`
`
`
`
`
`Asojsiyuolssasduaday}0}
`
`
`
`
`
`
`
`sessaidwovepqoozsoueldde(pp
`
`
`
`
`
`AJO\SIYUOISSAJGLUCDPSAlsO9J0}Bulsn
`
`
`
`poozsouelddewoasuodsay
`
`YIOMION
`
`SPOL
`
`YIOMJON
`
`qr0L
`
`VOL‘Sis
`
`
`
`S—=—a
`
`yual9e002
`.aouel|ddy
`
`+—>=!
`
`
`soueldde(1WoJ)eyepsjsenbeSIILUSUBA
`jue(¢
`!!!'''!!!!''''!1!
`AJOISIYUOISSeJdLUODBUlB}eEpOUyelo}saouelddy
`
`
`
`
`
`\Woyeyepspuss900¢souel|dde(1
`
`
`
`uoleolpulspuespoogeouel|dde(g
`
`
`yore‘eZQ|]UAal|D0}gO}JeAlas
`
`90)JansesWO.eyepsells
`
`s}senbelqzo)
`
`
`'poozsouelddeuolsseiduu0o
`'2002
`
`
`poozsoueldde(22002eoueldde(z
`
`aouelddy90)JeAles
`SOUILUUBJSpPUBO00Zsouel|ddewoypeareoas
`
`
`—O}9ZO}jUal|o==—:|woyjsenba
`sassed
`
`
`
`sayojeus}oajeppoozsouel|dde(9
`
`
`
`Bulalsosysulbsqpogzsouel|dde(¢
`jsonbeqzO]jUSal|o0}asuodse.
`
`
`qooz0}ayetulxoudaouelddeue
`
`0}puodseicesyunyopeyojew
`
`
`
`
`
`P00z
`
`
`
`poosouel|dde(p
`
`
`
`poozeouel|dde
`
`0}Xepul
`
`ABAIVS
`
`SOL
`
`yIOMION
`
`er0L
`
`
`
`X8PUlUOISSSJGLUODOC}
`
`
`
`QO)JeAsasWoy
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 27 of 29
`
`US 7,865,585 B2
`
`ysulyeAq‘BulAlaoas
`UOneD0|&‘dIASPPUODES98Y)O}SOIASPSUI)94}Aq‘Bunwsue)
`
`
`UONLI0]&‘BIIASPPUDDIS9U}0}BOIASPJsulJ9UyAq‘Bunwsuey
`
`
`UONEWNOJU!‘SdIASPYWNOJBU}0}SOIASPysuyy9y}Aq‘Bunwwsuey
`
`
`
`UOISSSJGLUOD98}JOUOIOday)‘solAepsul)au)Aq‘BululWa}ep
`
`
`
`WeadjseyepujJOUOIJOdeyeu}‘BdIA9PJsJijOU)Aq‘BulAyuapt
`
`
`
`puiooasau}UsemjeqpeseysAJO}SIL|UOISS8JGLUODeJO}SaLjUS
`
`
`
`JoXapulUe‘BdIAappUOdes&LOYBoIAap
`
`
`&JO}pspusjulWesseyepe‘aoIAapJsuyau}Aq‘Bulaisoas
`
`
`eBulslidwooAuexapulYoes‘ed1A9ppJly}epueSolAep
`
`
`
`8d|ABPPUOIESOU}UIPSJO}se}epJoJeyNUEp!UCI}ED0|
`
`
`
`Ajolsiyuolssesdwooay}JoUoloday)BulAyquapl
`
`
`
`
`
`Aquapeyoyelau}0}Bulpuodse.uocaJalyuepl
`
`
`AduP8Yyo}eW9Y}0}BUIPUOdSe.J0NJalJUSpI
`
`WeedseyepSU}JOLOlLiodeseyo}ewAJoysiy
`
`
`XOPUlPeAlsoesoy)JoAyjUSUeseyoyew
`
`gob‘Sila
`
`Sd1A9pYYNo}
`
`)
`
`)LOOL
`
`./Oo
`
`o=_
`
`_/oS
`
`oS=
`
`/6001
`
`)
`
`)eLoL
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 28 of 29
`
`US 7,865,585 B2
`
`YIOMJON
`
`oP0b
`
`ViLSls
`
`
`
`JaAlagJSB9]2O}S]lJSU}10}s}sanbel
`
`
`g0L1AjjequeyodeyoesJeujoBuO‘
`
`
`
`i1fosuibeqeoozeouel|dde(pF
`
`
`(qg¢1'\e002Jepuodsel1S8qJOSJWO;eourlddy
`11Joayoeoi'J@SMO1g)
`1111qzoL'1wally'1111111II11II11111111IIIIII\1'ayyayyBuiaey
`''''!SS'Sy
`
` ayoeoMay1|B90|SHIUlJOUSIaI}peysenbeayGQ'SOUILUa}opaouel|dde(Zez01BQO?
`
`YIOMJON{'q00z|'aourlddy\I|el\=:1111
`Itslsueyosje900Zaouel|dde
`av0L°vOb1YIOMJON
`2ZO}alloO}olyBunILUsUey
`
`'(Quebejualjo
`
`1'
`
`I
`
`90]JeAJas0}91}10}ysenbe's}ilusued}
`
`
` e0OZaouel|dde(eg'11
`
`‘Z
`
`jual|D
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 4, 2011
`
`Sheet 29 of 29
`
`US 7,865,585 B2
`
`)LELLL
`auyAq‘Humusuey yoalqo
`JSUlJ@UlpayeoojJousiJOafqoau)‘souerlddeauAq‘BulAyquapt
`
`
`
`
`0]algoau}JO}Jsanbejsuyyau‘eouel|ddeayyAq‘Hulpyenuo}
`
`
`0]ssuodsaleBUIAIa9eJ0}JOsoUel|ddeoy)Aq‘Buimiwsuey
`ueJOJJUSI|OCWO,JsanbadJsuye‘souelddeueAq‘HulAlsoel
`
`
`
`JOJ9AJ9S8U}JOSUOJSe9]YEWOU}dOURI|ddeaU)Aq‘BulAlsoos
`
`
`
`B0}algoau}JO}Jsenbespuodeske‘JsenbepapseMio}9y}
`
`
`qUal}a9}0}algoauy‘soueldde
`
`JaAlas&WOjoalgo
`
`
`
`souel|ddeey}josyoeo
`
`JO@AI8SBY)
`
`abbSls
`
`
`
`au}‘SdIASpPucdes9}
`
`
`
`ad1Aeppuczes
`
`

`

`US 7,865,585 B2
`
`1
`SYSTEMS AND METHODS FOR PROVIDING
`DYNAMIC AD HOC PROXY-CACHE
`HIERARCHIES
`
`FIELD OF THE INVENTION
`
`The present invention generally relates to data communi-
`cation networks. In particular, the present invention relates to
`systems and methods for compressing data streams and
`improving network performance by leveraging previously
`stored data.
`
`BACKGROUNDOF THE INVENTION
`
`Compressing data streams by utilizing previously stored
`data is a known technique for reducing the size of data
`streams transmitted between two devices. In broad terms, a
`typical compression methodentails two devices each storing
`copies of data that is sent between the devices. These stored
`copies ofthe data can be referred to as compressionhistories,
`as they representa history of previously transmitted data that
`is then used to compress future data streams. Whenoneofthe
`devicesis transmitting data to the other device,it searches its
`compression history for matches to the input data, and
`replaces the matched portions with references to the stored
`data in the transmission stream, reducing the size of the
`transmitted stream. The receiving device then uses the refer-
`ences in combination with its own compression history to
`reconstruct the uncompressed data stream. However, this
`general technique presents a numberof challenges.
`First, insufficiently long matches between input streams
`and compression histories can result in poor compression
`ratios, as well as increasing the processing overhead and
`numberoftimes that a compression history must be accessed.
`These problems can be exacerbated in cases where a device is
`transmitting multiple data streams simultaneously, and thus
`may haveseveral processes attempting to access a compres-
`sion history simultaneously. These problems also may be
`accentuated in devices using a compressionhistory stored on
`amedium,such as a disk, with long potential access latencies.
`To give a concrete example, a device sending a 2K file may
`find forty matching references scattered across its compres-
`sion history, each reference matching a different 50 bytes of
`the file. This may require 40 separate iterations of a poten-
`tially complex matching algorithm, and 40 separate disk
`accesses to a compression history. By contrast, if a device
`finds a single matching reference for the entire 2Kfile, only a
`single disk access may be needed. Thusthere is a need for
`systems and methodsfor efficiently creating locating long
`matches between an input stream and a compressionhistory.
`Second, when one device has sequencesin its compression
`history that are not in a corresponding compression history on
`another device, inefficiencies may result. The device may
`replace portions of data streams with references to the
`sequences, and then be forcedto retransmitthe data stream as
`it discovers the other device does not have the referenced
`
`2
`diverge. For example, one device mayrun out of storage and
`be forced to overwrite one or more previously stored portions.
`Or one device may have a disk error or other hardware or
`software glitch which corrupts or removes one or more pre-
`viously stored portions. Thus,
`there exists a need for
`improved systems and methodsfor efficiently synchronizing
`shared compressionhistories.
`Third, in many implementations, compression histories
`and caching only provide benefits if the same data is repeat-
`edly sent between the same two devices. This can be espe-
`cially problematic in situations where twosites, each having
`a cluster of devices, may repeatedly communicate similar
`information, but there is no guarantee the information will
`pass through the samepair of devices. For example, twosites
`may each maintain a cluster of devices to accelerate commu-
`nications betweenthesites. Cluster 1 may contain the devices
`A, B, and C, and cluster 2 may contain the devices X, Y, and
`Z. For example, devices A and Z may each maintain a com-
`pression history of a file sent between A and Z, but the next
`timethefile is requested the request and response maypass
`through devices A and Y. Similarly, the next timethefile is
`requested the request and response may pass through device
`B and device X. One potential solution is to organize the
`device clusters in a hierarchy so that all requests to a given
`cluster, network, or region pass through a gateway device.
`However, this solution may involve additional configuration
`and create network bottlenecks. Thus there exists a need for
`leveraging data previously transmitted between two devices
`to compress data streams transmitted between devices other
`than the original transmitters, without necessarily requiring
`explicit hierarchies.
`
`BRIEF SUMMARY OF THE INVENTION
`
`The present invention is directed towards systems and
`methodsofstoring previously transmitted data and using it to
`reduce bandwidth usage and accelerate future communica-
`tions. By using algorithmsto identify long compression his-
`tory matches, a network device may improve comp