Internet Engineering Task Force A. Szwabe Internet-Draft P. Misiorek Intended status: Experimental M. Urbanski, Ed. Expires: November 3, 2011 Poznan University of Technology E. Baccelli INRIA May 2, 2011 OLSRv2 Backpressure Traffic Engineering Extension draft-szwabe-manet-backpressure-olsrv2-02 Abstract This document specifies a traffic engineering extension for OLSRv2 based on backpressure, which allows advanced traffic shaping by providing each MANET router with information about packet queue levels of its neighbors. Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. This document may not be modified, and derivative works of it may not be created, and it may not be published except as an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. 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." This Internet-Draft will expire on November 3, 2011. Copyright Notice Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect Szwabe, et al. Expires November 3, 2011 [Page 1] Internet-Draft Backpressure extension of OLSRv2 May 2011 to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 6 4. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 6 5. Parameters and Constants . . . . . . . . . . . . . . . . . . . 6 5.1. Protocol and Port Numbers . . . . . . . . . . . . . . . . 6 5.2. Multicast Address . . . . . . . . . . . . . . . . . . . . 7 5.3. Message Intervals . . . . . . . . . . . . . . . . . . . . 7 5.4. Message Validity Times . . . . . . . . . . . . . . . . . . 7 5.5. Jitter . . . . . . . . . . . . . . . . . . . . . . . . . . 8 6. Information Bases . . . . . . . . . . . . . . . . . . . . . . 8 6.1. Local Information Base . . . . . . . . . . . . . . . . . . 8 6.2. Interface Information Base . . . . . . . . . . . . . . . . 8 6.3. Topology Information Base . . . . . . . . . . . . . . . . 8 6.4. Received Message Information Base . . . . . . . . . . . . 9 6.5. Flow Identification . . . . . . . . . . . . . . . . . . . 9 6.6. Queue Information Base . . . . . . . . . . . . . . . . . . 10 6.6.1. Queue Levels Set . . . . . . . . . . . . . . . . . . . 10 6.6.2. Urgency Set . . . . . . . . . . . . . . . . . . . . . 10 6.6.3. Updating the Data . . . . . . . . . . . . . . . . . . 11 7. Signaling . . . . . . . . . . . . . . . . . . . . . . . . . . 11 7.1. QR Message . . . . . . . . . . . . . . . . . . . . . . . . 11 7.1.1. QR Message Generation . . . . . . . . . . . . . . . . 11 7.1.2. QR Message TLVs . . . . . . . . . . . . . . . . . . . 12 7.1.3. QR Message Transmission . . . . . . . . . . . . . . . 13 7.1.4. QR Message Processing . . . . . . . . . . . . . . . . 13 7.2. UR Message . . . . . . . . . . . . . . . . . . . . . . . . 14 7.2.1. UR Message Generation . . . . . . . . . . . . . . . . 14 7.2.2. UR Message TLVs . . . . . . . . . . . . . . . . . . . 16 7.2.3. UR Message Transmission . . . . . . . . . . . . . . . 16 7.2.4. UR Message Processing . . . . . . . . . . . . . . . . 17 8. Data Available for Schedulers . . . . . . . . . . . . . . . . 17 9. Interoperability with other OLSRv2 Routers . . . . . . . . . . 19 10. Values for Parameters and Constants . . . . . . . . . . . . . 19 10.1. Message Interval Parameters . . . . . . . . . . . . . . . 19 10.2. Message Validity Times Parameters . . . . . . . . . . . . 19 10.3. Hop Limit Parameter . . . . . . . . . . . . . . . . . . . 20 10.4. Jitter Time Parameters . . . . . . . . . . . . . . . . . . 20 11. Security Considerations . . . . . . . . . . . . . . . . . . . 20 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 Szwabe, et al. Expires November 3, 2011 [Page 2] Internet-Draft Backpressure extension of OLSRv2 May 2011 12.1. Expert Review: Evaluation Guidelines . . . . . . . . . . . 20 12.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 20 12.3. Message-Type-specific TLV Type Registries . . . . . . . . 21 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 22 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22 14.1. Normative References . . . . . . . . . . . . . . . . . . . 22 14.2. Informative References . . . . . . . . . . . . . . . . . . 23 Appendix A. Illustrations . . . . . . . . . . . . . . . . . . . . 23 A.1. QR Message Examples . . . . . . . . . . . . . . . . . . . 23 A.2. UR Message Example . . . . . . . . . . . . . . . . . . . . 27 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 27 Szwabe, et al. Expires November 3, 2011 [Page 3] Internet-Draft Backpressure extension of OLSRv2 May 2011 1. Introduction This document specifies a traffic engineering extension for OLSRv2 [I-D.ietf-manet-olsrv2] based on backpressure, which can increase and balance end-to-end throughput by providing each MANET router with information about packet queue levels of its neighbors. This document defines signaling and processing that is necessary, in addition to the signaling and processing defined in [I-D.ietf-manet-olsrv2], [RFC6130] and [RFC5444], to provide efficient traffic engineering in OLSRv2 with a backpressure-based scheme [SMN+10]. 2. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. All terms introduced in [RFC5444], including "packet", "Packet Header", "message", "Message Header", "Message Body", "Message Type", "message sequence number", "hop limit", "hop count", "Address Block", "TLV Block", "TLV", "Message TLV", "Address Block TLV", "type" (of TLV), "type extension" (of TLV), "value" (of TLV), "address" and "address object" are to be interpreted as described there. All terms introduced in [RFC6130], including "interface", "MANET interface", "network address", "link", "symmetric link", "1-hop neighbor", "symmetric 1-hop neighbor", "symmetric 2-hop neighbor", "constant", "interface parameter", "router parameter", "Information Base", and "HELLO message" are to be interpreted as described there. All terms introduced in [I-D.ietf-manet-olsrv2] and [I-D.dearlove-olsrv2-metrics], including the terms "Router", "OLSRv2 interface", "Originator address", "Message originator address", "Routing Set", "Routing Tuple" are to be interpreted as described therein. Additionally, this document uses the following terminology: Flow A particular packet sequence transmitted through the network. Flow Identifier A set of values which enable unambiguous identification of the Flow. Szwabe, et al. Expires November 3, 2011 [Page 4] Internet-Draft Backpressure extension of OLSRv2 May 2011 Timeslot A definite continuously repeating time period when events may occur. For example: "In a given Timeslot, 15 packets have been processed." Scheduler In this document, a scheduler is considered as a part of the system maintaining the traffic on the router. A scheduler decides which Flow should be forwarded at a given time. Queue Level The number of units (e.g., packets or bytes) in a Flow Queue on a router. Backpressure The backpressure routing/scheduling policy is based on giving priority in forwarding to links and Flows that have higher backpressure, defined as the backlog differential (i.e., the difference between Queue Levels) at consecutive Routers. Basic OLSRv2 Router A OLSRv2 Router without Backpressure Extension. Backpressure Router A OLSRv2 Router featuring the Backpressure Extension. Backpressure Interface A OLSRv2 interface running the Backpressure Extension. Urgency Urgency is a queue-level-based scheduling weight used by a Backpressure Scheduler. Unless otherwise specified, urgency is defined as a backlog differential (i.e., the difference between Queue Levels) at consecutive Routers. Router Urgency The maximum Urgency over all active Flows and all active connections on the router. Backpressure Scheduler Specific type of scheduler which provides integrated packet scheduling and forwarding according to the backpressure policy based on the information on scheduling weights (Urgencies). Szwabe, et al. Expires November 3, 2011 [Page 5] Internet-Draft Backpressure extension of OLSRv2 May 2011 per-flow This term refers to resources which may be regarded as allocated to a Flow. 3. Applicability The OLSRv2 extension specified in this document should be used together with an OLSRv2 multipath extension such as [I-D.multipath-olsrv2], in order to fully benefit from potential load balancing and throughput optimization. However, the extension specified in this document can be used without any other OLSRv2 extension, to increase end-to-end throughput. Routers which do not support the OLSRv2 extension specified in this document are interoperable with routers that do support the extension according to the present specification. 4. Protocol Overview The OLSRv2 extension defined in the following sections provides traffic engineering capabilities to MANET routers, based on a backpressure scheme which can increase end-to-end throughput. This document specifies data flow identification, as well as periodical signaling of Queue Report (QR) and Urgency Report (UR) messages using the format specified in [RFC5444], which enables a router to monitor the queue levels of its neighbors. QR and UR messages provide each node with the information enabling the backpressure max-weight scheduling. Information carried by QR messages is necessary for each router to calculate its backpressure- based scheduling weights (i.e., its urgencies), whereas UR messages are used to inform each router on urgencies within its neighborhood. By using QR and UR messages routers may perform backpressure max- weight scheduling, which is theoretically proven as a distributed load-balancing solution maximizing overall network throughput, e.g., enabling to avoid forwarding packets through a network bottleneck [SMN+10]. 5. Parameters and Constants 5.1. Protocol and Port Numbers The backpressure extension of OLSRv2 specifies QR and UR messages, which are included in packets as defined in [RFC5444]. These packets may be sent either by using the "manet" protocol number or the Szwabe, et al. Expires November 3, 2011 [Page 6] Internet-Draft Backpressure extension of OLSRv2 May 2011 "manet" UDP well-known port number, as specified in [RFC5498]. QR, UR and TC [I-D.ietf-manet-olsrv2], HELLO [RFC6130] messages SHOULD be using the same transport protocol (either of IP or UDP) in order to make it possible to combine messages of all these protocols into a single [RFC5444] packet. 5.2. Multicast Address The Backpressure Extension of OLSRv2 specifies QR and UR messages, which are included in packets as defined by [RFC5444]. These packets MAY be transmitted using the link local multicast address "LL-MANET- Routers", as specified in [RFC5498]. 5.3. Message Intervals This specification defines the following message intervals: QR_INTERVAL - the maximum time between transmission of two consecutive QR messages UR_INTERVAL - the maximum time between transmission of two consecutive UR messages Intervals defined in this document MUST comply to the following constraints: o UR_INTERVAL > 0 o UR_INTERVAL < QR_INTERVAL 5.4. Message Validity Times This specification defines the following Advertised Information Validity Times: UR_HOLD_TIME - a validity time of UR message and a validity time of information carried by this message. QR_HOLD_TIME - a validity time of QR message and a validity time of information carried by this message. BP_HOLD_TIME - the maximum time without receiving a QR message or a UR message from a neighbor Router. Validity times defined in this document MUST apply to the following constrains: Szwabe, et al. Expires November 3, 2011 [Page 7] Internet-Draft Backpressure extension of OLSRv2 May 2011 o UR_HOLD_TIME > UR_INTERVAL o QR_HOLD_TIME > QR_INTERVAL o BP_HOLD_TIME > UR_INTERVAL or BP_HOLD_TIME > QR_INTERVAL o In the case of high loss ratio of QR and UR messages, BP_HOLD_TIME should be made significantly greater than UR_INTERVAL or QR_INTERVAL interval. 5.5. Jitter If jitter, as defined in [RFC5148], is used, the following jitter parameters are required to be defined: QR_MAXJITTER - value of MAXJITTER used in [RFC5148] for periodically generated QR messages sent by this Router. UR_MAXJITTER - value of MAXJITTER used in [RFC5148] for periodically generated UR messages sent by this Router. 6. Information Bases The Information Bases defined here extend these specified in [RFC6130] and [I-D.ietf-manet-olsrv2] with both: information and its uses. This organization of information serve purpose of describing the Backpressure Extension, and DOES NOT constrain in any way implementation of this extension. 6.1. Local Information Base The Local Information Base is specified in [I-D.ietf-manet-olsrv2]. Additionally information stored there is used for the Backpressure Extension signaling. 6.2. Interface Information Base The Interface Information Base is specified in [I-D.ietf-manet-olsrv2]. Additionally information stored there is used for the Backpressure Extension signaling. 6.3. Topology Information Base The Topology Information Base is specified in [I-D.ietf-manet-olsrv2]. Additionally information stored there is used for choosing on which interfaces QR and UR messages should be announced. Szwabe, et al. Expires November 3, 2011 [Page 8] Internet-Draft Backpressure extension of OLSRv2 May 2011 6.4. Received Message Information Base The Received Message Information Base defined by [I-D.ietf-manet-olsrv2] is extended by this specification by introducing also an information about QR and UR messages. The Received Message Information Base structure is not modified by the Backpressure Extension. The way the messages are processed in Information Base is defined in Section 7. 6.5. Flow Identification In order to enable backpressure-based per-flow routing, unambiguous Flow identification is specified by this document. For this purpose Flow Identifier MAY hold the following parameters set: o Destination address o Source address o Internet Protocol Number of a protocol used in the transport layer o If used, an additional transport protocol source and destination address (i.e. port addresses in TCP or UDP) This specification allows various combinations of these parameters to be used in order to identify a Flow. Flow identification parameters MUST be the same across the MANET network. Routers using different set of parameters to identify the Flow are treated as Basic OLSRv2 Routers by Backpressure Routers. One of the following parameters subsets MUST be used: o Destination address, Source address, Internet Protocol Number with source and port addresses (if used). o Destination address, Source address. o Only destination address Information about Flows is necessary from the perspective of the Scheduler which differentiate the traffic depending on its type. More detailed per-flow identification increases signaling overhead. As the countermeasure, the Urgency signaling (see Section 7.2) which significantly reduces amount of transmitted data is deployed. Overhead of Urgency signaling itself does not increase with complexity of Flow Identifier. For encoding of Flow Identifier special QR Message-specific TLVs are Szwabe, et al. Expires November 3, 2011 [Page 9] Internet-Draft Backpressure extension of OLSRv2 May 2011 defined: o PROTOCOL - Internet Protocol number used within transport layer. o PORT - address used in transport layer, associated with a single address. More detailed information about formatting of Flow Identifier in QR Messages as specified in Section 7.1.2. 6.6. Queue Information Base A Queue Information Base defined here stores information extracted from received QR and UR messages. The Queue Information Base consists of the Queue Level Set, the Urgency Set. 6.6.1. Queue Levels Set The Queue Level Set contains neighbor's Queue Levels reported by means of QR messages, as well as local Queue Levels of the Backpressure Router. This set consists of Queue Level Tuples: (Q_addr, Q_fid, Q_level, Q_time) where: o Q_addr is the originator address of the Backpressure Router sending the QR message; o Q_fid is a Flow Identifier; o Q_level is a Queue Level reported for this Flow by the Backpressure Router; o Q_time is the Tuple expiration time, after which Tuple MUST be removed. 6.6.2. Urgency Set The Urgency Set records Urgency values. Urgency values are delivered by means of UR messages (in the case of Urgencies of neighboring Routers) or calculated using values from Queue Level Set (in the case of local Urgency, i.e., the maximum Urgency of queues stored in the local Router). This set consists of Urgency Tuples: (U_addr, U_level, U_time) where: Szwabe, et al. Expires November 3, 2011 [Page 10] Internet-Draft Backpressure extension of OLSRv2 May 2011 o U_addr is the originator address of Backpressure Router associated with the Urgency value; o U_level is an Urgency; o U_time is a Tuple expiration time, after which Tuple MUST be removed. 6.6.3. Updating the Data In order to maintain the Queue Information Base properly, the following actions MUST be taken: o An entry MUST be removed after the time defined as the Tuple expiration time (Q_time or U_time respectively). o A new entry corresponding to a pair Q_addr and Q_fid in Queue Level Tuple or U_addr and U_level in Urgency Tuple, which is already present in the Queue Information Base, MUST be overwritten. 7. Signaling Messages defined by [RFC6130] and [I-D.ietf-manet-olsrv2] are used as specified there. This extension does not involve modifications to these messages. The packet and message format used by the Backpressure Extension of OLSRv2 are defined in [RFC5444]. If not noted otherwise, options defined in [RFC5444] MAY be used. The QR and UR messages MUST follow specification of Message Processing and Forwarding defined in [I-D.ietf-manet-olsrv2]. 7.1. QR Message 7.1.1. QR Message Generation QR messages are generated by a Router for each of its Backpressure interfaces, and MUST be sent proactively and MAY be sent in a combination of proactive and reactive techniques. proactive - at a regular interval, known as QR_INTERVAL, which may be fixed or dynamic, and in case of fixed interval MAY be the same across the network. Szwabe, et al. Expires November 3, 2011 [Page 11] Internet-Draft Backpressure extension of OLSRv2 May 2011 reactive - in reaction to a change of queue states, limited to queues that changed. In this case the maximum refresh time SHOULD be set, and minimal queue state change required to trigger QR message MUST be set (independently by each Router). A QR message MUST contain: o A := QR_HOPLIMIT, which limits the QR messaging network-wide overhead. o A message originator address, representing Router's originator address. A element MUST be used for this purpose. A QR message MAY contain: o Address blocks with associated PORT, PROTOCOL and QUEUE_LEVEL TLV as specified in Section 7.1.2, and as required for Flow Identification. 7.1.2. QR Message TLVs 7.1.2.1. Address Block TLVs In a QR message, a Router MAY include PROTOCOL Address Block TLV(s) as specified in Table 1. +----------+--------------+----------------------------------------+ | Type | Value Length | Value | +----------+--------------+----------------------------------------+ | PROTOCOL | 1 octet | Associated with a whole address block. | +----------+--------------+----------------------------------------+ Table 1: PROTOCOL TLV definition In a QR message, a Router MAY include PORT Address Block TLV(s) as specified in Table 2. +------+----------+-------------------------------------------------+ | Type | Value | Value | | | Length | | +------+----------+-------------------------------------------------+ | PORT | 2 octets | Indicates that source or destination uses | | | | corresponding PORT value as port number. | +------+----------+-------------------------------------------------+ Table 2: PORT TLV definition In a QR message, a Router MAY include QUEUE_LEVEL Address Block Szwabe, et al. Expires November 3, 2011 [Page 12] Internet-Draft Backpressure extension of OLSRv2 May 2011 TLV(s) as specified in Table 3. +-------------+----------+------------------------------------------+ | Type | Value | Value | | | Length | | +-------------+----------+------------------------------------------+ | QUEUE_LEVEL | up to 4 | Queue Level expressed as unsigned | | | octets | integer filed (encoded with network byte | | | | order). | +-------------+----------+------------------------------------------+ Table 3: QUEUE_LEVEL TLV definition Relationship between PROTOCOL TLV, PORT TLV, QUEUE_LEVEL is based on structure of Flow Identifier, and MUST comply with following rules: o One entity of Flow Identifier with associated QUEUE_LEVEL TLV MAY be presented as addr_block and tlv_block pair. o PORT TLV MUST not be used if there is no PROTOCOL TLV associated with these addresses. o If required by Flow Identifier, one per address PORT TLV MAY be used. o To be considered a valid Flow Identifier all used fields (PORT TLV, PROTOCOL TLV, QUEUE_LEVEL TLV) MUST be assigned to two addresses (representing source and destination address). 7.1.3. QR Message Transmission In order to exchange the Queue Level values between Routers, Router MUST generate QR Messages. The messages MUST be transmitted according to QR_INTERVAL. The scheduler assigned to the Router MUST provide sufficient information about Queue Levels of the Router. The information about Queue Level of the sending Router MUST be the most recent available. After each QR_INTERVAL, QR Message is generated and then broadcast to Router's neighbors. When a Router receives QR Message, an appropriate queue value is assigned to message originator as according to the corresponding entry in the Backpressure Information Base. 7.1.4. QR Message Processing Each received (and not discarded) QR message, after initially being processed according to [RFC5444], should be analyzed by Router and used to update the Queue Information Base, according to the following Szwabe, et al. Expires November 3, 2011 [Page 13] Internet-Draft Backpressure extension of OLSRv2 May 2011 rules: o There must be only one, the most actual, Queue Level Tuple in Queue Level Set of Queue Information Base corresponding to QR message originator address and Flow Identifier. o If there is no Queue Level Tuple in Queue Level Set corresponding to information in QR message, such Queue Level Tuple MUST be created. o If QR message contains Flow Identifier that is differently defined than the one used by this Router (see Section 6.5), the QR message MUST be discarded. 7.2. UR Message 7.2.1. UR Message Generation UR messages are generated by a Router independently for each of Routers Backpressure interfaces. UR messages SHOULD be sent proactively, at a regular interval, called UR_INTERVAL, which may be fixed or dynamic. A UR message MUST contain: o A := UR_HOP_LIMIT. o A message originator address, representing router's originator address. A element MUST be used for this purpose. o Routers Urgency value calculated from its Queue Information Base. Urgency value is calculated per interface, combining information from Routes Set from Topology Information Base and Queue Information Base. o A unique identifier of the maximum Urgency holder together with its corresponding Urgency value. The maximum Urgency holder is a Neighbor Backpressure Router with the highest Urgency value of neighboring Routers in MANET network connected to particular Backpressure Interface. This information is acquired through combining Queue Information Base and Interface Information Base (of this particular Backpressure Interface). A UR message MAY contain: o A unique identifier of the maximum Urgency holder together with its corresponding Urgency value. This information is included in UR message if maximum Urgency holder urgency is greater or equal Szwabe, et al. Expires November 3, 2011 [Page 14] Internet-Draft Backpressure extension of OLSRv2 May 2011 to Interface Urgency. The maximum Urgency holder is a Neighbor Backpressure Router with the highest Urgency value of neighboring Routers in MANET network connected to particular Backpressure Interface. This information is acquired through combining Queue Information Base and Interface Information Base (of this particular Backpressure Interface). Both values of Backpressure interface's Urgency and Maximum Urgency Holder are interface-specific. Thus UR messages are generated independently. 7.2.1.1. Urgency calculation This section presents only the example of a method for calculation of Urgency value. Implementation of the Backpressure Extension can use any other algorithm which will provide similar results. Interface Urgency Holder is set as follows: 1. Interface Urgency := 0; 2. For each Queue Tuple (i) from Queue Set where Q_addr is in Originator Tuple from Originator Set of Local Information Base as O_orig_addr. * For each Routing Tuple from Routing Set where R_local_iface_addr = this interface. + For each Queue Tuple (j) from Queue Set where Q_addr (j) = R_next_iface_addr and Q_fid (j) = Q_fid (i). - If Interface Urgency < Q_value (j) - Q_value (i) then Interface Urgency := Q_value (j) - Q_value (i) Maximum Urgency Holder (H_addr, H_urgency) for Backpressure Interface is set as follows: 1. H_addr := Local interface address and H_urgency := Local interface Urgency 2. For each Urgency Tuple in Urgency Set of Queue Information Base: * If there is Link Tuple in Link Set of Interface Information Base, for which: + L_neighbor_iface_addr_list contains U_addr; AND Szwabe, et al. Expires November 3, 2011 [Page 15] Internet-Draft Backpressure extension of OLSRv2 May 2011 + L_status = HEARD. and U_level > H_urgency then: + H_addr := U_addr; + H_urgency := U_level. 7.2.2. UR Message TLVs This specification defines one Message TLV and one Address Block TLV, both specific for UR message. 7.2.2.1. Message TLVs In a UR message, a Router MUST include one O_URGENCY TLV as specified in Table 4. +-----------+--------+----------------------------------------------+ | Name | Value | Description | | | Length | | +-----------+--------+----------------------------------------------+ | O_URGENCY | Up to | Specifies the Urgency of the Originator | | | 4 | Router. This value is represented as | | | octets | unsigned integer in network byte order. | +-----------+--------+----------------------------------------------+ Table 4: O_URGENCY TLV definition 7.2.2.2. Address Block TLVs +---------+---------+-----------------------------------------------+ | Name | Value | Description | | | Length | | +---------+---------+-----------------------------------------------+ | URGENCY | Up to 4 | Specifies the Urgency of the Router. This | | | octets | value is represented as unsigned integer in | | | | network byte order. | +---------+---------+-----------------------------------------------+ Table 5: URGENCY TLV definition 7.2.3. UR Message Transmission In order to exchange Urgency values between Routers, each Router MUST generate UR Messages. The messages MUST be transmitted according to UR_INTERVAL. Each Router utilizes its own Queue Information Base which contains the most recent Urgency values among the defined Szwabe, et al. Expires November 3, 2011 [Page 16] Internet-Draft Backpressure extension of OLSRv2 May 2011 (2-hop by default) neighborhood. UR Message contains information about Urgency of the Router which sends the message as well as the information about the maximal Urgency (and its holder) in the sending Router neighborhood (which in particular case may be the Router own Urgency). After each UR_INTERVAL, UR Message has been generated and broadcast to Router's neighbors. To determine the maximal Urgency in the neighborhood, the latest available information about Urgencies stored in Queue Information Base is used. 7.2.4. UR Message Processing Each received (and not discarded) UR message, after initially being processed according to [RFC5444], is analyzed by the Router and used to update the Queue Information Base, with the following rules in mind: o There must be only one Neighbor Tuple in Queue Information Base corresponding to the QR message originator address. o If there is not Neighbor Tuple in Queue Information Base corresponding to the UR message originator address, such Neighbor Tuple MUST be created. 8. Data Available for Schedulers The Backpressure Extension of OLSRv2 defines the minimal set of features required to use backpressure-based schedulers. The network area taken into account when the backpressure is calculated, SHOULD NOT be considered as covering the full network. In a case, when the values of QR_HOPLIMIT are set to proposed default (1), the area where backpressure information is available is limited to 2-hop neighborhood of the Router. Such range MAY be treated as an approximation of a collision domain of the Router. A 1-hop neighborhood area is covered by QR messages containing neighbors' Queue Levels. This area is extended to 2 hops, thanks to application of UR messages which contain information from the 2-hop neighborhood, in the form of the maximum backpressure weight together with its holders. An agent of the standard OLSRv2 protocol interacts with the IP layer through the Routing Set, consisting of the following information (corresponding to Routing Tuples of OLSRv2): Szwabe, et al. Expires November 3, 2011 [Page 17] Internet-Draft Backpressure extension of OLSRv2 May 2011 o Destination address o Next-hop address o Interface address o Distance Backpressure Extension of OLSRv2 described in this document extends this data in order to enable the scheduler to utilize the backpressure weights. Unlike the standard OLSRv2, data available for scheduler can be regarded as flow-oriented: each Flow has its own queues. The routing possibilities MAY be determined for each Flow separately. The QR and UR messages are transmitted periodically in parallel with regular data traffic. As a result, the Queue Level Set and Urgency Set (described in Section 6.6) are updated. Based on this data the scheduler is able to construct the table consisting of the following elements: o Flow Identifier (containing the destination Router address) o Next-hop address o Interface address o Urgency o Distance which may be presented as follows: +---+-------------+-------------+--------------+---------+----------+ | # | Flow | Next-hop | Interface | Urgency | Distance | | | Identifier | address | address | | | +---+-------------+-------------+--------------+---------+----------+ | 1 | (X) | (A) | eth0 | 4 | 2 | | 2 | (X) | (B) | eth0 | 10 | 3 | | 3 | (X) | (C) | eth0 | 9 | 2 | | 4 | (Y) | (C) | eth0 | 14 | 4 | | 5 | ... | ... | ... | ... | ... | +---+-------------+-------------+--------------+---------+----------+ Table 6: The table of extended routing entries The Urgencies of the computing Router's Flows MAY be set on the basis of the Queue Level Set entries. Following the classical backpressure Szwabe, et al. Expires November 3, 2011 [Page 18] Internet-Draft Backpressure extension of OLSRv2 May 2011 approach the Urgency for a given Flow and a given next-hop MAY be calculated as the differences of the Flow queue levels on the computing Router and the next-hop Router. Additionally, thanks to the Urgency Set entries the scheduler is able to use the information about the maximum value of Urgency in the neighborhood of the computing node. 9. Interoperability with other OLSRv2 Routers An OLSRv2 router running the backpressure extension can interoperate with an OLSRv2 router that does not run this extension. The Backpressure Extension provides functionalities considered as auxiliary. Additional messages are implemented according to [RFC5444] specification. Router which does not support the proposed OLSRv2 protocol extension may simply discard additional information. As for Backpressure Routers, the Router behavior for a case when there is no information about Queue Levels available from Basic OLSRv2 Routers is specified in Section 7.1.4. Same rules apply to Backpressure Routers using different Flow identification (see Section 6.5). The Backpressure Router can use following strategies to effectively use routes of Basic OLSRv2 Routers: o Temporary assuming Basic OLSRv2 Router's Queue Levels, that will make it last candidate for sending to. o Temporary assuming that Basic OLSRv2 Router's Queue Level is average of Neighbor Backpressure Routers Queue Level for particular Flow. 10. Values for Parameters and Constants 10.1. Message Interval Parameters o QR_INTERVAL := 300 milliseconds o UR_INTERVAL := QR_INTERVAL / 8 10.2. Message Validity Times Parameters o UR_HOLD_TIME := UR_INTERVAL x 3 o QR_HOLD_TIME := QR_INTERVAL x 3 Szwabe, et al. Expires November 3, 2011 [Page 19] Internet-Draft Backpressure extension of OLSRv2 May 2011 10.3. Hop Limit Parameter o QR_HOPLIMIT := 1 o UR_HOPLIMIT := QR_HOPLIMIT 10.4. Jitter Time Parameters o QR_MAXJITTER := QR_INTERVAL / 4 o UR_MAXJITTER := UR_INTERVAL / 4 11. Security Considerations To be elaborated. 12. IANA Considerations This specification defines two Message Types, which must be allocated from the "Message Types" registry of [RFC5444]. 12.1. Expert Review: Evaluation Guidelines For the registries where an Expert Review is required, the designated expert SHOULD take the same general recommendations into consideration as are specified by [RFC5444]. 12.2. Message Types This specification defines two Message Types, to be allocated from the 0-223 range of the "Message Types" namespace defined in [RFC5444], as specified in Table 7. +------+-------------------------+ | Type | Description | +------+-------------------------+ | TBD1 | UR : Urgency report | | TBD2 | QR : Queue Level report | +------+-------------------------+ Table 7: Message Type assignment Szwabe, et al. Expires November 3, 2011 [Page 20] Internet-Draft Backpressure extension of OLSRv2 May 2011 12.3. Message-Type-specific TLV Type Registries IANA is requested to create a registry for Message-Type-specific Message TLVs for UR messages, in accordance with Section 6.2.1 of [RFC5444], and with initial assignments and allocation policies as specified in Table 8. +-----------+---------+--------------------------+------------------+ | Name | Type | Description | Allocation | | | | | Policy | +-----------+---------+--------------------------+------------------+ | O_URGENCY | 128 | Specifies Router's | | | | | Urgency. | | | | 129-223 | Unassigned | Expert Review | +-----------+---------+--------------------------+------------------+ Table 8: UR Message-Type-specific Message TLVs IANA is requested to create a registry for Message-Type-specific Address block TLVs for UR messages, in accordance with Section 6.2.1 of [RFC5444], and with initial assignments and allocation policies as specified in Table 9. +---------+---------+-------------------------------+---------------+ | Name | Type | Description | Allocation | | | | | Policy | +---------+---------+-------------------------------+---------------+ | URGENCY | 128 | Specifies Urgency of | | | | | associated Router. | | | | 129-223 | Unassigned | Expert Review | +---------+---------+-------------------------------+---------------+ Table 9: UR Message-Type-specific Address block TLVs IANA is requested to create a registry for Message-Type-specific Message TLVs for QR messages, in accordance with Section 6.2.1 of [RFC5444], and with initial assignments and allocation policies as specified in Table 10. +---------+-------------+-------------------+ | Type | Description | Allocation Policy | +---------+-------------+-------------------+ | 128-223 | Unassigned | Expert Review | +---------+-------------+-------------------+ Table 10: QR Message-Type-specific Message TLVs IANA is requested to create a registry for Message-Type-specific Szwabe, et al. Expires November 3, 2011 [Page 21] Internet-Draft Backpressure extension of OLSRv2 May 2011 Address block TLVs for UR messages, in accordance with Section 6.2.1 of [RFC5444], and with initial assignments and allocation policies as specified in Table 11. +-------------+---------+------------------------------+------------+ | Name | Type | Description | Allocation | | | | | Policy | +-------------+---------+------------------------------+------------+ | PROTOCOL | 128 | Specifies Protocol Number | | | | | used on the transport layer. | | | QUEUE_LEVEL | 129 | Specifies Queue Level | | | | | status. | | | PORT | 130 | Specifies port address used | | | | | on the transport layer. | | | | 131-223 | Unassigned | Expert | | | | | Review | +-------------+---------+------------------------------+------------+ Table 11: QR Message-Type-specific Address block TLVs 13. Acknowledgements This work was partly supported by the grant of Poznan University of Technology DS 45-083/10 and the European Commission OPNEX STREP (FP7- 224218, http://opnex.eu). The authors also want to thank the following people for their contributions to this document: o Adam Nowak, Poznan University of Technology, Poland, o Przemyslaw Walkowiak, Poznan University of Technology, Poland, 14. References 14.1. Normative References [I-D.dearlove-olsrv2-metrics] Dearlove, C., Clausen, T., and P. Jacquet, "Link Metrics for OLSRv2", draft-dearlove-olsrv2-metrics-05 (work in progress), June 2010. [I-D.ietf-manet-olsrv2] Clausen, T., Dearlove, C., and P. Jacquet, "The Optimized Szwabe, et al. Expires November 3, 2011 [Page 22] Internet-Draft Backpressure extension of OLSRv2 May 2011 Link State Routing Protocol version 2", draft-ietf-manet-olsrv2-11 (work in progress), April 2010. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter Considerations in Mobile Ad Hoc Networks (MANETs)", RFC 5148, February 2008. [RFC5444] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, "Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format", RFC 5444, February 2009. [RFC5498] Chakeres, I., "IANA Allocations for Mobile Ad Hoc Network (MANET) Protocols", RFC 5498, March 2009. [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)", RFC 6130, April 2011. 14.2. Informative References [I-D.multipath-olsrv2] Szwabe, A., Nowak, A., Baccelli, E., Yi, J., and B. Parrein, "Multi-path for Optimized Link State Routing Protocol version 2", draft-szwabe-manet-multipath-olsrv2 (work in progress), 2010. [SMN+10] Szwabe, A., Misiorek, P., Nowak, A., and J. Marchwicki, "Implementation of Backpressure-Based Routing Integrated with Max-Weight Scheduling in a Wireless Multi-hop Network", Proc. of 3rd IEEE International Workshop on Wireless and Internet Services (WISe 2010), Denver, USA, pages 999-1004, 2010. Appendix A. Illustrations A.1. QR Message Examples This appendix illustrates QR message examples. As QR message is a instance of [RFC5444] and its exact form depends on conveyed information formatted by the sender. Because of that following examples show only possible form that specified information can be presented. First example of QR message conveys information about Queue Levels of Szwabe, et al. Expires November 3, 2011 [Page 23] Internet-Draft Backpressure extension of OLSRv2 May 2011 two Flows. The Backpressure Router uses complex Flow Identifier containing: o Destination address o Source address o Internet Protocol Number of a protocol used in the transport layer o If used, an additional transport protocol source and destination address (i.e. port addresses in TCP or UDP) This message contains two information about Flows: o UDP (17) stream from IP 192.168.40.1:4563 to 192.168.40.67:8213 o ICMP (1) ping requests from 192.168.40.72 to 192.168.40.69 Szwabe, et al. Expires November 3, 2011 [Page 24] Internet-Draft Backpressure extension of OLSRv2 May 2011 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QR |1 1 0 1|0 0 1 1|0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1| Message Sequence Number |0 0 0 0 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 0|0 0 0 0 0 0 1 0|1 0 0 0 0| Rsv |0 0 0 0 0 0 1 1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Head (192.168.40.) | Mid (.1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Mid (.67) |0 0 0 0 0 0 0 0|0 0 0 1 0 0 0 1| PORT TLV | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 1 0 1|Rsv|0 0 0 0 0 1 0 0| VALUE = UDP SRC PORT (4563) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | VALUE = UDP DST PORT (8213) | PROTOCOL TLV |0 0 0 1 0 0|Rsv| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1| VALUE = 17 |QUEUE_LEVEL TLV|0 0 0 1 0 0|Rsv| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 1 1| VALUE = QUEUE LEVEL | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 1 0|1 0 0 0 0| Rsv |0 0 0 0 0 0 1 1| Head | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Head (cont, 192.168.40.) | Mid (.72) | Mid (.69) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 0|0 0 0 0 1 1 0 1| PROTOCOL TLV |0 0 0 1 0 0|Rsv| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1| VALUE = 1 |QUEUE_LEVEL TLV|0 0 0 1 0 0|Rsv| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 1 0 0| VALUE = QUEUE LEVEL | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | VALUE (cont) | +-+-+-+-+-+-+-+-+ Figure 1: QR Message example of two Flows with a full Flow Identifier. Second example of QR message conveys information about Queue Levels of two Flows. Origin Backpressure Router uses Flow Identifier containing only: o Destination address o Source address This message contains two information about Flows: Szwabe, et al. Expires November 3, 2011 [Page 25] Internet-Draft Backpressure extension of OLSRv2 May 2011 o IP packets from IP 192.168.40.1 to 192.168.40.67 o IP packets from 192.168.40.72 to 192.168.40.69 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QR |1 1 0 1|0 0 1 1|0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1| Message Sequence Number |0 0 0 0 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 0|0 0 0 0 0 0 1 0|1 0 0 0 0| Rsv |0 0 0 0 0 0 1 1| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Head (192.168.40.) | Mid (.1) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Mid (.67) |0 0 0 0 0 0 0 0|0 0 0 1 0 0 1 0|QUEUE_LEVEL TLV| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 1 0 0|Rsv|0 0 0 0 0 1 0 0| VALUE = QUEUE LEVEL | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | VALUE (cont) |0 0 0 0 0 0 1 0|1 0 0 0 0| Rsv | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 1 1| Head (192.168.40.) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Mid (.72) | Mid (.69) |0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |QUEUE_LEVEL TLV|0 0 0 1 0 0|Rsv|0 0 0 0 0 1 0 0| VALUE | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | VALUE (cont) = QUEUE LEVEL | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2: QR Message example of two Flows with a simplified Flow Identifier. Szwabe, et al. Expires November 3, 2011 [Page 26] Internet-Draft Backpressure extension of OLSRv2 May 2011 A.2. UR Message Example 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | UR |1 1 0 1|0 0 1 1|0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hop Limit | Message Sequence Number |0 0 0 0 0 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 1 1 0| O_URGENCY TLV |0 0 0 1 0 0|Rsv|0 0 0 0 0 1 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | VALUE = ORIGIN URGENCY LEVEL | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 1|0 0 0 0 0| Rsv | Mid | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Mid (cont) |0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | URGENCY TLV |0 0 0 1 0 0|Rsv| VALUE = URGENCY LEVEL | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | VALUE (cont) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3: QR Message Example of one Flow. Authors' Addresses Andrzej Szwabe Poznan University of Technology 5 M. Sklodowskiej-Curie Sq. 60-965 Poznan Poland Phone: +48 61 665 3958 Email: Andrzej.Szwabe@put.poznan.pl Pawel Misiorek Poznan University of Technology 5 M. Sklodowskiej-Curie Sq. 60-965 Poznan Poland Phone: +48 61 665 3958 Email: Pawel.Misiorek@put.poznan.pl Szwabe, et al. Expires November 3, 2011 [Page 27] Internet-Draft Backpressure extension of OLSRv2 May 2011 Maciej Urbanski (editor) Poznan University of Technology 5 M. Sklodowskiej-Curie Sq. 60-965 Poznan Poland Phone: +48 61 665 3958 Email: Maciej.Urbanski@put.poznan.pl Emmanuel Baccelli INRIA Phone: +33-169-335-511 Email: Emmanuel.Baccelli@inria.fr URI: http://www.emmanuelbaccelli.org/ Szwabe, et al. Expires November 3, 2011 [Page 28]