In this paper, we consider Switched-Delay-Lines (SDL) constructions of optical priority queues by using optical (bufferless) crossbar switches and optical fiber delay lines. In a priority queue, each packet is associated with a priority upon its arrival, the highest-priority packet is sent out from the queue whenever there is a departure request, and the lowest-priority packet is dropped from the queue whenever there is a buffer overflow. Given any system for SDL constructions of optical priority queues, the main research problem is twofold: (i) the design of the routing policy performed by the optical crossbar switches; (ii) the choice of the delays of the optical fiber delay lines. Sarwate and Anantharam are the first to propose a feedback system consisting of an optical$(M+2)\times (M+2)$crossbar switch and M optical fiber delay lines (seeFigure 1inSection I) for SDL constructions of optical priority queues, and they have shown that the largest buffer size that can possibly be achieved by using such a feedback system is$2^{M}$. However, whether this theoretical buffer size$2^{M}$can be achieved or not remains an open research problem. Currently, the best result in the literature was obtained by Cheng et al. and the achieved buffer size is$2^{O(\sqrt {\alpha M})}$, where$\alpha $is a constant that depends on the parameters used in their constructions. In this paper, we consider a discrete-time setting and use a feedback system consisting of an optical crossbar switch and multiple groups of optical first-in first-out (FIFO) multiplexers with delay one (FM1’s) for SDL constructions of optical priority queues under apriority-based routing policy (seeFigure 2inSection I). Our contributions are as follows: (i) We extend and generalize an important class of constructions that contains the optimal constructions in the work of Cheng et al. As a result, we achieve larger buffer sizes and less construction complexities/costs than those by Cheng et al. (ii) We obtain a closed-form expression for the maximum buffer size that is achieved by the optimal construction for the scenario that each group of FM1’s has the same number of FM1’s. (iii) Our constructions possess a salient feature, namely, fault-tolerant capability, that can tolerate the malfunctioning of some FM1’s by using the generalized results obtained in this paper. (iv) We show that our constructions can be implemented by using an optical$(M+2)\times (M+2)$crossbar switch andMoptical fiber delay lines, and achieve a buffer size$2^{O(\sqrt {\alpha M})}$, where$\alpha $is a constant that depends on the parameters used in our constructions and is better, i.e., larger, than that in the work of Cheng et al. in a very broad regime.

One of the main challenges in all-optical packet switching is to design optical buffers for packet conflict resolution. In this paper, we consider a very general type of buffering schemes, namely, optical N-to-K priority queues with time-varying service capacity, where each packet is associated with a unique priority upon its arrival, at time slot t at most c(t) highest-priority packets are sent out from the queue if there are packets in the queue and the service capacity c(t) (0 ≤ c(t) ≤ K) of the queue is not zero, and up to N lowest-priority packets are dumped from the queue if there is a buffer overflow. We extend and generalize our previous constructions [8] of optical priority queues under a priority-based routing policy from single input/output to multiple inputs/outputs. The main contributions of this paper are as follows: (i) The priority queues considered in this paper subsume those considered in all previous works as special cases. (ii) Our queueing model with time-varying service capacity is not only more general but also more realistic than that with fixed service capacity previously studied in the literature. (iii) For the special case that N = K = 1, our constructions in this paper subsume those in [8] as special cases. (iv) For the special case that N = K, we show that an optical N-to-N priority queue with buffer size ${2^{O(\sqrt {M/N} )}}$ (exponential in $\sqrt {M/N} $) can be constructed by using an optical (M+2N)×(M+2N) (bufferless) crossbar switch and M fiber delay lines, which substantially improves the best result O(M3/N2) (polynomial in M/N) in the literature.

The design of optical buffers for packet contention resolution has been recognized as a key issue in all-optical packet switching. One of the most general buffering schemes is priority queues, which includes first-in first-out (FIFO) queues and last-in first-out (LIFO) queues as special cases. In a priority queue, each packet is associated with a unique priority upon its arrival, the packet with thehighestpriority is sent out from the queue whenever there is a departure request and there are packets in the queue, and the packet with thelowestpriority is dumped from the queue whenever there is a buffer overflow. In this paper, we consider the constructions of optical priority queues by using a feedback system consisting of an optical (bufferless) crossbar switch and multiple optical FIFO multiplexers with delay one (FM1’s) in the feedback path for buffering packets and feeding packets back to the switch. Such a feedback system is a generalization of that used in one of the authors’ earlier attempt for the constructions of optical priority queues in Tanget al.(2020). We fix theno-bufferingproblem in Tanget al.(2020) by using optical FM1’s to replace the optical FIFO multiplexers (FM’s) in Tanget al.(2020), which enables us to successfully achieve an exact emulation of a priority queue. We improve the utilization of buffering capacity over that in Tanget al.(2020) by routing packets to the optical FM1’s according to theirbuffering tagsinstead of theirtagsas used in Tanget al.(2020). We also extend and generalize the construction in Tanget al.(2020) and obtain a much larger class of constructions of optical priority queues. Our constructions are made possible by showing that the highest-priority (resp., lowest-priority) packet is always available at the input links of the switch whenever it needs to be routed to the departure (resp., loss) link, and by showing that there is no collision and there is no buffer overflow at any FM1 at any time so that there is no internal packet loss at any time. Our complexity analysis shows that by using a feedback system consisting of an optical$(M+2) \times (M+2)$(bufferless) crossbar switch and$M$fiber delay lines, we can achieve a buffer size of$2^{O(\sqrt {\alpha M})}$, where$\alpha $is a constant that depends on the parameters used in our constructions. Furthermore, we show that the best buffer size that we can achieve is$2^{O(\sqrt {4M/15})}$. Our result (exponential in$\sqrt {M}$) substantially improves on the best known result (polynomial in$M$) in the literature. Our numerical results show that the construction complexity of our constructions is lower than that of the construction in Tanget al.(2020), and the actual saving, in terms of the number of$2\times 2$switches needed, by our constructions could be quite significant even in the tiny-buffer and small-buffer regimes.

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 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.

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.

Recently, constructing optical queues by using optical crossbar Switches and fiber Delay Lines (SDL) has been recognized as a key research issue for all-optical packet switching. In this paper, we focus on SDL constructions of optical FIFO queues. We consider a network element consisting of a 1 × 2 optical crossbar switch, 2k + 1 2 × 2 optical crossbar switches, and 2k + 1 fiber delay lines of lengths ℓ0, ℓ1, ..., ℓ2k. The main contribution of this paper is to provide an explicit control scheme that explicitly specifies the connection patterns of the optical crossbar switches, and obtain a necessary and sufficient condition on the lengths ℓ0, ℓ1, ..., ℓ2k(specifically, the condition in (A1) in Section I) for such a network element to be operated as an optical FIFO queue with buffer equation under our proposed control scheme. The key idea in our proposed control scheme is to operate the network element such that packets stored in the network element satisfy an ordered property and a circularly contiguous property, which lead to the properties required of a FIFO queue.

In this paper, we propose an algorithm that detects overlapping communities in networks (graphs) based on a simple node behavior model. The key idea in the proposed algorithm is to find communities in an agglomerative manner such that every detected community S has the following property: For each node i ∈ S, we have (i) the fraction of nodes in S \ {i} that are neighbors of node i is greater than a given threshold, or (ii) the fraction of neighbors of node i that are in S \ {i} is greater than another given threshold. Through computer simulations of random graphs with built-in overlapping community structure, including LFR benchmark random graphs and Erdös-Rényi type random graphs, we show that our algorithm has excellent performance. Furthermore, we apply our algorithm to several real-world networks and show that the overlapping communities detected by our algorithm are very close to the known communities in these networks.

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.

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.

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.

