git.meshlink.io Git - meshlink/blob - 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.1.2.8 2002/02/10 21:57:51 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.