DIPLOMOVA PR¶ ACE¶

Univerzita Karlova v PrazeMatematicko-fyzikalnı fakulta

DIPLOMOVA PRACE

Zdenek Siblık

Compressing Proxy

Katedra softwaroveho inzenyrstvı

Vedoucı diplomove prace: RNDr. Vaclav Petrıcek

Studijnı program: INFORMATIKA, Softwarove systemy

ii

Dekuji predevsım vedoucımu sve diplomove prace Vaclavu Petrıckovi za trpelivost, odbornerady a cenne pripomınky, ktere mi velice pomohly pri realizaci teto prace.

Dale bych chtel podekovat Janu Redlovi z Czech On Line za prıstup k informacım o provozucache serveru, zapujcenı serveru pro testovanı a umoznenı srovnavacıho testovanı akceleratoru,a v neposlednı rade za jeho cenne pripomınky k prubehu testovanı.

Prohlasuji, ze jsem svou diplomovou praci napsal samostatne a vyhradne s pouzitım cito-vanych pramenu. Souhlasım se zapujcovanım prace. Obsah prilozeneho CD je volne siritelny.

V Praze dne 19.8.2005 Zdenek Siblık

Contents

1 INTRODUCTION 11.1 Internet and Client-Server networks . . . . . . . . . . . . . . . . . . . . . . . 11.2 Internet Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2.1 Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2.2 Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2.3 Accelerators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3 Thesis structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 BACKGROUND 62.1 World Wide Web and HTTP protocol . . . . . . . . . . . . . . . . . . . . . . 6

2.1.1 Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.1.2 Proxy servers and caching in HTTP . . . . . . . . . . . . . . . . . . . 82.1.3 Access Authentication . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.1.4 Digest Access Authentication Scheme . . . . . . . . . . . . . . . . . . 102.1.5 Content negotiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2 Proxies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2.1 User agent configuration . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2.2 Proxy categories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.3.1 Cache hierarchies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.3.2 Web caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.3.3 Cache effectiveness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.3.4 Cache and privacy protection . . . . . . . . . . . . . . . . . . . . . . . 15

2.4 Accelerators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.4.1 Acceleration of Internet connection . . . . . . . . . . . . . . . . . . . . 162.4.2 Accelerator Categories . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.4.3 Accelerators - Proxy servers . . . . . . . . . . . . . . . . . . . . . . . . 192.4.4 Accelerators - Pair of proxy servers . . . . . . . . . . . . . . . . . . . . 192.4.5 Measurement of connection acceleration . . . . . . . . . . . . . . . . . 21

2.5 General methods and practices in acceleration of Internet connection . . . . . 222.5.1 Data redundancy eliminating methods . . . . . . . . . . . . . . . . . . 222.5.2 Methods eliminating unwanted data . . . . . . . . . . . . . . . . . . . 252.5.3 Methods based on caching . . . . . . . . . . . . . . . . . . . . . . . . . 262.5.4 Methods based on tuning parameters of protocols used . . . . . . . . . 262.5.5 The most demanded or priority data predicting methods . . . . . . . . 29

2.6 Methods of application protocol’s acceleration . . . . . . . . . . . . . . . . . . 30

iii

CONTENTS iv

2.6.1 DNS protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.6.2 HTTP protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.6.3 Other application protocols . . . . . . . . . . . . . . . . . . . . . . . . 34

2.7 Compression methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.7.1 LZ77 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.7.2 ZLIB, GZIP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.7.3 LZ78, LZW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3 AVAILABLE SOLUTIONS 373.1 Review of contemporary accelerators . . . . . . . . . . . . . . . . . . . . . . . 37

3.1.1 Accelerators - Proxy servers . . . . . . . . . . . . . . . . . . . . . . . . 373.1.2 Accelerators - Pair of proxy servers . . . . . . . . . . . . . . . . . . . . 43

3.2 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4 DESIGN AND IMPLEMENTATION 514.1 Objectives and decisions made during the design phase . . . . . . . . . . . . . 51

4.1.1 Target accelerator’s architecture . . . . . . . . . . . . . . . . . . . . . 514.1.2 To start implementation from scratch or not to start . . . . . . . . . . 524.1.3 Why we choose a stable version of Squid as a base . . . . . . . . . . . 52

4.2 Squid Web Proxy Cache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.2.1 Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.2.2 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.2.3 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.3 Squeeze Web Accelerator design and architecture . . . . . . . . . . . . . . . . 574.3.1 Acceleration methods used . . . . . . . . . . . . . . . . . . . . . . . . 574.3.2 Squeeze Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.3.3 Squeeze Database . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654.3.4 Squeeze Graphical User Interface . . . . . . . . . . . . . . . . . . . . . 66

4.4 Squeeze Web Accelerator implementation . . . . . . . . . . . . . . . . . . . . 664.4.1 Libraries used . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664.4.2 Squeeze Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664.4.3 Squeeze Database . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674.4.4 Squeeze Graphical User Interface . . . . . . . . . . . . . . . . . . . . . 674.4.5 Squeeze compatible user agents . . . . . . . . . . . . . . . . . . . . . . 68

4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

5 RESULTS AND DISCUSSION 695.1 Performance tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.1.1 Test hardware and software . . . . . . . . . . . . . . . . . . . . . . . . 695.1.2 Performance Test Scenario . . . . . . . . . . . . . . . . . . . . . . . . 705.1.3 Accelerator settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705.1.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.2 Comparative test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735.2.1 Test hardware and software . . . . . . . . . . . . . . . . . . . . . . . . 735.2.2 Test scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735.2.3 Accelerator settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735.2.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

CONTENTS v

6 CONCLUSION 79

A Glossary 81A.1 Base terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81A.2 Base-derived terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82A.3 Cache-topology terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83A.4 Accelerators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

B What can affect performance of Web Accelerator 85B.1 Modems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

B.1.1 Modem compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85B.2 Anonymous proxy servers, firewalls . . . . . . . . . . . . . . . . . . . . . . . . 86B.3 Browsers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

B.3.1 HTTP protocol compatibility and Encoding support . . . . . . . . . . 86B.4 Origin Servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87B.5 Data nature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

C Squeeze Performance Graphs 89C.1 Performance Test 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89C.2 Comparative Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

List of Figures

1.1 Common Internet Services and particular Application layer Internet protocols 3

2.1 An example of HTTP request message requesting an HTML page. . . . . . . 72.2 An example of HTTP response message carrying an HTML page encoded by

deflate algorithm and with chunked transfer encoding applied. . . . . . . . . . 82.3 An example of HTTP request message requesting an HTML page sent through

proxy server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4 An example of HTTP response message returned through a proxy server and

carrying an HTML page encoded by gzip algorithm. . . . . . . . . . . . . . . 92.5 HTTP Basic Access Authentication - A challenge header . . . . . . . . . . . . 102.6 HTTP Basic Access Authentication - A credentials header . . . . . . . . . . . 102.7 Cache hit ratio of loaded Squid analyzed from one week logs . . . . . . . . . . 162.8 Cache byte ratio of loaded Squid analyzed from one week logs . . . . . . . . . 172.9 Accelerator - Proxy server. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.10 Accelerator - Pair of proxy servers. . . . . . . . . . . . . . . . . . . . . . . . . 212.11 LAN - The Typical case of fast network . . . . . . . . . . . . . . . . . . . . . 272.12 WAN - The Typical case of slow network . . . . . . . . . . . . . . . . . . . . 28

3.1 An HTML tag to specify pages for prefetching by GWA. . . . . . . . . . . . . 44

4.1 Example of Squeeze Deployment . . . . . . . . . . . . . . . . . . . . . . . . . 524.2 Squid proxy server high level architecture . . . . . . . . . . . . . . . . . . . . 544.3 Squeeze Web accelerator high level architecture . . . . . . . . . . . . . . . . . 584.4 Squid cache file: internal marker object for varying gif image . . . . . . . . . 604.5 Squid cache file: Squeeze modified (varying) gif image . . . . . . . . . . . . . 614.6 Flow of typical Squeeze request . . . . . . . . . . . . . . . . . . . . . . . . . . 634.7 User authentication to Squeeze Web accelerator from Internet Explorer Web

browser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674.8 Squeeze GUI main page . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684.9 Squeeze GUI page with statistics . . . . . . . . . . . . . . . . . . . . . . . . . 68

C.1 Performance Test 2: The mean CPU utilization, as a percentage, since Squeezewas started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

C.2 Performance Test 2: The total number of objects currently in the cache . . . 89C.3 Performance Test 2: The amount of memory (in kilobytes) currently used to

store in-memory objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

vi

LIST OF FIGURES vii

C.4 Performance Test 2: The amount of disk space (in kilobytes) currently used tostore on-disk objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

C.5 Performance Test 2: The amount of network traffic (in kilobytes) read fromcache clients and written to cache clients . . . . . . . . . . . . . . . . . . . . . 90

C.6 Performance Test 2: The amount of network traffic (in kilobytes) read fromorigin servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

C.7 Performance Test 2: The amount of network traffic (in kilobytes) written toorigin servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

C.8 Performance Test 2: The number of client requests that were cache hits vs.the total number of HTTP requests received from cache clients . . . . . . . . 90

C.9 Performance Test 2: The number of requests forwarded to origin servers . . . 90C.10 Performance Test 2: Squeeze’s cache hit ratio (percentage) over the last 5 minutes 90C.11 Performance Test 2: The number of MySQL queries per second multiplied by

1000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91C.12 Comparative Test: The mean CPU utilization, as a percentage, since Squeeze

was started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92C.13 Comparative Test: The total number of objects currently in the cache . . . . 92C.14 Comparative Test: The amount of memory (in kilobytes) currently used to

store in-memory objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92C.15 Comparative Test: The amount of disk space (in kilobytes) currently used to

store on-disk objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92C.16 Comparative Test: The amount of network traffic (in kilobytes) read from

cache clients and written to cache clients . . . . . . . . . . . . . . . . . . . . . 92C.17 Comparative Test: The amount of network traffic (in kilobytes) read from

origin servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92C.18 Comparative Test: The amount of network traffic (in kilobytes) written to

origin servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93C.19 Comparative Test: The number of client requests that were cache hits vs. the

total number of HTTP requests received from cache clients . . . . . . . . . . 93C.20 Comparative Test: The number of requests forwarded to origin servers . . . . 93C.21 Comparative Test: Squeeze’s cache hit ratio (percentage) over the last 5 minutes 93C.22 Comparative Test: Squeeze’s cache byte hit ratio (percentage) over the last 5

minutes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93C.23 Comparative Test: The number of MySQL queries per second multiplied by 1000 93

List of Tables

1.1 The TCP/IP protocol suite in the layered OSI-model . . . . . . . . . . . . . . 21.2 Growth of popularity of Google Web search engine, see [44] . . . . . . . . . . 3

3.1 Comparison of accelerators from Accelerators - Proxy servers category . . . . 423.2 Comparison of accelerators from Accelerators - Pair of Proxy servers category 49

5.1 Performance tests - client setup . . . . . . . . . . . . . . . . . . . . . . . . . . 695.2 Performance tests - Squeeze server setup . . . . . . . . . . . . . . . . . . . . . 705.3 Performance Test 1: Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . 705.4 Performance Test 2: Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . 715.5 Performance tests - Squeeze accelerator server settings . . . . . . . . . . . . . 715.6 Performance tests - Squeeze accelerator client settings . . . . . . . . . . . . . 725.7 Performance Test 1: Squeeze accelerator results . . . . . . . . . . . . . . . . . 725.8 Performance Test 2: Squeeze accelerator results . . . . . . . . . . . . . . . . . 725.9 Comparative Test: client setup . . . . . . . . . . . . . . . . . . . . . . . . . . 735.10 Comparative Test: CProxy server setup . . . . . . . . . . . . . . . . . . . . . 735.11 Comparative Test: Test scenario . . . . . . . . . . . . . . . . . . . . . . . . . 745.12 Comparative Test: Squeeze accelerator client settings . . . . . . . . . . . . . . 745.13 Comparative Test: Cproxy accelerator client settings . . . . . . . . . . . . . . 745.14 Comparative Test: Wget test tool settings . . . . . . . . . . . . . . . . . . . . 755.15 Comparative Test: CProxy accelerator results . . . . . . . . . . . . . . . . . . 765.16 Comparative Test: Squeeze accelerator results . . . . . . . . . . . . . . . . . . 775.17 Comparative Test: Structure of HTTP object types downloaded from Internet

by Squeeze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

B.1 Browsers capabilities and compatibility with accelerators. . . . . . . . . . . . 87

viii

Title: Compressing ProxyAuthor: Zdenek SiblıkDepartment: Department of Software EngineeringSupervisor: RNDr. Vaclav PetrıcekSupervisor’s e-mail address: [email protected]: In this thesis we present an overview of the methods used in connection accelera-tors.We compare existing connection accelerators with the special focus on compressing proxyservers.We find that there is an open-source implementation missing that would be comparable tocommercial accelerators.We describe our design and implementation of Squeeze - a connection accelerator based onpopular Squid proxy server.We perform performance tests of our implementation and compare it to a commercial accel-erator. The results show that our implementation is stable and delivers significant savingsunder real world scenarios.Keywords: connection accelerator, proxy server, compression, caching, filtering

Nazev prace: Compressing ProxyAutor: Zdenek SiblıkKatedra: Katedra Softwaroveho InzenyrstvıVedoucı diplomove prace: RNDr. Vaclav PetrıcekE-mail vedoucıho: [email protected]: V teto praci prinasıme prehled metod pouzıvanych akceleratory pripojenı.Porovnavame existujıcı akceleratory pripojenı, zamerujeme se na kompresnı proxy servery.Shledavame, ze chybı alternativa v podobe open-source akceleratoru srovnatelneho s komercnımiakceleratory.Popisujeme navrh a implementaci Squeeze - akceleratoru pripojenı jako rozsırenı popularnıhoSquid proxy serveru.Provadıme zatezove testy implementovaneho resenı a srovnavame ho s komercnım akceleratorem.Vysledky ukazujı, ze nase implementace je stabilnı a prinası vyznamne uspory v beznemprovozu.Klıcova slova: akcelerator pripojenı, proxy server, komprese, kesovanı, filtrovanı.

Chapter 1

INTRODUCTION

This chapter provides the reader with information about evolution of the Internet and thespecific terminology.

1.1 Internet and Client-Server networks

During the last 30 years, data communication (or networking) has become a fundamentalpart of computing. At the beginning efforts of individual hobbyists and scientists to inter-connect their personal computers enabled sharing data over large distances. Originally, onlylocal area networks had existed but over the years they expanded to wide area networks andmetropolitan networks. In the beginning, the majority of computer networks were temporaryconnected through modems. With the growth of networking popularity they soon changedto fixed networks. The Internet has evolved.Internet as a method of interconnecting physical networks covers a set of conventions for us-ing networks that allow the computers or devices to interact. Because of the diversity of theoriginal physical networks it was necessary to define and use many standards (protocols). Thestandards specify the details of how computers communicate, as well as a set of conventionsfor interconnecting networks and routing traffic. The most important set of such standardsis the TCP/IP protocol suite (also called the Internet protocol suite).More about TCP/IP and Internet history can be found in [24] or [7].When we attempt to compare Internet network architecture by functional relationship we canlook at the Internet like at a universe in which there occurs communication between devicesrepresenting Internet Services (servers) and their users (clients). See figure 1.1.Clients and servers use a number of different communication protocols to exchange informa-tion. These protocols are built on top TCP/IP and comprise the majority of all the Internettraffic today. A short summary of them can be found in the table 1.1.It has to be noted that Internet is not only a client-server world. A few years ago peer-to-peerapplication and systems became very popular. In these systems, clients share files and otherresources (e.g. CPU cycles) directly with each other. Servers in peer-to-peer realm (e.g. Nap-ster, Gnutella) usually act only as a directory and serve the needed connection information sothat two clients (peers) can communicate directly. Often a property of being either a clientor a server in peer-to-peer network are both characteristic of the same device.Besides client-server and peer-to-peer networks there are also multi-tier architecture networks.This thesis will discuss neither peer-to-peer networks nor multi-tier architecture networks; its

1

CHAPTER 1. INTRODUCTION 2

Table 1.1: The TCP/IP protocol suite in the layered OSI-modelOSI-model layer TCP/IP protocolsApplication e.g. HTTP, SMTP, SNMP, FTP, Telnet, SSH and Scp,

NFS, RTSPPresentation e.g. XDR, ASN.1, SMB, AFPSession e.g. TLS, SSH, ISO 8327 / CCITT X.225, RPC,

NetBIOS, ASPTransport e.g. TCP, UDP, RTP, SCTP, SPX, ATPNetwork e.g. IP, ICMP, IGMP, X.25, CLNP, ARP, RARP,

BGP, OSPF, RIP, IPX, DDPData link e.g. Ethernet, Token ring, PPP, HDLC, Frame relay,

ISDN, ATM, 802.11 WiFi, FDDIPhysical e.g. electricity, radio, laser

focus is on the native client-server realm.

1.2 Internet Services

1.2.1 Evolution

When the Internet had arisen, numerous Internet Services such as Electronic mail or Filetransport ([25]) appeared. Soon the File transport became the most popular Internet service.Over the time as the Internet spread into public everyday life the World Wide Web InternetService (or shortly Web) appeared and has become the number one in Internet today1.Common Internet services can be seen on 1.1 figure.Nowadays, world-wide Internet networks allow people to share, get or find information throughany of the various Internet services. Internet has enabled a sudden and extreme decentraliza-tion of information and data. It has quickly become a common media for current member ofmodern society.

With the fast-growing popularity of Internet (Internet Services respectively) there ap-peared various issues which needed to be solved but which had not been anticipated in thebeginnings of Internet.We introduce some of them in the subsequent paragraphs.

1.2.2 Issues

Excessive popularity

Some Internet Services started to be so popular that the acting servers were unable to fulfillincoming client requests due to permanent overloading.Administrators have to fall back on data replication, load balancing or caching practices tomake Internet Service’s servers less overloaded and more accessible. Where the load lowering

1According to Merit’s measurements from the NSFNet, [30], HTTP transport protocol specially designedfor the Web replaced FTP File transport’s transport protocol as the dominant transport protocol in April of1995.


Internet

Domain Name System

World Wide Web

File Transport

Electronic Mail

Secure Remote Login

client of some Internet

Service

DNS

HTTP, HTTPS

FTP, SCP

SMTP, POP, IMAP

SSH

News

NNTP

Time Synchronization

NTP

Figure 1.1: Common Internet Services and particular Application layer Internet protocols

practices were not sufficient enough, complex distributed systems for big data processing weredesigned and deployed.Good example of an extremely popular and loaded Internet Service is the World Wide WebGoogle portal purveying today’s Google Web search engine that is the most favourite searchengine today. See table 1.2. In Google Systems Labs the Google Cluster Architecture ([45])has been designed specifically for the purpose of making this Internet Service available andefficient enough.

Table 1.2: Growth of popularity of Google Web search engine, see [44]date # of search queries per day1998 (August-December) 10,0001999 (February-June) 500,0001999 (August-December) 3,000,0002000 (May-June) 18,000,0002000 (November-December) 60,000,0002001 (January-February) 100,000,0002005 over 200,000,000

Increased popularity of an Internet Service can be seen as traffic on backbone networksover which the Internet Service is accessible from the Internet. For that reason excessivepopularity of Internet Service can produce performance problems on backbone networks or


even be a cause of a network congestion.

Slow Internet connection issue

Bandwidth demands for the Internet are growing at an exponential rate and quickly saturat-ing the Internet capacity due to the pervasive use of World Wide Web or FTP applications.An Internet connection of consumer device to ISP’s network is an Internet bottle neck and isbecoming more and more narrow every day.Generally, Internet connection speed can be divided into two categories: dial-up and broad-band. Dial-up connection require the use of a phone line. Broadband connections can beeither ISDN, wireless, cable, DSL, Satellite or Etherned.Technological issues limit the Internet connection speeds for dial-up to relatively slow con-nection speed of 56 kbps. The limits of the ISDN technology are set slightly higher - 64 kbpsor 128 kbps when two lines are aggregated together. The connection speed of mobile devicesover GPRS technology is usually even lower than in both previous cases.The size of transferred objects is permanently growing. The objects being sent between In-ternet Services and their clients are bigger than they used to be in the dawn of the Internet.This is because of increasing popularity of Internet Services and because of the fact that thedata transferred is no more only text based but often image or multimedia-based data.As the volume of transferred data is rising the technologies used earlier are becoming rela-tively slow or even unfit for the use.Whereas a common Web site consisted of a few HTML files and images a few years ago, todaya Web site with hundreds or thousands of HTML files (static or dynamic), images, JavaScriptfiles, CSS files and other is no exception. Nobody is even surprised when the data transferredthrough the Web are as big as tens of megabytes.All the reasons above make the users and ISPs to scramble for new and faster broadbandtechnologies2 like ADSL, EDGE, CDMA2000, etc.Because many mobile devices (PDAs, SmartPhones) equipped with slow connection tech-nologies (GSM, GPRS, Bluetooth) have appeared on the market the slow Internet connectionissue is more important at the moment. Possibilities how to improve parameters affectingconnection speed on such devices are usually limited compared to the ones on personal com-puters.

Higher demands of Internet consumers issue

As the use of Internet spread from academic sphere to public, higher demands regarding par-ticularly Internet Service’s reliability and accessibility appeared. Not every Internet consumeris ready to wait for the Service. Consumer’s demands make ISPs to deploy new technologiesand to use common practices3 helping them to improve services permanently.

User agent and server compatibility issue

As the use of Internet Services growths, the spectrum of usable user-agent programs is in-creasing. But not all current user agents interpret data from Internet Service’s server thesame way. Many of the user agents or servers even violate existing protocols. It is usually

2See ”Broadband passes dial-up in U.S.” article by Eric Auchard onhttp://www.msnbc.msn.com/id/5750968/.

3Caching, content adaptation, load-balancing, geographically distributed backup, etc.


caused by the non-existence of proper standards or relaxed implementation of standards bytheir authors.Consequently, the authors of Internet Service’s servers have to take in account various buggyimplemented user agents and the analogous troubles must be solved by authors of user agents.

Advertisement and unwanted content flooding issue

Because the Internet became a mass medium it is a welcome means frequently used by ad-vertising companies to spread their advertisement.In Electronic mail service the spreading of advertisement went far beyond the acceptablebounds. Now the volume of promotional and spam messages, transferred through the world’smail services, has predominated the volume of relevant messages. And because today’s spamfilters4 are not able enough to filter out unwanted messages it is possible that relevant mes-sages selection will be used instead of spam filtering in the future.Throughout the Web we can encounter advertisement of many shapes, ranging from simpleimage banners up to multimedia content embedded into HTML pages.Internet advertising is one of the cheapest way of how to do promotion today and that’s whywe will often encounter this phenomenon in the future.

