On state aggregation for scalable QoS routing

State (topology) aggregation is the notion of reducing nodal as well as link information to achieve scaling in a large network. In this paper, we compare the performance of three different aggregation schemes, namely, the simple-node scheme, the full-mesh scheme, and the star scheme, which represent a given group of nodes by a single logical node, a complete graph between border nodes, and a star-like graph connecting all of the border nodes, respectively. We obtain transient performance measures for multi-service networks using our Z-iteration method. We restrict the set of candidate paths to short length paths as this has been shown to be an effective way to enhance network performance. Our simulation results indicate that under a uniformly distributed workload, the scheme that has more detailed topology information performs much better, as common sense suggests. More interestingly, however, we found that as the workload becomes skewed, i.e., as it concentrates around few “hot-spot” nodes, the simple-node scheme, which is considered to be the most inaccurate aggregation scheme, appears to perform at least as well as the full-mesh scheme, which on the contrary provides the most detailed information. We attribute this result to the conflicting goals of network utilization efficiency and network load balancing, a conflict that arises when restricting the set of candidate paths