Formalization and Analysis of Routing Loops by Inconsistencies in IP Forwarding Tables

Kazuya SUZUKI  Masahiro JIBIKI  

Publication
IEICE TRANSACTIONS on Communications   Vol.E90-B   No.10   pp.2755-2763
Publication Date: 2007/10/01
Online ISSN: 1745-1345
DOI: 10.1093/ietcom/e90-b.10.2755
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Section on New Challenge for Internet Technology and its Architecture)
Category: 
Keyword: 
high availability,  routing protocol,  the Internet,  router,  

Full Text: PDF>>
Buy this Article




Summary: 
The effect of inconsistencies in forwarding tables on the reachability of IP packets is evaluated. To improve a router's availability, in the architecture of current routers, the control element is separated from the forwarding element. However, a router with the current architecture cannot handle a notification for which the topology of the network system changes when its control element has stopped. In such a case, the router cannot update its own forwarding table, and an inconsistency between the forwarding tables of the router and those of the other routers will occur. To investigate the influence of this inconsistency, we formalize the network system, and derive the conditions under which such an inconsistency leads to unreachable routes. After that, the number of routes that are unreachable is evaluated by simulations. These simulations show that routing loops occur more frequently under the condition that a failed node is close to the restarting node or fewer links exist in the network system.