Implementation of Hybrid-RED Algorithm for Effective Congestion Avoidance in MANETS

Mobile Ad hoc Network (MANET) is a “self-configuring network of mobile routers connected by means of wireless links that have no central base station (no access point) and share the wireless medium”[1]. MANET is autonomous in nature. Autonomous in the sense that these mobile devices are capable of moving independently and thus organizing themselves arbitrarily. Congestion takes place within the system environment at the point when the totaled asset requests surpass the accessible limit. Due to this congestion, packet gets lost as a result of waiting in the network in a queue and the throughput may diminish and the delay occurred while travelling the path may increase. In MANETS, since there is an absence of a fixed infrastructure, no separate network elements called routers are present and therefore each and every mobile node themselves behave as the routers i.e. they are accountable for routing the packets. Thus congestion avoidance is very much important in MANET in view of the particular properties like limited resources, multi-hop routing and low bandwidth. Active Queue Management is a well-known technique for Congestion Avoidance in MANETS. The key idea behind AQM is to react to the initial congestion before buffer overflows. It detects congestion by typically monitoring the instantaneous or average queue length.

AQM schemes can be classified [2] into three major categories according to the metrics used for congestion. They are Congestion metric without flow information, Congestion metric with flow information and only flow information. Here flow information refers to the information about the incoming flow whether it is responsive or unresponsive or misbehaving flow. These are further classified as follows: Queue Length Based: It is used as a metric to identify congestion so that the control point lies in balancing the queue length. Ex: RED, DS-RED, MRED, HRED, LRED, FRED, CHOKe etc. Load Based: Determines congestion by predicting the link utilization. Ex: Yellow, AVQ, SAVQ, EAVQ, SFED, FABA, LUBA. Queue Length and Load Based: In order to gauge congestion, several AQM methods incorporate the consolidation of queue length based and information rate. Ex: REM, SVB.

This AQM algorithm belongs to the category of Congestion metric without flow information and Queue Length Based scheme. Hybrid-RED is proposed as a combination of MGF-RED and REDD algorithms. In this work MGF-RED’s best feature i.e., Gaussian Function dropping probability and REDD’s best feature i.e., queue space utilization has been

Packet Delivery Ratio as well as Packet Drop.

The rest of this paper is organized as follows: Section II reviews the related work that has been carried out. Section III describes Hybrid-RED algorithm which is a combination of MGF-RED and REDD algorithms. Section IV gives the Implementation of Hybrid-RED algorithm.

Active Queue Management (AQM) is a mechanism which avoids the network congestion with specific end goal to ensure an acceptable level of service to every user. It implies that the switch here attempts to decrease the rate of data transmission of the traffic originators by either packet dropping or marking. Two methods to illustrate congestion are dropping or marking packets. Variety of AQM algorithms were proposed and implemented in the routers to prevent the congestion. Various AQM algorithms that come under the classification of congestion metric without flow information and queue based are discussed in this section. They are based on packet drop probability for congestion avoidance. Sally Floyd and Van Jacobson [3] presented a method named Random Early Detection (RED) in 1993 that aims congestion avoidance. Here two thresholds namely minimum and maximum thresholds are used. When the average queue length (aql) is less than minimum threshold no packets are dropped. If average queue length crosses minimum threshold some packets are dropped and if average queue length crossed maximum threshold all packets are dropped. Although it solved “lockout” and “global synchronization” problem, it suffered from low throughput because of linear dropping function. Bing Zheng and Mohammed Atquizzamen [4] in 2000 presented a mechanism called Double Slope RED that aims congestion avoidance. The key idea in this work is that here there are two predefined thresholds Kl and Kh for a gateway buffer segment. This segment is partitioned further into two sub segments isolated by Km. As a result of that the comprehensive dropping function from Kl to Kh is circumstantiated by slopes α and β respectively. But faced the problem of parameter sensitivity and same problem as that of RED. W.-C. Feng, D.D. Kandlur, D. Saha, and K.G. Shin [5] presented a concept called Self Configuring RED. An algorithm called Self Configuring RED is developed and implemented by varying maxp (maximum drop probability) parameter taking into consideration minimum and maximum thresholds. Disadvantage of this approach is that it acquaints a few new parameters to accomplish execution. Framing these extra parameters leads to complications sometimes. Chonggang Wang, Jiangchuan Liu, Bo Li, Kazem Sohraby, and Y. Thomas Hou [6] in 2007 presented a mechanism named LRED( Loss Ratio Based RED). LRED for the estimation of clogging or congestion uses the ratio of recent packet loss as a supplement to the queue length. LRED estimates the ratio in every measurement period (tm) for stability. Disadvantage is that (tm) must be carefully configured. In the event that it is too little, the estimation could be incorrect; yet in the event that it is too enormous, the reaction time can be longer. Yanping Zhang, Jun Ma, Yongcheng Wang and Chao Xu in [7] presented a mechanism called Modified RED. This work is based on the inference that the queue that is present in the router is nonlinear. Idea is that, increment in computed average queue size also increments drop probability by means of nonlinear affinity. Trial results have demonstrated that with the identical parameter arrangement, vigorousness of the nonlinear RED calculation is superior to RED's. Here end to end delay is more. Hussein Abdel-jaber, Fadi Thabtah, Amjad M Daoud, Jafar Ababneh, Mahmoud Baklizi [8] presented a mechanism called Gentle RED (GRED). To deal with the drawbacks of RED, GRED was presented as an alternative to RED, where GRED enriches the approach of fine-tuning few of the RED’s parameters such as maximum threshold and Dmax. Also, GRED keeps up the average queue length esteem at a level on a switch cradle which is between the minimum and maximum positions, this level is named Taql. It has satisfactory mean queue length and satisfactory average queuing delay under heavy congestion.

