The performance analysis and implementation of an input accessscheme in a high-speed packet switch

The performance analysis of an input access scheme in a high-speed packet switch for broadband ISDN is presented. In this switch, each input port maintains a separate queue for each of the outputs, thus n ² input queues in an (n×n) switch. Using synchronous operation, at most one packet per input and output will be transferred in any slot. We derive lower and upper bounds for the throughput which show close to optimal performance. The bounds are very tight and approach to unity for switch sizes on the order of a hundred under any traffic load, which is a significant result by itself. Then the mean packet delay is derived and its variance is bounded. A neural network implementation of this input access scheme is given. The energy function of the network, its optimized parameters and the connection matrix are determined. Simulation results of the neural network fall between the theoretical throughput bounds     

Equivalent models for queueing analysis of deterministic service time tree networks

In this correspondence, we analyze feedforward tree networks of queues serving fixed-length packets. Using sample path conservation properties and stochastic coupling techniques, we analyze these systems without making any assumptions about the nature of the underlying input processes. In the case when the server rate is the same for all queues, the exact packet occupancy distribution in any queue of a multistage network is obtained in terms of a reduced two-stage equivalent model. Simple and exact expressions for occupancy mean and variance are derived from this result, and the network is shown to exhibit a natural traffic smoothing property, where preliminary stages act to smooth or improve traffic for downstream nodes. In the case of heterogeneous server rates, a similar type of smoothing is demonstrated, and upper bounds on the backlog distribution are derived. These bounds hold for general input streams and are tighter than currently known bounds for leaky bucket and stochastically bounded bursty traffic.     

Scaling properties of statistical end-to-end bounds in the network calculus

The stochastic network calculus is an evolving new methodology for backlog and delay analysis of networks that can account for statistical multiplexing gain. This paper advances the stochastic network calculus by deriving a network service curve, which expresses the service given to a flow by the network as a whole in terms of a probabilistic bound. The presented network service curve permits the calculation of statistical end-to-end delay and backlog bounds for broad classes of arrival and service distributions. The benefits of the derived service curve are illustrated for the exponentially bounded burstiness (EBB) traffic model. It is shown that end-to-end performance measures computed with a network service curve are bounded by /spl Oscr/(H log H), where H is the number of nodes traversed by a flow. Using currently available techniques, which compute end-to-end bounds by adding single node results, the corresponding performance measures are bounded by /spl Oscr/(H/sup 3/).     

Performance of sufficient conditions for distributed quality-of-service support in wireless networks

Given a wireless network where some pairs of communication links interfere with each other, we study sufficient conditions for determining whether a given set of minimum bandwidth quality-of-service requirements can be satisfied. We are especially interested in algorithms which have low communication overhead and low processing complexity. The interference in the network is modeled using a conflict graph whose vertices correspond to the communication links in the network. Two links are adjacent in this graph if and only if they interfere with each other due to being in the same vicinity and hence cannot be simultaneously active. The problem of scheduling the transmission of the various links is then essentially a fractional, weighted vertex coloring problem, for which upper bounds on the fractional chromatic number are sought using only localized information. We recall some distributed algorithms for this problem, and then assess their worst-case performance. Our results on this fundamental problem imply that for some well known classes of networks and interference models, the performance of these distributed algorithms is within a bounded factor away from that of an optimal, centralized algorithm. The performance bounds are simple expressions in terms of graph invariants. It is seen that the induced star number of a network plays an important role in the design and performance of such networks.     

Optical multistage interconnection networks: new challenges andapproaches

Optical interconnections for communication networks and multiprocessor systems have been studied extensively. A basic element of optical switching networks is a directional coupler with two inputs and two outputs or switching elements (SEs). Depending on the control voltage applied to it, an input optical signal is coupled to either of the two outputs, setting the SE to either the straight or cross state. A class of topologies that can be used to construct optical networks is multistage interconnection networks, which interconnect their inputs and outputs via several stages of SEs. Although optical MINs hold great promise and have demonstrated advantages over their electronic counterparts, they also introduce new challenges such as how to deal with the unique problem of avoiding crosstalk in the SEs. In this article we survey the research carried out, including major challenges encountered and approaches taken, on optical MINs     

