Migration to Software-Defined Networks: the Customers’ View

Tingting Yuan, Xiaohong Huang,＊, Maode Ma, Pei Zhang Institute of Network Technology, Beijing University of Posts and Telecommunications

2 School of Electrical & Electronic Engineering, Nanyang Technological University

* The corresponding author, email: huangxh@bupt.edu.cn

I. INTRODUCTION

TE in the legacy networks usually needs a large number of manual configuration and it’s difficult to integrate networking devices from different suppliers. However, SDN [1] can offer a more flexible and convenient way for the fine-grained TE which is flow-based forwarding different from the TE in conventional IP networks which is the destination-based forwarding [2], [3]. Besides, the SDN can simplify network operations and accelerate service delivery by open standardized interfaces and centralized control. What’s more important is that the migration from the legacy networks to the SDNs can also bring benefits to the customers. Openness which is one of main properties of the SDN can provide customers choice to build the best-of-breed networks.More forwarding paths available to carry the flows from the customers under the control of the central controller can provide more opportunities to establish the demand services specified by the customers and reduce the endto-end delay, therefore to improve the Quality of Experience (QoE) of the customers.

The general traditional network migration is a technical process of upgrading and exchanging the existing hardware/software(infrastructure) to other traditional network devices [4], [5], [6]. In the SDN scenarios, forwarding devices can select not only the port or ports of the shortest paths but also other ports to route flows for one source-destination pair.So, the biggest difference between the general network migration and the migration to the SDNs is whether new paths could be availably controlled and used for TE. Besides, different device migration from the legacy networks to the SDNs will generate different number of available paths. And these new available paths have different path-cost. Path-cost is the sum of metric values on links along the path end to end which can be used to illustrate the path quality. Thus, the quality and the quantity of available paths generated by migration is different.

Due to various reasons, such as operational and economic constraints, the network usually can’t be migrated overnight. Besides, in order to migrate the network from the legacy network to the SDN smoothly, the gradual migration is always chosen by ISPs and network managers. Thus, the network devices can only be substituted by the SDN-enabled devices in batches. During this transition phases, the network is known as a hybrid network with the legacy devices and SDN-enabled devices co-existing [7] [8]. For example, a medium or large-scale Internet Service Provider (ISP)may migrate its current IP networks to the SDNs in a multi-period planning cycle. One question is that the operators should be clear on particular groups of devices to be migrated in various phases. Different migration sequences can bring distinct effectiveness on the ability of the TE and the controllability of the networks. The number of alternative paths which can be used in TE [9], [10] and the network utilization improvement [3], [11] have been considered to determine the migration sequence. Moreover, it should be noticed that different migration schedules can lead to the generation of different new paths, which can be used by different customers to carry their traffic flows. So, it is extremely important but ignored before to design an effective schedule for the network migration in order to achieve better QoE for the customers.

In this paper, we design and propose a novel algorithm to optimize the sequence of SDN migration, referred to as migration scheduling in perspective of customers (OMSB). By OMSB the migration is able to maximize the benefits to customers in terms of the following two aspects: (1) the quantity and quality of the new paths generated by the migration, and (2)the number of the flows and customers that can use these multi-paths. To the best of our knowledge, this is the first work for the design of the optimization schedule for the legacy networks to migrate to the SDNs with the consideration of the customer’s benefits. Our major contribution presented in this paper is that an optimized SDN migration schedule in favor of the benefit of customers is designed and proposed. The beauty of the proposed scheme is that not only the quantity but also the quality of the available paths availed by migration is taken into consideration for the migration scheduling.

The rest of the paper is organized as follows. In Section II, the hybrid SDN environment and the customers’ benefit of migration are discussed. In Section III, the migration problem is formulated as an Integer Linear Programing (ILP) to achieve the optimized scheduling for the network migration. In Section IV, the performance of the proposed scheduling is evaluated by numerical analysis.In section V, a conclusion is provided with a summary.

II. NETWORK MIGRATION SCENARIO

