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.3 2001/07/22 14:58:18 guus Exp $
+ $Id: CONNECTIVITY,v 1.1.2.5 2001/07/22 17:41:52 guus Exp $
1. Problem
==========
D sends ADD_HOST(E) to A
D sends ADD_HOST(F) to A
- 2 A receives ADD_HOST(E) from D:
+ 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(E) from A:
+ 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(E) from B.
+ 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.
F sends ADD_HOST(D) to C
F sends ADD_HOST(E) to C
- 2 A receives ADD_HOST(E) from D:
+ 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(E) from A:
+ 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 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>
- B receives ADD_HOST(F) from C, and notes that is is already known:
+ 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(E) from B, and notes that it is already known:
+ 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>
<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