My Notes From My Notebook

1 Introduction

Major goal of network tomography is to infer the internal characteristics of network by only using data from the end nodes. Each node can either be a computer, router or a subnetwork. Broadly speaking large-scale network inference involves estimating network parameters (can be performance or other) based on traffic measurements at a limited subset of nodes [2]. Network tomography assumes that connections can be directional where data travels from origin to destination and the connections can be uni-directional or bidirectional which changes according to the level of abstraction of the model. During the collection of measurements, some of the data can be missing. Some of the reasons of missing data might be either lossy networks, devices’ load or connectionless UDP protocol.
According to data-collection mechanism, there can be 2 types of network tomography:
• Active Tomography: Active network tomography aims to infer the network’s internal characteristics by sending probe packets (or uses traceroute) from ends.
• Passive Tomography: Passive network tomography infers network information from passive observations of regular network traffic.

Some of the problems in literature about network-tomography (NT) that we are trying to solve are:

• Link-level measurement inference: This is the characterization of latent variables like delay from the observed measurements at the links of network.
• Network topology inference: The task of inferring the network’s topology by only using the end-to-end measurements.
• Sender-Receiver traffic intensity: This is also known as traffic matrices estimation. The task is to estimate the intensity of traffic between two sources.
• Network Anomography: This is the task of inferring anomalies in the network(might be caused by malfunctioning component, malwares or attacks like DDOS) using only the data from the ends.

The mathematical characterization of network tomography problem can be stated as[1]:

Given observations $$Y (t) := [Y_1 (t) . . . Y_l (t)]$$ , over times $$t = 1 . . . T$$ and a matrix $$A(l×κ)$$ such that $$Y (t) = AX(t), ∀t$$ we want to measure the latent variables $$X(t) := [X1 (t) . . . Xκ (t)]$$ over times $$t = 1 . . . T $$. It is always $$κ ≥ l$$ and in general $$κ = O(l^2 )$$.

Many network tomography problems can be approximated by the linear (not necessarily Gaussian) model $$Y (t) = AX(t) + e$$ where X is the $$κ$$ dimensional vector of network dynamic parameters(ex: delay, loss…etc), $$Y$$ is a $$l$$ dimensional measurement vector and hence $$A$$ is the $$l × κ$$ routing matrix. It is difficult to measure the traffic matrices directly. Therefore we try to estimate it by using statistical techniques like maximum entropy[12].

2 Related Works

The term network tomography was first used by Vardi (1996)[11] to capture the similarities between Origin-Destination(OD) traffic matrix estimation through link counts: in network inference, it is common that one does not observe quantities of interest but their aggregations instead and this goes beyond OD estimation. Vardi, also devised the linear tomography Poisson model for OD traffic estimation and the linear form [11] is shown later to approximate other network tomography problems [2]. Network Tomography tries to infer the latent variables and usually observed variables of the data is very limited. In that sense Network Tomography is an ill-posed inverse problem. Current approaches in network tomography uses a limited number of measurements to infer the network performance parameters, by using:

• Maximum Likelihood Estimator.
• Bayesian Inference.

and assuming a prior model.

Venkata et al(2003)[7], used Bayesian inference with Gibbs sampling for only using a number of lost and number of sent packets throughout the network. But although their model could give information about bottlenecks in the network, the model’s accuracy suffers. Nowak et al [2] [3] used MCMC to estimate MAP and EM to estimate MLE of the delays. In [6] Liang et al developed a pseudo EM to maximize the pseudo log-likelihood function. In order to illustrate the pseudo likelihood proposal, they inferred the internal link delay distribution and OD matrix estimation from link measurements. M. Rabbat et al in [8] inferred the network structure from the co-occurence data. Network elements that co-occur in many observations are assumed to be closely connected. Particularly, network elements that co-occur in many observations are probably closely connected and they modeled the co-occurrence observations as independent realizations of a random walk on the graph, subjected to a random permutation which accounts for the lack of order information. Treating the permutations as missing data, Rabbat et al employed MCEM algorithm with importance sampling for estimating the random walk parameters. As a result they were able get an accurate model of the network.

3 Possible Approaches to Attack the Problem

