‘
`
`-_ CACHING AND REPLICATION
`
`
`
`M'CHAELRABINWIBH
`
`'
`
`--
`
`
`
`(cid:48)(cid:44)(cid:55)(cid:3)(cid:21)(cid:19)(cid:20)(cid:21)
`(cid:47)(cid:76)(cid:80)(cid:72)(cid:79)(cid:76)(cid:74)(cid:75)(cid:87)(cid:3)(cid:89)(cid:17)(cid:3)(cid:48)(cid:44)(cid:55)
`(cid:44)(cid:51)(cid:53)(cid:21)(cid:19)(cid:20)(cid:26)(cid:16)(cid:19)(cid:19)(cid:21)(cid:23)(cid:28)
`
`1
`
`

`

`Many of the designations used by manufacturers and sellers to distinguish their products are
`claimed as trademarks. Where those designations appear in this book, and Addison-Wesley
`was aware of a trademark claim, the designations have been printed with initial capital letters
`or in all capitals.
`
`The authors and publisher have taken care in the preparation of this book, but make no
`expressed or implied warranty of any kind and assume no reaponsibility for errors or
`omissions. No liability is assumed for incidental or consequential damages in connection
`with or arising out of the use of the information or programs contained herein.
`
`The publisher offers discounts on this book when ordered in quantity for special sales. For
`more information, please contact:
`
`Pearson Education Corporate Sales Division
`201 W. 103rd Street
`
`Indianapolis, IN 46290
`(800) 428-5331
`corpseles®pearsoned.com
`Visit AW on the Web: www.crucom/cseug/
`
`Library of Congress Cataloging-in—Publication Data
`Rabinovich, Michael
`Web caching and replication/ Michael Rabinovich and Oliver Spatscheck
`p.
`cm.
`Includes bibliographical references and index.
`ISBN 0—201-61570-3 (alk. paper)
`1. Cache memory. 2. Electronic data processing—Backup processing alternatives.
`3. World Wide Web.
`I. Spatscheck, Oliver. II. Title.
`
`TK7895.M4 R32
`
`2002
`
`004.5’3~-dc21
`
`Copyright © 2002 by AT&T
`
`2001053733
`CIP
`
`All rights reserved. No pa rt of this publication may be reproduced, stored in a retrieval
`system, or transmitted, in any form, or by any means, electronic, mechanical, photocopying,
`recording, or otherwise, without the prior consent of the publisher. Printed in the United
`States of America. Published simultaneously in Canada.
`
`For information on obtaining permission for use of material from this work, please submit
`a written request to:
`
`Pearson Education, Inc.
`
`Rights and Contracts Department
`75 Arlington Street, Suite 300
`Boston, MA 02116
`
`Fax: (617) 848—7047
`
`ISBN 0-201-61570-3
`
`Text printed on recycled paper.
`
`1 2 3 4 5 6 7 B 9 10 42154504030201
`First printing, December 2001
`
`2
`
`

