Printer Friendly

Modeling Improved Low Latency Queueing Scheduling Scheme for Mobile Ad Hoc Networks.

1 INTRODUCTION

A Mobile Ad hoc Network (MANET) combines wireless mobile nodes that creates dynamically the network in the absence of fixed physical infrastructure. They offer quick and easy network deployment in situations where it is not possible otherwise [1]. MANET is a technology which enables users to communicate without any physical infrastructure regardless of their geographical location and that's why it is sometimes referred to as an infrastructure less network [2]. The increase of cheaper, small and more powerful devices make MANET a fastest growing network. Despite their widespread usage, there are various challenges that are associated with MANETs that affect their usefulness [3]: Firstly, the communication channel between the nodes in the network is highly unreliable. Secondly, the topology of a MANET can change due to the mobility of the nodes in the network. Thirdly, there is need to provide quality of service (QoS) requirements due to demanding applications as a result of commercial usage of multimedia transmission and the rapidly growing number of users, in addition to the type of traffic. This convergence of multimedia traffic with traditional data traffic creates yet another challenge because the former requires strict delay whereas the latter is delay-tolerant. Fourthly, Security due to potentially hostile environments, plus limited bandwidth and energy resources can be counted among other challenges. Due to the above mentioned challenges, guaranteeing Quality of Service (QoS) requirements to different users in MANETs becomes extremely hard. One of the most popular scheduling algorithms used in MANETs is Low Latency Queue (LLQ) [4]. LLQ was developed by Cisco to bring strict priority queuing (PQ) to class-based weighted fair queuing (CBWFQ). The LLQ algorithm allows delay-sensitive data (such as voice) to be given preferential treatment over other traffic by letting the data to be dequeued and sent first. The LLQ is a combination of Priority Queuing (PQ) and WFQ [5]. The LLQ scheme uses a strict priority queue that is given priority over other queues, which makes it ideal for delay and jitter sensitive applications. At the time of congestion, LLQ cannot transmit more data than its bandwidth permits, hence if more traffic arrives than the strict priority queue can transmit, it is dropped. In this paper, we develop an improved Low Latency Queueing scheme for Mobile Ad Hoc Networks. The rest of the paper is organized as follows; in the next section, we present the related work. In section 3, we present the system model, in section 4 we present the performance evaluation and finally conclude in section 5.

2 RELATED WORK

The traditional packet scheduling algorithm used in most systems is First-In-First-Out (FIFO), which places all packets into a single queue and processes them in the same order in which they are received. FIFO is easy to implement, however FIFO cannot differentiate among the different types of traffic. To overcome the above limitations and to provide fair sharing of resources, many other types of scheduling methods, such as Priority Queuing (PQ), Weighted Round Robin (WRR), Weighted Fair Queuing (WFQ), Custom Queuing (CQ) and Class-Based Weighted Fair Queuing (CB-WFQ) have been proposed [6]. The real time applications are treated preferentially in the priority queuing algorithm. However, when the amount of higher-priority traffic is excessive, the PQ suffers a starvation problem.

To overcome the challenges above, Cisco Systems introduced a Low Latency Queuing (LLQ) algorithm which combines a single strict priority queue with CBWFQ. LLQ allows delay-sensitive data (such as voice) to be given preferential treatment over other traffic. However, if sensitive audio and video packets are processed in the single priority queue due to resource sharing between many applications, the expected QoS level cannot be guaranteed.

A new approach combined WFQ with LLQ scheduling disciplines to ensure QoS for high priority bursty video conferencing, voice and data services at the same time [7]. The main drawback of the WFQ with LLQ is that we get reduced delay of high priority class (video conferencing) but at the same time we get highest delay time of voice traffic. In another study, Brunonas et al. [7] proposed a new approach by combining WFQ with LLQ scheduling disciplines to ensure QoS for high priority bursty video conferencing, voice and data services at the same time. The main weakness of the WFQ with LLQ is that although there is reduced delay of high priority class (video conferencing), there is highest delay time of voice traffic.

In a recent study Rukmani et al. [8] developed an Enhanced LLQ (ELLQ) scheduling algorithm that categorizes and prioritizes the real-time traffic. In this algorithm an additional priority queue is introduced for scheduling the video applications separately along with the dedicated strict-priority queue for voice applications. The lower priority queues are serviced using CBWFQ. Although this approach offers preferential treatment to real-time traffic, at high arrival rates of voice traffic, the video traffic may suffer starvation and complete resource malnourishment. To overcome the above challenge, we propose to modify the Enhanced LLQ algorithm by delaying voice packets and servicing video packets as long as the voice packets are not delayed beyond the maximum tolerable delay limit. The voice packets are given priority over video packets to avoid jitter that requires a non-variable delay, which is most important for voice applications. The lower priority packets are serviced using the CBWFQ algorithm.

3 SYSTEM MODELS

In this paper, we employ queueing theory. Queuing models are suitable in a variety of environments ranging from common daily life scenarios to complex service and business processes, operations research problems, or computer and communication systems. Queuing theory has been extensively applied to evaluate and improve system behavior [9]. An advantage of the queuing model is that one can use various results available in queuing theory to get appropriate approximations. Kendall introduced a standard notation for classifying queuing systems into different types [10]. Kendall's notation can be expressed in the form A/B/X/Y/Z where A and B stand for the distributions of the inter arrival times and service demands respectively, X stands for the number of servers in the system, Y stands for restrictions on system capacity, and Z denotes the scheduling policy that governs the queue. Video and voice traffic are modeled using the MMPP/G/1 queue system. Markov Modulated Poisson Process (MMPP) is one of the most used models to capture the typical characteristics of the incoming traffic such as self-similar behavior (correlated traffic), burstiness behavior, and long range dependency, and is simply a Poisson process whose mean value changes according to the evolution of a Markov Chain [11, 12]. Since real time traffic like voice and video signals can be bursty [8], Markov Modulated Poisson Process is best fitted to model its arrival rate. MMPP is normally used for modeling bursty traffic owing to its ability to model the time-varying arrival rate and capture the important correlation between interarrival times while still maintaining analytical tractability. G stands for general service time distribution, meaning the service time can take on any distribution, e.g exponential or Bounded Pareto, and one server.

