idnits 2.17.1 draft-chroboczek-babel-diversity-routing-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 177: '...monious encoding MAY be preferred by i...' RFC 2119 keyword, line 179: '... encodings MUST be correctly parsed ...' RFC 2119 keyword, line 214: '... a one-octet integer. The values MUST...' RFC 2119 keyword, line 224: '...ting IEEE 802.11 SHOULD use values 1 t...' RFC 2119 keyword, line 227: '... SHOULD choose values that do not co...' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (February 15, 2016) is 2994 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- ** Obsolete normative reference: RFC 6126 (Obsoleted by RFC 8966) ** Obsolete normative reference: RFC 7557 (Obsoleted by RFC 8966) Summary: 5 errors (**), 0 flaws (~~), 1 warning (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group J. Chroboczek 3 Internet-Draft IRIF, University of Paris-Diderot 4 Intended status: Experimental February 15, 2016 5 Expires: August 18, 2016 7 Diversity Routing for the Babel Routing Protocol 8 draft-chroboczek-babel-diversity-routing-01 10 Abstract 12 This document defines an extension to the Babel routing protocol that 13 allows routing updates to carry radio frequency information, and 14 therefore makes it possible to use radio diversity information for 15 route selection. 17 Status of This Memo 19 This Internet-Draft is submitted in full conformance with the 20 provisions of BCP 78 and BCP 79. 22 Internet-Drafts are working documents of the Internet Engineering 23 Task Force (IETF). Note that other groups may also distribute 24 working documents as Internet-Drafts. The list of current Internet- 25 Drafts is at http://datatracker.ietf.org/drafts/current/. 27 Internet-Drafts are draft documents valid for a maximum of six months 28 and may be updated, replaced, or obsoleted by other documents at any 29 time. It is inappropriate to use Internet-Drafts as reference 30 material or to cite them other than as "work in progress." 32 This Internet-Draft will expire on August 18, 2016. 34 Copyright Notice 36 Copyright (c) 2016 IETF Trust and the persons identified as the 37 document authors. All rights reserved. 39 This document is subject to BCP 78 and the IETF Trust's Legal 40 Provisions Relating to IETF Documents 41 (http://trustee.ietf.org/license-info) in effect on the date of 42 publication of this document. Please review these documents 43 carefully, as they describe your rights and restrictions with respect 44 to this document. Code Components extracted from this document must 45 include Simplified BSD License text as described in Section 4.e of 46 the Trust Legal Provisions and are provided without warranty as 47 described in the Simplified BSD License. 49 Table of Contents 51 1. Introduction and background . . . . . . . . . . . . . . . . . 2 52 2. Operation of the protocol . . . . . . . . . . . . . . . . . . 3 53 2.1. Changes to data structures . . . . . . . . . . . . . . . 3 54 2.2. Receiving updates . . . . . . . . . . . . . . . . . . . . 4 55 2.3. Sending updates . . . . . . . . . . . . . . . . . . . . . 4 56 2.4. Metric computation and route selection . . . . . . . . . 5 57 2.5. Protocol encoding . . . . . . . . . . . . . . . . . . . . 5 58 3. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6 59 4. References . . . . . . . . . . . . . . . . . . . . . . . . . 6 60 Appendix A. The Z3 algorithm . . . . . . . . . . . . . . . . . . 7 61 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 7 63 1. Introduction and background 65 The Babel routing protocol [RFC6126] does not mandate a specific 66 algorithm for computing metrics; Appendix A of that document suggests 67 using an additive integer metric. While this works well in many 68 topologies, it fails to take into account the possibility of 69 interference between radio links, which is important in multi- 70 frequency wireless mesh networks. 72 Consider for example the following topology, where the solid lines 73 use one radio frequency and the dashed lines another, and suppose 74 that the solid frequency has very slightly lower packet loss than the 75 dashed one: 77 B 78 / \ 79 / \ 80 A D 81 \ . 82 \ . 83 C 85 When sending data from A to D, Babel will reliably choose the solid 86 route through B. Howerver, this route self-interferes: when B is 87 sending a packet to D, it cannot simultaneously be receiving a packet 88 from A, which halves the effective throughput. No such issue arises 89 with the route through C, which should therefore be preferred. 91 Interference needs to be taken into account even when it happens 92 between non-adjacent links. Consider the following topology: 94 B +++ C 95 / \ 96 / \ 97 A F 98 \ . 99 \ . 100 D +++ E 102 When routing data from A to F, the route through B and C has two 103 interfering links: if two packets are sent by A and C at roughly the 104 same time, a collision will occur, and both packets will need to be 105 resent. Again, no such issue arises with the route through D and E. 107 2. Operation of the protocol 109 The diversity protocol extension allows a Babel router to attach 110 information about radio frequency to the routes that it maintains -- 111 we call this the route's "diversity information". 113 We assume that all links can be categorised into one of the following 114 categories: 116 o non-interfering links, e.g. wired links; 118 o links that have a well defined frequency, and only interfere with 119 other links at the same frequency; these are described by a single 120 channel number, an integer between 1 and 254; 122 o interfering links, links that interfere with all other links 123 except non-interfering links. 125 This model does not describe reality accurately, since distinct but 126 close radio frequencies do in fact interfere, but it works well 127 enough in practical networks, where a small number of discrete radio 128 frequencies are used. 130 2.1. Changes to data structures 132 A Babel router maintains a route table ([RFC6126] Section 3.2.5). A 133 router implementing diversity routing has one additional field in 134 every route table entry: 136 o the diversity data, a (possibly zero-length) sequence of channel 137 numbers, each of which is an integer between 0 and 255. 139 The diversity data is interpreted as the set of channels of the links 140 that would be followed by a packet sent along this route, omitting 141 non-interfering links. The values 0 and 255 are special: they 142 indicate, respectively, a non-interfering link (a link that doesn't 143 interfere with any other links) and an interfering link (a link that 144 is assumed to interfere with all other links except non-interfering 145 ones). 147 2.2. Receiving updates 149 When a node receives an Update TLV, it creates or updates a routing 150 table entry according to [RFC6126], Section 3.5.4. A node that 151 performs diversity routing extends the procedure given in that 152 section with the following actions. 154 Let D be the diversity information attached to the received Update 155 TLV, or the one-element sequence 255 if there is no such information. 156 Then the diversity information in the routing table entry is set to 157 D', where: 159 o if the interface over which the update was received is non- 160 interfering, then either D'=0.D or D'=D (the choice is left to the 161 implementation); 163 o if the interface over which the update was received is 164 interfering, then D'=255.D; 166 o if the interface over which the update was received is tuned to 167 channel C, then D'=C.D. 169 Note that zero-length diversity information is different from lack of 170 diversity information: the latter is treated as 255 (interfering, 171 since no information is available) in order to ensure reasonable 172 behaviour when interoperating with the original Babel protocol. 174 Note further that there are two ways of encoding a non-interfering 175 link: the interference information can be omitted (D'=D) or a 0 can 176 be prepended to the interference information. The latter, less 177 parsimonious encoding MAY be preferred by implementations that wish 178 to ignore diversity information after a given number of hops. Both 179 encodings MUST be correctly parsed by a receiving node. 181 2.3. Sending updates 183 A Babel node sends updates in various circumstances, described in 184 [RFC6126], Section 3.7. A node performing diversity routing attaches 185 diversity data to every update that it send. This diversity data is 186 computed as follows: 188 o if the update is for a locally redistributed route, then the value 189 is implementation-dependent (zero-length diversity information is 190 a good choice in most cases); 192 o if the update is for a route in the Babel route table, then the 193 diversity information is taken from the route table. 195 2.4. Metric computation and route selection 197 How the diversity data is used for metric computation and/or route 198 selection is left to the implementation, as long as it obeys the 199 rules given in Sections 3.5.2 and 3.6 of [RFC6126]. In particular, 200 the strict monotonicity requirement implies that a non-interfering 201 hop must be taken into account in the resulting metric -- it cannot 202 be simply ignored. 204 An algorithm that has been found to work well in practice is given in 205 Appendix A. 207 2.5. Protocol encoding 209 We define one new sub-TLV which is attached to Update TLVs and 210 contains a sequence of channel numbers. 212 2.5.1. Encoding of channel numbers 214 A channel number is encoded as a one-octet integer. The values MUST 215 be interpreted as follows: 217 o 0: used to represent a non-interfering link; 219 o 1-254: radio channel numbers, link-technology specific 221 o 255: used to represent an interfering link. 223 In order to ensure consistent metrics computation, implementations 224 supporting IEEE 802.11 SHOULD use values 1 through 14 and 46 through 225 165 for encoding IEEE 802.11b and IEEE 802.11a channel numbers 226 respectively, and implementations using other link technologies 227 SHOULD choose values that do not collide with IEEE 802.11a/b channel 228 numbers. However, since choosing inconsistent values does not 229 prevent interoperability but merely leads to suboptimal routing, this 230 is not mandated by this specification. 232 2.5.2. The Diversity sub-TLV 234 Diversity data is carried in a Diversity sub-TLV [RFC7557] that is 235 carried by Update TLVs. The sub-TLV contains a sequence of octets 236 that directly encode the diversity data from the route table. 238 0 1 2 3 239 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 240 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 241 | Type = 2 | Length | Channel 1 | Channel 2 | 242 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 243 | Channel 3 | ... 244 +-+-+-+-+-+-+-+-+-+-+-+-+- 246 Fields : 248 Type Set to 2 to indicate a Diversity Information sub-TLV. 250 Length The length of the body, exclusive of the Type and Length 251 fields. 253 Channel n An integer between 0 and 255, as described in the previous 254 section. 256 3. IANA Considerations 258 IANA is instructed to add the following entry to the "Babel Sub-TLV 259 Types" registry: 261 +------+-----------+-----------------+ 262 | Type | Name | Reference | 263 +------+-----------+-----------------+ 264 | 2 | Diversity | (this document) | 265 +------+-----------+-----------------+ 267 4. References 269 [RFC6126] Chroboczek, J., "The Babel Routing Protocol", RFC 6126, 270 April 2011, . 272 [RFC7557] Chroboczek, J., "Extension Mechanism for the Babel Routing 273 Protocol", RFC 7557, May 2015, 274 . 276 Appendix A. The Z3 algorithm 278 In this section, we describe the Z3 algorithm, a particular instance 279 of diversity routing that has seen some modest deployment and that 280 appears to work reasonably well in practice while being extremely 281 easy to implement. 283 The Z3 algorithm works by announcing a slightly smaller metric than 284 the metric it uses for route selection when announcing over a non- 285 interfering link. In effect, a Z3 router maintains two metrics for 286 each route: the noninterfering metric, which is announced on links 287 that can be proven to not interfere with the route being announced, 288 and the interfering metric, which is used for route selection and 289 announced over all other links. 291 More precisely, upon receiving an update with metric M over a link 292 with cost C, the interfering metric is set to C+M, as suggested in 293 Appendix A of [RFC6126]. The non-interfering metric is set to 294 alpha*C+M, where 0