Service function chains (SFCs) that utilize programmable data plane (PDP) have attracted attention due to their ability to balance high packet processing performance and flexibility. To adapt to network fluctuations, SFCs require periodic updates; paths are migrated from old to new ones. Ensuring state consistency during such migrations is essential for maintaining accurate packet processing. This paper presents an experimental analysis of migration time for an SFC with PDP-based network functions (NFs) by implementing two network systems. The first system, called System A, employs individual switch controllers, whereas the second system, called System B, consolidates them into the aggregated switch controller to eliminate overhead of aggregating state. An SFC migration time is measured under various conditions for both systems. When a firewall NF with 1000 table entries is used, the state extraction and conversion time accounts for 70% of the total migration time in System A. System B removes state conversion by integrating switch controllers and reduces the migration time by 76% compared to System A. In System B, state writing accounts for 72%, state extraction for 21%, and command propagation for 6.5% of the total migration time.

In a software-defined network (SDN), routes of packet flows need to be updated in situations such as maintenance and router replacement. Each flow is migrated from its old path to new path. The SDN update has an asynchronous nature; the time when the switches process commands by the controller varies depending on flows. Therefore, it is difficult to control an order of flow migrations, and packets can be lost by congestion. Existing models divide the time axis into rounds and assign migrations to these rounds. However, congestion caused by multiple migrations in the same round is uncontrollable. Based on the probability distribution of time required for each migration, congestion can occur. This paper proposes a flow update model which minimizes the expected amount of excessive traffic by shifting the probability distributions. The time axis is divided into time slots which are fine-grained than rounds, so that each probability distribution is shifted. The proposed model assigns the time when the controller injects a command of flow migration to time slots. The proposed model is formulated as an optimization problem to determine the command times to minimize the expected amount. This paper introduces two methods to compute the expected amount. This paper also introduces a two-stage scheduling scheme (2SS) that divides the optimization problem into two stages. 2SS suppresses the computation time from$\mathcal {O}(|T|^{|F|-1})$to$\mathcal {O}\left ({{|T|^{{}\frac {|F|-1}{2}}}}\right)$at the cost of including at most 0.12% error. 2SS suppresses the amount of excessive traffic than an existing model by at most 71.2%.

In network function virtualization, a network service is provided by a service function chain (SFC), which consists of a chain of virtual network functions (VNFs) within a specific order. SFC parallelism allows parallel processing among VNFs to reduce the end-to-end service delay. Existing works handle the service delay without considering traffic uncertainty, which leads to degraded performance on parallel structure balancing and deployment cost saving in the parallelized SFC deployment problem. This paper proposes a robust deployment model for parallelized SFCs against traffic uncertainty that satisfies the requirement of balanced parallel structures and minimizes the deployment cost. We define a traffic uncertainty set that handles both the variation of service traffic arrival rates and the fluctuation of parallel structures. We apply VNF sharing to improve the efficiency of resource allocation. We formulate the proposed model as a mixed integer second-order cone programming (MISOCP) problem. We introduce a heuristic algorithm to handle larger-size problems, where the MISOCP approach is intractable to obtain a solution in a practical time. Numerical results show the advantages of the proposed model in terms of deployment cost over the baseline models.

In network function virtualization, a network service is provided by a service function chain (SFC), which consists of a chain of virtual network functions (VNFs) within a specific order. SFC parallelism allows parallel processing among VNFs to reduce the end-to-end service delay. Existing works handle the service delay without considering traffic uncertainty, which leads to degraded performance on parallel structure balancing and deployment cost saving in the parallelized SFC deployment problem. This paper proposes a robust deployment model for parallelized SFCs against traffic uncertainty that satisfies the requirement of balanced parallel structures and minimizes the deployment cost. We define a traffic uncertainty set that handles both the variation of service traffic arrival rates and the fluctuation of parallel structures. We apply VNF sharing to improve the efficiency of resource allocation. We formulate the proposed model as a mixed integer second-order cone problem. Numerical results show the advantages of the proposed model in terms of deployment cost over the baseline models.

This paper proposes a backup computing and transmission capacity allocation model for virtual networks that minimizes the required backup computing capacity under multiple facility node failures. The proposed model adopts the probabilistic protection, where the probability that the protection fails due to insufficient capacity is restricted not to be greater than a given survivability parameter, by using robust optimization. The conventional model allocates the backup computing capacity by considering the probabilistic protection but allocates the transmission capacity for all backup paths dedicatedly. The proposed model allocates the backup transmission capacity only for the failure patterns that are considered under the probabilistic protection guarantee; the probabilistic protection is considered for both computing and transmission capacity allocation. Reducing the required backup transmission capacity can also reduce the required backup computing capacity, since more feasible solutions for backup computing capacity allocation can exist. We introduce a heuristic algorithm to solve the backup computing and transmission capacity allocation problem. Numerical results show that the proposed model reduces the required backup transmission capacity and enhances the feasibility of allocating virtual networks compared with the conventional model. We also observe that reducing the required backup transmission capacity can lead to reducing the required backup computing capacity.

