计算机工程与应用2018，Vol.54Issue(5)：7-13,7.DOI:10.3778/j.issn.1002-8331.1711-0341
基于子树分解的分数组播路由网络容量分析
Analysis to capacity of fractional multicast routing network based on subtree decompo-sition
摘要
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 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.关键词
网络容量/组播/子树分解/组合设计Key words
network capacity/multicast/subtree decomposition/combinatorial design分类
信息技术与安全科学引用本文复制引用
刘宴涛,刘珩..基于子树分解的分数组播路由网络容量分析[J].计算机工程与应用,2018,54(5):7-13,7.基金项目
国家自然科学基金(No.61471045) （No.61471045）
辽宁省自然科学基金(No.20170540008). （No.20170540008）
