Co to jest drzewo Aguri?

19

Przeglądając stare artykuły Hackera, natknąłem się na post od użytkownika, który powiedział:

Drzewa Aguri, które łączą trix radix o ograniczonym rozmiarze (tak jak w przypadku tabeli routingu programowego) z listą LRU i automatycznie syntetyzują agregaty (np. 10.0.0.0/16 z 1000 obserwacji we wszystkich adresach IP) na podstawie wzorca wstawiania. Najbardziej znane są w analizie ruchu, ale wykorzystaliśmy je również w analizie pamięci środowiska wykonawczego.

~ tptacek

Więc postanowiłem to sprawdzić,

  • Szybka wyszukiwarka Google prowadzi mnie do kierowcy F1.
  • Wyszukiwanie w Wikipedii prowadzi do kasty rolniczej w Indiach i niektórych produktów z Japonii
  • Przepełnienie stosu osiąga 0 wyników /programming//search?q=aguri site:stackoverflow.com/questions aguri

W końcu połączyłem go z powrotem z użytkownikiem, który widzi link na swoim blogu

http://www.matasano.com/log/1009/aguri-coolest-data-structure-youve-never-heard-of/

Ale to nie żyje.

Czym więc jest ta struktura danych Aguri i jeśli jest to prawdziwa struktura danych, dlaczego nie jest nigdzie udokumentowana?

phwd
źródło

Odpowiedzi:

15

Aguri to profiler ruchu, który wykorzystuje drzewa prefiksów. Cały artykuł znajduje się na tej stronie. Krótko mówiąc, nie ma takiej struktury danych jak „Drzewo Aguri”, chyba że policzymy drzewa prefiksów używane w tym systemie jako własne unikalne podtypy.

Inżynier świata
źródło
9

Bardzo niewiele naprawdę umiera w Internecie. Archive.org po prostu ma jedną migawkę tego posta na blogu od momentu jego opublikowania . Skopiowano tutaj:

Pewna zaradcza informatyka dla audytorów PCI na moich odbiorców.

Daję ci tablicę losowych liczb całkowitych. Jak rozpoznać, czy jest w nim liczba trzy?

Cóż, istnieje oczywisty sposób: sprawdzaj liczby kolejno, aż znajdziesz „3” lub wyczerpujesz tablicę. Wyszukiwanie liniowe. Biorąc pod uwagę 10 liczb, musisz założyć, że może to zrobić 10 kroków; N liczb, N kroków.

Zdjęcie 1.png

Wyszukiwanie liniowe jest złe. Trudno jest gorzej niż liniowo. Poprawmy to. Posortuj tablicę.

Zdjęcie 2.png

Posortowana tablica sugeruje inną strategię: przeskocz na środek tablicy i sprawdź, czy szukana wartość jest mniejsza niż (po lewej) lub większa niż (po prawej). Powtarzaj, przecinając tablicę za każdym razem o połowę, aż znajdziesz wartość.

Binary wyszukiwania. Biorąc pod uwagę 10 liczb, zajmie to aż 3 kroki - log2 z 10 - - znalezienie jednego z nich w posortowanej tablicy. Wyszukiwanie O (log n) jest niesamowite. Jeśli masz 65 000 elementów, wystarczy tylko 16 kroków, aby znaleźć jeden z nich. Podwój elementy, a to 17 kroków.

Ale posortowane tablice są do kitu; po pierwsze, sortowanie jest droższe niż wyszukiwanie liniowe. Dlatego nie używamy dużo wyszukiwania binarnego; zamiast tego używamy drzew binarnych.

Zdjęcie 3.png

Aby przeszukać drzewo binarne, zacznij od góry i zadaj sobie pytanie: „czy mój klucz jest mniejszy niż (lewy) lub większy niż (prawy) bieżący węzeł”, i powtarzaj, aż ok, ok, ok, znasz już te rzeczy. Ale to drzewo jest ładne, prawda?

