基于分组处理能力共享的低功耗路由器体系结构
开毅, 卢建元, 刘斌
清华大学 计算机科学与技术系, 北京 100084
刘斌,教授, E-mail:liub@tsinghua.edu.cn

作者简介: 开毅(1984-), 男(汉), 北京, 博士研究生。

摘要

为了解决目前互联网中核心路由器功耗大并且功耗效率低的问题,提出了一种基于处理能力共享的路由器体系结构GreenRouter。该结构将路由器线卡拆分为分组处理部分(母板)和接口部分(子板), 通过两级交换网络的互连使所有子板共享各母板的分组处理能力。调度算法将路由器各接口到达的流量分配到最小数目的处于工作状态的母板上,关闭其他母板实现节能。研究了GreenRouter的体系结构和运行机制中的关键问题,利用实际网络流量进行的模拟实验表明: GreenRouter在保证网络服务质量的前提下,能够节省超过40%的功耗。

关键词: 计算机网络; 路由器; 低功耗设计
中图分类号:TP393 文献标志码:A 文章编号:1000-0054(2014)04-0485-05
Architecture of a power-efficient router based on the sharing of packet processing capacities
Yi KAI, Jianyuan LU, Bin LIU
Department of Computer Science and Technology, Tsinghua University, Beijing 10084, China
Abstract

Modern core routers in the Internet consume much power due to inefficiencies. This paper presents a power-efficient router architecture named GreenRouter, which is based on the sharing of packet processing capacities. GreenRouter separates every line-card into a network interface card and a packet processing card. All cards in the router are connected by a two-stage switch fabric. The traffic from all the network interface cards shares all the packet processing cards and the traffic can be aggregated into a few active packet processing cards on demand while others are shut down to save power. The key issues of the GreenRouter's architecture are described. Real trace evaluations show that GreenRouter can save up to 40% of the power consumed while guaranteeing the quality of service (QoS) constraints.

Keyword: computer network; router; low power design

近年来互联网流量呈现出指数级增长,这对网络设备的性能需求日益加强,使得核心路由器的功耗不断加大。例如,思科公司的CRS-1路由器系统[1], 在最大配置下功率可达1 MW。高性能路由器的功耗越来越大,会带来电力传输、机房散热等一系列问题,已成为互联网运营商关注的焦点。

另一方面,当前互联网中骨干链路的最大平均利用率仅有40% 甚至更低[2]。并且互联网流量存在潮汐效应,即白天的网络流量明显的高于夜间。但是以前传统路由器设计的首要指标是满足网络节点的最大负载需求,并未考虑能耗效率问题,导致现有核心路由器的能耗效率较低。

在目前针对路由器节能的研究中[3,4], 自适应频率调整[5,6]和器件电压适配[7]是芯片级节能中最常用的两种技术,然而受制于路由器线卡在最低频率和电压下依然有很大的基础功耗的影响,该类方法所降低的功耗有限。另一类节能方法是创造机会休眠线卡或器件。这类方法又分为有、无网络协作两种应用情形。其中,对于没有网络协作的休眠[8], 由于骨干网中很少存在完全没有流量的机会,因此节能效果并不明显。对于网络协作下的休眠[9], 设计机制在保证QoS的同时将网络流量集中到尽可能少的链路中去,从而创造机会休眠链路和对应的线卡,以达到节能目的。但此方法受制于网络的拓扑结构和网络自治域、服务商之间的连接策略,能耗效率虽然优于无网络协作方法但依然不高。

本文提出了一种新的路由器体系结构GreenRouter。它与现有节能机制的重要区别在于通过改变路由器体系结构来达到节省功耗的目的,在更宏观的层面上提高节省功耗的效果。本文给出了GreenRouter的体系结构及其运行机制的设计方案,并进行了分析和实验仿真。结果表明: GreenRouter能够自动适配流量的变化,在保证QoS的前提下取得了很好的节能效果。

1 GreenRouter设计