We have implemented a Hybrid-RED algorithm that incorporates the best features of both MGF-RED and REDD algorithm. A. MGF-RED Algorithm In this mechanism, an AQM algorithm called MGF-RED [9] (Modified Gaussian Function) is used which is a slight modification to an existing system RED. Here the conventional RED’s packet dropping probability function is being replaced by the new Modified Gaussian Function. As an aftereffect of this, MGF has fewer packet drops. The calculation of

Step 1: Calculate the average queue length Step 2: if average queue length< minimum threshold then enqueue the packet Step 3: if average queue length > minimum threshold and < maximum threshold then calculate packet drop probability using Modified Gaussian probability. Step 4: if average queue length> maximum threshold then drop the packet. Step 5: Exit The MGF-RED packet dropping probability function formula is given in equation (1) P = a * v_a –x + d (1)

where x = (avg_len-b)2 / 2c2

avg_len is the average queue size and is given by: avg_len= q_len * Wq and Wq is the queue weight and is constant value provided at the time of simulation. Where P is new packet drop probability v_a and v_b are constant and are given by v_a = 1 / maxth-minth v_b = minth / maxth-minth a = cos2 (theta) + sin2 (theta) b = -sin (2*theta) + sin (2*theta) c= sin2 (theta) + cos2 (theta) theta = v_a * avg_len + v_b B. REDD Algorithm RED’s performance may deteriorate as aql increases as and when the number of sources adds on. This may also lead to the average queue length crossing the defined maximum threshold. As a result, every arriving packet will be dropped. In order to solve this issue, REDD [10] (Random Early Dynamic Detection) is used, where the idea of a versatile maximum threshold is utilized keeping in mind the end goal to recognize and control the congestion. REDD [10] figures the aql like RED and contrasts the aql with the already specified minimum as well as maximum threshold positions. On the off chance that at least double the minimum threshold, REDD lessens the maximum threshold value by 2. This will take the aql towards its corresponding target value. Then again, if the aql lies between the target value and the maximum threshold and furthermore if the value of maximum threshold is lesser than or equal to the difference of the router buffer capacity and the minimum threshold, then automatically the maximum threshold value will be incremented by 2. This is performed so that the aql will be balanced at the objective value (target value) and the throughput outcome may increase thereby giving 2 more space for the maximum threshold. The REDD algorithm works in the following steps: Step 1: Calculation of the average queue length Step 2: Calculate target value which is the half way between two specified thresholds. Step 3: If value of target greater than average queue length and maximum threshold more than or equal to 2* minimum threshold then decrease maximum threshold by 2. Step 4: If average queue length > target and less than (router buffer capacity - minimum threshold) then increase maximum threshold by 2 Step 5: Exit In this project an algorithm called Hybrid-RED is proposed as a combination of MGF-RED and REDD algorithms. In this work MGF-RED’s best feature i.e., Gaussian Function dropping probability and REDD’s best feature i.e., queue space utilization has been extracted and incorporated. As a result it provides better network execution in terms of throughput, Packet Delivery Ratio as well as Packet Drop. C. Hybrid-RED The Hybrid-RED algorithm works in the following steps: Step 1: Average queue length calculation. St. Step 2: Calculation of both minimum as well as maximum threshold values. St. Step 3: if the value of average queue length is littler than the minimum threshold value then packet gets enqueued i.e., drop probability=0. Step 4: In the event that the average queue length has greater value than minimum and lesser value

