IETF MANET Working Group Hakim Badis INTERNET-DRAFT Institut Gaspard-Monge, Marne-la-Vallee, France Expires: March 6, 2007 Khaldoun A. Agha LRI Laboratory, Orsay, France Project Hipercom, INRIA, France October 2006 CEQMM: A Complete and Efficient Quality of service Model for MANETs draft-badis-manet-ceqmm-01.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 March 6, 2007. 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 March 2007 [Page 1] INTERNET-DRAFT CEQMM October 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, (ii) path selection for best-effort traffic, (iii) next hop maintaining for each QoS class (except the high-priority class), (iv) active queue management and (v) backoff timer method. Badis Expires March 2007 [Page 2] INTERNET-DRAFT CEQMM October 2006 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3. Useful Definitions . . . . . . . . . . . . . . . . . . . . . . 5 4. CEQMM Characteristics . . . . . . . . . . . . . . . . . . . . . 8 5. Overview of the Architecture . . . . . . . . . . . . . . . . . 9 6. The QOLSR Protocol . . . . . . . . . . . . . . . . . . . . . . 11 6.1 Neighbor Sensing . . . . . . . . . . . . . . . . . . . . . 11 6.2 QoS Measurement on Links . . . . . . . . . . . . . . . . . 11 6.3 Multipoint Relay Selection . . . . . . . . . . . . . . . . 12 6.4 Quality of Service Multipoint Relay Selection . . . . . . 12 6.5 QMPR and QOS Conditions Information Declaration . . . . . 12 6.6 Routing Table Calculation . . . . . . . . . . . . . . . . 12 7. Call Admission Control . . . . . . . . . . . . . . . . . . . . 13 7.1 CREQ Message Format. . . . . . . . . . . . . . . . . . . . 14 7.2 CREQ Message Generation . . . . . . . . . . . . . . . . . 16 7.3 CREQ Message Processing . . . . . . . . . . . . . . . . . 17 7.4 CREP Message Format . . . . . . . . . . . . . . . . . . . 18 7.5 CREP Message Generation . . . . . . . . . . . . . . . . . 19 7.6 CREP Message Processing . . . . . . . . . . . . . . . . . 20 8. Bandwidth Reservation . . . . . . . . . . . . . . . . . . . . 20 8.1 Reservation Maintenance . . . . . . . . . . . . . . . . . 21 8.2 Rebuilding Broken Routes . . . . . . . . . . . . . . . . . 21 9. Priority classifier . . . . . . . . . . . . . . . . . . . . . . 21 10. Active Queue Management . . . . . . . . . . . . . . . . . . . 22 10.1 The Need for Active Queue Management . . . . . . . . . . 23 10.2 The Queue Management Algorithm "CEQMM-RED". . . . . . . . 24 10.2.1 Estimation of Average Queue Size . . . . . . . . . 25 10.2.2 Packet Drop Decision . . . . . . . . . . . . . . . 25 11. Packet Scheduling . . . . . . . . . . . . . . . . . . . . . . 27 12. Congestion Avoidance and Control . . . . . . . . . . . . . . . 28 12.1 Network Congestion Detection. . . . . . . . . . . . . . . 28 12.2 Best-effort Rate Control. . . . . . . . . . . . . . . . . 29 12.3 Dealing with Congestion . . . . . . . . . . . . . . . . . 30 12.3.1 The case of best-effort traffic. . . . . . . . . . 30 12.3.2 The case of low-priority QoS traffic . . . . . . . 30 12.3.3 The case of highest-priority QoS traffic . . . . . 33 12.3.4 The size of the backoff window . . . . . . . . . . 33 13. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . . 34 14. TLV Encoding for QoS Metrics . . . . . . . . . . . . . . . . . 34 15. Security Considerations . . . . . . . . . . . . . . . . . . . 34 16. References . . . . . . . . . . . . . . . . . . . . . . . . . . 34 17. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 36 18. Full Copyright Statement . . . . . . . . . . . . . . . . . . . 37 19. Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . 37 Badis Expires March 2007 [Page 3] INTERNET-DRAFT CEQMM October 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. CEQMM defines one class for best-effort traffic and one or more classes for QoS traffic. Each QoS class is assigned a priority level. The best-effort class has the lowest priority. 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 QoS 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 selection reduces the overhead in the network by maintaining the stability of the QoS paths as long as possible. The path's available bandwidth Badis Expires March 2007 [Page 4] INTERNET-DRAFT CEQMM October 2006 revised by the amount of intra-flow contention is used as the rate limit of the best-effort traffic at the originator node. For each QoS class, QOLSR computes optimal or quasi-optimal paths according to multiple constraints. The originator node maintains the complete path for each QoS flow of highest priority and only the next hop node for the other QoS classes. Once a path is chosen for one QoS flow of highest priority (or a next hop node for the other QoS classes), 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 or next hop selection, (ii) the congestion and (iii) the mobility. The validity of the route 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 route 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 next hop selection for best-effort traffic, (iii) QOLSR next hop maintaining for for each QoS class (except the high-priority class), (iv) active queue management, and (v) 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 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 next hop for its best-effort traffic. Only originator nodes limit their best-effort rates to the new available bandwidth. For flows of QoS classes (except the high-priority class), the first node in the flow's current path that precedes an overflowed arc and that has an alternate route satisfying the flow's QoS requirement should be considered for route switching. If the Badis Expires March 2007 [Page 5] INTERNET-DRAFT CEQMM October 2006 congestion persists, originator nodes using the congested links as part of their reserved paths decide to change the route after a backoff time. Some QoS flows may also be suspended under heavy congestion. 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. Changes Major changes from version 00 to version 01 - Providing scalable support for multiple classes of QoS guarantees. - Enhancement of congestion Avoidance and Control mechanisms. 3. 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). Badis Expires March 2007 [Page 6] INTERNET-DRAFT CEQMM October 2006 * 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 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 Badis Expires March 2007 [Page 7] INTERNET-DRAFT CEQMM October 2006 representation is to use the wireless channel utilization ratio. This value can be obtained by monitoring the channel status. 4. CEQMM Characteristics * Does the CEQMM define a set of service classes? Yes. * Does the CEQMM support both per-flow state property of IntServ and the service differentiation of DiffServ? Yes. * 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 March 2007 [Page 8] INTERNET-DRAFT CEQMM October 2006 5. 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 March 2007 [Page 9] INTERNET-DRAFT CEQMM October 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 (see section 5.6). 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 first regulates its best-effort traffic rate using a control rate to reduce congestion with QoS flows. CEQMM performs 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 (see section 11.2). Upon receiving a TC message indicating congested links, each node sending or forwarding a best-effort flow computes a new route for this flow. The node that precedes an overflowed arc and that has an alternate route satisfying the QoS requirement of the QoS classes (except the high-priority class) calculates a new next hop. The originator nodes of QoS traffic of highest priority waits a backoff time which enables to avoid the long process of recalculating and maintaining a new path. 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 March 2007 [Page 10] INTERNET-DRAFT CEQMM October 2006 6. 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. 6.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. 6.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 March 2007 [Page 11] INTERNET-DRAFT CEQMM October 2006 6.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. 6.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 the best QoS metrics 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. 6.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. 6.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 March 2007 [Page 12] INTERNET-DRAFT CEQMM October 2006 traffic and to allocate the remaining bandwidth to the best-effort traffic. Each entry in the routing table of the best-effort class or of any QoS class (except the QoS class of the highest priority) consists of R_dest, R_next, R_dist, R_cong, R_bw, R_del, etc., 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, available bandwidth R_bw, end-to-end delay R_del, etc. 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 flow. QOLSR uses an algorithm based on Lagrangian relaxation [10] to find shortest paths having the congestion metric value under a fixed threshold and optimal paths satisfying multiple constraints for best-effort and QoS flows respectively. Flows are rejected if no path that can meet the congestion metric or multiple constraints requirements cannot be found. Each entry in the routing table of the highest priority class 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 paths. 7. Call Admission Control Once a path is chosen for one QoS flow of highest priority (or a next hop node for the other QoS classes), the originator node cannot guarantee the end-to-end QoS requirements. Because routes are calculated using partial topology, and because of congestion and mobility, the validity of the route 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 only 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 only 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. Badis Expires March 2007 [Page 13] INTERNET-DRAFT CEQMM October 2006 The originator node sends out a Check REQuest (CREQ) message containing the entire path if the flow has the highest priority and only the next hop otherwise. A CREQ message includes also the QoS requirements: the minimum bandwidth, the maximum delay, etc. The format of this message is in the next section. 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. It also adds its next hop to the list of intermediate nodes of the forwarded CREQ message if the CAC process concerns a QoS flow of less priority. 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. The format of this message is shown in section 8.4. 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. 7.1 CREQ Message 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 13. 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: Badis Expires March 2007 [Page 14] INTERNET-DRAFT CEQMM October 2006 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 |P|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. P 0 : QoS flow (except that of highest priority). 1 : QoS flow of highest priority. RM This field indicates the reservation maintenance type: 00 : First CREQ message for this QoS flow. 01 : Refresh message. 10 : Flow releasing. Badis Expires March 2007 [Page 15] INTERNET-DRAFT CEQMM October 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. 7.2 CREQ Message Generation In order to check the validity of the selected route, the originator node MUST generate and send a CREQ message with RM = 00 (first CREQ message) containing the QoS requirements to the destination. The option "P" (flow priority) of this message is assigned the value 1, if the CAC process concerns a flow with the highest priority. If P = 1, the CREQ message includes all the hops of the selected path. Otherwise, it includes only the next hop. CREQ is forwarded only by intermediate nodes specified in this message. Badis Expires March 2007 [Page 16] INTERNET-DRAFT CEQMM October 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. 7.3 CREQ Message Processing Upon receiving a CREQ message with RM = 00 and P = 1, a node MUST evaluate its QoS conditions including the QoS requirements values of this message on the link to its next hop in the path. If the receiver cannot satisfy one of the QoS requirements, this message must be discarded. Otherwise, it 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. Considering the link from the receiver node to its next hop in the path, let (Bw_CREQ, Bw_link), (Del_CREQ, Del_link), (jitter_CREQ, jitter_link), etc., be respectively (available bandwidth indicated in the CREQ message, available bandwidth on that link), (delay indicated in the CREQ message, delay on that link), (jitter indicated in the CREQ message, jitter on that 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. When an intermediate node receives a CREQ message with RM = 00 and P = 0, it proceeds in the same manner as above (P = 1) except for bandwidth evaluation case. Indeed, the node cannot evaluate the bandwidth because it has no information about the path to the Badis Expires March 2007 [Page 17] INTERNET-DRAFT CEQMM October 2006 destination. So, it cannot detect the links in the path within the intra-flow contention. However, it can evaluate the other metrics. If this node satisfies all the QoS requirements of the corresponding QoS class (except bandwidth), it adds its next hop to the list of intermediate nodes of the received CREQ message. The received CREQ message is forwarded after modifying its QoS additive and multiplicative metrics requirements field's values according to the CAC process. 7.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 |P|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. Badis Expires March 2007 [Page 18] INTERNET-DRAFT CEQMM October 2006 P 0 : QoS flow (except that of highest priority). 1 : QoS flow of highest priority. RT This field indicates the bandwidth reservation type: 00 : Without reservation. 01 : Soft reservation. 10 : Hard reservation. 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 +-----------------+ +-------+ : +-------+ | |||| 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 March 2007 [Page 22] INTERNET-DRAFT CEQMM October 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. 10.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 March 2007 [Page 23] INTERNET-DRAFT CEQMM October 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. 10.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 March 2007 [Page 24] INTERNET-DRAFT CEQMM October 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. 10.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. 10.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 queue size *above which* all packets for Q_i will be dropped. When Badis Expires March 2007 [Page 25] INTERNET-DRAFT CEQMM October 2006 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 avgQi = (1 - Wq) x avgQi + Wq x Q, Else m = f(idle time, S), avgQi = (1 – Wq)^m x avgQi, 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, Badis Expires March 2007 [Page 26] INTERNET-DRAFT CEQMM October 2006 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]. 11. 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 | +----------+ +-------------+ : +----------+ QoS traffic | |||| +----------+ +----------+ 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 Badis Expires March 2007 [Page 27] INTERNET-DRAFT CEQMM October 2006 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. 12. 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 of highest priority, the originator node of this QoS flow decides to change the route after a backoff time. 12.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 Badis Expires March 2007 [Page 28] INTERNET-DRAFT CEQMM October 2006 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 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. 12.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. Badis Expires March 2007 [Page 29] INTERNET-DRAFT CEQMM October 2006 12.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. 12.3.1 The case of best-effort traffic When congestion occurs, the node before the congested link reacts quickly by computing a new path for its current best-effort traffic, either generated locally or forwarded from another node, 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, either generated locally or forwarded from another node. Only originator nodes limit their best-effort rates to the new path's available bandwidth. 12.3.2 The case of low-priority QoS traffic When a node detects a change in network conditions via HELLO and TC messages (including congestion), it checks for each QoS class (except the class of the highest priority), if the respective next hops can be kept without breaking the class' QoS requirements. This is achieved by applying the following distributed rule (Oscillation-Avoidance 2: OA2): each node checks if at least one of the non-congested paths starting from the current next hop towards the destination is satisfying the QoS requirements; if such a path does not exist, a new one is calculated starting from the current node and the next hop is changed, otherwise the next hop is kept the same. This rule allows avoiding the well known oscillation problem in the QOLSR protocol (For more details see [17]). Nevertheless, this rule alone is not enough to prevent low-priority QoS flows from colliding: there is no way that nodes of two colliding low-priority QoS flows behave differently in response to arc overflow. In the case of the next figure, both flows (Source1-Destination1, Source2-Destination2) will block, although at least one of them could use the path. Badis Expires March 2007 [Page 30] INTERNET-DRAFT CEQMM October 2006 Source1 Destination1 X X | | | | | | a X---------------X b | | | | | | X X Source2 Destination2 If initially low-priority QoS flows share an arc, they would both choose another path, and may choose paths with yet another shared arc, and fall into a completely equivalent situation. This shows how the collision-avoidance rule may introduce, quite paradoxically, another form of oscillation. Therefore, some asymmetry has to be introduced to enable nodes of colliding low-priority QoS flows to take different decisions regarding route change. This asymmetry can be achieved with the use of our proposed backoff-based solution. The idea is that the first node in the low-priority QoS flow's current path that precedes an overflowed arc and that has an alternate route satisfying the flow's QoS requirement should be considered for route switching. This node should initialize a random backoff timer and maintain the current next hop as long as the timer has not expired. At timer expiration, the node applies OA2 again and if the flow keeps colliding, then the node calculates a new path using QOLSR, instead of keeping the next hop. The node responsible for the switch is chosen using the following method: each node applies the OA2 rule and notifies the next hop if it is determined to have an alternate route; otherwise it waits for a notification from its preceding node. On reception of a notification, a node applies the OA2 rule if it has not done so already and notifies its next hop if it is determined to have an alternate route and so on. If the application of OA2 gives a negative answer regarding alternate routes from the next hop, the current node is the one that should switch the low-priority QoS flow. It then extracts the source address of the notification message which is the address of the preceding node on the current path and removes this node from the topology for alternate path calculation. Removal of the preceding node from the topology avoids finding paths that would route the flow back to it. Badis Expires March 2007 [Page 31] INTERNET-DRAFT CEQMM October 2006 The next hop calculation scheme for QoS classes (except the class of the highest priority) is as follows: +----------+ +---------->| NEW ANSN |<-----------------+----------------+------+ | +----------+ | | | | | | | | | | |No | | | V | | | | +-------------------+ NO +--------------+ | | | |Change of topology?|----->|Change of QoS?| | | | +-------------------+ +--------------+ | | | | | | | | |YES |YES | | | V V | | | +--------------------------+ +---------+ YES +----------+ | +-->|Routing table calculation?| |OA2 rule?|---->|Send Notif| | +--------------------------+ +---------+ +----------+ | | | |No | V | +------------------+ | |Backoff when Notif| | +------------------+ | | | | | V | +---------+ YES | |OA2 rule?|------------------+ +---------+ | | | |No | V | +--------------------------+ | |Routing table calculation?|----------+ +--------------------------+ Each TC message contains a Advertised Neighborhood Sequence Number (ANSN) which helps keeping track of topology and QoS changes. Upon reception of a TC message with a new ANSN, if the topology has changed, then the routing tables have to be recalculated using plain QOLSR methods. Otherwise, if the state of QoS of the network has changed for a given low-priority QoS class, then the OA2 rule MUST be applied to decide whether the path MUST be changed. If there exists at least one feasible path from the next node on the current path to the flow's destination, then a change of path must be performed by Badis Expires March 2007 [Page 32] INTERNET-DRAFT CEQMM October 2006 some node downstream. To inform these that the current node maintains its next hop for the current low-priority QoS class, a notification message is sent to the next node. When a node receives the notification, it applies the OA2 rule if not done previously and behaves exactly as the sender of the notification if a feasible path exists from the next node. Otherwise, it means that this node has to resolve the congestion itself. When a node is in charge of resolving congestion, it selects a random backoff timer value and delays further actions. Upon timer expiration, the OA2 rule is applied again to decide whether the current path has been freed by the congestion flow, in which case the congestion is resolved. If the congestion is still occurs, then the node calculates the alternate path, not using the current next hop. To avoid sending the flow back through the previous node, the source address of the notification message is extracted and the link to the previous node is removed during path calculation. Analysis and simulation results can be found in [17]. 12.3.3 The case of highest-priority QoS traffic 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. 12.3.4 The size of the backoff window The size of the backoff window must be set to reflect the priorities of flows, since a larger window increases the probability of selecting a timer value larger than that of colliding flows and consequently decreases the probability that the flow will have to switch routes. The highest-priority QoS traffic has the largest backoff window size. When the QoS traffic priority decreases, the backoff window size decreases. The "older" flow should obviously be prioritized over the more recent one. Therefore, each time congestion occurs after route switching, the size of the backoff window has to be doubled. Badis Expires March 2007 [Page 33] INTERNET-DRAFT CEQMM October 2006 13. 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. 14. 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 . | . | . . | . | . 15. 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. 16. References [1] H. Badis. " CEQMM: A Complete and Efficient Quality of service Model for MANETs". The Third ACM International Workshop on Performance Evaluation of Wireless Ad Hoc PE-WASUN, Spain, Oct. 2006 Badis Expires March 2007 [Page 34] INTERNET-DRAFT CEQMM October 2006 [2] H. Badis and K. Al Agha. "Quality of Service for Ad hoc Optimized Link State Routing Protocol (QOLSR)", draft-badis-manet-qolsr-04.txt, Oct. 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. [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. Badis Expires March 2007 [Page 35] INTERNET-DRAFT CEQMM October 2006 [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. [16] S. Floyd. "RED: Discussions of Byte and Packet Modes", Mar. 1997, http://www-nrg.ee.lbl.gov/floyd/REDaveraging.txt [17] H. Badis, I. Gawedzki and K. Al Agha. "QoS Routing in Ad hoc Networks Using QOLSR with no Need of Explicit Reservation". IEEE VTC'04-Fall: Vehicular Technology Conference, Los Angeles, USA, Sep. 2004. 17. Authors' Addresses Hakim Badis Institut Gaspard-Monge Computer science research laboratory University of Marne-la-Vallee Citι Descartes, 5 Bd Descartes, Champs-sur-Marne F-77454 Marne-la-Vallιe cedex 2. France Phone: +33 1 60 95 77 49 FAX: +33 1 60 95 75 57 EMail: badis@univ-mlv.fr Khaldoun Al Agha LRI Laboratory Paris-sud University, 91405 Orsay, France Phone: +33 1 6915 6617 EMail: Alagha@lri.fr Project HIPERCOM, INRIA Rocquencourt, BP 105 78153 Le Chesnay Cedex, France Phone: +33 1 3963 5908, EMail: Alagha.Khaldoun@inria.fr Badis Expires March 2007 [Page 36] INTERNET-DRAFT CEQMM October 2006 18. 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. 19. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Badis Expires March 2007 [Page 37]