根据文[3]的研究结果,在核心路由器中,分组处理(包括路由查找等)的功耗占比最大,达到整个数据平面功耗的71%。与之相比,网络接口和交换网络的功耗占比仅分别为14%和15%。在路由器的体系结构设计中若能针对这一现象进行优化,则有机会创造出很大的节能空间。

1.1 基本思想和示例

传统路由器中,线卡从功能上由网络接口和分组处理两部分组成。网络接口与网络链路连接,用于数据的封装、传输等; 分组处理包括进行路由查找、流分类等操作。两者是绑定的,即某网络接口到达的流量由固定的分组处理模块去处理。而在GreenRouter中,两者的绑定关系被解除,拆开后分别称为子板和母板。这为所有母板的分组处理能力被整个路由器的流量所共享创造了条件。

图1为GreenRouter的示例。假设一个5端口的路由器运行在负载较低的情况下。图1a的传统路由器中, 由于分组处理和网络接口的绑定关系,各分组处理模块都要保持工作状态。而图1b的GreenRouter中,可以将各接口的流量聚合到两块母板中,关闭其他三块母板达到节能的目的。

图1 传统路由器和GreenRouter工作原理示意图

在一些早期的边缘级小型路由器中,也出现过接口共享处理能力的结构。这是因为其性能要求很低,单个处理模块就能满足整个路由器的需求,与本文针对高速路由器的节能有本质区别。

1.2 GreenRouter的体系结构

在GreenRouter体系结构设计中存在两个主要的技术问题: 1) 设计合适的互连方法,使得所有子板全范围的共享所有母板; 2) 设计有效的调度算法,在保证QoS的前提下使尽可能少的母板处于加电工作的状态。

本文采用了两级交换网络来解决上述第一个问题。图2a的传统路由器中,每个线卡内的接口模块和分组处理模块是一个整体,线卡之间通过交换网络实现互连。线卡从其网络接口收到一个分组后,对该分组进行路由查找等操作。根据路由查找结果,将分组经由交换网络传输到目标端口所在的线卡上,最终发送到网络中去。

图2 传统路由器与GreenRouter的对比

而在图2b的GreenRouter中,母板与子板之间通过两级交换网络相连。分别记为第一级交换网络和第二级交换网络。当分组到达子板的网络接口后,子板对分组进行识别、成帧等操作后,送往对应的分发器。分发器是新增的子板内的关键部件,决定子板到达的流量如何分配给各母板。通过第一级交换网络,分组被送往选定的母板。母板对分组进行路由查找、流分类等处理后通过第二级交换网络送往目标端口所在的子板,并最终发送到网络中去。

图2可以看出,在体系结构上GreenRouter与传统路由器相比有2个主要的区别:

1) 分发器。GreenRouter中设计了分布式的分发器系统,每个子板有自己局部的分发器,每个分发器共享一些全局的状态信息,如工作中的母板数和各母板的实时负载等,但各自独立运行;

2) 交换网络: GreenRouter需要额外的1级交换网络。GreenRouter中两级交换网络的区别在于,第一级中,根据分发器的负载分配决策来进行交换; 第二级中,根据路由查找的结果即目标网络接口的位置进行交换。

尽管GreenRouter比传统路由器多使用了1级交换网络并增加了分发器,但是它们的功耗并不大。由节1可知,交换网络的功耗占比很小。而分发器仅实现简单的调度,并且不进行存储等操作,功耗也非常小,本文中暂且忽略。理论分析和模拟实验均表明,与GreenRouter取得的节能效果相比,增加的功耗代价是可接受的。同时,从较长的时间周期(如一天或一周)来看, GreenRouter存在更大的节能机会。即使某一段时间内路由器峰值负载很高,但现实网络中较低的平均负载和网络流量的潮汐效应使得GreenRouter的节能空间相当大,能够抵消额外功耗带来的影响。

2 GreenRouter的运行机制

