Fault-tolerant convergence routing

Abstract

This paper presents fault-tolerant protocols for fast packet switch networks withconvergence routing. The objective is to provide fast reconfiguration and continuous host-to-host communication after a link or a node (switch) failure,Convergence routingcan be viewed as a variant ofdeflection routing,which combines, in a dynamic fashion, the on-line routing decision with the traffic load inside the network. Unlike other deflection techniques, convergence routing operates withglobal sense of directionand guarantees that packets will reach or converge to their destinations. Global sense of direction is achieved by embedding of virtual rings to obtain a linear ordering of the nodes. We consider virtual ring embeddings over (i) a single spanning tree, and (ii) over two edge-disjoint spanning trees. Thus, the fault-tolerant solution is based on spanning trees and designed for a switch-based (i.e., arbitrary topology) architecture called MetaNet. In this work, the original MetaNet's convergence routing scheme has been modified in order to facilitate the property that the packet header need not be recomputed after a failure and/or a reconfiguration. This is achieved by having, at the network interface, a translator that maps the unique destination address to a virtual address. It is argued that virtual rings embedded over two-edge disjoint spanning trees increase the fault tolerance for both node and link faults and provides continuous host-to-host communication. © 1997 Academic Press.