In network function virtualization, virtual network functions (VNFs) are usually chained in specific orders to generate service function chains (SFCs). Recently, SFC parallelism has been presented to enable VNFs to run in parallel to reduce the end-to-end service delay. Existing works handle the issue of unbalanced parallel branches by assuming predefined linear delay models, which have limitations in efficient resource allocation and deployment cost savings. This paper proposes a deployment model for parallelized SFC that handles the imbalance issue with considering that the delay of each VNF depends on both arriving traffic and allocated computing resources, to improve the flexibility of computing resource allocation. We consider a nonlinear relationship between delay, allocated computing resources, and arriving traffic. We apply VNF sharing to improve the efficiency of resource allocation. We formulate the proposed model as a mixed integer second-order cone programming problem (MISOCP) to minimize the total deployment cost, with satisfying the end-to-end delay requirement. We also introduce a heuristic algorithm to solve the original problem, because the MISOCP approach is intractable to handle larger-size problems in practical time. Numerical results show that the proposed model achieves lower deployment cost than the baseline models.

This paper proposes a scheduling model for updating resource allocations for virtualized networks (VNs) without congestion. The proposed model determines the schedule of migrating traffic flows on VNs from old routes to new routes. The model aims to minimize the number of rounds required to complete the update of all existing VNs. We evaluate the performance of model in terms of the percentage of trials where feasible update scheduling exists and the number of rounds required to complete the update. Numerical results show that more rounds are required to achieve congestion-free update when the traffic demand or the number of VNs increases. The number of required rounds tends to remain the same when the maximum number of rounds exceeds a certain value; this observation helps network operators estimate the time required for VN update.

Service chaining provides network services to users by processing packets with a series of virtualized network functions (VNFs). This paper proposes a multi-source multicast service chaining model that guarantees the reliability of services with flexible routing and VNF placement. In order to obtain cost-efficient feasible solutions, we introduce an algorithm that iteratively solves an integer linear programming problem and an algorithm that conducts the VNF placement with a concept of the betweenness centrality. Numerical results show that the proposed model allocates the network and computation resources with the reduction in the total cost compared to the existing model.

In network function virtualization, virtual network functions (VNFs) are usually chained in specific orders to generate service function chains (SFCs). Recently, SFC parallelism has been presented to enable VNFs to run in parallel to reduce the end-to-end service delay. Existing works handle the issue of unbalanced parallel branches by assuming predefined linear delay models, which have limitations in efficient resource allocation and deployment cost savings. This paper proposes a deployment model for parallelized SFC that handles the imbalance issue with considering that the delay of each VNF depends on both the arriving traffic and the allocated computing resources, to improve the flexibility of computing resource allocation. We consider a non-linear relationship between delay, allocated computing resources, and arriving traffic. We apply VNF sharing to improve the efficiency of resource allocation. We formulate the proposed model as a mixed integer second-order cone problem to minimize the total deployment cost, with satisfying the end-to-end delay requirement. Numerical results show that the proposed model achieves lower deployment cost than the baseline models.

This paper proposes a controller placement model that takes into account the load-dependent sojourn time at each controller while considering controller failures in a software-defined network. The sojourn time is expressed by the queuing theory. The sojourn time varies depending on the amount of load arriving at each controller in the proposed model. The proposed model is formulated as a mixed integer second-order cone programming (MISOCP) problem. The controller placement problem studied in this paper is proven to be NP-hard. We develop a heuristic algorithm for the case where the solution to an optimization problem of the proposed model cannot be obtained in practical time. The proposed model is compared with two baseline models presented in the previous research. In the baseline models, the sojourn time does not depend on the amount of load arriving at each controller. Numerical results show that the number of placed controllers becomes smaller in the proposed model than in the baseline models. We also compare results obtained by solving the MISOCP problem to those of the heuristic algorithm. Numerical results show that the heuristic algorithm reduces the computation time required to determine the controller placement, whereas the difference between the number of controllers determined by the heuristic algorithm and the optimal value is at most 4.84%. The number of controllers placed by the heuristic algorithm tends to decrease by considering network centrality.

Service chaining provides network services by flexibly configuring service chains that connect virtualized network functions (VNFs) in the appropriate order so as to satisfy users’ needs. Existing models can be inefficient in terms of consuming network and computation resources since the models do not consider the traffic changes due to VNFs or the models restrict routing and VNF placement. This paper proposes a service chain provisioning model that handles the traffic changes created by VNFs while determining the VNF visit order of each request, request routes, and VNF placement. The service chain provisioning problem is formulated as an integer linear programming (ILP) problem. Three methods for limiting the number of VNF visit order patterns considered in the ILP problem are introduced to shorten the computation time. In order to handle a problem that is intractable with the ILP model, we introduce a greedy algorithm and an algorithm that divides the problem into the VNF placement part and the routing part. Numerical results show that considering the traffic changes due to VNFs yields more efficient consumption of network and computation resources than the alternative of assuming that the traffic amount of each request is constant between the endpoints. The results also show that the computation time can be shortened in our examined scenarios while we obtain the objective value larger by at most 0.4% than the optimal value by limiting the number of visit order patterns considered.

