The feasibility of software-defined optical networking (SDON) for a practical application critically depends on scalability of centralized control performance. The paper, highly scalable routing and wavelength assignment (RWA) algorithms are investigated on an OpenFlow-based SDON testbed for proof-of-concept demonstration. Efficient RWA algorithms are proposed to achieve high performance in achieving network capacity with reduced computation cost, which is a significant attribute in a scalable centralized-control SDON. The proposed heuristic RWA algorithms differ in the orders of request processes and in the procedures of routing table updates. Combined in a shortest-path-based routing algorithm, a hottest-request-first processing policy that considers demand intensity and end-to-end distance information offers both the highest throughput of networks and acceptable computation scalability. We further investigate trade-off relationship between network throughput and computation complexity in routing table update procedure by a simulation study.
© 2015 Optical Society of America
Separating the control plane from the data plane, software-defined networking (SDN) provides a high degree of flexibility to the network operator. Further advantages of SDN such as programmability of networking functions, vendor-independent property, and logically centralized control manifest a strong potential of SDN for an optimal networking solution [1,2 ]. As one promising control plane technique of SDN, OpenFlow enables network operators to manage and control the networks by software. Although OpenFlow protocol was initially proposed for IP networks , it is able to support optical transport networks with certain extensions . Even though centralized controllability in SDN introduces simplicity, reliability, and high-performance into the networks, it intrigues a classical but important question of scalability [4,5 ]. Wavelength channel is a precious resource in optical networks and thus an efficient control is highly required. Accordingly, routing and wavelength assignment (RWA) in wavelength-routed optical networks is regarded as a major problem and has been actively researched in the community [6–9 ]. An RWA algorithm in heavily loaded large scale networks is much time-consuming and thus the RWA performance may become the bottleneck against the scalability of software-defined optical networking (SDON). Therefore, we propose scalable and high-performance RWA algorithms for SDON.
The rest of this paper is organized as follows. Section 2 reviews and proposes heuristic RWA algorithms for SDON. Section 3 evaluates algorithms performances by simulation study. Experimental demonstrations on SDON testbed in Section 4 are presented as a proof of the validity of the proposed algorithms, and Section 5 concludes this paper.
2. Heuristic routing and wavelength assignment algorithms
A static lightpath establishment (SLE) problem is a typical RWA problem, where a set of requests in a time-slot is known in advance [6–9 ]. In order to solve a networking dimensioning problem, we limit the RWA algorithm in this paper for an SLE problem. An optimal solution of the SLE problem is a well-known NP-complete  and thus time-tractable heuristic approaches are highly required, such as decoupling between routing problem and wavelength assignment problem, albeit suboptimal. A fixed-routing algorithm is usually used in optical transport networks due to its simplicity and efficiency. However, the performance of the fixed-routing algorithm may degrade by a high blocking ratio due to stale network information in a fixed routing table. This problem can be resolved by a routing table update procedure in a dynamic routing algorithm. However, too frequent update of the routing table results in huge overhead.
As the scalability is one of major objects in this work, we consider a greedy heuristic approach for an SLE problem so that we pick a request and perform decoupled RWA algorithms one-by-one. Sequence of picking a request among a given set of requests in the SLE problem is a non-trivial problem of a greedy algorithm, which affects performances a lot. In order to maximize the total demands of served requests, one idea is to provide higher priority for a heavier demand request and we refer it as a heaviest-request-first (HRF) processing. In , authors introduce concept of a hottest-request-first (HTRF) processing where a request of shorter end-to-end distance and heavier demand is defined as a ‘hotter request’. The HTRF processing provides higher priority to a hotter request, in turn, a request of heavier demand and shorter end-to-end distance is served earlier by the HTRF processing. The intuition behind the HTRF processing is that a physically longer lightpath consumes more link resources in networks. In , the HTRF concept is applied to the traffic grooming algorithm in order to achieve energy efficient IP-over-WDM networking. Meanwhile, theHTRF concept in this paper is extended to combine with RWA algorithms to achieve high-network throughput and scalable SDON.
Algorithms under investigation in this paper are described in Fig. 1 . The first algorithm illustrated in Fig. 1(a) adopts the HRF as a processing policy of requests and shortest-path based fixed-routing with First-Fit wavelength assignment as a decoupled RWA algorithm. The First-Fit wavelength assignment algorithm is applied here to assign the first available wavelength for each request . The second algorithm is similar to the first algorithm, but adopts the HTRF as a processing policy of requests, as described in Fig. 1(b). Difference between the second and the last algorithms is a routing table update procedure. As shown in Fig. 1(c), the last algorithm updates a routing table whenever all wavelength channels on any link are exhausted. Since the aim of this paper is limited to investigate SLE problems, the routing table update procedure is not a dynamic update but achieved during an iteration process for RWA computing for a given demand in the greedy approach. We refer to the first, second, and last algorithms as the HRF algorithm, HTRF algorithm, and HTRF-with-update algorithm, respectively. The HTRF processing requires additional information of the shortest end-to-end distance of each request. However, as long as the shortest-path based routing algorithm in the HTRF algorithm maintains a pre-computed routing table, the information can be looked-up from the routing table. Therefore the complexity is equivalent in the HRF and HTRF algorithms. In the HTRF processing, one can assign a weight value to the demand or distance, based on the application or service.
3. Simulation analysis
For simulations, we consider a six-node butterfly network and real Japan photonic network models (JPN12, JPN25, JPN48) as illustrated in Figs. 2(a)-2(d) , respectively. In order to further analyze the scalability, we also create large scale topologies by randomly assigning links between 100-node (100N) and 200-node (200N) networks. Numbers over links in Fig. 2(a) indicate physical distances of the links and link distance information of JPN networks is available in . We assume 40 wavelength channels per fiber link and 100 Gbps capacity per wavelength channel. We randomly generate all-to-all discrete traffic requests as a dynamic traffic model and each request has a bandwidth demand of either 100 Gbps or 400 Gbps. In this paper we define a total network throughput as a summation of request demands which are provisioned by the algorithms .
As a scalability measure, Fig. 3(a) shows computing time in the matlab simulator of the proposed algorithms in diverse network topologies at 2.67GHz and 4G RAM computer. Bytaking advantage of pre-computed distance information in the shortest-path based routing algorithm, the HTRF algorithm achieves equivalent complexity to that of the HRF algorithm as shown in Fig. 3(a). As network size scales, the computation complexity gap between HTRF-with-update algorithm and without update algorithms increases exponentially due to the routing table update procedure in the HTRF-with-update algorithm. Figure 3(b) analyzes total network throughput performances of the proposed algorithms in the JPN25 network model which is described in Fig. 2(c). The HTRF algorithm achieves 15% total network throughput gain from the HRF algorithm without any complexity overhead. We also observe further 20% gains by occasional update of a routing table.
4. Proof-of-concept demonstration
The experiments of the proposed algorithms are conducted at a transport SDON testbed . Figure 4 describes the experiment configuration and a 6-node butterfly network topology in Fig. 2(a) is used for a physical topology. Optical cross connectors (OXC, Calient DiamondWave 256) are deployed as optical nodes and indexed from A to F. WDM modules (Tellabs 7100N) are located before each OXCs for WDM signal generation. Each WDM nodes are connected with OpenFlow switch via Gigabit Ethernet interface.
At first, a traffic generator generates requests and sends them to an OpenFlow switch. Then the OpenFlow switch sends Packet In message to a POX based OpenFlow controller. To demonstrate the proposed SLE RWA algorithms, the controller waited until having received all the requests to inform path computation element (PCE) , which includes the source and destination IP address as well as bandwidth requirement of the connection requests. In this work, we developed our own PCE which is as simple as capable of computing only RWA. In our experiment, the PCE is integrated into the OpenFlow controller without the use of a PCE communication protocol (PCEP). Based on the algorithms results, the OpenFlow controller sends flowtable modification messages to the Openflow switches, the corresponding WDM_agents and OXC_agents . The WDM_agents and OXC_agents translate the flowtable modification messages to device control commands based on the standardTransaction Language 1 (TL1) to assign wavelengths of WDM modules and set up the connections of OXCs, respectively. Then the requests are transmitted along the configured lightpaths. If a wavelength assignment of a request fails, the OpenFlow switch discards the request. We verified end-to-end transactions by a data quality analyzer and investigated wavelength usages by a spectrum analyzer. In our demonstrations, a traffic generator generates six requests (A → D, A → E, A → F, E → D, F → D, F → E) of 1 Gbps demand which are known in advance as for an SLE problem. Even though we understand a requirement of a dynamic provisioning RWA algorithm that considers continuation of the current service provisioning in calculation of next service provisioning, we have to leave this research topic for a further study. Two wavelength channels of 10 Gbps capacity are installed per fiber: 1555.57nm (λ1) and 1557.36nm (λ2).
Figure 5 describes optical powers of spectrum on each links, which are results of the HRF algorithm for a given set of requests. Only three requests (A → D, A → E, E → D) among six requests are accommodated by the HRF algorithm and the rests are blocked, although detour paths exist for the blocked requests. The reason behind this observation is that the HRF algorithm does not update a pre-computed routing table even though wavelength assignmentis unavailable for a given path of a request in a routing table. On a link between nodes A and F, denoted as lAF, all two wavelength channels are assigned for the corresponding requests by a WDM manner. On a neighboring link, lFE, all two wavelengths channels are used where optical powers of both channels are reduced by around 5 dBm from those of lAF. When an optical signal enters an optical device, it undergoes insertion loss and we measure insertion loss of an OXC in our SDON testbed as around 5 dBm. Therefore, by comparing optical powers of spectrum between adjacent links, lAF and lFE, one can trace that both wavelength channels on lAF bypass an OXC at an intermediate optical node F. Compared with spectrum on lFE, λ2 on lED recovers optical power while λ1 loses around 5 dBm again. We trace that a request over λ1 on lFE and lED is the equivalent and bypass an intermediate node E. Since there is no amplifier installation in the testbed, we can trace that a node E terminates a request (A → E) over λ2 and generates a new request (E → D) over λ2 toward lED.
Wavelength channels usages of result of the HTRF algorithm and HTRF-with-update algorithm are described in Fig. 6 . We confirm that four requests (A → F, F → E, E → D, A → E) and all the generated requests are served by the HTRF algorithm and HTRF-with- update algorithm, respectively. Since the HTRF-with-update algorithm provides a high priority for a hotter request, shorter distance requests (A → F, F → E, E → D) are served earlier over λ1 by the shortest-path based fixed routing and the first-fit wavelength assignment. Then λ2 is assigned for a request (A → E) and the HTRF-with-update algorithm updates the routing table because there are no available wavelength channels on lAF and lFE. Therefore, requests (A → D, F → D) pass through detour paths which are different observations from those of the HRF algorithm in Fig. 5. By comparing optical powers of spectrum in lAF and lFE, it is clear that λ1 is assigned for difference requests at each links while λ2 is assigned for the same request. λ1 in lFB and λ2 in lAB are multiplexed at a node B and they undergo insertion losses at nodes B and C. Observations and explanations of result of the HTRF algorithm are covered by those of the HTRF-with-update algorithm because the result of the HTRF algorithm is subset of that of the HTRF-with-update algorithm, as marked in Fig. 6. In our small size topology experiment, the HTRF-with-update algorithm computation requires 30 milliseconds while wavelength tuning of the WDM equipment and reconfiguration of the OXC take approximately 1 second and several tens of milliseconds, respectively. However, since the RWA computation will be the major bottleneck in scalability toward large SDN deployment, the analysis in Fig. 3(a) provides scalability criteria of SDN implementation.
High-performance and scalable networking research gains much attention in the SDN paradigm because a centralized control plane in SDN is an essential element that requires a rapid provisioning cycle of the networks. This paper proposes high networking performance algorithms of a static lightpath establishment problem for a scalable SDON operation. By considering end-to-end distance information of network service requests, without scalability sacrifices, the proposed HTRF algorithm gains 15% of total network throughput from the HRF algorithm. Further 20% gain is achieved at an acceptable cost of computation complexity of a routing table update procedure in the proposed HTRF-with-update algorithm. Proof-of-concept demonstration of the proposed algorithms on an OpenFlow-based SDON testbed confirms feasibility and validity of the SDON as a solution for optical networks. In order to validate configuration of lightpath establishments of the algorithms, we trace the optical powers of individual wavelength channels. The current solution of this paper focuses to understanding scalability issue in conjunction with OpenFlow based implementation while leaving a dynamic provisioning capability for a future study.
This research was supported in part by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2013R1A1A2009809).
References and links
1. Open Networking Foundation, “Software-defined networking: the new norm for networks,” ONF White Paper, https://www.opennetworking.org/.
2. N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “Openflow: enabling innovation in campus networks,” Comput. Commun. Rev. 38(2), 69–74 (2008). [CrossRef]
3. S. Gringeri, N. Bitar, and T. Xia, “Extending software defined network principles to include optical transport,” IEEE Commun. Mag. 51(3), 32–40 (2013). [CrossRef]
4. S. Sezer, S. Scott-Hayward, P. Chouhan, B. Fraser, D. Lake, J. Finnegan, N. Viljoen, M. Miller, and N. Rao, “Are we ready for SDN? Implementation challenges for software-defined networks,” IEEE Commun. Mag. Magazine 51(7), 36–43 (2013). [CrossRef]
5. S. Yeganeh, A. Tootoonchian, and Y. Ganjali, “On scalability of software-defined networking,” IEEE Commun. Mag. 51(2), 136–141 (2013). [CrossRef]
6. H. Zang, J. P. Jue, and B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Optical Networks Magazine 1(1), 47–60 (2000).
7. I. Chlamtac, A. Ganz, and G. Karmi, “Lightpath communications: an approach to high-bandwidth optical WAN’s,” IEEE Trans. Commun. 40(7), 1171–1182 (1992). [CrossRef]
8. C. Lee and J.-K. K. Rhee, “Traffic grooming for IP-over-WDM networks: energy and delay perspectives,” IEEE/OSA Opt,” Commun. Netw. 6(2), 96–103 (2014). [CrossRef]
9. M. Kumar and P. Kumar, “Static lightpath establishment in WDM networks-New ILP formulations and heuristic algorithms,” Elsevier Computer Communications 25(1), 109–114 (2002). [CrossRef]
10. A. Mokhtar and M. Azizoglu, “Adaptive wavelength routing in all-optical networks,” IEEE/ACM Trans. Netw. 6(2), 197–206 (1998). [CrossRef]
11. Japan photonic network model, http://www.ieice.org/~pn/jpn/jpnm.html
12. X. Cao, N. Yoshikane, T. Tsuritani, and I. Morita, “Heterogeneous multi-domain network virtualization with end-to-end differentiated service provisioning and virtual network organization,” in Optical Fiber Communication Conference, OSA Technical Digest (Optical Society of America, 2015) paper Th4G.3. [CrossRef]
13. A. Farrel, J.-P. Vasseur, and J. Ash, “A path computation element (PCE)-based architecture,” IETF RFC 4655 (2006), http://tools.ietf.org/html/rfc4655.