In this paper, we present a framework for convolutional coded Poisson receivers (CCPRs) that incorporates spatially coupled methods into the architecture of coded Poisson receivers (CPRs). We use density evolution equations to track the packet decoding process with the successive interference cancellation (SIC) technique. We derive outer bounds for the stability region of CPRs when the underlying channel can be modeled by a$\phi $-ALOHA receiver. The stability region is the set of loads that every packet can be successfully received with a probability of 1. Our outer bounds extend those of the spatially-coupled Irregular Repetition Slotted ALOHA (IRSA) protocol and apply to channel models with multiple traffic classes. For CCPRs with a single class of users, the stability region is reduced to an interval. Therefore, it can be characterized by a percolation threshold. We study the potential threshold by the potential function of the base CPR used for constructing a CCPR. In addition, we prove that the CCPR is stable under a technical condition for the window size. For the multiclass scenario, we recursively evaluate the density evolution equations to determine the boundaries of the stability region. Numerical results demonstrate that the stability region of CCPRs can be enlarged compared to that of CPRs by leveraging the spatially-coupled method. Moreover, the stability region of CCPRs is close to our outer bounds when the window size is large.

In this paper we consider coded slotted ALOHA (CSA) systems, in which each packet arrival is duplicated and transmitted to receivers randomly. Successfully received packets are used to cancel their interference with the reception of other packets. In this paper, we assume that interference cancellation is imperfect and that mean channel estimation errors follow an inverse square root law. We approximate the probability of correct reception of a message by the probability that the signal-to-interference-and-noise ratio (SINR) of the message exceeds a threshold. We derive a conditional probability of successful reception of a packet for a location model of transmitters and receivers, given the number of additional packet arrivals and the number of packets successfully received in previous iterations. We estimate this conditional probability by a mean field approximation. Under these assumptions, we perform an and-or tree analysis. We verify through extensive simulations that the mean field approximation and the and-or tree analysis work quite well. Simulation results show that throughput improvement of coded slotted Aloha systems with imperfect interference cancellation can be significantly lower that that of a system with perfect cancellation.

As a generalization of Irregular Repetition Slotted ALOHA (IRSA), the probabilistic framework of coded Poisson receivers (CPR) offers a unified approach to analyze coded multiple access with successive interference cancellation (SIC). One crucial performance metric of CPRs is the stability region in which every packet can be successfully received with probability 1. In this paper, we use the potential function for convolutional Low Density Parity Check (LDPC) codes to derive the potential function for CPRs. Based on such a potential function, we derive three thresholds: the single-system threshold$G_{s}^{*}$(for the original CPRs), the potential threshold$G_{conv}^{*}$(for the convolutional CPRs), and the potential upper bound$G_{up}^{*}$. We prove that$G_{s}^{*} < G_{conv}^{*} < G_{up}^{*}$• Our numerical results show that these thresholds match very well with existing works for D-fold ALOHA.

As an abstraction and generalization of various coded random access schemes in the literature, the probabilistic framework of coded Poisson receivers (CPR) with multiple traffic classes is a tentative solution for providing differentiated services for uplink transmissions in a single network. One crucial performance metric of CPRs is the stability region in which every packet can be successfully received with probability 1. In this paper, we derive upper bounds for the stability region of CPRs when the underlying channel can be modeled by a ϕ-ALOHA receiver. Our upper bounds generalize those for the Irregular Repetition Slotted ALOHA (IRSA) protocol and can also be used for other channel models with multiple traffic classes.

Most existing works on analyzing the performance of a random ensemble of low-density parity-check (LDPC) codes assume that the degree distributions of the two ends of a randomly selected edge are independent. In the paper, we take one step further and consider ensembles of LDPC codes with degree-degree correlations. For this, we propose two methods to construct an ensemble of degree-degree correlated LDPC codes. We then derive a system of density evolution equations for such degree-degree correlated LDPC codes over a binary erasure channel (BEC). By conducting extensive numerical experiments, we show how the degree-degree correlation affects the performance of LDPC codes. Our numerical results show that LDPC codes with negative degree-degree correlation could improve the maximum tolerable erasure probability. Moreover, increasing the negative degree-degree correlation could lead to better unequal error protection (UEP) design.

Motivated by the need to provide differentiated quality-of-service (QoS) in grant-free uplink transmissions in 5G networks and beyond, we extend the probabilistic analysis of coded Poisson receivers (CPR) to the setting with multiple classes of users and receivers. For such a CPR system, we prove (under certain technical conditions) that there is a region, called the stability region in this paper. Each transmitted packet can be successfully received with probability 1 when the offered load to the system is within the stability region. On the other hand, if the offered load is outside the stability region, there is a nonzero probability that a packet will fail to be received. We then extend the stability region to the$\epsilon $-stability region for CPR systems with decoding errors. We also demonstrate the capability of providing differentiated QoS in such CPR systems by comparing the stability regions under various parameter settings.

Motivated by the need to hide the complexity of the physical layer from performance analysis in a layer 2 protocol, a class of abstract receivers, called Poisson receivers, was recently proposed by Yuet al.(2021) as a probabilistic framework for providing differentiated services in uplink transmissions in 5G networks. In this paper, we further propose a deterministic framework of ALOHA receivers that can be incorporated into the probabilistic framework of Poisson receivers for analyzing coded multiple access with successive interference cancellation. An ALOHA receiver is characterized by a success function of the number of packets that can be successfully received. Inspired by the theory of network calculus, we derive various algebraic properties for several operations on success functions and use them to prove various closure properties of ALOHA receivers, including (i) ALOHA receivers in tandem, (ii) cooperative ALOHA receivers, (iii) ALOHA receivers with traffic multiplexing, and (iv) ALOHA receivers with packet coding. By conducting extensive simulations, we show that our theoretical results match extremely well with the simulation results.

In this article, we present a susceptible–infected–recovered (SIR) model with individuals wearing facial masks and individuals who do not. The disease transmission rates, the recovering rates, and the fraction of individuals who wear masks are all time-dependent in the model. We develop a progressive estimation of the disease transmission rates and the recovering rates based on the coronavirus disease 2019 (COVID-19) data published by John Hopkins University. We determine the fraction of individual who wear masks by a maximum likelihood estimation, which maximizes the transition probability of a stochastic SIR model. The transition probability is numerically difficult to compute whether the number of infected individuals is large. We develop an approximation for the transition probability based on the central limit theorem and mean-field approximation. We show through numerical study that our approximation works well. We develop a bond percolation analysis to predict the eventual fraction of population who are infected, assuming that parameters of the SIR model do not change anymore. The percolation threshold is exactly the basic reproduction number of the epidemic. We predict the outcome of COVID-19 pandemic using our theory.

In this article, we develop a probabilistic framework for analyzing coded random access. Our framework is based on a new abstract receiver (decoder), called a Poisson receiver, that is characterized by a success probability function of a tagged packet subject to a Poisson offered load. We show that various coded slotted ALOHA (CSA) systems are Poisson receivers. Moreover, Poisson receivers have two elegant closure properties: (i) Poisson receivers with packet routing are still Poisson receivers, and (ii) Poisson receivers with packet coding are still Poisson receivers. These two closure properties enable us to use smaller Poisson receivers as building blocks for analyzing a larger Poisson receiver. As such, we can analyze complicated systems that are not possible by the classical tree evaluation method. In particular, for CSA systems with both spatial diversity and temporal diversity, we can use the framework of Poisson receivers to compute the exact (asymptotic) throughput. We demonstrate that our framework can be used to provide differentiated services between ultra-reliable low-latency communication (URLLC) traffic and enhanced mobile broadband (eMBB) traffic. By conducting extensive simulations, we also verify that our theoretical results match extremely well with the simulation results.

