Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Information Theory
Internet Architecture
Large Classes
Network Computing
Order Statistic
Scheduling Algorithm
Wireless Network
Subscribe
Academic
Publications
Towards a QueueingBased Framework for InNetwork Function Computation
Towards a QueueingBased Framework for InNetwork Function Computation,10.1109/ISIT.2011.6034026,Siddhartha Banerjee,Piyush Gupta,Sanjay Shakkottai
Edit
Towards a QueueingBased Framework for InNetwork Function Computation
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Siddhartha Banerjee
,
Piyush Gupta
,
Sanjay Shakkottai
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 innetwork computation as compared to simple data forwarding. To this end, we define a class of functions, the FullyMultiplexible functions, which includes several functions such as parity, kth
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 minmincut. 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 MaxWeightlike 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. 25422546, 2011
DOI:
10.1109/ISIT.2011.6034026
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.
(
www.informatik.unitrier.de
)
(
adsabs.harvard.edu
)
(
arxiv.org
)
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
More »
Citation Context
(1)
...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 linkrate vector can be achieved by timesharing over admissible linkrate 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 throughputoptimal 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 throughputoptimality of this algorithm. The proof is given in [
14
]...
...For extensions to a more general class of functions, refer to [
14
]...
Siddhartha Banerjee
,
et al.
Towards a QueueingBased Framework for InNetwork Function Computation
References
(14)
Computing and communicating functions over sensor networks
(
Citations: 136
)
Arvind Giridhar
,
P. R. Kumar
Journal:
IEEE Journal on Selected Areas in Communications  JSAC
, vol. 23, no. 4, pp. 755764, 2005
Coding for computing
(
Citations: 92
)
Alon Orlitsky
,
James R. Roche
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 47, no. 3, pp. 903917, 2001
InformationTheoretic Bounds for Multiround Function Computation in Collocated Networks
(
Citations: 19
)
Nan Ma
,
Prakash Ishwar
,
Piyush Gupta
Journal:
Computing Research Repository  CORR
, vol. abs/0901.2, 2009
Optimal computation of symmetric Boolean functions in tree networks
(
Citations: 2
)
Hemant Kowshik
,
P. R. Kumar
Conference:
IEEE International Symposium on Information Theory  ISIT
, 2010
Network Coding for Computing: CutSet Bounds
(
Citations: 3
)
Rathinakumar Appuswamy
,
Massimo Franceschetti
,
Nikhil Karamchandani
,
Kenneth Zeger
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 57, no. 2, pp. 10151030, 2011
Sort by:
Citations
(1)
Towards a QueueingBased Framework for InNetwork Function Computation
(
Citations: 1
)
Siddhartha Banerjee
,
Piyush Gupta
,
Sanjay Shakkottai
Conference:
IEEE International Symposium on Information Theory  ISIT
, vol. abs/1105.5, pp. 25422546, 2011