Wyszukiwanie z (zrównoważonym) drzewem binarnym to O (log n), podobnie jak wyszukiwanie binarne, zmieniające się w zależności od liczby elementów w drzewie. Drzewa binarne są niesamowite: masz szybki przegląd i posortowane przechodzenie, coś, czego nie wyciągniesz ze stołu haszującego. Drzewa binarne są lepszą domyślną implementacją tabel niż tabele skrótów. 2)

Ale drzewa binarne nie są jedynym mechanizmem wyszukiwania o strukturze drzewa. Próbki binarnych podstaw, zwane także drzewami PATRICIA, działają jak drzewa binarne z jedną zasadniczą różnicą. Zamiast porównywać więcej niż / mniej niż w każdym węźle, sprawdzasz, czy bit jest ustawiony, rozgałęzia się w prawo, jeśli jest ustawiony, i w lewo, jeśli nie jest.

Zdjęcie 4.png

Często pomijam sposób, w jaki stara się podstawa binarna. Szkoda, ponieważ próby rzutu są notorycznie mało udokumentowane - Sedgewick niesławnie spieprzył je w „Algorytmach”, a strona Wikipedii jest do bani. Ludzie wciąż kłócą się o to, jak je nazwać! Zamiast wyjaśnienia linków zwrotnych i krawędzi oznaczonych pozycjami bitów, oto mała implementacja Ruby.

Oto, dlaczego próby Radix są fajne:

Search performance varies with the key size, not the number of elements in the tree. With 16 bit keys, you’re guaranteed 16 steps

niezależnie od liczby elementów w drzewie, bez równoważenia.

More importantly, radix tries give you lexicographic matching, which is a puffed-up way of saying “search with trailing wildcard”, or

„Wyszukiwanie w stylu zakończenia wiersza poleceń”. W drzewie radix możesz szybko wyszukać „ro *” i uzyskać „Rome”, „romulous” i „roswell”.

3)

Zgubiłem cię

Umieśćmy to w kontekście. Próby są kluczową strukturą danych dla routingu internetowego. Problem z routingiem wygląda następująco:

You have a routing table with entries for “10.0.1.20/32 -> a” and “10.0.0.0/16 -> b”.

You need packets for 10.0.1.20 to go to “a”

You need packets for 10.0.1.21 to to to “b”

Jest to trudny problem do rozwiązania z podstawowym drzewem binarnym, ale w przypadku trix radix, po prostu pytasz o „1010.0000.0000.0000.0000.0001.0100” (dla 10.0.1.20) i „1010.” (dla 10.0.0.0 ). Wyszukiwanie leksykograficzne zapewnia „najlepsze dopasowanie” do routingu. Możesz spróbować w powyższym kodzie Ruby; dodaj * ”10.0.0.0” .to_ip do trie i wyszukaj „10.0.0.1” .to_ip.

Zgodność między routingiem a próbami radix jest tak silna, że ​​najpopularniejsza biblioteka trie radix ogólnego przeznaczenia (ta z CPAN) jest faktycznie wykradziona z GateD. Nawiasem mówiąc, to bałagan i nie używaj go.

Jeśli rozumiesz, jak działa trie, rozumiesz również, jak działają wyrażenia regularne. Próby są szczególnym przypadkiem deterministycznych automatów skończonych (DFA), w których rozgałęzienia oparte są wyłącznie na porównaniach bitów i zawsze rozgałęziają się do przodu. Dobry silnik regex to po prostu obsługa DFA z większą liczbą „funkcji”. Jeśli moje zdjęcia mają dla ciebie sens, zdjęcia w tym doskonałym artykule na temat algorytmu redukcji NFA-DFA Thompsona również będą, a ten artykuł sprawi, że będziesz mądrzejszy. 4

