NDLI: Greedy is Good: On Service Tree Placement for In-Network Stream Processing

Content Provider	IEEE Xplore Digital Library
Author	Abrams, Z. Jie Liu
Copyright Year	2006
Description	Author affiliation: Stanford University, Stanford, CA (Abrams, Z.)
Abstract	This paper is concerned with reducing communication costs when executing distributed user tasks in a sensor network. We take a service-oriented abstraction of sensor networks, where a user task is composed of a set of data processing modules (called services) with dependencies. Communications in sensor networks consume significant energy and introduce uncertainty in data fidelity due to high bit error rate. These constraints are abstracted as costs on the communication graph. The goal is to place the services within the sensor network so that the communication cost in performing the task is minimized. In addition, since the lifetime of a node, the quality of network links, and the composition of the service graph may change over time, the quality of the placement must be maintained in the face of these dynamics. In this paper, we take a fresh look at what is generally considered a simple but poor performance approach for service placement, namely the greedy algorithm. We prove that a modified greedy algorithm is guaranteed to have cost at most 8 times the optimum placement. In fact, the guarantee is even stronger if there is a high degree of data reduction in the service graph. The advantage of the greedy placement strategy is that when there are local changes in the service graph or when a hosting node fails, the repair only affects the placement of services that depend on the changes. Simulations suggest that in practice the greedy algorithm finds a low cost placement. Furthermore, the cost of repairing a greedy placement decreases rapidly as a function of the proximity of the services to be aggregated.
Starting Page	72
Ending Page	72
File Size	397837
Page Count	1
File Format	PDF
ISBN	0769525407
ISSN	10636927
DOI	10.1109/ICDCS.2006.45
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2006-07-04
Publisher Place	Portugal
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Greedy algorithms Data processing Cost function Bandwidth Telecommunication network reliability Network topology Computer science Uncertainty Bit error rate Energy capture
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

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

Greedy is good: on service tree placement for in-network stream processing.

Greedy is good: On service tree placement for innetwork stream processing (2006)

Dimensioning computer network using tabu search

Fast rearrangement of multicast trees for applications with bandwidth and delay QoS requirements

Maximum-Bandwidth ALM Tree on Tree Network

Optimization of invariant telecommunication network using simulation modeling

Two Tree-Based Algorithms for Network Spare Capacity Design

Ostro: Scalable Placement Optimization of Complex Application Topologies in Large-Scale Data Centers

Minimum hop-count multicast algorithms for reliable multiple-stream communications

Greedy is Good: On Service Tree Placement for In-Network Stream Processing

Similar Documents

Greedy is good: on service tree placement for in-network stream processing.

Greedy is good: On service tree placement for innetwork stream processing (2006)

Dimensioning computer network using tabu search

Fast rearrangement of multicast trees for applications with bandwidth and delay QoS requirements

Maximum-Bandwidth ALM Tree on Tree Network

Optimization of invariant telecommunication network using simulation modeling

Two Tree-Based Algorithms for Network Spare Capacity Design

Ostro: Scalable Placement Optimization of Complex Application Topologies in Large-Scale Data Centers

Minimum hop-count multicast algorithms for reliable multiple-stream communications

Greedy is Good: On Service Tree Placement for In-Network Stream Processing