The provisioning cost of a virtualized network (VN) depends on several factors, including the numbers of virtual routers (VRs) and virtual links (VLs), mapping of them on a substrate infrastructure, and routing of data traffic. An existing model, known as the virtual network embedding (VNE) model, determines the embedding of given VN graphs into the substrate infrastructure. When the resource allocation model of the VNE problem is adopted to a single-entity scenario, where a single entity fulfills the roles of both a service provider and an infrastructure provider, an issue of increased costs of VNs and access paths arise. This paper proposes a model for virtualized network graph design and embedding (VNDE) for the single-entity scenario. The VNDE model determines the number of VRs and a VN graph for each request in conjunction with embedding. The VNDE model also determines access paths that connect customer premises and VRs. We formulate the VNDE model as an integer linear programming (ILP) problem. We develop heuristic algorithms for the cases where the ILP problem cannot be solved in practical time. We evaluate the performance of the VNDE model on several networks, including an actual Japanese academic backbone network. Numerical results show that the proposed model designs suitable VN graphs and embeds them according to the volume of traffic demands and access path cost. Compared with the benchmark model, which is based on a classic VNE approach, the proposed model reduces the provisioning cost at most 28.7% in our examined scenarios.

Service chaining concatenates virtual network functions (VNFs) in the network to automatically process packets in an appropriate order. In a situation where network traffic fluctuates, routes of service function chains (SFCs) need to be updated to achieve users' requirements. States of VNF instances that make up the SFC need to be kept consistent when updating the SFC routes. Existing models update SFCs one by one. If these models are adopted to the update of multiple SFCs, the total time required to update all SFCs can be long; problems such as leaving VNFs out-of-date can occur. This paper proposes a model that determines the update schedule of multiple SFCs guaranteeing state consistency. The objective function is minimizing the total time required to update all SFCs. Numerical results show that the total time required to update all SFCs can be shortened by updating multiple SFCs at the same time. The numerical results also show that the total time can be shortened by dividing a large buffer into an adequate number of small buffers.

Sparse mobile crowdsensing is a crowdsensing paradigm that reduces the sensing cost while ensuring data quality by collecting data sparsely and reconstructing desired data using inference algorithms including machine learning algorithms. However, real-time inference of spatial information with sparse mobile crowdsensing has not sufficiently considered the change of temporal characteristics of data. As a result, the accuracy of the reconstructed data can deteriorate over time. Therefore, this paper proposes a framework that periodically updates a machine learning model used for reconstructing data by evaluating the importance of the data in terms of both inference and re-training and giving priority to collecting important data.

This paper proposes a gradual program file placement control method using intermediate solutions output by an optimization solver. The computation resources in the platform can be efficiently utilized by reconfiguring the program file placement following the intermediate solutions. We present two policies, which differ on when to reconfigure the platform using intermediate solutions. Simulation results show that the proposed method achieves less cumulative number of program files placed in the platform, in exchange for the increase in the reconfiguration cost.

This paper proposes a controller placement model that takes into account the load-dependent sojourn time at each controller while considering controller failures. The sojourn time is expressed by the queuing theory. The sojourn time varies depending on the amount of load arriving at each controller in the proposed model. The proposed model is formulated as a mixed integer second-order cone programming problem. The proposed model is compared with two baseline models presented in the previous research. In the baseline models, the sojourn time does not depend on the amount of load arriving at each controller. Numerical results show that the number of placed controllers becomes smaller in the proposed model than in the baseline models. This indicates that, since the sojourn time in the proposed model varies according to the amount of load at a controller, the effect of the load-dependent sojourn time at a controller tends not to become dominant over that of the propagation delay, which enables a switch to connect to more distant controller than that in the baseline models.

This article proposes a primary and backup resource allocation model that provides a probabilistic protection guarantee for virtual machines against multiple failures of physical machines in a cloud provider to minimize the required total capacity. A physical machine allocates both primary and backup computing resources for virtual machines. When any failure occurs, the survived physical machines with preplanned backup resources recover the virtual machines on the failed physical machines and take over the workloads. The probability that the protection provided by a physical machine does not succeed is guaranteed within a given number. Providing the probabilistic protection can reduce the required backup capacity by allowing backup resource sharing, but it leads to a nonlinear programing problem in a general-capacity case against multiple failures. We apply robust optimization with extensive mathematical operations to formulate the primary and backup resource allocation problem as a mixed integer linear programming problem, where capacity fragmentation is suppressed. We prove the NP-hardness of considered problem. A heuristic is introduced to solve the optimization problem. The results reveal that the proposed model saves about one-third of the total capacity in our examined cases; it outperforms the conventional models in terms of both blocking probability and resource utilization.

