NDLI: Steiner-optimal data replication in tree networks with storage costs

Content Provider	IEEE Xplore Digital Library
Author	Kalpakis, K. Dasgupta, K. Wolfson, O.
Copyright Year	2001
Description	Author affiliation: Dept. of Comput. Sci., Maryland Univ., Baltimore, MD, USA (Kalpakis, K.)
Abstract	We consider the problem of placing copies of objects at multiple locations in a distributed system, whose interconnection network is a tree, in order to minimize the cost of servicing read and write requests to the objects. We assume that the tree nodes have limited storage and the number of copies permitted may be limited. The set of nodes that have a copy of the object, called replica nodes, constitute the replica set of the object. Read requests of a node are serviced from the closest replica node. Write requests of a node are propagated to all the replicas of the object using a minimum cost Steiner tree that includes the writer and all replica nodes. The total cost associated with a replica set equals the cost of servicing all the read and write requests, plus the storage cost at all the replica nodes. We are interested in finding a replica set with minimum total cost, i.e. a Steiner-optimal replica set. Given a tree with n nodes, we provide an O(n/sup 6/p/sup 2/)-time algorithm for finding a Steiner-optimal replica set of size p, taking into consideration the read, write, and storage costs. Our algorithm can also find a Steiner-optimal replica set for a tree with n nodes in time O(n/sup 8/). We also demonstrate that the policy used to propagate write requests to all the replica nodes in the network affects the cost and configuration of the optimal replica set for the object.
Sponsorship	Concordia Univ.
Starting Page	285
Ending Page	293
File Size	854377
Page Count	9
File Format	PDF
ISBN	0769511406
DOI	10.1109/IDEAS.2001.938096
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2001-07-16
Publisher Place	France
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Intelligent networks Cost function Surface-mount technology Computer science Web sites Web pages Internet System performance Multiprocessor interconnection networks
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

Optimal placement of replicas in trees with read, write, and storage costs

An algorithm for multicast tree generation in networks with asymmetric links

A partial-multiple-bus computer structure with improved cost-effectiveness

Performance, Cost, and Energy Evaluation of Fat H-Tree: A Cost-Efficient Tree-Based On-Chip Network

Asymptotically optimal randomized tree embedding in static networks

A simulation research on multiprocessor interconnection networks with wormhole routing

Interconnection strategies for wireless access networks

Race-free interconnection networks and multiprocessor consistency

Steiner-optimal data replication in tree networks (2001).

Steiner-optimal data replication in tree networks with storage costs

Similar Documents

Optimal placement of replicas in trees with read, write, and storage costs

An algorithm for multicast tree generation in networks with asymmetric links

A partial-multiple-bus computer structure with improved cost-effectiveness

Performance, Cost, and Energy Evaluation of Fat H-Tree: A Cost-Efficient Tree-Based On-Chip Network

Asymptotically optimal randomized tree embedding in static networks

A simulation research on multiprocessor interconnection networks with wormhole routing

Interconnection strategies for wireless access networks

Race-free interconnection networks and multiprocessor consistency

Steiner-optimal data replication in tree networks (2001).

Steiner-optimal data replication in tree networks with storage costs