Efficient Gain-Driven Routing-Assisted Mechanisms for Network-wide Traffic Monitoring

Abstract

Network-wide traffic monitoring is of interest to network operators. With constantly changing traffic characteristics and measurement objectives, existing techniques for traffic monitoring tend to be sub-optimal due to poor choice of monitor deployment locations. Routing-assisted network monitoring mechanisms have successfully catered to these needs and are able to maximize the overall traffic monitoring utility of the network by strategically re-directing selected traffic sub-populations over existing deployed monitoring devices. Both the traffic measurement gain of the network and the load-balancing of measurement workloads across distributed monitoring devices are important performance metrics in the design of efficient routing-assisted traffic monitoring mechanisms. This thesis focuses on the design of gain-driven routing-assisted monitoring mechanisms where maximizing the overall traffic measurement gain is our primary design objective. This problem is tackled using two different approaches. First, novel centralized optimal and heuristic routing solutions are proposed for jointly optimizing monitor placement and dynamic routing strategy to achieve maximum measurement gain of the network. Next, we consider the load-balancing problem about how to distribute the network measurement workload across monitoring devices without compromising on the overall traffic measurement gain of the network. Providing effective load-balancing is important since previously-placed monitoring devices may be easily overwhelmed with ever-increasing link rates and increasingly sophisticated measurement tasks. We present an optimization framework called LEISURE (Load-EqualIzed meaSUREment) for load-balancing network measurement workloads across distributed monitors. Finally, a distributed measurement-aware traffic engineering protocol is proposed based on a game-theoretic re-routing policy that attempts to optimally utilize existing monitor locations for maximizing the traffic measurement gain of the network while ensuring that the traffic load distribution across the network satisfies some traffic engineering constraint. It guarantees not only a provable Nash equilibrium, but also a quick convergence without significant oscillations to an equilibrium state in which the measurement utility of the network is close to the maximum achievable gain using offline, centralized routing-assisted network monitoring mechanisms. Both these centralized and distributed routing-assisted approaches improve the overall traffic measurement utility of the network significantly while ensuring low computation complexity.