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.

We propose a theoretical framework forconsistent channel hopping algorithmsto address the multichannel rendezvous problem (MRP) in wireless networks with heterogeneous available channel sets. A channel selection function is called consistent if the selected channel remains unchanged when the available channel set shrinks, provided the selected channel is still available. We show that all consistent channel selection functions are equivalent to the function that always selects the smallest-index channel under appropriate channel relabeling. This leads to a natural representation of a consistent channel hopping algorithm as a sequence of permutations. For the two-user MRP, we characterize rendezvous time slots using a fictitious user and derive tight bounds on the maximum time-to-rendezvous (MTTR) and expected time-to-rendezvous (ETTR). Notably, the ETTR is shown to be the inverse of the Jaccard index when permutations are randomly selected. We also prove that consistent channel hopping algorithms maximize the rendezvous probability. To guarantee a deterministic tight MTTR bound, we propose themodulo algorithm, which uses modular arithmetic with one-cycle permutations and achieves performance comparable to locality-sensitive hashing (LSH)-based algorithms. The framework is extended to multiple users, with novel strategies such as stick-together, spread-out, and a hybrid method that accelerates rendezvous in both synchronous and asynchronous settings. Simulation results confirm the effectiveness and scalability of the proposed algorithms.

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.

The computation of pseudoinverse matrices is critical in various communication and signal processing applications, especially in decoding schemes such as parallel decoding in Irregular Repetition Slotted ALOHA (IRSA) with noise. Traditional methods like singular value decomposition (SVD) are computationally intensive for large, sparse matrices. To address this issue, we propose a novel message-passing algorithm leveraging the dynamic programming principle to efficiently compute the pseudoinverse matrix of acyclic bipartite graphs, guaranteeing exact solutions. For cyclic graphs, we introduce modifications to handle non-orthogonal message propagation and implement a revised convergence criterion, resulting in accurate approximations or exact solutions upon convergence. Numerical results demonstrate that our algorithm converges faster and more reliably compared to Gaussian belief propagation (GaBP), particularly for cyclic SIC-decodable graphs, highlighting its potential in large-scale networked systems.

This paper presents a theoretical framework for consistent channel hopping algorithms to address the multi-channel rendezvous problem (MRP) in wireless networks. We define consistency in channel selection functions as the ability to maintain selection when channels are removed, as long as the selected channel remains available. Key contributions include: (i) showing that all consistent functions are equivalent to selecting the smallest indexed channel through channel relabeling; (ii ) characterizing rendezvous time slots using a fictitious user whose channel set is the union of both users' sets; (iii) deriving a tight Maximum Time-to-Rendezvous (MTTR) bound with one-cycle permutations; and (iv) proving that the Expected Time-to-Rendezvous (ETTR) is the inverse of the Jaccard index using random permutations. We also show that certain state-of-the-art locality-sensitive hashing (LSH) algorithms are consistent and generated by one-cycle permutations. To reduce computational complexity, we propose the modulo algorithm, which uses the modulo operation to generate channel hopping sequences. Simulations confirm that the modulo algorithm achieves competitive ETTR performance compared to LSH-based algorithms.

Recent advances in Large Language Models (LLMs) have demonstrated the emergence of capabilities (learned skills) when the number of system parameters and the size of training data surpass certain thresholds. The exact mechanisms behind such phenomena are not fully understood and remain a topic of active research. Inspired by the skill-text bipartite graph model proposed by Arora and Goyal for modeling semantic languages, we develop a mathematical theory to explain the emergence of learned skills, taking the learning (or training) process into account. Our approach models the learning process for skills in the skill-text bipartite graph as an iterative decoding process in Low-Density Parity Check (LDPC) codes and Irregular Repetition Slotted ALOHA (IRSA). Using density evolution analysis, we demonstrate the emergence of learned skills when the ratio of the number of training texts to the number of skills exceeds a certain threshold. Our analysis also yields a scaling law for testing errors relative to this ratio. Upon completion of the training, the association of learned skills can also be acquired to form a skill association graph. We use site percolation analysis to derive the conditions for the existence of a giant component in the skill association graph. Our analysis can also be extended to the setting with a hierarchy of skills, where a fine-tuned model is built upon a foundation model. It is also applicable to the setting with multiple classes of skills and texts. As an important application, we propose a method for semantic compression and discuss its connections to semantic communication.

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.