1.2.3 Accelerators

The issues outlined in the paragraphs above can be directly or indirectly solved or mitigatedby deploying an appropriate connection accelerator.The aim of this thesis is to inform in more detail about methods used by contemporary ac-celerators to make the most of the Internet connection. We will focus on accelerators fromthe compressing proxy servers category.Finally, because the World Wide Web is the most used Internet Service today, we will focuson it and its application protocol HTTP.

1.3 Thesis structure

In the first chapter we presented the motivation for the use of connection accelerators.In the chapter 2, we provide the needed terminology and information about the methods andpractices used by connection accelerators.The chapter 3 presents an overview of available commercial accelerators.In the chapter 4, we describe our design and implementation of Squeeze - a connection accel-erator based on popular Squid proxy server.Chapter 5 provides the testing methodology and discusses the results obtained.In the final chapter 6, we conclude and propose the possibilities of the future work.

4Programs or part of programs designed for the purpose of filtering spam and unwanted e-mail messages.

Chapter 2

BACKGROUND

This chapter provides the reader with the needed terminology and the information about themethods and practices of connection acceleration.

2.1 World Wide Web and HTTP protocol

World Wide Web is today the most popular Internet Service. It is based on three standards:The Uniform Resource Locator (URL), which specifies how each page of information is givena unique ”address” at which it can be found; Hyper Text Transfer Protocol (HTTP), a Websupporting protocol that will be discussed in this section; Hyper Text Markup Language(HTML), a method of encoding of information so that it can be displayed on a variety ofdevices1.The Hypertext Transfer Protocol (HTTP) is an application-level protocol for distributed,collaborative, hypermedia2 information systems.The first version of HTTP, referred to as HTTP/0.9, was a simple protocol for raw datatransfers across the Internet. The next version of the protocol was HTTP/1.0, defined byRFC 1945, was improved and allowed messages to be in format of MIME-like messages,containing metainformation about the data transferred and modifiers on the request/responsesemantics. Because of the proliferation of incompletely-implemented applications self-claimingto be HTTP/1.0 compatible a protocol change has necessitated so that the two communicatingapplication be able to determine each other’s true capabilities. It lead to the issuance of RFC2068 defining the HTTP/1.1 version of protocol in January 1997. In June of 1999, an updateof the protocol in RFC 2616 [2] was published.This version of the protocol includes more stringent requirements than previous in order toensure reliable implementation of its features. Persistent connections, range requests, datacompression are some of the new features in HTTP/1.1. A whole section 13 of the documentis devoted to caching.The complexity of HTTP protocol makes it hard to be fully implementable.

1A few years ago this standard was re-formulated using an XML Markup Language and named XHTML.2Hypermedia is a term used as a logical extension of the term hypertext, in which an audio, a video, a plain

text, and non-linear hyperlinks intertwine to create a generally non-linear medium of information. More seee.g. [24]

6

CHAPTER 2. BACKGROUND 7

2.1.1 Principles

A Hypertext Transfer Protocol (HTTP) is used for communication of a client and a Webserver. HTTP is a general stateless protocol and works on the principle of sending requestsand receiving response.

In more detail the typical request and response can look as follows:At first a client determines IP address of the server querying DNS server (if it already hasn’tit).Then a client initiates a TCP connection to the server or if already a such connection existsit uses it.Then, a client sends to a request message to a server consisting of a request line, followed bysome of general, request and entity headers and optional entity-body. Request line consistsof a method, a request-URI3 and a protocol version used.A method token in request line indicated the method to be performed on the resource identifiedby the request URI. The methods most used are as follows:

• GET - retrieve an entity identified by request-URI.

• POST - requests the origin server to accept the entity enclosed as a new subordinate ofthe resource identified by the request-URI in the request line. Used in connection withHTML forms.

• HEAD - is identical to GET method, but must not return a message body in response.This method can be used for obtaining metainformation about the entity without trans-ferring entity body itself. This method is often used for testing hypertext links forvalidity, accessibility, and recent modifications.

• CONNECT - is used by proxies to switch themselves to being a tunnel.

GET / HTTP/1.1

Host: www.mff.cuni.cz

User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7) Gecko/20040803 Firefox/0.9.3

Accept: text/xml,application/xml,application/xhtml+xml,text/html;q=0.9,text/plain;q=0.8,image/png,*/*;q=0.5

Accept-Language: cs,en;q=0.5

Accept-Encoding: gzip,deflate Accept-Charset:

ISO-8859-1,utf-8;q=0.7,*;q=0.7

Keep-Alive: 300

Connection: keep-alive

Figure 2.1: An example of HTTP request message requesting an HTML page.

After receiving and interpreting a request message, a server responds with a responsemessage consisting of a status line followed by some of general, response and entity headersand optional body holding an entity. Status line consists of protocol version, status code(signalizing how the method performed) and the reason phrase (saying the same in textualmanner).The request headers allow the client to pass additional information about the request4, and

3URI stands for the Uniform Resource Identifier and identifies a resource by name or location or both.More about URI can be found in [3].

4For example a host where an entity should be located.


about the client itself5, to the server. These fields act as request modifiers, with semanticsequivalent to the parameters on a programming language method invocation.The response headers allow the server to pass an additional information about the responsewhich cannot be placed in the status line. These header fields give an information about theserver6 and about further access to the resource identified by the request-URI7.Entity headers define metainformation8 about the entity-body or, if no body is present, aboutthe resource identified by the request.After receiving a whole response the client close the connection or keep it alive for a sometime when a Keep-Alive header is present.

HTTP/1.1 200 OK

Date: Wed, 20 Jul 2005 16:02:27 GMT

Server: Apache/1.3.33 (Unix) mod_ssl/2.8.22 OpenSSL/0.9.7e CSacek/2.1.9 PHP/4.3.11

Vary: Accept-Encoding,Accept-Charset,Accept-Language,User-Agent

X-Powered-By: PHP/4.3.11

Keep-Alive: timeout=15, max=99

Connection: Keep-Alive

Transfer-Encoding: chunked

Content-Type: text/html; charset=utf-8

Content-Encoding: deflate

...[entity body data]...

Figure 2.2: An example of HTTP response message carrying an HTML page encoded bydeflate algorithm and with chunked transfer encoding applied.

Although the HTTP was designed to be base protocol for World Wide Web, it is defactoa platform over it many other upper protocols are defined today, such as SOAP, etc.

HTTP is also used as a generic protocol for communication between user agents andproxies/gateways to other Internet systems, including those supported by the SMTP, NNTP,FTP, Gopher, and WAIS protocol.

2.1.2 Proxy servers and caching in HTTP

In the classic client-server model of communication a client sends its request directly to anorigin server.There is an alternative to this approach involving a proxy server as the intermediary.An example of an HTTP request message requesting an HTML page through proxy servercan be seen on the figure 2.3. Above all, note the different format of the request line incomparison to the request message sent directly to the origin server as shown on the figure2.1.

A proxy server is typically used for caching or network protection purposes.The caching proxy server requests on a client behalf a data from origin server and store its

5What content types are accepted by the client, a client identification string or if client understands to thetransfer encoding, etc.

6Server identification string7For example an entity tag that should uniquely identify the entity, vary headers signalizing that server is

returning variants of the entity (holding names of headers used for determining the most appropriate variant)or the age of the entity

8For example the information about encoding, type, length, expiration time or time of the last modificationof the entity.


GET http://www.mff.cuni.cz/ HTTP/1.1

Host: www.mff.cuni.cz

User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; cs-CZ; rv:1.7.8) Gecko/20050511 Firefox/1.0.4

Accept: text/xml,application/xml,application/xhtml+xml,text/html;q=0.9,text/plain;q=0.8,image/png,*/*;q=0.5

Accept-Language: cs,en;q=0.7,en-us;q=0.3

Accept-Encoding: gzip,deflate

Accept-Charset: windows-1250,utf-8;q=0.7,*;q=0.7

Keep-Alive: 300

Proxy-Connection: keep-alive

Proxy-Authorization: Basic dGVzdDp0ZXN0

Figure 2.3: An example of HTTP request message requesting an HTML page sent throughproxy server

HTTP/1.0 200 OK

Date: Sat, 23 Jul 2005 21:30:03 GMT

Server: Apache/1.3.33 (Unix) mod_ssl/2.8.22 OpenSSL/0.9.7e CSacek/2.1.9 PHP/4.3.11

Content-Length: 3628

Vary: Accept-Encoding,Accept-Charset,Accept-Language,User-Agent

X-Powered-By: PHP/4.3.11

Content-Type: text/html; charset=utf-8

Content-Encoding: gzip

X-Cache: MISS from urtax.ms.mff.cuni.cz

Proxy-Connection: keep-alive

...[entity body data]...

Figure 2.4: An example of HTTP response message returned through a proxy server andcarrying an HTML page encoded by gzip algorithm.

copy inside itself in addition to deliver response to a requesting client. From this moment thestored copy can be used by the caching proxy when processing subsequent requests for thesame data. Because the stored copy is better accessible a caching proxy can return a datamore quickly. In addition to lowering an access time to the data a caching proxy reduce avolume of transferred data between internal network9 and origin server.See more about proxy servers in section 2.2. Caching of HTTP data will be discussed insubsection 2.3.2.

2.1.3 Access Authentication

Access authentication is the mechanism how a client identifies itself to the remote origin serveror proxy server when they challenge it.Access authentication is optional in HTTP. The general framework for access authentication,and the specification of basic and digest authentication, are specified in [4].

Basic Access Authentication

The basic access authentication was specified in HTTP/1.0 protocol ([1]) and is based onthe model that the client must authenticate itself with a user-ID and a password for eachrealm. The realm value should be considered an opaque string which can only be comparedfor equality with other realms on that server (origin or proxy). The server will service the

9Inside of it the caching proxy is deployed.


request only if it can validate the user-ID and password for the protection space of the request-URI. There are no optional authentication parameters. It is not consider to be secure method

Proxy-Authenticate: Basic realm="Squeeze Web Accelerator"

Figure 2.5: HTTP Basic Access Authentication - A challenge header

of user authentication, as the user credentials10 are passed over the network in an unencryptedform.Upon receipt of an unauthorized request for a URI within the protection space, the proxyserver may respond with a challenge by including HTTP header like on the figure 2.5, where”Squeeze Web Accelerator” is the string assigned by the server to identify the protectionspace of the request-URI. An origin server may respond with the same challenge but usingthe WWW-Authenticate header field.

Proxy-Authorization: Basic dGVzdDp0ZXN0

Figure 2.6: HTTP Basic Access Authentication - A credentials header

To receive authorization, the client sends the user-ID and password, separated by a singlecolon character, within a base64 encoded string in the credentials11. The HTTP headerincluded in credentials for proxy server may look like on the figure 2.6. When credentials aresent as a response to origin server challenge the HTTP Authorization header is used insteadof Proxy-Authorization header.

2.1.4 Digest Access Authentication Scheme

The Digest Access Authentication scheme is not intended to be a complete answer to theneed for security in the World Wide Web. It does not provide encryption of message content.The scheme was designed in order to create and access authentication method that avoidsthe most serious flaws of Basic authentication.As the Basic Access Authentication, the Digest scheme is based on a simple challenge-responseparadigm. The Digest scheme challenges using a nonce value. A valid response contains achecksum (by default, the MD5 checksum) of the username, the password, the given noncevalue, the HTTP method, and the requested URI. In this way, the password is never sent inthe clear.

2.1.5 Content negotiation

Content Negotiation is a mechanism that makes it possible to serve different versions of aresource (object) at the same URL, so user agents get the version that is best suiting them.There are two kinds of content negotiation in HTTP, differed in the place where the objectvariant selection algorithm is located. Both are orthogonal so may be used separately or incombination.

10The user-ID and password.11In the example presented on the figure 2.6 the client identifies itself by the same user-ID and password -

“test”


Server-driven Negotiation

In this case the selection algorithm is located on server and is based on the available represen-tations of the response (the dimensions over which it can vary; e.g. language, content-coding,etc.) and the contents of particular header fields in the request message or on other informa-tion connected with the request (such as the network address of the client).Server-driven negotiation is used when the algorithm for selecting from among the availablerepresentations is difficult to describe to the user agent, or when the server desires to send its“best guess” to the client along with the first response (hoping to avoid the round-trip delayof a subsequent request if the “best guess” is good enough for the user).In order to improve the server’s guess, the user agent may include request header fields (Ac-cept, Accept-Language, Accept-Encoding, etc.) which describe its preferences for such aresponse.The Vary header field can be used by the server to express the parameters used to select arepresentation that is subject to server-driven negotiation.

Agent-driven Negotiation

With agent-driven negotiation, selection of the best representation for a response is performedby the user agent after receiving an initial response from the origin server. Selection is basedon a list of the available representations of the response included within the header fields orentity-body of the initial response, with each representation identified by its own URI.Selection from among the representations may be performed automatically (if the user agentis capable of doing so) or manually by the user selecting from a generated menu.Agent-driven negotiation is advantageous when the response would vary over commonly-used dimensions (such as type, language, or encoding), when the origin server is unable todetermine a user agent’s capabilities from examining the request, and generally when publiccaches are used to distribute server load and reduce network usage.

Transparent Negotiation

Transparent negotiation is a combination of both both negotiations. When a cache is sup-plied with any form of the list of available representations of the response (as in agent-drivennegotiation) and the dimensions of variance are completely understood by the cache, then thecache becomes capable of performing server-driven negotiation on behalf of the origin serverfor subsequent requests on that resource.Transparent negotiation has the advantage of distributing the negotiation work that wouldotherwise be required of the origin server and also removing the second request delay of agent-driven negotiation when the cache is able to correctly guess the right response.

Now it is the right time to set up needed terminology. In the following sections can befound some fundamental information about proxies, caches, and accelerators. The generalterminology used in scope of this thesis can be found in appendix, in chapter A.Feel free to skip to Accelerator section of this chapter.


2.2 Proxies

Much of this thesis is about proxies. A proxy is an intermediary in a networking transactionbetween the client and the server.Proxies are mainly used for caching and network protection purposes.

2.2.1 User agent configuration

Usually the client (user agent) has to be configured to send its requests through the proxy.The way how to do that is any as follows:

• A manual proxy configuration made by user assigning proxy address and port for anyproxyable protocols.Usually, a single proxy supports all of these, so the same proxy address is used for allprotocols. Some clients allow you to set a single proxy address rather than requiringyou to enter the same address repeatedly.

• The proxy auto-configuration (PAC) technique. It was invented by Netscape. Insteadof using static proxy addresses, the browser executes a function for every request. Thisfunction returns a list of proxy addresses that the browser tries until the request issuccessfully forwarded. The PAC function is written in JavaScript.In theory, any browser that supports JavaScript can also support PAC. Browsers usuallyretrieve the PAC script as a URL. This is perhaps the biggest drawback to proxy auto-configuration. Setting the PAC URL requires someone to enter the URL in a pop-upwindow, or the browser must be preconfigured with the URL.

• Web Proxy Auto-Discovery protocol (WPAD) is designed to let browsers automaticallylearn the auto-configuration URL with no assistance from the user.WPAD uses a number of protocols and services to find the auto-configuration URL. Thepreferred protocol is DHCP (Dynamic Host Configuration Protocol). If DHCP fails, theuser agent may try the Service Location Protocol (SLP12) next. If SLP fails as well, itqueries the DNS for A, SRV, and TXT records.A client that implements WPAD must support at least the DHCP and DNS A recordqueries. Support for SLP is optional.

Where the client configuration is not possible the interception proxying come on the stage.The interception proxying is the mechanism how to bring traffic to proxy without configuringclients. To enable interception proxying internal network routers or switches have to be setto divert traffic through proxies.13

2.2.2 Proxy categories

There are many different types of proxies out there. Depending on the purpose we can getproxy servers to route any of common Internet protocols, and many more.

• FTP proxy server relays and possibly caches FTP traffic.12Defined in RFC 206813It has to be note that routers and switches are supposed to deliver IP packets to their intended destination

according to Internet Protocol standards. This implies that an interception proxying violates the InternetProtocol standards.


• HTTP proxy server enables to send request to retrieve Web pages. It relays and possiblycaches HTTP traffic. This type of proxy is often simply called Web proxy.

• Socks proxy server uses a newer protocol to allow relaying data of different protocols(TCP or UDP based).

• NAT proxy server works a little different, it allows the redirection of all packets withouta program having to support a proxy server.

• SSL proxy server is an extension to HTTP proxy server created for the purpose of securerelaying TCP data similar to a Socks proxy server. It creates en encrypted connectionenabling sending of secure requests and responses.

Further more, a proxy server can be split into another two categories:

• Anonymous proxy server blocks the remote computer from knowing the identity of thecomputer using the proxy server to make requests.

• Transparent proxy server tells the remote computer the IP address of the requestingcomputer. This provides no privacy.

Anonymous proxy servers can further be broken down into two more categories - Elite andDisguised. An Elite proxy server can’t be identified by the remote computer as a proxy in anyway. A Disguised proxy server gives the remote computer enough information to let it knowthat it is a proxy but still does not give away the IP address of the computer it is relayinginformation for.Anonymous proxies are often used on firewalls to provide security. They allow (and optionallyrecord) requests from the internal network to the outside internet.Web proxies can be also used for filtering the content of Web pages served. Some censorwareapplications - which attempt to block offensive Web content - are implemented as Web proxies.Other Web proxies can reformat web pages for a specific purpose or audience.Network operators can deploy proxies to intercept computer viruses and other hostile contentserved from remote Web pages.

2.3 Caches

As a data processing term, caching refers to the storage of recently retrieved computer infor-mation for future reference. The stored information may or may not be used again, so cachesare beneficial only when the cost of storing the information is less than the cost of retrievingor computing the information again.Caching is widely used to alleviate the latency. Computer systems would be much slowerwithout any form of caching, because almost all data processing tasks exhibit locality ofreference and therefore benefit from caching. In addition to that caching is used to reducenetwork traffic.Caches work well because of principle known as locality of reference. There are two flavors oflocality: temporal and spacial. Temporal locality means some pieces of data are more popularthan others. Spatial locality means that requests for certain pieces of data are likely to occurtogether.Cache use locality of reference to predict future cache accesses based on previous ones. When


the prediction is correct, there is a significant performance improvement.There are some basic terms taken from classic literature. The fact that requested data isfound in the cache is called cache hit. Opposite situation is called cache miss. The percentageof all requests that are hits is called hit ratio. The percentage of data volume handled bycache like hits is called byte hit ratio.The performance improvement that a cache provides is based mostly on difference in servicetimes for cache hits and cache misses, on the proportion between hits and misses, and thevolume data they both represent. This improvement can be measured as request-responselatency reduction.

2.3.1 Cache hierarchies

The cache requests for data directly the origin server if any form of the cache miss occurs. Butin some cases it can be more effective to ask for the missed data near located cache insteadof distant origin server.Cache hierarchy is a collection of cooperating caches. The members of the collection are calledneighbors or peers. Neighbor caches have either a parent or sibling relationship. Topologically,parent caches are one level up in the hierarchy, while siblings are on the same level.For a cooperation among caches some protocols such as ICP14 protocol, HTCP protocol15 orCache Digests16 were designed.

2.3.2 Web caching

Web caching is the caching of web objects (HTML pages, images, etc.) in order to reducebandwidth usage and web site access times. A web cache stores copies of cacheable objectsrequested by users. Subsequent requests may be satisfied from the cache if certain conditionsare met.Web caching depends on the caching mechanism introduced in the version HTTP/1.1 of theHTTP protocol (see chapter 13 in [2]). The goal of the Web caching is to eliminate the need tosend HTTP requests in many cases, and to eliminate the need to send full HTTP responses inmany other cases. The former reduces the number of network round-trips required for manyoperations; it is used an expiration mechanism for this purpose. The latter reduces networkbandwidth requirements; it is used validation mechanism for this purpose.The basic cache mechanisms in HTTP (server-specified expiration times and validators) areimplicit directives to caches. Sometimes a server or client might need to explicit instruct thecache. There is the Cache-control header for this purpose. These explicit directives typicallyoverride the default caching mechanism.Cache aware HTTP clients then use HTTP HEAD method or conditional GET requests17 inconjunction with validators to determine whether they need to download the data or can usecache copy of it instead.

14See RFC 2186 and RFC 2187.15See RFC 275616Cache Digests enables caches to interchange lists of objects they are holding. Afterwards the lists can be

used by cache to determine a proper neighbor holding the data it wants.17The request message includes an If-Modified-Since, If-Unmodified-Since, If-Match, If-None-Match, or If-

Range header field.


2.3.3 Cache effectiveness

As was in previous in this section remarked, one possible measurement of cache effectivenessis a cache latency reduction defined precisely in [19].Another possible measurement of cache effectiveness can be done on comparing cache hit andcache byte hit ratios.Three factors affect hit ratios of caches: cache size, number of clients, and freshness heuristics.Obviously, a larger cache holds more objects. The chance that any given request is a cachehit increases as the cache size increases, but the relationship is not linear. The authors of [13]paper suggest it is pseudologarithmic.There was done some measurements regarding the hit ratio and cache latency reduction inrelation to the cache efficiency in the past.

• According to [6], Web caches generally achieve hit rates around 30% - 50% and becomemore effective as the user population increases.

• In contrast a study [19] showed that benefits from client-side caching are very limited dueto the lack of enough temporal locality in Web references. In this study accomplishedtests presented that passive caching is only able to reduce latency from 22%–26% andeven less when less clients participated but the latency reduction from 77% till 88% waspre-estimated. The cache hit ratio ranged from 47%–52% or 19%–28% with less clientsduring the tests. Authors note that the latency reduction from caching is significantlylimited by the rapid changes of objects in the Web and conclude that for the workloadstudied caching offers moderate assistance in reducing latency.

• To maximally benefit from caching the authors of [13] suggest to use 1-level cachehierarchy18 in small client populations (up to 1000 clients), cache hierarchy of 2- ormore level in large client populations (few thousands clients or more).

In obtained data from Czech On Line ISP we observed gains from the Squid cache19 atamount of 38,9% hits from all the request to the cache and 20,5% of the byte traffic from alltransferred data. See the figures 2.7 and 2.8.

2.3.4 Cache and privacy protection

Although the cache usage can have a performance benefits, it is necessary to see its potentialprivacy weakness.One way in which users’ privacy can be compromised is by cache access logs. Most web cachesin operation make a log entry for each and every request received. A typical log entry includesthe time of access, URL requested (maybe provided with valid session string), the requestingclient’s network address, and, in some cases, a username.Thus, many proxies and caches use modules that filters privacy information from the logs, bymodifying or removing the query part of the URL. The responsiveness of cache operators isto protect user’s data from abusing.

