Orchestration across network domains is essential for providing end-to-end network services in software-defined infrastructures. In this paper, we propose a vertex-centric distributed computing algorithm for finding all feasible mappings of a mesh virtual network request across domains. Our proposed algorithm is based on a distributed orchestration framework, where the topology information is locally maintained within each domain without disclosing to any centralized broker. The proposed algorithm first partitions a mesh virtual network request into a set of linear sub-requests and applies a vertex-centric distributed computing algorithm to find all feasible mappings of each individual linear sub-request. The feasible mappings of sub- requests are then merged to obtain all feasible mappings of the original virtual network request. Our simulation results show that partitioning a virtual network request to longer, balanced-length, non-overlap-link linear sub-requests is more scalable by significantly lowering the total computation time.

In this paper, we study the reliable virtual network mapping (RVNM) problem for allocating virtual machines (VMs) from multiple data centers (DCs) with the objective of maximizing the total reliability of a virtual network under two capacity constraints: computing capacity constraint at each DC and bandwidth capacity constraint on each link. We first describe graph models of RVNM, formulate the RVNM problem, and prove RVNM is NP-complete. We then formulate the problem as an integer linear programming (ILP) and give results for small-scale cases. A game theory based approach, named Link Mapping First (LMF), is proposed by modeling RVNM to the capacity-constrained potential game and is proved to be convergent to a pure Nash Equilibrium. Numerical results show that LMF achieves high reliability, which is close to the optimal solution, in small-scale cases and outperforms an existing Node Mapping First (NMF) algorithm, especially for large-scale cases.

In this paper, we study the minimum failure resource allocation (MFRA) problem of allocating virtual machines (VMs) across multiple optically interconnected data centers (DCs) with the objective of minimizing the total failure probability based on the information obtained from the optical network virtulization. We first describe the framework of resource allocation, formulate the MFRA problem, and prove that MFRA is NP-complete. We then provide ILP formulation to obtain the optimal solution for small scale problems and two heuristic algorithms, named Minimum SRG Cover (MSC) and Reliable DC Selection (RDS), to solve large scale problems. Numerical results show that both heuristics achieve results close to optimal solutions for small scale problems. Numerical results also show that although RDS has higher time complexity, it outperforms MSC especially when the requested VMs are small.

In this paper, we study the reliable resource allocation (RRA) problem of allocating virtual machines (VMs) from multiple optically interconnected data centers (DCs) with the objective of minimizing the total failure probability based on the information obtained from the optical network virtulization. We first describe the framework of resource allocation, formulate the RRA problem, and prove that RRA is NP-complete. We provide an algorithm, named Minimum Failure Cover (MFC), to obtain optimal solutions for small scale problems. We then provide a greedy algorithm, named VM-over-Reliability (VOR), to solve large scale problems. Numerical results show that VOR achieves results close to optimal solutions gained by MFC for small scale problems. Numerical results also show that VOR outperforms the resource allocation through random DC selection (RDS).

In this paper, we study the energy-efficient impairment-constrained regenerator placement (EIRP) problem with the objective of minimizing the total energy consumption in optical networks with mixed line rates. The destination of each path is guaranteed to receive the data correctly from the source based on the regenerator placement. We first provide the problem definition of EIRP and show that the EIRP problem is NP-complete. We then formulate the problem as a mixed integer linear program (MILP) and give results for small scale problems. Two heuristic approaches, named high line rate first (HLRF) and reroute only (RO), are presented. Numerical results show that HLRF achieves good results in both large and small scale problems, and that HLRF achieves higher energy efficiency than RO.

MultiMedia DataBase Management System (MMDBMS) becomes more popular in recent years, which supports complex and large multimedia data like images, audios, and videos etc. Data Broadcasting is an attractive approach for data dissemination to improve the limitations in mobile environment, such as narrow bandwidth, unreliable connections, and battery limitation. However, existing data broadcast schemes are inefficient for MMDBMS. In this paper, we present four novel multimedia data broadcast schemes (namely, SDAA, MDAA, AEA, and COA) specifically for wireless multichannel communications. The major strategies are scalable coding to generate data segments to different qualities, indexing and channel assignment to minimize the expected waiting time for clients. We prove theoretically that SDAA is a 2-approximation. COA performs best when we release the constraints and it can be judged as an theoretical lower bound, while AEA outputs local optimal solution with quality allocation constraints. Finally, SDAA+AEA form a best scheduling for practical applications. We also provide numerical experiments to evaluate the system performance, proving the efficiency of our schemes.

