[LT] Išradimas priskiriamas skaitmeninės informacijos stebėjimo ir testavimo sistemoms, kai kompiuterių tinkluose naudojamas paketinis duomenų perdavimas ir skirtas tinklo srauto analizei realiu laiku.Pasiūlytas kompiuterių tinklo analizės realiu laiku būdas leidžia pasirinkti tinklo srauto agregavimo metodą ir parametrus, pasižymi atsparumu klaidoms bei didele skaičiavimo sparta.Išradimo esmę sudaro tai, kad realiu laiku fiksuojamas tinklo srautas, formuojamos laiko eilutės, jos agreguojamos taikant judančių vidurkių glotninimo arba perduotų duomenų srauto sumos per laiko intervalą metodą, laikinoje atmintyje saugoma eilutė pastoviai papildoma naujais nariais. Eilutės savastingumas rekurentiškai įvertinamas, taikant robastinį empirinių kvantilių regresijos metodą, IR statistiką, R/S statistiką. Tinklo srauto savastingumo įvertinimui siūloma skaičiuoti ? stabilumo indeksą, IR įvertį ir Hurst koeficientą.
[EN] The invention relates to the digital information systems for monitoring and testing of computer networks using packet data transmission and network traffic analysis for real time. Analysis method of computer network traffic in real-time allows to select the network traffic aggregation method and parameters, and is characterized by fault – tolerance and high speed computing. The invention is characterized that at real time is fixed network traffic, are formed time series, which are aggregated using moving average smoothing or method of sum of transfer dates flow by time interval. Line, which is stored in a temporary memory, constantly supplemented with new members. Singularity of line introduces by recuperating method using robastic method of empirical quintile regression, IR statistic, R/S statistic. For evaluation of singularity network traffic is proposed to calculate ? stability index, IR estimation and Hurst coefficient.
[0001] Išradimas priskiriamas skaitmeninės informacijos stebėjimo ir testavimo sistemoms, kai kompiuterių tinkluose naudojamas paketinis duomenų perdavimas ir skirtas tinklo srauto analizei realiu laiku.
[0002] Perduodant kompiuterių tinklais informaciją svarbu, kad siuntėjo išsiųsti duomenų paketai sėkmingai pasiektų gavėją. Kiekvienam kompiuterių tinklo vartotojui paslauga suteikiama tuoj pat po jos pareikalavimo, todėl atskiruose tinklo segmentuose dažnai atsiranda nenumatytos tinklo perkrovos, sąlygojančios duomenų praradimus tinkle. Siekiant užtikrinti duomenų perdavimo patikimumą rekomenduojama kompiuterių tinkle prognozuoti tinklo segmentų perkrovas ir imtis veiksmų, mažinančių perduodamos informacijos praradimus.
[0003] Yra žinomas duomenų srauto pliūpsniškumo analizės realiu laiku būdas (žiūr. patentą US5343465), kai fiksuojamas duomenų paketo atėjimo į sistemą laikas taip formuojant laiko eilutes, kurioms realiu laiku yra skaičiuojami aprašomosios statistikos parametrai: variacijos koeficientas, koreliacijos koeficientas, dispersijos koeficientas. Dispersijos koeficientas charakterizuoja srauto pliūpsniškumą. Šis techninis sprendimas nepateikia srauto savastingumo įverčių.
[0004] Kitame patente (žiūr. patentą WO1999040703) tinklo srauto analizei realiu laiku naudoja suformuotų laiko eilučių bangelių analizės būdą. Trūkumas - šiame išradime naudojamas tik vienas srauto analizės ir vienas agregavimo metodas.
[0005] Yra žinomas patentas (žiūr. patentą EP1983687), kuriame siūlo savastingumo laipsnį matuoti dinamiškai skaičiuojant srauto Hurst koeficientą. Pirmas koeficientas apskaičiuojamas iš pirmos laiko eilutės, kuri suformuota skaičiavimo modulyje iš realių duomenų sekos, o kiti gaunami prie einamosios pridėjus naują narį ir apskaičiavus naują Hurst koeficientą iš naujai gautos laiko eilutės pradedant antruoju nariu. Skaičiavimams naudojama R/S statistika, laiko dispersijos, liekanos dispersijos, laiko absoliutinių momentų, siaurinimo (angl. whittles) didžiausio tikėtinumo, signalo bangelių įverčių, įterptojo šakojimo, betrendės fliuktuacijos analizės metodai. Šiame išradime neatliekamas eilučių agregavimas.
[0006] Taip pat žinomas būdas ir tinklo srauto analizės įrenginys (žiūr. patentą EP1780955), kuriame tinklo srauto analizei formuojama 1000 narių laiko eilutė, kuri vėliau papildoma naujais nariais, išsaugant tą patį eilutės ilgį. Eilutė formuojama buferyje, kuriame skaičiuojama R/S statistika, laiko dispersija, liekanos dispersija, laiko absoliutiniai momentai, siaurinimo didžiausias tikėtinumas, įvertinamos signalo bangelės, taikomi įterptojo šakojimo bei betrendės fliuktuacijos analizės metodai. Rezultatai klasifikuojami ir saugomi išeities buferyje.
[0007] Šio išradimo trūkumas toks, kad matavimams negalima naudoti kelių skirtingų agregavimo metodų, o Hurst koeficientai nesaugomi tolesnei analizei.
[0008] Šio išradimo tikslas padėti įvertinti tinklo perkrovų pasikartojimo galimybę ir priimti sprendimą dėl nereikšmingų srauto dedamųjų apribojimo ar techninės įrangos keitimo. Siūlomas būdas leidžia pasirinkti tinklo srauto agregavimo metodą ir parametrus, pasižymi atsparumu klaidoms bei didele skaičiavimo sparta.
[0009] Šis tikslas pasiekiamas tuo, kad:
[0010] realiu laiku agreguojamas tinklo srautas taikant judančių vidurkių glotninimo metodą arba perduotų duomenų srauto sumos per laiko intervalą metodą;
[0011] suformuotą eilutę saugo laikinoje atmintyje;
[0012] rekurentiškai skaičiuoja dinamiškai formuojamos eilutės savastingumo parametrus taikant robastinį empirinių kvantilių regresijos metodą, IR statistiką ir R/S statistiką.
[0013] skaičiavimo rezultatus tolesnei analizei saugo laikinojoje arba/ir pastovioje atmintyje;
[0014] siūloma skaičiuoti α stabilumo indeksą, IR įvertį ir Hurst koeficientą.
[0015] Išradimo esmė paaiškinta brėžiniuose:
[0016] fig. 1 - struktūrinė schema, pagal kurią gali būti realizuotas siūlomas kompiuterių tinklo srauto analizės realiu laiku būdas;
[0017] fig. 2 - kompiuterių tinklo srauto analizės realiu laiku būdo realizavimo algoritmas.
[0018] Įrenginio struktūrinė schema, pagal kurią gali būti realizuotas kompiuterių tinklo srauto analizės realiu laiku būdas, parodyta fig.l. Ji susideda iš nuosekliai sujungtų tinklo srauto agregavimo, analizės kriterijų ir parinkčių įvedimo modulio 1, paketų nuskaitymo modulio 2, tinklo paketų antraščių apdorojimo modulio 3, laiko eilutės agregavimo ir formavimo realiu laiku modulio 4, laiko eilučių laikinosios saugyklos 5, laiko eilučių savastingumo analizės modulio 6, skaičiavimo rezultatų formavimo modulio 7 ir skaičiavimo rezultatų saugyklos 8. Skaičiavimo rezultatų formavimo modulis 7 papildomai sujungtas su skaičiavimo rezultatų peržiūros sąsaja 9.
[0019] Pradedant tinklo srauto analizę, tinklo srauto agregavimo ir analizės kriterijų bei parinkčių įvedimo modulyje 1 pasirenka vieną iš duomenų srauto agregavimo būdų, parenka srauto analizės metodus, nurodo formuojamos eilutės ilgį, pasirenka laiko eilutės agregavimo intervalą bei nurodo, ar reikia saugoti gautus rezultatus. Šis modulis susijęs su paketų nuskaitymo moduliu 2, skaitančiu duomenų paketus iš kompiuterių tinklo fizinės terpės. Tinklo paketų antraščių apdorojimo modulyje 3 iš paketo antraštės atskiria informaciją, naudojamą agreguotos eilutės formavimui. Pagal įvedimo modulyje 1 pasirinktą agregavimo taikant judančių vidurkių glotninimo metodą arba perduotų duomenų srauto sumos per laiko intervalą metodą ir agregavimo intervalą agregavimo ir formavimo realiu laiku modulyje 4 formuoja laiko eilutę. Suformuota laiko eilutė saugoma laikinojoje saugykloje 5. Suformavus pirmą eilutę, kiekviena sekanti eilutė šioje saugykloje bus formuojama rekurentiškai. Toliau agreguota laiko eilutę perduoda į savastingumo analizės modulį (6), kuriame pagal pasirinktus analizės metodus (robastinį empirinių kvantilių regresijos, IR statistikos ir/arba R/S statistikos) skaičiuoja stabilumo indeksą, IR įvertį ir Hurst koeficientą. Gautus rezultatus perduoda į skaičiavimo rezultatų formavimo modulį 7, iš kur jie nukreipiami į skaičiavimo rezultatų peržiūros sąsają 9. Rezultatai gali būti pateikiami skaitinėje arba grafinėje formoje.
[0020] Jei vartotojas pasirinko saugoti skaičiavimo rezultatus, tai jie gali būti saugomi skaičiavimo rezultatų saugykloje 8.
[0021] Matematinis siūlomo būdo aprašymas.
[0022] Kompiuterių tinklo analizės metu realiu laiku formuojama laiko eilutė, kuri atitinka matavimus atliktus laiko tarpais t1, t2, ....., tn, čia n - eilutės narių kiekis. Tinklu ateinančių paketų atvykimo laikai ti kur i ∊ [1,n], yra netolyginiai ti -ti-1 ≠ ti+1 -ti, o duomenų paketai atitinkamais laiko tarpais x1, x2,..., xn nusako kanalo užimtumą kiekvienu laiko momentu ti Norint analizuoti tokią laiko eilutę ją būtina agreguoti, t. y. apskaičiuoti duomenų srautus vienodais laiko tarpais ∆t = ti - ti-1 = ti+1 - ti Duomenų agregavimą galima atlikti dviem būdais:
[0023] Pirmuoju būdu - taikant judančių vidurkių glotninimo metodą, kai pasirinktu laiko intervalu ∆t duomenų eilutei apskaičiuojamas vidutinis srautas:
[0024]
[0025] čia
[0026] j ∊ [1,n], kur n- sveikieji skaičiai,
[0027] k ∊ [1,n] , kur n- sveikieji skaičiai, j ir k tenkina nelygybę j > k.
[0028] Gautos laiko eilutės aprašo vidutinius duomenų srauto pokyčius kas laiko momentą ∆t.
[0029] Antruoju būdu - skaičiuojant duomenų srauto per laiko intervalą ∆t kiekį:
[0030]
[0031] čia
[0032] j ∊ [1,n], kur n - sveikieji skaičiai,
[0033] k ∊ [1,n], kur n - sveikieji skaičiai, j ir k tenkina nelygybę j > k .
[0034] Naudojant judančių vidurkių glotninimo metodą agreguotoje eilutėje bus nežymiai sumažinami tinklo srauto pliūpsniai, atsižvelgiant į vartotojo pasirinktą agregavimo intervalą. Taikant perduotų duomenų srauto sumos per laiko intervalą agregavimo metodą, atsižvelgiant į pasirinktą laiko intervalą, bus labiau išryškinami tinklo srauto pliūpsniai.
[0035] Formuojant laiko eilutes analizei galima pasirinkti diskrečius agregavimo intervalus, kuriuos keičiant ir palyginant gautus rezultatus galima įvertinti srauto fraktališkumą. Pasirenkant ∆t rekomenduojama atsižvelgti į matuojamo tinklo srauto intensyvumą, t. y. esant intensyvesniam srautui ∆t pasirenkamas mažesnis, priešingu atveju - didesnis.
[0036] Stabiliųjų atsitiktinių dydžių įverčių skaičiavimas.
[0037] Yra žinoma, kad savastingasis simetriškas procesas, aprašytas formulėmis ir pasižymintis begaline dispersija, yra vadinamas α-stabiliuoju procesu [Samorodnitsky G, Taqqu MS. Stable Non-Gaussian Processes: Stochastic Models with Infinite Variance // Chapman and Hall: New York, 1994. - P. 636.], jei kiekvienam atsitiktiniam procesui Y(t) galima aprašyti tinklo srauto pliūpsnius pagal formulę:
[0038]
[0039] kur:
[0040] P - tinklo srauto pliūpsnio pasirodymo tikimybė,
[0041] t - kintamas dydis, dar vadinamas laiko dedamąja,
[0042] Y(t) - funkcija, priklausanti nuo laiko,
[0043] x - skaičius ir x →∞,
[0044] c - konstanta ir c > 0 ,
[0045] α - stabilumo indeksas.
[0046] Yra įrodyta, kad, kai 1 < α < 2 aukščiau pateiktos formulės vidurkis yra baigtinis, o kai 0 < α ≤ 1 - begalinis [G. Samorodnitsky, Long Range Dependence. Foundations and Trends in Stochastic Systems. Vol. 1, No. 3, 2006, 163-257].
[0047] Stabilusis atsitiktinis dydis Sα (β, σ, μ) yra apibūdinamas keturiais stabilumo parametrais:
[0048] α - stabilumo indeksas α ∊ (0,2], dar vadinamas uodegų indeksu, nusakantis proceso pliūpsniškumą,
[0049] β - asimetrijos indeksas β ∊ [-1,1], nusakantis proceso poslinkį atžvilgiu nulio,
[0050] σ - mastelio indeksas, σ > 0 ir nusako proceso elementų dydį,
[0051] μ- padėties indeksas μ ∊ R.
[0052] Laiko eilutės savastingumo įvertinimui pakanka apskaičiuoti stabilumo indeksą. Likusių trijų stabilumo parametrų skaičiavimas leidžia tik įvertinti eilutės savybes, todėl jų skaičiavimo formulės nėra pateikiamos. Stabiliojo atsitiktinio stabilumo indekso α įvertinimui pasirinkti robastiniai vertinimo metodai, pasižymintys atsparumu klaidoms bei didele skaičiavimo sparta.
[0053] Plačiau apie tai darbe [L. Kaklauskas, L. Sakalauskas (2011). Study of on-line measurement of traffic self-similarity. Central European Journal of Operations Research, DOI: 10.1007/s10100-011-0216-5].
[0054] Mūsų siūlomame būde pritaikytas robastinis empirinių kvantilių regresijos metodas. Šis metodas α -stabiliųjų dydžių parametrų įvertinimui pasiūlytas darbe [I. A. Koutrouvelis (1981). An iterative procedure for the estimation of the parameters of the stable law. Communications in Statistics - Simulation and Computation 10, 1981, 17-28]. Šio metodo taikymai plačiau aprašyti darbe [I. Belovas, A.Kabašinskas, L. Sakalauskas, (2005). Vertybinių popierių rinkos stabiliųjų modelių tyrimas. Konferencijos "Informacinės technologijos 2005" medžiaga, Technologija, Kaunas, pp. 439-462].
[0055] Pagal robastinį empirinių kvantilių regresijos metodą stabilumo indeksas apskaičiuojamas pagal formulę:
[0056]
[0057] kur:
[0058]
[0059]
[0060] n - suformuotos laiko eilutės elementų skaičius,
[0061] xi - i-tasis laiko eilutės elementas,
[0062] t - pasirinktas laiko eilutės agregavimo intervalas,
[0063]
[0064] Jei gautoji α reikšmė 1 < α < 2, tai eilutė pasižymi savastingumu ir kuo α reikšmė arčiau 2, tuo savastingumo atmintis ilgesnė. Kaip minėta aukščiau, kitų trijų eilutės stabilumo parametrų skaičiavimas leidžia įvertinti eilutės savybes, tačiau apie jos savastingumą papildomos informacijos nepateikia.
[0065] Antras skaičiavimo metodas yra IR statistika (angl. Increment Ratio statistics). Plačiau toks skaičiavimas aprašytas darbe [D. Surgailis, G. Teyssiere, M. Vaičiulis. The increment ratio statistics. Journal of Multivariate Analysis Volume 99, Issue 3, March 2008, pages 510-541]. Skaičiuojant šiuo metodu įvertinama, ar analizuojamas tinklo srautas pasižymi savastingumu su ilgalaike atmintimi. Pagal IR statistikos metodą IR įvertis apskaičiuojamas pagal formulę:
[0066]
[0067] kur: k - kintamasis, naudojamas IR įverčio reikšmės skaičiavimui,
[0068] n - suformuotos eilutės narių skaičius,
[0069]
[0070] Xi - i-tasis suformuotos eilutės narys.
[0071] Su pasikliovimo lygmeniu 0,95 galima teigti, kad agreguota eilutė pasižymi savastingumu su ilgalaike atmintimi, jei tenkinama nelygybė:
[0072]
[0073] Hurst koeficientas H skaičiuojamas pagal žinomą R/S statistikų metodiką, pvz., pagal metodiką, aprašytą [G. Samorodnitsky. Long Range Dependence. Foundations and Trends in Stochastic Systems 2006b; 1(3):163 - 257].
[0074] Robastinį empirinių kvantilių regresijos metodą rekomenduojama naudoti, kai reikia tiksliau įvertinti tinklo srauto savastingumą ir jo ilgalaikę atmintį, skaičiuojant a indeksą. Klasikinė R/S statistika naudotina kaip gauto α indekso kontrolės priemonė, kuri iš esmės patvirtina tinklo srauto savastingumo savybę. IR statistika rekomenduojama naudoti tada, kai reikia įvertinti kompiuterių tinklo srauto kitimo tendencijas.
[0075] Algoritmas, kuris vertina kompiuterių tinklo srauto savastingumą pagal pateiktą būdą, pavaizduotas fig. 2. Pirmas žingsnis - vartotojo parinkčių įrašymas 10 - įvedama informacija apie pasirinktą agregavimo intervalą, agregavimo metodą, formuojamos laiko eilutės ilgį, pasirenkami savastingumo įvertinimo metodai bei rezultatų saugojimas. Antras žingsnis - tinklo paketų skaitymas iš tinklo įrenginio 11. Trečias žingsnis - informacijos iš paketų antraščių nuskaitymas 12. Ketvirtas žingsnis - laiko eilutės agregavimas 13. Jei pasirinktas judančių vidurkių glotninimo metodas 14, tai eilutė formuojama taikant šį agregavimo metodą , kitaip eilutė formuojama taikant duomenų srauto sumos per laiko intervalą metodą 15. Penktas žingsnis - agreguotos laiko eilutės saugojimas 16 (dažniausiai laikinoje arba operatyvioje atmintyje) kol bus suformuota agreguota laiko eilutė pagal vartotojo nurodytą laiko eilutės ilgį. Kiekviena sekanti eilutė bus formuojama rekurentiškai, 1. y. naikinamas pirmasis suformuotos eilutės narys ir pridedamas naujas agreguotas narys.
[0076] Šeštas žingsnis - stabilumo parametrų skaičiavimas:
[0077] pasirinktas robastinis empirinių kvantilių regresijos metodas 17,
[0078] stabilumo indekso skaičiavimas 17a,
[0079] pasirinktas IR statistikos metodas 18,
[0080] IR įverčio skaičiavimas 18a,
[0081] pasirinktas R/S statistikos metodas 19,
[0082] Hurst koeficiento skaičiavimas 19a.
[0083] Jei pasirinkti visi trys metodai, tai skaičiuojami visi parametrai.
[0084] Septintas žingsnis - rezultatų pateikimas vartotojui 20. Aštuntas žingsnis - rezultatų saugojimas 21. Jei buvo pasirinkta saugoti rezultatus, tai gauti įverčiai yra saugomi pastoviojoje atmintyje 21a.
[0085] Siūlomas būdas yra patikrintas panaudojant kompiuterinio imitavimo metodą bei atliekant skaičiavimus su realaus tinklo duomenų paketais. Atsitiktiniams srautams imituoti buvo sukurtas modulis, generuojantis laiko eilutes, aprašomas α-stabiliais dydžiais Sα(β, 1, 0), kai α ≠ 1. Generuotos savastingosios eilutės su šiais parametrais: α = 1,8 (H = 0,56), β = 0,. σ = 1, μ = 0, generuojamų eilučių skaičius - 1000, o kiekvienos eilutės narių kiekis n =3000. Gauti skaičiavimo rezultatai atitiko generuojant parinktas reikšmes, t. y. 1,73 < α < 1,86, o 0,538 < H < 0,578.
[0086] Siūlomo būdo realizavimui sukurta savastingumo vertinimo programinių modulių biblioteka (angl. Self-Similarity Estimator), sutrumpintai SSE. Naudojant siūlomą būdą buvo atlikti Šiaulių universiteto Nuotolinių studijų centro tinklo mazgo apkrovos matavimai realiu laiku. Apskaičiuotos 309 agreguotų laiko eilučių α stabilumo indekso ir Hurst koeficiento reikšmės. IR įverčio skaičiavimas parodė, kad 87,24% laiko eilučių pasižymi ilgalaike atmintimi (1 < α < 2). Vadinasi, agreguotomis eilutėmis aprašomas kompiuterių tinklu perduodamų duomenų paketų srautas yra persistentinis su ilgalaike atmintimi procesas. Keičiant agregavimo intervalą skaičiavimo rezultatai yra panašūs, vadinasi, laiko eilutės turi fraktalų savybių.
[0087] Įvertinus programa SSE gautų rezultatų standartinį nuokrypį, nustatyta, kad α stabilumo indekso, IR įverčio ir Hurst koeficiento vertinimo metodai tinkami savastingumo parametrų nustatymui realiu laiku.
[0088] Programinių modulių biblioteką taip pat galima naudoti apkrovos savastingumui matuoti tinklo mazge bei kliento kompiuteryje.
[0089] Pagal matavimo rezultatus ir taikomą tinklo modelį galima prognozuoti srauto pliūpsnius tinklo mazguose ir imtis prevencinių priemonių jiems sumažinti.
1. Kompiuterių tinklo srauto analizės realiu laiku būdas, kai rekurentiškai formuoja eilutę, skaičiuoja statistinius jos parametrus ir rezultatus saugo laikinojoje atmintyje, b e s i s k i r i a n t i s tuo, kad:
realiu laiku agreguoja tinklo srautą taikant judančių vidurkių glotninimo metodą arba perduotų duomenų srauto sumos per laiko intervalą metodą;
suformuotą eilutę saugo laikinoje atmintyje;
rekurentiškai skaičiuoja dinamiškai formuojamos eilutės savastingumo parametrus;
skaičiavimo rezultatus tolesnei analizei saugo laikinojoje arba/ir pastoviojoje atmintyje;
2. Būdas pagal 1 punktą, b e s i s k i r i a n t i s tuo, kad savastingumo parametrus skaičiuoja taikant robastinį empirinių kvantilių regresijos metodą, IR statistiką ir R/S statistiką,
3. Būdas pagal 2 punktą, b e s i s k i r i a n t i s tuo, kad savastingumo įvertinimui skaičiuoja α stabilumo indeksą, IR įvertį ir Hurst koeficientą.