CaltechAUTHORS
  A Caltech Library Service

Network coding for non-uniform demands

Cassuto, Yuval and Bruck, Jehoshua (2005) Network coding for non-uniform demands. In: International Symposium on Information Theory (ISIT 2005), Adelaide, Australia, 4-9 September 2005. IEEE , Piscataway, NJ, pp. 1720-1724. ISBN 0-7803-9151-9 http://resolver.caltech.edu/CaltechAUTHORS:CASisit05

[img]
Preview
PDF - Published Version
See Usage Policy.

227Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:CASisit05

Abstract

Non-uniform demand networks are defined as a useful connection model, in between multicasts and general connections. In these networks, each sink demands a certain number of messages, without specifying their identities. We study the solvability of such networks and give a tight bound on the number of sinks for which the min cut condition is sufficient. This sufficiency result is unique to the non-uniform demand model and does not apply to general connection networks. We propose constructions to solve networks at, or slightly below capacity, and investigate the effect large alphabets have on the solvability of such networks. We also show that our efficient constructions are suboptimal when used in networks with more sinks, yet this comes with little surprise considering the fact that the general problem is shown to be NP-hard.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/ISIT.2005.1523639DOIUNSPECIFIED
http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1523639PublisherUNSPECIFIED
Additional Information:© Copyright 2005 IEEE. Reprinted with permission. Publication Date: 4-9 Sept. 2005. This work was supported in part by the Caltech Lee Center for Advanced Networking and by NSF grant ANI-0322475.
Funders:
Funding AgencyGrant Number
Lee Center for Advanced Networking ,CaltechUNSPECIFIED
National Science FoundationANI-0322475
Subject Keywords:computability; computational complexity; directed graphs; encoding; multicast communication; optimization; NP-hard problem; connection model; min cut condition; network coding; network solvability; nonuniform demand networks
Record Number:CaltechAUTHORS:CASisit05
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:CASisit05
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:12449
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:03 Dec 2008 23:50
Last Modified:26 Dec 2012 10:32

Repository Staff Only: item control page