Towards the boundary between easy and hard control problems in multicast Clos networks

• Autorzy: Obszarski P. , Jastrzębski A. , Kubale M.

Identyfikatory

DOI

10.1515/bpasts-2015-0085

• Języki publikacji: EN

Abstrakty

EN

In this article we study 3-stage Clos networks with multicast calls in general and 2-cast calls, in particular. We investigate various sizes of input and output switches and discuss some routing problems involved in blocking states. To express our results in a formal way we introduce a model of hypergraph edge-coloring. A new class of bipartite hypergraphs corresponding to Clos networks is studied. We identify some polynomially solvable instances as well as a number of NP-complete cases. Our results warn of possible troubles arising in the control of Clos networks even if they are composed of small-size switches in outer stages. This is in sharp contrast to classical unicast Clos networks for which all the control problems are polynomially solvable.

Słowa kluczowe

EN

Clos-network; 2-cast call; hypergraph edge coloring; rearrageable network; nonblocking network; NP-completeness; 3-uniform hypergraph

PL

sieci; połączenie sieciowe; problem sieciowy

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2015
• Tom: Vol. 63, nr 3
• Strony: 739--744
• Opis fizyczny: Bibliogr. 14 poz., rys., tab.

Twórcy

autor

Obszarski P.

• Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, 11/12 Gabiela Narutowicza St., 80-233 Gdańsk, Poland

autor

Jastrzębski A.

• Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, 11/12 Gabiela Narutowicza St., 80-233 Gdańsk, Poland

autor

Kubale M.

• Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, 11/12 Gabiela Narutowicza St., 80-233 Gdańsk, Poland

Bibliografia

• [1] C. Clos, “A study of nonblocking switching networks”, Bell Syst. Tech. J. 32, 406–424 (1953).
• [2] F.K. Hwang, The Mathematical Theory of Nonblocking Switching Networks, World Scientific, London, 2004.
• [3] F.K. Hwang, “A unifying approach to determine the necessary and sufficient conditions for nonblocking multicast 3-stage Clos networks”, IEEE Trans. on Commun. 53, 1581–1586 (2005).
• [4] A. Jastrzębski and M. Kubale, “Rearrangeability in multicast Clos networks is NP-complete”, Proc. 2-nd Int. Conf. on Information Technology 1, 183–185 (2010).
• [5] F.K. Hwang and C.H. Lin, “Broadcasting in a three-stage point-to-point nonblocking network”, Int. J. Rel. Qual. Safety Eng. 2, 299–307 (1995).
• [6] D.Z. Du and H.Q. Ngo, “An extension of DHH-Erdos conjecture on cycle-plus-triangle graphs”, Taiwan J. Math. 6, 65–105 (2002).
• [7] F.K. Hwang, S.-C. Liaw, and L.D. Tong, “Strictly nonblocking 3-stage Clos networks with some rearrangeable multicast capability”, IEEE Trans. Commun. 6, 261–267 (2002).
• [8] H.-L. Fu and F.K. Hwang, “On 3-stage clos networks with different nonblocking requirements on two types of calls”, J. Comb. Opt. 9, 263–266 (2005).
• [9] I. Holyer, “The NP-completeness of edge-colouring”, SIAM J. Comput. 10, 718–720 (1981).
• [10] M. Kubale, “Average and worst-case performance of Paull’s algorithms for rearranging three-stage connection networks”, Annales Des Telecommunications 40, 270–276 (1985).
• [11] M.C. Paull, “Reswitching of connection networks”, Bell Syst. Tech. J. 41, 833-855 (1962).
• [12] R. Cole, K. Ost, and S. Schirra, “Edge-coloring bipartite multigraphs in O(E logD) time”, Combinatorica 21, 5–12 (2001).
• [13] R.L. Brooks, “On colouring the nodes of a network”, Proc. Cambridge Philosophical Society, Math. Phys. Sci. 37, 194–197 (1941).
• [14] S. Skulrattanakulchai, “Δ-list vertex coloring in linear time”, LNCS 2368, 240–248 (2002).