Routing Mieścińskiego

Routing Mieścińskiego - hipotetyczny model routingu numerycznego oparty niedeterministycznych maszyn Turinga (NDTM) oraz automatów stanów skończonych. Model ten stosowany jest w elementach sieci numerycznych.

W przeciwieństwie do klasycznych protokołów deterministycznych, Routing Mieścińskiego jako jedyny umożliwia efektywny routing datagramów IPoEAN.

Pierwszą praktyczną implementację tzw. Routera Mieścińskiego zrealizował Marek Kropidłowski w VHDL.

Model formalny

Niech:

$G=(V,E)$

oznacza graf numeryczny sieci, gdzie:

• $V$ – zbiór węzłów numerycznych,
• $E$ – zbiór połączeń numerycznych.

Routing Mieścińskiego definiowany jest jako siódemka:

$R=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,F)$

gdzie:

• $Q$ – skończony zbiór stanów routingu,
• $\mathrm{\Sigma }$ – alfabet wejściowy pakietów numerycznych,
• $\mathrm{\Gamma }$ – alfabet pomocniczy pamięci tras,
• $\delta$ – relacja przejścia niedeterministycznego,
• $q_0$ – stan początkowy,
• $F$ – zbiór stanów akceptujących.

Relacja przejścia ma postać:

$\delta (q,a)=\{(q_1,d_1),(q_2,d_2),...,(q_n,d_n)\}$

gdzie:

• $q_i$ oznacza kolejny stan routingu,
• $d_i$ oznacza kierunek transmisji pakietu przedziałowego.

Procedura routingu

Dla pakietu wejściowego:

$P=(a_1,a_2,...,a_n)$

system wykonuje algorytm algorytmem iteracyjnym numerycznym:

$x^{(k+1)}=M{x}^{(k)}+w$

gdzie:

• $M$ jest macierzą przedziałową przejść numerycznych,
• $w$ jest wektorem wag transmisji,
• $x^{(k)}$ oznacza stan sieci po $k$ iteracjach.

Jeżeli:

$\rho (M)<1$

to proces routingu jest zbieżny w sensie Harmonijki Mieścińskiego

Zastosowania

Routing Mieścińskiego znajduje zastosowanie w:

• praktycznym routingu sieci Eduroam,
• protokole Zeroconf,
• organizacji wydarzenia RoboDay,
• organizacji Dnia ze strażą akademicką.