On the Multimessage Capacity Region for Undirected Ring Networks

abstract

• The Japanese theorem is extended to multiple multicast sessions in an arbitrary network to characterize the routing capacity region by the intersection of an infinite collection of halfspaces. An elimination technique is developed to simplify this infinite description into a finite one based upon the shortest routing paths and trees in the network graph. This result is used as a step in providing the capacity regions for two multimessage multicast problems on undirected ring networks; in the first case only unicast and broadcast sessions are considered, and in the second case multicast sessions where the source and destination vertices form lines of adjacent vertices are studied. Network coding is generally necessary to achieve network capacity, but for our multimessage multicast problems, new arguments are used to demonstrate that routing can achieve network coding bounds. 2006 IEEE.

authors

• Savari, Serap

published proceedings

• IEEE TRANSACTIONS ON INFORMATION THEORY

author list (cited authors)

• Yazdi, S., Savari, S. A., Kramer, G., Carlson (Talaska), K., & Farnoud (Hassanzadeh), F.

citation count

• 4

complete list of authors

• Yazdi, SM Sadegh Tabatabaei||Savari, Serap A||Kramer, Gerhard||Carlson (Talaska), Kelli||Farnoud (Hassanzadeh), Farzad

publication date

• April 2010

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• IEEE TRANSACTIONS ON INFORMATION THEORY  Journal

keywords

• Japanese Theorem
• Multicast Sessions
• Network Capacity
• Ring Networks
• Routing

Digital Object Identifier (DOI)

• 10.1109/TIT.2010.2040866

start page

• 1930

end page

• 1947

volume

• 56

issue

• 4

URL

• http://dx.doi.org/10.1109/tit.2010.2040866