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

Towards a Queueing-Based Framework for In-Network Function Computation,10.1109/ISIT.2011.6034026,Siddhartha Banerjee,Piyush Gupta,Sanjay Shakkottai

Towards a Queueing-Based Framework for In-Network Function Computation   (Citations: 1)
BibTex | RIS | RefWorks Download
We seek to develop joint aggregation, routing, and scheduling algorithms that, for any graph topology and a large class of functions, 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, k-th order statistic and range, and for which we can 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 that is shown to be throughput- optimal.
Conference: IEEE International Symposium on Information Theory - ISIT , vol. abs/1105.5, pp. 2542-2546, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Further, we assume that cuv(I) cmax 8 (u;v) 2 L;I 2 I. Finally, ^ is said to be obtainable if ^ 2 CH() , the convex hull of . An obtainable link-rate vector can be achieved by time-sharing over admissible link-rate vectors. For details, refer to [14]...
    • ...However this framework can be extended to a more general class of functions (Refer to [14] for details)...
    • ...In the case where node i does not have a packet of round r in queue, it needs to store the new packet (see [14] for details)...
    • ...It can be shown (for details, see [14]) that for stability, a necessary condition on the refresh rate is: > (log2jR(f)j) 1 max...
    • ...Using this and the techniques of Andrews et al. [8], we can construct a static, randomized throughput-optimal scheme as follows: given the optimal rate point ~ from equation 1, we can use Edmonds’ theorem to construct a tree packing, and split the incoming flow according to that packing to obtain a stable routing (i.e., associate each round with an aggregation tree) and scheduling (using ~c ) algorithm (refer to [14] for details)...
    • ...neighbor’s packet. To this end, we define a packet in node i to be useful to neighbor j if (a) j has a packet of the same round (hence ensuring aggregation); and (b) transferring the packet to j does not result in an isolated neighbor k of i (for details, refer to [14])...
    • ...And finally we have the main theorem for the stability of the algorithm. For the proof, refer to [14]...
    • ...Finally we have a theorem stating the throughput-optimality of this algorithm. The proof is given in [14]...
    • ...For extensions to a more general class of functions, refer to [14]...

    Siddhartha Banerjeeet al. Towards a Queueing-Based Framework for In-Network Function Computation

Sort by: