X-Git-Url: https://www.tinc-vpn.org/git/browse?p=tinc;a=blobdiff_plain;f=doc%2FCONNECTIVITY;h=bf31451ede901435c48fbcdc7aa1b246d117a305;hp=f504f25f14276af5dbfaa7be57ddd81555810986;hb=0cae9098754d1414844ba2cdb575d80619516dc0;hpb=c1a98cd37ea20f6020487b2a5586e6de432398e7 diff --git a/doc/CONNECTIVITY b/doc/CONNECTIVITY index f504f25f..bf31451e 100644 --- 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. - Copyright 2001 Guus Sliepen + Copyright 2001-2006 Guus Sliepen Permission is granted to make and distribute verbatim copies of this documentation provided the copyright notice and this @@ -12,36 +12,32 @@ maintain a stable network. 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.1 2001/07/22 14:04:38 guus Exp $ - -1. Problem +1. Synchronisation +================== + +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. + +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. + +2. Routing ========== -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 +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. -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. +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.