Although the migration of an entire IP network to a SDN network is the final goal of the migration, due to various operational and economic constraints, the network devices can only be substituted by the SDN enabled devices in batches. For example, in each migration period, at most one-third of devices in a network can be migrated to the devices with the SDN functionalities, so three or four periods are required to migrate the entire network with a duration of a few days, weeks or even months. To handle the traffic change in the network during migration periods, there are two choices. The first one is to decide the migration sequence independent of traffic, while the second one is to use traffic pattern which won’t change dramatically in the migration period. And in order to gradually migrate the network to the SDN, the fundamental features of both SDN forwarding devices and the SDN controller should be maintained.

2.1 Hybrid SDNs

It’s assumed that SDN routers have to be capable to exchange the packets with the legacy routers, including the link-state advertisements (LSA) packets. And legacy devices can detect links with SDN-enabled devices and it will be entered in the link state Data Base(LSDB). With Link Layer Discovery Protocol(LLDP), Broadcast Domain Discovery Protocol (BDDP) and link information of legacy routing protocol, the SDN controller has the ability to obtain network information, including the network topology and the metrics of links [11]. For example, Magneto proposed in[12] is a unified network controller that exerts fi ne-grained path control over both Open Flow and legacy switches in hybrid networks. In a conclusion, the controller is able to generate a configuration of the SDN-enabled devices.

2.2 Customer’s benefit of SDN migration

The benefits to customers brought by the migration from the legacy network to the SDN is explained in figure 1, in which there are eleven legacy devices in the network originally.It is assumed that at most three of them can be migrated to the SDN devices in one phase.In each of the first three phases, three devices should be chosen to migrate. And in the last phase, the last two legacy devices should be migrated.

The migration of the legacy forwarding devices to the SDN-enabled forwarding devices can generate new candidate paths which can be used by customers for TE. Table 1 contains the network migration information and candidate paths of the topology in figure 1, where there is no device migrated yet. The link metric, which is marked on the links in figure 1,can be used to calculate the cost of paths. The SRC and the DST are the source and the destination devices of the flows, respectively. The FS and the CN are the data rate of the traffic flows (GB/s) and the number of customers,respectively. The MN is the SDN device. For example, if device M is migrated, it will have the ability to choose next hops linked to it besides c. But as the next hops are legacy devices, they can’t choose paths except the least cost path. So, two new candidate paths can be used for the flows from M to d by customers as showed in table 1 (M → a → b → d and M→ g → c → f → d). Specially, due to a loop in path M → c → g → c → f → d, the cost of it is set to be INFINITE and can’t be select asthe candidate paths by the controller. The last column of table 1 is the cost of paths. The cost of a path can be used to illustrate its quality.The less different between the cost of a candidate path and that of the shortest path of same source-destination pair, the better is this candidate path.

Table I Migration and Candidate Paths

Fig. 1 SDN-Legacy hybrid network in migration

It should be noticed that the migration to the SDN is able to produce benefits to customers, which would be affected by two aspects.One is the quantity and quality of the new paths generated by the migration. For example, if M is migrated, the flows from M to d can be split into multiple paths (M → c → f→ d, M → a → b → d and M → g → c → f→ d). If c is migrated, except the INFINITE cost path, the number of new candidate paths from M to d is 2 which is as many as M is migrated. But the cost of the new candidate path is higher than that caused by the migration of M. However, if K is migrated, there will be no new paths generated for the flows from M to d. For flows over one pair of devices, the more and the better paths obtained by the migration,the more ability the flows of customers in this pair will obtain to make good use of the network capacity and more chances to reduce the flows delay and packet lost. For the flows from M to d, the migration of M will have more benefit compared to the migration of c and K. Similarly, for the flows from K to d,the migration of K firstly is much better with more benefits. The other factor to impact the benefit is the number of the flows that can use multi-paths. The more flows can be transferred by multi-paths, the more benefits the customers will get.

Table II List of Notations

In conclusion, the more and the better paths availed by migration and can be used by more flows, the more benefit the customers will obtain. And the earlier this node should be migrated.

III. OPTIMIZATION PROBLEM FORMULATION