The multichannel rendezvous problem is a fundamental problem for neighbor discovery in many IoT applications. The existing works in the literature focus mostly on improving the worst-case performance, and the average-case performance is often not as good as that of the random algorithm. As IoT devices (users) are close to each other, their available channel sets, though they might be different, aresimilar. Using the locality-sensitive hashing (LSH) technique in data mining, we propose channel hopping algorithms that exploit the similarity between the two available channel sets to increase the rendezvous probability. For the synchronous setting, our algorithms have the expected time-to-rendezvous (ETTR) inversely proportional to a well-known similarity measure called the Jaccard index. For the asynchronous setting, we use dimensionality reduction to speed up the rendezvous process. Furthermore, we combine our LSH approach with the Asynchronous Channel Hopping sequence with Maximum rendezvous diversity (MACH) to ensure an upper bound of maximum time-to-rendezvous (MTTR). Our numerical results show that our algorithms can outperform the random algorithm in terms of ETTR.

Due to its simplicity and scalability, the Irregular Repetition Slotted ALOHA (IRSA) system that uses the successive interference cancellation (SIC) technique is a promising solution for uncoordinated multiple access of a massive number of Internet-of-Things (IoT) devices. In this paper, we propose two parallel decoding algorithms for IRSA in an additive white Gaussian noise channel. Our first algorithm is limited to SIC-decoupling matrices that correspond to the SIC decoding process in IRSA. For this, we propose a message-passing algorithm to find the optimal SIC-decoupling matrix that can minimize the accumulated noise power when the induced user-slot bipartite graph of an IRSA system is acyclic. This includes the Contention Resolution Diversity Slotted ALOHA (CRDSA) system that sends exactly two copies for each packet as a special case. Our second algorithm extends the first one by finding the optimal decoupling matrix for CRDSA through an optimal combination of two SIC-decoupling matrices. Using a random graph analysis, we derive the throughput for the two parallel decoding algorithms of CRDSA in a threshold-based decoding model. We then conduct various numerical experiments to illustrate the tradeoffs between sequential decoding with a limited number of iterations and parallel decoding with a predefined signal-to-noise ratio (SNR) threshold. Finally, we demonstrate how to extend our parallel decoding scheme to bipartite graphs with cycles.

The multichannel rendezvous problem is a fundamental problem for neighbor discovery in many IoT applications. The existing works in the literature focus mostly on improving the worst-case performance, and the average-case performance is often not as good as that of the random algorithm. As IoT devices (users) are close to each other, their available channel sets, though they might be different, are similar. Using the locality-sensitive hashing (LSH) technique in data mining, we propose channel hopping algorithms that exploit the similarity between the two available channel sets to increase the rendezvous probability. For the synchronous setting, our algorithms have the expected time-to-rendezvous (ETTR) inversely proportional to a well-known similarity measure called the Jaccard index. For the asynchronous setting, we use dimensionality reduction to speed up the rendezvous process. Our numerical results show that our algorithms can outperform the random algorithm in terms of ETTR.

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.

Network embedding that maps nodes in a graph to vectors in a Euclidean space is a very powerful method to address various tasks on a graph. However, most network embedding algorithms, in particular, graph neural networks (GNNs), are difficult to interpret and do not scale well to handle millions of nodes. In this article, we tackle the problem from a new perspective based on the equivalence of three constrained optimization problems: the network embedding problem, the trace maximization problem of the modularity matrix in a sampled graph, and the matrix factorization problem of the modularity matrix in a sampled graph. The optimal solutions to these three problems are the dominant eigenvectors of the modularity matrix. We propose two unsupervised learning algorithms that belong to a special class of graph convolutional networks (GCNs) for solving these problems: 1) Clustering As Feature Embedding (CAFE) and 2) Sphere. Both algorithms are stable trace maximization algorithms and yield good approximations of dominant eigenvectors. Moreover, there are linear-time implementations for sparse graphs. Various experiments are conducted to evaluate our algorithms and show that our proposed algorithms outperform several baseline methods.

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.

