Implementujte zjednodušený algoritmus pro tvorbu kostry sítě. Tento algoritmus se používá pro detekci minimálních cest mezi zapojenými switchi v síti.

Základní popis

Systém začíná ve stavu kdy máme několik switchů, každý ze switchů má předem určené množství portů. Porty můžou být nezapojené, zapojené do jiného switche, nebo zapojené do koncových počítačů.

Pro zjednodušení uvažujeme pouze spojitý systém (existuje cesta z každého switche do každého switche).

Algoritmus

Každý switch začíná ve stavu kdy zná minimální cestu ke strojům zapojeným na jeho portech (cesta délky 0) a u všech ostatních strojů má uvedenou nekonečnou vzdálenost (reprezentující nedosažitelný stroj).

Switch informaci o minimálních cestách (pouze konečných) oznámí všem switchům ke kterým je připojen.

Pokud switch dostane informaci o cestách od svého souseda, spojí si tuto informaci se svojí lokální informací a pokud dojde k aktualizaci některé z cest, pošle tuto informaci svým sousedům.

Např. pokud switch zná cestu na stroj ID10 přes port 3 se vzdáleností 3 a dostane novou informaci na portu 2 o cestě se vzdáleností 1, nastaví se pro stroj ID10 cestu přes port 2 o vzdálenosti 2. Tuto novou cestu vypropaguje svým sousedním switchům.

Ukončení

Tento algoritmus nemá explicitní ukončovací podmínku. Nicméně pokud budeme přepokládat že se zprávy neztrácí, je zřejmé, že systém po nějaké době zkonverguje do stavu kdy každý switch bude znát minimální cestu na každý stroj.

Ve zkonvergovaném stavu v systému nejsou žádné nezpracované zprávy a žádný uzel není ve stavu kdy se chystá notifikovat souseda o nové lepší cestě.

Implementace

Stroje budou v systému reprezentované pouze svými ID, switche budou reprezentovány třídou, která bude zároveň obsahovat hlavní logiku.

Počet portů by měl být konfigurovatelný.

Demonstrační main by měl vytvořit náhodný svět ve kterém bude rozumný počet různě zapojených switchů, na kterých následně budou zapojené koncové stroje.

Algoritmus by měl být schopen pracovat s postupným zapojováním (při zapojení se na nový spoj odešlou minimální cesty, čímž se opět spustí algoritmus).