Implementation of An Autonomic Active Queue Management in Mobile Ad Hoc Network (MANETs)

Implementation of An Autonomic Active Queue Management in Mobile Ad Hoc Network (MANETs)

G.Naveen, M. Tech Student, and Mr. D. Sharath Babu Rao, Faculty

Depart ment of Electronics & Co mmunication Engineering Jawaharla l Nehru Technological Un iversity

Anantapur, India

Abstract

In order to provide better quality of service to the multimedia applications in Mobile Ad Hoc Network (MANETs), where its resource is limited and changed dynamically, in this paper we introduce an Active Queue management mechanism with autonomic attributes, named Autonomic Active Queue Management (AAQM). With the rapid development of network services and network technologies, the users requirements of network mainly the QoS are to improve. Whereas the traditional Active Queue Management (AQM) mechanisms are not adequate to provide QoS guarantee to multimedia video traffics effectively. AAQM tries to adjust its network behaviour and optimize the overall network performance according to network and service condition information.

1. Introduction

   Autonomic network is a research hot spot in future architectures. By introducing the autonomic features to network entities we can solve the increasing comple xity of network control and management. Therefo re, we can introduce these autonomic mechanisms to Diffserv components, by that it can optimize the network performance by adaptively adjusting the network behaviour in accordance with the real-time condition informat ion.

   With the widely mu ltimed ia applicat ions in MANETs, it is expected to provide the better quality of service. However, the present IP network is not capable to provide QoS to meet the require ments of real-time video flow. Packet losses have serious impact on compressed video streams. Protecting the video data fro m packet loss

   is an important concept in QoS field. But it is difficult to prevent the packet loss to a very low level using traditional packet dropping control technologies. Moreover, even a very small pac ket loss may damage the video stream quality [1]. A ma in proble m is how to protect the perceived video quality in spite of e xisting packet loss.

   These queue management mechanisms are re lative ly effective in reducing packet loss by dropping the packets randomly. But in MPEG4 encoded mult imedia applications, there is no simple relat ion between packet loss and video quality perceived at the receiver. Due to the dependency between the video fra mes, even a small packet

   loss may cause many successively delivered packets with no use in practice, wh ich will seriously impact the video quality. To reduce the loss of video stream delivery quality and effectively drop video packets, we will introduce autonomic mechanism to queue manage ment mechanis m, dynamica lly ad justing the discarding operation according to the network environment and video or service feature informat ion.

   There are t wo majo r approaches for to provide better QoS ma inly for video applicat ions. They are end system based approach and network based approach respectively. In the end system based approach, the provision of QoS is depends on end system. But it increases the overhead and comple xity of the end systems greatly. In the network based approach, the provision of QoS is main ly depends upon the routers.

   As a mechanism to support congestion control at intermediate routers , Sally Floyd [1] firstly proposed an default AQM scheme i.e., Random Early Detection. IETF RFC2309 [2] suggested to adopt AQM mechanis m at routers, which become a research hotspot. The basic idea of AQM is to avoid congestion problem before the buffer is full by means of randomly dropping packets in advance.

2. Background

   The concept of autonomic network is derived fro m autonomic co mputing and communicat ion [3] & [9]. The ma in goal of this mechanism is to add autonomic attributes to network ele ments, simp lifying the network manage ment and control. Autonomic attributes such as self- configuration, self-adaptability, self-manage ment, self- aware and self-optimization are realized based on feedback control loop. The autonomic mechanisms can dynamica lly adjust network behaviour in accordance with the real-t ime network environ ment and optimize the overall network performance.

   A mong the end system based and network based approaches, the end system based approach is relatively effective, but the comple xity and overhead of end system are increased greatly. So, therefore it is expected to adopt the simp le and effective queue management approach to provide QoS by network based approach. Most AQM mechanis ms where they drop the packets randomly

   without diffe rentiating their importance. The trad itional queue management without considering the packets importance is not suitable for multimedia flow, wh ich will damage the video flow quality severely.

   In [4] & [6], a rate based RIO algorithm, na med Rb-RIO, is proposed. It classifies packets of I fra me , P fra me and B fra me to three priority classes. I fra me packet has smaller drop probability compared with other packets. [5] proposed a priority dropping mechanism, wh ich mapped I fra me , P fra me and B fra me packets of MPEG4 hierarchica l v ideo flow a rchitecture to different drop priorities of WRED, which is called REDN3.