Due to its simplicity and scalability, the Irregular Repetition Slotted ALOHA (IRSA) system that uses the successive interference cancellation (SIC) technique is a promising solution for uncoordinated multiple access of a massive number of Internet-of-Things (IoT) devices. However, the peeling (iterative) decoder for IRSA is sequential in nature, and it might lead to cascading errors due to imperfect SIC. In this paper, we propose a parallel decoding algorithm for IRSA in an Additive White Gaussian Noise (AWGN) channel. Inspired by a recent advance in collision resolution for random access, our approach is to find a SIC-decoupling matrix so that the receiver can perform interference cancellation based on the received signals only. We propose a message-passing algorithm to find the optimal SIC-decoupling matrix when the induced user-slot bipartite graph of an IRSA system is acyclic. This includes the Contention Resolution Diversity Slotted ALOHA (CRDSA) system that sends exactly two copies for each packet. Using a random graph analysis, we derive the throughput for parallel decoding of CRDSA in a threshold-based decoding model. We also conduct various numerical experiments to illustrate the tradeoffs between sequential decoding with a limited number of iterations and parallel decoding with a predefined signal-to-noise ratio (SNR) threshold. Our numerical results show that one can significantly reduce the decoding time and achieve comparable throughput by parallel decoding when the SNR is substantially larger than the decoding threshold.

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 the literature, there are several well-known periodic channel hopping (CH) sequences that can achieve maximum rendezvous diversity in a cognitive radio network (CRN). For a CRN with N channels, it is known that the period of such a CH sequence is at least N2. The asymptotic approximation ratio, defined as the ratio of the period of a CH sequence to the lower bound N2when N → ∞, is still 2.5 for the best known CH sequence in the literature. An open question in the multichannel rendezvous problem is whether it is possible to construct a periodic CH sequence that has the asymptotic approximation ratio of 1. In this paper, we tighten the theoretical gap by proposing CH sequences, called IDEAL-CH, that have the asymptotic approximation ratio of 2. For a weaker requirement that only needs the two users to rendezvous on one commonly available channel in a period, we propose channel hopping sequences, called ORTHO-CH, with period (2 p+1) p, where p is the smallest prime not less than N.

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.

In this paper, we propose a fast rendezvous algorithm for a heterogeneous cognitive radio network (CRN), where each user might have more than one radio. One of the wellknown problems for most multi-radio rendezvous algorithms in the literature is that they are not backward compatible to users with only one radio. To tackle this backward compatibility problem, our approach is a hierarchical construction that groups several time slots into an interval and proposes a novel algorithm to emulate two radios with a single radio in an interval. By doing so, at the interval level, each user behaves as if it had (at least) two radios. For the two-user rendezvous problem in a CRN with commonly labelled channels, the interval length is chosen to be 2M time slots, where = 2 ⌈log2(⌈log2N⌉)⌉ + 10. We show that the maximum time-to-rendezvous (MTTR) of our algorithm is bounded above by 18M⌈n1/m1⌉ . ⌈n2/m2⌉ time slots, where 1 (resp. 2) is the number of available channels to user 1 (resp. 2), and 1 (resp. 2) is the number of radios for user 1 (resp. 2). For the setting that each user is equipped with only one radio and two available channels, our MTTR bound is only and that improves the state-of-the-art bound 16(⌈log2log2N⌉ + 1) in the literature. By conducting extensive simulations, we show that the expected time-to-rendezvous (ETTR) of our algorithm is also better than the two commonly used multi-radio algorithms, JS/Independent and JS/Parallel, in most parameter settings.

The matrix factorization (MF) technique has been widely adopted for solving the rating prediction problem in recommender systems. The MF technique utilizes the latent factor model to obtain static user preferences (user latent vectors) and item characteristics (item latent vectors) based on historical rating data. However, in the real world, user preferences are not static but full of dynamics. Though there are several previous works that addressed this time-varying issue of user preferences, it seems (to the best of our knowledge) that none of them are specifically designed for tracking concept drift in individual user preferences. Motivated by this, we develop a temporal MF approach for tracking concept drift in each individual user latent vector. There are two key innovative steps in our approach: 1) we develop a modified stochastic gradient descent method to learn an individual user latent vector at each time step and 2) by Lasso regression, we learn a linear model for the transition of the individual user latent vectors. We test our method on a synthetic data set and several real data sets. In comparison with the original MF, our experimental results show that our temporal method is able to achieve lower root mean square errors (RMSEs) for both the synthetic and real data sets. One interesting finding is that the performance gain in RMSE is mostly from those users who indeed have concept drift in their user latent vectors at the time of prediction. In particular, for the synthetic data set and the Ciao data set, there are quite a few users with that property and the performance gains for these two data sets are roughly 20% and 5%, respectively.

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.