Matrix extensions of the filtering theory for deterministic trafficregulation and service guarantees

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     

A note on representation theorems for linear discrete-space systems

The cornerstone of the theory of discrete-space single-input single-output linear systems is the idea that every such system has an input-output mapH that can be represented by a convolution or the familiar generalization of a convolution. This thinking involves an oversight, which, for the case of bounded inputs mapped continuously into bounded outputs, was recently corrected by adding an additional term to the representation. Here we give a more general result that addresses an important larger family of inputs.     

Equivalent permutation capabilities between time-division opticalOmega networks and non-optical extra-stage Omega networks

Because signals carried by two waveguides entering a common switch element would generate crosstalk, a regular N×N multistage interconnection network (MIN) cannot be directly used as an optical switch between N inputs and N outputs in an optical network. A simple solution is to use a 2N×2N cube-type MIN to provide the N×N connections, which needs a much larger hardware cost. A previous research proposed another solution, called the time-domain approach, that divides the N optical inputs into several groups such that crosstalk-free connections can be provided by an N×N regular MIN in several time slots, one for each group. Researchers studied this approach on Omega networks and defined the class set &thetas; to be the set of N-permutations realizable in two time slots on an Omega network. They proved that the size of &thetas; is larger than the size of class Ω, where Ω consists of all N-permutations admissible to a regular N×N (nonoptical) Omega network. This paper first presents an optimal O(NlogN) time algorithm for identifying whether a given permutation belongs to class &thetas; or not. Using this algorithm, this paper then proves an interesting result that the class &thetas; is identical to the class Ω+1 which represents the set of N-permutations admissible to a nonoptical N×N one-extra stage Omega network     

Novel algorithms for the network lifetime problem in wireless settings

One of the major concerns in wireless ad-hoc networks design is energy efficiency. Wireless devices are typically equipped with a limited energy supply sufficient only for a limited amount of time which is reversely proportional to the transmission power of the device. The network lifetime is defined as the time the first device runs out of its initial energy charge. In this paper we study the maximum network lifetime problem for broadcast and data gathering in wireless settings. We provide polynomial time approximation algorithms, with guaranteed performance bounds while considering omnidirectional and unidirectional transmissions. We also consider an extended variant of the maximum lifetime problem, which simultaneously satisfies additional constraints, such as bounded hop-diameter and degree of the routing tree, and minimizing the total energy used in a single transmission. Finally, we evaluate the performance of some of our algorithms through simulations.     

灰色预估神经网络在时滞系统控制中的应用

针对过程控制中由于系统时滞引起的建模和控制方面的困难,提出了利用RBF神经网络对系统时滞进行辨识,采用灰色预估器对系统输出进行预测,并以此替代系统未来的实际输出反馈给输入端,最后利用RBF神经网络控制器对系统进行控制,有效地提高了控制器对时滞变化的自适应性。通过在一个具有时滞的加热炉系统中的应用,说明此方法能够克服不定时滞的影响,使控制目标具有良好的动态和静态性能。     

An efficient transmission scheduling algorithm for awavelength-reusable local lightwave network

Although single-hop star networks based on wave-length division multiplexing (WDM) are attractive owing to their all-optical communication features, the throughput of such lightwave networks is limited due to the small number of available wavelengths. In this paper, a wavelength-reusable local lightwave network that consists of two interconnected WDM star networks is proposed. Based on this architecture, the lower bounds for the problems of minimizing the switching duration and the number of switching modes are derived. A transmission scheduling algorithm for this architecture to efficiently reuse the wavelengths is also proposed. The analytical result shows that the proposed scheduling algorithm always produces solutions close to the lower bounds. Simulation results show that given the same number of users and available wavelengths, the solutions (in terms of the average switching duration and the average number of switching matrices) obtained by the proposed scheduling algorithm on the interconnected WDM networks are better than the optimal solution on a single-star WDM network. In most cases, the performance improvement achieves 20 to 45%     

