Żółty Kapłan: Utworzono nową stronę "'''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ą implem…"

2026-05-13T15:50:38Z

Utworzono nową stronę "'''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ą implem…"

Nowa strona

'''Routing Mieścińskiego''' - hipotetyczny model routingu numerycznego oparty [[Niedeterministyczna Maszyna Turinga|niedeterministycznych maszyn Turinga]] (NDTM) oraz [[Automat skończony|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:

:<math>G = (V,E)</math>

oznacza graf [[Elementy Analizy Numerycznej|numeryczny]] sieci, gdzie:
* <math>V</math> – zbiór węzłów numerycznych,
* <math>E</math> – zbiór połączeń numerycznych.

Routing Mieścińskiego definiowany jest jako [[Siedem liczb błędnie zaokrąglonych|siódemka]]:

:<math>R = (Q,\Sigma,\Gamma,\delta,q_0,F)</math>

gdzie:
* <math>Q</math> – skończony zbiór stanów routingu,
* <math>\Sigma</math> – alfabet wejściowy pakietów numerycznych,
* <math>\Gamma</math> – alfabet pomocniczy pamięci tras,
* <math>\delta</math> – relacja przejścia niedeterministycznego,
* <math>q_0</math> – stan początkowy,
* <math>F</math> – zbiór stanów akceptujących.

Relacja przejścia ma postać:

:<math>\delta(q,a)=\{(q_1,d_1),(q_2,d_2),...,(q_n,d_n)\}</math>

gdzie:
* <math>q_i</math> oznacza kolejny stan routingu,
* <math>d_i</math> oznacza kierunek transmisji pakietu [[Arytmetyka Przedziałowa|przedziałowego]].

== Procedura routingu ==

Dla pakietu wejściowego:

:<math>P=(a_1,a_2,...,a_n)</math>

system wykonuje algorytm algorytmem iteracyjnym numerycznym:

:<math>x^{(k+1)} = Mx^{(k)} + w</math>

gdzie:
* <math>M</math> jest [[Arytmetyka Przedziałowa|macierzą przedziałową]] przejść [[Elementy Analizy Numerycznej|numerycznych]],
* <math>w</math> jest wektorem wag transmisji,
* <math>x^{(k)}</math> oznacza stan sieci po <math>k</math> iteracjach.

Jeżeli:

:<math>\rho(M) < 1</math>

to proces routingu jest zbieżny w sensie [[Harmonijka Mieścińskiego|Harmonijki Mieścińskiego]]

== Zastosowania ==

Routing Mieścińskiego znajduje zastosowanie w:
* praktycznym routingu sieci [[Eduroam]],
* protokole [[Zeroconf]],
* organizacji wydarzenia [[RoboDay]],
* organizacji [[Dzień ze Strażą Akademicką|Dnia ze strażą akademicką]].

Routing Mieścińskiego - Historia wersji