电子学报 ›› 2018, Vol. 46 ›› Issue (8): 1876-1883.DOI: 10.3969/j.issn.0372-2112.2018.08.011

• 学术论文 • 上一篇    下一篇

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

刘宴涛1, 刘珩2   

  1. 1. 渤海大学工学院, 辽宁锦州 121013;
    2. 北京理工大学信息与电子学院, 北京 100081
  • 收稿日期:2017-03-31 修回日期:2018-01-17 出版日期:2018-08-25 发布日期:2018-08-25
  • 作者简介:刘宴涛 男,1975年生于吉林蛟河,渤海大学副教授,研究方向为网络编码、网络仿真、Ad hoc网络、网络安全、分布式存储等.Email:liuyantaocn@vip.163.com;刘珩 女,1981年生于湖北恩施,北京理工大学信息与电子学院副教授,2006年获得北京理工大学通信与信息系统博士学位,研究方向包括通信协议工程、无线自组织网络、传感器网络、分布式系统、网络仿真等.
  • 基金资助:
    国家自然基金(No.61471045);辽宁省自然科学基金(No.20170540008)

Rate Region Analysis for Uniform Fractional Routing Networks

LIU Yan-tao1, LIU Heng2   

  1. 1. College of Engineering, Bohai University, Jinzhou, Liaoning 121013, China;
    2. School of Information and Electronics, Beijing Institute of Technology, Beijing 100081, China
  • Received:2017-03-31 Revised:2018-01-17 Online:2018-08-25 Published:2018-08-25

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

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

Abstract: 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.

Key words: fractional routing, rate region, polytope, combinatorial design, subtree decomposition

中图分类号: