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.