`

`Introduction mm
`
`the collection of accurate statistics about content usage, which can be vital informa-
`tion for selling advertisements. Finally, some content is difficult or even impossible
`to cache because it is dynamically generated or personalized for a given user. Part
`II of this book describes various techniques for caching that address some of these
`problems (Chapter 13). However, there will always be plenty of requests that seep
`through all the caches to reach the origin servers. Handling these requests efficiently
`requires replication of popular servers, or Web replication for short.
`
`I.2 The Basics of Web Replication
`
`Unlike Web caching, which is performed by clients, Web replication. is a server-side
`approach to scaling up the Web. An early and still widely used method for Web
`replication is explicit mirroring. In this method, multiple Web sites, called mirror sites
`or simply mirrors, are created with the same content, each site having its own set of
`URLs. Users choose one of the mirrors to receive their requests. If you have seen a
`page inviting you to click on one link if you are in the United States or on another link
`if in Asia, you have encountered explicit mirroring.
`Many popular Web sites now have multiple mirrors. Figure 1.4 shows an example
`of an explicitly mirrored site. Several problems make explicit mirroring inadequate.
`
`- The existence of multiple mirrors is not transparent to the user. The user must
`explicitly Choose a mirror for connection.
`
`a This approach relies on proper user behavior to achieve load sharing. In other
`words, the content provider can request that certain groups of users connect
`to certain mirrors but cannot force them to do so. In an extreme case, users
`
`could conspire to connect to the same site, thus making it useless to have
`multiple mirrors. However, such undesirable user behavior also occurs
`without any malicious intent on the user side. Indeed, mirrors are generally
`not created when the service is first set up, but are added over time as the
`demand for the service approaches the capacity of the current set of servers.
`By the time the new mirrors appear, users may have already built links to the
`older sites into their applications. For example, they may have bookmarked
`the URLs pointing to those sites or embedded them into their own Web pages.
`Users may-miss the announcement about the newly created mirrors or be
`unwilling to change their existing applications to point to the new sites.
`
`0 The decision to create a mirror is irrevocable: once created, the mirror cannot
`be brought down without invalidating its URLs. These URLs may be stored in
`an unknown number of user bookmark files and embedded in third—party
`applications; therefore, removing the mirror could cause an unknown level of
`disruption of access to the site. One could of course make the former mirror
`redirect clients to the currently valid sites, but that does not change the fact
`that the mirror site must always exist, even if in a skeleton form.
`3
`3
`
`

`

`xxvi
`
`ihtroduction
`
` ' vase $511M“ 'Foundatluii
`
`Here is a list by oountry, of the mirrors ofW the Primary ENE
`Brojeet 5 World Wide Web SEMI: sponsored by the Emefioflararefioumiaflon
`(ESE), Here'ts a 1151 of our FTP mirrors.
`
`If. you would like to be a mirror site, please read this edition, and men ask
`W to add you to this list once you have your minor site set
`
`up.
`
`The pn'maflehsiie for the GNU Project is fairly busy. Please use one of
`these mirrors of our primary Web site that is close to you.
`
`Here are the wineries that have Web mirror sites:
`
`WIMIWIWIMIWIWIWI
`firmlfllmgamlflongfionglmdialmdonesialnammelandilapanlm :gff
`IMexicniNoorayiRemlRolandletugallRussmlfipainISnefleanabaaal
`WIWIWIW
`
`Figure [.4 A Web site with explicit mirrors
`Source: Used with permission of gnu.org and Netscape.
`
`The next step in the evolution of Web replication has been transparent static or irroring,
`where replication is hidden from the user. Each object on a transparently mirrored Web
`site has a single URL. Users cannot choose a server replica; in fact, they do not even
`know Whether the site has been replicated. Instead, user requests are automatically
`directed to one of the mirrors (Chapter 14 describes mechanisms for doing this). As in
`
`4
`4
`
`

`

`Introduction
`
`xxvii
`
`explicit mirroring, each mirror has a full copy of the Web site, and the set of mirrors
`is determined and set up by humans (system administrators). Once deployed, the
`mirror set remains fixed until the system administrators reconsider their decision.
`Transparent static mirroring can often be an adequate solution for a company run-
`ning its own Web site, especially if its Web operation represents a relatively small
`portion of the overall business. Such a company can afford to deploy enough re-
`sources to handle the highest imaginable load. Although wasteful, such provisioning
`for the worst—case scenario would likely be feasible, since it would still represent a
`small portion of the total company costs. Given the limited scale of this environment,
`monitoring the load and periodically reconsidering resource deployment would also
`be manageable.
`On the other hand, a hosting service provider—a company that provides facilities to
`host Web sites for third-party content providers—might host thousands of Web sites
`and millions of Web objects deployed on numerous Web servers around the globe.
`On this scale, the extent of the waste for worst-case provisioning would be multiplied
`by the number of hosted Web sites. Moreover, since running Web sites is the core
`business of the hosting service provider, the waste cannot be offset by other lines of
`business. At the same time, the number of possibilities for resource allocation, such
`as choosing how many mirrors of various Web sites to have and or! which servers to
`deploy them, explodes. As the scale of hosting systems grows, administering them
`becomes increasingly difficult, labor intensive, and error prone.
`In response to this challenge, the technology of transparent dynamic replication has
`emerged, where the replicas of various content are automatically created, deleted,
`or relocated based on observed demand. By automating resource allocation, one can
`afford to modify resource allocation much more often, according to the changing
`demand. Frequent resource reallocation also enables a quick adjustment to abrupt
`demand surges for a given site. Automating resource allocation also alIOWS resource
`management at a finer granularity. For example, one could create mirrors of only
`the most popular pages of a given Web site instead of the entire site. A server that
`replicates a portion of a Web site is sometimes called a partial mirror.
`As an illustration, consider a company that hosts two Web sites: one that provides
`news clips about the stock market and another that publishes Sports news. If we
`assume that there is a factor of two diurnal variations of the average—to—peak demand
`for each site and that satisfying the average demand takes one Web server with a 40,
`megabit-per-second (Mbps) Internet connection, then provisioning for the Worst~case
`scenario would require that either site be allocated four Web server replicas, each with
`a 40Mbps Internet connection (two servers for the peak demand, multiplied by two to
`be ready for unforeseen demand spikes, according to a common rule of thumb). The
`total resources for the two sites w0uld amOunt to eight servers with 320Mbps total
`Internet connectivity. However, it is likely that the peak demand occurs in the daytime
`for stock market news and at night for sports events. Thus, dynamic replication might
`allow the hosting company to allocate only five servers for both sites with 200MBps
`total link capacity: one server with a 40Ml3ps link to each site for routine demand,
`
`5
`5
`
`

