Routing Optimization For Cloud Services in SDN-based Internet of Things With TCAM Capacity Constraint

Shizhong Xu , Xiong Wang , Guangxu Yang , Jing Ren and Sheng Wang

Abstract

Abstract: Distributed in-network cloud architecture is a promising solution to efficiently host next generation internet-of-things (IoT) services. With the rapid increase of IoT devices and applications, the backhaul or backbone networks, which transmit IoT traffic to various in-network clouds, will experience a predicted explosion in the volume of carried traffic. To guarantee the QoS of IoT cloud services and improve the network performance, it is crucial for network operator to implement efficient routing optimization strategies for IoT traffic. As a promising networking paradigm, software-defined networking (SDN) has flexible and programmable control capability for fine-grained flows. The emergence of SDN paves a way for implementing high-performance routing optimization in networks. In SDN networks, the routing strategies are realized through flow rules, which are usually stored in TCAM with very limited capacity. However, the number of IoT flows are enormous. Thus, in this paper, we address the routing optimization problem in SDN-based IoT with TCAM capacity constraint. We first formulate the problem as a mixed integer linear programming problem and prove the problem is NP-hard. Then to solve the problem efficiently, we propose several approximate algorithms, which solve the problem in two stages. In the first stage, the algorithms calculate the routing strategies for flows without considering the TCAM capacity constraint. To meet the TCAM capacity constraint, the algorithms using different strategies to adjust the paths of some flows in the second stage. Extensive simulations are conducted on both real ISP and synthetic topologies to evaluate the performance of the algorithms. The simulation results verify that the algorithms can achieve promising load balancing performance in SDN-based IoT, where the capacity of TCAM in SDN switches is very limited.

Keywords: internet of things , routing optimization , softwaredefined networking , ternary content-addressable memory

1. Introduction

Internet of things (IoT) is an emerging network paradigm, which refers to the networking of devices, vehicles, buildings, machines, and other objects. The connected IoT objects sense, process and share real-time information about the phys-

Fig. 1.
The architecture of IoT.

ical world [1]. This emerging paradigm enables a new breed of applications in many different domains, such as medical aids, industrial automation, smart grids, intelligent home, and intelligent transportation [2]. Due to the intrinsic limitations of lightweight IoT devices (e.g., battery capacity, computation power, and storage space), many of the applications process and analyse the data collected from multiple devices in cloudlets [3] or micro-clouds [4], which are distributively located at different network nodes in future networks (as shown in Fig. 1).

On the other hand, with the predicted explosion in the number of IoT applications and connected devices [5], the volume of data required to be sent to nearby clouds through backhaul network will increase explosively in the near future, which may lead to high network congestion. Furthermore, many IoT applications, such as remote medical aids, intelligent transportation, and industrial automation, have strict QoS requirements. Thus, to avoid network congestion and guarantee the QoS requirements of IoT applications, it is essential to implement routing optimization (RO) strategies for flows. The RO is to adapt the routing of traffic to the changing traffic patterns. Since RO is an efficient way to improve user experience and network performance without upgrading network infrastructure, the RO has attracted enormous attention from both academic and industrial communities [6] in the past decades. However, due to the lack of flexible routing control capacity, it is hard for the traditional networks to achieve satisfactory performance with acceptable cost. For example, it is hard to get the optimal traffic distribution by adjusting the OSPF link weights, and it is costly to deploy explicit routing protocols, such as multi-protocol label switching (MPLS) [7] and segment routing [8].

To enhance the control plane flexibility of networks, the software-defined networking (SDN) is proposed [9]. SDN is a programmable networking paradigm, which separates the control and data planes in a network. The control plane runs on logically centralized network controllers, and the data plane located in each SDN switch. Network controllers provide program interfaces for various network applications and control the behaviors of SDN switches using standardized protocols (e.g., OpenFlow [10]). This functional separation and the implementation of control plane functions on powerful centralized platforms bring various expected operational benefits, such as programmability, flexibility, and global view of the network state. With the help of programmable and centralized network controllers, SDN networks have fine-grained and flexible routing control capability, which is achieved by modifying the flow rules residing in flow tables of SDN switches. Thus, the deployment of SDN paves a way for implementing efficient and online RO according to the changing traffic pattern. It has been shown that in SDN-enabled production networks, the RO can achieve near-optimal performance in the aspects of throughput and link utilization [11], [12].

In SDN networks, different routing strategies are realized by installing different flow rules in each SDN switch. To forward packets in line-rate, the flow rules are usually stored in ternary content-addressable memory (TCAM), which can perform parallel wildcard matching at high speed. However, TCAM has high power consumption and large footprint, leading to high heat generation [13], and TCAM is also very expensive [14]. Therefore, the capacity of TCAM in commodity SDN switches is very limited, e.g., many SDN switches usually only have 10K to 40K TCAM entries [15]. In contrast, there may be a huge number of cloud service flows (we use flows for short in this paper) going through an SDN switch in IoT, e.g., the number of fine-grained flows going through an SDN switch can be up to 1000K [16]. Thus, it is impossible to use a dedicated flow rule to process the packets of each flow. Since the static random access memory (SRAM) have a larger capacity and is cheaper than TCAM, some studies [17] implement flow tables in SRAM. But SRAM based flow tables have much higher implementation complexity than TCAM based flow tables, and it is also very challenging for the SRAM based flow tables to realize line-rate wildcard lookup [18]. Furthermore, the flow rule updating procedure in SDN switches is quite slow (e.g., about 40 to 50 rule updates per second [19]), updating a large number of flow rules will take a long time, which makes the routing strategies lag behind traffic variation. Therefore, a more efficient way is to calculate routing strategies under the TCAM capacity constraint.

In another hand, as it happens on most emerging network architectures and protocols, upgrading traditional networks to SDN networks cannot be realized at once, especially for large networks. The reason is twofold: First, an upgrade of an entire network requires huge capital expenditures since high-speed network device is expensive; Second, the one-step upgrade also raises performance and security risks due to the lack of operational experience for SDN networks. Therefore, large network providers usually prefer to incrementally deploy SDN devices in their existing networks. As a result, hybrid SDN architecture is likely to be a long-term solution for productive networks [20]. We also consider hybrid SDN networks in this paper.

The RO problem in SDN networks has attracted many research interests in recent years. However, to the best of our knowledge, the TCAM capacity constraint is not considered in the existing studies, which makes the existing algorithms hard to be used in networks carrying IoT traffic. In this paper, we investigate the RO problem under the TCAM capacity constraint in hybrid SDN-based IoT. Since full SDN-based IoT can be viewed as special cases of hybrid SDN-based IoT, the algorithms designed for hybrid SDN-based IoT in this paper can also be used in full SDN-based IoT. Our contributions are summarized as follows.

i We address the RO problem under the TCAM capacity constraint in hybrid SDN-based IoT. We first formulate the problem as a mixed integer linear programming (MILP) problem, and then we prove that the problem is NP-hard.

ii To efficiently tackle the problem, we propose several approximate algorithms with different complexity to solve the problem.

iii We conduct extensive simulations to evaluate the performance of the proposed approximate algorithms. The simulation results show that the proposed approximate algorithms can find near-optimal routing solutions for the flows under the TCAM capacity constraints, and by carefully selecting the paths for flows, we can achieve promising load balancing performance with a small number of TCAM entries in each SDN switch.

The remainder of this paper is organized as follows: Section II reviews related work. Section III formulates the RO problem in IoT. Section IV presents the approximate algorithms designed for solving the RO in IoT. Section V evaluates the proposed algorithms. Finally, Section VI summarizes the paper and presents the main conclusions.

II. RELATED WORK

The RO aims to adapt the routing of traffic to network conditions, with the goals of improving user experience and network performance. Since RO is an efficient scheme to improve network service capability without upgrading network infrastructure, it has attracted extensive attentions from both academic and industrial communities. During the last decades, IP based [22], MPLS based [23], [24], and segment routing based RO [25] schemes have been proposed to improve the network performance and meet the quality-of-service (QoS) requirements of applications. We refer the reader to [26], [27] for exhaustive surveys of the work on the RO problem in traditional networks. However, due to the limitations of traditional network architecture, the existing RO schemes suffer from many problems, such as low flexibility, low scalability, low performance, and high operational cost [28].

