LOGO
实验室博士生张启夏、姜炜祥、姚鹏程,硕士生艾明、汪涛、金琰祺的论文被IEEE ICDCS 2017录用
时间:2017-03-17 09:18:46

实验室博士生张启夏、姜炜祥、姚鹏程,硕士生艾明、汪涛、金琰祺的论文被IEEE ICDCS 2017录用

 

国际学术会议The 37th IEEE International Conference on Distributed Computing Systems (ICDCS 2017)录用结果揭晓,实验室有6篇论文被录用,分别是:博士生张启夏的论文“Joint Optimization of Chain Placement and Request Scheduling for Network Function Virtualization”、姜炜祥的论文“Virtual Machine Power Accounting with Shapley Value”、姚鹏程的论文“Towards Dataflow-based Graph Accelerator”,硕士生艾明的论文“Distributively Computing Random Walk Betweenness Centrality in Linear Time”、汪涛的论文“Multi-Resource Load Balancing for Virtual Network Functions”、金琰祺的论文“Reducing Cellular Signaling Traffic for Heartbeat Messages via Energy-Efficient D2D Forwarding”。

 

张启夏的论文“Joint Optimization of Chain Placement and Request Scheduling for Network Function Virtualization”主要研究了网络功能虚拟化的服务链编排与请求调度问题。相比在固化而昂贵的专有硬件上执行网络功能(Network FunctionNF),新兴的网络功能虚拟化(Network Function VirtualizationNFV)使得网络运营商能够灵活地将多样化的网络功能部署在低成本的通用服务器中,这一优势使其成为工业界和学术界共同关注的新兴技术。通过这种新模式来实现特定网络服务的关键在于,如何将多种类型的虚拟化网络功能编排成“服务链”,以最小化服务链响应延迟并最大化服务链中各计算节点的平均资源利用率。具体而言,运营商首先需要将各种虚拟化网络功能在服务链中进行合理放置形成服务实例,进而需要将动态产生的应用服务请求高效调度分配至该服务链中的各个服务实例当中。针对该实际需求,论文运用理论严密的排队论和开放式杰克逊网络分析,首次揭示了:虚拟化网络功能服务链放置问题在本质上等价于NP难的变容装箱问题。进而,针对服务链放置与请求调度的联合优化问题,论文提出了一种基于优先级的权重算法来提高系统资源利用率,并辅以一种启发式算法来降低服务响应延迟。由实际数据驱动的仿真实验结果显示,论文提出的NFV联合优化算法比本领域最新的研究工作提高了24.9%的平均资源利用率,同时降低了19.9%的平均响应延迟,可在不同应用场景中有效提高系统性能。

 

姜炜祥的论文“Virtual Machine Power Accounting with Shapley Value”主要研究了云计算虚拟机的能耗计量问题。数据中心日益增长的能源消耗给云计算运营商带来了巨额的成本压力。为了达到成本与收益的合理平衡,一种可行的途径是根据数据中心众多用户的实际资源和能源消耗进行精准公平计费。然而,虚拟机作为云计算数据中心内物理资源的复用抽象和租用对象,一直以来无法通过硬件手段直接测量其精确能耗,而且租户虚拟机之间存在相互竞争物理资源而导致的不公平能耗现象。为了解决这种共享和竞争有限资源的问题,论文巧妙地通过博弈论将虚拟机能耗测量的复杂工程问题提炼并转化为简洁的成本分配问题,从而能够运用经济学中著名的非确定性夏普利值(Shapley Value)方法为数据中心中大量的动态虚拟机能耗实现公平高效的计量。针对经典非确定性夏普利值(Shapley Value)方法在大规模数据中心中复杂度极高的瓶颈,论文结合虚拟机各维度资源和实际系统因素设计了高效降维方法。通过真实系统平台搭建与测量,论文发现当前领域内传统的“资源-能耗”映射分配模型在虚拟机能耗估测时存在高达25.22%~46.15%的误差,而本文所提出的方法不但满足了博弈论中分配问题的四条公平性定理,而且相比于传统的“资源-能耗”映射分配方法减少了56%的虚拟机能耗估测误差。

 

姚鹏程的论文“Towards Dataflow-based Graph Accelerator”主要研究了图计算的核内性能问题。随着图规模的增大,许多专用图计算系统被提出以高效地对图进行处理和分析。现有研究表明,虽然专用图计算系统设计了高效的编程模型和图划分策略,他们的性能依旧受限于低效的内存子系统。为了提升内存子系统的性能,一些工作开始研究利用新型硬件或专用架构以从硬件层面优化图计算。然而基于深入的微结构性能分析,本文发现内存子系统只造成了图计算过程中52%的性能损耗,而剩下48%的性能损耗是由较低的核内性能(较低的指令级并行度和较高的分支预测失败率)导致的。其中,较低的指令级并行度是由于图计算复杂的依赖性和顺序语意,而较高的分支预测失败率则是由于图计算复杂的分支预测条件。针对图计算核内性能低的问题,本文提出利用数据流模型取代图计算中传统的控制流模型,并详细分析了数据流模型在提升图计算核内性能的优势。实际部署实验的结果表明,数据流模型至少可以提升图计算60%的指令级并行度并降低70%的分支预测开销。进而,为了降低当前CPU架构带来的限制(指令必须按原始顺序retire),本文提出了一个基于数据流模型的图计算加速器以充分地利用数据流模型较高的并行度。

 