18This 1-level cache is located close to clients.19In this case this is a 2-level cache hierarchy.


Figure 2.7: Cache hit ratio of loaded Squid analyzed from one week logs

2.4 Accelerators

Our view on the Internet is restricted to client-server area as was earlier mentioned. Thedevices representing Internet Service’s servers and clients interchange entities (or objects) inorder to communicate.An temporary Internet connection between them have to be established or permanent oneexists for the sake of interchanging the entities.The connection speed influences notably whether the user’s Internet experience is positivelyor rather negatively perceived. Although an upgrade of the Internet with higher bandwidthnetworks has never stopped, users are experiencing access delays more often than ever.Where is not possible to replace the slow connection20 technology for any of technical oreconomical reasons, the some form of connection accelerator may help. Of course, we canalso deploy the accelerator where the fast connection technology is employed and push thespeed even further. After that we can benefit from smaller access delays to Internet Service’sobjects achieved by lowering their redundancy or filtering the unwanted embedded ones.

2.4.1 Acceleration of Internet connection

The Internet connection acceleration is an attempt to improve access times to Internet Ser-vice’s objects.We have to emphasize that the parameters of connection technology stays as they are whenusing the accelerator. The difference is in the way of use the connection resources by theaccelerator. In other words we can only lower the access time to the object if we achievelowering of the amount transferred data through the connection.We demand the value of information contained in objects is fully retained or at least it stays

20The one with high latency and low throughput.


Figure 2.8: Cache byte ratio of loaded Squid analyzed from one week logs

in acceptable bounds21. Apparently the way how to lower the amount of transferred datais to eliminate object’s redundancy22 or optimize access methods not to transfer redundantdata but not violate Internet Service protocol.Redundancy is natural attribute of data. Even though we don’t increase redundancy in ourdata unnecessarily, we use redundant data all the time, mostly without noticing it. Here aresome examples:All natural languages are redundant. A Portuguese who does not speak Italian may read anItalian newspaper and still understand most of the news because he recognizes the basic formof many Italian verbs and nouns and because most of the text he does not understand is su-perfluous (i.e., redundant). HTTP is an acronym for ”Hypertext Transfer Protocol” but youcan often meet with ”HTTP protocol” phrase, PIN is an acronym for ”Personal IdentificationNumber”, but in banks you will be probably asked for your ”PIN number”.If we eliminate unnecessary redundancy we save considerable amount of connection band-width. Successfulness of removing redundancy depends on the nature of data. The datacompression technique is the way how to achieve elimination such redundancy.Other usable methods for bandwidth savings are based on optimizing parameters of the Inter-net protocols and are employed on various network layers (transport layer, application layer,etc.).Particular use of methods can be also influenced by user habits or preferences.A more detailed description all the methods is in 2.5.

21The acceptable bounds can be obviously determined by content producers or content consumers.22Redundancy, in general terms, refers to the quality or state of being redundant, that is: exceeding what is

necessary or normal, containing an excess. [24]


2.4.2 Accelerator Categories

Connection accelerators can be divided into two main categories according to their archi-tecture and also the place of their intentional deployment in client-server network topology.These categories are:

• Accelerators - Proxy servers

• Accelerators - Pair of proxy servers

The main objective of this thesis are the accelerators from the ”Accelerators - Proxyserver” category.

Further we split up them into the subcategories according to the supported (accelerated)application level protocol.

Application protocols categorization

Connection accelerators are usually working at application protocol level because they usethe information about data content type and other data metainformation here available forthe most efficient transformations of this data. Last not least some application protocols,such as HTTP, were designed to directly support some methods of bandwidth savings suchas compression or caching.Although the accelerator can operate without this data content type information (e.g. com-pressing data on a TCP stream on transport layer) the effectiveness of a such accelerationis lesser than in case of employing content type suitable transformations instead of generalpurpose methods.

Considering the application protocols we can categorize accelerators to:

• Web accelerators when they are able to accelerate the HTTP protocol. In this thesiswe focus on such accelerators.

• File transport accelerators if they are able to accelerate the FTP protocol.

• Electronic mail accelerators which can handle acceleration of SMTP, POP or IMAPprotocols.

• SOCKS accelerators when they accelerate SOCKS standard proxy protocol.

Some accelerators are also able to accelerate more application protocols.

Finally, there are application protocols that do not allow acceleration or at least its im-plementation is difficult. As an example we can take the HTTPS protocol (HTTP protocolover SSL), where accelerator deployment can lead to security weakening.In every SSL session, the server must authenticate itself to the client. The threat is thata client may ask for a particular service but the reply to that request may come from animpostor or may be observed by an eavesdropper. To counter the possibility of an impostorserver reply, the server proves its identity to the client. In SSL version 3, the server may alsorequire the client to authenticate himself to the server, a result commonly known as ”mutual


authentication”. SSL performs authentication with public-key cryptography, and protectsconfidentiality and message-integrity with symmetric-key cryptography.When we add a proxy as the intermediary to the communication the problem with end toend authentication emerges.This problem is in most cases solved on proxies by using HTTP CONNECT method, anextension to HTTP that can be used to tunnel HTTPS request through HTTP. Since anHTTPS request is encrypted it is not possible to proxy it. It is therefore not possible to cacherequests or optimize in any way.There is the only possible solution to make such request comprehensible to the proxy - toprovide proxy with server and client certificate for being able authenticate itself to the clientas the server and vice versa. But this is insecure and in general bad solution with manydrawbacks.

2.4.3 Accelerators - Proxy servers

Although the principle of compressing proxy servers is simple and can be almost straightfor-wardly implemented, it offers satisfactory results23. The volume of saved data is affected bythe data nature and the fact that the compression and other transformations can be doneonly in one direction, from the compressing proxy to the client.This is the typical working scenario of Web accelerator - compressing proxy server:

• Client sends a request for an object to the proxy server.

• Proxy server reads and parse the request and determine whether is able to handle it(the requested object can be obtained or derived from its cache store) or the requestwill have to forward to the origin server or cache peer.

• If the proxy server is not able to serve the request then it determine the appropriateorigin server, connects with it and forwards client’s request to it. Origin server possiblyreply and send the asked object to the proxy server.

• Asked object is then in accelerator transformed (compressed, filtered) and possiblycached before it is sent to client.

Use of this accelerator type needs a client support primarily for decompression of com-pressed objects. It other words, the client must comprehend the compressed content whatimplies that on server have to be used a known (standardized) compression algorithm.

The advantage of using the accelerator of this type is that there is not a necessity to installany supporting software. The capable client is sufficient enough. Thus, these accelerators areparticularly advantageous on devices where could be difficult to install the client side, such ason some PDAs or SmartPhones. The only thing to do is to set the user agent to communicatewith the accelerator. Possible ways how to do that are described in 2.2.1.

2.4.4 Accelerators - Pair of proxy servers

These accelerators consists of two proxies, the client proxy and the server proxy. The clientproxy is installed on the user’s device. The server proxy requires better connectivity to In-ternet so it is typically located near backbone network of the ISP.

23The performance measurement results can be found in chapter 5


��

��

��

��

��

��

��

Figure 2.9: Accelerator - Proxy server.

Such accelerator do not need any special support from the client, because all the support isalready implemented in its client side proxy.

At first, we outline the disadvantages of this solution:

• Client proxy has to be implemented in a variant for every of platform used or operatingsystem.

• Client proxy should support automatic upgrades to new versions, because it is almostimpossible to force all the accelerator users reinstall client proxy every time the clientproxy changes.

Among advantages of this solution belong:

• More efficient data redundancy elimination because it is realized on both sides of thecommunication parties (on client and on server) which results in more significant con-nection acceleration.

• These accelerators are free to employ non-standard specialized algorithms of data com-pression that can be more effective than the standard general purpose one.

Client proxy appear to client as the common proxy server but with the exception it is locatedon the same device as the client. The client proxies usually configure well-known clients tobe able use their service or in another case users has to set their client programs by hand.


��

��

��

��

��

��

��

Figure 2.10: Accelerator - Pair of proxy servers.

2.4.5 Measurement of connection acceleration

