There are two lzo compression levels.

[tinc] / doc / CONNECTIVITY

diff --git a/doc/CONNECTIVITY b/doc/CONNECTIVITY
index 884df43..6cf16dd 100644 (file)
--- a/doc/CONNECTIVITY
+++ b/doc/CONNECTIVITY
@@ -1,7 +1,7 @@
 This document describes how nodes in a VPN find and connect to eachother and
 maintain a stable network.
 
 This document describes how nodes in a VPN find and connect to eachother and
 maintain a stable network.
 

-   Copyright 2001 Guus Sliepen <guus@sliepen.warande.net>
+   Copyright 2001-2002 Guus Sliepen <guus@sliepen.eu.org>

 
    Permission is granted to make and distribute verbatim copies of
    this documentation provided the copyright notice and this
 
    Permission is granted to make and distribute verbatim copies of
    this documentation provided the copyright notice and this


@@ -12,143 +12,34 @@ maintain a stable network.
    provided that the entire resulting derived work is distributed
    under the terms of a permission notice identical to this one.
 
    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.11 2002/09/16 14:08:04 wsl Exp $

 
 

-1. Problem
-==========
-
-We have a set of nodes (A, B, C, ...) that are part of the same VPN. They need
-to connect to eachother and form a single graph that satisfies the tree
-property.
-
-There is the possibility that loops are formed, the offending connections must
-be eliminated.
-
-Suppose we start with two smaller graphs that want to form a single larger
-graph. Both graphs consist of three nodes:
-
-  A-----B-----C
-  
-  
-
-  D-----E-----F
-  
-It is very well possible that A wants to connect to D, and F wants to connect
-to C, both at the same time. The following loop will occur:
-
-  A-----B-----C
-  |           ^
-  |           |
-  v           |
-  D-----E-----F
-
-The situation described here is totally symmetric, there is no preference to
-one connection over the other. The problem of resolving the loop, maintaining
-consistency and stability is therefore not a trivial one.
-
-What happens when A---D and C---F are connected to eachother? They exchange
-lists of known hosts. A knows of B and C, and D knows of E and F. The protocol
-defines ADD_HOST messages, from now on we will say that "node X sends and
-ADD_HOST(Y) to Z".
-
-There are two possible scenarios: either both A---D and C---F finish
-authentication at the same time, or A---D finishes first, so that ADD_HOST
-messages will reach C and F before they finish authentication.
+1. Synchronisation
+==================

 
 

-1.1 A---D finishes first
-------------------------
+Each tinc daemon has zero or more connections to other tinc daemons. It will
+try to keep its own information synchronised with the other tinc daemons. If
+one of its peers sends information, the tinc daemon will check if it is new
+information. If so, it will update its own information and forward the new
+information to all the other peers.

 
 

-After A---D authentication finishes the following actions are taken:
+This scheme will make sure that after a short amount of time all tinc daemons
+share the same information. It will also almost completely prevent information
+from looping, because "new" information that is already known is ignored and
+not forwarded any further. However, since information can also be deleted
+there's the possibility of a looping sequence of add/delete messages. This is
+resolved by additionaly adding a unique identifier to each broadcasted message.
+Messages are dropped if the same message with that identifier has already been
+seen.

 
 

-  1 A sends ADD_HOST(B) to D
-    A sends ADD_HOST(C) to D
-    D sends ADD_HOST(E) to A
-    D sends ADD_HOST(F) to A
-
-  2 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 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:
-      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(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.
-    C receives ADD_HOST(F) from B.
-    F receives ADD_HOST(B) from E.
-    F receives ADD_HOST(C) from E.
-
-Then C---F authentication finishes, the following actions are taken:
-
-  1 C notes that F is already known:
-      Connection is closed.
-    F notes that C is already known:
-      Connection is closed.
-
-1.2 Both A---D and C---F finish at the same time.
--------------------------------------------------
-
-  1 A sends ADD_HOST(B) to D
-    A sends ADD_HOST(C) to D
-    D sends ADD_HOST(E) to A
-    D sends ADD_HOST(F) to A
-    
-    C sends ADD_HOST(A) to F
-    C sends ADD_HOST(B) to F
-    F sends ADD_HOST(D) to C
-    F sends ADD_HOST(E) to C
-
-  2 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 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 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 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
+2. Routing
+==========

 
 

-  3 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
-    
-    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:
-      <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>
+Every node tells its peers to which other peers it is connected. This way
+every node will eventually know every connection every node has on the VPN.
+Each node will use graph algorithms to determine if other nodes are reachable or not and
+what the best route is to other nodes.

 
 

-  4 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>
-    F receives ADD_HOST(A) 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>
+Because all nodes share the same information, using a deterministic algorithm
+each node will calculate the same minimum spanning tree for the entire VPN.
+The MST will be used to send broadcast VPN packets.