In this paper, we study the problem of reliable collective communication (broadcast or gossip) with the objective of maximizing the reliability of the collective communication. The need for collective communication arises in many problems of parallel and distributed computing, including Grid or cloud computing and database management. We describe the network model, formulate the reliable collective communication problem, prove that the maximum reliable collective communication problem is NP-hard, and provide an integer linear program (ILP) formulation for the problem. We then provide a greedy approximation algorithm to construct collective communication (through a spanning tree) that achieves an approximation ratio of 1 + ln(|V|+α|E|-1) , where α is the average number of shared link risk groups (SRLGs) along links, and |V| and |E| are the total number of vertices and edges of the network, respectively. Simulations demonstrate that our approximation algorithm achieves good performance in both small and large networks and that, in almost 95% of total cases, our algorithm outperforms the modified minimum spanning tree algorithms.

In multi-domain optical networks, due to confidentiality and management considerations, it may be infeasible to broadcast complete domain state information among domains. Nevertheless, sufficient information on each domain is required in order to keep network activities operating successfully. Topology Aggregation (TA) may be adopted to abstract a domain's detailed topology into an aggregated topology which only shows limited information about the network. With the introduction of Shared Risk Link Groups (SRLGs), each of which includes a set of links affected by the same failure, the TA approach needs to consider the presence of SRLGs to generate a more survivable aggregated topology. In this paper, we propose SRLG-aware topology aggregation approaches that can help in finding a pair of inter-domain paths with a minimum set of common SRLGs.

In this paper, we study the problem of multicast flow aggregation with the objective of minimizing the total number of trees. Each established tree can choose a line rate from multiple available line rates. The destinations of each tree are guaranteed to receive data correctly from the source through the chosen line rate. We first use two auxiliary graphs to describe the problem and show that the problem is NP-hard. An integer linear program (ILP) is given to solve small scale problems. We then provide a heuristic approach, named highest rate first (HRF). Numerical results show that HRF achieves good results in both large and small scale problems.

In this paper, we address the dynamic multicast flow aggregation problem and propose a novel graph model with different aggregation policies. We first give the network model with an auxiliary graph for the aggregation. We then discuss an aggregation algorithm using the auxiliary graph and propose three policies for aggregating multicast flows. Numerical results show that aggregation can tremendously reduce the total trees in the network while the three policies can achieve good performance for various scenarios.

Standard advance reservation (SAR) mechanisms have been proposed as a way to provision resources for high-bandwidth applications in order to provide QoS guarantees to users; however, variations in the available bandwidth on different links over time can lead to situations in which standard advance reservations must be pushed further into the future, leading to higher end-to-end delays. We introduce the concept of time-shift advance reservation (TSAR), which improves bandwidth utilization by making use of delay elements at intermediate nodes within the network. We describe the TSAR architecture and discuss various design and implementation issues. The routing and scheduling problem in TSAR networks is defined, and a routing and scheduling algorithm is proposed. We find that TSAR with the proposed algorithm minimizes latency for each request and reduces request blocking compared to standard advance reservation and immediate reservation approaches.

In this paper, we study the content protection problem through multicast flow aggregation (CPMFA) in which programs with protection requirement are aggregated into different light trees at the access routers and delivered from the head end to one or more destinations. We first use a tri-partite graph to describe the problem and show that the problem is NP-complete. We then formulate the problem as an interger linear program (ILP) and give results for small scale problems. Two hueristic appoaches, named two-step separated multicast flow aggregation (S-MFA) and mixed multicast flow aggregation (M-MFA), are presented. Numerical results show that S-MFA and M-MFA achieve good results in both large and small scale problems.

In this paper, we study the problem of multicast flow aggregation combined with light-tree establishment in optical networks. We first give the network model with a tri-partite aggregation graph to describe the problem and show that the problem is NP-complete. We then formulate the problem as an integer linear program (ILP) and give results for small scale problems. A heuristic approach, named fixed tree aggregation (FTA), is presented and results show that FTA achieves good results in both large and small scale problems.

In this paper, we investigate the problem of survivable grooming for anycasting over wavelength division multiplexing (WDM) networks. Anycasting is a communication paradigm in which a source node sends data to any one out of multiple candidate destinations. In WDM networks, the standard anycasting problem involves the establishment of a connection from the source to any one destination with the objective of minimizing the resources used. In order to provide survivability, the problem can be extended to find both a connection to a primary destination and a connection to a backup destination. The connections, which may require an amount of bandwidth that may be less than the bandwidth of an entire wavelength, can be groomed with other connections in the WDM network. We propose an auxiliary graph approach to solving the survivable grooming problem for anycasting in WDM networks, and we propose three different protection approaches for providing different degrees of survivability against link failures and destination failures. The effectiveness of the proposed schemes is verified through simulation.

In this paper, we study the problem of time-constrained multicast flow aggregation in which programs with specified starting times and specified ending times are aggregated together and delivered from a head end to one or more destinations. We first use a four-partite graph to describe the problem and show that the problem is NP-complete. We then formulate the problem as an integer linear program (ILP) and give results for small scale problems. A heuristic approach, named time compatible first (TCF), is presented, and results show that TCF achieves good results in both large and small scale problems.