On the generalization of soft margin algorithms

Generalization bounds depending on the margin of a classifier are a relatively new development. They provide an explanation of the performance of state-of-the-art learning systems such as support vector machines (SVMs) and Adaboost. The difficulty with these bounds has been either their lack of robustness or their looseness. The question of whether the generalization of a classifier can be more tightly bounded in terms of a robust measure of the distribution of margin values has remained open for some time. The paper answers this open question in the affirmative and, furthermore, the analysis leads to bounds that motivate the previously heuristic soft margin SVM algorithms as well as justifying the use of the quadratic loss in neural network training algorithms. The results are extended to give bounds for the probability of failing to achieve a target accuracy in regression prediction, with a statistical analysis of ridge regression and Gaussian processes as a special case. The analysis presented in the paper has also lead to new boosting algorithms described elsewhere.     

Network programming methods for loss networks

This paper describes how some of the insights available from the stochastic analysis of dynamic routing may be incorporated into the classical mathematical programming approach to the design of networks. In particular, we present the results of a number of numerical investigations into network architectures for circuit-switched communication networks. Our investigations use recent theoretical results integrating network flow optimization and Markov decision processes to provide performance bounds for dynamic routing strategies. Following a tutorial introduction of the above mentioned topics we develop a sequence of network examples. Our first examples are familiar ones, such as symmetric fully connected networks and networks with moderate amounts of asymmetry, and we describe how network programming methods complement earlier work on dynamic routing. We then consider a variety of example networks which have a more sparse collection of links. These examples indicate the potential applicability of the methods to a variety of areas, including studies of the design, performance and resilience of future communication networks     

无线ad hoc网络多性能指标基本性能边界

在无线ad hoc网络中,基本性能边界对路由算法和资源分配协议的分析和评价具有重要的意义。对无线ad hoc网络多性能指标基本性能边界进行了研究,包括理论上最优的性能边界和实际可以得到的性能边界。提出了一种稳定状态(steady state)下的网络基本性能指标分析模型。该模型考虑了无线网络广播特性和无线信道干扰,可同时分析多个性能指标,包括：吞吐量、端到端延迟和能量消耗。基于该模型,针对ad hoc网络中最常见的多流—单/双中继拓扑分析基本性能指标,求解多目标优化问题得到基本性能边界。仿真结果验证了模型的准确性,均方根误差小于10-3量级。     

Approximating Fluid Schedules in Crossbar Packet-Switches and Banyan Networks

We consider a problem motivated by the desire to provide flexible, rate-based, quality of service guarantees for packets sent over input queued switches and switch networks. Our focus is solving a type of online traffic scheduling problem, whose input at each time step is a set of desired traffic rates through the switch network. These traffic rates in general cannot be exactly achieved since they assume arbitrarily small fractions of packets can be transmitted at each time step. The goal of the traffic scheduling problem is to closely approximate the given sequence of traffic rates by a sequence of transmissions in which only whole packets are sent. We prove worst-case bounds on the additional buffer use, which we call backlog, that results from using such an approximation. We first consider the NtimesN, input queued, crossbar switch. Our main result is an online packet-scheduling algorithm using no speedup that guarantees backlog at most (N+1)² /4 packets at each input port and each output port. Upper bounds on worst-case backlog have been proved for the case of constant fluid schedules, such as the N²-2N+2 bound of Chang, Chen, and Huang (INFOCOM, 2000). Our main result for the crossbar switch is the first, to our knowledge, to bound backlog in terms of switch size N for arbitrary, time-varying fluid schedules, without using speedup. Our main result for Banyan networks is an exact characterization of the speedup required to maintain bounded backlog, in terms of polytopes derived from the network topology     

Multirate Clos networks

Clos networks are a class of multistage switching network topologies that provide alternate paths between inputs and outputs, making it possible to minimize or eliminate the blocking that can otherwise occur in such networks. In his seminal paper in the Bell System Technical Journal in 1953, Charles Clos showed how these networks could be configured to make them nonblocking and effectively launched the systematic study of switching system performance, a field that has developed a rich technical literature, and continues to be very active and of continuing practical importance. This article describes how Clos' results have been generalized to systems that support connections with varying bandwidth requirements. These generalizations have extended the application of Clos networks well beyond their original technological context and have led to a number of interesting new results, especially in connection with systems that support multicast communication.     