Connection acceleration can be measured in two ways. The first one is based on a measurementof average access time to objects and another on the volume of transferred data.We have two measures because of the different nature of connection technologies. Whilespend time is counted in some technologies (dial-up, ADSL, cable, etc.) in another ones (e.g.GPRS) the transferred data counts.While in one place may the use of prefetching (see 2.5 help save the access time and acceleratethe connection in other may be use of this method unwanted due to particular nature ofconnection technology.

Measurement of access time

Access time we can define as the time interval between the instant at which a client sendsrequest for the object and the instant at which asked object arrives24. Access time consistsof the transmission time (the time needed by client to send request and receive reply) andthe service time (the time spent by origin server or accelerator to process the request).To be able to measure of connection acceleration we define an Acceleration factor as

Acceleration factor =access time directly through origin server

access time through accelerator. (2.1)

The value of acceleration factor > 1 means acceleration and the value < 1 means deceleration.Regardless two different clients can have the same accelerator’s settings and they will support

24This is also called a Round Trip Time.


all the accelerator transformations equally, an acceleration factor measured may vary. Ithappens whenever transmission times (to the same origin server and to the same accelerator)are different among these clients.

Measurement of transferred data

To measure a gain from the acceleration in this case we want to measure percentage of saveddata.Thus we define Saved data ratio as

Saved data ratio = 1− transferred data through accelerator

transferred data directly from origin server. (2.2)

If we multiple this by 100 we get a percentage of saved data due to accelerator deployment.

2.5 General methods and practices in acceleration of Internetconnection

In this section we will focus on general (an application level protocol independent) methodsof Internet connection acceleration. Without reference to connection technology used thereare some general and differently successful methods how to make the most of the Internetconnections.Instead of the change the connection technology to faster one we want to use available connec-tion resources more effectively, to optimize transmitted data by eliminating their redundancyand to bend their form to our needs.

For transparency we will divide the methods into the following categories:

• Data redundancy eliminating methods

• Methods eliminating unwanted data

• Methods based on caching

• Methods based on tuning parameters of protocols used

• The most demanded or priority data predicting methods

2.5.1 Data redundancy eliminating methods

For data redundancy elimination are used various methods of data compression. Compres-sion methods work on the principle of transforming data from original representation to therepresentation with less redundancy and thus less space demanding. Such transformation iscalled encoding. The inverse transformation is called decoding.Generally data are compressed for the transmission (to avoid transmission redundant data)and afterwards they are successfully transmitted they are decompressed (transformed backto the original representation) for the use.When we are comparing performance of the methods we can use the following measures:

Compression ratio =size of the output stream

size of the input stream. (2.3)


Compression ratio reflect size of the data output stream (compressed data) in comparison tosize of the data input stream (original uncompressed data). If the value is < 1 it means acompression, the value > 1 means expansion. A value 0.6 for example means that the dataoccupies 60% of its original size after compression.

Compression factor =size of the input stream

size of the output stream. (2.4)

Compression factor is the inverse of the compression ratio. In this case values > 1 mean acompression, the values < 1 mean expansion. The bigger the factor, the better the compres-sion.Sometimes, the factor is presented in the form of two figures separated by colon, e.g. ”7:1”,what can be interpreted as the original file (represented by the second figure) was compressedto 7 times smaller file.

Percentage of savings = 100 ∗ (1− Compression ratio). (2.5)

We use this measure to express the savings that we gain by using the compression method. Avalue of 60 means that the output stream occupies 40% of its original size (the compressionhas resulted in savings of 60%)

Generally we can data compression methods split into two categories:

• Lossless compression methods are the methods when the original and the decompresseddata are identical. We use this methods when this behavior is necessary or when noassumption can be made on whether certain deviation is uncritical. These methods aretypically used to compress source code, text data or executable programs.

• Lossy compression methods are in contrast methods achieving better compression bylosing some information. Thus when the compressed stream is decompressed, the resultis not identical to the original data stream. Lossy methods are most often used forcompressing sound or images. In these cases, the retrieved uncompressed data be quitedifferent to the original at the bit level while being indistinguishable to the human earor eye for most practical purposes.

Lossless data compression methods

Lossless compression methods may be categorized according to the type of data they aredesigned to compress. The three main types of targets for compression algorithms are text,images, and sound. Whilst, in principle, any general-purpose25 lossless compression algorithmcan be used on any type of data, many are unable to achieve significant compression on datathat is not of the form that they are designed to deal with. (For example sound data cannotbe compressed well with common text compression algorithms.)

Another possible categorization of Lossless methods ([8]) is based on the general principleshow the method works. Thus we have

25General-purpose means that they can handle all binary input.


• Basic methods compress data by replacing a run length of identical symbols with onecode, or token, containing the symbol and the length of the run. Thus these methodsare sometimes generally called RLE methods (see [8]).Sometimes irreversible text compression (also called compaction) is classified in thiscategory. This method replaces a run of consecutive blank spaces by a single space.But the decompressed text is not identical to the original, so this method can be usedin special cases only. Last not least this method is not lossless.

• Statistical methods are based on statistical model of the data and use variable-sizecodes26, with shorter codes assigned to symbols or groups of symbols that appear moreoften in the data (have a higher probability of occurrence). Decompression is a reverseprocedure to compression in these methods and is done by replacing back codes byoriginal symbols.The most important methods from this category are Huffman Code or Arithmetic Coding(both see [8]).

• Dictionary methods selects strings of symbols and encode each string as a token usinga dictionary. The dictionary holds strings of symbols and it may be static or dynamic(adaptive). The former is permanent, sometimes allowing the addition of strings but nodeletions, whereas the latter holds strings previously found in the input stream, allowingfor additions and deletions of strings as new input is being read.Supposing there already is a dictionary, some word (some string of symbols) have justbeen from input, and the dictionary is searching. If a match is found, an index to thedictionary is written into the output stream. Otherwise, the raw word itself is written.Because the index to directory is in principle shorter than word, we get a compression.The output stream thus contains indexes and raw words and they can be distinguishedfor example by including a bit flag in every item written, denoting that it is.When decompressing the same dictionary is used. As the tokens are read from com-pressed stream we they are probed if they are indexes or raw words. In the first casethe index to dictionary is replaced with respective string stored on that address in dic-tionary. Otherwise the raw word is written itself to the uncompressed stream instead.The most significant methods working on this principle are LZ77 (see [9]) or LZW (see[11]).

• Mixed are using a combination of methods from previous categories.

Many lossless compression methods used today are mixed and are based on a conjunctionof statistical and dictionary methods. An example of such method can be DEFLATE method(implemented by ZLIB library), which is a combination of LZ77 algorithm (Dictionary meth-ods) and Huffman coding (Statistical methods). We will focus on DEFLATE compressionfurther.

Lossy data compression methods

Lossy data compression methods can be divided into the following categories:

• Still image compression is used when compressing photos or static images.26A code is a symbol that stands for another symbol.


• Moving image compression is used when dealing with video data (e.g. movies taken byvideo cameras).

• Sound compression is used dealing with audio data and further can be split into themusic compression and speech compression.

We will focus on the still image compression, to JPEG image compression method further.

The idea of losing data information becomes more acceptable when is considered how digitalstill images are created. During an image is scanned from photograph or from a paintingsome information is loosed as a result of digitizing. This fact suggests that further loss ofinformation might be tolerable if done carefully.

2.5.2 Methods eliminating unwanted data

Content blocking

Content blocking is a mechanism how to prevent or protect consumers from accessing un-wanted data. In addition being an instrument of censorship a content blocking can be theway how to save line bandwidth and thus accelerate the connection.There are generally three types of content blocking depending on who is controlling the con-tent blocking:

• Content blocking driven by content producer (by origin server)

• Content blocking driven by distribution network (by routers, filtering proxy servers,etc.)

• Content blocking driven by consumer (by client)

While first two types works typically as a consumer protecting or preventing mechanism, thelast one is bandwidth saving mechanism so we will focus on it.Not all the data transferred from the origin server to client are required by client. Commoncase of such data are advertising Web objects (images, flash animations, etc.) included withdownloaded data or Electronic’s mail spam.There is an opinion that seeing advertising is a natural form of ”paying” for Internet contentbut when we are looking for data savings the advertisement is on the first place.In principle a content blocking can be done on two levels:

• Blocking at transport protocol layer, packets blocking - this type of blocking can beeasily implemented but offers little comfort. Commonly it is done by searching throughthe block list for a source or target packet address only, because we do not know at thislayer what object is inside a particular packet. If match is found, the packet is blocked.

• Blocking at application protocol layer, messages or object blocking - this type of blockingis more effective as can use the object’s metainformation, such as object content typeor object size, to decide whether the object will be blocked or not.


Content filtering

Difference between content filtering and content blocking is subtle. While content blockingterm is used when speaking about denying access to whole content, content filtering term isused when it is filtered out a part of data only.

Although the content blocking or content filtering always saves data, these methods are oftenproblematic and do not work in all cases because unwanted content may not be determineda priori, e.g. an advertising text object.

Content replacing

Content blocking or content filtering has the disadvantage that it is not obvious it has oc-curred. Sometimes it is demanded to signal the content consumer that content filtering orcontent blocking has taken place. That’s why filtered or blocked object is replaced with sim-ilar one (e.g. with the same content type) but with lower size.

2.5.3 Methods based on caching

Because caching mechanism is hierarchical in principle, the methods based on it work ondifferent levels of its hierarchy. Not all accelerators have all the following cache hierarchylevels.

• user-agent cache (private)

• client-proxy cache (private)

• private server-proxy cache (private)

• shared server-proxy cache (public)

• public origin server cache (public)

The words private and public in round bracket say what are nature of cached objects, if theyare user specific or not.From the user’s view is the client caching (the nearest cache) is the most important butbecause of such cache holds only user specific data and thus its cache hit ratio is low, itusually works in conjunction with global shared cache hierarchy on servers.Performance of cache methods depends on application level protocol, if it support them in itsdesign (e.g. HTTP) or not (e.g. FTP), and also on proper settings of object’s cacheabilitysigns.See section 2.3.

2.5.4 Methods based on tuning parameters of protocols used

These methods are based on tuning or smarter use of network protocols. We can divide themfurther to:

• Methods of optimizing low level network protocols - Up to transport protocol layer inTCP/IP stack, see table 1.1.


Figure 2.11: LAN - The Typical case of fast network

• Methods of optimizing high level network protocols - from session protocols to higherlayers, mostly application protocol’s optimizations.

Methods of optimization on low level (transport) protocol layer

We will focus on TCP transport protocol as on the most important representative of thetransport’s protocols, especially for its major use. In the early 21st century, TCP is typicallyused in approximately 95% of all Internet packets27.TCP protocol provides reliable stream delivery along a full duplex connection between twomachines, allowing them to exchange large volumes of data efficiently. More on TCP protocolcan be found in [7].Although there are many algorithm favorably affecting TCP performance (e.g. congestionreduction algorithms, algorithms for more effective calculation of Rount Trip Time values -Karn’s algorithm, algorithms for efficient network bandwidth use - Nagle’s algorithm, etc.)designed as TCP standard extensions and present implementations successfully use them28,there are some protocol parameters that can be set in the implementations and can signifi-cantly improve connection resource use.The connection accelerators are more often used on slow links29, so we will point at someexamples of TCP tuning for these links.

• Setting an appropriate send window size Wireless and satellite networks have a commonproblem of a higher bit error rate. One tuning strategy to compensate for the lengthydelays is to increase the send window, sending as much data as possible until the first

27Wikipedia28See [16], [17]29The links with high latency and possibly low throughput, e.g. common to dial-up, wireless and satellite

networks


Figure 2.12: WAN - The Typical case of slow network

ACK arrives. This way the link is utilized as much as possible. If the send window issmall, then there will be significant dead time between the time the send window sendspackets over the link and the time an ACK arrives and the sender can either retransmitor send the next window of packets in the send buffer. But due to the increased errorprobability, if one byte is not acknowledged by the receiver, the entire buffer must beresent. Hence, there is a trade-off to increase the buffer to increase throughput. Butthe window size can not be increased so much that if there is an error the performanceis degraded by more than was gained due to retransmissions. In addition to extradelays, retransmissions are bad because of employing TCP Slow Start algorithm [15]which prevent a network to get congested is in bad shape. Consequence of use ofthe algorithm is lowering a size of send window and its slow controlled increasing. Itimpacts negatively network utilization. This is where manual tuning comes in. Varioussettings based on an estimation of the link characteristics can be employed. One majorimprovement in TCP is the selective acknowledgement (SACK), where only the onebyte that was not received can be retransmitted, not the entire buffer. More on SACKcan be found in [14].

• Setting the number of consecutive duplicate ACKs that triggers the fast retransmit, fastrecovery algorithm Another problem introduced in these slow links is that the ACKsplay a major role. If ACKs are not received by the sender in a timely manner, thegrowth of windows is impacted. During initial slow start, and even slow start afteran idle, the send window needs to grow exponentially, adjusting to the link speed asquickly as possible for coarser tuning. It then grows linearly after reaching Slow StartThreshold value, for finer-grained tuning. However, if the ACK is lost, which has ahigher probability in these types of links, then the performance throughput is againdegraded.


• Adjusting timeouts It is important to adjust all timeouts to compensate for long-delaysatellite transmissions and possibly longer-distance WANs, as the different timeout val-ues must be compensated. For comparison of characteristics of fast and slow networksee the figures 2.11 and 2.12.

• Maintaining the single or a few persistent TCP connections and tunneling all trafficthrough them is popular method of TCP protocol acceleration in many acceleratorswith architecture pair of proxies. It reduces TCP overhead for connection setup andtransmission to minimum and it is advantageous particularly in slow networks.

Methods of optimization on high level (application) protocol layer

In difference to transport level protocols application level protocols offer more informationabout the transferred data, the format of the data is known, and so the methods use theinformation.Because connection accelerators operate typically on application protocol layer (Accelerators- Proxy servers), or at least use the information provided by this layer (Accelerators - Pair ofproxy servers), the methods of tuning of these protocols we are presenting in 2.6.

2.5.5 The most demanded or priority data predicting methods

Prefetching

Prefetching is a method how to decrease data access time. It is a suitable method, whenresponse from origin server has significant latency.Actually, prefetching does not reduce communication latency, it only lets exploit all free con-nection resources as soon as all explicitly requested data are downloaded and there are noother requests.Selection of data for prefetching can be done in several ways but all selection algorithms hasthe same objective - to choose the most wanted data in the future. In optimal case the dataare prefetched before it is explicitly asked. In this case the data is immediately available andwe save time for requesting an origin server and waiting for response.Prefetching can be categorized ([19]) into two categories, local and server-hint, based on placewhere the information for determining which objects to prefetch is generated.In local based prefetching, the client doing the prefetching uses local information (e.g. ref-erence patterns) to determine which objects to prefetch. Prefetching algorithms that do notmake use of information from the server, whether employed at a client or at a proxy, wouldbe considered local prefetching.In server-hint based prefetching, the server is able to use its content specific knowledge ofthe objects requested, as well as the reference patterns from a far greater number of clientsto determine which objects should be prefetched. The actual prefetching, however, must bedone by an agent closer to the client. Therefore, the server provides hints that assist thisagent (either a proxy or client) in prefetching. Implementation of this model is complicatedby the requirement for modifications at both the client or proxy side as well as the serverside.Prefetching put together with caching is called active caching (in contrast to the passivecaching how is called the classical form of request invoked caching).


The most significant drawback of prefetching is the fact that some data downloaded are neverused in the future because user behavior can not be exactly determined a priori. It resultsin downloading more data than in case of not applying this method. Thus this method iscompletely unusable for accelerating Internet connections that use per transferred data payedconnection technology.Misuse of this method can also lead to a network congestion in highly loaded network.

Priority downloading

Like in previous case this method is suitable in high latency networks.In contrast to previous method, this one does not download any spare data. It employs theidea that some (priority) data required by users are wanted more earlier that others. Thusthis priority data are downloaded earlier (e.g. priority downloading of all the textual objectsbefore image objects).

Often methods from different categories are combined.

2.6 Methods of application protocol’s acceleration

This thesis is focussing on acceleration of the most important application protocol HTTP(World Wide Web service).Other frequently used common application protocols are:

• FTP - is used as base protocol for File Transport Service

• SMTP, POP, IMAP - form the Electronic Mail Service

• SSH - is used as base protocol for Secure Remote Login (Secure SHell)

• DNS - is used as base protocol for Domain Name Service that purveys Domain Nameto IP and IP to Domain Name address lookup for other Internet services.

2.6.1 DNS protocol

The usage of the Domain Name Service is essential to the majority of the common applicationprotocols. These days DNS is used in quite a different manner than just a few years ago. Inaddition to its main purpose the DNS is also used to load distribution between servers, Mailtransfer agents use DNS to find out where to deliver E-mail for a particular address, etc.The duration of the DNS lookup time can be a significant part of the duration of an applicationtransaction30 even in fast networks and can become more significant in congested network.To prevent this service to become a bottleneck it is common practice to cache successful DNSlookup queries. In principle, there are two types of DNS caches:

• IP Cache that holds data for FQDN31 name to IP address translation.

• FQDN Cache that holds the data for translation in other way round.30For example, HTTP client has to translate Domain name obtained from user to IP address of an origin

server what does by sending an UDP packet to DNS server of ISP. The HTTP request can not be sent untilthe DNS server recursively searches for appropriate A (AAAA or CNAME) record and sends asked IP addressto HTTP client.

31FQDN stands for Fully Qualified Domain Name.


2.6.2 HTTP protocol

HTTP Keep-Alive

The early version design of HTTP was very simple. Each client request started with establish-ing a connection between the client and the origin server, then sending the request messageand waiting for response. After the response was completely received, the connection wasclosed. This made HTTP very inefficient, because of connection overhead and applying ”slowstart” congestion avoidance mechanism in every HTTP requests. There was done number ofperformance analysis, for instance [18].Thus in HTTP/1.0 version was introduced keep-alive mechanism that allow the client toask (by sending Connection: Keep-Alive or Keep-Alive header) the server for permanentconnection for elimination overhead of subsequent requests.In HTTP/1.1 was the mechanism changed (see [2]). In every HTTP/1.1 request is the per-sistence default, but can be suppressed (by sending header Connection: Close).For proxies and thus connection accelerators is the behavior essential, because almost allrequests from their clients travel to them. It implies that TCP connection and slow-startoverhead can be significantly removed when the proxy and clients support persistent connec-tions.

HTTP pipelining

Clients supporting persistent connections may send multiple HTTP requests to server withoutwaiting for each response. Server must (to comply with HTTP protocol) send responses tothose requests in the same order it received them.This let the server preparing the responses in advance and eliminate server request waitingdelays.

HTTP caching (Web caching)

See 2.3.2, in Caches section.

HTTP standard compression

Compression of HTTP objects is enabled by presence of content and transfer coding mecha-nism in HTTP standard.Content codings are transformations that can be or has been applied to HTTP data entitywithout losing the identity of its underlying media type and without loss of information.There are standardized the four following content codings in HTTP:

• gzip - An encoding format produced by the file compression program “gzip” (GNUzip), as described in RFC 1952 ([37]). This format is a Lempel-Ziv coding (LZ77) witha 32 bit CRC.

• compress - The encoding format produced by the common UNIX file compressionprogram “compress”. This format is an adaptive Lempel-Ziv-Welch coding (LZW).

• deflate - The “zlib” format defined in RFC 1950 ([35]) in combination with the “deflate”compression mechanism described in RFC 1951 ([36]).


• identity - The default (identity) encoding. It means no transformation whatsoever.

The mechanism works as follows:

If the client includes the following header along with the HTTP request for some objectlike HTML page on the origin server,

Accept-Encoding: gzip

then the origin server is advised that client understands “gzipped” content.If the server is sending the required HTML page encoded, it include the following HTTPheaders in response message.

Content-Type: text/htmlContent-Encoding: gzip

On the client side the encoded data from response is at first decoded and then it is treatedas a standard HTML file.In contrast to content codings, transfer codings can be applied to an entity-body in orderto ensure “safe transport” through the network. This differs from a content coding in thatthe transfer-coding is a property of the message, not of the original entity. Thus sometimescontent codings are called end-to-end transformations whereas transfer codings are calledhop-by-hop transformations.

Differential compression

The idea of differential compression is encode data file (source file) by using another data file(reference file).A differential compression algorithm locates substring common to both the source file andthe reference file, and encodes the source by indicating substrings that can be located in thereference file and substrings that are add explicitly.The result of the encoding process is a file called difference or delta that can be interpret asa description of differences between source file and reference file.Differential compression allows applications to encode compactly a new version of data withrespect to a previous or reference version of the same data.Differential compression was firstly used in source control systems such as RCS for effectivestoring new versions of source files.Nowadays some connection accelerators with pair of proxy servers architecture use it to reducedata transferred. There is an open-source implementation of differential compression librarycalled zdelta, based on Zlib Compression Library ([38]).

Lossy image compression, image transformations

Because at the HTTP level the metainformation about content type is available, it is possibleto put in place lossy image compression and other transformation methods to image data toobtain more bandwidth savings than in case of using general data compression only.The following techniques or their combinations is typically used:

• Lowering image resolution, image resampling.


• Lowering number of image colors.

• Conversion to another image format.

• Compression of image data by general compression algorithm.

Low bandwidth protocols over HTTP

Mobile devices are usually connected through low bandwidth technology and user agents onmobile devices have usually less capabilities than user agents on PCs. Thus make good senseto deliver another content with more simple structure than HTML to them.There were designed some low bandwidth protocols, such as:

• XHTML Basic is an XML-based markup language, a subset of XHTML, that is used forencoding information for simple (mainly handled) user agents, typically mobile devices.XHTML Basic include minimal set of XHTML modules for document structure, images,forms, basic tables, and object support.

• C-HTML is a subset of the HTML that was designed for mobile devices.

• WML stands for Wireless Markup Language and is the primary content format fordevices that implement the Wireless Application Protocol32 (WAP). WML pages arestored on a Web server similarly like HTML ones. WAP devices then access themthrough WAP gateway that serving like a proxy and translates their WAP requests toHTTP requests.

HTTP content blocking or filtering

Both, Content blocking and filtering, are typical proxy tasks.Content blocking in HTTP is done by comparing data metainformation (such as URL, objectMIME type, object size, etc.) from client request or from origin server reply with records inblock lists. If a match is found, it is sent the ”403 Forbidden” or ”404 Not Found” HTTPmessage as a response to the request by proxy instead of asked data.Content filtering is done usually on ”content level” but sometimes the HTTP metainforma-tion is used too. In content filtering, the origin server reply data is parsed by proxy andthen is possibly applied filtering transformation to it, before it is sent to the client. Thetransformations can be as follows:

• Replacing the content with substitute one, e.g. images from particular server are re-placed by 1x1pixel thumbnail picture.

• Conversion to another content representation, e.g. conversion HTML page to XHTMLBasic page, more suitable for mobile device.

• Recognition and filtering advertisement content.

• Text compaction and filtering HTML elements that have no influence to visible repre-sentation of the data.

32The protocol similar to HTTP but designed for wireless devices.


HTTP prefetching

HTML enable to describe relations between documents using <link> element. These relationscan be used by prefetching mechanism for selection the most demanded data. It worksprovided that user is downloading also related documents. But this is a common accesspattern for HTML page with embedded images, CSS styles, or Javascripts.Another approach is presented authors of the paper [20]. They suggest a proxy-based systemmonitoring user’s Web usage patterns and creating a directed weighted graph where the nodesrepresent URLs and edges represent the access path. The weight of a node u indicates thefrequency of access of the corresponding URL, while the weight of an edge (u,v) indicates thefrequency of access of the URL v immediately following the URL u. The system then use thisstatistical information to select data for prefetching into local cache. The authors observedthat on the average, they spend only 83% of the time they spend on a Web session when theywere using their active caching proxy system.

2.6.3 Other application protocols

FTP

In difference to HTTP protocol, which can be considered both - a communication protocoland application platform, FTP protocol serve only for file transport.FTP protocol does not support serving of dynamical content and does not support cachingdirectly. Today, majority of files offered by FTP servers are archives or software distribu-tion packages and as such are already compressed what implies there is no much room forimprovement.

SMTP/POP/IMAP

Besides Web Service the Electronic Mail Service is one of today’s most important Internetservices.The SMTP33, POP34 and IMAP35 serve for sending or receiving E-mail messages.It emerged a problem when transferring binary data and textual data coded into differentformat than 7-bit ASCII-chacter set due to an initial simple design. Thus the some extensionsof Electronic mail protocols were designed to allow transfer effectively 8-bit data or MIMEstructure of the transmitted data.Although the common implementations use the better standards designed for MIME structur-ing of the data and for 8-bit raw binary data transmissions on top of Electronic mail service36,some of old encoding (and data size increasing) schemas are still used.E-Mail messages, analogously to the Web pages, are transferred through the Internet in un-compressed form. Thus some methods of bandwidth savings (compression, content blocking,etc.) used in Web can be adapted to the area of Electronic Mail Service.For more bandwidth savings we have to think about other more effective methods, such asintelligent E-mail filtering, due to the considerable amount of spam E-mail messages trans-ferred by Electronic Mail Service. But this is a hardly solvable problem beyond the scope of

33Defined in RFC 82134Defined in RFC 193935RFC 173036See RFC 1426


this work.

2.7 Compression methods

Lossless data compression is at the heart of any accelerator as it directly increases the effectivethroughput of a low bandwidth connection.All the algorithms we will describe in this section belong to the dictionary methods categorymentioned in 2.5.1.

2.7.1 LZ77

In 1977 Lempel and Ziv presented dictionary based scheme for text compression ([9]). Thescheme was named LZ77 and becomes the base for other general compression methods.LZ77 algorithm uses like a dictionary a part of the previously seen input. The encoder main-tains a window to the input stream and shifts the input in that window from right to left asstring of symbols are being encoded. The window is called sliding window and is divided intotwo parts - a search buffer and a look-ahead buffer. Search buffer is the current dictionaryand it always includes symbols that have recently been input and encoded. The look-aheadbuffer contains text yet to be encoded. In practical implementations the search buffer is somethousands of bytes long, while the look-ahead buffer is only tens of bytes long.The encoder scans the search buffer backwards looking for the match to the first symbol inlook-ahead buffer. If some is found the encoder then matched as many symbols following thefirst symbol as possible. When it finishes, it has a position in search buffer and the length ofmatch. After that the encoder continues the backward scan, trying to find longer matches.When the encoder reach left end of sliding window it selects the longest match it found,or, if they are all the same length, the last one found and prepares output token (posi-tion,length,symbol), where position is the position of longest match in search buffer, length isthe length of this match and the symbol37 is the first symbol in look-ahead buffer after stringmatched the match.As soon as the token is written to the output, the sliding-window is shifted to the right inthe length of length+1.The efficiency of LZ77 is influenced by data redundancy, thus how frequently and how longmatches are found in search window. Practical implementations have to deal with some tech-nical problems. The way of coding of tokens is the most important problem affecting wholealgorithm performance.

2.7.2 ZLIB, GZIP

Probably the most known nowadays implementation of LZ77-based algorithm can be foundin Zlib Compression Library. The algorithm is called deflate and its output format is one ofsupported formats in HTTP standard compression.Deflate algorithm uses search buffer of size 32KB and the size of the match is limited to 258bytes.Algorithm also uses chained hash table to store phrases from search buffer. The phrase isstored in hash table by its first 3 bytes. Use of hash table speeds up searching for longest

37In later modification of the algorithm (LZSS) was this symbol removed.


match in search buffer and thus the whole encoding process.For coding of tokens it is used static Huffmann code. The Huffmann code is a variable-sizecode that has a prefix property, what means that no code word is a prefix of another code wordin Huffmann code. The prefix property enables unambiguous decoding the string consistedof concatenation of code words.The popular free software file compression program GNU zip (gzip) is also based on deflatealgorithm. The same algorithm uses ZIP format for compression on DOS and Windowsplatform and is also used for compression of image data in PNG format.More about efficiency of the algorithm can be read in [38].

2.7.3 LZ78, LZW

In 1978 Lempel and Ziv presented the LZ78 method ([10]) that does not use any search buffer,look-ahead buffer, or sliding window. Instead there is a dictionary of previously encounteredstrings. The dictionary starts empty or almost empty.The encoder outputs two-field token (pointer, code). The pointer is the pointer into dictionaryand the code is the code of the symbol. Tokens do not contain the length of a string sincethis is implied in the dictionary. Each token corresponds to a string of input symbols, andthat string is added to the dictionary after the token is written on the compressed stream.Nothing is ever deleted from the dictionary, which is both an advantage over LZ77 and aliability.LZW algorithm is a variant of LZ78 that eliminate the second field in the output token de-veloped by Welch ([11]).The UNIX ”compress” program uses an adaptive LZW method that starts with a small dic-tionary (of just 512 entries) and when it fills up, its size is doubled. This repeat every timetill dictionary reach maximum size set by user.After that, ”compress” continues without changing of dictionary and monitoring the com-pression ratio. If the ratio falls below a predefined threshold, the dictionary is deleted, and”compress” start again with new 512-entries dictionary.The decompression of data is done by ”uncompress” program and main task of the decoderis to maintains the dictionary the same way the encoder does.

Chapter 3

AVAILABLE SOLUTIONS

This chapter provides a review of contemporary connection accelerators and to compare theirfeatures.

3.1 Review of contemporary accelerators

In this section some of contemporary accelerators are presented. They are split into the twocategories defined in 2.4.At the end of each category there is a table summarizing the compared accelerators features.Although the comparison was done carefully, the information gathered about accelerators isnot complete and in some cases rely only on white paper materials obtained from manufacturerbecause we had no opportunity to directly verify it in lab.

3.1.1 Accelerators - Proxy servers

We differentiate the following two subtypes of accelerators from this category:An accelerator - surrogate is typically the combination of a Web server and a Web servermodule (also called a filter). The modules exist for most of the major Web server platforms.Accelerators - surrogates are mostly used for a compression of web pages. To this review weselected an Apache Web server and a Microsoft Internet Information Server platforms.An accelerators - proxy server is an accelerator with the same architecture as a surrogate butit is typically a designated server operating as an intermediary in ISP’s network and it is usedin addition to content compression for many other tasks as caching, content filtering, etc.

mod gzip

Mod gzip is an Internet Content Acceleration module for the popular Apache Web Server. Itcompresses the content delivered to the client.

Accelerator typeApache with the mod gzip module is a surrogate or when used in conjunction with themod proxy module it becomes a caching proxy server.

37

CHAPTER 3. AVAILABLE SOLUTIONS 38

System architectureMod gzip is an module for Apache web server at version 1.3.x. Apache web server supportsthe two different methods of integrating a module into its program code:

• Static integration means that the module becomes a permanent part of the linked pro-gram binary httpd that implements the Apache server.

• Dynamic integration means that the module can be loaded from a separate module fileas a shared object when starting the Apache process.

A gzip compression algorithm in mod gzip was implemented by Kevin Kiley.There is an Apache web server 2.x compatible version of mod gzip which uses zlib library.

Installation and ConfigurationMod gzip requires Apache web server to be installed first. Depending on the operation con-cept used for Apache web server and the given requirements, one of the two operation methodsfor mod gzip has to be selected, and the set of corresponding files required for this methodhas to be downloaded.There is no need to install any additional software on the client.More on installation and configuration of Apache directives can be found in [31], [32].

Features, supported protocols and user agentsApache web server with mod gzip supports serving compressed1 web objects through HTTP/1.1protocol. Mod proxy module enables support for FTP and SSL protocol proxying and caching.Compatible user agents are shown in the table 3.1.

How it worksIn Apache, there is a way how to send gzipped data to the client without mod gzip usingthe Content Negotiation protocol, what requires that the two separate sets of HTML filesbe generated: one for clients who can handle a gzip-encoding, and one for those who can’t.Apache then sends gzip-encoded files to the clients who understand them (clients let it knowby putting Accept-Encoding HTTP header with the request).But this solution can not be used for the compression of dynamically-generated pages.When we want to take an advantage of the gzip-encoding of dynamically-generated pages too,we have to use mod gzip module. When it is properly configured, it does the gzip-encodingon all the objects just after they have been processed by all of Apache’s other modules before2

they are sent to the client.The mechanism works as follows:If the client includes the following header along with the HTTP request for some object likean HTML page on the server,

Accept-Encoding: gzip

mod gzip processes the outgoing content from the server and include the following serverHTTP response headers.

Content-Type: text/html

Content-Encoding: gzip

1Gzip algorithm is used.2Mod gzip have to be set as the last in the Apache module order.


These server HTTP response headers mean that the content returned from the serveris encoded with gzip algorithm. On the client side the data is at first decoded and then istreated as a standard HTML file.

Versions and referencesVersion numbers of mod gzip correspond with version numbers of Apache web server. Currentversion of mod gzip is mod gzip 1.3.26.1a.Project home page can be found in [33].

mod deflate

Mod deflate is the successor of mod gzip module. As mod gzip module was initially designedto run under Apache web server at version 1.3.x, mod deflate module is designed to deliverbenefit of a data compression to Apache web server at version 2.x.The algorithm used in the mod deflate module was designed with emphasis to do a speedycompression. Probably, this is the reason it is less effective than mod gzip when the compres-sion ratio is compared.

Accelerator typeApache with the mod deflate module is a surrogate or when used in conjunction with someparticulars modules it becomes a proxy server. There are the following modules:

• mod proxy enable Apache to be an HTTP/1.1 proxy/gateway server.

• mod proxy ftp is a FTP supporting module for mod proxy.

• mod proxy http is an HTTP supporting module for mod proxy.

• mod proxy conntect is a mod proxy extension for CONNECT request handling.

• mod cache is used for a content caching keyed to URIs.

• mod negotiation provides a content negotiation.

System architectureThe architecture of Apache web server at version 2.x is different from 1.3.x architecture. Mainpart of the Apache 2.x request processing is implemented into multi-processing modules. Allextensions to Apache 2.x (e.g. mod deflate) are implemented like modules too. Mod deflateis the part of Apache web server 2.x installation.Mod deflate provides the DEFLATE output filter. The filter is a process that is applied todata sending or receiving by the server. The compression algorithm in mod deflate module isimplemented by using of the zlib library, see [38].

Installation and ConfigurationMod deflate requires Apache web server to be installed first. During the installation processit is possible to enable mod deflate and other needed modules. There is no need to installany additional software on the client.More on an installation and a configuration of Apache directives can be found in [31], [34].


Features, supported protocols and user agentsApache web server with mod deflate supports serving compressed3 web objects through theHTTP/1.1 protocol. Other available Apache modules extend the system to be supporting forthe HTTP, the FTP and the SSL protocol proxying and caching.Compatible user agents are shown in the table 3.1.

How it worksIt uses a similar mechanism as mod gzip to activate the compression, but the deflate al-gorithm it is used instead of gzip to encode objects. Therefore, the Accept-Encoding andContent-Encoding headers holds deflate value.

Versions and referencesVersion numbers of mod deflate correspond with version numbers of Apache web server.Current version of mod gzip is mod deflate 2.0.54.More information about mod deflate can be found in [34].

SqueezePlay

SqueezePlay is a software suite that runs on Microsoft Internet Information Server (IIS) toprovide a real-time HTTP compression of an outgoing dynamic and a static website content.It also provides an image reduction (resampling or conversion) for GIF, JPEG and PNG im-age formats.

Accelerator typeIIS in conjunction with the SqueezePlay filter forms a surrogate.

System architectureSqueezePlay is implemented like an ISAPI4 filter and it is in-lined into the IIS server.SqueezePlay supports IIS 4.0, through IIS 6.0, including .NET servers. SqueezePlay suitecontains the two utility programs - the Configurator and the Accelerometer. The Configura-tor tool can be used for changing and inspecting SqueezePlay’s settings and the Accelerometertool is a graphic performance meter.

Installation and ConfigurationSqueezePlay requires the IIS server to be installed first. After that, it is possible to deployand activate SqueezePlay. Afterwards, the Configurator tool can be used to configure andenable it. There is no need to install any additional software on the client.More on an installation and a configuration can be found in [42].

Features, supported protocols and user agentsIIS server with SqueezePlay supports serving compacted web objects through the HTTP/1.1protocol. The methods of bandwidth savings are as follows:

• The compression of web objects,

• the resampling of image types (JPG, GIF, PNG, ...),3The deflate algorithm is used.4Internet Service Application Programming Interface - a Microsoft Internet Information Server’s API.


• the conversion of image types to an another image type format with aim reducing theweb object’s size.

SqueezePlay supports the caching of static data after that it has been transformed. Compat-ible user agents are shown in the table 3.1.

How it worksIt uses a similar mechanism as mod gzip. An appropriate image reduction for bigger band-width savings can be selected by the server administrator globally, by site/page or on per afile-by-file basis.

Versions and referencesCurrent version of SqueezePlay is SqueezePlay 2.0. More about SqueezePlay can be read in[42].

XCompress

XCompress is a software suite that like SqueezePlay runs on IIS and provide a real-timeHTTP compression of an outgoing dynamic and a static website content. In addition to thecompression it does the white space compression and the normalization, which removes non-essential characters and standardizes syntax in HTML, JavaScript, and CSS.

Accelerator typeIIS in conjunction with an XCompress filter forms a surrogate.

System architectureXCompress is implemented in the two variants: an ISAPI filter or a COM object.

Installation and ConfigurationXCompress requires the IIS server to be installed first. After that it is possible to deploya filter or install a COM object, and to activate XCompress. XCompress can be managedthrough the IIS administration console. XCompress supports IIS from version 4.0, till version.NET.

Features, supported protocols and user agentsIIS server with XCompress supports serving compressed web objects through the HTTP/1.1protocol. Compatible user agents are shown in the table 3.1.

How it worksIt uses a similar mechanism as mod gzip.

Versions and referencesCurrent version of XCompress is XCompress 2.1 and XCompress 3.0. More about XCompresscan be found in [43].

Others accelerators not covered by this study include: AcceleNet/CL (clientless), CProxy(clientless), and more.


Tab

le3.

1:C

ompa

riso

nof

acce

lera

tors

from

Acc

eler

ator

s-

Pro

xyse

rver

sca

tego

ry

Apa

che

1.3

+m

odgz

ipA

pach

e2.

x+

mod

defla

teII

S+

Sque

ezeP

lay

IIS

+X

Com

pres

sSq

ueez

e+

mod

prox

y+

othe

rm

odul

esA

ccel

erat

orty

pesu

rrog

ate,

prox

ysu

rrog

ate,

prox

ysu

rrog

ate

surr

ogat

epr

oxy

(sur

roga

te)

Min

imal

mod

ifiab

leob

ject

size

opti

onal

N/A

N/A

N/A

opti

onal

Max

imal

mod

ifiab

leob

ject

size

opti

onal

N/A

N/A

N/A

opti

onal

Met

hod

sele

ctio

ntr

igge

rsU

RI,

file

exte

nsio

n,U

RI,

file

exte

nsio

n,ha

ndle

r,m

ime

type

,fil

eex

tens

ion

file

exte

nsio

nm

ime

type

hand

ler,

requ

est

head

er,m

ime

type

requ

est

head

er,m

ime

type

Com

pres

sion

algo

rith

mgz

ipde

flate

gzip

gzip

defla

teJP

EG

imag

etr

ansf

orm

atio

nno

noN

/Are

sam

plin

g,co

nver

sion

resa

mpl

ing

GIF

imag

etr

ansf

orm

atio

nno

noN

/Are

sam

plin

g,co

nver

sion

pale

tte

redu

ctio

nP

NG

imag

etr

ansf

orm

atio

nno

noN

/Are

sam

plin

g,co

nver

sion

com

pres

sion

Oth

erm

etho

dsof

nono

N/A

whi

tesp

ace

com

pact

ion,

notr

ansf

orm

atio

nno

rmal

izat

ion

Cac

hing

yes

yes

yes

noye

sC

onte

ntbl

ocki

ngno

noN

/AN

/Afla

shH

TM

Lfil

teri

ngno

noN

/AN

/Aye

sP

refe

tchi

ngno

noN

/AN

/Aac

cess

log

base

dSu

ppor

ted

prot

ocol

sH

TT

P,FT

P,SS

LH

TT

P,FT

P,SS

LH

TT

P,FT

P,SS

LH

TT

P,FT

P,SS

LH

TT

P,FT

P,SS

L,G

ophe

rA

ccel

erat

edpr

otoc

ols

HT

TP,

FT

P,SS

LH

TT

P,FT

P,SS

LH

TT

PH

TT

PH

TT

PB

row

sers

com

pati

bilit

yN

N4.

06+

,N

N6&

7,M

oz,Ffo

x,IE

4+,M

oz,Ffo

x,O

4+IE

5+,N

N4.

08+

,N

N6&

7,IE

4+,N

N4.

08+

,N

N6&

7,N

N4.

06+

,N

N6&

7,M

oz,

IE4+

,O

4+,LY

2.6+

Moz

,Ffo

x,O

4+M

oz,Ffo

x,O

4+Ffo

x,IE

4+,O

4+Se

rver

plat

form

Free

BSD

,Lin

ux,So

lari

s,Fr

eeB

SD,Lin

ux,So

lari

s,W

indo

ws

Win

dow

sFr

eeB

SD,So

lari

s,A

IX,

Win

dow

sW

indo

ws

Lin

ux,W

indo

ws


3.1.2 Accelerators - Pair of proxy servers

An accelerator - a pair of proxy servers consists typically of the one proxy server locatedinside of the ISP’s network and the one proxy server located at a user computer.These accelerators are mostly used for an efficient compression of an HTTP and an otherprotocol’s traffic in both directions - from the client to the server and the other way around.Of course, the other methods of a bandwidth saving and a connection acceleration can beemployed too.

We selected several of the most known accelerators among the numerous commercial so-lutions available today for this review.

Google Web Accelerator

Google Web Accelerator (GWA) uses the Google’s global computer network to make webpages load faster through the compression, the caching, and the prefetching of them. GWAis mainly optimized to speed up a web page loading for broadband connections.

System architectureGWA in an accelerator with a pair of proxy servers architecture. The client side proxy consistsof the main client accelerator program and from the two dynamic libraries - browser pluginsfor Internet Explorer and Firefox Browsers.We was not able to determine the system architecture of the server side proxy.

Installation and ConfigurationThe client side proxy has to be installed on user’s computer from an installation package thatcan be downloaded from the Google network. The size of the installation package is less than2 MB. After a successful installation the client proxy listens on port 9100 on user’s computer.Another side, the server proxy, is installed on server in one of the deployed local Googlenetworks. The preferred server proxy (probably the one from the nearest Google network) isselected according to the user’s network location automatically by the client proxy. It is alsocreated a client proxy PAC script for an auto-configuration of browsers and it is available onthe http://localhost:9100/proxy.pac URL.

Features, supported protocols and user agentsGWA accelerates an HTTP traffic using the following techniques:

• Sending user’s requests for pages through Google machines dedicated to handling theGoogle Accelerator traffic.

• Storing copies of frequently looked at pages to make them quickly accessible.

• Downloading only the updates if a web page has changed slightly since the user lastviewed it.

• Prefetching certain pages onto user’s computer in advance.

• Managing the Internet connection to reduce delays.


• Compressing data before sending it to user’s computer.

Some sites (can be selected by user) can be excluded from an acceleration.Performance statistics of accelerator include the number of pages that have been loaded andhow long these pages would have taken to load with and without GWA, and they are availablethrough browsers plugins.GWA supports Internet Explorer and Firefox browsers. Other browser can be set manuallyto use GWA too, but can not take all of its advantages.

How it worksAll the above techniques are used by GWA to speed up the surfing process for all web sitesnot only the sites located inside the Google networks.The prefetched data is determined, in part, by an algorithm that looks at user’s mousemovements in browser, and an aggregate traffic to sites counted on the server side proxy.Web content authors can specify which followed pages should be prefetched by GWA on theirsite if they include an HTML tag or tags into a head section of index page like in figure 3.1.An availability of the prefetched data is signalized in browsers highlighting of links to thisdata. The prefeching can be switched off when it is inappropriate.The cached or the prefetched data by GWA is stored in the client proxy cache separate fromthe browser cache. Similarly, the server proxy does the caching. Thus server proxy cache candetermine the most frequently accessed pages and can hold the latest copy them.GWA uses a parallel downloading of files and is able to transfer only the parts of Web pagethat changed, instead of the downloading an entire file.The transferred pages are compressed, images are left unchanged.

<link rel="prefetch" href="http://url/to/get/">

Figure 3.1: An HTML tag to specify pages for prefetching by GWA.

Versions and referencesAt the time of writing this thesis the beta phase testing of GWA was under the process. Moreon the Google Web Accelerator can be found in [26].

AcceleNet/CS

AcceleNet/CS5 accelerator was designed to improve the performance of networked applica-tions over wireless and dial-up connections.

System architectureAcceleNet/CS in an accelerator with pair of proxy servers architecture. Client side proxy(AcceleNet client) is a lightweight client program that runs on Windows PC and Pocket PCplatforms. Server side proxy (AcceleNet server) is a high-performance server running on ei-ther Windows or Linux.

5CS stands for Client-Server.


Installation and ConfigurationAcceleNet client can be installed from installation package of about 5 MB size and when itis running it automatically creates tunnel endpoints for application and start listening onthese endpoints. User agents can be configured automatically or manually to send its trafficthrough these endpoints.After installation of AcceleNet accelerator server it is automatically adjusting its performancein response to bandwidth availability, server load, and commmunication channel resources.Client upgrades are automatically downloaded from AcceleNet server. Client defaults areconfigurable by system administrator via wizard-based client builder application.

Features, supported protocols and user agentsThe AcceleNet/CS accelerator can be used for acceleration of HTTP traffic (mostly Web)and also SMTP, POP (Electronic Mail) or MS-RPC (Remote Procedure Call) traffic.The techniques used by AcceleNet/CS accelerator are:

• Compression - AcceleNet/CS uses proprietary, format specific algorithms decomposestandard files into their component parts, grouping similar types of data together. Itallow AcceleNet/CS to choose the optimal algorithm for each embedded component orcontent type within a given file. Instead of using a single algorithm on an entire file,AcceleNet/CS uses hundreds of micro-coders that are each designed to encode a specificdata component found within that file format.

• Proprietary transport protocol - AcceleNet/CS employs a proprietary transport protocolcalled ITP (Intelligent Transport Protocol). According to the manufacture’s whitepaper downloaded from [27], ITP provides better performance than TCP for transferringthe highly compressed data within the tunnel - up to 15% improvement over dial-upconnections and 35% improvement for packet-switched wireless networks. ITP runs ontop of UDP but providing 100% reliability and optimized flow control.

• Application-level optimizations - accelerator uses a knowledge of the application levelprotocols and of the profile of the network connection to eliminate performance weak-ness. ITP keeps track of each individual packet rather than using a stream-based ar-chitecture as done in TCP. ITP also uses information from the higher network layersto improve transport decisions such as when to re-transmit a packed whose acknowl-edgement has not been received or when to send partial packet rather than wait to fillout the target MTU size. ITP estimates link bandwidth and other parameters fromthe receiver side and then exchanges model data between both communicating sides, incontrast to generating inaccurate models just from RTTs like TCP does.

Compatible user agents are shown in the table 3.2.

How it worksWeb and Electronic mail content, transmitted between the user’s machine and origin serveron the Internet or an enterprise intranet, is transparently routed into the acceleration tunnelformed by the AcceleNet client and server endpoints.Before entering the tunnel, data are analyzed and perhaps decomposed before applying trans-formations for efficient transmission on slow or low latency links.


Transmitted data compression includes the lossy image compression for the JPEG, PNG, andGIF image types and also lossy the image compression of embedded images in the standardfile formats (Word, PowerPoint, Flash-Shockwave).For transmission it is used the proprietary ITP transport protocol instead of TCP. Versionsand referencesMore information on AcceleNet/CS can be obtained in [27].

Proxyconn Accelerator

Like GWA, the Proxyconn Accelerator uses the power of geographically distributed proxyservers deployed on backbone networks to optimize and accelerate data flow between Proxy-conn user’s computers and origin servers in Internet.

System architectureProxyconn in an accelerator with pair of proxy servers architecture. Client side proxy (Prox-yconn client) is a lightweight client program that runs on background of user’s machine.Proxyconn client has a speed meter component which measure the effective speed of eachpage downloaded.Server side proxy is typically deployed into a hierarchy and it is located on backbone network.Each hierarchy uses an Authorization and configuration server for obtaining information onconnecting users. Proxyconn Linux server uses modified Squid caching server, Windows serveruses Microsoft ISA caching server.

Installation and ConfigurationProxyconn client can be installed from self-installing module of size less than 2 MB. At presentProxyconn client is available only for Windows platform but Mac, Linux and Pocket PC ver-sions are being developed according to [28]. Proxyconn client is able to auto configure someuser agents. Client software upgrades can be done automatically.Proxyconn servers are available to Linux and to Windows platforms.

Features, supported protocols and user agentsProxyconn accelerator accelerates HTTP traffic (Web). It also accelerates POP3, IMAP,SMTP (Electronic Mail) and NNTP traffic.Proxyconn client offers the end-user options to protect against the use of Spyware for infor-mation collection by Advertisers and Networks.Compatible user agents are shown in the table 3.2.

How it worksProxyconn client and Proxyconn server maintain a tunnel between each other, optimize andcompress Web and Electronic Mail traffic transferred through. It also maintain client sidecache to minimize re-transmission already downloaded data to client and server side cache toreduces the number of round trips between client and previously visited sites. For the ISP, italso saves ”upstream” bandwidth.Proxyconn accelerator applies multiple techniques to improve downloading of large files asfollows:

• Multistreaming - Large files are downloaded in chunks through a number of connections;the number of streams is determined automatically.


• Mirroring - Downloading is done from multiple servers at the same time, if they areavailable.

• Transparent resumption of interrupted downloads - Up to 20 resumptions per downloadwithout user intervention. Downloads are resumed from the interruption point even ifstopped by the user or the computer was rebooted.

Versions and referencesMore information on Proxyconn Accelerator can be found in [28].

CProxy Accelerator

The CProxy Accelerator was designed to improve the performance of networked applicationsover mobile data networks or dial-up connections.

System architectureAs the previous accelerators in this category, CProxy is an accelerator with pair of proxyservers architecture.Client side proxy (CProxy client) is a light-weight client program that runs on Windows plat-form.Server side proxy (CProxy server) is a high-performance server running only on WindowsServer operating system and can be put in hierarchy. Inside hierarchy there is a one centralserver through it is the whole system maintained and connected to billing system.

Installation and ConfigurationCProxy client can be installed from installation package of a size less than 1 MB. CProxyclient automatically configure IE browser to work through CProxy. Other browsers and e-mail clients can be set manually. CProxy client had a the most detailed settings available tothe user over all accelerators tested, such as possibility to set image transformation compres-sion levels, Flash and advertising blocking, client side caching, etc. CProxy client offers wellarranged overview of transferred and saved data in both directions. CProxy client also offersautomatic updating to new versions.To install CProxy server it is necessary to also install Microsoft .NET Framework, and Mi-crosoft DataEngine or another SQL server’s runtime.

Features, supported protocols and user agentsCProxy accelerator accelerates HTTP traffic (Web). It also accelerates POP3, IMAP, SMTP(Electronic Mail) traffic. It supports an acceleration SOCKS4 protocol traffic. Because thecompression is done on IP protocol layer (network layer in OSI-model), it supports compress-ing traffic from and to any TCP/IP application. It also implies that the bandwidth savingsstatistics are gathered on this layer.

Compatible user agents are shown in the table 3.2.

How it worksAfter installation of the CProxy client on user’s computer it automatically start local serverslistening on ports for supported protocols’ traffic (HTTP, SMTP, POP). In addition, it can


be add manually other connection points listening on other TCP ports6 for any other TCPapplication.User’s programs connect through this local servers and the local servers redirect the trafficthrough tunnel created between CProxy Client and CProxy Server. The data are compressedjust before they are sent to the tunnel.CProxy Client and CProxy server maintains only one connection between themselves and alltraffic is transferred through it.Client Proxy can activate a bypass when CProxy server is not available.

Versions and referencesMore information as regards CProxy can be found in [29].

Other accelerators not covered by this study include: Browse blast, CRPUD Web Accel-erator, IPTunnelManager, NettGain, Opera Mobile Accelerator, Propel, Redline, Slipstream,Smart Internet Accelerator, Ziproxy, and more.

6This is called ’port mapping’ in CProxy.


Tab

le3.

2:C

ompa

riso

nof

acce

lera

tors

from

Acc

eler

ator

s-

Pai

rof

Pro

xyse

rver

sca

tego

ry

Goog

leW

ebA

ccel

erat

orA

ccel

eNet

/CS

Acc

eler

ator

Pro

xyco

nn

Acc

eler

ator

CP

roxy

Acc

eler

ator

Lev

elw

here

the

com

pres

sion

isdo

neap

plic

atio

npr

otoc

olle

vel

belo

wap

plic

atio

npr

otoc

olle

vel

appl

icat

ion

prot

ocol

leve

lbe

low

appl

icat

ion

prot

ocol

leve

lW

ebC

ompr

essi

onst

anda

rdH

TT

Pco

mp.

,pr

opri

etar

ypr

opri

etar

ypr

opri

etar

ydi

ffere

ntia

lco

mp.

diffe

rent

ialco

mp.

diffe

rent

ialco

mp.

N/A

JPE

Gim

age

tran

sfor

mat

ion

stan

dard

HT

TP

com

pres

sion

loss

yco

mpr

essi

on(4

leve

ls)

loss

yco

mpr

essi

on(4

leve

ls)

loss

yco

mpr

essi

on(1

6le

vels

)G

IFim

age

tran

sfor

mat

ion

stan

dard

HT

TP

com

pres

sion

loss

yco

mpr

essi

on(4

leve

ls)

loss

yco

mpr

essi

on(4

leve

ls)

loss

yco

mpr

essi

on(1

6le

vels

)P

NG

imag

etr

ansf

orm

atio

nst

anda

rdH

TT

Pco

mpr

essi

onlo

ssy

&lo

ssle

ssco

mpr

essi

on(4

leve

ls)

loss

less

com

pres

sion

loss

less

com

pres

sion

Em

bedd

edim

age

obje

cts

tran

sfor

mat

ion

noye

s(l

ossl

ess

and

loss

yco

mp.

)ye

s(l

ossl

ess

com

p.)

N/A

(Im

ages

insi

deof

Fla

shan

imat

ions

,P

DF

docu

men

ts,..

.)ot

her

HT

TP

opti

miz

atio

nsH

TT

Ppi

pelin

ing

N/A

N/A

N/A

Em

ailC

ompr

essi

onno

prop

riet

ary

gzip

prop

riet

ary

Tra

nspo

rtpr

otoc

olop

tim

ized

TC

PIT

P(p

ropr

ieta

ry)

opti

miz

edT

CP

opti

miz

edT

CP

Con

tent

bloc

king

noN

/APop

up,Fla

sh,A

ds,P

2Pap

pl.,

spyw

are

Ads

,Fla

shH

TM

Lfil

teri

ng—

com

pact

ion

no—

noN

/AN

/AN

/A—

yes

Clie

ntC

achi

ngye

sno

yes

yes

Serv

erC

achi

ngye

sN

/Aye

sye

sP

refe

tchi

ngye

sN

/AN

/Ano

Max

imum

mod

ifiab

leob

ject

size

N/A

N/A

opti

onal

(def

ault

:30

0KB

)op

tion

al(d

efau

lt:

<1M

B)

Supp

orte

dpr

otoc

ols

HT

TP,

HT

TP

SH

TT

P,H

TT

PS,

FT

P,SM

TP,

HT

TP,

HT

TP

S,P

OP

3,IM

AP,

HT

TP,

HT

TP

S,FT

P,SM

TP,

PO

P3,

PO

P3,

MS-

RP

CSM

TP,

NN

TP,

othe

r(p

ort

map

ping

)SO

CK

4,ot

her

(por

tm

appi

ng)

Acc

eler

ated

prot

ocol

sH

TT

PH

TT

P,FT

P,SM

TP,

PO

P3

HT

TP,

FT

P,P

OP

3,IM

AP,

HT

TP,

FT

P,SM

TP,

SOC

KS4

,M

S-R

PC

SMT

P,N

NT

P,ot

her

(por

tm

appi

ng)

othe

r(p

ort

map

ping

)B

row

sers

com

pati

bilit

yIE

5.5+

,Ffo

x,IE

4+,

IE4+

,N

N4.

07+

,O

4,IE

4+,

man

ualco

nf:

O4,

NN

4.06

+,ot

her

man

ualco

nf:

Moz

,Ffo

x,O

4,ot

her

Moz

,Ffo

x,ot

her

man

ualco

nf:

NN

4.08

+,N

N6&

7,M

oz,Ffo

x,O

4+,ot

her

E-m

ailcl

ient

sco

mpa

tibi

lity

none

Out

look

,O

utlo

okE

xpre

ss,

Out

look

,O

utlo

okE

xpre

ss,

Out

look

,O

utlo

okE

xpre

ss,

man

ualco

nf:

Eud

ora,

Net

scap

e,O

pera

man

ualco

nf:

Eud

ora,

Net

scap

e,O

pera

man

ualco

nf:

Eud

ora,

Net

scap

e,O

pera

Aut

hent

icat

ion

type

N/A

via

RD

MB

S,R

AD

IUS

auth

.,ac

cess

code

,P

IN,R

AD

IUM

auth

.us

er/p

ass

com

bina

tion

clie

ntIP

rang

esch

ecki

ngcl

ient

IPra

nges

chec

king

clie

ntIP

rang

esch

ecki

ngC

lient

auto

-upd

ate

supp

ort

N/A

yes

(dow

nloa

dfr

omse

rver

)ye

sye

s(i

ncre

men

tal)

Clie

ntpl

atfo

rmW

indo

ws

2000

,X

PW

indo

ws

98,M

E,20

00,X

P,W

indo

ws

98,M

E,20

00,X

PW

indo

ws

95,98

,M

E,N

T,20

00,X

P,20

03W

inC

E4

inde

velo

pmen

t:M

AC

,Lin

ux,Poc

ket

PC

inde

velo

pmen

t:Lin

ux,Poc

ket

PC

Clie

ntpr

oxy

confi

gura

tion

PAC

N/A

thro

ugh

AA

CN

/AC

lient

enab

leby

pass

yes

yes

yes

yes

Serv

erpl

atfo

rmG

oogl

eW

indo

ws

2000

,20

03Se

rver

Win

dow

s20

03Se

rver

Win

dow

s20

00,20

03Se

rver

Red

Hat

Ent

erpr

ise

Lin

ux3

Red

Hat

9Se

rver

can

bepu

tin

hier

arch

yye

sye

sye

sye

sSe

rver

load

bala

ncin

g(t

hrou

gh)

yes

(DN

S)ye

s(D

NS)

yes

(AA

Cse

rver

)ye

s(N

/A)


3.2 Conclusion

Although, there are several capable commercial connection accelerators available from boththe categories at the time of thesis writing, as we know there is not an open-source acceler-ator that implements both the data compression and other effective methods of bandwidthsavings7.

7Apache platform solutions mentioned are implementing the data compression only.

Chapter 4

DESIGN ANDIMPLEMENTATION

This chapter outlines ideas and decisions leading to the design and implementation of theSqueeze Web Accelerator.

4.1 Objectives and decisions made during the design phase

4.1.1 Target accelerator’s architecture

We decided to design and implement an accelerator with accelerator - proxy server architec-ture. This decision was influenced by the following reasons:

• Usage of the accelerator from this category is easier for the user, there is no need toinstall any software on a user’s computer. Only the configuration of user agents mustbe done.

• The operating the accelerator is also easier, because ISP does not have to distributeclient side proxies and the upgrade of accelerator software cab done at one place only -in the ISP’s network.

• There is a possibility to take an advantage of the accelerator on several platforms. Thereare no platform limitations for the client proxies.

• The implementation of such accelerator is easier.

However, we are aware of some performance limitations:

• The accelerator with this architecture will not be able to achieve such amount of band-width savings compared to the accelerator - pair of proxies accelerator; it can apply theoptimizations only in the direction from the origin server to the client.

• We can apply only the standardized and widely supported data compression methodswithin the accelerator although the use of specially designed algorithms for certain datacontent types could be more effective.

51

CHAPTER 4. DESIGN AND IMPLEMENTATION 52

��

��

��

��

��

��

��

��

��

��

��

��

��

Figure 4.1: Example of Squeeze Deployment

4.1.2 To start implementation from scratch or not to start

The decision of implement Squeeze as a Squid Web Caching Proxy extension was made soonafter summarizing ideas related to the design of Squeeze. We want to use the advantages ofa stable HTTP implementation and of a caching mechanism complying with the standard asa good starting point. We do not want to hack the implementation of an HTTP proxy serverto reach stability and good compatibility with as many user agents as possible; instead, wewant to focus on writing an accelerator.Therefore, we have decided to design Squeeze as a module (or modules) for Squid that wouldbe able to compress transferred and cached objects and possibly optimize or transform themfurther with an objective to obtain bandwidth savings and thus accelerate the connection.Also, the usage of an extensive Squid’s access control was a promising solution for the imple-mentation of user driven content blocking.Even the poor Squid programming documentation has not discouraged us from trying it.

4.1.3 Why we choose a stable version of Squid as a base

After we have choose the Squid as a basis the first question emerged as to what version touse as a basis. From the beginning we had two completely different options. The first to takethe stable version 2.51, the other option was to take the development version 3.02.The advantages of the stable version were above all as follows:

• The fact that it was stable, long-time tested, and thus qualified to be put into produc-tion.

• We have slightly more documentation to the stable version at our disposal than to thedevelopment one.

On the other hand, the adventages of development version were as follows:1At the time of designing the Squeeze, the exact stable version string was 2.5 STABLE 9.2At the time of designing the Squeeze, the exact development version string was 3.0-PRE3 (prerelease).


• The development version has a new core architecture and has been completely reimple-mented in C++ (stable version is in C).

• Implementation of Client Streams feature that provides a unidirectional, non-blocking,pull pipeline. They allow to insert the specific code into the reply logic as needed.

• The development version is not feature-freezed, so that Squeeze can be theoreticallyincluded into the main source branch and become a part of Squeeze.

We have performed a thorough examination of the Squid source code of both versions andused all possible information from developer’s mailing lists to make a good decision.Although the development version’s new feature called Client streams was would probablymake our design more simple and easily implementable, we have finally chosen for the stableversion, in particular because of its stability. In addition, we have decided to design Squeezeas independent from the current Squid version as possible so that it is portable to the newversion of Squid in the future more easily.

The following section outlines the architecture of the stable version of the Squid Web cachingproxy server.

4.2 Squid Web Proxy Cache

Squid is a full-featured Web proxy cache designed to run on Unix systems but also was recentlyported to Windows environment. It is a free, an open-source software, the result of manycontributions by unpaid and paid volunteers.

4.2.1 Features

Squid is a high-performance proxy caching server for web clients, supporting FTP, Gopher,and HTTP data objects. The current stable version Squid is HTTP/1.0 capable proxy cachingserver with extensions.Unlike traditional caching software, Squid handles all requests in a single, non-blocking, I/O-driven process.Squid keeps meta data and especially hot objects cached in RAM, caches DNS lookups, sup-ports non-blocking DNS lookups, and implements negative caching of failed requests.Squid supports SSL, extensive access controls, and full request logging. By using the lightweightInternet Cache Protocol, Squid caches can be arranged in a hierarchy or mesh for additionalbandwidth savings.In addition to be a caching proxy server is Squid capable to run as surrogate when switchedto ”server accelerator” mode.

4.2.2 Architecture

Squid consists of a main server program squid, a Domain Name System lookup programdnsserver, some optional programs for rewriting requests and performing authentication, andsome management and client tools.When squid starts up, it spawns a configurable number of dnsserver processes, each of whichcan perform a single, blocking Domain Name System (DNS) lookup. This reduces the amountof time the cache waits for DNS lookups which are essential for Squid.


� � � � � � � � � � � � � � � ��

� � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � � �

� � � � � � � � � � �

� � � �

� � � � � � � � � � � � �

� � � � � � � � �

� � � � � � � � � � � � � � ��

� � � � � � � � � � � � � �

� � � � � � �

� � � � � � � � � � � � � � � � �

� � � � � � � � � � � �

� � � � � � � �

� � � � � �

! � � � � � � � � � �

� � � � � " � � � � � � �

# # # � � � � �� $ � �

�

� � � � � � � � � � � � � � � % � � � � � � �

� � �

� � � � � �

�

� � � � � �

� � � � � ��

� � � � � � � � � �

& � � � � � � � � �

� � � � � �

' � � � ( � � � �

) � � � � � � � ��

