A Study Of Some Three-stage Clos Network Nonblocking Problems

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 three-stage 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, wide-sense 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 three-stage 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 three-stage Clos network in multirate environment. The first section introduces the multirate model in detail, while the second section presents some known results about three-stage Clos network. In the third section of this chapter we chiefly investigate the wide-sense nonblockinghess of three-stage Clos network in 2-rate environment with rate B and b. However, the previous study for 2-rate Clos network did not contain the case of B＞1/2. Therefore, in this section we give the best reservation-scheme routing for the B＞1/2 case to complete the discussion on the general 2-rate case. The fourth section studies the rearrangeable nonblockingness of three-stage 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≥2n-1 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/5-23/5.The fourth chapter investigates the wide-sense nonblocking property of three-stage 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 three-stage Clos network C(n, m, r) is multicast wide-sense nonblocking if m＞(?)(n-1)(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{n-1, r}]. In third section of this chapter we show that three-stage Clos network C(n, m, r) is multicast wide-sense nonblocking if m＞min(n-1)(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 three-stage 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 three-stage 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 wide-sense nonblocking property of three-stage Clos network in two most simple multirate multicast model: 1-rate multicast and 2-rate 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.