Wireless spoofing attacks are easy to launch and can significantly impact the performance of networks. Although the identity of a node can be verified through cryptographic authentication, conventional security approaches are not always desirable because of their overhead requirements. In this paper, we propose to use location information, a physical property associated with each node, hard to falsify, and not reliant on cryptography, as the basis for (1) detecting spoofing attacks; (2) determining the number of attackers when multiple adversaries masquerading as a same node identity; and (3) localizing multiple adversaries. We formulate the problem of determining the number of attackers as a multi-class detection problem. We first propose two cluster-based mechanisms to determine the number of attackers. We then develop SILENCE that employs the minimum distance testing of RSS values in addition to cluster analysis and can achieve better accuracy than other methods under study that merely use cluster analysis alone. We further developed an integrated detection and localization system that can localize the positions of multiple attackers. We evaluated our techniques through two testbeds using both an 802.11 (WiFi) network and an 802.15.4 (ZigBee) network in two real office buildings. Our experimental results show that SILENCE can achieve over 90% Hit Rate and Precision when determining the number of attackers. Additionally, our localization results using a representative set of algorithms provide strong evidence of high accuracy of localizing multiple adversaries.

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.

Given a discrete memoryless sourceX, it is well known that the expected codeword length per symbolLn(X) of an optimal prefix code for the extended sourceXnconverges to the source entropy asnapproaches infinity. However, the sequenceLn(X) need not be monotonic inn, which implies that the coding efficiency cannot be increased by simply encoding a larger block of source symbols (unless the block length is appropriately chosen). As the encoding and decoding complexity increases exponentially with the block length, from a practical perspective it is useful to know when an increase in the block length guarantees a decrease in the expected codeword length per symbol. While this paper does not provide a complete answer to that question, we give some properties ofLn(X) and obtain for eachnges1 and nondyadicp1n(p1is the probability of the most likely source symbol) an integerk* for whichLkn(X)Ln(X) for allkgesk*, implying that the coding efficiency of encoding blocks of lengthknis higher than that of encoding blocks of lengthnfor allkgesk*. This question is simpler in part becauseLkn(X)lesLn(X) is guaranteed for allnges1 andkges1, but our results distinguish scenarios where increasing the multiplicative factor guarantees strict improvement. These results extend and generalize those by Montgomery and Kumar.

It is known that the worst case near-far resistance of optimum multiuser detectors for asynchronous Gaussian multiple-access channels can be expressed in terms of a class of block-tridiagonal matrices, and the minimal eigenvalues of such a class of block-tridiagonal matrices serve as a good measure of the worst case near-far resistance. In this paper, we focus on the two-user scenario where each block-tridiagonal matrix under consideration is a tridiagonal matrix. We derive closed-form expressions for the minimal eigenvalues of such a class of tridiagonal matrices in terms of the largest real solution of a trigonometric equation in[0,pi]. We also obtain lower bounds and upper bounds on the minimal eigenvalues which improve on previously known results in the literature.

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.

Recently, there has been a lot of attention in the literature on a less well-known aspect of queueing theory, the theory of the constructions of queues. Such an interest originates mainly from optical packet switching due to the lack of optical buffers. These constructions of optical queues are based on optical switches and fiber delay lines (SDL). Theoretical studies in the SDL constructions have been recently reported for the constructions of various types of optical queues, including output-buffered switches, first-in-first-out (FIFO) multiplexers, FIFO queues, last-in-first-out (LIFO) queues, priority queues, linear compressors, nonovertaking delay lines, and flexible delay lines. In this paper, we consider the constructions of optical 2-to-1 FIFO multiplexers with a limited number of recirculations through the fibers, which is a very important practical feasibility issue on the constructions of optical queues that has not been theoretically addressed before. Specifically, we consider the constructions of optical 2-to-1 FIFO multiplexers with buffer size at least 2n-1 by using a feedback system consisting of an (M+2)times(M+2) optical crossbar switch and M fiber delay lines under a simple packet routing policy and under the limitation that each packet can be recirculated through the M fibers at most k times. In one of our previous works, we have shown that this can be done by using n fibers with delays 1, 2, 22,..., 2n-1if there is no limitation on the number of recirculations through the fibers. The main idea in our constructions in this paper is to use extra fibers (other than the n fibers with delays 1, 2, 22,..., 2n-1) with appropriately chosen delays to emulate the effective delays of the concatenations of some of the n fibers with delays 1, 2, 22,..., 2n-1so that the number of recirculations is reduced by so doing. It turns out that the number of fibers needed and their delays are determined based on a dynamic programming formulation obtained through a divide-and-conquer approach. We obtain a closed-form expression for the number of fibers needed in our constructions, and show that there are (rk) possible choices for the delays of the required fibers, where r is the remainder of n divided by k. Furthermore, we give the optimal choice of the fiber delays that achieves the maximum buffer size among the (rk) possible choices. Finally, we show that when n=k or nges2k, such an optimal choice also requires the minimum total fiber length among the (rk) possible choices.

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.

