×

Large fault-tolerant interconnection networks. (English) Zbl 0672.94021

Summary: This paper deals with reliability and fault-tolerant properties of networks. We first survey general reliability properties of networks, in particular those concerning diameter vulnerability. Then we study in details reliability properties of some families of networks in particular de Bruijn and Kautz networks and their generalizations which appear as very good fault-tolerant networks.

MSC:

94C15 Applications of graph theory to circuits and networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akers, S.B., Harel, D., Krishnamurthy, B.: The star graph: an attractive alternative to then-cube. 16th Conf. on Parallel Processing, 1987, pp. 393–400
[2] Akers, S.B., Krishnamurthy, B.: On group graphs and their fault tolerance. IEEE Trans. Comput.C-36, 885–888 (1987) · Zbl 0641.94049
[3] Amar, D.: On the connectivity of some telecommunication networks. IEEE Trans. Comput.C-32, 512–519 (1983)
[4] Ameter, D., de Gree, Max: Graphs and Interconnection networks. (Forthcoming book)
[5] Berge, C.: Graphs and hypergraphs. New-York: North-Holland Publishing Co. (1973) · Zbl 0254.05101
[6] Bermond, J.-C., Homobono, N., Peyrat, C.: Large fault-tolerant interconnection networks. LRI Research Report, 1986 · Zbl 0672.94021
[7] Bermond, J.-C., Bollobas, B.: The diameter of graphs- a survey. Proc. 12-th Southeastern Conference, Congressus Num.32, 3–27 (1981) · Zbl 0504.05038
[8] Bermond, J.-C., Bond, J., Paoli, M., Peyrat, C.: Graphs and interconnection networks: diameter and vulnerability. In surveys in combinatorics: Proc. 9-th British Combinatorial Conference, London Math. Soc., Lec. Notes Ser.82, 1–30 (1983) · Zbl 0525.05018
[9] Bermond, J.-C., Comellas, F., Hsu, F.: Distributed loop computer networks: a survey. IEEE trans. Comput. (1988) (submitted)
[10] Bermond, J.-C., Delorme, C., Quisquater, J.-J.: Strategies for interconnection networks: some methods from graph theory. J. of Parallel and Distributed Comput.3, 433–449 (1986)
[11] Bermond, J.-C., Favaron, O., Maheo, M.: Hamiltonian decomposition of Cayley graphs of degree four. J. Comb. Theory (B) (1988) · Zbl 0618.05032
[12] Bermond, J.-C., Illiades, G., Peyrat, C.: An optimization problem in distributed loop computer networks. In: Proc. third international conference on combinatorial math., New York, 1985, Annals N.Y. Acad. Science (1988) · Zbl 0727.68088
[13] Bhatt, S., Chung F.R.K., Leighton, T., Rosenberg, A.: Optimal simulations of tree machines. Proc. FOCS. pp. 274–282 (1986)
[14] Boesch, F.T.: Graph theoretic models for network reliability studies. Stevens Institute of technology, electrical engineering and computer science department, Technical Report 8010, 1980
[15] Boesch, F.T., Tindell, R.: Circulants and their connectivities. J. Graph Theory8, 487–499 (1984) · Zbl 0549.05048
[16] Boesch, F.T., Wang, J.: Reliable circulant networks with minimum transmission delay. IEEE Trans. Circuits Syst.CAS-32, 1286–1291 (1985) · Zbl 0583.94018
[17] Bollobas, B.: Graphs with given diameter and minimal degree. Ars Comb.2, 3–9 (1976) · Zbl 0357.05056
[18] Bond, J., Delorme, C., de la Vega, W.F.: Large Cayley graphs with small degree and diameter. LRI Research report 392, 1987
[19] Bond, J., Peyrat, C.: Diameter vulnerability in networks. In: Proc. of Kalamazoo Colloquium 1984, Graph theory and its applications to algorithms and computer science. pp. 123–149, New York: Wiley 1985
[20] Bond, J., Peyrat, C.: Diameter vulnerability of some large interconnection networks, The 19-th Southeastern Conference on Combinatorics, Graph Theory and Computing. Baton rouge, 1988 · Zbl 0678.05021
[21] Bondy, J.A., Hell, P.: Counterexamples to theorems of Menger type for the diameter. Discrete Math.44, 217–220 (1983) · Zbl 0509.05054
[22] Boyles, S.M., Exoo, G.: A counterexample to a conjecture on paths of bounded length. J. Graph Theory6, 205–209 (1982) · Zbl 0494.05039
[23] Broder, A., Dolev, D., Fischer, M., Simons, B.: Efficient fault-tolerant routings in networks. In: Proc. ACM 16-th STOC. pp. 536–541. (1984) · Zbl 0622.94034
[24] de Bruijn, N.G.: A combinatorial problem. Koninklijke Nederlandse Academie van Wetenschappen Proc.A49, 758–764 (1946) · Zbl 0060.02701
[25] Campbell, L., Carlsson, G.E., Faber, V., Fellows, M.R., Langston, M.A., Moore, J.W., Mullhaupt, A.P., Sexton, H.B.: Dense symmetric networks from linear groups and codes (1988) (preprint)
[26] Carlsson, G.E., Cruthirds, J.E., Sexton, H.B., Wright, C.G. Interconnection networks based on a generalization of cube-connected cycles. IEEE Trans. Comput.C-34, 769–772 (1985) · Zbl 0572.94019
[27] Chudnovsky, D.V., Chudnovsky, G.V., Denneau, M.M.: Regular graphs with small diameter as models for interconnection networks in 3rd Int. Conf. on Supercomputing Boston, 232–239 (1988)
[28] Chung, F.R.K.: Diameter of communication networks. Proceedings of Symposia in Applied Mathematics34, 1–18 (1986)
[29] Chung, F.R.K.: Diameters of graphs: old problems and new results. In: Proc. 18-th southeastern conference on Combinatorics, Graph theory and Computing Congresses Numeration 60, 295–317 (1987) · Zbl 0695.05029
[30] Chung, F.R.K.: Graphs with small diameter after edge deletion (1988) (preprint) · Zbl 0773.05060
[31] Chung, F.R.K., Coffman, E.G., Reiman, M.I., Simon, B.E.: The forwarding index of communication networks. IEEE Trans. Informat. Theory.IT-33, 224–232 (1987) · Zbl 0626.94019
[32] Chung, F.R.K., Garey, M.R.: Diameter bounds for altered graphs. J. Graph Theory8, 511–534 (1984) · Zbl 0562.05030
[33] Colbourn, C.J.: The Combinatorics of Networks Reliability. Oxford: Oxford University Press 1987
[34] Dolev, D., Halpern, J., Simons, B., Strong, R.: A new look at fault-tolerant network routings. In: Proc. ACM, 16-th STOC. 526–535, 1984 · Zbl 0638.68010
[35] van Doorn, E.A.: Connectivity of circulant digraphs. J. Graph Theory10, 9–14 (1986) · Zbl 0594.05042
[36] Du, D.Z., Hsu, D.F., Hwang, F.K.: Doubly-linked ring networks. IEEE Trans. Comput.C-34, 853–855 (1985)
[37] Du, D.Z., Hsu, D.Z., Hwang, F.K., Zhang, X.M.: The hamiltonian property of generalized de Bruijn digraphs. J. Comb. Theory (to appear) · Zbl 0736.05039
[38] Du, D.Z., Hwang, F.K.: Generalized de Bruijn digraphs. Networks 18, 27–38 (1988) · Zbl 0654.05036
[39] Dwork, C., Peleg, D., Pippenger, N., Upfal, E.: Fault tolerance in networks of bounded degree. SIAM J. Comput. (to appear) · Zbl 0669.68007
[40] Entringer, R.C., Jackson, D.E., Slater, P.J.: Geodetic connectivity of graphs. IEEE Trans. Circuits Syst.Cas-24, 460–463 (1977) · Zbl 0344.05137
[41] Escudero, M., Fabrega, J., Morillo, P.: Fault-tolerant routings in double-loop networks, In: Proc. 11-th British Combinatorical Conference 1987, Ars Comb. (to appear) · Zbl 0648.94024
[42] Esfahanian, A.H.: Lower-bounds on the connectivities of a graph. J. Graph Theory9, 503–511 (1985) · Zbl 0664.05050
[43] Esfahanian, A.H., Hakimi, S.L.: Fault-tolerant routing in de Bruijn communication networks. IEEE Trans. Comput.C-34, 777–788 (1985) · Zbl 0565.94027
[44] Exoo, G.: On a measure of communication network vulnerability. Networks12, 405–409 (1982) · Zbl 0493.94019
[45] Fábrega, J., Fiol, M.A., Escudero, M.: The connectivity of iterated line digraphs. Submitted to J. of Graph Theory · Zbl 0708.05025
[46] Fábrega, J., Fiol, M.A., Yebra, J.L.A., Alegre, I.: Connectivity and reliable routing algorithms in line digraphs. In: Proc. 3rd Int. Symp. Applied Informatics, pp. 45–50. Switzerland: Grindenwald 1985
[47] Faudree, R.J., Ordman, E.T., Schelp, R.H., Jacobson, M.S., Tuza, Z.: Menger’s theorem and short paths. J. Comp. Math. and Comp. Combinatorics2, 235–253 (1987) · Zbl 0649.05048
[48] Favaron, O., Kouider, M., Maheo, M.: Edge-vulnerability and mean distance. Networks (to appear)
[49] Feldman, P.: Fault tolerance of minimal path routings in a network. In: Proc. 17-th STOC, pp. 327–334, 1985
[50] Fiol, M.A., Fábrega, J., Homobono, N., Escudero, M.: On surviving route graphs of iterated line digraphs. Submitted to Proc. of Kalamazoo Colloquium (1988) · Zbl 0841.05037
[51] Fiol, M.A., Yebra, A., Alegre, I., Valero, M.: A discrete optimization problem in local networks and data alignment. IEEE Trans. Comput.C-36, 702–713 (1987)
[52] Fiol, M.A., Yebra, J.L.A., Alegre, I.: Line digraph iterations and the (d, k) digraph problem. IEEE Trans. Computer.C-33, 400–403 (1984) · Zbl 0528.68048
[53] Gomez, J.: Diametroy vulnerabilidad en redes de interconexion. Thesis, Universitat Politecnica de Catalunya, Barcelona, September 1986
[54] Greenberg, D.S., Heath, L.S., Rosenberg, A.: Optimal embeddings of the FFT graph in the hypercube (1988) (preprint)
[55] Hamidoune, Y.O.: On the connectivity of Cayley digraphs. Europ. J. Comb.5, 309–312 (1984) · Zbl 0561.05028
[56] Hartman, J., Rubin, I.: On diameter stability of graphs. Lect. Notes Math.642, 247–254 (1976)
[57] Heydemann, M.C., Meyer, J.-C., Opatrny, J., Sotteau, D.: Consistent routings and forwarding indices (1988) (preprint) · Zbl 0804.90041
[58] Heydemann, M.C., Meyer, J.-C., Sotteau, D.: On forwarding indices of networks. Discrete App. Math. (1988) · Zbl 0681.90077
[59] Hillis, W.D.: The connection machine. In: ACM Distinguished Dissertation. The MIT press (1985)
[60] Homobono, N.: Resistance aux pannes de grands reseaux d’interconnection. These de troisieme cycle, Universite de Paris-sud, LRI 1987
[61] Homobono, N.: Connectivity of the undirected Imase and Itoh networks. In: Proc. 11-th British Conference, Ars Comb.25C, 179–194 (1988) · Zbl 0648.05038
[62] Homobono, N., Peyrat, C.: Fault-tolerant routings in Kautz and de Bruijn digraphs. (To appear in the Combinatorial conference, Montreal, Quebec, 1987) · Zbl 0677.90028
[63] Homobono, N., Peyrat, C.: Connectivity of Imase and Itoh digraphs. IEEE Trans. Comput.37, 1459–1461 (1988) · Zbl 0659.68091
[64] Imase, M., Itoh, M.: Design to minimize a diameter on building block network. IEEE Trans. Comput.C-30, 439–443 (1981) · Zbl 0456.94030
[65] Imase, M., Itoh, M.: A design for directed graphs with minimum diameter. IEEE Trans. Comput.C-32, 782–784 (1983) · Zbl 0515.94027
[66] Imase, M., Manabe, Y.: Fault tolerant routing in ak-connected network. Information Processing Letters, 1988 · Zbl 0655.94023
[67] Imase, M. Soneoka, T., Okada, K.: Connectivity of regular directed graphs with small diameter. IEEE Trans. Comput.C-34, 267–273 (1985) · Zbl 0554.05044
[68] Imase, M., Soneoka, T., Okada, K.: A fault tolerant processor interconnection network. Denshi Tsushin Gakkai RonbunshiJ68-D, 8, 1449–1456 (in Japanese; translated in Systems and Computers in Japan, vol.17, No. 8, 21–30, 1986.)
[69] Itai, A., Perl, Y., Shiloach, Y.: The complexity of finding maximum disjoint paths with length constraints. Networks12, 277–286 (1982) · Zbl 0504.68041
[70] Jolivet, J.-L.: Sur la connexite des graphes orientes. C.R. Acad. Sci., Paris,274A, 148–150 (1972) · Zbl 0224.05110
[71] Kautz, W.H.: Bounds on directed (d, k) graphs. Theory of cellular logic networks and machines, AFCRL-68-0668 Final Report, pp. 20–28, 1968
[72] Kerjouan, R.: The edge-vulnerability of the diameter of interconnection networks. LRI Research Report 261, 1986, J. Graph Theory (submitted)
[73] Krishnamoorthy, M.S., Krishnamurthy, B.: Fault diameter of interconnection networks. Comput. Math. Applic.13, 577–582 (1987) · Zbl 0641.94048
[74] Kumar, V.P., Reddy, S.M.: A class of graphs for fault-tolerant processor interconnections. In: IEEE 1984 Int. Conf. Distributed Computing Systems, pp. 448–460, 1984
[75] Lovász, L., Neumann-Lara, V., Plummer, M.: Mengerian theorems for paths of bounded length. Period. Math. Hung.9, 269–276 (1978) · Zbl 0393.05033
[76] Mader, W.: Uber den Zusammenhang symmetrischer Graphen. Arch. Math.21, 331–336 (1970) · Zbl 0201.56804
[77] Mader, W.: Minimalen-fach kantenzusammenhängende Graphen. Math. Ann.191, 21–28 (1971) · Zbl 0204.24303
[78] Mader, W.: Connectivity and edge-connectivity in finite graphs. In: Surveys in Combinatorics: Proc. Seventh British Combinatorial Conference, Cambridge 1979, pp. 66–95. London Math. Soc. Lect. Note Ser.38, (1979) · Zbl 0404.05040
[79] Manabe, Y., Imase, M., Soneoka, T.: Reliable and efficient fixed routings in digraphs. Invited paper, IECIE, Japan 1988 · Zbl 0655.94023
[80] Meyer, F.J., Pradhan, D.K.: Flip-trees: fault-tolerant graphs with wide containers. IEEE Trans. Comput.37, 472–478 (1988)
[81] Morillo, P., Comellas, F., Fiol, M.A.: Diameter, mean distance and vulnerability of some graphs related to plane tesselations. Submitted to J. Graph Theory · Zbl 0711.05023
[82] Morillo, P., Fiol, M.A., Guitart, J.: On the (d, D, D, s)-digraph problem. 5th Int. Conf. on Applied Algebra, Error-Correcting Codes and Cryptography, AAECC-5, 1987 · Zbl 0677.05049
[83] Opatrny, J.: A new family of 3-regular network models. In: Proc. of Int. Computer Symposium, Taiwan, pp. 1397–1401, 1986
[84] Opatrny, J., Srinivasan, N., Alagar, V.S.: Highly fault-tolerant communication networks models. Submitted to IEEE on Circuits and System · Zbl 0666.94026
[85] Peleg, D., Simons, B.: On fault tolerant routings in general networks. PODCS, pp. 98–107, 1986 · Zbl 0618.94017
[86] Peyrat, C.: Diameter vulnerability of graphs. Discrete Appl. Math.9, 245–250 (1984) · Zbl 0549.05036
[87] Plesnik, J.: Note on diametrally critical graphs. In: Recent Advances in Graph Theory, Proc. 2-nd Czechoslovak Symp., Prague 1974, Academia Prague, pp. 455–465, 1975
[88] Plesnik, J.: Critical graphs of given diameter Acta Fac. Rerum Natur. Univ. Com. Mat.,30, 71–93 (1975) · Zbl 0318.05115
[89] Pradhan, D.K.: Interconnecting topologies for fault-tolerant parallel and distributed architectures. In: Proc. ICPP, pp. 238–242, 1981
[90] Pradhan, D.K.: On a class of fault-tolerant multiprocessor network architectures. In: 3rd Int. Conf. on Distributed Processing, Miami, Floride, 1982
[91] Pradhan, D.K.: Fault-tolerant Computing. Theory and Techniques, Englewood Cliffs, NJ, Prentice-Hall, 1986.
[92] Pradhan, D.K., Reddy, S.M.: A Fault-tolerant communication architecture for distributed sustems. IEEE Trans. Comput.C-31, 863–870 (1982) · Zbl 0488.94049
[93] Preparata, F.R., Vuillemin, J.: The cube connected cycles: a versatile network for parallel computation. Commun. ACM24, 300–309 (1981)
[94] Quaife, H.J.: On (d, k, {\(\mu\)}) graphs, IEEE Trans. Comput.C-18, 270–272 (1969) · Zbl 0183.28405
[95] Reddy, S.M., Kuhl, J.G., Hosseini, S.H., Lee, H.: On digraphs with minimum diameter and maximum connectivity. In: Proceedings of 20-th Annual Allerton Conference, pp. 1018–1026, 1982
[96] Reddy, S.M., Pradhan, D.K., Kuhl, J.G.: Directed graphs with minimal diameter and maximum node connectivity. School of Engineering Oakland Univ., Tech. Rep., 1980
[97] Ronen, D., Perl, Y.: Heuristics for finding a maximum number of disjoint bounded paths. Networks14, 531–544 (1984) · Zbl 0575.90083
[98] Schlumberger, M.: De Bruijn communications networks. Standford PhD Thesis, Computer Science Department, Stanford, California, 1974
[99] Schlumberger, M.: Connectivity of de Bruijn networks. Rapport de Recherche 154 Ensimag, Universite de Grenoble, 1978
[100] Schoone, A.A., Bodlaender, H.L., van Leeuwen, J.: Diameter increase caused by edge deletion. J. Graph Theory11, 409–427 (1987) · Zbl 0646.05038
[101] Schumacher, U.: An algorithm for construction of ak-connected graph with minimum number of edges and quasiminimal diameter. Networks14, 63–74 (1984) · Zbl 0547.05039
[102] Sengupta, A., Sen, A., Bandyopadhyay, S.: On an optimally fault-tolerant multiprocessor network architecture. IEEE trans. Comp.C-36, 619–623 (1987) · Zbl 0617.68038
[103] Soneoka, T., Imase, M., Manabe, Y.: Design of ad-connected digraph with a minimum number of edges and a quasiminimal diameter, Part II. Submitted to Networks · Zbl 0848.05034
[104] Soneoka, T., Nakada, H., Imase, M.: Sufficient conditions for dense graphs to be maximally connected. In: Proc. of ISCAS 85, pp. 811–814, 1985 · Zbl 0609.05050
[105] Soneoka, T., Nakada, H., Imase, M.: Design of ad-connected digraph with a minimum number of edges and quasiminimal diameter. Submitted to Discrete Appl. Math. · Zbl 0707.05027
[106] Soneoka, T., Nakada, H., Imase, M., Peyrat, C.: Sufficient conditions for maximally connected dense graphs. Discrete Math.63, 53–66 (1987) · Zbl 0609.05050
[107] Suurballe, J.W.: Disjoint paths in a network. Networks4, 125–145 (1974) · Zbl 0304.90114
[108] Vijayan, K., Murty, U.S.R.: On accessibility in graphs. Sankhya Ser. A,26, 299–302 (1964) · Zbl 0134.43304
[109] Wagner, A.: Embedding arbitrary binary trees in a hypercube. Submitted to J. Parallel and Distributed Computing · Zbl 0800.68150
[110] Watkins, W.E.: Connectivity of transitive graphs. J. Comb. Theory8, 23–29 (1970) · Zbl 0185.51702
[111] Wong, C.K., Coppersmith, D.: A combinatorial problem related to multimodule memory organizations. J. of Association for Communication for Computing Machinery21, 392–402 (1974) · Zbl 0353.68039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.