[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 $


    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

    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 

    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

    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
	    srxp_k = h^k * rx_0 + (1-h) * Sum( h^(k-i) * rx_i )

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
	0x0008 ETX_F_SECURE

    Extensions Bitmask


    Global Extensions Bitmask


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.


    [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