In this section, we present an optimization network migration strategy based on the benefit of customers. The parameters and variables used in our model are summarized in table 2.The network migration includes two steps.The first step is to find the admissible paths and their key devices. Admissible paths are the new manageable paths generated by the migration, which, at the same time, are subject to the limitations in path-cost and length.The second step is to compute the migration sequence. In this work, the issue of migration sequence is formulated as the Integer Linear Program (ILP) problem, which will be used to determine the devices to be migrated in each phase in favor to bringing benefits to customers. Besides, not only the quantity and quality of paths, but the flows pattern is taken into consideration for the scheduling.

3.1 Admissible paths and key devices finding

The admissible paths are the paths can be used in TE and bring benefit to customers, which may not be the least-cost paths. According to the state information of the network, it is possible to find the least-cost path and all the admissible paths for each pair of devices. A key-device of a path is the device have to be migrated to the SDN device first in order to make this path controllable. And for every admissible path, the key devices can be calculated.

Definition 1 The Admissible Paths

A Path with more hops stands for a more bandwidth cost. And the poor paths with more hops or large path-cost barely bring any benefit to customers. In addition, in order to reduce the complexity of the calculation for the migration sequence, two constrains have been set on the candidate paths. The set of admissible paths from i to j of period t:

In order to avoid a loop in a path, the cost of the path with a loop will set to be INFINITE. In (1), not only path-length but also cost of paths is taken into consideration. The cost of paths used here is defined in the OSPF protocol. The parameters are justified with the fact that longer paths with more hops or more path cost imply a decreased benefit, an increased packet delay and more capacity occupation. And depth-first search can be used to find all admissible paths which can meet the(1) restraints. It’s clear that the more admissible paths take into consideration, the better effect for TE. Conversely, more time is taken in finding the admissible paths and the TE schedule.

Definition 2 Key Devices of Admissible Paths

A key device of a path is a device which has to be SDN migrated in order to allow this path to be used by the customers for the TE schedule. A path is available only after all its key-devices have been migrated.

As shown in figure 2, there are three paths from S to D. The link weights are indicated above the link. Path S→a→b→ D is the shortest path without a key device. If S is migrated,the route of S→g→b→D can be availed. So,S is the key device of the route. Similarly, the key-device of S→a→k→D is a.

The generic approach to compute the set of key devices of an admissible path is presented in Algorithm 1. PKp, shown in line 2, is the set of possible key devices of path P. The devices whose connectivity is not less than three are in PKp. And the source of p whose connectivity is not less than two is also in PKp. And the destination of p is not in PKp. In the shortest path between a and the destination of P, the next hop of possible key-device is anextshown in line 5. And anext(P) in line 6 is the next hop of the possible key-device in P. So, if anext(P)is different from anext, the possible key-device will be a key-device of P (line 7-9).

The admissible path S→a→k→D in figure 2 is used as an example. The possible key devices of this path are S and a. The next hop of S in the shortest path from S to D is a. In this admissible path, the next hop of S is also a. So, S is not a key device of this path. But the next hop of a is k in this admissible path,and it is different from that of the shortest path from a to D which is b. So, a is the key device of the admissible path S→a→k→D. And the availability of it only based on whether the device a has been migrated or not.

3.2 Migration sequence computation

Fig. 2 Illustration of the key devices of admissible paths

Algorithm 1 Key devices of an admissible path

During the migration, new admissible paths can be used to route flows from customers.The benefit of customers depends on the quality and quantity of admissible paths that can be used by flows from customers. Besides, the number of flows from customers that can use these admissible paths also make a difference.The benefit of one period t is defined as follow:

Equation (2) is the customers’ benefit of the period t. There are two factors can affect the customers’ benefit. One is the quality and quantity of the admissible paths, and another is how many flows can use these admissible paths. The parameter β and 1−β in (2) are weights. If migration sequence is independent of the flow pattern, β is set to be one.Approaches can be used to estimate the flow pattern. And if the flow pattern won’t change dramatically during migration period, 1−β is set not to be zero. The availability of path p depends on whether all of its key devices have migrated to SDN in (3). And the value of π all depends on the value of variables λ. If all its key-devices have been migrated to SDN, this path is available to be used. The less difference between the cost of admissible path p and that of the shortest path from it o j is better (4).Equation (5) and (6) are nondimensionalized parameters of the quality of paths and the total size of flows from i to j. ωmaxand ωminare the maximum and minimum ωpof all available paths, respectively.

