Abstrakt. Vi anser att en router på Internet analyserar de statistiska egenskaperna hos en TCP/IP paketström. En grundläggande svårighet med att mäta trafikbeteende på Internet är att det helt enkelt finns för mycket data för att registreras för senare analys, på beställning av gigabyte en sekund. Till följd av detta kan nätroutrar endast samla in relativt få statistiska uppgifter om uppgifterna. Det centrala problemet som tas upp här är att använda det begränsade minnet av routrar för att fastställa viktiga funktioner i nätverkstrafiken. Ett särskilt svårt och representativt underproblem är att bestämma de högsta k-kategorierna som de flesta paket hör till, för ett önskat värde på k och för ett givet begrepp om kategorisering, t.ex. IP-adressen till destinationen. Vi presenterar en algoritm som deterministiskt finner (i synnerhet) alla kategorier som har en frekvens över 1/(m + 1) med hjälp av m räknare, som vi bevisar är bäst möjligt i värsta fall. Vi presenterar också en provtagningsbaserad algoritm för fallet att paketkategorier följer en godtycklig distribution, men deras ordning över tiden permuteras jämnt på måfå. Enligt denna modell identifierar vår algoritm flöden över ett frekvenströskelvärde på ungefär 1/ ε nm med hög sannolikhet, där m är antalet räknare och n är antalet observerade paket. Denna garanti är inte långt ifrån idealet att identifiera alla flöden (sannolikhet 1/n), och vi bevisar att det är bäst möjligt upp till en logaritmisk faktor. Vi visar att algoritmen rankar de identifierade flödena enligt frekvens inom varje önskad konstant noggrannhetsfaktor.
I REF, Demaine et al. presenterar counting-only heavyhitters identifieringsalgoritmer, som använder räknare och deterministiskt identifierar alla flöden som har en relativ frekvens ovan.
Frequency estimation of internet packet streams with limited space
{'venue': 'In Proceedings of the 10th Annual European Symposium on Algorithms', 'journal': None, 'mag_field_of_study': ['Computer Science']}