Debian Codegraph @

rfc6126.html

raw
1 <pre>Independent Submission J. Chroboczek
2 Request for Comments: 6126 PPS, University of Paris 7
3 Category: Experimental April 2011
4 ISSN: 2070-1721
5
6
7 <span class="h1">The Babel Routing Protocol</span>
8
9 Abstract
10
11 Babel is a loop-avoiding distance-vector routing protocol that is
12 robust and efficient both in ordinary wired networks and in wireless
13 mesh networks.
14
15 Status of This Memo
16
17 This document is not an Internet Standards Track specification; it is
18 published for examination, experimental implementation, and
19 evaluation.
20
21 This document defines an Experimental Protocol for the Internet
22 community. This is a contribution to the RFC Series, independently
23 of any other RFC stream. The RFC Editor has chosen to publish this
24 document at its discretion and makes no statement about its value for
25 implementation or deployment. Documents approved for publication by
26 the RFC Editor are not a candidate for any level of Internet
27 Standard; see <a href="./rfc5741#section-2">Section&nbsp;2 of RFC 5741</a>.
28
29 Information about the current status of this document, any errata,
30 and how to provide feedback on it may be obtained at
31 <a href="http://www.rfc-editor.org/info/rfc6126">http://www.rfc-editor.org/info/rfc6126</a>.
32
33 Copyright Notice
34
35 Copyright (c) 2011 IETF Trust and the persons identified as the
36 document authors. All rights reserved.
37
38 This document is subject to <a href="https://www.rfc-editor.org/bcp/bcp78">BCP 78</a> and the IETF Trust's Legal
39 Provisions Relating to IETF Documents
40 (<a href="http://trustee.ietf.org/license-info">http://trustee.ietf.org/license-info</a>) in effect on the date of
41 publication of this document. Please review these documents
42 carefully, as they describe your rights and restrictions with respect
43 to this document.
44
45
46
47
48
49
50
51
52 <span class="grey">Chroboczek Experimental [Page 1]</span></pre>
53 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span>
54 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
55
56
57 Table of Contents
58
59 <a href="#section-1">1</a>. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-3">3</a>
60 <a href="#section-1.1">1.1</a>. Features . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-3">3</a>
61 <a href="#section-1.2">1.2</a>. Limitations . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-4">4</a>
62 <a href="#section-1.3">1.3</a>. Specification of Requirements . . . . . . . . . . . . . . <a href="#page-4">4</a>
63 <a href="#section-2">2</a>. Conceptual Description of the Protocol . . . . . . . . . . . . <a href="#page-4">4</a>
64 <a href="#section-2.1">2.1</a>. Costs, Metrics, and Neighbourship . . . . . . . . . . . . <a href="#page-5">5</a>
65 <a href="#section-2.2">2.2</a>. The Bellman-Ford Algorithm . . . . . . . . . . . . . . . . <a href="#page-5">5</a>
66 <a href="#section-2.3">2.3</a>. Transient Loops in Bellman-Ford . . . . . . . . . . . . . <a href="#page-6">6</a>
67 <a href="#section-2.4">2.4</a>. Feasibility Conditions . . . . . . . . . . . . . . . . . . <a href="#page-6">6</a>
68 <a href="#section-2.5">2.5</a>. Solving Starvation: Sequencing Routes . . . . . . . . . . <a href="#page-8">8</a>
69 <a href="#section-2.6">2.6</a>. Requests . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-9">9</a>
70 <a href="#section-2.7">2.7</a>. Multiple Routers . . . . . . . . . . . . . . . . . . . . . <a href="#page-10">10</a>
71 <a href="#section-2.8">2.8</a>. Overlapping Prefixes . . . . . . . . . . . . . . . . . . . <a href="#page-11">11</a>
72 <a href="#section-3">3</a>. Protocol Operation . . . . . . . . . . . . . . . . . . . . . . <a href="#page-11">11</a>
73 <a href="#section-3.1">3.1</a>. Message Transmission and Reception . . . . . . . . . . . . <a href="#page-11">11</a>
74 <a href="#section-3.2">3.2</a>. Data Structures . . . . . . . . . . . . . . . . . . . . . <a href="#page-12">12</a>
75 <a href="#section-3.3">3.3</a>. Acknowledged Packets . . . . . . . . . . . . . . . . . . . <a href="#page-15">15</a>
76 <a href="#section-3.4">3.4</a>. Neighbour Acquisition . . . . . . . . . . . . . . . . . . <a href="#page-15">15</a>
77 <a href="#section-3.5">3.5</a>. Routing Table Maintenance . . . . . . . . . . . . . . . . <a href="#page-17">17</a>
78 <a href="#section-3.6">3.6</a>. Route Selection . . . . . . . . . . . . . . . . . . . . . <a href="#page-21">21</a>
79 <a href="#section-3.7">3.7</a>. Sending Updates . . . . . . . . . . . . . . . . . . . . . <a href="#page-22">22</a>
80 <a href="#section-3.8">3.8</a>. Explicit Route Requests . . . . . . . . . . . . . . . . . <a href="#page-24">24</a>
81 <a href="#section-4">4</a>. Protocol Encoding . . . . . . . . . . . . . . . . . . . . . . <a href="#page-27">27</a>
82 <a href="#section-4.1">4.1</a>. Data Types . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-28">28</a>
83 <a href="#section-4.2">4.2</a>. Packet Format . . . . . . . . . . . . . . . . . . . . . . <a href="#page-29">29</a>
84 <a href="#section-4.3">4.3</a>. TLV Format . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-29">29</a>
85 <a href="#section-4.4">4.4</a>. Details of Specific TLVs . . . . . . . . . . . . . . . . . <a href="#page-30">30</a>
86 <a href="#section-5">5</a>. IANA Considerations . . . . . . . . . . . . . . . . . . . . . <a href="#page-39">39</a>
87 <a href="#section-6">6</a>. Security Considerations . . . . . . . . . . . . . . . . . . . <a href="#page-39">39</a>
88 <a href="#section-7">7</a>. References . . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-40">40</a>
89 <a href="#section-7.1">7.1</a>. Normative References . . . . . . . . . . . . . . . . . . . <a href="#page-40">40</a>
90 <a href="#section-7.2">7.2</a>. Informative References . . . . . . . . . . . . . . . . . . <a href="#page-40">40</a>
91 <a href="#appendix-A">Appendix A</a>. Cost and Metric Computation . . . . . . . . . . . . . <a href="#page-41">41</a>
92 <a href="#appendix-A.1">A.1</a>. Maintaining Hello History . . . . . . . . . . . . . . . . <a href="#page-41">41</a>
93 <a href="#appendix-A.2">A.2</a>. Cost Computation . . . . . . . . . . . . . . . . . . . . . <a href="#page-42">42</a>
94 <a href="#appendix-A.3">A.3</a>. Metric Computation . . . . . . . . . . . . . . . . . . . . <a href="#page-43">43</a>
95 <a href="#appendix-B">Appendix B</a>. Constants . . . . . . . . . . . . . . . . . . . . . . <a href="#page-43">43</a>
96 <a href="#appendix-C">Appendix C</a>. Simplified Implementations . . . . . . . . . . . . . <a href="#page-44">44</a>
97 <a href="#appendix-D">Appendix D</a>. Software Availability . . . . . . . . . . . . . . . . <a href="#page-45">45</a>
98
99
100
101
102
103
104
105
106
107
108 <span class="grey">Chroboczek Experimental [Page 2]</span></pre>
109 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span>
110 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
111
112
113 <span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a>. Introduction</span>
114
115 Babel is a loop-avoiding distance-vector routing protocol that is
116 designed to be robust and efficient both in networks using prefix-
117 based routing and in networks using flat routing ("mesh networks"),
118 and both in relatively stable wired networks and in highly dynamic
119 wireless networks.
120
121 <span class="h3"><a class="selflink" id="section-1.1" href="#section-1.1">1.1</a>. Features</span>
122
123 The main property that makes Babel suitable for unstable networks is
124 that, unlike naive distance-vector routing protocols [<a href="#ref-RIP" title="&quot;RIP Version 2&quot;">RIP</a>], it
125 strongly limits the frequency and duration of routing pathologies
126 such as routing loops and black-holes during reconvergence. Even
127 after a mobility event is detected, a Babel network usually remains
128 loop-free. Babel then quickly reconverges to a configuration that
129 preserves the loop-freedom and connectedness of the network, but is
130 not necessarily optimal; in many cases, this operation requires no
131 packet exchanges at all. Babel then slowly converges, in a time on
132 the scale of minutes, to an optimal configuration. This is achieved
133 by using sequenced routes, a technique pioneered by Destination-
134 Sequenced Distance-Vector routing [<a href="#ref-DSDV" title="&quot;Highly Dynamic Destination- Sequenced Distance-Vector Routing (DSDV) for Mobile Computers&quot;">DSDV</a>].
135
136 More precisely, Babel has the following properties:
137
138 o when every prefix is originated by at most one router, Babel never
139 suffers from routing loops;
140
141 o when a prefix is originated by multiple routers, Babel may
142 occasionally create a transient routing loop for this particular
143 prefix; this loop disappears in a time proportional to its
144 diameter, and never again (up to an arbitrary garbage-collection
145 (GC) time) will the routers involved participate in a routing loop
146 for the same prefix;
147
148 o assuming reasonable packet loss rates, any routing black-holes
149 that may appear after a mobility event are corrected in a time at
150 most proportional to the network's diameter.
151
152 Babel has provisions for link quality estimation and for fairly
153 arbitrary metrics. When configured suitably, Babel can implement
154 shortest-path routing, or it may use a metric based, for example, on
155 measured packet loss.
156
157 Babel nodes will successfully establish an association even when they
158 are configured with different parameters. For example, a mobile node
159 that is low on battery may choose to use larger time constants (hello
160 and update intervals, etc.) than a node that has access to wall
161
162
163
164 <span class="grey">Chroboczek Experimental [Page 3]</span></pre>
165 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span>
166 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
167
168
169 power. Conversely, a node that detects high levels of mobility may
170 choose to use smaller time constants. The ability to build such
171 heterogeneous networks makes Babel particularly adapted to the
172 wireless environment.
173
174 Finally, Babel is a hybrid routing protocol, in the sense that it can
175 carry routes for multiple network-layer protocols (IPv4 and IPv6),
176 whichever protocol the Babel packets are themselves being carried
177 over.
178
179 <span class="h3"><a class="selflink" id="section-1.2" href="#section-1.2">1.2</a>. Limitations</span>
180
181 Babel has two limitations that make it unsuitable for use in some
182 environments. First, Babel relies on periodic routing table updates
183 rather than using a reliable transport; hence, in large, stable
184 networks it generates more traffic than protocols that only send
185 updates when the network topology changes. In such networks,
186 protocols such as OSPF [<a href="#ref-OSPF" title="&quot;OSPF Version 2&quot;">OSPF</a>], IS-IS [<a href="#ref-IS-IS" title="&quot;Information technology -- Telecommunications and information exchange between systems -- Intermediate System to Intermediate System intra-domain routeing information exchange protocol for use in conjunction with the protocol for providing the connectionless-mode network service (ISO 8473)&quot;">IS-IS</a>], or the Enhanced
187 Interior Gateway Routing Protocol (EIGRP) [<a href="#ref-EIGRP" title="&quot;EIGRP -- a Fast Routing Protocol Based on Distance Vectors&quot;">EIGRP</a>] might be more
188 suitable.
189
190 Second, Babel does impose a hold time when a prefix is retracted
191 (<a href="#section-3.5.5">Section 3.5.5</a>). While this hold time does not apply to the exact
192 prefix being retracted, and hence does not prevent fast reconvergence
193 should it become available again, it does apply to any shorter prefix
194 that covers it. Hence, if a previously deaggregated prefix becomes
195 aggregated, it will be unreachable for a few minutes. This makes
196 Babel unsuitable for use in mobile networks that implement automatic
197 prefix aggregation.
198
199 <span class="h3"><a class="selflink" id="section-1.3" href="#section-1.3">1.3</a>. Specification of Requirements</span>
200
201 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
202 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
203 document are to be interpreted as described in [<a href="./rfc2119" title="&quot;Key words for use in RFCs to Indicate Requirement Levels&quot;">RFC2119</a>].
204
205 <span class="h2"><a class="selflink" id="section-2" href="#section-2">2</a>. Conceptual Description of the Protocol</span>
206
207 Babel is a mostly loop-free distance vector protocol: it is based on
208 the Bellman-Ford protocol, just like the venerable RIP [<a href="#ref-RIP" title="&quot;RIP Version 2&quot;">RIP</a>], but
209 includes a number of refinements that either prevent loop formation
210 altogether, or ensure that a loop disappears in a timely manner and
211 doesn't form again.
212
213 Conceptually, Bellman-Ford is executed in parallel for every source
214 of routing information (destination of data traffic). In the
215 following discussion, we fix a source S; the reader will recall that
216 the same algorithm is executed for all sources.
217
218
219
220 <span class="grey">Chroboczek Experimental [Page 4]</span></pre>
221 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span>
222 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
223
224
225 <span class="h3"><a class="selflink" id="section-2.1" href="#section-2.1">2.1</a>. Costs, Metrics, and Neighbourship</span>
226
227 As many routing algorithms, Babel computes costs of links between any
228 two neighbouring nodes, abstract values attached to the edges between
229 two nodes. We write C(A, B) for the cost of the edge from node A to
230 node B.
231
232 Given a route between any two nodes, the metric of the route is the
233 sum of the costs of all the edges along the route. The goal of the
234 routing algorithm is to compute, for every source S, the tree of the
235 routes of lowest metric to S.
236
237 Costs and metrics need not be integers. In general, they can be
238 values in any algebra that satisfies two fairly general conditions
239 (<a href="#section-3.5.2">Section 3.5.2</a>).
240
241 A Babel node periodically broadcasts Hello messages to all of its
242 neighbours; it also periodically sends an IHU ("I Heard You") message
243 to every neighbour from which it has recently heard a Hello. From
244 the information derived from Hello and IHU messages received from its
245 neighbour B, a node A computes the cost C(A, B) of the link from A to
246 B.
247
248 <span class="h3"><a class="selflink" id="section-2.2" href="#section-2.2">2.2</a>. The Bellman-Ford Algorithm</span>
249
250 Every node A maintains two pieces of data: its estimated distance to
251 S, written D(A), and its next-hop router to S, written NH(A).
252 Initially, D(S) = 0, D(A) is infinite, and NH(A) is undefined.
253
254 Periodically, every node B sends to all of its neighbours a route
255 update, a message containing D(B). When a neighbour A of B receives
256 the route update, it checks whether B is its selected next hop; if
257 that is the case, then NH(A) is set to B, and D(A) is set to C(A, B)
258 + D(B). If that is not the case, then A compares C(A, B) + D(B) to
259 its current value of D(A). If that value is smaller, meaning that
260 the received update advertises a route that is better than the
261 currently selected route, then NH(A) is set to B, and D(A) is set to
262 C(A, B) + D(B).
263
264 A number of refinements to this algorithm are possible, and are used
265 by Babel. In particular, convergence speed may be increased by
266 sending unscheduled "triggered updates" whenever a major change in
267 the topology is detected, in addition to the regular, scheduled
268 updates. Additionally, a node may maintain a number of alternate
269 routes, which are being advertised by neighbours other than its
270 selected neighbour, and which can be used immediately if the selected
271 route were to fail.
272
273
274
275
276 <span class="grey">Chroboczek Experimental [Page 5]</span></pre>
277 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span>
278 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
279
280
281 <span class="h3"><a class="selflink" id="section-2.3" href="#section-2.3">2.3</a>. Transient Loops in Bellman-Ford</span>
282
283 It is well known that a naive application of Bellman-Ford to
284 distributed routing can cause transient loops after a topology
285 change. Consider for example the following diagram:
286
287 B
288 1 /|
289 1 / |
290 S --- A |1
291 \ |
292 1 \|
293 C
294
295 After convergence, D(B) = D(C) = 2, with NH(B) = NH(C) = A.
296
297 Suppose now that the link between S and A fails:
298
299 B
300 1 /|
301 / |
302 S A |1
303 \ |
304 1 \|
305 C
306
307 When it detects the failure of the link, A switches its next hop to B
308 (which is still advertising a route to S with metric 2), and
309 advertises a metric equal to 3, and then advertises a new route with
310 metric 3. This process of nodes changing selected neighbours and
311 increasing their metric continues until the advertised metric reaches
312 "infinity", a value larger than all the metrics that the routing
313 protocol is able to carry.
314
315 <span class="h3"><a class="selflink" id="section-2.4" href="#section-2.4">2.4</a>. Feasibility Conditions</span>
316
317 Bellman-Ford is a very robust algorithm: its convergence properties
318 are preserved when routers delay route acquisition or when they
319 discard some updates. Babel routers discard received route
320 announcements unless they can prove that accepting them cannot
321 possibly cause a routing loop.
322
323 More formally, we define a condition over route announcements, known
324 as the feasibility condition, that guarantees the absence of routing
325 loops whenever all routers ignore route updates that do not satisfy
326 the feasibility condition. In effect, this makes Bellman-Ford into a
327 family of routing algorithms, parameterised by the feasibility
328 condition.
329
330
331
332 <span class="grey">Chroboczek Experimental [Page 6]</span></pre>
333 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span>
334 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
335
336
337 Many different feasibility conditions are possible. For example, BGP
338 can be modelled as being a distance-vector protocol with a (rather
339 drastic) feasibility condition: a routing update is only accepted
340 when the receiving node's AS number is not included in the update's
341 AS-Path attribute (note that BGP's feasibility condition does not
342 ensure the absence of transitory "micro-loops" during reconvergence).
343
344 Another simple feasibility condition, used in Destination-Sequenced
345 Distance-Vector (DSDV) routing [<a href="#ref-DSDV" title="&quot;Highly Dynamic Destination- Sequenced Distance-Vector Routing (DSDV) for Mobile Computers&quot;">DSDV</a>] and in Ad hoc On-Demand
346 Distance Vector (AODV) routing, stems from the following observation:
347 a routing loop can only arise after a router has switched to a route
348 with a larger metric than the route that it had previously selected.
349 Hence, one could decide that a route is feasible only when its metric
350 at the local node would be no larger than the metric of the currently
351 selected route, i.e., an announcement carrying a metric D(B) is
352 accepted by A when C(A, B) + D(B) &lt;= D(A). If all routers obey this
353 constraint, then the metric at every router is nonincreasing, and the
354 following invariant is always preserved: if A has selected B as its
355 successor, then D(B) &lt; D(A), which implies that the forwarding graph
356 is loop-free.
357
358 Babel uses a slightly more refined feasibility condition, used in
359 EIGRP [<a href="#ref-DUAL" title="&quot;Loop-Free Routing Using Diffusing Computations&quot;">DUAL</a>]. Given a router A, define the feasibility distance of
360 A, written FD(A), as the smallest metric that A has ever advertised
361 for S to any of its neighbours. An update sent by a neighbour B of A
362 is feasible when the metric D(B) advertised by B is strictly smaller
363 than A's feasibility distance, i.e., when D(B) &lt; FD(A).
364
365 It is easy to see that this latter condition is no more restrictive
366 than DSDV-feasibility. Suppose that node A obeys DSDV-feasibility;
367 then D(A) is nonincreasing, hence at all times D(A) &lt;= FD(A).
368 Suppose now that A receives a DSDV-feasible update that advertises a
369 metric D(B). Since the update is DSDV-feasible, C(A, B) + D(B) &lt;=
370 D(A), hence D(B) &lt; D(A), and since D(A) &lt;= FD(A), D(B) &lt; FD(A).
371
372 To see that it is strictly less restrictive, consider the following
373 diagram, where A has selected the route through B, and D(A) = FD(A) =
374 2. Since D(C) = 1 &lt; FD(A), the alternate route through C is feasible
375 for A, although its metric C(A, C) + D(C) = 5 is larger than that of
376 the currently selected route:
377
378 B
379 1 / \ 1
380 / \
381 S A
382 \ /
383 1 \ / 4
384 C
385
386
387
388 <span class="grey">Chroboczek Experimental [Page 7]</span></pre>
389 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-8" ></span>
390 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
391
392
393 To show that this feasibility condition still guarantees loop-
394 freedom, recall that at the time when A accepts an update from B, the
395 metric D(B) announced by B is no smaller than FD(B); since it is
396 smaller than FD(A), at that point in time FD(B) &lt; FD(A). Since this
397 property is preserved when A sends updates, it remains true at all
398 times, which ensures that the forwarding graph has no loops.
399
400 <span class="h3"><a class="selflink" id="section-2.5" href="#section-2.5">2.5</a>. Solving Starvation: Sequencing Routes</span>
401
402 Obviously, the feasibility conditions defined above cause starvation
403 when a router runs out of feasible routes. Consider the following
404 diagram, where both A and B have selected the direct route to S:
405
406 A
407 1 /| D(A) = 1
408 / | FD(A) = 1
409 S |1
410 \ | D(B) = 2
411 2 \| FD(B) = 2
412 B
413
414 Suppose now that the link between A and S breaks:
415
416 A
417 |
418 | FD(A) = 1
419 S |1
420 \ | D(B) = 2
421 2 \| FD(B) = 2
422 B
423
424 The only route available from A to S, the one that goes through B, is
425 not feasible: A suffers from a spurious starvation.
426
427 At this point, the whole network must be rebooted in order to solve
428 the starvation; this is essentially what EIGRP does when it performs
429 a global synchronisation of all the routers in the network with the
430 source (the "active" phase of EIGRP).
431
432 Babel reacts to starvation in a less drastic manner, by using
433 sequenced routes, a technique introduced by DSDV and adopted by AODV.
434 In addition to a metric, every route carries a sequence number, a
435 nondecreasing integer that is propagated unchanged through the
436 network and is only ever incremented by the source; a pair (s, m),
437 where s is a sequence number and m a metric, is called a distance.
438
439 A received update is feasible when either it is more recent than the
440 feasibility distance maintained by the receiving node, or it is
441
442
443
444 <span class="grey">Chroboczek Experimental [Page 8]</span></pre>
445 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-9" ></span>
446 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
447
448
449 equally recent and the metric is strictly smaller. More formally, if
450 FD(A) = (s, m), then an update carrying the distance (s', m') is
451 feasible when either s' &gt; s, or s = s' and m' &lt; m.
452
453 Assuming the sequence number of S is 137, the diagram above becomes:
454
455 A
456 |
457 | FD(A) = (137, 1)
458 S |1
459 \ | D(B) = (137, 2)
460 2 \| FD(B) = (137, 2)
461 B
462
463 After S increases its sequence number, and the new sequence number is
464 propagated to B, we have:
465
466 A
467 |
468 | FD(A) = (137, 1)
469 S |1
470 \ | D(B) = (138, 2)
471 2 \| FD(B) = (138, 2)
472 B
473
474 at which point the route through B becomes feasible again.
475
476 Note that while sequence numbers are used for determining
477 feasibility, they are not necessarily used in route selection: a node
478 will normally ignore the sequence number when selecting a route
479 (<a href="#section-3.6">Section 3.6</a>).
480
481 <span class="h3"><a class="selflink" id="section-2.6" href="#section-2.6">2.6</a>. Requests</span>
482
483 In DSDV, the sequence number of a source is increased periodically.
484 A route becomes feasible again after the source increases its
485 sequence number, and the new sequence number is propagated through
486 the network, which may, in general, require a significant amount of
487 time.
488
489 Babel takes a different approach. When a node detects that it is
490 suffering from a potentially spurious starvation, it sends an
491 explicit request to the source for a new sequence number. This
492 request is forwarded hop by hop to the source, with no regard to the
493 feasibility condition. Upon receiving the request, the source
494 increases its sequence number and broadcasts an update, which is
495 forwarded to the requesting node.
496
497
498
499
500 <span class="grey">Chroboczek Experimental [Page 9]</span></pre>
501 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-10" ></span>
502 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
503
504
505 Note that after a change in network topology not all such requests
506 will, in general, reach the source, as some will be sent over links
507 that are now broken. However, if the network is still connected,
508 then at least one among the nodes suffering from spurious starvation
509 has an (unfeasible) route to the source; hence, in the absence of
510 packet loss, at least one such request will reach the source.
511 (Resending requests a small number of times compensates for packet
512 loss.)
513
514 Since requests are forwarded with no regard to the feasibility
515 condition, they may, in general, be caught in a forwarding loop; this
516 is avoided by having nodes perform duplicate detection for the
517 requests that they forward.
518
519 <span class="h3"><a class="selflink" id="section-2.7" href="#section-2.7">2.7</a>. Multiple Routers</span>
520
521 The above discussion assumes that every prefix is originated by a
522 single router. In real networks, however, it is often necessary to
523 have a single prefix originated by multiple routers; for example, the
524 default route will be originated by all of the edge routers of a
525 routing domain.
526
527 Since synchronising sequence numbers between distinct routers is
528 problematic, Babel treats routes for the same prefix as distinct
529 entities when they are originated by different routers: every route
530 announcement carries the router-id of its originating router, and
531 feasibility distances are not maintained per prefix, but per source,
532 where a source is a pair of a router-id and a prefix. In effect,
533 Babel guarantees loop-freedom for the forwarding graph to every
534 source; since the union of multiple acyclic graphs is not in general
535 acyclic, Babel does not in general guarantee loop-freedom when a
536 prefix is originated by multiple routers, but any loops will be
537 broken in a time at most proportional to the diameter of the loop --
538 as soon as an update has "gone around" the routing loop.
539
540 Consider for example the following diagram, where A has selected the
541 default route through S, and B has selected the one through S':
542
543 1 1 1
544 ::/0 -- S --- A --- B --- S' -- ::/0
545
546 Suppose that both default routes fail at the same time; then nothing
547 prevents A from switching to B, and B simultaneously switching to A.
548 However, as soon as A has successfully advertised the new route to B,
549 the route through A will become unfeasible for B. Conversely, as
550 soon as B will have advertised the route through A, the route through
551 B will become unfeasible for A.
552
553
554
555
556 <span class="grey">Chroboczek Experimental [Page 10]</span></pre>
557 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-11" ></span>
558 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
559
560
561 In effect, the routing loop disappears at the latest when routing
562 information has gone around the loop. Since this process can be
563 delayed by lost packets, Babel makes certain efforts to ensure that
564 updates are sent reliably after a router-id change.
565
566 Additionally, after the routers have advertised the two routes, both
567 sources will be in their source tables, which will prevent them from
568 ever again participating in a routing loop involving routes from S
569 and S' (up to the source GC time, which, available memory permitting,
570 can be set to arbitrarily large values).
571
572 <span class="h3"><a class="selflink" id="section-2.8" href="#section-2.8">2.8</a>. Overlapping Prefixes</span>
573
574 In the above discussion, we have assumed that all prefixes are
575 disjoint, as is the case in flat ("mesh") routing. In practice,
576 however, prefixes may overlap: for example, the default route
577 overlaps with all of the routes present in the network.
578
579 After a route fails, it is not correct in general to switch to a
580 route that subsumes the failed route. Consider for example the
581 following configuration:
582
583 1 1
584 ::/0 -- A --- B --- C
585
586 Suppose that node C fails. If B forwards packets destined to C by
587 following the default route, a routing loop will form, and persist
588 until A learns of B's retraction of the direct route to C. Babel
589 avoids this pitfall by maintaining an "unreachable" route for a few
590 minutes after a route is retracted; the time for which such a route
591 must be maintained should be the worst-case propagation time of the
592 retraction of the route to C.
593
594 <span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a>. Protocol Operation</span>
595
596 Every Babel speaker is assigned a router-id, which is an arbitrary
597 string of 8 octets that is assumed unique across the routing domain.
598 We suggest that router-ids should be assigned in modified EUI-64
599 format [<a href="#ref-ADDRARCH" title="&quot;IP Version 6 Addressing Architecture&quot;">ADDRARCH</a>]. (As a matter of fact, the protocol encoding is
600 slightly more compact when router-ids are assigned in the same manner
601 as the IPv6 layer assigns host IDs.)
602
603 <span class="h3"><a class="selflink" id="section-3.1" href="#section-3.1">3.1</a>. Message Transmission and Reception</span>
604
605 Babel protocol packets are sent in the body of a UDP datagram. Each
606 Babel packet consists of one or more TLVs.
607
608
609
610
611
612 <span class="grey">Chroboczek Experimental [Page 11]</span></pre>
613 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-12" ></span>
614 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
615
616
617 The source address of a Babel packet is always a unicast address,
618 link-local in the case of IPv6. Babel packets may be sent to a well-
619 known (link-local) multicast address (this is the usual case) or to a
620 (link-local) unicast address. In normal operation, a Babel speaker
621 sends both multicast and unicast packets to its neighbours.
622
623 With the exception of Hello TLVs and acknowledgements, all Babel TLVs
624 can be sent to either unicast or multicast addresses, and their
625 semantics does not depend on whether the destination was a unicast or
626 multicast address. Hence, a Babel speaker does not need to determine
627 the destination address of a packet that it receives in order to
628 interpret it.
629
630 A moderate amount of jitter is applied to packets sent by a Babel
631 speaker: outgoing TLVs are buffered and SHOULD be sent with a small
632 random delay. This is done for two purposes: it avoids
633 synchronisation of multiple Babel speakers across a network [<a href="#ref-JITTER" title="&quot;The synchronization of periodic routing messages&quot;">JITTER</a>],
634 and it allows for the aggregation of multiple TLVs into a single
635 packet.
636
637 The exact delay and amount of jitter applied to a packet depends on
638 whether it contains any urgent TLVs. Acknowledgement TLVs MUST be
639 sent before the deadline specified in the corresponding request. The
640 particular class of updates specified in <a href="#section-3.7.2">Section 3.7.2</a> MUST be sent
641 in a timely manner. The particular class of request and update TLVs
642 specified in <a href="#section-3.8.2">Section 3.8.2</a> SHOULD be sent in a timely manner.
643
644 <span class="h3"><a class="selflink" id="section-3.2" href="#section-3.2">3.2</a>. Data Structures</span>
645
646 Every Babel speaker maintains a number of data structures.
647
648 <span class="h4"><a class="selflink" id="section-3.2.1" href="#section-3.2.1">3.2.1</a>. Sequence Number</span>
649
650 A node's sequence number is a 16-bit integer that is included in
651 route updates sent for routes originated by this node. A node
652 increments its sequence number (modulo 2^16) whenever it receives a
653 request for a new sequence number (<a href="#section-3.8.1.2">Section 3.8.1.2</a>).
654
655 A node SHOULD NOT increment its sequence number (seqno)
656 spontaneously, since increasing seqnos makes it less likely that
657 other nodes will have feasible alternate routes when their selected
658 routes fail.
659
660 <span class="h4"><a class="selflink" id="section-3.2.2" href="#section-3.2.2">3.2.2</a>. The Interface Table</span>
661
662 The interface table contains the list of interfaces on which the node
663 speaks the Babel protocol. Every interface table entry contains the
664 interface's Hello seqno, a 16-bit integer that is sent with each
665
666
667
668 <span class="grey">Chroboczek Experimental [Page 12]</span></pre>
669 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-13" ></span>
670 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
671
672
673 Hello TLV on this interface and is incremented (modulo 2^16) whenever
674 a Hello is sent. (Note that an interface's Hello seqno is unrelated
675 to the node's seqno.)
676
677 There are two timers associated with each interface table entry --
678 the Hello timer, which governs the sending of periodic Hello and IHU
679 packets, and the update timer, which governs the sending of periodic
680 route updates.
681
682 <span class="h4"><a class="selflink" id="section-3.2.3" href="#section-3.2.3">3.2.3</a>. The Neighbour Table</span>
683
684 The neighbour table contains the list of all neighbouring interfaces
685 from which a Babel packet has been recently received. The neighbour
686 table is indexed by pairs of the form (interface, address), and every
687 neighbour table entry contains the following data:
688
689 o the local node's interface over which this neighbour is reachable;
690
691 o the address of the neighbouring interface;
692
693 o a history of recently received Hello packets from this neighbour;
694 this can, for example, be a sequence of n bits, for some small
695 value n, indicating which of the n hellos most recently sent by
696 this neighbour have been received by the local node;
697
698 o the "transmission cost" value from the last IHU packet received
699 from this neighbour, or FFFF hexadecimal (infinity) if the IHU
700 hold timer for this neighbour has expired;
701
702 o the neighbour's expected Hello sequence number, an integer modulo
703 2^16.
704
705 There are two timers associated with each neighbour entry -- the
706 hello timer, which is initialised from the interval value carried by
707 Hello TLVs, and the IHU timer, which is initialised to a small
708 multiple of the interval carried in IHU TLVs.
709
710 Note that the neighbour table is indexed by IP addresses, not by
711 router-ids: neighbourship is a relationship between interfaces, not
712 between nodes. Therefore, two nodes with multiple interfaces can
713 participate in multiple neighbourship relationships, a fairly common
714 situation when wireless nodes with multiple radios are involved.
715
716 <span class="h4"><a class="selflink" id="section-3.2.4" href="#section-3.2.4">3.2.4</a>. The Source Table</span>
717
718 The source table is used to record feasibility distances. It is
719 indexed by triples of the form (prefix, plen, router-id), and every
720 source table entry contains the following data:
721
722
723
724 <span class="grey">Chroboczek Experimental [Page 13]</span></pre>
725 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-14" ></span>
726 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
727
728
729 o the prefix (prefix, plen), where plen is the prefix length, that
730 this entry applies to;
731
732 o the router-id of a router originating this prefix;
733
734 o a pair (seqno, metric), this source's feasibility distance.
735
736 There is one timer associated with each entry in the source table --
737 the source garbage-collection timer. It is initialised to a time on
738 the order of minutes and reset as specified in <a href="#section-3.7.3">Section 3.7.3</a>.
739
740 <span class="h4"><a class="selflink" id="section-3.2.5" href="#section-3.2.5">3.2.5</a>. The Route Table</span>
741
742 The route table contains the routes known to this node. It is
743 indexed by triples of the form (prefix, plen, neighbour), and every
744 route table entry contains the following data:
745
746 o the source (prefix, plen, router-id) for which this route is
747 advertised;
748
749 o the neighbour that advertised this route;
750
751 o the metric with which this route was advertised by the neighbour,
752 or FFFF hexadecimal (infinity) for a recently retracted route;
753
754 o the sequence number with which this route was advertised;
755
756 o the next-hop address of this route;
757
758 o a boolean flag indicating whether this route is selected, i.e.,
759 whether it is currently being used for forwarding and is being
760 advertised.
761
762 There is one timer associated with each route table entry -- the
763 route expiry timer. It is initialised and reset as specified in
764 <a href="#section-3.5.4">Section 3.5.4</a>.
765
766 <span class="h4"><a class="selflink" id="section-3.2.6" href="#section-3.2.6">3.2.6</a>. The Table of Pending Requests</span>
767
768 The table of pending requests contains a list of seqno requests that
769 the local node has sent (either because they have been originated
770 locally, or because they were forwarded) and to which no reply has
771 been received yet. This table is indexed by prefixes, and every
772 entry in this table contains the following data:
773
774 o the prefix, router-id, and seqno being requested;
775
776
777
778
779
780 <span class="grey">Chroboczek Experimental [Page 14]</span></pre>
781 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-15" ></span>
782 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
783
784
785 o the neighbour, if any, on behalf of which we are forwarding this
786 request;
787
788 o a small integer indicating the number of times that this request
789 will be resent if it remains unsatisfied.
790
791 There is one timer associated with each pending request; it governs
792 both the resending of requests and their expiry.
793
794 <span class="h3"><a class="selflink" id="section-3.3" href="#section-3.3">3.3</a>. Acknowledged Packets</span>
795
796 A Babel speaker may request that any neighbour receiving a given
797 packet reply with an explicit acknowledgement within a given time.
798 While the use of acknowledgement requests is optional, every Babel
799 speaker MUST be able to reply to such a request.
800
801 An acknowledgement MUST be sent to a unicast destination. On the
802 other hand, acknowledgement requests may be sent to either unicast or
803 multicast destinations, in which case they request an acknowledgement
804 from all of the receiving nodes.
805
806 When to request acknowledgements is a matter of local policy; the
807 simplest strategy is to never request acknowledgements and to rely on
808 periodic updates to ensure that any reachable routes are eventually
809 propagated throughout the routing domain. For increased efficiency,
810 we suggest that acknowledged packets should be used in order to send
811 urgent updates (<a href="#section-3.7.2">Section 3.7.2</a>) when the number of neighbours on a
812 given interface is small. Since Babel is designed to deal gracefully
813 with packet loss on unreliable media, sending all packets with
814 acknowledgement requests is not necessary, and not even recommended,
815 as the acknowledgements cause additional traffic and may force
816 additional Address Resolution Protocol (ARP) or Neighbour Discovery
817 exchanges.
818
819 <span class="h3"><a class="selflink" id="section-3.4" href="#section-3.4">3.4</a>. Neighbour Acquisition</span>
820
821 Neighbour acquisition is the process by which a Babel node discovers
822 the set of neighbours heard over each of its interfaces and
823 ascertains bidirectional reachability. On unreliable media,
824 neighbour acquisition additionally provides some statistics that MAY
825 be used in link quality computation.
826
827 <span class="h4"><a class="selflink" id="section-3.4.1" href="#section-3.4.1">3.4.1</a>. Reverse Reachability Detection</span>
828
829 Every Babel node sends periodic Hellos over each of its interfaces.
830 Each Hello TLV carries an increasing (modulo 2^16) sequence number
831 and the interval between successive periodic packets sent on this
832 particular interface.
833
834
835
836 <span class="grey">Chroboczek Experimental [Page 15]</span></pre>
837 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-16" ></span>
838 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
839
840
841 In addition to the periodic Hello packets, a node MAY send
842 unscheduled Hello packets, e.g., to accelerate link cost estimation
843 when a new neighbour is discovered, or when link conditions have
844 suddenly changed.
845
846 A node MAY change its Hello interval. The Hello interval MAY be
847 decreased at any time; it SHOULD NOT be increased, except immediately
848 before sending a Hello packet. (Equivalently, a node SHOULD send an
849 unscheduled Hello immediately after increasing its Hello interval.)
850
851 How to deal with received Hello TLVs and what statistics to maintain
852 are considered local implementation matters; typically, a node will
853 maintain some sort of history of recently received Hellos. A
854 possible algorithm is described in <a href="#appendix-A.1">Appendix A.1</a>.
855
856 After receiving a Hello, or determining that it has missed one, the
857 node recomputes the association's cost (<a href="#section-3.4.3">Section 3.4.3</a>) and runs the
858 route selection procedure (<a href="#section-3.6">Section 3.6</a>).
859
860 <span class="h4"><a class="selflink" id="section-3.4.2" href="#section-3.4.2">3.4.2</a>. Bidirectional Reachability Detection</span>
861
862 In order to establish bidirectional reachability, every node sends
863 periodic IHU ("I Heard You") TLVs to each of its neighbours. Since
864 IHUs carry an explicit interval value, they MAY be sent less often
865 than Hellos in order to reduce the amount of routing traffic in dense
866 networks; in particular, they SHOULD be sent less often than Hellos
867 over links with little packet loss. While IHUs are conceptually
868 unicast, they SHOULD be sent to a multicast address in order to avoid
869 an ARP or Neighbour Discovery exchange and to aggregate multiple IHUs
870 in a single packet.
871
872 In addition to the periodic IHUs, a node MAY, at any time, send an
873 unscheduled IHU packet. It MAY also, at any time, decrease its IHU
874 interval, and it MAY increase its IHU interval immediately before
875 sending an IHU.
876
877 Every IHU TLV contains two pieces of data: the link's rxcost
878 (reception cost) from the sender's perspective, used by the neighbour
879 for computing link costs (<a href="#section-3.4.3">Section 3.4.3</a>), and the interval between
880 periodic IHU packets. A node receiving an IHU updates the value of
881 the sending neighbour's txcost (transmission cost), from its
882 perspective, to the value contained in the IHU, and resets this
883 neighbour's IHU timer to a small multiple of the value received in
884 the IHU.
885
886 When a neighbour's IHU timer expires, its txcost is set to infinity.
887
888
889
890
891
892 <span class="grey">Chroboczek Experimental [Page 16]</span></pre>
893 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-17" ></span>
894 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
895
896
897 After updating a neighbour's txcost, the receiving node recomputes
898 the neighbour's cost (<a href="#section-3.4.3">Section 3.4.3</a>) and runs the route selection
899 procedure (<a href="#section-3.6">Section 3.6</a>).
900
901 <span class="h4"><a class="selflink" id="section-3.4.3" href="#section-3.4.3">3.4.3</a>. Cost Computation</span>
902
903 A neighbourship association's link cost is computed from the values
904 maintained in the neighbour table -- namely, the statistics kept in
905 the neighbour table about the reception of Hellos, and the txcost
906 computed from received IHU packets.
907
908 For every neighbour, a Babel node computes a value known as this
909 neighbour's rxcost. This value is usually derived from the Hello
910 history, which may be combined with other data, such as statistics
911 maintained by the link layer. The rxcost is sent to a neighbour in
912 each IHU.
913
914 How the txcost and rxcost are combined in order to compute a link's
915 cost is a matter of local policy; as far as Babel's correctness is
916 concerned, only the following conditions MUST be satisfied:
917
918 o the cost is strictly positive;
919
920 o if no hellos were received recently, then the cost is infinite;
921
922 o if the txcost is infinite, then the cost is infinite.
923
924 Note that while this document does not constrain cost computation any
925 further, not all cost computation strategies will give good results.
926 We give a few examples of strategies for computing a link's cost that
927 are known to work well in practice in <a href="#appendix-A.2">Appendix A.2</a>.
928
929 <span class="h3"><a class="selflink" id="section-3.5" href="#section-3.5">3.5</a>. Routing Table Maintenance</span>
930
931 Conceptually, a Babel update is a quintuple (prefix, plen, router-id,
932 seqno, metric), where (prefix, plen) is the prefix for which a route
933 is being advertised, router-id is the router-id of the router
934 originating this update, seqno is a nondecreasing (modulo 2^16)
935 integer that carries the originating router seqno, and metric is the
936 announced metric.
937
938 Before being accepted, an update is checked against the feasibility
939 condition (<a href="#section-3.5.1">Section 3.5.1</a>), which ensures that the route does not
940 create a routing loop. If the feasibility condition is not
941 satisfied, the update is either ignored or treated as a retraction,
942 depending on some other conditions (<a href="#section-3.5.4">Section 3.5.4</a>). If the
943 feasibility condition is satisfied, then the update cannot possibly
944 cause a routing loop, and the update is accepted.
945
946
947
948 <span class="grey">Chroboczek Experimental [Page 17]</span></pre>
949 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-18" ></span>
950 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
951
952
953 <span class="h4"><a class="selflink" id="section-3.5.1" href="#section-3.5.1">3.5.1</a>. The Feasibility Condition</span>
954
955 The feasibility condition is applied to all received updates. The
956 feasibility condition compares the metric in the received update with
957 the metrics of the updates previously sent by the receiving node;
958 updates with finite metrics large enough to cause a loop are
959 discarded.
960
961 A feasibility distance is a pair (seqno, metric), where seqno is an
962 integer modulo 2^16 and metric is a positive integer. Feasibility
963 distances are compared lexicographically, with the first component
964 inverted: we say that a distance (seqno, metric) is strictly better
965 than a distance (seqno', metric'), written
966
967 (seqno, metric) &lt; (seqno', metric')
968
969 when
970
971 seqno &gt; seqno' or (seqno = seqno' and metric &lt; metric')
972
973 where sequence numbers are compared modulo 2^16.
974
975 Given a source (p, plen, id), a node's feasibility distance for this
976 source is the minimum, according to the ordering defined above, of
977 the distances of all the finite updates ever sent by this particular
978 node for the prefix (p, plen) carrying the router-id id. Feasibility
979 distances are maintained in the source table; the exact procedure is
980 given in <a href="#section-3.7.3">Section 3.7.3</a>.
981
982 A received update is feasible when either it is a retraction (its
983 metric is FFFF hexadecimal), or the advertised distance is strictly
984 better, in the sense defined above, than the feasibility distance for
985 the corresponding source. More precisely, a route advertisement
986 carrying the quintuple (prefix, plen, router-id, seqno, metric) is
987 feasible if one of the following conditions holds:
988
989 o metric is infinite; or
990
991 o no entry exists in the source table indexed by (id, prefix, plen);
992 or
993
994 o an entry (prefix, plen, router-id, seqno', metric') exists in the
995 source table, and either
996
997 * seqno' &lt; seqno or
998
999 * seqno = seqno' and metric &lt; metric'.
1000
1001
1002
1003
1004 <span class="grey">Chroboczek Experimental [Page 18]</span></pre>
1005 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-19" ></span>
1006 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1007
1008
1009 Note that the feasibility condition considers the metric advertised
1010 by the neighbour, not the route's metric; hence, a fluctuation in a
1011 neighbour's cost cannot render a selected route unfeasible.
1012
1013 <span class="h4"><a class="selflink" id="section-3.5.2" href="#section-3.5.2">3.5.2</a>. Metric Computation</span>
1014
1015 A route's metric is computed from the metric advertised by the
1016 neighbour and the neighbour's link cost. Just like cost computation,
1017 metric computation is considered a local policy matter; as far as
1018 Babel is concerned, the function M(c, m) used for computing a metric
1019 from a locally computed link cost and the metric advertised by a
1020 neighbour MUST only satisfy the following conditions:
1021
1022 o if c is infinite, then M(c, m) is infinite;
1023
1024 o M is strictly monotonic: M(c, m) &gt; m.
1025
1026 Additionally, the metric SHOULD satisfy the following condition:
1027
1028 o M is isotonic: if m &lt;= m', then M(c, m) &lt;= M(c, m').
1029
1030 Note that while strict monotonicity is essential to the integrity of
1031 the network (persistent routing loops may appear if it is not
1032 satisfied), isotonicity is not: if it is not satisfied, Babel will
1033 still converge to a locally optimal routing table, but might not
1034 reach a global optimum (in fact, such a global optimum may not even
1035 exist).
1036
1037 As with cost computation, not all strategies for computing route
1038 metrics will give good results. In particular, some metrics are more
1039 likely than others to lead to routing instabilities (route flapping).
1040 In <a href="#appendix-A.3">Appendix A.3</a>, we give a number of examples of strictly monotonic,
1041 isotonic routing metrics that are known to work well in practice.
1042
1043 <span class="h4"><a class="selflink" id="section-3.5.3" href="#section-3.5.3">3.5.3</a>. Encoding of Updates</span>
1044
1045 In a large network, the bulk of Babel traffic consists of route
1046 updates; hence, some care has been given to encoding them
1047 efficiently. An Update TLV itself only contains the prefix, seqno,
1048 and metric, while the next hop is derived either from the network-
1049 layer source address of the packet or from an explicit Next Hop TLV
1050 in the same packet. The router-id is derived from a separate
1051 Router-Id TLV in the same packet, which optimises the case when
1052 multiple updates are sent with the same router-id.
1053
1054 Additionally, a prefix of the advertised prefix can be omitted in an
1055 Update TLV, in which case it is copied from a previous Update TLV in
1056 the same packet -- this is known as address compression [<a href="#ref-PACKETBB" title="&quot;Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format&quot;">PACKETBB</a>].
1057
1058
1059
1060 <span class="grey">Chroboczek Experimental [Page 19]</span></pre>
1061 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-20" ></span>
1062 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1063
1064
1065 Finally, as a special optimisation for the case when a router-id
1066 coincides with the interface-id part of an IPv6 address, the
1067 router-id can optionally be derived from the low-order bits of the
1068 advertised prefix.
1069
1070 The encoding of updates is described in detail in <a href="#section-4.4">Section 4.4</a>.
1071
1072 <span class="h4"><a class="selflink" id="section-3.5.4" href="#section-3.5.4">3.5.4</a>. Route Acquisition</span>
1073
1074 When a Babel node receives an update (id, prefix, seqno, metric) from
1075 a neighbour neigh with a link cost value equal to cost, it checks
1076 whether it already has a routing table entry indexed by (neigh, id,
1077 prefix).
1078
1079 If no such entry exists:
1080
1081 o if the update is unfeasible, it is ignored;
1082
1083 o if the metric is infinite (the update is a retraction), the update
1084 is ignored;
1085
1086 o otherwise, a new route table entry is created, indexed by (neigh,
1087 id, prefix), with seqno equal to seqno and an advertised metric
1088 equal to the metric carried by the update.
1089
1090 If such an entry exists:
1091
1092 o if the entry is currently installed and the update is unfeasible,
1093 then the behaviour depends on whether the router-ids of the two
1094 entries match. If the router-ids are different, the update is
1095 treated as though it were a retraction (i.e., as though the metric
1096 were FFFF hexadecimal). If the router-ids are equal, the update
1097 is ignored;
1098
1099 o otherwise (i.e., if either the update is feasible or the entry is
1100 not currently installed), then the entry's sequence number,
1101 advertised metric, metric, and router-id are updated and, unless
1102 the advertised metric is infinite, the route's expiry timer is
1103 reset to a small multiple of the Interval value included in the
1104 update.
1105
1106 When a route's expiry timer triggers, the behaviour depends on
1107 whether the route's metric is finite. If the metric is finite, it is
1108 set to infinity and the expiry timer is reset. If the metric is
1109 already infinite, the route is flushed from the route table.
1110
1111 After the routing table is updated, the route selection procedure
1112 (<a href="#section-3.6">Section 3.6</a>) is run.
1113
1114
1115
1116 <span class="grey">Chroboczek Experimental [Page 20]</span></pre>
1117 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-21" ></span>
1118 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1119
1120
1121 <span class="h4"><a class="selflink" id="section-3.5.5" href="#section-3.5.5">3.5.5</a>. Hold Time</span>
1122
1123 When a prefix p is retracted, because all routes are unfeasible, too
1124 old, or have an infinite metric, and a shorter prefix p' that covers
1125 p is reachable, p' cannot in general be used for routing packets
1126 destined to p without running the risk of creating a routing loop
1127 (<a href="#section-2.8">Section 2.8</a>).
1128
1129 To avoid this issue, whenever a prefix is retracted, a routing table
1130 entry with infinite metric is maintained as described in
1131 <a href="#section-3.5.4">Section 3.5.4</a> above, and packets destined for that prefix MUST NOT be
1132 forwarded by following a route for a shorter prefix. The infinite
1133 metric entry is maintained until it is superseded by a feasible
1134 update; if no such update arrives within the route hold time, the
1135 entry is flushed.
1136
1137 <span class="h3"><a class="selflink" id="section-3.6" href="#section-3.6">3.6</a>. Route Selection</span>
1138
1139 Route selection is the process by which a single route for a given
1140 prefix is selected to be used for forwarding packets and to be
1141 re-advertised to a node's neighbours.
1142
1143 Babel is designed to allow flexible route selection policies. As far
1144 as the protocol's correctness is concerned, the route selection
1145 policy MUST only satisfy the following properties:
1146
1147 o a route with infinite metric (a retracted route) is never
1148 selected;
1149
1150 o an unfeasible route is never selected.
1151
1152 Note, however, that Babel does not naturally guarantee the stability
1153 of routing, and configuring conflicting route selection policies on
1154 different routers may lead to persistent route oscillation.
1155
1156 Defining a good route selection policy for Babel is an open research
1157 problem. Route selection can take into account multiple mutually
1158 contradictory criteria; in roughly decreasing order of importance,
1159 these are:
1160
1161 o routes with a small metric should be preferred over routes with a
1162 large metric;
1163
1164 o switching router-ids should be avoided;
1165
1166 o routes through stable neighbours should be preferred over routes
1167 through unstable ones;
1168
1169
1170
1171
1172 <span class="grey">Chroboczek Experimental [Page 21]</span></pre>
1173 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-22" ></span>
1174 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1175
1176
1177 o stable routes should be preferred over unstable ones;
1178
1179 o switching next hops should be avoided.
1180
1181 A simple strategy is to choose the feasible route with the smallest
1182 metric, with a small amount of hysteresis applied to avoid switching
1183 router-ids.
1184
1185 After the route selection procedure is run, triggered updates
1186 (<a href="#section-3.7.2">Section 3.7.2</a>) and requests (<a href="#section-3.8.2">Section 3.8.2</a>) are sent.
1187
1188 <span class="h3"><a class="selflink" id="section-3.7" href="#section-3.7">3.7</a>. Sending Updates</span>
1189
1190 A Babel speaker advertises to its neighbours its set of selected
1191 routes. Normally, this is done by sending one or more multicast
1192 packets containing Update TLVs on all of its connected interfaces;
1193 however, on link technologies where multicast is significantly more
1194 expensive than unicast, a node MAY choose to send multiple copies of
1195 updates in unicast packets when the number of neighbours is small.
1196
1197 Additionally, in order to ensure that any black-holes are reliably
1198 cleared in a timely manner, a Babel node sends retractions (updates
1199 with an infinite metric) for any recently retracted prefixes.
1200
1201 If an update is for a route injected into the Babel domain by the
1202 local node (e.g., the address of a local interface, the prefix of a
1203 directly attached network, or redistributed from a different routing
1204 protocol), the router-id is set to the local id, the metric is set to
1205 some arbitrary finite value (typically 0), and the seqno is set to
1206 the local router's sequence number.
1207
1208 If an update is for a route learned from another Babel speaker, the
1209 router-id and sequence number are copied from the routing table
1210 entry, and the metric is computed as specified in <a href="#section-3.5.2">Section 3.5.2</a>.
1211
1212 <span class="h4"><a class="selflink" id="section-3.7.1" href="#section-3.7.1">3.7.1</a>. Periodic Updates</span>
1213
1214 Every Babel speaker periodically advertises all of its selected
1215 routes on all of its interfaces, including any recently retracted
1216 routes. Since Babel doesn't suffer from routing loops (there is no
1217 "counting to infinity") and relies heavily on triggered updates
1218 (<a href="#section-3.7.2">Section 3.7.2</a>), this full dump only needs to happen infrequently.
1219
1220 <span class="h4"><a class="selflink" id="section-3.7.2" href="#section-3.7.2">3.7.2</a>. Triggered Updates</span>
1221
1222 In addition to the periodic routing updates, a Babel speaker sends
1223 unscheduled, or triggered, updates in order to inform its neighbours
1224 of a significant change in the network topology.
1225
1226
1227
1228 <span class="grey">Chroboczek Experimental [Page 22]</span></pre>
1229 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-23" ></span>
1230 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1231
1232
1233 A change of router-id for the selected route to a given prefix may be
1234 indicative of a routing loop in formation; hence, a node MUST send a
1235 triggered update in a timely manner whenever it changes the selected
1236 router-id for a given destination. Additionally, it SHOULD make a
1237 reasonable attempt at ensuring that all neighbours receive this
1238 update.
1239
1240 There are two strategies for ensuring that. If the number of
1241 neighbours is small, then it is reasonable to send the update
1242 together with an acknowledgement request; the update is resent until
1243 all neighbours have acknowledged the packet, up to some number of
1244 times. If the number of neighbours is large, however, requesting
1245 acknowledgements from all of them might cause a non-negligible amount
1246 of network traffic; in that case, it may be preferable to simply
1247 repeat the update some reasonable number of times (say, 5 for
1248 wireless and 2 for wired links).
1249
1250 A route retraction is somewhat less worrying: if the route retraction
1251 doesn't reach all neighbours, a black-hole might be created, which,
1252 unlike a routing loop, does not endanger the integrity of the
1253 network. When a route is retracted, a node SHOULD send a triggered
1254 update and SHOULD make a reasonable attempt at ensuring that all
1255 neighbours receive this retraction.
1256
1257 Finally, a node MAY send a triggered update when the metric for a
1258 given prefix changes in a significant manner, either due to a
1259 received update or because a link cost has changed. A node SHOULD
1260 NOT send triggered updates for other reasons, such as when there is a
1261 minor fluctuation in a route's metric, when the selected next hop
1262 changes, or to propagate a new sequence number (except to satisfy a
1263 request, as specified in <a href="#section-3.8">Section 3.8</a>).
1264
1265 <span class="h4"><a class="selflink" id="section-3.7.3" href="#section-3.7.3">3.7.3</a>. Maintaining Feasibility Distances</span>
1266
1267 Before sending an update (prefix, plen, router-id, seqno, metric)
1268 with finite metric (i.e., not a route retraction), a Babel node
1269 updates the feasibility distance maintained in the source table.
1270 This is done as follows.
1271
1272 If no entry indexed by (prefix, plen, router-id) exists in the source
1273 table, then one is created with value (prefix, plen, router-id,
1274 seqno, metric).
1275
1276 If an entry (prefix, plen, router-id, seqno', metric') exists, then
1277 it is updated as follows:
1278
1279 o if seqno &gt; seqno', then seqno' := seqno, metric' := metric;
1280
1281
1282
1283
1284 <span class="grey">Chroboczek Experimental [Page 23]</span></pre>
1285 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-24" ></span>
1286 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1287
1288
1289 o if seqno = seqno' and metric' &gt; metric, then metric' := metric;
1290
1291 o otherwise, nothing needs to be done.
1292
1293 The garbage-collection timer for the modified entry is then reset.
1294 Note that the garbage-collection timer is not reset when a retraction
1295 is sent.
1296
1297 <span class="h4"><a class="selflink" id="section-3.7.4" href="#section-3.7.4">3.7.4</a>. Split Horizon</span>
1298
1299 When running over a transitive, symmetric link technology, e.g., a
1300 point-to-point link or a wired LAN technology such as Ethernet, a
1301 Babel node SHOULD use an optimisation known as split horizon. When
1302 split horizon is used on a given interface, a routing update is not
1303 sent on this particular interface when the advertised route was
1304 learnt from a neighbour over the same interface.
1305
1306 Split horizon SHOULD NOT be applied to an interface unless the
1307 interface is known to be symmetric and transitive; in particular,
1308 split horizon is not applicable to decentralised wireless link
1309 technologies (e.g., IEEE 802.11 in ad hoc mode).
1310
1311 <span class="h3"><a class="selflink" id="section-3.8" href="#section-3.8">3.8</a>. Explicit Route Requests</span>
1312
1313 In normal operation, a node's routing table is populated by the
1314 regular and triggered updates sent by its neighbours. Under some
1315 circumstances, however, a node sends explicit requests to cause a
1316 resynchronisation with the source after a mobility event or to
1317 prevent a route from spuriously expiring.
1318
1319 The Babel protocol provides two kinds of explicit requests: route
1320 requests, which simply request an update for a given prefix, and
1321 seqno requests, which request an update for a given prefix with a
1322 specific sequence number. The former are never forwarded; the latter
1323 are forwarded if they cannot be satisfied by a neighbour.
1324
1325 <span class="h4"><a class="selflink" id="section-3.8.1" href="#section-3.8.1">3.8.1</a>. Handling Requests</span>
1326
1327 Upon receiving a request, a node either forwards the request or sends
1328 an update in reply to the request, as described in the following
1329 sections. If this causes an update to be sent, the update is either
1330 sent to a multicast address on the interface on which the request was
1331 received, or to the unicast address of the neighbour that sent the
1332 update.
1333
1334 The exact behaviour is different for route requests and seqno
1335 requests.
1336
1337
1338
1339
1340 <span class="grey">Chroboczek Experimental [Page 24]</span></pre>
1341 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-25" ></span>
1342 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1343
1344
1345 <span class="h5"><a class="selflink" id="section-3.8.1.1" href="#section-3.8.1.1">3.8.1.1</a>. Route Requests</span>
1346
1347 When a node receives a route request for a prefix (prefix, plen), it
1348 checks its route table for a selected route to this exact prefix. If
1349 such a route exists, it MUST send an update; if such a route does
1350 not, it MUST send a retraction for that prefix.
1351
1352 When a node receives a wildcard route request, it SHOULD send a full
1353 routing table dump.
1354
1355 <span class="h5"><a class="selflink" id="section-3.8.1.2" href="#section-3.8.1.2">3.8.1.2</a>. Seqno Requests</span>
1356
1357 When a node receives a seqno request for a given router-id and
1358 sequence number, it checks whether its routing table contains a
1359 selected entry for that prefix; if no such entry exists, or the entry
1360 has infinite metric, it ignores the request.
1361
1362 If a selected route for the given prefix exists, and either the
1363 router-ids are different or the router-ids are equal and the entry's
1364 sequence number is no smaller than the requested sequence number, it
1365 MUST send an update for the given prefix.
1366
1367 If the router-ids match but the requested seqno is larger than the
1368 route entry's, the node compares the router-id against its own
1369 router-id. If the router-id is its own, then it increases its
1370 sequence number by 1 and sends an update. A node MUST NOT increase
1371 its sequence number by more than 1 in response to a route request.
1372
1373 If the requested router-id is not its own, the received request's hop
1374 count is 2 or more, and the node has a route (not necessarily a
1375 feasible one) for the requested prefix that does not use the
1376 requestor as a next hop, the node SHOULD forward the request. It
1377 does so by decreasing the hop count and sending the request in a
1378 unicast packet destined to a neighbour that advertises the given
1379 prefix (not necessarily the selected neighbour) and that is distinct
1380 from the neighbour from which the request was received.
1381
1382 A node SHOULD maintain a list of recently forwarded requests and
1383 forward the reply in a timely manner. A node SHOULD compare every
1384 incoming request against its list of recently forwarded requests and
1385 avoid forwarding it if it is redundant.
1386
1387 Since the request-forwarding mechanism does not necessarily obey the
1388 feasibility condition, it may get caught in routing loops; hence,
1389 requests carry a hop count to limit the time for which they remain in
1390 the network. However, since requests are only ever forwarded as
1391 unicast packets, the initial hop count need not be kept particularly
1392
1393
1394
1395
1396 <span class="grey">Chroboczek Experimental [Page 25]</span></pre>
1397 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-26" ></span>
1398 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1399
1400
1401 low, and performing an expanding horizon search is not necessary. A
1402 request MUST NOT be forwarded to a multicast address, and it MUST be
1403 forwarded to a single neighbour only.
1404
1405 <span class="h4"><a class="selflink" id="section-3.8.2" href="#section-3.8.2">3.8.2</a>. Sending Requests</span>
1406
1407 A Babel node MAY send a route or seqno request at any time, to a
1408 multicast or a unicast address; there is only one case when
1409 originating requests is required (<a href="#section-3.8.2.1">Section 3.8.2.1</a>).
1410
1411 <span class="h5"><a class="selflink" id="section-3.8.2.1" href="#section-3.8.2.1">3.8.2.1</a>. Avoiding Starvation</span>
1412
1413 When a route is retracted or expires, a Babel node usually switches
1414 to another feasible route for the same prefix. It may be the case,
1415 however, that no such routes are available.
1416
1417 A node that has lost all feasible routes to a given destination MUST
1418 send a seqno request. The router-id of the request is set to the
1419 router-id of the route that it has just lost, and the requested seqno
1420 is the value contained in the source table, plus 1.
1421
1422 Such a request SHOULD be multicast over all of the node's attached
1423 interfaces. Similar requests will be sent by other nodes that are
1424 affected by the route's loss and will be forwarded by neighbouring
1425 nodes up to the source. If the network is connected, and there is no
1426 packet loss, this will result in a route being advertised with a new
1427 sequence number. (Note that, due to duplicate suppression, only a
1428 small number of such requests will actually reach the source.)
1429
1430 In order to compensate for packet loss, a node SHOULD repeat such a
1431 request a small number of times if no route becomes feasible within a
1432 short time. Under heavy packet loss, however, all such requests may
1433 be lost; in that case, the second mechanism in the next section will
1434 eventually ensure that a new seqno is received.
1435
1436 <span class="h5"><a class="selflink" id="section-3.8.2.2" href="#section-3.8.2.2">3.8.2.2</a>. Dealing with Unfeasible Updates</span>
1437
1438 When a route's metric increases, a node might receive an unfeasible
1439 update for a route that it has currently selected. As specified in
1440 <a href="#section-3.5.1">Section 3.5.1</a>, the receiving node will either ignore the update or
1441 retract the route.
1442
1443 In order to keep routes from spuriously expiring because they have
1444 become unfeasible, a node SHOULD send a unicast seqno request
1445 whenever it receives an unfeasible update for a route that is
1446 currently selected. The requested sequence number is computed from
1447 the source table as above.
1448
1449
1450
1451
1452 <span class="grey">Chroboczek Experimental [Page 26]</span></pre>
1453 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-27" ></span>
1454 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1455
1456
1457 Additionally, a node SHOULD send a unicast seqno request whenever it
1458 receives an unfeasible update from a currently unselected neighbour
1459 that is "good enough", i.e., that would lead to the received route
1460 becoming selected were it feasible.
1461
1462 <span class="h5"><a class="selflink" id="section-3.8.2.3" href="#section-3.8.2.3">3.8.2.3</a>. Preventing Routes from Expiring</span>
1463
1464 In normal operation, a route's expiry timer should never trigger:
1465 since a route's hold time is computed from an explicit interval
1466 included in Update TLVs, a new update should arrive in time to
1467 prevent a route from expiring.
1468
1469 In the presence of packet loss, however, it may be the case that no
1470 update is successfully received for an extended period of time,
1471 causing a route to expire. In order to avoid such spurious expiry,
1472 shortly before a selected route expires, a Babel node SHOULD send a
1473 unicast route request to the neighbour that advertised this route;
1474 since nodes always send retractions in response to non-wildcard route
1475 requests (<a href="#section-3.8.1.1">Section 3.8.1.1</a>), this will usually result in either the
1476 route being refreshed or a retraction being received.
1477
1478 <span class="h5"><a class="selflink" id="section-3.8.2.4" href="#section-3.8.2.4">3.8.2.4</a>. Acquiring New Neighbours</span>
1479
1480 In order to speed up convergence after a mobility event, a node MAY
1481 send a unicast wildcard request after acquiring a new neighbour.
1482 Additionally, a node MAY send a small number of multicast wildcard
1483 requests shortly after booting.
1484
1485 <span class="h2"><a class="selflink" id="section-4" href="#section-4">4</a>. Protocol Encoding</span>
1486
1487 A Babel packet is sent as the body of a UDP datagram, with network-
1488 layer hop count set to 1, destined to a well-known multicast address
1489 or to a unicast address, over IPv4 or IPv6; in the case of IPv6,
1490 these addresses are link-local. Both the source and destination UDP
1491 port are set to a well-known port number. A Babel packet MUST be
1492 silently ignored unless its source address is either a link-local
1493 IPv6 address, or an IPv4 address belonging to the local network, and
1494 its source port is the well-known Babel port. Babel packets MUST NOT
1495 be sent as IPv6 Jumbograms.
1496
1497 In order to minimise the number of packets being sent while avoiding
1498 lower-layer fragmentation, a Babel node SHOULD attempt to maximise
1499 the size of the packets it sends, up to the outgoing interface's MTU
1500 adjusted for lower-layer headers (28 octets for UDP/IPv4, 48 octets
1501 for UDP/IPv6). It MUST NOT send packets larger than the attached
1502 interface's MTU (adjusted for lower-layer headers) or 512 octets,
1503 whichever is larger, but not exceeding 2^16 - 1 adjusted for lower-
1504
1505
1506
1507
1508 <span class="grey">Chroboczek Experimental [Page 27]</span></pre>
1509 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-28" ></span>
1510 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1511
1512
1513 layer headers. Every Babel speaker MUST be able to receive packets
1514 that are as large as any attached interface's MTU (adjusted for
1515 lower-layer headers) or 512 octets, whichever is larger.
1516
1517 In order to avoid global synchronisation of a Babel network and to
1518 aggregate multiple TLVs into large packets, a Babel node MUST buffer
1519 every TLV and delay sending a UDP packet by a small, randomly chosen
1520 delay [<a href="#ref-JITTER" title="&quot;The synchronization of periodic routing messages&quot;">JITTER</a>]. In order to allow accurate computation of packet
1521 loss rates, this delay MUST NOT be larger than half the advertised
1522 Hello interval.
1523
1524 <span class="h3"><a class="selflink" id="section-4.1" href="#section-4.1">4.1</a>. Data Types</span>
1525
1526 <span class="h4"><a class="selflink" id="section-4.1.1" href="#section-4.1.1">4.1.1</a>. Interval</span>
1527
1528 Relative times are carried as 16-bit values specifying a number of
1529 centiseconds (hundredths of a second). This allows times up to
1530 roughly 11 minutes with a granularity of 10 ms, which should cover
1531 all reasonable applications of Babel.
1532
1533 <span class="h4"><a class="selflink" id="section-4.1.2" href="#section-4.1.2">4.1.2</a>. Router-Id</span>
1534
1535 A router-id is an arbitrary 8-octet value. Router-ids SHOULD be
1536 assigned in modified EUI-64 format [<a href="#ref-ADDRARCH" title="&quot;IP Version 6 Addressing Architecture&quot;">ADDRARCH</a>].
1537
1538 <span class="h4"><a class="selflink" id="section-4.1.3" href="#section-4.1.3">4.1.3</a>. Address</span>
1539
1540 Since the bulk of the protocol is taken by addresses, multiple ways
1541 of encoding addresses are defined. Additionally, a common subnet
1542 prefix may be omitted when multiple addresses are sent in a single
1543 packet -- this is known as address compression [<a href="#ref-PACKETBB" title="&quot;Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format&quot;">PACKETBB</a>].
1544
1545 Address encodings:
1546
1547 o AE 0: wildcard address. The value is 0 octets long.
1548
1549 o AE 1: IPv4 address. Compression is allowed. 4 octets or less.
1550
1551 o AE 2: IPv6 address. Compression is allowed. 16 octets or less.
1552
1553 o AE 3: link-local IPv6 address. The value is 8 octets long, a
1554 prefix of fe80::/64 is implied.
1555
1556 The address family of an address is either IPv4 or IPv6; it is
1557 undefined for AE 0, IPv4 for AE 1, and IPv6 for AE 2 and 3.
1558
1559
1560
1561
1562
1563
1564 <span class="grey">Chroboczek Experimental [Page 28]</span></pre>
1565 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-29" ></span>
1566 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1567
1568
1569 <span class="h4"><a class="selflink" id="section-4.1.4" href="#section-4.1.4">4.1.4</a>. Prefixes</span>
1570
1571 A network prefix is encoded just like a network address, but it is
1572 stored in the smallest number of octets that are enough to hold the
1573 significant bits (up to the prefix length).
1574
1575 <span class="h3"><a class="selflink" id="section-4.2" href="#section-4.2">4.2</a>. Packet Format</span>
1576
1577 A Babel packet consists of a 4-octet header, followed by a sequence
1578 of TLVs.
1579
1580 0 1 2 3
1581 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
1582 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1583 | Magic | Version | Body length |
1584 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1585 | Packet Body ...
1586 +-+-+-+-+-+-+-+-+-+-+-+-+-
1587
1588 Fields :
1589
1590 Magic The arbitrary but carefully chosen value 42 (decimal);
1591 packets with a first octet different from 42 MUST be
1592 silently ignored.
1593
1594 Version This document specifies version 2 of the Babel protocol.
1595 Packets with a second octet different from 2 MUST be
1596 silently ignored.
1597
1598 Body length The length in octets of the body following the packet
1599 header.
1600
1601 Body The packet body; a sequence of TLVs.
1602
1603 Any data following the body MUST be silently ignored.
1604
1605 <span class="h3"><a class="selflink" id="section-4.3" href="#section-4.3">4.3</a>. TLV Format</span>
1606
1607 With the exception of Pad1, all TLVs have the following structure:
1608
1609 0 1 2 3
1610 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
1611 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1612 | Type | Length | Body...
1613 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
1614
1615
1616
1617
1618
1619
1620 <span class="grey">Chroboczek Experimental [Page 29]</span></pre>
1621 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-30" ></span>
1622 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1623
1624
1625 Fields :
1626
1627 Type The type of the TLV.
1628
1629 Length The length of the body, exclusive of the Type and Length
1630 fields. If the body is longer than the expected length of
1631 a given type of TLV, any extra data MUST be silently
1632 ignored.
1633
1634 Body The TLV body, the interpretation of which depends on the
1635 type.
1636
1637 TLVs with an unknown type value MUST be silently ignored.
1638
1639 <span class="h3"><a class="selflink" id="section-4.4" href="#section-4.4">4.4</a>. Details of Specific TLVs</span>
1640
1641 <span class="h4"><a class="selflink" id="section-4.4.1" href="#section-4.4.1">4.4.1</a>. Pad1</span>
1642
1643 0
1644 0 1 2 3 4 5 6 7
1645 +-+-+-+-+-+-+-+-+
1646 | Type = 0 |
1647 +-+-+-+-+-+-+-+-+
1648
1649 Fields :
1650
1651 Type Set to 0 to indicate a Pad1 TLV.
1652
1653 This TLV is silently ignored on reception.
1654
1655 <span class="h4"><a class="selflink" id="section-4.4.2" href="#section-4.4.2">4.4.2</a>. PadN</span>
1656
1657 0 1 2 3
1658 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
1659 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1660 | Type = 1 | Length | MBZ...
1661 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
1662
1663 Fields :
1664
1665 Type Set to 1 to indicate a PadN TLV.
1666
1667 Length The length of the body, exclusive of the Type and Length
1668 fields.
1669
1670 MBZ Set to 0 on transmission.
1671
1672 This TLV is silently ignored on reception.
1673
1674
1675
1676 <span class="grey">Chroboczek Experimental [Page 30]</span></pre>
1677 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-31" ></span>
1678 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1679
1680
1681 <span class="h4"><a class="selflink" id="section-4.4.3" href="#section-4.4.3">4.4.3</a>. Acknowledgement Request</span>
1682
1683 0 1 2 3
1684 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
1685 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1686 | Type = 2 | Length | Reserved |
1687 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1688 | Nonce | Interval |
1689 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1690
1691 This TLV requests that the receiver send an Acknowledgement TLV
1692 within the number of centiseconds specified by the Interval field.
1693
1694 Fields :
1695
1696 Type Set to 2 to indicate an Acknowledgement Request TLV.
1697
1698 Length The length of the body, exclusive of the Type and Length
1699 fields.
1700
1701 Reserved Sent as 0 and MUST be ignored on reception.
1702
1703 Nonce An arbitrary value that will be echoed in the receiver's
1704 Acknowledgement TLV.
1705
1706 Interval A time interval in centiseconds after which the sender will
1707 assume that this packet has been lost. This MUST NOT be 0.
1708 The receiver MUST send an acknowledgement before this time
1709 has elapsed (with a margin allowing for propagation time).
1710
1711 <span class="h4"><a class="selflink" id="section-4.4.4" href="#section-4.4.4">4.4.4</a>. Acknowledgement</span>
1712
1713 0 1 2 3
1714 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
1715 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1716 | Type = 3 | Length | Nonce |
1717 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1718
1719 This TLV is sent by a node upon receiving an Acknowledgement Request.
1720
1721 Fields :
1722
1723 Type Set to 3 to indicate an Acknowledgement TLV.
1724
1725 Length The length of the body, exclusive of the Type and Length
1726 fields.
1727
1728
1729
1730
1731
1732 <span class="grey">Chroboczek Experimental [Page 31]</span></pre>
1733 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-32" ></span>
1734 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1735
1736
1737 Nonce Set to the Nonce value of the Acknowledgement Request that
1738 prompted this Acknowledgement.
1739
1740 Since nonce values are not globally unique, this TLV MUST be sent to
1741 a unicast address.
1742
1743 <span class="h4"><a class="selflink" id="section-4.4.5" href="#section-4.4.5">4.4.5</a>. Hello</span>
1744
1745 0 1 2 3
1746 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
1747 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1748 | Type = 4 | Length | Reserved |
1749 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1750 | Seqno | Interval |
1751 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1752
1753 This TLV is used for neighbour discovery and for determining a link's
1754 reception cost.
1755
1756 Fields :
1757
1758 Type Set to 4 to indicate a Hello TLV.
1759
1760 Length The length of the body, exclusive of the Type and Length
1761 fields.
1762
1763 Reserved Sent as 0 and MUST be ignored on reception.
1764
1765 Seqno The value of the sending node's Hello seqno for this
1766 interface.
1767
1768 Interval An upper bound, expressed in centiseconds, on the time
1769 after which the sending node will send a new Hello TLV.
1770 This MUST NOT be 0.
1771
1772 Since there is a single seqno counter for all the Hellos sent by a
1773 given node over a given interface, this TLV MUST be sent to a
1774 multicast destination. In order to avoid large discontinuities in
1775 link quality, multiple Hello TLVs SHOULD NOT be sent in the same
1776 packet.
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788 <span class="grey">Chroboczek Experimental [Page 32]</span></pre>
1789 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-33" ></span>
1790 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1791
1792
1793 <span class="h4"><a class="selflink" id="section-4.4.6" href="#section-4.4.6">4.4.6</a>. IHU</span>
1794
1795 0 1 2 3
1796 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
1797 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1798 | Type = 5 | Length | AE | Reserved |
1799 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1800 | Rxcost | Interval |
1801 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1802 | Address...
1803 +-+-+-+-+-+-+-+-+-+-+-+-
1804
1805 An IHU ("I Heard You") TLV is used for confirming bidirectional
1806 reachability and carrying a link's transmission cost.
1807
1808 Fields :
1809
1810 Type Set to 5 to indicate an IHU TLV.
1811
1812 Length The length of the body, exclusive of the Type and Length
1813 fields.
1814
1815 AE The encoding of the Address field. This should be 1 or 3
1816 in most cases. As an optimisation, it MAY be 0 if the TLV
1817 is sent to a unicast address, if the association is over a
1818 point-to-point link, or when bidirectional reachability is
1819 ascertained by means outside of the Babel protocol.
1820
1821 Reserved Sent as 0 and MUST be ignored on reception.
1822
1823 Rxcost The rxcost according to the sending node of the interface
1824 whose address is specified in the Address field. The value
1825 FFFF hexadecimal (infinity) indicates that this interface
1826 is unreachable.
1827
1828 Interval An upper bound, expressed in centiseconds, on the time
1829 after which the sending node will send a new IHU; this MUST
1830 NOT be 0. The receiving node will use this value in order
1831 to compute a hold time for this symmetric association.
1832
1833 Address The address of the destination node, in the format
1834 specified by the AE field. Address compression is not
1835 allowed.
1836
1837 Conceptually, an IHU is destined to a single neighbour. However, IHU
1838 TLVs contain an explicit destination address, and it SHOULD be sent
1839 to a multicast address, as this allows aggregation of IHUs destined
1840
1841
1842
1843
1844 <span class="grey">Chroboczek Experimental [Page 33]</span></pre>
1845 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-34" ></span>
1846 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1847
1848
1849 to distinct neighbours into a single packet and avoids the need for
1850 an ARP or Neighbour Discovery exchange when a neighbour is not being
1851 used for data traffic.
1852
1853 IHU TLVs with an unknown value for the AE field MUST be silently
1854 ignored.
1855
1856 <span class="h4"><a class="selflink" id="section-4.4.7" href="#section-4.4.7">4.4.7</a>. Router-Id</span>
1857
1858 0 1 2 3
1859 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
1860 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1861 | Type = 6 | Length | Reserved |
1862 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1863 | |
1864 + Router-Id +
1865 | |
1866 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1867
1868 A Router-Id TLV establishes a router-id that is implied by subsequent
1869 Update TLVs.
1870
1871 Fields :
1872
1873 Type Set to 6 to indicate a Router-Id TLV.
1874
1875 Length The length of the body, exclusive of the Type and Length
1876 fields.
1877
1878 Reserved Sent as 0 and MUST be ignored on reception.
1879
1880 Router-Id The router-id for routes advertised in subsequent Update
1881 TLVs
1882
1883 <span class="h4"><a class="selflink" id="section-4.4.8" href="#section-4.4.8">4.4.8</a>. Next Hop</span>
1884
1885 0 1 2 3
1886 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
1887 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1888 | Type = 7 | Length | AE | Reserved |
1889 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1890 | Next hop...
1891 +-+-+-+-+-+-+-+-+-+-+-+-
1892
1893 A Next Hop TLV establishes a next-hop address for a given address
1894 family (IPv4 or IPv6) that is implied by subsequent Update TLVs.
1895
1896
1897
1898
1899
1900 <span class="grey">Chroboczek Experimental [Page 34]</span></pre>
1901 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-35" ></span>
1902 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1903
1904
1905 Fields :
1906
1907 Type Set to 7 to indicate a Next Hop TLV.
1908
1909 Length The length of the body, exclusive of the Type and Length
1910 fields.
1911
1912 AE The encoding of the Address field. This SHOULD be 1 or 3
1913 and MUST NOT be 0.
1914
1915 Reserved Sent as 0 and MUST be ignored on reception.
1916
1917 Next hop The next-hop address advertised by subsequent Update TLVs,
1918 for this address family.
1919
1920 When the address family matches the network-layer protocol that this
1921 packet is transported over, a Next Hop TLV is not needed: in that
1922 case, the next hop is taken to be the source address of the packet.
1923
1924 Next Hop TLVs with an unknown value for the AE field MUST be silently
1925 ignored.
1926
1927 <span class="h4"><a class="selflink" id="section-4.4.9" href="#section-4.4.9">4.4.9</a>. Update</span>
1928
1929 0 1 2 3
1930 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
1931 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1932 | Type = 8 | Length | AE | Flags |
1933 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1934 | Plen | Omitted | Interval |
1935 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1936 | Seqno | Metric |
1937 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1938 | Prefix...
1939 +-+-+-+-+-+-+-+-+-+-+-+-
1940
1941 An Update TLV advertises or retracts a route. As an optimisation,
1942 this can also have the side effect of establishing a new implied
1943 router-id and a new default prefix.
1944
1945 Fields :
1946
1947 Type Set to 8 to indicate an Update TLV.
1948
1949 Length The length of the body, exclusive of the Type and Length
1950 fields.
1951
1952 AE The encoding of the Prefix field.
1953
1954
1955
1956 <span class="grey">Chroboczek Experimental [Page 35]</span></pre>
1957 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-36" ></span>
1958 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
1959
1960
1961 Flags The individual bits of this field specify special handling
1962 of this TLV (see below). Every node MUST be able to
1963 interpret the flags with values 80 and 40 hexadecimal;
1964 unknown flags MUST be silently ignored.
1965
1966 Plen The length of the advertised prefix.
1967
1968 Omitted The number of octets that have been omitted at the
1969 beginning of the advertised prefix and that should be taken
1970 from a preceding Update TLV with the flag with value 80
1971 hexadecimal set.
1972
1973 Interval An upper bound, expressed in centiseconds, on the time
1974 after which the sending node will send a new update for
1975 this prefix. This MUST NOT be 0 and SHOULD NOT be less
1976 than 10. The receiving node will use this value to compute
1977 a hold time for this routing table entry. The value FFFF
1978 hexadecimal (infinity) expresses that this announcement
1979 will not be repeated unless a request is received
1980 (<a href="#section-3.8.2.3">Section 3.8.2.3</a>).
1981
1982 Seqno The originator's sequence number for this update.
1983
1984 Metric The sender's metric for this route. The value FFFF
1985 hexadecimal (infinity) means that this is a route
1986 retraction.
1987
1988 Prefix The prefix being advertised. This field's size is (Plen/8
1989 - Omitted) rounded upwards.
1990
1991 The Flags field is interpreted as follows:
1992
1993 o if the bit with value 80 hexadecimal is set, then this Update
1994 establishes a new default prefix for subsequent Update TLVs with a
1995 matching address family within the same packet;
1996
1997 o if the bit with value 40 hexadecimal is set, then the low-order 8
1998 octets of the advertised prefix establish a new default router-id
1999 for this TLV and subsequent Update TLVs in the same packet.
2000
2001 The prefix being advertised by an Update TLV is computed as follows:
2002
2003 o the first Omitted octets of the prefix are taken from the previous
2004 Update TLV with flag 80 hexadecimal set and the same address
2005 family;
2006
2007 o the next (Plen/8 - Omitted) (rounded upwards) octets are taken
2008 from the Prefix field;
2009
2010
2011
2012 <span class="grey">Chroboczek Experimental [Page 36]</span></pre>
2013 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-37" ></span>
2014 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
2015
2016
2017 o the remaining octets are set to 0.
2018
2019 If the Metric field is finite, the router-id of the originating node
2020 for this announcement is taken from the low-order 8 octets of the
2021 prefix advertised by this Update if the bit with value 40 hexadecimal
2022 is set in the Flags field. Otherwise, it is taken either from the
2023 preceding Router-Id packet, or the preceding Update packet with flag
2024 40 hexadecimal set, whichever comes last.
2025
2026 The next-hop address for this update is taken from the last preceding
2027 Next Hop TLV with a matching address family in the same packet; if no
2028 such TLV exists, it is taken from the network-layer source address of
2029 this packet.
2030
2031 If the metric field is FFFF hexadecimal, this TLV specifies a
2032 retraction. In that case, the current router-id and the Seqno are
2033 not used. AE MAY then be 0, in which case this Update retracts all
2034 of the routes previously advertised on this interface.
2035
2036 Update TLVs with an unknown value for the AE field MUST be silently
2037 ignored.
2038
2039 <span class="h4"><a class="selflink" id="section-4.4.10" href="#section-4.4.10">4.4.10</a>. Route Request</span>
2040
2041 0 1 2 3
2042 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
2043 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2044 | Type = 9 | Length | AE | Plen |
2045 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2046 | Prefix...
2047 +-+-+-+-+-+-+-+-+-+-+-+-
2048
2049 A Route Request TLV prompts the receiver to send an update for a
2050 given prefix, or a full routing table dump.
2051
2052 Fields :
2053
2054 Type Set to 9 to indicate a Route Request TLV.
2055
2056 Length The length of the body, exclusive of the Type and Length
2057 fields.
2058
2059 AE The encoding of the Prefix field. The value 0 specifies
2060 that this is a request for a full routing table dump (a
2061 wildcard request).
2062
2063 Plen The length of the requested prefix.
2064
2065
2066
2067
2068 <span class="grey">Chroboczek Experimental [Page 37]</span></pre>
2069 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-38" ></span>
2070 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
2071
2072
2073 Prefix The prefix being requested. This field's size is Plen/8
2074 rounded upwards.
2075
2076 A Request TLV prompts the receiving node to send an update message
2077 for the prefix specified by the AE, Plen, and Prefix fields, or a
2078 full dump of its routing table if AE is 0 (in which case Plen MUST be
2079 0, and Prefix is of length 0). A Request may be sent to a unicast
2080 address if it is destined to a single node, or to a multicast address
2081 if the request is destined to all of the neighbours of the sending
2082 interface.
2083
2084 <span class="h4"><a class="selflink" id="section-4.4.11" href="#section-4.4.11">4.4.11</a>. Seqno Request</span>
2085
2086 0 1 2 3
2087 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
2088 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2089 | Type = 10 | Length | AE | Plen |
2090 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2091 | Seqno | Hop Count | Reserved |
2092 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2093 | |
2094 + Router-Id +
2095 | |
2096 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2097 | Prefix...
2098 +-+-+-+-+-+-+-+-+-+-+
2099
2100 A Seqno Request TLV prompts the receiver to send an Update for a
2101 given prefix with a given sequence number, or to forward the request
2102 further if it cannot be satisfied locally.
2103
2104 Fields :
2105
2106 Type Set to 10 to indicate a Seqno Request message.
2107
2108 Length The length of the body, exclusive of the Type and Length
2109 fields.
2110
2111 AE The encoding of the Prefix field. This MUST NOT be 0.
2112
2113 Plen The length of the requested prefix.
2114
2115 Seqno The sequence number that is being requested.
2116
2117 Hop Count The maximum number of times that this TLV may be forwarded,
2118 plus 1. This MUST NOT be 0.
2119
2120
2121
2122
2123
2124 <span class="grey">Chroboczek Experimental [Page 38]</span></pre>
2125 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-39" ></span>
2126 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
2127
2128
2129 Prefix The prefix being requested. This field's size is Plen/8
2130 rounded upwards.
2131
2132 A Seqno Request TLV prompts the receiving node to send an Update for
2133 the prefix specified by the AE, Plen, and Prefix fields, with either
2134 a router-id different from what is specified by the Router-Id field,
2135 or a Seqno no less than what is specified by the Seqno field. If
2136 this request cannot be satisfied locally, then it is forwarded
2137 according to the rules set out in <a href="#section-3.8.1.2">Section 3.8.1.2</a>.
2138
2139 While a Seqno Request MAY be sent to a multicast address, it MUST NOT
2140 be forwarded to a multicast address and MUST NOT be forwarded to more
2141 than one neighbour. A request MUST NOT be forwarded if its Hop Count
2142 field is 1.
2143
2144 <span class="h2"><a class="selflink" id="section-5" href="#section-5">5</a>. IANA Considerations</span>
2145
2146 IANA has registered the UDP port number 6697, called "babel", for use
2147 by the Babel protocol.
2148
2149 IANA has registered the IPv6 multicast group ff02:0:0:0:0:0:1:6 and
2150 the IPv4 multicast group 224.0.0.111 for use by the Babel protocol.
2151
2152 <span class="h2"><a class="selflink" id="section-6" href="#section-6">6</a>. Security Considerations</span>
2153
2154 As defined in this document, Babel is a completely insecure protocol.
2155 Any attacker can attract data traffic by advertising routes with a
2156 low metric. This particular issue can be solved either by lower-
2157 layer security mechanisms (e.g., IPsec or link-layer security), or by
2158 appending a cryptographic key to Babel packets; the provision of
2159 ignoring any data contained within a Babel packet beyond the body
2160 length declared by the header is designed for just such a purpose.
2161
2162 The information that a Babel node announces to the whole routing
2163 domain is often sufficient to determine a mobile node's physical
2164 location with reasonable precision. The privacy issues that this
2165 causes can be mitigated somewhat by using randomly chosen router-ids
2166 and randomly chosen IP addresses, and changing them periodically.
2167
2168 When carried over IPv6, Babel packets are ignored unless they are
2169 sent from a link-local IPv6 address; since routers don't forward
2170 link-local IPv6 packets, this provides protection against spoofed
2171 Babel packets being sent from the global Internet. No such natural
2172 protection exists when Babel packets are carried over IPv4.
2173
2174
2175
2176
2177
2178
2179
2180 <span class="grey">Chroboczek Experimental [Page 39]</span></pre>
2181 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-40" ></span>
2182 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
2183
2184
2185 <span class="h2"><a class="selflink" id="section-7" href="#section-7">7</a>. References</span>
2186
2187 <span class="h3"><a class="selflink" id="section-7.1" href="#section-7.1">7.1</a>. Normative References</span>
2188
2189 [<a id="ref-ADDRARCH">ADDRARCH</a>] Hinden, R. and S. Deering, "IP Version 6 Addressing
2190 Architecture", <a href="./rfc4291">RFC 4291</a>, February 2006.
2191
2192 [<a id="ref-RFC2119">RFC2119</a>] Bradner, S., "Key words for use in RFCs to Indicate
2193 Requirement Levels", <a href="https://www.rfc-editor.org/bcp/bcp14">BCP 14</a>, <a href="./rfc2119">RFC 2119</a>, March 1997.
2194
2195 <span class="h3"><a class="selflink" id="section-7.2" href="#section-7.2">7.2</a>. Informative References</span>
2196
2197 [<a id="ref-DSDV">DSDV</a>] Perkins, C. and P. Bhagwat, "Highly Dynamic Destination-
2198 Sequenced Distance-Vector Routing (DSDV) for Mobile
2199 Computers", ACM SIGCOMM'94 Conference on Communications
2200 Architectures, Protocols and Applications 234-244, 1994.
2201
2202 [<a id="ref-DUAL">DUAL</a>] Garcia Luna Aceves, J., "Loop-Free Routing Using
2203 Diffusing Computations", IEEE/ACM Transactions on
2204 Networking 1:1, February 1993.
2205
2206 [<a id="ref-EIGRP">EIGRP</a>] Albrightson, B., Garcia Luna Aceves, J., and J. Boyle,
2207 "EIGRP -- a Fast Routing Protocol Based on Distance
2208 Vectors", Proc. Interop 94, 1994.
2209
2210 [<a id="ref-ETX">ETX</a>] De Couto, D., Aguayo, D., Bicket, J., and R. Morris, "A
2211 high-throughput path metric for multi-hop wireless
2212 networks", Proc. MobiCom 2003, 2003.
2213
2214 [<a id="ref-IS-IS">IS-IS</a>] "Information technology -- Telecommunications and
2215 information exchange between systems -- Intermediate
2216 System to Intermediate System intra-domain routeing
2217 information exchange protocol for use in conjunction with
2218 the protocol for providing the connectionless-mode
2219 network service (ISO 8473)", ISO/IEC 10589:2002.
2220
2221 [<a id="ref-JITTER">JITTER</a>] Floyd, S. and V. Jacobson, "The synchronization of
2222 periodic routing messages", IEEE/ACM Transactions on
2223 Networking 2, 2, 122-136, April 1994.
2224
2225 [<a id="ref-OSPF">OSPF</a>] Moy, J., "OSPF Version 2", STD 54, <a href="./rfc2328">RFC 2328</a>, April 1998.
2226
2227 [<a id="ref-PACKETBB">PACKETBB</a>] Clausen, T., Dearlove, C., Dean, J., and C. Adjih,
2228 "Generalized Mobile Ad Hoc Network (MANET) Packet/Message
2229 Format", <a href="./rfc5444">RFC 5444</a>, February 2009.
2230
2231 [<a id="ref-RIP">RIP</a>] Malkin, G., "RIP Version 2", STD 56, <a href="./rfc2453">RFC 2453</a>,
2232 November 1998.
2233
2234
2235
2236 <span class="grey">Chroboczek Experimental [Page 40]</span></pre>
2237 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-41" ></span>
2238 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
2239
2240
2241 <span class="h2"><a class="selflink" id="appendix-A" href="#appendix-A">Appendix A</a>. Cost and Metric Computation</span>
2242
2243 The strategy for computing link costs and route metrics is a local
2244 matter; Babel itself only requires that it comply with the conditions
2245 given in Sections <a href="#section-3.4.3">3.4.3</a> and <a href="#section-3.5.2">3.5.2</a>. Different nodes MAY use different
2246 strategies in a single network and MAY use different strategies on
2247 different interface types. This section gives a few examples of such
2248 strategies.
2249
2250 The sample implementation of Babel maintains statistics about the
2251 last 16 received Hello TLVs (Appendix A.1), computes costs by using
2252 the 2-out-of-3 strategy (Appendix A.2.1) on wired links, and ETX
2253 [<a href="#ref-ETX" title="&quot;A high-throughput path metric for multi-hop wireless networks&quot;">ETX</a>] on wireless links. It uses an additive algebra for metric
2254 computation (Appendix A.3.1).
2255
2256 <span class="h3"><a class="selflink" id="appendix-A.1" href="#appendix-A.1">A.1</a>. Maintaining Hello History</span>
2257
2258 For each neighbour, the sample implementation of Babel maintains a
2259 Hello history and an expected sequence number. The Hello history is
2260 a vector of 16 bits, where a 1 value represents a received Hello, and
2261 a 0 value a missed Hello. The expected sequence number, written ne,
2262 is the sequence number that is expected to be carried by the next
2263 received hello from this neighbour.
2264
2265 Whenever it receives a Hello packet from a neighbour, a node compares
2266 the received sequence number nr with its expected sequence number ne.
2267 Depending on the outcome of this comparison, one of the following
2268 actions is taken:
2269
2270 o if the two differ by more than 16 (modulo 2^16), then the sending
2271 node has probably rebooted and lost its sequence number; the
2272 associated neighbour table entry is flushed;
2273
2274 o otherwise, if the received nr is smaller (modulo 2^16) than the
2275 expected sequence number ne, then the sending node has increased
2276 its Hello interval without our noticing; the receiving node
2277 removes the last (ne - nr) entries from this neighbour's Hello
2278 history (we "undo history");
2279
2280 o otherwise, if nr is larger (modulo 2^16) than ne, then the sending
2281 node has decreased its Hello interval, and some Hellos were lost;
2282 the receiving node adds (nr - ne) 0 bits to the Hello history (we
2283 "fast-forward").
2284
2285
2286
2287
2288
2289
2290
2291
2292 <span class="grey">Chroboczek Experimental [Page 41]</span></pre>
2293 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-42" ></span>
2294 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
2295
2296
2297 The receiving node then appends a 1 bit to the neighbour's Hello
2298 history, resets the neighbour's Hello timer, and sets ne to (nr + 1).
2299 It then resets the neighbour's Hello timer to 1.5 times the value
2300 advertised in the received Hello (the extra margin allows for the
2301 delay due to jitter).
2302
2303 Whenever the Hello timer associated to a neighbour expires, the local
2304 node adds a 0 bit to this neighbour's Hello history, and increments
2305 the expected Hello number. If the Hello history is empty (it
2306 contains 0 bits only), the neighbour entry is flushed; otherwise, it
2307 resets the neighbour's Hello timer to the value advertised in the
2308 last Hello received from this neighbour (no extra margin is necessary
2309 in this case).
2310
2311 <span class="h3"><a class="selflink" id="appendix-A.2" href="#appendix-A.2">A.2</a>. Cost Computation</span>
2312
2313 <span class="h4"><a class="selflink" id="appendix-A.2.1" href="#appendix-A.2.1">A.2.1</a>. k-out-of-j</span>
2314
2315 K-out-of-j link sensing is suitable for wired links that are either
2316 up, in which case they only occasionally drop a packet, or down, in
2317 which case they drop all packets.
2318
2319 The k-out-of-j strategy is parameterised by two small integers k and
2320 j, such that 0 &lt; k &lt;= j, and the nominal link cost, a constant K &gt;=
2321 1. A node keeps a history of the last j hellos; if k or more of
2322 those have been correctly received, the link is assumed to be up, and
2323 the rxcost is set to K; otherwise, the link is assumed to be down,
2324 and the rxcost is set to infinity.
2325
2326 The cost of such a link is defined as
2327
2328 o cost = FFFF hexadecimal if rxcost = FFFF hexadecimal;
2329
2330 o cost = txcost otherwise.
2331
2332 <span class="h4"><a class="selflink" id="appendix-A.2.2" href="#appendix-A.2.2">A.2.2</a>. ETX</span>
2333
2334 The Estimated Transmission Cost metric [<a href="#ref-ETX" title="&quot;A high-throughput path metric for multi-hop wireless networks&quot;">ETX</a>] estimates the number of
2335 times that a unicast frame will be retransmitted by the IEEE 802.11
2336 MAC, assuming infinite persistence.
2337
2338 A node uses a neighbour's Hello history to compute an estimate,
2339 written beta, of the probability that a Hello TLV is successfully
2340 received. The rxcost is defined as 256/beta.
2341
2342 Let alpha be MIN(1, 256/txcost), an estimate of the probability of
2343 successfully sending a Hello TLV. The cost is then computed by
2344
2345
2346
2347
2348 <span class="grey">Chroboczek Experimental [Page 42]</span></pre>
2349 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-43" ></span>
2350 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
2351
2352
2353 cost = 256/(alpha * beta)
2354
2355 or, equivalently,
2356
2357 cost = (MAX(txcost, 256) * rxcost) / 256.
2358
2359 <span class="h3"><a class="selflink" id="appendix-A.3" href="#appendix-A.3">A.3</a>. Metric Computation</span>
2360
2361 <span class="h4"><a class="selflink" id="appendix-A.3.1" href="#appendix-A.3.1">A.3.1</a>. Additive Metrics</span>
2362
2363 The simplest approach for obtaining a monotonic, isotonic metric is
2364 to define the metric of a route as the sum of the costs of the
2365 component links. More formally, if a neighbour advertises a route
2366 with metric m over a link with cost c, then the resulting route has
2367 metric M(c, m) = c + m.
2368
2369 A multiplicative metric can be converted to an additive one by taking
2370 the logarithm (in some suitable base) of the link costs.
2371
2372 <span class="h4"><a class="selflink" id="appendix-A.3.2" href="#appendix-A.3.2">A.3.2</a>. External Sources of Willingness</span>
2373
2374 A node may want to vary its willingness to forward packets by taking
2375 into account information that is external to the Babel protocol, such
2376 as the monetary cost of a link, the node's battery status, CPU load,
2377 etc. This can be done by adding to every route's metric a value k
2378 that depends on the external data. For example, if a battery-powered
2379 node receives an update with metric m over a link with cost c, it
2380 might compute a metric M(c, m) = k + c + m, where k depends on the
2381 battery status.
2382
2383 In order to preserve strict monotonicity (<a href="#section-3.5.2">Section 3.5.2</a>), the value k
2384 must be greater than -c.
2385
2386 <span class="h2"><a class="selflink" id="appendix-B" href="#appendix-B">Appendix B</a>. Constants</span>
2387
2388 The choice of time constants is a trade-off between fast detection of
2389 mobility events and protocol overhead. Two implementations of Babel
2390 with different time constants will interoperate, although the
2391 resulting convergence time will most likely be dictated by the
2392 slowest of the two implementations.
2393
2394 Experience with the sample implementation of Babel indicates that the
2395 Hello interval is the most important time constant: a mobility event
2396 is detected within 1.5 to 3 Hello intervals. Due to Babel's reliance
2397 on triggered updates and explicit requests, the Update interval only
2398 has an effect on the time it takes for accurate metrics to be
2399 propagated after variations in link costs too small to trigger an
2400 unscheduled update.
2401
2402
2403
2404 <span class="grey">Chroboczek Experimental [Page 43]</span></pre>
2405 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-44" ></span>
2406 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
2407
2408
2409 At the time of writing, the sample implementation of Babel uses the
2410 following default values:
2411
2412 Hello Interval: 4 seconds on wireless links, 20 seconds on wired
2413 links.
2414
2415 IHU Interval: the advertised IHU interval is always 3 times the
2416 Hello interval. IHUs are actually sent with each Hello on lossy
2417 links (as determined from the Hello history), but only with every
2418 third Hello on lossless links.
2419
2420 Update Interval: 4 times the Hello interval.
2421
2422 IHU Hold Time: 3.5 times the advertised IHU interval.
2423
2424 Route Expiry Time: 3.5 times the advertised update interval.
2425
2426 Source GC time: 3 minutes.
2427
2428 The amount of jitter applied to a packet depends on whether it
2429 contains any urgent TLVs or not. Urgent triggered updates and urgent
2430 requests are delayed by no more than 200 ms; other TLVs are delayed
2431 by no more than one-half the Hello interval.
2432
2433 <span class="h2"><a class="selflink" id="appendix-C" href="#appendix-C">Appendix C</a>. Simplified Implementations</span>
2434
2435 Babel is a fairly economic protocol. Route updates take between 12
2436 and 40 octets per destination, depending on how successful
2437 compression is; in a double-stack mesh network, an average of less
2438 than 24 octets is typical. The route table occupies about 35 octets
2439 per IPv6 entry. To put these values into perspective, a single full-
2440 size Ethernet frame can carry some 65 route updates, and a megabyte
2441 of memory can contain a 20000-entry routing table and the associated
2442 source table.
2443
2444 Babel is also a reasonably simple protocol. The sample
2445 implementation consists of less than 8000 lines of C code, and it
2446 compiles to less than 60 kB of text on a 32-bit CISC architecture.
2447
2448 Nonetheless, in some very constrained environments, such as PDAs,
2449 microwave ovens, or abacuses, it may be desirable to have subset
2450 implementations of the protocol.
2451
2452 A parasitic implementation is one that uses a Babel network for
2453 routing its packets but does not announce any of the routes that it
2454 has learnt from its neighbours. (This is slightly more than a
2455 passive implementation, which doesn't even announce routes to
2456 itself.) It may either maintain a full routing table or simply
2457
2458
2459
2460 <span class="grey">Chroboczek Experimental [Page 44]</span></pre>
2461 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-45" ></span>
2462 <span class="grey"><a href="./rfc6126">RFC 6126</a> The Babel Routing Protocol April 2011</span>
2463
2464
2465 select a gateway amongst any one of its neighbours that announces a
2466 default route. Since a parasitic implementation never forwards
2467 packets, it cannot possibly participate in a routing loop; hence, it
2468 need not evaluate the feasibility condition and need not maintain a
2469 source table.
2470
2471 A parasitic implementation MUST answer acknowledgement requests and
2472 MUST participate in the Hello/IHU protocol. Finally, it MUST be able
2473 to reply to seqno requests for routes that it announces and SHOULD be
2474 able to reply to route requests.
2475
2476 <span class="h2"><a class="selflink" id="appendix-D" href="#appendix-D">Appendix D</a>. Software Availability</span>
2477
2478 The sample implementation of Babel is available from
2479 &lt;<a href="http://www.pps.jussieu.fr/~jch/software/babel/">http://www.pps.jussieu.fr/~jch/software/babel/</a>&gt;.
2480
2481 Author's Address
2482
2483 Juliusz Chroboczek
2484 PPS, University of Paris 7
2485 Case 7014
2486 75205 Paris Cedex 13,
2487 France
2488
2489 EMail: [email protected]
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516 Chroboczek Experimental [Page 45]
2517 </pre>