Comparative Study of Link Utilization, Queue, Delay and Loss Characteristics of Active Queue Management Schemes in Wireless Networks

Comparative Study of Link Utilization, Queue, Delay and Loss Characteristics of Active Queue Management Schemes in Wireless Networks

Shivanand V Manjaragi

Sr. Lecturer, CSE Department,

Hirasugar Institute of Technology, Nidasoshi-591236, Karnataka, India.

Abstract

Congestion control mechanism is one of the key that keeps any network efficient and reliable for the users. Many mechanisms were proposed in the literature over the years for the efficient control of congestion that occur in the network. Active Queue Management (AQM) is one such mechanism, which provides better control in the recent years. Over the last decade numerous AQM schemes have been proposed in the literature. However, much recent work has focused on improving AQM performance through alternate approaches. This study focuses on an unbiased comparative evaluation of the various proposals. The evaluation methodology adopted is the following: we first briefly introduce the queue, delay, and loss characteristics a subset of network characteristics that can be used to describe the behavior of network entities. Next, we present a method based on the NS simulation technique and simulation-based comparisons of AQM schemes chosen, which will help to understand how they differ from in terms of per-node queuing information in wireless (Wireless LAN) networks.

Keywords: Congestion control, AQM, QoS, WLAN.

1. Introduction

   The Internet and wireless technologies have experienced tremendous development and network technologies have been revolutionized in the last decade. The speed and capacity of various components in a networking system, such as transmission media, switches, and routers have been drastically increased. Millions of users and billions of traffic have introduced into wired and/or wireless networks. In addition, multimedia traffic such as audio and video have been widely delivered. As Internet traffic volume continues to grow, network congestion is more likely to occur and it becomes more challenging to provide good throughput i.e. Quality-of-Service (QoS) to millions of Web users under congestion. When multiple input

   streams from a number of senders arrive at a router whose output capacity is less than the sum of the inputs, the router can be congested. Bursty traffic and flash crowds cause congestion. As the number of users and the size of the Internet increase, users are likely to experience more packets loss, longer delay and other performance degradation due to congestion [3].

   The rapid development of wireless communications in recent years has imposed great challenges for network support. As most current networking protocols were designed mainly for wired networks, many assumptions that make these protocols efficient in wired networks are no longer true and cause severe performance degradation in wireless environment. An urgent task for todays networking research is to identify such deficiencies and to enhance these protocols.

   While wireless networks provide mobility and convenience to users, the quality of service and efficiency of todays wireless networks are still far from satisfactory. Conversations may be cut off when mobile subscribers travel between cells. Wireless data connections have high bit error rates, low bandwidth and long delays. Many wireless local area networks achieve only a small portion of the advertised peak bandwidth.

   In order to understand the origin of these problems, we need to know the differences between wired and wireless media. Wireless communications come in many forms and span a large range of throughput and distances. The world of wireless data includes fixed microwave links, wireless LANs, ad-hoc networks, sensor networks, satellite links, digital dispatch networks, diffused infrared, laser-based communications, the Global Positioning System and more. In addition to its wide range of forms, wireless media is essentially different from traditional wired media in the following ways. First, the available bandwidth of the wireless media is limited and shared by many users, and overall throughput is therefore much lower than that of wired media. A typical category 5 unshielded twisted-pair (UTP) cable can deliver 1 Gbps bandwidth in Gigabit networks, but a

   typical wireless WAN in GSM is designed for 9600 bps per user. In wired networks, laying more cables yields more bandwidth, so the bandwidth of wired media can be expanded infinitely. On the other hand, the bandwidth of wireless media is limited by the available radio spectrum. The allocation of the spectrum is normally controlled by government agencies. While radio spectrum experts are looking for ways to encode more bits in the spectrum, the available spectrum remains limited. In this sense, the wireless bandwidth cannot be expanded infinitely.

   Second, wireless media is shared. Competition for the shared medium causes access contention. If not coordinated properly, the access contention can result in low efficiency and unpredictable channel access delay. Third, wireless media is prone to transmission errors. Variable conditions in the natural environment, multi-path reflection, noise, channel interference and fading affect the signal transmission and lead to high bit error rates.

   Some of the low QoS problems of wireless networks are due to the limitations of the wireless media. Wireless networks cannot achieve the same level of bandwidth and quality of service as wired networks. However, many of these problems are the result of incorrect underlying assumptions that were made based on wired networks that do not hold true in wireless networks. Most existing networking protocols were designed when the networks were composed solely of wired links. These protocols made assumptions about the characteristics and operation of the underlying media. While these assumptions improved efficiency in wired networks, they do not apply to wireless links. Continuing to use these assumptions in heterogeneous networks that consist of wired and wireless links causes poor performance. With the rapid development of wireless networks, identifying the causes of poor performance and enhancing the current protocols has become an urgent task.

   Depending on the network architecture, we can investigate the congestion control problem in three different types of wireless networks including Wireless LANs, Ad-hoc Networks, and Sensor Networks but using AQM. We can address congestion problem in Wireless LANs.

   1. Wireless Local Area Networks

      The architecture of a typical wireless local area network (WLAN) is shown in Figure 1.1.

      In this figure, a mobile host is communicating with a host (either a server or a workstation) in a fixed network connected to the Internet. The key components in this architecture include the mobile host, the base

      stations, the wired gateway and the Internet. The mobile host can be a mobile telephone, a PDA, or a laptop computer with a wireless modem. The base station is a stationary collection of hardware components that communicate with nearby mobile hosts through radio media. The geographical area covered by a base station is called a cell. A cellular system typically consists of thousands of cells, each with its own base station. Together these cells cover a large region, such as a metropolitan area or an entire country. All communication with mobile hosts is through the radio channel between the mobile host and the base stations. The radio channel consists of a downlink and an uplink. The downlink is broadcast from the base station to all mobile hosts in the cell. The access to the uplink is normally shared by all mbile hosts. The base station is responsible for scheduling the access to the media and for resolving contentions using a media access control protocol. Therefore, it is often called an access point (AP).

      Fig. 1.1 Wireless Local Area Network Architecture

      The gateway is a network element that sits one or more hops away from the access point to provide mobility, security and QoS support. All traffic in-out of the access point is routed through this gateway, with some sort of tunneling/NATing mechanism if the gateway is server based and multiple hops away from the access point. Next hop gateways are switch based and provide the same services as server-based gateways. Switch-based solutions can also supply power-over-Ethernet (POE) to the access point. Another overriding concern in wireless deployments is cost. As access points get loaded with functionality, they get more and more expensive, thereby making radio coverage provisioning in an enterprise very expensive. An alternative architecture, called light weight access points, is again the use of a gateway in which the bulk of networking functionality is provided by a gateway, limiting the access point to do basic

      802.11 channel access along with simple bridging to

      802.2 frames. Features like QoS, mobility, security, management, location services etc. are supported in the gateway which can handle more than one access-port.

      The economies of scale deliver significant cost benefits for medium and large scale deployments.

      Since the actually available bandwidth in wireless networks is much smaller than the bandwidth in wired

      loss rate

      total number of dropped packets total number of input packets

      networks, there is a difference of speeds in channel capacity which makes the access point a significant network congestion point in the downstream direction. Due to the shared nature of wireless media, for TCP sessions, such congestion will also introduce unfairness between downlink and uplink traffic between the wireless and wired domains. A current architectural trend in wireless local area networks (WLAN) is to move functionality from access points to a centralized gateway in order to reduce cost and improve features. In this, we applied the AQM to queues at the access point inorder to achieve improved.