In this paper, we consider the two-user multichannel rendezvous problem in a cognitive radio network (CRN) and derive tight lower bounds for maximum time-to-rendezvous (MTTR) and maximum conditional time-to-rendezvous (MCTTR) of various channel hopping (CH) schemes under a channel loading constraint. In the symmetric and synchronous setting, we propose a novel Cycle-Adjustable Channel Hopping (CACH) scheme to achieve the MTTR lower bound (when the channel loading is bounded above by 1/u with u being a prime power). Thus, the MTTR lower bound is tight and the CACH scheme is optimal in minimizing MTTR among all the symmetric and synchronous CH schemes under the same channel loading constraint. In the asymmetric setting, we show that the classical wait-for-mommy strategy can be used to achieve the MCTTR lower bound, and thus it is optimal. In the symmetric and asynchronous setting, we also show a hierarchical construction of an asynchronous CH sequence by using two smaller asynchronous CH sequences. To further understand the effect of channel loading to the other performance metrics in a CRN, we perform various computer simulations for various CH schemes. Our simulation results show that the average time-to-rendezvous of CACH is independent of the total number of channels, and it is also robust to the disturbance of primary users.

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 user-item networks, the link prediction problem has received considerable attentions and has many applications (e.g., recommender systems, ranking item popularity) in recent years. Many previous works commonly fail to utilize the dynamic nature of the networks. This paper focuses on dealing with the temporal information and proposes an algorithm to cope with the link prediction problem on bipartite networks. We describe a temporal bipartite projection method that yields a projected item graph, called the temporal projection graph (TPG). Based on the TPG, we propose a scoring function called STEP (Score for TEmporal Prediction) for each user-item pair. STEP leverages the historical behaviors of individual users and the social aggregated behaviors learned from the TPG for the link prediction problem. Furthermore, we use TPG and PageRank to rank the popularity of items. To validate our algorithms, we perform various experiments by using the DBLP author-conference dataset, the Flickr dataset and the Delicious dataset. We show that our results of the link prediction problem for new links are substantially better than other temporal link prediction algorithms. We also find the item rankings generated by our approach match very well with that existed in the real world.

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.

Establishing control channels in a cognitive radio network (CRN) is an important and challenging problem. To cope with the problem of control channel saturation and the problem of channel blocking by primary users, channel hopping (CH) schemes are commonly used in the literature for control channel establishment in CRNs. There are three metrics that are widely used for evaluating the performance of CH schemes: (i) degree of overlapping (the number of distinct rendezvous channels), (ii) worst case time-to-rendezvous (TTR), and (iii) system load. In this paper, we focus on the symmetric and synchronous setting and propose a novel Cycle-Adjustable Channel Hopping (CACH) scheme that outperforms several existing CH schemes, including SSCH and QCH, in terms of the three metrics. The key idea of CACH is to create an additional layer of logical channels on the top of physical channels so that the cycle of channel hopping sequences can be adjusted to optimize system performance. The mathematic tools for our scheme are based on the operations in Galois fields that are more general than the prime number modular arithmetic used in SSCH. We show that CACH is much more general than SSCH and it can achieve the maximum degree of overlapping while allowing the worst case TTR to be adjustable. It is also much better than QCH in terms of reducing system load while keeping the same degree of overlapping and the same worst case TTR. Our simulation results show that CACH outperforms several existing schemes in many other aspects, including throughput, and robustness to the disturbance of PUs.

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.

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.

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.

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.

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.

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.

There has been tremendous progress in understanding how bandwidth is shared by TCP-like connections. By associating each TCP-like connection with a utility function, the bandwidth sharing problem of TCP-like connections can be modeled as a distributed optimization problem for utility functions. However, little is known on how bandwidth is shared by HTTP-like connections through their utility functions at the TCP level. One of the main objectives of this paper is to provide a theory for bandwidth sharing of a large number of HTTP-like connections. Based on certain technical assumptions, we show that there is a utility function at the HTTP level for an HTTP-like connection and such a utility function can be derived from the utility function at the TCP level. The bandwidth is then shared by HTTP-like connections through utility functions at the HTTP level. We also address two possible extensions of the theory: the case with impatient TCP connections and the case with multiple types of requests. With appropriate modification of the utility functions at the HTTP level, we show that the bandwidth is still shared by optimizing their utility functions at the HTTP level for the case with impatient TCP connections. For the case with multiple types of requests, the bandwidth shared at the HTTP level can still be found by solving a unique fixed point limit.

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.

