IETF MANET Working Group Hakim Badis INTERNET-DRAFT LIX, Ecole Polytechnique, France Expires: October 21, 2006 Project Hipercom, INRIA, France April 2006 CEQMM: A Complete and Efficient Quality of service Model for MANETs draft-badis-manet-ceqmm-00.txt Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on October 21, 2006. Copyright Notice Copyright (C) The Internet Society (2006). Abstract This draft specifies CEQMM, a Complete and Efficient Quality of Service (QoS) Model for MANETs which combines the positive aspects of both IntServ and DiffServ. It uses a hybrid per-flow and per-class provisioning scheme. In such a scheme, traffic of highest priority is Badis Expires October 2006 [Page 1] INTERNET-DRAFT CEQMM April 2006 given per-flow provisioning while other priority classes are given per-class provisioning. To offer this scheme and to ensure that certain packets receive higher priority transmission than other packets, priority classifier, active queue management and packet scheduler are integrated. CEQMM applies the QOLSR protocol to support multiple-metric routing criteria and to respond quickly when changes in topology and/or QoS conditions are detected. Once a path is chosen for one QoS flow, CEQMM performs call admission control (CAC) at each intermediate node. For only QoS flows of highest priority, a node can precede to soft and later hard bandwidth reservation on links during the CAC process. CEQMM implements congestion avoidance mechanisms to prevent a network from entering the congested state. However, in MANETs, network congestion can still occur frequently under mobility. In order to prevent performance degradation due to mobility-triggered congestion, CEQMM uses congestion control scheme based on: (i) rated control of best-effort traffic in the originator node, (ii) path selection for best-effort traffic, (iii) active queue management and (iv) backoff timer method. Badis Expires October 2006 [Page 2] INTERNET-DRAFT CEQMM April 2006 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Useful Definitions . . . . . . . . . . . . . . . . . . . . . . 6 3. CEQMM Characteristics . . . . . . . . . . . . . . . . . . . . . 8 4. Overview of the Architecture . . . . . . . . . . . . . . . . . 9 5. The QOLSR Protocol . . . . . . . . . . . . . . . . . . . . . . 11 5.1 Neighbor Sensing . . . . . . . . . . . . . . . . . . . . . 11 5.2 QoS Measurement on Links . . . . . . . . . . . . . . . . . 11 5.3 Multipoint Relay Selection . . . . . . . . . . . . . . . . 12 5.4 Quality of Service Multipoint Relay Selection . . . . . . 12 5.5 QMPR and QOS Conditions Information Declaration . . . . . 12 5.6 Routing Table Calculation . . . . . . . . . . . . . . . . 12 6. Call Admission Control . . . . . . . . . . . . . . . . . . . . 14 6.1 CREQ Message Format. . . . . . . . . . . . . . . . . . . . 14 6.2 CREQ Message Generation . . . . . . . . . . . . . . . . . 16 6.3 CREQ Message Processing . . . . . . . . . . . . . . . . . 17 6.4 CREP Message Format . . . . . . . . . . . . . . . . . . . 19 6.5 CREP Message Generation . . . . . . . . . . . . . . . . . 20 6.6 CREP Message Processing . . . . . . . . . . . . . . . . . 20 7. Bandwidth Reservation . . . . . . . . . . . . . . . . . . . . 21 7.1 Reservation Maintenance . . . . . . . . . . . . . . . . . 22 7.2 Rebuilding Broken Routes . . . . . . . . . . . . . . . . . 22 8. Priority classifier . . . . . . . . . . . . . . . . . . . . . . 23 9. Active Queue Management . . . . . . . . . . . . . . . . . . . . 23 9.1 The Need for Active Queue Management . . . . . . . . . . . 24 9.2 The Queue Management Algorithm "CEQMM-RED" . . . . . . . . 25 9.2.1 Estimation of Average Queue Size . . . . . . . . . 26 9.2.2 Packet Drop Decision. . . . . . . . . . . . . . . . 26 10. Packet Scheduling . . . . . . . . . . . . . . . . . . . . . . 28 11. Congestion Avoidance and Control . . . . . . . . . . . . . . . 29 11.1 Network Congestion Detection. . . . . . . . . . . . . . . 29 11.2 Best-effort Rate Control. . . . . . . . . . . . . . . . . 30 11.3 Dealing with Congestion . . . . . . . . . . . . . . . . . 30 12. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . . 31 13. TLV Encoding for QoS Metrics . . . . . . . . . . . . . . . . . 32 14. Security Considerations . . . . . . . . . . . . . . . . . . . 32 15. References . . . . . . . . . . . . . . . . . . . . . . . . . . 32 16. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 34 17. Full Copyright Statement . . . . . . . . . . . . . . . . . . . 34 18. Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . 34 Badis Expires October 2006 [Page 3] INTERNET-DRAFT CEQMM April 2006 1. Introduction The QoS Model specifies the architecture which will enable users to offer services that operate better than the current best-effort model that exists in MANets. This architecture SHOULD take into consideration the challenges of Mobile Ad Hoc Networks (MANETs) e.g., dynamic topology and time-varying link capacity. In addition, the potential commercial applications of MANETs require the seamless connection to the Internet. Thus the QoS model for MANETs SHOULD also consider the existing QoS architectures in the Internet. CEQMM [1], a Complete and Efficient Quality of Service (QoS) Model for MANETs, is designed to combine knowledge from the solutions offered in the wire-based networks and apply them to a new QoS model which will take into consideration the characteristics of MANETs. The basic idea of that model is that it uses both per-flow state property of IntServ and service differentiation of DiffServ. In other words, this model proposes that highest priority is assigned per flow provisioning and other priority classes are given per-class provisioning. Since the states of per-flow granularity come from only a small fraction of the traffic, the scalability problem in IntServ does not exist. To offer this hybrid scheme and to ensure that certain packets receive higher priority transmission than other packets, priority classifier, active queue management and packet scheduler are integrated in the CEQMM architecture. The priority classifier differentiates between control, QoS and best-effort traffic. It directs the received packets to the corresponding queue according to the priority level. The queue management algorithms control the queue size by dropping packets if necessary. Scheduling algorithms determine which packet is served next among packets in queues. In this first CEQMM draft, only two classes are used: QoS traffic class and best-effort traffic class. QoS traffic class is given per-flow provisioning. Control traffic is enqueued in a separate queue and assigned the highest priority than the data traffic to maintain the most recent information about the network topology and QoS conditions. CEQMM applies the QOLSR protocol [2,3] to support multiple-metric routing criteria and to respond quickly when changes in topology and/or QoS conditions are detected. This protocol can find optimal paths on the known partial topology having the same bandwidth performances that those on the whole network. For best-effort traffic, QOLSR finds shortest paths under the congestion metric threshold (constraint) to reduce the intra-flow contention and to relieve congestion. When congestion occurs, best-effort path Badis Expires October 2006 [Page 4] INTERNET-DRAFT CEQMM April 2006 selection reduces the overhead in the network by maintaining the stability of the QoS paths as long as possible. The path's available bandwidth revised by the amount of intra-flow contention is used as the rate limit of the best-effort traffic at the originator node. For QoS traffic, QOLSR computes optimal or quasi-optimal paths according to multiple constraints specified by the application. Once a path is chosen for one QoS flow, the originator node cannot guarantee the end-to-end QoS requirements. This is due to: (i) the partial topology obtained by TC messages used for path selection, (ii) the congestion and (iii) the mobility. The validity of the path MUST be checked to admit a new flow at the originator node, usually referred to as Call Admission Control (CAC). Using CEQMM, each intermediate node on the selected path checks locally the QoS constraints. For only QoS flows of highest priority, a node can precede to soft and later hard bandwidth reservation on the links during the CAC process. This ensures that no two QoS flows initiated simultaneously will contend for the same resource. CEQMM uses congestion avoidance techniques to prevent a network from entering the congested state. It applies the CAC process, best-effort rate control and active queue management. Under the mobility, the topology may change after a QoS flow is admitted, resulting in changes of the traffic distribution in the network. Thus, congestion may still occur under mobility even though there is enough bandwidth at the time of flow admission. In order to prevent performance degradation due to mobility-triggered congestion, CEQMM uses congestion control scheme based on: (i) rated control of best-effort traffic in the originator node, (ii) QOLSR routes selection for best-effort traffic, (iii) active queue management, and (iv) backoff timer. By dropping packets before buffers overflow, active queue management allows nodes to control when and how many packets to drop. This mechanism solves both lock-out and full queues problems. Once congestion occurs, the node before the congested link computes a new path (next-hop) for its current sending and forwarding best-effort traffic and drops some best-effort flows in the queue to relieve congestion. It also informs the network about this congested link by diffusing a TC message with the new congestion metric value. Each node in the network receiving this message computes a new path for its best-effort traffic. Only originator nodes limit their best-effort rates to the new available bandwidth. If the congestion persists, originator nodes using the congested links as part of their QoS traffic's paths decide to change the route after a backoff time. Some QoS flows may also be suspended under heavy congestion. Badis Expires October 2006 [Page 5] INTERNET-DRAFT CEQMM April 2006 CEQMM operates on a best-effort MACs and can include heterogeneous nodes with different radio capabilities. CEQMM specification uses conventional meanings [4] for capitalized words such as MUST, SHOULD, etc., to indicate requirement levels for various protocol features. 2. Useful definitions * Flow A flow is a sequence of packets sent from a particular originator, and a particular application running on the originator host, using a particular host-to-host protocol for the transmission of data over the network, to a particular (unicast or multicast) destination, and particular application running on the destination host, or hosts, with a certain set of traffic, and quality of service requirements. * Best-effort traffic (or best effort flow) Best-effort traffic is a flow generated by an application that doesn't request any special QoS control service. * QoS traffic (or QoS flow) QoS traffic is a flow which has a special QoS control requirement (e.g. in term of bandwidth). * Intergrated Services (IntServ) IntServ architecture [5] allows sources to communicate their QoS requirements to routers and destinations on the data path by means of a signaling protocol such as RSVP [6]. Hence, IntServ provides per-flow end-to-end QoS guarantees. IntServ defines two service classes: guaranteed service and controlled load, in addition to the best-effort service. The guaranteed service class guarantees to provide a maximum end-to-end delay, and is intended for applications with strict delay requirements. Controlled load, on the other hand, guarantees to provide a level of service equivalent to best-effort service in a lightly loaded network, regardless of network load. This service is designed for adaptive Badis Expires October 2006 [Page 6] INTERNET-DRAFT CEQMM April 2006 real-time applications. As is the case in the Internet, IntServ is not appropriate for MANETs, because the amount of state information increases proportionally with the number of flows, which results in scalability problems. * Differentiated Services (DiffServ) DiffServ architecture [7] avoids the problem of scalability by defining a small number of per-hop behaviors (PHBs) at the network edge routers and associating a different DiffServ Code Point (DSCP) in the IP header of packets belonging to each class of PHBs. Core routers use DSCP to differentiate between different QoS classes on per-hop basis. Thus, DiffServ is scalable but it does not guarantee services on end-to-end basis. This is a drawback that hinders DiffServ deployment in the Internet, and remains to be a drawback for MANETs as well, since end-to-end guarantees are also required in MANETs. In DiffServ, we can identify three different classes: expedited forwarding, assured forwarding, and best-effort. Expedited forwarding provides a low delay, low loss rate, and an assured bandwidth. Assured forwarding provides guaranteed/expected throughput for applications, and best-effort which provides no guarantee. * Congestion metric CEQMM relies on packet loss as an indication of network congestion. In MANETs packets may be lost due to: (i) unavailability of route in the routing table, (ii) buffer overflow, and (iii) next-hop is unreachable within the MAC retransmission thresholds. The point (iii) can be happen when the next-hop moves out of transmission range or collisions. The congestion metric is given by packet loss ratio due to only buffer overflow and collisions. This metric is used as an indication of collision presence. A second method for congestion metric representation is to use the wireless channel utilization ratio. This value can be obtained by monitoring the channel status. Badis Expires October 2006 [Page 7] INTERNET-DRAFT CEQMM April 2006 3. CEQMM Characteristics * Does the CEQMM define a set of service classes? Yes. However, this CEQMM draft uses two service classes: QoS class and best-effort class. The next draft update will give a predefined set of service classes. * Does the CEQMM support both per-flow state property of IntServ and the service differentiation of DiffServ? Yes. In this draft version, traffic of QoS class is given per-flow provisioning. The next draft update will use both per-flow state property of IntServ and the service differentiation of DiffServ. * Does the CEQMM support multi-constraint path QoS routing? Yes. This is ensured by the QOLSR protocol. * Does the CEQMM include admission control mechanism? Yes. * Does the CEQMM include bandwidth reservation mechanism? Yes. * Does the CEQMM include congestion avoidance mechanism? Yes. CEQMM tries to limit the network congestion appearance. * Does the CEQMM include congestion control mechanism? Yes. Badis Expires October 2006 [Page 8] INTERNET-DRAFT CEQMM April 2006 4. Overview of the Architecture An overview of the CEQMM architecture is illustrated in the following figure. Best-effort flow QoS flow | | v v +-----------------------------------------+ | QOLSR protocol |<---------------+ +-----------------------------------------+ | |HELLO & |Best-effort | | | TC | flow | | | v | | | +---------------+ |QoS flow | | |Rate control if| | | | |originator node| | | | +---------------+ v | | | +--------------------+ +---------------------+ | | | Admission control |<------| Metrics measurement | | | +--------------------+ +---------------------+ | | | | | Qos flow of | ^ | ^ | | | | |highest priority | | | | | | | |CREQ v v | | | | | | | +-------------------------+ | | | | | QoS flow| | | Bandwidth reservation | | | | | | | | +-------------------------+ | | | | | | | |Qos flow |CREQ | | | v v v v v v | | | +--------------------------------------------------+ | | | | Priority classifier | | | | +--------------------------------------------------+ | | | | | | | v | | | +----------------------+ | | | | Queue Management |-------------------+ | | +----------------------+ Dropped packet ratio | | | | | v | | +----------------------------------------------+ | | | Scheduler |<-----------------+ | +----------------------------------------------+congestion metric | | | v | +---------------------------------------------------------------------+ | MAC | +---------------------------------------------------------------------+ Badis Expires October 2006 [Page 9] INTERNET-DRAFT CEQMM April 2006 Both best-effort and QoS flows first enter the QOLSR protocol component to calculate optimal paths. This protocol is considered as the first step of admission control process, since QoS flows are rejected if no path that can meet the QoS requirements cannot be found. It is also considered as an important element of the congestion control scheme by dropping best-effort flows if no path satisfying the congestion metric threshold exists. Then, the best-effort flows of each node (except the originator node) are injected directly into the packet classifier without admission control. The originator node MUST first regulate its best-effort traffic rate using a control rate to reduce congestion with QoS flows. CEQMM MUST perform admission control for all QoS flows having paths to limit the packet drop and the end-to-end delay. For only QoS flows of highest priority, a node can proceed to soft and later hard bandwidth reservation on the links during the control admission process. Using the packet classifier, flows are classified into service classes each of which is buffered in a separate queue. To avoid network congestion, each originator node of best-effort traffic in the network limits its rate to the available bandwidth of its selected path revised by the amount of the intra-flow contention. Upon receiving a TC message indicating congested links, each node sending or forwarding best-effort flow computes a new route (next-hop) for this flow. The originator nodes of QoS traffic waits a backoff time which enables to avoid the long process of recalculating and maintaining a new path for QoS flows. The active queue management algorithm drops arriving packets probabilistically before queues overflow. The probability of drop increases as the estimated average queue size grows. The amount of the dropped packets is sent to metrics measurement component and used with packet loss ratio due to the collision problem as a congestion indication. The packet scheduler determines which packet is served next among packets in queues. It makes decision according to flow priority and congestion in the network. The metric measurements component estimates metrics values (available bandwidth, delay, jitter, loss probability, congestion metric, etc.) on links to each neighbor. These metrics are than communicated to the following components: QOLSR protocol, admission control, bandwidth reservation and scheduler. Badis Expires October 2006 [Page 10] INTERNET-DRAFT CEQMM April 2006 5. The QOLSR Protocol The QOLSR protocol [2,3] is an extension introduced to OLSR [8] to fulfill QoS requirements. It ensures that optimal metrics are made available along a route between communication partners. Additional fields about QoS conditions are added to HELLO and TC messages. No additional control messages are generated. Using the metric measurements component, a node computes QoS metrics like available bandwidth, delay, jitter, loss probability, cost, etc., on links to its neighbor nodes having direct and symmetric link. These QoS metrics information are used to calculate QoS MPRs (QMPRs) and then flooded in the network by TC messages to calculate routing tables. QOLSR routes contain only QMPRs as intermediate nodes between a source destination pair. As in OLSR, QOLSR uses MPRs to ensure that the overhead is as low as possible for forwarding control traffic. TC messages are generated By QMPRs and relayed by MPRs. QOLSR carried out different functions which are required to perform the task of routing. 5.1 Neighbor Sensing Each node detects the neighbor nodes with which it has a direct and bi-directional link. The uncertainties over radio propagation may make some links uni-directional. Consequently, all links MUST be checked in both directions in order to be considered valid. To accomplish this, each node periodically broadcasts HELLO messages, containing the information about its neighbors and their link status. These control messages are transmitted in broadcast mode. HELLO messages are received by all one hop neighbors, but they are not relayed to further nodes. 5.2 QoS Measurement on Links Using the metric measurements component, each node estimate the QoS conditions (available bandwidth, delay, congestion metric, loss probability, cost, security, power consumption, etc.) on links to each neighbor having direct and symmetric link. Afterwards, QoS conditions in vicinity are broadcasted using HELLO messages. Consequently, HELLO messages will permit each node to discover its neighborhood up to two hops and their QoS conditions. Badis Expires October 2006 [Page 11] INTERNET-DRAFT CEQMM April 2006 5.3 Multipoint Relay Selection Each node selects its MPR set from among its 1-hop symmetric neighbors. This set is selected such that it covers (in terms of radio range) all symmetric strict 2-hop nodes. The information required to perform this calculation is acquired through the periodic exchange of HELLO messages, as described in [8]. The MPR set is re-calculated when a change in 1-hop or 2-hop neighbor sets with bi-directional link is detected. 5.4 Quality of Service Multipoint Relay Selection Each node of the network independently selects its own set of QMPRs. This set is calculated to contain a subset of the 1-hop neighbors which provides maximum bandwidth and minimum delay from each 2-hop neighbor to the given node. The QMPR set needs not to be optimal, however it SHOULD be small enough to minimize the number of generated TC messages in the network. The information required to perform this calculation is acquired through the periodic exchange of HELLO messages. QMPRs of a given node are declared in the subsequent HELLOs transmitted by this node, so that the information reaches the QMPRs themselves. The QMPR set is re-calculated when a change in 1-hop or 2-hop neighbor sets with bi-directional link is detected; or a change is detected in their QoS conditions. 5.5 QMPR and QOS Conditions Information Declaration Topology Control extension messages are sent by each QMPR node in the network at regular intervals to declare its QMPR selector set and QoS conditions. The information diffused in the network by these TC messages will help each node to calculate its routing table. 5.6 Routing Table Calculation Each node maintains two routing tables: best-effort routing table and QoS routing table. Those tables are built from neighborhood and topology databases. The available bandwidth on links has tow values. The first value "Q_bw" is calculated using only QoS traffic in the vicinity. The second value "B_bw" is calculated considering both QoS and best-effort flows. "Q_bw" and "B_bw" values on links are used in the weighted topology to find respectively optimal paths for QoS and best-effort flows. The idea behind this method is to prioritize QoS Badis Expires October 2006 [Page 12] INTERNET-DRAFT CEQMM April 2006 traffic and to allocate the remaining bandwidth to the best-effort traffic. Each entry in the best-effort routing table consists of R_dest, R_next, R_dist, R_cong, R_bw which specifies that the node identified by R_dest is estimated to be R_dist hops away from the local node with congestion metric value R_cong and available bandwidth R_bw. The one hop neighbor node with address R_next is the next-hop node in the route to R_dest. Entries are recorded in the table for each destination in the network for which the route is known. R_time represents the validity time of the QoS flow. QOLSR uses an algorithm based on Lagrangian relaxation [10] to find the shortest path having the congestion metric value under a fixed threshold. Best-effort flows are rejected if no path that can meet the congestion metric requirement cannot be found. Each entry in the QoS routing table consists of R_id, R_next, R_res and R_time which specifies that the one hop neighbor node with address R_next is the next-hop node in the route selected for the Qos flow identified by R_id. R_id consists of the originator node address, the destination node address and the QoS requirements. R_res indicates the reservation type (none, soft or hard). QOLSR uses an algorithm based on Lagrangian relaxation to find the optimal path satisfying multiple constraints. Badis Expires October 2006 [Page 13] INTERNET-DRAFT CEQMM April 2006 6. Call Admission Control Once a path is chosen for one QoS flow, the source node cannot guarantee the end-to-end QoS requirements. Because paths are calculated using partial topology, and because of congestion and mobility, the validity of the path must be checked to admit a new flow at the originator node. This is usually referred to as Call Admission Control (CAC). A CAC can be carried out at the originator or distributedly at each hop in the path. An originator node needs information about the whole network topology to check if the flow is admissible. However, only links between QMPRs and QMPR selectors are advertised and thus each node has only partial topology information about the whole network (all the nodes but only some links). So, CAC at the originator node cannot be used with the QOLSR routing protocol. A CAC at each hop initialized by the originator node is more suitable for proactive protocols. The originator node sends out a Check REQuest (CREQ) message containing the entire path and the QoS requirements. For example, the amount of bandwidth desired for its new flow request (minimum bandwidth), the maximum delay, etc. An intermediate node on the selected path which receives the CREQ message MUST be able to meet the service requirements in order to forward the CREQ. If no CREQ message reaches the destination, it is unable to respond, and the originator node times out. The flow is then rejected as inadmissible. When the destination node receives a CREQ message, it sends a Check REPly (CREP) message back to the originator of the QoS flow. For strong guarantees, an intermediate node receiving a CREP message MUST perform once again a CAC on the link to the CREP sender (not to the next-hop). This allows that no two QoS flows initiated simultaneously will contend for the same resource. 6.1 CREQ Message Format CEQMM communicates using the same unified packet format defined in the OLSR protocol [8] for all data related to the Model. This provides an easy way of piggybacking different "types" (HELLO, TC, CERQ, CREP, etc.) of information into a single transmission, and thus for a given implementation to optimize towards utilizing the maximal frame-size, provided by the network. These packets are embedded in UDP datagrams for transmission over the network. The present document is presented with IPv4 addresses. Considerations regarding IPv6 are given in section 12. Badis Expires October 2006 [Page 14] INTERNET-DRAFT CEQMM April 2006 Each packet encapsulates one or more messages. The messages share a common header format, which enables nodes to correctly accept and (if applicable) retransmit messages of an unknown type. The proposed format of a CREQ message is as follows: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | reserved |RM |RT | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address[1] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address[2] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address[n] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS requirements | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS requirements | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ This is sent as the data-portion of the general message format with the "Message Type" set to CREQ_MESSAGE. The time to live SHOULD be set to the number of hops separating the source node and the destination. Reserved This field must be set to "0000000000000000000000000000" to be in compliance with this specification. RM This field indicates the reservation maintenance type: 00 : First CREQ message for this QoS flow. 01 : Refresh message. 10 : Flow releasing. Badis Expires October 2006 [Page 15] INTERNET-DRAFT CEQMM April 2006 RT This field indicates the bandwidth reservation type: 00 : Without reservation 01 : Soft reservation 10 : Hard reservation Address[1..n] The originator route indicates a sequence of hops, originating at the originator node specified in the Originator Address field of the message header, through each of the Address[i] nodes in the order listed in the CREQ message, ending with the destination node indicated by Address[n]. The number of addresses present in the Address[1..n] field is indicated by the Message Size field in the Message header (n = (Message Size/ 4) - 3). QoS requirements QoS requirements field is defined by QoS flow demand like minimum bandwidth, maximum delay, maximum delay jitter, maximum loss probability, etc. TVL (type/length/Value) encoding format is used to encode those (if exist) QoS metrics as follow: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type |Length | Value... | Type |Length | Value... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type and Length are fixed according to section 13. 6.2 CREQ Message Generation In order to check the validity of the path selected by the QOLSR protocol, the originator node MUST generate and send a CREQ message with RM = 00 (first CREQ message) to the destination. This message includes adding to the QoS requirements, all the hops of the path. CREQ is forwarded only by intermediate nodes specified in this message. Badis Expires October 2006 [Page 16] INTERNET-DRAFT CEQMM April 2006 CREQ messages are transmitted using the unicast mode. However, for QoS flows of less priority and to reduce the message overhead, CREQ messages can be transmitted using the broadcast mode in the same packet with the current HELLO and/or TC messages. In this first draft version, all the CREQ messages are transmitted as unicast packets. 6.3 CREQ Message Processing Upon receiving a CREQ message with RM = 00, a node MUST apply the following algorithm: 1 If the receiver address is not the last address of the intermediate nodes (not final destination) indicated in this message: 1.1 The receiver node extracts the next-hop address from the set of addresses given in this message, 1.2 If this next-hop node is not in the 1-hop neighborhood of the receiver, the message MUST be discarded. Exit. 1.3 The receiver MUST evaluate its QoS conditions including the QoS requirements values of this message on the link to its next-hop in the path, 1.4 If the receiver cannot satisfy one of the QoS requirements, this message MUST be discarded. Exit. 1.5 The receiver adds an entry to its QoS routing table by setting R_id to the flow identification, R_next to the next-hop address indicated in the set of addresses given in the message and R_res to SoftBW if the flow has bandwidth constraint. The originator node uses the same algorithm from step 1.2 before sending its CREQ message. In this case, the receiver node in the above algorithm is replaced by the originator. Badis Expires October 2006 [Page 17] INTERNET-DRAFT CEQMM April 2006 The step 1.3 allows the receiver node to decide if the new flow QoS requirements are meet on the link to its next-hop in the path. Considering this link, let (Bw_CREQ, Bw_link), (Del_CREQ, Del_link), (jitter_CREQ, jitter_link), etc., be respectively (available bandwidth indicates in the CREQ, available bandwidth on the link), (delay indicates in the CREQ, delay on the link), (jitter indicates in the CREQ, jitter on the link), etc. The evaluation process is as fellows: - For the bandwidth requirement: the receiver node MUST re-calculate its Bw_link adding the Bw_CREQ value to the rate of this link and to each link in the path within the intra-flow contention (contention between packets of the same flow). If the new available bandwidth on this link is bigger than 0, the link to the next-hop satisfies the minimum bandwidth requirement. - For the end-to-end delay requirement: if Del_link is bigger than Del_CREQ, the receiver node will simply discard the CREQ message. Otherwise, it subtracts from Del_CREQ its Del_link and includes this value as the new Del_CREQ in the forwarded CREQ. - For the jitter requirement: if jitter_link is bigger than jitter_CREQ, the receiver node will simply discard the CREQ message. Otherwise, it subtracts from jitter_CREQ its jitter_link and includes this value as the new jitter_CREQ in the forwarded CREQ. The received CREQ message is forwarded after modifying its QoS additive and multiplicative metrics requirements field’s values according to the CAC process. Badis Expires October 2006 [Page 18] INTERNET-DRAFT CEQMM April 2006 6.4 CREP Message Format The proposed format of a unicast CREP message is as follows: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved |RT | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address[1] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address[2] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Address[n] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS requirements | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS requirements | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ This is sent as the data-portion of the general message format with the "Message Type" set to RREQ_MESSAGE. The time to live SHOULD be set to the number of hops separating the source node and the destination. Reserved This field must be set to "000000000000000000000000000000" to be in compliance with this specification. RT This field indicates the bandwidth reservation type: 00 : Without reservation. 01 : Soft reservation. 10 : Hard reservation. Badis Expires October 2006 [Page 19] INTERNET-DRAFT CEQMM April 2006 Address[1..n] The destination node sends a unicast CREP using the reverse path indicated by Address[i] nodes in the order listed in the received CREQ message. I.e., the nodes of Address[i], 0| |||| Control traffic (highest priority) / +-------+ / +-----------------+ / +-------+ |Packet Classifier| / | |||| QoS traffic +-----------------+ +-------+ +-------+ | |||| Best-effort traffic (less priority) +-------+ An important factor in service differentiation is the queuing strategy. Several approaches have been proposed in the literature. In [12], two prioritization schemes for FQMM [13] are proposed. Firstly, a simple priority queue ensures that heigh-priority packets are given unconditional preference over low-priority packets. Secondly, they consider a FIFO queue which they enhance with a RIO buffer management (Random Early Discard with IN/OUT). SWAN [14] also conceptually uses a priority queue, but limits the amount of QoS traffic in order to protect the lower-priority traffic from starvation. With a FIFO queue it might occur that a high-priority packet is scheduled after a burst of low-priority traffic even if it is the only high-priority packet currently in the queue, regardless of whether a drop-tail queue or a more sophisticated approach like RIO is used for traffic shaping. Thus, a high-priority packet may suffer large delays. Badis Expires October 2006 [Page 23] INTERNET-DRAFT CEQMM April 2006 With priority queue, this is obviously prevented. A high-priority packet is scheduled before any lower-priority packets. Thus, its delay depends solely on the amount of high-priority packets currently in the queue and the medium contention in the node’s neighborhood. On the other hand, a priority queue might result in a starvation of low-priority traffic. When the amount of high-priority traffic is exceptionally high, low-priority traffic might not be transmitted at all or at a very low rate, because all the high-priority traffic is scheduled ahead of any low-priority traffic. Both SWAN and FQMM solve this problem by admitting only a predefined amount of high-priority traffic to be injected in the network. CEQMM uses a per-class queuing approach. Each queue is given a distinct priority. To avoid the starvation of low-priority traffic problem and to schedule a high-priority packet before any lower-priority packets, CEQMM implements a scheduling algorithm based on token balancing. CEQMM keeps the average queue size small and reduces the delays seen by QoS flows by using an active queue management to drop packets before queues overflow. The dropped packet ratio is transmitted to the metrics measurements component. 9.1 The Need for Active Queue Management The traditional technique for managing node queue lengths is to set a maximum length (in terms of packets) for each queue, accept packets for the queue until the maximum length is reached, then reject (drop) subsequent incoming packets until the queue decreases because a packet from the queue has been transmitted. This technique is known as "tail drop", since the packet that arrived most recently (i.e., the one on the tail of the queue) is dropped when the queue is full. This method has served the Internet well for years, but it has two important drawbacks. 1. Lock-Out In some situations tail drop allows a single connection or a few flows to monopolize queue space, preventing other connections from getting room in the queue. 2. Full Queues The tail drop discipline allows queues to maintain a full (or, almost full) status for long periods of time, since tail drop Badis Expires October 2006 [Page 24] INTERNET-DRAFT CEQMM April 2006 signals congestion (via a packet drop) only when the queue has become full. It is important to reduce the steady-state queue size, and this is perhaps queue management's most important goal. Besides tail drop, two alternative queue disciplines that can be applied when the queue becomes full are "random drop on full" or "drop front on full". Under the random drop on full discipline, a node drops a randomly selected packet from the queue when the queue is full and a new packet arrives. Under the "drop front on full" discipline, the node drops the packet at the front of the queue when the queue is full and a new packet arrives. Both of these solve the lock-out problem, but neither solves the full-queues problem described above. The solution to the full-queues problem is for nodes to drop packets before a queue becomes full, so that nodes can respond to congestion before buffers overflow. This proactive approach is called "active queue management". By dropping packets before buffers overflow, active queue management allows nodes to control when and how many packets to drop. This approach keeps the average queue size small and reduces the delays seen by QoS flows. It can also prevent lock-out behavior by ensuring that there will almost always be a buffer available for an incoming packet. 9.2 The Queue Management Algorithm "CEQMM-RED" CEQMM-Random Early Detection, or CEQMM-RED, is an active queue management algorithm for nodes that will provide the performance advantages cited in the previous section. It is based on the Random Early Detection (RED) [15], which prevents congestion through monitoring outbound queues to detect impending congestion, and randomly chooses and notifies senders of network congestion so that they can reduce their transmission rate [15]. CEQMM-RED applies the RED algorithm for each incoming data packet with the specified thresholds according to the queue class. It doesn’t use any explicit congestion notification like the RED algorithm. When congestion occurs, the node sends a TC message to inform all the nodes in the network about the congested links. Note: In order to maintain the most recent information about the network topology and QoS conditions, CEQMM uses the EQMM-RED algorithm only for data traffic classes. Control packets are not dropped when congestion occurs. Badis Expires October 2006 [Page 25] INTERNET-DRAFT CEQMM April 2006 In contrast to traditional queue management algorithms, which drop packets only when the buffer is full, the RED algorithm drops arriving packets probabilistically. The probability of drop increases as the estimated average queue size grows. Note that RED responds to a time-averaged queue length, not an instantaneous one. Thus, if the queue has been mostly empty in the "recent past", RED won't tend to drop packets (unless the queue overflows). On the other hand, if the queue has recently been relatively full, indicating persistent congestion, newly arriving packets are more likely to be dropped. The RED algorithm itself consists of two main parts: estimation of each average queue size and the decision of whether or not to drop an incoming packet. 9.2.1 Estimation of Average Queue Size For each queue, RED estimates the average queue size in units of packets. The estimate avgQ is a time-averaged queue length. Every packet arrival, the estimate is updated with the current queue size Q using a weight Wq: avgQ <-- avgQ + Wq (Q – avgQ). When a packet arrives at an empty queue, the queue idle time is tacked into account: the average is updated as many times as the number pf packets, m, that could have been transmitted during this period. I.e., avgQ <-- (1-Wq)^m avgQ. The node calculates the average queue size as if m packets of the same class have arrived to the corresponding queue with a queue size of zero and m can be computed as queue idle time/S with S an average queuing time in this queue. 9.2.2 Packet Drop Decision In the second portion of the algorithm, RED decides whether or not to drop an incoming packet. For each queue Qi, two RED parameters, minth_Qi (minimum threshold for the queue Qi) and maxth_Qi (maximum threshold for the queue Qi), figure prominently in this decision process. Minth_Qi specifies the average queue size *below which* no packets for Qi will be dropped, while maxth_Qi specifies the average Badis Expires October 2006 [Page 26] INTERNET-DRAFT CEQMM April 2006 queue size *above which* all packets for Q_i will be dropped. When the estimate avgQi is between the tow thresholds, randomization is used to decide whether the packet is accepted or not. The packet for queue Qi is dropped with probability P_a, given by P_b <-- maxp x (avgQi – minth_Qi)/(mawth_Qi – minth_Qi), P_a <-- p_b/(1 – count x p_b). When avgQi varies from minth_Qi to maxth_Qi, P_b varies linearly from 0 to maxp. To realize a uniformly distributed interdropping time, the final drop probability P_a also takes into account the "count" of packets that already have been accepted since the last dropped packets. Below the pseudo-code of the RED algorithm is given, amore detailed description can be found in [15]. Initialization avgQi = 0 count = -1 For each packet arrival destined for Qi Update the average queue size estimate, avgQi: If the queue is nonempty avgQ = (1 - Wq) x avgQ + Wq x Q, Else m = f(idle time, S), avgQ = (1 – Wq)^m x avgQ, If minth_Qi =< avgQi < maxthQi increment count, calculate probability P_a: P_b = maxp x (avgQi – minth_Qi)/(mawth_Qi – minth_Qi), P_a = p_b/(1 – count x p_b), With probability P_a drop the arriving packet, count = 0, Else If maxth_Qi =< avgQi drop the arriving packet, count = 0, Else count = -1, Note: the decision whether or not to drop an incoming packet can be made in "packet mode", ignoring packet sizes, or in "byte mode", taking into account the size of the incoming packet. The performance implications of the choice between packet mode or byte mode is discussed further in [16]. Badis Expires October 2006 [Page 27] INTERNET-DRAFT CEQMM April 2006 10. Packet scheduling Scheduling algorithms determine which packet is served next among packets in queues (next figure). A simple Packet scheduling strategy, based on the token bucket scheme, provides high priority to control and QoS traffic, and also protects the lower priority (best-effort) traffic from starvation. +----------+ Control traffic | |||| +----------+ \ \ +----------+ \ +-------------+ QoS traffic | |||| +->| Scheduler | +----------+ +-------------+ +----------+ Best-effort traffic | |||| +----------+ In this scheme, prioritization is achieved with token balancing. Each traffic class has a balance of tokens, and the class with higher balance has a higher priority when dequeuing the next packet for transmission. For each transmission of packet of class s, an amount Ws tokens is subtracted from the class' token balance and an equal fraction thereof is added to every other class' balance such that the sum of all tokens is always the same. The weight value Ws reflect the amount of the lower QoS requirements assigned to the different classes. A higher weight value Ws corresponds to lower QoS requirements. The size of the token balance together with the value Ws determines the maximal length of a burst of traffic from one class. In this scheme, as long as the amount of QoS flows does not to grow too large, it is forwarded as quickly as possible after traffic control forwarding, and if it does grow too large, starvation of best- effort flows is prevented. Setting the upper bound of a class' token balance depending on its QoS requirements enables further tuning of the described method. Badis Expires October 2006 [Page 28] INTERNET-DRAFT CEQMM April 2006 11. Congestion avoidance and control CEQMM uses congestion avoidance techniques to prevent a network from entering the congested state. It applies the CAC process, the best-effort rate control and the active queue management. However, in MANETs, network congestion can still occur frequently under mobility. The next Figure shows a simple case of flow congestion between Source1-Destination1 and Source2-Destination2 QoS flows. This situation can appear after nodes moving. Source1 a Source2 X---------X---------X | | | X---------X---------X Destination1 b Destination2 Thus, congestion control is needed to provide QoS in such situations. Once congestion occurs, the node before the congested link computes a new path for its best-effort traffic (to transmit or to forward), and then limits its rate to the new available bandwidth of that path. It also drops some best-effort flows (having the old next-hop) in the queue. Some QoS flows may also be suspended under heavy congestion. If the congestion persists on links transmitting QoS flows, the originator node of this QoS flow decides to change the route after a backoff time. 11.1 Network Congestion detection Network congestion detection is the first step needed to exercise congestion control. Congestion is straightforward to detect in wired networks. Usually, when congestion occurs, the queue at the bottleneck link will build up, or even overflow, causing packets drops. However, in multi-hop wireless networks, correctly detecting congestion of a neighborhood is difficult. The queue length is no longer a valid indication of congestion. The MAC layer usually retries a transmission for a limited number of times (e.g., default retry time in the IEEE 802.11 DCF is 7) before dropping a packet. Thus, a queue may not have yet build up at the early stage of congestion. To estimate the amount of overflow of the arcs' capacities, CEQMM scheme takes into account the packet loss ratio on each arc based on the number of packets dropped by the MAC layer due Badis Expires October 2006 [Page 29] INTERNET-DRAFT CEQMM April 2006 to the collision problem (NB: not to the mobility of the next-hop) and by the active queue management policy. This metric is applied the congestion metric. A second method for congestion detection is to use the wireless channel utilization ratio by monitoring the channel status. 11.2 Best-effort rate control An originator node can block or reduce (regulate) the transmitting process when too much traffic is sent, while an intermediate node has no other choice than to drop excess traffic when its buffers are full. So, a rate control can be done only in originator nodes. When the originator node computes an optimal path for one best-effort flow, the paths’s available bandwidth is used to limit its best-effort rate. The maximum available bandwidth on this path is not the minimum available bandwidth value on individual links. We MUST take into account the contention between packets belonging to a single flow that are forwarded at different hops along this path (intra-flow contention). Here a pretty straightforward simplification can take place, as we can consider that a link of the path cannot interfere with another link of the same path that is enough hops away. The way to go is the following: if the path has a length of one hop, then that path's bandwidth is the bandwidth of its only link. If a path has a length of two hops, then that path's bandwidth is the minimum bandwidth of its two links divided by 2: only one link can be used at a time. If path has a length of three hops or more, the path's bandwidth is the minimum bandwidth of its links divided by 3. The originator node regulates its best-effort traffic rate according to the number of hops and bandwidth on links of the found path. 11.3 Dealing with congestion CEQMM tries to avoid network congestion by repelling implicitly best-effort traffic from possible congestion zones using the QOLSR protocol. Each originator node regulates its best-effort traffic rate according to the available bandwidth of the selected path revised by the amount of intra-flow contention. Incoming QoS and best-effort packets can be dropped before queues overflow using the active queue management. When congestion occurs, the node before the congested link reacts quickly by computing a new path (next-hop) for Badis Expires October 2006 [Page 30] INTERNET-DRAFT CEQMM April 2006 its current best-effort traffic (to send or to forward) and by dropping some best-effort flows in the queue to relieve congestion. It also sends an early TC message with the new congestion metric value to inform all the nodes in the network about the congested link. Each node receiving this TC message MUST recalculate in its turn a new path for its best-effort traffic (to send or to forward). Only originator nodes limit their best-effort rates to the new path’s available bandwidth. An originator node detecting a congested link (via the received TC messages) in its reserved path SHOULD initialize a random backoff timer and maintain the current path as long as the timer has not expired. At timer expiration, if the congested link still exists, the originator node releases the bandwidth reservation on that path and proceeds to reserve a new one. Because the long process of reserving a path for QOS flows, the backoff timer allows to reduce the overhead in the network and to avoid the oscillation problem of QoS traffic. Three cases of traffic congestion can appear: - Between best-effort flows: in this case, the congestion is resolved only by the QOLSR protocol without changing the reserved paths of the QoS flows. - Between best-effort and QoS flows: in this case, the congestion is resolved by the QOLSR protocol to change the route of the best-effort flow and the backoff timer to maintain the same reserved path of the QoS flow. - Between tow QoS flows: in this case, the backoff can alone resolve the congestion problem. The originator node with the bigger backoff time maintains its reserved path and the other node releases its QoS flow and reserves a new path. 12. IPv6 Considerations All the operations and parameters described in this document used by CEQMM for IP version 4 are the same as those used by CEQMM for IP version 6. To operate with IP version 6, the only required change is to replace the IPv4 addresses with IPv6 address. The minimum packet and message sizes (under which there is rejection) should be adjusted accordingly, considering the greater size of IPv6 addresses. Badis Expires October 2006 [Page 31] INTERNET-DRAFT CEQMM April 2006 13. TLV encoding for QoS metrics The following table specifies the proposed TLV encoding for some useful QoS metrics. QoS metric | Type | Length ---------------------+--------+-------------- Loss probability | 0 | 8 bits Delay jitter | 1 | 8 bits Power consumption | 2 | 8 bits Cost | 3 | 8 bits Buffer space | 4 | 8 bits Network stability | 5 | 8 bits Security | 7 | 8 bits . | . | . . | . | . 14. Security Considerations This draft specifies mechanisms for handling quality of service. It does not introduce any special security vulnerabilities which were not already present in the CEQMM architecture. However, security can be one metric for QoS requirements. 15. References [1] H. Badis. " CEQMM: A Complete and Efficient Quality of service Model for MANETs", PhD thesis, Chapter no. 6, pp. 103-153, University of Paris-Sud XI, Dec. 2005. [2] H. Badis and K. Al Agha. "Quality of Service for Ad hoc Optimized Link State Routing Protocol (QOLSR)", draft-badis-manet-qolsr-03.txt, Mar. 2006. [3] H. Badis and K. Al Agha. "QOLSR, QoS routing for Ad Hoc Wireless Networks Using OLSR". European Transactions on Telecommunications, Vol. 15, No. 4, pp. 427-442, 2005. [4] S. Bradner. "Key words for use in RFCs to Indicate Requirement Levels". IETF RFC 2119, Mar. 1997. Badis Expires October 2006 [Page 32] INTERNET-DRAFT CEQMM April 2006 [5] R. Braden, D. Clark and S. Shenker. "Integrated services in the internet architecture", RFC 1633, 1994. [6] R. Braden, L. Zhang, S. Berson, S. Herzog and S. Jamin. "Resource reservation protocol (RSVP) – version 1 functional specification", IETF RFC 2205, Sept. 1997. [7] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang and W. Weiss. "An architecture for differentiated services", IETF RFC 2475, 1998. [8] T. Clausen and P. Jacquet. "Optimized Link State Routing Protocol". IETF RFC 3626, Oct. 2003. [9] H. Badis, A. Munaretto, K. Al Agha, and G. Pujolle. "Optimal Path Selection in a Link State QoS Routing Protocol". IEEE VTC2004- spring, May 2004. [10] H. Badis and K. Al Agha. "Distributed Algorithm for Multiple- metric Link State QoS Routing Problem". IEEE MWCN2003, Oct. 2003. [11] S. Lee and A. Campbell. "INSIGNIA: In-band signaling support for QoS in mobile ad hoc networks", MoMuC'98, Berlin, Germany, Oct. 1998. [12] H. Xiao, W. K. G. Seah, A. Lo and K. C. Chua. "On service prioritization in mobile ad-hoc networks", In Proc. IEEE International Conference on Communications 2001 (ICC’01), pp. 1900–1904, June 2001. [13] H. Xiao, W. K. G. Seah, A. Lo, and K. C. Chua. "A flexible quality of service model for mobile ad-hoc networks", In Proc. IEEE VTC Fall, pp. 445–449, May 2000. [14] G.-S. Ahn, A. T. Campbell, A. Veras and L.-H. Sun. "Supporting service differentiation for real-time and best-effort traffic in stateless wireless ad hoc networks (SWAN)", IEEE Transactions on Mobile Computing, 1(3): 192–207, 2002. [15] S. Floyd and V. Jacobson. "Random Early Detection Gateways for Congestion Avoidance", IEEE/ACM Transactions on Networking, Aug. 1993. Badis Expires October 2006 [Page 33] INTERNET-DRAFT CEQMM April 2006 [16] S. Floyd. "RED: Discussions of Byte and Packet Modes", Mar. 1997, http://www-nrg.ee.lbl.gov/floyd/REDaveraging.txt 16. Authors' Addresses Hakim Badis LIX, Ecole Polytechnique, France 91128 Palaiseau Cedex, France Phone: +33 1 69 33 28 63 EMail: Hakim.Badis@lix.polytechnique.fr Project HIPERCOM INRIA Rocquencourt, BP 105 78153 Le Chesnay Cedex, France Phone: +33 1 3963 5133 EMail: Hakim.Badis@inria.fr 17. Full Copyright Statement Copyright (C) The Internet Society (2006). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. "This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 18. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Badis Expires October 2006 [Page 34]