Recently, space-division multiplexing (SDM) has been incorporated with elastic optical networks (EONs) to enhance the fiber capability, which forms space-division multiplexing-based elastic optical networks (SDM-EONs). During transmission of optical signals through multi-core fibers, inter-core crosstalk (XT) and intra-core physical layer impairments (PLIs) arise, which deteriorate the signal quality. Existing models typically handle inter-core XT and intra-core PLIs separately and set a single XT threshold for each modulation format, which results in an unacceptable lightpath due to the degradation of signal quality or leads to inefficient spectrum utilization. This paper proposes a routing, modulation, spectrum, and core allocation (RMSCA) model for SDM-EONs to consider inter-core XT and intra-core PLIs jointly. For each modulation format, it sets different XT thresholds and transmission reaches according to inter-core XT and intra-core PLIs. An optimization problem is formulated as an integer linear programming (ILP) problem. We prove that the RMSCA decision problem is NP-complete. We introduce a heuristic algorithm when the ILP problem is not tractable. Numerical results demonstrate that, by setting several XT limits for each modulation format, the proposed model increases spectrum efficiency compared to a benchmark model based on the literature.

Visual surveillance of dynamic objects on roads has been developed to ensure road safety for people. Particularly, vehicle tracking is considered as a key technology for the road safety; studies on multi-object tracking (MOT) are being actively pursued. However, when MOT is performed, raw vision data are not always available because of the technical limitation or the privacy concern of the system; MOT needs to be performed only using the coordinates obtained from the object detector without using features extracted from raw image data such as color of vehicles, which degrades the accuracy of MOT to the unsatisfactory level for road safety. This paper proposes an MOT scheme for moving vehicles that is inspired by cell tracking using the Viterbi algorithm. The proposed scheme extends the Brownian motion model, which was used in the base scheme of cell tracking, by weighting probability transitions in accordance with the direction of travel of vehicles on the road. We evaluate the proposed scheme using simulated vehicle-traffic data and verify that the proposed scheme performs better than benchmark schemes in terms of the accuracy of MOT. We also demonstrate an example of how the proposed scheme works well for real vehicle-traffic data.

This paper proposes a service chain provisioning model considering traffic changing effects of virtualized network functions (VNFs) while determining the VNF visit order of each request, routes of requests, and VNF placement. The service chain provisioning problem is formulated as an integer linear programming (ILP) problem. Three methods of limiting the number of VNF visit order patterns considered in the ILP problem are introduced in order to shorten the computation time. These methods select visit order patterns so as to suppress the sum of the traffic amount reserved by each request on its route. Numerical results show that the consumption of network and computation resources becomes more efficient by considering traffic amount changed by VNFs than the case assuming the traffic amount of each request to be constant end-to-end. The results also show that the computation time can be shortened in our examined scenarios while we obtain the objective value larger by at most 0.4% than the optimal value by limiting the number of visit order patterns.

Space-division multiplexing-based elastic optical networks (SDM-EONs) enhance the fiber capacity. Inter-core crosstalk (XT) and intra-core physical layer impairments (PLIs) occur in the multi-core fiber and degrade the optical signal. An existing model separately considers inter-core XT and intra-core PLIs, and sets a single XT threshold to each modulation format. This can lead to an unacceptable lightpath due to signal degradation or the occurrence of spectrum inefficiency. This paper proposes a routing, modulation, spectrum, and core allocation (RMSCA) model, which jointly considers inter-core XT and intra-core PLIs for SDM-EONs. The proposed model sets multiple XT thresholds for each modulation format based on inter-core XT and intra-core PLIs. We present an optimization problem and formulate it as an integer linear programming (ILP) problem. We introduce a heuristic algorithm for a network where the ILP problem is not tractable. Numerical results observe that the proposed model improves the spectrum efficiency by setting multiple XT thresholds to each modulation format.

This paper proposes a two-level processing scheme for three-dimension-image sensing. The first level processing selects only spatial regions needed for a smart monitoring task to reduce the total volume of data traffic. The second level processing integrates multiple (physical) image sensors into a virtual one to improve the delay and jitter performance in the realtime transmission of data from sensors to the cloud server. We develop a prototype system to implement the proposed scheme. Our demonstration validates that the proposed processing scheme works better than the benchmarks which do not adopt the two-level processing.

This article proposes a network design model to minimize the worst-case network congestion against multiple link failures, where open shortest path first link weights are determined at the beginning of network operation. In the proposed model, which is called the preventive start-time optimization model against multiple link failures (PSO-M), the number of multiple link failure patterns to support is restricted by introducing a probabilistic constraint calledprobabilistic guarantee. If the total probability of non-connected failure patterns does not exceed a specified probability, PSO-M provides a feasible solution of link weights. Otherwise, no feasible solution can be obtained. We introduce an extended model of PSO-M, called PSO-M with link reinforcement (PSO-MLR), where links are reinforced under a budget constraint. Link reinforcement in PSO-MLR has two purposes: maintaining network connectivity and reducing the worst-case congestion ratio. Numerical results show that PSO-M offers lower worst-case congestion ratios than the start-time optimization model, where link weights are obtained against the non-failure pattern assuming that multiple link failures are possible. The superiority of PSO-M strengthens as the average node degree of the network increases. Given a fixed budget, PSO-MLR allows the worst-case congestion ratio to be varied within a specific range. PSO-MLR can support a part of non-connected failure patterns to determine link weights, and so is a valuable enhancement of PSO-M.

