面向SD-DCN的OpenFlow分组转发能效联合优化模型

在软件定义网络(software-defined networking, SDN)中,OpenFlow交换机通常采用三态内容可寻址存储器(ternary content addressable memory, TCAM)存储流表,以支持快速通配查找.然而,TCAM采用并行查找方式,查找能耗高,因此有必要为OpenFlow交换机选择合适的TCAM容量,以平衡分组转发时延和能耗.针对软件定义数据中心网络(software-defined data center network, SD-DCN)这一典型应用场景,利用多优先级M/G/1排队模型刻画OpenFlow交换机的分组处理过程,进而建立OpenFlow分组转发时延模型.同时,基于网络流分布特性,建立TCAM流表命中率模型,以求解OpenFlow分组转发时延与TCAM容量的关系式.在此基础上,结合TCAM查找能耗,建立OpenFlow分组转发能效联合优化模型,并设计优化算法求解TCAM最优容量.实验结果表明：所提时延模型比现有模型更能准确刻画OpenFlow分组转发时延.同时,利用优化算法求解不同参数配置下的TCAM最优容量,为SD-DC...     

支持压缩和多下一跳查找的路由查找方案

TCAM(ternary content addressable memory)是目前流行的一种高速路由查找技术.TCAM具有查找速度快、操作简单的优点,但同时它也具有3个明显的缺点:成本高、功耗大和路由更新复杂.路由器为了实现负载平衡以及策略路由,在路由表中保存着相当数量的具有多个下一跳的路由表项.基于TCAM技术,提出一种支持多下一跳的高速路由查找方案.方案通过两级索引表实现了多下一跳路由的存储和快速访问.为了提高TCAM的更新效率,方案还提出了一个N子空间TCAM更新算法.该算法对目前实际网络中的路由表,可达到近似O(1)的更新复杂度.为了减少TCAM的成本和功耗,方案中还使用了有效的路由压缩技术.压缩技术基于Trie树结构,实现简单.应用压缩技术,对于实际网络中的路由表,可减少20%的路由.该查找方案可以很容易地应用到未来的IPv6网络中.     

基于TCAM的高效浮动关键词匹配算法

针对传统浮动关键词匹配算法功耗高和速率低的问题,提出一种基于三态内容寻址寄存器(TCAM)的高效匹配算法。该算法应用关键词分类数据结构,将关键词存储在不同的TCAM模块中,并只将疑似关键词送入TCAM中查找匹配,从而减少每次访问TCAM查找的表项数目,提高一个查询周期内待匹配报文的移动速度。仿真结果表明,与传统算法相比,该算法功耗较低、匹配速度较快。     

一种TCAM策略路由融合表项维护管理算法*

基于单次TCAM匹配完成策略路由查找的功能需求,针对尽量缩短TCAM离线更新时间的约束条件,设计了一种高效的TCAM表项融合及维护管理方案及算法,确保了系统功能的实现。测试表明应用效果较好。     

一种面向FPGA异构计算的高效能KV加速器

网络功能虚拟化等新兴应用的蓬勃发展对Key-Value查询的能效提出了更高要求。传统的解决方法要么采用基于软件Hash表,要么采用专用的三态内容可寻址存储器(TCAM)芯片进行加速。其中,软件方法实现成本低,但是在数据冲突较高时会导致查表性能急速下降;硬件TCAM方法具有优良的时间特性,但其价格昂贵、耗能巨大。目前,随着基于现场可编程门阵列FPGA的异构计算技术的高速发展,利用系统已经提供的FPGA资源对基于软件实现的Hash表结构进行加速成为一种性价比更佳的解决方案。探讨如何利用FPGA上的RAM资源来实现一种具有高扩展性和高能效比的TCAM逻辑。与传统的TCAM结构不同,提出的架构支持查表范围的动态缩放,从而可以有效减少查表功耗。为了验证方案的有效性,利用Virtex-7系列FPGA对本文方案进行实现和评估,并与软件查表的性能进行详细比较。实验表明,本文方案吞吐量可达到234 Mpps,查表延迟为25.56ns。相比软件的方法,吞吐量提高780倍,延迟降低240倍。     

采用集合切分编码的大容量模式匹配算法*

针对现有模式匹配算法无法实现大容量模式集快速搜索的不足,提出了一种基于TCAM多字节状态机的模式匹配算法。利用TCAM的掩码特性,切分具有相同匹配字符串的状态集,提出了一种编号编码压缩机制。通过理论证明,集合切分编码利用状态机的已匹配信息,将编号存储改变为编号段存储,大幅压缩了具有相同转移字符串和目的状态的交叉转移路径,减少TCAM表项数目。经理论分析和实验仿真,该算法不仅具有高搜索速率,而且可以减少大量相似表项,降低TCAM存储资源消耗,从而支持大容量的模式集。     

兼容IPv4和IPv6的高速路由设计

