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 w_q value, the weights for the optimal packet drop probability. In this study we tried to offer a different approach to the search w_q values using genetic algorithms. This is done to adapt the possible values w_q dynamically according to the character of traffic.
Analysis and Implementation Genetic Algorithms on Random Early Detection
Prima Hernandia1, Hendrawan1
1,2 Sekolah Tinggi Elektro dan Informatika, Institut Teknologi Bandung
Jl. Ganesha no. 10, Bandung, Indonesia
1primahernandia@gmail.com
2hend@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.
Frequently Asked Questions About "Analysis and Implementation Genetic Algorithms on Random Early Detection"
What is the main focus of the study?
The study focuses on using genetic algorithms to find optimal values for the weights of packet drop probability in Random Early Detection (RED). This is done to dynamically adapt the values according to the characteristics of traffic.
What is Random Early Detection (RED) and why is it important?
RED is an Active Queue Management (AQM) technique used in routers to prevent congestion. It proactively drops packets based on the average queue length, aiming to maintain a short queue and avoid global synchronization problems.
What are the limitations of traditional RED?
Traditional RED uses static parameters, which may not be optimal for varying traffic conditions.
How does the study propose to improve RED?
The study proposes using genetic algorithms to dynamically adjust RED parameters, specifically the weights for packet drop probability, to adapt to changes in traffic patterns.
What is Active Queue Management (AQM)?
AQM aims to improve the performance of TCP/IP by managing queues in routers. This is often achieved by dropping or marking packets before the queue overflows.
What problem does Drop Tail queuing cause?
Drop Tail is a naive queuing method where packets are dropped when the queue is full. This can lead to global synchronization, where multiple connections experience packet loss simultaneously, reducing overall throughput.
What is ECN and how does it relate to AQM?
Explicit Congestion Notification (ECN) is a mechanism that allows routers to signal congestion to the sender by setting bits in the IP header, without dropping packets. This allows the sender to reduce its transmission rate proactively.
What are some other AQM variants mentioned in the text?
The text mentions Adaptive-RED (ARED), Stabilized RED (SRED), and FRED as variations of RED that address limitations of the original algorithm. These variations focus on aspects like fairness, queue stability, and bandwidth allocation.
What is the purpose of the tables in the text?
Table I-1 provides a classification of AQM approaches, while Table I-2 illustrates ECN bit indicators and their meaning.
What are and in the context of RED?
and represent the minimum and maximum thresholds, respectively, for the average queue length in RED.
What is the "count" value used for in RED?
The "count" value tracks the number of packets that have arrived since the last packet was marked or dropped. It is used in determining the packet drop probability when the average queue length is between and .
- Arbeit zitieren
- Prima Hernandia (Autor:in), 2012, Analysis and Implementation Genetic Algorithms on Random Early Detection, München, GRIN Verlag, https://www.grin.com/document/192774
