MATHEMATICAL ENGINEERING TECHNICAL REPORTS Computing a DAG using MA ordering for the all-to-one maximum ∞ow routing problem

The purpose of the Internet routing system is to construct a Directed Acyclic Graph (DAG) for each destination. Although the number of paths and the connectivity of the graph are important properties, constructing a DAG that includes all edges to increase the number of paths and the connectivity has not been studied. In this paper we describe a new problem called all-to-one maximum flow routing problem that maximizes the minimum of maximum flow among all nodes to a destination. We studied an algorithm that utilizes the MA ordering to find the desirable DAG for a given network. It is proven that the algorithm produces the optimal solution, and the time complexity is the same with that of the MA ordering, O(m+n log n) where m and n are the number of edges and nodes, respectively. Simulations showed that the routing calculated by MA ordering outperforms current shortest path routing significantly in terms of maximum flow on each pair of nodes, but for the link utilization on a traffic demand of random model between multiple pair of nodes, MA ordering is outperformed by the shortest path routing because of a lack of efficient method to compute traffic split ratio.