When is n-pairs information a multicommodity flow?
Girish N. Nair · 2011
Information does not generally behave like a flow in communication networks with multiple sources and sinks. However, it is often conceptually and practically useful to be able to associate separate data streams with each source-sink pair, with only routing and no coding performed at the network nodes. This raises the question of whether there is a nontrivial class of network topologies for which achievability is always equivalent to “routability”, for any combination of source signals and positive channel capacities. This paper considers a possibly cyclic, directed, errorless network with n source-sink pairs, mutually independent source signals, and a relaxed communication objective in terms of demanded information rates at sinks. The concept of triangularizability is introduced and it is shown that, if the network topology is triangularizable, then a given combination of source signals, demand rates and channel capacities is achievable if and only if the digraph supports a feasible multicommodity flow.