The objective function is to maximize the total benefit of the network and all customers by migration, summarized over the whole planning horizon:

The object is to maximize the benefit of customers of all periods (7).λtnis a boolean variable to determine whether node n should be migrated or not in period t. The left part of (9) is the number of key devices in path p which have been migrated. The right part of(9) is the number of key devices of path p. The key-devices of paths p is always not less than those migrated. The number of devices that may be migrated in a time-step is bounded by the total number of devices in the network averaged over the entire migration period (8).Equation (10) is obtained based on no backwards migration is allowed, so the number of available paths would never be decreased.

problem is not a dynamical problem. So, the time used to compute the migration sequence won’t make a big difference in migration.However, for large scale network, such as network with hundreds or thousands of devices,we can use the greedy algorithm to find a good migration sequence. It greedily chooses devices with maximum customer benefit one by one.

IV. PERFORMANCE EVALUATION

4.1 Experiment design

Networks GERMANY50, COST266 and INDIA35 which are generated in the Survivable fixed telecommunication Network Design library (SNDlib) [13] are used for performance evaluation as shown in table 3. For example,the GERMANY50 in table 3 has 50 nodes, 88 links and 2450 traffic flows. The capacity of the links is assigned randomly between 1Gbit/s and 10Gbit/s. The link weights are assumed to be the inverse of the link capacity. And the traffic matrix was randomly generated between 0 and 100Mbit/s. The number of devices migrated in the first several periods and the last period is called NFL for short. For the GERMANY50, the entire network migration is assumed to have 17 equal periods. In first 16 periods, 3 devices can be migrated in each period, and in the last period only 2 devices should be migrated. As shown in table 3, NFL of GERMANY50 is (3, 2). The migration sequence and the TE schedule is computed on Intel Core i7 (2.9 GHz) and 16GB memory.The Gurobi Optimizer, a programming solver,is chosen to solve the optimization problems in this paper.

1) Migration Schemes for Comparison: Six existing migration approaches are used for the performance comparison. One of migration approaches is Minimize the Maximum Utilization of the network (MMU). The object of the MMU which is proposed in [3] is to migrate the device that gives the highest decrease of the maximum utilization firstly. The object of the second approach, called MNPA for short, is to determine the migration sequence to maximize the number of path alternatives[9]. The third one is to Maximize Diversity(MDI). MDI determines the location based on the path diversity. Diversity denotes that new admissible paths generated by the migrationcan server different pairs (s, d). The fourth approach is the Maximum Degree First (MDF).

Table III Information of Topologies

Fig. 3 Characters and performance with different parameters

Fig. 4 Performance comparison of different schedules in customers’ benefit

The MDF is to greedily pick up legacy nodes with max degrees based on the intuition that heavily connected nodes are likely to be traversed by more end-to-end routing paths. The fifth migration approach is the Maximum Betweenness Centrality (MBC). Betweenness centrality is an indicator of a node’s centrality in a network. It is equal to the number of shortest and available paths from all nodes to all others that pass through the node. The last one is random sequence schemes (RAN).

2) Migration Schedules’ Parameters selection: The TE performance depends on the selection of ε and α in (1). Different parameters(ε and α) mean that different paths can be used for the TE. The horizontal axis of figure 3(a),figure 3(b) and figure 3(c) are the parameters ε and α in (1). Eight pairs of parameters are used for the example in figure 3. Parameters(0, 0) means there are no admissible paths but the shortest paths can be used. All these figures are in the same conditions that 40%devices have been migrated into the SDN by the OMSB scheme.

The vertical axis of figure 3(a) is the number of the available paths. It can be easily seen that the number of admissible paths is different with different parameters. Less hops and cost limitation can offer more admissible paths for the TE. For example, the number of available paths with parameters (1, 1.15) is more than that with (0, 1.05).