3. Weighted Random Early Detection

   Congestion avoidance techniques monitor network traffic loads in an effort to anticipate and avoid congestion at common network and inter-netwo rk bottlenecks before it becomes a problem. These techniques are designed to provide preferentia l treat ment for p re miu m (p riority) c lass traffic under congestion situations while concurrently ma ximizing network throughput and capacity utilizat ion and minimizing packet loss and delay. Congestion avoidance is achieved through packet dropping. Among the more co mmonly used congestion avoidance mechanis ms is Weighted Random Early Detection (WRED), which is optimu m for high-speed transit networks.

   Weighted random early detection (WRED) is a queue management algorith m with congestion avoidance capabilit ies, where d ifferent queue (class) has different queue thresholds. Each queue threshold is associated to a particular IP p recedence. For e xa mp le : A queue may have lower thresholds for lo wer priority packet and higher thresholds for higher priority traffic. A queue build up will cause the lower priority packets to be dropped, hence protecting the higher priority packets in the higher priority queue.

   Packet Arival

   Average queue size calculated

   < Min Threshold > Max Threshold

   >Min & <Max Threshold

   The packet drop probability is based on the minimu m threshold, ma ximu m threshold, and mark probability denominator. When the average queue depth is above the min imu m threshold, WRED starts dropping packets. The rate of packet drop increases linearly as the average queue size increases until the average queue size reaches the maximu m threshold. When the average queue size is above the ma ximu m threshold, all packets are dropped.

   Figure 2, depicts the graphical representation of packet drop probability vs. average queue size for two types of traffic (lo w priority traffic and high priority traffic). The low prio rity traffic has lower value for minimu m and ma ximu m thresholds compared to higher priority traffic. Hence at times of congested traffic, the drop rate for lower priority traffic will be higher compared to higher priority traffic . WRED para meters inc luding minimu m threshold, ma ximu m threshold and drop profile can be adjusted as per the requirement of different types of traffic.

   Figure 2. WRED Packet Drop Probability

   The available queue manage ment Weighted RED (WRED) [7] & [8] algorith ms which is able to diffe rentiate packet priorities. But the priorit ies are not simp lified based on the video packets importance.

4. Autonomic Active Queue Management

   The above queue management technique with diffe rentiating video packet importance usually just takes into account the difference of fra me type. Where it mapping the packets to different dropping priorities according to fra me type and ma intaining fixed para meters for respective priority may not leads to obtain desired optima l performance. We should ma ke full use of the

   Compulsory Pass

   Drop/Pass as per Drop Probability

   Compulsory Drop

   packet feature information caused by the video encode process to optimize the queue manage ment operation.

   So in order to overcome the above problem, we introduce the autonomic mechanism to our queue manage ment design. Autonomic attributes mainly the self-

   Figure 1. W RED Algorithm Flow Diagra m

   adaptation and self-configuration are realized base on feedback control loop. Where it is based on context

   informat ion collected. And the context information used in our mechanis m inc ludes network context and service context. We use the context information to dynamica lly configure and adjust the packet dropping operation.

   The self-configuration and self-adaptation autonomic attributes are realized base on a feedback loop. In the feedback loop, the network and service context is collected through the collecting step. Then the configuration is determined based on the service context. And the congestion level is judged according to the network conte xt info rmation. Fina lly e xecute corresponding configuration and adjustment. The feedback loop will optimize the overall network performance and adaptively adjust the network behaviour .

   The service context informat ion is recorded in the packet header according to their video co mpression character by source end. When the packet travels in network, nodes are able to abstract the service context informat ion directly fro m packet header. The service context informat ion, for e xa mple video compress character informat ion, such as frame type, fra me situation and frame size are abstracted from the IP packet header, and it will determine the configuration of the queue management mechanis m para meters. Network environ ment conditions will change with time dynamically. The length of nodes queue is changing according to traffic rate and link bandwidth. The queue management mechanism will collect this network context informat ion to judge the congestion condition. Network context in formation is monitored by wireless nodes.

   1. Implementation of Source operation:

      M PEG encodes video as a sequence of fra mes. Usually, v ideo has a high degree of te mporal redundancy, i.e., informat ion in successive frames is highly correlated. Standard MPEG encoders generate three types of compressed frames (I, P, or B). An I fra me is intra-coded, having no dependence on any other frames. Meanwhile, MPEG uses motion pred iction and interpolation techniques to reduce the size of intermed iate fra mes. Two types of motion prediction are used: Forward prediction, where a previous frame is used as a reference for decoding the current fra me , and bidirectional prediction, where both past and future fra mes are used as a reference.

      This technique provides a better compression. The encoding of P fra mes uses forward predict ion and the encoding of B fra mes uses bidirectional pred iction. As a consequence, the I fra mes are norma lly the la rgest in size, followed by the P fra mes, and finally the B fra mes .

      The video sequence may be decomposed into smaller units which are coded together. Such units are called GOPs (Group of pictures). Each GOP holds a set of fra mes or pictures that are in a continuous display order.

      Usually GOPs are made independently decidable units to facilitate rando m access. Such GOPs are called c losed GOPs as they contain all relevant decoding parameters so that it can be decoded independent of other units. If a GOP needs other GOPs for decoding, it is called an open GOP.

      The GOP pattern specifies the number and te mporal order of P and B fra mes between two successive I fra mes. Such a GOP pattern is characterized by two p arameters: the I-to-I fra me d istance (N) and the I-to-P fra me d istance (M). This structure and the dependency for decoding of each fra me in such GOP pattern is illustrated in Figure 3.

      GOP

      I1 B1 B2 P1 B3 B4 P2 B5 B6 P3 B7 B8 I2

      Figure 3. GOP Structure (N = 12 and M = 3)

      The hierarch ical structure of MPEG encoding with possible error propagation through the frames imposes a great difficulty on sending MPEG v ideo streams over lossy networks. Sma ll packet loss rates may translate into much higher fra me error rates. For exa mp le, a 3% packet loss percentage could translate into a 30% fra me error. This situation may seriously degrade the user perceived quality at the video reproduction. Moreover, network resources may be wasted with the transmission of information that becomes useless to the receiver. So me of the received data may beco me useless to the decoder as insufficient fra me data is available for decoding. Such situation may occur either when there a re losses in the network or when some fra me in wh ich the current fra me depends on to be considered decodable is considered undecodable.

      To imp rove the transfer of co mprehensible informat ion, we associate different leve ls of drop precedence to packets that carry informat ion of different fra mes. Under this scheme, increasing drop precedences are associated with packets from I, P, or B fra mes, respectively. That is, packets transporting fragments of a B fra me are more likely to be discarded in a congested router than packets from P fra mes. Meanwhile, P fra me packets have precedence in discard when compared to I fra me packets.

      We can get the frame importance comparison result in each GOP. I fra me is the refe rence fra me to a ll the fra mes in the GOP, so I fra me has the highest importance. P fra mes at the front part has higher importance than the P fra mes at the rear part in each GOP. P and B fra me is encoded with prediction encoding, its data amount almost reflects the approximat ion between the B fra me and the

      prediction fra me . Therefo re, we can consider that B fra me with larger size is more important than smalle r one. In summary, the frames in each GOP ordered by importance fro m high to low are I fra me , the P fra me at the front part, the P frame at the rear part, B fra me with large size, and B fra me with sma ll size respectively.

      The service context informat ion means the character information generated by the video compression, including video fra me type, fra me nu mber, fra me size and so on.

      Precedence	Type of Packet	Precedence inde x(PI)
      Class A	Packet carrying I fra me data in GOP	001
      Class B	Packet carrying the forme r part P fra me data in GOP	010
      Class C	Packet carrying the latter part P fra me data in GOP	011
      Class D	Packet carrying la rger size B fra me data in GOP	100
      Class E	Packet carrying sma ller size B fra me data in GOP	101

      TABLE 1: PA CKET PRECEDENCCE MAPPING

      The character information wh ich is generated by the source video codec is recorded into the packet header. We add several fie lds into the IP header, including fra me type, the number of P fra me in GOP, the ma x P fra me nu mber, B fra me size and the ma x B fa me size, na med f_type, f_seq, PN, f_size and BS respectively. For f_type filed, 0 means I fra me , 1 means P fra me, and 2 means B fra me. The number of P fra me is the P fra me pred icted sequence number in GOP, wh ich is between 1 and PN. And the f_size fie ld records the B fra me size.

      The source end divides the video packets into five priorities according to the video compression character informat ion. Additionally we add another filed into IP header, named PI (p riority inde x). The priority divid ing table is shown in table I. The packet importance decreases fro m c lassA to classE.

   2. Implementation of Queue management:

