Abstract
This thesis consists of two parts. The first part is devoted to the routability andconditional nonblocking properties of families of multistage interconnection networks(MINs). Moreover, as the load-balanced switches are much more scalable than other existing switching architecture in the literature, we show how these conditional nonblocking properties can be used to help implement load-balanced switches. First, to construct a universal load-balanced switch for an arbitrary number of linecards, we propose two special families of MINs, twister networks and degenerated banyan networks: the first one is inspired by the recent development of optical queueing theory, and the second one can be obtained by using only halves of input and output ports of classical banyan networks. Then, we depict a placement rule for adding a new linecard to both of these families of MINs so that all the existing linecards need not be changed, while the packets can still be self-routed and the routing paths are guaranteed to be link-disjoint. We also consider the problem of implementation of load-balanced switches with fattree networks, where the link capacity has to be increased exponentially from the bottom of the tree to the root, and each node at higher level has to be thus constructed as a nonblocking switch with a large number of input/output lines. We show that the bitreverse permutation and all its variants obtained by circular shifts, which all satisfy the uniform mapping property, can be used as a set of connection patterns of a load-balanced switch while the capacity of each link in the fat-tree is specified by the lower bound. Moreover, we found that a banyan-type network can be used to further reduce the implementation complexity of a fat-tree when used as a load-balanced switch, where the self-routing property is preserved. In the second part of this thesis, we consider the stability of wired networks. By using the network calculus and the large deviation principle, we propose the Dynamic Frame Sizing (DFS) algorithm that not only needs only a buffer of size two at each internal node but also guarantees 100% throughput even if we have no prior information about arrival processes. Moreover, by using the DFS algorithm, each internal link makes its own decision independently at each time slot, whereas the central arbitrator only collects and broadcasts information once a frame. We then extend our result for wired networks to wireless networks. In wireless networks, the transmission of each link might interfere with each other and thus only a certain set of links can transmit at the same time. The DFS algorithm for wireless networks also does not have a fixed frame size. An optimization problem needs to be solved at the beginning of each frame to determine the frame size. Once the frame size is determined, a hierarchical smooth schedule is devised to determine both the schedule for configuration vectors and the schedule for multicast traffic flows in each link. Under the assumption of Bernoulli arrival processes with admissible rates, we show that the number of packets of each multicast traffic flow inside the wireless network is bounded above by a constant and thus one only requires to implement a finite internal buffer in each link in such a wireless network.