www.tinc-vpn.org Git - tinc/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 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.5 2001/07/22 17:41:52 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.