GreenRouter的设计目标在于最小化路由器的功耗,并保证QoS的关键性能。其基本思路是通过仅开启当前网络负载所需的母板并关闭其他的母板来节省功耗。因此,当负载上升时,应当开启部分关闭的母板来保证路由器性能,避免分组丢失; 当负载下降时,应当合并流量来产生空闲的母板,并关闭它们来最大化节能。

因为有别于传统路由器的结构, GreenRouter运行机制中有2点需要特别考虑的:

1) 负载分配: 负载分配是指将各端口到达的流量分配给开启的母板,需要保证负载均衡和负载适度集中。负载均衡有利于改善QoS性能,而负载集中到尽可能少的母板中有利于节能效率的提高。

2) 流保序: 互联网中很多应用以流为粒度,流保序也是TCP重要的QoS性能之一。但是GreenRouter的结构有可能会使同一个流内的分组被不同的母板处理,带来潜在的乱序可能。

针对以上两点,本文为GreenRouter设计了一个基于流的调度机制。对每个流尽可能固定一个母板来处理从而保证流保序; 通过对新流的分配来实现负载分配的目标,即负载均衡和负载聚合。

2.1 分发器的设计

图3为分发器的工作流程。在分发器中,使用了Hash表来储存流的状态和对应母板的信息。使用Hash表而非完整流表是因为在核心路由器中流的数目非常大(数百万)[10], 这会导致实现完整流表的代价过大。表项中,“目标母板”是指正在处理当前表项中的流的母板,“流状态”则是指表项中流的状态是新流或活动流。本文定义活动流为有分组在路由器中等待被处理或正在被处理的流。

对于在同一个Hash表项中的那些流,在后续处理中可认为是同一个流。首先,多个流聚合后的流若能保证不乱序,则单个的流不会乱序; 其次,文[11]指出,核心路由器中活动流的数目很小,仅为数百个,因此合适的Hash表大小可以保证很小概率的Hash冲突。

分发器的工作流程如下:

1) 分组到达后,利用分组头部中的五元组在Hash表中进行查找,然后从Hash表中读取对应的表项;

2) 如果为活动流,若对应的目标母板并未满负荷工作,则直接将该分组分配给对应的目标母板;

3) 如果为活动流,但对应目标母板已经处于满负荷状态,则将该流重新分配,可能带来乱序;

4) 如果为新流,则根据各母板的负载状态,以不同的概率随机选择一个开启的母板作为目标母板用来处理该分组;

5) 更新Hash表,包括目标母板、流状态等。

2.2 新流的判断和分配

对每个Hash表项,利用一个计时器来判断流的状态。当一个表项内长时间无分组到达时,则认为该表项内后续到达的分组属于一个新流。值得注意的是,对于同一个Hash表项内连续到达的两个分组,如果它们之间的时间间隔大于母板处理分组所需的最大时间,则即使这两个分组事实上属于同一个流,但若将此后的分组都视为一个新流,分配去往其他的母板,也不会带来乱序的问题。核心路由器中,同时存在的流的数量级为百万个,而正在被处理的活动流的数目仅为几百或几千个。因此通过以母板处理分组所需的最大时间为计时器触发条件,在保证不乱序的前提下,可以产生更多的“新流”,有助于调度的灵活性。

新流的分配则是实现负载聚合和负载均衡的关键。新流被随机分配给运行状态的母板,分配的概率由母板的负载状态所决定。采用随机分配则是为了避免分布在各子板上的分发器同时集中地向同一个母板发送分组。本文将母板分为重载、轻载和中等负载三种状态。

1) 对于重载的母板,需要预留一定的处理能力以应对正在被该母板处理的各流的负载波动,避免将活动流的后续分组分配给其他母板从而产生乱序,因此,对其应尽量少地分配新流或不分配新流;

2) 对于轻载的母板,当路由器负载下降时,这些母板的负载应当进一步降低直至完全空闲以创造关闭的条件,因此对其也尽量少地分配新流;

