Analysis and Implementation Genetic Algorithms on Random Early Detection

Analysis and Implementation Genetic Algorithms on Random Early Detection

Prima Hernandia¹, Hendrawan¹

¹,² Sekolah Tinggi Elektro dan Informatika, Institut Teknologi Bandung
Jl. Ganesha no. 10, Bandung, Indonesia

¹primahernandia@gmail.com

²hend@stei.itb.ac.id

Abstraksi— Application requirements for delay and low jitter has driven the development of Active Queue Management (AQM) is very fast. Random Early Detection (RED) as one of the AQM has grown so rapidly and become a reference for the development of other AQM variants. RED to be fast growing because of its simplicity and ease to modified its parameter. There have been many studies that discuss the development of RED, but very few have focused on finding value, the weights for the optimal packet drop probability. In this study we tried to offer a different approach to the search values ​​using genetic algorithms. This is done to adapt the possible values ​​ dynamically according to the character of traffic.

Keywords— RED, value, dynamic traffic, genetic algorithms.

I. Introduction

This Active queue management (AQM) has grown so rapidly by using a different approach. Generally aims to improve the performance of Transmission Control Protocol / Internet Protocol which has been recommended by the Internet Engineering Task Force (IETF) for the next generation router. In RFC 2309 [1] one of the goals is to maximize throughput AQM received by the user. The approach to AQM can be classified on the basis of the solution space search, as follows:

Table I-1 AQM Classification

illustration not visible in this excerpt

Active Queue Management was first introduced by using the addition of bits of ECN as a mechanism of preventive control of the congestion. These control bits are not doing any calculations, but only as a status that is marked on the package to be dropped when congestion occurs. The use of ECN bits first introduced by the Network Working Group RFC in the recommendations. Currently what happens is congestion on the network transport layer was detected on. In the paper [2], the author gives a suggestion that congestion should be detected before a buffer overflow and packet should be dropped. ECN RFC proposes the addition of two bits in IP header to indicate the occurrence of congestion. Proposed solution with addition of ECN bits can not be directly implemented, at least there are some considerations, there are Routers that do not support the ECN mechanism must have the ability to support migration to ECN, congestion control mechanisms that exist should still be used. In the RFC states that reserved addition of 2 bits (6 and 7) is used to indicates status of the packet flow. The use of these bits is as follows:

Table I-2 ECN Bit Indicator

illustration not visible in this excerpt

If the received packet with ECN code 11 and packet will be dropped, then the congestion window to be halved. Mechanisms used to avoid data loss during transmission by providing prior notification before congestion occurs.

Different approach was done by using Drop Tail as described in [3]. Authors in [3] provides a simple solution to deal with congestion on the router. We used to know that Drop Tail is naive handling of overflow traffic. If the packet is coming and it will be queued unserved prior in long queues with static queue, the queue when it comes unhandled again so the next packet will be dropped. It is occur when the arrival time is much faster than the router service time.

FIFO approach such as the Drop Tail buffer overflow condition is very prone to global synchronization, which dropped packets from different connections. Conditions of global synchronization, causing the window size decreases and the impact on the overall throughput. This is a concern in the paper [3] with the development of mechanisms of Random Early Detection (RED) to avoid congestion. The main focus of the development of this mechanism is to maintain long average queue in the router keep it short. This is made ​​possible by a specific packet drop or mark placed in the queue exceeds certain limits. Queuing system by using RED queue defining and as upper and lower limits. At the time the package arrived, this system will calculate of the incoming flow and compared with and . values ​​updated every new package comes with the formula: , where the value is weight of the average queue length before and is a current queue length at this time.

If exceed then the packet is marked, whereas if the value is between and then the probability of packet marker can be searched with the following formula: where the value of count is the number of packets since last packet is marked. defined as follows: . Packet characterized by the probability , in this case the count is reset. If the package is not marked, then the count will increase. This mechanism allows the average queue length can be controlled and avoid congestion.

RED still has limitations with parameters that are static. Floyd, Gummadi, and Shenker in the paper [4] did a little modification to the RED. Adaptive-RED mechanism capable of adapting to changes in parameters of RED based on the existing situation. The parameters used in the RED Adapative similar to those used previously. RED randomly discarding packets with a probability according to the average queue length. Only congestion and parameter setting has an effect on the balance between link utilization and delay the rendah.ARED as described in [4], the parameter adaptation to reduce the packet loss rate and variance of queue length.

In the previous RED development is emphasized to regulate the average queue length so that variance is not too volatile, fairness issues remain unresolved as well. In the paper [5] The issue was raised, Stabilized RED (SRED) is developed by taking into account the current flow. The number of active flows recorded (zombie list), each zombie list can consist of more than one entry per flow. Counter value of independent, not dependent on any list though zombies represent the same flow. If the new package and then the zombie corresponding counter value increases, if the opposite occurs according to the probability of the identifier of the zombie rewritten with the identification of a new package and the counter value at reset.

Managing of different traffic flow is also become main focus in paper [6], constraints on the RED which is not fair sharing of bandwidth in different traffic. RED does not consider to bandwidth utilization of related current flow will do drop packets. FRED on paper [6] proposed to utilize the bandwidth per flow to reduce the loss of each flow, resulting in overall bandwidth utilization. The main purpose of FRED is to provide a different strategy to drop packets of different flows. The new parameters used in the model queue. and represent the number of packets of flow i is accommodated in the buffer. and is the maximum and minimum size of an average size of the buffer. is the current number of packets in flow i and is the average size of the buffer in the system.

If the paper [6] handling of packet drop done by looking at the behavior of current flow and does not depend on previous conditions, different approaches conducted in paper [7] through the RED-Preferential Dropping (RED-PD), the mechanism is to use the previous and dropping notes identify a flow that uses a large bandwidth. When the detected on the record, dropped packets have a relationship with a certain flow over the next packet is chosen to be dropped. RED-PD is only active when there is not enough bandwidth is sufficient for all the flow and do drop certain packets to be normal bandwidth.

At the time of arrival of packets, detect whether the system violates the bandwidth limitation, in the event that the packet will be dropped based on the specific flow characteristics. If no violation is detected, then the probability limit bandwidth drop to comply with the usual RED.

[...]

^[1] Braden B, Clark D, Crowcroft J, Davie B, Deering S, Estrin D, Floyd S, Jacobson V, Minshall G, Partridge C,Peterson L, Ramakrishnan K, Shenker S, Wroclawski J, Zhang L. Recommendations on queue management and congestion avoidance in the Internet. RFC 2309, April 1998.

^[2] K. Ramakrishnan, S. Floyd, and D. Black. RFC 3168, The Addition of Explicit Congestion Notification (ECN) to IP. 2001.