| . | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
802.11e implementation for the ns simulator |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
1. Introduction This patch implements the new EDCF/HCF access mechanisms for 802.11 WLAN in the ns simulator. These enhancements to the Medium Access Control (MAC) have been introduced by IEEE in the draft standard P802.11e/D3.2 in order to achieve Quality of Service (QoS) guarantees. EDCF (Enhanced Distributed Coordination Function) is a contention-based channel access method, providing a distributed access to the wireless medium for different Access Categories (ACs). Each Wireless Station (WS) may have up to 8 ACs, i.e. 8 queues at MAC layer to support 8 different priorities. Each queue executes a separate access algorithm, and relative priorities among ACs are provisioned by configuring different value for the minimum and maximum value of the Contention Window (CWmin and CWmax) and for Arbitration Interframe Spacing (AIFS). Each AC within a station behaves like a virtual station, starting independently its backoff timer after sensing the medium as idle for at least AIFS. If the backoff counters of two or more parallel ACs in one station reach zero at the same time, a virtual collision will occur and access to the medium is granted to the highest priority AC. The lower priority ACs behave as if there were an external collision on the wireless medium. HCF is a controlled contention channel access method, through which the Hybrid Coordinator (HC) operating at the Quality Access Point (QAP) node of the BSSID provides contention-free channel access to the requesting Quality Wireless Stations (QSTAs) for different Access Categories (ACs). The Hybrid Coordinator grants contention-free access to a requesting QSTA by waiting a shorter time between transmissions than the stations using the EDCF or DCF access procedures and therefore gaining control of the wireless medium, then sending a QoS (+)CF-Poll to the QSTA. The reception of the QoS (+)CF-Poll frame allocates a contention-free interval, which is referrred to as the Polled Transmission Opportunity (TXOP), whose duration is defined by the QoS (+)CF-Poll itself and during which the QSTA and the HC can exchange QoS data for a selected Traffic Category. Moreover, the HC introduces a Contention Free Period (CFP) that alternates with the Contention Period (CP). During the CFP the HC follows a polling procedure and sends QoS (+)CF-Polls to all the QSTAs in its Polling List, allocating Polled TXOPs in a sequence for all the CFP duration. During the CP the EDCF contention-based access mechanism is used, but the HC can start Controlled Access Periods (CAPs) during which it can poll a limited number of requesting QSTAs. 2. Modifications to ns The patch described here includes a collection of Tcl scripts combined with some modifications to the existing ns C++ code. The Tcl scripts are discussed next. The modified C++ files are the ones listed below:
ns-2.1b9a/apps/udp.cc
Within these files, the lines of code that have been added or modified can be found by searching for the string EDCFpatch. Within these strings, the comments HCFstart and HCFend include the code relative to the HCF channel access procedure implementation.You can download the package with all the modified C++ files here The Tcl scripts define a particular network situation, including traffic agents and network topology, and also produce a statistics file at the end of the simulation. The Tcl files are the ones listed below:
You can download the package with the Tcl scripts here After the Installation, Running the 802.11e patch shows how to use this patch. The modifications to the ns simulator are described in 802.11e MAC layer and Error model, presenting the new MAC layer with the interface queue and the error model respectively. The others blocks are the sames as in the original version of the Network Simulator, therefore they are not described in this manual. The included Tcl scripts' traffic agents and network topology are shown in Traffic agents and Topology. Finally Statistics explains the structure of the output files. 3. Installation This patch requires the Network Simulator 9. After the Network Simulator installation, extract all the archive in the 'ns-allinone-2.1b9a' directory, overwriting the existing files. Then run a 'make' command into the 'ns-allinone-2.19a' directory. If any compliation error occurs, or if no 802.11e support is present at the end of the installation process, a 'make clean' command could be necessary prior running the 'make' command. 4. Running the 802.11e patch The main Tcl script is main.tcl, that is run on the command line. It creates a new instance of the Network simulator, calls the others Tcl scripts in order to create and configure the network, then runs the simulation. In order to start a new simulation, it is necessary to pass some parameters to the Tcl scripts: this can be obtained with the following instruction:ns main.tcl -par1 val1 .. -parn valn}The parameters that have to be passed to the Tcl scripts are listed below:
Each parameter must be preceded by a - symbol, while all the others tokens are assumed to be the value of the previous parameter. Some parameters will be explained with more details in the next sections. However, a demonstrative ns_802_11e_test.sh can be downloaded here.5. 802.11e MAC layer In order to realize the new EDCF access mechanism, we split the original Mac802_11 class of mac-802_11.cc in two parts. The first, still called Mac802_11, implements some operations common to each AC, while the new Mac802_11e class emulates the access algorithm of a single virtual queue with its own EDCF parameters. Since every AC needs its queue, we add in drop-tail.cc a new class, called BS_DropTail, that implements as many queues as the number of MAC ACs. Then we derived form the previous classes two new classes, still included in the mac-802_11.cc file, called Mac802_11HC and Mac802_11eHC. These new classes are the equivalent of the above ones, but they implement the MAC layer for the Hybrid Coordinator (HC); the necessity of these new classes comes from to the control role that the HC has, with respect to the wireless station, during the contention controlled periods.Another functionality available in this patch is the possibility of using a bursting transmission, which allows a virtual queue to transmit a burst of frames only separated by a SIFS period. In our implementation, each frame in the burst must be followed by an ACK frame. This mode improves the channel efficiency because only the first frame in a burst must contend for the medium. The time for which a station can consecutively send frames is limited by the txoplmt parameter, that represents the Transmission Opportunity Limit (TXOPLimit) defined in the 802.11e draft. More precisely, in our scripts the parameters {\tt wtburst} and {\tt bsburst} allow the use of two different bursting modalities:
The EDCF access parameters should be defined in topology.tcl for each AC. For example, having only 2 ACs, the following lines must be included:
set tc_par(0,aifs) 0.000150It is important to note that the larger is the numeric index of the AC, the greater is the priority of the corresponding frames. Indeed, virtual collisions are won by the virtual queue with the highest numeric index. Even if not mentioned in the draft, we diversify the Short and the Long Retry Limit (SRL, LRL) among the ACs for experimental studies. After this, for each wireless node (including the base station) and for each AC, it is necessary to configure the Interface Queue and the MAC layer by calling the following commands:
$obj(ifq,n) init-llc $opt(bsburst)init-llc, invoked on a BS_DropTail object (i.e. the Interface Queue), sets the bursting mode (0,-1 or N as explained above). init-mac informs the Mac802_11 object (i.e. the MAC layer) about the number of ACs and the value of the TXOPLimit. add-queue tells the Interface Queue to create a new queue for this AC. Finally, set-qos sets the EDCF parameters (AIFS, CWmin, SRL, LRL, CWmax) of the corresponding virtual queue.By default in this patch, TCP traffic is associated to the lowest priority (0), while CBR traffic is handled by the highest priority (1). To change these settings, it is necessary to modify the select() method of the class BS_DropTail within the file drop-tail.cc. More precisely, it is possible to modify the following lines:
switch (hdr->ptype()) {For example, when assigning the AC, it is possible to adopt others decisions based on the source/destination addresses of the frames (per-station differentiation), or based on the priority field of the IP header (like DiffServ differentiation). The maximum size of each queue is automatically configured when a node is created. It can be controlled by the bsqlen parameter for the base-station, and by ifqlen for the wireless stations. The RTS_Threshold of the MAC is fixed to 400 bytes: this value can be changed in mac-802_11.h. Furthermore, the macstandard parameter allows to simulate the original DCF 802.11b behavior. In this case only one AC is created, and the DCF parameters are set equal to the ones originally used in ns: DIFS 50µs, CWmin 31, CWmax 1023, SRL 7, LRL 4.The HCF channel access procedure is implemented in the following way. First of all it is ncessary to associate the new Mac802_11HC class to the MAC layerof the BS node, so that during the contention controlled access periods, the AP will act as Hybrid Coordinator. The wireless stations maintain instead the original Mac802_11 class. The HC coordinates the Controlled Access Periods (CAPs) and Contention Free Periods (CFPs). Therefore, in the Base Station definition are present some commands that are used to set-up these mechanisms:
$obj(mac,0) set-cap $opt(cap_interval) $opt(nccop)The set-cap command is used to define the time interval between two subsequent CAPs and the number of Contention Control Opportunities (CCOPs) provided by the HC within each CAP. cap_start, cap_stop, pcf_start and pcf_stop set the time at which the HC must start/stop the CAP mechanism and the Point Coordination Function behaviour, i.e. the CFP mechanism. This allows the HC to start CAPs and CFPs at different times with respect to the simulation start time and therefore to study the different results we have with EDCF, EDCF+CAPs, EDCF+CFPs and EDCF+CAPs+CFPs in the same simulation. Moreover, there's the possibility to disable the CAPs or the CFPs, just setting to 0 their start times: this way we can perform entire simulations using one of the above combinations. When setting these values pay attention to the fact that the product between the number of CCOPs and the TXOP limit must fit within the CAP interval, and that the time left in the CAP interval is the one used by the EDCF procedure. The following command is also used to define the HC behaviour during CFPs:
for {set k 0} {$k < $opt(num_tc)} {incr k} {This for cycle fills the HC's Polling List, that is to say the sequence of wireless stations that will be polled by the HC during the CFP. The cf-poll command takes two arguments, the wireless station's MAC address and the Access Category for which the station requires to be polled, and stores them into the Polling List. The maximum number of Wireless Stations/Access Categories elements that can be stored into the Polling List is defined in mac-802_11.h in the line:
#define MAX_CF_POLL 64
This value can be changed, remembering that its product with the TXOP limit must fit into the CFP duration, that is set again in mac-802_11.h with the following line:
#define MAC_CFPDurRemaining 0.21
We don't need such predefined Polling List during CAPs , because it is dynamically built by the HC every time, using a Contention Control (CC) frame at the beginning of the CAP, that prompts the wireless stations for Reservation Request (RR) frames containing requests to be polled for a certain AC. The maximum number of Wireless Stations/Access Categories elements that can be stored into the Polling List for CAPs is set once again in mac-802_11.h with the line:
#define MAX_RR_POLL 8
This value must at least match the number of CCOPs in each CAP. The last command introduced to handle the HCF channel access procedure is the following:
$obj(mac,$num_n) set-legacy
This must be used every time a wireless station not supporting EDCF/HCF (legacy station) is defined in a network in which EDCF/HCF stations and legacy stations are mixed. It identifies the station as a legacy station, so that it won't answer to HCF broadcast CC frames. 6. Error model Modeling the wireless channel behavior is very challenging due to the burstiness and time correlation of wireless errors. Furthermore, WLANs may experience location-dependent channel errors, in that a WS can correctly communicate with the AP, while at the same time another one may suffer from frame drops due to errors on the channel. In order to consider all these aspects, an independent error model for each communicating pair of nodes was introduced. Therefore, given N WSs, we have as a conclusion N*(N-1)/2 independent error models. Our error model is represented by a three-state discrete-time Markov chain. The Markov chain time slot is equal to the aSlotTime parameter of the 802.11b MAC, i.e., 20µs in our simulations. Errors over the channel occur in the states LONG-BAD (LB) and SHORT-BAD (SB), while the GOOD (G) state is error-free. Thus, a frame transmission is successful only if the error model is in state G for all slots it takes during its transmission, while it fails otherwise. The difference between the LB and SB states is the time correlation of errors: LB corresponds to long bursts of errors, SB to short ones. The average number of bad slots experienced when the states LB and SB are entered, are respectively given by: burstBB = 1/pbg_B burstBG = 1/pbg_G where pbg_B (pbg_G) is the transition probability from state LB (SB) to G. Similarly, the average number of consecutive error-free slots is given by: burstG = 1/pgb_G where pgb_G is the probability to leave the state G. The parameter pGB is the probability that the Markov chain moves to the LB state given that it leaves the state G; pGB also represents the probability that an error burst is long, or, in other terms, the fraction of long bursts over the total number of error bursts. The characteristics of the error model, i.e. the slot error probability, can be easily derived from the steady-state behavior of the Markov chain:
In order to compute the steady-state probabilities, the following equations system should be resolved: πLB = pgb_G pGB πG + (1-pbg_B) πLB πSB = pgb_G (1-pGB) πG + (1-pbg_G) πSB 1 = πG + πLB + πSB Solving this equation system, we can find the average error probability, i.e. the probability of having a bad slot: perr = πLB + πSB = K / (K + (pbg_B pbg_G / pgb_G)) where K = pGB pbg_G + (1-pGB) pbg_B perr is one of the error model parameters set on the command line. The other are burstBB, burstBG and pGB. The remaining three transition probabilities of the Markov chain (pGB is already know) can be computed by inverting the previous relations: pbg_B = 1/burstBB pbg_G = 1/burstBG pgb_G = (perr / 1-perr) (pbg_B pbg_G / K) All these calculations can be found in errmodel.tcl. Finally, in topology.tcl it is important to add a new error model for each pair of wireless stations, then to start the state transitions as in:
$opt(timer_list) add-timer [$obj(mac,$j) id] [$obj(mac,$k) id]7. Traffic agents The simulations support TCP traffic, UDP traffic or both. TCP flows can be activated by forcing to 1 the tcp parameter and by setting the packet size with tcp_size. The version of the TCP protocol that we use is the NewReno, which improves TCP performance during Fast Recovery. The traffic generated by TCP can be greedy if the onoff flag is set to 0, or with On-Off behavior when it is set to 1. In the former case, the transmission rate of the TCP sources is controlled only by the TCP congestion protocol, because at the upper layers there are FTP agents that continuously have data to send. This is useful to simulate heavy-loaded networks.With On-Off traffic, a typical web interaction is simulated: a source starts sending packets, then enters a silent phase before transmitting again. The average duration of the Off period is a configurable parameter ( avg_wait): during these periods no segments are generated. Clearly, by tuning the value of the Off period, we act on the system load. When a connection is turned On, its duration depends on the amount of bytes to send, and the achievable throughput: this value is uniformly chosen among the ones reported next, that were derived by measurements of real Internet traffic. A TCP connection reverts to the Off phase only when the sender agent receives the acknowledgment for the last TCP segment that it sent during the previous On period.
TCP connections are established between each WS and the fixed node S. In particular, given N wireless stations, N/2 TCP connections are established in the uplink direction (from a WS to S), while the remaining N/2 are in the downlink direction. To change these settings, it is necessary to modify the following instructions in traffic.tcl:
if {[expr $j % 2] == 0} {To test other scenarios it is sufficient to change the nodes at which the TCP agents are attached. UDP traffic can be activated by setting the udp flag to 1. The size of UDP packets is configurable by udp_size. This traffic is generated by CBR sources, and acting on the load parameter, we can control the global rate generated by all CBR flows. Since there is a CBR source for each node, the rate at which each node transmits is equal to load/nn. Consequently the delay between two consecutive frame departures is:CBRdelay = (8 * udp_size * nn)/loadActually, to avoid synchronization effects during simulations, packet departure times are affected by a very small random noise, therefore CBRdelay becomes the average value for the delay between two consecutive frame departures. In this case all flows are in the downlink direction, so the UDP frames are all generated by the fixed node S. Like TCP flows, this setting can be changed by acting on the following lines of traffic.tcl:
$ns_ attach-agent $W(0) $udp($j)8. Topology In the scripts included in the distribution, we consider a wireless-cum-wired network scenario configured as follows. A fixed node S is connected with an AP through a wired link of speed 5*BW (where BW is equal to the bandwidth parameter) and propagation delay 2ms. This link is over-provisioned with a buffer size of 150 frames, so that no packets are dropped at its ends. The instruction for configuring this link is the following (from topology.tcl):
$ns_ duplex-link $W(0) $BS(0) [expr $opt(bandwidth) * 5] 2ms DropTail
The wireless portion is an 802.11 WLAN with N WSs, where N is equal to the nn parameter. Each WS can directly communicate only with the AP, since we focus on AP-coordinated wireless networks, disregarding the ad hoc mode. The data rate at which WSs and the AP operate is configurable on the command line by the bandwidth parameter.
The wireless stations are suited on a circumference of diameter dia, and the base-station is on the center of this circle, so that it is distant dia/2 from each wireless node. These settings can be changed in motion.tcl9. Statistics At the end of the simulation, a statistics file can be found in the directory specified on the command line by the dir parameter. The file name is *_finish.txt, where * represents the value of the idx parameter. For example, running the ns_802_11e_test.sh script, the output file produced is test/test_finish.txt. Opening this file, it is possible to see the different sections that are described next.Simulation parameters At the beginning of the file, some simulation parameters are reported. The first part (MAC parameters) shows the 802.11 parameters used in the simulation. They are, in order: MAC object, node index, control frames rate, data frames rate, AIFS, EIFS, CWmin, CWmax, SRL, LRL. Following, Node's Initial Positions reports the (x,y) coordinates of each node. The section TCP Flows summarizes the configuration of the TCP traffic: flow identifier, source node, destination node, direction (uplink or downlink) and the time at which they have started to send frames. The UDP Flows part shows the same data for UDP traffic. Finally, the list of Tcl parameters is printed. TCP Statistics The following variables define the TCP traffic:
UDP Statistics The following variables define the UDP traffic:
LL Statistics This section of the output file reports some LLC layer variables:
IFQ Statistics These statistics regard the Interface Queue, where frames are queued before accessing the channel through the MAC:
MAC Statistics The first part includes the HCF time occupancy statistics
The second part includes the collision and CFB statistics:
Finally, the third part includes the MAC frame statistics:
Network Statistics Here it's possible to find the Wireless Medium statistics:
Error Model Statistics These statistics report on the packet affected by the Error Model:
Error Model Time Change This section of the output file shows the state transitions of each Error Model:
tcp/udp DELAY/VARIANCE Statistics In the last part of the output file, the TCP (UDP) statistics about average delay (delay variance) are reported:
Some variance values can be negative: this is due to Tcl approximations when the real value is null or very small. Statistics for TCP On-Off traffic When the On-Off TCP model is used, another file is produced, with extension *\_web.txt. This file collects the following per-flow Tcp statistics:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||