`

`
`
`Objects
`__||
`
`
`
` Server Surrogate
`
`_—|| Objects
` Enterprise Network
`
`Server Surrogate
`
`Popular
`
`from
`Server X
`
`Popular
`
`from
`Server X
`
`xxviil
`
`introdriction
`
`
`
`
`Browser
`
`
`
`
`
`
`of Web Site Owner
`
`
`
`Figure l.5 Web server surrogates
`
`one for both sites for peak demand, and two for unforeseen spikes. In this case, each
`site would be replicated as needed and, because the periods of peak demand do not
`coincide, both sites would share the same server for peak demand. Both sites Would
`also share the same spare servers for unforeseen demand spikes, because it is highly
`unlikely that both sites would experience these spikes at the same time. By selectively
`replicating only the most popular content on either site, the hosting company may
`realize further savings in storage capacity.
`Figure 1.5 depicts a currently prevalent type of transparent dynamic replication
`using surrogates, also known as reverse proxies. In this scenario a Web site distributes
`incoming requests among surrogates as if they were static transparent mirrors func-
`tionng as full server replicas. A surrogate, however, processes a request as does a
`regular proxy, which is sometimes called a forward proxy, to clearly distinguish it: the
`surrogate satisfies the request from its cache if possible; otherwise, it fetches the re—
`quested object from the origin server, forwards it to the client, and perhaps caches
`it for future use. As a result, a surrogate acts as a partial replica with a state that
`dynamically changes with the demand.
`The same surrogate can be shared by multiple Web sites, as is show in Figure 1.6.
`A shared surrogate caches objects from all participating sites; on a cache miss, the
`surrogate obtains the object from the appropriate site. A Whole industry of content
`delivery networks (CDNs) has Sprung up around the basic concept of shared surrogates.
`CDNs operate shared surrogatesand sell their surrogate services to content providers.
`Shared surrogates introduce economies of scale and make it feasible for even a
`
`6
`
`

`

`introduction xxix
`
`Shared Surrogate
`
`Popular
`
`_| Objects
`I from
`Servers
`X and Y
`
`Browser
`
`
`
`
`
`Objects
`from
`
`Servers
`X and Y
`
`Browser
`
`Figure l.6 Shared surrogates (a CDN)
`
`modest-sized Web site to benefit from a large number of well-connected surrogates
`deployed at highly prized locations in the Internet.
`In the remainder of this book, we use the term server replica to refer collectively to
`mirrors, partial mirrors, and surrogates. A server replica does not have to be identical
`to the origin server, because the former may not have all the objects of the latter
`and also because a server replica may be shared by several origin servers. We also
`distinguish between server replicas, which refer to computers, and content replicas,
`which refer to pieces of content stored on those computers.
`Web replication can help performance in several ways: first, it can improve the
`scalability of a Web site by distributing the load across multiple servers; second, it can
`improve the proximity of clients to the Web site by servicing requests from a mirror
`or surrogate that is close to the requesters; and third, communicating with nearby
`mirrors or surrogates localizes traffic on the Internet, improving its overall scalability.
`These benefits are analogous to those of Web caching, which also reduces load on
`origin servers, improves proximity, and reduces network traffic. However, by leaving
`content providers in full control, Web replication addresses many limitations of Web
`caching mentioned previously in this chapter. Content providers are free to enforce
`the same access restrictions at server replicas as at the origin server. They can imple-
`ment arbitrary nonstandard protocols between the origin server and its replicas to
`
`7
`
`