提出一种兼容IPv4和IPv6报文高速路由查找方案，方案基于TCAM技术，同时对TCAM路由表更新算法进行比较，最后采用松散前缀顺序约束算法实现TCAM路由表的更新，并在网络处理器原型设计中得到应用。方案可以满足10Gbps速率IP报文线速转发的要求。     

基于TCAM的二级转发表管理方案

目前高性能路由器的查找方案采用基于三重内容可寻址存储器(TCAM)的硬件查找。路由查找的最长前缀匹配要求使得TCAM的表项更新复杂。该文针对当前转发表管理方案在带突发情况下的不足,提出一种基于TCAM二级转发表管理方案,并对该方案进行了计算机仿真研究,仿真结果表明该方案在突发的情况下仍能保证转发系统稳定工作。     

基于Trie树分割路由表降低TCAM功耗的方法

TCAM已成为在路由器设计中实现路由查找的硬件方案,具有速度快、实现简单的优点,但其功耗较高.该文提出了一种基于trie树的结构进行路由表分割、降低TCAM功耗的方法,同传统的TCAM相比,前缀数量达到200时降低大约80%的功耗,前缀数量越多,相对降低的比例越大.     

ISCP-TCAM :一种低功耗高速路由查找引擎结构

提出一种高速、低功耗路由查找引擎结构ISCP TCAM(ImprovedStage ControlPipeline TernaryContentAddressableMemory),这种结构不但具有传统内容可寻址寄存器(TCAM)管理简单、 更新容易、查找快速等优点,而且功耗要比同等容量的TCAM小得多。同时为进一步评估其性能利 用ALTERA公司的逻辑可编程门阵列(FPGA)实现了这一结构。该结构在低功耗高速路由查找引擎 的设计中是一个较好的选择。     

面向云计算的期限约束的MapReduce作业调度方法

提出一种面向异构云计算环境的截止时间约束的MapReduce作业调度方法。使用加权偶图建模MapReduce作业调度问题,将Map任务及Reduce任务与资源槽分为2个节点集合,连接2个节点集合的边的权重为任务在资源槽上的执行时间。进而,使用整数线性规划求解最小加权偶图匹配,从而得到任务到资源槽的调度方案。本文考虑了云计算环境下异构节点任务处理时间的差异性,在线动态评估和调整任务的截止时间,从而提升了MapReduce作业处理的性能。实验结果表明,所提出的方法缩短了作业数据访问的时间,最小化了截止时间冲突的作业数量。     

On-line maintenance job scheduling and assignment to resources in distributed systems by heuristic-based optimization

A heuristic-based optimization algorithm is proposed in this paper for on-line scheduling and assignment of preventive maintenance jobs to processors, to minimize under availability constraints, on a given time-window, the total cost of the maintenance operations of a distributed system. This algorithm minimizes the cost of discharge of preventive maintenance tasks or jobs, while assigning the tasks along with balancing the processors load. It is shown that the problem is NP-hard. To solve it, the concept of job emergency is introduced and the priority rule for total flow time (PRTF) criterion is used in an adapted heuristic job-scheduling model. In addition, the algorithm considers the constraints of precedence among consecutive standby jobs and their emergency. It is depicted the specific properties of the proposed heuristic allowing jobs scheduling in the right order. Computational results illustrate the efficiency of the approach implemented on different system configurations.     

一种保持OpenFlow功能完整性的TCAM流表压缩模型

随着OpenFlow协议版本的不断更新,其在数据平面上细粒度的控制能力得到了很大提升。然而,由于表项匹配域支持的任意通配符依赖TCAM进行匹配处理,随着OpenFlow匹配域支持字段的增加,设备中的TCAM存储空间面临很大压力。为此,提出一种减小TCAM中流表存储空间的数学模型FICO(A Function-Integral TCAM-saving Compression model for flow table of OpenFlow)。FICO首先根据匹配域不同字段间的关系,将字段之间的冗余分为三种。然后基于冗余提出三种预压缩算法,分别为域间字段合并、字段映射、域内字段压缩,最终组合为更小位宽的表项被送往TCAM中进行流匹配。通过仿真表明在保持OpenFlow功能完整性的前提下,较未压缩流表,FICO可以节省60%TCAM存储空间。并且随着流表规模的增大,压缩性能保持稳定。     

Preemptive cloud resource allocation modeling of processing jobs

