WDM networks and working vacation queues

CHAPTER 1 1.3. WDM NETWORKS AND WORKING VACATION QUEUES

Servi and Finn [139] considered multi-queue generalization of a cyclic service queue- ing model arise in WDM network. They have obtained the transform formulae for the distribution of number of customers in the system and sojourn time in steady-state. As an example of the WDM optical access network they applied those results to performance analysis of a gateway router in fiber communication network and showed that the use of WV model for WDM access networks can improve performance over the alternative of having no reconfiguration or reconfiguring all wavelengths. They have modelled the WDM by assuming that, multiple wavelengths who serve as a router, can be accurately approximated by a single-server or, alternately, by assuming that the multiple wavelengths are engineered to indeed perform as if they are a single-server which is called continuous bandwidth mode [138].

The difference between a classical vacation model and a WV model can be outlined as follows. In a classical vacation queueing model, a server completely stops serving the customers during its vacation period and made all the customers wait for service till the vacation period ends. But in a WV model, the server is always available to the customers and rather than cease the service completely during its vacation period, the server serves at a lower rate. Also, during a vacation, customers in the former can only depart the system unserved however, departing customers in the later may complete its service before leaving.

Apart from WDM systems, application of WV models are also seen in other commu- nication networks. Some examples of practical systems which can be viewed as a WV model are provided:

1. Mobile ad hoc network (MANET) is a self-configuring network of mobile devices in which mobile subscribers (MS) are connected to a base station (BS) by wireless links.

Wireless hosts are usually powered by batteries which provide a limited amount of energy. To reduce the energy consumption, power control schemes are used which suitably vary the transmit power and save energy. When a call request comes to a BS, it assigns the MS a link to the destination. If no links are available, the call retries till a link is allocated successfully or balks the system. During transmission,

CHAPTER 1 1.3. WDM NETWORKS AND WORKING VACATION QUEUES

the source node sends out a RTS (‘Request to Send’) packet. The receiver node replies with a packet called CTS (‘Cleared to Send’) packet. After the transmitter node receives the CTS packet, it transmits the data packets. The source node may transmit DATA using a lower power level. The destination node transmits an ACK (acknowledgement) using the minimum required power to reach the source node. In Power Control MAC (PCM) protocol [81] different power levels are used for DATA transmission. After the RTS-CTS handshake using higher power say p_max, suppose the source and destination nodes decide to use power level p₁ for DATA and ACK.

But to avoid a potential collision with ACK, the source node transmits DATA at a higher power level p_max, periodically, for just enough time, so that nodes in the carrier sensing zone can sense it. If the DATA is allowed to transmit only withp_max, more power will be consumed and also it cannot be transferred withp₁ which causes DATA fading. Thus during the sequence of an RTS-CTS-DATA-ACK transmission, the PCM protocol uses a power level changes betweenp₁ and p_max with a maximum power savings without causing throughput degradation. We can model this network as a queue with WVs where the RTS-CTS-DATA-ACK transmission with powerp₁ is a WV period, transmission with powerp_max is non-vacation period. The repeated call attempts are retrials.

2. Edge devices, which are primarily comprised of desktop computers, are the largest Internet-related energy consumers. A desktop computer or a PC is connected to a first-level LAN (Local Area Network) switch through an Ethernet link. In computer networking, Ethernet or IEEE 802.11h, is a digital data transmission technology for LANs. The power consumption of such links are higher for high transmission rates.

Switching to lower link rates during low utilization periods result in reducing the energy consumption. Medium Access Control (MAC) layer is proposed and ana- lyzed for dynamically changing the link rate in the Network Interface Card (NIC), adapting to network utilization. MAC handshake protocol [9] helps to decrease the average power consumption without causing any user-perceivable delays. The pro- tocol uses a dual threshold policy for dictating when to change link rates. Whenever

CHAPTER 1 1.3. WDM NETWORKS AND WORKING VACATION QUEUES

the buffer occupancy drops below the low threshold or rises above the high thresh- old, the handshake mechanism is activated. The link rate is reduced to a low rate when buffer occupancy is below the low threshold value and the rate switched to a higher rate as the buffer congestion reaches the high threshold. This system can also be modeled as a WV queue where the WV (non-vacation) duration is the one when the link rate is low (high).

