On traffic domination in communication networks

Abstract

Input data for communication network design/optimization problems involving multi-hour or uncertain tra c can consist of a large set of tra c matrices. These matrices are explicitly considered in prob- lem formulations for link dimensioning. However, many of these matrices are usually dominated by others so only a relatively small subset of ma- trices would be su cient to obtain proper link capacity reservations, sup- porting all original tra c matrices. Thus, elimination of the dominated matrices leads to substantially smaller optimization problems, making them treatable by contemporary solvers. In the paper we discuss the issues behind detecting domination of one tra c matrix over another. We consider two basic cases of domination: (i) total domination when the same tra c routing must be used for both matrices, and (ii) ordi- nary domination when tra c dependent routing can be used. The paper is based on our original results and generalizes the domination results known for fully connected networks.