To cope with the limitations of the traditional network architecture, the SDN paradigm is proposed. SDN decouples the forwarding and control planes of a network system [21], so that network operators can program packet forwarding behavior based on the global view of network status. The SDN pave a way for implementing flexible and fine-grained RO, which can significantly improve the network performance and resource utilization. Microsoft [11] and Google [12] have deployed SDN in their inter-data center networks, and their operational results show that the SDN-enabled networks can achieve near-optimal performance in the aspect of throughput and link utilization by implementing RO.

Most RO problems in full SDN networks (all nodes are SDNenabled) are equivalent to the multicommodity flow problems [29], which have been well studied. Nevertheless, fully deploying the SDN in the existing network will not work out in a short term due to the budget and operation constraints [30], [31]. Deploying SDN in network incrementally should be a natural choice. Thus, the RO problem in hybrid SDN networks attracts more attentions [32]–[36]. S. Agarwal et al. [32] first address the RO problem in hybrid SDN networks. They formulate the RO problem as a linear programming problem and propose a polynomial algorithm with performance bound to calculate paths and flow splitting strategies for the flows. Similar to the work in [32], He et al. also propose polynomial algorithms with performance bound to solve the RO problems for two hybrid SDN network models. In [32], [33], the link weights are fixed and all link weights are assumed to be 1. To further improve the RO performance, Guo et al. [34] propose to jointly optimize OSPF link weights and flow splitting ratios of the SDN switches in hybrid SDN networks. Furthermore, to guarantee forwarding consistency in hybrid SDN network, Wang et al. [35] optimize traffic distribution on constructed forwarding graphs. In SDN networks, the SDN switches use flow rules usually installed in TCAMs to math and forward flows. Since the TCAM is expensive and power hungry, the capacity of TCAM is very limited. To mitigate the impact of TCAM space limitation on the RO performance, S. Zhang et al. [36] propose TCAM space aware RO algorithms, which try to minimize the TCAM space consumption while optimizing flow routing. Even though the TCAM space aware RO algorithms can reduce the required TCAM entries, they are also hard to meet the TCAM capacity constraint, especially when there are a large number of flows.

On the other hand, the SDN deployment strategy also has an impact on the RO performance of hybrid SDN networks. Y. Guo et al. [37] propose a heuristic algorithm to find a migration sequence of traditional routers to SDN switches that obtains the most of the benefits from the perspective of RO. Furthermore, K. Poularakis et al. [38] consider a more practical model that captures time-varying migration costs, network topologies, and two objectives benefiting for RO. These work consider the objectives benefiting for RO when make SDN deployment decisions. However, these work are different from the work in this paper for the following two reasons: First, these work pursue the indirect objectives benefiting for RO (e.g., maximize programmable traffic or routing flexibility), but our work directly optimizes the traffic distribution objective (e.g., load balancing); Second, these work calculate SDN deployment strategies, while our work optimizes the routing for flows.

In summary, the RO problem in hybrid SDN has gained many attentions due to the important role of RA. The SDN networks rely on flow rules installed in TCAM entries to realize routing strategies. So in real SDN networks, the routing strategies would likely be unrealizable due to the TCAM capacity limitation. Therefore, the TCAM capacity constraint must be considered when we optimize routing strategies, especially for IoT, where the number of flows is much more than that of available

Fig. 2.
An example for routing optimization in hybrid SDN-based IoT.

flow rules. However, to the best of our knowledge, all the existing work do not consider the TCAM capacity constraint.

III. PROBLEM FORMULATION

A. Network Model and Assumptions

We model an SDN-based IoT as a connected undirected graph G(V,E), where V is the set of nodes and E is the set of links. The cloudlets [3], which provide computing and storage capabilities for IoT services, are deployed at some network nodes. Each link [TeX:] $$e \in E$$ has a capacity c(e) and a weight w(e). Since deploying SDN devices incrementally is a natural choice for network providers [38], we in this paper also consider hybrid SDN networks, where only a subset of the nodes are SDN switches and the rest of the nodes are traditional routers. We assume that the set of nodes deploying with SDN switches are given. Let [TeX:] $$V_{S D N}$$ and [TeX:] $$V_{I P}\left(V=V_{S D N} \cup V_{I P}\right)$$ denote the sets of SDN nodes and IP routers, respectively. The IP routers must forward packets to the adjacent nodes on the shortest paths determined by the link weights, while the SDN switches can forward packets to any adjacent nodes according to the rules stored in TCAM. Since TCAM is expensive and power hungry, the capacities of TCAM in switches is very limited. Let [TeX:] $$\gamma(v)$$ be the number of available (i.e., unused) TCAM entries in SDN node [TeX:] $$v\left(v \in V_{S D N}\right).$$

The set F of flows in the network is given. In SDN-based IoT, the granularity of flows can be flexibly defined by the matching fields allowed by SDN. For example, a flow can be either a TCP streaming video flow or an aggregated flow between two subnetworks. Each flow [TeX:] $$f_{i} \in F$$ can be represented as a three-tuple [TeX:] $$\left(s_{i}, d_{i}, h_{i}\right),$$ where [TeX:] $$s_{i} \text { and } d_{i}$$ are the source and destination nodes of [TeX:] $$f_{i},$$ respectively, and [TeX:] $$h_{i}$$ is the volume of flow [TeX:] $$f_{i}.$$ In hybrid SDN networks, some paths are infeasible due to the shortest path routing constraint of traditional IP routers. For example, the path A - B - C - E - F in Fig. 2 is infeasible since IP router C running OSPF protocol cannot forward packets destined to node F via link (C,E). For hybrid SDN networks, a path p from source node s to destination node d is termed feasible if it satisfies the following two constraints:

c1 For each non-SDN node [TeX:] $$u \in p,$$ link (u, v) is on the shortest path from node u to node d, where v is the next node of u on path p.

c2 The path p is loop-free.

We use [TeX:] $$P_{i}$$ to denote the set of feasible paths for flow [TeX:] $$f_{i},$$ and the feasible path set [TeX:] $$P_{i}$$ is calculated in advance. To reduce the complexity, we calculate at most k feasible paths for each flow. We use an algorithm modified from the k-shortest path algorithm to calculate at most k feasible paths for each flow. The k-shortest path algorithm generates candidate paths from each node on an existing path. However, in hybrid SDN networks, a non-SDN node cannot forward a flow to a neighbor that is not on the shortest path from the non-SDN node to the destination node of the flow. Thus, the modified algorithm only generates candidate paths from the SDN nodes on an existing feasible path. To ensure that the returned paths are feasible, the infeasible paths generated by the modified algorithm will be ignored. The algorithm for calculating feasible paths for a flow [TeX:] $$f_{i}$$ is shown in Algorithm 1.

If there are enough TCAM entries in an SDN switch, the SDN switch can use a dedicated flow rule to forward each flow. However, it is not possible due to the hard constraint of TCAM capacity. Similar to the traditional IP routers, SDN switches can also aggregate the rules with the same prefix and action to one rule. To save TCAM entries, we assume that initially, all SDN switches use only one rule to forward the packets destined to each node, i.e., the rules for the packets with the same destination IP address are aggregated into one rule. Without loss of generality, we assume that in default, the flows are forwarded by aggregated rules, which forward flows along the shortest paths. To improve the RO objective, the available TCAM entries in SDN switches can be used to adjust the paths of the flows going through the SDN switches. Let us consider the example in Fig. 2. In Fig. 2, the numbers on the links denote the link weights, and there are two flows [TeX:] $$\left(f_{A F} \text { and } f_{B F}\right)$$ requiring 1 unit bandwidth. Since the two flows are destined to the same node, the two flows will be forward to node D by the aggregation rule in SDN switch B, leading to traffic congestion on link (B,D) (Fig. 1(a)). To achieve load balance, a flow rule with a longer prefix and a higher priority can be added in node B to forward flow [TeX:] $$f_{A F}$$ to node E (Fig. 2(b)).

