provided that the entire resulting derived work is distributed
under the terms of a permission notice identical to this one.
- $Id: CONNECTIVITY,v 1.1.2.1 2001/07/22 14:04:38 guus Exp $
+ $Id: CONNECTIVITY,v 1.1.2.5 2001/07/22 17:41:52 guus Exp $
1. Problem
==========
The situation described here is totally symmetric, there is no preference to
one connection over the other. The problem of resolving the loop, maintaining
consistency and stability is therefore not a trivial one.
+
+What happens when A---D and C---F are connected to eachother? They exchange
+lists of known hosts. A knows of B and C, and D knows of E and F. The protocol
+defines ADD_HOST messages, from now on we will say that "node X sends and
+ADD_HOST(Y) to Z".
+
+There are two possible scenarios: either both A---D and C---F finish
+authentication at the same time, or A---D finishes first, so that ADD_HOST
+messages will reach C and F before they finish authentication.
+
+1.1 A---D finishes first
+------------------------
+
+After A---D authentication finishes the following actions are taken:
+
+ 1 A sends ADD_HOST(B) to D
+ A sends ADD_HOST(C) to D
+ D sends ADD_HOST(E) to A
+ D sends ADD_HOST(F) to A
+
+ 2 A sends ADD_HOST(D) to B
+ A receives ADD_HOST(E) from D:
+ A sends ADD_HOST(E) to B
+ A receives ADD_HOST(F) from D:
+ A sends ADD_HOST(F) to B
+ D sends ADD_HOST(A) to E
+ D receives ADD_HOST(B) from A:
+ D sends ADD_HOST(B) to E
+ D receives ADD_HOST(C) from A:
+ D sends ADD_HOST(C) to E
+
+ 3 B receives ADD_HOST(D) from A,
+ B sends ADD_HOST(D) to C
+ B receives ADD_HOST(E) from A:
+ B sends ADD_HOST(E) to C
+ B receives ADD_HOST(F) from A:
+ B sends ADD_HOST(F) to C
+ E receives ADD_HOST(A) from D:
+ E sends ADD_HOST(A) to F
+ E receives ADD_HOST(B) from D:
+ E sends ADD_HOST(B) to F
+ E receives ADD_HOST(C) from D:
+ E sends ADD_HOST(C) to F
+
+ 4 C receives ADD_HOST(D) from B.
+ C receives ADD_HOST(E) from B.
+ C receives ADD_HOST(F) from B.
+ F receives ADD_HOST(A) from E.
+ F receives ADD_HOST(B) from E.
+ F receives ADD_HOST(C) from E.
+
+Then C---F authentication finishes, the following actions are taken:
+
+ 1 C notes that F is already known:
+ Connection is closed.
+ F notes that C is already known:
+ Connection is closed.
+
+1.2 Both A---D and C---F finish at the same time.
+-------------------------------------------------
+
+ 1 A sends ADD_HOST(B) to D
+ A sends ADD_HOST(C) to D
+ D sends ADD_HOST(E) to A
+ D sends ADD_HOST(F) to A
+
+ C sends ADD_HOST(A) to F
+ C sends ADD_HOST(B) to F
+ F sends ADD_HOST(D) to C
+ F sends ADD_HOST(E) to C
+
+ 2 A sends ADD_HOST(D) to B
+ A receives ADD_HOST(E) from D:
+ A sends ADD_HOST(E) to B
+ A receives ADD_HOST(F) from D:
+ A sends ADD_HOST(F) to B
+ D sends ADD_HOST(A) to E
+ D receives ADD_HOST(B) from A:
+ D sends ADD_HOST(B) to E
+ D receives ADD_HOST(C) from A:
+ D sends ADD_HOST(C) to E
+
+ C sends ADD_HOST(F) to B
+ C receives ADD_HOST(D) from F:
+ A sends ADD_HOST(D) to B
+ C receives ADD_HOST(E) from F:
+ A sends ADD_HOST(E) to B
+ F sends ADD_HOSTS(C) to E
+ F receives ADD_HOST(A) from C:
+ D sends ADD_HOST(A) to E
+ F receives ADD_HOST(B) from C:
+ D sends ADD_HOST(B) to E
+
+ 3 B receives ADD_HOST(D) from A,
+ B sends ADD_HOST(D) to C
+ B receives ADD_HOST(E) from A:
+ B sends ADD_HOST(E) to C
+ B receives ADD_HOST(F) from A:
+ B sends ADD_HOST(F) to C
+ E receives ADD_HOST(A) from D:
+ E sends ADD_HOST(A) to F
+ E receives ADD_HOST(B) from D:
+ E sends ADD_HOST(B) to F
+ E receives ADD_HOST(C) from D:
+ E sends ADD_HOST(C) to F
+
+ B receives ADD_HOST(F) from C, and notes that is is already known:
+ <insert solution here>
+ B receives ADD_HOST(D) from C, and notes that is is already known:
+ <insert solution here>
+ B receives ADD_HOST(E) from C, and notes that is is already known:
+ <insert solution here>
+ E receives ADD_HOST(C) from F, and notes that is is already known:
+ <insert solution here>
+ E receives ADD_HOST(A) from F, and notes that is is already known:
+ <insert solution here>
+ E receives ADD_HOST(B) from F, and notes that is is already known:
+ <insert solution here>
+
+ 4 A receives ADD_HOST(D) from B, and notes that it is already known:
+ <insert solution here>
+ A receives ADD_HOST(E) from B, and notes that it is already known:
+ <insert solution here>
+ A receives ADD_HOST(F) from B, and notes that it is already known:
+ <insert solution here>
+ F receives ADD_HOST(A) from E, and notes that it is already known:
+ <insert solution here>
+ F receives ADD_HOST(B) from E, and notes that it is already known:
+ <insert solution here>
+ F receives ADD_HOST(B) from E, and notes that it is already known:
+ <insert solution here>
+
+ ...
+
+1.2.1 Augmenting ADD_HOST
+-------------------------
+
+A solution would be to augment ADD_HOST with an extra parameter, the nexthop of
+the added host:
+
+ 3 B receives ADD_HOST(D,A) from A,
+ B sends ADD_HOST(D,A) to C
+ B receives ADD_HOST(E,D) from A:
+ B sends ADD_HOST(E,D) to C
+ B receives ADD_HOST(F,E) from A:
+ B sends ADD_HOST(F,E) to C
+ E receives ADD_HOST(A,D) from D:
+ E sends ADD_HOST(A,D) to F
+ E receives ADD_HOST(B,A) from D:
+ E sends ADD_HOST(B,A) to F
+ E receives ADD_HOST(C,B) from D:
+ E sends ADD_HOST(C,B) to F
+
+ B receives ADD_HOST(F,C) from C, and notes that F is already known:
+ <insert solution here>
+ B receives ADD_HOST(D,E) from C, and notes that D is already known:
+ <insert solution here>
+ B receives ADD_HOST(E,F) from C, and notes that E is already known:
+ <insert solution here>
+ E receives ADD_HOST(C,F) from F, and notes that C is already known:
+ <insert solution here>
+ E receives ADD_HOST(A,B) from F, and notes that A is already known:
+ <insert solution here>
+ E receives ADD_HOST(B,C) from F, and notes that B is already known:
+ <insert solution here>
+
+So, B and E have to make a choice. Which ADD_HOST is going to win? Fortunately,
+since the ADD_HOST messages are augmented, they have an extra piece of
+information they can use to decide in a deterministic way which one is going to
+win. For example, B got ADD_HOST(F,E) and ADD_HOST(F,C). Since "E" > "C", it
+could let ADD_HOST(F,E) win.
+
+ B receives ADD_HOST(F,C) from C, and notes that F is already known:
+ since "C" < "E", B ignores ADD_HOST(F,E)
+ B sends ADD_HOST(F,C) to A
+ ...
+ E receives ADD_HOST(C,F) from F, and notes that C is already known:
+ since "F" > "B", E removes the ADD_HOST(C,B) in favour of the new one
+ E sends ADD_HOST(C,F) to D
+
+ 4 A receives ADD_HOST(F,E) from B, and notes that F is already known:
+ since "E" < "D", A ignores ADD_HOST(F,D).
+ ...
+ D receives ADD_HOST(C,F) from E, and notes that C is already known:
+ since "F" > "B", D removes the ADD_HOST(C,B),
+ closes the connection with C, in favour of the new one.
projects / tinc / blobdiff