`

`xxx Introduction
`
`keep replicated content consistent.2 They can collect accurate usage statistics by ag»
`gregating the statistics from individual replicas. They can also replicate applications
`that personalize Web pages or generate Web objects dynamically.
`Like Web caching, Web replication has its own limitations. Not every content
`provider can afford replicating its Web site. For example, most academic sites are
`unlikely to deploy mirrors across the Internet or purchase CDN services. And while
`they probably will not make any of the ”100 most popular sites” lists, they are of vital
`importance to certain classes of users, such as fellow academics. Also, as much as
`CDNs try to penetrate into every corner of the Internet, they would be hard-pressed
`to deploy surrogates as close to all Internet users as ISPs can deploy forward proxies.
`We believe that replication is unlikely to obviate the need for caching, just as caching
`alone is unlikely to solve the Web scalability problem.
`Web replication issues are discussed in Part III, including the diversion of client
`requests to replicas (Chapter 14), CDN architectures and issues (Chapter 15), and
`choosing a server replica for a given request (Chapter 16). Because we discuss only
`transparent replication in this book, the word "transparent” is usually omitted.
`
`L3H Beyond Performance
`
`Historically, Web proxies were used for security reasons. Corporate networks have
`special computers called firewalls that block direct communication of corporate com-
`puters with outside networks. Any application in a corporate network, including a
`Web browser, had to communicate with outside networks through special security
`gateways to get through the firewall, and a Web proxy served as such a gateway.
`Thus, early proxies played a functional role as a. component of a security service
`rather than a performance enhancer. TWo later developments had big implications for
`how enterprises used proxies. First, caching was added to these gateways, turning
`them into Web proxies as we know them today. Second,-firewalls that can operate
`transparently to other corporate computers replaced many such explicit gateways.
`Because of these developments, the main motivation for using proxies in enterprise
`networks switched from providing essential functionality to improving performance.
`Increasingly, however, proxies and surrogates are again being viewed as platforms
`to implement new functionalities. Examples of services that can be conveniently im-
`plemented on proxies or surrogates include content filtering (that is, restricting user
`access to certain kinds of content); content adaptation, where content is modified
`depending on the capabilities of the browser that requested the content; advertise—
`ment insertion; billing and accounting; and so on. Although the primary goal of Web
`
`
`
`2 Nonstandard protocols that do not require an inter-enterprise convention are called proprietary, as
`opposed to open protocols that have been standardized by an organization such as Internet Engineer-
`ing Task Force (IETF).
`
`8
`
`

`

`Chapter 14
`
`Basic Mechanisms
`
`
`
`for Request Distribution
`
`As we mentioned in the introduction to Part III, this book focuses on transparent
`replication: replication techniques that require no user involvement or even awareness
`of whether or not a Web site utilizes replication. Transparent replication requires
`that clients use a single logical name when requesting a resource, regardless of the
`physical server that ends up processing the request. So a fundamental requirement
`of transparency is a mechanism for the redirection of logically identical requests to
`distinct servers.
`
`There are a variety of points on the request processing path where such redirection
`may occur: at the client, at the intermediate proxies, at various points in the DNS
`system, at the primary origin server, or somewhere in the network. This chapter
`presents the basic alternatives for request redirection, while the next chapter describes
`how CDNs use these building blocks to implement their architectures. Sections 14.1
`and 14.2 of this chapter discuss request redirection mechanisms that are oblivious to
`requested objects; the mechanisms that take into account which objects are requested
`are considered in Section 14.3.
`
`14.1 Content-Blind Request Distribution
`with Full Replication
`
`This section considers request distribution mechanisms that are oblivious to the re-
`quested objects; we refer to those mechanisms as content-blind mechanisms. The gran—
`ularity of request distribution in these schemes is a Web site; all requests to a given
`site are distributed in the same way regardless of which objects are requested. These
`mechanisms include client redirection, redirection by a balancing switch, redirection
`by the Web site’s DNS servers, and anycast.
`
`9
`9
`
`231
`
`

