Cassuto, Yuval and Bruck, Jehoshua (2005) Network Coding for Nonuniform Demands. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2005.ETR064
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2005.ETR064
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.
|Item Type:||Report or Paper (Technical Report)|
|Group:||Parallel and Distributed Systems Group|
|Usage Policy:||You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.|
|Deposited By:||Imported from CaltechPARADISE|
|Deposited On:||22 Mar 2005|
|Last Modified:||26 Dec 2012 13:53|
Repository Staff Only: item control page