Stojan Trajanovski
Stojan Trajanovski has a total of 38 co-authors. Here are the top co-authors by number of shared publications:
- Xiaoming Fu
University of Göttingen
7 shared publications - Fan Li
School of Computer Science and Technology, Beijing Institute of Technology, Beijing, China
6 shared publications - Song Yang
School of Computer Science and Technology, Beijing Institute of Technology, Beijing, China
6 shared publications - Liehuang Zhu
Beijing Institute of Technology
3 shared publications Piet Van Mieghem
Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands
3 shared publications- Dongchao Guo
School of Computer Science, Beijing Information Science and Technology University, Beijing 102206, China
2 shared publications
Latest Publications
- 18 November 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Networking
- Vol. 34, 1761-1776
Efficient and Flexible Multi-Qubit Entanglement Transmission in Quantum Networks
The unprecedented advancements in quantum technology have opened new prospects for the widespread adoption of quantum applications, placing new demands on the information transmission capabilities of large-scale quantum networks. Long-distance and stable entanglements are deemed as the lifeline in quantum network communication. However, some weaknesses, e.g., quantum decoherence, scarce quantum memory, and uneven-quality entanglement, of the quantum entanglement hinder the development. In this paper, we propose Sophon, an online transmission framework for quantum networks, which utilizes high-dimensional entanglements to concurrently transmit multi-qubit data to satisfy the transmission requirements of the real-time request set. We first model the quantum network with multi-qubit entanglement represented by $W$ quantum state and then formulate the Entanglement Routing and Qubit Provisioning (ERQP) problem as a global-local optimization process. To solve the ERQP problem, we distributedly regard each network node as an RL agent for resource provisioning and extend the step-updating of the Markov Decision Process by introducing a centralized controller for entanglement route selection to optimize local and global objectives, respectively. Extensive simulations demonstrate, on the self-made simulation platform, Sophon achieves a $21.89\%-66.52\%$ decrease in the communication cost, and is more robust on different scales of the network topology and the request set than the baselines.
- 18 November 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Networking
- Vol. 34, 1761-1776
Efficient and Flexible Multi-Qubit Entanglement Transmission in Quantum Networks
The unprecedented advancements in quantum technology have opened new prospects for the widespread adoption of quantum applications, placing new demands on the information transmission capabilities of large-scale quantum networks. Long-distance and stable entanglements are deemed as the lifeline in quantum network communication. However, some weaknesses, e.g., quantum decoherence, scarce quantum memory, and uneven-quality entanglement, of the quantum entanglement hinder the development. In this paper, we propose Sophon, an online transmission framework for quantum networks, which utilizes high-dimensional entanglements to concurrently transmit multi-qubit data to satisfy the transmission requirements of the real-time request set. We first model the quantum network with multi-qubit entanglement represented by $W$ quantum state and then formulate the Entanglement Routing and Qubit Provisioning (ERQP) problem as a global-local optimization process. To solve the ERQP problem, we distributedly regard each network node as an RL agent for resource provisioning and extend the step-updating of the Markov Decision Process by introducing a centralized controller for entanglement route selection to optimize local and global objectives, respectively. Extensive simulations demonstrate, on the self-made simulation platform, Sophon achieves a $21.89\%-66.52\%$ decrease in the communication cost, and is more robust on different scales of the network topology and the request set than the baselines.
- 4 November 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 33 (1) , 398-413
Exploiting Wide-Area Resource Elasticity With Fine-Grained Orchestration for Serverless Analytics
With the flourishing of global services, low-latency analytics on large-volume geo-distributed data has been a regular requirement for application decision-making. Serverless computing, with its rapid function start-up and lightweight deployment, provides a compelling way for geo-distributed analytics. However, existing research focuses on elastic resource scaling at the stage granularity, struggling to heterogeneous resource demands across component functions in wide-area settings . The neglect potentially results in the cost inefficiency and Service Level Objective (SLO) violations. In this paper, we advocate for fine-grained function orchestration to exploit wide-area resource elasticity . We thereby present Demeter , a fine-grained function orchestrator that saves job execution costs for geo-distributed serverless analytics while ensuring SLO compliance. By learning from volatile and bursty environments, Demeter jointly makes per-function placement and resource allocation decisions using a well-optimized multi-agent reinforcement learning algorithm with a pruning mechanism. It prevent the irreparable performance loss by function congestion control. Ultimately, we implement Demeter and evaluate it with the realistic workloads. Experimental results reveal that Demeter outperforms the baselines by up to 46.6% on cost, while reducing SLO violation by over 23.7% and bringing it to below 15%.
- 4 November 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 33 (1) , 398-413
Exploiting Wide-Area Resource Elasticity With Fine-Grained Orchestration for Serverless Analytics
With the flourishing of global services, low-latency analytics on large-volume geo-distributed data has been a regular requirement for application decision-making. Serverless computing, with its rapid function start-up and lightweight deployment, provides a compelling way for geo-distributed analytics. However, existing research focuses on elastic resource scaling at the stage granularity, struggling to heterogeneous resource demands across component functions in wide-area settings . The neglect potentially results in the cost inefficiency and Service Level Objective (SLO) violations. In this paper, we advocate for fine-grained function orchestration to exploit wide-area resource elasticity . We thereby present Demeter , a fine-grained function orchestrator that saves job execution costs for geo-distributed serverless analytics while ensuring SLO compliance. By learning from volatile and bursty environments, Demeter jointly makes per-function placement and resource allocation decisions using a well-optimized multi-agent reinforcement learning algorithm with a pruning mechanism. It prevent the irreparable performance loss by function congestion control. Ultimately, we implement Demeter and evaluate it with the realistic workloads. Experimental results reveal that Demeter outperforms the baselines by up to 46.6% on cost, while reducing SLO violation by over 23.7% and bringing it to below 15%.
- Open Access
Core-sets for Fair and Diverse Data Summarization
We study core-set construction algorithms for the task of Diversity Maximization under fairness/partition constraint. Given a set of points $P$ in a metric space partitioned into $m$ groups, and given $k_1,\ldots,k_m$, the goal of this problem is to pick $k_i$ points from each group $i$ such that the overall diversity of the $k=\sum_i k_i$ picked points is maximized. We consider two natural diversity measures: sum-of-pairwise distances and sum-of-nearest-neighbor distances, and show improved core-set construction algorithms with respect to these measures. More precisely, we show the first constant factor core-set w.r.t. sum-of-pairwise distances whose size is independent of the size of the dataset and the aspect ratio. Second, we show the first core-set w.r.t. the sum-of-nearest-neighbor distances. Finally, we run several experiments showing the effectiveness of our core-set approach. In particular, we apply constrained diversity maximization to summarize a set of timed messages that takes into account the messages' recency. Specifically, the summary should include more recent messages compared to older ones. This is a real task in one of the largest communication platforms, affecting the experience of hundreds of millions daily active users. By utilizing our core-set method for this task, we achieve a 100x speed-up while losing the diversity by only a few percent. Moreover, our approach allows us to improve the space usage of the algorithm in the streaming setting.Open AccessCore-sets for Fair and Diverse Data Summarization
We study core-set construction algorithms for the task of Diversity Maximization under fairness/partition constraint. Given a set of points $P$ in a metric space partitioned into $m$ groups, and given $k_1,\ldots,k_m$, the goal of this problem is to pick $k_i$ points from each group $i$ such that the overall diversity of the $k=\sum_i k_i$ picked points is maximized. We consider two natural diversity measures: sum-of-pairwise distances and sum-of-nearest-neighbor distances, and show improved core-set construction algorithms with respect to these measures. More precisely, we show the first constant factor core-set w.r.t. sum-of-pairwise distances whose size is independent of the size of the dataset and the aspect ratio. Second, we show the first core-set w.r.t. the sum-of-nearest-neighbor distances. Finally, we run several experiments showing the effectiveness of our core-set approach. In particular, we apply constrained diversity maximization to summarize a set of timed messages that takes into account the messages' recency. Specifically, the summary should include more recent messages compared to older ones. This is a real task in one of the largest communication platforms, affecting the experience of hundreds of millions daily active users. By utilizing our core-set method for this task, we achieve a 100x speed-up while losing the diversity by only a few percent. Moreover, our approach allows us to improve the space usage of the algorithm in the streaming setting. - Top Cited Papers
- 30 January 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 34 (4) , 1186-1201
Leveraging Deep Reinforcement Learning With Attention Mechanism for Virtual Network Function Placement and Routing
The efficacy of Network Function Virtualization (NFV) depends critically on (1) where the virtual network functions (VNFs) are placed and (2) how the traffic is routed. Unfortunately, these aspects are not easily optimized, especially under time-varying network states with different QoS requirements. Given the importance of NFV, many approaches have been proposed to solve the VNF placement and Service Function Chaining (SFC) routing problem. However, those prior approaches mainly assume that the network state is static and known, disregarding dynamic network variations. To bridge that gap, we leverage Markov Decision Process (MDP) to model the dynamic network state transitions. To jointly minimize the delay and cost of NFV providers and maximize the revenue, we first devise a customized Deep Reinforcement Learning (DRL) algorithm for the VNF placement problem. The algorithm uses the attention mechanism to ascertain smooth network behavior within the general framework of network utility maximization (NUM). We then propose attention mechanism-based DRL algorithm for the SFC routing problem, which is to find the path to deliver traffic for the VNFs placed on different nodes. The simulation results show that our proposed algorithms outperform the state-of-the-art algorithms in terms of network utility, delay, cost, and acceptance ratio.
- 30 January 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 34 (4) , 1186-1201
Top Cited PapersLeveraging Deep Reinforcement Learning With Attention Mechanism for Virtual Network Function Placement and Routing
The efficacy of Network Function Virtualization (NFV) depends critically on (1) where the virtual network functions (VNFs) are placed and (2) how the traffic is routed. Unfortunately, these aspects are not easily optimized, especially under time-varying network states with different QoS requirements. Given the importance of NFV, many approaches have been proposed to solve the VNF placement and Service Function Chaining (SFC) routing problem. However, those prior approaches mainly assume that the network state is static and known, disregarding dynamic network variations. To bridge that gap, we leverage Markov Decision Process (MDP) to model the dynamic network state transitions. To jointly minimize the delay and cost of NFV providers and maximize the revenue, we first devise a customized Deep Reinforcement Learning (DRL) algorithm for the VNF placement problem. The algorithm uses the attention mechanism to ascertain smooth network behavior within the general framework of network utility maximization (NUM). We then propose attention mechanism-based DRL algorithm for the SFC routing problem, which is to find the path to deliver traffic for the VNFs placed on different nodes. The simulation results show that our proposed algorithms outperform the state-of-the-art algorithms in terms of network utility, delay, cost, and acceptance ratio.
- 22 August 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. PP (15361233) , 1-17
Video Content Placement At the Network Edge: Centralized and Distributed Algorithms
In the traditional video streaming service provisioning paradigm, viewers typically request video content through a central Content Delivery Network (CDN) server. However, because of the uncertain wide area network delays, the (remote) viewers usually suffer from long video streaming delay, which affects the quality of experience. Multi-Access Edge Computing (MEC) offers a way to shorten the video streaming delay by building small-scale cloud infrastructures at the network edge, which are in close proximity to the viewers. In this paper, we present novel centralized and distributed algorithms for the video content placement problem in MEC. In the proposed centralized video content placement algorithm, we leverage the Lyapunov optimization technique to formulate the video content placement problem as a series of one-time-slot optimization problems and apply an Alternating Direction Method of Multipliers (ADMM)-based method to solve each of them. We further devise a distributed Multi-Agent Reinforcement Learning (MARL)-based method with value decomposition mechanism and parallelization policy update method to solve the video content placement problem. The value Decomposition mechanism deals with the credit assignment among multiple agents, which promotes the cooperative optimization of the global target and reduces the frequency of information exchange. The parallelization of policy network can speed up the convergence process. Simulation results verify the effectiveness and superiority of our proposed centralized and distributed algorithms in terms of performance.
- 22 August 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. PP (15361233) , 1-17
Video Content Placement At the Network Edge: Centralized and Distributed Algorithms
In the traditional video streaming service provisioning paradigm, viewers typically request video content through a central Content Delivery Network (CDN) server. However, because of the uncertain wide area network delays, the (remote) viewers usually suffer from long video streaming delay, which affects the quality of experience. Multi-Access Edge Computing (MEC) offers a way to shorten the video streaming delay by building small-scale cloud infrastructures at the network edge, which are in close proximity to the viewers. In this paper, we present novel centralized and distributed algorithms for the video content placement problem in MEC. In the proposed centralized video content placement algorithm, we leverage the Lyapunov optimization technique to formulate the video content placement problem as a series of one-time-slot optimization problems and apply an Alternating Direction Method of Multipliers (ADMM)-based method to solve each of them. We further devise a distributed Multi-Agent Reinforcement Learning (MARL)-based method with value decomposition mechanism and parallelization policy update method to solve the video content placement problem. The value Decomposition mechanism deals with the credit assignment among multiple agents, which promotes the cooperative optimization of the global target and reduces the frequency of information exchange. The parallelization of policy network can speed up the convergence process. Simulation results verify the effectiveness and superiority of our proposed centralized and distributed algorithms in terms of performance.
- 25 September 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Biomedical Engineering
- Vol. 68 (4) , 1330-1340
Tongue Tumor Detection in Hyperspectral Images Using Deep Learning Semantic Segmentation
Objective: The utilization of hyperspectral imaging (HSI) in real-time tumor segmentation during a surgery have recently received much attention, but it remains a very challenging task. Methods: In this work, we propose semantic segmentation methods and compare them with other relevant deep learning algorithms for tongue tumor segmentation. To the best of our knowledge, this is the first work using deep learning semantic segmentation for tumor detection in HSI data using channel selection and accounting for more spatial tissue context and global comparison between the prediction map and the annotation per sample. Results and Conclusion: On a clinical data set with tongue squamous cell carcinoma, our best method obtains very strong results of average dice coefficient and area under the ROC-curve of 0.891 +/- 0.053 and 0.924 +/- 0.036, respectively on the original spatial image size. The results show that a very good performance can be achieved even with a limited amount of data. We demonstrate that important information regarding tumor decision is encoded in various channels, but some channel selection and filtering is beneficial over the full spectra. Moreover, we use both visual (VIS) and near-infrared (NIR) spectrum, rather than commonly used only VIS spectrum; although VIS spectrum is generally of higher significance, we demonstrate NIR spectrum is crucial for tumor capturing in some cases. Significance: The HSI technology augmented with accurate deep learning algorithms has a huge potential to be a promising alternative to digital pathology or a doctors' supportive tool in real-time surgeries.
- 25 September 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Biomedical Engineering
- Vol. 68 (4) , 1330-1340
Tongue Tumor Detection in Hyperspectral Images Using Deep Learning Semantic Segmentation
Objective: The utilization of hyperspectral imaging (HSI) in real-time tumor segmentation during a surgery have recently received much attention, but it remains a very challenging task. Methods: In this work, we propose semantic segmentation methods and compare them with other relevant deep learning algorithms for tongue tumor segmentation. To the best of our knowledge, this is the first work using deep learning semantic segmentation for tumor detection in HSI data using channel selection and accounting for more spatial tissue context and global comparison between the prediction map and the annotation per sample. Results and Conclusion: On a clinical data set with tongue squamous cell carcinoma, our best method obtains very strong results of average dice coefficient and area under the ROC-curve of 0.891 +/- 0.053 and 0.924 +/- 0.036, respectively on the original spatial image size. The results show that a very good performance can be achieved even with a limited amount of data. We demonstrate that important information regarding tumor decision is encoded in various channels, but some channel selection and filtering is beneficial over the full spectra. Moreover, we use both visual (VIS) and near-infrared (NIR) spectrum, rather than commonly used only VIS spectrum; although VIS spectrum is generally of higher significance, we demonstrate NIR spectrum is crucial for tumor capturing in some cases. Significance: The HSI technology augmented with accurate deep learning algorithms has a huge potential to be a promising alternative to digital pathology or a doctors' supportive tool in real-time surgeries.
- Top Cited Papers
- 17 August 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 32 (2) , 295-314
Recent Advances of Resource Allocation in Network Function Virtualization
Network Function Virtualization (NFV) has been emerging as an appealing solution that transforms complex network functions from dedicated hardware implementations to software instances running in a virtualized environment. In this survey, we provide an overview of recent advances of resource allocation in NFV. We generalize and analyze four representative resource allocation problems, namely, (1) the VNF Placement and Traffic Routing problem, (2) VNF Placement problem, (3) Traffic Routing problem in NFV, and (4) the VNF Redeployment and Consolidation problem. After that, we study the delay calculation models and VNF protection (availability) models in NFV resource allocation, which are two important Quality of Service (QoS) parameters. Subsequently, we classify and summarize the representative work for solving the VPTR problem and the VRC problem by considering various QoS parameters (e.g., cost, delay, reliability and energy) and different scenarios (e.g., edge cloud, online provisioning and distributed provisioning). Finally, we conclude our survey with a short discussion on the state-of-the-art of literatures and emerging topics in the related field, and highlight areas where we expect high potential for future research.
- 17 August 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 32 (2) , 295-314
Top Cited PapersRecent Advances of Resource Allocation in Network Function Virtualization
Network Function Virtualization (NFV) has been emerging as an appealing solution that transforms complex network functions from dedicated hardware implementations to software instances running in a virtualized environment. In this survey, we provide an overview of recent advances of resource allocation in NFV. We generalize and analyze four representative resource allocation problems, namely, (1) the VNF Placement and Traffic Routing problem, (2) VNF Placement problem, (3) Traffic Routing problem in NFV, and (4) the VNF Redeployment and Consolidation problem. After that, we study the delay calculation models and VNF protection (availability) models in NFV resource allocation, which are two important Quality of Service (QoS) parameters. Subsequently, we classify and summarize the representative work for solving the VPTR problem and the VRC problem by considering various QoS parameters (e.g., cost, delay, reliability and energy) and different scenarios (e.g., edge cloud, online provisioning and distributed provisioning). Finally, we conclude our survey with a short discussion on the state-of-the-art of literatures and emerging topics in the related field, and highlight areas where we expect high potential for future research.
- 20 July 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Internet of Things Journal
- Vol. 8 (2) , 1095-1108
Survivable Task Allocation in Cloud Radio Access Networks With Mobile-Edge Computing
Cloud radio access network (C-RAN) is a promising 5G network architecture by establishing baseband units (BBU) pools to perform baseband processing functionalities and deploying remote radio heads (RRHs) for wireless signal transmission and reception. Mobile-edge computing (MEC) offers a way to shorten the service delay by building small-scale cloud infrastructures at the network edge. By co-locating the BBU pool with edge cloud at the so-called BBU node, we can take full advantages of C-RAN and MEC for better spectrum utilization and delay-guaranteed services. In this article, we first study how to allocate each user's task to the BBU node and find the path from his/her accessing RRH node to the BBU node such that the maximum service delay among all the requests is minimized. We then consider this problem with survivability concerns, which is to use both primary and backup BBU nodes to issue the request such that the primary path and backup path are link disjoint. We analyze the complexities of these two problems and prove they are NP-hard in general. Subsequently, we devise a randomized approximation algorithm and an efficient heuristic to solve the considered problems, respectively. The simulation results show that the proposed algorithms outperform two benchmark heuristics in terms of acceptance ratio and maximum service delay.
- 20 July 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Internet of Things Journal
- Vol. 8 (2) , 1095-1108
Survivable Task Allocation in Cloud Radio Access Networks With Mobile-Edge Computing
Cloud radio access network (C-RAN) is a promising 5G network architecture by establishing baseband units (BBU) pools to perform baseband processing functionalities and deploying remote radio heads (RRHs) for wireless signal transmission and reception. Mobile-edge computing (MEC) offers a way to shorten the service delay by building small-scale cloud infrastructures at the network edge. By co-locating the BBU pool with edge cloud at the so-called BBU node, we can take full advantages of C-RAN and MEC for better spectrum utilization and delay-guaranteed services. In this article, we first study how to allocate each user's task to the BBU node and find the path from his/her accessing RRH node to the BBU node such that the maximum service delay among all the requests is minimized. We then consider this problem with survivability concerns, which is to use both primary and backup BBU nodes to issue the request such that the primary path and backup path are link disjoint. We analyze the complexities of these two problems and prove they are NP-hard in general. Subsequently, we devise a randomized approximation algorithm and an efficient heuristic to solve the considered problems, respectively. The simulation results show that the proposed algorithms outperform two benchmark heuristics in terms of acceptance ratio and maximum service delay.
- 31 August 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Control of Network Systems
- Vol. 5 (4) , 1682-1692
Designing Virus-Resistant, High-Performance Networks: A Game-Formation Approach
Designing an optimal network topology while balancing multiple, possibly conflicting objectives like cost, performance, and resiliency to viruses is a challenging endeavor, let alone in the case of decentralized network formation. We therefore propose a game-formation technique where each player aims to minimize its cost in installing links, the probability of being infected by a virus and the sum of hopcounts on its shortest paths to all other nodes.
- 31 August 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Control of Network Systems
- Vol. 5 (4) , 1682-1692
Designing Virus-Resistant, High-Performance Networks: A Game-Formation Approach
Designing an optimal network topology while balancing multiple, possibly conflicting objectives like cost, performance, and resiliency to viruses is a challenging endeavor, let alone in the case of decentralized network formation. We therefore propose a game-formation technique where each player aims to minimize its cost in installing links, the probability of being infected by a virus and the sum of hopcounts on its shortest paths to all other nodes.
- Open Access
Reliable Virtual Machine Placement and Routing in Clouds
In current cloud computing systems, when leveraging virtualization technology, the customer's requested data computing or storing service is accommodated by a set of communicated virtual machines (VM) in a scalable and elastic manner. These VMs are placed in one or more server nodes according to the node capacities or failure probabilities. The VM placement availability refers to the probability that at least one set of all customer's requested VMs operates during the requested lifetime. In this paper, we first study the problem of placing at most H groups of k requested VMs on a minimum number of nodes, such that the VM placement availability is no less than $\delta$, and that the specified communication delay and connection availability for each VM pair under the same placement group are not violated. We consider this problem with and without Shared-Risk Node Group (SRNG) failures, and prove this problem is NP-hard in both cases. We subsequently propose an exact Integer Nonlinear Program (INLP) and an efficient heuristic to solve this problem. We conduct simulations to compare the proposed algorithms with two existing heuristics in terms of performance. Finally, we study the related reliable routing problem of establishing a connection over at most w link-disjoint paths from a source to a destination, such that the connection availability requirement is satisfied and each path delay is no more than a given value. We devise an exact algorithm and two heuristics to solve this NP-hard problem, and evaluate them via simulations.Open AccessReliable Virtual Machine Placement and Routing in Clouds
In current cloud computing systems, when leveraging virtualization technology, the customer's requested data computing or storing service is accommodated by a set of communicated virtual machines (VM) in a scalable and elastic manner. These VMs are placed in one or more server nodes according to the node capacities or failure probabilities. The VM placement availability refers to the probability that at least one set of all customer's requested VMs operates during the requested lifetime. In this paper, we first study the problem of placing at most H groups of k requested VMs on a minimum number of nodes, such that the VM placement availability is no less than $\delta$, and that the specified communication delay and connection availability for each VM pair under the same placement group are not violated. We consider this problem with and without Shared-Risk Node Group (SRNG) failures, and prove this problem is NP-hard in both cases. We subsequently propose an exact Integer Nonlinear Program (INLP) and an efficient heuristic to solve this problem. We conduct simulations to compare the proposed algorithms with two existing heuristics in terms of performance. Finally, we study the related reliable routing problem of establishing a connection over at most w link-disjoint paths from a source to a destination, such that the connection availability requirement is satisfied and each path delay is no more than a given value. We devise an exact algorithm and two heuristics to solve this NP-hard problem, and evaluate them via simulations.