Step 5: if average queue length< target and maximum threshold >= 2* minimum threshold then decrease maximum threshold by 2 and calculate dropping probability using MGF-RED dropping probability formula. Step 6: If average queue length > target and less than (router buffer capacity - minimum threshold) then increase maximum threshold by 2 and calculate dropping probability using MGF-RED dropping probability formula. Step 7: If average queue length crosses queue size then drop all packets. Step 8: Exit

Implementation includes all those activities that take place to convert from the old system to the new. The new system may be totally new, replacing an existing system or it may be major modification to the system currently put into use. Here RED algorithm is taken as the base algorithm and few modifications have been implemented in terms of efficient queue space utilization and effective packet dropping function.

Here language used is OTcl for front end and C++ for back end. Platform used is FEDORA 15 and the simulator used is Network Simulator-2.35. The Hybrid-RED architecture is shown in the below Figure 1. Hybrid-RED architecture gives the overall working of the combined approach in MANETs. Source node is the node from which the packets are being sent, intermediate nodes acts as routers to forward the packet to the destination node. AQM policy is being employed in the intermediate node, after each packet arrival at the intermediate node the computation of the required average queue length is performed. The figured out average queue length value is then evaluated with the minimum and maximum threshold values and adaptive threshold policy is implemented to utilize queue space effectively. The MGF dropping function comes into picture when the value of average queue length lies in the middle of these minimum as well as maximum thresholds.

Initially the procedure calculates the throughput, PDF and End to End delay for RED algorithm. Then the same procedure is repeated for the modified Gaussian function based RED and Hybrid-RED i.e. the proposed algorithm. The simulation results shows that the proposed algorithm give the better network recital in requisites of throughput, PDF and delay. In the simulation comparison of existing algorithm with the proposed algorithm has been done. The simulation parameters are shown in table 1.

Parameter Value Routing Protocol AODV Number of Nodes 30 Area 1128 m*100 m Packet Size 1000b Simulation time 30s Traffic Pattern CBR Some of the important parameters defined in Hybrid-RED algorithm along with their initial values are as shown below Minimum Threshold = 15 packets Maximum Threshold = 45 packets Queue Size = 60 packets Mean packet size = 1000 bytes

Cur_max_p = 0.05

The results have been obtained by using the NS-2.35 simulator and results shows that our proposed algorithm performs better than traditional RED and MGF-RED algorithm in terms of throughput, packet delivery ratio and packet drop rate.

It may be defined as the total amount of data received by destination from the source node divided by time taken to receive the last packet. Figure 2 shows the Simulation Time (X-Axis) versus Throughput (Y-Axis) of HYBRID-RED, MGF-RED and RED. It has been clear from the figure that the proposed algorithm (HYBRID-RED) gives the higher throughput than the Traditional RED. The simulation is carried out for 30sec. Once the average queue size crosses the minimum threshold value, packet drop takes place in order to avoid congestion hence in that case throughput gradually flows down and once packet drop remains constant even the throughput remains constant.

It is the total number of packets received by destination to total number of packet sent by source. Figure 3 shows the simulation time (X-Axis) versus packet delivery ratio (Y-Axis) of HYBRID-RED, MGF-RED and RED. The graph shows that initially PDR is more as there is no packet drop. When the avg crosses the minimum threshold value, packet drop increases gradually for getting away from congestion; in that case PDR gradually decreases. When the packet dropping reduces, thereafter slightly PDR increases and when packet drop remains constant then PDR also remains constant.

