Fat-tree networks have been widely used in the field of Network-on-Chip. One of the key issues in a fat-tree network is that the degree of a node has to be increased rapidly from the bottom of the tree to the root. As such, the complexity of implementing the switches near the root could be extremely high, and this poses a serious scalability issue. To cope with the scalability issue in fat-tree networks, many previous works require changing the tree topology and adding buffers in nodes. Unlike the existing arts, we adopt a different approach that can still maintain the original tree topology without adding any buffers in internal nodes. Our key idea is to explore various nice features of the load-balanced Birkhoff-von Neumann switches. Such switches have been shown to achieve 100% throughput for all admissible traffic and have comparable delay performance to the ideal output-buffered switch when traffic is heavy and bursty. We show that the implementation complexity can be greatly reduced if a fat-tree network is only required to realize a set of N permutations needed for the N × N load-balanced Birkhoff-von Neumann switches. For this, we first derive a lower bound on the required degree for each node in a fat-tree network. By using the uniform mapping property of the bit-reverse permutation, we show that there exists a set of N permutations that achieve the lower bound.

In this paper, we consider a network that supports multiple multicast flows with network coding. It is well-known that network coding can be used to increase the throughput of a delay-free network. However, as there are multiple multicast flows in the network, packets might be delayed due to contention. As packets from the same flow have to be synchronized for network coding, additional buffers, known as em synchronization buffers in the literature, are required. In certain networks, such as multistage interconnection networks in switch fabrics , the size of internal buffers could be quite limited. One of the key contributions of the paper is to propose a packet scheduling algorithm so that synchronization buffers can be bounded by a em finite constant that only depends on the maximum hop count of the flows. We also show that our scheduling algorithm does not cause any throughput degradation as it can stabilize the network for any em admissible traffic. Moreover, our algorithm is em universal and it does not require to know the rates of the flows in the network. The main idea of our algorithm is to introduce em fictitious packets in the dynamic frame sizing algorithm recently proposed in for stabilizing switches and em wired networks (without network coding). By so doing, packets that might be stalled in synchronization buffers can be flushed out. We show that the number of fictitious packets in each frame is also bounded by a finite constant that only depends on the maximum hop count.

Distributed algorithms based on pulse-coupled oscillators have been recently proposed in [4], [14] for achieving desynchronization of a system of identical nodes. Though these algorithms are shown to work properly by various computer simulations, they are still lack of rigorous theoretical proofs for both the convergence of the algorithms and the rates of convergence for these algorithms. On the other hand, all the nodes are not likely to be identical in many practical applications. In particular, there might be a node that needs to interact with the “outside” world and thus may not have the freedom to adjust its local clock. Motivated by all these, in this paper we consider the desynchronization problem in a system where there exists an anchored node that never adjusts the phase of its oscillator. For such a system, we propose a generic anchored desynchronization algorithm that achieves ∈-desynchrony (defined in [4]) in O(n2ln(n over ∈)) rounds of firings. We also prove that our algorithm converges even for the generalized processor sharing (GPS) scheme, where every node is assigned a weight and the amount of resource received by a node is proportional to its weight. In comparison with the original algorithm in [4], we show that the rate of convergence of the original algorithm in [4] is not always better than ours and it is only better in the asymptotic regime.

In this paper, we consider the problem for maximizing the throughput of a discrete-time wireless network, where only certain sets of links can transmit simultaneously. It is well known that each set of such links can be represented by a configuration vector and the convex hull of the configuration vectors determines the capacity region of the wireless network. In the literature, packet scheduling polices that stabilize any admissible traffic in the capacity region are mostly related to the maximum weighted matching algorithm (MWM) that identifies the most suitable configuration vector in every time slot. Unlike the MWM algorithm, we propose a dynamic frame sizing (DFS) algorithm that also stabilizes any admissible traffic in the capacity region. The DFS algorithm, as an extension of our previous work for wired networks, also does not have a fixed frame size. To determine the frame size, an optimization problem needs to be solved at the beginning of each frame. 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.

