| 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 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=""RIP Version 2"">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=""Highly Dynamic Destination- Sequenced Distance-Vector Routing (DSDV) for Mobile Computers"">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=""OSPF Version 2"">OSPF</a>], IS-IS [<a href="#ref-IS-IS" title=""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)"">IS-IS</a>], or the Enhanced |
| 187 |
Interior Gateway Routing Protocol (EIGRP) [<a href="#ref-EIGRP" title=""EIGRP -- a Fast Routing Protocol Based on Distance Vectors"">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=""Key words for use in RFCs to Indicate Requirement Levels"">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=""RIP Version 2"">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=""Highly Dynamic Destination- Sequenced Distance-Vector Routing (DSDV) for Mobile Computers"">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) <= 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) < 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=""Loop-Free Routing Using Diffusing Computations"">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) < 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) <= 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) <= |
| 370 |
D(A), hence D(B) < D(A), and since D(A) <= FD(A), D(B) < 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 < 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) < 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' > s, or s = s' and m' < 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=""IP Version 6 Addressing Architecture"">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=""The synchronization of periodic routing messages"">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) < (seqno', metric') |
| 968 |
|
| 969 |
when |
| 970 |
|
| 971 |
seqno > seqno' or (seqno = seqno' and metric < 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' < seqno or |
| 998 |
|
| 999 |
* seqno = seqno' and metric < 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) > m. |
| 1025 |
|
| 1026 |
Additionally, the metric SHOULD satisfy the following condition: |
| 1027 |
|
| 1028 |
o M is isotonic: if m <= m', then M(c, m) <= 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=""Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format"">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 > 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' > 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=""The synchronization of periodic routing messages"">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=""IP Version 6 Addressing Architecture"">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=""Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format"">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=""A high-throughput path metric for multi-hop wireless networks"">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 < k <= j, and the nominal link cost, a constant K >= |
| 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=""A high-throughput path metric for multi-hop wireless networks"">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 |
<<a href="http://www.pps.jussieu.fr/~jch/software/babel/">http://www.pps.jussieu.fr/~jch/software/babel/</a>>. |
| 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> |