Towards a queueing-based framework for in-network function computation

DOI10.1007/S11134-012-9296-8MaRDI QIDQ373447zbMATH OpenOpenAlexFDO

Authors Siddhartha Banerjee, Piyush Gupta, Sanjay Shakkottai

Publication date 22 October 2013

Published in Queueing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1105.5651

zbMATH Keywords

wireless sensor networksdynamic routing and scheduling algorithmsin-network function computation

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Network protocols (68M12)

Abstract: We seek to develop network algorithms for function computation in sensor networks. Specifically, we want dynamic joint aggregation, routing, and scheduling algorithms that have analytically provable performance benefits due to in-network computation as compared to simple data forwarding. To this end, we define a class of functions, the Fully-Multiplexible functions, which includes several functions such as parity, MAX, and k th -order statistics. For such functions we exactly characterize the maximum achievable refresh rate of the network in terms of an underlying graph primitive, the min-mincut. In acyclic wireline networks, we show that the maximum refresh rate is achievable by a simple algorithm that is dynamic, distributed, and only dependent on local information. In the case of wireless networks, we provide a MaxWeight-like algorithm with dynamic flow splitting, which is shown to be throughput-optimal.

Recommendations

• Lower bounds for in-network computation of arbitrary functions
• Function computation in wireless sensor networks
• Fast Distributed Algorithms for Computing Separable Functions
• Computing separable functions via gossip
• Distributed Symmetric Function Computation in Noisy Wireless Sensor Networks

Cites work

• Coding for computing
• Distributed Random Access Algorithm: Scheduling and Congestion Control
• Maximizing queueing network utility subject to stability: greedy primal-dual algorithm
• Network Coding for Computing: Cut-Set Bounds
• Optimal resource allocation for multicast sessions in multi-hop wireless networks
• Resource Allocation and Cross-Layer Control in Wireless Networks
• SCHEDULING IN A QUEUING SYSTEM WITH ASYNCHRONOUSLY VARYING SERVICE RATES
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• The capacity of wireless networks

Cited in

(2)

• Function computation in wireless sensor networks
• Lower bounds for in-network computation of arbitrary functions

Describes a project that uses

Uses Software

• TAG

This page was built for publication: Towards a queueing-based framework for in-network function computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q373447)