Performance Analysis of Banyan-Type Multistage Interconnection Networks Under Nonuniform Traffic Pattern

Multistage Interconnection Networks(MINs) have a number of applications in the areas of computer and communications. The most widely researched structure among MINs is the (1)banyan type network. It has several variations such as buffered banyan, batcher-banyan, tandem banyan, recirculating banyan and banyan with contention resolution phase. Analytical performance evaluation is crucial for justifying the merit of the design in different operational conditions. While several analytical models have been proposed for the performance evaluation of MINs, they are mainly for uniform traffics. Even the models for nonuniform traffics have several shortcomings such as they only consider output buffered structure or do not consider blocking conditions.In this paper, the more accurate models than any other ones so far have been proposed for the performance evaluation of multibuffered banyan-type MINs under nonuniform traffic condition is obtained. The accuracy of proposed models are conformed by comparing with the results from simulation.Firstly, single buffer model is developed. Markov chain is used for the analysis. Multibuffer model is obtained from single buffer model. Simulation is performed using Discrete Evenet Simulaton(DES) method. As a results, proposed model proves to be very accurate.     

Performance estimation of banyan semi layer networks with drop resolution mechanism

Multistage interconnection networks (MINs) are a basic class of switch-based network architectures, which are used for constructing scalable parallel computers or for connecting networks. Semi-layer MINs are a special case of MINs. A performance evaluation of semi-layer MINs (using simulation models) is presented in this paper. The configurations of the under study networks apply a conflict drop resolution mechanism. The proposed architecture's performance is studied under uniform traffic conditions and various offered loads, buffer-lengths and MIN sizes. In this paper, the improvements on semi-layer MIN performance, in terms of throughput and latency, are demonstrated quantitatively. These performance measures can be valuable tools for designers of parallel multiprocessor systems and networks, in order to minimize the overall deployment costs and help deliver efficient systems.     

Simulation of dynamic input buffer space in multistage interconnection networks

This paper presents a simulation study of a new dynamic allocation of input buffer space in multistage interconnection networks (MINs). MINs are composed of an interconnected set of switching elements (SEs), connected in a specific topology. The SEs are composed of input and output buffers which are used to store received and forwarded packets, respectively. The performance of these networks depends on the design of these internal buffers and the clock mechanism in synchronous MINs. Various cycle models exist which include the big cycle, small cycle and the smart cycle, each of which provides a more efficient cycle timing. The smart cycle model achieves a superior performance by using output buffers and acknowledgement. However, it suffers from lost and out-of-order packets at high traffic loads. This paper, presents a variation of the smart cycle model, whereby, the input buffer space of each SE is allocated dynamically as a function of traffic load, in order to overcome the above-mentioned drawbacks. A shared buffer pool is provided, which supplies the required input buffer space as required by each SE. Simulation results are presented, which show the required buffer pool for various network sizes and for different network loads. Also, comparison with a static allocation scheme shows an increased network throughput, and the elimination of lost and out-of-order packets at high traffic loads.     

Performance analysis of cut-through buffered banyan networks with finite buffer size

In this paper, we present an analytic model to estimate the performance of cut-through buffered banyan networks with finite buffer size. Two conflict resolution policies are considered in order to resolve conflicts when two packets are destined to the same output link, and their performances are compared. Our analytic model enables analysis of the networks in which buffers are unevenly distributed, i.e., each stage has a different buffer size. It is shown that if buffers are properly distributed in the network, higher throughput and lower delay are possible, although the improvement is considered small. Finally, in order to validate our model, some analytic results are compared to simulation.     

Modelling and performance study of finite-buffered blocking multistage interconnection networks supporting natively 2-class priority routing traffic

