A SIMPLE DISTRIBUTED LOOP-FREE ROUTING STRATEGY FOR COMPUTER-COMMUNICATION NETWORKS

The loops resulting from either component failures or Load changes in a computer communication network degrade the performance and the adapt ability of conventional distributed adaptive routing strategies, such as ARPANET's previous routing strategy (APRS). In this paper, we devel op a distributed loop-free routing strategy by adding only one additio nal piece of information-the total number of minimum-delay paths-to th e commonly used routing messages and tables. Most conventional approac hes to the looping problem suffer high overheads in time and space bec ause each message must either include the first several nodes of its p ath or trace the entire path to detect a loop. By contrast, the propos ed routing strategy requires only easily obtainable information, yet r emoves loops completely. It is far more efficient in both time and spa ce than its conventional counterparts, especiallyTable Ifor sparse com puter networks. The correctness of the proposed strategy is proved, an d several illustrative e?xamples are given. The performance of this st rategy is shown to be always better than, or at least as good as, that of APRS and any multiorder routing strategies, where the order of a r outing strategy is determined by the amount of routing information car ried in each routing message.