A burst-level priority scheme for bursty traffic in ATM networks

Statistical gain is achieved in asynchronous transfer mode (ATM) networks by making bursty connections share resources stochastically. To guarantee the quality of service (QOS) of established connections, a call admission control (CAC) scheme is used to limit the number of admitted connections based on their traffic characteristics and QOS requirements. When connections with different QOS requirements share the same resources, the highest QOS requirements would typically be the limiting factor in determining the admissible load at a link. This may lead to connections with low QOS requirements getting better service than they require, leading to an underutilization of the resources. To alleviate this problem, a burst-level priority scheme is proposed. In the proposal, burst of related cells are to be handled in the network on a burst-by-burst basis. Bandwidth is allocated to bursts on-the-fly according to their priorities. This proposal includes a two-level priority CAC scheme for controlling the burst-level blocking rates of independent heterogeneous on–off sources.     

Message latency in hypercubic computer networks with the bursty traffic pattern

An interconnection network is a crucial component of parallel computers because the overall system performance is very sensitive to the latency of messages delivered by the network to communicate among collaborating processors. This paper presents an analytical performance model to calculate message latency in circuit-switched hypercubic networks in the presence of bursty traffic pattern, which is a typical scenario for multimedia applications. A message in circuit switching may need a number of connection attempts before successfully setting up a path from source to destination. The proposed model uses the approach of superposing infinite bursty traffic streams to capture the effective traffic entering the network from a source node, which includes the traffic generated by the source and those due to many connection attempts. Results obtained from simulation experiments confirm that the proposed model exhibits a good degree of accuracy for various network sizes and under different operating conditions.     

An algorithm for architecture partitioning in high-speed networks with bursty traffic

This paper analyzes the performance of a switching architecture. The performance measures include the elapsed time of packet transfer and the waiting time to begin transfer. The architecture is partitioned depending on the type of network used and the expected traffic in the network. Every partition has a switch with a buffer that can absorb surges of bursty traffic within the network partition. The buffer size depends on the type of the network and incoming traffic. The partition size depends on the network bandwidth, network traffic, packet size and buffer size. Examples of different networks are used to show the applications of the model. The results show that the elapsed time of packet switch transfer depends exponentially on the number of partitions in the network.     

An efficient implementation of bypass queue under bursty traffic

In this paper we present a new bypass queue scheme for an input buffered nonblocking packet switch operating under bursty traffic. The proposed scheme uses first-in-first-out (FIFO) queues and is thus more efficient for implementation as compared to other schemes which use first-in-random-out (FIRO) queues. Maximum throughput comparison of the proposed scheme with the conventional scheme shows significant improvement.     

Controlling mean queuing delay under multi-class bursty and correlated traffic

This paper presents an adaptive queue management scheme to maintain queuing delay in a router at a required level based on a comprehensive analytical model under aggregated Internet traffic flows from various traffic classes. The proposed scheme uses a closed-loop feedback control mechanism to constrain the average queuing delay by regulating traffic arrival rate implicitly through a movable queuing threshold. A discrete-time queuing model is developed to derive the relationship between average queuing delays and queuing thresholds based on a traffic model that models aggregated Internet traffic through superposition of N MMBP-2 arrival processes. The queuing threshold is adjusted dynamically with reference to the relationship derived in the analytical model and also feedback of average queuing delay measurement. Packets are dropped dynamically with respect to the changes of queuing threshold and the packet loss events serve as implicit congestion indicators. Matlab is used to perform queuing analysis and simulation. Statistical evaluation is performed to show the efficiency and accuracy of the analytical and simulation results.     

An efficient and orderly implementation of bypass queue under bursty traffic

Sharma and Pinnu proposed an implementation of bypass queue by many FIFOs; unfortunately, the detailed procedure paid little attention to maintaining cell sequence, which is an important feature in ATM network. In this paper, we propose an improved architecture which guarantees cell sequence integrity and describe its related operating procedures.     

Fundamental calculus on generalized stochastically bounded bursty traffic for communication networks

Since many applications and networks do not require or provide deterministic service guarantees, stochastic service guarantee analysis is becoming increasingly important and has attracted a lot of research attention in recent years. For this, several stochastic versions of deterministic traffic models have been proposed in the literature. Unlike previous stochastic models that are based on the traffic amount property of an input process, we present another stochastic model, generalized Stochastically Bounded Burstiness (gSBB), which is based on the virtual backlog property of the input process. We show the advantages of this approach. We study the superposition of gSBB traffic, and set up the input–output relation. Under various service disciplines, we characterize the output process for each source and investigate probabilistic upper bound on delay. Finally, we introduce a stochastic ordering monotonicity property of gSBB. With this property, we show that many well-known traffic models can be readily represented using the proposed gSBB model. These results set up the basis for a network calculus for gSBB traffic.     

Multicast communication in multicomputer networks

