A virtual clustering approach for routing problems in telecommunication networks

We propose an adaptable routing scheme for telecommunication networks based on the notion of virtual clustering. Virtual clustering logically reconfigures the network topology in a periodic basis according to the traffic requirements in the network. This temporary topology configuration imposes restrictions on the potential paths between certain groups of source–destination node pairs, thus regulating and balancing the global network traffic while maintaining sufficient local flexibility for real-time routing. The proposed routing scheme can be implemented in an established telecommunication environment where the actual routing of network traffic is conducted by an existing dynamic routing algorithm, while the routing tables are preprocessed by the current virtual clustering configuration. We develop a virtual clustering algorithm using problem space search proposed by Storer, Wu and Vaccari. The algorithm iteratively evaluates clustering solutions and their potential impact to routing performance by perturbation of the traffic requirement matrix. The proposed routing scheme is tested through intensive computational experiments on randomly generated geometric networks, and on PREPNET, a real-world sub-network on the Internet. Using Monte Carlo simulation, we compare the proposed routing scheme to centralized routing and decentralized asynchronous routing. Computational results show that the proposed approach significantly outperforms these traditional schemes under dynamic traffic fluctuation.