3) 中等负载的母板是新流分配的主要目标,这样可使得它们负载上升变为重载母板。因此,除随时可能关闭的轻载母板外,其他处于工作状态的母板都会趋向于重载,从而达到动态的负载均衡。

2.3 乱序的控制

对于一个母板,当其中正在处理的负载出现波动而突然持续增加时,有可能超过该母板的处理和缓存能力。

这种情况出现后,本文中选择将流的后续分组调度到其他母板来处理,这就会带来乱序的风险。通过控制重载母板的负载,预留一定的处理能力(如5%), 并在母板入口处增加一个容量很小的缓存,可以将乱序率控制在很好的水平(小于10-8)。仿真实验的结果验证了这一点。这是由于,每个母板处理的流的数目很大,达到数十万甚至百万。尽管其中的一些流可能会出现负载突然增长的情况,但同时有很多流突发的概率非常小,整个母板所处理的流聚合起来的负载大幅度持续增长的概率非常小。

3 节能效率分析

GreenRouter的节能来自于被关闭的母板,而关闭的母板数是随着网络负载的变化而动态变化的。同时,增加的1级交换网络和分发器需要增加部分功耗,是GreenRouter为节能所付出的代价。

根据文[12]的研究,不同负载下网络设备消耗的功耗基本相同。据此可假设相同的模块在传统路由器和GreenRouter中消耗相同的功耗。令 N表示总共的母板数, M表示关闭的母板数, PG PT分别是GreenRouter和传统路由器数据平面消耗的功耗, Plinecard Pswitch PDB PMB分别表示单个线卡、交换网络、子板和母板的功耗则可得:

PT=NPlinecard+Pswitch=N(PMB+PDB)+Pswitch,PG=NPDB+(1-M)PMB+2Pswitch.1

又根据文[3]的研究,核心路由器中数据平面的各模块的功耗占比分别为: 交换网络占15%, 分组处理部分(母板)占71%, 接口部分(母板)占14%。可得到GreenRouter和传统路由器之间功耗的关系为

PG(ρ)=1-71%×M(ρ)N+15%PT(ρ).(2)

其中ρ表示路由器的负载。由式(2)可知, GreenRouter的节能效率与开启的母板的数目(或被关闭母板的数目)直接相关。因此,只需在仿真实验中得到开启的母板数,即可推算出GreenRouter的节能效率。

4 仿真结果

为了验证GreenRouter的性能和节能效率,本文进行了2种类型的仿真实验,分别为基于分组的仿真和基于吞吐率的仿真。

基于分组的仿真是指以分组为粒度,模拟GreenRouter的运行过程,验证其功能和性能。本文观察了开启的母板数的变化情况,并根据数学建模的结果来估算节能的效率; 同时验证了QoS性能能否满足要求,包括乱序率和额外的排队时延。本文采用了分别来自芝加哥、圣何塞和CERNET的网络原始数据。这些数据均截取自OC-192的链路,时间均为1 h。

基于吞吐率的仿真是指观察网络吞吐量在较长周期(如一天或一周)内的变化对GreenRouter节能效率的影响。根据对路由器吞吐率采样的结果,推算各采样时刻的开启的母板数并以此计算节能效率。本文采用了清华大学校园网内某骨干路由器吞吐率采样数据,时间为一周。

基于分组的仿真结果显示, GreenRouter中开启的母板数能够自适应负载的波动。图4是芝加哥数据的仿真结果。可以看出, GreenRouter能够及时对开启的母板数进行调整,在保证性能的同时尽量节能。

图4 开启的母板数随负载变化图

基于分组的仿真结果同时表明,在选取合适的缓存大小(用分组数表示)后,乱序率可控制在10-8以下(见图5), 符合QoS要求。合适的缓存大小是指缓存带来的额外时延足够小,满足QoS限制。仿真过程表明: 由于GreenRouter不会分配新流给重载母板,因此缓存的利用率较低,超过90%的分组不会被缓存而直接进入母板。而被缓存的分组中,最大额外时延仅为40 us, 符合QoS要求。