For a discrete memoryless source X, it is well known that the expected codeword length per symbol Ln(X) of an optimal prefix code for the extended source Xn converges to the source entropy. However, the sequence Ln(X) need not be nonincreasing. As the encoding and decoding complexity increases exponentially with the block length, from a practical perspective it is both important and of interest to know when we can have a decrease in the expected codeword length per symbol by increasing the block length.

Recent advances in the literature have shown that there exist systematic switched delay lines (SDL) construction methods for various types of optical buffers. 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 optical 2-to-1 first-in first out (FIFO) multiplexers. We consider a feedback system consisting of an (M+2)times(M+2) optical crossbar switch andMfiber delay lines with delaysd1,d2,..,dM. TheseMfiber delay lines are connected fromMoutputs of the crossbar switch back toMinputs of the switch, leaving two inputs (resp., two outputs) of the switch for the two inputs (resp., two outputs) of the 2-to-1 multiplexer. In one of our previous papers, we have shown a necessary and sufficient condition on the fiber delaysd1,d2,..dM(specifically, the condition in (A1) given in Section I) for such a feedback system to be operated as a 2-to-1 FIFO multiplexer with bufferi=1Mdiunder a simple packet routing policy. In this paper, we obtain another condition on the fiber delaysd1,d2,..dM(specifically, the condition in (A2) given in Section II-A) such that the feedback system can still be operated as a 2-to-1 FIFO multiplexer with bufferi=1M-Fdieven after up toFof the fibers are broken, where 0 lesFlesM-1. We show that such a choice given by (A2) is better than a straightforward choice of the fiber delays. The idea behind the choice given by (A2) is to compose fibers with larger delays by using fibers with smaller delays so that the condition in (A1) is still satisfied even after up toFof the fibers are broken. Furthermore, we obtain the optimal choice (in the sense of maximizing the buffer size) among all of the choices given by (A2). In order to compare various choices of the fiber delays, we introduce the construction efficiency for a construction of a 2-to-1 FIFO multiplexer. By specifying a special choice of the fiber delays that satisfy the condition in (A2), we are able to derive a lower bound on the asymptotic construction efficiency for the optimal choice of the fiber delays. Our results show that the (asymptotic) construction efficiency for the optimal choice is much better than that for the straightforward choice of the fiber delays.

In this correspondence, we consider one-to-one encodings for a discrete memoryless source, which are "one-shot" encodings associating a distinct codeword with each source symbol. Such encodings could be employed when only a single source symbol rather than a sequence of source symbols needs to be transmitted. For example, such a situation can arise when the last message must be acknowledged before the next message can be transmitted. We consider two slightly different types of one-to-one encodings (depending on whether the empty codeword is used or not) and obtain lower and upper bounds on the expected length of optimal one-to-one codes. We first give an extension of a known tight lower bound on the expected length of optimal one-to-one codes for the case that the the size of the source alphabet is finite and partial information about the source symbol probabilities is available. As expected, our lower bound is no less than the previously known lower bound obtained without side information about the source symbol probabilities. We then consider the case that the source entropy is available and derive arbitrarily tight lower bounds on the expected length of optimal one-to-one codes. We also derive arbitrarily tight lower bounds for the case that the source entropy and the probability of the most likely source symbol are available. Finally, given that the probability of the most likely source symbol is available, we obtain an upper bound on the expected length of optimal one-to-one codes. Our upper bound is tighter than the best upper bound known in the literature

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

