As the Internet grows, various types of traffic, such as voice, video and data, are transmitted. Therefore, the Internet should provide the Quality of Service (QoS) required by each type of traffic as well as end-to-end connectivity, and routing decisions should be based on the utilization of links/routers and/or the application types of traffic. This kind of routing is called Traffic Engineering (TE), and its objective is to improve such performance factors as flow loss probability for users and the utilization of links for networks, simultaneously. Some studies claim that the Multi-Protocol Label Switching (MPLS) technique can easily implement TE. So far, some experimental results show that TE is effective on a MPLS network; however, its performance has not been theoretically and quantitatively analyzed. Thus, in this paper, we will investigate the basic and preliminary performance of MPLS networks with TE by analyzing flow loss probability and Smoothness index of link utilization in the queueing system.

This paper proposes an efficient fair queuing algorithm, called Medium Starting Potential Fair Queuing (MSPFQ), which has O(1) complexity for the virtual time computation while it has delay and fairness properties similar to Starting-Potential Fair Queueing (SPFQ). The key idea of MSPFQ algorithm is that it recalibrates the system virtual time to the medium value of the minimum possible virtual start times of HOL packets in each backlogged session. We show that MSPFQ belongs to the class of Rate-Proportional Server (RPS). In addition, we analytically prove that our algorithm has good delay and fairness properties.

This paper studies the local Poisson property of aggregated IP traffic. First, it describes the scenario where IP traffic presents a Poisson-like characteristic within some limited range of time scales when packets from independent traffic streams are aggregated. Each of the independent traffic streams corresponds to a series of correlated IP packets such as those of a transport connection. Since the Poisson-like characteristic is observed only within some limited range of time scales, we call this characteristic the local Poisson property. The limited range of time scales of the local Poisson property can be estimated from a network configuration and characteristics of transport connections. Second, based on these observations, we seek the possibility to apply an ordinary Poisson process to evaluation of the packet loss probability in IP networks. The analytical investigation, where IP traffic is modeled by a superposition of independent branching Poisson processes that presents the local Poisson property, suggests that the packet loss probability can be estimated by a finite-buffer queue with a Poisson process when the buffer size is within a certain range. The investigation is verified by simulations. These findings expand the applicability of conventional Poisson-based approaches to IP network design issues.

In provisioning packet data service on wireless cellular networks, a scheme of altering connection status between mobile and base stations appeared with an effort to utilize resource during idle periods. A critical issue in such scheme of sojourn and transition on the connection states is to determine a maximum time to sojourn at each state. An excessive sojourn time leads to resource invasion by inactive stations, while a high cost of re-establishing connection components is imposed by an insufficient sojourn. Thus, the maximum sojourn times must be optimized in consideration of the two conflicting arguments. In this paper, we consider a generic scheme of connection status transitions and formulate a decision problem to determine maximum sojourn times by introducing a loss function which reflects the cost of connection re-establishment as well as the loss induced by inefficient resource usage. From the decision problem, we derive an optimal value for maximum sojourn time, identified as Bayes rule, by observing the delay time of last packet to have posterior information about the length of upcoming idle period. From the analytical results, we show the Bayes sojourn time is trivial under a constraint on loss coefficients when packet arrivals follow a Poisson process.

In this paper, we propose a packet-scheduling algorithm, called the Class-level Service Lagging (CSL) algorithm, that guarantees multiple delay bounds for multi-class traffic in packet networks. We derive the associated schedulability test conditions, which are used to determine call admission. We first introduce a novel implementation of priority control, which has a conventional and simple form. We show how the efforts to confirm the logical validity of that implementation are managed to reach the definition of the CSL algorithm. The priority control is realized by imposing class-level unfairness in service provisioning, while the underlying service mechanism is carried out using the notion of fair queueing. The adoption of fair queueing allows the capability to maintain the service quality of the well-behaving traffic even in the presence of misbehaving traffic. We call this the firewall property. Simulation results demonstrate the superiority of the CSL algorithm in both priority control and firewall functionality. We also describe how the CSL algorithm is implementable with a computational complexity of O(1). Those features as well as the enhanced scalability, which results from the class-level approach, confirm the adequacy of the CSL algorithm for the fast packet networks.

This letter presents a new approach for obtaining the expected waiting time for packets under the drop-head (also called a drop-from-front) scheme for buffer management. The results show that the drop-head scheme is more effective in reducing queueing delays than the drop-tail scheme.

Dual-Banyan is a buffered banyan asynchronous transfer mode (ATM) switch encompassing bifurcated queueing as its buffering strategy. This paper describes an efficient analytical model, based on iterative calculations, for performance evaluation of the Dual-Banyan switch under uniform and non-uniform traffic patterns with much less time than the simulation. The efficiency of the given model is verified through a comparison with simulation results. Another benefit of our model is the possibility to adopt it in any non-uniform incoming traffic. At last, we compare performance of Dual-Banyan switch and Input Buffer Banyan, and show that Dual-Banyan switch has significant better performance levels.

In this paper, we propose a new fair queueing algorithm to improve cell delay variation (CDV) for real-time service categories and to make efficient use of system resources for multimedia traffic in high speed ATM networks. The proposed algorithm is called the delay variation-based fair queueing (DVFQ) algorithm, which is based on per-VC queueing to improve CDV and fairness for each VC of real-time services such as CBR and rt-VBR. In DVFQ algorithm, we define two fairness indexes, which indicate the degree of the fairness of CDV at the rate of each VC, and the degree of impartially sharing the bandwidth between the scheduled cells for each VC. The simulation results for both heavily and lightly loaded conditions show that DVFQ algorithm provides better performances in terms of the CDV, the CDV fairness, and the service fairness than those of FCFS for real-time service.

We consider the services of broadcasting short messages via forward signaling channels in wireless cellular networks. In the provision of such services, the negative effect of short messages on the delivery of delay-sensitive control messages must be restricted. On the other hand, it is desirable to accommodate the users' demands for service enhancements involving timeliness and informativeness. As a way to resolve such conflicting arguments, we present a generic scheme in which a short message may be rejected or removed according to the buffer occupancy at the base station and is split into a number of segments for the transmission across a forward signaling channel. However, the rejection, removal and segmentation exhibit a trade-off among several facets of service enhancements. Thus, for a quantitative evaluation of the scheme and efficient optimization of design parameters, we develop an analytical method to calculate the moments of delay times experienced by control and short messages at a base station. Using the analytical method, we investigate the delay and loss performance of control and short messages with respect to the message load and short message length.

For several years, more and more people are joining the Internet and various kind of packets (so called transaction-, block-, and stream-types) have been transmitted in the same network, so that poor network conditions cause loss of the stream-type data packets, such as voices, which request smaller transmission delay time than others. We consider a switching node (router) in a network as an N-series M/G/1-type queueing model and have mainly evaluated the fluctuation of packet delay time and end-to-end delay time, using the two moments matching method with initial value, then define the delay jitter D of a network which consists of jointed N switching nodes. It is clarified that this network is not suitable for voice packets transmission media without measures.

