A Study of Some Threestage Clos Network Nonblocking Problems 

Author  ZuoWenQing 
Tutor  HeYong;YaoEnZuo 
School  Zhejiang University 
Course  Operational Research and Cybernetics 
Keywords  Switching network Threestage Clos network Strictly nonblocking Widesense nonblocking Rearrangeable nonblocking Coloring Sum graph Sum number 
CLC  O233 
Type  PhD thesis 
Year  2007 
Downloads  118 
Quotes  1 
The switching network problem is an combinatorial optimization problem originated from the connection of telephone network. At first, the study on the switching network is in the classical circuit switching model. However, with the development of digital and information technology, there are many new models emerged, such as multirate model, multicast model and multirate multicast model. So, more and more people concern with the switching network. And the switching network plays an important role in many area, for example, data transmission, conference calls, broadcast, satellite communication etc. In the classical networks of the switching network, the threestage Clos network is considered as the most basic and popular multistage interconnection network. In this paper we mainly study and analyze the nonblocking property, i.e., strictly nonblocking, widesense nonblocking and rearrangeable nonblocking, of threestage Clos network under these new models. This paper is composed of five chapters. In the first chapter we chiefly introduce some basic concepts and preliminary knowledge about switching network.Since the coloring theory of graph theory is used in the study of threestage Clos network, the first section of the second chapter mainly introduces some basic concepts and preliminary knowledge of graph theory, while the second section presents the coloring theory. However, when we investigate the problem of switching network using the knowledge and method of graph theory, the issue we have to face is the storage of graph. So, in the third section we chiefly give the sum graph theory which can be used to the storage of graph and present our results.The third chapter mainly studies the nonblockingness of threestage Clos network in multirate environment. The first section introduces the multirate model in detail, while the second section presents some known results about threestage Clos network. In the third section of this chapter we chiefly investigate the widesense nonblockinghess of threestage Clos network in 2rate environment with rate B and b. However, the previous study for 2rate Clos network did not contain the case of B＞1/2. Therefore, in this section we give the best reservationscheme routing for the B＞1/2 case to complete the discussion on the general 2rate case. The fourth section studies the rearrangeable nonblockingness of threestage Clos network in multirate environment. Chung and Ross produce a conjecture: the sufficient and necessary condition for threestage Clos network C（n, m, r） to be rearrangeable nonblocking is m≥2n1 if each call has weight chosen from a given set of k weights. Furthermore, the conjecture seems to be true not only in the discrete bandwidth case but also in the continuous one. In this section we show that the conjecture of Chung and Ross holds not only in the discrete bandwidth case but also in continuous one for r≤2n/523/5.The fourth chapter investigates the widesense nonblocking property of threestage Clos network in multicast environment. In the first section we introduce the multicast model in detail, while in the second section we present some known results about threestage Clos network. Yang and Masson showed that threestage Clos network C（n, m, r） is multicast widesense nonblocking if m＞（?）（n1）(x+r^{1/x}), where x is a positive integer. From this result they obtained a bound of m as a function of n and r by giving a fixed value to x. However, the bound has a defect, i.e., the given value to x may not belong to the interval [1, min{n1, r}]. In third section of this chapter we show that threestage Clos network C（n, m, r） is multicast widesense nonblocking if m＞min（n1）(x+r^{1/x}), where x is a positive integer. Our result is better than Yang and Masson’s for that it loosens the restriction to x. And, just for that the bound of x is canceled, we say that the bound of m as a function of n and r given by Yang and Masson is right. Furthermore, we can improve the bound by analysis.The fifth chapter chiefly studies the nonblockingness of threestage Clos network in multirate multicast environment. The first section introduces the multirate multicast model in detail, while the second section presents some known results on threestage Clos network. The multirate multicast model is the most complicated case and hard to analyze. So, very little is known for this case. In the third section of this chapter we investigate the widesense nonblocking property of threestage Clos network in two most simple multirate multicast model: 1rate multicast and 2rate multicast environment. Kim and Du gave a result about multirate multicast rearrangeable nonblocking Clos network in the condition of restricted bandwidth. In fourth section we show that they made a small error in the count, and correct it. Furthermore, our result improve Kim and Du’s.