H A Abuzanat

Fairness models to improve the quality of service in ad-hoc wireless networks

En premier lieu, je tiens à exprimer ma profonde gratitude aux directeurs de cette thèse le Professeur Armand TOGUYENI et à Benoit TROUILLET, Maître de Conférences. Je veux les remercier pour leur encadrement plein d'enthousiasme et de rigueur et pour la conance dont ils ont fait preuve à mon égard. De plus, je tiens à leur manifester ma sincère reconnaissance pour leurs grandes qualités humaines qui ont fait que cette thèse se passe dans la bonne humeur.

Finalement, ces remerciements ne seraient pas complets si je n'y associais pas toutes les personnes qui ont contribué de près ou de loin à la réalisation de ce travail, en particulier, mes collègues, tout le personnel du LAGIS et de l'École Centrale de Lille pour leur bonne humeur et leur disponibilité, notament: Virginie Leclercq et Régine Duplouich. iv 4.6 The average lost packet rate between EDCA vs. FQ-EDCA in Scenario II . . . . . . . .

General Introduction

The Internet, that connects all users, has many topologies, infrastructures and protocols for wired and wireless networks. However, a big challenge is faced to develop and implement their performance and their characteristics, which can permit all users to transfer their packets of dierent applications: data packets (ex. FTP), control packets (ex. Admission control), and media packets (ex. Voice 'VoIP', video streams), real-time packets (ex. safetycritical packets), etc.

One of the most famous protocols that became a dominant protocol in the internet world is IP (Internet Protocol) (RFC7 81a). IP was designed to provide a Best-eort service, which is the service in the internet without priority or guarantees, for delivery of data packets and to run across any network transmission media and system platform. These things are increasing the popularity of IP and make it carrying everything over IP; ex. Real-time data, audio, streaming video, etc. So, this makes IP to transfer all packets of dierent applications.

However, at each moment in the Wide Area Network (WAN), the network becomes a heavy loaded. That means, WAN bandwidth is not free yet. As a consequence, the network trac is not all equally and deployed fairly with respecting the Service Level Agreement (SLA). Therefore, time-sensitive applications (video, audio, real-time streams) need a guarantee for transmission with end-to-end bounded delay.

General Introduction

In addition, IP is not the best protocol that control every thing and managing the entire network. Thus, the misbehaved (mischievous, ill-behaved or annoying behavior) users can consume the bandwidth resources more than the other users. For example, a user is sending FTP packets of size 1500byte and another user is sending Real-time packets of size 512byte (normally, the packet size of real-time is less than 512byte). So, the ill-behaved users lead to a fairless network, because the router will serve the packets in round-robin manner. That means the packets of FTP will consume almost 3 times of bandwidth resources more than the real-time packets. Further, the heavy tracs that were caused by the ill-behaved users, make the congestion and bottle-neck in the network. This leads to a starvation. So, if the trac is regulated with fairness, it could resolve some of crucial problems in the networks like the congestion and starvation. Indeed, the heavy trac, congestion or starvation are undesirable for feedback-based congestion control algorithms in data communication networks. To solve this problem, the senders have to balance between two considerations. On the one hand, when they want to send data to the network as fast as possible. On the other hand, when they do not want to send the data so fast. To achieve the best performance, the source needs to detect the amount of bandwidth available to itself and match its sending rate to the available bandwidth.

