Repository : ssh://git@open-mesh.org/doc

On branches: backup-redmine/2017-07-13,master

commit d78152a7d27628e2280f66a882d6e15ea8f0cdc5 Author: Simon Wunderlich sw@simonwunderlich.de Date: Wed Jun 8 23:26:28 2011 +0000

doc: batman-adv/Bridge-loop-avoidance-II

d78152a7d27628e2280f66a882d6e15ea8f0cdc5 batman-adv/Bridge-loop-avoidance-II.textile | 144 ++++++++++++++++++++++++++++ 1 file changed, 144 insertions(+)

diff --git a/batman-adv/Bridge-loop-avoidance-II.textile b/batman-adv/Bridge-loop-avoidance-II.textile new file mode 100644 index 00000000..a74bded2 --- /dev/null +++ b/batman-adv/Bridge-loop-avoidance-II.textile @@ -0,0 +1,144 @@ +h1. Bridge loop avoidance II + +This page contains a concept in progress, it is not implemented yet, but feel free to discuss it. + +h2. Goals: + + * Should be able to scale + * Communication between meshnodes and LAN should be via the best gateway + * Minimize Broadcast Traffic in the LAN + * Roaming should still be possible + +h2. Definitions: + + + * Gateway: A mesh node which is conncted to both a mesh and a LAN + * Client: A non-mesh network participant which is sending data via the mesh. The Client is always identified by the Source MAC address of the payload Ethernet header. + +h2. Key Concepts: + +h3. Claims: + +Only one gateway (out of possibly many gateways) should serve a client from the mesh for the LAN. This is announced by sending "claim packets" on the soft-interface bat0. A "claim packet" contains a list of MAC addresses the gateway feels responsible for. Each gateway will save the claim list of other gateways. By doing this, it can: + + * see which clients are already tracked (claimed) + * see which other gateways exist in the LAN + +Note that gateways may overwrite a claim of another gateway by simply claiming the same client. In this case, the newest claim wins, and local databases are updated accordingly. + +Gateways can also "unclaim" their own clients. After doing this, the client is not claimed anymore for this LAN. + +h3. Duplicate list: + +To track duplicate Ethernet frames without meta information (like sequence numbers, etc), broadcast packets are checksummed. A node keeps a list of the last N checksums of frames. A new frame can be matched by checksumming it and check for matches in the list. + +Two different duplicate lists are kept in the concept: + + * mesh duplicate list: This list is kept for every gateway mesh node which is connected to a LAN with multiple gateways. It checks broadcast packets which are sent from the LAN into the mesh through multiple gateways (and thus multiple times). + * LAN duplicate list: This is a single list. It tracks broadcast packets which were sent from the mesh through the soft interface into the LAN. + +h2. Details and Cases: + +The concept will be explained by discussing the different cases: unicast and broadcast frames, both for the LAN->mesh and mesh->LAN case. Loop cases are considered too: LAN->mesh->LAN +and mesh->LAN->mesh. Furthermore, roaming is discussed when a client changes from the LAN to another mesh node and back. + +h3. Broadcast, mesh->LAN: + +If the originator of the broadcast is another gateway from the same LAN, drop it immediately. + +If a gateway has already claimed the client, only the resposible gateway will deliver the frame to the bridge. Other gateways will discard the packet. + +If no gateway has claimed the client, the gateway(s) will race for the claim: + + * check if a claim is present (we assumed there is none) + * wait for a short, random time + * check again if any other gateway has claimed in the meantime. If yes, drop it. + * send a claim packet including the new client + * deliver the Broadcast frame to the soft-interface + +The random backoff is used to avoid the race conditions when the packet is delivered from the mesh by multiple gateways at the same time. + +For every broadcast frame delivered into the LAN, add an entry in the LAN duplicate list. This is used for loop detection and roaming. + +h3. Unicast, mesh->LAN: + +If the client is not claimed by the gateway receiving the unicast, a claim packet is sent out first. This gateway is now the (new) responsible gateway for this client. + +Then, the unicast packet is delivered to the soft interface. + +h3. Broadcast, LAN->mesh: + +If the client is claimed, all not responsible gateways should discard the frame - this might be a loop. The responsible gateway shall check its LAN duplicate list - if the frame matches, it is a frame he sent out by himself (and received due to bad drivers or stupid switches). In this case, discard it. If the packet does not match, it might be sent from a client which just roamed into our LAN. In this case, "unclaim" this client by sending an according claim packet, and forward the packet into the mesh. + +If the client is not claimed by any gateway, every gateway shall forward the packet into the mesh. This will lead to duplicates of the broadcast with different meta information (different originators, different sequence numbers). To avoid duplicates within the mesh, every mesh node will use the "mesh duplicate list": + + * after the (old) seqno window check: match the frame to the "mesh duplicate list" of other gateways to see if another gateway from the same LAN has sent a broadcast with the same payload checksum. + * if true, drop the packet. Otherwise, add the checksum to the entries and re-forward it. + +(Note that it might be neccesary to connect the checksums to sequence numbers to allow intentionally sent duplicate payload broadcasts) + +h3. Unicast, LAN->mesh: + +Nothing fancy should happen here, as a switch should do the right thing. If the client is not claimed, the frame is simply sent into the mesh. + +However, when using hubs (or broken switches), also unicast packets might loop. Therefore, if the client is claimed by any gateway, drop it. + +h3. mesh->LAN->mesh loop: + +A broadcast frame is only sent to LAN by the (yet to be) responsible gateway. Back from the LAN to the mesh, all not responsible gateway will drop the frame. The responsible gateway will also drop it as the packet is matched in the "LAN duplicate list". + +To avoid loops for hubs, unicast packets are dropped from LAN to mesh if the client is claimed. + +h3. LAN->mesh->LAN loop: + +Although a broadcast frame is sent into the mesh from different originators, it won't loop back into the LAN as a gateway will drop it if was sent from another gateway (from the same LAN). + +h3. LAN->mesh Roaming: + +This is the easy case: Sooner or later, a claim will be added for the roamed client. + +h3. mesh->LAN Roaming: + +We assume that the client was already claimed by a gateway before, otherwise there is nothing to consider. + +When a broadcast frame is sent, the responsible gateway can detect the roam: The frames checksum should not be in the "LAN duplicate list", as the frame is new and has not been sent by this gateway. The client will therefore be unclaimed. This first broadcast will only be broadcasted by the (previously) responsible gateway into the mesh, later broadcasts will be sent by all gateways again. + +Unicast frames are dropped, and the clients roaming will not be known as long as no broadcast frame is sent. This is a limitation. :( + +h3. Gateway selection: + +The gateways should announce the other gateways from their LAN, e.g. within TT/HNA messages. + +Other non-gateway meshnodes may then select their best gateway to the LAN based on the TQ value. They must also use this information to effectively detect duplicates from the LAN->mesh +case. + +h2. Discussion: + +h3. Features: + + * no single "super" gateway => should scale better + * the only additional BATMAN LAN packets are claim packets, which are only sent for new claims + * no encupsulated BATMAN packets on the LAN + * broadcasts are sent from all the gateways into the mesh + * nodes can select gateways, and change among them (gateways will automatically re-claiming) + * should not loop ;) + +h3. Limitations: + + * Roaming to the LAN with multiple gateways is slow when only unicast packets are used + * duplicate lists based on checksums may fail due to checksum collisions or out-of-list frames. This may lead to duplicates, loops and other ugly stuff. Therefore, the checksums should be wide and the lists should be long. :) + * quite complex concept + * other things I might have missed ... + +h3. Further ideas (from discussion on 2011-06-08): + + * What to do if a gateway fails? how do we timeout it? - we could change the concept to work like the new TT: regular updates of changes (with a sequence number), only send changes, and request full update if required. The regular update would allow us to timeout gateways if they are no longer there/connected. + * Not included in the concept is how we handle LAN-interconnected, separate mesh clouds. The gateways of the different mesh clouds would claim clients, which would prevent traffic going from mesh 1 to mesh 2. This could be solved by verifying that a gateway is not only accessible via LAN, but also via mesh (looking into the originator table). If they are not in our mesh, we ignore the claims. + * Instead of using the "mesh duplicate list", we could also try to synchronize the broadcast sequence numbers of the gateways, so that broadcasts are always sent with the same originator address + sequence number, appearing as the same broadcast. There may be a lot of side effects to consider (packet loss, racing packets, etc ...) + * some pictures to illustrate the concept would be nice :) + +h3. Agenda/Comments for next discussion + +Please add any comments for the next discussion here: + + * (still empty, please edit! now!) \ No newline at end of file