Abstract-Vi undersöker problemet med att identifiera individuella länkmått i ett kommunikationsnätverk från ackumulerade end-to-end-mått över utvalda mätvägar, under antagandet att länkmått är additiva och konstanta under mätningen, och mätvägar kan inte innehålla cykler. Vi vet från linjär algebra att alla länkmått kan identifieras unikt när antalet linjärt oberoende mätvägar är lika med n, antalet länkar. Det är dock ineffektivt att samla in mätningar från alla möjliga vägar, vars antal kan växa exponentiellt i n, eftersom antalet användbara mätningar (från linjärt oberoende vägar) är som mest n. Syftet med detta papper är att utveckla effektiva algoritmer för att konstruera linjärt oberoende mätvägar och beräkna länkmått. Vi visar att närhelst det finns en uppsättning n linjärt oberoende mätvägar, måste det finnas en uppsättning av tre parvis oberoende spännande träd. Vi utnyttjar denna egenskap för att utveckla en algoritm som kan konstruera n linjärt oberoende, cykelfria vägar mellan monitorer utan att undersöka alla kandidatvägar, vars komplexitet är quadratic i n. En ytterligare fördel med den föreslagna algoritmen är att de genererade banor uppfyller en bonad struktur som tillåter linjär-tid beräkning av länkmått utan att uttryckligen invertera mätningsmatrisen. Våra utvärderingar av både syntetiska och verkliga nätverkstopologier verifierar den överlägsna effektiviteten hos de föreslagna algoritmerna, som är storleksordningar snabbare än referenslösningar för stora nätverk.
Mamma och Al. I REF föreslås en effektiv algoritm för att konstruera linjärt oberoende mätvägar.
Efficient Identification of Additive Link Metrics via Network Tomography
{'venue': '2013 IEEE 33rd International Conference on Distributed Computing Systems', 'journal': '2013 IEEE 33rd International Conference on Distributed Computing Systems', 'mag_field_of_study': ['Computer Science']}