We consider a threshold type control mechanism for dynamic setup/release of /spl lambda/-channels in optical networks. There are two types of costs for the control mechanism: the setup/release cost and the operation cost. For such a control mechanism, there is a corresponding Markov model with high complexity. By state aggregation, we are able to identify a semi-Markov process that is simpler to analyze. Based on the semi-Markov process, we derive the average cost formula for the threshold type control mechanism and carry out several numerical examples to find the optimal thresholds that minimize the average cost.

There has been tremendous progress in understanding how bandwidth is shared by TCP-like connections. By associating each TCP-like connection with a utility function, the bandwidth sharing problem of TCP-like connections can be modelled as a distributed optimization problem for utility functions. However, little is known on how bandwidth is shared by HTTP-like connections through their utility functions at the TCP level. One of the main objectives of this paper is to provide a theory for bandwidth sharing of a large number of HTTP-like connections. Based on certain technical assumptions, we show that there is a utility function at the HTTP level for an HTTP-like connection and such a utility function can be derived from the utility function at the TCP level. The bandwidth is then shared by HTTP-like connections through utility functions at the HTTP level. Moreover, there is a probabilistic interpretation for how the utility function at the HTTP level is related to the utility function at the TCP level. This is done by relating utility functions to large deviation rate functions.

By extending the system theory under the (min, +) algebra to the time-varying setting, we solve the problem of constrained traffic regulation and develop a calculus for dynamic service guarantees. For a constrained traffic-regulation problem with maximum tolerable delay d and maximum buffer size q, the optimal regulator that generates the output traffic conforming to a subadditive envelope f and minimizes the number of discarded packets is a concatenation of the g-clipper with g(t) = min[f(t+ d), f (t)+q] and the maximal f-regulator. The g-clipper is a bufferless device, which optimally drops packets as necessary in order that its output be conformant to an envelope g. The maximal f-regulator is a buffered device that delays packets as necessary in order that its output be conformant to an envelope f. The maximal f-regulator is a linear time-invariant filter with impulse response f, under the (min, +) algebra. To provide dynamic service guarantees in a network, we develop the concept of a dynamic server as a basic network element. Dynamic servers can be joined by concatenation, "filter bank summation," and feedback to form a composite dynamic server. We also show that dynamic service guarantees for multiple input streams sharing a work-conserving link can be achieved by a dynamic service curve earliest deadline scheduling algorithm, if an appropriate admission control is enforced.

Based on a decomposition result by Birkhoff (1946) and von Neumann (1953) for a doubly sub-stochastic matrix, in this letter we propose a scheduling algorithm that is capable of providing guaranteed-rate services for input-buffered crossbar switches. Our guarantees are uniformly good for all nonuniform traffic. The computational complexity to identify the scheduling algorithm is O(N/sup 4.5/) for an N/spl times/N switch. Once the algorithm is identified, its on-line computational complexity is O(log N) and its on-line memory complexity is O(N/sup 3/ log N).

In this paper, we consider the problem of providing delay guarantees in a distributed environment, e.g., a wireless network or a cable network. In a distributed environment, the information of the arrival process is, in general, not available to the network. Due to the lack of such information, traffic regulators and scheduling policies discussed in the literature cannot be directly applied. To cope with the problem, we propose a distributed traffic regulator (DTR) that uses the information of the departure process. Based on such DTRs, we propose the distributed earliest deadline first (DEDF) scheduling policy. For the DEDF scheme, we derive an admission-control criterion and show that the maximum delay can be guaranteed if the criterion is satisfied.

