Control Area Network (CAN) development began in 1983 and continues today. The forecast for annual world production in 2008 is approximately 65-67 million vehicles with 10-15 CAN nodes per vehicle on average . Although the CAN network is successful in automobile and industry control because the network provides low cost, high reliability, and priority messages, a starvation problem exists in the network because the network is designed to use a fixed priority mechanism. This paper presents a priority inversion scheme, belonging to a dynamic priority mechanism to prevent the starvation problem. The proposed scheme uses one bit to separate all messages into two categories with/without inverted priority. An analysis model is also constructed in this paper. From the model, a message with inverted priority has a higher priority to be processed than messages without inverted priority so its mean waiting time is shorter than the others. Two cases with and without inversion are implemented in our experiments using a probabilistic model checking tool based on an automatic formal verification technique. Numerical results demonstrate that low-priority messages with priority inversion have better expression in the probability in a full queue state than others without inversion. However, our scheme is very simple and efficient and can be easily implemented at the chip level.

In wireless networks, sleep mode based power saving mechanisms can reduce the energy consumption at the expense of additional packet delay. This letter analyzes its packet queueing delay and wireless terminals' energy efficiency. Based on the analysis, optimal sleep window size can be derived to optimize terminal energy efficiency with delay constraint.

The IEEE 802.16e standard specifies the sleep mode and the idle mode of a mobile station (MS) for power saving. In this paper, to reduce the energy consumption of the MS, we employ the sleep mode while the MS is on-session, and the idle mode while it is off-session. Under the assumption that the time duration from the end of a session to the arrival of a new downlink session request follows an exponential distribution of the mean and that arrivals of messages during an on-session follow a Poisson process with rate λ, we analyze the awake mode period and the sleep mode period by using the busy period analysis of the M/G/1 queue, and then we derive the total mean length of an on-session which consists of a geometric number of awake mode periods and sleep mode periods. Since the sum of an on-session and an off-session constitutes a cycle, we can express the average power consumption in terms of the mean lengths of an awake mode period, a sleep mode period and an idle mode period. The average power consumption indicates how much the MS can save energy by employing the sleep mode and the idle mode. We also derive the Laplace Stieltjes transform (and the mean) of the queueing delay of messages to examine a tradeoff between the power consumption and the delay of messages. Analytical results, which are shown to be well-matched by simulations, address that our employment of the sleep mode and the idle mode provides a considerable reduction in the energy consumption of the MS.

In this paper, we discuss software performability evaluation considering the real-time property; this is defined as the attribute that the system can complete the task within the stipulated response time limit. We assume that the software system has two operational states from the viewpoint of the end users: one is operating with the desirable performance level according to specification and the other is with degraded performance level. The dynamic software reliability growth process with performance degradation is described by the extended Markovian software reliability model with imperfect debugging. Assuming that the software system can process the multiple tasks simultaneously and that the arrival process of the tasks follows a nonhomogeneous Poisson process, we analyze the distribution of the number of tasks whose processes can be completed within the processing time limit with the infinite server queueing model. We derive several software performability measures considering the real-time property; these are given as the functions of time and the number of debugging activities. Finally, we illustrate several numerical examples of the measures to investigate the impact of consideration of the performance degradation on the system performability evaluation.

We propose two vertical handoff schemes for cellular network and wireless local area network (WLAN) integration: integrated service-based handoff (ISH) and integrated service-based handoff with queue capabilities (ISHQ). Compared with existing handoff schemes in integrated cellular/WLAN networks, the proposed schemes consider a more comprehensive set of system characteristics such as different features of voice and data services, dynamic information about the admitted calls, user mobility and vertical handoffs in two directions. The code division multiple access (CDMA) cellular network and IEEE 802.11e WLAN are taken into account in the proposed schemes. We model the integrated networks by using multi-dimensional Markov chains and the major performance measures are derived for voice and data services. The important system parameters such as thresholds to prioritize handoff voice calls and queue sizes are optimized. Numerical results demonstrate that the proposed ISHQ scheme can maximize the utilization of overall bandwidth resources with the best quality of service (QoS) provisioning for voice and data services.

Traffic Engineering (TE) is important for improving QoS in forwarding paths by efficient use of network resources. In fact, MPLS allows several detour paths to be (pre-)established for some source-destination pair as well as its primary path of minimum hops. Thus, we focus on a two-phase path management scheme using these two kinds of paths. In the first phase, each primary path is allocated to a flow on a specific source-destination pair if the path is not congested, i.e., if its utilization is less than some predetermined threshold; otherwise, as the second phase, one of the detour paths is allocated randomly if the path is available. Therefore, in this paper, we analytically evaluate this path management scheme by extending the M/M/c/c queueing system, and through some numerical results we investigate the impact of a threshold on the flow-blocking probability. Through some numerical results, we discuss the adequacy of the path management scheme for MPLS-TE.

Fair queueing is a service scheduling discipline to pursue the fairness among users in packet communication networks. Many fair queueing algorithms, however, have problems of computational overhead since the central scheduler has to maintain a certain performance counter for each flow of user packets based on the global virtual time. Moreover, they are not suitable for wireless networks with high probability of input channel errors due to the lack or complexity in the compensation mechanism for the recovery from the error state. In this paper, we propose a new, computationally efficient, distributed fair queueing scheme, which we call Channel-Aware Throughput Fair Queueing (CATFQ), that is applicable to both wired and wireless packet networks. In our CATFQ scheme, each flow is equipped with a counter that measures the weighted throughput achievement while it has a backlog of packets. At the end of every service to a packet, the scheduler simply selects a flow with the minimum counter value as the one from which a packet is served next. We show that the difference between any two throughput counters is bounded. Our scheme significantly reduces the scheduler's computational overhead and guarantees fair throughput for all flows. For wireless networks with error-prone channels, the service chance lost in bad channel condition is compensated quickly as the channel recovers. Our scheme suppresses the service for leading flows, brings short-term fairness for flows without channel errors, and achieves long-term fairness for all flows. These merits are verified by simulation.

In this paper, we propose the use of a discrete-time connection oriented Internet service system with a release delay for broadband, high-speed, high-capacity and high-reliability Internet requirements. The release delay called close-delay is set before the release process of a connection. An upper limit length T called timer length is set as a system parameter for the close-delay period. We build a batch arrival Geom*/G/1 queue model with a setup/close-delay/close-down strategy to characterize the system operation. By using a discrete-time imbedded Markov chain approach, we derive the stationary distribution of the system, and present the formula for Probability Generation Functions of the queue length, waiting time, busy period and busy cycle. Correspondingly, we describe the performance measures for the packet response time, setup ratio, and utility of connection. We also develop a cost model to determine the optimal timer length and its expected optimal cost. Based on numerical results, we discuss the influence of the timer length for the close-delay period on the system performance and investigate the minimum timer length and the minimum cost for different offered loads and different burst degrees, and show that the choice of the timer length is significant in improving the system performance.

This letter proposes a new weighted fair queueing algorithm, which adjusts dynamically each flow's service probability according to its weight and average packet length and then uses the service probability parameters to implement fair queueing. This solves the main drawback of traditional weighted fair queueing algorithms--the packet-based tracing of weight parameters. In addition, this letter proposes a novel service probability calculation method which solves the unfairness problem induced by the variable packet length.

Self-Clocked Fair Queueing (SCFQ) and Credit-Based Fair Queueing (CBFQ) are well-known fair scheduling schemes for packet-switched network. In this paper, it is shown that SCFQ and CBFQ are equivalent in selecting packets to transmit. For this, we modified the per-packet service tag based SCFQ algorithm to an equivalent per-session service tag based algorithm, SCFQ+, and showed that the service tags for SCFQ+ and CBFQ evolve identically.

In future systems beyond IMT-2000, macrocell cellular systems such as the 3G systems and high bandwidth microcell wireless systems such as Wireless LAN will complement one another. Routing in the systems beyond IMT-2000 will support seamless inter- and intra-system handover among the cellular and WLAN systems by maintaining active connections. Under such environments, the time scales of mobility and bandwidth-sharing behavior cannot be easily separated. It is not obvious what fraction of traffic is accommodated by each cellular and WLAN system, i.e. the traffic distribution is unknown. This paper shows the considerable impacts the mobility of users has on the capacities of the systems beyond IMT-2000 with roaming capability between different bit rate systems. Especially, this paper demonstrates that the traffic distribution among different systems is a major factor in defining total network throughput. We also provide an analytical method to determine the traffic distribution based on the theory of queueing networks.