Jesteś operatorem sieci szkieletowej dostawcy usług internetowych. Wasz świat składa się głównie z „prefiksów” - par sieci IP / maski sieci. Maski sieciowe w tych prefiksach są dla Ciebie niezwykle ważne. Na przykład 121/8 należy do Korei; 121.128 / 10 należy do Korea Telecom, 121.128.10 / 24 należy do klienta KT, a 121.128.10.53 to jeden komputer w tym kliencie. Jeśli śledzisz botnet, operację spamowania lub rozprzestrzenianie robaków, ten numer maski sieci jest dla Ciebie bardzo ważny.

Niestety, choć są ważne, nigdzie w pakiecie IP nie ma wytłoczonej „maski sieci” - maski sieciowe są całkowicie szczegółami konfiguracji. Tak więc, kiedy oglądasz ruch, zasadniczo masz te dane do pracy z:

ips.png

Zaskakujące, biorąc pod uwagę wystarczającą liczbę pakietów do obejrzenia, jest to wystarczająca ilość informacji, aby odgadnąć maski sieciowe. Pracując w Sony, Kenjiro Cho wymyślił naprawdę elegancki sposób na zrobienie tego, w oparciu o próby. Oto jak:

Wypróbuj podstawową wersję binarną trix radix, podobnie jak te używane przez routery programowe. Ale ogranicz liczbę węzłów w drzewie, powiedzmy do 10 000. Łączem szkieletowym, rejestrującym adresy poza nagłówkami IP, w ciągu kilku chwil wyczerpiesz 10 000 węzłów.

Przechowuj listę węzłów na liście, posortowaną w kolejności LRU. Innymi słowy, gdy dopasujesz adres IP do węzła, „dotknij” węzła, umieszczając go na górze listy. Stopniowo często widoczne adresy bąbelkują do góry, a rzadko widoczne węzły opadają na dół.

Zdjęcie 6.png

Teraz sztuczka. Kiedy zabraknie węzłów i potrzebujesz nowego, odzyskaj z dołu listy. Ale kiedy to zrobisz, zwiń dane z węzła do jego elementu nadrzędnego, w ten sposób:

Zdjęcie 5.png

10.0.1.2 i 10.0.1.3 to rodzeństwo / 32s, dwie połówki 10.0.1.2/31. Aby je odzyskać, połącz je w 10.0.1.2/31. Jeśli chcesz odzyskać 10.0.1.2/31, możesz połączyć ją z 10.0.1.0/31, aby utworzyć 10.0.1.0/30.

Zrób to, powiedzmy, przez minutę, a wyjątkowe źródła będą bronić swojej pozycji w drzewie, pozostając na szczycie listy LRU, podczas gdy otoczenie / 32 szumy bąbelkowe do / 0. Dla surowej listy adresów IP powyżej, ze drzewem 100 węzłów, otrzymujesz to.

Cho nazywa to heurystycznym Aguri. 5

Aguri ma licencję BSD. Możesz go pobrać, a także sterownik, który ogląda pakiety przez pcap, ze starej strony domowej Cho. 6.

Idę gdzieś z tym, ale mam teraz 1300 słów do tego postu, a jeśli jesteś osobą algorytmiczną, jesteś już mną zmęczony, a jeśli nie, jesteś zmęczony mną przez teraz. Wpuść Aguri, a dam ci coś fajnego i bezużytecznego do zrobienia z tym w tym tygodniu.

Jest tam rozrzuconych wiele linków. Niestety Archive.org nie przechowuje obrazów, tylko tekst, więc kilka z nich zostało utraconych. Oto te, które zostały zarchiwizowane:

Izkata
źródło
To rzeczywiście pokazuje informacje, czy jest jakiś powód, dla którego wszystkie te linki nie są już dostępne?
phwd
@phwd Właśnie skopiowałem / wkleiłem linki na dole, z których prowadzi Wayback Machine. I łączy się z samym sobą, więc widzisz te strony, które były w pobliżu, gdy powstał post na blogu. Artykuły w Wikipedii i porównanie wyrażeń regularnych, wiem, że nadal istnieją.
Izkata