ALGORITHM FOR EFFICIENT GENERATION OF LINK-STATE UPDATES IN ATM NETWORKS

In the routing framework defined by the ATM Forum Private Network Node Interface (P-NNI) working group, each node broadcasts link-state upda te (LSU) messages (which include information such as available bandwid th, maximum delay, etc.) about the outgoing links attached to it to ot her nodes in the network. For each connection request, the source node selects an end-to-end route that meets the quality of service (QoS) r equirements of the connection based on the most recent information tha t it has about network links. Up-to-date information about network lin ks is, therefore, key to making ''good'' routing decisions. The trigge ring of LSU broadcasts after adding or removing a single connection on any link would certainly enable optimal paths to be calculated but at a potentially significant cost in processing and bandwidth. A periodi c update scheme, on the other hand, might be more preferable since it can be used to bound the frequency of updates at the expense of delayi ng important updates (such as those reporting large changes in link lo ad), The goal of an efficient LSU generating algorithm is, therefore, to provide ''accurate'' information on link loads while keeping the nu mber of LSUs under control. In this paper, we investigate the issue of when to broadcast LSUs and its effects to the network performance, A simulation model is built to model the basic routing framework develop ed at the ATM Forum P-NNI working group, Based on the intuition gained by running the simulation model with different schemes and parameters , a hybrid LSU generating algorithm, combining event-driven and period ic update strategies, is proposed to substantially reduce the number o f LSUs generated in the network without a significant negative impact on the network performance. The proposed algorithm is not limited to t he P-NNI framework and it can be used in networking technologies that are based on the link-state principles.