In this article, we propose a new averaging model for modeling the competitive influence of K candidates among n voters in an election process. For such an influence propagation model, we address the question of how many seeded voters that a candidate needs to place among undecided voters in order to win an election. We show that for a random network generated from the stochastic block model (SBM), there exists a percolation threshold for a candidate to win the election if the number of seeded voters placed by the candidate exceeds the threshold. By conducting extensive experiments, we show that our theoretical percolation thresholds are very close to those obtained from simulations for random networks, and the errors are within 10% for a real-world network.

Centrality analysis has been a very important research topic in online social networks. Traditionally, centrality analysis is carried out for a specific network. In this article, we conduct centrality analysis in random networks. For this, we consider the class of d-regular directed acyclic random networks generated by the configuration model. We consider two centralities: the PageRank and the in-component centrality (defined as the size of the in-component of a node). For the PageRank, we derive a closed-form solution in the complete directed acyclic network and show that it can be used as an approximation in a d-regular directed acyclic random network. For the in-component centrality, we derive upper bounds for its first moment and its second moment in a d-regular directed acyclic random network. These results have interesting applications in top-k recommendations. In particular, we propose a qualifying round algorithm that outputs a set of nodes to include the top-k nodes with high probability. Various experiments are conducted to show the effectiveness of the algorithm.

In this paper, we study the problem of providing heterogeneous quality-of-service (QoS) guarantees for asynchronous grant-free uplink transmissions in multichannel wireless networks. The multiple access channel model is the classical collision channel, where partially overlapped packets during the transmissions are assumed to be completely lost. For such a network model, we propose two asynchronous multichannel transmission schedules (AMTS): 1) the EPC-based AMTS and 2) the DS-based AMTS. The EPC-based AMTS is constructed by time-spreading one-dimensional extended prime code (EPC), and the DS-based AMTS is constructed by using difference sets (DS) and finite projective planes. We show for both scheduling algorithms that the maximum delay between two successive successful transmissions of an active device can be upper bounded by a constant when the channel load does not exceed a designed threshold parameter. Moreover, different devices are allowed to have different throughput (rate) guarantees. By conducting extensive simulations, we also show that the overall throughputs of both scheduling algorithms are almost identical to that of the random access protocol, when the number of active devices exceeds the designed threshold parameter.

In this paper, we conduct centrality analysis for attributed networks. An attributed network, as a generalization of a graph, has node attributes and edge attributes that represent the "features'' of nodes and edges. Traditionally, centrality analysis of a graph is done by providing a sampling method, such as a random walk, for the graph. To take node attributes and edge attributes into account, the sampling method in an attributed network needs to be twisted from the original sampling method in the underlining graph. For this, we consider the family of exponentially twisted sampling methods and propose using path measures to specify how the sampling method should be twisted. For signed networks, we define the influence centralities by using a path measure from opinions dynamics and the trust centralities by using a path measure from a chain of trust. For attributed networks with node attributes, we also define advertisement-specific influence centralities by using a specific path measure that models influence cascades in such networks. Various experiments are conducted to further illustrate these centralities by using two real datasets: the political blogs and the MemeTracker dataset.

There is growing interest in structural analysis of directed networks. Two major points that need to be addressed are: 1) a formal and precise definition of the graph clustering and community detection problem in directed networks and 2) algorithm design and evaluation of community detection algorithms in directed networks. Motivated by these, we develop a probabilistic framework for structural analysis and community detection in directed networks based on our previous work in undirected networks. By relaxing the assumption from symmetric bivariate distributions in our previous work to bivariate distributions that have the same marginal distributions in this paper, we can still formally define various notions for structural analysis in directed networks, including centrality, relative centrality, community, and modularity. We also extend three commonly used community detection algorithms in undirected networks to directed networks: the hierarchical agglomerative algorithm, the partitional algorithm, and the fast unfolding algorithm. These are made possible by two modularity preserving and sparsity preserving transformations. In conjunction with the probabilistic framework, we show these three algorithms converge in a finite number of steps. In particular, we show that the partitional algorithm is a linear time algorithm for large sparse graphs. Moreover, the outputs of the hierarchical agglomerative algorithm and the fast unfolding algorithm are guaranteed to be communities. These three algorithms can also be extended to general bivariate distributions with some minor modifications. We also conduct various experiments by using two sampling methods in directed networks: 1) PageRank and 2) random walks with self-loops and backward jumps.

One of the main problems in all-optical packetswitched networks is the lack of optical buffers, and currently the only known feasible technology for the constructions of optical buffers is to use optical crossbar Switches and fiber Delay Lines (SDLs). In this paper, we consider SDL constructions of optical queues with a limited number of recirculations through the optical switches and the fiber delay lines. Such a problem arises from practical feasibility considerations, such as crosstalk, power loss, amplified spontaneous emission from the Erbium doped fiber amplifiers, and the pattern effect of the optical switches. We first transform the design of the fiber delays in such SDL constructions into an equivalent integer representation problem. Specifically, given 1 ≤ k ≤ M, we seek for an M-sequence dM= (d1, d2, ..., dM) of positive integers to maximize the number of consecutive integers (starting from 0) that can be represented by the C-transform (a generalization of the well-known binary representation) with respect to dMsuch that there are at most k 1-entries in their C-transforms. Then, we propose a class of greedy constructions of dM, in which d1, d2, ..., dMare obtained recursively in a greedy manner so that the number of representable consecutive integers by using d1, d2, . .., diis larger than that by using d1, d2, . .., di-1for all i. Finally, we show that every optimal construction (in the sense of maximizing the number of representable consecutive integers) must be a greedy construction. As a result, the complexity of searching for an optimal construction can be greatly reduced from exponential time to polynomial time by only considering the greedy constructions rather than performing an exhaustive search. The solution of such an integer representation problem can be applied to the constructions of optical 2-to-1 FIFO multiplexers with a limited number of recirculations. Similar results can be obtained for the constructions of optical linear compressors/decompressors with a limited number of recirculations.

The multichannel rendezvous problem in cognitive radio networks (CRNs) has been a hot research topic lately. One of the most challenging settings of the multichannel rendezvous problem is the oblivious rendezvous problem in heterogeneous CRNs, where: 1) there are no distinguishable roles of users; 2) users' clocks are not synchronized; 3) users may have different available channel sets; and 4) there is no universal labelling of the channels. Most existing works in the literature focus on achieving deterministic bounds for the maximum conditional time-to-rendezvous (MCTTR) and perform poorly (in comparison with the random algorithm) for the expected time-torendezvous (ETTR) due to the “stay” modes in these works. In this paper, we tackle the oblivious rendezvous problem by taking both MCTTR and ETTR into consideration. In order to have guaranteed rendezvous, we only make two assumptions: (A1) there is at least one common available channel and (A2) there is a unique ID for each user. We first propose a new class of strong symmetrization mappings to encode user IDs for speeding up the rendezvous process. Two efficient and yet simple encoding schemes are proposed by utilizing the C-transform and the existing 4B5B encoding. Based on the new class of strong symmetrization mappings, we propose the twoprime modular clock algorithm for the two-user rendezvous problem. The ETTR of our algorithm is almost the same as that of the random algorithm and its MCTTR is also comparable to the best existing bound. We also extend the two-prime modular clock algorithm for multiuser rendezvous by proposing the stick together algorithm and the spread out algorithm. One interesting finding for the multiuser rendezvous problem is that the spread out algorithm is not always better than the stick together algorithm as commonly claimed in the literature.

