Algorithmische Probleme in grossen Netzwerken

In diesem Vortrag studieren wir einige algorithmische Probleme, die in grossen Netzwerken wie dem World-Wide-Web entstehen.

• Verbindungscaching: In einem Netzwerk ist eine Menge von offenen TCP-Verbindungen zu verwalten. Wir stellen optimale Online-Algorithmen vor, die die gesamten Verbindungsherstellungskosten minimieren.

• TCP-Acknowledgement: Werden Datenpakete ueber eine offene TCP-Verbindung geschickt, so muss der empfangende Netzwerkknoten die Ankunft der Pakete bestaetigen. Wir stellen fuer eine Reihe von Zielfunktionen optimale Protokolle fuer das dynamische Bestaetigen vor.

• Dokumenten-Caching: In Web-Servern und Browsern sind lokale Caches mit Web-Dokumenten so zu verwalten, dass haeufig angefragte Dokumente nicht staendig ueber das Netz heruntergeladen werden muessen. Wir stellen Offline-Approximationsalgorithmen vor, die die Ladekosten minimieren.

B.Hammer