uppspännande träd

(spanning tree) – i nätstrukturer: en samman­­hängande figur av linjer (en graf) som når alla noder (knutpunkter) i nätet. Figuren får grena sig, men den får inte bilda slingor. – Minsta upp­­spännande träd (minimum spanning tree, på svenska också minimalt…) är den kortaste graf som når alla noder i nätet (beskrivs här). – Spanning tree proto­­col, känt som STP, är ett protokoll som an­­vänds för att hindra att meddelanden i nätverk går i slingor. Protokollet, som ut­­veck­lades 1985 av Radia Perlman, då på Digital†, senare på Intel, nu på Dell, hittar ett minsta uppspännande träd i nätet och stänger av alla förbindelser som inte ingår i trädet. Ett med­­de­lande som slussas från nod till nod kan då inte gå runt i slinga. – I början av 00-talet började det bli uppenbart att STP inte var effektivt, och rent av kontraproduktivt, i stora nätverk, eftersom det bara tillåter en enda förbindelse mellan två noder i nätverket, inte alltid den kortaste eller snabbaste. Därför utvecklades TRILL som allt mer har ersatt STP. – Läs mer i Wikipedia. – Läs också om traversering.

[matematik] [nätverk] [ändrad 20 maj 2020]

Dagens ord: 2017-05-21