2a893ff7c5ca8433f59026b9f76a7966d722d6bf
[oweals/tinc.git] / doc / CONNECTIVITY
1 This document describes how nodes in a VPN find and connect to eachother and
2 maintain a stable network.
3
4    Copyright 2001 Guus Sliepen <guus@sliepen.warande.net>
5
6    Permission is granted to make and distribute verbatim copies of
7    this documentation provided the copyright notice and this
8    permission notice are preserved on all copies.
9
10    Permission is granted to copy and distribute modified versions of
11    this documentation under the conditions for verbatim copying,
12    provided that the entire resulting derived work is distributed
13    under the terms of a permission notice identical to this one.
14
15    $Id: CONNECTIVITY,v 1.1.2.2 2001/07/22 14:46:11 guus Exp $
16
17 1. Problem
18 ==========
19
20 We have a set of nodes (A, B, C, ...) that are part of the same VPN. They need
21 to connect to eachother and form a single graph that satisfies the tree
22 property.
23
24 There is the possibility that loops are formed, the offending connections must
25 be eliminated.
26
27 Suppose we start with two smaller graphs that want to form a single larger
28 graph. Both graphs consist of three nodes:
29
30   A-----B-----C
31   
32   
33
34   D-----E-----F
35   
36 It is very well possible that A wants to connect to D, and F wants to connect
37 to C, both at the same time. The following loop will occur:
38
39   A-----B-----C
40   |           ^
41   |           |
42   v           |
43   D-----E-----F
44
45 The situation described here is totally symmetric, there is no preference to
46 one connection over the other. The problem of resolving the loop, maintaining
47 consistency and stability is therefore not a trivial one.
48
49 What happens when A---D and C---F are connected to eachother? They exchange
50 lists of known hosts. A knows of B and C, and D knows of E and F. The protocol
51 defines ADD_HOST messages, from now on we will say that "node X sends and
52 ADD_HOST(Y) to Z".
53
54 There are two possible scenarios: either both A---D and C---F finish
55 authentication at the same time, or A---D finishes first, so that ADD_HOST
56 messages will reach C and F before they finish authentication.
57
58 1.1 A---D finishes first
59 ------------------------
60
61 After A---D authentication finishes the following actions are taken:
62
63   1 A sends ADD_HOST(B) to D
64     A sends ADD_HOST(C) to D
65     D sends ADD_HOST(E) to A
66     D sends ADD_HOST(F) to A
67
68   2 A receives ADD_HOST(E) from D:
69       A sends ADD_HOST(E) to B
70     A receives ADD_HOST(F) from D:
71       A sends ADD_HOST(F) to B
72     D receives ADD_HOST(B) from A:
73       D sends ADD_HOST(B) to E
74     D receives ADD_HOST(C) from A:
75       D sends ADD_HOST(C) to E
76
77   3 B receives ADD_HOST(E) from A:
78       B sends ADD_HOST(E) to C
79     B receives ADD_HOST(F) from A:
80       B sends ADD_HOST(F) to C
81     E receives ADD_HOST(B) from D:
82       E sends ADD_HOST(B) to F
83     E receives ADD_HOST(C) from D:
84       E sends ADD_HOST(C) to F
85
86   4 C receives ADD_HOST(E) from B.
87     C receives ADD_HOST(F) from B.
88     F receives ADD_HOST(B) from E.
89     F receives ADD_HOST(C) from E.
90
91 Then C---F authentication finishes, the following actions are taken:
92
93   1 C notes that F is already known:
94       Connection is closed.
95     F notes that C is already known:
96       Connection is closed.
97
98 1.2 Both A---D and C---F finish at the same time.
99 -------------------------------------------------
100
101   1 A sends ADD_HOST(B) to D
102     A sends ADD_HOST(C) to D
103     D sends ADD_HOST(E) to A
104     D sends ADD_HOST(F) to A
105     
106     C sends ADD_HOST(A) to F
107     C sends ADD_HOST(B) to F
108     F sends ADD_HOST(D) to C
109     F sends ADD_HOST(E) to C
110
111   2 A receives ADD_HOST(E) from D:
112       A sends ADD_HOST(E) to B
113     A receives ADD_HOST(F) from D:
114       A sends ADD_HOST(F) to B
115     D receives ADD_HOST(B) from A:
116       D sends ADD_HOST(B) to E
117     D receives ADD_HOST(C) from A:
118       D sends ADD_HOST(C) to E
119
120     C receives ADD_HOST(D) from F:
121       A sends ADD_HOST(D) to B
122     C receives ADD_HOST(E) from F:
123       A sends ADD_HOST(E) to B
124     F receives ADD_HOST(A) from C:
125       D sends ADD_HOST(A) to E
126     F receives ADD_HOST(B) from C:
127       D sends ADD_HOST(B) to E
128
129   3 B receives ADD_HOST(E) from A:
130       B sends ADD_HOST(E) to C
131     B receives ADD_HOST(F) from A:
132       B sends ADD_HOST(F) to C
133     E receives ADD_HOST(A) from D:
134       E sends ADD_HOST(A) to F
135     E receives ADD_HOST(B) from D:
136       E sends ADD_HOST(B) to F
137     
138     B receives ADD_HOST(E) from C, and notes that is is already known:
139       <insert solution here>
140