In this paper, we model, analyze and evaluate the performance of a 2-class priority architecture for finite-buffered multistage interconnection networks (MINs). The MIN operation modelling is based on a state diagram, which includes the possible MIN states, transitions and conditions under which each transition occurs. Equations expressing state and transition probabilities are subsequently given, providing a formal model for evaluating the MIN's performance. The proposed architecture's performance is subsequently analyzed using simulations; operational parameters, including buffer length, MIN size, offered load and ratios of high priority packets which are varied across experiments to gain insight on how each parameter affects the overall MIN performance. The 2-class priority MIN performance is compared against the performance of single priority MINs, detailing the performance gains and losses for packets of different priorities. Performance is assessed by means of the two most commonly used factors, namely packet throughput and packet delay, while a performance indicator combining both individual factors is introduced, computed and discussed. The findings of this study can be used by network and interconnection system designers in order to deliver efficient systems while minimizing the overall cost. The performance evaluation model can also be applied to other network types, providing the necessary data for network designers to select optimal values for network operation parameters.     

Queueing analysis of buffered slotted multiple access protocols

Much of the literature on the performance evaluation of multiple access protocols has assumed a buffer capacity of one unit. This assumption is not realistic. In practice the buffer capacities used are larger than one unit in order to reduce the probability of packet rejection. This is more crucial for multiple access protocols, which allow moderate to high values of the expected throughput (URN, Random TDMA etc.).In this paper, a model appropriate for the analysis of buffered slotted multiple access schemes is proposed. The method can be applied to several multiple access protocols such as the URN protocol, the ALOHA protocol, Random TDMA etc. The cases of infinite and finite buffer capacity are examined separately but under the same basic assumptions. The analysis is based on the assumption that each user process can be modelled as an M/G/1 queueing system. The proposed method requires a small amount of computation and is characterized by a high speed, a fact that simplifies the buffer's design as well. The solution obtained is extremely accurate and exhibits excellent agreement with simulation results, which corroborate the accuracy of the model. The special case when the buffer capacity is equal to 1 is examined. In that case, the present approach also allows for computation of the packet delay distribution.     

Delay and playout probability trade-off in mesh-based peer-to-peer streaming with delayed buffer map updates

In mesh-based peer-to-peer streaming systems data is distributed among the peers according to local scheduling decisions. The local decisions affect how packets get distributed in the mesh, the probability of duplicates and consequently, the probability of timely data delivery. In this paper we propose an analytic framework that allows the evaluation of scheduling algorithms. We consider four solutions in which scheduling is performed at the forwarding peer, based on the knowledge of the playout buffer content at the neighbors. We evaluate the effectiveness of the solutions in terms of the probability that a peer can play out a packet versus the playback delay, the sensitivity of the solutions to the accuracy of the knowledge of the neighbors’ playout buffer contents, and the scalability of the solutions with respect to the size of the overlay. We also show how the model can be used to evaluate the effects of node arrivals and departures on the overlay’s performance.     

Prediction of user navigation patterns by mining the temporal web usage evolution

Advances in the data mining technologies have enabled the intelligent Web abilities in various applications by utilizing the hidden user behavior patterns discovered from the Web logs. Intelligent methods for discovering and predicting user’s patterns is important in supporting intelligent Web applications like personalized services. Although numerous studies have been done on Web usage mining, few of them consider the temporal evolution characteristic in discovering web user’s patterns. In this paper, we propose a novel data mining algorithm named Temporal N-Gram (TN-Gram) for constructing prediction models of Web user navigation by considering the temporality property in Web usage evolution. Moreover, three kinds of new measures are proposed for evaluating the temporal evolution of navigation patterns under different time periods. Through experimental evaluation on both of real-life and simulated datasets, the proposed TN-Gram model is shown to outperform other approaches like N-gram modeling in terms of prediction precision, in particular when the web user’s navigating behavior changes significantly with temporal evolution.     

A new bootstrap-based forecast evaluation method tested on time series

This article proposes a new forecast quality evaluation method for parametric models. The method takes into account the nonequivalence of forecast errors induced by different accuracies of evaluation of unknown parameters at different time instants and uses nonuniform weighting. Optimal weights values are determined and several numerical algorithms are proposed for their approximate evaluation. The method is tested using time series that describe real economic processes. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 148–158, January–February 2008.     

