Routing inference based on pseudo traffic matrix estimation

Routing information is so crucial to an operational network that it is always regarded as confidential by network administrators. This paper proposes a novel routing inference method that only needs the knowledge of the network topology and the link counts, both of which can be obtained from MRTG (multi-router traffic grahper) data. The insight is that the traffic observed on each link arises from the superposition of the traffic demands between the origin-destination (OD) pairs and each traffic demand corresponds to a unique path. The method employs expectation maximization (EM) algorithm cooperating with a hypothetic pseudo routing scheme, which is expected to embrace the real routing, to compute a pseudo traffic matrix. The real routing then can be conjectured from this pseudo traffic matrix. This method is applied to a real IP network, and the results show that it correctly infers the routings for 87% OD pairs.