In our recent works, we developed a probabilistic framework for structural analysis in undirected networks. The key idea of that framework is to sample a network by a symmetric bivariate distribution and then use that bivariate distribution to formerly define various notions, including centrality, relative centrality, community, and modularity. The main objective of this paper is to extend the probabilistic framework to directed networks, where the sampling bivariate distributions could be asymmetric. Our main finding is that we can relax the assumption from symmetric bivariate distributions to bivariate distributions that have the same marginal distributions. By using such a weaker assumption, we show that various notions for structural analysis in directed networks can also be defined in the same manner as before. However, since the bivariate distribution could be asymmetric, the community detection algorithms proposed in our previous work cannot be directly applied. For this, we show that one can construct another sampled graph with a symmetric bivariate distribution so that for any partition of the network, the modularity index remains the same as that of the original sampled graph. Based on this, we propose a hierarchical agglomerative algorithm that returns a partition of communities when the algorithm converges.

In this paper, we propose a new model for binary opinion dynamics in a (fully connected) structurally balanced network. In a structurally balanced network, agents are classified into two clusters and two agents in the same cluster (resp. different clusters) are connected with a positive (resp. negative) edge. Initially, every agent is assigned with one of the two opinions randomly. In every time slot, three agents are randomly selected to have their opinions updated. If the three agents belong to the same cluster, the majority rule (MR) is used to update their opinions. On the other hand, if the three agents belong to two different clusters, with probability p, a consensus is reached by the MR, and with probability 1 - p, a polarization (in line with the signs of the three edges) is reached. The probability p, called the rationality probability, plays a significant role for measuring how rational the agents in a network behave when they encounter different opinions. By applying a fluid limit theorem for jump Markov processes, we derive a system of differential equations for the density functions of opinions for large networks. We show that the equilibrium points corresponding to consensus and polarization are the only stable equilibrium points. All other equilibrium points are all unstable. As such, as time goes on, the network eventually reaches a consensus or a polarization, depending on the rationality probability and the initial state of the network.

Two-stage constructions and banyan-type networks play important roles in designing high speed switch fabrics. Switch fabrics designed from two-stage constructions and banyan-type networks cannot realize all the permutations and are known as conditionally nonblocking switches. A renowned property for conditionally nonblocking switches is the closure property, i.e., if all the switches in a two-stage construction can realize a subset of permutations that satisfy a certain property P, then the switch resulted from the two-stage construction can also realize a subset of permutations that satisfy the same property P. However, such a closure property is mostly stated for the sufficient part in the literature and the necessary part of the statement is in general either not true or unknown. Finding such a necessary and sufficient result is of fundamental importance to two-stage constructions as it can completely characterize the permutations that are realizable by two-stage constructions. In this paper, we prove a necessary and sufficient closure property for two-stage constructions. For this, we consider uniform mapping permutations and define uniform mapping switches as switches that can only realize the set of uniform mapping permutations. We show that a switch constructed by a two-stage construction is a uniform mapping switch if and only if all the switches at the first stage and the second stage are uniform mapping switches. Such a necessary and sufficient result provides a complete characterization of the permutations that can be realized by two-stage constructions. Since banyan-type networks are constructed recursively by using two-stage constructions with 2 × 2 switches, we obtain a complete characterization for any realizable permutation of any banyan-type network as a composition of its trace, a uniform mapping permutation and its guide.

The crosstalk effect is one of the main problems in deep sub-micron designs of high-speed buses. To mitigate the crosstalk effect, there are several types of crosstalk avoidance codes proposed in the literature. In this paper, we are particularly interested in generating forbidden transition codes that do not have opposite transitions on any two adjacent wires. For this, we propose asequential bit-stuffingalgorithm and aparallel bit-stuffingalgorithm. For the sequential bit-stuffing algorithm, we perform a worst-case analysis and a probabilistic analysis. We show by both theoretic analysis and simulations that the coding rate of the sequential bit-stuffing encoding scheme is quite close to the Shannon capacity. In particular, for a bus with$n=10$parallel wires, the difference is only 2.2 percent. Using a Markov chain analysis, we show that the coding rate of the parallel bit-stuffing algorithm is only slightly lower than that of the sequential bit-stuffing algorithm. The implementation complexity of the parallel bit-stuffing algorithm is linear with$n$. In comparison with the existing forbidden transition codes that use the Fibonacci representation in the literature, our bit-stuffing algorithms not only achieve higher coding rates but also have much lower implementation complexity.

In this paper we propose to model the formation of online social networks by a duplication model. In this model vertices are added into the network one at a time. Each vertex is first attached to a randomly selected vertex. Each neighbor of the attached vertex establishes an edge with the new vertex with a probability. A main contribution of this paper is that we derive analytically the clustering coefficient for this model. Numerical studies show that the range of mean degree and the clustering coefficient of the duplication model is quite large. By properly choosing values for the parameters of our model, the mean degree and the clustering coefficient match well with those of popular online social networks.

One of the main problems in deep submicrometer designs of high speed buses is the propagation delay due to the crosstalk effect. To alleviate the crosstalk effect, there are several types of crosstalk avoidance codes proposed in the literature. In this paper, we develop explicit constructions of two types of memoryless crosstalk avoidance codes: 1) forbidden overlap codes (FOCs) and 2) forbidden transition codes (FTCs). Our constructions for both FOCs and FTCs have the largest set of codewords. To the best of our knowledge, this is the first explicit construction of a FOC that has the largest set of codewords. Our approach is based on the C-transform developed for routing optical packets in optical queues. We show such an approach can also be used for constructing limited-weight no adjacent transition codes.

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.

Based on Newman's fast algorithm, in this paper we develop a general probabilistic framework for detecting community structure in a network. The key idea of our generalization is to characterize a network (graph) by a bivariate distribution that specifies the probability of the two vertices appearing at both ends of a randomly selected path in the graph. With such a bivariate distribution, we give a probabilistic definition of a community and a definition of a modularity index. To detect communities in a network, we propose a class of distribution-based clustering algorithms that have comparable computational complexity to that of Newman's fast algorithm. Our generalization provides the additional freedom to choose a bivariate distribution and a correlation measure. As such, we obtain significant performance improvement over the original Newman fast algorithm in the computer simulations of random graphs with known community structure.

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.