Previously, we proposed a scheduling algorithm that is capable of providing rate guarantees for input-buffered crossbar switches. The algorithm is based on a decomposition result by Birkhoff (1945) and von Neumann (1953) for a doubly substochastic matrix. An input buffered crossbar switch that uses such an algorithm is called the Birkhoff-von Neumann switch in this paper. For the Birkhoff-von Neumann switch, the rate guarantees are uniformly good for all non-uniform traffic, and it does not require framing or internal speedup. Our objective of this paper is to make the Birkhoff-von Neumann switch more complete and practical. We do so by addressing three topics: providing best-effort services in the Birkhoff-von Neumann switch, hardware implementation of the switch fabric, and multistage Birkhoff-von Neumann switches.

We address the parameterization problem for traffic envelopes needed for deterministic traffic regulation and service guarantees. A parameterized function is a good "substitute" for a traffic envelope if (i) the substitute is not smaller than the envelope and (ii) no other functions not smaller than the envelope are smaller than the substitute. Analogous to the least square approximation problem in a vector space, we use projections under the (min, +)-algebra to find a substitute for a traffic envelope. To facilitate the computation of operations under the (min, +)algebra, we develop the concept of ordered orthogonal buses. A substitute for a traffic envelope can be represented by a coordinate vector with respect to an ordered orthogonal basis. Operations under the (min, +)-algebra, including pointwise minimum, convolution, subadditive closure, and pointwise maximum, can then be computed on the domain of coordinate vectors. A substitute and its coordinate vector forms a transform pair, called C-transform in the paper. The C-transform is related to the Legendre (or convex) transform and has many properties such as Parseval's formula.

By extending the filtering theory under the (min, +)-algebra to the time varying setting, we solve the problem of constrained traffic regulation and develop a calculus for dynamic service guarantees. For a constrained traffic regulation problem with maximum tolerable delay d and maximum buffer size q, the optimal regulator that generates the output traffic conforming to a subadditive envelope f and minimizes the number of discarded packets is a concatenation of the g-clipper with g(t)=min[f(t+d), f(t)+q] and the maximal f-regulator. The g-clipper is a bufferless device which optimally drops packets as necessary in order that its output be conformant to an envelope g. The maximal f-regulator is a buffered device that delays packets as necessary in order that its output be conformant to an envelope f. The f-regulator is a linear time invariant filter with impulse response f, under the (min, +)-algebra. To provide dynamic service guarantees in a network, we develop the concept of a dynamic server as a basic network element. Dynamic servers can be joined by concatenation, "filter bank summation" and feedback to form a composite dynamic server, we also show that dynamic service guarantees for multiple input streams sharing a work conserving link can be achieved by a dynamic SCED (service curve earliest deadline) scheduling algorithm, if an appropriate admission control is enforced.

We extend the filtering theory, presented in a previous paper, for deterministic traffic regulation and service guarantees to the matrix setting. Such an extension enables us to model telecommunication networks as linear systems with multiple inputs and multiple outputs under the (min,+)-algebra. Analogous to the scalar setting, there is an associated calculus in the matrix setting, including feedback, concatenation, "filter bank summation", and performance bounds. As an application of the calculus, we derive service guarantees for networks with nested window flow control. In particular, service guarantees for networks with tandem flow control can be solved explicitly by the Gauss elimination.

We develop a filtering theory for deterministic traffic regulation and service guarantees under the (min, +)-algebra. We show that traffic regulators that generate f-upper constrained outputs can be implemented optimally by a linear time-invariant filter with the impulse response f/sub */ under the (min, +)-algebra, where f/sub */ is the subadditive closure defined in the paper. Analogous to the classical filtering theory, there is an associate calculus, including feedback, concatenation, "filter bank summation", and performance bounds. The calculus is also applicable to the concept of service curves that can be used for deriving deterministic service guarantees. Our filtering approach not only yields easier proofs for more general results than those in the literature, but also allows us to design traffic regulators via systematic methods such as concatenation, filter bank summation, linear system realization, and FIR-IIR realization. We illustrate the use of the theory by considering a window flow control problem and a service curve allocation problem.

We develop a filtering theory for deterministic traffic regulators that generate f-constrained outputs. We show that such regulators can be implemented by a linear time invariant filter with the impulse response f under the (min,+)-algebra if the function f is increasing and subadditive. The filtering approach not only yields easier proofs for more general results than those in the literature, but also allows us to design traffic regulators via systematic methods such as concatenation, filter bank summation, linear system realization, and FIR-IIR realization. The theory has many applications, including leaky buckets, traffic regulation for periodic constraint functions, and service curves. In particular, we find a new linear system realization and a new FIR-IIR realization for a concatenation of leaky buckets. Moreover, we find an FIR-IIR realization for traffic regulators with periodic constraint functions. We also show that such regulators, in conjunction with maximum delay guarantee, guarantee shifted-subadditive service curves. Based on this, we provide a couple of rules for service curve allocation among a concatenation of servers.

