Policy-aware algorithms for proxy placement in the Internet

Policy-AwareAlgorithmsforProxyPlacementintheInternetKrishnanand M.Kamath, HarpalSingh Bassali, Ra jendraprasadB.HosamaniandLixin GaoUniversityof MassachusettsAmherst,MA01003harpal@cs.umass.edu,fkkamath,rhosaman,lgaog@ecs.umass.eduABSTRACTInternet has grown explosively for the past few years and has matured into an imp ortant commercial infrastructure.The explosivegrowth of trac has contributed to degradation of user p erceived resp onse times in to day's Internet.Cachingattheproxyserverhaveemergedasane ectivwayofreducingoeralllatency.Theenessofaproxyserverisprimarilydeterminedbyitslocality.Thislo calita ectedfactorssuchastheInternettop ology and routing p olicies.In this pap er, we present heuristic algorithms for placing proxies in the Internet byconsidering b oth Internet top ology and routing p olicies.In particular, wemake use of the logical top ology inferredfrom Autonomous System (AS) relationships17to derive the path b etween a proxy and a client.We present heuristicalgorithms for placing proxies and evaluate these algorithms for the Internet logical top ology over three years.To theb est of our knowledge, this is the rst work on placing proxy servers in the Internet that considers logical top ology.1.INTRODUCTIONOver the past few years, there has b een an explosive growth in the use of the World Wide Web.Commercializationand the development of standard to ols for creating and navigating web do cuments have b een the main reasons forthis growth.The quick adoption of the Internet has also led to the degradation in the p erformance of the Internet, asthe web clients often encounter unacceptably long resp onse time.Server and Network congestion at p eak time alongwith long propagation delays are b elieved to b e the ro ot cause of the problem.Caching improves network and systemp erformance for browsing bysaving network bandwidth, reducing the server load and achieving load balancing.The principle b ehind caching is that it allows the required do cuments to b e kept close to the clients; thus reducingthe resp onse time of web access and also decreasing network congestion.The most p opular lo cations to place a cacheare the web browser and proxy server.1Wwser caching has b een implemented by most existing wwsers.2This helps in preventing the client from generating trac for the same data again.Cachingattheproxyserver have emergedasane ectivewayofreducingoeralllatency.Axy servercanbeeitherareplicatingserverorwebproxy,whichisanintermediatethatactsascachingagentbetween clients and server.If prop erly placed, a proxy server can signi cantly reduce web access delay and netorkcongestion.In addition, it can reduce the server load, whichmay b e critical during p eak-time.For example, ContentDistribution Networks (CDN's) have emerged as a p oerful solution to improe the resp onse times to web pages andto reduce the trac in the Internet to some extent.CDN's consist of a set of distributed proxy servers replicatingthe content for b etter p erformance and availability than the centralized servers.The e ectiveness of a proxy server is primarily determined byitslocality.This lo cality is a ected by factors suchas the Internettop ology and routing p olicies.In this pap er,we present heuristic algorithms for placing proxies intheInternet byconsidering b othternettop ology androuting p olicies.In particular,wemakeuseof thelogicaltop ology inferred from AutonomousSystem (AS)relationships17to derivethepath b etween a proxy anda client.We present heuristic algorithms for placing proxies and evaluate these algorithms for the Internet logical top ologyover three years.To the b est of our knowledge, this is the rst work on placing proxy servers in the Internet thatconsiders logical top ology.Theauthorwas supp ortedin part byNSFgrantNCR-9977555,andNSF CAREER Award grant ANI-9875513.Anopinions, ndings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reect the viewsof the National Science Foundation.