Dependence graph and master switch for seamless dependent routes replacement in SDN (extended abstract)
Yefim Dinitz, Shlomi Dolev, Daniel Khankin · 2017
We study the problem of seamlessly updating several routes in a network, in the context of Software-Defined Networking (SDN). A set of routes pairs (Ci, Ni) is given, where each new Nishould replace the existing Ci. We look for a way of gradual updating, so that routing cycles are never created during the replacement process. In that, we follow the recent paper of Delaet et al., which considered the case of updating a single route. In addition, we require avoiding congestion on links. We provide an example of several routes replacement, where the strategy suggested by Delaet et al. fails: it arrives at a deadlock, while a legal way of replacement exists. We suggest a dependence graph model for solving the problem. The dependence graph nodes are: a) the sub-routes resulting from sub-dividing all Niand Ciby the routers common to Niand Ci, and b) the potentially congested links. We define which new sub-routes are legal for replacement. Further, we describe the changes in routing and in the dependence graph resulting from launching a legal new subroute. Summarizing, we reduce the route replacement problem to finding an (optimal) sequence of launchings of currently legal new sub-routes, using the dynamic dependence graph. Moreover, we suggest a novel meta-approach for resolving deadlocks, by utilizing the optical wires that connect the SDN controller to the routers.