Managing complexity in large-scale networks via flow and network aggregation
Michael Montgomery, Gustavo de Veciana · 1998
Two well-known approaches to reducing complexity in large-scale communication networks are flow and network aggregation. Flow aggregation bundles together a group of individual flows and jointly manages and switches them inside a network or subnetwork. Network aggregation hierarchically groups network elements into subnetworks and approximately represents each subnetwork's state in a compact form which reduces the overheads of information exchange in traffic management algorithms. In the flow aggregation area, we first explore the benefits of aggregating multicast demands on Virtual Path (VP) trees. We show that this can effectively reduce capacity requirements, balance network loads, and reduce the number of VP trees required. Real networks have time-varying demands and finite signaling resources, so we develop adaptive resource allocation algorithms for aggregated flows subject to such constraints. In some cases it is desirable to modify the manner in which flows are aggregated (the VP layout), so we investigate algorithms to migrate from one layout to another. For incremental changes, the potential for performance losses during migration in terms of call blocking is minimal. However, when dramatic changes in the VP layout are warranted, it is desirable to enhance performance by implementing a simple decentralized algorithm that we have proposed. In the network aggregation area, we develop an implicit representation of the congestion level of a subnetwork which is based on a distributed computation of the average implied cost to go through or into the subnetwork. We prove that both a synchronous and asynchronous computation of the implied costs will converge to a unique solution under a light load condition, and an alternative, more aggressive approximation based on additional local averaging will converge under any traffic conditions subject to sufficient damping. Our experiments show that our costs are indeed quite accurate. Based on this representation for congestion, we propose a Quality of Service-sensitive routing algorithm that is able to appropriately route high-level flows while significantly reducing complexity. The algorithm uses effective bandwidths to capture traffic behavior, and it adaptively selects hierarchical routes so as to maximize network revenue, while allowing low-level dynamic routing within subnetworks to respond to traffic fluctuations.