This document describes how nodes in a VPN find and connect to eachother and maintain a stable network. Copyright 2001 Guus Sliepen Permission is granted to make and distribute verbatim copies of this documentation provided the copyright notice and this permission notice are preserved on all copies. Permission is granted to copy and distribute modified versions of this documentation under the conditions for verbatim copying, 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.5 2001/07/22 17:41:52 guus 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.1 A---D finishes first ------------------------ After A---D authentication finishes the following actions are taken: 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 sends ADD_HOST(D) to B 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 sends ADD_HOST(A) to E 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(D) from A, B sends ADD_HOST(D) to C 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 E receives ADD_HOST(C) from D: E sends ADD_HOST(C) to F 4 C receives ADD_HOST(D) from B. C receives ADD_HOST(E) from B. C receives ADD_HOST(F) from B. F receives ADD_HOST(A) from E. 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 sends ADD_HOST(D) to B 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 sends ADD_HOST(A) to E 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 sends ADD_HOST(F) to B 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 sends ADD_HOSTS(C) to E 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 3 B receives ADD_HOST(D) from A, B sends ADD_HOST(D) to C 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 E receives ADD_HOST(C) from D: E sends ADD_HOST(C) to F B receives ADD_HOST(F) from C, and notes that is is already known: B receives ADD_HOST(D) from C, and notes that is is already known: B receives ADD_HOST(E) from C, and notes that is is already known: E receives ADD_HOST(C) from F, and notes that is is already known: E receives ADD_HOST(A) from F, and notes that is is already known: E receives ADD_HOST(B) from F, and notes that is is already known: 4 A receives ADD_HOST(D) from B, and notes that it is already known: A receives ADD_HOST(E) from B, and notes that it is already known: A receives ADD_HOST(F) from B, and notes that it is already known: F receives ADD_HOST(A) from E, and notes that it is already known: F receives ADD_HOST(B) from E, and notes that it is already known: F receives ADD_HOST(B) from E, and notes that it is already known: ... 1.2.1 Augmenting ADD_HOST ------------------------- A solution would be to augment ADD_HOST with an extra parameter, the nexthop of the added host: 3 B receives ADD_HOST(D,A) from A, B sends ADD_HOST(D,A) to C B receives ADD_HOST(E,D) from A: B sends ADD_HOST(E,D) to C B receives ADD_HOST(F,E) from A: B sends ADD_HOST(F,E) to C E receives ADD_HOST(A,D) from D: E sends ADD_HOST(A,D) to F E receives ADD_HOST(B,A) from D: E sends ADD_HOST(B,A) to F E receives ADD_HOST(C,B) from D: E sends ADD_HOST(C,B) to F B receives ADD_HOST(F,C) from C, and notes that F is already known: B receives ADD_HOST(D,E) from C, and notes that D is already known: B receives ADD_HOST(E,F) from C, and notes that E is already known: E receives ADD_HOST(C,F) from F, and notes that C is already known: E receives ADD_HOST(A,B) from F, and notes that A is already known: E receives ADD_HOST(B,C) from F, and notes that B is already known: So, B and E have to make a choice. Which ADD_HOST is going to win? Fortunately, since the ADD_HOST messages are augmented, they have an extra piece of information they can use to decide in a deterministic way which one is going to win. For example, B got ADD_HOST(F,E) and ADD_HOST(F,C). Since "E" > "C", it could let ADD_HOST(F,E) win. B receives ADD_HOST(F,C) from C, and notes that F is already known: since "C" < "E", B ignores ADD_HOST(F,E) B sends ADD_HOST(F,C) to A ... E receives ADD_HOST(C,F) from F, and notes that C is already known: since "F" > "B", E removes the ADD_HOST(C,B) in favour of the new one E sends ADD_HOST(C,F) to D 4 A receives ADD_HOST(F,E) from B, and notes that F is already known: since "E" < "D", A ignores ADD_HOST(F,D). ... D receives ADD_HOST(C,F) from E, and notes that C is already known: since "F" > "B", D removes the ADD_HOST(C,B), closes the connection with C, in favour of the new one.