The forwarding index of communication networks

A network is defined as an undirected graph and a routing which consists of a collection of simple paths connecting every pair of vertices in the graph. The forwarding index of a network is the maximum number of paths passing through any vertex in the graph. Thus it corresponds to the maximum amount of forwarding done by any node in a communication network with a fixed routing. For a given number of vertices, each having a given degree constraint, we consider the problem of finding networks that minimize the forwarding index. Forwarding indexes are calculated' for cube networks and generalized de Bruijn networks. General bounds are derived which show that de Bruijn networks are asymptotically optimal. Finally, efficient techniques for building large networks with small forwarding indexes out of given component networks are presented and analyzed.     

An all-optical network architecture

A novel photonic network, MATRIX (for multi-wavelength all-optical transparent information exchange), is proposed in this paper. The all-optical multihop network supports wavelength continuity and provides a very high network capacity. Spatial reuse of wavelengths as well as the multiplicity of fibers in optical fiber cables are exploited and enable the interconnection of N² network nodes with merely N wavelengths. The node structure is simple since neither tunable devices nor wavelength converters are required. Packets are routed through the network by photonic fast packet switching as well as by wavelength and experience a maximum hop number of two. Multiple optical paths between any pair of nodes provide a good network survivability     

GEMNET: a generalized, shuffle-exchange-based, regular, scalable,modular, multihop, WDM lightwave network

GEMNET is a generalization of shuffle-exchange networks and it can represent a family of network structures (including ShuffleNet and de Bruijn graph) for an arbitrary number of nodes. GEMNET employs a regular interconnection graph with highly desirable properties such as small nodal degree, simple routing, small diameter, and growth capability (viz. scalability). GEMNET can serve as a logical (virtual), packet-switched, multihop topology which can be employed for constructing the next generation of lightwave networks using wavelength-division multiplexing (WDM). Various properties of GEMNET are studied     

Lightwave networks based on de Bruijn graphs

Proposes de Bruijn graphs as logical topologies for multihop lightwave networks. After deriving bounds on the throughput and delay performance of any logical topology, the authors compute the throughput and delay performance of de Bruijn graphs for two different routing schemes and compare it with their bounds and the performance of shufflenets. For a given maximum nodal in- and out-degree and average number of hops between stations, a logical topology based on a de Bruijn graph can support a larger number of stations than a shufflenet and this number is close to the maximum that can be supported by any topology. The authors also propose de Bruijn graphs as good physical topologies for wavelength routing lightwave networks consisting of all-optical routing nodes interconnected by point-to-point fiber links. The worst-case loss experienced by a transmission is proportional to the maximum number of hops (diameter). For a given maximum nodal in- and out-degree and diameter, a physical topology based on a de Bruijn graph can support a large number of stations using a relatively small number of wavelengths     

一种计算缩减级型广义洗牌网络平均跳距的算法

简单介绍了广义洗牌网络（ＧＳＮ）的结构和分类,着重分析缩减级型ＧＳＮ的平均跳距性能,并提出一种计算平均跳距的算法     

A novel switching architecture for ATM networks

It is known that the flexibility and capacity of asynchronous transfer mode (ATM) networks can meet the bandwidth requirements of multimedia applications. In ATM networks, switching is one of the major bottlenecks of end-to-end communication. We propose using a multiple partitionable circular bus network (MPCBN) as an ATM switch. Connection requests are first transformed into a graph where vertices and edges represent connection requests and conflicts among connection requests, respectively. We then use a graph traversal algorithm to select a maximal set of requests for execution in physically partitioned buses. An approach of using finite projective planes is then used to reduce the number of switch points from O(N²) to O(N √N), where N is the number of ports of a switch. A performance evaluation for both uniform and bursty data sources shows that the approach of using finite projective planes to reduce the number of switch points results in a small increase of cell loss probability     

Low-complexity centralized joint power and admission control in cognitive radio networks

This letter introduces a centralized joint power and admission control algorithm for cognitive radio networks. Its novelty lies in the proposed admission metric. Unlike those in existing algorithms, our metric predetermines the admission order of N secondary users which intend to access the network. This allows us to search a group of admitted secondary users with the bisection method. The proposed algorithm is shown by simulation to achieve a comparable performance to existing algorithms, and the computational complexity is reduced from O(N³) to O(N² log₂ N).     

