NDLI: Algorithms for Optimizing Bandwidth Costs on the Internet

Please wait, while we are loading the content...

Voice Interactive Personalized Security (VoIPSEC) protocol: Fortify Internet telephony by providing end-to-end security through inbound key exchange and biometric verification

A Soft Semantic Web

Improving Packet Caching Scalability Through the Concept of an Explicit End of Data Marker

Before-Commit Client State Management Services for AJAX Applications

Schema-Driven Security Filter Generation For Distributed Data Integration

Web Information Extraction Using Generalized Hidden Markov Model

A Mixed Coding Scheme for Inverted File Index Compression

Algorithms for Optimizing Bandwidth Costs on the Internet

Content Provider	IEEE Xplore Digital Library
Author	Adler, M. Sitaraman, R. Venkataramani, H.
Copyright Year	2006
Description	Author affiliation: Dept. of Comput. Sci.,, Massachusetts Univ., Amherst, MA (Adler, M.; Sitaraman, R.; Venkataramani, H.)
Abstract	Content delivery networks (CDNs) deliver Web content to end-users from a large distributed platform of Web servers hosted in data centers belonging to thousands of Internet service providers (ISPs) around the world. The bandwidth cost incurred by a CDN is the sum of the amounts it pays each ISP for routing traffic from its servers located in that ISP out to end-users. A large enterprise may also contract with multiple ISPs to provide redundant Internet access for its origin infrastructure using technologies such as multihoming and mirroring, thereby incurring a significant bandwidth cost across multiple ISPs. This paper initiates the formal study of bandwidth cost minimization in the context of a large enterprise or a CDN, a problem area that is both algorithmically rich and practically very important. First, we model different types of contracts that are used in practice by ISPs to charge for bandwidth usage, including average, maximum, and $95^{th}-percentile$ contracts. Then, we devise an optimal offline algorithm that routes traffic to achieve the minimum bandwidth cost, when the network contracts charge either on a maximum or on an average basis. Next, we devise a deterministic (resp., randomized) online algorithm that achieves cost that is within a factor of 2 (resp., e/(e - 1)) of the optimal offline cost for maximum and average contracts. In addition, we prove that our online algorithms achieve the best possible competitive ratios in both the deterministic and the randomized cases. An interesting theoretical contribution of this work is that we show intriguing connections between the online bandwidth optimization problem and the seemingly-unrelated but well-studied ski rental problem where similar optimal competitive ratios are known to hold. Finally, we consider extensions for contracts with a committed amount of spend (CIRs) and contracts that charge on a $95^{th}-percentile$ basis
Starting Page	1
Ending Page	9
File Size	11389286
Page Count	9
File Format	PDF
ISBN	1424405955
DOI	10.1109/HOTWEB.2006.355262
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2006-11-13
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Availability Network servers Web and internet services Bandwidth Telecommunication traffic Traffic control Cost function IP networks Web server Contracts
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Multicast injection for application network deployment

Market-Based Cooperative Resource Allocation for Overlay Networks

Single IP Address Cluster for Internet Servers

Multifractal study of Internet traffic

Initial Results from an IPv6 Darknet13

Configuration management of large IP telephony networks

On the placement of Web server replicas

Network prediction in a policy-based IP network

CONIC: Content-Oriented Network with Indexed Caching

Algorithms for Optimizing Bandwidth Costs on the Internet

Similar Documents

Multicast injection for application network deployment

Market-Based Cooperative Resource Allocation for Overlay Networks

Single IP Address Cluster for Internet Servers

Multifractal study of Internet traffic

Initial Results from an IPv6 Darknet13

Configuration management of large IP telephony networks

On the placement of Web server replicas

Network prediction in a policy-based IP network

CONIC: Content-Oriented Network with Indexed Caching

Algorithms for Optimizing Bandwidth Costs on the Internet