Bridge loop avoidance protocol description

Further pages on this topic:

Claim frames

image0

All claim operations are sent using “special” gratuitous ARP frames. 4 types are used which are illustrated above:

  • CLAIM frames are used to tell others that a backbone gateway feels responsible for a client now

  • UNCLAIM frames are sent when a backbone gateway does not feel responsible anymore

  • ANNOUNCE frames are sent regularly to find other backbone gateways and provides the CRC of its local table

  • REQUEST frames are used to ask for a full table update when the information is out of sync (i.e. the announced CRC does not match with the local CRC)

The claim type is announced within the 4th byte of the Target HW address.

Note: Although this is a misuse of ARP packets, the “normal” ARP process should not be disturbed as the IP addresses (0.0.0.0) should not be in any sane ARP table. As far as I understand, a gratuitous ARP should only be considered if the IP address is already in an ARP table [2].

[1] https://tools.ietf.org/html/rfc826 [2] https://tools.ietf.org/html/rfc2002#section-4.6

CLAIM frames

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet DST: FF:FF:FF:FF:FF:FF                            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet DST (cont)        |  Ethernet Source: client addr |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet SRC: client addr (cont)                           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet type: 08 06       |  HW type: 00 01               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Protocol type: 08 00       |  HW size: 06  | Prot size: 04 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Opcode: 02 = Reply         |  Sender HW addr: orig addr    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Sender HW addr: originator addr (cont)                     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Sender IP: 0.0.0.0                                         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Target HW addr: FF:43:05:00:XX:XX                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Target HW addr (cont)      | Target IP: 0.0.0.0            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Target IP: 0.0.0.0 (cont)  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

A CLAIM frame is sent when a new client is added to the local table and the backbone gateway wants to be responsible now.

Backbone gateways which receive a CLAIM frame (and accept the backbone gateway) must add the claim in their tables, replacing older claims if they are present (even their own).

UNCLAIM frames

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet DST: FF:FF:FF:FF:FF:FF                            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet DST (cont)        |  Ethernet Source: orig addr   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet SRC (originator addr, cont)                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet type: 08 06       |  HW type: 00 01               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Protocol type: 08 00       |  HW size: 06  | Prot size: 04 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Opcode: 02 = Reply         |  Sender HW addr: client addr  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Sender HW addr: client addr (cont)                         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Sender IP: 0.0.0.0                                         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Target HW addr: FF:43:05:01:XX:XX                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Target HW addr (cont)      | Target IP: 0.0.0.0            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Target IP: 0.0.0.0 (cont)  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

An UNCLAIM frame is sent when the backbone gateway is not responsible anymore, e.g. due to detected roaming into the backbone or a timeout

Backbone gateways which receive an UNCLAIM frame (and accept the backbone gateway) must remove the the claim from their tables.

ANNOUNCE frames

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
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |    Ethernet DST: FF:FF:FF:FF:FF:FF                            |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |    Ethernet DST (cont)        |  Ethernet Source: orig addr   |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |    Ethernet SRC (originator addr, cont)                       |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |    Ethernet type: 08 06       |  HW type: 00 01               |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |    Protocol type: 08 00       |  HW size: 06  | Prot size: 04 |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |    Opcode: 02 = Reply         |  Sender HW addr: ...          |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |    Sender HW addr: 43:05:43:05:YY:YY (cont)                   |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |    Sender IP: 0.0.0.0                                         |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |    Target HW addr: FF:43:05:02:XX:XX                          |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |    Target HW addr (cont)      | Target IP: 0.0.0.0            |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |    Target IP: 0.0.0.0 (cont)  |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The periodic ANNOUNCE frames (default: every 10 seconds) by the backbone gateways serve the following purposes:

  • backbone gateways learn about the existence of other backbone gateways (this is important for new gateways)

  • when no ANNOUNCE frames are received anymore, we can assume that this backbone gateway is no longer serving the backbone and can remove its claims

  • It contains a checksum (the last 2 bytes YY:YY within the Sender HW address) which other backbone gateways can use to check their table consistency. If a table is not consistent, a backbone gateway can ask for the full claim table via the REQUEST frame.

Note: the SRC HW address is a “locally administered address” group address which should not be used by any NIC or protocol, but is not registered with the IEEE

REQUEST frame

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet DST: Gateways addr                                |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet DST (cont)        |  Ethernet Source: orig addr   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet SRC (originator addr, cont)                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet type: 08 06       |  HW type: 00 01               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Protocol type: 08 00       |  HW size: 06  | Prot size: 04 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Opcode: 02 = Reply         |  Sender HW addr: gw addr      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Sender HW addr: gateway addr (cont)                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Sender IP: 0.0.0.0                                         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Target HW addr: FF:43:05:03:XX:XX                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Target HW addr (cont)      | Target IP: 0.0.0.0            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Target IP: 0.0.0.0 (cont)  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

A REQUEST frame is sent by a backbone gateway who just received an ANNOUNCE frames and discovers that the CRC is out of sync.

It then sends a REQUEST frame to the backbone gateway it just received the ANNOUNCE frame from, and deletes all claims it knows from this backbone gateway.

The asked backbone gateway will send all of its local CLAIM frames again, and send another ANNOUNCE frame afterwards.

The requesting backbone gateway will add all claims it receives through the CLAIM frames, and can check the CRC once more as soon as it receives the final ANNOUNCE frame. (If the CRC is still wrong, the process will start again)

While a request is in flight, the requesting backbone gateway will close down its soft-interface for broadcast to avoid loops in this period.

LOOP DETECT frame

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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet DST: FF:FF:FF:FF:FF:FF                            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet DST (cont)        |  Ethernet Source: orig addr   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet SRC (originator addr, cont)                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Ethernet type: 08 06       |  HW type: 00 01               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Protocol type: 08 00       |  HW size: 06  | Prot size: 04 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Opcode: 02 = Reply         |  Sender HW addr: orig addr    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Sender HW addr: originator addr (cont)                     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Sender IP: 0.0.0.0                                         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Target HW addr: FF:43:05:05:XX:XX                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Target HW addr (cont)      | Target IP: 0.0.0.0            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Target IP: 0.0.0.0 (cont)  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

A LOOP DETECT frame is sent every 60 seconds to detect loop scenarios which can’t be avoided by BLA-II (see Bridge-loop-avoidance-II#Limitations).

The Ethernet source MAC address has the first two octets set to BA:BE, and the following octets are randomized and changed with every sent packet. The packet will be sent to LAN first, and in contrast to other packet types, other nodes will be forwarded into the mesh. If a LOOP DETECT packet is received from the mesh (which is only processed if the sending originator is not in the same BLA group), and the randomized Ethernet Source MAC matches the own one, an event is thrown. This can be handled by userspace to react to the loop scenario, e.g. by disabling interfaces.

group forming

Within the “Target HW address”, the last 2 bytes XX:XX are used for as a local group identifier.

After starting batman, these bytes are initialized with the CRC16 checksum of the local mac address. Once it receives a claim frame from another backbone gateway which is also known through the mesh, the own group identifier is copied from this other backbone gateway when it is bigger than the own one. Due to this mechanism, after a short period all mesh nodes who are participating in the same mesh share the same group id.

Generally, claim frames are only accepted if they are on the same group (e.g. participating on the same mesh). This helps for some network scenarios, e.g. when multiple different meshes are connected to one shared backbone (see two meshes test setup below).