Algorytmy Internetu

O czym jest ten przedmiot?

Zapewne macie wyobrażenie, o czym wykład Algorytmy Internetu powinien być. Prawdopodobnie jednak jest to wyobrażenie błędne. Wykład ten nie służy bowiem do przekazania informacji na temat istniejących protokołów sieciowych. Zakładam, że taką wiedzę wynieśliście z przedmiotu Sieci komputerowe. Nie będzie ona zresztą nam bardzo potrzebna. Obycie z działaniem Internetu będzie przydatne głównie do zrozumienia istotności poruszanych zagadnień. Wykład nie będzie też rozszerzeniem powyższego przedmiotu o analizę protokołów, które tam poznaliście.

Wykład ten jest o matematycznych mechanizmach, które sprawiają, że obecny Internet wygląda tak, jak wygląda. Tego, czego dowiecie się na tym przedmiocie, nie znajdziecie w żadnej pojedynczej książce. Będziemy dotykać tematów, które są zupełnie ze sobą nie związane, a których jedynymi cechami wspólnymi jest to, że są — w moim mniemaniu — ciekawą matematyką i mają związek z Internetem.

Czasem będą to pojedyncze matematyczne odkrycia, które pozwoliły firmom takim jak Google stać się wielomiliardowymi gigantami. Albo przykładowo pomogły przyspieszyć pracę routerów i są powszechnie stosowane. Czasem będą to po prostu powszechnie znane i używane mechanizmy, np. aukcje cyfrowe umożliwiające funkcjonowanie firmom typu Ebay czy Allegro. Czasem będą to algorytmy routingu, których zastosowanie ograniczone jest obecnie tylko do sieci ustrukturyzowanych, np. takich, które łączą poszczególne elementy klastrów obliczeniowych. Czasem będą to algorytmy, które są niezbędne przy przetwarzaniu olbrzymich ilości danych. I wreszcie czasem będzie to inżynieria wsteczna, czyli próba zrozumienia dlaczego pewne wprowadzone dziesiątki lat temu protokoły sieciowe sprawdzają się w praktyce. Można to wszystko podsumować jednym określeniem: matematyczne narzędzia analizy sieci.

Na zakończenie wstępu chciałem przestrzec przed jednym. Te zagadnienia są trudne. A może i bardzo trudne, a ich zrozumienie wymagać będzie dużo wysiłku i samozaparcia. Nie polecam tego przedmiotu nikomu, kto nie operuje w miarę sprawnie pojęciami z analizy algorytmów, dyskretnego rachunku prawdopodobieństwa, algebry liniowej czy kombinatoryki. A pozostałych serdecznie zapraszam!

Wyklad

• 7.10.2013. Algorytm Pagerank: rangi stron, właściwości macierzy stochastycznych, metoda iteracyjna, wartości własne, losowy surfer, problemy z metodą iteracyjną.

  • S. Brin, L. Page: The Anatomy of a Large-Scale Hypertextual Web Search Engine, Computer Networks, 30(1-7):107-117, 1998.

  • K. Bryan, T. Leise: The $25,000,000,000 eigenvector: The linear algebra behind google, SIAM Review, 48:569-581, 2006.
    

• 14.10.2013. Algorytm Pagerank: modyfikacja grafu, zbieżność metody iteracyjnej. Routing: wybór ścieżek, przełączanie pakietów, obciążenie (congestion), opóźnienie (dilation)
  

