[Babel-users] Babel 2 protocol draft
jch
jch at pps.jussieu.fr
Thu Oct 9 10:16:15 UTC 2008
Hi,
I'm attaching the current state of the new Babel protocol spec. Let
me know if you find anything stupid.
Juliusz
The Babel Routing Protocol version 2
Top-secret ultra-confidential draft
Juliusz Chroboczek
<jch at pps.jussieu.fr>
9 October 2008
Differences from Babel 1
************************
There is only one major conceptual difference between Babel 1 and Babel 2:
associations are now between pairs of interfaces and not between pairs of
routers. This means that the neighbour table no longer contains any router
ids, that Hello messages no longer contain a router id, and that IHU
messages now carry a link-local address rather than a router id.
There is one new facility in the protocol, the ability to send a message
reliably. This facility is optional -- a node need not send any reliable
messages, but a node must be able to acknowledge a message that requests an
acknowledgement. This facility allows a more efficient implementation of
``important'' messages, and may in the future allow implementations of
Babel that are useful over reasonably reliable but very expensive and
intermittently available links (think GPRS, ISDN, X.25 or other telecom-
derived nonsense).
Updates now carry an explicit update interval. This means that the hold
time no longer needs to be hard-wired. (This is not very important, since
Babel normally uses reliable explicit retractions, but it doesn't harm
much.)
Unlike Babel 1, which can only run over IPv6, Babel 2 can run over IPv4 or
IPv6. (Of course, both Babel 1 and Babel 2 can carry IPv4 and IPv6 routes,
whatever protocol they are transported over.) Babel 2 should be able to
accomodate other underlying protocols (even raw Ethernet) with only minor
changes.
Router ids are now just 8 bytes, in modified EUI-64 format. The
router_hash hack is gone, request messages now carry the full router id.
Since the above changes require an incompatible revision of the protocol,
I've completely redesigned the packet format. Rather than using
fixed-length messages, the new format uses variable length messages, and
omits common prefixes from IPv6 addresses. It is about two times as
compact as the old format, both for IPv4 and for IPv6.
Data structures
***************
Interval
--------
Relative times are carried as two-octet values specifying a number of
centiseconds. This gives times going up to roughly 11 minutes with
a granularity of 10ms, which should cover all possible applications of
Babel.
router id
---------
A router id is an arbitrary 8-octet value. Router ids should be assigned
in modified EUI-64 format.
Address
-------
Since the bulk of the protocol is taken by addresses, three address
encodings are defined. Additionally, a common subnet prefix may be omitted
from adresses -- this is known as address compression. (The idea is taken
from the manet-packetbb draft, which I hereby gratefully acknowledge.)
Address encodings:
AE 0. Wildcard address. The value is 0 octets long.
AE 1. IPv4 address. Compression is allowed. 4 octets or less.
AE 2. IPv6 address. Compression is allowed. 16 octets or less.
AE 3. Link-local IPv6 address. 8 octets long, a prefix of fe80::/64 is
implied.
Prefixes
--------
A network prefix is encoded just like a network address, but it is encoded
using the smallest number of octets that are enough to encode the prefix
length.
Packet format
*************
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Magic | Version | Body length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Body ...
+-+-+-+-+-+-+-+-+-+-+-+-+-
Magic is 42. Version is 2. Body length is the length of the body, in
octets. Body is a sequence of messages.
Any data beyond the body length MUST be silently ignored.
Messages
--------
With the exception of Pad1, all messages have the following structure:
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 | Length | Body...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
Type identifies the kind of message. Length is the length of the body.
Body depends on the message type.
Messages longer than the expected length for a given type of message must
be accepted, and the extra data silently ignored.
0. Pad1
-------
0
0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+
| Type = 0 |
+-+-+-+-+-+-+-+-+
Ignored upon reception.
1. Padn
-------
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 = 1 | Length | MBZ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
Ignored upon reception.
2. Acknowledgment request
-------------------------
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 | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Nonce | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Requests that the receiving node send an Acknowledgment message within
Interval centiseconds.
3. Acknowledgment
-----------------
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 = 3 | Length | Nonce |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The nonce is copied from the Acknowledgment request.
Note that since nonces are not globally unique, and Acks do not contain
a destination address, they must be sent over unicast. This means that
they cannot be aggregated across routers.
4. Hello
--------
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 = 4 | Length | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Seqno | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This message may only be sent over multicast.
5. IHU
------
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 = 5 | Length | AE | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Txcost | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address...
+-+-+-+-+-+-+-+-+-+-+-+-
IHUs carry a link-local address.
AE should be 1 or 3 in most cases. However, if an IHU is sent using
unicast, or if bidirectional reachability is checked by other means, then
it may use an AE of 0.
6. Router id
------------
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 = 6 | Length | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Router id +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This sets the implied router id for the following update packets.
7. next hop
-----------
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 = 7 | Length | AE | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next hop...
+-+-+-+-+-+-+-+-+-+-+-+-
This sets the implied next hop for the following update packets. It is not
needed when a route's address family matches the packet's transport, in
which case the packet's sender address is used instead.
This is not suitable for third-party announcements, since the metric is
still computed suitably for the sender.
8. Update
---------
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 = 8 | Length | AE | Flags |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Plen | Omitted bytes | Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Seqno | Metric |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix...
+-+-+-+-+-+-+-+-+-+-+-+-
Flag 0x80 specifies that the default prefix for the given address family
should be set to the prefix (after decompression). Flag 0x40 specifies
that the router id should be set to the low 64 bits of the prefix. The
other flags are reserved, must be sent as 0 and silently ignored on
reception.
Interval is the maximum time after which this announcement will be
repeated. The value 0xFFFF (infinity) means that this announcement will
not be repeated, the value 0 is reserved.
Omitted bytes is the number of leading bytes that should be taken from the
default prefix and prepended to the prefix.
9. Single-hop request
----------------------
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 = 9 | Length | AE | Plen |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix...
+-+-+-+-+-+-+-+-+-+-+-+-
AE=0 specifies a request for a full routing table dump. Other values of AE
specify a request for a single route.
10. Multi-hop request
---------------------
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 = 10 | Length | AE | Plen |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| seqno | hop count | reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Router id +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Prefix...
+-+-+-+-+-+-+-+-+-+-+
AE=0 is not allowed.
Hop count is decremented on reception; messages with hop count of 0 must
not be sent. Requests a new route either from the same router with seqno
at least the value specified, or from a different router, in which case
seqno is irrelevant.
Local Variables:
fill-column: 75
End:
More information about the Babel-users
mailing list