The collecting operation of autonomic loop monitors the queue length to estimate the network congestion situation. The average queue length and real time queue length are used as congestion metric. The interface queue of wireless node for video packets is a FIFO queue in our design. But in the internal queue structure, packets are directly mapping to five virtual queues (VQ) according to their prio rity inde xes (PI) recorded by the source end. Packet drop priority increases fro m VQ1 to VQ5. The algorithm uses the highest drop

priority dropping method. If packet dropping needed, the arriving packet will enter into its corresponding virtual queue, and the first packet of the highest drop priority virtual queue will be dropped. Parameters in the WRED queue Management algorithm a re static. The parameter ma xp is set as a fixed value. But in our design, the ma xp is able to adjust according to the packets service context Information. The origina l ma xp for I, P and B fra me are ma xp_i, ma xp_p and ma xp_b respectiv ely. But the ma xp_p is able to be adjusted according to the P frame number. The ma xp is adjusted according to P number as

maxp = maxp_i + (maxp_ p maxp_i) * a * (No./PN)

And the ma xp_b is adjusted according to the B frame size, as

maxp = maxp_ p + (maxp_ b maxp_ p) * b * (PS/size)

Where a & b are s ma ll constant values.

If the average queue length qavg is less than the small threshold minth, then enter the arrival packet into the queue. If qavg is between the two thresholds, then calculate a drop probability, enter the arrival packet, and discard the drop target packet with the probability. The probability calculated is the drop probability of the first packet of the highest drop priority virtual queue. If qavg is larger than the large threshold ma xth, then enter the arrival pac ket to its corresponding queue, and drop the first packet in the highest drop priority virtual queue.

PSEUDO-CODE OF AAQM ALGORITHM

Calcu late the average queue length qavg and get the current queue length qcur mapping the arrival packet to corresponding virtual queue according to Precedence Index (PI).

//adjusting the ma xp para meter & ca lculate the drop probability

1. if the arrival packet carry ing I fra me data

2. ma xp = ma xp_ i

3. e lse

4. if the arrival packet ca rry ing P fra me data

5. ma xp = ma xp_ i + (ma xp_p ma xp_ i) * a * (No./N)

6. e lse

7. ma xp = ma xp_p + (ma xp_b ma xp_p) * b * PS/size

8. if ((qavg >= ma xth) || (qcur = qlim ))

9. enter the arriva l packet to its corresponding virtual queue drop the packet with h ighest drop priority

10. e lse

11. if (qavg < minth )

12. enter the arrival pac ket into its corresponding virtual queue

13. else

14. pb = ma xp * (qavg minth ) / (ma xth minth)

15. randomize a number u,

16. if ( u<= pb )