• 28.10.2013. Routing: adaptujący się wybór ścieżek: O(log m)-aproksymacyjny algorytm AAFPW; nieświadomy (oblivious) wybór ścieżek: systemy ścieżek, dolne ograniczenia, losowe systemy ścieżek, routing w hiperkostce (Valiant's trick), informacja o minimalizowaniu obciążenia w ogólnych grafach (Räcke).

  • J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, O. Waarts: On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM, 44(3):486–504, 1997.

  • A. Borodin, J. E. Hopcroft: Routing, merging and sorting on parallel models of computation, 14th ACM Symposium on Theory of Computing (STOC), 338-344, 1982.

  • L. G. Valiant: A Scheme for Fast Parallel Communication, SIAM J. Comput. 11, pp. 350-361, 1982.

  • H. Räcke: Optimal Hierarchical Decompositions for Congestion Minimization in Networks, 40th ACM Symposium on Theory of Computing (STOC), 255-264, 2008.
    

• 4.11.2013. Routing: przełączanie pakietów: czas routingu na cyklu, algorytm Radnom Rank dla grafów acyklicznych.

  • F. Leighton, B. Maggs, A. Ranade, S. Rao: Randomized Routing and Sorting on Fixed-Connection Networks, J. of Algorithms, 17, pp. 157-205, 1994.
    

• 18.11.2013. Sieci Peer-to-peer: Chord, DHT, haszowanie spójne, równomierność rozłożenia danych.

  • I. Stoica, R. Morris, D. Karger, M. Kaashoek, H. Balakrishnan: Chord: A scalable peer-to-peer lookup service for internet applications, SIGCOMM Comput. Commun. Rev., 31(4), 149-160, 2001

  • Chernoff bound (lecture notes)
    

• 25.11.2013. Sieci Peer-to-peer: Chord: struktura sieci, wyszukiwanie i wstawianie nowych wierzchołków.
  

• 4.12.2013. Serwery proxy: problem pamięci podręcznej, LRU, Random-Mark, analiza konkurencyjna.

  • D. Sleator, R. Tarjan: Amortized efficiency of list update and paging rules, Communications of the ACM, 28(2), 202-208, 1995

  • A. Fiat, R. Karp, M. Luby, L. McGeoch, D. Sleator, N. Young: Competitive Paging Algorithms, Journal of Algorithms 12, 685-699 (1991)
    

• 9.12.2013. Serwery proxy: wariant niejednorodny: algorytmy Greedy-Dual i Landlord.

  • N. Young: The K-Server Dual and Loose Competitiveness for Paging, Algorithmica, 11(6), 525-541, 1994

  • N. Young: On-Line File Caching, Algorithmica, 33, 371-383, 2002
    

• 16.12.2013. Tablice routingu: problem wyszukiwania w tablicy routingu (longest prefix match): trie + tablice haszujące, kompresja tablic routingu.

  • M. Waldvogel, G. Varghese, J. Turner, B. Plattner: Scalable high speed IP routing lookups, SIGCOMM Comput. Commun. Rev., 27(4), 25-36, 1997

  • R.Draves, C. King and V. Srinivasan, B. Zill: Constructing Optimal IP Routing Tables, INFOCOM, 88-97, 1999
    

• 7.1.2014. Aukcje cyfrowe: mechanizmy aukcyjne, wymuszanie prawdomówności, niezależność od ofert, aukcje typu cost-share, aproksymacja maksymalizacji zysku.

  • A. Goldberg, J. Hartline, A. Karlin, M. Saks, A. Wright: Competitive auctions, Games and Economic Behavior, 55(2), 242-269, 2006

  • A. Goldberg, J. Hartline, A. Wright: Competitive Auctions and Digital Goods, technical report.
    

• 20.1.2014. Problem Adwords: algorytm oparty o programowanie liniowe.

  • A. Mehta, A. Saberi, U. Vazirani, V. Vazirani: AdWords and generalized online matching, Journal of the ACM, 54(5), 2007
    

• 27.1.2014. Kontrola przepływu: zagadnienie potwierdzania pakietów, algorytm deterministyczny dla problemu TCP acknowledgement, wariant problemu na drzewie.

  • D. Dooly, S. Goldman, S. Scott: On-line analysis of the TCP acknowledgment delay problem, J. ACM, 48(2), 243-273, 2001.

  • S. Khanna, J. Naor, D. Raz: Control Message Aggregation in Group Communication Protocols, ICALP 2002.