In the improved LLQ algorithm, all incoming traffic will arrive at the classifier, from outside the system according to either an MMPP or a Poisson process with specified rate. At the classifier, the traffic will be identified and forwarded to the class of their priority. The required service priority are provided through MAC service class parameters [8]. Real time voice and video packets are forwarded to the strict priority queue, while the other types of data are forwarded to the CBWFQ queue. During service, voice packets are prioritized over video. LLQ provides priority for voice packets to ensure that voice packets are not stuck behind the large video packets. At high arrival rate of voice packets, voice packets are delayed to serve video packets as long as the voice packets are not delayed beyond the tolerable delay limits. In this case the video packets are serviced immediately after the voice packets found in the queue without necessarily waiting to service voice packets that arrive while the video packets are already in the queue. The voice packets are given priority over video to avoid jitter that requires a non-variable delay, which is most important for voice applications. On the other hand the CBWFQ queue will consist of FTP, HTTP and e-mail packets. Figure 1 represents the proposed model.

Next, expressions for average waiting time for an MMPP/G/1 queue system are derived. MMPP/G/1 is a queue system where the arrivals follow Markov Modulated Poisson Process, the service times follow the general service distribution, and one server is allowed to provide service. The behavior of an MMPP/G/1 queue is approximated analytically. The method employed consists in approximating the MMPP/G/1 queue system using a weighted superposition of different M/G/1 queues.

3.1 Expressions for the Performance Metrics

Consider an MMPP/G/1 queue, and let the MMPP that models the incoming data traffic be composed by H states ([S.sub.1], [S.sub.2]). An MMPP with two transition states are used in this study. Let the notation Mi/G/1 to refer to an M/G/1 queue whose average arrival rate is [[lambda].sub.i] observed in state [S.sub.i],i = 1, 2 and the service rate is [mu] and is constant among all the [S.sub.i] states. The analytical approximations is based on the observation that if the MMPP stays in state [S.sub.i] long enough without transiting to another state, the average waiting time at time t reach the same steady state observed for the corresponding [M.sub.i]/G/1 queue. The values are pinned on the same steady state value of [M.sub.i]/G/1 as long as the MMPP does not change its state from [S.sup.i]. Similar approximations have been used to approximate mean queue length and average response time for an MMPP/M/1 queue system [13].

