检索结果-内蒙古大学图书馆

Congestion Minimization for Service Chain Routing Problems With Path Length Considerations

IEEE-ACM TRANSACTIONS ON NETWORKING 2020年第6期28卷 2643-2656页

作者： Gao, Lingnan Rouskas, George N. North Carolina State Univ Dept Comp Sci Raleigh NC 27695 USA North Carolina State Univ Raleigh NC 27695 USA King Abdulaziz Univ Dept Comp Sci Jeddah 21589 Saudi Arabia

Network function virtualization (NFV), with its perceived potential to accelerate service deployment and to introduce flexibility in service provisioning, has drawn a growing interest from industry and academia alike over the past few years. One of the key challenges in realizing NFV is the service chain routing problem, whereby traffic must be routed so as to traverse the various components of a network service that have been mapped onto the underlying network. In this work, we consider the online service chain routing problem. We route the service chain with the goal of jointly minimizing the maximum network congestion and the number of hops from the source to the destination. To this end, we present a simple yet effective online algorithm in which the routing decision is irrevocably made without prior knowledge of future requests. We prove that our algorithm is O(log m)-competitive in terms of congestion minimization, where m is the number of edges of the underlying network topology, and we show that this ratio is asymptotically optimal.

关键词： Routing Heuristic algorithms Minimization Network function virtualization Resource management IEEE transactions Noise measurement Network function virtualization virtual network functions NFV orchestration online algorithm resource allocation

来源：评论

学校读者我要写书评

暂无评论

Mini-batch learning of exponential family finite mixture models

引用

STATISTICS AND COMPUTING 2020年第4期30卷 731-748页

作者： Nguyen, Hien D. Forbes, Florence McLachlan, Geoffrey J. La Trobe Univ Dept Math & Stat Melbourne Vic Australia Univ Grenoble Alpes LJK Grenoble INP CNRSINRIA F-38000 Grenoble France Univ Grenoble Alpes Inst Engn Grenoble France Univ Queensland Sch Math & Phys Brisbane Qld Australia

Mini-batch algorithms have become increasingly popular due to the requirement for solving optimization problems, based on large-scale data sets. Using an existing online expectation-maximization (EM) algorithm framework, we demonstrate how mini-batch (MB) algorithms may be constructed, and propose a scheme for the stochastic stabilization of the constructed mini-batch algorithms. Theoretical results regarding the convergence of the mini-batch EM algorithms are presented. We then demonstrate how the mini-batch framework may be applied to conduct maximum likelihood (ML) estimation of mixtures of exponential family distributions, with emphasis on ML estimation for mixtures of normal distributions. Via a simulation study, we demonstrate that the mini-batch algorithm for mixtures of normal distributions can outperform the standard EM algorithm. Further evidence of the performance of the mini-batch framework is provided via an application to the famous MNIST data set.

关键词： Expectation-maximization algorithm Exponential family distributions Finite mixture models Mini-batch algorithm Normal mixture models online algorithm

来源：评论

学校读者我要写书评

暂无评论

online packet scheduling with bounded delay and lookahead

引用

THEORETICAL COMPUTER SCIENCE 2019年 776卷 95-113页

作者： Boehm, Martin Chrobak, Marek Jez, Lukasz Li, Fei Sgall, Jiri Vesely, Pavel Charles Univ Prague Comp Sci Inst Prague Czech Republic Univ Bremen Bremen Germany Univ Calif Riverside Dept Comp Sci & Engn Riverside CA 92521 USA Univ Wroclaw Inst Comp Sci Wroclaw Poland George Mason Univ Dept Comp Sci Fairfax VA 22030 USA Univ Warwick Dept Comp Sci Coventry W Midlands England

