Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

Verteiltes DHCP im Mesh

Dieses Dokument beschreibt das auf der ffnordcon2015 erarbeitete Konzept für verteiltes DHCP in Meshnetzen. Als Vorrausetzung wird angenommen:

  • es gibt eine Anycast-IPv4 Adresse unter der alle Knoten für die Clients erreichbar sind
  • alle Knoten können sich per IPv6 Uni- und Multicast erreichen
  • jeder Knoten hat einen eindeutigen Identifier (z.B. die node_id, MAC oder den Hostteil der IPv6)

IPv4-Blöcke

Das IPv4 Subnetz wird in gleichgroße Blöcke unterteilt. Als Blockgröße sind 4 oder 8 IPv4 Adressen angedacht und als Subnetzgröße wird mindestens ein /18 angenommen. Jedem Knoten (der Clients bedient) ist mindestens ein Block zugeordnet, so dass die maximale Anzahl an Knoten entsprechend begrenzt ist.

Die Knoten geben unregelmäßig eine Liste der Blöcke, die sie belegen bekannt; spätestens jedoch nach der halben Blockleasetime. Diese Information wird von allen Knoten im RAM vorgehalten:

  • Block ID (evtl. implizit durch Index in einer Tabelle)
  • Besitzer
  • Timeout/Timestamp

Desweiteren können Blöcke auch gesperrt sein um dort eine manuelle Konfiguration zu ermöglichen. In den meisten Fällen dürfte mindestens der Block mit der statischen Anycast-IPv4 gesperrt sein.

Block belegen

Um einen Block zu belegen, geht ein Knoten wie folgt vor:

  1. Ein Knoten wählt einen Block (er kennt ja die aktuelle Belegung), der frei sein müsste.
  2. Er fragt mehrmals per Multicast nach, ob dieser Block bereits belegt ist.
  3. Falls es innerhalb einer kurzen Zeit keine Antwort gibt, nimmt er den Block in besitz.
  4. Dies teilt er wiederum per Multicast allen Knoten mit, so dass diese ihre Belegungstabelle aktualisieren können. Falls der Block tatsächlich schon belegt war, wird der Eintrag überschrieben.

Falls der Block belegt sein sollte, aktualisiert der Knoten seine Belegungstabelle und probiert es mit einem anderen Block erneut. Hat er alle freien Blöcke erfolglos durchprobiert, ist er für eine gewisse Zeit still und probiert es erneut sobald ein Block in der Tabelle frei wird.

Blockfreigabe und -delegation

Knoten haben die Möglichkeit einen Block vor Ablauf des Timeouts freizugeben. Desweiteren besteht die Möglichkeit den Besitzer eines Blockes direkt zu ändern. Dies ist beispielsweise sinnvoll, wenn nur eine IPv4 des Blocks belegt und der Client zu einem anderen Knoten gewechselt ist. Dazu kommunizieren die betroffenen Knoten im Vorfeld via Unicast.

Anfragen von Clients

Discover

Sendet der Client ein Discover, kann der Knoten dem Client eine IPv4 aus einem seiner Blöcke anbieten. Dabei versucht der Knoten eine starke Fragmentierung der Blöcke zu vermeiden. Gibt es keine freie IPv4, versucht der Knoten einen weiteren Block zu belegen und bietet dem Client daraus eine IPv4 an. Kann der Knoten dem Client keine IPv4 anbieten, kann er den Client ablehnen oder ihm eine "spezielle IPv4" zuweisen, die lediglich für den Internetzugang, nicht jedoch für die Kommunikation mit anderen Clients verwendbar ist.

Renew

Grundsätzlich führt immer der Knoten, der den Block verwaltet auch die Verlängerung der Leases durch. Ist ein Client zwischenzeitlich zu einem anderen Knoten geroamed, wird der neue Knoten den ursprünglichen Knoten bitten die Lease zu verlängern. Ist jener nicht erreichbar, wird der neue Knoten versuchen den Block selbst zu belegen. Stellt sich dabei ein neuer Besitzer heraus, wird dieser kontaktiert um die Leaseverlängerung durchzuführen. Dieser Vorgang kann einige, wenige Male wiederholt werden. Ist er permanent erfolglos, verweigert er dem Client die Verlängerung. Der Client wird daraufhin nach einer neuen IPv4 mittels Discover fragen.