Supporting Quality of Service (QoS) over the Internet is a very important issue and many mechanism have been already devised or are under way towards achieving this goal. One of the most important approaches is the class-based architecture, which provides a scalable mechanism for QoS support in a TCP/IP network. Class-based service differentiation can be realized without resource reservation, admission control and traffic policing. However, the resulting services are only relative. While it is, in principle, not feasible to provision for absolute guarantees without admission control and/or traffic policing, such a service can be reasonably well emulated using adaptive rate allocation at the link scheduler of routers. In this paper, we propose mechanism for link scheduler of router that achieve emulated absolute and other relative guarantees using dynamic weighted fair queueing (DWFQ) combining with class packet dropping. The weights of DWFQ are frequently adjusted to current load conditions and based on prediction of realistic class traffic. These mechanisms can realize many approaches to QoS guarantees and class-based differentiation.

Admission control is becoming an essential technique for IP networks to provide full-fledged multimedia streaming services. Although signaling-based schemes are utilized to achieve this, these are difficult to deploy and can hardly achieve strict admission control taking the properties of packet arrival into consideration. In this paper, we propose a novel admission control strategy called the Tentative Accommodating and Congestion Confirming Strategy (TACCS). The main idea is to accommodate incoming flows tentatively and confirm congestion after a certain period. Since tentative accommodating enables us to generate the same situation as where incoming flows have been accommodated, TACCS makes it possible to control admission considering the properties of packet arrival after they have been accommodated, without collecting resource information in advance. From the results of mathematical analysis, we confirmed that TACCS enabled a domain to control admission without a centralized management agent and we provided guidelines for configuring parameters of TACCS.

The recent Internet needs a network structure and traffic engineering that can support various applications requiring differentiated traffic processing and a high quality of service. The extension of the Internet from wired to wireless systems that generate location-dependent and burst errors has made the support of good services more difficult with existing packet scheduling algorithms. Accordingly, this paper proposes a wireless differentiated service packet scheduling (WDSPS) algorithm that can provide reliable and fair services in differentiated wireless internet service networks. As such, the proposed scheduling algorithm solves the HOL blocking problem within a class packet queue that occurs in a wireless network, supports differentiated services for each class defined in a differentiated service network, and facilitates gradual and efficient service compensation not only among classes but also among flows within a class, thereby preventing a monopoly by one class or one flow. Simulations confirmed that the proposed WDSPS scheduling algorithm could provide the required QoS differentiation between classes and enhanced the service throughput under various wireless network conditions.

To provide better QoS management, we investigated network-level dynamic priority methods. We propose methods in which packets of the same type of application receive different treatment in the network, depending on the route information. They feature a simple mechanism, which enables the methods to be executed easily with a small processing load at the routers as well as a small amount of information stored in the packet header. The effectiveness of these methods is shown by numerical comparison with the existing static priority method as well as the dynamic priority method.

Fair scheduling algorithms have been proposed to tackle the problem of bursty and location-dependent errors in wireless packet networks. Most of those algorithms ensure the fairness property and guarantee the QoS of all sessions in a large-scale cellular network such as GSM or GPRS. In this paper, we propose the Weighted-Sacrificing Fair Queueing (WSFQ) scheduling algorithm for small-area and device-limited wireless networks. WSFQ slows down the growth of queue length in limited-buffer devices, still maintains the properties of fairness, and guarantees the throughputs of the system. Moreover, WSFQ can easily adapt itself to various kinds of traffic load. We also implement a packet-based scheduling algorithm, the Packetized Weighted Sacrificing Fair Queueing (PWSFQ), to approach the WSFQ. WSFQ and PWSFQ are evaluated by comparing with other algorithms by mathematical analysis and simulations.

