关键词: 网络容量, 组播, 子树分解, 组合设计

Abstract: Network capacity measures the maximum transmission rate of a network. Determining network capacity is a fundamental mission in network information theory. Network capacity is classified into coding capacity and routing capacity. For a single session multicast network, coding capacity is characterized by the minimum min-cut between the source node and sink nodes. While, its routing capacity is impacted by topology, the number and position of source and sinks, so that a similar simple general conclusion does not exist. For any given network, routing capacity needs to be calculated specifically. Calculating routing capacity for a multicast network can be modeled by the Packing Steiner Trees problem, which is proven to be NP-hard. An efficient method for multicast routing capacity calculationis still missing. This paper addresses routing capacity analysis for a fractional multicast routing network, whose source message and link capacity are integral dimensional. Within this category, multicast routing capacity analysis can be modeled by a combinatorial design problem. A method is proposed to solve the problem. The key point of the method is leveraging subtree decomposition to greatly reduce network scale so as to decrease the complexity of combinatorial design. Two examples related to a three-layer network model are given to illustrate the implementation of the method.

Key words: network capacity, multicast, subtree decomposition, combinatorial design