B. The Routing Optimization Problem with TCAM Capacity Constraint

Given the hybrid SDN-based IoT G(V,E), the set F of flows, and the set [TeX:] $$P_{i}$$ of feasible paths for each flow [TeX:] $$f_{i} \in F,$$ the RO problem under the TCAM capacity constraint can be formulated as a MILP problem. For ease of description, the notations used in the formulation are summarized in Table 1.

To avoid network congestion, the optimization objective considered in this paper is maximum link utilization (MLU), which is a widely used metric for load balancing [29], [32]. The RO problem tries to minimize the MLU by selecting proper forwarding paths for the flows:

Calculating Feasible Paths For a Flow
Table 1.
The notations used in the formulation.

(1)
[TeX:] $$\operatorname{minimize} \quad \lambda.$$

To accommodate each flow [TeX:] $$f_{i} \in F, $$ a path must be selected from the set [TeX:] $$P_{i}$$ for the flow:

(2)
[TeX:] $$\sum_{p \in P_{i}} x_{i p}=1 \quad \forall f_{i} \in F.$$

For each SDN node [TeX:] $$u \in V_{S D N},$$ an available flow rule is required to forward flow [TeX:] $$f_{i}$$ to a link [TeX:] $$(u, v) \in E,$$ which is not on the shortest of flow [TeX:] $$f_{i}.$$ In this case, a flow rule in SDN node u is used to adjust the forwarding path of flow [TeX:] $$f_{i}$$ to a non-shortest path, and the variable [TeX:] $$\theta_{i u}$$ must be equal to 1.

(3)
[TeX:] $$\sum_{p \in P_{i}} \omega_{i p}^{u} x_{i p} \leq \theta_{i u} \quad \forall f_{i} \in F, u \in V_{S D N}.$$

To ensure that all the required flow rules can be installed in TCAM, the following TCAM capacity constraint for each SDN node [TeX:] $$u \in V_{S D N}$$ must be satisfied.

(4)
[TeX:] $$\sum_{f_{i} \in F} \theta_{i u} \leq \gamma(u) \quad \forall u \in V_{S D N}.$$

At last, we have the link utilization constraint for each link [TeX:] $$e \in E:$$

(5)
[TeX:] $$\sum_{f_{i} \in F} \sum_{p \in P_{i}} x_{i p} h_{i} \xi_{i p}^{e} \leq \lambda c(e) \quad \forall e \in E.$$

The complexity of a MILP problem is known to be exponential, i.e., [TeX:] $$O\left(2^{N}\right),$$ where N is the number of integer variables. Thus the MILP formulation presented above has an exponential complexity with N in [TeX:] $$O(|V||F|),$$ which makes it computationally expensive in large networks. Theorem 1 shows the problem is NP-hard.

Theorem 1: The RO problem with TCAM capacity constraint in hybrid SDN networks is NP-hard.

Proof: We now prove that the RO problem with the TCAM capacity constraint is NP-hard, by conducting a reduction from the k disjoint route problem to the RO problem with the TCAM capacity constraint. An instance of the k disjoint route problem is given by a graph [TeX:] $$G_{1}\left(V_{1}, E_{1}\right)$$ and a set O of k distinct node pairs. It asks for calculating k mutually link-disjoint paths for the k node pairs. This problem is known to be NP-hard [39].

We can easily conduct a reduction from the k disjoint routing problem to the RO problem with TCAM capacity constraint as follows. Let an instance [TeX:] $$I_{\infty}$$ of the k disjoint problem be given by [TeX:] $$G_{1}\left(V_{1}, E_{1}\right) \text { and } O=\left\{o_{1}, o_{2}, \cdots, o_{k}\right\}.$$ Based on the given instance [TeX:] $$I_{\infty},$$ we construct an instance [TeX:] $$I_{2}$$ of the RO problem with TCAM capacity constraint in the following way. Let [TeX:] $$G_{2}\left(V_{2}, E_{2}\right)=G_{1}\left(V_{1}, E_{1}\right),$$ and set the capacity of each link of graph [TeX:] $$G_{2}\left(V_{2}, E_{2}\right)$$ and the TCAM capacity of each node to 1 unit and k, respectively. For each node pair [TeX:] $$o_{i}=<s_{i}, d_{i}>\in O,$$ we add a flow [TeX:] $$f_{i}$$ between nodes [TeX:] $$s_{i} \text { and } d_{i}$$ to flow set F. The volumes of the flows are 1 unit. Clearly, [TeX:] $$\mathcal{I}_{\in}$$ can be constructed from [TeX:] $$\mathcal{I}_{\infty}$$ in polynomial time. It also can easily verify that the k disjoint route problem has a solution if and only the constructed RO problem has a solution with maximum link utilization 1, and the two solutions share the same paths.

Hence, to efficiently solve the RO problem in large networks, we propose approximate algorithms in Section IV.

IV. THE APPROXIMATE ALGORITHMS

We have shown that the RO problem with TCAM capacity constraint is NP-hard in Section III. B. Thus, to efficiently solve the problem, we propose approximate algorithms. In order to reduce the complexity, we solve the RO problem with TCAM constraint in two stages. In the first stage, we ignore the TCAM capacity constraint and optimize the flow routing such that the maximum link utilization is minimized. Given the paths calculated for the flows in the first stage, we need to adjust the paths of some flows to meet the TCAM capacity constraint in the second stage. For ease of description, the problems solved in the first and second stages are called minimum congestion routing (MCR) and routing adjustment (RA) problems, respectively. In this section, we will present the approximate algorithms for solving the MCR and RA problems.

A. The Minimum Congestion Routing Problem

Given the network topology G(V,E) and the set F of flows, the MCR problem can be formulated as:

61)
[TeX:] $$\operatorname{minimize} \quad \lambda$$

(7)
[TeX:] $$\sum_{p \in P_{i}} x_{i p}=1 \quad \forall f_{i} \in F$$

(8)
[TeX:] $$\sum_{f_{i} \in F} \sum_{p \in P_{i}} x_{i p} \xi_{i p}^{e} \leq \lambda c(e) \quad \forall e \in E$$

(9)
[TeX:] $$x_{i p} \in\{0,1\} \quad \forall f_{i} \in F.$$

The MCR problem is also NP-hard [32]. Thus, we use two approximate algorithms with performance bound to get the routing solution for the MCR problem. The two approximate algorithms for the MCR problem are called randomized rounding algorithm (RRA) and online algorithm (OA) [40], respectively. By using the two algorithms, we can get near-optimal routing solution for the RO problem without TCAM capacity constraint.

(1) The Randomized Rounding Algorithm

In the MCR problem, the decision variable [TeX:] $$x_{i p}$$ is a binary variable, which restricts the route of flow [TeX:] $$f_{i}$$ to a single path. If we relax the binary constraint [TeX:] $$x_{i p} \in\{0,1\} \text { to } 0 \leq x_{i p} \leq 1,$$ the relaxed MCR problem is equivalent to maximum concurrent flow (MCF) problem [42]. The RRA first calculates a fractional flow routing solution for the MCF problem, and then it uses the randomized rounding strategy [41] to get a single-path routing solution for the MCR problem based on the fractional flow routing solution. Algorithm 2 shows the detailed procedure of RRA.

In the first step (line 3), the RRA uses a fully polynomial time approximation scheme (FPTAS) [32] (Algorithm 3) to calculate routing strategy for the MCF problem. An FPTAS can guarantee that for any [TeX:] $$\epsilon>0,$$ the solution found by it has objective value with [TeX:] $$(1+\epsilon)$$ -factor of the optimal, and the running time is as most a polynomial function of the network size and [TeX:] $$1 / \epsilon.$$ Here, the complexity of Algorithm 2 is [TeX:] $$O\left(\epsilon^{-2} m^{2} \log ^{O(1)} m\right),$$ when is set to

[TeX:] $$\delta=\frac{1}{(1+n \epsilon)^{\frac{1-\epsilon}{\epsilon}}}\left(\frac{1-\epsilon}{m}\right)^{\frac{1}{\epsilon}}.$$