Discrete-time queueing models have been studied for many years because of their direct applicability in the performance evaluation of digital communication system and networks, where buffers are used to temporarily store information packets which cannot be transmitted instantaneously. In this paper, we investigate the behavior of a discrete-time multiserver buffer system with infinite buffer size. Packets arrive in the system according to a two-state correlated arrival process. The service times of the packets are assumed to be independent and identically distributed according to a geometric distribution. We present an analytical technique, based on the use of generating functions, for the analysis of the system. Explicit expressions are obtained for the mean values, the variances and the tail distributions of the system contents and the packet delay. The influence of the various model parameters on the behavior of the system is shown by means of some numerical examples.

In provisioning packet data service on wireless cellular networks, a scheme of altering connection status between mobile and base stations appeared intending to efficiently utilize resource during idle periods. In such a scheme, connection components are sequentially released as an idle period persists, while the transmitting station converts to an transmission activity mode as the station is loaded with packets. However, actual resume of transmission activity is postponed by connection retrieval time to restore lost connection components. In general, an idle period affects the following connection retrieval time, which in turn produces an impact on the forthcoming idle period. Such chain reaction also makes a significant influence on overall packet delay performance. In this paper, as a way of improving packet delay performance, we propose two schemes identified as conservative extension and load threshold schemes. In the conservative extension scheme, we intentionally extend connection retrieval times so that each connection retrieval time is guaranteed not to be lower than a certain value. On the other hand, according to the load threshold scheme, a retrieval of lost connection components is postponed until packets are accumulated at the transmitting station up to a prescribed threshold. An increase in the value and threshold incurs an additional stand-by before resuming transmission activity in both proposed schemes. In turn, such intentional stand-by may contribute to regulating the length of idle period and connection retrieval time, and subsequently improving packet delay performance. To inspect the impact of conservative extension and load threshold schemes on packet delay performance, we first investigate the properties of idle periods. Secondly, for Poisson packet arrivals, we present an analytical method to exactly calculate the moments of packet delay time (at steady state) in each scheme. From numerical examples, we confirm the existence of non-trivial optimal value and threshold minimizing average packet delay or packet delay variation and conclude that conservative extension and load threshold schemes are able to enhance packet delay performance in various environments.

This paper proposes a novel method of identifying the design parameters for a practical implementation of the fair queueing discipline, which is capable of class-level delay control. The notion of class weight is introduced at first, and then the session weights are determined. This two-phase approach is favorable in terms of the scalability;that is, the overall complexity is dependent upon the number of classes only. We propose a packet scheduler referred to as the DPS (Delay-centric Processor Sharing) scheme which employs those design parameters to deliver class-wise delay bound services. The associated admission policy for delay guarantee is also derived. System analysis and derivation of the parameters have their origins in the understanding of the so-called system equation, which describes the dynamics of the class-level service share. The proposed design parameters are QoS-aware in that they are consistently refined depending on the system status. Several numerical and simulation results show that the DPS scheme is advantageous over other ones in terms of both resource efficiency and the robustness. Concerning the scalability, we show that an alternative tagging process of the DPS scheme is implementable with O(1) complexity with no significant degradation in delay performance.

Classical studies of Asynchronous Transfer Mode (ATM) switching elements and in particular the buffer behavior of the Shared Buffer Memory (SBM), assume that all read and write operations of cells to, respectively from, the SBM are executed simultaneously. However, in a real switching element, the inlets (outlets) are scanned sequentially for arriving (departing) cells during the so-called input (output) cycle. Furthermore, the input and output cycles are intermingled, each read operation being followed by a write operation. This is referred to as the Timeslot Interchange Mechanism (TIM). In this paper, we present the analysis of a queueing model that includes the TIM. We model the cell arrival processes on the inlets of the switching element as independent Bernoulli arrival processes. Moreover, we assume that cells are routed from the inlets to the outlets of the switching element according to an independent and uniform process, i.e., the destinations of consecutive cell arrivals on any given inlet are independent and for a given cell all destinations are equiprobable. Under these assumptions, we will derive expressions for the probability generating functions of the queue length in an individual routing group (a logical queue that contains all cells scheduled for the same destination), the (total) queue length in the SBM, and the cell waiting time. From these results, expressions for the mean values and the tail distributions of these quantities are calculated, and the influence of the TIM on the buffer behavior is studied through comparison with a model where all read and write operations occur simultaneously.