Document analysis and visualization with zero-inflated poisson

Data visualization is aimed at obtaining a graphic representation of high dimensional information. A data projection over a lower dimensional space is pursued, looking for some structure on the projections. Among the several data projection based methods available, the Generative Topographic Mapping (GTM) has become an important probabilistic framework to model data. The application to document data requires a change in the original (Gaussian) model in order to consider binary or multinomial variables. There have been several modifications on GTM to consider this kind of data, but the resulting latent projections are all scattered on the visualization plane. A document visualization method is proposed in this paper, based on a generative probabilistic model consisting of a mixture of Zero-inflated Poisson distributions. The performance of the method is evaluated in terms of cluster forming for the latent projections with an index based on Fisher’s classifier, and the topology preservation capability is measured with the Sammon’s stress error. A comparison with the GTM implementation with Gaussian, multinomial and Poisson distributions and with a Latent Dirichlet model is presented, observing a greater performance for the proposed method. A graphic presentation of the projections is also provided, showing the advantage of the developed method in terms of visualization and class separation. A detailed analysis of some documents projected on the latent representation showed that most of the documents appearing away from the corresponding cluster could be identified as outliers.     

An analytical model for Network-on-Chip with finite input buffer

An analytical model is proposed for input buffer router architecture Network-on-Chip (NoC) with finite size buffers. The model is developed based on M/G/1/K queuing theory and takes into consideration the restriction of buffer sizes in NoC. It analyzes the packet’s sojourn time in each buffer and calculates the packets average latency in NoC The validity of the model is verified through simulation. By comparing our analytical outcomes to the simulation results, we show that the proposed model successfully captures the performance characteristics of NoC, which provides an efficient performance analysis tool for NoC design.     

时隙间迭代的输入队列交换机Round-Robin调度算法

输入队列因具有良好的可扩展性而广泛应用于高速交换机和路由器中,但输入队列需要精心设计调度算法以获取较好的性能.Round-Robin算法因其简单性和并行性而得到广泛的研究,但现有的Round-Robin算法在突发流量和非均匀流量下的负荷-延迟性能较差.提出了调度决策在时隙间进行迭代的思想,并利用队列长度具有随机性的特点设计了能近似最大匹配的Round-Robin算法--iSLOT.仿真结果表明,iSLOT不仅在均匀流量下是稳定的,在非均匀流量和突发流量下的吞吐率及延迟性能均远好于现有的Round-Robin算法.     

Queuing analysis of shared-buffer switches with control scheme under bursty traffic

Shared-buffer switches have many advantages such as relatively low cell loss rate and good buffer utilization, and they are increasingly favoured in recent VLSI switch designs for ATM. However, their performance degrades dramatically under nonuniform traffic due to the monopolization of the buffer by some favoured cells. To overcome this, restricted types of sharing and hot-spot pushout (HSPO) have been proposed, and the latter has been shown by simulation to perform better in all situations. In this paper we develop an analytical model for performance evaluation of a shared-buffer asynchronous transfer mode (ATM) switch with HSPO under bursty traffic. This analytical model is an improved version of the first model ever developed for this purpose. We balance the relative queues to approximate the effects of pushout, while keeping only four state-variables, and our model gives a good agreement with simulation, for calculating throughput and cell loss.     

IEEE802.11e EDCA饱和吞吐量的性能分析

提出了新的饱和状态下EDCA分析模型。与原有模型相比增加了站点内部竞争冲突和传输机遇两个特性。根据提出的模型,估计了多业务在实施不同的传输机遇情况下的吞吐量性能。仿真结果显示提出的新模型比原模型更加准确。     

Novel Approaches to Probabilistic Neural Networks Through Bagging and Evolutionary Estimating of Prior Probabilities

