A Scheme to Update OSPF Network Metrics without Loops while Minimizing Routing Instability Duration

摘要

This letter proposes a scheme to update metrics without loops while minimizing routing instability time in an Open Shortest Path First (OSPF) network. The original OSPF network enters the transient state when metrics are being updated to improve the routing performance, and in this state packets may fall into loops. This may cause packet loss and inefficient network resource utilization. To avoid transient loops, a conventional scheme gives each router a priority that reflects the optimum time for metric update. However, when the updated metrics include both larger and smaller values than the preceding ones, two sequential updating processes, one for larger values and one for smaller values, are required. It takes time to converge on the final metric values in the conventional scheme, given that the interval time between the two processes is not insignificant. The second process starts only when the first process is confirmed to be completed. The interval time including the confirmation time and the time needed to reconfigure the metrics in all routers, lengthens the transient state duration; from several seconds to several tens of seconds. This causes routing instability. The proposed scheme transforms the set of updated metrics into an equivalent set of metrics that are either all larger or all smaller (if changed at all) than the ones before the update. The set of equivalent metrics yield exactly the same results in terms of routing as the conventional scheme, i.e. the result desired by the network operator. The non-mixture update requires only one updating process and so eliminates the interval time. Numerical results indicate that the probability that the proposed scheme can achieve non-mixture update is more than 67% in the networks examined.