FAULT-TOLERANT CONVERGENCE ROUTING

This paper presents fault-tolerant protocols for fast packet switch ne tworks with convergence routing, The objective is to provide fast reco nfiguration and continuous host-to-host communication after a link or a node (switch) failure, Convergence routing can be viewed as a varian t of deflection 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 with global sense of direction and guarantees that packets will reach or converge to their destinations, Global sense of direction is achieved by embed ding of virtual rings to obtain a linear ordering of the nodes, We con sider virtual ring embeddings over (i) a single spanning tree, and (ii ) over two edge-disjoint spanning trees, Thus, the fault-tolerant solu tion is based on spanning trees and designed for a switch-based (i,e,, arbitrary topology) architecture called MetaNet, In this work, the or iginal MetaNet's convergence routing scheme has been modified in order to facilitate the property that the packet header need not be recompu ted after a failure and/or a reconfiguration, This is achieved by havi ng, at the network interface, a translator that maps the unique destin ation address to a virtual address, It is argued that virtual rings em bedded over two-edge disjoint spanning trees increase the fault tolera nce for both node and link faults and provides continuous host-to-host communication, (C) 1997 Academic Press.