Network Coding for Nonuniform Demands

Cassuto, Yuval and Bruck, Jehoshua (2005) Network Coding for Nonuniform Demands. Technical Report. California Institute of Technology, Pasadena, CA. [CaltechPARADISE:2005.ETR064]

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

In this paper we define nonuniform-demand networks as a useful connection model, in between multicasts and general connections. In these networks, the source has a pool of messages, and 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 that achieve capacity in a worst-case network. 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.

EPrint Type:	Monograph (Technical Report)
Additional Information:	http://www.paradise.caltech.edu/papers/etr064.pdf
Subjects:	All Records
ID Code:	92
Deposited By:	Caltech Library System
Deposited On:	22 March 2005
Record Number:	CaltechPARADISE:2005.ETR064
Official Persistent URL:	http://resolver.caltech.edu/CaltechPARADISE:2005.ETR064
Usage Policy:	You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.

Archive Staff Only: edit this record