In figure 3(b), the vertical axis of it is the time cost to schedule the same traffic. The TE proposed in [3] is used as the TE schedule in figure 3(b). It can be seen that it takes different time for the TE schedule under different parameters. Observing figure 3(a) and figure 3(b)together, we can easily find that these curves are in the similar tendency. More paths for TE schedule always need more time to schedule.For example, the number of paths for TE under parameters (0, Inf) is more than the others,and it also needs more time for the TE.

Figure 3(c) is the max utilization of network with 40% devices migrated under different parameters (ε and α). The more admissible paths take into consideration, the better effect for the flows scheduling in the TE. Conversely, more time is taken in flows scheduling for the TE. However, most of the network providers don’t want to spend a lot of time in sched-uling. The parameters selection is a trade off between performance and time cost. There is an easy way to select proper parameters. For the time cost is an important metric for TE,we can choose parameters based on it. GERMANY50 is used for example. If TE must be done in 5 seconds, then (0, 1.05), (0, 1.15) and(1.1.05) can be used. Besides, the utilization of (1,1.05) is the best. So, (1, 1.05) should be chosen. On other hand, if the performance of network utilization is more important, parameters can be chosen based on performance. For example, if the utilization is expected to be under 0.8 in GERMANY50, then the parameters (0, Inf), (1, 1.05), (1, 1.15), (2,1.05) and(2, 1.15) can be chosen. Among them, (1,1.05)costs the minimum time in TE. So, (1,1.05) is a good choice.

4.2 Performance in terms of customers’ benefit

To compare the performance of different migration schedules, ε=1 and α=1.15 are selected as the parameters of the admissible paths for an illustration. Similar performance can be obtained with other parameters in the migration schedules. And the weight β which is used to calculate the customers’ benefit is assumed to be 0.5. Figure 4 shows the performances of the OMSB, the MMU, the MNPA, the MDI,the MDF, the MBC and the RAN schemes on the benefit for the customers generated by migration under the same parameters, ε=1 and α=1.15, depending on the number of migrated nodes. Different topologies, GERMANY50,COST266 and INDIA35, are used as an illustration in figure 4(a), figure 4(b) and figure 4(c). Figure 4 shows the relationship between the total benefit of the customers and the number of nodes which have been migrated. In figure 4(a), all the curves start at the coordinate origin because before the migration process,none of the routers has been migrated to make any benefit for the customers. All curves also end at the same point because of the independence of the migration schedule and all admissible paths taken into consideration are available after all nodes have been migrated to the SDN-enabled devices. It is obvious that the more devices migrated to the SDN devices, the more benefit the customers will obtain.The OMSB, the MMU, the MNPA and the MDI schemes have an eye caching increase on the benefit for the customers, especially during the early migration period, compared with the others. And when 40% devices have been migrated, these schemes can achieve almost 100% benefit. As shown in table 4, it’s the improvement percentage of the OMSB compared to the other six schemes in figure 4. Table 4(a)shows the average performance improvement made by the OMSB scheme compared to the other six schemes in all the migration periods.Table 4(b) shows the average performance improvement on the first 40% migrated nodes because the migration of the last 60% devices doesn’t bring nearly any benefit, especially,with the advanced migration schemes such as the OMSB, the MMU, the MNPA and the MDI schemes. For example, table 4(a)shows the OMSB scheme can achieve up to 11.25% improvement on average compared to the MMU scheme in the GERMANY50 network. For the first 40% nodes migration in table 4, the OMSB can achieve 27.13%on average improvement. Since the MMU scheme works based on TE, the utilization is more balanced. But the QoE of the customers is not only dependent on the value of the max link utilization. Compared with the MNPA,the OMSB can achieve 13.38% for all and33.21% for the first 40% devices migration.The number of available paths is considered in the scheduling by the MNPA scheme, but it ignores the appraisal of paths and the influence of flows from the customers. However, the OMSB scheme takes them into consideration in the schedule. Compared to the MMU and the MNPA, the MDI scheme has little performance improvement because the MDI takes the priority of path diversity into the consideration for the scheduling. The MDF, the MBC and the RAN schemes are not able to perform very well for the customers. The MDF only takes the number of degree into consideration for the scheduling. And the MBC works based on the centrality. But the number of available paths is not decided by the degree and the centrality. Similar results can be found from figure 4(b) which shows the performance of the COST266 network and figure 4(c) which shows the performance of the of INDIA35 network. As a conclusion, compared to the MMU, the MNPA and the MDI, the benefits of customers produced by the OMSB scheme can increase up to 9%-14% on average and 21%-34% on average for first 40% nodes migration.