Efficient routing of messages is a key to the performance of multicomputers. Multicast communication refers to the delivery of the same message from a source node to an arbitrary number of destination nodes. While multicast communication is highly demanded in many applications, most of the existing multicomputers do not directly support this service; rather it is indirectly supported by multiple one-to-one or broadcast communications, which result in more network traffic and a waste of system resources. The authors study routing evaluation criteria for multicast communication under different switching technologies. Multicast communication in multicomputers is formulated as a graph theoretical problem. Depending on the evaluation criteria and switching technologies, they study three optimal multicast communication problems, which are equivalent to the finding of the following three subgraphs: optimal multicast path, optimal multicast cycle, and minimal Steiner tree, where the interconnection of a multicomputer defines a host graph. They show that all these optimization problems are NP-complete for the popular 2D-mesh and hypercube host graphs. Heuristic multicast algorithms for these routing problems are proposed     

Numerical analysis of the power saving with a bursty traffic model in LTE-Advanced networks

We analyze the power saving operation called Discontinuous Reception (DRX) with a novel bursty packet arrival model in 3GPP Long Term Evolution (LTE)-Advanced networks. Typical analytical studies on the power saving operations in wireless networks have been carried out under the assumption that an expectation of exponentially distributed packet arrival intervals stays unchanged. However, practical packet arrival rate may change depending on time or typical Internet services may incur bursty packet arrivals. In either case, we need to evaluate the performance of the DRX operation. For this purpose, we develop a more realistic traffic arrival model considering packets may arrive in a bursty manner under the DRX operation. We, then, analyze the performance of the DRX operation in terms of power saving efficiency and average queuing delay, respectively. The analytical results are validated via comparisons with simulation results.     

Analytical modelling in 802.11 ad hoc networks

This paper tries to bring together the physical model and protocol model that have been used to characterize interference relationship in an 802.11 ad hoc network. The physical model (known as the SNR model) is generally considered as a reference model for the physical layer behaviour but its application in wireless ad hoc networks is restricted by its complication. On the other hand, the protocol model (known as the unified disk graph) is straightforward but its validity is doubtful. We propose an analytical model for 802.11 ad hoc wireless networks where both the physical and protocol models are improved and modelled accurately by taking into accounts all emitters in the network and circumventing simplistic assumptions where communications are supposed to systematically fail if non-intended emitters fall in proximity of a receiver node. Our model consists in replacing a finite number of nodes by an equivalent continuum - characterized by a density of nodes - and disseminated in the network according to some distribution function. The key feature of the proposed model is that it permits taking into account the effect of interference, the CSMA/CA mechanism and radio propagation aspects in an easy and clear-cut way. All assumptions in the model are assessed with simulation results. Closed form formula of the signal to noise ratio and the throughput capacity per node will be given, corroborated by extensive simulation results in ns-2.     

Deadlock-free message routing in multicomputer networks

The execution of a concurrent computation by a network of processors requires a routing algorithm that is deadlock free. Many routing algorithms proposed for processor networks have the potential of deadlock due to the cyclic topology of the network. In this paper we first formalize the concept of message routing. Next, we show a method by which a deadlock-free routing algorithm can be constructed out of a given routing algorithm. Finally the method is illustrated by constructing deadlock-free routing algorithms for cartesian product processor networks. Peter A.J. Hilbers received the B.S. and M.S. degrees in mathematics, and the Ph.D. degree in computer science from Groningen University, Groningen, The Netherlands, in 1979, 1983, and 1989, respectively. From 1988 to 1989 he was an Assistant Professor with the Department of Computing Science at Groningen University. Currently he is a research engineer in the Department of Mathematics and Systems Engineering at the Koninklijke/Shell-Laboratorium, Amsterdam (Shell Research B.V.). His research intersts are program derivation and correctness, concurrency, and processor networks. Johan J. Lukkien received the B.S. and M.S. degrees in mathematics from Groningen University, Groningen, The Netherlands in 1982 and 1986 respectively. Currently he is a Ph.D. student at the Department of Computing Science, Groningen University. His research area is the construction and verification of concurrent programs.     

Modelling and analysis of pipelined circuit switching in interconnection networks with bursty traffic and hot-spot destinations

Pipelined circuit switching (PCS) that combines the advantages of both circuit switching and wormhole switching is an efficient method for passing messages in interconnection networks. Analytical modelling is a cost-effective tool and plays an important role in achieving a clear understanding of the network performance. However, most of the existing models for PCS are unable to capture the realistic nature of message behaviours generated by real-world applications, which have a significant impact on the design and performance of communication networks. This paper presents a new analytical model for PCS in interconnection networks in the presence of bursty and correlated message arrivals coupled with hot-spot destinations, which can capture the bursty message arrival process and non-uniform distribution of message destinations. Such a traffic pattern has been found in many practical communication environments. The accuracy of the proposed analytical model is validated through extensive simulation experiments. The model is then applied to investigate the effects of the bursty message arrivals and hot-spot destinations on the performance of interconnection networks with PCS.     

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.     

Analytical modelling of cyber-physical systems: applying kinetic gas theory to anomaly detection in networks

Journal of Computer Virology and Hacking Techniques - In connection with anomaly detection in cyber-physical systems, we suggest in this paper a new way of modelling large systems consisting of a...     

Analytical derivation of traffic patterns in cache-coherent shared-memory systems