Queue management is an important aspect of routers. Routers have several interfaces (inif-ingrees, outif-egress) which each link is connected to and the data comes from these interfaces processed by a FPGA or specific multi-core CPU’s. Packets from different queues are processed in a FCFS and round-robin way. Hence it is a natural way to use queuing networks to model the routers’ behavior. Internet is built on the distributed networks scattered around the world and naturally measurements in the end-points can be modeled with queuing networks and graphical models which also allows us to apply Markov chain Monte Carlo for the missing data. C Sutton et al developed a model for Bayesian inference in queuing networks [10], [9] and obtained satisfactory results in their test for the web servers. In a similar fashion, using queuing networks for network tomography might be a more realistic model. Thus I expect that it will yield better accuracy for the estimation of throughput and RTT (round trip-time). Because the large amount of data-processing we’ll need to parallelize and adapt scalable approaches for the machine learning algorithms to be used.Sensor-networks are becoming more ubiquitous and Internet is moving from client-server architecture to the P2P architecture. These networks have specific importance in network tomography. Because there is no other efficient way to have information about the networks internal characteristics. There are some challenges that network tomogoraphy for these networks are bringing to like massive data load and lack of ends. Because every node can be an end. Thus there is no specific end. It might be more efficient to get measurements from supernodes. Network coding[4] is a new technique for modeling network and it has many applications in network tomography. This model is very suitable for bayesian causality and belief propagation. The possibilities should be investigated. Apart from the network’s internal characteristics, it is possible to approximate the router’s internal characteristics like cpu load and temperature with a sampler like MCMC.

With the recent revision of SNMP protocol it is possible to get different types of measurements from MIB’s like the number of in and out connections of a host (this data can be obtained from SNMPv2 by implementing a simple SNMP agent). It is possible to predict device’s connection behavior in an evolving network similar to the social network analysis and protein-protein interaction predictions. This problem is highly structured and device’s behavior is highly correlated with the number of incoming and outgoing connections. Therefore I believe it is possible to use CRF for network’s hosts’ behavior analysis [5]. Flow exporting from routers is an expensive procedure so routers use sampling (e.g.: trajectory sampling) and the missing data problem in that case can be solved with MCMC by sampling from the posterior distribution.

References

[1] E.M. Airoldi and C.N. Faloutsos. Advances in network tomography. Citeseer, 2003.
[2] A. Coates, AO Hero Iii, R. Nowak, and B. Yu. Internet tomography. Signal Processing Magazine, IEEE, 19(3):47–65, 2002.
[3] M.J. Coates and R.D. Nowak. Network tomography for internal delay estimation. In Acoustics, Speech, and Signal Processing, 2001. Proceedings.(ICASSP’01). 2001 IEEE International Conference on, volume 6, pages 3409–3412. IEEE, 2002.
[4] C. Fragouli, J. Le Boudec, and J. Widmer. Network coding: an instant primer. Computer Communication Review, 36(1):63, 2006.
[5] T. Karagiannis, K. Papagiannaki, and M. Faloutsos. BLINC: multilevel traffic classification in the dark. In Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications,pages 229–240. ACM, 2005.
[6] G. Liang and B. Yu. Maximum pseudo likelihood estimation in network tomography. Signal Processing, IEEE Transactions on, 51(8):2043–2053, 2003.
[7] V.N. Padmanabhan, L. Qiu, and H.J. Wang. Passive network tomography using bayesian inference. In Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurement, pages 93–94. ACM, 2002.
[8] M.G. Rabbat, M.A.T. Figueiredo, and R.D. Nowak. Network inference from co-occurrences. Information Theory, IEEE Transactions on, 54(9):4053–4068, 2008.
[9] C. Sutton and M.I. Jordan. Inference and Learning in Networks of Queues. 3
[10] C. Sutton and M.I. Jordan. Bayesian Inference for Queueing Networks and Modeling of Internet Services. Arxiv preprint arXiv:1001.3355, 2010.
[11] Y. Vardi. Network Tomography: Estimating Source-Destination Traffic Intensities from Link Data. Journal of the American Statistical Association, 91(433),1996.
[12] Y. Zhang, M. Roughan, C. Lund, and D. Donoho. An information-theoretic approach to traffic matrix estimation. In Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, pages 301–312. ACM, 2003.

Related Posts:

• Esoteric Algorithms and Esoteric Programming Languages
• Should implementing ML algorithms banned for Production Systems?
• Network Anomaly Detection