Network topology analysis – graph properties that matter

Network topology analysis – graph properties that matter

 

This article presents correlation between network metrics with graph properties, more specifically spectral graph characteristics. This work is in the foundation of network topology analysis based on the relevant graph representation of the network and its properties. In the beginning is made an overview of the basic network metrics that contribute to the network quality, resilience, robustness and performance, which in turn reflects in the satisfaction of the final user, which is usually measured with the Quality of Experience (QoE) level. These metrics include, but are not limited to: • Link latency and Round-trip time  Jitter • Throughput • Packet loss • Availability. The next part is focus on topology parameters of graphs, how they are calculated and what their meaning in the context of networks is. Focus is given on the so called spectral graph properties, because they well represent global metrics of the topology in terms of quality and resilience. Such spectral graph properties are the algebraic connectivity, graph spectrum and some of their products such as graph diameter, effective resistance and network criticality. In the third part is given a view on the correlation between the network metrics and graph properties, so the analysis of the properties of the graph that represents the real network, can give pretty good estimation on the network quality in total. Based on this analysis, the graph topology can be optimized, so that the network that it represents can be also optimized to achieve better quality. Such network optimization ultimately leads to improving the QoE level of a network.

 

Тази статия представя корелация между мрежовите показатели чрез свойства на графите и по-специално чрез спектралните характеристики на графите. Работата е в основата на анализа на топологичната структура на мрежата въз основа на съответното представяне на мрежата и нейните свойства чрез графи. В началото е направен преглед на основните показатели на мрежата, които допринасят за качеството на мрежата, гъвкавостта, устойчивостта и производителността, което от своя страна отразява удовлетворението на крайния потребител, което обикновено се измерва с нивото на качество на възприемане. Тези показатели включват, но не се ограничават до: закъснения и време за изпращане и връщане на пакета, джитер, пропускателна способност, загуба на пакети, наличност. Следващата част се фокусира върху топологичните параметри на графите, как те се изчисляват и какъв е техният смисъл в контекста на мрежи. Набляга се върху така наречените спектрални свойства на графите, тъй като те добре представят глобални показатели на топологичната структура по отношение на качество и гъвкавост. Такива свойства на спектралните графи са алгебричната свързаност, спектър на графа и някои от техните производни като диаметър на графа, ефективна устойчивост и критичност на мрежата. В третата част е даден поглед върху корелацията между мрежовите показатели и свойствата на графа, така че анализът на свойствата на графа, който представя реалната мрежа, да може да даде доста добра оценка за качеството на мрежата като цяло. Въз основа на този анализ, топологичната структура на графа може да бъде оптимизирана, така че мрежата, която представлява, също да бъде оптимизирана за постигане на по-добро качество. Такава мрежова оптимизация в крайна сметка води до подобряване на нивото на възприемане на мрежата.

 

Download PDF full text