This paper proposes an optimization model to derive the virtual network function (VNF) allocation of time slots in sequence aiming to maximize the continuous available time of service function chains (SFCs) in a network. The proposed model suppresses service interruptions otherwise created by the unavailability of virtual machines (VMs) and the reallocation of VNFs. The proposed model computes VNF allocation in a series of time slots based on a VM availability schedule, which provides information on the availability of each VM in each time slot. We formulate the proposed model as an integer linear programming (ILP) problem with the goal of maximizing the minimum number of longest continuous available time slots in each SFC. We prove that the decision version of the VNF allocation problem (VNFA) is NP-complete. As the size of ILP problem increases, the problem is difficult to solve in a practical time. We develop a heuristic algorithm to solve the VNFA problem. Numerical results show that the proposed model improves the continuous available time of SFCs compared with existing models, which partially consider VM unavailability or VNF reallocation. We observe that the proposed model together with a consideration of routing reduces the path length of requests. The developed heuristic algorithm is faster than the ILP approach with a limited performance penalty.

Service chaining is a method for providing desired network services to users by concatenating virtualized network functions (VNFs) in the network. There have been studies on service chain provisioning models that relax the visit order of VNFs and routing constraints. These models make it difficult to obtain an optimal solution in a practical time due to the huge number of decision variables associated with the problem. A heuristic approach that obtains a nearly-optimal solution within a practical time is needed. This paper proposes a column generation based heuristic algorithm for the service chain provisioning problem that relaxes the VNF visit order and routing constraints. The proposed algorithm divides the problem into a VNF placement problem and a routing problem and applies the column generation technique to solve the latter. Numerical results show that the proposed algorithm shortens the computation time compared to directly solving the original integer linear programming problem in exchange for some increase in the cost for VNF placement and link utilization.

This paper proposes a virtual network function (VNF) placement model for service chaining that minimizes the cost of using computation resources when no failure occurs while guaranteeing recovery against any single facility node failure within the recovery time objective (RTO) defined for each service. The proposed model adaptively allocates computation resources to each service under its RTO constraint. The proposed model introduces two sharing methods of computation resources among multiple service chains. The first method allows sharing a virtual machine (VM) where a VNF is scheduled to run after a failure, which contributes to suppressing the number of VMs reserved in preparation for a failure. The second method allows sharing computation capability used for VMs, which prevents unnecessary VNF scale-up that requires additional computation resources. A simulation study verifies that the proposed model reduces the cost of using computation resources compared to comparative models.

Real-time prediction of communications (or road) traffic by using cloud computing and sensor data collected by Internet-of-Things (IoT) devices would be very useful application of big-data analytics. However, upstream data flow from IoT devices to the cloud server could be problematic, even in fifth generation (5G) networks, because networks have mainly been designed for downstream data flows like for video delivery. This paper proposes a framework in which a software defined network (SDN), edge server, and cloud server cooperate with each other to control the upstream flow to maintain the accuracy of the real-time predictions under the condition of a limited network bandwidth. The framework consists of a system model, methods of prediction and determining the importance of data using machine learning, and a mathematical optimization. Our key idea is that the SDN controller optimizes data flows in the SDN on the basis of feature importance scores, which indicate the importance of the data in terms of the prediction accuracy. The feature importance scores are extracted from the prediction model by a machine-learning feature selection method that has traditionally been used to suppress effects of noise or irrelevant input variables. Our framework is examined in a simulation study using a real dataset consisting of mobile traffic logs. The results validate the framework; it maintains prediction accuracy under the constraint of limited available network bandwidth. Potential applications are also discussed.

A virtual network function allocation model to maximize continuous available time of service function chains was introduced in our previous work. The performance of this model needs to be evaluated on network devices. It is time-consuming and costly to deploy functions with real network devices. Existing simulation tools require powerful computation capability, which limits the usable cases. We implement a network service header based service function chain application which can be cooperated with the model. Demonstration validates that the application allocates functions by using the allocation from the model automatically and runs service function chains correctly.

This paper proposes a backup network design scheme that can determine backup link capacity in practical time. The proposed scheme suppresses the required backup link capacity while providing a guaranteed level of recovery against multiple independent link failures. The conventional scheme is based on robust optimization and suffers from the problem of overestimating the backup link capacity. The proposed scheme addresses the overestimation problem by computing the probabilistic distribution function of required backup link capacity in polynomial time. We formulate the backup network design problem with the proposed scheme as a mixed integer linear programming problem to minimize the total required backup link capacity. We prove that the decision version of backup network design problem is NP-complete. Given that network size will continue to increase, we introduce a heuristic approach of simulated annealing to solve the same problem. Numerical results show that the proposed scheme requires less total backup link capacity than the conventional scheme based on robust optimization.