In this paper; we consider one-to-one encodings for a discrete memoryless source, which are "one-shot" encodings associating a distinct codeword with each source symbol. Such encodings could be employed when only a single source symbol rather than a sequence of source symbols needs to be transmitted. We consider two slightly different types of one-to-one encodings depending on whether the empty codeword is used or not. Given that the probability of the most likely source symbol is available, we provide several new lower and upper bounds on the expected length of optimal one-to-one codes.

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 this paper, we consider an exponentially weighted average codeword length introduced by Campbell as a performance measure for source codes. This criterion assumes that the cost is an exponential function of the codeword length and includes the usual expected codeword length criterion as a special case. Such situations could arise when the cost for encoding and decoding is significant, or if the buffer overflow caused by long codewords is a serious issue. The source codes under consideration are one-to-one encodings for a discrete memoryless source, which are "one-shot" encodings associating a distinct codeword with each source symbol. Such encodings could be employed when only a single source symbol rather than a sequence of source symbols needs to be transmitted. For example, such a situation can arise when the last message must be acknowledged before the next message can be transmitted. We consider two slightly different types of one-to-one encodings (depending on whether the empty codeword is used or not) and obtain several new upper bounds on Campbell's average length of optimal one-to-one codes when the probability of the most likely source symbol is available.

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).

We consider a hybrid selection/maximal-ratio combining (HS/MRC) diversity system and assume independent Nakagami fading on the diversity branches with unequal fading parameters and unequal signal-to-noise ratios (SNR's). We use the virtual branch technique and two series expressions for the characteristic function (CF) of the sum of independent gamma random variables to derive closed-form expressions for CF, the probability density function (PDF), the mean, and the variance of the instantaneous combiner output SNR. We also obtain closed-form expressions for the outage probability, the channel capacity under different transmission policies, and the average symbol error probability (SEP) for a general class of M-ary modulation schemes (including MPSK, MQAM, BFSK, and MSK) with coherent detection. Our approach provides a canonical structure for the closed-form expressions, which are the closed-form expressions for a single-branch system in different Nakagami fading environments.

In this paper, we provide a unified analysis of average symbol error probability (SEP) for a diversity system over generalized gamma fading channels, which is a generalization of Rayleigh, Nakagami, and Ricean fading channels. We consider independent generalized gamma fading on the diversity branches and derive different closed-form expressions of the average SEP for a general class of M-ary modulation schemes (including MPSK, MQAM, BFSK, and MSK) with maximal-ratio combining (MRC) and for M-ary orthogonal FSK with postdetection equal-gain combining (EGC). The results apply to the situations where some branches are Nakagami faded and the others are Ricean faded. Furthermore, the results are applied to obtain closed-form expressions of the average SEP for the cases of arbitrarily correlated and not necessarily identically distributed Nakagami and Ricean faded branches with the help of virtual branch technique by Win et al. Our approach provides a canonical structure for the average SEP as a weighted sum of elementary closed-form expressions, which are the closed-form expressions for the average SEP of a diversity system in independent and identically distributed (i.i.d.) Nakagami fading environments.

The generalized Hamming weights introduced by Wei (1991) have been shown to be fundamental descriptive parameters of a linear block code. They have been found to be useful in certain cryptographic applications and in the studies of minimal trellis diagrams of linear block codes. In this correspondence, we determine the first few and the last few generalized Hamming weights of binary primitive BCH codes with minimum distance one less than a power of two, of their extensions, and of the duals of both.

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.