Med hjälp av entropi av trafikdistributioner har visat sig stödja en mängd olika nätövervakningstillämpningar såsom anomalidetektering, klusterbildning för att avslöja intressanta mönster och trafikklassificering. Men att inse denna potentiella nytta i praktiken kräver exakta algoritmer som kan fungera på höghastighetslänkar, med låga CPU- och minneskrav. I den här artikeln undersöker vi problemet med att uppskatta entropin i en strömmande beräkningsmodell. Vi ger lägre gränser för detta problem, visar att varken approximation eller randomisering ensam kommer att låta oss beräkna entropi effektivt. Vi presenterar två algoritmer för att slumpmässigt approximera entropin på ett tids- och rymdeffektivt sätt, tillämpliga för användning på mycket höga hastigheter (större än OC-48) länkar. Den första algoritmen för entropiuppskattning är inspirerad av den strukturella likheten med det seminala arbetet av Alon et al. för att uppskatta frekvensmoment, och vi ger starka teoretiska garantier för fel och resursanvändning. Vår andra algoritm använder observationen att prestandan hos den strömmande algoritmen kan förbättras genom att separera högfrekventa objekt (eller elefanter) från lågfrekventa objekt (eller möss). Vi utvärderar våra algoritmer på trafikspår från olika driftsättningsscenarier.
I REF föreslås effektiva streamingalgoritmer för att genomföra entropimätningen på höghastighetslänkar med låga CPU- och minneskrav.
Data streaming algorithms for estimating entropy of network traffic
{'venue': "SIGMETRICS '06/Performance '06", 'journal': None, 'mag_field_of_study': ['Computer Science']}