| Network Working Group | J. Chroboczek |
| Internet-Draft | PPS, University of Paris-Diderot |
| Intended status: Experimental | July 4, 2014 |
| Expires: January 5, 2015 |
Diversity Routing for the Babel Routing Protocol
draft-chroboczek-babel-diversity-routing-00
This document defines an extension to the Babel routing protocol that allows routing updates to carry radio frequency information, and therefore makes it possible to use radio diversity information for route selection.
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."
This Internet-Draft will expire on January 5, 2015.
Copyright (c) 2014 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
The Babel routing protocol [BABEL] does not mandate a specific algorithm for computing metrics; Appendix A of that document suggests using an additive integer metric. While this works well in many topologies, it fails to take into account the possibility of interference between radio links, which is important in multi-frequency wireless mesh networks.
Consider for example the following topology, where the solid lines use one radio frequency and the dashed lines another, and suppose that the solid frequency has very slightly lower packet loss than the dashed one:
B / \ / \ A D \ . \ . C
When sending data from A to D, Babel will reliably choose the solid route through B. Howerver, this route self-interferes: when B is sending a packet to D, it cannot simultaneously be receiving a packet from A, which halves the effective throughput. No such issue arises with the route through C, which should therefore be preferred.
Interference needs to be taken into account even when it happens between non-adjacent links. Consider the following topology:
B +++ C / \ / \ A F \ . \ . D +++ E
When routing data from A to F, the route through B and C has two interfering links: if two packets are sent by A and C at roughly the same time, a collision will occur, and both packets will need to be resent. Again, no such issue arises with the route through D and E.
The diversity protocol extension allows a Babel router to attach information about radio frequency to the routes that it maintains — we call this the route's "diversity information".
We assume that all links can be categorised into one of the following categories:
This model does not describe reality accurately, since distinct but close radio frequencies do in fact interfere, but it works well enough in practical networks, where a small number of discrete radio frequencies are used.
A Babel router maintains a route table ([BABEL] Section 3.2.5). A router implementing diversity routing has one additional field in every route table entry:
The diversity data is interpreted as the set of channels of the links that would be followed by a packet sent along this route, omitting non-interfering links. The value 255 is special — it indicates an interfering link.
When a node receives an Update TLV, it creates or updates a routing table entry according to [BABEL], Section 3.5.4. A node that performs diversity routing extends the procedure given in that section with the following procedure.
Let D be the diversity information attached to the received Update TLV, or the one-element sequence 255 if there is no such information. Then the routing table entry diversity information is set to D', where:
Note that zero-length diversity information is different from lack of diversity information: the latter is treated as 255 (interfering, since no information is available) in order to ensure interoperability with the original Babel protocol.
A Babel node sends updates in various circumstances, described in [BABEL], Section 3.7. A node performing diversity routing attaches diversity data to every update that it send. This diversity data is computed as follows:
How the diversity data is used for metric computation and/or route selection is left to the implementation, as long as it obeys the rules given in Sections 3.5.2 and 3.6 of [BABEL]. In particular, the strict monotonicity requirement implies that a non-interfering hop must be taken into account in the resulting metric — it cannot be simply ignored.
An algorithm that has been found to work relatively well in practice is given in Appendix A.
We define one new sub-TLV which is attached to Update TLVs and contains a sequence of channel numbers.
A channel number is encoded as a one-octet integer. The following values are used by the current implementation:
Other values are not currently used, and MAY be used by mutual agreement to represent radio frequencies not covered by the above.
Diversity data is carried in a Diversity sub-TLV [BABEL-EXT] that is carried by Update TLVs. The sub-TLV contains a sequence of octets that directly encode the diversity data from the route table.
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type = 2 | Length | Channel 1 | Channel 2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Channel 3 | ... +-+-+-+-+-+-+-+-+-+-+-+-+-
Fields :
| [BABEL] | Chroboczek, J., "The Babel Routing Protocol", RFC 6126, February 2011. |
| [BABEL-EXT] | Chroboczek, J., "Extension Mechanism for the Babel Routing Protocol", Internet Draft draft-chroboczek-babel-extension-mechanism-01, June 2014. |
In this section, we describe the Z3 algorithm, a particular instance of diversity routing that has seen some modest deployment and that appears to work reasonably well in practice while being extremely easy to implement.
The Z3 algorithm works by announcing a slightly smaller metric than the metric it uses for route selection when announcing over a non-interfering link. In effect, a Z3 router maintains two metrics for each route: the noninterfering metric, which is announced on links that can be proven to not interfere with the route being announced, and the interfering metric, which is used for route selection and announced over all other links.
More precisely, upon receiving an update with metric M over a link with cost C, the interfering metric is set to C+M, as suggested in Appendix A of [BABEL]. The non-interfering metric is set to alpha*C+M, where 0<alpha<1 is called the diversity factor (with rounding biased upwards in order to ensure strict monotonicity).
Let D be the diversity data of route R, and L be a link. We say that R interferes with L when one of the following is true:
When we announce R over L, we announce the interfering metric if R interferes with L, and the non-interfering metric otherwise.
The metric that Z3 yields is non-isotonic; hence, Z3 Babel does not necessarily converge to a set of minimum-metric routes. In fact, the set of minimum-metric routes might not even be a tree in the general case. The author believes that Z3 Babel converges to a Nash equilibrium, but this appears to be a difficult property to prove.