This paper presents an analytical method to derive the worst-case traffic pattern caused by a task graph mapped to a cache-coherent shared-memory system. Our analysis allows designers to rapidly evaluate the impact of different mappings of tasks to IP cores on the traffic pattern. The accuracy varies with the application’s data sharing pattern, and is around 65% in the average case and 1% in the best case when considering the traffic pattern as a whole. For individual connections, our method produces tight worst-case bandwidths.     

卫星终端突发性业务模型与排队性能分析

随着卫星网络在应急通信中的应用,卫星终端业务的种类不断增加,业务流量可瞬间增大,具有明显的突发性,终端上的数据流量数据呈现出自相似性。利用时间间隔服从重尾分布的ON/OFF叠加模型产生卫星终端的自相似业务流量,并讨论了自相似业务流量输入对卫星终端的丢包率、时延和时延抖动的影响以及对有效带宽的需求。通过仿真,得出了网络终端业务丢包率、时延、时延抖动与系统缓存之间的关系,在此基础上,提出了减少时延、降低丢包率的思路,在带宽和缓存受限的情况下,为信息的高效传输提供了理论依据。     

On the performance of multicomputer interconnection networks

Several researchers have analysed the performance of k-ary n-cubes taking into account channel bandwidth constraints imposed by implementation technology, namely the constant wiring density and pin-out constraints for VLSI and multiple-chip technology respectively. For instance, Dally [IEEE Trans. Comput. 39(6) (1990) 775], Abraham [Issues in the architecture of direct interconnection networks schemes for multiprocessors, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1992], and Agrawal [IEEE Trans. Parallel Distributed Syst. 2(4) (1991) 398] have shown that low-dimensional k-ary n-cubes (known as tori) outperform their high-dimensional counterparts (known as hypercubes) under the constant wiring density constraint. However, Abraham and Agrawal have arrived at an opposite conclusion when they considered the constant pin-out constraint. Most of these analyses have assumed deterministic routing, where a message always uses the same network path between a given pair of nodes. More recent multicomputers have incorporated adaptive routing to improve performance. This paper re-examines the relative performance merits of the torus and hypercube in the context of adaptive routing. Our analysis reveals that the torus manages to exploit its wider channels under light traffic. As traffic increases, however, the hypercube can provide better performance than the torus. Our conclusion under the constant wiring density constraint is different from that of the works mentioned above because adaptive routing enables the hypercube to exploit its richer connectivity to reduce message blocking.     

Deadlock-free adaptive routing in multicomputer networks usingvirtual channels

The use of adaptive routing in a multicomputer interconnection network improves network performance by using all available paths and provides fault tolerance by allowing messages to be routed around failed channels and nodes. Two deadlock-free adaptive routing algorithms are described. Both algorithms allocate virtual channels using a count of the number of dimension reversals a packet has performed to eliminate cycles in resource dependency graphs. The static algorithm eliminates cycles in the network channel dependency graph. The dynamic algorithm improves virtual channel utilization by permitting dependency cycles and instead eliminating cycles in the packet wait-for graph. It is proved that these algorithms are deadlock-free. Experimental measurements of their performance are presented     

A batch arrival queue under randomised multi-vacation policy with unreliable server and repair

This article examines an M^[x]/G/1 queueing system with an unreliable server and a repair, in which the server operates a randomised vacation policy with multiple available vacations. Upon the system being found to be empty, the server immediately takes a vacation. If there is at least one customer found waiting in the queue upon returning from a vacation, the server will be activated for service. Otherwise, if no customers are waiting for service at the end of a vacation, the server either remains idle with probability p or leaves for another vacation with probability 1???p. When one or more customers arrive when the server is idle, the server immediately starts providing service for the arrivals. It is possible that an unpredictable breakdown may occur in the server, in which case a repair time is requested. For such a system, we derive the distributions of several important system characteristics, such as the system size distribution at a random epoch and at a departure epoch, the system size distribution at the busy period initiation epoch, and the distribution of the idle and busy periods. We perform a numerical analysis for changes in the system characteristics, along with changes in specific values of the system parameters. A cost effectiveness maximisation model is constructed to show the benefits of such a queueing system.     

A batch arrival queue with a vacation time under single vacation policy

We consider an M^x/G/1 queueing system with a vacation time under single vacation policy, where the server takes exactly one vacation between two successive busy periods. We derive the steady state queue size distribution at different points in times, as well as the steady state distributions of busy period and unfinished work (backlog) of this model.Scope and purposeThis paper addresses issues of model building of manufacturing systems of job-shop type, where the server takes exactly one vacation after the end of each busy period. This vacation can be utilized as a post processing time after clearing the jobs in the system. To be more realistic, we further assume that the arrivals occur in batches of random size instead of single units and it covers many practical situations. For example in manufacturing systems of job-shop type, each job requires to manufacture more than one unit; in digital communication systems, messages which are transmitted could consist of a random number of packets. These manufacturing systems can be modeled by M^x/G/1 queue with a single vacation policy and this extends the results of Levy and Yechiali, Manage Sci 22 (1975) 202, and Doshi, Queueing Syst 1 (1986) 29.