17. enter the arriva l packet to its corresponding virtual Queue drop the packet with highest drop priority

18. e lse

19. enter the arriva l packet into its corresponding queue

Fixed Pa ra meters:

Minth: minimu m threshold for queue Maxth: ma ximu m threshold for queue Maxp: ma ximu m va lue for pb

Saved Variables:

qavg: average queue size

qlim: ma ximu m value of queue size pb : Packet marking probability qcur: current queue size

1. Simulation Results

   1. Simulation Specifications:

      Simulator : MATLAB

      Topology : MANETs topology

      Number of nodes 10

      Radio Transmission Range : 300m

      Simulation time : 100 sec and 30 sec Area of the Network : 500m*500m Routing Protocol : DSDV

   2. Simulation Results :

      In this part, we use simu lation to compare the performance of the proposed AAQM algorithm with WRED in MANETs scenario. The queue management algorith m is applied on the wire less interface queue.

      The re are 10 wire less nodes move randomly in a given 500×500 m2 square. Video sequences are in the 4:2:0 YUV format. We encoded the video into MPEG4 formatted file , and transmitted through the wire less network. Fina lly co mpare the file afte r transmission with the original file, and ca lculate the PSNR(Peak Signal-to- Noise Ratio) va lue. PSNR is one of the most widespread objective metrics to assess the application-level Qo S of video transmissions. Node communication radius is set as 300m. Routing protocol uses DSDV.

      The two queue manage ment algorithms are simu lated using the same para meter va lue. WRED is used as [5] described, video packets are divided into three priorities according to their fra me type.

      The simu lation MANETs topology, including original topology and final topology after simu lation, are illustrated in Fig.4. We send video flow and background

      traffic at wire less node 4. And wire less node 5 is the destination node. The moving tracks of the two nodes are also presented. For simp lic ity, we o mit the other wire less nodes.

      WN: Wireless Node SWN: Source Wire less Node DWN: Destination Wireless Node

      Figure 4: The original and final topology with the moving tracks of the source and destination nodes.

      1. Scenario1:

         We trans mit the video flow fro m the source node to the destination node.

         The two algorithms are simulated with the same scenario separately. And then analyze PSNR of the video. The PSNR results of .yuv formatted video file using AAQM and WRED a re shown in Fig.5.

         Fra me index

         Figure 5: PSNR of v ideo flow in scenario-1

         At most time AAQM protects packets with higher importance effective ly, avoiding the severe degradation of PSNR. The average PSNR of AAQM is 25.80dB, wh ile WRED is 21.81dB.

         Figure 6: screen snapshots of AAQM (le ft) and WRED (right)

         The co mparison of screen snapshots of .yuv formatted video file is shown in Fig. 6. Le ft is got by AAQM, and right is got by WRED. The average throughput of AAQM is 0.1402Mb/s, while the WRED is 0.1408Mb/s. When the throughputs of the two algorithms are almost the same, AAQM are obviously better than WRED. The loss of less important packet only has effect on a few fra mes near it. But the loss of important packet affects a series of fra mes. AAQM can protect more important video packets better than RED.

         5.2.2 Scenario2:

         In th is scenario, we add background UDP flow between wire less nodes. We use a longer video sequence to analyze. The UDP background flo w lasting fro m the start of simu lation to the end with 4M sending rate, and the background video traffic is added at the intermedia ry time. The UDP background flow is assigned to the two higher priorities with proportion of 7:3 in WRED. While the background UDP flo w is assigned to VQ 1 to VQ3 with proportion of 7:1:2 in AAQM likewise.

         The PSNR results of. yuv formatted video file using AAQM and WRED are shown in Fig.6. The average PSNR of AAQM is 24.12dB, and the average PSNR of WRED is 20.18dB.

         Figure 7: screen snapshots of AAQM (le ft) and WRED (right)

         The comparison of screen snapshots of .yuv formatted video file is shown in Fig.7. Le ft is got by AAQM, and right is got by WRED. Fro m fig. 6 we find that, AAQM protects important vido packets more effectively than WRED. The background video flow was added at the intermediate to add the traffic load. The AAQM has higher PSNR than WRED at the most time.