In this paper, we consider the constructions of anN-to-Koptical priority queue with buffer Σi=1Mdiby using a feedback system consisting of a single (M+max[N,K]) × (M+max[N,K]) (bufferless) optical crossbar switch, min[N,K] 1× 2 (bufferless) optical crossbar switches, andMfiber delay lines with delaysd1,d2,...,dM, where N is the number of arrival links and K is the number of departure links of the priority queue. We first obtain two sufficient conditions [the conditions (A1) and (A2) in Section I] for our constructions ofN-to-Koptical priority queues. By establishing a space-time advancement property and a monotonically decreasing/increasing property for the packets stored in the fiber delay lines, we then use these sufficient conditions to show that with an appropriate choice for the delaysd1,d2,...,dM, we can achieve a buffer size ofO([(M3/N2)]) for the case thatN=K. For the special case thatN=K=1, our constructions achieve a buffer size ofO(M3), which is much better than theO(M2) buffer size previously known in the literature for single-input single-output optical priority queues. Therefore, other than the extension from the constructions of optical priority queues with a single input and a single output to the constructions of optical priority queues with multiple inputs and multiple outputs, our constructions also achieve a larger buffer size than previous constructions of single-input single-output optical priority queues. Furthermore, we give another sufficient condition [the condition (A3) in Section I] for our constructions ofN-to-Koptical priority queues and then use that condition to obtain choices for the delaysd1,d2,...,dMso that our constructions have the fault tolerant capability that can tolerate up toFbroken/malfunctioning fibers (e.g., fiber cut, fiber shorting out, etc.), where 0 ≤F≤M-1.

It is well known that output-buffered switches have better performance than other switch architectures. However, output buffered switches also suffer from the notorious scalability problem, and direct constructions of large output-buffered switches are difficult. In this paper, we study the problem of constructing scalable switches that have comparable performance (in the sense of 100 percent throughput and first-in first-out (FIFO) delivery of packets from the same flow) to output-buffered switches. For this, we propose a new concept, called quasi-output-buffered switch. Like an output-buffered switch, a quasi-output-buffered switch is a deterministic switch that achieves 100 percent throughput and delivers packets from the same flow in the FIFO order. Using the three stage Clos network, we show that one can recursively construct a larger quasi-output-buffered switch with a set of smaller quasi output-buffered switches. By recursively expanding the three-stage Clos network, we obtain a quasi-output-buffered switch with only 2 × 2 switches. Such a switch is called a packet-pair switch in this paper as it always transmits packets in pairs. By computer simulations, we show that packet-pair switches have better delay performance than most load-balanced switches with comparable construction complexity.

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.

Motivated by the design of high speed switching fabrics, in this paper we propose a bit-stuffing algorithm for generating forbidden transition codes to mitigate the crosstalk effect between adjacent wires in long on-chip buses. We first model a bus with forbidden transition constraints as a forbidden transition channel, and derive the Shannon capacity of such a channel. Then we perform a worst case analysis and a probabilistic analysis for the bit-stuffing algorithm. We show by both theoretic analysis and simulations that the coding rate of the bit stuffing encoding scheme for independent and identically distributed (i.i.d.) Bernoulli input traffic is quite close to the Shannon capacity, and hence is much better than those of the existing forbidden transition codes in the literature, including the Fibonacci representation.

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.

Load balanced Birkhoff-von Neumann switches are known to be more scalable than other existing switch architectures that guarantee 100% throughput. However, there are still several design and implementation challenges in prototyping such a switch, including (i) modular design, (ii) synchronization and propagation delay, (iii) fault tolerance, and (iv) buffer management. In this paper, we address these challenges and propose our solutions in our prototype. Specifically, we propose a folded architecture for modular design, a pipelining mechanism for synchronization and propagation delay, a Benes network for fault tolerance, and a caching scheme for buffer management.

Despite all the recent advances in the mathematical theories for constructing optical queues by optical Switches and fiber Delay Lines (SDL), there are still many problems that need to be resolved. In this paper, we tackle the following problems: (i) is it possible to construct optical queues with switches of arbitrary sizes? (ii) is there a general theory that unifies many constructions of optical queues with known packet delays? and (iii) under what conditions can a concatenation of optical queues allow overtaking? For the first problem, we propose a new class of optical memory cells that can be made by switches of arbitrary sizes. Moreover, we propose the generalized C -transform for routing packets through such optical memory cells. For the second problem, we introduce a new class of optical queues, including FIFO, LIFO and absolute contractors. We show that both linear compressors in [13] and FIFO multiplexers (with multiple inputs) in [5], [7] are special cases of contractors. An interesting finding is that overtaking can occur in LIFO and absolute contractors.

A Combined Input and Crosspoint Queueing (CICQ) switch is a switch that has both buffers at the crosspoints of the switch fabric and buffers at the inputs. Inspired by the fixed frame based algorithm for an input-buffered switch and the smooth scheduling algorithm for a CICQ switch, in this paper we propose using a dynamic frame sizing algorithm for a CICQ switch. It is formally shown that such a CICQ switch indeed achieves 100% throughput for certain Poisson-like traffic models. This is done without using the framed Birkhoff-von Neumann decomposition needed. Moreover, such a CICQ switch only requires a two-cell buffer at each crosspoint when there is only unicast traffic. Unlike input-buffered switches, the dynamic frame sizing algorithm also achieves 100% throughput in the setting of multicast traffic. This is done at the cost of increasing the buffer size at each crosspoint.

In this paper we propose to construct an flexible delay line with maximum delay d by parallel non-overtaking delay lines. We show that for a fixed number of non-overtaking delay lines, an optimal policy to minimize packet losses is to assign arriving packets to the non-overtaking delay line that has the largest residual service time while maintaining the FIFO order for each non-overtaking delay lines. Based on this optimal policy we show that to exactly emulate an flexible delay line, one needs [(d + 1)/2] non-overtaking delay lines. We also show that if one can tolerate a small packet loss probability, one just needs O(radic(d)) non-overtaking delay lines. In this case, we show that the residual service times of the non-overtaking delay lines behaved as if they followed the order statistics of uniform random variables.

The constructions of optical queues is one of the most critically sought after optical technologies in all-optical packet-switched networks, and constructing optical queues directly via optical switches and fiber delay lines (SDL) has received a lot of attention recently in the literature. A practical and challenging issue in the constructions of optical queues is on the fault tolerant capability of such constructions. In this paper, we focus on the constructions of fault tolerant optical linear compressors and linear decompressors. The basic network element for our constructions is scaled optical memory cell, which is constructed by a 2X2 optical crossbar switch and a fiber delay line. We first obtain a fundamental result on the minimum construction complexity of a linear compressor by using fiber delay lines as the storage devices for the packets queued in the linear compressor. This result shows that one of our previous constructions of a linear compressor by a concatenation of scaled optical memory cells is an optimal construction in the sense of minimizing the construction complexity. However, such an optimal construction lacks the fault tolerant capability. To construct a linear compressor with fault tolerant capability, we give a multistage construction of a self-routing linear compressor by a concatenation of scaled optical memory cells, and show that if the delays, say d1, d2, . . . , dM, of the fibers in the scaled optical memory cells satisfy a certain condition (specifically, the condition in (A2) given in Section IV-A), then our multistage construction can be operated as a self-routing linear compressor with maximum delay Sigmai=1M-Fdiin the worst case even after up to F of the M scaled optical memory cells fail to function properly, where 0 les Fles M - 1. Furthermore, we prove that our multistage construction with the fiber delays d1, d2, . . . , dMgiven by the generalized Fibonacci sequence of order F is the best among all of the constructions of a linear compressor that can tolerate up to F faulty scaled optical memory cells by using M scaled optical memory cells. Similar results are also obtained for the constructions of fault tolerant linear decompressors.

Wireless sensor networks attract more and more attention since they are capable of monitoring the environment. Since wireless sensor nodes typically have limited energy and power, power efficiency is a main concern in designing protocols for wireless sensor networks. Data aggregation is one of the strategies that can reduce the power consumption in wireless sensor networks. In this paper, we propose a cross layer algorithm with data aggregation to minimize the power consumption. Most importantly, our proposed algorithm is distributed and therefore, it is suitable for wireless sensor networks. From numerical results, we conclude that not all data packets should be aggregated before they arrive the destination nodes.

Output-buffered switches are known to have better performance than other switch architectures. However, output- buffered switches also suffer from the notorious scalability problem, and direct constructions of large output-buffered switches are difficult. In this paper, we study the problem of constructing scalable switches that have comparable performance to output- buffered switches. For this, we propose a new concept, called quasi-output-buffered switch. Like an output-buffered switch, a quasi-output-buffered switch is a deterministic switch that delivers packets in the FIFO order and achieves 100% throughput. Using the three-stage Clos network, we show that one can recursively construct a larger quasi-output-buffered switch with a set of smaller quasi-output-buffered switches. By recursively expanding the three-stage Clos network, we obtain a quasi-output-buffered switch with only 2 x 2 switches. Such a switch is called a packet- pair switch as it always transmits packets in pairs. By computer simulations, we show that packet-pair switches have better delay performance than most load-balanced switches with comparable construction complexity.

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.

A new optical device called variable optical delay line (VODL) has been proposed in the literature. As suggested by its name, the delay of a VODL can be dynamically set within a certain range. Once set, a VODL behaves like a traditional fiber delay line and can admit packets requiring the same delay as that set by the VODL. As in the queueing context, a VODL can thus be viewed as a server that serves packets with the service times equal to the required delays. We consider loss systems with parallel VODLs subject to various classes of packet arrivals. Such loss systems are different from the classical loss systems as a VODL, even when occupied, can still admit new packets with the same delay. For the case with an infinite number of VODLs, we show that the number of VODLs occupied by different classes of packets still has a product form solution. However, the analysis for the case with a finite number of VODLs is much more difficult. For this, we propose an approximation method based on state truncation. We show that the packet loss probabilities derived from our approximation are very close to those generated from simulations. In order to minimize the packet loss probabilities in such loss systems, we also consider the problem of assigning dedicated VODLS to various classes of packets. We show under the light traffic condition, the complete sharing policy, i.e., the policy that does not assign any dedicated VODLs, is optimal. For the general traffic condition, we propose a greedy search algorithm to find a suboptimal assignment of dedicated VODLS. Simulation results show that our greedy algorithm yields very good assignments when comparing with the optimal ones.

Traditionally, conflict resolution in an input- buffered switch is solved by finding a matching between inputs and outputs per time slot, which incurs unscalable computation and communication overheads. The main objective of this paper is to propose a scalable solution, called the mailbox switch, that solves the out-of-sequence problem in the two-stage switch architecture. The key idea of the mailbox switch is to use a set of symmetric connection patterns to create a feedback path for packet departure times. With the information of packet departure times, the mailbox switch can schedule packets so that they depart in the order of their arrivals. Despite the simplicity of the mailbox switch, we show via both the theoretical models and simulations that the throughput of the mailbox switch can be as high as 75%. With limited resequencing delay, a modified version of the mailbox switch achieves 95% throughput. We also propose a recursive way to construct the switch fabrics for the set of symmetric connection patterns. If the number of inputs, N, is a power of 2, we show that the switch fabric for the mailbox switch can be built with y log2 N 2 x 2 switches.

The capacity of a power controlled wireless network can be changing due to user's mobility, fading or shadowing effects. As a result, the quality of service (QOS) of all users may not be guaranteed in a wireless network. In this paper, we propose a two-phase distributed subset selection algorithm to identify a subset of wireless users whose QOS is guaranteed. In the first phase, it finds a basic feasible set, and then it tries to expand the basic feasible set in the second phase. Through simulations we evaluate the performance of the proposed scheme in terms of the number of average feasible links and the average execution time.

Optical queues, usually constructed by optical switches and fiber delay lines (SDL), are the key elements for conflict resolution in optical packet switching. It is recently shown in the work of Chang et al. (2006) that several optical queues constructed by SDL elements are indeed infinite dimensional switches in time and they can be constructed by many classical constructions in the switching theory. In particular, a (unicast) flexible delay line is a discrete-time infinite-server queue that corresponds to the nonblocking switch in the switching theory, and it can be constructed either by the three-stage Clos network or the Cantor network. In this paper, we propose two new constructions for multicast flexible delay lines that use the unicast flexible delay lines as the basic construction elements. The first one is constructed by using parallel unicast flexible delay lines. It is shown that a multicast flexible delay line with maximum delay d can be constructed by using O(radic/d) unicast flexible delay lines with maximum delay d. Our second construction is a recursive construction. We show that a multicast flexible delay line with maximum delay 2d-1 can be constructed by two unicast flexible delay lines with maximum delay d-1 and a multicast flexible delay line with maximum delay d-1. As an application, we show that multicast flexible delay lines can be used for the constructions of optical multicast switches with 100% throughput.

The constructions of optical buffers is one of the most critically sought after optical technologies in all-optical packet-switched networks, and constructing optical buffers directly via optical switches and fiber delay lines (SDL) has received a lot of attention recently in the literature. A practical and challenging issue of the constructions of optical buffers that has not been addressed before is on the fault tolerant capability of such constructions. In this paper, we focus on the constructions of fault tolerant linear compressors and linear decompressors. The basic network element for our constructions is scaled optical memory cell, which is constructed by a 2 x 2 optical crossbar switch and a fiber delay line. We give a multistage construction of a self-routing linear compressor by a concatenation of scaled optical memory cells. We also show that if the delays, say d1,d2,... ,dm, of the fibers in the scaled optical memory cells satisfy a certain condition (specifically, the condition in (A 2) given in Section I), then our multistage construction can be operated as a self-routing linear compressor with maximum delay SigmaM-Fi=1dieven after up to F of the M scaled optical memory cells fail to function properly, where 0 les F les M - 1. Furthermore, we prove that our multistage construction with the fiber delays d1, d2, ... , dMgiven by the generalized Fibonacci sequence of order F is the best among all constructions of a linear compressor that can tolerate up to F faulty scaled optical memory cells by using M scaled optical memory cells. Similar results are also obtained for the constructions of fault tolerant linear decompressors.

In this paper, we study the problem of exact emulation of two types of optical queues: (i)N-to-1 output-buffered multiplexers with variable length bursts, and (ii) N times N output-buffered switches with variable length bursts. For both queues, the delay of a packet (in a burst) is known upon its arrival. As such, one can emulate such queues by finding a delay path that yields the exact delay for each packet. For emulating the delay of a packet in such queues, in this paper we consider a multistage feedforward network with optical crossbar switches and fiber delay lines (SDL). For any fixed delay d, there exist multiple delay paths in such a network. A delay path is feasible if it satisfies the following three constraints: (i) conflict constraint: no more than one packet can be scheduled at the same input/output ports of each crossbar switch at the same time, (ii) causality constraint: no packet can be scheduled before its arrival, and (iii) strong contiguity constraint: packets in the same burst should be routed through any fiber delay lines contiguously. By the worst case analysis, we find sufficient conditions for the numbers of delay lines needed in each stage of such a feedforward network to achieve exact emulation of both queues. For N-to-1 output-buffered multiplexers, our sufficient conditions are also necessary when each burst contains exactly one packet. By computer simulation, we also show that the number of delay lines in each stage can be greatly reduced due to statistical multiplexing gain.

