mina86.com

Hmmm… co do części pierwszej: może EIGRP? :)

Edit: Swoją drogą, porównywanie beduinów do routerów Cisco jest dość nietuzinkowe :P

Muszę jeszcze dokładniej poczytać o tym algorytmie, ale wydaje mi się, iż polega on w przypadku, gdy zakładamy ograniczoną pamięć beduinów, należy bowiem wziąć pod uwagę, że nie występuje tutaj coś takiego jak podsieci i „klasy” beduinów.

No i chyba obmyśliłem, jak można rozwiązać problem z ograniczoną pamięcią. Do tej pory źle się zabierałem do sprawy—cała sztuczka polega na nadaniu beduinom adresów.

Na początek wybieramy arbitralnie jakiegoś beduina, który staje się korzeniem. Proces ten można zautomatyzować wybierając beduina o „najmniejszym” (w sensie jakiegoś przyjętego dobrego porządku) imieniu.

Teraz beduini zapamiętują odległość (którą na początku inicjują nieskończonością) oraz listę dzieci. Korzeń rozpoczyna wszystko zerując swoją odległość i krzycząc trójkę (NULL, swoje imię, 1). Gdy ktoś usłyszy komunikat (rodzic, imię, metryka) robi co następuje:

1. jeśli rodzic to on sam zapamiętuje imię w liście dzieci, chyba że już tam jest;
2. jeśli rodzic to ktoś inny oraz imię znajduje się w liście dzieci usuwa je stamtąd;
3. jeśli metryka jest mniejsza od zapamiętanej odległości ustawia odległość na wartość metryki po czym krzyczy (imię, swoje imię, odległość + 1).

W tej chwili beduini mogą zapomnieć odległość, ale muszą ciągle pamiętać listę dzieci oraz swój identyfikator (adres). Zabawę ponownie rozpoczyna korzeń ustawiając swój adres na „0” i wykrzykując dla każdego ze swoich dzieci komunikat (imię dziecka, „id.n”), gdzie id to jego identyfikator, a n to numer dziecka. Po wykrzyczeniu tych komunikatów zapomina listę dzieci (gdyż nie będzie już potrzebna). Gdy ktoś usłyszy wiadomość, gdzie imię zgadza się z jego imieniem ustawia swój identyfikator na ten z wiadomości i powtarza czynność wykonaną przez korzeń.

Aby wysłać wiadomość, beduin musi znać identyfikator odbiorcy—tutaj niestety trzeba zastosować zapytanie rozchodzące się po całej pustyni. Zakładamy, że każdy z beduinów będzie rozmawiał z taką liczbą osób, że jest w stanie zapamiętać identyfikatory ich wszystkich.

Tymczasem, gdy trzeba wysłać wiadomość do wierzchołka o konkretnym identyfikatorze, to po prostu przekazujemy ją do rodzica, aż do momentu, gdy identyfikator beduina będzie przedrostkiem identyfikatora odbiorcy, a następnie do dzieci zgodnie z docelowym adresem.

Dalej twierdzę, że wyważasz otwarte drzwi. Od tego są automatyczne protokoły routingu.

Co do przedostatniego akapitu (o identyfikatorach odbiorcy), to sprawa wygląda jeszcze prościej: beduini nie są głupi i nie muszą pamiętać imion wszystkich, po prostu będą sprawdzać, czy identyfikator odbiorcy należy do odpowiedniej klasy adresowej (przestrzeni nazw, jak zwał tak zwał). Jeśli więc odbiorcą jest Abdul, Muhammad, Tariq czy Saddam to wszystko jest OK. Natomiast wiadomość przeznaczona dla Krzysia, Fxjfdh2w czy 10.0.2.3 powinna zostać odrzucona jako nieprawidłowy odbiorca.

OK, nie czaję o czym mówisz. ;)

Cały problem z protokołami routingu jest taki, że sieci zazwyczaj są podzielone na podsieci dzięki czemu nawet gdyby każdy router miałby trzymać całą tablicę routingu to sprawa jest prostsza niż w opisanym problemie, gdyż nie muszą pamiętać ścieżki do każdej maszyny, a jedynie do podsieci, w której one się znajdują.

Z beduinami jest tak, że nie ma tutaj żadnych podsieci. Nie można wnioskować, że Abdul jest gdzieś w pobliżu Ahmeda, a na zupełnie innym końcu pustyni niż Zenon. Doszedłem do wniosku, że należy to rozwiązać tworząc takie podsieci i klasy adresowe.

Co do identyfikatorów, to po ich przydzieleniu komunikaty wysyłane są do ziomka o podanym identyfikatorze, a nie imieniu i dlatego najpierw trzeba poznać identyfikator komputera o zadanym imieniu, aby móc do niego wysyłać wiadomości (coś jak ARP).