* �

� � � � � �� " � � � � � � �

� � � � � % � � � � � � �

� � � � � � � � � ��

�

� � � � � �

� � � ��

� � +

� � � � � �

� �

� � � � � �

� � � � � � �

, - � � � � � �

� � � � � � �

) � � � � � � � �

� � � � � � � � �

� � � � � � � � � ) � � � � � � � ��

+ � � � � � �

� � � � � ��

� � . � � � � � � . �

� - �

� � � � � �

, - �

� � � � � �

Figure 4.2: Squid proxy server high level architecture

Client Side

The Client Side, Server Side and Storage Manager are the most important parts of Squidserver program.All the communication with a client is taken place in client side such as request reading,parsing or response preparing and sending off.Per-connection state information is held in a data structure called ConnStateData and everyclient’s request is represented by clientHttpRequest structure.

Server Side

The Server Side is the part responsible for client request processing. It communicate withorigin servers or neighbor caches.

Storage Manager

The Storage Manager is the glue between Client and Server Sides. Every object saved in thecache is allocated a StoreEntry structure. While the object is being accessed, it also has aMemObject structure.Squid can quickly locate cached objects because it keeps a hash table of all StoreEntry ’s in


memory. The keys for the has table are MD5 checksums of the URL.For each object the StoreEntry maps to a cache directory and a cache swap file name. Acache swap file consists of two parts: the cache metadata, and the object data. Object dataincludes the full HTTP reply - headers and body.Client-side requests register themselves with a StoreEntry to be notified when new dataarrives. Multiple clients may receive data via a single StoreEntry. For POST and PUT HTTPrequest, this process works in reverse. Server-side functions are notified when additional datais read from the client.

