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

Bulletin of the Polish Academy of Sciences. Technical Sciences

M. KubaleCorresponding authorFaculty of Electronics, Telecommunications and Informatics, Gda?sk University of Technology, 11/12 Gabiela Narutowicza St., 80-233 Gda?sk, PolandEmailOther articles by this author:De Gruyter OnlineGoogle Scholar¹  A. Jastrz?bskiFaculty of Electronics, Telecommunications and Informatics, Gda?sk University of Technology, 11/12 Gabiela Narutowicza St., 80-233 Gda?sk, PolandOther articles by this author:De Gruyter OnlineGoogle Scholar¹  P. ObszarskiFaculty of Electronics, Telecommunications and Informatics, Gda?sk University of Technology, 11/12 Gabiela Narutowicza St., 80-233 Gda?sk, PolandOther articles by this author:De Gruyter OnlineGoogle Scholar¹ 

[1] Faculty of Electronics, Telecommunications and Informatics, Gda?sk University of Technology, 11/12 Gabiela Narutowicza St., 80-233 Gda?sk, Poland

关键词: Keywords: Clos network;    2-cast call;    hypergraph edge-coloring;    rearrageable network;    nonblocking network;    NP-completeness;    3-uniform hypergraph;   

DOI  :  10.1515/bpasts-2015-0085

学科分类：工程和技术（综合）

来源: Polska Akademia Nauk * Centrum Upowszechniania Nauki / Polish Academy of Sciences, Center for the Advancement of Science

【 摘 要 】

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.

【 授权许可】

Unknown