Routing-oriented betweenness centrality in communication networks

Project description

Betweenness centrality in networks provides an indication of how much traffic is carried through a particular node or link in the network, under normal operating conditions. Betweenness was introduced by Freeman [1]. It is calculated by considering a unit traffic flow between all node pairs in the network. Each traffic flow is assumed to follow the shortest path between the nodes. The fraction of all traffic flows that traverse a particular node or link provides the betweenness for that node or link.

 

When multiple shortest paths exist between a node pair, traffic is distributed over these multiple shortest paths. The betweenness contribution value on the nodes and links that reside on these multiple paths, is proportional to the distribution of the traffic flow over these multiple shortest paths.

 

The traditional method of calculating betweenness is to distribute the unit traffic flow between a node pair equally over the multiple shortest paths between that node pair. Brandes Betweenness [2] is based on this approach. For telecommunication networks, routing takes a different approach. IP routers in telecommunication networks distribute traffic in accordance with the (remaining) shortest path length, regardless of the number of (remaining) shortest paths. This leads to a different betweenness contribution value on the nodes and links through which the traffic routed between these two nodes. Consequently, the nodes and links in the network have different betweenness value, compared to the traditional method of calculating betweenness.

 

Essentially, the proposed method of calculating betweenness is “routing aware”. This definition of betweenness calls for a different approach towards calculating betweenness for each node and link. As traffic between two nodes flows through the network, the betweenness contribution value on each traversed node and link will be proportional to the distribution of the traffic flow over the multiple shortest paths between these nodes. This method of routing follows the Equal Cost Multipath (ECMP) method of routing [3].

 

In this MSc thesis, the student will do a thorough investigation in graph theory, shortest paths, routing and betweenness. The student will analyse the above-described method of betweenness in communication networks and compare this with the traditional method of calculating betweenness. The thesis comprises theory, algorithm development, programming, simulation and analysis.

 

Keywords: Communication networks, Graph theory, Betweenness, Routing

 

Contact

Rogier Noldus, This email address is being protected from spambots. You need JavaScript enabled to view it.

 

References

[1] Freeman, L. C. (1977). A Set of Measures of Centrality Based on Betweenness. Sociometry, 40(1), 35–41.

[2] Brandes, U. (2001). A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology, 25(2), 163–177.

[3] IETF RFC 2992