We study the online bounded delay packet scheduling problem (PacketScheduling), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature;yet currently the best published upper bound is 1.828 [8], still quite far from the best lower bound of phi approximate to 1.618 [11,2,6]. In the variant of PacketScheduling with s-bounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of phi applies even to the special case of 2-bounded instances, and a phi-competitive algorithm for 3-bounded instances was given in [5]. Improving that result, and addressing a question posed by Goldwasser [9], we present a phi-competitive algorithm for 4 bounded instances. We also study a variant of PacketScheduling where an online algorithm has the additional power of 1- lookahead, knowing at time t which packets will arrive at time t + 1. For PacketScheduling with 1-lookahead restricted to 2-bounded instances, we present an online algorithm with competitive ratio 1/2 (root 13-1) approximate to 1.303 and we prove a nearly tight lower bound of 1/4 (1 + root 17) approximate to 1.281. In fact, our lower bound result is more general: using only 2-bounded instances, for any integer l >= 0 we prove a lower bound of 1/2(l+1) (1+root 5+8l+4l(2)) for online algorithms with l-lookahead, i.e., algorithms that at time t can see all packets arriving by time t + l. Finally, for non-restricted instances we show a lower bound of 1.25 for randomized algorithms with l-lookahead, for any l >= 0. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Buffer management online scheduling online algorithm Lookahead

来源：评论

学校读者我要写书评

暂无评论

Mobile coupons delivery problem: Postponable online multi-constraint knapsack

引用

DECISION SUPPORT SYSTEMS 2019年 116卷 13-25页

作者： Kang, Keumseok Altinkemer, Kemal Hur, Inkyoung Florida Int Univ Coll Business Miami FL 33199 USA Purdue Univ Krannert Sch Management W Lafayette IN 47907 USA Nova Southeastern Univ Coll Engn & Comp Ft Lauderdale FL 33314 USA

We study the mobile coupons delivery problem (MCDP) in a push-based location based advertisement where an advertiser proactively sends mobile coupons to prospective customers on behalf of stores based on the customers' location and preferences. MCDP provides a new capability called postponable selection that enables an advertiser to better capitalize on the plethora of customer information provided by mobile phone users through network service providers. Postponable selection allows a customer to be reconsidered for selection for coupon delivery (i.e. postponed) as more information becomes available. We formulate MCDP as a new problem category referred to as the postponable online multi-constraint knapsack. We propose a single threshold-type algorithm with different design options and conduct extensive computational experiments to discuss the effectiveness of our algorithm as well as the benefit of postponable selection. Our experimental results show that the proposed algorithm outperforms the First-Come-First-Serve heuristic by 46% and postponable selection additionally improves performance by 4% on average.

关键词： Mobile coupons delivery problem online multi-constraint knapsack problem online algorithm Postponable selection Computational experiment

来源：评论

学校读者我要写书评

暂无评论

online Parallel-Batch Machines Scheduling with a Single Server

引用

Chinese Quarterly Journal of Mathematics 2022年第4期37卷 403-411页

作者： FU Ru-yan LIN Lin School of Mathematics China University of Mining and TechnologyXuzhou 221116China Institute of Technology and Standards Research China Academy of Information and Communication TechnologyBeijing 100191China Key Laboratory of Internet of Vehicle Technical Innovation and Testing(CAICT) Ministry of Industry and Information TechnologyBeijing 100191China

We consider parallel-batch machines scheduling problem with a single server to minimize the maximum completion *** arrive over *** batch has to be loaded by the sever before being processed on *** loading(setup)operation of a batch occurs only when some machine is idle,and the server can perform only one setup operation every *** some special case,we provide a best possible online algorithm with competitive ratio■.For general case,we give another online algorithm with competitive ratio 3.

关键词： Parallel-batch machines Server online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Q-SR: An extensible optimization framework for segment routing

引用

COMPUTER NETWORKS 2021年 200卷 108517-108517页

作者： Zhang, Jianwei Zhao, Chenwei Zhejiang Univ City Coll Sch Comp & Comp Sci 51 Huzhou St Hangzhou 310015 Zhejiang Peoples R China Zhejiang Univ Coll Comp Sci & Technol 38 Zheda Rd Hangzhou 310027 Zhejiang Peoples R China