Network function virtualization enables network operators to implement network functions in a software-oriented manner and makes network services (NSes) provisioning much simpler. This paper proposes an optimization model to schedule delay sensitive NSes with deadlines allowing resource sharing and preemption. Unlike conventional NS scheduling models with static resource allocation for virtualized network function (VNF) instances, the proposed model ensures that VNF instances deployed on the same node share computation resources of the node and are able to scale up/down to change their process rate at runtime. NSes mapped to the same VNF instance of the same node share computation resources of the VNF instance and are able to be processed in parallel by the VNF instance. Preemption is allowed, which means that rescheduling the order of NS processing at runtime is possible and the process duration of each function of an NS is allowed to be discrete. We formulate the proposed model as an integer linear programming problem to maximize the number of admissible NSes. Due to the complexity of the problem, we develop a genetic algorithm to solve it efficiently. We evaluate the proposed model with conventional models in the static and dynamic scenarios. The numerical results show that the proposed model outperforms conventional models in terms of acceptance ratio in both static and dynamic scenarios.

Software-defined network (SDN) is a network that the centralized SDN controller stores flow entries in the flow table of each SDN switch and controls packet flows as instructed by the stored flow entries. When a multicast service is provided in an SDN, the SDN controller stores a multicast entry dedicated for a multicast group in each SDN switch. It is necessary to suppress the number of flow entries required to set up a multicast tree due to the limited capacity of the flow table. In a conventional research, a multicast routing model that suppresses the number of multicast entries in one multicast request by replacing a part of them with unicast entries has been devised. However, since this conventional model individually determines a multicast tree route for each request, unicast entries configured for the same receiver are distributed in various SDN switches when multiple multicast services are requested. As a result, there is still the possibility of improving the reduction of the number of flow entries. In this paper, we propose a multicast routing model for multiple multicast requests that minimizes the number of flow entries. This proposed model determines multiple multicast tree routes simultaneously so that a unicast entry configured for the same receiver and stored in the same SDN switch is shared by multicast trees. We formulate the proposed model as an Integer Linear Programming (ILP) problem. Numerical results show that the proposed model reduces the required number of flow entries compared to the conventional model.

Real-time prediction of spatial information has attracted a lot of attention. Machine learning enables us to provide real-time prediction of spatial information such as road traffic by using aggregated sensor data. The amount of mobile traffic is forecasted to increase exponentially, thereby causing serious transmission delays when traffic loads are heavy. If a part of the data used for predicting spatial information in real time does not arrive on time, the prediction accuracy degrades because the prediction is done without the missing data. A utility-based scheduling technique has been suggested as a way of prioritizing such delay-sensitive data. However, no study has not addressed the utility-based scheduling for the real-time prediction of spatial information. Therefore, this paper proposes a scheme that enables modeling the utility function for real- time prediction of spatial information. The scheme is roughly composed of two steps: the first creates training data from original time-series data and a machine learning model using the data, while the second models the utility function using the feature selection method in the learning model. Feature selection method enables extracting the importance of data in terms of how much the data contributes to the prediction accuracy. This paper assumes the road traffic prediction as a scenario and shows the utility function modeled by the proposed scheme using real spatial datasets. A numerical study demonstrates how the model of the utility function works effectively in prioritizing data for real-time prediction in terms of accuracy.

This paper presents three approaches to solve the problem of finding the optimal backup resource assignment which maximizes the survival probability of network functions of middleboxes. In the previous work, no mathematical model to solve this problem is provided, so we formulate the problem as a mixed-integer linear programming (MILP) problem as the first approach. Formulating this MILP problem includes some special steps, which are not considered in the previous work. The MILP problem is not always solved in a practical time when the problem size becomes large. Then, we develop two heuristic approaches by replacing the objective of the original MILP problem relying on the idea of balancing the failure probabilities of functions of connected components. Numerical results show that our two developed heuristic approaches improve the survival probability from a conventional heuristic algorithm in some cases and reduce computation time compared to obtaining the optimal solution. Furthermore, one of our developed heuristic approaches provides exactly the optimal solution with shorter computation time compared to the time solving the original MILP problem in a special case.

In this paper, we propose a virtual network function placement and routing model for multicast service chaining based on merging multiple service paths (MSC-M). The multicast service chaining (MSC) provides a multicast path, which connects a source node and multiple destination nodes, and virtual network functions (VNFs) are placed on the path so that users on the destination nodes receive their desired services. The conventional MSC model configures multicast paths for services, each of which has the same source data and the same set of VNFs in a predefined order. In the MSC-M model, if paths of different services carry the same data on the same link, these paths are allowed to be merged into one path at that link, which improves the utilization of network resources. The MSC-M model determines the placement of VNFs and the route of paths so that the total cost associated with VNF placement and link usage is minimized. The MSC-M model is formulated as an integer linear programming (ILP) problem. In the ILP problem, data flows whose source data is the same and which already passed the same subset of VNFs belong to the same group. A part of paths of different services which carry data flows belonging to the same group are allowed to be merged into one path. Numerical results show that the MSC-M model reduces the total cost by 28.7% at a maximum compared to the conventional MSC model.

