Computer Science – Networking and Internet Architecture
Scientific paper
2008-10-09
Computer Science
Networking and Internet Architecture
26 pages, 27 figures, submitted to IEEE Transactions on Information Theory
Scientific paper
The problem of serving multicast flows in a crossbar switch is considered. Intra-flow linear network coding is shown to achieve a larger rate region than the case without coding. A traffic pattern is presented which is achievable with coding but requires a switch speedup when coding is not allowed. The rate region with coding can be characterized in a simple graph-theoretic manner, in terms of the stable set polytope of the "enhanced conflict graph". No such graph-theoretic characterization is known for the case of fanout splitting without coding. The minimum speedup needed to achieve 100% throughput with coding is shown to be upper bounded by the imperfection ratio of the enhanced conflict graph. When applied to KxN switches with unicasts and broadcasts only, this gives a bound of min{(2K-1)/K,2N/(N+1)} on the speedup. This shows that speedup, which is usually implemented in hardware, can often be substituted by network coding, which can be done in software. Computing an offline schedule (using prior knowledge of the flow rates) is reduced to fractional weighted graph coloring. A graph-theoretic online scheduling algorithm (using only queue occupancy information) is also proposed, that stabilizes the queues for all rates within the rate region.
Eryilmaz Atilla
Kim MinJi
Koetter Ralf
Medard Muriel
Sundararajan Jay Kumar
No associations
LandOfFree
Network Coding in a Multicast Switch does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Network Coding in a Multicast Switch, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network Coding in a Multicast Switch will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-526462