`

`232
`
`Part Hi Web Replication
`
`14.1.1 Client Redirection
`
`One way to implement request redirection is to use a Web client’s DNS [Fei et al. 1998].
`Client DNS servers either are colocated with the Web clients on the same machines or
`run on separate machines. In any case, a client is configured to use its DNS server.
`This mechanism is illustrated on Figure 14.1. When the client wants to access a URL,
`for example, http: //www.corn_pany.com /home.html, it issues a query to its client DNS
`server to find the IP address of the site. The client DNS ultimately obtains the response
`to this query from the Web site’s DNS (see Section 4.3 for details). In this approach,
`the response from the Web site’s DNS server contains a list of IP addresses of physical
`servers rather than a single IP address. The client DNS server then chooses a server
`from the list and returns its IP address to the client. Finally, the client requests the
`required object, homehtml, from the chosen server.
`.
`Another app roach is to perform request redirection directly at the client. This mech-
`anism also requires the Web site's DNS to return a list of server replicas. But the client
`DNS server will convey the whole list to the client instead of making a choice itself.
`The client then will decide which server to use. The main advantage of this scheme
`over doing redirection by the client DNS server is that the client can monitor the
`performance of accesses to different servers and use these observations to make a
`more intelligent choice (see Section 15.5). Active clients such as forward. proxies are
`especially well suited for redirecting requests, since they generate more traffic than
`individual clients and therefore have a better chance to collect enough performance
`measurements of prior accesses to different server replicas.
`An advantage of client-based schemes is that the client is in a good position to make
`the server selection. It can compare routing paths from itself to various servers, or it can
`measure response times, packet loss rates, or other metrics. Another advantage is that
`these schemes do not interfere with DNS caching (we will see that some schemes do).
`
`
`
`
`Addr2
`
`Addri
`
`
`
`
`Web Site's
`DNS Server
`
`AddrS
`
`
`
`Figure 14.1 Request redirection by client DNS
`
`10
`10
`
`

`

`Chapter 14 Basic Mechanisms for Request Distribution
`
`233
`
`Since the response from the Web site’s DNS server contains the entire replica list, it
`can be freely cached within the DNS infrastructure as long as the replica list remains
`valid. For instance, in the case of redirection by the client DNS server, the client DNS
`server can cache the received server list and use it for many client queries, each time
`performing a different server selection.
`The main disadvantage is that the Web site cedes control over server selection to the
`client. The client may choose suboptimal servers or perform no intelligent selection at
`all; its capabilities are not known to the Web site. Overall, client-based approaches are
`not widely used at the present. If a response from a Web site’s DNS contains multiple
`IP addresses, most clients simply use the first address on the list.
`Another disadvantage, at least from the practical perspective, is that these ap-
`proaches require a modification to either the client DNS server or the client itself. So
`while transparent to the end user, these approaches are not transparent to the current
`software used at the client side. A more transparent approach, which requires only
`client configuration but no software modification, uses Java applets and is described
`in the context of content-aware request distribution (see Section 14.3.1).
`
`14.1.2 Redirection by a Balancing Switch
`
`A Widely used approach incorporates a hardware-based solution to redirect requests.
`In this approach, a special load-balancing switch, a balancer for short, is placed in
`front of a group of servers that host a Web site. A server group that uses a balancer is
`often called a serverfarm. Figure 14.2 illustrates this scheme. The domain name of the
`Web site is mapped to the IP address of the balancer, so all clients send their packets
`to it. When the first packet .from a client arrives, the balancer selects a server and
`forwards the packet (and all subsequent packets in the same session) to this server.
`
`
`
`Figure 14.2 Request redirection by a balancing switch
`
`11
`11
`
`

`