A time optimal wavelength rerouting algorithm for dynamic trafficin WDM networks

In this paper, we consider wavelength rerouting in wavelength routed wavelength division multiplexed (WDM) networks with circuit switching, wherein lightpaths between source-destination pairs are dynamically established and released in response to a random pattern of arriving connection requests and connection holding times. The wavelength continuity constraint imposed by WDM networks leads to poor blocking performance. Wavelength rerouting is a viable and cost effective mechanism that ran improve the blocking performance by rearranging certain existing lightpaths to accommodate a new request. Recently, a rerouting scheme called “parallel move-to-vacant wavelength retuning (MTV-WR)” with many attractive features such as shorter disruption period and simple switching control, and a polynomial time rerouting algorithm, for this scheme, to minimize the weighted number of rerouted lightpaths have been proposed. This paper presents a time optimal rerouting algorithm for wavelength-routed WDM networks with parallel MTV-WR rerouting scheme. The algorithm requires only O(N²W) time units to minimize the weighted number of existing lightpaths to be rerouted, where N is the number of nodes in the network and W is the number of wavelength channels available on a fiber link. Our algorithm is an improvement over the earlier algorithm proposed in that it requires O(N³W+N²W²) time units, which is not time optimal. The simulation results show that our algorithm improves the blocking performance considerably and only very few lightpaths are required to be rerouted per rerouting. It is also established through simulation that our algorithm is faster than the earlier rerouting algorithm by measuring the time required for processing connection requests for different networks     

Linear complexity of de Bruijn sequences-old and new results

The linear complexity of a de Bruijn sequence is the degree of the shortest linear recursion which generates the sequence. It is well known that the complexity of a binary de Bruijn sequence of length 2ⁿ is bounded below by 2^n-1+n and above by 2^n-1 for n⩾3. We briefly survey the known knowledge in this area. Some new results are also presented, in particular, it is shown that for each interval of length 2^{[log n]+1} in the above range, there exist binary de Bruijn sequences of length 2ⁿ with linear complexity in the interval     

Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience

This paper examines graph-theoretic properties of existing peer-to-peer networks and proposes a new infrastructure based on optimal-diameter de Bruijn graphs. Since generalized de Bruijn graphs exhibit very short average distances and high resilience to node failure, they are well suited for distributed hash tables (DHTs). Using the example of Chord, CAN, and de Bruijn, we study the routing performance, graph expansion, clustering properties, and bisection width of each graph. Having confirmed that de Bruijn graphs offer the best diameter and highest connectivity among the existing peer-to-peer structures, we offer a very simple incremental building process that preserves optimal properties of de Bruijn graphs under uniform user joins/departures. We call the combined peer-to-peer architecture optimal diameter routing infrastructure.     

A new family of space/wavelength/time spread three-dimensionaloptical code for OCDMA networks

A new family of space/wavelength/time spread three-dimensional (3-D) optical codes for optical code-division multiple-access (OCDMA) networks has been proposed. Two types of 3-D codes have been constructed: 3-D codes with single pulse per plane and 3-D codes with multiple pulses per plane. Both codes are based on the prime sequence algorithm and have shown improved performance compared to the previously proposed two-dimensional (2-D) prime code. Effective implementation of the 3-D code has also been proposed. In order to eliminate the requirement of fiber ribbons and multiple star couplers in space/wavelength/time spread 3-D code based optical networks, a wavelength²/time scheme has been suggested, in which the periodic property of an arrayed waveguide grating (AWG) is used. It has been shown that the system performance can be maximized for given resources with a proper choice of the wavelength²/time scheme. Due to the improved performance of the 3-D code and the effective architecture of the wavelength²/time scheme, the feasibility of the OCDMA network is much enhanced     

Routing and wavelength assignment in all-optical networks