图5 缓存大小对乱序率的影响

图6则展示了基于吞吐率的仿真结果。可以看出,网络流量有明显的潮汐效应,即在白天时较高而在夜晚尤其是深夜时很低。在此情况下, GreenRouter的节能效率更加明显。图6中该链路一周内的最大负载为27.2%, 平均负载为16.23%, 而GreenRouter在数据平面的功耗消耗仅为传统路由器的56.12%, 即GreenRouter可节能43.88%。

图6 一周流量变化和节能效果图

5 结 论

本文设计了一种新的路由器体系结构GreenRouter, 在保证性能和QoS的基础上实现了很大幅度的节能。有别于其他器件级、芯片级或电路级节能, GreenRouter的节能是针对整个路由器体系结构的优化。本文研究了GreenRouter的体系结构、运行机制等关键问题,并给出了初步的仿真结果。下一步将对GreenRouter中各功能模块进行细化分析,挖掘更大的节能空间,并进一步完善GreenRouter的数学模型。

The authors have declared that no competing interests exist.

参考文献
[1] Epps G, Tsiang D, Boures T. System power challenges [R]. www.cisco.com/web/about/ac50/ac207/proceedings/POWER_GEPPS_rev3.ppt. [本文引用:1]
[2] Yamada M, Yazaki T, Matsuyama N, et al. Power efficient approach and performance control for routers [C]// Proc IEEE International Conference Communications. Dresden, Germany: IEEE, 2009: 1-5. [本文引用:1]
[3] Bolla R, Bruschi R, Davoli F, et al. Energy efficiency in the future internet: A survey of existing approaches and trends in energy-aware fixed network infrastructures [J]. Communications Surveys Tutorials, 2011: 223-244. [本文引用:1] [JCR: 6.49]
[4] Gelenbe E, Morfopoulou C. A framework for energy-aware routing in packet networks[J]. The Computer Journal, 2011, 54(6): 850-859. [本文引用:1]
[5] Gunaratne C, Christensen K, Nordman B, et al. Reducing the energy consumption of ethernet with adaptive link rate (alr)[J]. IEEE Transactions on Computers, 2008, 57: 448-461. [本文引用:1] [JCR: 1.473]
[6] Nedevschi S, Popa L, Iannaccone G, et al. Reducing network energy consumption via sleeping and rate-adaptation [C]// Proc 5th USENIX Symp. on Networked Systems Design and Implementation (NSDI'08), San Francisco, CA: USENIX, 2008: 323-336. [本文引用:1]
[7] Mandviwalla M, Tzeng N F. Energy-Efficient Scheme for Multiprocessor-Based Router Linecards [C]// Proc International Symp on Applications on Internet. Turku, Finland: IEEE, 2008: 156-163. [本文引用:1]
[8] Reviriego P, Maestro J, Hernández J, et al. Burst transmission for energy efficient Ethernet[J]. IEEE Internet Computing, 2010, 14: 50-57. [本文引用:1] [JCR: 2.0]
[9] ZHANG Mingui, YI Cheng, LIU Bin, et al. Greente: Power-aware traffic engineering [C]// Proc 18th IEEE Conf Network Protocols, Kyoto: IEEE, 2010: 21-30. [本文引用:1]
[10] SHI Lei, LI Wenjie, LIU Bin. Flow based packet mode load balancing for parallel packet switches[J]. High Speed Networks, 2010, 17: 97-128. [本文引用:1] [JCR: 0.379]
[11] HU Chengchen, CHEN Kai, TANG Yi, et al. Dynamic Queuing Sharing Mechanism for Per-flow QoS Control[J]. IET Communications, 2010, 4(4): 472-483. [本文引用:1] [JCR: 0.72]
[12] Adelin A, Owezarski P, Gayraud T. On the impact of monitoring router energy consumption for greening the Internet [C]// Proc 11th IEEE/ACM International Conference on Grid Computer. Brussels, Belgium: IEEE/ACM, 2010: 298-304. [本文引用:1]