2. Network Performance Metrics

   The performance of AQM in this investigation is evaluated by network performance indicators. The performance measures[1] used in this investigation such as utilization, throughput, and average queue Length in a router, queueing delay, and packet loss rate are defined in this section.

   Throughput is defined as the rate at which the packets are sent by a network source in megabits/sec (Mbps).

   Throughput is calculated by the formula

   total number of bytes transmitted

3. Active Queue Management (AQM)

   schemes

   The order in which the packets are to be processed is determined by the congestion avoidance and packet drop policy called Active Queue Management at the node. The main purpose of AQM is to provide congestion information for sources to set their sending rates.

   A description of the basic schemes for IP network

   [2] including DropTail, RED, REM, PI, FQ, SFQ, and DRR and present analytic models of their dropping (or marking) probability is given bellow.

   1. Drop Tail (FIFO)

      Drop tail, commonly used in most Internet routers, implements first-come-first-served (FCFS) queueing and drop-on-overflow buffer management. The first packet that arrives at a router is the first packet to be transmitted. If a packet arrives at a router whose outgoing link queue is full, then the router discards the packet regardless of which flow the packet belongs to or how important the packet is.

      Throghput

      timeinterval

   2. Random Early Detection (RED)

      Link Utilization is defined as the fraction of link capacity being used for transferring data. Utilization can be expressed as a decimal point between 0 and 1 or as a percentage (%).Utilization is calculated by the formula

      (databits x 100)

      Utilization( %)

      (bandwidthx interval)

      Queue length is defined as the number of packets in the queue for a router outgoing link and is considered as an important performance measurement related to delay.

      Queuing Delay is the delay between the point of entry of a packet in the transmit queue to the actual point of transmission of the message. This delay depends on the load on the communication link.

      Loss The simplest way to quantify loss is by calculating the overall loss rate, which is equal to the total amount of lost traffic divided by the total amount

      RED[4] was presented with the objective to minimize packet loss and queuing delay, to avoid global synchronization of sources, to maintain high link utilization, and to remove biases against bursty sources. To achieve these goals, RED utilizes two thresholds, minth and maxth, and a exponentially-weighted moving average (EWMA) formula to estimate the average queue length, Qavg = (1-Wq)·Qavg+Wq ·Q, where Q is the current queue length and Wq is a weight parameter, 0 Wq 1.The two thresholds are used to establish three zones. If the average queue length is below the lower threshold (minth), RED is in the normal operation zone and all packets are accepted. On the other hand, if it is above the higher threshold (maxth), RED is in the congestion control region and all incoming packets are dropped. If the average queue length is between both a threshold, RED is in the congestion avoidance region and the packets are discarded with a certain probability Pa:

      of input traffic over the a certain period of time. Because we use a constant packet size in our simulation, the loss rate can be expressed as

      Pa

      Pb

      (1- count.Pb)

      This probability is increased by two factors. A counter is incremented every time a packet arrives at

      the router and is queued, and reset whenever a packet is dropped. As the counter increases, the dropping probability also increases. In addition, the dropping probability also increases as the average queue length approaches the higher threshold. In implementing this, RED computes an intermediate probability Pb,

      maxp

      Pb .(Qavg minth) maxth minth

      Whose maximal value given by maxp is reached when the average queue length is equal to maxth. For a constant average queue length, all incoming packets have the same probability to get dropped. As a result, RED drops packets in proportion to the connections share of the bandwidth.

   3. Random Exponential Marking (REM)

      REM[5] (Random Exponential Marking) maintains a variable, price to measure congestion. Price is updated periodically and determines the marking probability based on rate mismatch and queue mismatch. Rate mismatch is the difference between input rate and link capacity, and queue mismatch is the difference between queue length and target. When either the input rate exceeds the link capacity or the queue length is greater than target queue length, the weighted sum is positive. When the number of users grows, the input rate mismatch and queue mismatch increases, raising price and finally marking probability. When the source rates are small, the mismatches become negative, reducing price and marking probability. REM stabilizes queue length around a small target.

   4. Proportional Integrator (PI)

   While RED uses average queue length, PI (Proportional Integrator) uses instantaneous queue length and regulates queue length to a desired queue reference value (qref). The drop probability of PI is proportional to queue length mismatches. The difference between the current queue length and a desired target queue length, and difference between a previous queue length and a desired target queue length determines drop probability and the drop probability is accumulated. That is, weighted subtraction of the previous queue msmatch from current queue mismatch is added to the previous drop probability. If the result of the subtraction is positive, drop probability gets larger than previous drop probability and smaller otherwise. Figure 3.1 gives the basics of the PI algorithm.

   qref is a desired queue reference value and qlen is an instaneous queue length. P and qlen are saved for the next PI drop probability calculation. By adjusting drop

   probability based on queue length, PI keeps queue length close to the desirable target queue length and maintains a stable queue length. Moreover, it prevents the queue in a router from overflowing.

   PI coeffieients : a = 0.00001822, b = 0.00001816 Once every period

   Calculate probability P with qref and qlen

   P = a * ( qlen qref ) – b * ( qold qref ) + Pold drop(P)

   Pold = P

   qold = qlen

   PI coeffieients : a = 0.00001822, b = 0.00001816 Once every period

   Calculate probability P with qref and qlen

   P = a * ( qlen qref ) – b * ( qold qref ) + Pold drop(P)

   Pold = P

   qold = qlen

   Fig 3.1 PI Algorithm

