Fault-tolerant routing for unidirectional networks

by Lam, Chun-wing

(Uncorrected OCR) Abstract of thesis entitled

FAULT-TOLERANT ROUTING FOR UNIDIRECTIONAL NETWORKS

submitted by

LAM Chun Wing

for the degree of Master of Philosophy at The University of Hong Kong

in December 2003

Current routing protocols are based on the assumption that neighboring routers are connected by bi-directionallinks. However, unidirectional links are emerging in an increasing number of configurations. Current routing protocols are no longer acceptable, and protocols dealing with unidirectional links are needed. Although several studies have been conducted recently to produce protocols dealing with unidirectional links, the suggested protocols exhibit either communication or space overheads, and are not adequate for the purpose.

This thesis presents a distance-vector protocol for routing in networks with unidirectional links that can also handle link and node faults. Because of the unidirectional nature of the links, the design of a correct and efficient protocol for such networks is nontrivial.

The proposed protocol collects "from" information from other nodes and thereby generates routing information. Updated information is multicasted to the neighborhood. Only affected entries are propagated, in order to save bandwidth. The storage in each node ofthis protocol is O(en), where n is the number of nodes and e is the degree of a node in the network. A formal proof of the correctness of the protocol is given in the thesis.

A discrete-event network simulator for network with unidirectional links (NUDLs) is implemented to evaluate the performance of the proposed protocol. The results demonstrate that it is superior to other current distance-vector protocols for NUDLs in terms of both message complexity and message size complexity. The protocol also converges faster in relatively dense networks than in relatively sparse networks.