Segment routing (SR) combines the advantages of source routing powered by software-defined networking (SDN) paradigm and hop-by-hop routing in legacy network infrastructure. The recent applications of SR in multi-domain network and service function chaining (SFC) entail the efficient use of multiple segments. However, because of the computation inefficiency, it is nearly impossible to accurately evaluate whether and to what extent various types of networks will benefit from SR with multiple segments using conventional approaches. In this paper, we propose a flexible Q-SR framework as well as its formulation in order to fully explore the potential of SR from an algorithmic perspective. The framework is highly extensible to design and evaluate algorithms that can be adapted to various network topologies and traffic matrices. For the offline setting, we develop a fully polynomial time approximation scheme (FPTAS) which can find a (1 +w) approximation solution for any specified w > 0 in time that is a polynomial function of the network size. To the best of our knowledge, the proposed FPTAS is the first algorithm that can compute arbitrarily accurate solution. For the online setting, we develop an online primal-dual algorithm that is proven to be O(1)-competitive and violates link capacities by a factor of O(logn), where n is the node number of the network. For the proposed approximation algorithms, we prove theoretical performance bounds and conduct extensive simulations on synthetic and realistic networks to analyze SR related and algorithmic parameters and validate the computation efficiency in both offline and online scenarios.

关键词： Segment routing (SR) Traffic engineering (TE) Approximation algorithm online algorithm Software-defined networking (SDN)

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Packet Scheduling

Online Algorithms for Packet Scheduling

引用

作者： Veselý, Pavel Charles University of Prague

We study online scheduling policies for buffer management models, in which packets are arriving over time to a buffer of a network switch to be sent through its single output port. However, the bandwidth of the port is limited and some packets need to be dropped, based on their weights. The goal of the scheduler is to maximize the weighted throughput, that is, the total weight of packets transmitted. Due to the natural lack of information about future, an optimal performance cannot be achieved, we thus pursue competitive analysis and its refinements to analyze online algorithms on worst-case inputs. Specifically, in the first part of the thesis, we focus on a simple online scheduling model with unit-size packets and deadlines, called Bounded-Delay Packet Scheduling. We design an optimal φ-competitive deterministic algo- rithm for the problem, where φ ≈ 1.618 is the golden ratio. It is based on a detailed understanding of an optimal schedule of pending packets, called the plan, which may be of independent interest. We also propose a semi-online setting with lookahead that allows the algorithm to see a little bit of future, namely, packets arriving in the next few steps. We provide an algorithm with lookahead for instances in which each packet can be scheduled in at most two consecutive slots and prove lower...

关键词： online algorithm competitive analysis online scheduling buffer management resource augmentation

来源：评论

学校读者我要写书评

暂无评论

Joint online Coflow Routing and Scheduling in Data Center Networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2019年第5期27卷 1771-1786页

作者： Tan, Haisheng Jiang, Shaofeng H. -C. Li, Yupeng Li, Xiang-Yang Zhang, Chenzi Han, Zhenhua Lau, Francis Chi Moon USTC Coll Comp Sci & Technol Hefei 230027 Anhui Peoples R China Weizmann Inst Sci Fac Math & Comp Sci IL-76100 Rehovot Israel Univ Toronto Dept Elect & Comp Engn Toronto ON M5S 1A1 Canada Univ Hong Kong HKU Dept Comp Sci Hong Kong Peoples R China Jinan Univ Dept Comp Sci Guangzhou 510632 Guangdong Peoples R China