We study the problem of wireless access to asynchronous transfer modes (ATMs). We consider three classes of ATM sources: constant bit rate (CBR), variable bit rate (VBR), and available bit rate (ABR). We propose a polling scheme with nonpreemptive priority. Under such a scheme, we derive sufficient conditions such that all the CBR sources satisfy their jitter constraints and all the VBR sources satisfy their delay constraints. The remaining bandwidth is used by the ABR sources, for which we adapt a random access scheme proposed by Chen and Lee (1994). For this random access scheme, we derive the throughput-offer load characteristic, and thus the capacity. Based on this, we propose adaptive random access schemes that track the offer load to its optimal value. Our simulations show that our adaptive schemes maintain a high throughput with respect to the whole range of system load.

We use the theory of effective bandwidth for bandwidth allocation in high speed digital networks (ATM), and experiment with simulated Markov traces and actual VBR traces. To approximate the effective bandwidth, we use the four traffic descriptors: average rate, asymptotic variance, peak rate and average burst duration. In our experiments, we find the theory yields good approximations of the queue length distributions for simulated Markov traces and a video conference trace. However, our estimations for asymptotic variance do not converge for some VBR video traces. This implies that some VBR traces might be long-range dependent. Based for the fractional Brownian motion (FBM) model, we revise the theory of effective bandwidth and modify the associated traffic descriptors for such VBR traces. Our experiments show that the FBM model is good in heavy traffic, but does not fit well in light traffic.

The well known problem among most random access protocols in wireless networks is that the throughput drops rapidly in heavy loads. To cope with this problem, one has to control to the load offered to a network. Unlike the traditional backoff policy in Ethernet where backoff occurs after collision, we propose various control schemes based on the new idea of resampling, where carrier sensing ability is used to determine whether a backoff command should be issued or not. We show from various experiments that our schemes are capable of controlling the offer load to the optimal offer load. As a result, the throughputs of these schemes are kept close to the network capacity in heavy loads.

In this paper, we refine the calculus proposed previously by Chang et al. (1994). The new calculus, including network operations for multiplexing, input-output relation, and routing, allows us to compute tighter exponential bounds for the tail distributions of queue lengths in intree networks with routing. In particular, if external arrival processes and routing processes are either Markov arrival processes or autoregressive processes, the stationary queue length at a local node is stochastically bounded above by the sum of a constant and an Erlang random variable. The decay rate of the Erlang random variable is not greater than (in some cases equal to) the decay rate of the tail distribution of the stationary queue length. The number of stages of the Erlang random variable is the number of external arrival processes and routing processes contributing to its queue length. For the single queue case, both the lower and upper-bounds are derived.

The theory of large deviations provides a simple unified basis for statistical mechanics, information theory and queueing theory. The objective of this paper is to use large deviation theory and the Laplace method of integration to provide an simple intuitive overview of the theory of effective bandwidth for high-speed digital networks, especially ATM networks. This includes (1) identification of the appropriate energy function, entropy function and effective bandwidth function of a source, (2) the calculus of the effective bandwidth functions, (3) bandwidth allocation and buffer management, (4) traffic descriptors, and (5) envelope processes and conjugate processes for fast simulation and bounds.>

The authors show the existence of effective bandwidths for multiclass Markov fluids and other types of sources that are used to model ATM traffic. More precisely, it is shown that when such sources share a buffer with deterministic service rate, a constraint on the tail of the buffer occupancy distribution is a linear constraint on the number of sources. That is, for a small loss probability one can assume that each source transmits at a fixed rate called its effective bandwidth. When traffic parameters are known, effective bandwidths can be calculated and may be used to obtain a circuit-switched style call acceptance and routing algorithm for ATM networks. The important feature of the effective bandwidth of a source is that it is a characteristic of that source and the acceptable loss probability only. Thus, the effective bandwidth of a source does not depend on the number of sources sharing the buffer or the model parameters of other types of sources sharing the buffer.>