Considers routing connections in a reconfigurable optical network using WDM. Each connection between a pair of nodes in the network is assigned a path through the network and a wavelength on that path, such that connections whose paths share a common link in the network are assigned different wavelengths. The authors derive an upper bound on the carried traffic of connections (or equivalently, a lower bound on the blocking probability) for any routing and wavelength assignment (RWA) algorithm in such a network. The bound scales with the number of wavelengths and is achieved asymptotically (when a large number of wavelengths is available) by a fixed RWA algorithm. The bound can be used as a metric against which the performance of different RWA algorithms can be compared for networks of moderate size. The authors illustrate this by comparing the performance of a simple shortest-path RWA (SP-RWA) algorithm via simulation relative to the bound. They also derive a similar bound for optical networks using dynamic wavelength converters, which are equivalent to circuit-switched telephone networks, and compare the two cases. Finally, they quantify the amount of wavelength reuse achievable in large networks using the SP-RWA via simulation as a function of the number of wavelengths, number of edges, and number of nodes for randomly constructed networks as well as de Bruijn networks. They also quantify the difference in wavelength reuse between two different optical node architectures     

Self-firing cell scheduler for input queueing ATM switches

The authors propose a simple cell scheduler for input queueing ATM switches. The proposed self-firing cell scheduler consists of N² processing elements connected by a two dimensional torus network, where each processing element can determine the diagonal by itself in a distributed manner. It allows a simple implementation for high speed ATM switches     

Optimal Unicast Capacity of Random Geometric Graphs: Impact of Multipacket Transmission and Reception

We establish a tight max-flow min-cut theorem for multi-commodity routing in random geometric graphs. We show that, as the number of nodes in the network n tends to infinity, the maximum concurrent flow (MCF) and the minimum cut-sparsity scale as θ(n²r³(n)/k), for a random choice of k = ω(n) source-destination pairs, where n and r(n) are the number of nodes and the communication range in the network respectively. The MCF equals the interference-free capacity of an ad-hoc network. We exploit this fact to develop novel graph theoretic techniques that can be used to deduce tight order bounds on the capacity of ad-hoc networks. We generalize all existing capacity results reported to date by showing that the per-commodity capacity of the network scales as θ(1/r(n)k) for the single-packet reception model suggested by Gupta and Kumar, and as θ(nr(n)/k) for the multiple-packet reception model suggested by others. More importantly, we show that, if the nodes in the network are capable of (perfect) multiple-packet transmission (MPT) and reception (MPR), then it is feasible to achieve the optimal scaling of θ(n²r³(n)/k), despite the presence of interference. In comparison to the Gupta-Kumar model, the realization of MPT and MPR may require the deployment of a large number of antennas at each node or bandwidth expansion. Nevertheless, in stark contrast to the existing literature, our analysis presents the possibility of actually increasing the capacity of ad-hoc networks with n even while the communication range tends to zero!     

Multiaccess mesh (multimesh) networks

This paper introduces the multiaccess mesh (or multimesh) network. Stations are arranged in a two-dimensional (2-D) mesh in which each row and column functions as a conventional linear local-area network (LAN) or metropolitan-area network (MAN) subnetwork. Full connectivity is achieved by enabling stations to merge their row and column subnetworks, under the coordination of a merge control protocol. A two-dimensional token-passing protocol is considered, and a more complex protocol motivated by max-min fairness is also presented. Like conventional LANs and MANs, the multimesh requires no transit routing or store-and-forward buffering. The multimesh is a generalization of the token grid network. Using analysis and simulation, we study the capacity of multimeshes constructed of token rings and slotted rings, under uniform and nonuniform loads. A multimesh can support much higher throughput than conventional linear LAN and MAN networks with the same transmission hardware. Moreover, the multimesh capacity grows with the number of stations, We also present a healing mechanism that ensures full network connectivity regardless of the number of failed stations     

Topologies for wavelength-routing all-optical networks

Three regular meshed topologies are compared in light of their possible use for the implementation of large all-optical wavelength-routing communication networks (or interconnection systems). These systems provide all source-destination pairs with end-to-end transparent channels that are identified through a wavelength and a physical path. The considered topologies are the K-dimensional bidirectional square lattice, the twin shuffle, and the de Bruijn graph. The comparison is based on the maximum and average distance between source and destination (number of traversed nodes), on the degree of connectivity for each node (number of input and output fibers), and on the minimum number of wavelengths in the WDM comb necessary to discriminate all source-destination pairs     