It may be defined as the total number of sent and forwarded packets minus the received packets. Figure 4 shows the packet drop comparison of RED, Hybrid-RED and MGF-RED. Here X-axis shows the simulation time and the Y-axis shows the Packet drop. Because of adaptive maximum threshold policy number of packets dropped in Hybrid-RED is less when compared to the other two. In RED around 2600 packets are dropped, in MGF-RED around 2200 and in Hybrid-RED around 810 packets are dropped

Congestion detection and congestion avoidance becomes a major problem in MANETs due to its specific characteristics like dynamic topology, frequent path breaks, limited buffer space, limited battery power etc., To overcome the above mentioned drawbacks, various AQM algorithms like

Hence it works well for prefixed network scenarios like the wired networks. To overcome these disadvantages of RED, Hybrid-RED is implemented as a combination of MGF-RED and REDD algorithms. Hybrid-RED makes use of dynamic adjustment policy of maximum threshold according to the current traffic conditions. This dynamic threshold adjustment policy is designed to regulate the maximum packet dropping probability using average queue length. The Hybrid-RED algorithm also changed the linear dropping function of RED. The implemented algorithm is compared with RED and MGF-RED by using NS-2 simulations. The experimental results demonstrated that Hybrid-RED outperforms RED and MGF in terms of network throughput, packet delivery ratio and packet dropping probability. Also Hybrid--RED does the efficient utilization of queue space.

Mr. Raja, Capt. Dr. S Santhosh Baboo, “An Overview of MANET: Applications, Attacks and Challenges”, International Journal of Computer Science and Mobile Computing, Vol.3 Issue.1, pg. 408-417, January- 2014. K.Chita, Dr. G.Padmavati, “Classification and Performance of AQM-Based Schemes for Congestion Avoidance”, International Journal of Computer Science and Information Security, Vol. 8, No. 1 ,pp. 331-340, 2010. S. Floyd and V. Jacobson, “Random early detection gateways for congestion avoidance”, IEEE/ACM Transactions on Networking, vol.1, no.4, pp. 397, August- 1993. Bing Zheng and M. Atiquzzaman,“DSRED: An Active Queue Management Scheme for Next Generation Networks”, In Proceedings of the 25th Annual IEEE Conference on Local Computer Networks LCN ’00,Washington, DC, USA, 2000. IEEE Computer Society. W.-C. Feng, D.D. Kandlur, D. Saha, and K.G. Shin, “ A Self- Configuring RED Gateway”, In Proceedings of IEEE INFOCOM ’99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies, volume 3, pp. 1320–1328, Mar 1999. Chonggang Wang, Jiangchuan Liu, , Bo Li, Kazem Sohraby, and Y. Thomas Hou, “LRED: A Robust and Responsive AQM Algorithm Using Packet Loss Ratio Measurement”, IEEE transactions on parallel and distributed Yanping Zhang, Jun Ma, Yongcheng Wang and Chao Xu, “MRED : An Improved Nonlinear RED Algorithm”, International Conference on Computer and Automation Engineering (ICCAE 2011),IPCSIT vol. 44, 2011. Hussein Abdel-jaber, Fadi Thabtah, Amjad M Daoud, Jafar Ababneh, Mahmoud Baklizi, “Performance Investigations of Some Active Queue Management Techniques Using Simulation”, International Journal on New Computer Architectures and Their Applications (IJNCAA) 2(1), pp. 286-301, 2012. Makul Mahajan, Tanu Preet Singh, “The Modified Gaussian Function based RED (MGF-RED) Algorithm for Congestion Avoidance in Mobile Ad Hoc Networks”, International Journal of Computer Applications (0975 – 8887) , vol. 91, April 2014. Hussein Abdel-jaber, Fadi Thabtah, Mike Woodward, Ahmad Jaffar, Hussein Al Bazar, “Random Early Dynamic Detection Approach for Congestion Control “,Baltic J. Modern Computing, Vol. 2, No. 1,pp. 16-31,2014.

PES Institute of Technology and Management/CSE, Shivamogga, India