Space-efficient and accurate forwarding loop detection method using Bloom-filter for fast and reliable internet routing

Link or router node failure in a network of Internet is a typical cause of traffic congestion due to the developed forwarding loop at the router. This failure has a significant impact on Internet performance, contributed from the inability of the affected router to find alternative link/route in fast manner and from the high probability of packet dropping during the attempt of re-routing. The existing Internet approach in handling this issue is to use TTL (time-to-live) of TCP/IP, by which a packet will be dropped whenever the TTL timer expires. However, this approach was found inefficient due to long convergence period. Hence, the effort now is to develop a faster re-routing mechanism, by reducing the possibility of forwarding loop incidents for any cases of link/node failures, whilst minimizing packet losses during the convergence period. This work proposes a novel detection method for possible forwarding loop incidents at a router with support of Bloom-filter. Bloom-filter is a probabilistic data structure that helps to ensure the availability of an item in a set, which never lead to false negative results, but may produce false positive results. With this Bloom-filter-based method, link�s or node�s failure information is attached at the packet header of a packet in a space-efficient manner and to accurately detect for possible incidents of forwarding loop when the packet is traversing through its route from source to destination. If the possibility can be more accurately detected, then packets losses can be minimized to very least during the convergence period and hence, fast and reliable routing shall be achieved. Through simulations, it was found that the proposed method of BF-k/2 has outperformed the other re-routing methods. It has not only efficiently used the limited space of the packet header, but also adaptively reducing the false positive probabilities for reliable routing. © 2005 - 2015 JATIT & LLS. All rights reserved.