Cache Manager

The Cache Manager provides access to certain information needed by the cache administratorsuch as cache utilization, hit ratio, number of connected users, etc.A companion program, cachemgr.cgi can be used to make this information available via aWeb browser.

Event Queue

Inside Squid is maintained a linked-list event queue for functions to be executed at a futuretime. The event queue is used for periodic functions such as performing cache replacement,cleaning swap directories, as well as one-time functions such as ICP query timeouts.

The Main loop

At the core of Squid is the select() system call. Squid uses select() or poll() to process I/Ooperations on all open file descriptors. Squid only checks for read and write events on filedescriptors and if any event occurs it call appropriate associated handler function.

Handler functions

File descriptor’s associated handlers are stored in fde structure. Squid holds fde structuresof open file descriptors in fd table array.Typical read handlers are httpReadReply(), diskHandleRead(), and icpHandleUdp(). Typicalwrite handlers are commHandleWrite(), diskHandleWrite(), and icpUdpReply(). In additionto read and write handlers there are close handlers, timeout and lifetime handlers.

I/O Model

Network communication is one of the slowest among other computer operations. In the tra-ditional server architecture there is a main program, which is launching a separate process orthread for conversation with each client. Client requests are handled asynchronously in eachprocess.Squid, in contrast handles all client requests in a single non-blocking process driven by I/O(networking and disk) operations.Sockets and files are represented by file descriptors so every network or file operation has thefile descriptor as a parameter. Among these operations the most important are of course readand write operations.


All network operations are non-blocking, the data is transferred to memory buffers asyn-chronously. When the network operation is over a completion routine call is scheduled. Thecompletion routines are callback functions.Although networking and disk I/O have much in common in Squid an implementation of themis separated. Network routines do not support queuing multiple blocks of data for writingwhereas disk routines do. Consequently, a callback occurs for every network write requestbut does not necessarily occur for every file write request.

Callback Functions

Because of the Squid design I/O blocking operations are implemented using callback functionsmechanism. Implementation of blocking operation consists typically from two phases, theinitiating and the callbacking one.In the first phase of operation Squid allocates a state structure (holding callback data andalso the name of the callback function to run when operation is complete) and scheduleslaunching execution of the operation (by setting the appropriate handler in file descriptor’sfde structure located in fd table array). Afterwards the initiating phase is over.When the control is returned to the Main loop open file descriptors are checked and associatedhandlers are called for file descriptors that are ready.The operation will start as soon as the previously set handler is called. This will start thesecond phase. The operation will not block because handler will not called before the filedescriptor will be ready. At the end of the handler the callback function is called and whenit is finished Squid will free state structure.

Memory Management

Because of extensive use of memory enable Squid support for memory pooling. To preventfrequent memory allocation Squid doesn’t free every unused memory block but keep it forfuture use. This may result in more efficient use of memory at the expense of a larger processsize.Squid allocate memory for holding object data in 4-KB chunks.

Memory Cache

Squid stores some of its recently retrieved objects fully in memory. It is done mainly becauseserving objects from memory is generally faster than reading data from the disk. This is alsocalled hot object cache.The current stable version of Squid stores objects in memory only if they come from network(from origin server or neighbor cache) and only objects smaller than a certain (adjustable inconfiguration file) size are held in memory.In-memory objects fall into one of two groups: in-transit and complete. In-transit object arethose just downloading from the network and complete object are those already downloaded.

Access Control

Access controls are the most important part of Squid configuration file. They can be used togrant access to authorized users, to restrict or prevent access to, certain material; to controlrequest rewriting; to route requests through hierarchy; and to support different qualities of


service.Access controls are built from two different components. First, it is necessary to define anumber of access control list (ACL) elements. These elements refer to specific aspects ofclient requests, such as IP addresses, URL hostnames, request methods, origin port numbers,and more. After defining the necessary elements, they can be combined into a number ofaccess list rules. The rules apply to particular services or operations3 within Squid.

Support for Cache Hierarchies

For cooperation with neighbor caches Squid implements an ICP protocol at version 2 and 3and HTCP protocol.

4.2.3 References

More about Squid can be found in [23], [22]. The installation and configuration is elaboratelydescribed in the latter.

The following section outlines the aspects of Squeeze design.

4.3 Squeeze Web Accelerator design and architecture

The Squeeze architecture is in a certain degree dependant on the Squid architecture shortlydescribed in section 4.2 and respects it.We have decided to accelerate an HTTP protocol traffic in Squeeze although Squid supportsmore protocols than just HTTP. However, the design was done in a protocol-independent wayso that there are no obstacles to a possible future extensions of Squeeze which would alsoenable an acceleration of other application layer protocols.

As can be seen on figure 4.3, Squeeze as well as Squid consist of a main server programand other optional components. In addition to these, Squeeze needs an SQL database serversupport for storing user’s information and statistics. Because there is no client side on auser’s computer we need another way of enabling users to change accelerator behavior andinspect the accelerator statistics, such as the amount of saved data. For this purpose, wehave decided to design and implement a Web-based graphical interface that can be accessiblethrough a Web browser.

4.3.1 Acceleration methods used

Data compression

Our decision to use the HTTP standard compression was given by the target architecture ofthe proposed accelerator.We designed a content encoding (CE) mechanism using a modified Squid framework. Forthis purpose we have decided to exploit the Zlib Compression Library. In Zlib, there is useda previously mentioned deflate algorithm and the library is able to output encoded data ingzip, deflate and compress format. All the mentioned formats were used in the design andimplementation of CE in Squeeze.

3For example, the http access rules are applied to incoming HTTP requests.


� � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � �

� � �

� � � � � � � � � � � � � � � � � �

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

� � � � � � � � � � �

� � ! � � � � � � � �

� � � � �

� � � � ! � � � � ! � �

� � � � � � � � �

� � � � � � � � � � � � � "� � � � � #

� � � � � � � � � � � � �

" � � � � � $

� � � � � � � � � � � � � � � � � �

� � � � � � � ! � �

% & & � � � � � � �

' & � � � � � � �

( � � � � � � � � � � �

� � � � ) � � � � � � �

* * * � � � � � �

� � � � ! � + !�

� � � � � � � � � � � � � � , � � � � � � �

% & & �

� � � � � �

' & �

� � � � � �

! � � � � ��

� � � � � � � � �

- � � � � � � �

� � � � � �

. � � � � � � �

/ � � � � � � ��

� � �

� � � � � �� ) � � � � � � �

� � � � , � � � � � � �

� � � � � � � � � � � � � � � � � �

' �

� � � � � �

� � � ��

� � �

� � � � � �

� �

� � � � � �

� � � � � � � �

� 0 � � � � � � �

� � � � � � � �

/ � � � � � � �

� � � � � � � �

� � � � � � � � �/ � � � � � � ��

� � ! � � � � �

� � ! ! � ��

� � � 1 � � � � 1 �

� 0 � �

� � � � � �

� 0 �

� � � � � �

� � �+ ��

* * *

� � � � � �

� � � � � � ��

� � � � � � �� .

� � � � � �

� � � � � � �� ! ��

� � � � � � ��

� � � � � � �' � � � ��

Figure 4.3: Squeeze Web accelerator high level architecture

Another mechanism, the transfer encoding (TE) mechanism was not implemented due tocomplete absence of support for this task from Squid. An attempt to implement TE in stableversion of Squid would require a complete rewriting of the whole Squid core.In terms of the HTTP protocol, Squid with a Squeeze module is a non-transparent proxycaching server.

Lossy and lossless image transformations

Image objects form the majority of all Web objects. According to our survey done on logsfrom Czech On Line, image objects represent more than a half of the total of the data transfervolume and about two thirds of all objects transferred.The majority of the image data is almost incompressible by conventional general compressionmethods. Thus, lossy image compression methods are usually applied to this data. For prac-tical reasons, it is profitable to focus on those image formats which represent the majority ofthe overall image data. These are the JPEG, GIF and PNG image formats.Lossy image transformations are also suitable in terms of the fact that image data are notalways a necessary part of Web pages for users. Often, the textual information is preferred byusers and images represent complementary and illustrative information. Because of the factthat image information is sometimes more important and other times less, it is reasonable to


implement several levels of lossy image transformations.

We have chosen the following transformations on image objects to be done:

• JPEG - Changing level of JPEG image compression. This is a lossy image transforma-tion. The transformation parameter can take HIGH (original quality image), MIDDLE(medium quality image), or LOW (low quality image) value.

• GIF - Reduction number of colors in image palette. This is a lossy image transformation.The transformation parameter can take any of the three values ranging from HIGH(original number of colors in image palette) to LOW (significantly reduced number ofcolors in image palette).

• PNG - Changing level of lossless compression of PNG image. PNG uses GZIP format.See 2.7.2. The transformation parameter can take any of the three values ranging fromLOW (PNG image remains unchanged) to HIGH (PNG image is recompressed with thegreatest level of GZIP lossless compression).

If during a transformation (except of the one preserving original image quality) the size ofimage is not lowered, the transformation is repeated using a more aggressive parameter. Ifafter the second transformation there is no saving, the same procedure is applied K−2 timeswhere K is server configuration parameter. If there is no saving even after K transformationsare done, Squeeze returns the unchanged original object. The parameter K is set to 3 bydefault, and it can be set for each image transformation individually.In addition to three levels of image transformation for every supported image format wedesigned a common transformation for them - the replacement of an image by a thumbnailof the size 1x1 pixel. In case of PNG and GIF format this thumbnail is transparent, in JPEGformat the color of the thumbnail is white. This transformation was designed for users whostrongly prefer textual information to the image one.

User-driven content blocking

Squid’s access control mechanism allows the administrator to define access lists to effectivelyblock downloading or serving of objects according to various parameters, such as contenttype, source or destination domain or IP address, content length or the time when the clientasks for it.We have decided to use the access control mechanism to implement a user-driven contentblocking. From this perspective the fact that only the server administrator can allow or blockobjects is the main disadvantage of the access control mechanism (because the settings affectall server users globally and not individually).We used an existing representation of access lists and we modified the access control frameworkto allow also the blocking of objects according to the individual user’s settings.The blocking of Flash objects was implemented in this way. For the purpose of Flash blockingthere are two MIME-type based access lists. The one, that allows to serve the object andthe other, denying it. According to the user’s settings the first one or the second one is thenapplied.From the administrator view, there is a mandatory access rule (http reply access type), thatmust be defined in the configuration file, and which selects Flash objects by MIME type andallows them. After starting the Squeeze server, this access list rule is parsed, and in this way


two (previously mentioned) access lists arise.Although this mechanism was used only for the Flash-object blocking, it is general and canbe also used for another type of content blocking, e.g. blocking of content from advertisementservers.

User-driven content filtering

In Squeeze design we have included a simple form of HTML filtering driven by regular ex-pressions.This transformation is designed only for simple filtering-out of unwanted parts of an HTMLfile like included JavaScripts, embedded objects, or images from advertising servers.For the implementation of this simple HTML filter we have used the GNU regex library be-cause it is already used in Squid (some access lists in the configuration file can be describedby regular expressions).Each HTML filter consists of the following three parts:

• bounds - this is a regular expression defining the bounds of the HTML string.

• condition - this is a regular expression that defines a substring that is searched in thebounds string. If it is successfully found, an HTML string defined by bounds is replacedby the replacement.

• replacement - this is a string used for the replacement of bounds string in case ofcondition match.

The possibility to define an HTML filter was given to the Squid administrator. The Squeezeuser can only set, whether an HTML filter should be applied as a whole or not at all.HTML filters can not be used for complex HTML filtering, whose implementation wouldrequire the use of an HTML aware parser.

Caching of compressed and modified data

We enable the caching of modified data in Squeeze if the original (not modified) object iscacheable (Squid complies to HTTP protocol caching).

[serialized STORE_META_STD TLV field (contains URL)]

HTTP/1.0 200 Internal marker object

Server: squid/2.5.STABLE9-20050331

Mime-Version: 1.0

Date: Mon, 15 Aug 2005 21:25:14 GMT

Content-Type: x-squid-internal/vary

Expires: Wed, 17 Aug 2005 01:11:54 GMT

Vary: negotiate,x-gif-palette

Figure 4.4: Squid cache file: internal marker object for varying gif image

For this purpose we modify the Server Content Negotiation algorithm used in Squid, addingmore dimensions in which objects can vary.On the figure 4.4 can be seen a Squid internal marker object that is used for signalling toSquid that a gif image (represented by URL field in STORE META STD) is varying and what


[serialized STORE_META_STD TLV field]

HTTP/1.0 200 OK

Server: thttpd/2.24 26oct2003

Content-Type: image/gif

Date: Mon, 15 Aug 2005 21:29:21 GMT

Accept-Ranges: bytes

Connection: close

Warning: 214 Squeeze "Transformation applied"

Content-Length: 11314

Vary: negotiate,x-gif-palette

X-Squeeze-Original-Reply-Size: 25081

Last-Modified: Mon, 15 Aug 2005 08:16:21 GMT

X-GIF-Palette: low

[GIF87a...modified gif image data...]

Figure 4.5: Squid cache file: Squeeze modified (varying) gif image

are the vary dimension (in this case it the x-gif-palette header). On the figure 4.5 can beseen the instance of a varying gif image object and the presence of X-GIF-Palette: lowheader signalizes that for this image the GIF palette reduction transformation was applied.Both these objects are stored in Cache as Cache files.The HTTP headers we have defined for the purpose of increasing the dimensions, in which aparticular object can vary, are as follows:

• X-JPEG-Quality - for storing Squeeze modified JPEG image of different quality levels.

• X-GIF-Palette - for storing Squeeze modified GIF image with a different number ofcolor in palette.

• X-PNG-Comp-Level - for storing Squeeze compressed PNG image with different com-pression levels.

• X-Squeeze-Filter - for storing varying instances of Squeeze filtered HTML page.

Also, we have used the existing Content-Encoding header for storing instances of ContentEncoding varying objects.If any object is modified by Squeeze, the appropriate header (according to its type and thetransformation applied) is added to this object.Also, if the reply from the origin server bringing the object contains any of the followingheaders, it is necessary to modify them.

• Vary - Value of this header is a list of all dimensions in which the object is varying.If the header is present in the origin server reply and Squeeze is modifying the object,it also adds name of an appropriate header (see the list above). If the header is notpresent, Squeeze will add it.

• ETag - If the origin server reply has this header, Squeeze changes its value by adding asuffix to it (according to transformation applied).

• Content-Length - The value of this header is the length of the modified object.

For the purpose of gathering Squeeze statistics we store the original reply size along with themodified (and possibly cached) object as the the value of X-Squeeze-Original-Reply-Size


header.The newly added headers in reply increase the length of the reply sent to client not morethan by tens of bytes.

4.3.2 Squeeze Server

Similarly to Squid, the Squeeze’s main server program is one single non-blocking process. Themain idea of the program was preserved.

Flow of typical Squeeze request

For the flow of typical Squeeze request look at the figure 4.6, and also the figure 4.3.

1. A client connection is accepted by the client-side. The HTTP request is parsed.

2. The access controls are checked. The client-side builds an ACL state data structureand registers a callback function for the notification when access control checking iscompleted. If the client is not authentized, Squeeze asks for it by sending an ”HTTP407 Proxy Authentication Required” response message.

3. After the access controls have been verified, the client-side loads the user’s settings fromSqueezeUser module and looks for the requested object in the cache. If there is a cachehit, then the client-side registers its interest in the StoreEntry. Otherwise, Squeezeneeds to forward the request, in same cases with an If-Modified-Since header.

4. The request-forwarding process begins with the peer selection procedure, which mayinvolve sending ICP queries and receiving ICP replies. The peer selection procedure alsoinvolves the checking of configuration options such as never direct and always direct.

