The network virtualization allows new on-demand management capabilities, in this work we demonstrate such a service, namely, on-demand efficient monitoring or anonymity. The proposed service is based on network virtualization of expanders or sparsifiers over the physical network. The defined virtual (or overlay) communication graphs coupled with a multi-hop extension of Valiant randomization based routing lets us monitor the entire traffic in the network, with a very few monitoring nodes. In particular, we show that using overlay network with expansion properties and Valiant randomized load balancing it is enough to place @math monitor nodes when the length of the overlay path (number of intermediate nodes chosen by Valiant's routing procedure) is @math . We propose two randomized routing methods to implement policies for sending messages, and we show that they facilitate efficient monitoring of the entire traffic, such that the traffic is distributed uniformly in the network, and each monitor has equiprobable view of the network flow. In terms of complex networks, our result can be interpreted as a way to enforce the same betweenness centrality to all nodes in the network. Additionally, we show that our results are useful in employing anonymity services. Thus, we propose monitoring or anonymity services, which can be deployed and shut down on-demand. Our work is the first, as far as we know, to bring such on-demand infrastructure structuring using the cloud network virtualization capability to existing monitoring or anonymity networks. We propose methods to theoretically improve services provided by existing anonymity networks, and optimize the degree of anonymity, in addition providing robustness and reliability to system usage and security. We believe that, our constructions of overlay expanders and sparsifiers weighted network are of independent interest.
We show that our network architecture is valuable for network monitoring. showed an efficient flooding scheme for generating a collaboration between a group of random walking agents who are released from different sources and at different times @cite_0 . This participation of agents results in a collaborative monitoring infrastructure, requiring only a small number of active monitors.
@cite_0
2160504298
We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time - the expected time required to visit every node in a graph at least once - and we show that for a large collection of interesting graphs, running many random walks in parallel yields a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probablistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected s-t-connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.