4. Simulation Methodology and tools

   This includes NS-2 (Network Simulator)[9], simulation input and output traces, data extraction and analysis, experimental setup and validations, and simulation scenarios with simulation network topology and simulation design specification. The experiments in this study are performed through procedure. The simulation script written in OTcl is run in NS-2 and trace files are generated as a result of the simulation. The data is extracted from the trace files and is plotted in a graph to analyze the performances. The simulation process is presented in Figure 4.1.

   Fig 4.1 NS2 Simulation process

   1. NS-2 Network Simulators

      The Network simulator version 2 (NS-2), written in C++ and Otcl, is an object oriented, and discrete event driven network simulator. NS-2 developed as the VINT (Virtual Inter Network Tested) project at Lawrence Berkeley National Laboratory (LBL), Xerox PARC, the University of California, Berkeley, and the University of Soutern California/ISI and is mainly used in the network research community. NS-2 simulates a variety of IP networks and including network protocols such as TCP, and UDP (User Datagram Protocol), traffic source behavior such as FTP, Telnet, Web, CBR and VBR, router queue management mechanisms such as Drop Tail, RED, PI and AVQ. NS-2 also supports

      simulation of TCP, routing, and multicast protocols over wired and wireless (local and satellite) networks.

   2. Simulation Input

      To run a simulation in NS-2, configuration and behaviors expected to be simulated are described in the form of an OTcl script. Basically, the topology is defined and nodes, agents, applications are instantiated and attached in the input script. These simulation objects in OTcl script are mirrored in classes in C++, the compiled hierarchy. The applications such as FTP, and Telnet traffic sources and the traffic distributions such as CBR (Constant Best Rate), Pareto, and exponential are specified. The start time and end time of the simulation are set in the script. During the simulation time, the events are generated and scheduled by time. Each event includes a packet arrival from a source to a router queue, drop, enqueue, dequeue, an arrival at a destination, a generation of an ACK packet, and timeouts. The input script also sets trace files keeping track of packets and other specific information such as instantaneous queue length.

   3. Simulation Output Traces

      The simulation is traced during the simulation time by using trace objects and monitor objects. The monitor objects collect data for basic information about the simulation. For example, the monitor objects are implemented as counters to count total number of packets, drops, and bytes received. In contrast, the trace objects collect the data for specific information. It keeps track of packets in the process of transmission and contains event number, time, source node, destination node, packet type, packet size, flow id, source address, destination address, sequence number and packet id for each packet arrival at a queue in a router, drop or en-queue, de-queue and departure. In this study, packet-based traces are needed to understand the simulation comprehensively so the data is collected by using the trace object. An output trace generated by the trace object in NS-2 has a fixed format shown in Figure 4.2

      r : receive (at to_node)

      + : enqueue (at queue)

      – : dequeue (at equeu) d : drop (at queue)

      : src addr node.port (ex. 3.0)

      : dest addr node.port (ex. 0.0)

   4. Data Extraction

      Once the simulation is done, the traced data is extracted for computation of performance metrics. The

      data extraction modules developed in C and perl generate reports on utilization, drop rate, delay and other statistical data such as drop ratio and average congestion window size for each type of flows.

      Fig 4.2 ns2 trace file output

   5. Data Analysis

      The data extracted from the traced files are fed into the data analysis tools, Gnuplot and MS excel to produce graphs based on the data. The graphs show the performance of the simulation results clearly so that the performance metrics are compared and analyzed.