Load-balanced switches have received a lot of attention lately as they are much more scalable than other existing switch architectures in the literature. One of the most salient features of load-balanced switches is its simplicity of implementing deterministic and periodic connection patterns for the switch fabrics. In particular, for an N × N load-balanced switch, its switch fabric only needs an N × N rotator that is capable of realizing all the powers of the circular shift permutation. In this paper, we consider the problem of incremental update of the number of linecards in load-balanced switches. For this, our idea is to consider a 2M× 2Mdegenerated banyan network that only uses half of the 2M+1inputs/outputs in the classical 2M+1× 2M+1banyan network. We show how one can use the 2M× 2Mdegenerated banyan network as a p × p rotator for any 2 ≤ p ≤ 2M. This is done by a specific rule of placing the p linecards in the 2Minput/output ports of the 2M× 2Mdegenerated banyan network. In special, when p = 2M, the 2M× 2Mdegenerated banyan network can also be used as a crosstalk-free 2M× 2Mrotator, where all the routing paths do not share a common node. As such, one can use a 2M+1× 2M+1banyan network as the switch fabric for a 2M× 2Mload-balanced switch that is capable of providing incremental update of the number of linecards.

Inspired by the recent development of optical queueing theory, in this paper we study a class of multistage interconnection networks (MINs), called twister networks. Unlike the usual recursive constructions of MINs (either by two-stage expansion or by three-stage expansion), twister networks are constructed directly by a concatenation of bipartite networks. Moreover, the biadjacency matrices of these bipartite networks are sums of subsets of the powers of the circular shift matrix. Though MINs have been studied extensively in the literature, we show there are several distinct properties for twister networks, including routability and conditionally nonblocking properties. In particular, we show that a twister network satisfying (Al) in the paper is routable, and packets can be self-routed through the twister network by using the C-transform developed in optical queueing theory. Moreover, we define an N -modulo distance and use it to show that a twister network satisfying (A2) in the paper is conditionally nonblocking if the N-modulo distance between any two outputs is not greater than two times of the N-modulo distance between the corresponding two inputs. Such a conditionally nonblocking property allows us to show that a twister network with N inputs/outputs can be used as a p × p rotator and a p × p symmetric TDM switch for any 2 ¿ p ¿ N. As such, one can use a twister network as the switch fabric for a two-stage load balanced switch that is capable of providing incremental update of the number of linecards.

Recently, there has been a lot of attention on the constructions of optical queues by using optical Switches and fiber Delay Lines (SDL). In this paper, we consider the constructions of optical queues with a limited number of recirculations through the fibers in such SDL constructions. Such a limitation on the number of recirculations comes from practical feasibility considerations, such as crosstalk, power loss, amplified spontaneous emission (ASE) from the Erbium doped fiber amplifiers (EDFA), and the pattern effect of the optical switches. We first transform the design of the fiber delays in such SDL constructions to an equivalent integer representation problem. Specifically, given 1 les k les M, we seek for an M-sequence dM1= (d1,d2,...,dm) of positive integers to maximize the number of consecutive integers (starting from 0) that can be represented by the C-transform relative to dM1such that there are at most k 1-entries in their C-transforms. Then we give a class of greedy constructions so that d1, d2,..., dMare obtained recursively and the maximum number of representable consecutive integers by using d1,d2,...,diis larger than that by using d1,d2,...,di-1for all i. Furthermore, we obtain an explicit recursive expression for d1, d2,..., dMgiven by a greedy construction. Finally, we show that an optimal M-sequence (in the sense of achieving the maximum number of representable consecutive integers) can be given by a greedy construction. The solution of such an integer representation problem can be applied to the construction of optical 2-to-l FIFO multiplexers with a limited number of recirculations. We show that the complexity of searching for an optimal construction under our routing policy can be greatly reduced from exponential time to polynomial time by only considering the greedy constructions instead of performing an exhaustive search. Similar results can be obtained for linear compressors and linear decompressors with a limited number of recirculations.

In this paper, we consider a multicasting model that uses incremental forward error correction (FEC). In this model, there is one sender and r/sup n/ receivers. The sender uses an ideal (n,n(1-p),np) FEC code to code a group of n(1-p) data packets with additional np redundant packets so that any set of n(1-p) packets received by a receiver can be used to recover the original n(1-p) data packets. Packets to the receivers are lost independently with probability q. For this model, we prove several strong laws of large numbers for the asymptotic throughput as n /spl rarr/ /spl infin/. The asymptotic throughput is characterized by the unique solution of an equation in terms of p, q, and r. These strong laws not only provide theoretical justification for several important observations made in the literature, but also provide insights that might have impact on future design of multicasting protocols.