The proof for the running time can be found in [42].

In the second step (lines 4-9), RRA chooses a path for each flow [TeX:] $$f_{i} \in F$$ from its candidate path set calculated in the first step. Intuitively, a path carries higher traffic volume for flow [TeX:] $$f_{i}$$ should be more likely to be chosen as the path for flow [TeX:] $$f_{i}.$$ Therefore, RRA chooses path [TeX:] $$p_{i}^{k}$$ as the path for flow [TeX:] $$f_{i}$$ with

Randomized Rounding Algorithm
Maximum Concurrent Flow Algorithm

probability [TeX:] $$f_{i}^{k} / \sum_{j \in P_{i}} f_{i}^{j}, \text { where } P_{i}$$ is the set of candidate paths calculated for flow [TeX:] $$f_{i}$$ in the first step, and [TeX:] $$f_{i}^{j}$$ is the volume of flow [TeX:] $$f_{i}$$ carried on path [TeX:] $$p_{j} \in P_{i}.$$

(2) The Online Algorithm

The FPTAS used in the RRA takes [TeX:] $$O\left(\epsilon^{-2} m\right)$$ time to calculate fractional routing solution for the MCF problem. So RRA will take a long time to get the solution if we use a small [TeX:] $$\epsilon$$ (see Section V. B). To speed up the routing calculation process, we

Online Algorithm

need to use a faster algorithm, which routes each flow with only one iteration. Furthermore, the set of flows must be given in advance in RRA. However, the flows may arrive on the fly, and thus it is desired to use an OA [40] to route every newly arrived flow.

The detailed procedure of OA is shown in Algorithm 4. Here, is the step size of the link weight update. In the ith iteration, the OA first finds the shortest path [TeX:] $$p_{i}$$ from the feasible path set [TeX:] $$P_{i}$$ for flow [TeX:] $$f_{i}$$ under the link weights [TeX:] $$w=\{w(1), w(2), \cdots, w(|E|)\}$$ (line 3), and then it updates the utilizations and weights of the links that are traversed by path [TeX:] $$p_{i}$$ (line 4).

Since RRA uses the randomized rounding strategy to get a single-path routing solution for the MCR problem, RRA performs better when the number of flows is larger. This is because when the number of flow is large, the results returned by RRA are very close to the expectation result. In contrast, the OA performs better than RRA when the number of flows is small.

B. The Routing Adjustment Problem

In the first phase, we solve the MCR problem without considering the TCAM capacity constraint. Thus, the paths calculated for the flows in the first phase will likely not be able to be realized in SDN networks due to the TCAM capacity constraint. In the second phase, we will adjust the paths for some flows to meet the TCAM capacity constraint. The key idea of routing adjustment is to adjust some paths requiring TCAM entries to the shortest paths. Three routing adjustment strategies, which are called global-optimal strategy (GOS), node-optimal strategy (NOA), and node-greedy strategy (NGS), respectively, are used in our paper.

(1) Global-Optimal Strategy

Let [TeX:] $$p_{i}$$ denote the path calculated for flow [TeX:] $$f_{i}$$ in the first phase, and [TeX:] $$s p_{i}$$ is the shortest path between the source and destination nodes of flow [TeX:] $$f_{i}.$$ If [TeX:] $$p_{i} \neq s p_{i},$$ some extra TCAM entries will be required at some SDN switches on the path [TeX:] $$p_{i}$$ to forward flow along the path [TeX:] $$p_{i}.$$ To reduce TCAM usage, we can simply adjust the path of flow [TeX:] $$f_{i} \text { to } s p_{i}.$$ However, the path adjustment may lead to load balancing performance degradation. Thus, to avoid load balancing performance degrade significantly, we need to carefully select the flows for taking path adjustment.

For ease of description, we first introduce some notations. We use variable [TeX:] $$x_{i}$$ to denote whether to adjust the path [TeX:] $$p_{i}$$ of flow [TeX:] $$f_{i}$$ to the shortest path [TeX:] $$s p_{i}.$$ The parameter [TeX:] $$\omega_{i}^{j}$$ denote whether an TCAM entry is required at node j to forward flow [TeX:] $$f_{i}$$ along path [TeX:] $$p_{i}.$$ Given the set F of flows and the set [TeX:] $$P_{i}$$ of candidate paths for the flows, the routing adjustment problem can be formulated as the following integer linear programming (ILP) problem:

(10)
[TeX:] $$P1: minimize \ \lambda$$

(11)
[TeX:] $$\sum_{f_{i} \in F} h_{i}\left(x_{i} \xi_{i p_{i}}^{e}+\left(1-x_{i}\right) \xi_{i s p_{i}}^{e}\right) \leq \lambda c(e) \quad \forall e \in E$$

(12)
[TeX:] $$\sum_{f_{i} \in F} \omega_{i}^{j} x_{i} \leq \gamma(j) \quad \forall j \in V_{S D N}$$

(13)
[TeX:] $$x_{i} \in\{0,1\} \quad \forall f_{i} \in F$$

Equation (11) represents the link capacity constraint, and (12) denotes the TCAM capacity constraint. By solving the above ILP problem, we can get an optimal routing adjustment strategy for the flows. However, for large networks, the ILP problem may be intractable computationally.

(2) Node-Optimal Strategy

As presented above, the GOS optimizes the routing adjustment solution for all the flows at a time, which may lead to high computational complexity. In order to reduce the computational complexity, NOS only pursue the optimal routing adjustment solution for a part of flows at a time, and it gets the whole solution by repeating the process. Specifically, NOS first finds the SDN switch whose TCAM capacity constraint is most seriously violated, and then it optimizes the routing adjustment solution for the flows that go through the SDN switch and are forwarded by the dedicated TCAM entries at the SDN switch. For ease of description, we use [TeX:] $$F_{u}$$ to denote the set of flows that go through the SDN switch u and are forwarded by dedicated TCAM entries at the SDN switch u. Similar to the GOS, the NOS also gets the optimal routing adjustment solution for the flows in[TeX:] $$F_{u}$$ by solving an ILP problem. Given the set [TeX:] $$F_{u}$$ of flows and the set [TeX:] $$P_{u}$$ of candidate paths for the flows in [TeX:] $$F_{u},$$ the ILP is formulated as follows:

(14)
[TeX:] $$P2: minimize \ \lambda$$

(15)
[TeX:] $$\sum_{f_{i} \in F_{u}} \omega_{i}^{u} x_{i} \leq \gamma(u)$$

(16)
[TeX:] $$\sum_{f_{i} \in F_{u}} h_{i}\left(x_{i} \xi_{i p_{i}}^{e}+\left(1-x_{i}\right) \xi_{i s p_{i}}^{e}\right)+r b_{e} \leq \lambda c(e) \quad \forall e \in E$$

(17)
[TeX:] $$x_{i} \in\{0,1\} \quad \forall f_{i} \in F_{u}.$$

where [TeX:] $$r b_{e}$$ is the bandwidth used by the flows in [TeX:] $$F \backslash F_{u}$$ on link e. Since [TeX:] $$\left|F_{u}\right|\left(u \in V_{S D N}\right)$$ is usually much smaller than [TeX:] $$|F|,$$ the

Node-Optimal Strategy

complexity of the ILP used by NOS is much lower than that of the ILP used by GOS. Algorithm 5 shows the detailed procedure of NOS.

(3) Node-Greedy Strategy

Even though the complexity of NOS is much lower than that of GOS, solving the ILP problem P2 may also take a long time for large networks. Thus, we propose NGS, which is a greedy algorithm with polynomial time complexity.