A coflow is a collection of related parallel flows that occur typically between two stages of a multi-stage computing task in a network, such as shuffle flows in MapReduce. The coflow abstraction allows applications to convey their semantics to the network so that application-level requirements can be better satisfied. In this paper, we study the routing and scheduling of multiple coflows to minimize the total weighted coflow completion time (CCT). We first propose a rounding-based randomized approximation algorithm, called OneCoflow, for single coflow routing and scheduling. The multiple coflow problem is more challenging as coexisting coflows will compete for the same network resources, such as link bandwidth. To minimize the total weighted CCT, we derive an online multiple coflow routing and scheduling algorithm, called OMCoflow. We then derive a competitive ratio bound of our problem and prove that the competitive ratio of OMCoflow is nearly tight. To the best of our knowledge, this is the first online algorithm with theoretical performance guarantees which considers routing and scheduling simultaneously for multi-coflows. Compared with existing methods, OMCoflow runs more efficiently and avoids frequently rerouting the flows. Extensive simulations on a Facebook data trace show that OMCoflow outperforms the state-of-the-art heuristic schemes significantly (e.g., reducing the total weighted CCT by up to 41.8% and the execution time by up to 99.2% against RAPIER).

关键词： Coflow datacenter networks online algorithm

来源：评论

学校读者我要写书评

暂无评论

online Energy Management in Microgids Considering Reactive Power

引用

IEEE INTERNET OF THINGS JOURNAL 2019年第2期6卷 2895-2906页

作者： Zou, Hualei Wang, Yu Mao, Shiwen Zhang, Fanghua Chen, Xin Nanjing Univ Aeronaut & Astronaut Dept Elect Engn Nanjing 210016 Jiangsu Peoples R China Auburn Univ Dept Elect & Comp Engn Auburn AL 36849 USA

The optimal power energy scheduling of a microgrid (MG) is not only related to the active power of distributed generators but also dependent on the reactive power and system operational constraints. It is essential to manage the active and reactive power simultaneously in optimal energy distribution. This paper is focused on developing an online algorithm to optimize the real-time power energy distribution in the MG, considering both reactive power and system operational constraints. The goal is to provide high quality electricity usage for users in the MG and maximize users' utility. The output power of controllable generators are also optimized. The proposed online algorithm is asymptotically optimal, since its solution converges to the offline optimal solution. The effectiveness of the proposed algorithm is validated using data traces obtained from a real-world MG.

关键词： Averaging fixed horizon control (AFHC) energy management system (EMS) online algorithm power quality smart grid

来源：评论

学校读者我要写书评

暂无评论

online detection of abnormal passenger out-flow in urban metro system

引用

NEUROCOMPUTING 2019年 359卷 327-340页

作者： Wang, Haiyang Li, Longyuan Pan, Pingjun Wang, Yongkun Jin, Yaohui Shanghai Jiao Tong Univ State Key Lab Adv Opt Commun Syst & Network Shanghai Peoples R China AI Inst MoE Key Lab Artificial Intelligence Shanghai Peoples R China Shanghai Jiao Tong Univ China Inst Urban Governance Shanghai Peoples R China

Accurate forecasting of the number of passengers coming into the urban metro system, namely, passenger in-flow has been one of the most important issues in the research on the intelligent transportation system. Existing studies aim at making the prediction mainly by learning the recurring patterns from historical passenger in-flows. However, passenger out-flows from the urban metro system, which may usually contribute to understanding passenger behavior, and help forecast passenger in-flows, especially burst in-flows on unusual conditions, have rarely been studied yet. In this paper, we propose a model called EAD-OF (Elastic Abnormality Detection for Out-flow) to real-time detect the abnormal passenger out-flows and alarm the administrators in time. Furthermore, we analyze the characteristics of passenger in-flow, out-flow and their correlation. We evaluate our model with real transportation data of the biggest city in China and use large-scale social event data to further explain our model. The result shows that EAD-OF can effectively detect the abnormal out-flows which would cause burst in-flows with performance tens of times better than the baseline models. In term of efficiency, EAD-OF can also beat the direct computation approach several times. (C) 2019 Published by Elsevier B.V.

关键词： Anomaly detection online algorithm Intelligent transportation system Big data mining Urban computing

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：