The use of Huygens' equivalence principle for solving 3-D volumeintegral equation of scattering

A three-dimensional (3-D) version of the nested equivalent principle algorithm (NEPAL) is presented. In 3-D, a scatterer is first decomposed into N subscatterers. Then, spherical wave functions are used to represent the scattered field of the subscatterers. Subscatterers are divided into different levels of groups in a nested manner. For example, each group consists of eight subgroups, and each subgroup contains eight sub-subgroups, and so on. For each subgroup, the scattering solution is first solved and the number of subscatterers of the subgroup is then reduced by replacing the interior subscatterers with boundary subscatterers using Huygens' equivalence principle. As a result, when the subgroups are combined to form a higher level group, the group will have a smaller number of subscatterers. This process is repeated for each level, and in the last level, the number of subscatterers is proportional to that of boundary size of the scatterers. This algorithm has a computational complexity of O(N²) in three dimensions for all excitations and has the advantage of solving large scattering problems for multiple excitations. This is in contrast to Gaussian elimination which has a computational complexity of O(N³)     

On a class of predefined wavelet packet bases for efficientrepresentation of electromagnetic integral equations

A general wavelet packet tree is proposed to design predefined wavelet packet (PWP) bases for the efficient representation of electrodynamic integral equations. The wavelet packet decomposition tree is constructed by zooming in along the spectral oscillatory frequency of the free-space Green's function. Numerical results show that for typical two dimensional (2-D) scatterers the number of above-threshold elements in the PWP-based moment matrix is on the order of O(N^1.3) and tends to grow at a rate of O(N·log N) for large-scale problems. Therefore, the complexity of solving the moment equations can be reduced accordingly. Furthermore, it is shown that the elements of the moment matrix based on the PWP bases can be computed directly at approximately the same complexity as the fast wavelet transform approach. Consequently, with on-the-fly thresholding of the matrix elements, the O(N²) memory bottleneck in the formation of the PWP-based moment matrix can be circumvented     

On the support of MSE-optimal, fixed-rate, scalar quantizers

This paper determines how the support regions of optimal and asymptotically optimal fixed-rate scalar quantizers (with respect to mean-squared error) depend on the number of quantization points N and the probability density of the variable being quantized. It shows that for asymptotic optimality it is necessary and sufficient that the support region grow fast enough that the outer (or overload) distortion decreases as o(1/N²). Formulas are derived for the minimal support of asymptotically optimal quantizers for generalized gamma densities, including Gaussian and Laplacian. Interestingly, these turn out to be essentially the same as for the support of optimal fixed-rate uniform scalar quantizers. Heuristic arguments are then used to find closed-form estimates for the support of truly optimal quantizers for generalized gamma densities. These are found to be more accurate than the best prior estimates, as computed by numerical algorithms. They demonstrate that the support of an optimal quantizer is larger than the minimal asymptotically optimal support by a factor depending on the density but not N, and that the outer distortion of optimal quantizers decreases as 1/N³     

Two fast architectures for the direct 2-D discrete wavelettransform

We propose two architectures for the direct two-dimensional (2-D) discrete wavelet transform (DWT). The first one is based on a modified recursive pyramid algorithm (MRPA) and performs a “"nonstandard” decomposition (i.e., Mallat's (1989) tree) of an N×N image in approximately 2N²/3 clock cycles (ccs). This result consistently speeds up other known architectures that commonly need approximately N² ccs. Furthermore, the proposed architecture is simpler than others in terms of hardware complexity. Subsequently, we show how “symmetric”/“anti-symmetric” properties of linear-phase wavelet filter bases can be exploited in order to further reduce the VLSI area. This is used to design a second architecture that provides one processing unit for each level of decomposition (pipelined approach) and performs a decomposition in approximately N²/2 ccs. In many practical cases, even this architecture is simpler than general MRPA-based devices (having only one processing unit)