Abstract-I detta dokument föreslår vi en algoritm för att effektivt diagnostisera storskaliga klusterfel. Algoritmen, Cluster-MAX-COVERAGE (CMC), är baserad på girig strategi. Vi tar itu med utmaningen att fastställa fel med ofullständiga symtom. CMC gör ny användning av både positiva och negativa symtom för att skriva ut en hypoteslista med ett lågt antal falska negativa och falska positiva snabbt. CMC kräver rapporter från ungefär hälften så många noder som andra befintliga algoritmer för att avgöra fel med 100% noggrannhet. Dessutom gör CMC denna vinst betydligt snabbare (ibland av två storleksordningar) än en algoritm som matchar dess noggrannhet. Dessutom föreslår vi en adaptiv algoritm kallad Adaptive-MAX-COVERAGE (AMC) som fungerar effektivt under båda typerna av fel, dvs oberoende och klustererade. Under en serie fel som inkluderar både oberoende och klustererade, AMC resulterar i ett minskat antal falska negativa och falska positiva. [13] föreslås lokalisera storskaliga misslyckanden i nätverk. Det visas att genom att överväga felmönster i storskaliga avbrott, denna algoritm kan uppnå högre noggrannhet än befintliga algoritmer som utvecklats för oberoende fel [10]. Nackdelen med netCSI är dock att run-time komplexiteten hos algoritmen ökar exponentiellt med ökningen av nätverkens storlek eftersom det är en kombinatorisk strategi. I detta dokument föreslår vi en ny algoritm som heter Cluster-MAX-COVERAGE (CMC) som diagnostiserar storskaliga klusterfel. För att identifiera de felaktiga nätverkselementen (dvs. nätverksnoder, routers och länkar) använder CMC en kunskapsbas av möjliga nätverksvägar och end-to-end symptominformation. De observerade end-to-end-symtomen under misslyckanden inkluderar båda de negativa symptomen, t.ex. vilka källdestinationspar som kopplas bort, samt positiva symtom, t.ex. vilka källdestinationspar som fortfarande kan kommunicera. Denna information rapporteras till nätverkshanteraren av några utvalda noder i nätverket som kallas rapporteringsnoder; en fullständig lista över symtom krävs inte. Med hjälp av denna information, CMC utdata en hypotes lista som består av en uppsättning nätverk element vars misslyckanden överensstämmer med symptomen. För att lösa frågan om run-time komplexitet, CMC antar en girig strategi när generera hypoteslistan över felaktiga nätverkselement, i motsats till den kombinatoriska metoden i netCSI. Vår giriga strategi liknar en feldiagnosalgoritm som kallas MAX-COVERAGE (MC) [10], som är utvecklad för att diagnostisera svarta hål eller tysta fel (oberoende fel) i IP-nätverk. Vid klusterfel försämrar MC:s prestanda i synnerhet avsevärt, vilket ger ett oöverkomligt stort antal falska negativa effekter (se avsnitt V-C1). För att övervinna denna begränsning använder CMC kluster av objekt i stället för enstaka objekt när man bildar hypoteslistan. De viktigaste bidragen från CMC inkluderar: • Klustermodeller: För att diagnostisera storskaliga misslyckanden väljer CMC kluster av objekt girigt baserat på klustermodeller. Vi föreslår två olika klustermodeller baserade på den information som finns tillgänglig för nätverksförvaltaren (se avsnitt IV-A för ytterligare information). • Använda positiva symtom: Till skillnad från MC som endast använder negativa symtom, CMC anser både positiva och negativa symtom. Som ett resultat, CMC ger en hypotes lista med färre falska positiva. I våra experiment märker vi att falska positiva medel reduceras med i genomsnitt 45% med innefattande av positiva symtom. • Klara av partiell symptominformation: Under 978-1-4673-1625-5/12/$31.00 ©2012 IEEE
Srikar m.fl. föreslå en adaptiv algoritm för att diagnostisera storskaliga fel i datornätverk REF, genom att analysera en graf som representerar nätverket topologi.
Adaptive algorithms for diagnosing large-scale failures in computer networks
{'venue': 'IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2012)', 'journal': 'IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2012)', 'mag_field_of_study': ['Computer Science']}