Multi-session function computation and multicasting in undirected graphs

Sreeram Kannan, Pramod Viswanath

Research output: Contribution to journalArticle

Abstract

In the function computation problem, certain nodes of an undirected graph have access to independent data, while some other nodes of the graph require certain functions of the data; this model, motivated by sensor networks and cloud computing, is the focus of this paper. We study the maximum rates at which function computation is possible on a capacitated graph; the capacities on the edges of the graph impose constraints on the communication rate. We consider a simple class of computation strategies based on Steiner-tree packing (so-called em computation trees), which does not involve block coding and has minimal delay. With a single terminal requiring function computation, computation trees are known to be optimal when the underlying graph is itself a directed tree, but have arbitrarily poor performance in general directed graphs. Our main result is that computation trees are em near optimal for a wide class of function computation requirements even at em multiple terminals in em undirected graphs. The key technical contribution involves connecting approximation algorithms for Steiner cuts in undirected graphs to the function computation problem. Furthermore, we show that existing algorithms for Steiner tree packings allow us to compute approximately optimal packings of computation trees in polynomial time. We also show a close connection between the function computation problem and a communication problem involving multiple multicasts.

Original languageEnglish (US)
Article number6481624
Pages (from-to)702-713
Number of pages12
JournalIEEE Journal on Selected Areas in Communications
Volume31
Issue number4
DOIs
StatePublished - Apr 4 2013

Fingerprint

Multicasting
Trees (mathematics)
Communication
Directed graphs
Approximation algorithms
Cloud computing
Sensor networks
Polynomials

Keywords

  • Function computation
  • Steiner packing
  • capacity
  • computation trees
  • multicasting
  • multiple unicast
  • network coding
  • sensor networks

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Cite this

Multi-session function computation and multicasting in undirected graphs. / Kannan, Sreeram; Viswanath, Pramod.

In: IEEE Journal on Selected Areas in Communications, Vol. 31, No. 4, 6481624, 04.04.2013, p. 702-713.

Research output: Contribution to journalArticle

@article{ab39fac00571492cb6b4f66ca7c332b8,
title = "Multi-session function computation and multicasting in undirected graphs",
abstract = "In the function computation problem, certain nodes of an undirected graph have access to independent data, while some other nodes of the graph require certain functions of the data; this model, motivated by sensor networks and cloud computing, is the focus of this paper. We study the maximum rates at which function computation is possible on a capacitated graph; the capacities on the edges of the graph impose constraints on the communication rate. We consider a simple class of computation strategies based on Steiner-tree packing (so-called em computation trees), which does not involve block coding and has minimal delay. With a single terminal requiring function computation, computation trees are known to be optimal when the underlying graph is itself a directed tree, but have arbitrarily poor performance in general directed graphs. Our main result is that computation trees are em near optimal for a wide class of function computation requirements even at em multiple terminals in em undirected graphs. The key technical contribution involves connecting approximation algorithms for Steiner cuts in undirected graphs to the function computation problem. Furthermore, we show that existing algorithms for Steiner tree packings allow us to compute approximately optimal packings of computation trees in polynomial time. We also show a close connection between the function computation problem and a communication problem involving multiple multicasts.",
keywords = "Function computation, Steiner packing, capacity, computation trees, multicasting, multiple unicast, network coding, sensor networks",
author = "Sreeram Kannan and Pramod Viswanath",
year = "2013",
month = "4",
day = "4",
doi = "10.1109/JSAC.2013.130408",
language = "English (US)",
volume = "31",
pages = "702--713",
journal = "IEEE Journal on Selected Areas in Communications",
issn = "0733-8716",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "4",

}

TY - JOUR

T1 - Multi-session function computation and multicasting in undirected graphs

AU - Kannan, Sreeram

AU - Viswanath, Pramod

PY - 2013/4/4

Y1 - 2013/4/4

N2 - In the function computation problem, certain nodes of an undirected graph have access to independent data, while some other nodes of the graph require certain functions of the data; this model, motivated by sensor networks and cloud computing, is the focus of this paper. We study the maximum rates at which function computation is possible on a capacitated graph; the capacities on the edges of the graph impose constraints on the communication rate. We consider a simple class of computation strategies based on Steiner-tree packing (so-called em computation trees), which does not involve block coding and has minimal delay. With a single terminal requiring function computation, computation trees are known to be optimal when the underlying graph is itself a directed tree, but have arbitrarily poor performance in general directed graphs. Our main result is that computation trees are em near optimal for a wide class of function computation requirements even at em multiple terminals in em undirected graphs. The key technical contribution involves connecting approximation algorithms for Steiner cuts in undirected graphs to the function computation problem. Furthermore, we show that existing algorithms for Steiner tree packings allow us to compute approximately optimal packings of computation trees in polynomial time. We also show a close connection between the function computation problem and a communication problem involving multiple multicasts.

AB - In the function computation problem, certain nodes of an undirected graph have access to independent data, while some other nodes of the graph require certain functions of the data; this model, motivated by sensor networks and cloud computing, is the focus of this paper. We study the maximum rates at which function computation is possible on a capacitated graph; the capacities on the edges of the graph impose constraints on the communication rate. We consider a simple class of computation strategies based on Steiner-tree packing (so-called em computation trees), which does not involve block coding and has minimal delay. With a single terminal requiring function computation, computation trees are known to be optimal when the underlying graph is itself a directed tree, but have arbitrarily poor performance in general directed graphs. Our main result is that computation trees are em near optimal for a wide class of function computation requirements even at em multiple terminals in em undirected graphs. The key technical contribution involves connecting approximation algorithms for Steiner cuts in undirected graphs to the function computation problem. Furthermore, we show that existing algorithms for Steiner tree packings allow us to compute approximately optimal packings of computation trees in polynomial time. We also show a close connection between the function computation problem and a communication problem involving multiple multicasts.

KW - Function computation

KW - Steiner packing

KW - capacity

KW - computation trees

KW - multicasting

KW - multiple unicast

KW - network coding

KW - sensor networks

UR - http://www.scopus.com/inward/record.url?scp=84875632788&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84875632788&partnerID=8YFLogxK

U2 - 10.1109/JSAC.2013.130408

DO - 10.1109/JSAC.2013.130408

M3 - Article

AN - SCOPUS:84875632788

VL - 31

SP - 702

EP - 713

JO - IEEE Journal on Selected Areas in Communications

JF - IEEE Journal on Selected Areas in Communications

SN - 0733-8716

IS - 4

M1 - 6481624

ER -