In literature, the study of WV queueing systems has been carried out by many re- searchers after Servi and Finn. Liu et al. [113] analyzed the M/M/1/WV model using QBD process and matrix-geometric method to obtain explicit expressions of the perfor- mance measures and their stochastic decompositions. Tian et al. [154] have presented the M/M/1 queue with single WV. Xu and Tian [167] and Xiu et al. [165] analyzed this model with single WV and setup times. Wang et al. [161] observed the M/M/1 machine repair problem with WV in which the server works with different repair rates and used Newton’s method to compute steady-state probabilities and several system performance measures. Wu and Takagi [163] extended Servi and Finn’s work to M/G/1/WV model with generally distributed service times and vacation duration times, taking the Laplace- Stieltjes Transforms for the distribution of vacation length to be a rational function. Jain and Agrawal [76] dealt with state dependent M/Ek/1 queueing system with server break- down. Baba [22] considered the GI/M/1/WV system with general independent arrival process where the distribution of the vacation duration times and service times are ex- ponential. He formulated the queueing system as a embedded Markov chain and solved it using matrix-geometric method. Recently, Jain et al. [77] investigated a single-server WV queueing model with multiple types of server breakdowns where each type requires a finite random number stages of repair before service is restored. Wang [158] studied the M/M/1 queue with WV and non-zero switching times and studied a cyclic service system in WDM-based access networks with reconfigurable delay.

The finite-buffer model GI/M/1/K/WV was presented by Banik et al. [26] with multiple WV policy as an extension of Baba’s infinite buffer model. Chen et al. [39, 40]

proposed N-policy WV and cyclic polling system for WDM taking the service times as

CHAPTER 1 1.3. WDM NETWORKS AND WORKING VACATION QUEUES

exponential and PH respectively. Lin and Ke [111] considered a multi-server M/M/c queue and a cost model is derived to determine the optimal values of the number of servers and the WV rate simultaneously, in order to minimize the total expected cost per unit time. Li et al. [109] analyzed a bulk input M^[X]/M/1 queue with single WV. Dutta and Chaubey [55] presented priority assignment to incoming call connection requests for all optical WDM communication, using queuing theory concept. Do [51] studied a retrial M/M/1/WV queue which was motivated by the performance analysis of a Media Access Control (MAC) function in wireless systems and derived the close-form solutions.

Connecting vacation interruption(VI)s and the WV policy, Li and Tian [107] was first to introduce VIs in the basic M/M/1/WV model and derived the stochastic decomposition structure. They further extended the work to GI/M/1/WV and VI queue with multiple exponential vacations [108] and Zhao et al.[173] considered the model with setup period.

In discrete-time case, Tian [148] analyzed the Geom/Geom/1/WV with geometrically distributed vacation duration as an extension of Servi’s work but using quasi birth-death process and matrix-geometric solution method. Subsequently, Li et al. [106] presented the GI/Geo/1 queue with multiple WV, with the same geometrically distributed vaca- tion duration. Considering the two variations of the arrival and departure schemes, early arrival system (EAS) and late arrival system (LAS) with delayed access (LAS-DA) and immediate access (LAS-IA), they obtained the uniform results on the stationary distri- butions and stochastic decomposition properties under both the schemes. Yi et al. [170]

considered a Geo/G/1 queue with disasters that remove all workloads from the system upon their occurrence and presented the steady-state queue length distribution. Xu et al. [166] studied a bulk input Geom^[X]/Geom/1 queue with single WV and found the bi- parameter addition theorems of the conditional negative Binomial distribution. Thus the WV queues are analyzed in continuous-time and also in discrete-time considering different aspects of the system under study.

CHAPTER 1 1.4. PHASE-TYPE DISTRIBUTION

Motivation

The WV queues have been studied considering various features of system characteristics.

Queues with WVs are seen to arise in several communication systems including the WDM networks. Communication systems carry various types of data packets or voice packets which have special properties and accordingly they need special attentions. For example, packets are bursty and correlation between the packets is high and has to be maintained;

some packets need priority over the others and have to be kept separate to allocate different sets of wavelengths on priority basis; some packets make repeated attempts for services, mostly in mobile networks, and have to be assigned a buffer space for their temporary storage, until they receive the requested service; also, packets may abandon the system before receiving service because of impatience and have to be refrained from leaving the system, to maintain the system efficiency. Such features need earnest attention as they are very common in communication networks. Communication systems along with these specific features of packets can be modelled as queues with WVs. In literature, such queues have not been the focus of study. In this thesis, we consider some WV queueing models which incorporate these characteristics of packets. We model these modified WV queues as Markov processes and analyze the performance of those queueing systems.

In the following sections, some mathematical concepts relevant to this thesis are dis- cussed.