5. When the ICP replies (if any) have been processed, the request is passed to the HTTPmodule.

6. The HTTP module first opens a connection to the origin server or the cache peer.If there is no idle persistent socket available, a new connection request is given to theNetwork Communication module (Comm module) with a callback function. The Commmodule routines may try establishing a connection multiple times before giving up.

7. When a TCP connection has been established, the HTTP module builds a request bufferand submits it for writing on the socket. It then registers a read handler to receive andprocess the HTTP reply.

8. After the reply is received for the first time, the HTTP reply headers are parsed andplaced into a reply data structure. At this moment Squeeze will decide if the object fromreply is modifiable or not. If that is the case, it also selects an appropriate transformationand creates another StoreEntry structure for the modified object. Each time reply datais read, they are appended to the original StoreEntry and possibly to the modifiedStoreEntry structure.

9. If the object is not modifiable, every time data is appended to the StoreEntry, theclient-side is notified of the new data via a callback function.


��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

�� !"�# $%"#&

MISS HIT

MODIFIABLEOBJECT

UNMODIFIABLEOBJECT

UNCACHEABLEREFRESH

CACHEABLE

REQUESTREPLY

FORWARDEDREQUEST

ORIGINALREPLY

TRANSFORMATION

TRANSFORMATION

TRANSFORMATION

Figure 4.6: Flow of typical Squeeze request

10. If the object is modifiable, the buffering of StoreEntries is switched on, and the client-side is not notified until the whole reply arrives and is transformed4. After the whole re-ply arrives, SqueezeCommon module is notified. It loads user’s settings from SqueezeUsermodule and starts the transformation (already selected) with appropriate parameters(taken from user’s settings). After the transformation is finished, it possibly registersthe object’s StoreEntries for caching (if the original object is cacheable), swaps theStoreEntries in order to send the modified StoreEntry to client instead of the originalone, switches off the StoreEntry buffering, and notifies the client-side.

4Note that Squeeze is a proxy caching server with Store-Forward architecture. This is due to the fact thatsome object transformations are not stream-oriented and can be done on a whole object only


11. After the client-side is notified of new data, it copies the data from the StoreEntry andsubmits it for writing on the client socket.

12. After data are appended to the StoreEntry, and the client reads it, the data may besubmitted for writing on the disk.

13. When the HTTP module finishes reading the reply from the upstream server, it marksthe StoreEntry as ”complete.” The server socket is either closed or given to the persistentconnection pool for future use.

14. When the client-side has written all of the object data, it unregisters itself from theStoreEntry. At the same time it either waits for another request from the client, orcloses the client connection.

Squeeze transformation selection algorithm

All the transformations on objects are done on the principle of object content-type detectionand the triggering of one or more appropriate actions.The appropriate actions are chosen among the standard content encoding, lossy and losslesscompression of images, content blocking, and HTML content filtering actions.

Object variants

Squid saves cached objects to serially number-named files in cache. Inside a memory theobjects are represented by StoreEntry structures. These StoreEntries are quickly accessiblethrough a hashing table using MD5 checksums of the object’s URL as the key to the hashingfunction.If the cached object is varying then the index to hashing table is returned by the hashingfunction with MD5(HTTP METHOD, object’s URL) as parameter, and it refers to an ”In-ternal Marker Object” instead of the object itself (see 4.4).If Squeeze is looking for some cached object and gets ”Internal Marker Object” instead of itduring the processing of a request from the client, then it knows that the object is varyingand a proper object variant must be selected for sending to the client.The proper variant of the asked object can then be found on the position returned by thehashing function with MD5(HTTP METHOD, object’s URL, and the concatenation of valuesof client’s request headers in which an object is varying) as the key.Our modification to the Server Content Negotiation algorithm is composed of the definitionof new vary dimensions and the modification of the object selection mechanism.

User’s settings

Squeeze user’s settings include options of turning on or off some transformations or changingtheir parameters. User’s settings are stored in SQL database and can be changed throughGUI by user.The accessing of the database every times Squeeze needs user settings5 could have a negativeimpact on Squeeze performance, we decided to cache the settings of the recently accessedusers in memory6. The records are accessible through the hash table with a username as a

5It is defacto in every request made by user.6Access to database is much slower than memory access and the record with user settings is rather small


parameter to the hashing function. Records of passive users are periodically garbage-collected(using a LRU-based algorithm) and freed from memory.Because the changes of user’s settings in database can be done asynchronously to Squeezeserver, it has to synchronize memory-cached structures with the database. During synchro-nization it is checked if any user changed his/her settings and if so, only these user’s settingsare synchronized. The synchronization period can be set in the configuration file and is bydefault 1 second.

Gathering the statistic data

During the Squeeze operation, the statistic data are gathered about transferred data to client,saved data, cache efficiency, etc., on a user-individual basis.This information is then stored in the SQL database.To prevent an excessively frequent access into the database that could affect the performanceof Squeeze, it stores the gathered data only if the volume of transferred data to client exceedsthe reasonable value (default value is 100KB). See T STATISTICS QUEUE in 4.3.3.

Logging

In order to enable the administrator to monitor Squeeze efficiency through logs, we added acolumn into the Squid log representing the original size of object (before it was modified) justbehind the actual size of the object (size of the modified object). If the object is unmodified,administrator recognizes it by the same value of both these columns.Because there are many cache analyzers for Squid available that use native Squid format,we have also written an AWK script for transforming the Squeeze log file back to the nativeSquid log file.

User authentication

The access control mechanism is used in Squeeze on two places: for accessing the acceleratoritself and for accessing the GUI.We have decided to use the HTTP Basic access control because this is not the only securityaccess mechanism used in Squeeze7 and it can be simply implemented.Inside the server, we used an original Squid authentication framework to get the user infor-mation where it was necessary. Thus, if there is for example a need for an access control basedon the HTTP Digest authentication it can be implemented in the future without a biggermodification of the Squeeze server.

4.3.3 Squeeze Database

Squeeze database model consists from the the following tables:

• T USER SETTINGS - holding Squeeze user’s settings. Each user is represented byexactly one row in this table.

• T USER STATISTICS - holding Squeeze user’s statistics. Each user is represented byexactly one row in this table.

7IP address range or domain address checking can be applied to control the access.


• T UPDATE QUEUE - holding IDs (keys from T USER SETTINGS) of users thatchanged their settings. Each user ID can be stored maximally once. If there is al-ready a record for the user inserted it is rewritten.

• T STATISTICS QUEUE - holding Squeeze user statistics updates. Each row of thistable represents a chunk of statistic for a particular user.

4.3.4 Squeeze Graphical User Interface

The main objective of the GUI design was to enable the user to set various levels of Squeezetransformations and to inspect savings from Squeeze. Thus, we have decided to take a simpleWeb-based GUI.User access to GUI requires the user to successfully authenticate himself/herself. The HTTPBasic authentication method is used.

4.4 Squeeze Web Accelerator implementation

Squeeze was implemented as an accelerator with proxy server8 architecture based on the SquidWeb Proxy Cache Server. Squeeze was designed to accelerate the World Wide Web Internetservice.

4.4.1 Libraries used

For the accelerator implementation we used the following libraries:

• Zlib Compression Library is free, an open source compression library (see [38]).It provides in-memory compression and decompression functions, including integritychecks of the uncompressed data.

• libpng library is the official PNG reference library (see [39]). It supports almost allPNG features.

• GD Graphics Library is an open source code library for dynamic creation of imageswritten in C (see [40]). GD creates PNG, JPEG and GIF images, among other formats.GD is commonly used to generate charts, graphics or thumbnails on the Web.

4.4.2 Squeeze Server

On the figure 4.3 can be seen newly implemented server modules yellow highlighted and themodules that had to be rewritten to make Squeeze functional are blue colored. Compare withthe figure 4.2.

Mandatory user authentication

Squeeze server process requests on demand of authenticated user only. Authentication ismandatory. When the accelerator is accessed it sends ”HTTP 407 Proxy AuthenticationRequired” HTTP response message to signal the browser that positive identification is nec-essary to get any other response. Username token acquired from authentication is then used

8In the HTTP protocol terminology, Squeeze is a non-transparent proxy caching server.


for logging purposes and for accessing user settings.On the figure 4.7 can be seen the typical way how is the Squeeze user asked to authenticateitself to the accelerator.

Figure 4.7: User authentication to Squeeze Web accelerator from Internet Explorer Webbrowser

4.4.3 Squeeze Database

The MySQL database server was selected as a storage for Squeeze user settings and statisticaldata. For more information about MySQL database server see [41].Proper connection details have to be set in Squeeze server configuration file or the server doesnot start complaining about it.

4.4.4 Squeeze Graphical User Interface

Squeeze GUI was implemented using PHP as simple as possible. It consists from the twopages. The figure 4.8 is showing main page of Squeeze GUI and the figure 4.9 is showing pagewith user statistics.The main page can be used to set the parameters of Squeeze Accelerator transformations; toset the JPEG quality, GIF palette size, PNG compression, to enable blocking Flash blockingand to enable HTML content filtering. It also inform the authenticated user what the CEmethod his/her browser uses.The page with statistics, reachable from the main page through the ”Show statistics” button,shows the size of downloaded data, the cache efficiency and the data saved for the user bythe accelerator.


Figure 4.8: Squeeze GUI main page Figure 4.9: Squeeze GUI page with statis-tics

4.4.5 Squeeze compatible user agents

Squeeze can be used by common browsers or any other user at least HTTP/1.0 capableagents. To benefit from connection to Squeeze a compatible user agents must implementHTTP protocol at version HTTP/1.0 or HTTP/1.1 and understands any of gzip, deflate orcompress content encodings. It also should support persistent connections.To see today’s the most popular browsers that are compatible with Squeeze look at table B.1.

4.5 Conclusion

The tested version of Squeeze has a limitations in modifying only the responses with Content-Length header. The responses without this header are left as they are. We implemented anew version without this limitation, but it was not stable enough at the time of testing thuswe do not compare it with CProxy accelerator. Removing this limitation improve Squeezeperformance particularly on dynamically generated (not buffered) pages.The current Squeeze architecture could have a performance limitations when more compli-cated transformations would be applied due to single process core. If the core would berewritten to support parallel thread executions from main flow, we could use the advantageof multiprocessors performance for faster transformations.There can be easily written a program for server side (server hint) prefetching selecting themost demanded data by analyzing the server logs. Maybe it already exists such.Squeeze is able to work as an accelerator - proxy server. If it will be slightly modified it isable to work as an accelerator - surrogate.If the client proxy would be implemented, the users with such client proxy installed would beable to benefit from another forms of effective data compression (e.g. differential compres-sion). Other Squeeze clients would get common proxy response.

Chapter 5

RESULTS AND DISCUSSION

This chapter provides the reader with information about testing methodology and to presentthe obtained results.

5.1 Performance tests

The objective of Performance tests was to simulate a maximum load Squeeze can handle. Wewanted to make sure our design and pilot implementation of transformations are not breakingSquid performance.We have made two tests. The objective of the first test (Performance Test 1) was to findthe maximal load that Squeeze handled, and the second one (Performance Test 2) tested theSqueeze behavior when have been loaded near this limit value and the ability recover whenthe load decrease.

5.1.1 Test hardware and software

Clients

See the table 5.1.

Table 5.1: Performance tests - client setupHardware 10 x PC (Intel Celeron 850 Mhz, 256 MB RAM, CD,

20 GB PATA HDD, 100Mbit FastEthernet card)Software Windows 2000 Professional, Internet Explorer 5.5Test tool Wget (1.9.1)

Squeeze Server

See the table 5.2.

69

CHAPTER 5. RESULTS AND DISCUSSION 70

Table 5.2: Performance tests - Squeeze server setupHardware 1 x PC (Intel P4/Xeon 3.2 GHz, 2 GB RAM (400 MHz),

20 GB/2MB cache PATA HDD, 100Mbit FastEthernet card)Software Linux Fedora Core 2 (2.6.5-1.358 SMP kernel, EXT3 filesystem),

MySQL Database Server (3.23.58),Apache Web Server (2.0.51) with PHP (4.3.10),

Squeeze Web Accelerator (0.1)

5.1.2 Performance Test Scenario

Performance Test 1

The Performance Test 1 test was planned to incrementally add load to Squeeze until we reachthe maximum it can handle. For the test scenario look at the table 5.3.

Table 5.3: Performance Test 1: ScenarioSimulated users 100Requests in user scenario 50.000Maximum requests in test 5.000.000Planned test duration till server fall down (max 6 hours)

Performance Test 2

The Performance Test 2 was planned to run in the four following phases:

• Incremental loading the server until the near value to the maximum load (obtained inPerformance Test 1). As soon as the server show symptoms of overloading, we switchto next phase.

• Five minutes break to let the server empty queues and buffers. Switch to next phase.

• Continuing to fill the accelerator cache to until becomes (almost) full with 70% of theusers. After that, we switch to the next phase.

• Lowering the load and continuing with only 20% of the users until end of the test andmonitoring Squeeze.

For the test scenario look at the table 5.4.

5.1.3 Accelerator settings

Squeeze server

The main options affecting Squeeze accelerator performance was set like shown in the table5.5 in the Squeeze-modified squid.conf file.


Table 5.4: Performance Test 2: ScenarioSimulated users 100Requests in user scenario 50.000Maximum requests in test 5.000.000Planned test duration 150 minutes

Table 5.5: Performance tests - Squeeze accelerator server settingsserver config settingscache mem 8MBmaximum object size 4MBminimum object size 0KBmaximum object size in memory 8KBmemory replacement policy lrucache dir aufs 1024 MB (16/256 directories)transformation settingsSqueeze CE text object ONSqueeze CE application object ONSqueeze IT JPEG object ONSqueeze IT GIF object ONSqueeze IT PNG object ONSqueeze max modifiable object size 4MBSqueeze min modifiable object size 2KB

Clients

The client accelerator options was set through Web GUI like in the table 5.6.

5.1.4 Results

Performance Test 1

The length of Performance Test 1 test was negatively affected by an improper auto-configurationbehavior of Ethernet card and associated switch. Thus from the beginning of the test thenetwork interface run in 10MBit half-duplex mode. After recognizing this, the problem wasfixed. In less than half hour later was the Squeeze server overloaded.The results of the Performance Test 1 test can be found in the table 5.7.

Performance Test 2

The results of the Performance Test 2 test can be found in the table 5.8.For more information about the progress of the test, see the performance graphs in sectionC.1 in appendix.


Table 5.6: Performance tests - Squeeze accelerator client settingstransformation settingsContent Compression ONJPEG quality MIDDLEPNG compression MIDDLEGIF palette size MIDDLEFlash blocking ONAds filtering OFF

Table 5.7: Performance Test 1: Squeeze accelerator resultsTest duration 4:05:03Maximum data flow reached over 11 MbpsMaximum amount of network traffic read from clients 114,9 KB/sMaximum amount of network traffic written to clients 1408 KB/sTotal number of HTTP requests arrived 330 000

Table 5.8: Performance Test 2: Squeeze accelerator resultsTest duration 2:30:00Maximum data flow reached over 11 MbpsMaximum amount of network traffic read from clients 110,9 KB/sMaximum amount of network traffic written to clients 1384.3 KB/sTotal number of HTTP requests arrived from clients 932 048Average Total size of the original data requested by a client 62169,4 KBAverage Total amount of HTTP traffic transferred to a client 38611,9 KBAverage percentage of data saved by Squeeze 37,89%


5.2 Comparative test

The objective of Comparative test was to compare Squeeze with an existing accelerator. Wehad an opportunity to compare Squeeze with the CProxy accelerator operated by Czech OnLine ISP.

5.2.1 Test hardware and software

Clients

See the table 5.9

Table 5.9: Comparative Test: client setupHardware 5 x PC (Intel Celeron 850 Mhz, 256 MB RAM, CD,

20 GB PATA HDD, 100Mbit FastEthernet card)Software Windows 2000 Professional, Internet Explorer 5.5,

CProxy ClientTest tool Wget (1.9.1)

Squeeze server

Squeeze Server test hardware and software configuration was identical to the in PerformanceTests, see table 5.2.

CProxy Server

See the table 5.10

Table 5.10: Comparative Test: CProxy server setupHardware 2 x PC (N/A)Software Windows Server

mSQL Database ServerCProxy Server proxy

5.2.2 Test scenario

Test scenario of the Comparative Test test can be found in 5.11.

5.2.3 Accelerator settings

Clients - Squeeze

See the table 5.12.


Table 5.11: Comparative Test: Test scenarioSimulated users 10Requests in user scenario 10.000Maximum requests in test 100.000Planned test duration till all requests processed

Table 5.12: Comparative Test: Squeeze accelerator client settingstransformation settingsContent Compression ONJPEG quality HIGHPNG compression HIGHGIF palette size HIGHFlash blocking ONAds filtering OFF

Clients - CProxy

See the table 5.13.

Table 5.13: Comparative Test: Cproxy accelerator client settingstransformation settingsContent Compression ONJPEG compression MAXIMUMGIF compression MAXIMUMHTML optimization ONFlash blocking ONAds filtering ONClient caching ON (64MB cache)

Clients - Wget

We have noticed that the Wget behavior was problematic if the combination of the http keep aliveand use proxy was both switched on. Unfortunately, Wget was unable to create a persistentconnection through proxy.Wget settings can be found in 5.14.

5.2.4 Results

The following notes shortly explains the results:


Table 5.14: Comparative Test: Wget test tool settingsconnect timeout 30 shttp keep alive offignore length ONuse proxy ONread timeout 30 srobots OFFtimestamping ONtries 2wait 0waitretry 10

• It is necessary to note, that data counted by Wget in case of CProxy results are al-ready uncompressed. Because CProxy uses proprietary compression method, it has todecompress the data before it passes it to the client.

• The saved data by Squeeze was counted as the ratio of the total data transferred fromInternet to Squeeze to the total data transferred by Squeeze to the clients.

• The exact amount of blocked content cannot be calculated because both the acceleratorsdo not download the blocked data. Thus, they are not able to determine the exact sizeof the content in the case of the Content-Length header is missing or it is holding abad value.

• CProxy counts data below the application-protocol layer, Squeeze on the application-protocol layer.

• Although the total amount of downloaded data from the Internet is lower in case ofCProxy (particularly because of employing of the client proxy content blocking andcaching mechanisms), the total amount of downloaded data by clients from the CProxyclient proxy is bigger. We noticed that CProxy is removing Last-Modified header fromsome responses. This explains the disparity between the number of downloads made byWget in case of the CProxy usage and the case of the Squeeze usage.It is necessary to note, what mechanism is used to determine if the object in its cacheis fresh or not by Wget. The mechanism is called time-stamping and it is implementedby checking of the Last-Modified header. If the file does exist locally, Wget will firstcheck its local time-stamp, and the send a HEAD request to the proxy, demanding theinformation on the remote file. The Last-Modified header is examined to find whichfile was modified more recently (which makes it ”newer”). If the remote file is newer, itwill be downloaded; if it is older, Wget will give up. In this version of Wget is done anadditional check, Wget look at the Content-Length header, and compare the sizes; ifthey are not the same, the remote file is downloaded no matter what time-stamp says.

• The other possible explanation of the bigger amount of saved data by Squeeze can bethe more aggressive (lossy) compression in case of the Squeeze usage. We had no closerinformation about the methods used in CProxy to be able to validate this supposition.


In the tables 5.15 and 5.16 can be found the following symbols representing the informationsource from which was the results obtained.

• (C) - Cproxy statistics

• (S) - Squeeze logs

• (W) - Wget logs

CProxy

CProxy results can be found in the table 5.15.

Table 5.15: Comparative Test: CProxy accelerator resultsparameter value sourceTest duration 2:44:11 (W)Total number of HTTP requests sent to CProxy N/ATotal number of downloaded files from requests 72293 (W)Total number of downloaded data by clients 506,67 MB (W)(exclude headers and responses without body)Total number of downloaded data by clients 469,65 MB (C)(include headers and responses without body)Total size of original data downloaded by CProxy 614,16 MB (C)Saved data by CProxy 23,5 % (C)

Squeeze

Squeeze results can be found in the table 5.16.For more information about the progress of the test, see the performance graphs in sectionC.2 in appendix.For a more detailed results of tests carried out or an up-to-date information about Squeezesee the [46].

Structure of original HTTP objects

The table 5.17 shows HTTP objects sorted by MIME-types which were downloaded fromInternet by Squeeze.


Table 5.16: Comparative Test: Squeeze accelerator resultsparameter value sourceTest duration 2:08:28 (W)Total number of HTTP requests sent to Squeeze 111546 (S)Total number of HTTP requests forwarded to 70350 (S)origin servers by SqueezeTotal number of downloaded files 47088 (W)by clients from requestsTotal number of downloaded data by clients 332,37 MB (W)(exclude headers and responses without body)Total number of downloaded data by clients 397,97 MB (S)(include headers and responses without body)Total size of original data downloaded by Squeeze from Internet 627,18 MB (S)(include headers and responses without body)Number of cache hits from the total number 39271 (S)of HTTP requests sent to SqueezeCache hit ratio 35,2 % (S)The volume of transferred data 17,86 MB (S)to clients in cache hitsCache byte hit ratio 4,27 % (S)Saved data by Squeeze 36,55 % (S)


Table 5.17: Comparative Test: Structure of HTTP object types downloaded from Internetby Squeeze