Auflösung von Split Brain

Sollten sich zwei beliebige, disjunkte Teile des Meshes verbinden, können Blöcke doppelt belegt sein. Dies wird durch die periodischen Multicast Announcements erkannt. Je doppelt belegten Block wird jeweils der Knoten, dessen Block die meisten vergebenen (maßgeblich sollte die halbe Leasetime sein, da andernfalls der Client wahrscheinlich schon weg ist) Adressen enthält, den Block behalten. Bei Gleichstand entscheidet der Identifier des Knotens (größer gewinnt). Der unterlegene Knoten wird den Block freigeben bzw. dem neuen Besitzer übergeben um die Belegungstabelle aller Knoten zu synchronisieren.

Der unterlegene Knoten merkt sich die betroffenen IPv4 Adressen und Clients und wird ggf. vermeiden Traffic von diesen Clients in das Mesh zu leiten. Versuchen diese Clients ihre Adressen zu erneuern, greift der übliche Vorgang (d.h. der überlegene Knoten ist erstmal zuständig).

Konfiguration

  • node identifier (64 bit integer)
  • IPv4 Prefix (32 bit + 8 bit mask)
  • Blockgröße (1 byte)
  • Liste von gesperrten Blöcken
  • diverse Timeouts
  • Gateway IPv4
  • Liste von DNS IPv4
  • Searchdomain
  • interface on which DHCP clients are served
  • interface for communication with other nodes

Todo

  • Timeouts konkretisieren
  • konkretisieren wie gesperrte Blöcke behandelt werden
  • vermeiden von Fragmentierung konkretisieren
  • Protokoll ausarbeiten
  • Irgendwoher muss die Information kommen welcher Gateway einem Client zugeordnet ist

Weitere Ideen

  • Knoten könnten Blöcke nach einiger Zeit (Stunden, Tage, ...) automatisch wieder freigeben.
  • Damit ein neuer Knoten schnell einen Überblick über die Blocktabelle erhält, könnte er diese von Nachbarn (oder dem nächstbesten Knoten) erhalten.
  • Multicastgruppen je Block um Broadcasts zu reduzieren?
  • Bei Split Brain dem unterlegenen Knoten die gesamte Tabelle senden?
  • Event bei neuen Leases um z.B. batman's DAT zu füllen?

Links

required types
--------------
- [X] Block allocation/freeing/delegation
- [ ] request for block owner
- [ ] lease renewal (proxy)
- [ ] lease renewal response (proxy)
Allocate Block
==============
This packet type is used for multiple purposes:
- allocating an unused block
- freeing a block (setting timeout to zero)
- delegating a block (setting owner to the other node)
Commands
--------
0x01 - allocate block
0x02 - inform (notifying a node about another node's allocations)
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IPv4 prefix (4) |
+---------------+---------------+---------------+---------------+
| prefixlen (1) | blocksize (1) | command (1) | count (1) |
+---------------+---------------+---------------+---------------+
| |
~ sender's node IPv6 (16) ~
| |
+---------------------------------------------------------------+
| |
~ holder's node IPv6 (16) ~
| |
+---------------------------------------------------------------+
| block index (4) |
+-------------------------------+-------------------------------+
| timeout (2) | reserved (2) |
+-------------------------------+-------------------------------+
IPv4 prefix: the IPv4 prefix used by this node
prefixlen: length of the prefix
blocksize: number of IPv4 addresses in each block
command: command of this packet
count: number of block allocations in this packet
timeout: number of seconds this allocation will be valid
holder's node identifier, block index, timeout and the remaining 2 bytes
of the block are repeated $count times for each allocation. Up to 60
allocations may be send within a single packet.
IPv4 prefix, prefixlen and blocksize identify a specific network. Nodes
must ignore packets where these fields don't match their own.
Renewal of block allocations
----------------------------
Nodes should update their allocations after half of the allocation timeout has passed.
@rubo77
Copy link

rubo77 commented Aug 13, 2015

alpha dynamischer DHCP server auf https://github.com/tcatm/pyddhcpd

@rubo77
Copy link

rubo77 commented Jul 3, 2018

Funktionierende Umsetzung: https://github.com/sargon/ddhcpd

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment