Fault-Tolerant Computer Networks Constructed on the Basis of Combinatory Block Designs

The paper presents a new class of computer systems and networks consisting of homogeneous processors with local memory and a high-speed communication network. We carried out the topology analysis and synthesis of the given class of computer and communication networks, using combinatory objects with special properties: counterbalanced incomplete block designs (block-schemes). We give a detailed description of a class of computer communication networks which are especially appropriate for practical use - so-called Steiner triple system. These computer systems and the networks are well-structured, have a high fault tolerance, have a small average length of the way, the minimum cost of communication and gradual degradation of topology with the influence on the failure flow network. Besides, they have a free parameter which makes it possible to co-ordinate productivity and network cost. The topology of such computer networks is optimum among cyclic systems, with regard to the average diameter, productivity, fault tolerance and cost. Finally, we suggest a sufficiently simple algorithm of routing providing the fault tolerance work of a computer communication network with cyclic topology.

References

[1] Tarannikov Yu.V. Kombinatornye svoystva diskretnykh struktur i prilozheniya k kriptologii [Combinatorial properties of discrete structures and application to cryptology problems]. Moscow, MTsNMO Publ., 2011. 152 p. (in Russ.).

[2] Andreev A.M., Mozharov G.P., Syuzev V.V. Mnogoprotsessornye vychislitel’nye sistemy: teoreticheskiy analiz, matematicheskie modeli i primenenie [Multiprocessing computing systems: theoretical analysis, mathematical models and application]. Moscow, Bauman MSTU Publ., 2011. 334 p.

[3] Deza M.M., Loran M. Geometry of cuts and metrics. 1997, Springer-Verlag, Berlin, Heidelberg. 588 p. (Russ. ed.: Geometriya razrezov i metric. Moscow, MTsNMO Publ., 2001. 736 p.).

[4] Stanley R.P. Enumerative combinatorics. Vol. 2. Cambridge University Press, 1999. 595 p. (Russ. ed.: Perechislitel’naya kombinatorika. T. 2. Moscow, Mir Publ., 2009. 767 p.).

[5] Asanov M.O., Baranskiy V.A., Rasin V.V. Diskretnaya matematika: grafy, matroidy, algoritmy [The discrete mathematics: grahhs, matroids, algorithms]. Sankt-Petersburg, Lan’ Publ., 2010. 368 p. (in Russ.).

[6] Raygorodskiy A.M. Ekstremal’nye zadachi teorii grafov i analiz dannykh [Extremum problems of graphs theory and data analysis]. Moscow, RKhD Publ., 2009. 64 p. (in Russ.).

[7] Zvonkin A.K., Lando S.K. Grafy na poverkhnostyakh i ikh prilozheniya [Graphs on surfaces and their appendices]. Moscow, MTsNMO Publ., 2010. 480 p. (in Russ.).

[8] Deza M., Grishukhin V., Shtogrin M. Scale-isometric polytopal graphs in hypercubes and cubic lattices. Gardners Books, 2004. 188 p. (Russ. ed.: Izometricheskie poliedral’nye podgrafy v giperkubakh i kubicheskikh reshetkakh. Moscow, MTsNMO Publ., 2008. 192 p.)

[9] Lando S.K. Vvedenie v diskretnuyu matematiku [Introduction in discrete mathematics]. Moscow, MTsNMO Publ., 2012. 265 p. (in Russ.).

[10] Andreev A.M., Berezkin D.V., Mozharov G.P., Svirin I.S. Mathematical simulation of reliability of computer systems and networks. Vestnik MGTU im. N.E. Ваышат. Ser. Priborostroenie. Spets. vyp. "Modelirovanie i identifikatsiya komp’yuternykh sistem i setey" [Herald of the Bauman Moscow State Technical University. Ser. Instrument Engineering. Spec. iss. "Modeling and identification of computer system and links"], 2012, pp. 3-46 (in Russ.).

[11] Foss S., Shneer S., Turlikov A. Stability of a Markov-modulated Markov chain, with application to a wireless network governed by two protocols. Stochastic Systems, 2012, vol. 2, no. 1, pp. 208-231. DOI: 10.1214/11-SSY030

[12] Ziegler Gunter M. Projected Products of Polygons. Electronic Research Announcements. AMS, 2004, vol. 10, pp. 122-134. DOI: 10.1090/S1079-6762-04-00137-4

[13] Tsigler G.M. Teoriya mnogogrannikov [Polytopes theory]. Moscow, MTsNMO Publ., 2014. 568 p. (in Russ.).

[14] Alon N., Spencer J.H. The probabilistic method. New York, A Wiley Interscience Publication, 2004. 328 p. (Russ. ed.: Veroyatnostnyy metod. Moscow, BINOM Publ., 2007. 320 p.).