An overview of stochastic partitioning algorithms and their performance

The main goals of quality-of-service (QoS) routing algorithms are: (1) to try to accommodate new connections which expect certain end-to-end QoS requirements and (2) to improve the overall network efficiency. These QoS requirements are in the form of delay, jitter, packet-loss and bandwidth. In order to accommodate every new connection through the network that satisfies the QoS, the resources must be controlled and reserved. However, there are issues related to scalability of QoS routing algorithms in large networks and the increased cost involved in terms of rapid computations. The problem of scaling QoS routing algorithms in the environment of large networks using partitioning is studied in this paper. In particular, the paper focuses on a review of the so called stochastic partitioning (SP) methods that dynamically change a network partition according to the traffic patterns in the network in order to minimise an objective function that reflects the computational effort involved in the underlying routing algorithms used in the network. Such methods therefore exploit the interactions between the network topology, the traffic flows and the routing which are not collectively considered by other forms of partitioning. Stochastic partitioning can be used to scale any routing algorithms so that the computational effort remains bounded to a manageable value as the number of network nodes grows. The performance is thus measured in terms of reduction in computational effort compared with non-partitioned networks.