Similar to the NOS, NGS also calculates the routing adjustment solution for the flows in a set [TeX:] $$F_{u}$$ in each time. However, instead of solving an ILP, NGS uses a greedy algorithm to calculate the routing adjustment solution for the flows in a set [TeX:] $$F_{u}.$$ Algorithm 6 shows the detailed procedure of NGS. In each iteration, NGS selects some flows going through the same SDN switch to reroute (lines 2-17). To reduce the impact of path adjustment on the maximum link utilization, NGS greedily chooses a flow to implement path adjustment at a time such that the increment of maximum link utilization is minimized (lines 7-15). In Algorithm 6, [TeX:] $$\Delta_{i}$$ represents the increment of maximum link utilization if the path of flow [TeX:] $$f_{i}$$ is adjusted from [TeX:] $$p_{i} \text { to } s p_{i}$$ (line 8).

The three strategies have different complexity and optimization performance. The global-optimal strategy (GOS) and nodeoptimal strategy (NOA) get the global-optimal and node-optimal solution by solving MILP models, while node-greedy strategy (NGS) uses an efficient heuristic to get approximate solution. Thus, the optimization performance of GOS and NOA is better than that of NGS, while NGS has lower computation complexity than GOS and NOA.

In summary, to efficiently solve the RO problem under the TCAM capacity constraint, we use a two-stage approach to solve the problem. In the first phase, we consider the MCR problem and use RRA and OA algorithms to solve the MCR problem. In the second phase, we use the GOS, NOS, and NGS to solve the RA problem to meet the TCAM capacity constraint. Thus, we actually have six algorithms for the RO problem under the TCAM capacity constraint. For convenience, we call the six algorithms as RRA-GOS, RRA-NOS, RRA-NGS, OA-GOS, OA-NOS, and OA NGS, respectively.

Node-Greedy Strategy

V. PERFORMANCE EVALUATION

To evaluate the performance of the proposed approximate algorithms, we conduct simulations on both real ISP topologies and synthetic topologies using synthetic flows. In this section, we first describe the simulation setup, and then we show the simulation results.

A. Simulation Setup

Network topologies: In our simulations, we use the real ISP topologies from the Topology Zoo project [43]. There are 260 topologies in Topology Zoo [43], and we select 6 topologies of different sizes from the topology set. Table 2 summarizes the number of nodes and links in each topology. The selected topologies cover the small-size, medium-size, and large-size topologies. Moreover, to evaluate the performance of the algorithms on dense topologies, we also generate random topologies using Barabási-Albert (BA) and Erdös-Rényi (ER) models.

Since the real ISP and synthetic topologies do not have the link capacity information, we set the capacity of a link (u; v) base on the degrees of nodes u and v. In real networks, a link

Table 2.
Real ISP topologies.

(u, v) may have a higher capacity if node u or node v has higher degree. Therefore, we set the capacity of each link [TeX:] $$(u, v) \in E$$ as follows:

1) If the degrees of both nodes u and v are higher or equal to 3, the capacity of link (u, v) is set to 39813.12 Mbps (OC 768).

2) If the degree of either node u or node v is higher or equal to 3, the capacity of link (u, v) is set to 9953.28 Mbps (OC 192).

3) Otherwise, the capacity of link (u, v) is set to 2488.32 Mbps (OC 48).

We assume that only a subset of nodes are deployed with SDN switches. let [TeX:] $$p_{S D N}$$ denote the SDN deployment ratio, which is defined as [TeX:] $$\left|V_{S D N}\right| /|V|.$$ We assume that the node with the higher degree has higher priority to deploy SDN switch, and the number of TCAM entries is the same for all of the SDN switches. For simplicity, the total number of TCAM entries (n) in every SDN switch is the same. Since the performance of RO algorithms is jointly determined by the capacity of TCAM and the number of flows, we use flow aggregation ratio as a simulation parameter. The flow aggregation ratio is defined as the ratio between the total number of TCAM entries in each SDN switch and the total number of flows, i.e., [TeX:] $$r=n /|F|$$.

Flows: Since the real ISP topologies and synthetic topologies also do not have flow information, we use the gravity model to generate aggregated flow [TeX:] $$a f_{i j}$$ between each node pair <i, j>. In the gravity model, the volume of aggregated flow [TeX:] $$a f_{i j}$$ is as follows:

(18)
[TeX:] $$a f_{i j}=T \frac{T_{o u t}(i)}{\sum_{k \in V} T^{i n}(k)} \frac{T_{i n}(j)}{\sum_{k \in V} T^{i n}(k)},$$

where [TeX:] $$T_{\text {out}}(i)$$ denotes the total volume of aggregated flows sent from node [TeX:] $$i, T_{i n}(j)$$ denotes the total volume of aggregated flows injected to node j, and [TeX:] $$T=\sum_{j \in V} T_{i n}(j).$$ Generally speaking, [TeX:] $$T_{\text {out}}(i) \text { and } T_{i n}(i)$$ is proportional to the total capacity of the links incident to node i. Thus, we have:

(19)
[TeX:] $$T_{i n}(i)=\alpha \sum_{l \in N_{i}} c(l),$$

(20)
[TeX:] $$T_{o u t}(i)=\beta \sum_{l \in N_{i}} c(l),$$

where and are parameters randomly chosen in range [0.3, 0.8], [TeX:] $$N_{i}$$ is the set of links incident to node i. In our simulations, we randomly generate aggregated flows using different and . Given the set of aggregated flows, we can get the nearoptimal routing solution without TCAM and unsplittable flow constraints by using the maximum concurrent flow algorithm [42]. We assume that the maximum link utilization under the near-optimal routing solution is [TeX:] $$\lambda^{*}.$$ Therefore, we can normalize the aggregated flow sizes by multiplying a factor [TeX:] $$\theta / \lambda^{*}$$ if we want to let the optimal maximum link utilization equal to

The flows generated above are aggregated flows between network nodes. However, in our simulations, we need fine-grained flows, which are flows between IP prefixes. We assume that each network node has a set of IP prefixes (sub-network addresses), and the number of IP prefixes assigned to a node is uniformly distributed in [4, 5]. Let [TeX:] $$f_{i j}^{k}$$ denote the kth fine-grained flow between nodes i and j. To determine the volume of flow [TeX:] $$f_{i j}^{k},$$ we use the following equation:

(21)
[TeX:] $$\left|f_{i j}^{k}\right|=\left|a f_{i j}\right|\frac{\operatorname{len}\left(f_{i j}^{k} \cdot \operatorname{src}\right)}{\sum_{\text {pre} \in \text {Pre}_{i}} \operatorname{len}(\text {pre})} \frac{\operatorname{len}\left(f_{i j}^{k} \cdot d s t\right)}{\sum_{\text {pre} \in \text {Pre}_{j}} \operatorname{len}(\text {pre})},$$

where operator [TeX:] $$\operatorname{len}(\cdot)$$ returns the length of a prefix, and [TeX:] $$\text {Pre}_{i}$$ is the set of prefixes assigned to node i.

B. Simulation Results

(a) Real ISP Topologies

We first present the simulation results for the six real ISP topologies chosen from Topology Zoo project [43]. Fig. 3 shows the MLUs of the algorithms under different flow aggregation ratios. In these simulations, the SDN deployment ratio is set to 1. In Fig. 3, we compare the six algorithms proposed with SPR, RRA, OA, and the Lagrangian relaxation based routing algorithm (LRRA) [44], where SPR denotes the shortest path routing strategy. Since the flows routing along the shortest paths can be aggregated based on the destination IP prefixes, the TCAM capacity constraint is naturally met in SPR. As shown in Section IV. A, The RRA and OA only consider how to route flows to achieve the minimum MLU, and they do not consider the TCAM capacity constraint at SDN switches. Thus, the paths calculated by RRA and OA may be unrealizable in practical SDN networks. However, the results of RRA and OA can be viewed as the lower bounds for our proposed algorithms. The LRRA is a classical constrained routing algorithm that can be used to solve a broad types of constrained routing problem, and it can be also used to solve the routing optimization problem under the TCAM capacity constraint by making some simple modifications. In our simulation, LRRA converges slowly, and in some cases, it cannot get a feasible solution. So when LRRA cannot get a feasible solution that meets the TCAM capacity constraint, we adjust the paths of some flows to the shortest paths of the flows such that the TCAM constraint is satisfied.

From Fig. 3, we have the following observations. 1) We can see that the MLUs of SPR, RRA, and OA do not vary with the flow aggregation ratio. This is because the three algorithms do not consider the TCAM capacity constraint (i.e., it is equivalent to that the flow aggregation ratio is set to 1 in the three algorithms). 2) We also can note that generally, the MLUs of our proposed algorithms decrease with the increasing of flow aggregation ratio. The reason is that as the flow aggregation ratio increases, more available TCAM entries can be used to adjust the forwarding paths of the flows, resulting in better load balance performance. 3) The load balance performance of our proposed algorithms is much better than that of SPR and LRRA. This verifies that upgrading the IP networks running the shortest path based routing protocol to the SDN-enabled ones can significantly improve the network performance. 4) The load balance performance of our proposed algorithms is also much better than that of LRRA. This because LRRA hardly converges to the optimal solution when the number of flow is large. 5) OA performs slightly better than RRA when they calculate minimum congestion routing for the flows, and as expected, the GOS and NOS have better performance than NGS when they adjust flow routing to meet the TCAM capacity constraint. 6) When the flow aggregation is higher than a threshold (e.g., 0.008 in our simulations), the performance of NGS is very close to that of GOS and NOS. 7)The performance differences of the proposed algorithms on Arnes and Cernet are obviously larger than those on RedBestel and VtWavenet. This is because Arnes and Cernet are denser [TeX:] $$(i.e., |E| /|V| \text { is higher })$$ than RedBestel and VtWavenet, and thus, Arnes and Cernet have more routing optimization options than RedBestel and VtWavenet, which is beneficial for GOS and NOS. 8) Our proposed algorithms can achieve good load balancing performance even if the flow aggregation is low [TeX:] $$(e.g., r=0.01),$$ which means that we can achieve good load balancing performance with small TCAM space.

To evaluate the impact of SDN deployment ratio on the load balancing performance, we show the MLUs of the algorithms under different SDN deployment ratios in Fig. 4. In these simulations, we fix the flow aggregation ratio to 0.001. Since only the SDN switches can flexibly control the forwarding paths of the flows going through them, the MLUs of the algorithms decrease with the increasing of SDN deployment ratio. Similar to the results in Fig. 3, the load balancing performance can be significantly improved by leveraging the flexible routing control capacity of SDN switches. From Fig. 4, we also can observe that in all cases, GOS and NOS perform better than NGS, and the performance of NOS is very close to that of GOS. Furthermore, it is notable that in most topologies, the MLUs of the algorithms decrease marginally when the SDN deployment ration is higher than 0.3. This implies that upgrading a small portion of network nodes to SDN-enable ones can achieve satisfactory performance. In addition, Fig. 4 shows that the MLUs of the GOS and NOS are very close to those of OA and RRA, which do not consider the TCAM capacity constraint. This demonstrates that by carefully optimizing the routing for the flows, we can obtain good load balancing performance even if there are only very limited number of TCAM entries in the SDN switches. At last, the performance of our proposed algorithms is also much better than that of LRRA in all cases.

Figs. 5 and 6 show the running times of the algorithms when r and [TeX:] $$p_{S D N}$$ vary, respectively. We also have the simulation results for the other four real ISP topologies, and the results show similar trends for all the algorithms. Thus, to save space, we do not show them here. The running times of the algorithms are mainly related to the network size and the characteristics of network topologies. Generally speaking, the algorithms have longer running times on larger topologies and have shorter running times on sparser network topologies. In all simulations, the LRRA converges very slowly(e.g., it takes about 5000 s in Garr topology). So to keep the clarity of the figures, we do not show the running time of LRRA in Figs. 5 and 6. Evidently, the running time of RRA is much longer than that of OA. The reason is that RRA uses the Algorithm 3 to calculate the fractional flow routing solution in the first step, and the Algorithm 3 may need a large number of iterations to get a near-optimal routing solution. From Figs. 5 and 6, we also can note that the running times of the algorithms using GOS are just slightly longer than those of the algorithms using NOS, and the running times of the algorithms using GOS may even shorter than those of the algorithms

Fig. 3.
The MLUs of the algorithms in real ISP topologies when flow aggregation ratio r varies: (a) Arnes, (b) Cernet, (c) Garr, (d) Dfn, (e) RedBestel, and (f) VtWavenet2011.

using NGS (e.g., Figs. 5(a) and 6(b)). This is because the real ISP topologies are sparse, and thus there may be only a small number of decision variables required to be determined in GOS. The results indicate that we can use GOS or NOS to get a better solution within a short time in networks with sparse topologies.

(b) Synthetic Topologies

From Table 2, we know that the real ISP are sparse. To evaluate the performance of the algorithms on topologies that are denser than the real ISP topologies, we generate synthetic topologies with 70 nodes using BA and ER models and conconduct simulations on these synthetic topologies. BA model generates random topologies by beginning with an initially connected topology of [TeX:] $$n_{0}\left(n_{0}=4 \text { in our simulations }\right)$$ nodes and adding new nodes sequentially. Each new node is connected to [TeX:] $$d_{\min }$$ existing nodes with a probability that is proportional to the degree of the existing nodes. In the ER model, a topology is constructed by independently connecting each pair of nodes by a link with a fixed probability p. In our simulations, [TeX:] $$d_{\min }$$ and p are set to 3 and 0.088, respectively, and thus the number of the links in the generated synthetic topologies is about 200.

Fig. 4.
The MLUs of the algorithms in real ISP topologies when the SDN deployment ratio pSDN varies: (a) Arnes, (b) Cernet, (c) Garr, (d) Dfn, (e) RedBestel, and (f) VtWavenet2011.

We plot the MLUs of the algorithms in BA and ER topologies under different flow aggregation ratios in Fig. 7. From Fig. 7, we can observe that the simulation results of the algorithms in synthetic topologies and real ISP topologies (Fig. 3) share similar trends. It is worth to note that the MLUs of the algorithms decrease quickly with the increasing of flow aggregation ratio, and we can get promising load balancing performance even using a small number of TCAM entries (e.g., the MLUs improve marginally when the flow aggregation ratio higher than 0.005.). Moreover, the GOS and NOS also perform better than NGS, especially when the flow aggregation is low (e.g., lower than 0.005).

We also show the running times of the algorithms in synthetic topologies in Fig. 8. Similar to the results in real ISP topologies (i.e., Fig. 5), the running times of the algorithms using RRA are much longer than those of the algorithms using OA. Fur-

Fig. 5.
The running times of the algorithms in real ISP topologies when flow aggregation ratio r varies: (a) Garr and (b) VtWavenet2011.
Fig. 6.
The running times of the algorithms in real ISP topologies when the SDN deployment ratio [TeX:] $$\mathcal{P S D N}$$ varies: (a) Garr and (b) VtWavenet2011.
Fig. 7.
The MLUs of the algorithms in Synthetic topologies when flow aggregation ratio r varies: (a) BA and (b) ER.

thermore, as expected, the running times of the algorithms using NGS is shorter than those of the algorithms using GOS and NOS. The reason is that as the topologies become denser, there will be more decision variables involved in the ILP models used in GOS and NOS, and thus the complexity of solving the MILP models also increase dramatically.

In summary, we can mainly get the following insights from the simulation results. 1) With the help of SDN technique, the RO performance of IP networks can be significantly improved; 2) The proposed algorithms can achieve satisfactory RO performance even with a small number of available TCAM entries in hybrid SDN networks, which may only have a small portion of

Fig. 8.
The running times of the algorithms in Synthetic topologies when flow aggregation ratio r varies: (a) BA and (b) ER.

SDN switches; 3) Generally, the algorithms using OA perform better than those using RRA in terms of load balancing performance and running time.

VI. CONCLUSION