This paper proposes an optimization model to schedule network services (NSes) in virtual networks with resource sharing and preemption. Inefficient NS scheduling can severely degrade the acceptance ratio of arriving NSes of the network. Conventional NS scheduling models do not consider sharing computational resources of a node among different virtual network function (VNF) instances deployed on this node. In the proposed model, NSes mapped to the same VNF instance on the same node share computational resources of the VNF instance, and VNF instances deployed on the same node share computational resources of the node. The proposed model allows preemption, which means that rescheduling the process order of NSes in runtime is possible and the process duration of each function of an NS is allowed to be discrete. We formulate the proposed model as an integer linear programming problem to maximize the number of admissible NSes. The numerical results show that the proposed model outperforms conventional models in terms of the acceptance ratio of arriving NSes.

This paper proposes a master and slave controller assignment model against multiple controller failures in software defined network with considering propagation latency between switches and controllers. In our model, a controller can be assigned to multiple switches, and the survivability of each switch is guaranteed to a certain degree by assigning multiple controllers to it. We define the average-case expected propagation latency, the worst-case expected propagation latency, and the expected number of switches within a propagation latency bound, as three different objectives to be optimized, which lead to three different problems, in this paper. We formulate the proposed master and slave controller assignment model with different goals as three mixed integer linear programming problems. Results show that the optimal assignments vary for different problems. A greedy algorithm with polynomial time complexity is introduced to solve the same optimization problems. We evaluate the performance of introduced greedy algorithm compared with the optimal value in one of the problems, which minimizes the average-case propagation latency. The numerical results reveal that the computational time of running the greedy algorithm to obtain a solution is about 10-3times compared to that of solving the mixed integer linear programming problem; the obtained objective value is about 1.00324 times of the optimal value in average in our examined scenarios.

The machine-to-machine (M2M) service network platform that accommodates and controls various types of Internet of Things (IoT) devices has been presented. This paper investigates the program file placement strategies for the M2M service network platform which achieve low blocking ratio of new task requests and accommodate as many tasks as possible in the dynamic scenario. We present four strategies to arrange the program file placement, which differ in the objective function, the computation method, and the timing of rearrangement of whole program file placement. The simulation results show that a strategy based on solving a mixed-integer linear programming (MILP) model achieves the lowest blocking ratio and the highest number of completed tasks within a certain time period. In the case that the MILP-based strategies are intractable due to the computation time, a heuristic algorithm-based strategy which basically determines the program file placement for only a newly requested task achieves low blocking ratio.

In this paper, we describe approaches to enable a four-limbed robot to get over a step higher than its leg with torso contact. The higher the step becomes, the more difficult it is for legged robots to get over from the viewpoint of stability and kinematic reachability. Torso landing contributes to improving stability and robustness of motion for moving onto high step because of lower center of mass (CoM) and larger support polygon, which is seldomly utilized by previous human-sized legged robots. The approaches in this paper consist of the following two components. As for hardware, spikes are arranged on the bottom of robot’ s body for stable torso landing on a high step. As for motion generation, Sequential Quadratic Programming (SQP) is utilized to generate motion with torso landing to guarantee stability of robots during getting over the high step. From experiments, it is confirmed that the fourlimbed robot WAREC-I succeeded in moving onto a step with the height of 865mm.

Network function virtualization paradigm enables us to implement network functions provided in middleboxes as softwares that run on commodity servers. This paper proposes a backup resource allocation model for middleboxes with considering both failure probabilities of network functions and backup servers. A backup server can protect several functions; a function can have multiple backup servers. We take the importance of functions into account by defining a weighted unavailability for each function. We aim to find an assignment of backup servers to functions, where the worst weighted unavailability is minimized. We formulate the proposed backup resource allocation model as a mixed integer linear programming problem. We prove that the backup resource allocation problem for middlebox with importance is NP-complete. We develop three heuristic algorithms with polynomial time complexity to solve the problem. We analyze the approximation performances of different heuristic algorithms with providing several lower and upper bounds. We present the competitive evaluation in terms of deviation and computation time among the results obtained by running the heuristic algorithms and by solving the mixed integer linear programming problem. The results show the pros and cons of different approaches. With our analyses, a network operator can choose an appropriate approach according to the requirements in specific application scenarios.

This work proposes a defragmentation scheme using reroutable backup paths in toggled-based quasi 1+1 path protected elastic optical networks to enhance the efficiency of defragmentation and suppress the fragmentation effect. The proposed scheme allows both reallocation of spectrum slots of backup paths and rerouting of backup paths. By using the path exchanging approach in the proposed scheme, the primary paths become the backup path while the backup path becomes the primary path. This allows to utilize the advantages of defragmentation in both primary and backup paths. Considering rerouting and path exchanging, we present to the key idea to formulate the proposed scheme as an integer linear programming (ILP) problem. A heuristic algorithm is introduced to solve the problem for large networks, when ILP is not tractable. For a dynamic traffic scenario, an approach that suppresses the fragmentation considering rerouting and path exchanging operations is presented. The numerical results indicate that the blocking probability using the proposed scheme is suppressed compared to the conventional scheme.

