Analysis of adaptive cost functions for dynamic update policies for QoS routing in hierarchical networks

QoS routing for hierarchical networks are adopted for achieving high scalability and efficiency, e.g., the Inter/Intra Internet and the ATM Private Network-to-Network Interface (PNNI) specification. In hierarchical routing, several nodes of lower level are aggregated as a logical node of the corresponding next higher level recursively. Moreover, in PNNI, each (logical) node bundles its state information in the structure of PNNI Topology StateElements (PTSE) and sends to its neighbors periodically. That results in hierarchical routing with inaccurate information. Since, aggregated routing information is exchanged based on a time-based update policy in PNNI. However, the dynamic nature of network status makes it very difficult to set an appropriate update interval. Therefore, in this paper, we propose two cost-based adaptive update policies: Dynamic Cost-based Update policy and Dynamic Cost-based Update policy with hysteresis, which update routing information only when the change of the cost of a link exceeds a threshold. Our numerical results show that the cost-based update policies not only reduce connection blocking probability, but also decrease the frequency of routing information updates. In this paper, we analyze three approaches to define link cost function and examine the performance of the cost-based update policies under these link cost functions. We find that the proposed cost-based adaptive update policies together with the Markov Decision Process-based link cost function yield the best performance. (C) 2002 Elsevier Science Inc. All rights reserved.