A fast and incremental update scheme for SDN based on a relation graph

Configuration consistency during the update process is a critical challenge for network stability in software-defined networking (SDN). An efficient updating scheme with configuration consistency is required. In this paper, we propose a fast incremental consistent update scheme (FICUS) for SDN that is based on a new structure - relation graph (RG). In our scheme, we analyze the relations between update operations, construct the RG and find the proper order of these update operations to avoid inconsistencies. In the RG, we first define two types of relations: the path dependency relation and the path rejection relation. Then, we analyze the properties of the RG and show how we accelerate the calculation of the update order with the help of the RG. To overcome the loops that may exist in the RG, we use two dividing algorithms to break the loops. We also evaluate our scheme and algorithms through comprehensive experiments. The results show that our scheme needs only 10%-40% of the rules compared with the two-phase update scheme and accelerates the update process by 40% on average.