MIME type value itemapplication/* 2091 Total number of HTTP requests sent to Internetapplication/* 31,19 MB Total volume of downloaded data from repliesaudio/* 43 Total number of HTTP requests sent to Internetaudio/* 290,52 MB Total volume of downloaded data from repliesimage/gif 19202 Total number of HTTP requests sent to Internetimage/gif 42,56 MB Total volume of downloaded data from repliesimage/jpeg 18021 Total number of HTTP requests sent to Internetimage/jpeg 137,04 MB Total volume of downloaded data from repliesimage/png 513 Total number of HTTP requests sent to Internetimage/png 2,78 MB Total volume of downloaded data from repliestext/* 25570 Total number of HTTP requests sent to Internettext/* 112,46 MB Total volume of downloaded data from repliesvideo/* 3 Total number of HTTP requests sent to Internetvideo/* 7,88 MB Total volume of downloaded data from repliesother 4907 Total number of HTTP requests sent to Internetother 2,75 MB Total volume of downloaded data from replies*/* 70350 Total number of HTTP requests sent to Internet*/* 627,18 MB Total volume of downloaded data from replies

Chapter 6

CONCLUSION

In this thesis, we analyzed various approaches that can be used for the acceleration of HTTPprotocol transmissions. We have examined the caching, HTTP standard compression, lossyimage compression, the content blocking and the filtering of HTTP data.

With a growing number of dynamic web sites the efficiency of caches is decreasing. Thisis not only given by the non-persistent character of dynamic web sites, but often also by a de-liberate prevention of caching objects by web designers and server administrators. Although,this method is still up-to-date especially in the case of cache hierarchy usage, it is necessaryto look for further (more efficient) methods.Thus, we have inspected the possible savings offered by the data compression methods.

We have examined the features of commercial connection accelerators and have testedsome of them. We were searching for an open-source solution that would be comparable tocommercial accelerators. We discovered that there is a such connection accelerator missing.

As the result of our investigation, we designed and implemented Squeeze - an open-sourceconnection accelerator based on the popular Squid proxy server.In Squeeze, we have decided to compress both the textual and non-textual objects using theHTTP standard compression and the lossy image compression methods. We have especiallyfocused on the lossy image compression, because image data represent the majority of thedata transmitted on the Web and because of the lossy way of gaining these data. Otherfurther suitable ways of lossy compression want do any harm. On the contrary, they oftenlead to a significant decrease of the data volume. Because the losses caused by lossy imagecompression are not exactly measurable and are acceptable from the user perspective to avarious degree, it is necessary to give the user a choice between several levels of image dataquality.We decided to cache the compressed data in order to save the CPU time of the server which isunnecessarily spent on a repeated compression of already compressed objects. We examinedthe possibility and efficiency of a user-driven blocking of objects in Squeeze and we made apractical test when we implemented the Flash-objects blocking mechanism. We also designedand implemented the simple HTML content filtering to Squeeze.

It appeared to us that because of Squid’s non-traditional architecture, the use of the

79

CHAPTER 6. CONCLUSION 80

Squeeze module could lead to a more significant decrease of performance of the Squid server.Thus, We carried out the performance test to prove or disprove it. It turned out during thetest that in spite of certain performance decrease of the server, the operability of the serverwas preserved.In the comparative test, we compared Squeeze to a commercial accelerator. The carried outtest showed us the advantages and the limits of our solution.

Although the results shown that our implementation is stable and delivers significant sav-ings under real world scenarios there is a space for the future improvements.

If we implement Squeeze as a module to a development version of the Squid server, thiswill not only lead to a simplier Squeeze source code and an easier integration into the server,but also to an easier implementation of transformations, such as transfer encoding.The tests also shown that it is important to focus on the user-driven blocking of advertise-ment. Given the fact the blocking of advertisement data on the server’s side can not eliminatea certain overhead (the reply must be sent that the data have been blocked), it would be moreeffective to implement user-driven blocking on the client side. If the client side is implementedit would be also possible to use of other methods of lossless data compression (e.g., differentialcompression).Even though we have not dealt with the prefetching method in this thesis in much detail,it is possible to add easily a server side prefetching to the Squeeze-module equipped Squidin order to increase the cache hit ratio. For the Squid server there are different programsavailable which enable prefetching on the basis of the Squid log parsing. For a more efficientuse of active caching it would be necessary to employ the client local-based prefetching as issuggested in [20].The Internet Content Adaptation Protocol may also present a way how to modify and possi-bly compress the data. However this possibility has not been examined within this thesis.

We believe that the use of Squeeze can be a beneficial especially for the ISPs that operatethe Squid Web Caching server, to help them accelerate the slow connection technologies andto solve the issues we have pointed to in the beginning of this thesis.

Appendix A

Glossary

The following terminology provides definitions of common terms used within scope of thisthesis. Base terms are taken, where possible, from HTTP/1.1 specification [2]. Standardterminology and the taxonomy of web replication and caching infrastructure deployed in theInternet today can be found in [5].

A.1 Base terms

Most of these terms are taken as-is from HTTP/1.1 specification [2], and are included herefor reference.

• client (taken from [2])A program that establishes connection for the purpose of sending requests.

• server (taken from [2])An application program that accepts connections in order to service requests by sendingback responses. Any given program may be capable of being both a client and a server;our use of these terms refers only to the role being performed by the program for aparticular connection, rather than to the program’s capabilities in general. Likewise,any server may act as an origin server, proxy, gateway, or tunnel, switching behaviorbased on the nature of each request.

• proxy (taken from [2])An intermediary program which acts as both a server and a client for the purpose ofmaking requests on behalf of other clients. Requests are serviced internally or by pass-ing them on, with possible translation, to other servers. A ”transparent proxy” is aproxy that does not modify the request or response beyond what is required for proxyauthentication and identification. A ”non-transparent proxy” is a proxy that modi-fies the request or response in order to provide some added service to the user agent,such as group annotation services, media type transformation, protocol reduction, oranonymity filtering. Except where either transparent or non-transparent behavior isexplicitly stated, the HTTP proxy requirements apply to both types of proxies.

Note: The term ”proxy server” is in context of this thesis sometimes used as a syn-onym of proxy.

81

APPENDIX A. GLOSSARY 82

• cache (taken from [2])A program’s local store of response messages and the subsystem that controls its mes-sage storage, retrieval, and deletion. A cache stores cacheable responses in order toreduce the response time and network bandwidth consumption on future, equivalentrequests. Any client or server may include a cache, though a cache cannot be used bya server that is acting as a tunnel.

Note: The term ”cache” used alone often is meant as ”caching proxy”.Note: There are additional motivations for caching, for example reducing server load(as a further means to reduce response time).

• cacheable (taken from [2]A response is cacheable if a cache is allowed to store a copy of the response messagefor use in answering subsequent requests. The rules for determining the cacheabilityof HTTP responses are defined in section 13 of [2]. Even if a resource is cacheable,there may be additional constraints on whether a cache can use the cached copy for aparticular request.

• gateway (taken from [2]A server which acts as an intermediary for some other server. Unlike a proxy, a gatewayreceives requests as if it were the origin server for the requested resource; the requestingclient may not be aware that it is a communication with gateway.

• tunnel (taken from [2])An intermediary program which is acting as a blind relay between two connections.Once active, a tunnel is not considered a party to the HTTP communication, thoughthe tunnel may have been initiated by an HTTP request. The tunnel ceases to existswhen both ends of the relaying connections are closed.

• Internet service provider (ISP) (taken from [24])An Internet service provider (ISP) is a business or organization that offers access to theInternet and related services. They provide services such as Internet transit, domainname registration and hosting, dial-up access, leased line access and colocation.Most telecommunications operators are ISPs.

• content consumerA person who employs the services provided by ISPs to consume or to influence theInternet content.

• userSee ”content consumer”.

• consumerSee ”content consumer”.

A.2 Base-derived terms

• origin server (taken from [2])The server on which a given resource resides or is to be created.


• user agent (taken from [2])The client which initiates a request. These are often browsers, editors, spiders (web-traversing robots), or other end user tools.

• caching proxy (taken from [5])A proxy with a cache, acting as a server to clients, and a client to servers.

Caching proxies are often referred to as ”proxy caches” or simply ”caches”. The term”proxy” is also frequently misused when referring to caching proxies.

• surrogate (taken from [5])A gateway co-located with an origin server, or at a different point in the network, dele-gated the authority to operate on behalf of, and typically working in close co-operationwith, one or more origin servers. Responses are typically delivered from an internalcache.

Surrogates may derive cache entries from the origin server or from another of the originserver’s delegates. In some cases a surrogate may tunnel such requests.

Where close co-operation between origin servers and surrogates exists, this enablesmodifications of some protocol requirements, including the Cache-Control directives in[1]. Such modifications have yet to be fully specified.

Devices commonly known as ”reverse proxies” and ”(origin) server accelerators” areboth more properly defined as surrogates.

• reverse proxy See ”surrogate”.

• server accelerator See ”surrogate”.

• browser (taken from [5])A special instance of a user agent that acts as a content presentation device for contentconsumers.

A.3 Cache-topology terms

The following definitions are added to describe caching device topology:

• user agent cache (taken from [5])The cache within the user agent program.

• local caching proxy (taken from [5])The caching proxy to which a user agent connects.

• intermediate caching proxy (taken from [5])Seen from the content consumer’s view, all caches participating in the caching meshthat are not the user agent’s local caching proxy.

• cache server (taken from [5])A server to requests made by local and intermediate caching proxies, but which doesnot act as a proxy.


• cache array (taken from [5])A cluster of caching proxies, acting logically as one service and partitioning the resourcename space across the array. Also known as ”diffused array” or ”cache cluster”.

• caching mesh (taken from [5])”a loosely coupled set of co-operating proxy- and (optionally) caching-servers, or clus-ters, acting independently but sharing cacheable content between themselves using inter-cache communication protocols.

A.4 Accelerators

• Connection acceleratorA program, that uses various methods and techniques for the effective utilization ofconnection resources to make the most of the Internet connection. In other words, thegoal of the accelerator is to maximize the transferred information and to minimize thecost of the transmission.

• AcceleratorSee the ”Connection accelerator”.

• Data Compression method (also compression method) is a general term for the tech-nique or the way how to achieve elimination of data redundancy. This is typically themost important method used by connection accelerators.

Appendix B

What can affect performance ofWeb Accelerator

B.1 Modems

A modem is a device that modulates an analog carrier signal (e.g. sound), to encode digi-tal information, and that also demodulates such a carrier signal to decode the transmittedinformation. The goal is to produce a signal that can be transmitted easily and decoded toreproduce the original digital data.Modems are one of main gadgets used in various communication technologies used in today’scomputer network systems.

We can divide modems into some categories by the way the signal is encoded/decoded andtransmitted.

• Analog modems

• Wireless modems

• Broadband modems

More on this topic can be read e.g. in [24].

B.1.1 Modem compression

It is well known that data compression plays a significant role when using a modem connec-tion for data transmissions. Because the presence of noise is a natural attribute of networkcommunication there are error correction protocols that comprise a inseparable pair withmodem compression protocols.While the goal of compression protocols is to decrease data redundancy during transmissionthe error correction protocols bring back some redundancy in order to detect the badly trans-mitted data and to retransmit them automatically.In the area of classic analog modems we can meet with the following standards:

• V.42 is an error correction protocol used with conjunction with the V.42bis protocol.

85

APPENDIX B. WHAT CAN AFFECT PERFORMANCE OF WEB ACCELERATOR 86

• V.42bis is an adaptive data compression protocol. It uses the adaptive of LZW algo-rithm.

• V.44 is an adaptive data compression protocol incorporated into the V.92 dial-up modemstandard. V.44 is based on LZJH1 compression technology and offers better compressionperformance than the older V.42bis protocol.

• MNP2 and MNP4 are error correction protocols.

• MNP5 is a data compression protocol used with conjunction with MNP’s correctionprotocols.

Although there are new modem compression protocols constantly developed, the modemcompression does not reach the results of traditional software compression what demonstratefor example the [21] article.This is mainly because the modem compression protocols are dictionary based and in contrastto software compression the size of the dictionary and the length of coded word is limited bymodem hardware.It can be taken as an another good argument to deployment of connection accelerators,which can reduce the volume of transmitted data more significantly by using the softwarecompression (on the PPP protocol level at link layer or even on higher levels of the OSImodel).

B.2 Anonymous proxy servers, firewalls

One of the common tasks of a firewall is to remove dangerous or unwanted contents fromreceived data. This implies that the firewall understands this context. Correctly workingfirewall should decode the compressed content and analyze the data. There were reportedfirewalls ([33]) that are removing or rewriting Accept-Encoding header to make the dataunreadable for the browser.

B.3 Browsers

B.3.1 HTTP protocol compatibility and Encoding support

Only the most popular browser2 are considered. There are another versions of presentedbrowsers or less popular browsers, such as Internet Explorer 3, Opera 6, America Online,Lynx, etc.

bugs

• At least the combination of Acrobat Reader 4 or 6 and Internet Explorer 5 or 6 canmake an access to the content of a PDF document fail when transferred in compressedform. It seems to be a problem caused by improper passing the PDF document frombrowser to associate PDF reader instance because everything works as expected, whenthe PDF document is stored to disk manually before opening it in Acrobat Reader.

1Lempel-Ziv-Jeff-Heath2According to the W3C Browser Statistics - http://www.w3schools.com/browsers/.


Table B.1: Browsers capabilities and compatibility with accelerators.Browser name Browser code HTTP Content Encoding, Squeeze

compatibility Transfer Encoding compatibleFirefox Ffox HTTP/1.0, gzip, deflate yes

HTTP/1.1Internet Explorer 4 IE4 HTTP/1.0, gzip, deflate yes



HTTP/1.1Mozilla Moz HTTP/1.0, gzip, deflate yes

HTTP/1.1Netscape 3 NN3 HTTP/1.0 noNetscape 4 NN4 HTTP/1.0 gzip (since 4.06) yes (since 4.06)Netscape 6 NN6 HTTP/1.1 gzip, deflate, compress;q=0.9 yesNetscape 7 NN7 HTTP/1.1 gzip, deflate, compress;q=0.9 yesOpera 7 O7 HTTP/1.1 deflate, gzip, x-gzip, identity, *;q=0 yesOpera 8 O8 HTTP/1.1 deflate, gzip, x-gzip, identity, *;q=0 yes

• Internet Explorer at version 5.5 and 6 has the bug that may cause losing the first 2048bytes of data that are sent in compressed form3.

B.4 Origin Servers

The performance of Web accelerator can be significantly affected by origin servers. Considerthe following:

• If an origin server sends a data already compressed the accelerator mostly leave it as itis. This is generally desirable but it has to be noted that it affects the volume of saveddata by the accelerator.

• Some accelerator’s transformations can be done on the whole data only, not on the datastream in chunks, such as some image transformations, HTML content filtering, etc.If the origin server doesn’t send Content-Length header the accelerator is not abledetermine the length of the object before downloads it completely. Because an accel-erator usually needs to know the object’s length for allocation memory buffers for thetransformation. So the accelerator may decide not to transform such object because iscomplicated for the accelerator to work around it.

• The transformability and cacheability of objects can be explicitly influenced by sendingof Cache-Control or Pragma HTTP Header. Misuse of this headers may prohibit HTTPprotocol adhering caches from doing their job.

3There is a fix for this problem in article number 312496 published by Microsoft Support -http://support.microsoft.com


B.5 Data nature

While text objects can be successfully compressed with compression factor over 5:14, imageand multimedia objects are almost incompressible. Sometimes an attempt to compress non-text object may result in object expansion. Although there are some lossy compression orcompaction methods, they can not be applied in general.

4This compression factor can be reached by using deflate algorithm, see ”Technical Details” note in docu-mentation in [38].

Appendix C

Squeeze Performance Graphs

All the presented graphs are daily graphs generated from 5 minute average gathered throughSNMP.

C.1 Performance Test 2

Figure C.1: Performance Test 2: Themean CPU utilization, as a percentage, sinceSqueeze was started

Figure C.2: Performance Test 2: The totalnumber of objects currently in the cache

Figure C.3: Performance Test 2: The amountof memory (in kilobytes) currently used tostore in-memory objects

Figure C.4: Performance Test 2: The amountof disk space (in kilobytes) currently used tostore on-disk objects

89

APPENDIX C. SQUEEZE PERFORMANCE GRAPHS 90

Figure C.5: Performance Test 2: The amountof network traffic (in kilobytes) read fromcache clients and written to cache clients

Figure C.6: Performance Test 2: The amountof network traffic (in kilobytes) read from ori-gin servers

Figure C.7: Performance Test 2: The amountof network traffic (in kilobytes) written to ori-gin servers

Figure C.8: Performance Test 2: The numberof client requests that were cache hits vs. thetotal number of HTTP requests received fromcache clients

Figure C.9: Performance Test 2: The numberof requests forwarded to origin servers

Figure C.10: Performance Test 2: Squeeze’scache hit ratio (percentage) over the last 5minutes


Figure C.11: Performance Test 2: The num-ber of MySQL queries per second multipliedby 1000


C.2 Comparative Test

Figure C.12: Comparative Test: The meanCPU utilization, as a percentage, sinceSqueeze was started

Figure C.13: Comparative Test: The totalnumber of objects currently in the cache

Figure C.14: Comparative Test: The amountof memory (in kilobytes) currently used tostore in-memory objects

Figure C.15: Comparative Test: The amountof disk space (in kilobytes) currently used tostore on-disk objects

Figure C.16: Comparative Test: The amountof network traffic (in kilobytes) read fromcache clients and written to cache clients

Figure C.17: Comparative Test: The amountof network traffic (in kilobytes) read from ori-gin servers


Figure C.18: Comparative Test: The amountof network traffic (in kilobytes) written to ori-gin servers

Figure C.19: Comparative Test: The numberof client requests that were cache hits vs. thetotal number of HTTP requests received fromcache clients

Figure C.20: Comparative Test: The numberof requests forwarded to origin servers

Figure C.21: Comparative Test: Squeeze’scache hit ratio (percentage) over the last 5minutes

Figure C.22: Comparative Test: Squeeze’scache byte hit ratio (percentage) over the last5 minutes

Figure C.23: Comparative Test: The numberof MySQL queries per second multiplied by1000

Bibliography

[1] Fielding, R., Frystyk, H. and T. Berners-Lee, ”Hypertext Transfer Protocol –HTTP/1.0”, RFC 1945, May 1996.

[2] Fielding, R., Gettys, J., Mogul, J., Frystyk, H., Masinter, L., Leach, P. and T. Berners-Lee, ”Hypertext Transfer Protocol – HTTP/1.1”, RFC 2616, June 1999.

[3] Fielding, R., Irvine, U., C., Masinter, L. and T. Berners-Lee, ”Uniform Resource Identi-fiers (URI): Generic Syntax”, RFC 2396, August 1998.

[4] Franks, J., Hallam-Baker, P., Hostetler, J., Lawrence, S., Leach, P., Luotonen, A., Sink,E., and L. Stewart, ”HTTP Authentication: Basic and Digest Access Authentication”,RFC 2617, June 1999.

[5] Cooper, I., Melve, I., and G. Tomlinson, ”Internet Web Replication and Caching Taxon-omy”, RFC 3040, January 2001.

[6] Wessels, D., ”Web Caching”, O’Reilly, June 2001.

[7] Comer, D. E., ”Internetworking with TCP/IP” (Volume I, second edition), Prentice-Hall,1991.

[8] Salomon, D., ”Data Compression - The Complete Reference”, Springer-Verlag, 1998.

[9] Lempel, A., Ziv, J., ”A Universal Algorithm for Sequential Data Compression”, IEEETransactions on Information Theory, May 1977.

[10] Lempel, A., Ziv, J., ”Compression of Individual Sequences Via Variable-Rate Coding”,IEEE Transactions on Information Theory, September 1978.

[11] Welch, T., ”A Technique for High-Performance Data Compression”, Computer, 1984.

[12] Pierzchala, S., ”Performance Improvement From Caching and Compression” -http://www.webperformance.org/performance/cach-comp-perf.html

[13] Duska, B., M., Marwood, D., Feeley, M., J., ”The Measured Access Statistics of World-Wide-Web Client Proxy Caches”, USENIX Symposium, December 1997.

[14] Mathis, M., Mahdavi, J., Floyd, Romanow, A., ”TCP Selective Acknowledgement Op-tions”, RFC2018, October 1996.

[15] Stevens, W., ”TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Re-covery Algorithms”, RFC 2001, January 1997.

94

BIBLIOGRAPHY 95

[16] Mathis, M., Reddy, R., ”Enabling High Performance Data Transfers”,http://www.psc.edu/networking/projects/tcptune/

[17] MacDonald, D., Barkley, W., ”Microsoft Windows 2000 TCP/IP Implementation De-tails” white paper

[18] Touch, J., Heidemann, J., Obraczka, K., ”Analysis of HTTP Performance”, USC/ISIResearch Report 98-463, December 1998.

[19] Kroeger, T., M., Long, D., D., E., Mogul, J., C., ”Exploring the Bounds of Web LatencyReduction from Caching and Prefetching”, USENIX Symposium on Internet Technologiesand Systems Monterey, December 1997.

[20] Loon, T., S., Bharghavan, V., ”Alleviating the Latency and Bandwidth Problems inWWW Browsing”, USENIX Symposium on Internet Technologies and Systems Monterey,December 1997.

[21] Mitronov, P., ”Modem compression: V.44 against V.42bis.”, http://www.digit-life.com/articles/compressv44vsv42bis/, 2003.

[22] Wessels, D., ”Squid: The Definitive Guide”, O’Reilly, January 2004.

[23] Squid Web Proxy Cache Home Page - http://www.squid-cache.org

[24] Wikipedia, The Free Encyclopedia - http://en.wikipedia.org

[25] Postel, J., Reynolds, J., ”File Transfer Protocol”, RFC 959, October 1985.

[26] Google Web Accelerator Home Page - http://webaccelerator.google.com

[27] AcceleNet Accelerator Home Page - http://www.ictcompress.com

[28] Proxyconn Accelerator Home Page - http://www.proxyconn.com

[29] CProxy Accelerator Home Page - http://www.cproxy.com

[30] GVU’s NSFNET statistics - http://www.cc.gatech.edu/gvu/stats/NFS/merit.html

[31] Apache HTTP Server Project Home Page - http://httpd.apache.org

[32] Mod gzip project Home Page - http://sourceforge.net/projects/mod-gzip/

[33] Home Page of mod gzip project - http://www.schroepl.net/projekte/mod gzip/

[34] Mod deflate documentation page - http://httpd.apache.org/docs-2.0/mod/mod deflate.html

[35] Deutsch, P., Gailly, J-L., ”ZLIB Compressed Data Format Specification version 3.3”,RFC 1950, May 1996.

[36] Deutsch, P. ”DEFLATE Compressed Data Format Specification version 1.3”, RFC 1951,May 1996.

[37] Deutsch, P. ”GZIP file format specification version 4.3”, RFC 1952, May 1996.

BIBLIOGRAPHY 96

[38] Zlib library Home Page - http://www.zlib.net

[39] libpng Home Page - http://www.libpng.org/pub/png/libpng.html

[40] GD Graphics Library Home Page - http://www.boutell.com/gd/

[41] MySQL Home Page - http://www.mysql.com

[42] SqueezePlay Home Page - http://www.innermedia.com/sp/

[43] XCompress Home Page - http://www.xcache.com, XCompress for IIS

[44] Google Corporate Information - http://www.google.com/corporate/timeline.html

[45] Barroso, L., A., Dean, J., Holzle, U., ”Web Search For a Planet: The Google ClusterArchitecture”, IEEE Micro, March-April 2003

[46] Squeeze Web Accelerator Home Page - http://www.zdesibyl.net/projects/Squeeze/

Date post:	12-Sep-2021
Category:	Documents
Upload:	others
View:	5 times
Download:	0 times

DIPLOMOVA PR¶ ACE¶

Documents