اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOnline Admission Control and Embedding of Service Chains
109
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The virtualization and softwarization of modern computer networks enables the definition and fast deployment of novel network services called service chains: sequences of virtualized network functions (e.g., firewalls, caches, traffic optimizers) through which traffic is routed between source and destination. This paper attends to the problem of admitting and embedding a maximum number of service chains, i.e., a maximum number of source-destination pairs which are routed via a sequence of to-be-allocated, capacitated network functions. We consider an Online variant of this maximum Service Chain Embedding Problem, short OSCEP, where requests arrive over time, in a worst-case manner. Our main contribution is a deterministic O(log L)-competitive online algorithm, under the assumption that capacities are at least logarithmic in L. We show that this is asymptotically optimal within the class of deterministic and randomized online algorithms. We also explore lower bounds for offline approximation algorithms, and prove that the offline problem is APX-hard for unit capacities and small L > 2, and even Poly-APX-hard in general, when there is no bound on L. These approximation lower bounds may be of independent interest, as they also extend to other problems such as Virtual Circuit Routing. Finally, we present an exact algorithm based on 0-1 programming, implying that the general offline SCEP is in NP and by the above hardness results it is NP-complete for constant L.
قيم البحث
اقرأ أيضاً
One of the most important aspects of moving forward to the next generation networks like 5G/6G, is to enable network slicing in an efficient manner. The most challenging issues are the uncertainties in consumption and communication demand. Because th
e slices arrive to the network in different times and their lifespans vary, the solution should dynamically react to online slice requests. The joint problem of online admission control and resource allocation considering the energy consumption is formulated mathematically. It is based on Integer Linear Programming (ILP), where, the $Gamma$- Robustness concept is exploited to overcome Virtual Links (VL) bandwidths and Virtual Network Functions (VNF) workloads uncertainties. Then, an optimal algorithm that adopts this mathematical model is proposed. To overcome the high computational complexity of ILP which is NP-hard, a new heuristic algorithm is developed. The assessments results indicate that the efficiency of heuristic is vital in increasing the accepted requests count, decreasing power consumption and providing adjustable tolerance vs. the VNFs workloads and VLs traffics uncertainties, separately. Considering the acceptance ratio and power consumption that constitute the two important components of the objective function, heuristic has about 7% and 12% optimality gaps, respectively, while being about 30X faster than that of optimal algorithm.
Network Function Virtualization (NFV) on Software-Defined Networks (SDN) can effectively optimize the allocation of Virtual Network Functions (VNFs) and the routing of network flows simultaneously. Nevertheless, most previous studies on NFV focus on
unicast service chains and thereby are not scalable to support a large number of destinations in multicast. On the other hand, the allocation of VNFs has not been supported in the current SDN multicast routing algorithms. In this paper, therefore, we make the first attempt to tackle a new challenging problem for finding a service forest with multiple service trees, where each tree contains multiple VNFs required by each destination. Specifically, we formulate a new optimization, named Service Overlay Forest (SOF), to minimize the total cost of all allocated VNFs and all multicast trees in the forest. We design a new $3rho_{ST}$-approximation algorithm to solve the problem, where $rho_{ST}$ denotes the best approximation ratio of the Steiner Tree problem, and the distributed implementation of the algorithm is also presented. Simulation results on real networks for data centers manifest that the proposed algorithm outperforms the existing ones by over 25%. Moreover, the implementation of an experimental SDN with HP OpenFlow switches indicates that SOF can significantly improve the QoE of the Youtube service.
Control of wireless multihop networks, while simultaneously meeting end-to-end mean delay requirements of different flows is a challenging problem. Additionally, distributed computation of control parameters adds to the complexity. Using the notion o
f discrete review used in fluid control of networks, a distributed algorithm is proposed for control of multihop wireless networks with interference constraints. The algorithm meets end-to-end mean delay requirements by solving an optimization problem at review instants. The optimization incorporates delay requirements as weights in the function being maximized. The weights are dynamic and vary depending on queue length information. The optimization is done in a distributed manner using an incremental gradient ascent algorithm. The stability of the network under the proposed policy is analytically studied and the policy is shown to be throughput optimal.
The emerging paradigm of network function virtualization advocates deploying virtualized network functions (VNF) on standard virtualization platforms for significant cost reduction and management flexibility. There have been system designs for managi
ng dynamic deployment and scaling of VNF service chains within one cloud data center. Many real-world network services involve geo-distributed service chains, with prominent examples of mobile core networks and IMSs (IP Multimedia Subsystems). Virtualizing these service chains requires efficient coordination of VNF deployment across different geo-distributed data centers over time, calling for new management system design. This paper designs a dynamic scaling system for geo-distributed VNF service chains, using the case of an IMS. IMSs are widely used subsystems for delivering multimedia services among mobile users in a 3G/4G network, whose virtualization has been broadly advocated in the industry for reducing cost, improving network usage efficiency and enabling dynamic network topology reconfiguration for performance optimization. Our scaling system design caters to key control-plane and data-plane service chains in an IMS, combining proactive and reactive approaches for timely, cost-effective scaling of the service chains. We evaluate our system design using real-world experiments on both emulated platforms and geo-distributed clouds.
Recently, much effort has been devoted by researchers from both academia and industry to develop novel congestion control methods. LearningCC is presented in this letter, in which the congestion control problem is solved by reinforce learning approac
h. Instead of adjusting the congestion window with fixed policy, there are serval options for an endpoint to choose. To predict the best option is a hard task. Each option is mapped as an arm of a bandit machine. The endpoint can learn to determine the optimal choice through trial and error method. Experiments are performed on ns3 platform to verify the effectiveness of LearningCC by comparing with other benchmark algorithms. Results indicate it can achieve lower transmission delay than loss based algorithms. Especially, we found LearningCC makes significant improvement in link suffering from random loss.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