In this paper, we consider the construction of an optical priority queue with a single (M+1)times(M+1) switch and M fiber delay lines. The M fiber delay lines are connected from M outputs of the switch back to M inputs of the switch, leaving one input (resp. output) of the switch for the input (resp. output) of the priority queue. It was known that with an appropriate choice of the lengths of the delay lines, such a construction can be used for exact emulation of an optical priority queue with O(M2) buffer size. In this paper, we show that the buffer size can be further extended to O(M3) using the same construction. The improvement relies on establishing a partial ordering for all the packets stored in the delay lines.

Load-balanced switches have received a great deal of attention recently as they are much more scalable than other existing switch architectures in the literature. However, as there exist multiple paths for flows of packets to traverse through load-balanced switches, packets in such switches may be delivered out of order. In this paper, we propose a new switch architecture, called the CR switch, that not only delivers packets in order but also guarantees 100% throughput. The key idea, as in a multiple access channel, is to operate the CR switch in two modes: (i) the contention mode in light traffic and (ii) the reservation mode in heavy traffic. To do this, we invent a new buffer management scheme, called I-VOQ (virtual output queue with insertion). With the I-VOQ scheme, we give rigorous mathematical proofs for 100% throughput and in order packet delivery of the CR switch. By computer simulations, we also demonstrate that the average packet delay of the CR switch is considerably lower than other schemes in the literature, including the uniform frame spreading scheme (Keslassy et al., 2003), the padded frame scheme (Jaramillo et al., 2006) and the mailbox switch (Chang et al., 2004).

One of the most popular approaches for the constructions of optical buffers needed for optical packet switching is to use switched delay lines (SDL). Recent advances in the literature have shown that there exist systematic SDL construction theories for various types of optical buffers, including first-in first-out (FIFO) multiplexers, FIFO queues, priority queues, linear compressors, nonovertaking delay lines, and flexible delay lines. As parallel FIFO queues with a shared buffer are widely used in many switch architectures, e.g., input-buffered switches and load-balanced Birkhoff-von Neumann switches, in this paper we propose a new SDL construction for such queues. The key idea of our construction for parallel FIFO queues with a shared buffer is two-level caching, where we construct a dual-port random request queue in the upper level (as a high switching speed storage device) and a system of scaled parallel FIFO queues with a shared buffer in the lower level (as a low switching speed storage device). By determining appropriate dumping thresholds and retrieving thresholds, we prove that the two-level cache can be operated as a system of parallel FIFO queues with a shared buffer. Moreover, such a two-level construction can be recursively expanded to an n-level construction, where we show that the number of 2times2 switches needed to construct a system of N parallel FIFO queues with a shared buffer B is O((NlogN)log(B/(NlogN))), for NGt1. For the case with N=1, i.e., a single FIFO queue with buffer B, the number of 2times2 switches needed is O(logB). This is of the same order as that previously obtained by Chang We also show that our two-level recursive construction can be extended to construct a system of N parallel last-in first-out (LIFO) queues with a shared buffer by using the same number of 2times2 switches, i.e., O((NlogN)log(B/(NlogN))), for NGt1 and O(logB) for N=1. Finally, we show that a great advantage of our construction is its fault tolerant capability. The reliability of our construction can be increased by simply adding extra optical memory cells (the basic elements in our construction) in each level so that our construction still works even when some of the optical memory cells do not function properly

Abstract — Queueing theory is generally known as the theory to study the performance of queues. In this paper, we are interested in another aspect of queueing theory, the theory to construct queues via switched delay lines. We consider three types of discrete-time queues: linear compressors, non-overtaking delay lines and flexible delay lines. These three types of queues correspond to certain conditional nonblocking switches and (strict sense) nonblocking switches in switching theory. Analogous to their counterparts in switching theory, there exist multistage constructions for these three types of queues. Specifically, we develop a two-stage construction of a linear compressor and a three-stage construction of a non-overtaking delay line. Similarly, there is a three-stage construction of a flexible delay line. Moreover, a flexible delay line can also be constructed by a layered Cantor network. I.

The capacity of a power controlled wireless network can be changing due to user’s mobility, fading or shadowing effects. As a result, the quality of service (QOS) of users accepted by call admission control may not be guaranteed in a wireless network. In this paper, we propose a two-phase distributed scheduling algorithm to identify a subset of wireless users whose QOS is guaranteed. In the first phase, each link transmits with a probing power and each user determines whether it can be a member of the basic feasible set or not in a distributed manner. In the second phase, we develop a generalized call admission control algorithm that attempts to merge as many as possible the rest links into the basic feasible set. We consider a variation that attempts to enlarge the set of feasible links. For starvation prevention, we discuss conflict resolution in the power domain and in the time domain. Through simulation we evaluate the performance of the proposed scheme in terms of average execution time, average packet delay and maximum of the cycle time.

In the literature, research has been published extensively on how one achieves exact emulation of First In First Out (FIFO) multiplexers for fixed-size cells (or packets) using optical crossbar Switches and fiber Delay Lines (SDL). In this paper, we go a step further and propose a new architecture that achieves exact emulation of FIFO multiplexers for variable length bursts. Our architecture consists of two blocks: a cell-scheduling block and a FIFO multiplexer for fixed-size cells. Both blocks are made of SDI, units. The objective of the cell-scheduling block is to schedule cells in a burst to the right input at the right time so that cells in the same burst depart contiguously from the multiplexer for fixed-size cells. We show that cell scheduling can be done efficiently by keeping track of a single state variable, called the total virtual waiting time in this paper. Moreover, the delay through the cell-scheduling block is bounded above by a constant that only depends on the number of inputs and the maximum number of cells in a burst. Such a delay bound provides a limit on the number of fiber delay lines needed in the cell-scheduling block.

Discrete-time queues are infinite dimensional switches in time. Ever since Shannon published his paper ("Memory requirements in a telephone exchange", Bell Syst. Tech. J., pp. 343-349, vol. 29, 1950) on the memory requirements in a telephone exchange, there have been tremendous efforts in the search for switches with minimum complexity. Constructing queues with minimum complexity has not received the same amount of attention as queues are relatively cheap to build via electronic memory. Recent advances in optical technologies, however, have spurred interest in building optical queues with minimum complexity. In this correspondence, we develop mathematical theory of constructing discrete-time optical first-in-first-out (FIFO) queues. To our surprise, we find that many classical constructions for switches have their counterparts for constructing queues. Analogous to the three-stage construction of Clos networks, we develop a three-stage construction of optical FIFO queues via switched delay lines (SDLs). Via recursively expanding the three-stage construction, we show that an optical FIFO queue with buffer 2/sup n/-1 can be constructed by using 2n 2/spl times/2 switches with the total fiber length 3/spl middot/2/sup n-1/-2.