Table IV Performance Improvement of OMSB Compared with other Schemes(a) All periods

V. CONCLUSIONS

In this paper, we have addressed the issue of the migration of the legacy networks to the SDNs. We have designed an optimization schedule for the migration in phases in favor of the benefit of customers. Specifically, we have taken not only the quantity and the quality of the paths but also the size of flows into consideration when the migration sequence is generated. By the results of simulation, it is clearly shown that the sequence of migration is very important to customers. Compared with other six existing schemes, the proposed OMSB scheme has demonstrated the best performance for the migration. Compared to the MDF, the MBC and the RAN, the OMSB, the MMU, the MNPA and the MDI schemes have much better performance. Compared to the MMU, the MNPA and the MDI schemes, the benefit for customers produced by the OMSB scheme can increase up to 9%-14% on average and 21%-34% on average for the first 40%nodes migration.

For future study, we want to study how to migrate smoothly with less negative impact on user traffic. We also want to study how to migrate the network to SDN with less migrating periods and migrating time.

ACKNOWLEDGEMENTS

This work has been supported by Joint Funds of National Natural Science Foundation of China and Xinjiang under code U1603261, the Research Fund of Ministry of Education-China Mobile under Grant No. MCM20160304 and the Fundamental Research Funds for the Central Universities.

[1] B. A. A. Nunes, M. Mendonca, X.-N. Nguyen,K. Obraczka, and T. Turletti, “A survey of software-defined networking: Past, present, and future of programmable networks,” IEEE Communications Surveys & Tutorials, vol. 16, no. 3,2014, pp. 1617–1634.

[2] I. F. Akyildiz, A. Lee, P. Wang, M. Luo, and W.Chou, “A roadmap for traffic engineering in sdn-openflow networks,” Computer Networks,vol. 71, 2014, pp. 1–30.

[3] S. Agarwal, M. Kodialam, and T. Lakshman,“Traffic engineering in software defined networks,” Proc. IEEE INFOCOM, 2013, pp. 2211–2219.

[4] D. V. Andrade and M. G. Resende, “Grasp with path-relinking for network migration scheduling,” Proc. the International Network Optimization Conference, 2007.

[5] S. Türk, R. Radeke, and R. Lehnert, “Network migration using ant colony optimization,” Proc.IEEE CTTE, 2010, pp. 1–6.

[6] S. Rajagopalan, “Adoption timing of new equipment with another innovation anticipated,”Engineering Management, IEEE Transactions on engineering management, vol. 46, no. 1, 1999,pp. 14–25.

[7] M. Caria, T. Das, A. Jukan, and M. Hoffmann,“Divide and conquer: Partitioning ospf networks with sdn,” Proc. IEEE IM, 2015, pp. 467–474.

[8] S. Vissicchio, L. Vanbever, and O. Bonaventure,“Opportunities and research challenges of hybrid software defined networks,” ACM SIGCOMM Computer Communication Review, vol.44, no. 2, 2014, pp. 70–75.

[9] M. Caria, A. Jukan, and M. Hoあmann, “A perfor-mance study of network migration to sdn-enabled traffic engineering,” Proc. IEEE GLOBECOM, 2013, pp. 1391–1396.

[10] T. Das, M. Caria, A. Jukan, and M. Hoあmann, “A techno-economic analysis of network migration to software-defined networking,” Proc. IEEE ICC,2014.

[11] D. K. Hong, Y. Ma, S. Banerjee, and Z. M. Mao,“Incremental deployment of sdn in hybrid enterprise and isp networks,” Proc. ACM SOSR,2016.

[12] C. Jin, C. Lumezanu, Q. Xu, H. Mekky, Z. L.Zhang, and G. Jiang, “Magneto: Unified finegrained path control in legacy and openflow hybrid networks,” Proc. ACM SOSR, 2017, pp.75–87.

[13] “Sndlib library,” http://sndlib.zib.de.