Fault detection and isolation using concatenated wavelet transform variances and discriminant analysis

A method for fault detection and isolation is developed using the concatenated variances of the continuous wavelet transform (CWT) of plant outputs. These concatenated variances are projected onto the principal component space corresponding to the covariance matrix of the concatenated variances. Fisher and quadratic discriminant analyses are then performed in this space to classify the concatenated sample CWT variances of outputs in a given time window. The sample variance is a variance estimator obtained by taking the displacement average of the squared wavelet transforms of the current outputs. This method provides an alternative to the multimodel approach used for fault detection and identification, especially when system inputs are unmeasured stochastic processes, as is assumed in the case of the mechanical system example. The performance of the method is assessed using matrices having the percentage of correct condition identification in the diagonal and the percentages misclassified conditions in the off-diagonal elements. Considerable performance improvements may be obtained due to concatenation-when two or more outputs are available-and to discriminant analysis, as compared with other wavelet variance methods.     

Capacity results for the discrete memoryless network

A discrete memoryless network (DMN) is a memoryless multiterminal channel with discrete inputs and outputs. A sequence of inner bounds to the DMN capacity region is derived by using code trees. Capacity expressions are given for three classes of DMNs: (1) a single-letter expression for a class with a common output, (2) a two-letter expression for a binary-symmetric broadcast channel (BC) with partial feedback, and (3) a finite-letter expression for push-to-talk DMNs. The first result is a consequence of a new capacity outer bound for common output DMNs. The third result demonstrates that the common practice of using a time-sharing random variable does not include all time-sharing possibilities, namely, time sharing of channels. Several techniques for improving the bounds are developed: (1) causally conditioned entropy and directed information simplify the inner bounds, (2) code trellises serve as simple code trees, (3) superposition coding and binning with code trees improves rates. Numerical computations show that the last technique enlarges the best known rate regions for a multiple-access channel (MAC) and a BC, both with feedback. In addition to the rate bounds, a sequence of inner bounds to the DMN reliability function is derived. A numerical example for a two-way channel illustrates the behavior of the error exponents.     

A Computer Program for Approximating System Reliability

A computer program, which provides bounds for system reliability, is described. The algorithms are based on the concepts of success paths and cut sets. A listing of the elements in the system, their predecessors, and the probability of successful operation of each element are the inputs. The outputs are the success paths, the cut sets, and a series of upper and lower reliability bounds; these bounds converge to the reliability which would be calculated if all the terms in the model were evaluated. The algorithm for determining the cuts from the success paths is based on Boolean logic and is relatively simple to understand. Two examples are described, one of which is very simple and the computation can be done by hand, and a second for which there are 55 success paths and 10 cuts and thus machine computation is desirable.     

On the application of forking nodes to product-form queueing networks

We define a ‘forking node’ as a service centre with one input feeding two outputs (each served by its own queue) under the control of an internal path-selection (PS) policy. We assume that both outputs lead to paths through which a packet reaches its final destination. However, the mean downstream delays on the two paths may be different and the PS policy should favour the path with the lower downstream delay. Using simulation, we compare the performance of this system under a variety of random, deterministic, state-dependent PS policies, including threshold-based and join-shortest-queue with bias (JSQ + b). We show that JSQ + b has better performance than the other alternatives. Moreover, if the input process to the forking node is Poisson, standard time series analysis techniques show that its two outputs are very close to being independent Poisson processes. Thus, if we find an accurate and efficient ‘offline’ analytical performance model for JSQ + b forking node, we can extend the applicability of product-form queueing networks to include such forking nodes. For this reason, we present several ways of modelling the performance of a JSQ + b node, using bounds, and compare their results on example networks. We establish a closed-form expression relating the bias b and the delays of the downstream paths. Copyright © 2007 John Wiley & Sons, Ltd.