We propose an efficient, low cost, multicast ATM switch which is fair to all inputs. The switch consists of a novel copy network which creates unicast packets in a fair manner, followed by a network that routes packets to their correct Address Translation Tables (ATT's) and ultimately a unicast routing network which ensures sequencing. The copy and routing networks are based on deflection routing. We show that our switch requires O(log N) stages and can be designed for any arbitrarily low level of packet loss. The theoretical results are backed up by simulations. Switching elements in both the copying and routing networks have O(1) bit complexity, making the overall bit level hardware complexity of the network O(N log N). The latency of the switch is proportional to the number of stages O(log N). Unlike other existing copy networks, our copy network drops packets in a fair manner and hence can provide quality of service (QoS) support. The switch is output queued and allows the delivery of multiple packets to the same destination during a time slot.

WFQ (Weighted Fair Queueing) is an ideal scheduling algorithm in terms of delay and fairness. However, timestamp computation complexity makes the implementation difficult. In this paper we propose an efficient and simple fair queueing algorithm, called Emulated Weighted Fair Queueing (EWFQ), which has O(1) complexity for the virtual time computation while it almost perfectly emulates the delay and fairness properties of WFQ. The key idea of EWFQ is that it calibrates the system virtual time only at the end of each packet transmission, while it calculates the system virtual time for a newly arrived packet by employing a linear approximation. By doing so, EWFQ has a rate-proportional property. EWFQ can be implemented in a router for supporting the differential and integrated services.

In the past, a number of scheduling algorithms that approximate GPS, such as WFQ, have been proposed and have received much attention. This class of algorithms provides per-flow QoS guarantees in terms of the bounded delay and minimum bandwidth guarantee. However, with O(log N) computational cost for each new arrival scheduling, where N is the number of backlogged flows, these algorithms are expensive to implement (e.g., in terms of scalability). Moreover, none of them addresses the issues of delay distribution and jitter. In this paper, we propose a new traffic scheduling discipline called Jitter Control Frame-based Queueing (JCFQ) that provides an upper bound for delay jitter in the case of rate-controlled connections, such as packet video streams and IP telephony, while guaranteeing bounded delay and worst-case fair weighted fairness, such as in the WF2Q algorithm, but with O(1) complexity in selecting the next packet to serve, assuming that the number of flows is fixed. Three different algorithms for slot or service order assignment between flows are proposed: Earliest Jitter Deadline First (EJDF), Rate Monotonic (RM) and Maximum Jitter First (MJF). In these algorithms, delay jitter is formulated into the virtual finish time calculation. We compare the fairness, delay and jitter performance of the JCFQ with that of the MJF algorithm with WF2Q via simulation. The results show that with proper choice of the slot size, JCFQ can achieve better flow isolation in delay distribution than can WF2Q.

Recently, the Guaranteed Frame Rate (GFR) service was proposed as a new service category of ATM to support non-realtime data applications and to provide the minimum rate guarantee. To keep the simplicity of GFR as much as possible and overcome defects of FIFO-based mechanisms, we propose a FIFO-based algorithm extending DFBA one to improve the fairness and provide the minimum rate guarantee for a wider range of Minimum Cell Rate (MCR). The key idea is controlling the number of CLP1 cells which are occupying more buffer space than the fair share even when the queue length is below Low Buffer Occupancy (LBO).

A new scheduling algorithm called the Adaptive Weighted Round Robin with Delay Tolerance (AWRR/DT) is presented. This scheme can adapt to the traffic fluctuation of networks with a small processing burden. The proposed scheme incorporates a cell discarding method to reduce the QoS degradation in high-loaded (or congested) period. Simulation results show that the proposed scheme can reduce the average delay of the non-real-time (NRT) class, especially in high-loaded conditions, while maintaining the QoS of real-time (RT) classes. Our scheme with the discarding method can also reduce both the mean waiting time and cell loss ratio of RT classes.

This paper proposes a new scheduling algorithm named TWFQ (Two-phased Weighted Fair Queueing) not only to maintain the fair utilization of available bandwidth but also to improve the performance of CDV and cell loss probability. The TWFQ algorithm makes use of the cell inter-arrival time of each connection for determining the cell service order among connections, which contributes to get a small CDV. To achieve low cell loss probability, the TWFQ allows connections, which suffer from the more bursty input traffic, to send the cell with more opportunities by using two scheduling phases. Through simulations, we show that the proposed algorithm achieves good performance in terms of CDV and cell loss probability, while other performance criteria are preserved in an acceptable level.

Medium access control (MAC) protocol is one of the key components for providing quality of service (QoS) in wireless ATM (W-ATM) networks. In this paper, we propose a hierarchical scheduling scheme coupled with fair queueing algorithms with adaptive weights. This scheme is intended to be applicable to a TDMA/TDD based MAC protocol. Specifically, the performance of the fair-queueing algorithm using fixed weights and adaptive weights is evaluated and compared. Simulation results show that the proposed hierarchical fair-queueing scheduling with adaptive weights (HAW) can yield a lower cell transfer delay and a higher channel utilization while maintaining fairness among multiple users.

This paper proposes a new model which can approximate the delay time distribution in the Internet. It is well known that the delay time in communication links follows the exponential distribution. However, the earlier models cannot explain the distribution when a communication link is heavily overloaded. This paper proposes to use the M/M/S(m) model for the Internet. We have applied our model to the measurement results. This paper deals with one-way delay because it reflects the actual characteristics of communication links. Most measurement statistics in the Internet have been based on round-trip time delay between two end nodes. These characteristics are easily measured by sending sample packets from one node to the other. The receiver side echoes back the packets. However, the results are not always useful. A long distance communication link, such as a leased line, has two different fibers or wires for each direction: an incoming link, and an outgoing link. When the link is overloaded, the traffic in each link is quite different. The measurement of one-way delay is especially important for multimedia communications, because audio and video transmissions are essentially one-way traffic.

The author proposes a flow control scheme which derives the optimal packet transmission rate from the ACKs of the sending packets. The optimization is based on mathematical programming such as the extremal method and least-squares method. The author proves that the proposed method is fair when the RTT and thepacket length of each sender are the same. It is also shown that the sufficient condition for the proposed method to be optimal and stable generally holds true in packet networks. The performances are examined by computer simulations, and it is found that high throughput is obtained regardless of the network structure.

A packet-based leaky-bucket algorithm functions like the early packet discard (EPD), and accepts a newly arriving packet if the probability that all the cells of the packet are accepted is high. We derive some performance characteristics of the cell and packet arrival processes that are accepted by the leaky-bucket algorithm. From these analyses, a method to determine the values of the parameters of the leaky-bucket algorithm and certain relations between this leaky-bucket algorithm and the generic cell rate algorithm (GCRA) are obtained.