Use logging.h instead of syslog.h
[tinc] / 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-2002 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.2 2002/04/12 08:25:01 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 sends ADD_HOST(D) to B
69     A receives ADD_HOST(E) from D:
70       A sends ADD_HOST(E) to B
71     A receives ADD_HOST(F) from D:
72       A sends ADD_HOST(F) to B
73     D sends ADD_HOST(A) to E
74     D receives ADD_HOST(B) from A:
75       D sends ADD_HOST(B) to E
76     D receives ADD_HOST(C) from A:
77       D sends ADD_HOST(C) to E
78
79   3 B receives ADD_HOST(D) from A,
80       B sends ADD_HOST(D) to C
81     B receives ADD_HOST(E) from A:
82       B sends ADD_HOST(E) to C
83     B receives ADD_HOST(F) from A:
84       B sends ADD_HOST(F) to C
85     E receives ADD_HOST(A) from D:
86       E sends ADD_HOST(A) to F
87     E receives ADD_HOST(B) from D:
88       E sends ADD_HOST(B) to F
89     E receives ADD_HOST(C) from D:
90       E sends ADD_HOST(C) to F
91
92   4 C receives ADD_HOST(D) from B.
93     C receives ADD_HOST(E) from B.
94     C receives ADD_HOST(F) from B.
95     F receives ADD_HOST(A) from E.
96     F receives ADD_HOST(B) from E.
97     F receives ADD_HOST(C) from E.
98
99 Then C---F authentication finishes, the following actions are taken:
100
101   1 C notes that F is already known:
102       Connection is closed.
103     F notes that C is already known:
104       Connection is closed.
105
106 1.2 Both A---D and C---F finish at the same time.
107 -------------------------------------------------
108
109   1 A sends ADD_HOST(B) to D
110     A sends ADD_HOST(C) to D
111     D sends ADD_HOST(E) to A
112     D sends ADD_HOST(F) to A
113     
114     C sends ADD_HOST(A) to F
115     C sends ADD_HOST(B) to F
116     F sends ADD_HOST(D) to C
117     F sends ADD_HOST(E) to C
118
119   2 A sends ADD_HOST(D) to B
120     A receives ADD_HOST(E) from D:
121       A sends ADD_HOST(E) to B
122     A receives ADD_HOST(F) from D:
123       A sends ADD_HOST(F) to B
124     D sends ADD_HOST(A) to E
125     D receives ADD_HOST(B) from A:
126       D sends ADD_HOST(B) to E
127     D receives ADD_HOST(C) from A:
128       D sends ADD_HOST(C) to E
129
130     C sends ADD_HOST(F) to B
131     C receives ADD_HOST(D) from F:
132       A sends ADD_HOST(D) to B
133     C receives ADD_HOST(E) from F:
134       A sends ADD_HOST(E) to B
135     F sends ADD_HOSTS(C) to E
136     F receives ADD_HOST(A) from C:
137       D sends ADD_HOST(A) to E
138     F receives ADD_HOST(B) from C:
139       D sends ADD_HOST(B) to E
140
141   3 B receives ADD_HOST(D) from A,
142       B sends ADD_HOST(D) to C
143     B receives ADD_HOST(E) from A:
144       B sends ADD_HOST(E) to C
145     B receives ADD_HOST(F) from A:
146       B sends ADD_HOST(F) to C
147     E receives ADD_HOST(A) from D:
148       E sends ADD_HOST(A) to F
149     E receives ADD_HOST(B) from D:
150       E sends ADD_HOST(B) to F
151     E receives ADD_HOST(C) from D:
152       E sends ADD_HOST(C) to F
153     
154     B receives ADD_HOST(F) from C, and notes that is is already known:
155       <insert solution here>
156     B receives ADD_HOST(D) from C, and notes that is is already known:
157       <insert solution here>
158     B receives ADD_HOST(E) from C, and notes that is is already known:
159       <insert solution here>
160     E receives ADD_HOST(C) from F, and notes that is is already known:
161       <insert solution here>
162     E receives ADD_HOST(A) from F, and notes that is is already known:
163       <insert solution here>
164     E receives ADD_HOST(B) from F, and notes that is is already known:
165       <insert solution here>
166
167   4 A receives ADD_HOST(D) from B, and notes that it is already known:
168       <insert solution here>
169     A receives ADD_HOST(E) from B, and notes that it is already known:
170       <insert solution here>
171     A receives ADD_HOST(F) from B, and notes that it is already known:
172       <insert solution here>
173     F receives ADD_HOST(A) from E, and notes that it is already known:
174       <insert solution here>
175     F receives ADD_HOST(B) from E, and notes that it is already known:
176       <insert solution here>
177     F receives ADD_HOST(B) from E, and notes that it is already known:
178       <insert solution here>
179
180     ...
181
182 1.2.1 Augmenting ADD_HOST
183 -------------------------
184
185 A solution would be to augment ADD_HOST with an extra parameter, the nexthop of
186 the added host:
187
188   3 B receives ADD_HOST(D,A) from A,
189       B sends ADD_HOST(D,A) to C
190     B receives ADD_HOST(E,D) from A:
191       B sends ADD_HOST(E,D) to C
192     B receives ADD_HOST(F,E) from A:
193       B sends ADD_HOST(F,E) to C
194     E receives ADD_HOST(A,D) from D:
195       E sends ADD_HOST(A,D) to F
196     E receives ADD_HOST(B,A) from D:
197       E sends ADD_HOST(B,A) to F
198     E receives ADD_HOST(C,B) from D:
199       E sends ADD_HOST(C,B) to F
200     
201     B receives ADD_HOST(F,C) from C, and notes that F is already known:
202       <insert solution here>
203     B receives ADD_HOST(D,E) from C, and notes that D is already known:
204       <insert solution here>
205     B receives ADD_HOST(E,F) from C, and notes that E is already known:
206       <insert solution here>
207     E receives ADD_HOST(C,F) from F, and notes that C is already known:
208       <insert solution here>
209     E receives ADD_HOST(A,B) from F, and notes that A is already known:
210       <insert solution here>
211     E receives ADD_HOST(B,C) from F, and notes that B is already known:
212       <insert solution here>
213
214 So, B and E have to make a choice. Which ADD_HOST is going to win? Fortunately,
215 since the ADD_HOST messages are augmented, they have an extra piece of
216 information they can use to decide in a deterministic way which one is going to
217 win. For example, B got ADD_HOST(F,E) and ADD_HOST(F,C). Since "E" > "C", it
218 could let ADD_HOST(F,E) win.
219
220     B receives ADD_HOST(F,C) from C, and notes that F is already known:
221       since "C" < "E", B ignores ADD_HOST(F,E)
222       B sends ADD_HOST(F,C) to A
223     ...
224     E receives ADD_HOST(C,F) from F, and notes that C is already known:
225       since "F" > "B", E removes the ADD_HOST(C,B) in favour of the new one
226       E sends ADD_HOST(C,F) to D
227
228   4 A receives ADD_HOST(F,E) from B, and notes that F is already known:
229       since "E" < "D", A ignores ADD_HOST(F,D).
230     ...
231     D receives ADD_HOST(C,F) from E, and notes that C is already known:
232       since "F" > "B", D removes the ADD_HOST(C,B),
233       closes the connection with C, in favour of the new one.
234
235 Ok, time to forget this crap.
236
237 1.2.2
238 -----
239
240 The problem with the current ADD/DEL_HOST technique is that each host only
241 knows the general direction in which to send packets for the other hosts. It
242 really doesn't know much about the true topology of the network, only about
243 it's direct neighbours. With so little information each host cannot make a
244 certain decision which it knows for sure all the others will decide too.
245
246 Let's do something totally different. Instead of notifying every host of the
247 addition of a new host, which is represented by a vertex in a graph, lets send
248 out notifications of new connections, which are the edges in a graph. This is
249 rather cheap, since our graphs are (almost) spanning trees, there is
250 approximately one edge for each vertex in the graph, so we don't need to send
251 more messages. Furthermore, an edge is characterized by two vertices, so we
252 only send a fixed amount of extra information. The size/complexity of the
253 problem therefore does not increase much.
254
255 What is the advantage of notifying each vertex of new edges instead of new
256 vertices? Well, all the vertices now know exactly which connections are made
257 between each host. This was not known with the former schemes.
258
259 Ok back to our problem:
260
261   A-----B-----C
262   
263   
264
265   D-----E-----F
266   
267 Edges are undirected, and are characterised by the vertices it connects, sorted
268 alphabetically, so the edges in the two graphs are:
269
270 (A,B), (B,C), (D,E) and (E,F).
271
272 So again we have that A wants to connect to D, and F wants to connect to C,
273 both at the same time. The following loop will occur:
274
275   A-----B-----C
276   |           ^
277   |           |
278   v           |
279   D-----E-----F
280
281 Instead of sending ADD_HOSTs, lets assume the hosts send ADD_EDGEs. So, after
282 making the connections:
283
284   1 A sends ADD_EDGE(A,D) to B
285     A sends ADD_EDGE(A,B) to D
286     A sends ADD_EDGE(B,C) to D
287     D sends ADD_EDGE(A,D) to E
288     D sends ADD_EDGE(D,E) to A
289     D sends ADD_EDGE(E,F) to A
290     
291     C sends ADD_EDGE(C,F) to B
292     C sends ADD_EDGE(A,B) to F
293     C sends ADD_EDGE(B,C) to F
294     F sends ADD_EDGE(C,F) to E
295     F sends ADD_EDGE(D,E) to C
296     F sends ADD_EDGE(E,F) to C
297
298   2 B receives ADD_EDGE(A,D) from A:
299       B sends ADD_EDGE(A,D) to C
300     B receives ADD_EDGE(D,E) from A:
301       B sends ADD_EDGE(D,E) to C
302     B receives ADD_EDGE(E,F) from A:
303       B sends ADD_EDGE(E,F) to C
304     ...
305     
306     B receives ADD_EDGE(C,F) from C, notes that both C and F are already known,
307     but that the edge (C,F) was not known, so a loop has been created:
308       <resolve loop here>
309
310 Ok, how to resolve the loop? Remeber, we want to do that in such a way that it
311 is consistent with the way all the other hosts resolve the loop. Here is the
312 things B does when it notices that a loop is going to be formed:
313
314   B performs a Breadth First Search from the first element of the list of all
315   known hosts sorted alfabetically, in this case A, and thereby finds a
316   spanning tree. (This might later be changed into a minimum spanning tree
317   alhorithm, but the key point here is that all hosts do this with exactly the
318   same starting parameters.) All known edges that are not in the spanning tree
319   are marked inactive.
320
321 An edge marked inactive does not mean anything, unless this edge is connected
322 to B itself. In that case, B will stop sending messages over that edge. B might
323 consider closing this edge, but this is not really needed. Keeping it means no
324 DEL_EDGE has to be sent for it, and if another edge is removed (which will
325 quite certainly split the graph if it's a spanning tree), this edge might be
326 reactivated, without the need of sending a new ADD_EDGE for it. On the other
327 hand, we mustn't keep to many inactive edges, because we want to keep the
328 number of known edges linear to the number of hosts (otherwise the size of the
329 problem will grow quadratically).
330
331 So, since B didn't deactivate one of it's own edges, it forwards the
332 ADD_EDGE(C,F) to A, which also does a BFS, and so on, until it reaches F. F of
333 course also does a BFS, notes that is is one of it's own edges. It deactivates
334 the edge (C,F), and consequently will not forward the ADD_EDGE(C,F) to C
335 anymore. In the mean time, C got messages from B which will make C do the same.
336
337 Ok, suppose a DEL_EDGE was sent, and it means an inactive edge has to be
338 reactivated. The vertices connected by that edge must exchange their entire
339 knowledge of edges again, because in the mean time other messages could have
340 been sent, which were not properly forwarded. Take this example:
341
342   X     C-----D
343   |     |     |
344   |     |     |
345   v     |     |
346   A-----B- - -E
347
348 The edge (B,E) is inactive. X is trying to make a new connection with A. A
349 sends an ADD_EDGE(A,X) to B, which forwards it to C. At that time, the
350 connection between C and D goes down, so C sends a DEL_EDGE(C,D) to B, and D
351 sends a DEL_EDGE(C,D) to E. If we just allow (B,E) to be reactivated again
352 without anything else, then E and D will never have received the ADD_EDGE(A,X).
353 So, B and E have to exchange edges again, and propagate them to the hosts they
354 already know.