[Cu-wireless] ETX Protocol Spec
Bryan Cribbs
bdcribbs at ojctech.com
Fri Apr 9 18:38:27 CDT 2004
This is draft 1 of an ETX protocol specification.
$Id: etx 459 2004-04-09 23:10:11Z bdcribbs $
Introduction
This protocol is intended to provide the expected transmission
count (ETX) routing metric based on the work of the M.I.T.
Computer Science and Artificial Intelligence Laboratory [1],
and be used between routers on ad hoc wireless networks.
Protocol Description
The Expected Transmission Count (ETX) path metric is a simple,
proven routing path metric that favors high-capacity, reliable
links. The ETX metric is found from the proportion of beacons
sent but not received in both directions on a wireless link.
Each participant router broadcasts a beacon to its one hop
neighbors at a configurable interval. Each beacon contains
the protocol version, flags and a sequence number. The beacon
contains a list of the router's one hop neighbors. For each
neighbor a history of whether or not the beaconing router
received a beacon from this neighbor is included. The history
includes the last BITFIELD_LENGTH (32) of this neighbor's beacon
intervals. An optional set of extensions may be included. No
extensions exist at this time.
At a configurable interval, the cost of the link associated
with each peer is computed based on expected probability of
beacons to be transmitted and received. See Receiving Beacons
and Computing Link Costs.
Beacon Flags
ETX_F_INIT - this flag MUST be set for the first BITFIELD_LENGTH
transmissions made by an ETX router. It is used to
distinguish sequence number wrap-around. See Sending
Beacons and Receiving Beacons.
ETX_F_EXTENSIONS - indicates that a beacon contains extensions.
If set, each peer block in the beacon MUST contain at least
one extension block. See Extensions.
ETX_F_SUSPEND - May be set by a router to indicate that it will
be out of communication for some length of time. If set,
the beacon MUST contain the 32-bit time of return field.
See Transmitting Beacons.
Receiving Beacons
Upon receiving a beacon it is implicitly required that certain
data must be available in order for the router to conform to
the protocol. For example it is necessary to have accurate
expectations regarding the arrival of future beacons from this
neighbor.
When beacons are received from a previously unheard of neighbor,
the data for the new neighbor are initialized appropriately.
It is added to the neighbor list and the contents of the bit
field are processed in full (dependent on the ETX_F_INIT flag).
If the beacon is from a neighbor that is already known, its
sequence number is compared to the sequence number of the last
beacon received from this neighbor. If the sequence number of
the received beacon is less than or equal to the most recently
received sequence number these statistics are recorded for MIB.
If the sequence number of the received beacon is within
BITFIELD_LENGTH intervals of the last heard sequence number,
the previous bits of the affected bits in hte bitfield are set
accordingly.
The sequence number of the incoming beacon is compared to the
currently expected sequence number from this neighbor. If it
is less or more than expected these statistics are recorded
for MIB. The bitfield is updated with the available data.
A sequentially valid beacon is processed as follows. Each
sequence number that has passed since the last beacon received
from this neighbor it is inferred that no beacon was received.
Beacon received is set for the current beacon interval. This
updated bitfield is used to recompute the probability of beacons
being received from this peer. See Computing Link Costs.
Additionally, we expect that the received beacon will contain
a peer block for the localhost. The bitfield from this block
is used to recompute the probability of beacons being transmitted
to this peer. See Computing Link Costs.
Transmitting Beacons
At each beacon interval, the router must assemble and broadcast
a beacon to its one-hop neighbors. The sequence number MUST
start at 0 and be incremented by exactly 1 with each beacon
transmitted. The ETX_F_INIT flag MUST be set for the initial
BITFIELD_LENGTH beacons transmitted.
For each known neighbor a valid bitfield must be determined.
If a beacon was expected but not received, the bitfield must
be updated accordingly (an expected and received beacon will
have already been processed). If this neighbors beacon interval
is longer than the local beacon interval, the bitfield should
not be updated until the neighbor beacon interval has expired.
If the neighbor interval is shorter than the local interval,
the extra bits of the bitfield must be evaluated (if these
beacons have been received, they will already be set correctly).
Computing Link Costs
Periodically, the data of known peers is used to compute the
cost associated with the link to that peer. To do so, smoothed
probability ratings of transmission to and reception from each
peer are used. Let 'srxp_k' and 'stxp_k' represent these
respective probabilities for some peer at interval 'k'.
The cost of the link with this peer is computed as
1
cost_k = -----------------------------
1 / srxp_k * 1 / stxp_k
The probability of receiving from this peer is computed as
Let srxp_0 = rx_0
srxp_k = h * srxp_k-1 + (1-h) * rx_k
where rx_k = 1 if a beacon was received, 0 otherwise.
The values of rx_k are read from the bitfield associated with this
peer. 'h' is a configurable value that specifies the influence of a
single interval on the probability.
The probability of transmitting to this peer may be computed
in the same manner, in this case the values of tx_k are read
from the peer block corresponding to the localhost in the beacon
received from this peer.
It is possible that no tx data is available for a number of reasons:
1) a beacon was not received from this peer. A configurable
tentative value is used for tk_k. If this beacon is received
late, the actual value must be substituted in at that time.
2) the received beacon did not contain a peer block referring to the
receiver. The value of tk_k = 0 is used.
3) the beacon's ETX_F_INIT flag is set and the 'k' interval is not
yet valid (as determined by the sequence nubmer). This interval
should not be included in computing the link cost.
For efficiency it is not desirable to recompute the probabilities
at every BEACON_INTERVAL. The following formula may be used
to include several intervals in a single recomputation
Let srxp_0 = rx_0
k
srxp_k = h^k * rx_0 + (1-h) * Sum( h^(k-i) * rx_i )
i=1
Beacon Format
An ETX beacon consists of a 32-bit header, containing an 8-bit
version number, 8-bit flags, 12-bit sequence number, and 4-bit
beacon interval. The beacon interval is specified in "log-seconds".
Meaning, it is a twos-complement integer, range [-8, 7], and the
actual beacon interval is 2^n. The version number is 0.
If and only if the ETX_F_GLOBAL_EXTENSIONS flag is set, the header
includes a global extensions block. The format is identical to the
Peer extension blocks described below. No global extensions exist
at this time.
If and only if the ETX_F_SUSPEND flag is set the header includes
by a 32-bit field containing the expected time to return, in
multiples of the beacon interval. The value of 0 indicates
unspecified time, perhaps never.
The remainder of the beacon consists of one or more ETX peer blocks.
An ETX peer block consists of the 128-bit IPv6 address of the peer.
IPv4 addresses are encoded as v6 addresses. The address is followed
by the bitfield (32-bit) for the peer. In the bitfield, the least
significant bit is always most recent. During the ETX_F_INIT stage,
the most significant bits are set to zero and are not used. If and
only if the ETX_F_EXTENSIONS flag is set in the beacon header, the
peer block concludes with one or more ETX Extension blocks.
An ETX Extensions block consists of a 16-bit extensions-used
bitmask, and a 16-bit field indicating the length of the
extension block. To allow for more than 16 extensions, the
most significant bit in the extensions-used bitmask is reserved
to indicate another extension block follows.
Beacon Diagram
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version # | Flags | Sequence Number | int |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
( Global Extensions Bitmask | Global Extensions Length )
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
( Time expected to return, iff ETX_F_SUSPEND flag is set. )
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+- -+
+- IPV6 address (ipv4 padded to ipv6) -+
+- -+
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bitfield |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
( Extensions Used Bitmask | Length of Extensions Block )
(-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-)
( ....... )
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+- -+
+- IPV6 address (ipv4 padded to ipv6) -+
+- -+
| ....... |
Beacon Flags
0x0001 ETX_F_INIT
0x0002 ETX_F_EXTENSIONS
0x0004 ETX_F_SUSPEND
0x0008 ETX_F_SECURE
0x0010 ETX_F_GLOBAL_EXTENSIONS
Extensions Bitmask
0x8000 ETX_E_MORE_EXTENSIONS
Global Extensions Bitmask
0x8000 ETX_E_MORE_EXTENSIONS
Management Information Base
Beacon Interval - specifies how frequently this router transmits
a beacon. It is not necessary that all routers use the same
interval. Valid range is [ 2^(-8), 3^7 ].
Link Compute Interval - specifies how frequently this router
recomputes link costs. No range limits apply. This parameter
does not affect interoperability with other routers.
Hysteresis - This value controls the impact of a single interval
when computing the smoothed probabilities of transmitting to and
receiving from each peer. See Computing Link Weights.
Statistics - statistics of abnormal or unexpected behaviour are
available to the MIB. See Receiving Beacons.
Security Considerations
At this time, ETX has no authentication and no confidentiality which
presents certain vunerabilities. For example, a malicious or faulty
router could transmit beacons that cause false link costs to be
calculated. The mechanism of global extensions (see Beacon Format)
may be used in future revisions to sign beacons.
References
[1] D. Decouto, D. Aguayo, J. Bicket, and R. Morris,
"A high-throughput path metric for multi-hop wireless networks",
in Proceedings of MobiCom, 2003.
vim: tw=72 ai
$Id: etx 459 2004-04-09 23:10:11Z bdcribbs $
More information about the CU-Wireless
mailing list