In this contribution, novel approaches are proposed for the improvement of the performance of Probabilistic Neural Networks as well as the recently proposed Evolutionary Probabilistic Neural Networks. The Evolutionary Probabilistic Neural Network’s matrix of spread parameters is allowed to have different values in each class of neurons, resulting in a more flexible model that fits the data better and Particle Swarm Optimization is also employed for the estimation of the Probabilistic Neural Networks’s prior probabilities of each class. Moreover, the bagging technique is used to create an ensemble of Evolutionary Probabilistic Neural Networks in order to further improve the model’s performance. The above approaches have been applied to several well-known and widely used benchmark problems with promising results.      

Using a heuristic approach to derive a grey-box model through an artificial neural network knowledge extraction technique

Artificial neural networks (ANNs) are primarily used in academia for their ability to model complex nonlinear systems. Though ANNs have been used to solve practical problems in industry, they are not typically used in nonacademic environments because they are not very well understood, complicated to implement, or have the reputation of being a “black-box” model. Few mathematical models exist that outperform ANNs. If a highly accurate model can be constructed, the knowledge should be used to understand and explain relationships in a system. Output surfaces can be analyzed in order to gain additional knowledge about a system being modeled. This paper presents a systematic approach to derive a “grey-box” model from the knowledge obtained from the ANN. A database for an automobile’s gas mileage performance is used as a case study for the proposed methodology. The results show a greater ability to generalize system behavior than other benchmarked methods.     

Analytic models for multistage interconnection networks

Central to all parallel architectures is a switching network which facilitates the communication between a machine's components necessary to support their cooperation. Multistage interconnection networks (MINs) are classified and analytic models are described for both packet-switched and circuit-switched MINs with asynchronous transmission mode. Under strong enough assumptions, packet switching can be modeled by standard queuing methods, hence providing a standard against which to assess approximate models. We describe one such approximate model with much weaker assumptions which is more widely applicable and can be implemented more efficiently. To model circuit switching requires a different approach because of the presence of passive resources, namely multiple links through the MIN which must be held before a message can be transmitted and throughout its transmission. An approximate analysis based upon the recursive structure of a particular MIN topology which yields accurate predictions when compared with simulation is described.     

A new model for context-aware transactions in mobile services

With the ubiquity of handheld devices (such as smart phones and PDAs) and the availability of a wide range of mobile services (such as mobile banking, road traffic updates, and weather forecast), people can nowadays access information and conduct online transactions virtually anywhere and anytime. In such flexible, dynamic but less reliable environment, transaction management technology is believed to provide service reliability and data consistency. Indeed, in mobile and ubiquitous environments where devices as well as services can seamlessly join and leave the ubiquitous network; transaction management can be very helpful during the recovery of services from failure. Current transaction models and commit protocols do not take into account context information. However, in mobile environments, it is imperative to consider context information in the commit of a transaction—i.e., a transaction can be successfully completed if it meets the required context. In this paper, we propose a new model for context-aware transactions and their performance management in mobile environments. Unlike conventional transactions, context-aware transactions adapt to the required context. By context, we mean the service’s context as well as the users’ context that includes users’ needs and preferences. This paper designs and develops the proposed transaction model and evaluates its performance in terms of time and message complexities as well as transaction’s throughput.     

Load-Balancing in Multistage Interconnection Networks under Multiple-Pass Routing

Multistage interconnection networks (MINs) have been widely used in multiprocessor systems, and recently they have been adopted as a way to construct ATM switches for broadband networks. In such systems, the fault-tolerant ability is an important issue. Many researchers have proposed ways to enhance the reliability of MINs, among them a low-cost and efficient way is to use multipass routing schemes in MINs in which thedynamic full access(DFA) property exists. The performance of multipass routing, however, has been largely ignored by researchers in the past. In this paper, we show that multipass routing may degrade the system performance if the communication loads are not well balanced among processors; congestion may appear in some processors and the useful communication bandwidth is badly affected. We propose methods to design DFA routing schemes that are load-balanced and thus can utilize system resources (i.e., the bandwidth) more efficiently.