In this paper, we prove a necessary and sufficient condition for the construction of 2-to-1 optical buffered first-in–first-out (FIFO) multiplexers by a single crossbar switch and fiber delay lines. We consider a feedback system consisting of an$(M+2)times (M+2)$crossbar switch and$M$fiber delay lines with delays$d_1, d_2,ldots, d_M$. These$M$fiber delay lines are connected from$M$outputs of the crossbar switch back to$M$inputs of the switch, leaving two inputs (respectively, two outputs) of the switch for the two inputs (respectively, two outputs) of the 2-to-1 multiplexer. The main contribution of this paper is the formal proof that$d_1=1$and$d_i le d_i+1 le 2d_i$,$i=1,2, ldots, M-1$, is a necessary and sufficient condition on the delays$d_1, d_2,ldots,d_M$for such a feedback system to be operated as a 2-to-1 FIFO multiplexer with buffer$sum _i=1^M d_i$under a simple packet routing policy. Specifically, the routing of a packet is according to a specific decomposition of the packet delay, called the$cal C$-transform in this paper. Our result shows that under such a feedback architecture a 2-to-1 FIFO multiplexer can be constructed with$M=O(log B)$, where$B$is the buffer size. Therefore, our construction improves on a more complicated construction recently proposed by Sarwate and Anantharam that requires$M=O(sqrt B)$under the same feedback architecture (we note that their design is more general and works for priority queues).

Recently, there is tremendous interest in the research of two-stage switches. Unlike input-buffered switches, two-stage switches do not need to find matchings between inputs and outputs. However, two-stage switches usually suffer from the out-of-sequence problem. To design a simple and high performance switch using the two-stage architecture, we address three buffer design problems in this paper: re-sequencing buffers, central buffers and input buffers. We show that the size of the resequencing buffer needs to be proportional to the size of the central buffer to ensure that no packets are lost due to resequencing. Via simulations, we find that a moderate size of central buffer yields good throughput when traffic is not bursty. However, when the traffic is bursty, one needs to address the head-of-line blocking problem at the input. We also find that using the round-robin service policy for multiple virtual output queues at inputs may exhibit a catastrophic phenomenon, called a non-ergodic mode. When a switch is trapped in a non-ergodic mode, its throughput is sharply reduced. To solve such a problem in input buffers, we show that one may introduce "randomness" into a switch to jump out of a non-ergodic mode.

Many switch architectures with buffers placed at input ports suffer from the head-of-line blocking (HOL) problem and thus can not achieve 100% throughput. For an input-buffered switch, the number of HOL packets is often characterized by the Lindley equation for a discrete-time queue, i.e. q(t+1)=(q(t)-F)/sup +/+a(t), where q(t) is the number of HOL packets at time t, a(t) is the number of new HOL packets at time t, and F is the maximum number of HOL packets that can depart per unit of time. As the total number of HOL packets is bounded in a switch, it places an upper limit on the expected number of HOL packets. Thus, the maximum throughput is the utilization that makes the expected HOL packets equal to the upper limit. For the case with F=1, the expected number of HOL packets can be found via the Pollaczek-Khinchin formula and the maximum throughput can be solved by a quadratic equation as reported in [M.J. Karol et al. (1987), C. Kolias et al. (1996), G. Thomas (1997)]. One of the main contributions of this paper is that we derive a generalized Pollaczek-Khinchin formula for the case F>1. Such a formula is then used for finding the maximum throughput of several input-buffered switches. For the case F/spl Gt/1, numerical computation of the maximum throughput becomes difficult. For large F, we present several bounds and approximations for the throughput. Numerical studies and simulation results confirm that our approximation methods work well.

This paper is about load-balancing packets across multiple paths inside a switch, or across a network. It is motivated by the recent interest in load-balanced switches. Load-balanced switches provide an appealing alternative to crossbars with centralized schedulers. A load-balanced switch has no scheduler, is particularly amenable to optics, and - most relevant here -guarantees 100% throughput. A uniform mesh is used to load-balance packets uniformly across all 2-hop paths in the switch. In this paper we explore whether this particular method of load-balancing is optimal in the sense that it achieves the highest throughput for a given capacity of interconnect. The method we use allows the load-balanced switch to be compared with ring, torus and hypercube interconnects, too. We prove that for a given interconnect capacity, the load-balancing mesh has the maximum throughput. Perhaps surprisingly, we find that the best mesh is slightly non-uniform, or biased, and has a throughput of N/(2N - 1), where N is the number of nodes.