`234
`
`Port m Web Replication
`
`The balancer also modifies the response packets as they pass from the server to the
`client, so that the packets’ headers contain the balancer’s IP address rather than that of
`the server. Thus, all clients have the illusion that they communicate with a single host
`With the IP address of the balancer while actually connecting to one of the servers in
`the server group. For this reason, the IP address of the balancer is sometimes called a
`virtual IP address of the site. The balancer can be either content blind or content aware.
`We consider content—aware balancers in Section 14.3 and concentrate on content—blind
`balaneers here.
`
`The balancer maintains a sessions database, which records a server chosen for each
`
`active communication session. The sessions database is needed to ensure that, once
`a server is chosen for servicing a request, all packets from this client in this session
`go to the same server. In the simplest case, the content-blind balancer considers a
`session to be over when no more packets arrive from the client for a certain time, say
`60 seconds. In this case, the balancer examines only Layer 3 information in packet
`headers: source IP addresses in packets from clients to associate these packets with
`sessions, and source I P addresses in packets from servers to replace these addresses
`with the virtual IP address.
`
`Alternatively, the balancer can equate sessions with TCP connections and con-
`sider sessions to be over when TCP connections are closed. In this case, the balancer
`must examine TCP headers to determine the TCP port numbers and detect FIN or
`RST packets that close connections. This is Layer 4 information, and the balancer
`then becomes an L4 switch. Note, however, that the functionality of this L4 switch
`is very different from the intercepting L4 switches we considered in the context of
`forward proxies (see Chapter 8). The main function of an intercepting switch is to in—
`tercept packets and direct them to proxies. In contrast, clients explicitly address their
`packets to the balancing switch, so no interception is needed. While intercepting L4
`switches usually select a proxy to send a packet to based on the packet destination IP
`address, balancing switches choose between servers based on the packet source IP ad-
`dresses. In practice, many L4 switches, such as those offered by Foundry and Nortel’s
`Alteon division, are capable of functioning as both intercepting and balancing switches,
`depending on how they are configured.
`Whether the balancing switch considers only Layer 3 information or also Layer 4
`headers, this approach to request redirection is often called lP balancing. lP balancing
`uses standard clients and DNS and Web servers. However, by having a focal com~
`munication point at the balancing switch, it does not scale geographically. Thus, it is
`mostly used for load sharing in a server farm on a local 'area network.
`Some products, such as IBM Network Dispatcher and Radware, add an interesting
`twist to JP balancing. Their balancers select servers and forward client packets to them
`as before. But servers respond to clients directly, bypassing the balancer and using the
`balancer’s IP address as the Sender address. This results in triangular communication;
`from the client to the balancer to the server and back to the client (Figure 14.3). Tech-
`nically, this mechanism can be implemented using either- network address translation
`(NAT) or IP-in—IP encapsulation (see Section 8.3.2).
`
`12
`12
`
`

`