Cloud computing allows execution and deployment of different types of applications such as interactive databases or web-based services which require distinctive types of resources. These applications lease cloud resources for a considerably long period and usually occupy various resources to maintain a high quality of service (QoS) factor. On the other hand, general big data batch processing workloads are less QoS-sensitive and require massively parallel cloud resources for short period. Despite the elasticity feature of cloud computing, fine-scale characteristics of cloud-based applications may cause temporal low resource utilization in the cloud computing systems, while process-intensive highly utilized workload suffers from performance issues. Therefore, ability of utilization efficient scheduling of heterogeneous workload is one challenging issue for cloud owners. In this paper, addressing the heterogeneity issue impact on low utilization of cloud computing system, conjunct resource allocation scheme of cloud applications and processing jobs is presented to enhance the cloud utilization. The main idea behind this paper is to apply processing jobs and cloud applications jointly in a preemptive way. However, utilization efficient resource allocation requires exact modeling of workloads. So, first, a novel methodology to model the processing jobs and other cloud applications is proposed. Such jobs are modeled as a collection of parallel and sequential tasks in a Markovian process. This enables us to analyze and calculate the efficient resources required to serve the tasks. The next step makes use of the proposed model to develop a preemptive scheduling algorithm for the processing jobs in order to improve resource utilization and its associated costs in the cloud computing system. Accordingly, a preemption-based resource allocation architecture is proposed to effectively and efficiently utilize the idle reserved resources for the processing jobs in the cloud paradigms. Then, performance metrics such as service time for the processing jobs are investigated. The accuracy of the proposed analytical model and scheduling analysis is verified through simulations and experimental results. The simulation and experimental results also shed light on the achievable QoS level for the preemptively allocated processing jobs.     

面向MapReduce计算的大规模集群通信优化

为了优化大规模集群运行MapReduce作业时的通信效率和减少shuffle数据传输量,首先采用存储局部性换取通信局部性的策略建立一个分布式协同数据映射模型;其次通过随机抽样和机器学习方法来提取作业数据的局部性特征,实现map计算数据的有效部署;最后,利用软件定义网络的全局灵活控制能力,优选通信链路好的节点并将计算任务映射到该类节点中。实验表明对于中间数据混洗密集类作业有较好的优化效果,通信延迟降低了4.3%~5.8%。该方案能减少shuffle流量和数据迁移延迟,并且适合各种调度策略和网络拓扑结构。     

基于决策树映射的低功耗TCAM包分类方案

为了实现网络流的线速转发,高性能交换机普遍采用三态内容寻址存储器(TCAM)来构建其包分类引擎。针对TCAM功耗高的问题,近年来出现了许多低功耗索引方案,实现了TCAM存储块的选择性激活以降低功耗,但这些索引方案普遍采用自底向上的局部优化算法来构建,无法有效实现流表规则的均匀划分,严重影响了TCAM的存储效率及功耗降低效果。提出并实现了一种基于决策树映射的TCAM低功耗索引方案,在极大降低功耗的同时提升了TCAM的存储效率。利用规则普遍存在的小域特征,将原始规则集划分为若干个规则子集,然后针对各个子集的特征域,采用自顶向下的方式分别构建平衡决策树,最后通过对各个决策树进行贪心遍历,从而得到TCAM索引列表。实验表明,针对规模为十万条的规则集,算法在仅使用额外1.3%存储空间开销的同时实现了98.2%的功耗降低。     

Power-efficient TCAMs for bursty access patterns

Ternary content addressable memories (TCAM) have become a popular hardware device for fast routing-table lookups. However, the high power consumption in TCAM increases power supply and cooling costs, and limits the router design to fewer ports. Based on an analysis of the prefix hierarchy in routing tables, the authors propose an optimization model to reduce the power consumption for bursty access patterns. This model can reduce the average power consumption by a factor of 11.     

全局EDZL实时调度算法的可调度性判定

可调度性判定就是离线验证实时系统中所有任务是否可调度。通过可调度性判定,能够更好地保证实时系统的可靠性。有多种分析方法可用于可调度性判定,得到的结果有所不同。通过分析在多处理器实时系统中全局EDZL算法的任务需求,考虑带入作业和带出作业对处理器资源的需求。引入最大连续忙区间的概念,以确定带入作业的最大个数,得到了多处理器实时系统中全局EDZL算法的可调度性判定算法。实验结果说明了这种方法提高了通过可调度性判定的任务数量,是一种更紧密的可调度性判断方法。     

Power efficient packet classification using cascaded bloom filter and off-the-shelf ternary CAM for WDM networks

In wavelength division multiplexing (WDM) networks, tens or hundreds of wavelengths can be transmitted over a single fiber. As transmission line speed goes to 10 Gb/s and beyond, ternary CAM (TCAM) is usually employed for wire speed packet classification. To the best of authors’ knowledge, this is the first paper that addresses the impact of WDM transmission on the power consumption of packet classification. We show that as the number of wavelengths increases in the WDM networks, the power consumption of TCAMs can become the limiting factor for WDM network expansion. For example, the power consumption of IPv4 and IPv6 packet classification with merely 32 channels at 40 Gb/s can be as high as 700 and 1400 W, respectively, while technology wise it is feasible to transmit over 500 channels over a single fiber. Existing power efficient TCAM designs require special modification to TCAM cell structures, which makes the adoption of the technology difficult. This paper proposes a novel approach which cascades bloom filter with off-the-shelf TCAM to greatly reduce the power consumption of packet classification. In particular, the proposed solution takes advantage of the fact that bloom filters may give false positive alarms but never give false negative alarms. By eliminating majority of non-matching packets before passing the packets to the TCAM, the TCAM is only activated to exam packets with a high potential of matching in the filter set. The proposed scheme greatly reduces the activation frequency of the TCAM, thus achieving great power savings.