A trac contract as Service Level Agreement (SLA) species guarantees for the ability of a network and its protocols to give guaranteed performance, throughput and bounded delays. This could be made by prioritizing trac. Therefore, the network requires Quality of Service (QoS) (Shin 03; Ciscc; RFC1; RFC2a; Cisc [START_REF] Cisc | Cisco Systems. DIFFSERV THE SCALABLE END-TO-END QUALITY OF SERVICE MODEL[END_REF] in addition to best-eort service.

QoS has the permission to control and manage the entire network. Further, dierent applications have varying needs for delay, delay variation (jitter), bandwidth, packet loss, and availability. These parameters form the base of QoS. Thus, the IP networks should be designed to provide the request of the applications for QoS. Therefore, the networks must provide secure, pre-General Introduction dictable, measurable and guaranteed services to these applications. So, the required service can be achieved by managing the delay, delay variation (jitter), bandwidth and packet loss parameters on a network, while maintaining its simplicity and its scalability. Which is critical and not simple to achieve, specially for the entire network complex applications.

A dened Quality of Service may be required for certain types of network trac. For example, IP telephony (VoIP) may require strict limits on jitter and delay. And also, a streaming multimedia may require guaranteed throughput. Further, some types of service applications are called inelastic, meaning that they require a certain level of bandwidth to function, any more than required is unused, and any less will make the service non-functioning. For example a safety-critical application, such as remote surgery, which is the ability for a doctor to perform surgery on a patient even though they are not physically in the same location. That must require a guaranteed service level of availability with no permission of failure or malfunction. Also, this is called hard QoS. By contrast, elastic applications can take advantage of however much or little bandwidth is available.

So, the problem is how to guarantee their QoS, which poses serious challenges to network researchers, whether from the service providers or internet end customers. For example, (Zhon 07; Parc 05; Vare [START_REF] Vare | [END_REF] pose the problem of real-time control of machinery on the internet. Basically, this requires QoS guarantees bounded delays to have a deterministic time.

Therefore, one of the topics that can enhance the QoS guarantees is the fairness. As described, regulating trac with fairness is one of the missions of QoS in all types of networks. Thus, QoS need to allocate the resources with fairness depending on the priority of packets to guarantee the services for time-sensitive applications. However, the fairness objective in wireless network depends on its topology, its size, its technology and the type of tracs and their applications. Therefore, it must follow an agreement (i.e. SLA). However, the fairness objective could be referred to many considerations; such as:

• Flow fairness: the throughput of each ow must be allocated fairly between all ows (No priority).

• Prioritized ow fairness: the throughput of each ow must be allocated fairly between all ows of the same priority level.

• Source fairness: the throughput of each source node must be allocated fairly between all the sources.

• Reserved source fairness: the bandwidth of each source node must be allocated fairly between all the nodes. The dierence between this denition and the last one is that not all the nodes are source nodes at the same time.

• Max-Min fairness: it allocates low throughputs required for some sources. And the rest of bandwidth is distributed for the other sources, which require high throughputs, and so on.

Further, nowadays, the technologies of connecting people is enhanced. So, you would be connected wherever you are, and whatever you want to send (i.e. real-time, video, audio, etc.). And also, these technologies could be implemented on any infrastructure networks. Therefore, in the wired network side, there is a large research on optimizing QoS. That enhancement of QoS could be considered not bad and better than the enhancement of QoS in wireless networks side. Although there is a lot of research concerning the QoS optimization in wireless networks, this optimization does not have at least the same level compared with that optimization in wired networks. This is referred to the problematic of wireless networks is not the same as that in wired networks. So, we will describe in brief the problematic of wireless networks. For example, the channel error in wireless networks is happened often when there is an interference with other channels or no Line of Sight (LoS) because of the obstacles that attenuate the wireless signal. Also, for the same mentioned reasons and the mobility, the wireless networks bandwidth is variable and makes the required throughputs hard to be allocated fairly.

General Introduction

Further, some of wireless devices have limited energy (i.e wireless sensors, mobiles, PDAs, etc.) that makes the routing paths changeable with extra control trac.

Moreover, the wireless networks problematic leads also to face many difculties for adopting the enhancement of wired side to wireless side. In addition, the denitions of OSI layers (MAC and PHY layers) are translated and adopted in the wireless networks to still have the compatibility, because the functionality of accessing channel in wireless network depends on these layers. Therefore, new phenomenas are appeared (i.e. hidden and exposed terminal problems, spatial reuse, unfairness, etc.) and need solutions. Indeed, an extension of MAC layer and dynamic solutions are needed to resolve almost the problematic of wireless networks. Unfortunately, like these solutions will have complex calculations and heavy trac. Therefore, there is a trade-o between the perfect solution and the complexity. However, there is no perfect solutions that resolve the wireless network problematic, because every solution has its undesired eects. So, it is better to resolve each problem separately with its circumstances to achieve the required goals and evaluate its benets. Therefore, the wireless networks can operate in two modes. One of them is the infrastructure mode targeted to the centralized purpose. And this type of network can be managed centrally. Thereby, the most of research of this mode is applied on the center devices. The other one is ad-hoc mode targeted to the distributed purpose. And this type of network could be managed independently by each device.

The main goal of wireless ad-hoc networks is to allow a group of communication devices to setup and maintain a network among themselves, without the support of a central controller. Thereby, the collaboration between these devices establish the connectivity between them. However, some of situations (i.e. home and oce networks, conference meetings, military applications, crisis response for emergency, etc.) (Jurd 07) that require quick local network deployment without infrastructure, and guaranteed service for receiving their data.

General Introduction

Therefore, the most of the previous undesired eects are appeared in this type of wireless networks. So, if some of these undesired eects are treated, a real enhancement will be achieved. This enhancement will make serious problems to be resolved. One of these serious problems is satisfying and enhancing the QoS in wireless networks especially ad-hoc mode.

So, in our research, we aim to enhance and optimize the QoS in wireless ad-hoc network with fairness. Thus, multiple models are proposed to enhance the QoS in ad-hoc. This enhancement is proved by implementing our models and evaluating them. However, our models are evaluated and compared with recent standards of QoS in wireless networks to obtain the real benets of our enhancement.

In our thesis, we will rst introduce the wireless network technologies. Then we present a state of the art of the QoS, its characteristics, its mechanisms, its protocols and its researches, in both wired and wireless environments. Then, the second part is targeted to our models that enhance QoS with fairness (i.e. F-EDCA (Abuz 09c; Abuz 08) and FQ-EDCA (Abuz 09b; Abuz 09a)). These models are implemented and simulated by using the Network simulator (NS-2). As a consequence, an evaluation is obtained for each model that present the concerned enhancement. Finally, we will compare these two models and present our conclusions.

Part I The State of The Art

Chapter 1

Wireless Networks

Introduction to Wireless Networks

The wireless networks appeared in the last decades. It refers to the interconnection between the nodes (hosts) without wires, using radio waves. These waves are propagated with an infrared band or an unlicensed spectrum bands frequencies (2.4GHz and 5GHz). The frequency of 2.4GHz is associated globally for Industrial, Scientic and Medical purpose (ISM band), while the frequency of 5GHz is associated for Unlicensed National Information Infrastructure (UNII band). These bands frequencies are unlicensed and free, which make the wireless networks widely deployed. However, this evolution of networks from wires to wireless contributes to have many advantages such as:

• Facilitating the construction of networks and exibility.

• Minimizing the budget of wiring and installations.

• Interconnecting the mobile objects.

• Being used for variable topologies. On the other hands, many disadvantages need to be overcome, such as: Chapter 1 : Wireless Networks

Wireless Network Technologies

• Low bandwidth compared to the wired networks.

• Hard challenge to adapt the wired protocols.

So, theses disadvantages are problematic in wireless networks, and caused by many reasons such as the variation of bandwidth is depending on the network's topology, the mobility and the density of the wireless devices, the channel-error because of the signal attenuation (i.e. between the buildings, trees, mountains, etc.). As a consequence, these problems make the optimization of the wireless networks harder and more dicult.

Therefore, various technologies of wireless networks are developed and associated for computer networks and its devices. Generally, these technologies are classied depending on the size of networks or type of using (i.e. WPAN, WLAN and WMAN) and standardized in IEEE802.1xx. Where, xx is dierent numbers and characters that species various series of wireless technologies, see table 1.1 and table 1.2. One of them is the standard IEEE 802.11. That is the most popular standard in wireless computer networks. However, the dierence between these technologies is the data rate, signal frequency, type of carrier, quality of service, etc. They have dierent characteristics implemented and taken place in the physical (PHY) and the data-link (MAC) layers. Where, the denition of the network layers is based on the OSI model.

Wireless Network Technologies

We will describe the technologies of wireless networks depending on their coverage area.

WPAN

WPAN (Labi 06) is the Wireless Personal Area Networks. It refers to small sized networks that are used to establish connections between a computer and its devices which covers an area of only a few dozen of meters (i.e. room).

Chapter 1 : Wireless Networks

Wireless Network Technologies

This network is standardized by IEEE802.15. We will describe the most important technologies of WPANs.

Bluetooth

Bluetooth (Labi 06) is a vast commercial name specied by the standard IEEE802.15.1 (IEEE 05b). This technology is broadly used to interconnect the devices of computers (i.e. headphone, mouse, keyboard, mobile phones, etc.) used clearly for personal purposes. This technology is operated in the ISM band. Indeed, it uses a frequency hopping spread spectrum signaling method (FHSS), while the original standard of IEEE802.11 uses two variations FHSS and DSSS. The last one is direct sequence spread spectrum signaling method. Recently, the new technology of WLAN or Wi-Fi devices uses DSSS. That means, the Bluetooth does not interfere with the new Wi-Fi devices of WLAN, although they use the same band.

ZigBee

ZigBee (Labi 06) is targeted for WPAN applications that require a low data rate, long battery life, and secure networking. Theses characteristics make it to have low prices. This technology has a large deployment and it is adapted for sensor networks. Generally, it is standardized with IEEE802.15.4 (IEEE 06). It uses the ISM band like WLAN or Wi-Fi devices. And also, it uses the DSSS signaling method. There are several series of the IEEE802.11 family. So, we will describe the most popular and concerned ones:

• IEEE802.11: it is the legacy standard associated to WLAN. The data is carried over frequency hopping spread spectrum (FHSS) or direct sequence spread spectrum (DSSS) signal modulation. It can provide a data rate of 1Mbps or 2Mbps in the ISM band (2.4GHz).

• IEEE802.11a: it is an extension of IEEE802.11. It provides a data rate, depending on the channel conditions, that could be any of 6, 9, 12, 18, 24, 36, 48, or 54 Mbps. Whereby, another signal modulation is adopted rather than FHSS or DSSS, which is the orthogonal frequency division multiplexing (OFDM). Also, it is applied in the UNII band (5GHz) that supports 8 to 12 non-overlapping channels.

• IEEE 802.11b: it is an extension of IEEE802.11. Also, it is considered as IEEE802.11 High Rate. It is referred to the commercial term (Wi-Fi). It provides a data rate, depending on the channel conditions, that could be any of 1, 2, 5.5, or 11 Mbps. It uses only DSSS signal modulation scheme in the ISM band (2.4GHz) that supports 3 nonoverlapping channels.

• IEEE 802.11g: it is an extension of IEEE802.11 (Wi-Fi). It uses the OFDM, DSSS or both signal modulations to obtain on the data rate in range of 5.5 to 54Mbps in the ISM band (2.4GHz).

The versions of (a, b and g), as mentioned above, describe the physical layer specications. Thus, these versions have dierent specications though they use a common MAC layer. Further, the dierence of the Inter-Frame spaces between them is considered, as seen in table 1. • IEEE 802.11n: it is a work in progress that supports data rates over than 100 Mbps by adding multiple-input multiple-output (MIMO) antennas instead of one. The additional transmitter and receiver antennas allow for increased data throughputs. This version of IEEE802.11 is considered as an enhancement for the legacy standard of IEEE802.11a/g that uses the signal modulation OFDM. And secondly by adding the channel-bonding operation applied in the physical (PHY) layer, which uses two non-overlapping channels to increase data transmission. And, a frame aggregation is applied to the MAC layer. So, by these methods the bandwidth obtained is more than the legacy IEEE802.11a/g multiple times and reach to 540Mbps.

However, in this thesis, we focus our studies in enhancing generally the standard IEEE802.11e specially in ad-hoc mode. And also, the other tech-Chapter 1 : Wireless Networks 1.2 Wireless Network Technologies nologies of IEEE802.11 (i.e. a,b,g, etc.) almost have an identical behaviors when there is a congestion, heavy load or bottleneck. So, all the simulations will be performed with the characteristics of the standard IEEE802.11b.

WMAN: WiMAX

WMAN (Labi 06) is the Wireless Metropolitan Area Networks. It refers to a large sized network, which covers an area of dozens of kilometers. This type of network, as a consequence of the explosion and deployment of the wireless networks, promises a broadband wireless networks comparable with the wired DSL or cable networks. One of the most new technologies of WMAN is WiMAX standardized by IEEE802.16 (IEEE 05c).

WiMAX is the Worldwide Interoperability for Microwave Access. Commercially, it is deployed and standardized with a subset of the IEEE802.16 standard. This standard provides a broadband wireless access for xed station and named xed WiMAX. While, an amendment of the IEEE802.16 standard is achieved to support the mobile users and named the mobile WiMAX, which is a subset of the IEEE802.16e standard. However, the mobile users can be connected to this broadband wireless access by extending the specications of WiMAX and supporting the Wi-Fi hot-spots with internet. In addition, it adopts several technologies of high performance physical layer (PHY). This is the major technical advance of WiMAX to provide a high data rate connections (i.e. tens of Mbps) between the base station (BS) and the subscriber stations (SS) for distance of several kilometers. Also, WiMAX adopts OFDMA (Orthogonal Frequency Division Multiple Access) as signal modulation that is based on OFDM. Further, mobile WiMAX uses a scalable OFDMA (SOFDMA) for broadband wireless access to mobile users.

Another enhancement in PHY layer, WiMAX implements multiple antennas for the transmitter and the receiver (MIMO) further SOFDMA. Thus, it can support of data rate over than 100Mbps. Therefore, it can cover thousands of users and mobile users distributed in a wide area.

The Point Coordination Function (PCF)

PCF is a method to access channel in the infrastructure mode. It is a synchronous method to access the channel by using beacon frames at regular intervals, as described in gure 1.2. Thereby, the access point polls each station during the contention free period (CFP). Thus, there is no collision this period. Therefore, PCF can provide a time bounded service (QoS). Also, it can be used in combination with DCF to support a super-frame, as specied in gure 1.2 and gure 1.3. This super-frame has two periods, one for polling in the CFP and the other for DCF in the Contention Period (CP).

Also in the infrastructure mode, all the STAs associated to the same AP have the same Basic Service Set (BSS). The BSS is composed at least of one AP and one STA that have a unique ID for association (BSSID). For the mobile STA, it can be associated to multiple AP. So, it is associated to Extended Service Set (ESS). This lets the mobile STA to change its AP by associating automatically with the AP that has the strong signal. And the name of this feature is Roaming. However, we are concerned by enhancing the operation in ad-hoc mode not in infrastructure one. So, we described PCF in brief. On the other hand, we will describe DCF in details, which explains the operation of ad-hoc mode.

The Distributed Coordination Function (DCF)

DCF is a method to access the channel in a distributed way. It is an asynchronous method to access the channel randomly. It represents the process to access the channel in ad-hoc mode. Also, it is used in infrastructure mode as well as ad-hoc mode, as described in gure 1.2.

Chapter 1 : Wireless Networks

MAC access channel

We will describe this part in details because our studies are related to this part and its enhancements, all in ad-hoc mode. However, DCF does not support delay sensitive data transmissions applications (e.g. Multimedia, Real-time applications) since it is a simple technique designed to access channel for the Best-eort data transmission applications (e.g. FTP, Mail, Browsing internet). So, it cannot guarantee QoS.

However, the algorithm of DCF Access channel (Gast 05) is expressed in algorithm 1. This algorithm describes the functionalities of DCF in MAC layer to access the channel; channel free, channel busy or collision occurrence.

As explained in algorithm 1 and gure 1.4 (Gast [START_REF] Cisc | Cisco Systems. DIFFSERV THE SCALABLE END-TO-END QUALITY OF SERVICE MODEL[END_REF], DCF is based on the Carrier Sense Multiple Access Collision Avoidance (CSMA/CA) with slotted time scale. The slotted time scale dened as the back-o counter. Thereby, every competing node attempts to transmit when its back-o counter is expired. Also, other time scales are dened as Inter-frame spaces. There are three inter-frame spaces in the original standard IEEE802.11. They are specied as following:

• SIFS: is the short inter-frame space, which is used for accessing the channel rst to enable ACK, RTS, CTS or the highest priority transmissions (i.e. SIFS is equal to 10µs for the standard IEEE80.2.11b).

• DIFS: is the DCF inter-frame space, which is used for the contention based services (i.e. initiating the back-o counter) especially in adhoc mode or at the CP in infrastructure mode. However, when the channel is free within this period, each node may access the channel in contention based services (i.e. DIFS is equal to 50µs for the standard IEEE80.2.11b Chapter 1 : Wireless Networks 1.4 MAC access channel the maximum limit of the CW. However, after each successful transmission, the CW is reinitialized to CWmin.

At the opposite of the CSMA/CD (Ethernet), in wireless, the collision is avoided at the sender by the back-o mechanism and avoiding sending when the medium is busy. Thus, the collision happens at the receiver because of the hidden and exposed terminal problem, error check of CRC or channel error. These make the receiver abort sending the ACK. Therefore, the sender considers a collision is occurred after the timeout for ACK message.

The collision can be dened as; the moment for two source nodes attempt to send their packets at the same time. Because of the signal interference, the receiver cannot capture the correct signal. Therefore, the collide sources must retransmit their packets. Since the probability, that two source nodes will choose the same back-o number, is small, the probability of packet collisions, under normal circumstances, is low. So, this probability is perceptible when the number of source nodes is high.

Also for collision avoidance, an enhancement for DCF is based on (RT-S/CTS) exchanging control frames to treat the hidden node or hidden terminal problem. That makes the QoS enhanced and optimized.

Before presenting our models, we will present the state of the art and the main concepts of QoS in wired and wireless networks. These concepts will be described for local and end-to-end QoS applied in dierent layer levels (i.e.

MAC layer and higher layers).

Chapter 2

Quality of Services (QoS)

QoS is a set of tools or technologies for managing network trac in a cost effective manner to enhance the services for home and enterprise environments. QoS technologies have the abilities to detect changing network conditions (i.e. congestion trac, bottlenecks, channel error, variable bandwidth, etc.). These abilities allow prioritizing or throttling trac. Thus, QoS technologies dierentiate trac and prioritize the critical and time-sensitive trac over the non-critical trac.

Denition 1. (IETFa): the Quality of Service provides a manner that is designed to provide the service which is used to send the packets and is described with parameters, i.e. bandwidth, delays of packets and the losses of the packets.

And also, it is highly recommended to provide a level of services similar to those available from the conventional wired networks. Thus, the services are classied in various classes depending on its service level.

Since the public network can carry many dierent types of ows, including voice, video, streaming music, web pages and e-mail, many of the proposed QoS mechanisms are complex or fail to meet the demands of the public Internet. Till now, there are data losses and packet delays. So, it is dicult to support each service with its requirements. For example, there is a critical trac (i.e. audio and video streams and real-time data) that needs the Chapter 2 : Quality of Services (QoS) guarantee for low latency and bounded delay. And there is a non-critical trac (i.e. web pages, FTP, etc.) that does not require better than besteort service.

Thereupon, QoS architecture introduces tools to treat packets dierently by dierentiating and classifying ows in categories or classes. Thus one ow receives better performance on the expense of others.

However, in the wired network side, there is a large research on optimizing QoS. For example, (Kadd 07) give results on measurements made on the Internet. These results show a good QoS in wired networks. Therefore, this enhancement of QoS could be considered not bad and better than the enhancement of QoS in wireless networks side. Although there is a lot of research concerning the QoS optimization in wireless networks, this optimization does not have at least the same level compared with that optimization in wired networks. This is referred to the problematic of wireless networks is not the same as that in wired networks. Thus, the wireless networks problematic leads also to face many diculties for adopting and transforming the enhancement of wired side to wireless side.

In this chapter, we will present the QoS solutions, architectures, characteristics and managements for two parts. The rst part is concerned for QoS in wired networks. The other one describes the QoS in wireless networks. Indeed, the rst part is necessary to show the ability to transform the protocols designed for wired networks and adapt them in wireless networks and their limits (ex. (Nian 02) describes an introduction of DiServ QoS in 802.11 Standard). Thus, we will describe the most important architectures in wired networks (i.e. IntServ and DiServ).

On the other hand, we will describe the QoS for wireless networks technologies, especially, that are designed for WLAN (i.e. the standard IEEE 802.11e). Because, there is a growing need to support QoS for wireless applications and mobile portable devices such as laptops, palmtops, etc. These devices become more and more popular, and the interest of using those portable devices without wires is growing very fast nowadays.

Chapter 2 : Quality of Services (QoS)

QoS Characteristics

Further, this chapter could be described to introduce and summarize the QoS in three axes:

• The local QoS, that is referred to apply the QoS in hop-by-hop mode, against the global QoS, that is referred to apply the QoS in end-to-end mode.

• The QoS protocols applied in MAC layer level against those in higher layers levels, notably the network layer.

• The QoS approaches for wired networks against wireless networks.

Thus, by these axes, the QoS ideas and its conceptions almost are presented to describe the state of the art.

QoS Characteristics

The characteristics of QoS are considered as the parameters of QoS. Thereupon, the QoS is managed and controlled to serve the applications with guarantees and assured services. These parameters will be described as following:

The delay or latency

It is the time taken to transmit a packet from the application layer of the sender to the same level of the receiver. This time of period is called the end-to-end delay. It can be expressed as the summation of delays; sender process delay, propagation delay, buer delay and receiver process delay.

However, the sender process delay could be made by the processing delay from the upper layer to the lower layer, and by the exchanged messages to establish a connection.

And also, the same thing could be for the receiver process delay, but in the opposite consequence. However, these dierent types of delays are categorized into two categories, as:

Chapter 2 : Quality of Services (QoS)

QoS Characteristics

Constant delays

They include encoding and decoding times (for voice and video), and the propagation time, depending on the electrical or optical pulses speeds (Light speed, which is almost equal to 300.000 km/s in free space).

Variable delays

They refer generally to the network conditions, such as bottlenecks, queuing (scheduling) and congestion. That could be bounded or averaged to managing QoS.

So, the end-to-end delay could be bounded between the minimum delay and the maximum delay. Thus, the QoS can manage the resource allocations depending on the required service of the application.

Delay jitter

It is dened as the delay variance or as the dierence time of the packets that arrive at the receiver in dierent sequences (packets have varied delays).

In other words, it is the dierence of end-to-end delays between two sequenced packets. For example, two sequenced packets have end-to-end delay times; 50ms and the other 70ms. Thus, the delay jitter is 20ms. Therefrom, for veritable values, it causes distortion of voice signal.

Packet losses

Generally in networks, the packet is expressed as lost packet when it is dropped within queuing because of the congestion occurrences or bottlenecks. And also, when the receiver checks the CRC check error of a packet received, it nd the packet corrupted because of signal degradation, saturated network links and noise interferences. So, the receiver neglects sending Ack to the sender. Therefore, the sender considers that packet is lost after the time-out of Ack waiting.

Chapter 2 : Quality of Services (QoS)

QoS Management

Further, it is dened as the dierence between the total number of emitted packets and the total number of received packets.

Bandwidth

It is the allocated resource of the network. However, it can be measured by the rate of sending bits (the principle unit of data or packets). Also, this rate is variable (i.e. in Wireless networks) and depends on many factors, such as the technology (i.e. Ethernet 10/100/1000Mbps, WiFi 1/11/54Mbps), the topology, the media (i.e. ber optics, wireless, twisted pair, coaxial, etc.), the interference, the routing protocols, processing, queuing, etc. And also, as bandwidth increases, power consumption increases. In a wireless device (i.e. hand-held device), this reduces battery life.

However, to guarantee QoS, global management of networks must be applied to control and manage the tracs of the networks, as described in the next section.

QoS Management

QoS management helps to set and evaluate QoS policies and goals. Further, the basic implementation of QoS in a network could be illustrated in three main componenets, as seen in gure 2.1.

Thus, supporting QoS in various networks requires collaboration of many components or techniques:

Admission Control

It limits the number of ows admitted into the network. So, each individual ow obtains its desired QoS specied by reservation resources, identication and marking techniques for coordinating QoS from end to end between network elements. Further, the policies to control and administer end-to-end Chapter 2 : Quality of Services (QoS) 2.2 QoS Management transmitted rst on the output link? Signicantly, it impacts QoS guarantees for dierent ows. Therefrom, it aects the parameters of QoS (ex. delay, jitter and loss rate).

However, there are a lot of scheduling algorithms or disciplines, such as; FCFS, GPS (Pare 93), WFQ (Kesh 89), etc. We will describe some of them later in the scheduling and queuing algorithms.

Therefore, some of these algorithms can be used to schedule the queued packets with fairness, weights or priority; depending on the packets' ows or packets' classes and the architecture model of QoS.

Queue management controls the queue size and decide which packets to drop during congestion. Therefore, it controls packet loss rate. However, managing queues is important to schedule data ows and to minimize and treat the congestion.

Thus, there are a lot of packet drop strategies such as (Fero 00), (Wurt 02), etc. The last one is Weighted Random Early Detection (WRED), which is one of the variety of RED and one of the congestion control techniques. However, we will describe the technologies and the solutions of QoS, as presented in the next sections. These technologies apply the parameters of QoS and attempt to guarantee the required services.

Congestion Control

Therefore, let us present the state of the art for the QoS architectures in both of wired and wireless networks. We will describe the most important architectures for QoS, which are used nowadays, such as IntServ that is a per-ow model, and DiServ that is a per-class model.

Furthermore, we will describe the compatibility of these architectures to adopt them in wireless networks and realize the required QoS (IEEE802.11e standard; HCCA and EDCA).

QoS in Wired networks

IntServ and DiServ are QoS architectures, which are the most applicable nowadays in various networks. We will describe them in details.

IntServ (Integrated Services)

IntServ ( RFC1) is a ow-based mechanism. This mechanism treats the trac ow that belongs to the same source application. Where the end hosts signal their QoS needs to the network.

Then, IntServ follows the signaled QoS. The idea of IntServ is that; every router in the system implements IntServ path map, see gure 2.2. Thus, every application that requires some kind of guarantees has to make an individual reservation.

However, to implement the path map, the Flow Specications describe what the reservation is for by two parts:

• Trac Specication (TSPEC): this includes token bucket parameters. Thereupon, DiServ classies ows packets, which allows serving trac to be partitioned into multiple priority levels or classes depending on the ow requirement.

DiServ Model (Domain)

A DiServ domain consist of two parts; the edge routers and core routers, see gure 2.3:

The Edge routers (Boundary routers): They perform the classication and conditioning. A packet classier classies the ows packets depending on the packet information via Behavior Aggregate (BA) classier. That classier is searching the DSCP (Dierentiated Services Code Point) (Nich 98) of the ToS (Type of Service, 8bit) in IP header, see gure 2.5. Thus, the classier classies the packets depending on the priority level of ToS with respect to the operator conditions TCA (Trac Conditioning Agreement), which is part of the network provisioning contract of the service provider.

• Assured Forwarding (AF): It is expressed as better than best eort. It provides a guaranteed service (with dierent drop precedence) to end users. And its parameters of QoS depend on predictivity, probability (ex. Delay < 10ms with 75%) and stochastic distribution. This service is supported for the applications of priority level between the EF and BE.

Moreover, as seen in table 2.1, the AF could be able to classify the packets in 12 priority class described as (AFxy) referenced with DSCP.

Thus, it denes a method by which PHBs can be given dierent forwarding assurances. The AFxy in PHB denes four AFx classes: AF1, AF2, AF3 and AF4. Each class is assigned a certain amount of buer space and bandwidth, dependent on the SLA with the Service Provider/policy.

For example, trac can be divided into gold, silver, and bronze classes. The gold class allocates 50 percent of the available link bandwidth, silver 30 percent and bronze 20 percent.

Also, within each AFx class, it is possible to specify three drop precedence values when there is congestion in a DiServ Domain on a specic link.

As seen in gure2.5, the DSCP is 6-bit eld in the IP header and is dened in RFC 2474 (Nich 98 However, we will present also the state of the art in wireless networks.

QoS in Wireless

This section describes the quality of service in the environment of WLAN implementations. The QoS guarantees in WLAN refer to its capability to support dierentiated services for the network tracs. These services are prioritized depending on the sensitivity of time, which called the QoS parameters, of those tracs. Therefore, these tracs can be managed to serve the higher priority with greater bandwidth and less delay than the lower priority with lower bandwidth and more delay.

And also, the bandwidth can be managed eciently by controlling the network congestion and trac shaping. This make the capability for controlling the jitter and the delay of tracs is more ecient.

The problems of wireless networks are characterized by many features, that aect the trac link. They are Channel-error and Location-dependent as described in (Lu 97). The channel-error causes high error-rate and burstyerror, while, location-dependent is caused by user mobility. So, a high errorrate makes the bandwidth of the network is scarce and the mobility makes the bandwidth of the network is variable (time-varying). Thereby, a timevarying wireless link capacity and scarce bandwidth limit QoS guarantees and make the development of QoS hard challenge in wireless networks.

Chapter 2 : Quality of Services (QoS)

QoS in Wireless

However, it is highly recommended to provide a level of services similar to those available from the conventional wired networks. Thus, the services are classied in various classes depending on service level.

In the last decade, the market of wireless networks is grown rapidly while the prices of its devices are decreased. This makes the interest and the popularity of the wireless networks, especially those are based on IEEE 802.11 (IEEE 97), is also increased. Thus, IEEE 802.11 wireless LAN has become a dominant broadband wireless technology in recent years. Therefore, the development of WLAN is crucial and important.

The wireless applications that need Quality of Services guarantees are growing too. These applications have time-sensitive data such as real-time data, voice and video. Their trac data, which should be associated with these services classes, must be delivered to those wireless portable devices at specic data rates and within specic delays, packet loss and jitter bounds, which are the parameters requirements of QoS.

Moreover, at the beginning of developing the wireless network, it was mainly used for the best-eort and the low bandwidth data tracs. That means there are no QoS guarantees. Nowadays, the technologies of wireless networks are required to transport the critical and time sensitive data tracs, and also to support in various environments. This requirement led to the necessity for QoS in wireless networks. Thus, QoS is one of the challenges, which must be overcome, to realize the practical benets in wireless networks.

Therefore, the upcoming IEEE 802.11e standard (IEEE 05a) enhances the original IEEE 802.11 MAC layer to support applications with QoS requirements by introducing Hybrid Coordination Function (HCF), which includes two techniques for medium access:

• Enhanced distributed channel access (EDCA): that administrates QoS in each station. EDCA is a distributed technique and can be used for ad-hoc mode. This is the architecture model concerned for. Further, we will focus on this model.

• HCF controlled channel access (HCCA): that administrates QoS in the Chapter 2 : Quality of Services (QoS)

QoS in Wireless

base station (QAP). HCCA is a centralized technique and manages access to the medium using a QoS access point, which can be used for the infrastructure mode.

In IEEE 802.11, PCF has a poor QoS performance. Therefore, it does not dene classes of trac. And also, it uses a simple round-robin algorithm, which cannot handle the various QoS requirements. Moreover, the transmission time of the polled stations is unknown, that make the station to reserve the channel until nish sending. Thus, the problems of PCF are resolved by HCCA.

On the other hand, in ad-hoc, DCF has also a poor QoS performance, because it is designed for equal priorities, and the station may keep the channel as long as it needs.

Therefore, HCF provides guaranteed services. Whereas, it is enhanced by providing delay guarantees in IEEE 802.11e Networks (Anne 04). However, it combines the advantages of PCF and DCF. And also, it coordinates the trac in many scheduling mechanism (not only round-robin). So, both EDCA and HCCA dene Trac Classes, to classify packets depending on their priorities.

HCCA

HCCA enhanced the PCF that is used in infrastructure mode, by developing scheduling mechanism in the base station (AP) that separates the ows in each queue depending on their priority. That means, it classies the packets depending on its type (best-eort, video and voice, etc.).

However, in our studies, we are concerned for optimizing the QoS in adhoc mode. So, all the detailed aspects of the HCCA are beyond the scope of our studies as we focus on the HCF contention-based channel access (i.e. EDCA). Thus we will present EDCA.

As well, QoS over the wireless link is achieved via admission control, resource allocation and packet scheduling at the base stations (AP) in infrastructure mode. Even so, it is not the same QoS administration over the Chapter 2 : Quality of Services (QoS)

QoS in Wireless

wireless link in ad-hoc. Indeed, in ad-hoc, there is no admission control that manages all trac for all hosts. Every host station manages its data separately, which makes QoS in ad-hoc is a hard and complicated challenge. Therefore, in ad-hoc, it cannot guarantee QoS for all conditions and for all the time.

Thus, we need to treat each condition separately, which leads to enhance QoS guarantee in ad-hoc wireless networks.

Let us explain the architecture of QoS in wireless ad-hoc mode (EDCA).

EDCA

EDCA enhanced DCF that used in ad-hoc mode. The principles of DiServ for dierentiating ows is adapted and translated in EDCA by introducing the concepts of access category (AC) (IEEE 05a). It provides service dierentiation and classies the trac of 8 dierent user priorities , as dened in three bits of TOS in the header packet of the upper layer (i.e. Network layer), see gure 2.5. Thereby, each data packet from the upper layer with a specic user priority value should be mapped into a corresponding Access Categories (AC), see table 2.3. Therefrom, the user priority value is dened in the IEEE 802.1d bridge specication (IEEE 98a).

However, each station has four ACs to provide service dierentiation, see gure 2.6. Moreover, it implements an Arbitrary Inter-Frame Space (AIFS). AIFS is a waiting time before the beginning countdown of back-o procedure. So, this waiting time is equal to a number of slot-times. This number is referred to AIFSN, which is a parameter in EDCA to access the channel.

Every AC behaves as a single DCF contending entity, and each entity has its own contention parameters (i.e. AIF S[AC], CW min [AC], CW max [AC]), see table 2.3. Thereby, each AC supports dierent kinds of applications such as; background data, best-eort data, video data and voice data, which each trac data can be mapped to dierent AC queue (i.e. AC_BK, AC_BE, AC_V I, AC_V O respectively).

• AC BK

• AC BE • C V I • AC V O AIF SN [AC] CW max [AC] CW min [AC]
Chapter 2 : Quality of Services (QoS) (2.1) For example, as seen in gure 2.7, let the packets that are classied in AC x have a privileged priority more than those in AC y . As a consequence, the time waiting for data of AIF S(AC x ) is less than AIF S(AC y ) to start deferring access channel. Then, data of AC x attempt to access channel and the other categories wait and pause their back-o's counting down.

QoS in Wireless

According to EDCA, it behaves as DCF scheme for each AC with an extra procedure of waiting (AIFS). Thus, after the classication, the packets for the same AC are enqueued in FCFS (First Come First Serve or FIFO) simple queue with drop tail technique (drop the last packet when the queue is full). Then the packet is dequeued when it can access the channel to attempt for transmission after a waiting time. This waiting time is the summation of Chapter 2 : Quality of Services (QoS) Every AC decrements its back-o counter. When the back-o[AC] reaches zero, the node attempts to transmit the elected packet for that AC and the other categories wait and pause back-o's counting down. If the channel is clear or idle, then it transmits the packet and access the channel. Normally, the probability of packet collisions is high when the number of nodes is high.

QoS in Wireless

However, the CW is reset to its minimum value (CW min [AC]) after each successful transmission. Otherwise, it is doubled when a collision occurs or the medium is sensed to be busy at the end of defer access period, as seen in (2.2). In (Zhai 05), many of proposal are proposed to solve with challenges the last problems, but this leads to new problems such as wasting bandwidth and channel utilization (spatial reuse).

CW new [AC] = min(2 * CW old [AC], CW max [AC]) (2.2) 2.4.
Indeed, as described in (Chen 06), in EDCA there is no admission control that manages all trac for all hosts. Every host station manages its data And also, routing node has to access more frequently the channel than another node which is not participating in routing. Therefore, depending on the amount of data to route, CW is increased when there is a collision (after each unsuccessful transmission) by multiplying it by a multiplicative factor M F i . By default, this factor is equals to 2 in DCF and EDCA as in (2.2). While, in RAMAC, M F i is smaller than the value 2. So, the computation of the new value of CW that belong to node (i) is described in ( 2.3, 2.4, 2.5)

CW new (i) = min(M F (i) * CW old (i), CW max (i)) (2.3) M F (i) = 2 -ρ(i) (2.4) ρ(i) = W r i (t)/(W o i (t) + W r i (t))
(2.5) Where:

• ρ(i) is the ratio of routed packets in routing node i over the total packets.

• W o i (t) is the amount of the own data trac to send, which belong to node i at the time t.

• W r i (t) is the amount of the routed data trac to send, which belong to other nodes at the time t.

• (t) is the time of unsuccessful access channel (collision).

Thereby, M F (i) is ranged between 1 and 2, since the ratio ρ(i) is in the range between 0 and 1. Thus, the node which is sending its own trac and participating in routing other nodes' trac has the lowest contention window value so that it should have the highest priority to access the channel.

In addition, an enhancement of RAMAC is proposed by (Nait 04) for DCF, it proposes a smoothing multiplicative factor (β). β is equal to a constant value between [0, 1], involved in the computation of the new contention window value, see ( 2.6), in order to reach a better fairness in sharing the Chapter 2 : Quality of Services (QoS) 2.4 QoS in Wireless bandwidth. (Nait 04) describes that combining both the trac dierentiation and smoothing the CW increase function, has a signicant impact on the medium access fairness between nodes.

M F (i) = 2 -ρ(i) * β (2.6)
However, after each successful transmission, the CW is reset to its minimum value (CW min ), because it helps the node to access the medium with a high probability. Moreover, the approaches described above are proposed for enhancing the QoS in MAC layer wireless ad-hoc networks. Whereas, other approaches for QoS provision are applied in network layer that are dependent or independent on the layer below (i.e. MAC layer), as described in the next section.

QoS routing in ad-hoc

There is a wide range of QoS requirements for ad-hoc (i.e. Mobile ad-hoc (MANET) (IETFb)), including throughput, delay, reliability or energy consumption. Most of QoS routing protocols involve trade-os between these QoS metrics, as described in (Redd 06). As a result, several of these protocols adopt exible mechanisms for tuning QoS variables to support various applications.

As described in (Jurd 07), the QoS for routing protocols aim to satisfy one or more performance goals at the network or node level. These goals include high reliability, robustness, low delay, high throughput and ecient energy. As described, the nodes in ad-hoc networks operate independently and have individual communication goals. So, generally, QoS protocols in ad-hoc networks should be provided on the node level. Therefore, in ad-hoc networks the QoS guarantees must be enabled for each node and even for each connection to optimize the network performance.

The goal of routing protocols is to determine a good path (sequence of routers) through the network from the source to the destination and to opti-mize the use of network resources. Typically, a good path means minimum cost path that characterized by the delay, the congestion level, throughput, stability of routes, signal strength, link cost, etc. Whereas, wired networks have dierent cost characteristics. Thereby, in ad-hoc, after receiving a service request from the sender, the rst task is to nd a suitable loop-free path from the source to the destination that have the necessary resources to meet the QoS requirement of the desired service. Therefore, this process is known as the QoS routing.

Moreover, the traditional routing algorithms depend on two principles: distance vector or link state. Distance vector establish a good path depending on periodic exchange of messages and selecting the shortest path if several paths available. While, link state noties all routers periodically about the current state of all physical links. Therefore, complex computation is needed for router to get a global view of the network.

However, in ad-hoc, every node can send its packets to its neighbors. And also it must be treated as a router for routing and forwarding the packets of their neighbors. Therefore, the path is constructed by the collaboration and the connectivity between nodes.

Thereby, an example illustrates the QoS routing in ad-hoc wireless network shown in gure 2.8. The numbers between the parentheses are the attributes of each link. These numbers represent the available bandwidth in Mbps and the delay in ms. Suppose a service required to send a data ow from node A to node D with an end-to-end bandwidth guarantee of 3Mbps and an end-to-end delay of 14ms. Whence, the QoS metrics can be classied as additive metrics, concave metrics and multiplicative metrics. Therefore, the cost path of bandwidth is a concave metric, that means it is calculated by the minimum cost link of bandwidth. While, the cost path of delay is an additive metric, that means the end-to-end delay cost is calculated by the summation cost link of delay.

Thereby, QoS routing searches for a path that has sucient bandwidth and bounded delay to meet the QoS requirement of the ow. The possible

• •
Chapter 2 : Quality of Services (QoS)

QoS in Wireless

• OLSR (Optimized Link State Routing) (RFC3 03b)

• PLBQR (Predictive Location-Based QoS Routing) (Shah 02)

• ZRP (Zone Routing Protocol) (Haas 97)

• CEDAR (Core Extraction Distributed Ad-hoc Routing) (Sinh 99)

• BR (Bandwidth Routing) (Lin 99)

• DSR (Dynamic Source Routing) (John 96)

• AODV (Ad-hoc On-demand Distance Vector) (Perk 99)

• QoSAODV (QoS enabled Ad-hoc On-demand Distance Vector) (Perk 00)

• TBP (Ticket-Based Probing) (Chen 99)

• TDR (Trigger-based Distributed Routing) (De 02)

• OQR (On-demand QoS Routing) (Lin 01)

• AQR (Asynchronous QoS Routing) (Vidh 03)

• OLMQR (On-demand Link-state Multi-path QoS Routing) (Chen 02) As presented in gure 2.9, these protocols are classied on the network layer depending on the periodic update of routing state information. So, the state information, that are sent periodically, are called table-driven or proactive protocols. While, the state information, that are sent on-demand, are called on-demand or reactive protocols. Further, when the last two are implemented together, they are called hybrid protocols. Therefore, we will introduce some of QoS routing protocols that are implemented in network layer as following: DSDV (Broc 98; Perk 94) is an expansion of distance vector routing. It is a table-driven protocol. Thus, each node keeps a routing table of destination, next-hop, number of hops and sequence number. The loop free is treated by the sequence number. The sequence number is originated by the destination Reply (RREP) messages which specify QoS parameters (i.e. the bandwidth and the delay) during the phase of route discovery.

In addition, PLBQR (Shah 02) is a table-driven (proactive) protocol. This protocol is mainly to relieve the scalability issue with respect to communication overhead. Instead of distributing the state information of each link in the network wide. Each node broadcasts its current position, velocity, moving direction, and available resources on each of its outgoing links across the network periodically. Wherein, mobile hosts are equipped with Global Positioning System (GPS) receivers and their moving behavior is predictable. Therefore, at any instant each node can locally depict an instant view of the entire network. So, the source locally computes a path that accommodates a QoS request and route data packets along the calculated path. Further, the source can predict path break and predictively compute a new path before the old path breaks by using the stored global state information. This tabledriven routing protocol is for providing soft QoS in small or medium sized networks, because it is inaccuracy in delay prediction.

Moreover, CEDAR (Sinh 99) is a hybrid protocol. It is designed to select routes with sucient bandwidth resources. Therefore, it dynamically manages a core network, on which the state information of those links of stable bandwidth is incrementally propagated. Each core node is responsible for maintaining its local topology and calculating routes on behalf of nodes in its neighbors. CEDAR selects QoS routes upon request. Then, a core path is rst established (from dominator) by ooding a control message across the core network. So, a QoS path calculation is then performed. However, this core path is shorten by using the partial information that are kept by the core. Thus, its performance depends on how well core nodes can manage their local resources. On the other hand, its disadvantages are specied as; the load factor or bottleneck at core nodes and how it can aect the network performance, are not addressed.

As a conclusion, QoS routing is a key issue in provision of QoS in Ad Hoc networks. However, no particular of QoS routing approaches provides an Chapter 2 : Quality of Services (QoS) 2.5 Layer QoS technologies overall or a perfect solution, because these approaches have been proposed for focusing on dierent QoS metrics.

Although, QoS routing protocols could provide end-to-end QoS in adhoc networks, an integration and coordination with MAC layer is needed as described in (Zhan 05). Thus, as described above, DSDV is a traditional routing protocol and a principle of QoS routing protocols. So, this protocol is performed in the simulations (with xed topologies) of our models (i.e. F-EDCA and FQ-EDCA) to enhance the QoS guarantees with fairness.

Thereby, logically, these models could be integrated with a QoS routing protocol to enhance the QoS provision with fairness for mobile hosts in dynamic topologies.

Further, we will describe the technologies and the solutions of QoS depending on their layer level, as presented in the next section.

Layer QoS technologies

QoS functions in multi layer depending on the service or the structure of the networks, so we will present the QoS technologies depending on the layer OSI model, as the following: 2.5.1 Data Link layer technologies (Layer 2) IEEE802.1Q/p/d (IEEE 98b; IEEE 98a) are the most important solutions for QoS in this layer. In the last decade, these standards dedicated for the Ethernet frames. Thereupon, the standard IEEE802.1p (included in IEEE802.1d) prioritizes the data packets encapsulated in the frame to 8 priorities. These priorities are specied by 3 bits in the header frame (i.e. Tag header). On the other hand, IEEE802.1Q is used to divide the performed LAN to multiple Virtual LANs (VLANs). Also, these standards are enabled by the announced Tag header in the frame header.

However, the solutions in that layer are considered as a QoS solution The QoS technologies for the application layer, which map to lower layers, are concentrated on the process and new codec developing performance.

However, the most of time-sensitive applications, that need the QoS guarantees, are oriented for multimedia (i.e. audio and video), telephony (ex. VoIP), real-time, and so on.

For example, the image processing and video coding are developed for multimedia and video telephony (ex. standard H.264) and mapped to the lower layers protocols (i.e. Real-time Transport Protocol (RTP)/UDP).

Other approaches, like (Mulr 06), enhance the last development to degrade the congestion that leads to minimize losses and retransmissions. Thereupon, the QoS for these applications (simultaneous) is enhanced. And also, these applications could be synchronized, by scheduling. This leads to enhance the QoS.

Further, in (Bout 07), it describes a cross layer architecture for real-time applications. As a consequence, the environment of research for developing the QoS for multiple layers is large. So, a good distribution of tasks in each layer could simplify the QoS administrations and managements.

Trac shaping and policing

Trac shaping and policing (Evan 07) limit the full bandwidth potential of the trac ows. They are used to avoid the overow or the congestion. However the trac shaping is using token bucket and leaky bucket schemes to optimize or guarantee performance, low latency and bandwidth, to deal with the concepts of QoS. So, these techniques regulate the trac rate. While, policing is the same of trac shaping, but it diers by discarding not buering the trac that exceeds its congured rate. However, the main concepts of trac shaping are actually managed by the scheduling mechanisms.

However, trac shaping schemes are commonly implemented at the network edges to control trac that is entering the network (i.e. DiServ).

Chapter 2 : Quality of Services (QoS) 2.6 Trac shaping and policing Thus, upon identifying trac ow using DiServ, it applies a policy to control trac's ows. Such that, some of the ows need either to guarantee a certain quality (i.e. Multimedia and VoIP) or to provide best-eort delivery.

This may be applied at the ingress router (the router at which trac enters the network) with a granularity that allows the trac shaping mechanism to separate trac into classes or individual ows and shape them dierently.

As a consequence, each ow could have the required resources depending on the service level agreement (SLA) and its policy. Further, it is necessary, for bounding the end-to-end delay, to satisfy the required components of QoS. Therefore, trac shaping provides a limited and controlled rate when serving and queuing the packets in scheduling.

Actually, there are two methods for trac shaping, which limit and control data rate of burst trac. These methods could be adapted in QoS and scheduling disciplines:

2.6.1 Leaky Bucket
It is a method of trac shaping that controls the incoming burst data trac (Evan 07).

However, as seen in gure 2.10.a, if the incoming trac with rate R, which is less than the bucket rate r, the outgoing trac rate will be equal to R.

In this case, when it starts with an empty bucket, the rate of the incoming trac is the same as the rate of the outgoing trac as long as R < r.

And, as seen in gure 2.10.b, if the incoming trac with rate R, which is greater than the bucket rate r, the outgoing trac rate will be equal to r (bucket rate). That leads to extra packets will be stocked in the bucket, whose capacity is b (in bytes or in packets). As long as R>r, the bucket will be lled up, as seen in gure 2.10.c. Thereby, another extra packet will be dropped or treated dierently depending on the policy.

Chapter 2 : Quality of Services (QoS) 2.7 Scheduling the packets. It can be implemented to avoid congestion and to distribute the resource allocations of bandwidth equally (with Fairness) or weighted (for QoS). The gateway schedules packets from multiple ows and forward them for the same outgoing link (ex. Multiplexer, Round-robin). The simple solution for scheduling is that the packet which First come First served (FCFS) or FIFO that used for Best-eort service (without QoS). In the other hand, the scheduler that provide QoS guarantee, is a complex solution and statistical multiplexer for:

• Which packets should be given preference?

• How many packets should be transmitted from a ow? Further, the scheduler that provides QoS guarantee is a hard challenge, because it depends on the type of network and its topology, the protocols of upper layers, the type of ows, etc.

The dierence between scheduling with or without fairness (Simo 03), see gure 2.12. We will describe concretely the scheduler's mechanisms in this chapter. However, the packets have dierent size. Thus, when multiple ows are enqueued in FCFS queue, then the ows will be served with dierent allocations of bandwidth depending of their packets size. So, the packets that have the large size will consume the most of bandwidth. And also, when there are condensed packets enqueued in the queue, the other ows will wait these packets to be served. On the other hand, another story and treatment for the schedulers with dierent queues to treat each ow with fairness or guaranteed service.

However, the scheduling mechanisms can be classied in two conceptions (Klei 76; Lieb 99):

• Work-conserving scheduler: Always transmits a packet as long as there is at least a packet available in switch buer. And also, it has an optimal performance in terms of throughput.

• • • • • • • •
Chapter 2 : Quality of Services (QoS)

Scheduling

• WFQ: Weighted Fair Queuing (Kesh 89).

• SCFQ: self-clocked fair queuing (Gole 94).

• WF2Q: Worst-case Fair Weighted Fair Queueing (R 96).

• CBWFQ: Class-based weighted fair queuing (Cisca).

• LLQ: Low Latency Queuing (Ciscb).

• MMFS: max-min fair sharing (Zhan 96).

• VC: Virtual-Clock (Zhan 91).

• ADPQ: Adaptive Priority Queue (Khan 05).

• EDD: Earliest Due Date (Boda 00).

• DRR: Decit Round-robin (Shre 96). Generally, a lot of them have the same idea or the same characteristics for supporting fairness or guaranteed services for QoS, but till now, there is no perfect mechanism. We will describe in brief some of them: 2.7.1 First-Come-First-Served FCFS or FIFO (Mela 02) is the simplest way of scheduling for Best-eort networking, see gure 2.12.a. The packets are queued into a common buer. Then, they dequeued from front of queue. The rst packet arrived, it is served rst. However, this technique has a lot of disadvantages as; there is no ow isolation, which leads to unfair sharing of bandwidth. So a greedy (illbehaved) source can occupy most of the queue and cause delay to other ows using the same queue, because there is no control for ill-behaved sources. Thus, TCP ows get penalized (congestion sensitive) with respect to UDP (no congestion control). And also, the time-sensitive ows (ex. Multimedia) will be served with degraded service. Therefore, there are no QoS guarantees.

And, it is hard to control the delay or bound it for the transmitted packets through FIFO buers. In addition, for Congestion control, it uses drop-tail packet method; that means dropping the last packet arrive when the buer is full.

However, FIFO is the principle architecture for EDCA, as described in section 2.4.2. Thereby, EDCA provides FIFO queuing method for each Access Category. Therefore, EDCA could miss fairness. For that reason, we will present a Fairness Queuing model (FQ-EDCA) that enhances EDCA, as described in chapter 4. 2.7.2 Round-robin RR (Chas 99) is the simplest way of scheduling as a multiplexer for Best-eort networking, see gure 2.13. It has the same features of FIFO for the same queue. The dierence is that; RR separates queues for each ow packets. And, the packets are served in a pure round-robin manner. However, there are disadvantages such as; it is unfair for dierent packet sizes. Theoretically, there is a conception, which is bit-by-bit round-robin that is impossible to apply. The scheduler serves a bit from each queue. So, each queue is served fairly. Practically, the scheduler serves a packet from each queue. Thus, RR is fair, if the packets have equal sizes. Therefore, Packet-by-packet Round-Robin (PRR) or Weighted Round-Robin (WRR) (Kate 91), that is the same of WFQ (Kesh 89), treats the packets of dierent sizes and solves the problem of unfairness.

In addition, there is no congestion-avoidance, which is caused by illbehaved (mischievous) sources.

Actually, it is the principle method of scheduling that can be applied for QoS. And also, it is a work-conserving, which means that the server is not idle when there is a queued packet or non-empty queue.

However, the concepts of WRR are adopted in FQ-EDCA to apply fairness, as described in chapter 4.

Chapter 2 : Quality of Services (QoS) 2.7 Scheduling queue serves ow of packets.

In addition, GPS can ensure fair allocation of bandwidth among all backlogged (the queue is not empty) sessions. Thus, it is suitable for feedback based congestion control algorithms. In other words, it provides fair share services. Thus, all ows sessions have the same resources (the same slope for all ow session graphs, see gure 2.16). So, if ow sessions (i,j) are backlogged at time (τ ), the service for ow session (i) equal the service for ow session (j). And also, if the bandwidth equal 1, it will be divided equally for both sessions (session (i) = 0.5 and session (j) = 0.5). On the other hand, if there is one backlogged session, it will consume all the bandwidth. Therefore, GPS can be described with all ows have equal weights as the following equations ( 2.7, 2.8, 2.9):

S(i, τ, t) = S(j, τ, t)
(2.7)

g(i) = R N (2.8) r(i) R N (2.9)
Where:

• S(i, τ, t): is the service of ow (i) in [τ, t], ow (i) is active at this interval.

• g(i): is the minimum rate guaranteed for ow (i).

• R: is the total bandwidth.

• N : is the number of active sessions.

We will illustrate the GPS calculations and its packet emulation (PGPS)

with the following example:

An example of GPS and PGPS, which describes the behavior of two sessions (ows). Every session belong to a buer queue, see table 2.5. As described, the time of arrival for each packet arrives at the head of the queue.

Each packet is served depending on the nish time for both GPS and PGPS.

Chapter 2 : Quality of Services (QoS)

Scheduling

As seen in gure 2.16, where:

• R1: average rate for session1.

• R2: average rate for session2.

• Si(t): GPS serving method for session i (S(i,t)).

• Ai(t): arriving packet for session i (A(i,t)).

• Backlog: there is waiting a packet.

• Packet sizes in units (u).

• Bandwidth = 1 u/s.

• The slope of the curve is equal to the average rate of session (r(i)): r(i)= 1 u/s when the other session of i is idle. r(i)= 0.5 u/s when there is no idle sessions. r(i)= 0 u/s when the session of i is idle. In gure 2.16, at time 0 session 2 serves the rst packet. Since it is the only active session. Thus, it is served with all of the bandwidth (rate R2=1). Then, at time 1 session 1 serves the rst packet, so the bandwidth is distributed half for session 1 and the second half for session 2, and so on.

In the other hand, gure 2.17, it presents the practical method (PGPS) which is the emulation of GPS. So, at time 0 session 2 serves the rst packet with rate R2=1. Then, at time 1 session 1 backlogs the rst packet, it cannot serve the packet until session 2 nish serving its packet at time 3, and so.

As illustrated above, GPS calculations are approximated by PGPS. However, there is dierence for serving delay packet. For example, the delay for the third packet of session 1 in GPS is equal to 6 and in PGPS is equal to 4. And the dierence is compensated for serving other packets.

However, it is possible to make worst-case network queuing delay guarantees constrained by leaky bucket trac shaping. And also, it is independent Chapter 2 : Quality of Services (QoS) 2.7 Scheduling fore, various packet approximation algorithms of GPS have been proposed.

One of the best approximations is WFQ (Weighted Fair Queuing) (Kesh 89).

In fact, WFQ runs GPS computations and uses them to tag packets in ows to indicate the time that would have nished. WFQ approximates GPS by using byte-by-byte round-robin service. Thus, for a packet of size N bytes at the head of a queue, it will have complete service after the scheduler has performed N rounds of visiting all the other queues. Actually, packets cannot be transmitted one byte at a time from multiple queues. So, instead the packets are tagged with a nish-number, which indicates when they would have completed service if served byte-by-byte. Therefore, we can see that packets with the smallest nish number are the ones that should be transmitted rst. Let us take the simple case that the queue is empty and a packet of size 100 bytes arrives in the queue. When it is served byte-by-byte round-robin, it will be serviced in 100 rounds. So, its nish number will simply be the current round-number plus its own size in bytes. Thus, if the round-number is 50, the nish number for that packet is 150. If the queue is non-empty, then the packets, already in the queue, will be served rst. Thereby, the nish number of the next packet will be the nish number for that packet in front of it plus its own size in bytes. And also, when the round-number is equal to (or greater than) the nish number of a packet, it should be served immediately. However, the rate of round-number is controlled by the number of active connections. Therefore, the nish number for packet k on ow i at time t is given by the following equations ( 2.10, 2.11):

F (i, k, t) = max{F (i, k -1, t), R(t)} + P (i, k, t) (2.10) R(t) = R(τ ) + (t -τ )/N ac (t, τ ) (2.11)
Where:

• F(i,k,t): is the nish number of packet k for ow i at time t.

• P(i,k,t): is the size of packet k for ow i at time t.

• R(t): is the round number at time t.

• R(τ): is the round number at time τ .

• N ac (t,τ): is the number of active ows in the interval [t,τ]. In particular, the bounded delay provided by WFQ (PGPS) is within one packet transmission time of that provided by GPS. Even though it is computationally expensive, and need to hold each ow separately, WFQ is used by many router manufacturers.

However, there are alternatives to WFQ such as: self-clocked fair-queuing (SCFQ) (Gole 94), Virtual-Clock (VC) (Zhan 91) and Worst-case Fair Weighted Fair Queuing (WF2Q) (R 96). SCFQ has similar properties to WFQ, except that it removes the expensive round-number computation (by time-stamping synchronization). But also, it has a higher end-to-end delay bound than WFQ. Whereas, VC has a major dierence of WFQ; that VC is based on the resource reservation instead of an equal share to all users. That can allocate any specic resource to each user. Whenever, WF2Q has more approximation uid ow of GPS. That it provides almost identical service with GPS. And also, the maximum dierence between GPS and WF2Q is no more than one packet size, because WF2Q serves all the backlogs sessions.

In other words, in a WFQ system, when the scheduler chooses the next packet for transmission at time t, it selects among all the packets that are backlogged at t, and selects the rst packet that would complete service in the corresponding GPS.

In the other hand, in a WF2Q system, when the scheduler chooses the next packet at time t, it chooses only from the packets that have started receiving service in the corresponding GPS at t, and chooses the packet among them that would complete service rst in the corresponding GPS.

Thus it has less end-to-end delay bound than WFQ. However, in the example above, which illustrates the GPS and PGPS. As seen in gure 2.17, the behavior of PGPS can simulate both of WFQ and WF2Q

As illustrated above, WFQ and WF2Q have almost the same properties. But, WFQ has a problem, and WF2Q has better approximation of GPS than WFQ. The problem of WFQ is that it serves the backlogged packets. So, if there are condensed backlogged packets in a queue, it will serve these packets and the other non-empty queues will wait serving. Therefore, instead of searching for the smallest nishing time of all packets in the queue, WF2Q looks for the packet with the smallest nishing time, of whose start time has already occurred.

As described in chapter 4, the principles of calculations of WFQ and WF2Q are adopted in FQ-EDCA and transfered in WLAN ad-hoc to apply fairness between all source nodes.

Conclusion

To support true end-to-end QoS on an IP-network, two technologies have been dened: Integrated Services (IntServ) and Dierentiated Services (Di-Serv). IntServ follows the signaled QoS technology, where the end-hosts signal their QoS needs to the network. While DiServ works on the provisioned QoS technology, where network elements are setup to service multiple classes of trac with varying QoS requirements. Thus, these technologies need to be translated in wireless networks by adopting their principles such as dierentiating, marking, classifying, shaping, scheduling, etc.

However, wireless scheduling plays an important role in the design of wireless networks protocols. As well, it determines the QoS provisioning over the wireless link. So, it is very clear that the scheduling algorithm is the core of the protocol that determines the performance and guarantees QoS. However, the design of an ideal wireless scheduling is assumed by a full knowledge on current channel conditions and analytically provable delay and throughput bounds. Therefore, it is not simple to adapt a model that is designed for wired environments. And also, it is assumed, that the wired networks have error-free channel. While, the wireless networks have burst Chapter 2 : Quality of Services (QoS)

Conclusion

error channel and location dependent channel. Thus, a lot of research is oriented on extending the scheduling algorithms proposed in wired networks to wireless domain as reported in (Lu 97).

Thereby, to develop a model for wireless networks, it must supply; a fairness model for wireless fair queuing, knowledge on current channel conditions and approximates the characteristics of the ideal algorithm. However, it is pronounced that the MAC layer needs substantial more work to have a complete solution for wireless fair queuing. Typically, most related works of fairness in wireless networks concentrated on the probability of channel access and controlling the contention window. While in wired networks, fair scheduling has been extensively researched. So, fairness schedulers should be aected carefully with the probability of channel access and contention window.

As a conclusion, the scheduler mechanisms (Simo [START_REF] Vare | [END_REF], that provide QoS have to support services for arrival packets as: dening and keeping separate queues for dierent ows, sharing bandwidth for resource allocation and bandwidth guarantees, reducing delay variations (Bounding Delay) to guarantees QoS, isolating ill-behaved users and applying the fairness to competing ows. We will see that FQ-EDCA (Chapter 4) takes into account the previous services, notably the last crucial service. In the other hand, for outgoing packets, they manage serving packets in the output queues. Thus, the QoS could be guaranteed, and the congestion of the network could be avoided too (Floy 93; Kesh 92).

However, an extension is needed to enhance RAMAC behavior when the nodes in the network use other dierent trac types with dierent priorities, which can be implemented to guarantee QoS with fairness of bandwidth sharing. Therefore, our model (F-EDCA) evaluates and extends RAMAC, and enhances QoS (EDCA) in wireless ad-hoc networks, as we will see in chapter 3. While, FQ-EDCA applies fairness and enhances the QoS by implementing a hierarchical scheduling technique, as described in chapter 4. However, the mobility of host node make the topology of ad-hoc network is dynamically varying. That makes frequent paths breaks and discovers another paths. This re-establishment of paths may be unacceptable for some of application because of extra delay, packet losses, etc. For that reason, our enhancement of F-EDCA and FQ-EDCA are applied and performed on static topologies to avoid the interruptions of routing paths breaks. This Where, DCF consists in deferring the channel access in ad-hoc mode. Thereby, EDCA dierentiates and classies the packets in Access Categories depending on their priorities. Although EDCA is concerned to be the important enhancement for QoS in wireless ad-hoc networks, EDCA is not enough to provide fairness in QoS guarantees.

There are many propositions that develop the QoS in ad-hoc mode. They are based on control access channel such as Multiple Access Collision Avoidance with Contention Window optimization (MACAW) (Bhar 94). This model is enhanced with (RAMAC) (Nait 03) to access channel fairly by dierentiating the routed and owned packets in routing nodes. However, RAMAC is implemented in the legacy DCF to obtain fairness. It does not take into account the EDCA model. Thereby, we had proposed F-EDCA to enhance and develop QoS of EDCA in ad-hoc networks by implementing the principles of RAMAC. Thus, the transmitted queued packets in routing nodes will be dierentiated depending on their priorities (EDCA specications) and their type (Owned or Routed packet) to apply fairness in routing Chapter 3 : F-EDCA nodes.

As a consequence of the spread of popularity in WLANs, the interest for ad-hoc networks is taken into account. Where, the wireless devices need to transmit their packets with fairness and guaranteed services (i.e. Multimedia packets) in ad-hoc networks.

In addition, ad-hoc uses peer-to-peer through single-hop or multi-hop paths. Therefore, each station must work cooperatively to apply the connectivity between the sender and the receiver. Thus, each station must accept to route and forward the packets of others stations.

Although this is the only solution in ad-hoc to apply the connectivity, many of cases this leads to unfair resource allocation. Because some of stations (Routing nodes) contend to access channel for transferring their packets (Owned Packets) and the packets of their neighbors (Routed Packets) to apply a complete cooperation. Other stations (Non-routing nodes) contend to access channel for transmitting only their own packets. Indeed, there are nodes that have more bandwidth than others. As a consequence, unfairness of resources allocation minimize QoS guarantees notably for routing nodes.

Indeed, there is no admission control that manages all trac for all hosts in ad-hoc. Every host station manages its data separately, which makes QoS in ad-hoc is a hard and complicated challenge. Therefore, in ad-hoc, it cannot guarantee QoS for all conditions and for all the time. Thus, we need to address each condition separately to enhance QoS guarantee in ad-hoc.

Moreover, the EDCA does not have a distributed admission control algorithm to access the channel fairly. Therefore, we are working on an enhancement of the EDCA, such that it can be used to provide fairness of resources allocation for routing nodes. Thus, every node can dierentiate between its owned packets and the routed packets, which are queued depending on packet's priority. As well, we implement F-EDCA taking the advantage of RAMAC concepts in EDCA. Thereby, by adding this service, routing nodes can access channel more frequently than the other nodes. As a result, F-EDCA supports fairness of resource allocations in ad-hoc wireless networks.

Chapter 3 : F-EDCA 3.1 Denition of F-EDCA Thus, QoS guarantees will be optimized in EDCA.

In this chapter, we will rst describe our model (F-EDCA) that enhances EDCA with regard to fairness. The next section gives simulations results for the two models: F-EDCA and EDCA with its default parameters. These comparative simulations of the two models will enable us to evaluate the real benets of F-EDCA. These simulations will be performed under conditions which allow comparing their performances and their capacity to guarantee fairness.

Most of the proposals for QoS enhancement in ad-hoc wireless networks mainly focus on two conceptions; the station-based DCF enhancement scheme such as (Nait 03; Bhar 94; Aad 01) and queue-based enhancement scheme such as (IEEE 05a; Mang 02; Romd 03; Wiet; Abuz 09a). Thereby, we will present F-EDCA, which is a fusion of the last two conceptions.

The principles of DiServ for dierentiating ows is adapted and translated in EDCA by introducing the concepts of Access Category (AC). Thereby, we will adopt the conception of RAMAC in EDCA. This adoption is not simple, because there is no compatibility between the parameters of EDCA and RAMAC. Thus, F-EDCA will take into account this compatibility. As a consequence some of ideas in F-EDCA will try and describe this compatibility, as presented in the next section.

And also, an extension is needed to enhance RAMAC behavior when the nodes in the network use dierent trac priorities to transfer the data of dierent services. It leads us to implement this idea in EDCA in order to guarantee QoS with fairness resource allocations. Therefore, we will present F-EDCA (Fairness EDCA) and its evaluations that extend RAMAC and enhance EDCA in wireless ad-hoc networks.

Denition of F-EDCA

First, we should dene some of the main notions used by F-EDCA. There are two types of nodes in WLAN ad-hoc that are: Chapter 3 : F-EDCA

Denition of F-EDCA

• Routing node: it is a wireless node station that routes the packets' ows of its neighbors. The packets in this node are classied, queued depending on their respective class and dierentiated to:

Owned packet (O): It is a packet that belongs to this node. Routed packet (R): It is a packet that belongs to a nearby node that is routed by this node.

• Non-Routing node: It is a wireless node station that does not forward its neighbors packets.

Let us precise here that in fact in an ad-hoc network, most of the nodes are routing nodes. At the borderline there are few nodes that are just source non-routing nodes.

However, F-EDCA means Fairness EDCA. Thus, a fairness model is applied in EDCA to enhance it. Further, the Fairness is one of the topics that can enhance the QoS guarantees. The fairness objective in wireless network depends on its topology, its size, its technology and the type of tracs and their applications. Therefore, it must follow an agreement (i.e. SLA). However, the fairness objective could be referred to many considerations as described in the general introduction, such as ow fairness, prioritized ow fairness, source fairness, etc.

Thus, the bandwidth is considered to be fairly allocated as described in (Gamb 04). As well, EDCA provides packet level fairness (Priority classes) in MAC to guarantee QoS. While there is a lot of research work on improving fairness in the presence of hidden terminals (Bhar 94; Nait 03; Toba 75). So, the fairness objective in F-EDCA is the source fairness. It is dened as the bandwidth or throughput of each source node that must be allocated fairly between all the sources. Thus, in F-EDCA, the resource is fairly allocated with respect to the percentage of owned packets and the priority of their respective class.

F-EDCA model

QoS architecture of EDCA must be provided in WLAN to make F-EDCA applicable. Therefore, we will extend to EDCA the concepts of fairness that is developed by RAMAC.

Thereby, we will enhance EDCA to get more fairness for routing nodes. This can be realized by adapting a mechanism that controls the routing nodes to access channel more frequently than non-routing nodes. So, the allocated bandwidth of routing nodes, which is consumed for forwarding packets, will be compensated. For example, gure 3.2 presents the distribution of the bandwidth between three nodes (A, B and C). A and C are non-routing nodes, and B is a routing node, for the topology as seen in gure 3.1. In gure 3.2.a, the bandwidth is distributed equally between A, B and C. Indeed, the allocated bandwidth of B for transmitting its owned packets is less than the allocated bandwidth of A or C. This can be adjusted, see gure 3.2.b, by allowing more bandwidth allocated to B. Therefore, A, B and C get nearly the same allocated bandwidth to transmit their owned packets. Thus, the obtained fairness can minimize the delay and increase the QoS in ad-hoc networks. In wired networks, unfairness of bandwidth allocation problem can be solved simply by enhancing the scheduling techniques (i.e. Weighted Fair Queuing (Kesh 89), Weighted Round-Robin (Kate 91), . . . ). As explained, it is a hard challenge to adapt wired techniques in wireless. In other words, a lot of proposals suggest another solution to manage bandwidth allocation by accessing channel. Thus, the contention window (CW) will be controlled in F-EDCA based on a MACAW/RAMAC like approaches as described in (3.1). However, F-EDCA denes three parameters for routing nodes: a ratio of fairness (ρ) as described in (3.2), a Multiplicative Factor (MF ) and a tuning constant parameter (β) as described in (3.3). As well, all the following equations are applied in each access category (AC) for node i:

CW new (AC, i) = min(M F e (AC, i) * CW old (AC, i), CW max (AC, i)) (3.1) ρ e (AC, i, t) = W o(AC, i, t)/(W o(AC, i, t) + W r(AC, i, t)) (3.2) M F e (AC, i) = 1 + β(AC) * ρ e (AC, i) (3.3)
Where:

• M F e (AC, i) is the enhanced multiplicative factor for AC in node i.

• β(AC) is the constant tuning factor for AC in each node.

• ρ e (AC, i, t) is the enhanced ratio of the owned packets over the total queued packets in AC for node i.

• W o(AC, i, t) is the amount of owned packets to send in bytes, which belong to node i and queued in its AC at time t.

Chapter 3 : F-EDCA 3.2 F-EDCA model CW min from the value 31 to 3. This change makes the current CW exceed the CW max slowly after consequent collisions. Thereby, this makes the pa- rameters of equation (2.4) be signicant. Thus, if the current CWs of the collided nodes (i.e. routing and non-routing nodes) exceed the CW max , they will be equal to CW max for both of the collided nodes. Therefore, these nodes will have the same possibility with no priority for routing nodes to access the channel.

On the other hand, EDCA classies the packets to AC depending on their priority.

Whereas, the parameters of CW min and CW max for the highest priority are equal to 7 and 15 respectively, as described in table 2.3. So, after two consequent collisions between nodes (i.e. routing and non-routing nodes), the current CW of these nodes will exceed the CW max . This makes the parameters of the equation (2.4) are insignicant and makes M F almost be doubled with no priority for routing nodes. This leads to access the channel with the same chance for both routing and non-routing nodes, almost like the legacy EDCA. As a conclusion, there are two ideas to solve partially the lacuna described above. Firstly, by modifying the equation (2.4) to (3.3) to make the value of M F near to be 1 for routing nodes. Secondly, modifying the parameters of CW min and CW max for each AC to allow the parameters of equation (3.3) be signicant. So, after modifying the initial denition of M F , it still has the fairness assured by (2.4), as illustrated in section 3.5.

Chapter 3 : F-EDCA

The working principles of F-EDCA

However, the tuning parameter (β(AC)), noted here for simplicity, is a constant parameter for all the nodes that depend on the priority of class (AC). Its value is ranged between 0 and 1 (to dene the value of M F e (AC, i) between 1 and 2). If the value of β AC near to 1, the value of M F e (AC, i) will be maximized. As well, if the value of β AC near to 0, the value of M F e (AC, i) will be minimized. Thereby, β AC must be minimized for the high priority class depending on the parameters of CW min and CW max . However, the value of β AC is regulated depending on the AC's parameters of EDCA (i.e. CW min ,CW max and AIFSN) performed by the simulations. So, regulating β AC with modifying CW min and CW max for all ACs is a hard work and need a lot of time.

For example, β AC is minimized for the high priority class and equal to 0.5. This value is signicant when the parameters of CW min is equal to 3 and CW max is equal to 15. These values of parameters are performed by the simulations, as described in section 5.1, and achieve the required fairness as the result obtained in section 3.5.

As well, for the sake of simplicity, β AC is treated as a xed number for each AC evaluated by the simulation. Thereby, F-EDCA can assure the required fairness for each AC. Let us recall here that the default RAMAC, as described in equations ( 2.3, 2.4, 2.5), cannot be adapted to apply fairness for each AC with respect to EDCA parameters because it does not do dierentiation between data and so does not consider their dierent priorities. So, F-EDCA make the compatibility between RAMAC and EDCA by equations ( 3.1, 3.2, 3.3)

The working principles of F-EDCA

As seen in gure 3.3, each routing node station apply the following algorithm in MAC layer:

• It dierentiates between its owned packets and the routed packets by marking with (O) and (R) respectively. An interface between upper • Each packet is classied and queued according to its priority class.

• The value of ρ is calculated by (3.2) for each AC when there is a collision. This is done with taking into account the size and the type of packets queued in each AC. Therefore, CWnew (3.1) is obtained.

• Each packet at the head of queue waits its back-o and AIFS.

• If several packets at the head of the dierent queue have the same waiting time before its access to the medium, a virtual collision will occur inside the node. Consequently, a simple scheduler (like Roundrobin) treats this problem. Then the node attempts to transmit the head packet of the selected queue.

• CW is reinitialized to its minimum value after each successful transmission.

Chapter 3 : F-EDCA 3.4 The simulations of F-EDCA

The simulations of F-EDCA

Network Simulator 2 (version 2.31 of ns-allinone (NS2)) is chosen to implement and evaluate F-EDCA. The topology, which is used in our simulations, is described in gure 3.1. This topology is a basic ad-hoc network. Its simplicity allows a better understanding of the bandwidth fairness allocation between the routing node and the others. So we can treat it like a generic case in ad-hoc wireless network area that focuses the problem of unfairness of bandwidth allocation. Indeed, this is the objective of the simulations, because without dealing with this problem, F-EDCA would work like EDCA. And also, another objective, the dierence between routing and non-routing nodes could be dierentiated by these simulations. However, Nodes (A, B, C, D, E and F) are nodes working in ad-hoc mode. B is a routing node. A,C, D, E and F are non-routing nodes. D, E and F are treated as sink nodes. E and F are implied to receive ows of A and C respectively. This leads to avoid the impact of hidden terminal problem that is described in (Kose 08). Indeed, the hidden terminal nodes may need to transmit multiple ows to their neighbors (one-hop destinations) or to be forwarded through routing nodes to multi-hop destinations. So, if A, B and C send to the same destination (ex. F), another problem will be produced, as described in section 4.1. Thereby, the topology of gure 3.1 is chosen to separate the other problems, and to focus on the problem of unfairness between routing and non-routing nodes.

Our aim in these simulations is to compare the respective bandwidth of nodes A, B and C. Six ows are sent by these source nodes (A, B and C) as the following:

• A sends a ow to C routed by B. And another ow for its neighbor E without routing by B.

• B sends two ows to its neighbor D.

• C sends a ow to A routed by B. And another ow for its neighbor F without routing by B. The ows are sent at constant bit rate CBR/UDP trac applications with constant packet size (see table 4.9). And also, each source node sends two ows to have the same conditions for accessing the channel. In addition, F-EDCA is compared with EDCA model default parameters (Wiet). To achieve the comparison, bottlenecks and heavy loads of trac ow should be applied in the network. This is the case that is considered in the performed topology. All the parameters of simulations are presented in table 4.9. The values of the parameters are chosen to focus clearly the problem of unfairness between routing and non-routing nodes and to be treated by F-EDCA.

The results of rst simulations

The results of our simulations are considered as following: Figure 3.4 describes the bandwidth allocations for default EDCA model (Wiet). We remark that although the allocated bandwidth to transmit all the packets (owned and routed) queued in B is nearly as much as A and C, the dedicated bandwidth to transmit the owned packets of B is weak compare Chapter 3 : F-EDCA 3.5 The results of rst simulations with other source nodes (i.e. A and C). Indeed, all source nodes (A, B and C) obtain nearly 2.4Mbps of bandwidth. Nevertheless the allocated bandwidth for the owned packets of B is nearly 1.8Mbps. Therefore, there is unfairness of bandwidth allocations.

Figure 3.5 describes the bandwidth allocations by using F-EDCA. We remark that the allocated bandwidth of B is bigger than those of A and C. But the allocated bandwidth of the owned packets for each node is the same. Indeed, every source node gets nearly 2.3Mbps of bandwidth for its owned packets.

As well, we observe that the allocated bandwidth for all the packets of B is increased nearly 40% (from nearly 2.4M bps to around 3.3M bps). While the allocated bandwidth of A and C is slightly reduced.

However, when B contend to access the channel more frequently than others, the collisions is increased. Thus, gure 3.5 shows more variations than gure 3.4. Figure 3.6 explains the described phenomenon previously. Indeed, when the allocated bandwidth of B is increased, the dedicated bandwidth for the 3.5 The results of rst simulations routed packets, which belong to A and C, is increased also. Therefore, the allocated bandwidths of A and C are slightly minimized.

Figure 3.7 describes the delay of routed packets of B. As well, gure 3.8 describes the delay of owned packets of B for both F-EDCA and EDCA. It is observed that the delay is decreased by 50% for the two types of packets in F-EDCA compared with EDCA. Thereby, the QoS is optimized with F-EDCA.

Further, as seen in all gures, that F-EDCA achieves the stability of resource allocations better than EDCA. So, F-EDCA became stable after almost 20s. This time is needed to ad-hoc networks for constructing the routing paths. While, EDCA became stable after 80s due to constructing the routing paths, the congestion, hidden terminal problem, etc. Therefore, we can say that F-EDCA treats partially these problems Chapter 3 : F-EDCA

Conclusion

Conclusion

Many of researches of QoS enhancement in ad-hoc wireless networks mainly focus on station-based DCF enhancement scheme or queue-based enhancement scheme. In our proposition (F-EDCA), we have merged the stationbased DCF and queue-based enhancements. Therefore, we have implemented F-EDCA that supports bandwidth allocation with fairness in the architecture of EDCA by taking into account dierentiation between wireless node stations (Routing and Non-routing nodes). Thus, the routing node can access the channel more frequently than other nodes when there is a collision. As a consequence, each routing node has an extra bandwidth (depending on the percentage of routed packets) to compensate the deduction of its bandwidth that is needed for forwarding neighbors' packets.

Therefore, we can say that F-EDCA treats partially the hidden terminal problem and avoids the congestion by allocating fairly the resources. Thus, the misbehaving of resource allocations can be resolved by F-EDCA. Some perspectives of this study is to evaluate, to verify the scalability of this model and to propose a model to be able to guarantee end-to-end QoS Chapter 4 FQ-EDCA FQ-EDCA is a Fair Queuing Model for EDCA to optimize QoS in Ad-hoc Wireless Network. It aims to develop and optimize the Quality of Service (QoS) with fairness in multi-hop wireless ad-hoc networks. As we described in the state of the art, the development of the wireless networks is crucial. And the interest for ad-hoc networks has also increased. Because the needs for wireless devices (i.e. PDAs, Sensors, Wireless stations, . . . ) is rapidly increased, while their prices are decreased. Therefore, some of applications need to transfer critical data (i.e. Multimedia, real-time, . . . ) by using these devices. These data sometimes require strict services, which could not be oered by the legacy standard IEEE802.11 (IEEE 97).

Since, QoS supports critical and time-sensitive data, it is one of the challenges, that must be overcome, to realize the practical benets of wireless networks specially ad-hoc.

As a consequence, an enhancement of that standard (IEEE802.11e) is developed and concerned to support QoS in both the infrastructure and ad-hoc modes (IEEE 05a). Therefore, for ad-hoc, IEEE 802.11e standard enhances the legacy IEEE 802.11 MAC layer to support QoS by introducing the Enhanced Distributed Channel Access (EDCA) that manages QoS in each station. EDCA is implemented and applied in ad-hoc to support services for multimedia trac and real-time. It dierentiates and classies the packets Chapter 4 : FQ-EDCA 4.1 Denitions and problematic in Access Categories (AC) depending on their priorities. However, some of problems could be appeared in EDCA and not solved in F-EDCA, as dened in the next section. Therefore, FQ-EDCA is proposed to solve these problems.

In this chapter, we will present denitions and problematic in wireless networks, FQ-EDCA model and its algorithm. This model will be simulated to obtain the results and applied for many topologies. Therefore, these results will be evaluated and compared with the EDCA.

Denitions and problematic

The QoS could be satised by the standard IEEE802.11e, specially in the infrastructure mode. Although, in ad-hoc, the distributed EDCA is an important enhancement for the legacy IEEE 802.11, it is not enough to provide strict QoS guarantees required by real-time and multimedia services. Because there are crucial problems (i.e. hidden terminal) that need solutions, as explained in chapter 1, see gure 1.7, and in (Zhai 05).

In addition, another problem could appear frequently that an ill-behaved transmission of a source node leads to a lack of resource distribution and unfairness, because it could consume the ma jority of bandwidth and aect the performance of many others. This problem could be described by this example, as seen in gure 4.1.

Nodes A and B are source nodes that need to transmit their packets to node C. Thus, node B is dened as an in-ranged node, because it is in the range of transmission of node C. So, it can send its packets to node C directly. While, node A is dened as an out-ranged node, because it is out of the range of transmission of node C. So, it could not send its packets to node C directly and needs node B to route them. Like this situation, node B will attempt to send its packets and the packets of node A. That leads to the resource allocation of node A is ill-behaved controlled by node B while the congestion. So, node B is dened as an ill-behaved source node.

Chapter 4 : FQ-EDCA 4.2 FQ-EDCA model node). These packets are queued depending on their source nodes. Then, a hierarchical scheduling algorithm is implemented to serve and control the packets transmission.

As a result, FQ-EDCA supports fairness of resources allocation between source nodes in ad-hoc wireless networks. It is proved and analyzed by experimental simulations for many topologies like (star, chain, tree, . . . ), see gure 4.4. Thus, the bandwidth is distributed fairly between all the source nodes. As a consequence, these nodes can access the channel fairly to transmit their ows with respect to EDCA specications of Access Categories (AC) priorities. And also, the delay of ows of the same priorities is minimized and nearly xed for all the source nodes. This leads to minimize the Jitter also. Therefore, the services guarantees of QoS are enhanced.

FQ-EDCA model

FQ-EDCA is a Fairness Queuing technique applied in EDCA to guarantee QoS. The fairness objective in wireless must consider the resource which is to be fairly allocated, as described in (Gamb 04). In other words, the source nodes that have to transmit their loads (the same load for each node) have the same bandwidth of resource allocation.

However, EDCA is applied in MAC layer which coordinates the ecient use of the limited shared wireless resource. But, the problems of hidden terminal still exist and make EDCA unfairness for some cases because of the ill-behaved source nodes. This is obviously illustrated in (Kose 08) and our simulations.

In (Zhai 05), many proposals are proposed to solve the last problems, but this leads to new problems such as wasting bandwidth and channel utilization (spatial reuse). Therefore, FQ-EDCA has the ability to overcome these problems, without regenerating undesired problems, and prevent the ill-behaved sources from arbitrarily increasing their rate.

In (Abuz 08) we have proposed F-EDCA (Fairness EDCA) to obtain a Chapter 4 : FQ-EDCA 4.2 FQ-EDCA model fairness solution by dierentiating between routing nodes and non-routing nodes. F-EDCA is a fusion of station-based DCF enhancement with EDCA that leads to a fairness approach, while FQ-EDCA is a pure queue-based enhancement. Thus, the fairness solution in FQ-EDCA is obtained by dierentiating the packets type and source nodes and by implementing an adaptive fair queuing scheduler. These implementations are applied in each AC separately to reduce the complexity of our algorithm.

The algorithm of FQ-EDCA

In FQ-EDCA model, hierarchical scheduling techniques (multi-level of scheduling packets) are implemented, to control network trac and to guarantee QoS with fairness. The network trac could be controlled by trac rate control and trac-shaping to optimize QoS guarantee performance, low latency and bandwidth. Therefrom, controlled trac rate is performed with scheduling and queues disciplines.

In wired networks, trac-shaping schemes are commonly implemented at the network edges to control trac that is entering the network (DiServ)(RFC2a; Lee 06). Which make the network has a proper admission control. While, in ad-hoc IEEE 802.11(e), every node is autonomous and there is no proper admission control, as described in (Chen 06; Zhai 05). Thus, to transfer the conceptions of wired networks DiServ to ad-hoc wireless networks, we would implement a DiServ like in each node station, as explained in FQ-EDCA algorithm.

It is very important for bounding the end-to-end delay to guarantee QoS requirements. Therefore, trac-shaping provides a limited and controlled rate when queuing and serving the packets with a proper scheduler discipline.

The scheduler disciplines, such as GPS (Pare 93), WFQ (Kesh 89), WRR (Kate 91), WF2Q (R 96), etc., control the order for forwarding the packets.

They can be implemented to avoid congestion and to distribute the bandwidth equally (with Fairness). However, these disciplines are successfully implemented and evaluated in wired networks. Therefrom, an extension of Chapter 4 : FQ-EDCA 4.2 FQ-EDCA model these disciplines is needed to perform its fairness in wireless network. Thus, their conceptions of fairness is translated and adapted to apply the expected fairness for EDCA in each AC. That we will see in FQ-EDCA algorithm.

The simple solution for scheduling is that the packet which rst comes is rst served (FCFS). It is used for best eort service (without QoS).

In the other hand the scheduler that provides QoS guarantee is a hard challenge, because it depends on the type of network and its topology, the protocols of upper layers, the type of ow, etc. Therefore, the model have to support services for arrival packets as: dening and keeping separate queues for dierent ows, allocating resource required for each ow, reducing delay variations (bounding delay), isolating ill-behaved users and applying the fairness to competing ows. We will see that FQ-EDCA takes into account the previous services, notably the last crucial service.

However, when EDCA receives packets from the network layer, it classies the packets depending on their priorities that are assigned in upper layers. After the classication, in EDCA, the packets for the same AC are enqueued in First Come First Serve (FCFS) with drop tail technique (drop the last packet when the queue is full). While, in FQ-EDCA, multiple levels of scheduling are implemented to compensate EDCA by controlling trac and apply fairness, see gure 4.2.

Then, for both FQ-EDCA and EDCA, the packet is dequeued when it can access the channel to attempt for transmission after a waiting time. This waiting time is the summation of deferring time of the Arbitrary Inter-Frame Number, depending on its AC (AIFSN(AC)), and the back-o countdown time. The back-o time is chosen randomly between the interval (CWmin, CWmax). These packets will be transmitted depending on the parameters of EDCA (AIFSN, CWmin and CWmax) (IEEE 05a). These parameters are decided depending on the policy for the QoS in wireless, which is already asserted. Thus, FQ-EDCA has the same parameters of EDCA to respect that policy.

Therefore, the preferred fairness must be applied in each class (AC) for

•

Chapter 4 : FQ-EDCA 4.2 FQ-EDCA model layer). Normally, these packets are prioritized according with the 8 priorities assigned in IP header. Then, it classies the packets into 4 classes as dened in EDCA specications (IEEE 05a).

• In each AC, it dierentiates the packets, depending on their type, to control packets (RTS/CTS, Ack, IP routing, etc.) and data packets (TCP/UDP). This dierentiation is important, to allow the control packets transmitted without delay. That leads to increase the eciency of routing and QoS guarantee.

• Another dierentiation is applied for the data packets, depending on their source nodes, to dene one queue for each source node. However, in ad-hoc, the node may transmits its packets and the packets of its neighbors. That causes unfairness of resource allocation while congestion. Thereby, by this dierentiation, the ill-behaved sources can be separated to be controlled.

• For queuing in each AC, one queue is dened for the control packets, while n ac i queues are dened for the data packets. However, n ac i is equal to the number of source nodes for AC_(ac) in this node ( i). Let SN is equal to all the source nodes ⇒

n ac i ⊂ SN . If i ∈ SN then i ∈ n ac i . If i / ∈ SN then i / ∈ n ac i .
• A Fairness Queuing (FQ) mechanism (an extension of WFQ and WF2Q) is implemented. Where, every packet ( P q kq ) of sequence (k q ) will be en- queued in queue (q) for ac i . If queue (q) is full then this packet is dropped. However, queue (q) is dened for the source node (m) of this packet. So, m ∈ n ac i , SN . If m = i then node(i) is routing the packets of node (m). FQ selects an eligible packet for ac i . The eligible packet must pass through a hierarchical scheduling levels before attembting of transmission. This scheduling technique will be described in the next section.

This scheduling technique is the basis of equity provided by the FQ-EDCA model. It ensures that all queues will be served in time, giving priority to those with the earliest packet in the lead (see the eligible packet notion).

In the FQ-EDCA model, as seen in gure 4.2, the following equations dene the techniques of the rst level of scheduling (Fairness Queuing (FQ)). Which is the most important part of FQ-EDCA's algorithm.

Let ac i be an access category of the node i, where n ac i queues are eectives to schedule the packets in the node i. Each queue will be represented by the associated rank (q ∈ 1, n ac i ). All the packets in a same queue are indexed by there rank. We will call P q kq the k th q packet in the queue q which is supposed to be at the head of the queue; all the previous packets ({P q 1 , . . . , P q kq-1 })

have been sent. In this way, we dene in the rest of this section a model which denes the techniques of the rst level of scheduling. The equations are described below; the expected start-number for serving the rst byte of packet (P q kq ) queued at the head of queue (q). This value is given by the greatest value between the virtual-round-number (V ) and the expected nish-number for the preceding packet (F(P q kq-1 )).Thus we have:

∀q ∈ 1, n ac i , ∀k ∈ N, S(P q kq ) = max(V, F (P q kq-1 ))

Proof. The proof is based on the explanation previously given. This value must be greater than: For all q ∈ 1, n ac i and for all k ∈ N

• The value of the virtual-round-number (V ): S(P q kq ) V

• The expected nish-number for the preceding packet (F(P q kq-1 )): S(P q kq ) F (P q kq-1 )

Then we must have:

S(P q kq ) max(V, F (P q kq-1 ))

We want to optimize the system. In this context, we start as soon as possible. Naturally, the earliest date is given by the max of the previous value. Then, we obtain the next formula: ∀q ∈ 1, n ac i , ∀k ∈ N, S(P q kq ) = max(V, F (P q kq-1 ))

The expected nish-number is for serving the last byte of packet (P q kq ) queued at the head of queue (q) for ac i . The expected nish-number will be given by the start number (S(P q kq )) plus the size in byte of the packet (L(P q kq )). Thus we have:

F (P q kq ) = S(P q kq ) + L(P q kq )
Proof. The expecting nish-number is, basically given by:

• The start-number: S(P q kq )

• The size of the packet (P q kq ):

L(P q kq )
Thus we have:

F (P q kq ) = S(P q kq ) + L(P q kq )

It will be useful to consider a special packet:

The eligible packet is the one that has the earliest nish-number, between packets that their start-number are below than the virtual-round-number. This packet will be abstract in the next by the equation below:

P e = arg min {(kq)|S(P q kq ) V } 1 F (P q kq )
Chapter 4 : FQ-EDCA

FQ-EDCA model

Remark. P e is a denition. The idea is to dene a special packet which will be send in rst. So we consider the set of all packet characterized by a startnumber lower than the virtual-round-number. After that, we take the packet in the queue with the lower index.

To evaluate the virtual-round-number, we will need rst the minimum value of the start-number between the n ac i queue for the access category and the V old will be upgraded to a new value. This value could be either the minimum value of the start-number or increasing the V old by a round number. This is described by the next equation:

S min = min 1 q nac i {S(P q kq )} V = max(V old + L(P e ) n ac i , S min )
Proof. The expecting virtual-round-number is, basically given by:

• V V old + L(Pe) nac i
Normally, the round number is dened by the size of the served (eligible) packet. Thus, for each round, the next packet of this queue could be served after serving the other active queues ( n ac i -1). That means, the packets queued at the head of n ac i queues could be served for each round.

• V S min If the queue is empty after serving the packet.

Then we must have the equality below:

V max(V old + L(P e ) n ac i , S min )

Then we set the equality for sending as soon as possible.

As a consequence, we obtain the next system of equations for our work.

It describes by the following system:

Chapter 4 : FQ-EDCA 4.2 FQ-EDCA model S(P q kq ) = max(V, F (P q kq-1 ))

(4.1)

F (P q kq ) = S(P q kq ) + L(P q kq ) (4.2)

P e = arg min

{(kq)|S(P q kq ) V } F (P q kq ) (4.3)
S min = min

1 q nac i {S(P q kq )} (4.4) V = max(V old + L(Pe) nac i , S min ) (4.5)
Where:

• P q kq is the rst packet in the queue q. Whereas, all the previous packets ({P q 1 , . . . , P q kq-1 }) have been sent.

• S(P q kq ) is the expected start-number for serving the rst byte of packet (P q kq ) queued at the head of queue (q) for ac i .

• F (P q kq ) is the expected nish-number for serving the last byte of packet (P q kq ) queued at the head of queue (q) for ac i .

• L(P q kq ) is the size of that packet in bytes.

• V is the virtual-round-number (byte-by-byte serving mode) for ac i . V old is used to specify the previous value of the virtual round number.

• S min is the minimum start-number between the (n ac i ) queues for ac i .

• n ac i is the number of queues for ac i .

• P e is the eligible packet, that has the earliest nish-number, between packets that their start-number are smaller than the virtual-roundnumber.

Moreover, FQ-EDCA's algorithm, that is described in the last section is continued by the following steps to select the eligible packet:

Chapter 4 : FQ-EDCA

FQ-EDCA model

• At the initialization, S(P q 1 ) and V are equal to zero. However, S(P q kq ) (4.1) and F (P q kq ) (4.2) are calculated for each packet at the head of queue. Therefore V will be updated (4.5) after nding the minimum start-number between the non-empty queues of n ac i (4.4).

• The eligible packet must pass through a hierarchical scheduling levels.

For dequeuing, a Fairness Queuing (FQ) scheduler (rst level) will serve the packet (P e ) queued at the head of queue that has the earliest nish-number, between packets that their start-number are below than the virtual-round-number (4. [START_REF]+ &1-+ , &+ $ +[END_REF].

Then in each AC, a Priority Queuing (PQ) scheduler (second level) will serve two types of outgoing packets (control and data packets). Thereby, depending on packet's type, the packet that has the highest priority is eligible. Normally, the control packet has the highest priority. Thus, the data packet will be served if the queue of the control packet is empty

The eligible packet at each AC waits its back-o and AIFS, depending on its AC. If several packets have the same wait time, a PQ scheduler (third level) will treat the elected packet depending on its priority. Thereby, the packet that has the highest priority is eligible and so on. However, by this algorithm, the policy of IEEE802.11e (EDCA) is also respected. We will prove that by the simulations. Although, some of scheduling disciplines (i.e WFQ and WF2Q) are less complicated than FQ-EDCA, they need more calculations than the rst level of scheduling of FQ-EDCA. Because in WFQ and WF2Q, there are weights distributed for each ow to be prioritzed. While in FQ-EDCA, these weights are implicitly dened by the classications of priorities in each AC. That means, the parameters of EDCA (i.e. AIFSN, CWmin and CWmax) describe the weights of the ows in each AC.

Q 1 (S, F ) Q 2 (S, F ) S min V S V ⇒ min(F )
Chapter 4 : FQ-EDCA 4. ) is chosen to implement and evaluate FQ-EDCA. Therefore three scenarios are applied to evaluate FQ-EDCA compared with EDCA. Moreover, each scenario has a topology described in gure 4.4. These topologies are basic structures of ad-hoc networks. However, a cascaded nodes connected together to transmit their packets and forward the packets of their neighbors, as chain topology (i.e. topology (I)). And also, sometimes many of source nodes needs to forward their packets by the same routing node, as tree topology (i.e. topologies (II and III)). The las two topologies are proposed, as it will be expected, to present the dierence of resource allocation btween the in-ranged source nodes and the out-ranged source nodes. Further, with increasing the out-ranged source nodes, the total bandwidth will be reduced because of increasing collisions and congestion. Thereby, these dierent behaviors cause dierent resource allocations between source nodes for each topology. They lead to unfairness as explained in the results of simulations (next section). However, for each scenarios, nodes A, B, C and E (node E for topology III) are source nodes, while D is a sink node. D is implied to receive ows of A, B, C and E. Our aim in these simulations is to compare the respective bandwidth of the source nodes A, B, C and E. Therefore, each source node transmits 4 ows to D (one ow for each AC, i.e. AC_V O, AC_V I, AC_BE and AC_BK). The ows are sent at constant baud rate (constant bit rate) CBR/UDP trac applications with constant packet size (see table 4.9). Further, in topologies (II and III), the distance between D and the center node is 250m to insure that only the centre node is in-ranged source node and the others are out-ranged source nodes. If that distance is made 200m, all the source nodes will be in-ranged source nodes else node E in topology (III). So, that thing couldnot give us the expected results.

In addition, FQ-EDCA is compared with EDCA model default parame- As described, the rst scenario is applied on a chain topology, as seen in gure 4.4 topology (I). The results of this scenario are given by gure 4.5. It describes the resource allocations for default EDCA model (Wiet) for different priorities. We remark that the allocated resources of bandwidth for A, B and C are dierent and lack the fairness for all the priorities. Indeed, C is queuing its packets and the routed packets of A and B in the same queue for each AC. Therefore, no control management is applied to control the ill-behavior of source nodes. So, the out-ranged sources (i.e. A and B) suer from the unfairness of resource allocations. Figure 4.6 describes the bandwidth allocations by using FQ-EDCA. We remark that the allocated bandwidth for the all sources are equal with respect to the priorities. Indeed, because of the robustness and the strength of FQ-EDCA, it can separate the ill-behaved sources. As well, we observe that the allocated bandwidth for all priorities are equal. That leads to minimize the delay of the out-ranged sources with balance, as seen in table 4.3. The delay is calculated from the sender to the receiver. Moreover, FQ-EDCA balances the average lost packet rate, as seen in table 4. Further, for the lowest priority (AC_BK), it is clear that there is no resources available for this AC in both of FQ-EDCA and EDCA, because all the bandwidth is allocated for the higher priorities. Therefore, to show you the state of starvation and bottleneck occurred, we are compelled to present the behavior of lowest priority, as seen in gure 4.8 and gure 4.9.

As a result, in the second scenario, FQ-EDCA enhances EDCA and guarantees services by implementing the fairness, see gure 4.10. The total bandwidth of the network is nearly 4.1Mbps for both EDCA and FQ-EDCA. That means FQ-EDCA has almost the same complexity as EDCA with no aection on the total bandwith or network throughput. Further, FQ-EDCA enhances EDCA by allocating the resources with fairnes for all source nodes of the same priority class.

The third scenario

As described, the third scenario is applied on a tree topology, as seen in gure 4.4 topology (III). The results of this scenario are given by gure 4.11. It explains the described phenomenon previously in the second scenario. We remark that the allocated resources of bandwidth for A, C and E are less

• At level (0): 1 sink node (destination) in the center.

• At level (1): 3 source nodes in the range of destination (In-ranged nodes).

• At level (2): 6 source nodes out of range of destination (Out-ranged nodes).

• At level (3): 12 source nodes out of range of destination (Out-ranged nodes).

• At level (4): 24 source nodes out of range of destination (Out-ranged nodes).

More than these nodes, the network will be died with taking into account the simulations parameters described in table 4.9. However, every level has a distance nearly of 200m faraway of the level below, and each node has a range distance equal to 250m. Normally, we choose this values because by default the simulation (NS-2) use this range distance depending on the physical parameters (i.e. signal power, line of site, interfernce, etc.).

Our aim in these simulations is to compare the respective bandwidth for each source node. Therefore, each source node transmits to the sink node, as shown in gure 4.14, 3 ows at the same time (one ow for each AC: AC_V O, AC_V I and AC_BE). The ows are sent at constant baud rate (constant bit rate) CBR/UDP trac applications with constant packet size (see table 4.9). Intentionally the CBR tracs are performed for multimedia and Best-eort data to obtain the worst-case of congestion and make our results be evaluated.

In addition, FQ-EDCA is compared with EDCA model default parameters (Wiet). To realize the comparison, many simulations are performed depending on the level of source nodes around the sink node (i.e. one level ⇒ 3, two levels ⇒ 9, three levels ⇒ 21 and four levels ⇒ 45 source nodes). This is the case considered in the performed simulations to show you the 123 Chapter 4 : FQ-EDCA 4.5 An extension of FQ-EDCA simulations Figure 4.14: Topology of (45) source nodes organized with multi-hop distribution around (1) sink node. ability of FQ-EDCA for treating the congestion in large topologies. All the parameters of simulations are presented in table 4.9.

Results of simulations

The results of the last simulations obviously illustrate the problem of unfairness in EDCA. This unfairness is because, the nodes must cooperate to be connected together in multi-hop mode to transmit their packets and forward (route) the packets of their neighbors. So, the data packets received from upper layer are dened as owned packets. And those from PHY layer are dened as neighbors (routed) packets. Indeed in MAC layer, these packets are queued in one queue for each AC at the source node. However, because of the problems of wireless networks as explained, the owned packets are received to be queued faster than the routed packets. That gives more of the chance to access channel for the owned packets. As a result, under these conditions, the in-ranged nodes will consume the most of allowed bandwidth. Whereas, the dierence of bandwidth between the out-ranged source nodes is bounded by the curves (Out-ranged_Min, Out-ranged_Max) for each trac priority.

Logically, for the same problem explained above, the allocated bandwidth for the out-ranged source nodes of level ( 2) is more than that of level [START_REF]+ &1-+ , &+ $ +[END_REF]. And also, the allocated bandwidth for the source nodes of level ( 3) is more than that of level (4), and so on for each trac priority.

Therefore, these dierent resource allocations between source nodes lead to the unfairness explained, which is resolved by FQ-EDCA.

Indeed, because of the strength of FQ-EDCA, it can separate the illbehaved sources. As well, we observe that the allocated bandwidth for all priorities are equal. That leads to minimize the end-to-end delay of the outranged sources with balance, as seen in table 4.10. And also, FQ-EDCA balances the average lost packet.

As a result, in these simulations, FQ-EDCA enhances EDCA and guarantees services by implementing the fairness in large topologies. Thereby, the QoS is optimized with FQ-EDCA in these topologies. As well, this will be shown in the next section.

Chapter 4 : FQ-EDCA 4.6 Network Performance of FQ-EDCA throughput of all nodes. Therefore, throughput can be stated as (4.6):

T hroughput of a N ode = T otal Received Data Bits Simulation Runtime (4.6)

Similarly, the throughput for the network can be described as (4.7):

N etwork T hroughput = Sum of N odes ′ T hroughput N umber of N odes (4.7)

End-to-End Delay

The end-to-end delay is the time taken for a data packet to reach the destination node. The term "End-to-End" means from an end-point sender to an end-point receiver.

When the simulations are performed with a random topology, the destination, that has the maximum number of hops from the sender, receives data packet with maximum delay. Therefore, the delay can be stated as (4. Moreover, the delay for a packet is the time taken for it to reach the destination. And the average delay is calculated by taking the average of delays for every data packet transmitted successfully. Thus, the average delay of the network can be stated as (4.9):

AverageDelay = Sum of all P acket Delays T otal N umber of Received P ackets (4.9)

Delivery Ratio

It refers to the percentage of the transmitted data packets that are successfully received over all sent packets. The all sent packets are considered as; the summation of the dropped packets and the received packets. However, it is an important metric, which can be used as an indicator to a congested network. In other words, the delivery ratio is calculated as the Chapter 4 : FQ-EDCA 4.6 Network Performance of FQ-EDCA percent of received packets to the sent packets. Therefore, the delivery ratio can be calculated as (4.10):

Delivery Ratio = N umber of Received P ackets N umber of T ransmitted P ackets * 100%

(4.10)

And the same thing for the delivery ratio of the network as stated in (4.11):

N etworkDeliveryratio = Sum of Delivery ratios N umber of N odes (4.11)

Another metric of the network performance is the energy consumption. However, in our studies is neglected, because we focuses our studies in the network performance for data transmission. Now, we will analyze the performance of FQ-EDCA.

The performance analysis of FQ-EDCA

To evaluate the performance of FQ-EDCA, we will implement it in real topologies with dierent number of nodes and dierent data transmission rates. Thus, random topologies are applied for this evaluation. These topologies are generated by using topology generation tool (built on the random waypoint algorithm) implemented in the network simulator (NS2). However, as seen in gures below, multiple topologies are applied for different number of nodes distributed randomly to achieve real benets and make FQ-EDCA applicable in the real worlds. Also, these topologies are applied for two purpose. The rst is for the network performance measurements, and the second is for the end-to-end performance measurements.

The performed simulations

The simulations are performed for last topologies (from 5 to 50 nodes). However, these nodes are enumerated from (0) to (N -1), where N is the number of nodes for each topology. Thereby, the number of source nodes equals to (N -1) for each topology. Every source node sends its packets to a random destination with a constant baud rate. Whereas, the baud rate is the user sending rate in bits per seconds. However, the simulations are repeated for dierent baud rates, see table 4.11. So, high baud rates make the network behavior overloaded. That leads to a congestion in the network. Also, this leads to increase the ill-behaved sources which consume the most of network resources.

All the nodes are distributed randomly except 2 nodes, which are enumerated with 0 and (N -1). These nodes are considered as the end-points, marked as receiving end-point and sending end-point. This distribution is made intentionally to obtain the end-to-end measurements. These measurements are essential for end-to-end QoS comparison.

The parameters of performed simulations are stated in table 4.11. However, these simulations are applied with the same parameters for both EDCA and FQ-EDCA, to compare their results.

Network Throughput

As described, the network throughput is a metric of the network performance, which can describe the general state of the network trac.

Thus, as seen of the curves of EDCA in gure 4.24, we remark that, in EDCA, the network throughput increases when increasing the baud rate until the source nodes consume the most resources of the network. And also, it is clear that when the number of nodes is high the network throughput is minimized, because the number of collisions and retransmissions are increased. Thus, for large number of source nodes with heavy load, this degrades the network throughput.

On the other hand, as seen of the curves of FQ-EDCA in gure 4.24, we remark that, in FQ-EDCA, the Network throughput is increased with increasing the baud rate until the source nodes consume the most resources of the network. And also, it is clear that FQ-EDCA enhances the network throughput of EDCA specially for small number of source nodes. Also, this enhancement is minimized for increasing the number of source nodes, because the number of collisions and retransmissions is still high.

Moreover, in network throughput analysis, we cannot conclude the benets of FQ-EDCA over EDCA, because in both models they utilize the available resources of the network. Further, it does not take into account the dierentiating between routed and owned packets and the fairness. While, the main enhancement of FQ-EDCA is to apply fairness. For that reason, they have nearly the same average network throughputs, specially for the network throughputs of 20 nodes and above.

In addition, in FQ-EDCA, almost all the source nodes have the chance to send their packets. While, (30 -50%) of source nodes are dead nodes in EDCA, specially for large number of source nodes and high baud rate. Thus, the source nodes of one-hop destination (in-ranged nodes) have the most of resource allocations than the source nodes of multi-hop destination (out-ranged nodes) in EDCA. While, the fairness of resource allocation is applied between the source nodes of one-hop and multi-hop destination in Indeed, in general for both FQ-EDCA and EDCA, they have the same phenomenon of network throughput. That means, the complexity of FQ-EDCA is still like EDCA with taking into account the enhancement that will be obtained for other metrics of performance.

Further, let us present the end-to-end network performance.

End-to-end Throughput

The end-to-end throughput is an important metric of the network performance and QoS, which can describe the end-to-end throughput for the longest path trac. This path is established between sending and receiving endpoints. Thus, as seen of the curves of EDCA in gure 4.25, we remark that, in EDCA, the end-to-end throughput is increased with increasing the baud rate until the source nodes consume the most resources of the network. Then, the end-to-end throughput is decreased, because of the lack of resources. And also, it is clear that when the number of source nodes is increased, the end-to-end throughput is minimized, because the number of collisions and retransmissions are increased. Thus, for large number of source nodes with heavy load, the number of ill-behaved sources is increased. Therefore, this degrades the end-to-end throughput and makes it reach to zero.

While, as seen of the curves of FQ-EDCA in gure 4.25, we remark that the end-to-end throughput in FQ-EDCA is more stable and robust. This makes the QoS guarantee is increased. So, it is clear that FQ-EDCA enhances EDCA and the end-to-end throughput.

End-to-end delay

The end-to-end delay is an important metric of the network performance and QoS, which can describe the worst case path delay between sending and receiving end-points.

Chapter 4 : FQ-EDCA

Conclusion

As seen of the curves of EDCA in gure 4.26, we remark that in EDCA, the end-to-end delay is increased exponentially with increasing the baud rate of senders. This delay becomes innity (dead link) with increasing the number of source nodes for xed baud rate.

While, as seen of the curves of FQ-EDCA in gure 4.26, we remark that in FQ-EDCA, the end-to-end delay is increased slowly with increasing the number of source nodes and the baud rate of senders. That means, FQ-EDCA minimizes the end-to-end delay and enhances the QoS guarantee, as expected.

End-to-end delivery ratio

The end-to-end delivery ratio is a metric of the network performance and QoS, which can describe the percentage of received packets between sending and receiving end-points.

Thus, as seen in gure 4.27, we remark clearly that, FQ-EDCA increases the end-to-end delivery ratio better than EDCA, which enhances the QoS guarantee. While in EDCA, the end-to-end delivery ratio decreased faster than FQ-EDCA whit increasing the number of source nodes or their baud rate.

Conclusion

As expected, FQ-EDCA has proved that it can guarantee the QoS better than EDCA, with taking into account that its complexity like EDCA. Thereby, FQ-EDCA solves the most of problems of EDCA, such as fairness of resource allocations, separating the ill-behaved sources, giving the chance for the multi-hop sources to transmit, etc. FQ-EDCA is veried for simple, large and random topologies. FQ-EDCA is evaluated comparable with EDCA. As a result, FQ-EDCA is a robust, fairly and controllable model. It has the ability for enhancing and optimizing the QoS in wireless networks. routing and non-routing nodes. Thus, it enhances locally EDCA by treating the packets queued in a routing node and dierentiating between the trafc that belongs to that node, and the trac that belongs to its neighbors. So, F-EDCA treats the trac locally between the routing nodes and their neighbors.

Conclusion

On the other hand, in chapter 4, we have compared FQ-EDCA with EDCA. Thereby, it is clear by the results obtained that FQ-EDCA enhances EDCA by allocating the network resources with fairness. As described, FQ-EDCA dierentiates the data ow packets of the source nodes to be queued in separate queues, with taking into account the control packets buered in separate one queue. This idea enhances EDCA by supporting the ability to treat the packets of all source nodes with fairness, and separating the ill-behaved sources that consume the majority of the network resources. Therefore, FQ-EDCA enhances the end-to-end delivery packets by enhancing the end-to-end throughput and delay for all the source nodes, specially multi-hop nodes (out-ranged nodes).

However, another comparison is needed between F-EDCA and FQ-EDCA, Chapter 5 : FQ-EDCA vs. F-EDCA 5.1 The comparison of simulations because both of them enhance EDCA with fairness. So, this comparison will present the level of enhancement for each model and observe the dierent behaviors by increasing the number of source nodes and their sending rate (baud rate (kbps)). A s a result, dierent network performance will be obtained after the simulations of these models, as described in the next section.

The comparison of simulations

Network Simulator 2 (version 2.31 of ns-allinone (NS2)) is chosen to implement and evaluate this comparison.

Therefore multi scenarios are applied to evaluate the comparison between F-EDCA and FQ-EDCA.

However, for each scenario, the performed topology is illustrated in gure 5.1. This topology is considered as a real topology because each node is positioned randomly. This topology is generated by using topology generation tool (built on the random waypoint algorithm) implemented in the network simulator [START_REF]Network Simulator 2[END_REF].

Also, the scenarios are performed with dierent baud rates (i.e. 50kbps, 100kbps and 1Mbps). However, the simulations are started by letting the sending end-point to emit its packets to the receiving end-point (destination). Then, after each two seconds, each source node starts transmitting to a random destination. For each scenario, all the source nodes are sending their packets with the same baud rate. So, each source node is sending one ow with constant baud rate, constant bit-rate CBR/UDP trac applications and constant packet size, see table 5.1.

In addition, to realize the comparison, bottlenecks and heavy loads of trafc ows should be applied in the network. For that reason, the CBR/UDP trac is implied in each simulation. So, this is the case considered in the performed scenarios to show the ability of F-EDCA and FQ-EDCA for treating the congestion and the queued packets.

The results of simulations

The obtained results are divided in two parts. The rst one describes the network performance and the end-to-end results (i.e. end-to-end throughput and end-to-end delay) between the sending end-point to the receiving endpoint for baud rates (50-100kbps). These end-points draw the longest path of routing between the sender and the receiver. On the other hand, the second part describes the network performance and the end-to-end results for high baud rate (1Mbps).

So, let us show you the evaluations of these models, as following.

Network performance and end-to-end results

The network performance could present the performance of a model. Thereby, it is measured by how this model exploit the network resources. Therefore, as seen in gure 5.2, we remark that the network throughput is increased with increasing the number of source nodes depending on their baud rates. Thus, the value of the network throughput approaches to the maximum value (sending baud rate) when the number of source nodes is almost 15. Then, with increasing the number of source nodes, the network throughput starts to decrease depending on the baud rate, almost for 50kbps at 50 nodes and for 100kbps at 25 nodes. As a consequence, the curve of FQ-EDCA is decreased slowly. While, the curve of F-EDCA is decreased a little bit faster than FQ-EDCA. So, this makes FQ-EDCA is better than F-EDCA for the network throughput. Further, when there are source nodes that almost cannot access the channel because of the congestion, these nodes are treated as Dead-nodes. These nodes try to attempt for accessing the channel, which is dicult to achieve, because of the congestion and the ill-behaved sources that consume the majority of network resources and make access the channel is hard. Therefore, depending on the sending baud rate, in F-EDCA, there is a lot of dead-nodes while in FQ-EDCA it is almost disappeared, because FQ-EDCA separates the ill-behaved sources.

Chapter 5 : FQ-EDCA vs. F-EDCA

The results of simulations

However, for the end-to-end results, gure 5.3 describes the end-to-end throughput for the longest path trac. So, the value of the end-to-end throughput approaches to the maximum value (sending baud rate). Then, with increasing the number of source nodes, the end-to-end throughput starts to decrease depending on the baud rate, almost for 50kbps at 50 nodes and for 100kbps at 25 nodes. As a consequence for baud rate 50kbps, the average end-to-end throughput of FQ-EDCA is decreased and almost approaches to an average throughput (15kbps) for 99 source nodes. While, the average end-to-end throughput of F-EDCA is decreased and almost approaches to a low average throughput (≈ 2kbps) for almost 40 source nodes.

Further, as seen in gure 5.3, the average end-to-end throughput of FQ-EDCA is decreased and almost approaches to an average throughput (30kbps) for 99 source nodes. While, the average end-to-end throughput of F-EDCA is decreased and almost approaches to a low average throughput (≈ 2kbps) for almost 75 source nodes.

As a conclusion, FQ-EDCA is better than F-EDCA for the end-to-end throughput. Thus, the end-to-end delay is aected, as seen in gure 5.4. So, for baud rate 50kbps, the end-to-end delay started with 80ms. Then, it is increased for 50 source nodes. It is clear that the curve of F-EDCA increased faster than the curve of FQ-EDCA with taking into account that zero of packets received within the marked periods, because of the congestion and the ill-behaved sources that make access the channel is hard. Indeed, at these periods, the calculations of delay depends on the packets received. So, when there is no packets received, it consider the delay of packets is zero. That means, there is no change on the average delay calculations.

Further, as seen in gure 5.4 for baud rate 100kbps, the end-to-end delay started with 40ms. Then, it is almost increased for 15 source nodes in F-EDCA and for 25 source nodes in FQ-EDCA. It is clear that the curve of F-EDCA increased faster than the curve of FQ-EDCA with taking into account that zero of packets received within the marked periods for the problem described above.

Chapter 5 : FQ-EDCA vs. F-EDCA

Conclusion

EDCA and F-EDCA have almost the same network throughput. On the other hand, in FQ-EDCA, there is no Dead-nodes. That means, all the nodes have the chance to send with almost the same resource allocations.

Also, with the same explication above, the end-to-end analysis for the FQ-EDCA is better than F-EDCA, as seen in gure 5.6. Where, in FQ-EDCA, the end-to-end throughput is reached almost to 40kbps as an average value when the number of source nodes is equal to 99. While, in F-EDCA, the end-to-end throughput is reached almost to zero when the number of source nodes is equal to 20.

Moreover, in gure 5.6, the end-to-end delay of F-EDCA is increased exponentially when increasing the number of source nodes. And it follows the behavior of EDCA because both of them do not separate the ill-behaved sources that consume the majority of bandwidth. While, in FQ-EDCA, the worst case of the end-to-end delay is increased almost linearly.

Conclusion

The network performance is an important metric. It almost describes the performance of how exploit the most of resources available in the network. Nevertheless, it cannot describe other existing problems like the ill-behaved sources. These sources could absorb the most of network resources without taking into account the other source nodes. Therefore, this problem leads to unfairness of resource allocation.

By the analysis of the end-to-end performance, FQ-EDCA has more performance than F-EDCA, for throughput and delay. And also, it is a powerful model for end-to-end QoS specially for a large number of source nodes. That means, in FQ-EDCA, the worst case of the end-to-end delay is increased almost linearly with increasing the number of source nodes.

As expected, FQ-EDCA enhances the QoS guarantee better than F-EDCA. Because FQ-EDCA solves the most problems in EDCA, such as fairness of resource allocations, separating the ill-behaved sources, give the Further, we conclude that FQ-EDCA is strong and can be applied for large topologies (as tested in 100 source nodes with high baud rate).

However, we can say that FQ-EDCA is a global model. While, F-EDCA is a local model, because F-EDCA does not solve the problem of the illbehaved sources. So, F-EDCA treats the fairness locally between the routing nodes and their neighbors. But both of them enhanced EDCA for QoS in dierent judged situations. Indeed, F-EDCA treats the problem of fairness by dierentiating the routing and non-routing nodes. While, FQ-EDCA treats the problem of fairness by dierentiating the source nodes. Finally, we conclude that our models have good enhancement of QoS guarantees.

Chapter 6

Conclusions and perspectives

As seen in EDCA, no control management is applied to control the ill-behaved (mischievous) source nodes (i.e. In-ranged). So, the Out-ranged sources suer from the unfairness of resource allocations. FQ-EDCA has a robust treatment of the congestion. Therefore, FQ-EDCA is classied within the queue-based enhancements. We have implemented FQ-EDCA that supports control management of trac ows that is performed by hierarchical scheduling techniques. Thereby, it enhances EDCA by applying a fair resource allocation model to the source nodes. Thus, FQ-EDCA separates the ill-behaved sources that routing the ows of the out-ranged source nodes. As a consequence, with FQ-EDCA, the performed congestion is controlled. Each source node has a guarantee service like the others. And also, an end-to-end delay is decreased and bounded for the out-ranged sources and the average lost rate packets for all the source nodes is balanced also. So, FQ-EDCA solves most of the problems of EDCA, such as fairness of resource allocations, separating the ill-behaved sources, giving the chance to transmit for the multi-hop sources, etc.

However, the analysis of the network performance, FQ-EDCA has more performance than EDCA for throughput, delay and delivery ratio. And also, it is a powerful model for end-to-end QoS. That means, in FQ-EDCA, the worst case of the end-to-end delay is increased almost linearly when increasing Chapter 6 : Conclusions and perspectives This should enhance the fairness of allocation resources for mobile hosts (i.e. varying network topology) in ad-hoc wireless networks and guarantee the end-to-end QoS.

A perspective of this study is to evaluate FQ-EDCA, to verify the scalability of this model and to propose a model to be able to guarantee end-to-end QoS in ad-hoc networks performed for almost all the topologies.

Further, a fusion of both F-EDCA and FQ-EDCA could have a good advantage to enhance fairness for dierent sides, because FQ-EDCA can separate the ill-behaved sources and F-EDCA can dierentiate between the routing and non-routing nodes.

However, enhancing the technology of WiMAX by adopting our models is constructive also. This enhancement could evaluate the scalability of our models to apply fairness.

Glossary

• AAS -Adaptive Antenna System

• ABR -Available Bit Rate Titre : Modèles d'équité pour l'amélioration de la qualité de service dans les réseaux sans l en mode ad-hoc L'objectif de ce travail est l'amélioration de la qualité de service (QdS) dans les réseaux sans l ad-hoc avec équité. La QdS dans les réseaux sans l ad-hoc est actuellement dénie par la norme IEEE802.11e (EDCA). Elle permet de garantir l'accès prioritaire aux ressources pour le trac de priorité élevé (trac temps réel et trac multimédia). Elle est mise en uvre dans chaque station par la classication des paquets dans diérentes le d'attente caractérisant chacune une classe de trac à laquelle est associée une priorité de traitement. Toutefois, EDCA n'est pas un protocole équitable. En eet, lorsque un nud participe au routage du trac des ces voisins, son trac propre se trouve réduit. Pour résoudre ce problème, nous proposons un nouveau modèle appelé F-EDCA. Ce modèle permet à un nud routeur d'accéder plus régulièrement au réseau en fonction de son taux d'occupation. Une autre forme de non équité résulte de la position d'un nud source par rapport au nud destination. Plus le nud source est éloigné, moins il a de bande passante. Pour résoudre ce problème, nous proposons FQ-EDCA. Il améliore la QdS en distinguant dans chaque classe de trac, une le d'attente par source de trac. Le modèle met alors en uvre des techniques d'ordonnancement équitable en se basant sur la technique du temps virtuel. Ainsi, les ressources sont allouées équitablement entre tous les nuds. F-EDCA et FQ-EDCA sont mis en uvre et évaluées de manière comparative avec EDCA. Ce travail montre que chacun d'eux améliore EDCA et pourrait allouer équitablement les ressources dans des conditions diérentes et augmenter la garantie de la QdS.

Mots clés : Ad-hoc, Ordonnancement, Equité, Réseau sans l, IEEE802.11e, EDCA. Title: Fairness models to improve the quality of service in ad-hoc wireless networks This thesis aims to enhance the quality of service (QoS) in wireless ad-hoc networks with fairness. The QoS in wireless ad-hoc networks is referred to the standard IEEE802.11e (EDCA) to guarantee the high priority trac (i.e. Multimedia and Real-time tracs). Further, the QoS is managed in each station by dierentiating the packets in categories to be queued depending on their priorities. Then, these packets will access the channel in dierent waiting time. However, EDCA cannot control the heavy trac caused by the ill-behaved users. So, if the trac is regulated with fairness, it could resolve some of networks' problems like the congestion and starvation. These problems degrade the QoS guarantee, because the ill-behaved sources consume the majority of the allocated resources. That leads to some of source nodes suer from the lack of bandwidth and unfairness. So, without a proper control mechanism, it could decrease the QoS guarantees. Therefore, we propose (FQ-EDCA) that is a Fairness Queuing model for EDCA. It enhances the QoS by implementing scheduling techniques and improving the architecture of EDCA. Thereby, the trac is regulated between the source nodes by separating the ill-behaved sources. Thus, the resources are allocated fairly between all the source nodes. Further, a fairness model (F-EDCA) is proposed to dierentiate between two source nodes. One of them is routing packets of its neighbors and the other is only sending its packets. Both of these models are implemented and evaluated with EDCA. As a consequence, each of them enhances EDCA, could allocate the resources with fairness in dierent conditions and increase the QoS guarantee.

Keywords: Quality of Service, Ad-hoc, Scheduling, Fairness, Wireless Networks, IEEE802.11e, EDCA.

  Raed À mes s÷urs Manal, Maram et Hadeel leaky bucket rate, (B): the incoming rate is bigger than the leaky bucket rate and (C): the incoming rate is bigger than leak bucket rate with dropped packets. . . . . . . . . . . . . . 61 2.11 Token Bucket scheme; (A): the incoming rate is less than the token rate, (B): the incoming rate is bigger than the token rate with non-empty bucket, (C): the incoming rate is bigger than the token rate with empty bucket. . . . . . . . . . . . . . 62 2.12 (A) Scheduling with the simple method FIFO, (B) Scheduling with fairness. . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 2.13 Round-robin scheduling . . . . . . . . . . . . . . . . . . . . . . 67 2.14 an example of SP scheduling . . . . . . . . . . . . . . . . . . 68 2.15 A model expresses LLQ and CB-WFQ architectures. . . . . . 69 2.16 GPS serves two sessions. . . . . . . . . . . . . . . . . . . . . . 71 2.17 PGPS serves two sessions. . . . . . . . . . . . . . . . . . . . . 73 3.1 The topology of simulations (node (B) is a routing node, nodes (A,C) are non-routing nodes and nodes (D,E and F) are sink nodes) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.2 BW allocation for routing node (B) and non-routing nodes(A,C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 3.3 Model of F-EDCA . . . . . . . . . . . . . . . . . . . . . . . . 89 3.4 EDCA default behavior (without fairness) . . . . . . . . . . . 92 3.5 F-EDCA behavior (with fairness) . . . . . . . . . . . . . . . . 93 3.6 Throughput of routed packets in node (B) . . . . . . . . . . . 93 3.7 Delay of ows routed by node (B) . . . . . . . . . . . . . . . 94 3.8 Delay of node (B)'s ow . . . . . . . . . . . . . . . . . . . . . 95 4.1 An example to dene the ill-behaved sources . . . . . . . . . 99 4.2 Model of FQ-EDCA . . . . . . . . . . . . . . . . . . . . . . . 103 4.3 A small example explains the rst level scheduling in FQ-EDCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 xi LIST OF FIGURES LIST OF FIGURES 4.4 Topology (I) is a chain topology, where the source nodes(A,B and C) send data to D. Topology (II) is a T topology, where the source nodes(A,B and C) send data to D. And topology (III) is a tree topology, where the source nodes(A, B, C and E) send data to D. . . . . . . . . . . . . . . . . . . . . . . . . 112 4.5 EDCA default behavior in the rst scenario . . . . . . . . . . 114 4.6 FQ-EDCA behavior in the rst scenario . . . . . . . . . . . . 115 4.7 Total Bandwidth of resource allocations in scenario (I) for both FQ-EDCA and EDCA . . . . . . . . . . . . . . . . . . . . . . 116 4.8 EDCA default behavior in the second scenario . . . . . . . . 117 4.9 FQ-EDCA behavior in the second scenario . . . . . . . . . . . 117 4.10 Total Bandwidth of resource allocations in scenario (II) for both FQ-EDCA and EDCA . . . . . . . . . . . . . . . . . . . 119 4.11 EDCA default behavior in the third scenario . . . . . . . . . 120 4.12 FQ-EDCA behavior in the third scenario . . . . . . . . . . . 121 4.13 Total Bandwidth of resource allocations in scenario (III) for both FQ-EDCA and EDCA . . . . . . . . . . . . . . . . . . . 122 4.14 Topology of (45) source nodes organized with multi-hop distribution around (1) sink node. . . . . . . . . . . . . . . . . . 124 4.15 Comparison between FQ-EDCA and EDCA for Voice trac priority . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 4.16 Comparison between FQ-EDCA and EDCA for Video trac priority . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 4.17 Comparison between FQ-EDCA and EDCA for Best-eort trac priority . . . . . . . . . . . . . . . . . . . . . . . . . . 126 4.18 A random topology of 10 nodes . . . . . . . . . . . . . . . . . 131 4.19 A random topology of 15 nodes . . . . . . . . . . . . . . . . . 131 4.20 A random topology of 20 nodes . . . . . . . . . . . . . . . . . 131 4.21 A random topology of 30 nodes . . . . . . . . . . . . . . . . . 131 4.22 A random topology of 40 nodes . . . . . . . . . . . . . . . . . 132 4.23 A random topology of 50 nodes . . . . . . . . . . . . . . . . . 132 xii LIST OF FIGURES LIST OF FIGURES 4.24 The network throughputs of EDCA and FQ-EDCA for 10, 20, 30, 40 and 50 nodes . . . . . . . . . . . . . . . . . . . . . . . . 135 4.25 The end-to-end throughput in EDCA and FQ-EDCA for 10, 20, 30, 40 and 50 nodes . . . . . . . . . . . . . . . . . . . . . . 137 4.26 The end-to-end delay in EDCA and FQ-EDCA for 10, 20, 30, 40 and 50 nodes . . . . . . . . . . . . . . . . . . . . . . . . . . 139 4.27 End-to-end delivery ratio in EDCA and FQ-EDCA for 10, 20, 30, 40 and 50 nodes . . . . . . . . . . . . . . . . . . . . . . . . 140 5.1 A random topology of 100 nodes . . . . . . . . . . . . . . . . . 145 5.2 The comparison of the network throughput for dierent baud rates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 5.3 The comparison of the end-to-end throughput for dierent baud rates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 5.4 The comparison of the end-to-end delay for dierent baud rates149 5.5 The comparison of the network throughput for baud rate 1Mbps151 5.6 The comparison of the end-to-end throughput and delay for baud rate 1Mbps . . . . . . . . . . . . . . . . . . . . . . . . . 153 xiii List of Tables 1.1 The characteristics of the WLAN standards . . . . . . . . . . 1.2 The comparison between the standards of WPAN, WLAN and WMAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 the times of the IFS for multiple versions of IEEE802.11 . . . 2.1 Assured Forwarding (AFxy) levels, with its DSCP . . . . . . . 2.2 Comparison between IntServ VS. DiServ . . . . . . . . . . . 2.3 The values of parameters of EDCA assigned for each user priority that mapped for each AC. . . . . . . . . . . . . . . . . . 2.4 The possible routing paths between nodes A and D . . . . . . 2.5 An example of GPS and its packet emulation PGPS that illustrates the comparison between two sessions. . . . . . . . . . 3.1 The parameters of simulations . . . . . . . . . . . . . . . . . . 4.1 The serving sequence for each queued packet in the small example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 The parameters of simulations . . . . . . . . . . . . . . . . . . 4.3 Delay comparison between EDCA vs. FQ-EDCA in Scenario I 4.4 The average lost packet rate between EDCA vs. FQ-EDCA in Scenario I . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Delay comparison between EDCA vs. FQ-EDCA in Scenario II xiv

  06) is the Wireless Local Area Networks. It is the most famous wireless networks. That represents the basic standard of IEEE802.11(IEEE 97). It is referred to the commercial term (Wi-Fi). However, Wi-Fi is a trademark registered for WECA (Wireless Ethernet Compatibility Alliance), with which the wireless devices of WLAN based on IEEE802.11 are certied. This certication grants the interoperability between the dierent Chapter 1 : Wireless Networks 1.2 Wireless Network Technologies wireless devices of WLAN.

1. 3

 3 The operation modes in WLAN IEEE802.11 can operate in two modes: Chapter 1 : Wireless Networks 1.4 MAC access channel 1.4 MAC access channel IEEE802.11 denes two basic techniques to access the channel, which are related to the mode of operation in the wireless network. Further, these techniques take place in MAC layer.

  It avoids, prevents, handles and recovers the network congestion. Therefore, a lot of proposals treat the congestion, such as; (Kesh 91), RED (Floy 93), WRED (Wurt 02), RIO (Clar 98). The last two proposals are extensions of RED (Random Early Detection) for challenging feedback problem (implicit feedback via dropped packets) with supporting QoS. RIO is RED with In/Out, which supports by dierentiating the input and the output ows. However, Internet trac shows self-similar behavior in the TCP/IP networks that leads to the global synchronization. Also, there are many of implementations for congestion control over TCP such as (RFC2b; Brak 95). Further, the explicit congestion notication (ECN) (Rama 01; Floy 94) passes a congestion information (one bit of ECN is implemented in IP header) Chapter 2 : Quality of Services (QoS) 2.3 QoS in Wired networks back to senders when the packet is dropped by the queue management.

•

  Chapter 2 : Quality of Services (QoS) 2.3 QoS in Wired networks as we will see in DiServ. 2.3.2 DiServ (Dierentiated Services) DiServ (RFC2a; Cisc 05; Auri 04; Loch 04) is a class-based mechanism. It is a coarse-grained control system aggregation of ows into Per-Hop Behavior (PHB) groups. So it is a mechanism that treats data trac separately in aggregate behaviors. That make the DiServ to be scalable not like IntServ. Its principle works on the provisioned QoS model, where network elements are set up to service multiple classes of trac with varying QoS requirements. Each router on the network is congured to dierentiate trac based on its class. Each trac class can be managed dierently, insuring preferential treatment for higher priority trac on the network. The DiServ model does not make judgment on what types of trac should be given priority treatment since that is left up to the network operator (SLA).

Figure 2

 2 Figure 2.7: The Inter-frame access scheme for IEEE802.11e

Chapter 2 :

 2 Quality of Services (QoS) 2.4 QoS in Wireless loads, which can reduce the trac quality in the network. There are many of proposal that incorporate the QoS mechanisms of wired networks into wireless networks (Maha 01; Xu 05; Chan 07; Gall 07; Nian 02). (Maha 01) proposes an experimental framework for supporting QoS in wireless networks using Dierentiated services (DiServ). However its results show that the need for a signaling and messaging protocol, which considers the variable bandwidth and mobility characteristics of the network, as opposed to the implicit admission control of DiServ network. And also, the need for signaling and bandwidth allocation is important when the user moves between regions. QoS based on applications suer from interruptions during a wireless connection link because of an overhead caused by route discoveries that leads to an extra heavy trac. Therefore, to avoid this, stability routing is needed (Gerh 03); resource constraints to support dierent demands for trac classes that need DiServ to achieve the optimal utilization. Unfortunately, DiServ principles need the high layers (i.e. Network layer) to obtain the optimal utilization and guarantee QoS, although IEEE802.11e classies the trac in MAC layer. Also, many of researches of QoS enhancement in ad-hoc wireless networks mainly focus on station-based DCF enhancement scheme such as (Nait 03; Bhar 94; Aad 01) or queue-based enhancement scheme such as (Mang 02; Romd 03; Wiet). Further, (Nian 04) enhance a schema of QoS in wireless networks However, EDCA still has the problems of transmission and access channel such as hidden and exposed terminals problems (Kose 08).

Chapter 2 :

 2 Quality of Services (QoS) 2.5 Layer QoS technologies for LAN. And they could not be considered as a complete solution (End-toend QoS) without taking into account the upper layers protocols and their specications. 2.5.2 Network layer technologies (Layer 3) Upon this layer, the end-to-end QoS solutions could be considered and evaluated. Recently, a lot of approaches are developed to enhance the QoS solutions. The main models are IntServ (RFC1) and DiServ (RFC2a; Cisc 05) presented in section 2.3 2.5.3 Transport layer (Layer 4) Port priority is the simplest way to indicate the priority for the type of data (ex. Port 21 for FTP low priority). Although, TCP/UDP are the most famous protocols in the internet world, they could not guarantee QoS requirements for the upper layer (i.e. the application layer). Thus, Real-time Transport Protocol (RTP) (RFC3 03a) is developed and used extensively for real-time and media streams applications. Further, there are some approaches applied for QoS enhancement in transport layer, such as SCTP (Stream Control Transport Protocol) (RFC2c; Stew 00) and AOTP (Application-Oriented Transport Protocol)(Tsao 00). AOTP is oriented for applications of upper layer and provide their requirements of QoS. Thereupon, AOTP supports transport services, with new functionality added specically, to trade o reliability, throughput and/or jitter. While, SCTP could be considered to meet the application requirement and translate them to the lower layers to achieve the end-to-end QoS. Further, another enhancement of SCTP applied in wireless environment (Ma 03). These protocols are developed to replace the ancient protocols (UD-P/TCP), because the last ancient protocols could not completely meet the strict requirements of the upper layer. Chapter 2 : Quality of Services (QoS) 2.6 Trac shaping and policing 2.5.4 Application layer technologies (Upper layer)

Further, both

  of F-EDCA and FQ-EDCA are enhancements for MAC Chapter 2 : Quality of Services (QoS) 2.8 Conclusion layer. While, routing protocols are applied over MAC layer to satisfy an end-to-end QoS requirement for mobile hosts wireless networks (MANET).

  could evaluate a pure study of fairness resource allocations for EDCA in (Abuz 09c; Abuz 08) is a fairness model for QoS optimization in wireless network. It aims to develop and optimize the QoS with fairness in wireless ad-hoc networks. As discussed in Chapter 2, IEEE802.11e (EDCA) (IEEE 05a) enhances the original standard by enhancing the Distributed Coordination Function (DCF).

Figure 3 . 1 :

 31 Figure 3.1: The topology of simulations (node (B) is a routing node, nodes (A,C) are non-routing nodes and nodes (D,E and F) are sink nodes)

Figure 3

 3 Figure 3.2: BW allocation for routing node (B) and non-routing nodes(A,C)

Chapter 3 : F-EDCA 3 . 3 Figure 3 . 3 :

 33333 Figure 3.3: Model of F-EDCA

Chapter 3 :

 3 F-EDCA 3.5 The results of rst simulations

Figure 3 .

 3 Figure 3.4: EDCA default behavior (without fairness)

Figure 3 .Figure 3 . 6 :

 336 Figure 3.5: F-EDCA behavior (with fairness)

Figure 3 . 8 :

 38 Figure 3.8: Delay of node (B)'s ow

  4. The values of average lost Chapter 4 : FQ-EDCA 4.4 The results of simulations

  An extension of FQ-EDCA simulations

Chapter 4 :

 4 FQ-EDCA 4.6 Network Performance of FQ-EDCA

4.6. 4

 4 The results of the performed simulations After the simulations, many of measurements are obtained to analyze the performance of FQ-EDCA and compare it with EDCA. the results are obtained as following:Chapter 4 : FQ-EDCA 4.6 Network Performance of FQ-EDCA

Figure 4 .

 4 Figure 4.24: The network throughputs of EDCA and FQ-EDCA for 10, 20, 30, 40 and 50 nodes

Figure 4 .Figure 4

 44 Figure 4.26: The end-to-end delay in EDCA and FQ-EDCA for 10, 20, 30, 40 and 50 nodes

β

  Chapter 5 : FQ-EDCA vs. F-EDCA5.2 The results of simulations

Chapter 5 :

 5 FQ-EDCA vs. F-EDCA 5.3 Conclusion chance to transmit for the multi-hop sources, etc. While, in the network performance (i.e. network throughput), they have almost the same behavior. As a result, FQ-EDCA is a robust, fairly and controllable model. It has the ability for enhancing the QoS in wireless networks. While, F-EDCA is a fairly model. That has the ability to enhance locally the QoS with fairness in wireless networks.In addition, as illustrated in FQ-EDCA curves behavior, the average network throughput is almost equal to the average end-to-end throughput. That means, the end-point source node has almost the same allocated resource as the average resource allocated to other nodes. Therefore, FQ-EDCA achieves the required fairness. Thereby, it enhances end-to-end QoS with fairness.

•

  ACK -Acknowledgment• AF -Assured Forwarding• AODV -Ad-hoc On-demand Distance Vector• AP -Access Point • AQR -Asynchronous QoS Routing • ATM -Asynchronous Transfer Mode • BA -Behavior Aggregate • BE -Best Eort Service • BER -Bit Error Rate • BR -Bandwidth Routing • BS -Base Station • BSS -Basic Service SetGlossary • TBP -Ticket-Based Probing • TCP -Transmission Control Protocol • TDMA -Time Division Multiple Access • TDM -Time Division Multiplexing • TDR -Trigger-based Distributed Routing • TOS -Type Of Service • UDP -User Datagram Protocol • UL -Uplink • VC -Virtual Channel • VLAN -Virtual Local Area Network • VoIP -Voice over Internet Protocol • WiMax -Worldwide Interoperability for Microwave Access • WLAN -Wireless Local Area Network • WPAN -Wireless Personal Area Network • WRED -Weighted Randomly Early Detected • ZRP -Zone Routing Protocol

  3. And they have dierent signal modulations, as seen in table 1.2.

	Chapter 1 : Wireless Networks	1.2 Wireless Network Technologies
	Table 1.1: The characteristics of the WLAN standards The standard Release date Maximum Frequency
			BW (Mbps)	Band
				(GHz)
	802.11	1997	2	2.4
	802.11a	1999	54	5
	802.11b	1999	11	2.4
	802.11g	2003	54	2.4
	802.11e	2005	11;54	2.4;5
	802.11n	2009	540	2.4;5

• IEEE 802.11e: it denes the Quality of Service (QoS) supported for WLANs. It is an enhancement to the legacy IEEE802.11a/b/g. That means, it uses the PHY layer specications of IEEE802.11a/b/g and enhances the MAC layer. This enhancement can support the QoS guarantees for the real-time and the multimedia applications and maintain the compatibility with IEEE802.11a/b/g standards for WLAN. It will be described in details in the state of the art (see section 2.4).

Table 1 .

 1 2: The comparison between the standards of WPAN, WLAN and WMAN

	Chapter 1 : Wireless Networks	1.3 The operation modes in WLAN
	Technology WMAN	WLAN	WPAN
	Commercial	WiMAX	Wi-Fi	Bluetooth ZigBee
	name
	Standards	IEEE802.16e IEEE802.11	802.15.1 802.15.4
			(a,b,g,n)
	Release year 2005	1999, 1999,	2002	2006
			2003, 2009
	Frequency	2-66GHz	2.4GHz,	2.4Ghz 2.4GHz
	Band		5GHz
	Coverage	Wide area	Local area	Personal area 10m
		50km	100m-2km
	Maximum	>100Mbps	540Mbps	3Mbps 250kbps
	BW
	Number of	Thousands Dozens	<Dozen	Dozens
	users
	Transmission	MIMO,	MIMO,	FHSS	DSSS
	Method	OFDMA	OFDM,
			DSSS,
			FHSS

A comparison that summarize the dierence between the various technologies of the wireless networks, is presented in table 1.2.

  ). The rst six bits contain the DiServ Code Points Chapter 2 : Quality of Services (QoS) 2.4 QoS in Wireless Table 2.2: Comparison between IntServ VS. DiServ

	Comparison	IntServ	DiServ
	Packets classication Granularity of service State in routers Trac classication Signaling protocol Flow aggregation Coordination of service Priority service Scalability limited Network management	ows individual ow per ow several header elds required(RSVP) ne-grained global (End-to-End) for each ow by number of ows as circuit switching net-works	classes aggregate ows per aggregate DS eld not required coarse-grained local (Per-Hop) for each class by number of service classes as existing IP networks

Table 2 .

 2 3:The values of parameters of EDCA assigned for each user priority that mapped for each AC.As seen in table 2.3, AIFSN is equal or bigger than 2. Thereby, AIFS can be determined by (2.1). Thus, the lowest AIFS can accelerate back-o countdown and vice versa. So, AIFS is equal to DIFS, which is the minimum arbitrary waiting time for the highest priority.

	AC Trac Type User ity Prior-	AIFSN CW min CW max
	AC_BK Background 1	7	31	1023
		Background 2
	AC_BE Best Eort 0	3	31	1023
	AC_VI	Video	3	2	15	31
		Video	4
		Video	5
	AC_VO	Voice	6	2	7	15
		Voice	7

AIF S(AC) = SIF S + AIF SN (AC) * SlotT ime

  • W r(AC, i, t) is the amount of routed packets to send in bytes, which belong to other nodes and queued in AC of node i at time t.These approaches modied the parameters of CW min and CW max . For example, RAMAC had modied the parameters of the legacy DCF by reducing

	• (t) is the time of unsuccessful access channel (collision).
	Indeed, equations (2.4, 3.3) have the same goal, which is to make the rout-
	ing node access the channel more frequent than non-routing node. However,
	in F-EDCA, we have modied the equation (2.4) to (3.3), because MACAW,
	RAMAC and other approaches are proposed and implemented for pure DCF.

Table 3

 3

	.1: The parameters of simulations
	Standards	IEEE802.11b/e
	QoS	EDCA
	Topology mode	ad-hoc
	Routing protocol	DSDV
	Routing nodes	B
	Non-routing nodes	A and C
	Sink nodes	D, E and F
	Number of ows	6 (All ows have the same priority)
	Type of ows	CBR/UDP
	Distance between nodes	150m
	Transmission range	250m
	CWmin	3
	CWmax	1023
	β	1
	Packet size	1472 bytes
	Packet interval	[5ms, 10ms]
	Bandwidth	11Mbps
	Time of simulation	200s

  [START_REF]+ &1-+ , &+ $ +[END_REF] The simulations of FQ-EDCA in simple topologies 4.[START_REF]+ &1-+ , &+ $ +[END_REF] The simulations of FQ-EDCA in simple topolo-

	gies
	Network Simulator 2 (version 2.31 of ns-allinone (NS2)

Table 4 .

 4 5: Delay comparison between EDCA vs. FQ-EDCA in Scenario II

			EDCA			FQ-EDCA
	AC	A	B	C	A	B	C
	AC_BK	-	-	0.2s	1.1s	1.1s	1s
	AC_BE	0.42s 0.48s 20ms	78ms	78ms	73ms
	AC_VI	31ms 31ms	9ms	17ms	17ms	16ms
	AC_VO	8ms	8ms	6ms	7ms	7ms	7ms

Table 4

 4

	.6: The average lost packet rate between EDCA vs. FQ-EDCA in
	Scenario II		EDCA			FQ-EDCA
	AC	A	B	C	A	B	C
	AC_BK	100% 100% 97%	98%	98%	98%
	AC_BE	99%	99%	79%	94%	94%	94%
	AC_VI	89%	89%	45%	78%	78%	78%
	AC_VO	41%	40%	0%	26%	26%	26%

Table 4 .

 4 10: Delay comparison between EDCA vs. FQ-EDCA

	AC VO VI BE	Nodes 3 9 21 45 3 9 21 45 3 9 21 45	EDCA In-ranged Out-ranged Out-ranged In-ranged Out-ranged Out-ranged FQ-EDCA Min Max Min Max 30ms 30ms 30ms 30ms 30ms 30ms 30ms 30ms 30ms 30ms 30ms 30ms 50ms 0.2s 0.5s 50ms 50ms 0.2s 70ms 0.1s 7s 0.3s 0.3s 0.6s 30ms 30ms 30ms 30ms 30ms 30ms 30ms 30ms 30ms 30ms 30ms 30ms 0.2s 0.5ss 2s 0.5s 0.5s 0.7s 0.6s 1s 25s 2s 2s 2.5s 30ms 30ms 30ms 30ms 30ms 30ms 50ms 0.1s 0.2s 80ms 90ms 0.1s 0.3s 1s 30s 1s 1s 1.6s ---2s 2s 5s

Table 4 .

 4 11: The parameters of performed simulations

	Standards	IEEE802.11b/e
	QoS	EDCA & FQ-EDCA
	Topology mode	ad-hoc
	Routing protocol	DSDV
	Source nodes	5 -50
	Type of ows	CBR/UDP
	Transmission range	250m
	Carrier sense range	550m
	Packet size	512bytes
	Packet baud rate	10 -100kbps
	Bandwidth	1M bps

Chapter 3 : F-EDCA3.6 Conclusionin ad-hoc networks, as presented in chapter 4. And also, this can be done by regulating β with modifying the parameters of CW min ,C W max and AIFSN for each AC.

The function arg min stands for the argument of the minimum, that is to say, the set of points of the given argument for which the value of the given expression attains its minimum value. arg min x f (x) = {x|∀y, f (x) f (y)}

Remerciements

FQ-EDCA model has been developed and implemented using network simulator (ns-2) to study the throughput, average delay and fairness performance, and to compare them with the recent standards of wireless networks (i.e. the IEEE802.11e (EDCA) ).

Before evaluating the network performance of our model, we will dene the performance metrics.

Performance Metrics

Several metrics can be dened to grade the performance of our model (FQ-EDCA) against the recent standards (IEEE802.11e) in ad-hoc wireless networking for QoS (EDCA). Therefore, some of these metrics have been carefully chosen to give an idea of the behavior and the reliability of FQ-EDCA in ad-hoc wireless networks.

However, these metrics measure the data transmission's features with respect to data packets. As a consequence, the analysis focuses on the benets obtained by FQ-EDCA compared with other models. An explanation of these metrics follows:

Network Throughput

It is a measure of the amount of data (Bytes) transmitted from the source to the destination in a unit period of time (seconds). Considering the data rates and throughputs supported by IEEE802.11 standard, the throughput is measured in total bits received per second. Also, this metric only measures the total data throughput over the network.

The throughput of a node is measured by rst counting the total number of data packets successfully received at the node, and computing the number of bits received, which is nally divided by the total simulation runtime.

The throughput of the network is nally dened as the average of the 4.6 Network Performance of FQ-EDCA

Conclusion

By the analysis of the network performance, FQ-EDCA has more performance than EDCA for throughput, delay and delivery ratio. And also, it is a powerful model for end-to-end QoS.

Chapter 6 : Conclusions and perspectives the number of source nodes. While, in EDCA or F-EDCA, the end-to-end delay is increased almost exponentially. Thus, End-to-end QoS for FQ-EDCA could be applied by adopting DiServ of network layer in wireless networks, like (Nian 04).

Further, as illustrated in FQ-EDCA results, the average network throughput is almost equal to the average end-to-end throughput. That means, the end-point source node has almost the same allocated resource as the average resource allocated to other nodes. Thereby, FQ-EDCA achieves the required fairness. Therefore, it enhances the end-to-end QoS with fairness.

On the other hand, F-EDCA is a fairness model for EDCA. Whereas, a lot of researches for QoS enhancement in ad-hoc wireless networks mainly focus on station-based DCF enhancement scheme or queue-based enhancement scheme. F-EDCA has merged the station-based DCF and queue-based enhancements. Therefore, we have implemented F-EDCA that supports resource allocation with fairness in the architecture of EDCA by taking into account dierentiation between wireless node stations (Routing and Nonrouting nodes). Thus, the routing node can access the channel more frequently than other nodes when there is a collision. As a consequence, each routing node has an extra bandwidth (depending on the percentage of routed packets) to compensate the deduction of its bandwidth that is needed for forwarding neighbors' packets.

Therefore, F-EDCA treats partially the hidden terminal problem and avoids the congestion by allocating fairly the resources. Thus, the misbehaving of resource allocations for non-routing nodes could be resolved locally by F-EDCA.

Further, F-EDCA could be classied as soft or local QoS approach that treats the resource allocations between a routing node and its neighbors.

While, FQ-EDCA could be classied as global QoS approach that treats the resource allocations for all the source nodes.

Our future works is to combine our models (i.e. F-EDCA and FQ-EDCA) with QoS routing protocols in mobile ad-hoc networks (MANET) (IETFb).

Chapter 7 Annexe 7.1 Network Simulation (NS-2)

Network simulator 2 (NS2), is an object-oriented and discrete event simulator targeted at networking research (i.e. Wired, Wireless, Satellite, etc.). Thus, it is an open code application functions under Unix/Linux.

However, not all users use NS-2 under Unix/Linux (Ritc 78), because an emulator of Unix (Cygwin) (cygw) functions under Microsoft Windows (Micr).

Further, most recent release of NS-2 is ns-2.33 (released Mar 31, 2008). In our simulations, we had used NS-2.31 network simulator. That version is compatible with the EDCA model (Wiet; TKN) to be implemented.

Creating a wireless scenario

All conguration parameters of the simulation and the parameters of the dierent objects created (nodes, agents, etc.) are passed to the simulator as an input le (*.tcl).

However, there are two types of output les can be obtained as a result of simulation:

• trace les (*.tr).

Chapter 7 : Annexe 7.1 Network Simulation (NS-2)

• animation les (*.nam).

Generating tools

NS-2 has utilities to generate ad-hoc topologies and scenarios:

• setdest: generates movement pattern les using the random waypoint algorithm • cbrgen: random trac pattern for wireless scenarios 7.1.3 The functionality of NS-2 NS-2 denes the objects of the simulation and set their parameters. Thereby, these objects are connected to each other. Then, it denes the topology of the network. However, it starts the source applications (tracs). And at the end, it exits the simulator after a certain xed time, or when a particular event happens.

Implementing a model in NS-2

To implement a model in NS-2, it is a hard work, because it depends on the functionality of the model. Indeed, there is two main languages to program the codes of the required model as:

• TCL/OTCL (TCL): Tool Command Language (TCL) for programing the events of scenarios. The object oriented of TCL (OTCL) is to code the interfaces with C++ language in NS-2.

• C/C++ (Kern 78): It is a famous object oriented language for programing the function codes of the model. That means, if the model is an event model, it could be coded by TCL.

While, C++ is the language to implement a model with functions or develop the infrastructure of model. However, in our implementation of F-EDCA and Chapter 7 : Annexe

Network Simulation (NS-2)

FQ-EDCA, we had implemented EDCA, as described in (TKN). Then, we implement our models by using the C++ language in (*.cc, *.h) les. These les exist in the folder of NS-2 (ns-2.31/mac/802_11e) as following:

• F-EDCA model is implemented in the les: mac-802_11e.h, mac-802_11e.cc, priq.h, priq.cc and priority.tcl.

• FQ-EDCA model is implemented in the les: d-tail.h, d-tail.cc, mac-802_11e.h and mac-802_11e.cc.

Therefore, after implementing these models, the C++ les are ready to be compiled and used by NS-2.

Glossary

• BSSID -Basic Service Set Identication 5; ( -/66/ ;?3 =/<+3> 6+ :</73T</ N =/ >/<738/< /6+ :/<7/> ./ :<3@36U13/< 6/= 036/= .I+>>/8>/= -98>/8+8> ./= :/>3>= :+;?/>= -977/ +? .U><37/8> ./ -/66/= ;?3 98> ./= :+;?/>= ./ >+366/ 37:9<>+8>/ 7+B 738 + = IU;?+>398 :/<7/> +:<T= -2+;?/ -C-6/ ./ ><+3>/7/8> </-+6-?6/< 6+ .+>/ ./ 6I29<691/ @3<>?/66/ ( '8/ 093= =U6/->3988U :+< 6/ 7U-+83=7/ ./ $ =-2/.?6381 6/ :+;?/> @+ :+==/< ./?B +?></= 9<.988+8-/7/8>= ,+=U= =?< 6+ :<39<3>U -97:+<U/ ./= 06?B ./ 7+83T</ N <U=9?.</ 6/= -9663=398= @3<>?/66/= +@/-=93> ?8 :+;?/> ./ -98><Z6/ @93</ ./= :+;?/>= =U6/->3988U= :9?< 6/= +?></= -6+==/= ./ ><+03-/ 79.T6/ + U>+3> U@+6?/< :+< =37?6+>398 =9?= !% ./ 7+83T</ .I?8/ :+<> N @U<303/< =+ -+:+-3>U N <U=9?.</ 6/ :<9,6T7/ .IU;?3>U ./ =9?<-/ #9?< -/6+ 89?= 6I+@98= -97:+<U N =?< ./= >9:96913/= 0+-36/7/8> +8+6C=+,6/= -977/ -/66/ ./ 6+ 31?</ /= 31?</ /> 31?</ 366?=></8> 6+ .300U</8-/ .IU;?3>U /8></ /> $ "8 :/?> @93< ;?/ :9?< >9?>/= 6/= -6+==/= ./ ><+03-+:<T= ?8 ><+8=3>93</ ./ ;?/6;?/= 7= >9?>/= 6/=