5. Network topology for implementing AQM schemes in WLAN

   The simulation network topology consists of Base Station Node which is called Access Point in WLAN (802.11 MAC)[7]. Base station node creates cell for the data access in the wireless nodes, is responsible for delivering packets into and out of wireless domain. Access point is an wireless node but it must kept stationary and therefore hierarchical routing will be used to communicate with mobile nodes within its cell. WLAN should be connected to wired network; this access point is connected to fixed point node, which is acting as a gateway for the wireless and wired network. In turn this gateway is connected to a router of the wired network. There are 5 nodes connected to the router. Here all wired links are 100 Mbps and have propagation delay of 10 ms. Schematic of a Base Station Node(Access Point) is shown in Figure 5.1.

   There are 5 TCP flows are used in the simulation, each TCP source is an FTP application on top of NewReno TCP. The FTP packet size is 500 bytes.

   Flow 1: From the node S1 to mobile node M1 Flow 2: From the mobile node M2 to node S2 Flow 3: From the node S3 to mobile node M3 Flow 5: From the node S5 to mobile node M5

   First two TCP flows started at 10 sec, later three more TCP flows are added at 50sec.Buffer size at access point is 20 packets. The experiment lasts for 50 seconds of simulated time. The simulation topology is shown in fig 5.2.

   Fig 5.1 Structure of base station node

   Fig 5.2 Simulation Topology

   We have implemented the different AQM schemes such as DropTail, RED, REM and PI at the Access Point. We record queue information such as average queue length, queuing delay, loss rate, and through put.

