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

Rate Region Analysis for Uniform Fractional Routing Networks

均匀分数路由网络是指网络边传输的数据包具有相同的维数,且该维数与信源消息的维数可以不同.已知分数路由网络的容量域是多维欧式空间中的多胞体,但对各种业务模式网络的容量域的计算尚缺乏有效的可操作方法.本文研究了三种业务模式的容量域计算方法:针对多重单播,提出了基于缩减图、合并缩减图和虚拟节点的方法;针对一重组播,提出了基于子树分解和组合设计的方法;针对二重混合网络,提出了基于凸多边形极点的方法.除了理论证明之外,还举了大量样例演示这些方法的正确性.

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.