`Chapter i4 Basic Mechanisms for Request Distribution
`
`235
`
`
`
`
`
`VirtLlal IP
`Address
`
`
`
`Virtual IP
`
`Address
`
`Virtual [P
`
`Address
`
`Figure 14.3 lP balancing with triangular communication
`
`With network address translation, the balancer modifies the destination IP address
`of every packet to that of the Chosen server. The server then responds to the client
`using the IP address of the switch as the source IP address of its packets. IP-in-LP
`encapsulation is more general because it does not require the servers to know the
`virtual IP address in advance. In this scheme, the switch encapsulates an entire packet
`from the client into a new IP packet with new headers. The new headers indicate the
`switch IP address (the site’s virtual IP address) as the source IP address and the chosen
`server [P address as the destination. The server unwraps the client packet and replies
`to the client using, again, the IP address of the switch. In contrast with network add ress
`translation, the server learns the switch IP address from the wrapper headers of the
`packet. Being able to learn which IP address to use as its source IP address becomes
`especially handy when a server is forwarded packets by more than one balancing
`switch (which is sometimes the case in content delivery networks, see Section 15.6).
`With both NAT and IP-in-IP encapsulation, a client cannot tell that the host it sends
`its request to is different from the host that replies, because both hosts use the same
`IP address to communicate with the client. Because content flowing from servers to
`clients takes a direct route, and because it constitutes most of the data exchanged be-
`tween clients and servers, this approach improves geographical scalability, especially
`from. the bandwidth-consumption perspective. The latency gain is limited by the need
`for client acknowledgments to travel via the balancer. Still, it can red uce response time
`considerably, because the aggregate bandwidth available to the Web site increases.
`
`14.1 .3 Redirection by a Web Site's DNS
`
`Many DNS unplementations—including Cisco Distributed Director, Alteon’s GSLB,
`Arrowpoint’s Content Smart Site Selector, F5 Networks BDNS, and others—allow the
`Web site’s DNS server to map a hest domain name to a set of IP addresses and choose
`one of them for every client DNS query. DNS redirection by a Web site’s DNS is far
`more. widely used than DNS redirection by client DNS servers; therefore we often
`
`13
`13
`
`

`

`236
`
`Part in Web Replication
`
`
`
`
`
`
`
`Server Side l:vww_company_com—>Addr1Addr2
`
`DNS Server
`AddrB
`
`® Addr2
`
`Web Site‘s
`
`Addrs
`
`Figure 14.4 Request redirection by a Web site’s DNS server
`
`use shorter terms such as ”DNS~based redirection,” or ”DNS server selection" in the
`remainder of the book, meaning by default that the redirection is performed by a Web
`site’s DNS.
`
`The scheme is illustrated in Figure 14.4. In this example, the site’s domain name
`(www.companycom) is mapped to three IP addresses. When a query arrives, the site’s
`DNS server selects a server replica and includes its 113 address in the response. Then
`the client sends its request directly to this Web server. Notice the difference with DNS—
`based client redirection considered in Section 14.1.1. In the client—based approach, the
`site’s DNS returned the entire set of 1P addresses corresponding to the domain name,
`leaving server selection to the client DNS. Here, the site’s DNS server itself makes
`the selection and returns only the 1? address of the selected server. Server selection is
`based on such factors as the query origin and the load on server replicas. We discuss
`selection algorithms in detail later in Chapter 16.
`Several advantages have made this approach widely used. It scales well geograph-
`ically since clients can communicate directly with nearby servers, balancing load
`among them and balancing traffic among distinct routing paths. Like 1P balancing, it
`is implemented entirely by the content site; no modification of the client or its DNS is
`needed.
`
`On the other hand, DNS response caching by clients complicates changing replica
`sets and centrolling request distribution among replicas. In Figure 14.4, for example,
`once client 1 obtains the DNS response that maps www.companycom to server 1,
`this client will continue using this server while the mapping is cached, regardless of
`the server load and availability. In fact, since clients usually acquire DNS mappings
`through client DNS servers, the cached mapping will be used by all Web clients
`connected to client 1’s DNS server.
`To counter the caching effect, Web sites often reduce the lifetime of cached DNS
`responses, by assigning them low time to live (lTL) values (see Section 4.2). However,
`
`14
`14
`
`

`

`Chapter 14 Basic Mechanisms for Request Distribution
`
`237
`
`this forces clients to perform DNS queries (and incur the latency of these queries) more
`often. Also, some. client DNS servers and most Web browsers set a minimum lifetime
`for DNS responses and refuse to reduce it any further.
`All this leads to the general observation that DNS redirection is good for request
`distribution based on stable metrics. For example, the network proximity of clients
`to servers does not change often, and DNS redirection would be appropriate for
`proximity-based request distribution. On the other hand, conditions related to server
`load and network congestion may change quickly and may call for more responsive
`mechanisms.
`There are several other issues with redirection by a Web site’s DNS. Because this
`method lies at the foundation of CDNs, we discuss the subject further in Chapter 15,
`
`which is devoted to CDN architectures.
`
`1 4.1 .4 Anycast
`
`The principal idea behind anycest is that multiple physical servers use a single I]?
`address called an anycest IP address. Each server advertises both the anycast IP address
`and its regular 11’ address to its routers, which advertise them to their neighbor routers
`in a normal manner. As a result, each router builds a path corresponding to the anyca st
`address that leads to the server closest to