均匀分数路由网络容量域分析  

Rate Region Analysis for Uniform Fractional Routing Networks

作　　者：刘宴涛 刘珩[2] LIU Yan-tao;LIU Heng(College of Engineering,Bohai University,Jinzhou,Liaoning 121013,China;School of Information and Electronics,Beijing Institute of Technology,Beijing 100081,China)

机构地区：[1]渤海大学工学院,辽宁锦州121013 [2]北京理工大学信息与电子学院,北京100081

出　　处：《电子学报》2018年第8期1876-1883,共8页Acta Electronica Sinica

基　　金：国家自然基金(No.61471045);辽宁省自然科学基金(No.20170540008)

摘　　要：均匀分数路由网络是指网络边传输的数据包具有相同的维数,且该维数与信源消息的维数可以不同.已知分数路由网络的容量域是多维欧式空间中的多胞体,但对各种业务模式网络的容量域的计算尚缺乏有效的可操作方法.本文研究了三种业务模式的容量域计算方法:针对多重单播,提出了基于缩减图、合并缩减图和虚拟节点的方法;针对一重组播,提出了基于子树分解和组合设计的方法;针对二重混合网络,提出了基于凸多边形极点的方法.除了理论证明之外,还举了大量样例演示这些方法的正确性.If packets are with identical dimensions,which may be different from the dimensions of source messages,the network is called uniform fractional routing network.The rate region of a fractional routing network is a polytope in a multidimensional Euclidean space,but effective implementable methods are still missing to calculate the region for networks with different traffic patterns.This paper studied rate region analysis methods for three traffic patterns:For multiple unicasts,a method based on reduced graph,union reduced graph,and virtual node was proposed;For a single multicast,it was based on subtree decomposition and combinatorial design;For a pattern mixed of two flows,the polygon region was drawn by determining all extreme points.Correctness of these methods was proved in theory and illustrated by examples.

关 键 词：分数路由 容量域 多胞体 组合设计 子树分解 

分 类 号：TN915[电子电信—通信与信息系统]