基于子树分解的分数组播路由网络容量分析

摘要

网络容量度量了网络的最大信息传输率,计算网络容量是网络信息论的基本任务.网络容量可以分为编码容量和路由容量,一重组播网络的编码容量已被证明等于信源和各个信宿之间最小割的最小值,但路由容量却由于受到网络拓扑、信源信宿的数目和位置等因素的影响不存在这样简单和一般化的结论,对具体网络需要做出具体分析.组播路由网络容量分析可建模为Packing Steiner Trees问题,但该问题是NP-hard的,目前尚缺乏计算组播路由网络容量的有效方法.讨论分数组播路由网络的容量分析问题,分数网络的信源消息和边容量都是整数维的,在这个范畴内,把组播路由网络的容量分析建模为组合设计问题并提出一种方法加以解决,该方法的关键点在于通过子树分解技术大大缩减了网络规模,由此降低了组合设计的复杂度,并通过对三层网络的分析演示了该方法的使用.%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 dimen-sional. 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.