The average packet waiting time is an average evaluated over the number of incoming requests which are not distributed equally over time (during the state [S.sub.1] the arrival rate of requests is [[lambda].sub.1], while during the state [S.sub.2] the arrival rate of requests is [[lambda].sub.2]. Therefore, the average packet waiting time of the MMPP/G/1 is a weighted sum of the average packet queueing delays of the Mi/G/1 queues, expressed as

WQ = [2.summation over (i=1)] W[Q.sub.i][X.sub.i] (1)

where [W.sub.Q] is the packet queueing delay, and ([x.sub.i]) is the weight of the delay in each state. The weights ([x.sub.i]) are scaled to keep into account the different arrival rate per each state. Hence

[x.sub.i] = [p.sub.i][[lambda].sub.i]/[[summation].sup.2.sub.j=1] [p.sub.j][[lambda].sub.j] (2)

[p.sub.i] is the probability of being in state i, and [[lambda].sub.i] is the arrival rate of packets in state i.

3.2 Expression for average waiting time of voice packets under MMPP/M/1 queue system before delay

In this study, models for the average waiting time in the queue for voice packets are derived. Assuming a tagged voice packet arriving to the voice queue. This packet will be delayed by:

* mean residual time of the packets found in service,

* the mean waiting time of the voice packets found in the queue.

The average total waiting time of the tagged voice packet can be derived as follows: We approximate the MMPP/M/1 queue system using a weighted superposition of different M/M/1 queues. Let [lambda] and [mu] be the rate of arrival for the Poisson process and [mu] the rate of service for the exponential distribution. Consider the state transition diagram for a simple M/M/1 queue shown in figure 2.

Considering the global balance equations for this system we can derive the general expression for the probability of a packet being in any state:

[P.sub.1] = [lambda]/[mu] x [P.sub.0] (3)

[P.sub.2] = [([lambda]/[mu]).sup.2] x [P.sub.0] (4)

[P.sub.3] = [([lambda]/[mu]).sup.3] x [P.sub.0] (5)

where [P.sub.i,i] = 0,1, 2, 3 is the probability of being in states 0, 1, 2, 3, etc. In general, the probability of a packet being in any state can be deduced as:

[P.sub.i] = [([lambda]/[mu]).sup.i] x [P.sub.0], 1 = 1,2, ..., [integral] (6)

Using the fact that [[summation].sup.[integral].sub.i=1] [([lambda]/[mu]).sup.i] x [P.sub.0] = 1 we obtain [P.sub.n] = (1 - [rho])[[rho].sup.n], n = 0,1, 2, ..., [integral]

Average number of packets in the queue is given by

[Mathematical expression not reproducible.]

Using Little's law [9], [N.sub.Q] = [mu][W.sub.Q], where [W.sub.Q] is the average waiting time in the queue.

[W.sub.Q] = R/(1 - [rho]) (7)

Since is equivalent to the residual service time [R.sup.[rho]/[mu]].

The expression for the average packet waiting time for the two states of MMPP/M/1 can be obtained by combining equations 1 and 7 to obtain:

[W.sub.Q] = [2.summation over (i=1)] [x.sub.i] x R/(1 - [rho]) (8)

Where [x.sub.i] = [P.sub.i][[lambda].sub.i]/[[summation].sup.2.sub.j=1] [P.sub.j][[lambda].sub.j]

Hence, the expression for the average packet waiting time experienced by the tagged voice packet is given as:

[W.sup.Vo.sub.Q] = [2.summation over (i=1)][x.sub.i] x R/(1 - [[rho].sup.Vo]) (9)

3.3 Expression for average waiting time of video packets under MMPP/M/1 queue system before delay

In this study, derive models for the average waiting time in the queue for video packets before delay are derived. Assuming a tagged video packet arriving to the video queue. This packet will be delayed by:

* mean residual time of the packets found in service,

* the mean waiting time of the high priority voice packets found in the queue,

* the mean waiting time of video packets found in the queue,

* the mean waiting time of subsequent arrivals of voice packets while the tagged video packet is waiting in the queue for service.

The expression for the average waiting time for video packets can be derived as shown below:

[Mathematical expression not reproducible.]

But [W.sup.Vo] = R/(1 - [[rho].sup.Vo])

[Mathematical expression not reproducible.] (10)

Therefore, the expression for the average waiting time for packets in the video queue is given by

[W.sup.v] = [2.summation over (i=1)][x.sub.i] R/(1 - [[rho].sup.vo])(1 - [[rho].sup.vo] - [[rho].sup.V]) (11)

3.4 Expression for average waiting time of voice packets in an MMPP/M/1 queue after being delayed once

In this study, models for the average waiting time in the queue for voice packets after being delayed once are derived. Assuming a tagged voice packet arriving to the voice queue. This packet will be delayed by:

* mean residual time of the packets found in service,

* the mean waiting time of the voice packets found in the queue,

* the mean waiting time of video packets found in the queue,

The expression for the average waiting time for the tagged voice packet can be derived as shown below:

[Mathematical expression not reproducible.]

After simplification, we get

[W.sup.Vo] = (R/1 - [[rho].sup.Vo]) + [[rho].sup.v]R/[(1 - [[rho].sup.Vo]).sup.2](1 - [rho] [[rho].sup.Vo] - [[rho].sup.V])

Hence,

[W.sup.Vo] = (R/1 - [[rho].sup.Vo]) + [[rho].sup.v]R/[(1 - [[rho].sup.Vo]).sup.2](1 - [rho] [[rho].sup.Vo] - [[rho].sup.V])

Therefore, the expression for the average waiting time for packets in the voice queue after being delayed once is given by

[W.sup.Vo] = [2.summation over (i=1)][x.sub.i] (R/1 - [[rho].sup.Vo]) + [[rho].sup.v]R/[(1 - [[rho].sup.Vo]).sup.2](1 - [rho] [[rho].sup.Vo] - [[rho].sup.V]) (12)

* mean residual time of the packets found in service,

* the mean waiting time of the voice packets found in the queue,

* the mean waiting time of video packets found in the queue,

The expression for the average waiting time for the tagged voice packet can be derived as shown below:

[Mathematical expression not reproducible.]

After simplification, we get

[W.sup.v] = R/(1 - [[rho].sup.V])(1 - [[rho].sup.Vo])

Hence,

[W.sup.v] = R/(1 - [[rho].sup.v])(1 - [[rho].sup.Vo]) (13)

Therefore, the expression for the average waiting time for packets in the video queue after delaying voice packets once is given by

[w.sup.V] = [2.summation over (i=1)][x.sub.i] R/(1 - [[rho].sup.v])(1 - [[rho].sup.vo]) (14)

3.5 Expression for average waiting time for video packets in an MMPP/M/1 queue after delaying voice packets once

In this study, models for the average waiting time in the queue for video packets after delaying voice packets once are derived. Assuming a tagged video packet arriving to the video queue. This packet will be delayed by:

3.6 Expression for average waiting time of voice packets under MMPP/BP/1 queue system before delay

In this study, models for the average waiting time in the queue for voice packets under MMPP/BP/1 queue system are derived. The expression for average packet waiting time in the queue for MMPP/BP/1 can be derived from the general expression for MMPP/G/1. However, the average waiting time of a packet for MMPP/G/1 queue system can be got by approximating the MMPP/G/1 queue system using a weighted superposition of different M/G/1 queues.

There are various approximations for the average waiting time experienced by requests under the M/G/1 queue system [14]. A naturally refined heavy-traffic approximation exploiting the exact M/M/1 results is given in [15] as:

E[[W.sup.M,G,1]] = Co[V.sup.2] + 1/2 + 1E[[W.sup.M/M/1]] (15)

where CoV is the coefficient of variation of the service time distribution. The coefficient of variation defined as the ratio of the standard deviation to the mean of a distribution is a common metric to measure the variability of a distribution, and the higher the CoV value of a distribution, the higher the variability of the distribution. E[[W.sup.M/G/1]] is the average waiting time under M/G/1 queue system, and E[[W.sup.M/M/1]] is the average waiting time under M/M/1 queue system.

The expression for the average waiting time of packets under MMPP/G/1 can be deduced as follows:

From equation 7, the average waiting time of a voice packet under M/G/m can be deduced as:

[W.sup.vo] = (Co[V.sup.2] + 1)/2 R/(1 - [rho]) (16)

The expression for the average waiting time for a tagged voice packet before delay for two states for MMPP/G/1 is given as:

[W.sup.vo] = [2.summation over (i=1)][x.sub.i] ((Co[V.sup.2] + 1/2 R/1 - [[rho].sup.Vo])) (17)

Where [x.sub.i] = [p.sub.i][[lambda].sub.i]/[[summation].sup.2.sub.j=1][p.sub.j][[lambda].sub.j]

In the next section, we derive the expression for average waiting time of video packet under the MMPP/G/1 queue system before delaying the voice packet.

3.7 Expression for average waiting time of video packets under MMPP/BP/1 queue system before delaying the voice packet

In this study models for the average waiting time in the queue for video packets under MMPP/BP/1 queue system are derived. Using a similar approach, the average waiting time of video packets can be estimated using the M/M/1 results given in [15] as:

E[[W.sup.M/G/1]] = Co[V.sup.2] + 1/2 + E[[W.sup.M/M/1]] (18)

The expression for the average waiting time of video packets before delaying the voice packets under MMPP/G/1 can be deduced from equation 10 as follows:

[W.sup.V] = (Co[V.sup.2] + 1)/2 R/(1 - [[rho].sup.Vo] (1 - [[rho].sup.Vo] - [[rho].sup.V])) (19)

Therefore, the expression for the average waiting time for a tagged video packet before delaying the voice packets for two states for MMPP/G/1 is given as:

[Mathematical expression not reproducible.] (20)

where [x.sub.i] = [p.sub.i][[lambda].sub.i]/[[summation].sup.2.sub.j=1][p.sub.j][[lambda].sub.j]

In the next section, the expression for average waiting time of voice packet under the MMPP/G/1 queue system after delaying the voice packets is derived.

3.8 Expression for average waiting time of voice packets in an MMPP/BP/1 queue after being delayed once

In this study models for the average waiting time in the queue for voice packets after being delayed once under MMPP/BP/1 queue system are derived. Using a similar approach as used in section 3.6, the average waiting time of voice packets can be estimated using the M/M/1 results given in (Allen, 1990) as:

E[[W.sup.M/G/1]] = Co[V.sup.2]/2 + E[[w.sup.M/M/1]] (21)

The expression for the average waiting time of voice packets after delaying the voice packets once under MMPP/G/1 can be deduced from equation 3.4 as follows:

[Mathematical expression not reproducible.] (22)

Therefore, the expression for the average waiting time of voice packets after delaying the voice packets once for two states for

MMPP/G/1 is given as:

[Mathematical expression not reproducible.] (23)

where [x.sub.i] = [p.sub.i][[lambda].sub.i]/[[summation].sup.2.sub.j=1][p.sub.j][[lambda].sub.j]

In the next section, the expression for average waiting time of video packets under the MMPP/G/1 queue system after delaying the voice packets is derived.

3.9 Expression for average waiting time of video packets in an MMPP/BP/1 queue after delaying voice packets once

In this study models for the average waiting time in the queue for video packets after delaying voice packets once under MMPP/BP/1 queue system are derived. Using a similar approach as used in section 3.6, the average waiting time of voice packets can be estimated using the M/M/1 results given in (Allen, 1990) as:

E[[W.sup.M/G/1]] = Co[V.sup.2] + 1 E[[W.sup.M/M/1]] (24)

The expression for the average waiting time of video packets after delaying the voice packets once under MMPP/G/1 can be deduced from equation 13 as follows:

[W.sup.V] (Co[V.sup.2] + 1)/2 R/(1 - [[rho].sup.v]}(1 - [[rho].sup.vo]) (25)

Therefore, the expression for the average waiting time of video packets after delaying the voice packets once for two states for MMPP/G/1 is given as:

[Mathematical expression not reproducible.] (26)

where[x.sub.i] = [p.sub.i][[lambda].sub.i]/[[summation].sup.2.sub.j=1][p.sub.j][[lambda].sub.j]

4 PERFORMANCE EVALUATION

In this study the performance of the derived models are tested. The performance of voice and video packets under the MMPP/M/1 and MMPP/BP/1 queue systems before and after delaying voice packets once using MATLAB and present numerical results are presented. Furthermore, the comparison of the performance of voice and video packets under MMPP/M/1 and MMPP/BP/1 queue systems are made. Specifically MMPP/M/1 and MMPP/BP/1 are used which are special cases of MMPP/G/1 in terms of average waiting time. The results nicely illustrate the impact of delayed voice packets on the performance of both voice and video packets. Furthermore, the impact of correlated arrivals as compared to Poisson arrivals are investigated. Consider the MMPP parameters that are set on the basis of the results reported in which has shown, via real traces analysis, the feasibility to model incoming traffic to a GRID server [16]. According to the data reported in [16], the incoming data traffic of the analyzed GRID server can be modeled by a 2-state MMPP model, whose parameters are presented in table 1. The transition probability [P.sub.1] from state [S.sub.1] to state [S.sub.2], is 0.17, while the transition probability [p.sub.2], from state [S.sub.2] to state [S.sub.1], is 0.08. For voice packets, the recommended maximum delay of 150ms as per the ITU-T recommendation G.114 is used [17]. Usually the loss of some amount of voice packets is compensated using redundant data to recover lost content and silence intervals. For video packets, we consider interactive video and video on demand applications which also have maximum tolerable delay limit of 150ms [17]. Arrival rates of packets in the system is set from 0 packets/second to 22.1 packets/second, arrival rates of packets within similar ranges have been used to analyze performance of MANETS in [18, 19]. In addition arrival rate of 0 to 24 packets per second was used to simulate an on-demand Quality of Service (QoS) and stability based multicast routing (OQSMR) scheme in MANETS [20]. The Maximum delay limit for voice packets is taken as 150ms [17], and the maximum delay limit for video packets is 150ms [17]. Table 1 shows the hypothetical parameters used in the analysis which is consistent with parameters used in literature [15, 16].

4.1 Average waiting time for voice packets as a function of load under MMPP/M/1 system

Table 1. implementation parameters Next, the performance of voice packets before and after delay is investigated. In doing this, the changes in average waiting time with increase in load and arrival rate are determined.

The study compares the performance of voice packets before and after delay under MMPP/M/1 queue system in terms of average waiting time as a function of load due to voice and video packets. The results nicely illustrate the impact of delaying voice packets to serve video packets in terms of average waiting time as the performance metric. Figure 3 shows a graph of average waiting time of voice packets as a function of load due to voice packets. Equations 9 and 12 are used to plot the graph. It can be observed from figure 3 that average waiting time increases with increase in load due to voice packets regardless of whether the voice packets are delayed or not. The increase in average waiting time as the load due to voice packets increase can be explained by the fact that as the load increases, the number of voice packets to be processed in the system also increases. It is further observe that for low load values, the average waiting time for voice packets under MMPP/M/1 queue system before and after delay are much closer, however as the load due to voice packets increase the average waiting time after delay is much higher than before delay. The difference in average waiting time before delay and after delay is more pronounced for higher load values. It can also be observed that voice packets can be delayed to serve video packets as long as the load due to voice packets in the system does not exceed 81% as shown by the maximum tolerable delay limit.

Average waiting time for voice packets as a function of arrival rate under MMPP/M/1 system

The performance of voice packets before and after delay under MMPP/M/1 queue system in terms of average waiting time as a function of arrival rate of voice and video packets are compared.

Figure 4 shows a graph of average waiting time of voice packets as a function of arrival rate of voice packets. Equations 9 and 12 are used to plot the graph. It can be observed from figure 4 that average waiting time of voice packets increase with increase in arrival rate of voice packets before and after delaying voice packets. Increase in arrival rate leads to increase in the number of packets to be processed in the system which in turn leads to increase in average waiting time. It can also be observed that at low arrival rate of voice packets, the average waiting time for voice packets under MMPP/M/1 queue system before and after delay are much closer, however as the arrival rate of voice packets increase the average waiting time after delay is much higher than before delay. The difference in average waiting time before delay and after delay is more pronounced at higher arrival rates of voice packets. Furthermore, it can be observed that voice packets can be delayed to serve video packets as long as the arrival rate of voice packets in the system does not exceed approximately 14 packets/second as shown by the maximum tolerable delay limit.

4.2 Evaluation of average waiting time for video packets under MMPP/M/1 before and after delay

The study investigates the performance of video packets before and after delay. In doing this, the changes in average waiting time with increase in load and arrival rate is determined.

Average waiting time for video packets as a function of load under MMPP/M/1 system The study compares the performance of video packets before and after delay under MMPP/M/1 queue system in terms of average waiting time as a function of load due to voice and video packets. The results nicely illustrate the impact of delaying voice packets to serve video packets in terms of average waiting time as the performance metric.

Figure 5 shows a graph of average waiting time of video packets as a function of load due to voice packets. Equations 11 and 14 are used to plot the graph. It is observed from figure 5 that average waiting time of video packets increase with increase in load due to voice packets regardless of whether the voice packets are delayed or not. The increase in average waiting time of video packets as the load due to voice packets increase can be explained by the fact that as the load due to voice packets increase, the number of voice packets to be processed in the system also increases and this in turn increases the average waiting time of video packets since video packets have to wait for voice packets found in the system to be serviced before they receive service. It can also be observed that for low load values, the average waiting time of video packets under MMPP/M/1 queue system before and after delay are much closer, however as the load due to voice packets increase the average waiting time after delay is much lower than before delay. The difference in average waiting time before delay and after delay is more pronounced for higher load values of voice packets. In addition, it is observed that video packets experience lower average waiting time as a result of delaying voice packets to serve video pack ets, and the reduction in average waiting time is much higher at higher load values of voice packets.

Figure 6 shows a graph of average waiting time of video packets as a function of load due to video packets. Equations 11 and 14 are used to plot the graph. It is observed from figure 6 that average waiting time of video packets increase with increase in load due to video packets regardless of whether the voice packets are delayed or not. The increase in average waiting time of video packets as the load due to video packets increase can be explained by the fact that as the load due to video packets increase, the number of video packets to be processed in the system also increases and this in turn increases the average waiting time of video packets. It can be further observed that for low load values, the average waiting time of video packets under MMPP/M/1 queue system before and after delay are much closer, however as the load due to video packets increase the average waiting time after delay is much lower than before delay. The difference in average waiting time before delay and after delay is more pronounced for higher load values of video packets. It can also be observed that video packets experience lower average waiting time as a result of delaying voice packets to serve video packets, and the reduction in average waiting time is higher at higher load values of video packets.

Average waiting time for video packets as a function of arrival rate under MMPP/M/1 system

The study compares the performance of video packets before and after delay under MMPP/M/1 queue system in terms of average waiting time as a function of arrival rate of voice and video packets.

Figure 7 shows a graph of average waiting time of video packets as a function of arrival rate of voice packets. Equations 11 and 14 are used to plot the graph. It can be observed from figure 7 that average waiting time of video packets increase with increase in arrival rate of voice packets irrespective of whether the voice packets are delayed or not. The increase in average waiting time of video packets as the arrival rate of voice packets increase can be explained by the fact that as the arrival rate of voice packets increase, the number of voice packets to be processed in the system also increases and this in turn increases the average waiting time of video packets since video packets have to wait for voice packets found in the system to be serviced before they receive service. It is further observed that for low arrival rates, the average waiting time of video packets under MMPP/M/1 queue system before and after delay are much closer, however as the arrival rate of voice packets increase the average waiting time after delay is lower than before delay. The difference in average waiting time before delay and after delay is more pronounced for higher arrival rates of voice packets. It can also be observed that video packets experience lower average waiting time as a result of delaying voice packets to serve video packets, and the reduction in average waiting time is much higher at higher arrival rates of voice packets. Furthermore, it can be observed that video packets can be delayed to serve video packets as long as the arrival rate of voice packets in the system does not exceed approximately 14 packets/second.

Figure 8 shows a graph of average waiting time of video packets as a function of arrival rate of video packets. Equations 11 and 14 are used to plot the graph. It can be observed from figure 8 that average waiting time of video packets increase with increase in arrival rate of video packets regardless of whether the voice packets are delayed or not. The increase in average waiting time of video packets as the arrival rate of video packets increase can be explained by the fact that as the arrival rate of video packets increase, the number of video packets to be processed in the system also increases which results into increase in the average waiting time of video packets. It can also be observed that for low arrival rates of video packets, the average waiting time of video packets under MMPP/M/1 queue system before and after delay are closer, however as the arrival rate of video packets increase the average waiting time after delay is lower than before delay. The difference in average waiting time before delay and after delay is more pronounced for higher arrival rates of video packets. In addition, it can be observed that video packets can be delayed to serve video packets as long as the arrival rate of video packets in the system does not exceed approximately 21 packets/second.

4.3 Evaluation of average waiting time for voice packets under MMPP/BP/1 before and after delay

In this study, the performance of voice packets before and after delay under MMPP/BP/1 queue system in terms of average waiting time as a function of load and arrival rate are compared. The results nicely illustrate the impact of delaying voice packets to serve video packets in terms of average waiting time as the performance metric.

4.4 Average waiting time for voice packets as a function of load under MMPP/BP/1 system

The study compares the performance of voice packets before and after delay under MMPP/BP/1 queue system in terms of average waiting time as a function of load due to voice and video packets.

Figure 9 shows a graph of average waiting time of voice packets as a function of load due to voice packets under MMPP/BP/1 queue system. Equations 17 and 23 are used to plot the graph. It can be observed from figure 9 that average waiting time of voice packets increase with increase in load due to voice packets regardless of whether the voice packets are delayed or not. The increase in average waiting time of voice packets as the load due to voice packets increase can be explained by the fact that as the load due to voice packets increase, the number of voice packets to be processed in the system also increases and this in turn increases the average waiting time of voice packets. Furthermore, it can be observed that for low load values, the average waiting time of voice packets under MMPP/BP/1 queue system before and after delay are much closer, however as the load due to voice packets increase the average waiting time after delay is much higher than before delay. The difference in average waiting time before delay and after delay is more pronounced for higher load values of voice packets. It can also be observed that voice packets can be delayed to serve video packets as long as the load due to voice packets does not exceed 81% as shown by the maximum tolerable delay limit.

Average waiting time for voice packets as a function of arrival rate under MMPP/BP/1 system

Comparison of the performance of voice packets before and after delay under MMPP/BP/1 queue system in terms of average waiting time as a function of arrival rate of voice and video packets.

Figure 10 shows a graph of average waiting time of voice packets as a function of arrival rate of voice packets under MMPP/BP/1 queue system. Equations 17 and 23 are used to plot the graph. It can be observed from figure 10 that average waiting time of voice packets increase with increase in arrival rate of voice packets regardless of whether the voice packets are delayed or not. The increase in average waiting time of voice packets as the arrival rate of voice packets increase can be explained by the fact that as the arrival rate of voice packets increase, the number of voice packets to be processed in the system also increases and this leads to increase in the average waiting time of voice packets. It can further be observed that for low arrival rate values of voice packets, the average waiting time of voice packets under MMPP/BP/1 queue system before and after delay are closer, however as the arrival rate of voice packets increase the average waiting time after delay is higher than before delay. The difference in average waiting time before delay and after delay is much higher at higher arrival rate of voice packets. It can also be observed that voice packets can be delayed to serve video packets as long as the arrival rate of voice packets does not exceed 14 packets/second.

4.5 Evaluation of average waiting time for video packets under MMPP/BP/1 before and after delaying voice packets

This study compares the performance of video packets before and after delaying voice packets under MMPP/BP/1 queue system in terms of average waiting time.

Average waiting time for video packets as a function of load under MMPP/BP/1 system

The study compares the performance of video packets before and after delaying under MMPP/BP/1 queue system in terms of average waiting time as a function of load due to voice and video packets.

Figure 11 shows a graph of average waiting time of video packets as a function of load due to voice packets under MMPP/BP/1 queue system. Equations 20 and 26 are used to plot the graph. It can be observed from figure 11 that average waiting time of voice packets increase with increase in load due to voice packets irrespective of whether the voice packets are delayed or not.

It can further be observed that for low load values of video packets, the average waiting time of voice packets under MMPP/BP/1 queue system before and after delay are closer, however as the load due to voice packets increase the average waiting time after delay is lower than before delay. The difference in average waiting time before delay and after delay is higher at higher arrival rates of voice packets. It can also be observed that voice packets can be delayed to serve video packets even when the load due to voice packets is approximately 90%.

Figure 12 shows a graph of average waiting time of video packets as a function of load due to video packets under MMPP/BP/1 queue system. Equations 20 and 26 are used to plot the graph. It can be observed from figure 12 that average waiting time of video packets increase with increase in load due to video packets regardless of whether the voice packets are delayed or not. The increase in average waiting time of video packets as the load due to video packets increase can be explained by the fact that as the load due to video packets increase, the number of video packets to be processed in the system also increases and this in turn increases the average waiting time of video packets. It can further be observed that for low load values of video packets, the average waiting time of video packets under MMPP/BP/1 queue system before and after delay are much closer, however as the load due to video packets increase the average waiting time after delay is lower than before delay. The difference in average waiting time before delay and after delay increases as the load due to video packets increase. It can also be observed that voice packets can be delayed to serve video packets without restrictions on the load due to video packets.

Average waiting time for video packets as a function of arrival rate under MMPP/BP/1 system

The study compares the performance of video packets before and after delaying under MMPP/BP/1 queue system in terms of average waiting time as a function of arrival rate of voice and video packets.

Figure 13 shows a graph of average waiting time of video packets as a function of arrival rate of voice packets under MMPP/BP/1 queue system. Equations 17 and 23 are used to plot the graph. It can be observed from figure 13 that average waiting time of video packets increase with increase in arrival rate of voice packets regardless of whether the voice packets are delayed or not. The increase in average waiting time of video packets as the arrival rate of voice packets increase can be explained by the fact that as the arrival rate of voice packets increase, the number of voice packets to be processed in the system also increases and this leads to increase in the average waiting time of video packets since video packets have to wait for voice packets found in the system to be serviced before video packets can get serviced. It can further be observed that for low arrival rate values of voice packets, the average waiting time of video packets under MMPP/BP/1 queue system before and after delay are closer, however as the arrival rate of voice packets increase the average waiting time after delay is lower than before delay. The difference in average waiting time before delay and after delay is much higher at higher arrival rate of voice packets. It can also be observed that voice packets can be delayed to serve video packets for arrival rates of voice packets of upto approximately 22 packets/second.

Figure 14 shows a graph of average waiting time of video packets as a function of arrival rate of video packets under MMPP/BP/1 queue system. Equations 17 and 23 are used to plot the graph. We observe from figure 14 that average waiting time of video packets increase with increase in arrival rate of video packets irrespective of whether the voice packets are delayed or not. The increase in average waiting time of video packets as the arrival rate of video packets increase can be explained by the fact that as the arrival rate of video packets increase, the number of video packets to be processed in the system also increases and this leads to increase in the average waiting time of video packets. It can further be observed that for low arrival rate values of video packets, the average waiting time of video packets under MMPP/BP/1 queue system before and after delay are closer, however as the arrival rate of video packets increase the average waiting time after delay is lower than before delay. The difference in average waiting time before delay and after delay is much higher at higher arrival rate of video packets. It can also be observed that voice packets can be delayed to serve video packets for arrival rates of video packets of upto approximately 22 packets/second.

Next, the tradeoff in improvement in performance of video packets against degradation in service of voice packets under MMPP/M/1 is evaluated.

4.6 Tradeoff in improvement in performance of video packets and degradation in service of voice packets under MMPP/M/1

The study investigates the tradeoff in improvement in performance of video packets against the degradation in performance of voice packets in terms of average waiting time as a function of load and arrival rate under MMPP/M/1 queue system.

Figure 15 shows a graph of average waiting time of voice and video packets as a function of load due to voice packets under MMPP/M/1 queue system. Equations 9 and 12, 11 and 14 are used to plot the graph. It can be observed from figure 15 that average waiting time of both voice and video packets increase with increase in load due to voice packets irrespective of whether the voice packets are delayed or not. It can further be observed that video packets experience a higher improvement in performance as a result of reduced average waiting time, for example, at the load of 0.4 the average waiting time is reduced by 0.0028 seconds while the increase in average waiting time of voice packets at the same load is increased by 0.001 seconds. A similar trend is observed at a load of o.6 where the reduction in average waiting time of video packets is 0.014 while the increase in average waiting time of voice packets is 0.005 seconds. It can also be observed that voice packets can be delayed to serve video packets as long as the load due to voice packets does not exceed 81%.

Figure 16 shows a graph of average waiting time of voice and video packets as a function of arrival rate of voice packets under MMPP/M/1 queue system. Equations 9 and 12, 11 and 14 are used to plot the graph. It can be observed from figure 16 that average waiting time of both voice and video packets increase with increase in arrival rate of voice packets regardless of whether the voice packets are delayed or not. It can further be observed that video packets experience a higher improvement in performance as a result of reduced average waiting time, for example, at the arrival rate of 5 packets/second the average waiting time is reduced by 0.005 seconds while the increase in average waiting time of voice packets at the same arrival rate is increased by 0.004 seconds. A similar trend is observed at a arrival rate of 10 packets/second where the reduction in average waiting time of video packets is 0.03 while the increase in average waiting time of voice packets is 0.02 seconds. It can also be observed that voice packets can be delayed to serve video packets as long as the arrival rate of voice packets does not exceed 14 packets/second.

4.7 Tradeoff in improvement in performance of video packets and degradation in service of voice packets under MMPP/BP/1

The study investigates the tradeoff in improvement in performance of video packets against the degradation in performance of voice packets in terms of average waiting time as a function of load and arrival rate under the MMPP/BP/1 queue system.

Figure 17 shows a graph of average waiting time of voice and video packets as a function of load due to voice packets under MMPP/BP/1 queue system. Equations 17 and 17, 20 and 20 are used to plot the graph. It can be observed from figure 17 that average waiting time of both voice and video packets increase with increase in load due to voice packets regardless of whether the voice packets are delayed or not. It can further be observed that video packets experience a higher improvement in performance as a result of reduced average waiting time, for example, at the load 0.4 the average waiting time is reduced by 0.0025 seconds while the increase in average waiting time of voice packets at the same arrival rate is increased by 0.0008 seconds. A similar trend is observed at a load of 0.6 where the reduction in average waiting time of video packets is 0.014 while the increase in average waiting time of voice packets is 0.004 seconds. It can also be observed that voice packets can be delayed to serve video packets as long as the load does not exceed 81%.

Figure 18 shows a graph of average waiting time of voice and video packets as a function of arrival rate of voice packets under MMPP/BP/1 queue system. Equations 17 and 17, 20 and 20 are used to plot the graph. It can be observed from figure 18 that average waiting time of both voice and video packets increase with increase in arrival rate of voice packets regardless of whether the voice packets are delayed or not. It can further be observed that video packets experience a higher improvement in performance as a result of reduced average waiting time, for example, at arrival rate of 5packets/second the average waiting time is reduced by 0.003 seconds while the increase in average waiting time of voice packets at the same arrival rate is 0.004 seconds. A similar trend is observed at arrival rate of 10 packets/second where the reduction in average waiting time of video packets is 0.02 while the increase in average waiting time of voice packets is 0.017 seconds. Note also that voice packets can be delayed to serve video packets as long as the arrival rate does not exceed 15 packets/second.

5 CONCLUSION

This study proposes an improved LLQ algorithm which delays voice packets that arrive while the video packets are already in the queue and services video packets as long as the voice packets are not delayed beyond the maximum tolerable delay limits. The algorithm is modeled using the MMPP/G/1 queue system. Two special cases of MMPP/G/1 are used, that is, MMPP/M/1 and MMPP/BP/1 which exhibit correlated arrivals and exponential and Bounded Pareto service times respectively. We developed analytical models which enables us to investigate the trade-offs existing between the increase in delay experienced by voice packets as a result of delay and the delay reduction experienced by video packets as a result of delaying voice packets. The numerical results obtained from the derived models show that delaying voice packets leads to reduction in the average waiting time of video packets and an increase in the average waiting time of voice packets, however the reduction in average waiting time of video packets is higher than the increase in the average waiting time of voice packets. Furthermore, the voice packets can be delayed to serve video packets as long as the load and arrival rates of voice packets does not exceed 81% and 14 packets/second respectively.

REFERENCES

[1] P. Jumnani, M. Zaveri, "A Novel Cross-Layer Architecture for Video Streaming Over MANET," in Proc. Ninth International Conference on Wireless Communication and Sensor Networks, 2014.

[2] M. Veeralakshmi, R. Pugazendi, "Depiction of Routing Protocols in Mobile Adhoc Networks: Behaviour Analysis," in International Journal of Com puter Science and Mobile Computing. Volume 2(8), August 2013, pp.96-101.

[3] K. Bora, "Efficient Use of Resources in Mobile Ad Hoc Networks", (Ph.D. dissertation, University of Rochester, New York), 2013.

[4] K. Wallance, "Authorized Self-Study Guide-Cisco Voice over IP (CVOICE)", Cisco Press, 2010.

[5] K. Semeria, "Supporting Differentiated Service Classes: Queue Scheduling Disciplines", Juniper Networks, Inc, 2001.

[6] H. Tetsuji, "Analysis of Multiclass Feedback Queues and its Application to a Packet Scheduling Problem," Journal of Industrial and Management Optimization, Volume 6(3), 2010, pp.541-568.

[7] B. Dekeris, T. Adomkus, and A. Budnikas, "Analysis of QoS Assurance Using Weighted Fair Queueing (WFQ) Scheduling Discipline with Low Latency Queue (LLQ), in Proc. International Conference on Information Technology, Jun. 2006.

[8] P. Rukmani, R. Ganesen, "Enhanced Low Latency Queueing Algorithm for real Time Applications in Wireless Networks," International Journal of Technology, Volume 7(4), 2016. pp. 663-672.

[9] L. Kleinrock .Queueing Systems, Volume I & II. Computer Applications. John Wiley & Sons, 1976..

[10] E. Glenbe, G. Pujolle, J.C. Nelson, "Introduction to Queuing Networks," John Wiley and Sons, 1987.

[11] B. K. Asingwire, M. Okopa, T. Bulega, "Modeling Performance of VoIP Traffic over 802.11 Wireless Mesh Network Under Correlated Inter-arrival Times," In the International Journal of Digital Information and Wireless Communications (IJDIWC), Volume 6(2)May 2016. pp. 122-138.

[12] W. Fischer, K. Meier-Hellstern, "The Markovmodulated Poisson process (MMPP) cookbook". Proceedings of the Performance Evaluation, volume 18(2), Sep. 1993, pp. 149-171.

[13] B. Ciciani, A. Santoro, P. Romano, "Approximate Analytical Models for Networked Servers Subject to MMPP Arrival Processes," Proceedings of The 6th IEEE International Symposium on Network Computing and Applications, 2007.

[14] N. Gans, G. Koole, A. Mandelbaum, "Telephone Call Centers: Tutorial, Review, and Research Prospects," Proceedings of the Manufacturing & Service Operations Management, volume 2(5), 2003.

[15] A. O. Allen, "Probability, Statistics and Queuing Theory, with computer Science Applications," Academic Press, Boston., 2nd edition, 1990.

[16] H. Li, M. Muskulus, L. Wolters, "Modeling Job Arrivals in adata-intensive Grid," Proceeding of the 12th Workshop on Job Scheduling Strategies for Parallel Processing, 2006.

[17] ITU-T Recommendation G.114, "International telephone connections and circuits-General Recommendations on the transmission quality for an entire international telephone connection," ITU-T GSERIES RECOMMENDATIONS, 2003.

[18] P. Rohal1, R. Dahiya, P. Dahiya, "Study and Analysis of Throughput, Delay and Packet Delivery Ratio in MANET for Topology Based Routing Protocols (AODV, DSR and DSDV. In the International Journal for Advance Research in Engineering and Technology. Volume 1(II). 2013, pp. 54-58.

[19] R. Kumar, M. Misra, A. K. Sarje, "A Simplified Analytical Model for End-To-End Delay Analysis in MANET," In nternational Journal of Computer Applications-IJCA, 2010, pp. 195-199.

[20] P. I. Basarkod, S. S. Manvi, "On-demand QoS and Stability Based Multicast Routing in Mobile Ad Hoc Networks," In International Journal of Electronics and Telecommunications, Volume 60(1). 2014, PP. 27-39.

Kakuba Samuel (1), Kyanda S. Kaawaase (2), Michael Okopa (3)

Makerere University (1,2), Cavendish University Uganda (3)

samuelkakuba@yahoo.com (1), kswaibk@cis.mak.ac.ug (2), okopamike@gmail.com (3)

Caption: Figure 1. Improved Low Latency Queuing scheduling algorithm

Caption: Figure 2. The state transition diagram for an M/M/1 queue. Adopted [9]

Caption: Figure 3. Average waiting time of voice packets under MMPP/M/1 as a function of load due to voice packets

Caption: Figure 4. Average waiting time of voice packets under MMPP/M/1 as a function of arrival rate of voice packets

Caption: Figure 5. Average waiting time of video packets under MMPP/M/1 as a function of load due to voice packets

Caption: Figure 6. Average waiting time of video packets under MMPP/M/1 as a function of load due to video packets

Caption: Figure 7. Average waiting time of video packets under MMPP/M/1 as a function of arrival rate of voice packets

Caption: Figure 8. Average waiting time of video packets under MMPP/M/1 as a function of arrival rate of video packets

Caption: Figure 9. Average waiting time of voice packets under MMPP/BP/1 as a function of load due to voice packets

Caption: Figure 10. Average waiting time of voice packets under MMPP/BP/1 as a function of arrival rate of voice packets

Caption: Figure 11. Average waiting time of video packets under MMPP/BP/1 as a function of load due to voice packets

Caption: Figure 12. Average waiting time of video packets under MMPP/BP/1 as a function of load due to video packets

Caption: Figure 13. Average waiting time of video packets under MMPP/BP/1 as a function of arrival rate of voice packets

Caption: Figure 14. Average waiting time of video packets under MMPP/BP/1 as a function of arrival rate of video packets

Caption: Figure 15. Average waiting time of voice and video packets under MMPP/M/1 as a function of load due to voice packets

Caption: Figure 16. Average waiting time of voice and video packets under MMPP/M/1 as a function of arrival rate of voice packets

Caption: Figure 17. Average waiting time of voice and video packets under MMPP/BP/1 as a function of load due to voice packets

Caption: Figure 18. Average waiting time of voice and video packets under MMPP/BP/1 as a function of arrival rate of voice packets
Table 1. implementation parameters Next, the performance of
voice packets before and after delay is investigated. In
doing this, the changes in average waiting time with increase
in load and arrival rate are determined.

Parameter                                 Value

Service time, [mu]                 10ms
Load, [rho]                        Oto 0.9
Transition states                  two
Arrival rate                       0 to 25 packets/sec
[P.sub.1]                          0.17
[P.sub.2]                          0.08
[[lambda.sub.1]                    22.10 requests/sec
[[lambda.sub.2]                    7.16 requests/sec
Co[V.sup.2] for BP distribution    0.53 [15]
COPYRIGHT 2017 The Society of Digital Information and Wireless Communications
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2017 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Samuel, Kakuba; Kaawaase, Kyanda S.; Okopa, Michael
Publication:International Journal of Digital Information and Wireless Communications
Article Type:Report
Date:Apr 1, 2017
Words:9922
Previous Article:Dynamic Optimization of IEEE 802.11 DCF based on Active Stations and Collision Probability.
Next Article:Mining Top-T Web Traversal Subsequences.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |