NDLI: Connection caching under various models of communication

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

The data locality of work stealing

Scheduling Cilk multithreaded parallel programs on processors of different speeds

Optimal schedules for data-parallel cycle-stealing in networks of workstations (extended abstract)

Diffusive load balancing schemes on heterogeneous networks

Interprocessor communication with memory constraints

Efficient on-line communication in cellular networks

Connection caching under various models of communication

Fault tolerant networks with small degree

Generalized connection caching

Comparing the effectiveness of fine-grain memory caching against page migration/replication in reducing traffic in DSM clusters

Asynchronous scheduling of redundant disk arrays

Infinite parallel job allocation (extended abstract)

Data management in hierarchical bus networks

Efficient, distributed data placement strategies for storage area networks (extended abstract)

Broadcast scheduling optimization for heterogeneous cluster systems

DCAS-based concurrent deques

A no-busy-wait balanced tree parallel algorithmic paradigm

Algorithmic foundations for a parallel vector access memory system

An experimental study of a simple, distributed edge coloring algorithm

Multithreaded algorithms for the fast Fourier transform

A (2.954 + ε)n oblivious routing algorithm on 2D meshes

VLSI layout and packaging of butterfly networks

Compact, multilayer layout for butterfly fat-tree

An efficient self-simulation algorithm for reconfigurable meshes

Connection caching under various models of communication

Content Provider	ACM Digital Library
Author	Kaplan, Haim Zwick, Uri Cohen, Edith
Abstract	Motivated by Web applications, we recently introduced the following theoretical model for connection-caching: Each host on a network can maintain (cache) a limited number of connections to other hosts. A message can be transmitted from one host to another only if the connection between these two hosts is open, i.e., it is cached by both endpoints. If a message request arrives and the respective connection is not open (a miss), the connection needs to be established and certain activation cost is incurred. The establishment of the new connection may force the termination (eviction) of other connections at each endpoint.The distributed nature of connection-caching makes it considerably more involved than the standanrd caching problem. It also makes it necessary to specify the type and amount of communication the different hosts are allowed to use to coordinate the contents of their caches. We consider three different models of communication. In the first and most basic model, hosts are allowed no extra communication. In particular, they are not notified when a connection is closed by its other endpoint. In the second model, hosts are notified of connection closures but are allowed no additional communication. In the third model, hosts are allowed to exchange information regarding shared open connections. The second model of communication corresponds to TCP under normal network conditions, the first corresponds to network failures. Although the third model is not yet implemented, we believe that it is interesting to explore its potential benefits. We show that all algorithms belonging to a natural class of marking algorithms, working under the third communication model, are optimally competitive, i.e., achieve a competitive ratio of k, where k is the size of the largest cache in the network. This answers the main open problem left in [7]. Interestingly, all these optimally competitive algorithms exchange at most one extra bit per open connection. We also present an optimally competitive connection-caching algorithm that works under the second model. These results show that optimal competitiveness can be achieved with very limited communication.Finally, we also consider randomized marking algorithms and show that they are O(log k)-competitive.
Starting Page	54
Ending Page	63
Page Count	10
File Format	PDF
ISBN	1581131852
DOI	10.1145/341800.341808
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2000-07-09
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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