2. Conclusion

   Th is paper proposes an autonomic Active Queue Management (AAQM) mechanis m to improve the

   mu ltimed ia video flo w delivery quality. We introduce

   autonomic attributes to queue management algorith m. The mechanis m is capable of configuring and adjustin g dynamica lly accord ing to network and service context informat ion. The simulat ion co mpared the performance of the proposed AAQM with WRED when transmitting MPEG4 formatted video flow. The result shows that AAQM can protect important video packets and reduce the impact of packet loss on video quality effective ly

3. Acknowledgme nt

   Naveen would like to thank Mr. D. Sharath Babu Rao, who had been guiding through out to complete the work successfully, and would also like to thank the HOD, ECE Depart ment and other Professors for extending their help& support in giving technical ideas about the paper and motivating to complete the work effectively & successfully.

   Fra me index

   Figure 6: PSNR of v ideo flo w in scenario-2

4. References

1. S. Floyd, V. Jacobson. Random early detection gateways for congestion avoidance. IEEE/ACM Transactions on Networking, IEEE/ACM , vol. 1, August 1993, pp. 397-413.

2. B. Braden, D. Clark, J. Crowcroft, Recommendations on

   Queue M anagement and Congestion Avoidance in the Internet, IETF RFC 2309, IETF, April 1998.

3. J.Kephart, D. Chess, The Vision of Autonomic Computing, IEEE Computer, vol. 36, January 2003, pp.41 50.

4. J. Chung, M . Claypool. Rate-Based Active Queue M anagement with Priority Classes for Better Video Transmission, Proceedings of the Seventh International Symposium on Computers and Communicaitons, ISC C, July 2002, pp.99-105.

5. A. Ziviani, J.F. Rezende, Improving the Delivery Quality of MPEG Video Streams by Using Differentitated Services. 2nd European Conference on Univeral M ultiservice Networks(ECUMN) 2002.

6. D.Clark, W. Fang, Explicit allocation of best-effort packet

   delivery service, IEEE ACM Transactions on Networking, IEEE, vol. 6,August 1998, pp.362-373.

7. Technical Specification from Cisco, Distributed Weighted Random Early Detection, online available at http://www.cisco.com/univercd/cc/td/doclproducsoftware/io/ wred.pdf

8. U. Bodin, O. SchelCn, S. Pink, Load-tolerant Differentiation with Active Queue M anagement, ACM Computer Communicaitons Review, ACM , vol. 30, July 2000, pp.4-16.

9. S. Dobson, S. Denazis, etc., A survey of autonomic communications, ACM Transactions on Autonomous and Adaptive Systems, ACM, vol. 1, December 2006, pp.223- 259.

Authors Profile

G.Naveen received B.Tech Degree in Electronics & Co mmun ication

Eng ineering fro m Madanapalle

Institute of Technology and Science, Madanapalli, Kurnool, India . Presently he is pursuing his M. Tech in Dig ital Systems & Co mputer Electronics specialization in the

Depart ment of Electronics & Co mmun ication

Engineering fro m Ja waharla l Nehru Technological University, Anantapur, India. His research interests include Wire less Co mmunications, Co mputer Networks and Electronics and Co mmunications .

Mr. D. Sharath Babu rece ived his B.Tech Degree in Electronics & Co mmunicat ion Engineering fro m Sri Krishna Devaraya Engineering college, gooty, India. And he received his Master of Engineering (ME) fro m Os mania Un iversity, Hyderabad. Presently he is pursuing his Ph.D in "VLSI Imple mentation of

Gigabit Ethernet MAC" in the Depart ment of ECE, fro m

JNTU Anantapur, India. He is presently working as a Lecturer in the Department of Electronics & Co mmunicat ion Engineering, JNTU Un iversity, Anantapur. His research interests include VLSI and Wireless Co mmunicat ions.