Recently, the demand for realtime and accurate prediction of mobile traffic has been growing in traffic engineering and dynamic resource allocation that work to handle increased mobile data traffic. However, most conventional prediction techniques assumed that traffic logs at every unit time at every base station are perfectly available. This assumption is critical in realtime mobile traffic prediction because the volume of traffic log data collected at base stations is huge and they compete bandwidth with normal user application traffic when they are sent from base stations to the server that performs prediction. Therefore, in realtime mobile traffic prediction, we should consider the condition in which the bandwidth ensured for forwarding traffic log data is limited. In this paper, we propose a method that prioritizes traffic log data in the basis of the contribution to prediction accuracy; each base station sends more important traffic log data to the server with higher priority. The importance of each data entry of traffic log data means how much prediction accuracy would degrade if the entry is missing. The proposed method enables us to reduce the volume of traffic log data sent from base stations to the server while maintaining prediction accuracy at the sufficient level. Our simulation study using a real dataset of mobile-traffic measurement validates our method in terms of prediction accuracy under the limitation of available traffic log data.

This paper shows how to design, within practical time constraints, a backup network that suppresses the required resources while providing a guaranteed level of recovery against multiple link failures. The conventional scheme based on robust optimization has the problem of overestimating the backup link capacity. The backup network design scheme proposed herein computes the probabilistic distribution function of required backup link capacity in polynomial time, and so addresses the optimization problem of minimizing the total backup network capacity. For large networks, we introduce the heuristic approach of simulated annealing that adopts our approach to computing backup link capacity. Numerical analyses show that the proposed scheme requires less total backup network capacity than the conventional scheme based on robust optimization.

This paper proposes a backup resource allocation model that provides a probabilistic protection for primary physical machines in a cloud provider to minimize the required total capacity. When any random failure occurs, workloads are transferred to preplanned and dedicated backup physical machines for prompt recovery. In the proposed model, a probabilistic protection guarantee is introduced to prevent the cloud provider from capacity overbooking. We apply robust optimization in our model to formulate the backup resource allocation problem as an integer linear programming problem. A simulated annealing heuristic is adopted to solve the same optimization problem when the cloud provider is large. Finally, the results reveal that the required backup capacity depends on the reliability of primary physical machines. Specifically, the more the resources in primary physical machines share backup capacity when the failure probabilities of primary physical machines are sufficiently small, the less capacity is required for backup resource allocation.

Recently, the energy consumption in data centers is increasing. Introducing optical circuit to the inter-rack communication is considered as an effective solution. The authors are working on the research and development of the High-speed Optical Layer 1 Switch system for Time slot switching based optical data center networks (HOLST). We focused on Plomb Lanthanum Zirconate Titanate (PLZT) optical switch that performs nano seconds switching time. In this paper, several ideas on how to connect PLZT optical switches and Micro Electro Mechanical Systems (MEMS) optical switches, the composing modules of the HOLST, are proposed to design network architecture and evaluated in order to compare and consider power saving effect. The result of the numerical simulation shows that the proposal architecture achieves 50% energy consumption reduction than the conventional architecture.

In a high-speed backbone network, the failure of a network link may cause large data losses, so it is necessary to reserve spare network resources for faster recovery. The conventional protection methods to reserve backup routes do not consider the failure probability of each network link, so the same amount of network resources for the backup route are needed regardless of the failure probability of network links. This leads a decrease in the number of connections that can be accepted into the network. This paper proposes a routing and capacity allocation method that guarantees the expected value of allocated capacity. We formulate a mixed integer liner programming model for the proposed method. We conduct simulations to study the advantage of the expected capacity guaranteed routing over the conventional routing method in terms of bandwidth blocking probability. The results show that the proposed method reduces the bandwidth blocking probability to about 1/3 as compared to that of the conventional path protection method.

This article proposes a network control method that realizes on-demand service providing in Elastic Lambda Aggregation Network (EλAN). EλAN is a next-generation access/aggregation network that provides various network services having different protocols and QoS requirements. EλAN also achieves the reduction of total network power consumption by sharing access network equipment by multiple network services. In the proposed method, fixed optical trees are introduced to EλAN to exchange control messages in the same manner as today's FTTH systems. Discovery process and optical path/tree aggregation using the optical trees are explained in this article. We also discuss the energy-saving effect of the optical path/tree aggregation in EλAN.

We propose a technique for reducing the number of message duplicates during message flooding in wired networks. The key feature of our proposal is that each node keeps the partial information of shortest path trees whose roots are in its neighborhood. When receiving the flooding message, each node generates its duplicates and forwards them to a subset of neighbors, which are on the partial shortest path tree rooted at the message source. The partial information on shortest path trees is stored in message forwarding table of each node. We show that the partial shortest path tree can be constructed in a fully-distributed manner by simply using dummy message flooding. Our proposal can largely reduce the number of message duplicates while it guarantees the full reachability and keeps the time to reach the same as that in the full flooding. Duplicate reduction effect of our proposal is theoretically evaluated and numerically examined by simulation experiments.