Date: 12-Feb-19 (Tue)
Time: 12:00
Location: Bldg. 37, room 202
Lecturer: Daniel Khankin
Host: Shlomi Dolev
Title: Algorithms, Techniques and Applications for Virtual Networks
Abstract:
In the first part of this work, motivated by anonymity/monitorability on-demand in SDN-based cloud, we characterize expanders and sparsifiers based virtual networks. Using probabilistic methods, we extend the work by Goyal~et~al. for approximating the expansion of the underlying graph via a random walk based generated random spanning trees. We generalize the proposed approximation technique for the general case of weighted graphs. We show that a union of random spanning trees approximates the expansion of the underlying weighted graph.
In addition, we show that it spectrally approximates the primal graph.
In particular, we show
that a union of $\Theta(\log n)$ trees is required to spectrally approximate a bounded degree graph. This closes a previously open question on the number of trees required for sparsification.
At last, we show that such construction enhances security features in communication networks.
Namely, we show that our proposed method can theoretically improve monitoring or anonymity services that are based on network virtualization of expanders or sparsifiers based topology over the physical network.
In the second part of this work, we study the problem of seamlessly updating routes in a communication network, in the context of SDN. A set of routes pairs $(C_i, N_i)$ is given, where each new $N_i$ should replace the existing $C_i$. Additionally, we require avoiding congestion on links.
We first focus on a single pair of routes and provide a polynomial algorithm for solving the case.
For this, we utilize the \textit{Make-Before-Break} paradigm, in fact, the \textit{Make\&Activate-Before-Break} (MABB) paradigm, and we propose two methods for implementing such paradigm.
In the first method, we perform a careful multicast on both portions of new and current routes.
After two identical packets arrive at the common destination, the controller can dismantle the current part of the route as the new part is ready and operational.
In the second method, we utilize the controller to verify the correct working of the new route before the traffic is redirected and the current route is dismantled.
The controller keeps the
connection operational in order to preserve the functional requirements of the network.
The general routes replacement problem is known to be NP-hard. We suggest using AI methods for solving such a hard problem. For solving it by AI methods, we propose a dependence graph model based on the concept of a new sub-path legal for replacement.
We define which new sub-routes are legal for replacement, and describe the changes in routing and in the dependence graph resulting from launching a legal new sub-route.