Traditionally, conflict resolution in an input-buffered switch is solved by finding a matching between inputs and outputs per time slot. To do this, a switch not only needs to gather the information of the virtual output queues at the inputs, hut also uses the gathered information to compute a matching. As such, both the communication overhead and the computation overhead make it difficult to scale. Recent works on the two-stage switch architecture in (6|, [7], [12], (8| showed that conflict resolution can be easily solved over time and space without communication and computation overhead. However, the main problem of such a two-stage switch architecture is that packets might be out of sequence. The main objective of this paper is to propose a scalable solution, called the mailbox switch, that solves the out-of-sequence problem in the two-stage switch architecture. The key idea of the mailbox switch is to use a set of symmetric connection patterns to create a feedback path for packet departure times. With the information of packet departure times, the mailbox switch can schedule packets so that they depart in the order of their arrivals. Despite the simplicity of the mailbox switch, we show via both the theoretical models and simulations that the throughput of the mailbox switch can be as high as 75%. With limited resequencing delay, a modified version of the mailbox switch achieves 95% throughput. We also propose a recursive way to construct the switch fabrics for the set of symmetric connection patterns. If the number of inputs, N, is a power of 2, we show that the switch fabric for the mailbox switch can be built with N/2 log/sub 2/ N 2/spl times/2 switches.

In this paper, we develop mathematical theory for recursive construction of first-in first-out (FIFO) optical multiplexers by the combination of (bufferless) crossbar switches and fiber delay lines (SDLs). We show that by cascading multistage SDL units, 2-to-1 multiplexers with a large buffer can be emulated exactly for both the departure process and the loss process from the multiplexer. Such results are extended to the case of n-to-1 multiplexers by introducing a new class of multiplexers, called delayed-loss multiplexers. A delayed-loss multiplexer has the same departure process as an ordinary multiplexer. However, lost packets due to buffer overflow in a multiplexer might be delayed. A key result from our theory is the self-routing n-to-1 multiplexer, where the routing path of a packet through the multistage SDL units can be determined upon its arrival.

It has been studied extensively in the literature how one achieves exact emulation of First In First Out (FIFO) multiplexers for fixed size cells (or packets) using optical crossbar switches and fiber delay lines (SDL). In this paper, we take a step further and propose a new architecture that achieves exact emulation of FIFO multiplexers for variable length bursts. Our architecture consists of two blocks: a cell scheduling block and an FIFO multiplexer for fixed size cells. Both blocks are made of SDL units. The objective of the cell scheduling block is to schedule cells in a burst to the right input at the right time so that cells in the same burst depart contiguously from the multiplexer for fixed size cells. We show that cell scheduling can be done efficiently by keeping track of a single state variable, called the total virtual waiting time in this paper. Moreover, the delay through the cell scheduling block is bounded above by a constant that only depends on the number of inputs and the maximum number of cells in a burst. Such a delay bound provides a limit on the number of fiber delay lines needed in the cell scheduling block.

In this paper, we propose two schemes for the load balanced Birkhoff-von Neumann switches to provide guaranteed rate services. As in [C. S. Chang et al., (2002)], the first scheme is based on an earliest deadline first (EDF) scheduling policy. In such a scheme, we assign every packet of a guaranteed rate flow a targeted departure time that is the departure time from the corresponding work conserving link with capacity equal to the guaranteed rate. By adding a jitter control mechanism in front of the buffer at the second stage and running the EDF policy at the output buffer, we show that the end-to-end delay for every packet of a guaranteed rate flow is bounded by the sum of its targeted departure time and a constant that only depends on the number of flows and the size of the switch. Our second scheme is a frame based scheme as in [I. Keslassy et al., (2002)]. There, time slots are grouped into fix size frames. Packets are placed in appropriate bins (buffers) according to their arrival times and their flows. We show that if the incoming traffic satisfies certain assumptions, then the end-to-end delay for every packet and the size of the central buffers are both bounded by constants that only depend on the size of the switches and the frame size. The second scheme is much simpler than the first one in many aspects: (i) the online complexity is O(1) as there is no need for EDF, (ii) central buffers are finite and thus can be built into a single chip, (iii) connection patterns of the two switch fabrics are changed less frequently, (iv) there is no need for resequencing-and-output buffer after the second stage, and (v) variable length packets may be handled without segmentation and reassembly.

In this paper we study the quality of service of integrated voice and data services in a wireless network. The voice traffic is transmitted in circuit-switched mode and data traffic is transmitted in packet-switched mode. We apply a fluid analysis to study the performance of the data buffer under two handoff schemes and the basic system. From this, analysis, we derive admission controls for voice traffic as well as for data traffic. This analysis also enables us to conclude that the reserved channel scheme not only is more effective in reducing the forced termination probability of handoff calls, it is also more effective in providing the QoS guarantee for the data traffic.

We propose a generalized longest queue first (GLQF) service discipline for ATM networks. We classify sources so that sources in one class have the same cell loss probability requirement. Assume that there are N classes of traffic. Under this discipline, buffer i is assigned a positive number w/sub i/ for the weight of buffer i. The scheduler transmits a cell from the buffer that has the maximal weighted queue length. The advantage of this discipline is that it can adapt to temporary overload quickly. We approximate the queue length distribution by decomposing the system into N single server queues with probabilistic service discipline. Our method is an iterative one, which we prove to be convergent by using stochastic dominance arguments and the coupling technique. For high utilization, we present a heavy traffic limit theorem.

Current designs of high-speed networks assume that all customers are tolerant of some amount of losses. However, it is possible that some applications may require very high reliability, and would be willing to pay more for it, if such a service were available. Motivated by this, we propose a design of a hybrid network which can guarantee zero cell loss probability for type 1 traffic while allowing some losses for type 2 traffic. This paper has three contributions. Our first contribution in this paper is to propose a service discipline (which can be implemented easily on a specific switch architecture) which guarantees zero losses for type 1 traffic. Our second contribution is to propose an algorithm for a scheduling strategy which reduces the number of buffers required at the output pods of the switches to zero for type 1 traffic. Our last contribution is to solve a difficult queueing problem involving service interruptions, which characterizes the performance of type 2 traffic.

In this paper, we analyze a generalized non-preemptive queue with two priority classes. When the server serves the low priority queue, up to l customers are served before the server returns to the high priority queue. We study the embedded Markov chain at departure epochs and obtain the transforms of the queue-length and sojourn-time distributions. From these transforms, it is easy to find the moments.

A threshold-based priority scheme in which a tuning parameter is used to provide adequate quality of service to real-time traffic while providing the best possible service to the non-real-time traffic is proposed. The priority scheme is a generalization of the static priority scheme and the one-limited scheme and is more flexible than both. For this scheme, the authors carry out a queueing analysis and obtain the joint distribution of the queue-lengths. They show by numerical examples how the parameter of this scheme can be tuned dynamically, so that the tuning function can be integrated with the call admission policy.>

In this paper, we examine a problem which is an extension of the limited service in a queueing system with a cyclic server. In this service mechanism, each queue, after receiving service in cycle j, makes a reservation for its service requirement in cycle j + 1. In this paper, we consider symmetric case only, i.e., the arrival rates to all the queues are the same. The main contribution to queueing theory is that we propose an approximation for the queue length and sojourn-time distributions for this discipline. Most approximate studies on cyclic queues, which have been considered before, examine the means only. Our method is an iterative one, which we prove to be convergent by using stochastic dominance arguments. We examine the performance of our algorithm by comparing it to simulations and show that the results are very good.

The transient behavior of a Markov-modulated Poisson arrival queue is studied under overload control. The queue has finite or infinite buffer capacity with multiple exponential servers. A Markov-modulated Poisson process is used to represent an aggregated voice or video packet arrival process in integrated services networks. With overload control, the arrival process is properly altered once the buffer contents exceed a designated level. The probability distribution of queue length as a function of time is obtained. The temporal effect of the overload control is measured in two forms. While in overload, the amount of time for the queue to fall into underload is measured. While in underload, the amount of time for the queue to rise to overload is measured. A proper design of the control will not only reduce the fall time but also increase the rise time. The transient queuing behavior as affected by time stochastic properties of the underlying Markov chain for the arrival process is also explored.>

A hierarchical discrete cosine transform (DCT) coding scheme is described for 135-Mb/s HDTV (high-definition television) transmission in ATM (asynchronous transfer mode) networks. Cell loss due to network congestion and cell misdelivery in the ATM may seriously degrade picture quality. To cope with cell loss, a hierarchical system employing an intrafield 8*4 DCT that segments the coefficients into a main signal and an enhancement signal is proposed. The two signals are separately assembled into cells for transmission over the ATM networks. The cells from the main signal are protected by labeling them with a high priority. The enhancement signal is labeled with a lower priority and is subject to higher cell-loss rates. Considerations for signal segmentation, packet assembling, and effect of cell loss on picture quality are addressed. Computer simulation of the hierarchical DCT system was performed on two HDTV sequences. For comparison, simulations were also applied to nonhierarchical DCT systems with and without cell concealment. The results indicate that the hierarchical system offers very effective protection against cell loss.>

In this paper we will study the video packet loss due to excessive queueing delay in a single statistical multiplexer. Because of the real time nature of video service, packets exceeding a time constraint will be declared lost at the destination. Any packet arriving during the period when the queue length exceeds the threshold determined by the time constrain will be dropped at the destination. Thus, packet losses occur in clusters. We measure the quality of the received pictures by the expected underload period and the expected number of high priority arrivals during an overload period. The former quantity measures the frequency of packet dropping due to excessive delay, while the later is an indicator of the picture area affected. We analyze and compare two system schemes, where the first scheme drops late packets only at the destination and the second one blocks arrivals in front of the multiplexer once the packets exceed the permissible delay. Comparison of the two system schemes based on the two measurements mentioned above indicates that the second scheme is superior to the first one. In order to further improve the video service quality, a simple congestion control based on the dynamics of queue length is proposed. Our analysis shows that the proposed control scheme significantly extends the expected underload period.