Towards a Queueing-Based Framework for In-Network Function Computation

Details Towards a Queueing-Based Framework for In-Network Function Computation Towards a Queueing-Based Framework for In-Network Function Computation

2011-05-27

arxiv.org/abs/1105.5651v2

Computer Science

Networking and Internet Architecture

Scientific paper

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 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.

Affiliated with

Also associated with

No associations

Rating

Towards a Queueing-Based Framework for In-Network Function Computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Towards a Queueing-Based Framework for In-Network Function Computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards a Queueing-Based Framework for In-Network Function Computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-49328