艾明的论文“Distributively Computing Random Walk Betweenness Centrality in Linear Time”主要研究了图介数中心度的分布式计算问题。介数中心度(Betweenness Centrality)为图的重要性质,在网络分析领域受到了广泛关注。一个点的介数中心度越大,表明该点在不同团体间的重要性越高。它常被定义为经过该点的最短路径数与所有最短路径数之比(简称为最短路径介数中心度)。然而,最短路径介数中心度易受到网络拓扑变化影响。此外,研究还表明网络中信息传输不仅仅通过最短路径传播,还可以通过随机游走(Random Walk)传递消息。基于此定义了基于随机游走的介数中心度。一个点的随机游走介数中心度表示该点被所有其它点对间随机游走所访问的次数。顺序计算随机游走介数中心度需要O(n4)时间(n为图中节点的个数),显然不适用于大规模图。基于此,论文提出了一个时间复杂度为O(nlogn)的分布式随机近似算法,该算法能够以常数倍误差计算所有点的随机游走介数中心度。同时,该文还证明了精确求解随机游走介数中心度的下界为Ω(n/log n+D)D为图直径),表明论文提出的分布式算法达到了近似最优。

 

汪涛的论文“Multi-Resource Load Balancing for Virtual Network Functions”主要研究了网络功能虚拟化环境下的多维资源负载均衡问题。网络功能在确保云应用性能和安全性上有至关重要的作用。当前的网络功能虚拟化技术(NFV)使得网络管理者得以简便地将多样化的网络功能以轻量级的软件形式灵活部署到通用廉价的服务器上。然而,不同的网络功能在处理数据包时对不同类型的资源(包括CPU、主存、网络I/O等)占用程度各不相同,引发了远复杂于传统单资源负载均衡的多维度资源负载均衡问题,以及相应的多维资源任务调度方法的缺失。针对这一问题,论文提出了一种适配网络功能虚拟化环境的多维资源负载均衡算法。不同于传统的单资源负载调度方法,论文所提出的新算法首先通过感知优势资源负载(dominant resource,即当前服务器上消耗最高的资源)来“化繁为简”,从而将多维资源负载均衡问题简化为“给定资源需求下最小化每个服务器优势资源负载”的问题。进而,通过先进的交替方向乘子法(ADMM)将该问题进行分布式的并发高效求解。基于实际系统实验,证明该算法比传统方法具有更快的收敛速度和更好的负载均衡效果。

 

金琰祺的论文“Reducing Cellular Signaling Traffic for Heartbeat Messages via Energy-Efficient D2D Forwarding”研究实现了降低蜂窝网络信令风暴和移动设备能耗的“端到端”多设备智能互联通信(Device-to-DeviceD2D)系统和用例。即时通信类软件(例如微信、QQWhatsApp等)已经成为移动用户最常用的应用之一,而该类应用普遍需要在后台向服务器频繁发送心跳包以保持在线状态。论文通过实际测量发现,这种周期性发送的心跳包虽然所携带的数据量很小,但是由于移动设备(如智能手机)在传输时与基站之间需要频繁建立与释放通信信道,因此消耗了大量的信令资源,是造成运营商基站“信令风暴”痛点问题的重要因素之一。同时,这种频繁的小包传输也会导致移动设备频繁激活数据通信模块,从而也消耗了大量的移动设备电能。为了解决心跳包给运营商和移动设备带来的信令与电能的双重消耗,论文应用5G时代下“端到端”多设备智能互联通信(Device-to-DeviceD2D)技术开发了一种新型的群体心跳包互助转发系统,其基本思想是:首先,通过合理挑选和激励蜂窝网络中的部分移动设备作为转发者,并适时以高能效的D2D通信方式收集周围邻近的移动设备心跳包;然后,由转发者将收集到的心跳包进行统一批量发送,从而大幅减少蜂窝网络内众多移动设备的信令消耗。在转发时,该系统能够基于心跳包的周期和失效时间进行合理的传输调度,从而在满足延迟约束的条件下最小化基站信令和移动设备电能消耗。论文在安卓智能手机上实现了基于该系统的真实App,实测验证了该系统能够减少50%以上的信令消耗并节省高达36%的电能,同时探讨了该D2D方式下的安全性初步方案。

同时,实验室博士生汤载阳的文章”Selective Traffic Offloading On the Fly: a Machine Learning Approach”以及硕士生王娜的文章” Parallel Algorithms for Core Maintenance in Dynamic Graphs”也被ICDCS 2017录用为短文。

ICDCS是分布式计算与系统领域享有盛誉和重要影响力的顶级国际学术会议,本届ICDCS在全球531篇投稿中录用90篇论文,录用率仅约16.9%

 

通讯员: 吴未
 更多 更多 更多 更多