检索结果-内蒙古大学图书馆

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

QUEUEING SYSTEMS 2012年第3-4期72卷 219-250页

作者： Banerjee, Siddhartha Gupta, Piyush Shakkottai, Sanjay Univ Texas Austin Dept ECE Austin TX 78705 USA Bell Labs Math Networks & Commun Murray Hill NJ 07974 USA

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 kth-order statistics. For such functions we 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.

关键词： in-network function computation Wireless sensor networks Dynamic routing and scheduling algorithms

来源：评论

学校读者我要写书评

暂无评论

Reduced Complexity Sum-Product Algorithm for Decoding Nonlinear network Codes and in-network function computation

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2016年第10期64卷 4070-4082页

作者： Gupta, Anindya Rajan, B. Sundar Indian Inst Sci Dept Elect Commun Engn Bengaluru 560012 India

While the capacity, feasibility, and methods to obtain codes for network coding problems are well studied, the decoding procedure and complexity have not garnered much attention. In this paper, we pose the decoding problem at a sink node in a network as a marginalize product function (MPF) problem over the Boolean semiring and use the sum product (SP) algorithm on a suitably constructed factor graph to perform iterative decoding. The number of operations required to perform SP decoding is reduced using traceback. The number of operations required to perform SP decoding with and without traceback is obtained. For nonlinear network codes, we define fast decodability of a network code at sinks demanding all the messages and identify a sufficient condition for the same. Next, we consider the network function computation problem wherein the sink nodes demand a function of the messages. We present an MPF formulation for function computation at the sink nodes and use the SP algorithm to obtain the value of the demanded function. Though the proposed method can be used for decoding both linear and nonlinear network codes, it is advantageous only for the case of nonlinear network codes.

关键词： Decoding in-network function computation network coding sum-product algorithm traceback

来源：评论

学校读者我要写书评

暂无评论

Efficient Flow Allocation Algorithms for in-network function computation

Efficient Flow Allocation Algorithms for In-Network Function...

引用

54th Annual IEEE Global Telecommunications Conference (GLOBECOM)

作者： Shah, Virag Dey, Bikash Kumar Manjunath, D. Univ Texas Austin Dept ECE Austin TX 78712 USA

ISBN: (纸本)9781424492688

We consider in-network computation of an arbitrary function over an arbitrary communication network. We consider the same model as our earlier work in [1]. The given network consists of directed/undirected links with capacity constraints, some source nodes which generate data, and other intermediate forwarding nodes. An arbitrary function of this distributed data is to be computed at a terminal node. The structure of the function is described by a given computation schema represented by a directed tree. In our earlier work, we presented a linear program to define the maximum rate of computation, and then introduced a notion of flow-conservation suitable in this context so as to come up with a flow-conservation based linear program which can be solved in polynomial time. In this paper, we develop a combinatorial primal-dual algorithm to obtain (1-epsilon)-approximate solutions to these linear programs. As a part of this, we present an algorithm to find a minimum-cost embedding in a network of weighted links-which is of independent interest. We then describe application of our techniques to other practically interesting problems of multiple terminals wanting different functions, computation with a given desired precision, and to networks with energy constraints at nodes.

关键词： Approximation algorithms Complexity theory Distributed databases IEEE Communications Society Peer to peer computing Vectors arbitrary communication network capacity constraints combinatorial primal-dual algorithm computation schema directed tree distributed data energy constraints flow allocation algorithm flow conservation in-network function computation intermediate forwarding nodes linear program linear programming minimum cost embedding polynomial time polynomials source nodes telecommunication network management terminal node

来源：评论

学校读者我要写书评

暂无评论

Reduced Complexity Sum-Product Algorithm for Decoding Nonlinear network Codes and in-network function computation

Reduced Complexity Sum-Product Algorithm for Decoding Nonlin...

引用

IEEE International Conference on Communications (ICC)

作者： Gupta, Anindya Rajan, B. Sundar Indian Inst Sci Dept Elect Commun Engn Bengaluru 560012 India

关键词： Decoding in-network function computation network coding sum-product algorithm traceback

来源：评论

学校读者我要写书评

暂无评论

Fast Arbitrary function computation over a Wireless network: A Linear Programming Approach

Fast Arbitrary Function Computation over a Wireless Network:...

引用

IEEE Wireless Communications and networking Conference (WCNC)

作者： Shukla, Samta Vyavahare, Pooja Kuri, Joy Manjunath, D. RPI Troy NY 12180 USA Indian Inst Technol Bombay Maharashtra India IISc Bangalore Bangalore Karnataka India

ISBN: (纸本)9781479984060

in-network function computation (INFC) is becoming an essential aspect of large database systems where the data is distributed over the network. Such situations arise often in resource constrained wireless sensor network making them a natural candidate for INFC. We study the problem of maximizing the rate of INFC in wireless networks. In this paper, we develop a functional flow model for INFC when the function computation sequence is represented by a directed acyclic graph. We propose a linear program formulation to maximize the rate of INFC over all possible embeddings. We also formulate a mixed integer linear program (MILP) for maximizing the rate of computation for a single embedding on a capacity constrained wireless network. The MILP for finding the single embedding that yields maximum rate turns out to be NP hard;we develop a heuristic to solve this problem by formulating a linear program. We provide numerical results to illustrate the performance of these formulations.

关键词： in-network function computation wireless network operator placement embedding arbitrary function maximum rate interference maximal independent sets

来源：评论

学校读者我要写书评

暂无评论

Optimal Embedding of functions for In-network computation: Complexity Analysis and Algorithms

引用

IEEE-ACM TRANSACTIONS ON networkING 2016年第4期24卷 2019-2032页

作者： Vyavahare, Pooja Limaye, Nutan Manjunath, D. Indian Inst Technol Dept Elect Engn Bombay 400076 Maharashtra India Indian Inst Technol Dept Comp Sci & Engn Bombay 400076 Maharashtra India

We consider optimal distributed computation of a given function of distributed data. The input (data) nodes and the sink node that receives the function form a connected network that is described by an undirected weighted network graph. The algorithm to compute the given function is described by a weighted directed acyclic graph and is called the computation graph. An embedding defines the computation communication sequence that obtains the function at the sink. Two kinds of optimal embeddings are sought, the embedding that: 1) minimizes delay in obtaining function at sink, and 2) minimizes cost of one instance of computation of function. This abstraction is motivated by three applications-in-network computation over sensor networks, operator placement in distributed databases, and module placement in distributed computing. We first show that obtaining minimum-delay and minimum-cost embeddings are both NP-complete problems and that cost minimization is actually MAX SNP-hard. Next, we consider specific forms of the computation graph for which polynomial-time solutions are possible. When the computation graph is a tree, a polynomial-time algorithm to obtain the minimum-delay embedding is described. Next, for the case when the function is described by a layered graph, we describe an algorithm that obtains the minimum-cost embedding in polynomial time. This algorithm can also be used to obtain an approximation for delay minimization. We then consider bounded treewidth computation graphs and give an algorithm to obtain the minimum-cost embedding in polynomial time.

关键词： Graph embedding in-network function computation operator placement

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：