- Tytuł:
- Towards the boundary between easy and hard control problems in multicast Clos networks
- Autorzy:
-
Obszarski, P.
Jastrzębski, A.
Kubale, M. - Powiązania:
- https://bibliotekanauki.pl/articles/200819.pdf
- Data publikacji:
- 2015
- Wydawca:
- Polska Akademia Nauk. Czytelnia Czasopism PAN
- Tematy:
-
Clos-network
2-cast call
hypergraph edge coloring
rearrageable network
nonblocking network
NP-completeness
3-uniform hypergraph
sieci
połączenie sieciowe
problem sieciowy - Opis:
- 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.
- Źródło:
-
Bulletin of the Polish Academy of Sciences. Technical Sciences; 2015, 63, 3; 739-744
0239-7528 - Pojawia się w:
- Bulletin of the Polish Academy of Sciences. Technical Sciences
- Dostawca treści:
- Biblioteka Nauki
Artykuł