6. Performance comparison and analysis of AQMs in WLAN

   The performance of DropTail, RED, REM, and PI is compared and analyzed in WLAN for TCP flows. For

   each discipline throughput, loss rate, queuing delay, and average queue length at access point is monitored.

   1. Through put

   2. Queueing Delay

   3. Loss rate in %

   4. Average Queue Length

   Fig 5.3 a) Throughput, b) Queueing Delay, c) Loss Rate and d) Avg. Queue length for WLAN

   In the downstream direction, Ethernet frames across the ingress and egress interfaces of the gateway and get queued up at the access point for transmission over the air. Through put with the DropTail, and PI degrades as the number of flows increases but RED maintains stable throughput as the number of flows increases. RED also shows a lower and stable packet loss rate and delay as compared to DropTail, REM and PI. RED keeps the paket loss rate under 1% regardless the buffer size.

   Also we found that when average queue length and queueing delay decreases and throughput increases, loss rate decreases.

   Above shown graphs shows RED is best AQM discipline for the wireless LAN when traffic is high at the gateway.

7. Conclusion

   Congestion control mechanism is one of the key that keeps any network efficient and reliable for the users. There are many mechanisms for congestion control, Active Queue Management (AQM) is one such mechanism. In this work, we defined and classified various network characteristics. Here the main objective was to present a method based on the NS simulation technique for the comparisons of AQM schemes, which will help to understand how they differ in terms of per-node queueing information such as link utilization, throughput, average queue length, queueing delay, and loss rate. We studied the feasibility of an AQM scheme to handle the congestion at the wireless access point (WLAN) and determined which AQM scheme is useful for WLAN.

   The performance of DropTail, RED, REM, and PI is compared and analyzed in WLAN for TCP flows.

   Throughput with the DropTail, and PI degrades as the number of flows increases but RED maintains stable throughput as the number of flows increases. RED also shows a lower and stable packet loss rate and delay as compared to DropTail, REM and PI. RED keeps the packet loss rate under 1% regardless the buffer size.

8. References

1. Lowekamp, B.Tierney, B.Cottrell, L.Hughes-Jones, R.Kielmann, T.Swany, A Hierarchy of Network Performance Characteristics for Grid Applications and Services. GFD-R-P.023, May 2004.

2. Bitorika, A.Robin, M.Huggard, M.: A Survey of Active Queue Management Schemes. Trinity College Dublin, Department of Computer Science, Tech. Rep., Sept. 2003.

3. M. Allman, V. Paxson, and W. Stevens, TCP congestion control, Request for Comments, RFC 2581, April, 2005.

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

5. D.E. Lapsley and S.H. Low, Random exponential marking for internet congestion control, in the proceedings of IEEE Globecom 1999, Dec. 1999, pp. 6674.

6. Bitorika, A.Robin, M.Huggard, M.: An Evaluation Framework for Active Queue Management Schemes. in Proc. MASCOTS 03.

7. T.Nandagopal, T.Kim, X.Gao, and V.Bharghavan,

   Achieving MAC layer fairness in wireless packet networks, in the proceedings of ACM obiCom00, Aug.2006.

8. Robert N.Shorten and Douglas J.Leith, On Queue Provisioning, Network Effficiency and TCP, IEEE/ACM Transactions on Networking, Vol. 15, No. 4, Aug 2007.

9. ns-2 network simulator, http://www.isi.edu/nsnam/ns/.

10. IEEE 802.11 standard, http://standards.ieee.org/getieee802/802.11.html.