Connectivity Problem Solution for Direction Ordered Deterministic Routing in nD Torus

I. A. Pozhilov, Researcher, e-mail: ilyapoz@gmail.com, A. S. Semenov, Head от Sector, e-mail: alxdr.Semenov@gmail.com, D. V. Makagon, Head от Department, e-mail: makagond@nicevt.ru, Joint-stock company "Scientific Research Centre for Electronic Computer Technology", Moscow

Connectivity problem for nD torus with link failures is addressed. An algorithm is proposed to solve the problem in the general case. Connectivity loss probability for given number of link failures examined for non-minimal direction ordered routing, First Step/Last Step method and the complete routing algorithms. First Step/Last Step is shown to be adequate for maintaining connectivity.

Keywords: fault tolerance, communication networks, multidimensional torus, connectivity, deterministic routing, direction ordered routing

pp. 13–19