With the rapid development of IoT and distributed cloud computing architecture, vast amounts of data collected from a variety of IoT devices are required to be sent to clouds located at network nodes through backhaul or backbone network. Thus, the number of flows and the total volume of flows transmitted on the networks will increase explosively in the the near future. To guarantee the QoS of IoT cloud services and avoid network congestion, it is essential to implement efficient RO strategies for the IoT flows. On the other hand, the emergence of SDN paves a way for implementing efficient RO strategies. In SDN networks, the flow routing is realized by using flow rules usually installed in TCAM in SDN switches. However, due to physical limitations and cost constraint, the capacity of TCAM in SDN switches is very limited, and thus the number of available flows in SDN switches is far less than the number of IoT flows. Furthermore, the hybrid SDN networks, where SDN switches coexist with traditional devices, are an important deployment scenario that needs to be considered. Therefore, in this paper, we studied the RO problem under the TCAM capacity constraint in hybrid SDN-based IoT. Specifically, we first formally formulated the problem and proved that the problem is NP-hard, and then we proposed several two-stage approximate algorithms to efficiently solve the problem. To evaluate the performance of the algorithms under the TCAM capacity constraint, we conducted extensive simulations on real ISP and synthetic topologies. The simulation results revealed that the proposed algorithms can significantly improve load balancing performance by properly leveraging the very limited number of TCAM entries in SDN switches.

Biography

Shizhong Xu

Shizhong Xu received his B.S., M.S., and Ph.D. degrees in Electrical Engineering from the University of Electronic Science and Technology of China, Chengdu, China, in 1994, 1997, and 2000, respectively. He now is a Professor in the school of Information and Communication at the University of Electronic Science and Technology of China, Chengdu, China. His research interests include Internet of Things, next generation network and network science.

Biography

Xiong Wang

Xiong Wang is an Associate Professor in school of Information and Communication at the University of Electronic and Science of China, Chengdu, China. He received his Ph.D. in Communication and Information System from the University of Electronic and Science of China, Chengdu, china, in 2008. From 2013 to 2014, he was a Visiting Scholar in Electrical and Computer Engineering at the University of California, Davis, CA, USA. His research interests include network measurement, modeling and optimization, algorithm analysis and design, network management in communication networks.

Biography

Guangxu Yang

Guangxu Yang is an a M.S. student in the School of Communication and Information Engineering, University of Electronic Science and Technology of China, Chengdu, China. His research interests are software defined networking and network measurement.

Biography

Jing Ren

Jing Ren received her Ph.D. degree in communication and information system from the University of Electronic Science and Technology of China, Chengdu, China, in 2007. She now is a Lecturer in school of Information and Communication at the University of Electronic and Science of China, Chengdu, China. Her research interests include network architecture and protocol design, information-centric networking, and software-defined networking.

Biography

Sheng Wang

Sheng Wang received the B.S. degree in Electronic Engineering, and the M.S. and Ph.D. degrees in Communication Engineering from the University of Electronic Science and Technology of China, Chengdu, China, in 1992, 1995, and 2000, respectively. He now is a Professor in the school of Information and Communication at the University of Electronic Science and Technology of China, Chengdu, China. His research interests include planning and optimization of wire and wireless networks, next generation of internet, and next-generation optical networks.

References

  • 1 A. Al-Fuqaha, M. Guizani, M. Mohammadi, M. Aledhari, M. Ayyash, "Internet of things: A survey on enabling technologies, protocols, and applications," IEEE Commun. Surveys Tuts., vol. 17, no. 4, pp. 2347— 2376-2347— 2376, June, 2015.doi:[[[10.1109/COMST.2015.2444095]]]
  • 2 P. Bellavista, G. Cardone, A. Corradi, L. Foschini, "Convergence of MANET and WSN in IoT urban scenarios," IEEE Sensors J., vol. 13, no. 10, pp. 3558—3567-3558—3567, Oct, 2013.custom:[[[-]]]
  • 3 M. Satyanarayanan, P. Bahl, R. Caceres, N. Davies, "The case for VMbased cloudlets in mobile computing," IEEE Pervasive Comput., vol. 8, no. 4, pp. 14—23-14—23, Oct, 2009.custom:[[[-]]]
  • 4 S. Wang, G. Tu, R. Ganti, et al., "Mobile micro-cloud: Application classification, mapping, and deployment," in Proc.AMITA, 2013.custom:[[[-]]]
  • 5 A. Sivanathan, D. Sherratt, H. H. Gharakheili, et al., "Characterizing and classifying IoT traffic in smart cities and campuses," in Proc.IEEE INFOCOMWorkshops, May, 2017.custom:[[[-]]]
  • 6 A. Mendiola, J. Astorga, E. Jacob, M. Higuero, "A survey on the contributions of software-defined networking to traffic engineering," IEEE Commun.SurveyTuts., vol. 19, no. 2, pp. 918-953, Nov, 2016.doi:[[[10.1109/COMST.2016.2633579]]]
  • 7 U. D. Black, "MPLS and label switching networks," PrenticeHall, 2002.custom:[[[-]]]
  • 8 C. Filsfils, N. K. Nainar, C. Pignataro, J. C. Cardona, P. Francois, "The segment routing architecture," in Proc.IEEE GLOBECOM, Dec, 2015.custom:[[[-]]]
  • 9 N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, J. Turner., "Openflow: Enabling innovation in campus networks," SIGCOMM Comput. Commun. Review, vol. 38, no. 2, pp. 69-74, Mar, 2008.doi:[[[10.1145/1355734.1355746]]]
  • 10 OpenFlow Switch Specification,, https://www.opennetworking.org/wpcontent/uploads/2014/10/openflow-spec-v1.3.0.pdf
  • 11 C. Y. Hong et al., "Achieving high utilization with software-driven wan," in Proc.ACMSIGCOMM, pp. 15-26, Aug, 2013.custom:[[[-]]]
  • 12 S. Jain et al., "B4: Experience with a globallydeployed software defined wan," in Proc.ACMSIGCOMM, pp. 3-14, Aug, 2013.custom:[[[-]]]
  • 13 B. Agrawal, T. Sherwood, "Modeling TCAM power for next generation network devices," in Proc.IEEE ISPASS, pp. 120—129-120—129, Mar, 2006.custom:[[[-]]]
  • 14 K. Kannan, S. Banerjee, "Compact TCAM: flow entry compaction in TCAM for power aware SDN," in Proc.IDCN, pp. 439-444, 2013.custom:[[[-]]]
  • 15 W. Braun, M. Menth, "Wildcard compression of inter-domain routing tables for openflow-based software-defined networking," in Proc. EWSDN, Sept, 2014.custom:[[[-]]]
  • 16 Y. Li, R. Mao, C. Kim, M. Yu, "FlowRadar: A better netFlow for data centers," in Proc.USENIXNSDI, Mar, 2016.custom:[[[-]]]
  • 17 Z. Ullah, M. K. Jaiswal, R. C. C. Cheung, "Z-TCAM: an SRAMbased architecture for TCAM," IEEE Trans. Very Large Scale Integration Systems, vol. 23, no. 2, pp. 402-406, Mar, 2014.custom:[[[-]]]
  • 18 J. Zhang, K. Xi, H. J. Chao, "Load balancing for multiple traffic matrices using SDN hybrid routing," in Proc.IEEE HPSR, July, 2014.custom:[[[-]]]
  • 19 X. Jin et al., "Dynamic scheduling of network updates," in Proc. ACM SIGCOMM, Aug, 2014.custom:[[[-]]]
  • 20 Sandhya, Y. Sinha, K. Haribabu, "A survey: Hybrid SDN," J. Netw. Comput.Applications, vol. 100, Dec, 2017.doi:[[[10.1016/j.jnca.2017.10.003]]]
  • 21 R. Masoudi, A. Ghaffari, "Software defined networks: A survey," J. Netw.Comput.Applications, vol. 67, pp. 1-25, May, 2016.doi:[[[10.1016/j.jnca.2016.03.016]]]
  • 22 B. Fortz, J. Rexford, M. Thorup, "Traffic engineering with traditional IP routing protocols," IEEE Commun. Mag., vol. 40, no. 10, pp. 118-124, Oct, 2002.custom:[[[-]]]
  • 23 X. Xiao, A. Hannan, B. Bailey, L. M. Ni, "Traffic engineering with MPLS in the Internet," IEEE Netw../, vol. 14, no. 2, pp. 28-33, Mar, 2000.doi:[[[10.1109/65.826369]]]
  • 24 M. N. Soorki, H. Rostami, "Label switched protocol routing with guaranteed bandwidth and end to end path delay in MPLS networks," J. Netw. Comput.Applications, vol. 42, pp. 21-38, June, 2014.doi:[[[10.1016/j.jnca.2014.03.008]]]
  • 25 R. Bhatia, F. Hao, M. Kodialam, T. V. Lakshman, "Optimizing network traffic engineering using segment routing," in Proc. IEEE INFOCOM, Apr, 2015.custom:[[[-]]]
  • 26 N. Wang, K. Ho, G. Pavlou, M. Howarth, "An overview of routing optimization for Internet traffic engineering," IEEE Commun.SurveyTuts.vo. 10, no. 1, pp. 36-56, Apr, 2008.doi:[[[10.1109/COMST.2008.4483669]]]
  • 27 A. Mendiola, J. Astorga, E. Jacob, M. Higuero, "A survey on the contributions of software-defined networking to traffic engineering," IEEE Commun.SurveyTuts., vol. 19, no. 2, pp. 918-953, Nov, 2017.doi:[[[10.1109/COMST.2016.2633579]]]
  • 28 Z. Shu, J. Wan, J. Lin, S. Wang, D. Li, S. Rho, C. Yang, "Traffic engineering in software-defined networking: measurement and management," IEEE Access, vol. 4, pp. 3246-3256, June, 2016.doi:[[[10.1109/ACCESS.2016.2582748]]]
  • 29 M. Pioro, D. mehdi, "Routing, flow, and capacity design in communication and computer networks," MorganKaufmannPublishers, 2004.custom:[[[-]]]
  • 30 S. Vissicchio, L. Vanberer, O. Bonaventure, "Opportunities and research challenges of hybrid software defined networks," ACMComput.Commun. Review, vol. 44, no. 2, Apr, 2014.doi:[[[10.1145/2602204.2602216]]]
  • 31 S. Vissicchio, L. Vanbever, L. Cittadini, G. G. Xie, O. Bonaventure, "Safe update of hybrid SDN networks," IEEE /ACM Trans. Netw., vol. 25, no. 3, pp. 1649-1662, Jan, 2017.doi:[[[10.1109/TNET.2016.2642586]]]
  • 32 S. Agarwa, M. Kodialam, T. V. Lakshman, "Traffic engineering in software defined networks," in Proc.IEEE INFOCOM, Apr, 2013.doi:[[[10.1109/infcom.2013.6567024]]]
  • 33 J. He, W. Songk, "Achieving near-optimal traffic engineering in hybrid software defined networks," in Proc.IFIPNetw., May, 2015.doi:[[[10.1109/ifipnetworking.2015.7145321]]]
  • 34 Y. Guo, Z. Wang, X. Yin, X. Shi, J. Wu, "Traffic engineering in SDN/OSPF hybrid network," in Proc.IEEE ICNP, Oct, 2014.custom:[[[-]]]
  • 35 W. Wang, W. He, J. Su, "Enhancing the effectiveness of traffic engineering in hybrid SDN," in Proc.IEEE ICC, May, 2017.custom:[[[-]]]
  • 36 S. Zhang, Q. Zhang, et al., "Sector: TCAM space aware routing on SDN," in Proc.ITC, Sept, 2016.custom:[[[-]]]
  • 37 Y. Guo, Z. Wang, X. Yin, X. Shi, J. Wu, H. Zhang, "Incremental deployment for traffic engineering in hybrid SDN network," in Proc.IPCCC, Dec, 2015.custom:[[[-]]]
  • 38 K. Poularakis, G. Iosifidis, G. Smaragdakis, L. Tassiulas, "One step at a time: optimizing SDN upgrades in ISP networks," in Proc.IEEE INFOCOM, May, 2017.custom:[[[-]]]
  • 39 M. Garey, D. Johnson, "Computers and Intractability," W.H. FreemanNew York, 1979.custom:[[[-]]]
  • 40 Y. Cui, B. Li, K. Nahrstedt, "On achieving optimized capacity utilization in application overlay networks with multiple competing sessions," in Proc.ACMSPAA, June, 2004.custom:[[[-]]]
  • 41 P. M. Bialon, "A randomized rounding approach to a k-splittable multicommodity flow problem with lower path flow bounds affording solution quality guarantees," TelecommunicationSystems, pp. 525-542, June, 2017.doi:[[[10.1007/s11235-016-0190-2]]]
  • 42 G. Karakostas, "Faster approximation schemes for fractional multicommodity flow problems," in Proc.ACM/SIAMSODA, Jan, 2002.doi:[[[10.1145/1328911.1328924]]]
  • 43 S. Knight, H. X. Nguyen, N. Falkner, R. Bowden, M. Roughan, "The Internet Topology Zoo," IEEE J. Selected Areas Commun., vol. 29, no. 9, pp. 1765-1775, Sept, 2011.doi:[[[10.1109/JSAC.2011.111002]]]
  • 44 N. Varyani, Z. Zhang, M. Rangachari, D. Dai, "LADEQ: A fast lagrangian relaxation based algorithm for destination-based QoS routing," in Proc.IFIP/IEEE IM, Apr, 2019.custom:[[[-]]]

Table 1.

The notations used in the formulation.
F The set of flows.
[TeX:] $$f_{i}$$ The ith flow in F.
[TeX:] $$P_{i}$$ The set of feasible paths of[TeX:] $$f_{i}$$
[TeX:] $$h_{i}$$ A binary decision variable denotes whether the flow [TeX:] $$f_{i}$$ selects feasible path [TeX:] $$p \in P_{i}.$$
[TeX:] $$x_{i p}$$ A binary decision variable denotes whether the flow [TeX:] $$f_{i}$$ selects feasible path [TeX:] $$p \in P_{i}.$$
[TeX:] $$\lambda$$ A decision variable denotes the maximum link utilization of a network.
[TeX:] $$\gamma(v)$$ The number of available TCAM entries in SDN node v.
c(e) The capacity of link e.
[TeX:] $$\theta_{i u}$$ A binary decision variable denotes whether a flow rule in SDN node u is used to adjust the forwarding path of flow [TeX:] $$f_{i}.$$
[TeX:] $$\omega_{i p}^{u}$$ A binary decision variable indicates whether the feasible path p of flow [TeX:] $$f_{i}$$ consumes an extra TCAM entry of SDN node u.
[TeX:] $$\xi_{i p}^{e}$$ A binary decision variable indicates whether the link e appears in the feasible path p of flow [TeX:] $$f_{i}$$

Table 2.

Real ISP topologies.
Topology type Topology name Node number Link number
Small-size Arnes 34 47
Cernet 41 59
Medium-size Garr 54 71
Dfn 58 87
Large-size RedBestel 84 101
VtWavenet2011 92 96
The architecture of IoT.
An example for routing optimization in hybrid SDN-based IoT.
Calculating Feasible Paths For a Flow
Randomized Rounding Algorithm
Maximum Concurrent Flow Algorithm
Online Algorithm
Node-Optimal Strategy
Node-Greedy Strategy
The MLUs of the algorithms in real ISP topologies when flow aggregation ratio r varies: (a) Arnes, (b) Cernet, (c) Garr, (d) Dfn, (e) RedBestel, and (f) VtWavenet2011.
The MLUs of the algorithms in real ISP topologies when the SDN deployment ratio pSDN varies: (a) Arnes, (b) Cernet, (c) Garr, (d) Dfn, (e) RedBestel, and (f) VtWavenet2011.
The running times of the algorithms in real ISP topologies when flow aggregation ratio r varies: (a) Garr and (b) VtWavenet2011.
The running times of the algorithms in real ISP topologies when the SDN deployment ratio [TeX:] $$\mathcal{P S D N}$$ varies: (a) Garr and (b) VtWavenet2011.
The MLUs of the algorithms in Synthetic topologies when flow aggregation ratio r varies: (a) BA and (b) ER.
The running times of the algorithms in Synthetic topologies when flow aggregation ratio r varies: (a) BA and (b) ER.