类脑处理器异步片上网络架构

杨智杰; 王蕾; 石伟; 彭凌辉; 王耀; 徐炜遐

doi:10.7544/issn1000-1239.202111032

类脑处理器异步片上网络架构

国防科技大学计算机学院　长沙　410073

基金项目: 国家重点研发计划项目（2018YFB2202603，2020AAA0104602）

详细信息

作者简介:
杨智杰: 1995年生.博士研究生.主要研究方向为类脑计算和计算机架构

王蕾: 1977年生.博士，副研究员.CCF高级会员.主要研究方向为微处理器设计和类脑计算

石伟: 1982年生.博士，副研究员.主要研究方向为计算机架构、微处理器设计和信息安全

彭凌辉: 1997年生.工程师.主要研究方向为类脑计算和片上网络设计

王耀: 1983年生.博士，助理研究员.主要研究方向为超大规模集成电路、微处理器设计与实现和半导体器件性质与可靠性

徐炜遐: 1963年生.博士，研究员，博士生导师.CCF会员.主要研究方向为高性能计算机系统结构

通讯作者:
王蕾（leiwang@nudt.edu.cn）

中图分类号: TP389.1
计量
- 文章访问数: 330
- HTML全文浏览量: 37
- PDF下载量: 193
出版历程
- 收稿日期: 2021-10-17
- 修回日期: 2022-06-06
- 网络出版日期: 2023-02-10
- 刊出日期: 2022-12-31

Asynchronous Network-on-Chip Architecture for Neuromorphic Processor

College of Computer Science and Technology, National University of Defense Technology, Changsha 410073

Funds: This work was supported by the National Key Research and Development Programs of China (2018YFB2202603, 2020AAA0104602).

摘要

摘要:
类脑处理器较深度学习处理器具有能效优势.类脑处理器的片上互连一般采用具有可扩展性高、吞吐量高和通用性高等特点的片上网络.为了解决采用同步片上网络面临的全局时钟树时序难以收敛的问题以及采用异步片上网络面临的链路延迟匹配、缺乏电子设计自动化工具实现和验证的问题，提出了一种异步片上网络架构——NosralC，用于构建全局异步局部同步（global asynchronous local synchronous， GALS）的多核类脑处理器. NosralC采用异步链路和同步路由器实现.实验表明，NosralC较同步基线，在4个类脑应用数据集下展现出37.5%~38.9%的功耗降低、5.5%~8.0%的平均延迟降低和36.7%~47.6%的能效提升，同时增加不多于6%的额外资源以及带来较小的性能开销（吞吐量降低0.8%~2.4%）. NosralC在现场可编程门阵列（FPGA）上得到了验证，证明了该架构的可实现性.
- 类脑处理器 /
- 片上网络 /
- 异步电路 /
- 全局异步局部同步 /
- 脉冲神经网络
Abstract:
Neuromorphic processors show extremely high energy efficiency advantages over traditional deep learning processors. The network-on-chip with high scalability, high throughput, and high versatility features is generally adopted as the on-chip communication and connection implementation of neuromorphic processors. In order to solve the problems of making the synchronous network-on-chip that adopts the global clock tree to achieve timing closure, matching link delay in the asynchronous network-on-chip, and lacking electronic design automation tools in implementation and verification of asynchronous network-on-chip, we propose a low-power asynchronous network-on-chip architecture, NosralC, to build a global-asynchronous-local-synchronous multi-core neuromorphic processor. NosralC is implemented with asynchronous links and synchronous routers. The small amount of asynchronous design makes NosralC similar to the synchronous design and friendly to implementation and validation of asynchronous design using existing electronic design automation tools. Experiments show that compared with a synchronous counterpart baseline with the same function, NosralC achieves 37.5%−38.9% reduction in power consumption, 5.5%−8.0% reduction in average latency, and 36.9%−47.6% improvement in energy efficiency in executing the FSDD, DVS128 Gesture, NTI-DIGITS, and NMNIST neuromorphic application datasets while increasing less than 6% additional resource overhead and a small amount of performance overhead (0.8%−2.4% throughput decrease). NosralC is verified on the field programmable gate array (FPGA) platform and its implementability is proved.
- neuromorphic processor /
- network-on-chip (NoC) /
- asynchronous circuit /
- global asynchronous local synchronous (GALS) /
- spiking neural network

HTML全文

软件定义网络（software-defined networking, SDN）作为一种新兴网络架构，将网络控制功能从数据交换设备中解耦出来，形成逻辑上集中的控制平面. SDN控制平面负责构建并维护全局网络视图，根据网络拓扑结构制定流规则，并通过以OpenFlow为代表的南向接口协议下发到数据交换设备中，从而实现灵活高效的数据传输. 基于OpenFlow的SDN技术有力地打破了传统网络的封闭和僵化问题，大大提升了网络的灵活性、可管控性和可编程能力，被普遍认为是未来网络最有发展前景的方向之一^[1-2]. 经过十来年的不断发展与演进，SDN技术已广泛应用于各种网络场景，尤其是数据中心网络. 软件定义数据中心网络（software-defined data center network, SD-DCN）显著简化了网络功能管理，降低了部署成本，提高了数据传输效率，优化了网络应用性能，为数据中心的优化部署提供了新的技术方案^[3-4].

数据中心作为承载海量数据处理的重要基础设施，广泛应用于在线购物、网络电视、短视频分享等数据密集型产业，目前已进入井喷式的高速建设和发展时期^[5]. 然而，在数据中心规模飞速扩张的同时，能耗问题已成为制约其可持续发展的瓶颈. 在数据中心能耗中，网络设备产生的能耗占比可达50%以上^[6]，主要由提供高速数据传输服务的交换机产生. 在SD-DCN网络中，OpenFlow交换机通常采用三态内容可寻址存储器（ternary content addressable memory, TCAM）存储流表以支持快速通配查找，其查找能耗高（15~30 W/Mbit）^[7-8]，约为静态存储器的50倍^[9]. 同时，SD-DCN网络采用等价多路径路由机制，将产生不少额外的流规则并存储到TCAM中，导致能耗问题更加凸显. 因此，如何设置OpenFlow交换机的TCAM容量，以平衡分组转发时延和TCAM查找能耗，是SD-DCN实际部署需要解决的一个关键问题.

目前已有不少研究工作关注OpenFlow交换机的TCAM能耗问题. 为降低TCAM查找能耗，部分研究人员采用内容可寻址存储器（CAM）缓存流表中的活跃流^[10-11]，进而直接转发大多数分组，以大幅度减少TCAM流表查找操作. 然而，CAM同样采用并行查找方式，查找能耗仍高. 也有研究者利用过滤器预测流表查找失败情形^[9]，减少不必要的TCAM查找操作，但只能过滤每条流的首个分组，节能效果极为有限. 还有研究人员关注OpenFlow交换机的TCAM流表优化模型^[12-13]，但却主要关注流超时设置、流规则放置等问题，缺乏对其最优容量的考量. 此外，许多工作关注OpenFlow交换机的分组转发时延，利用排队论构建OpenFlow分组转发性能模型^[14-15]，但却同样忽略了TCAM容量对分组转发时延的影响.

针对上述问题，本文面向SD-DCN网络场景，拟提出一种OpenFlow分组转发能效联合优化模型，以求解TCAM最优容量. 为此，本文首先描述了一个典型的SD-DCN网络部署场景，分析其分组转发过程和排队特性，构建OpenFlow分组转发时延模型. 然后，根据数据中心网络中的流分布特性，建立TCAM命中率模型，进而求解OpenFlow分组转发时延与TCAM容量的关系式. 进一步，结合TCAM查找能耗，建立OpenFlow分组转发能效联合优化模型，并设计对应的优化算法求解TCAM最优容量. 最后，通过模拟实验评估本文所提OpenFlow分组转发时延模型，并利用优化算法求解不同参数配置下的TCAM最优容量.

本文的主要贡献有4个方面：

1）针对SD-DCN网络典型部署场景，在分析其分组到达和处理过程的基础上，为OpenFlow交换机构建了多优先级M/G/1排队模型，进而建立了一种更准确的OpenFlow分组转发时延模型；

2）基于SD-DCN网络中的流量分布特性，为OpenFlow交换机建立了TCAM命中率模型，以求解OpenFlow分组转发时延与TCAM容量的关系式；

3）以分组转发时延和能耗为优化目标，建立OpenFlow分组转发能效联合优化模型；

4）证明了优化目标函数的凸性质，进而设计了优化算法求解TCAM最优容量，为SD-DCN实际部署提供有效指导.

1. 相关工作

针对OpenFlow交换机的TCAM能耗问题，部分研究人员设计了TCAM流表节能查找方案. Congdon等人^[10]根据网络流量局部性，为交换机的每个端口设置CAM缓存，存储包签名与流关键字之间的映射关系，以预测包分类结果，使大部分分组绕过TCAM查找过程. 然而，CAM存储器同样采用并行查找方式，查找能耗仍高. 针对OpenFlow多流表的流水线查找模式，Wang等人^[11]利用马尔可夫模型选取每个流表中的活跃表项，并集中存放到流水线前的Pop表中，使大部分分组查找命中Pop表，以避免复杂的多流表查找过程. Kao等人^[9]提出了基于布鲁姆过滤器的流表查找方案TSA-BF，通过优化设计布鲁姆过滤器以预测流表查找失败情形，使新流分组绕过TCAM失败查找操作. 但该方案只能过滤每条流的首个分组，节能效果极为有限.

同时，许多研究工作利用排队论建立OpenFlow分组转发时延模型. 针对OpenFlow交换机的分组处理过程和SDN控制器的Packet-in消息处理过程，Xiong等人^[14]将其分别建模为M^X/M/1和M/G/1排队模型，Abbou等人^[15]则分别建模成M/H₂/1排队模型和M/M/1排队模型，Chilwan和Jiang^[16]分别建模成M/M/1/∞和M/M/1/K排队模型，进而推导OpenFlow平均分组转发时延. 针对多控制器部署场景，Zhao等人^[17]为SDN控制器集群和OpenFlow交换机分别建立M/M/n和M/G/1排队模型，分析平均分组转发时延，并结合SDN控制器集群的部署成本，求解最优控制器数量. 然而，文献[14-17]所述模型未考虑不同类型网络分组的优先级差异. 对此，Rahouti等人^[18]将SDN网络建模成带反馈机制的双队列排队系统，将分组划分成多个优先级队列，以提供差异化的QoS服务. Li等人^[19]为OpenFlow虚拟交换机的分组转发过程建立排队系统，以分析丢包率、流表查找失败概率、分组转发时延等关键性能指标，进而利用多线程处理、优先制队列设置、分组调度策略和内部缓存区设置等多种方法优化分组转发性能. 然而，文献[18-19]所述模型均未考虑TCAM容量对OpenFlow分组转发时延的影响.

进一步，已有部分研究工作关注OpenFlow交换机的TCAM流表优化模型. Metter等人^[20-21]建立基于M/M/∞排队系统的流表解析模型，分析不同网络流量特性下流超时时长对Packet-in发送消息速率和流表占用率的影响. 进一步，AlGhadhban等人^[12]为流安装过程建立基于类生灭过程的解析模型，分析流表匹配概率的影响因素，进而推导不同流超时时长下的流表容量. Zhang等人^[13]采用M/G/c/c排队系统分析流超时时长对流规则的截断时间、冗余时间和安装失败率的影响，进而提出自适应流超时算法，以提高TCAM流表资源利用率. 然而，文献[12-13, 20-21]所述模型未考虑TCAM容量优化设置问题. 对此，Shen等人^[22]将流表项生命周期划分为Packet-in消息发送、控制器处理和流表项超时3个阶段，并分别建立M/M/1，M/M/1和M/G/c/c排队模型，进而提出流表空间估计模型，求解流安装失败概率约束下的TCAM最小容量. 然而，该工作仅关注TCAM容量对流安装成功率的影响，却没有考虑流表命中率和分组转发时延等关键性能指标. 本文则考虑TCAM容量对分组转发时延和能耗的影响，建立OpenFlow分组转发能效联合优化模型，求解TCAM最优容量，为SD-DCN实际部署提供参考依据.

2. 面向SD-DCN的OpenFlow分组转发时延模型

本节在描述SD-DCN网络典型部署场景的基础上，为OpenFlow交换机的分组处理过程构建多优先级M/G/1排队模型，进而建立OpenFlow分组转发时延模型.

2.1 SD-DCN

随着在线购物、网络电视、视频分享、搜索引擎等数据密集型应用的日益盛行，数据中心作为承载海量数据处理的重要基础设施，其规模不断扩大，网络通信量正快速增长^[23]. 传统数据中心网络因扩展性差、缺乏灵活的管理，无法满足数据处理业务中日益增长的网络需求. 基于OpenFlow的SDN技术将控制逻辑与数据转发相解耦，进而对网络设备进行逻辑上集中的管理和控制，并为上层应用提供统一的编程接口，大大提升了网络的灵活性、开放性和可管控能力，为构建高性能数据中心网络提供了新的解决思路. SD-DCN具备动态路由控制、服务质量管理、安全智能连接等技术优势，降低了数据中心网络的部署成本，有助于构建更加灵活高效的数据中心，已成为一种新的发展趋势^[24].

图1描述了一种典型的SD-DCN网络架构，分为基础设施平面、数据平面、控制平面和应用平面. 基础设施平面包含众多服务器，提供强大的存储和计算能力. 数据平面大多采用fat-tree拓扑结构组网^[25-26]，交换机自下而上分为边缘交换机、汇聚交换机和核心交换机，为众多服务器提供高性能的网络互联和数据传输服务. 在数据平面中，每个交换机根据控制平面下发的流规则，快速转发网络分组. 控制平面根据上层应用需求，基于全局网络视图制定流规则，并通过以OpenFlow为代表的南向接口协议下发到各个交换机中，指导分组转发行为. 应用平面基于控制平面提供的北向接口，实现服务编排、安全控制、QoS管理、资源调度等功能.

图 1 SD-DCN网络架构

Figure 1. Network architecture of SD-DCN

下载: 全尺寸图片幻灯片

在图1所示的SD-DCN网络场景中，OpenFlow交换机根据SDN控制器制定的流规则转发分组. 对于每个到达的分组，交换机从分组首部提取匹配字段，进而查找流表. 若查找成功，则依据流表项中给定的动作集转发分组. 否则，交换机判定该分组属于新流，将其首部信息或整个分组封装成流安装请求发送到控制器. 控制器根据全局网络视图生成流规则，并下发到流传输路径上的各个交换机中. 交换机将流规则安装至流表，并据此转发该流后续到达的分组.

2.2 OpenFlow交换机排队模型

在SD-DCN数据平面中，来自服务器的大量分组汇聚到OpenFlow交换机，形成队列等待处理. OpenFlow交换机的分组排队和处理过程如图2所示. 对于到达的每个分组，交换机首先将其缓存到入端口队列，然后逐个解析分组首部信息，提取关键字段，以计算流标识符. 再根据流标识符查找OpenFlow流表，以定位对应的流表项. 若查找成功，交换机在ACL应用、计数器更新等一系列相互独立的操作后，将分组发送到出端口等待转发；若查找失败，交换机发送Packet-in消息给控制器，待收到相应的Flow-mod消息后，将其中的流规则安装到TCAM流表，并据此转发该流后续到达的分组. 控制器下发的Flow-mod消息同样以分组的形式到达交换机，但优先级高于数据分组，以保证分组转发行为的一致性和高效性.

图 2 OpenFlow交换机的分组排队和处理过程

Figure 2. The queueing and processing of packet in the OpenFlow switch

下载: 全尺寸图片幻灯片

网络测量结果表明：在数据中心等大规模网络场景下，流量汇聚程度高，并发流数量庞大，趋于相互独立^[27-28]. 因此，OpenFlow交换机的分组到达过程和流到达过程均可视为泊松过程^[17,22]. 在OpenFlow分组转发过程中，所有新流的首个分组在Open-Flow交换机中的处理步骤相同，且处理过程相互独立. 根据Burke定理^[29]，交换机发送的Packet-in消息流仍为泊松流. 假设每台交换机发送的Packet-in消息流相互独立，根据泊松流的可加性，汇聚到控制器的Packet-in消息流可叠加为泊松流. 控制器为每个Packet-in消息独立生成流规则后，以Flow-mod消息的形式下发至流路径上的各个交换机. 因此，OpenFlow交换机的Flow-mod消息到达过程同样为泊松过程. 假定控制器收到交换机S_k发送的Packet-in消息后，生成流规则并下发Flow-mod消息给交换机S_i的概率为δ_ik，则有δ_ii=1. 若交换机S_k的Packet-in消息发送速率为 $\lambda _k^{({\text{in}})}$ ，控制器共管理K台交换机，则交换机S_i的Flow-mod消息到达速率如式（1）所示：

$\lambda _i^{({\text{m}})} = \displaystyle\sum\limits_{k{\text{ = }}1}^K {{\delta _{ik}}\lambda _k^{({\text{in}})}} .$

(1)

OpenFlow交换机的分组处理过程可分解为首部解析、流表查找、计数器更新等相互独立的步骤，不妨假设其共有M步. 假设交换机S_i中第j(1 $\leqslant$ j $\leqslant$ M)步的处理时间T_ij服从速率为μ_ij的负指数分布，则其均值E(T_ij)=1/μ_ij，方差D(T_ij)=1/ ${\mu_{ij}^2}$ . 由于每个步骤相互独立，因此交换机S_i的分组处理时间T_i服从一般分布，其均值E(T_i)如式（2）所示：

$E({T_i}) = \displaystyle\sum\limits_{j = 1}^M {E({T_{ij}}) = } \displaystyle\sum\limits_{j = 1}^M {\frac{1}{{{\mu _{ij}}}}} .$

(2)

因此，交换机S_i的平均分组处理速率 $\mu _i^{({\text{s}})}$ 和分组处理时间方差 $\sigma _i^{{{({\text{s}})}^2}}$ 分别如式（3）（4）所示：

$\mu _i^{({\text{s}})} = \frac{1}{{E({T_i})}} = \frac{1}{{\displaystyle\sum_{j = 1}^M {{1 \mathord{\left/ {\vphantom {1 {{\mu _{ij}}}}} \right. } {{\mu _{ij}}}}} }},$

(3)

$\sigma _i^{{{({\text{s}})}^2}} = D({T_i}) = \sum\limits_{j = 1}^M {D({T_{ij}}) = } \sum\limits_{j = 1}^M {\frac{1}{{\mu _{ij}^2}}} .$

(4)

基于以上排队分析，本文将OpenFlow交换机的分组处理过程建模为多优先级M/G/1排队模型：1）交换机S_i的Flow-mod消息和分组到达过程为泊松过程，到达速率分别为 $\lambda _i^{\left( {\rm{m}} \right)}$ 和 $\lambda _i^{( {\rm{p}})}$ ；2） OpenFlow交换机的入端口有Flow-mod消息高优先级队列和分组低优先级队列，按非抢占式多优先级调度策略依次处理；3）交换机S_i的分组处理时间服从一般分布，分组处理速率和分组处理时间方差，分别如式（3）（4）所示. 根据排队论，可计算出Flow-mod消息和分组在交换机中的平均逗留时间为 $W_i^{({\text{m}})}$ 和 $W_i^{({\text{p}})}$ ，分别如式（5）（6）所示：

$W_i^{({\text{m}})} = \frac{{\rho _i^{({\text{s}})}\bar R_i^{({\text{s}})}}}{{1{{ - }}\rho _i^{({\text{m}})}}} + \frac{1}{{\mu _i^{({\text{s}})}}},$

(5)

$W_i^{({\text{p}})} = \frac{{\rho _i^{({\text{s}})}\bar R_i^{({\text{s}})}}}{{\left( {1{{ - }}\rho _i^{({\text{m}})}} \right)\left( {1 - \rho _i^{({\text{m}})} - \rho _i^{({\text{p}})}} \right)}} + \frac{1}{{\mu _i^{({\text{s}})}}}.$

(6)

其中 $\rho _i^{({\text{s}})} = {{(\lambda _i^{({\text{m}})} + \lambda _i^{({\text{p}})})} \mathord{\left/ {\vphantom {{(\lambda _i^{({\text{m}})} + \lambda _i^{({\text{p}})})} {\mu _i^{({\text{s}})}}}} \right. } {\mu _i^{({\text{s}})}}}$ ， $\rho _i^{({\text{m}})} = {{\lambda _i^{({\text{m}})}} \mathord{\left/ {\vphantom {{\lambda _i^{({\text{m}})}} {\mu _i^{({\text{s}})}}}} \right. } {\mu _i^{({\text{s}})}}}$ ， $\rho _i^{({\text{p}})} = {{\lambda _i^{({\text{p}})}} \mathord{\left/ {\vphantom {{\lambda _i^{({\text{p}})}} {\mu _i^{({\text{s}})}}}} \right. } {\mu _i^{({\text{s}})}}}$ ， $\bar R_i^{({\text{s}})}$ 为交换机处理分组时的剩余服务时间均值，如式（7）所示：

$\bar R_i^{({\text{s}})} = \frac{{E(T_i^2)}}{{2E({T_i})}} = \frac{{\sigma _i^{{{({\text{s}})}^2}} + {1 \mathord{\left/ {\vphantom {1 {\mu _i^{{{({\text{s}})}^2}}}}} \right. } {\mu _i^{{{({\text{s}})}^2}}}}}}{{{2 \mathord{\left/ {\vphantom {2 {\mu _i^{({\text{s}})}}}} \right. } {\mu _i^{({\text{s}})}}}}}.$

(7)

2.3 OpenFlow分组转发时延模型

根据SD-DCN网络中的分组转发流程，结合2.2节所述的OpenFlow交换机排队模型，可建立OpenFlow分组转发排队系统如图3所示. 在图3中，网络分组以速率 $\lambda _i^{({\text{p}})}$ 到达OpenFlow交换机S_i，在入端口处排队等待处理. 交换机S_i依据TCAM流表以速率 ${\mu _i^{({\text{s}})}}$ 逐个处理分组. 假定TCAM流表命中率为h_i，则交换机S_i以速率 $\lambda _i^{({\text{in}})} = \lambda _i^{({\text{p}})}(1 - {h_i})$ 发送Packet-in消息到SDN控制器. 控制器接收其管理的所有交换机发送的Packet-in消息流，并统一存入队列等候处理. 控制器的Packet-in消息到达速率为 ${\lambda ^{({\text{c}})}} = \displaystyle\sum_{i = 1}^K {\lambda _i^{({\text{p}})}(1 - {h_i})}$ ，处理速率为 $\mu^{({\rm{c}})}$ . 控制器为每个Packet-in消息生成流规则后，以速率 $\lambda _i^{({\text{m}})} = \displaystyle\sum_{k = 1}^K {{\delta _{ik}}\lambda _k^{({\text{p}})}(1 - {h_k})}$ 下发Flow-mod消息到交换机S_i. 交换机将所有流规则依次安装到流表，进而转发新流的分组.

图 3 OpenFlow分组转发排队系统

Figure 3. OpenFlow-based packet forwarding queueing system

下载: 全尺寸图片幻灯片

在上述OpenFlow分组转发排队系统中，到达控制器的Packet-in消息流相互独立，其到达过程为泊松过程，且控制器对每个Packet-in消息的处理过程相互独立，处理时间可视为服从负指数分布^[30-31]. 因此，可将控制器的Packet-in消息处理过程建模为M/M/1排队模型，进而可知Packet-in消息在控制器中的平均逗留时间W^（c）如式（8）所示：

${W^{({\text{c}})}} = \frac{1}{{{\mu ^{({\text{c}})}} - {\lambda ^{({\text{c}})}}}}.$

(8)

根据上述OpenFlow交换机的分组处理排队模型和控制器的Packet-in消息处理排队模型，可推导出交换机S_i的平均分组转发时延. 根据OpenFlow分组转发过程可知，交换机S_i中的分组转发过程可分为2种情况：直接转发和请求控制器安装流规则的间接转发. 分组直接转发时延即为分组在交换机中的逗留时间 $W_i^{({\text{p}})}$ . 分组间接转发时延包含分组在交换机中的逗留时间 $W_i^{({\text{p}})}$ 、Packet-in消息在控制器中的逗留时间 $W^{({\text{c}})}$ 、Flow-mod消息在交换机中的逗留时间 $W_i^{({\text{m}})}$ ，以及Packet-in消息和Flow-mod消息在交换机到控制器之间的总传输时延 $W_i^{({\text{t}})}$ . 因此，交换机S_i的平均分组转发时延可表达如式（9）所示：

${D}_{i}=\left\{\begin{array}{ll}{W}_{i}^{(\text{p})}, & 概率为{h}_{i}. \\ {W}_{i}^{(\text{p})}+{W}_{i}^{(\text{m})}+{W}_{i}{}^{(\text{t})}+{W}^{(\text{c})}, & 概率为\left(1-{h}_{i}\right)\text{.} \end{array}\right.$

(9)

将式（5）（6）（8）代入式（9）可得，交换机S_i的平均分组转发时延D_i如式（10）所示：

$\begin{split} {D_i} =& {h_i}W_i^{({\text{p}})} + \left( {1 - {h_i}} \right)\left( {W_i^{({\text{m}})} + W_i^{({\text{p}})} + W_i^{({\text{t}})} + {W^{({\text{c}})}}} \right) =\\ &\frac{{\rho _i^{({\text{s}})}\bar R_i^{({\text{s}})}}}{{\left( {1- \rho _i^{({\text{m}})}} \right)\left( {1 - \rho _i^{({\text{m}})} - \rho _i^{({\text{p}})}} \right)}} + \frac{1}{{\mu _i^{({\text{s}})}}} +\\ & \left( {1 - {h_i}} \right)\left( {\frac{{\rho _i^{({\text{s}})}\bar R_i^{({\text{s}})}}}{{1- \rho _i^{({\text{m}})}}} + \frac{1}{{\mu _i^{({\text{s}})}}}+ \frac{1}{{{\mu ^{({\text{c}})}} - {\lambda ^{({\text{c}})}}}}+ W_i^{({\text{t}})}} \right). \end{split}$

(10)

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

本节根据SD-DCN中的网络流分布特性建立TCAM命中率模型，进而结合2.3节所述的OpenFlow分组转发时延模型，建立OpenFlow分组转发能效联合优化模型，以求解TCAM最优容量.

3.1 TCAM命中率模型

在分组交换网络中，网络流量存在明显的局部性特点，大部分分组集中分布在少数流中^[32]. 以数据中心网络为例，众多测量研究结果表明：20%的top流占据分组总数的80%以上^[33]. 根据网络流量局部性，众多研究利用Zipf分布刻画网络流中的分组数量分布特性^[34-37]. 假设网络中有N条流，则可按照流大小即流的分组数量依次递减排序为（f₁, f₂, …, f_N）. 根据Zipf分布可知，流f_r的分组数量Q(r)与其大小排名r（r=1, 2, …, N）存在式（11）所示的幂律关系.

$Q(r) = \frac{C}{{{r\,^\alpha }}}.$

(11)

其中C和α均为大于0的常数，α表示分组在网络流中分布的倾斜程度. 假设OpenFlow交换机的TCAM容量为n条流表项，且存储所有网络流中排名靠前的n条流，则TCAM命中率h（n）如式（12）所示：

$h(n) = \dfrac{{\displaystyle\sum_{r = 1}^n {Q(r)} }}{{\displaystyle\sum_{r = 1}^N {Q(r)} }} = \dfrac{{\displaystyle\sum_{r = 1}^n {{r^{ - \alpha }}} }}{{{{{\varGamma }}_\alpha }(N)}}.$

(12)

其中 ${{{\varGamma }}_\alpha }(N) = \displaystyle\sum_{r = 1}^N {{r^{ - \alpha }}}$ . 假定网络流总数N=20000，对于不同的网络流分布倾斜度α，根据式（12）可得 TCAM命中率与TCAM容量的估计关系如图4所示.

图 4 TCAM命中率与TCAM容量的估计关系

Figure 4. Estimated relationship between TCAM hit rate and TCAM capacity

下载: 全尺寸图片幻灯片

从图4中可看出：α越大，相同容量下的TCAM命中率越高，即相同数量top流所占据的分组比例越高，网络流量局部性越明显. 当TCAM容量为4000条流表项，即可存储前20%的流时，若α=0.95，则TCAM命中率可达81.05%，与数据中心网络中的流量测量结果基本一致.

3.2 OpenFlow分组转发能效联合优化模型

在OpenFlow分组转发过程中，每个到达交换机的分组都需要查找TCAM流表，进而实现分组转发处理. 根据2.3节所述的OpenFlow分组转发时延模型和3.1节所述的TCAM命中率模型可知：TCAM容量越大，存储的流规则越多，TCAM命中率越高，即TCAM流表查找成功的分组占比越大，平均分组转发时延越小. 因此，平均分组转发时延与TCAM容量呈负相关关系. 由于TCAM采用并行匹配方式查找整个流表，查找能耗基本上与其容量成正比，假定分组转发过程中的其他能耗固定，则分组转发能耗可视为与TCAM容量呈正线性相关关系. 因此，可将TCAM容量作为决策变量，以分组转发时延和能耗为优化目标，建立能效联合优化模型求解TCAM最优容量.

对于TCAM容量为n的OpenFlow交换机，根据式（12）所示的TCAM命中率，定义TCAM流表命中失败概率q(n)=1− h(n). 进而结合式（10），可求出交换机的平均分组转发时延D(n)：

$\begin{aligned} D(n) =& {W^{({\text{p}})}}(n) + q(n)\left[ {{W^{({\text{m}})}}(n) + {W^{({\text{c}})}}(n) + {W^{({\text{t}})}}} \right]= \\ & \frac{{{{\bar R}^{({\text{s}})}}\left[ {{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]}}{{\left[ {1 - {a_1}q(n)} \right]\left[ {1 - {a_1}q(n) - {\rho ^{({\text{p}})}}} \right]}} + \frac{1}{{{\mu ^{({\text{s}})}}}} +\\ & q(n)\left\{ \begin{gathered} \frac{{{{\bar R}^{({\text{s}})}}\left[ {{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]}}{{1 - {a_1}q(n)}} + \frac{1}{{{\mu ^{({\text{s}})}}}} + \frac{1}{{{\mu ^{({\text{c}})}} - {a_0}q(n)}} + {W^{({\text{t}})}} \\ \end{gathered} \right\}, \\ \end{aligned}$

(13)

其中

${a_0} = \displaystyle\sum\limits_{i = 1}^K {\lambda _i^{({\text{p}})}} , \;\; {a_1} = \dfrac{{\displaystyle\sum_{k = 1}^K {{\delta _k}\lambda _k^{({\text{p}})}} }}{{{\mu ^{(s)}}}}, {{\bar R}^{({\text{s}})}} = \frac{{{\sigma ^{{{({\text{s}})}^2}}} + {1 {/ {\vphantom {1 {{\mu ^{{{({\text{s}})}^2}}}}}} } {{\mu ^{{{({\text{s}})}^2}}}}}}}{{{2 {/ {\vphantom {2 {{\mu ^{({\text{s}})}}}}} } {{\mu ^{({\text{s}})}}}}}}.$

(14)

同时，根据式（12）给出的TCAM命中率，可建立OpenFlow交换机的分组转发能耗模型. 假定每条TCAM流表项的平均查找能耗为e₁，由于TCAM容量为n条流表项，且采用并行查找方式，因此每个分组的TCAM查找能耗为ne₁. 若分组转发过程中的其他处理能耗为e₀, 则交换机的平均分组转发能耗E(n)如式（15）所示：

$E(n) = n{e_1} + {e_0}.$

(15)

以式（13）和式（15）分别给出的平均分组转发时延和能耗为优化目标，可建立式（16）所示的OpenFlow分组转发能效联合优化模型，求解TCAM最优容量.

$\mathop {\arg \min }\limits_n \left( {D(n),E(n)} \right).$

(16)

其中约束条件为

$\begin{gathered} D(n) < {D_{\max }}, \\ E(n) < {E_{\max }}, \\ n \in {\mathbb{N}_ + }. \\ \end{gathered}$

(17)

式（16）优化模型包含3个约束条件：1）平均分组转发时延D(n)不能超过QoS规定的最大时延D_max；2）平均分组转发能耗E(n)不能超过上限值E_max；3） TCAM容量n为正整数.

3.3 优化模型求解

OpenFlow分组转发能效联合优化模型是一个不等式约束下的多目标优化模型. 在该模型中，以TCAM容量n为决策变量，平均分组转发时延D(n)可通过定理1证明具有单调递减性，平均分组转发能耗E(n)显然单调递增. 而约束条件限定了D(n)和E(n)的最大值，即决定了TCAM容量的最小值n_min和最大值n_max，进而可求得D(n)和E(n)的最小值分别为D_min=D(n_max)和E_min=E(n_min).

定理1. 对于式（13）中的平均分组转发时延D(n)，若其参数均为正，且ρ^(m)+ρ^(p)=ρ^(s)<1，ρ^(c)=λ^(c)/μ^(c) <1，则D(n)具有单调递减性，即 $D'(n) < 0$ .

证明. 对于式（13），不妨假设n为连续自变量，利用复合函数求导法，可得D(n)的一阶导数：

${D^\prime }(n) = {D^\prime }\left( {q(n)} \right){q^\prime }(n).$

(18)

其中 $D'\left( {q(n)} \right)$ 如式（19）所示：

$\begin{aligned} {D^\prime }\left( {q(n)} \right)=& \frac{{{{\bar R}^{({\text{s}})}}{a_1}}}{{g\left( {q(n)} \right)}} + \frac{{ - g'\left( {q(n)} \right){{\bar R}^{({\text{s}})}}\left[ {{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]}}{{g{{\left( {q(n)} \right)}^2}}} + \\ &\frac{{{{\bar R}^{({\text{s}})}}\left[ {2{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]}}{{1 - {a_1}q(n)}} + \frac{{{{\bar R}^{({\text{s}})}}{a_1}\left[ {{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]q(n)}}{{{{\left[ {1 - {a_1}q(n)} \right]}^2}}} + \\ & \frac{1}{{\mu _i^{({\text{s}})}}}+ \frac{1}{{{\mu ^{({\text{c}})}} - {a_0}q(n)}} + \frac{{{a_0}q(n)}}{{{{\left[ {{\mu ^{({\text{c}})}} - {a_0}q(n)} \right]}^2}}} + {W^{({\text{t}})}}. \\ \end{aligned}$

(19)

其中

$g\left( {q(n)} \right) = \left[ {1 - {a_1}q(n) - {\rho ^{({\text{p}})}}} \right]\left[ {1 - {a_1}q(n)} \right],$

(20)

$g'\left( {q(n)} \right) = {a_1}\left[ {2{a_1}q(n) + {\rho ^{({\text{p}})}} - 2} \right].$

(21)

在式（20）中，有

${a_1}q(n) = \dfrac{{\displaystyle\sum_{k = 1}^K {{\delta _k}\lambda _k^{({\text{p}})}q(n)} }}{{{\mu ^{({\text{s}})}}}} = {\rho ^{({\text{m}})}} < 1.$

(22)

进而可知1−a₁q(n)>0. 由于ρ^(m)+ρ^(p)=ρ^(s)<1，则有1−a₁q(n)−ρ^(p)=1−ρ^(s)>0. 带入式（20）（21）中可得

$g\left( {q(n)} \right) > 0,$

(23)

$g'\left( {q(n)} \right) = {a_1}\left[ {{\rho ^{({\text{s}})}} - 1 + {\rho ^{({\text{m}})}} - 1} \right] < 0.$

(24)

同时 ${a_0}q(n) = \displaystyle\sum_{i = 1}^K {\lambda _i^{({\text{p}})}q(n)} = {\lambda ^{({\text{c}})}}$ ，而 ${\mu ^{({\text{c}})}} > {\lambda ^{({\text{c}})}}$ ，因此可得

${\mu ^{({\text{c}})}} - {a_0}q(n) = {\mu ^{({\text{c}})}} - {\lambda ^{({\text{c}})}} > 0.$

(25)

加之各项参数为正，因此式（19）等号右边的每项均为正，进而可得 $D'\left( {q(n)} \right) > 0$ . 对q(n)求导有

$q'(n) = - \frac{{{n^{ - \alpha }}}}{{{{{\varGamma }}_\alpha }(n)}} < 0.$

(26)

将上述结论带入式（18）可知： $D'(n) < 0$ .

证毕.

此时，可将优化目标D(n)和E(n)分别进行归一化处理，进而利用线性加权法将式（16）中的多目标优化函数转换成单目标优化函数f(n)：

$f(n) = \omega \frac{{D(n) - {D_{\min }}}}{{{D_{\max }} - {D_{\min }}}} + (1 - \omega )\frac{{E(n) - {E_{\min }}}}{{{E_{\max }} - {E_{\min }}}},$

(27)

其中ω为OpenFlow 平均分组转发时延所占的权重. 该函数具有凸性质，如定理2所证.

定理2. 对于式（27）所示的目标函数，若其参数均为正，且ρ^(s)<1，ρ^(c)<1，则该函数具有凸性质，即 $f''(n) > 0$ .

证明. 对f（n）二阶求导有

$\begin{aligned} &f''(n) = \\ &\frac{\omega }{{{D_{\max }} - {D_{\min }}}}\left[ \begin{gathered} {D^{\prime \prime }}\left( {q(n)} \right)\frac{{{n^{ - 2\alpha }}}}{{{{{\varGamma }}_\alpha }{{(N)}^2}}} + {D^\prime }\left( {q(n)} \right)\frac{\alpha }{{{{{\varGamma }}_\alpha }(N)}}{n^{ - \alpha - 1}} \end{gathered} \right]. \end{aligned}$

(28)

其中

$\begin{aligned} {D^{\prime \prime }}\left( {q(n)} \right) =& \frac{{ - 2{{\bar R}^{({\text{s}})}}{a_1}g'\left( {q(n)} \right)}}{{g{{\left( {q(n)} \right)}^2}}} + \\ & \frac{{2{{\bar R}^{({\text{s}})}}\left[ {{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]\left[ {g'{{\left( {q(n)} \right)}^2} - {a_1}^2g\left( {q(n)} \right)} \right]}}{{g{{\left( {q(n)} \right)}^3}}} + \\ & \frac{{2{{\bar R}^{({\text{s}})}}{a_1}}}{{1 - {a_1}q(n)}} + \frac{{2{{\bar R}^{({\text{s}})}}{a_1}\left[ {2{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]}}{{{{\left[ {1 - {a_1}q(n)} \right]}^2}}} + \\ & \frac{{2{{\bar R}^{({\text{s}})}}{a_1}^2\left[ {{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]q(n)}}{{{{\left[ {1 - {a_1}q(n)} \right]}^3}}} + \\ &\frac{{{a_0}}}{{{{\left[ {{\mu ^{({\text{c}})}} - {a_0}q(n)} \right]}^2}}} + \frac{{2{a_0}q(n)}}{{{{\left[ {{\mu ^{({\text{c}})}} - {a_0}q(n)} \right]}^3}}}. \end{aligned}$

(29)

其中 $g\left( {q(n)} \right)$ 和 $g'\left( {q(n)} \right)$ 分别如式（20）和式（21）所示. 根据定理1的证明过程可知

$\begin{gathered} g'\left( {q(n)} \right) = {a_1}\left[ {{\rho ^{({\text{s}})}} - 1 + {\rho ^{({\text{m}})}} - 1} \right] < {a_1}\left[ {{\rho ^{({\text{m}})}} - 1} \right] < 0, \\ \end{gathered}$

(30)

因此有

$\begin{gathered} g'{\left( {q(n)} \right)^2} = {a_1}^2{\left[ {{\rho ^{({\text{s}})}} - 1 + {\rho ^{({\text{m}})}} - 1} \right]^2} > {a_1}^2{\left[ {{a_1}q(n) - 1} \right]^2}. \\ \end{gathered}$

(31)

而

$\begin{split} {a_1}^2g\left( {q(n)} \right) = &{a_1}^2\left[ {1 - {a_1}q(n) - {\rho ^{({\text{p}})}}} \right]\left[ {1 - {a_1}q(n)} \right] <\\ & {a_1}^2{\left[ {1 - {a_1}q(n)} \right]^2}, \end{split}$

(32)

因此，在式（29）中，有

$g'{\left( {q(n)} \right)^2} - {a_1}^2g\left( {q(n)} \right) > 0.$

(33)

根据定理1的证明过程可知1−a₁q(n)>0，μ^(c)−a₀q(n)>0，g(q(n))>0，g'(q(n))<0. 加之各项参数均为正，则式（29）等号右边的每项均为正，进而可知 $D''\left( {q(n)} \right) > 0$ . 同时，根据定理1的证明过程可知 $D'\left( {q(n)} \right) > 0$ . 代入式（28）可得 $f''(n) > 0$ .

证毕.

由于目标函数f(n)具有凸性质，因此可利用二分法在整数范围[n_min, n_max]内搜索TCAM最优容量n_opt，使f(n)取最小值. 算法1给出了OpenFlow分组转发能效联合优化模型的求解算法.

算法1. OpenFlow分组转发能效联合优化算法.

输入：1）网络拓扑信息G(V,E)；2） OpenFlow交换机的分组到达速率λ^(p)，每个步骤j的处理速率 $\lambda _j^{\left( {\rm{s}} \right)}$ ，控制器的Packet-in处理速率μ^(c)；3）平均每条TCAM流表项的查找能耗e₁，分组转发过程中其他处理步骤的能耗之和e₀，分组转发能耗上限E_max；4） QoS允许的分组转发时延上限D_max.

输出：交换机的TCAM最优容量n_opt.

① 计算交换机的分组处理速率μ^(s) 和分组处理时间方差 ${\sigma ^{{{({\rm{s}})}^2}}}$ ;

② 计算控制器收到交换机S_k发送的Packet-in消息后，生成流规则并下发Flow-mod消息给交换机S_i的概率为δ_ik;

③ if λ^(p)>μ^(s)

④ 　exit；

⑤ end if

⑥ ${n_{\max }} = \left\lfloor {{{({E_{\max }} - {e_0})} \mathord{\left/ {\vphantom {{({E_{\max }} - {e_0})} {{e_1}}}} \right. } {{e_1}}}} \right\rfloor$ ；

⑦ ${n_{\min }} \leftarrow {D_{\max }}$ ；

⑧ while n_min ≠n_max do

⑨ 　 ${n_{{\text{mid}}}} = \left\lfloor {{{({n_{\min }} + {n_{\max }})} \mathord{\left/ {\vphantom {{({n_{\min }} + {n_{\max }})} 2}} \right. } 2}} \right\rfloor$ ；

⑩ 　计算目标函数f(n_mid) , f(n_mid +1)；

⑪ 　if f(n_mid) > f(n_mid +1)

⑫　　n_min = n_mid +1；

⑬ 　else

⑭　　n_max = n_mid；

⑮ 　end if

⑯ end while

⑰ return n_opt = n_min.

算法1分为3个步骤：1）计算中间参数，包括交换机处理速率μ^(s)（行①），交换机S_k发送的Packet-in消息触发控制器下发Flow-mod消息到交换机S_i的概率δ_ik（行②）；2）确定TCAM容量n的整数范围[n_min, n_max] （行⑥⑦）；3）二分查找TCAM容量的最优值n_opt（行⑧~⑰）.

4. 实　　验

本节首先通过模拟实验评估本文所提OpenFlow分组转发时延模型的准确性，然后采用数值分析方法分析不同因素对分组转发时延的影响，进而求解不同参数下的TCAM最优容量.

4.1 时延模型对比

实验采用Mininet平台模拟典型的Fat-tree网络拓扑结构^[22]，SDN控制器共管理10台OpenFlow交换机，包含2台核心交换机、4台汇聚交换机、4台边缘交换机. 其中，SDN控制器采用OpenDaylight，OpenFlow交换机采用Open vSwitch v2.13. 在模拟实验中，利用OFsuite性能测试工具测得控制器的Packet-in消息处理速率为21 kmsg/s，每台交换机的分组处理速率为20 kpkt/s. 同时，将交换机的流表容量设置为8000条流表项，流超时间隔为10 s. 实验利用Iperf工具为每台交换机模拟产生不同速率的网络流量，其中新流分组占比约为10%，进而测得平均分组转发时延如图5所示. 同时，将上述参数代入本文所提的OpenFlow分组转发时延模型和现有模型，其中控制器均采用M/M/1模型，OpenFlow交换机分别采用多优先级M/G/1模型、M/G/1模型^[17]、M^k/M/1模型^[14]，进而计算出平均分组转发时延的估计值如图5所示.

图 5 不同分组到达速率下的时延模型对比

Figure 5. Comparison of delay models with different packet arrival rates

下载: 全尺寸图片幻灯片

从图5中可以看出：与现有模型相比，本文所提基于多优先级M/G/1的OpenFlow分组转发时延模型具有更接近于测量值的估计时延. OpenFlow交换机的分组处理过程包含多个相互独立的步骤，而M^k/M/1模型将分组处理时间简单地看作服从泊松分布，故其估计时延与测量值相差较大. M/G/1模型可较为准确地估计OpenFlow交换机的分组处理时间，但在分组到达速率较大时，其估计时延明显较小. 这是因为该模型只考虑到达OpenFlow交换机的数据分组，而忽略了控制器下发的消息分组. 多优先级M/G/1模型则着重考虑了Flow-mod消息的分组处理时延，因而其分组转发时延估计值更接近于测量值.

实验采用4.1节所述参数，将OpenFlow交换机的分组到达速率 $\lambda _i^{( {\rm{p}} )}$ 设为10 kpkt/s，并不断调整OpenFlow交换机的流表容量值，可测得平均分组转发时延如图6所示. 同时，将上述参数代入本文所提的OpenFlow分组转发时延模型和现有模型，计算出平均分组转发时延的估计值如图6所示.

图 6 不同流表容量下的时延模型对比

Figure 6. Comparison of delay models with different flow table capacities

下载: 全尺寸图片幻灯片

从图6中可以看出：本文所提OpenFlow分组转发时延模型的估计时延比现有模型更接近于测量时延. 现有模型由于忽略了流表容量对分组转发时延的影响，其分组转发时延始终保持不变，估计不准确. 与此形成对照的是，随着流表容量的不断增大，本文所提模型的分组转发时延估计值逐步降低，并趋于稳定，与测量值接近. 这是因为交换机的流表命中率随流表容量的增大而升高，进而导致发送给控制器的Packet-in消息逐渐减少，其估计时延逐步接近于M/G/1模型. 特别地，当交换机的流表容量小于3000条流表项时，模拟实验中的控制器负载过大，将会丢弃部分Packet-in消息，导致分组转发时延测量值急剧升高. 此时，对于OpenFlow分组转发时延模型，由于流表命中率过低，控制器的Packet-in消息到达速率高于其处理速率，导致模型失效.

4.2 分组转发时延

进一步，实验采用数值分析方法研究平均分组转发时延的主要影响因素. 实验参数设定为：假定分组在网络流中的分布倾斜程度α = 0.95，每台OpenFlow交换机的分组到达速率λ^(p) = 10 kpkt/s，分组处理过程分为10个步骤，且每个步骤的处理速率相同，分组处理速率μ^(s) = 20 kpkt/s. 同时，SDN控制器的Packet-in消息处理速率μ^(c) = 21 kmsg/s，每台控制器管理10台OpenFlow交换机.

实验设置不同的TCAM容量，可得到平均分组转发时延与分组到达速率之间的关系如图7所示. 从图7可看出：当TCAM容量一定时，分组到达速率越高，交换机和控制器的负载越大，平均分组转发时延越高. 同时，当分组到达速率一定时，交换机的TCAM容量越大，流表命中率越高，Packet-in消息的发送速率越低，其在控制器中的逗留时间越短，平均分组转发时延越低. 此外，TCAM容量越大，允许的分组到达速率越高. 具体而言，当交换机的TCAM容量n分别为4000，6000，8000，10000条流表项时，平均分组转发时延在分组到达速率λ^(p)分别超过10 kpkt/s，11.6 kpkt/s，12.8 kpkt/s，13.8 kpkt/s时急剧上升，且允许的最大分组到达速率分别为10.7 kpkt/s，12.6 kpkt/s，14.3 kpkt/s，15.3 kpkt/s.

图 7 平均分组转发时延与分组到达速率的关系

Figure 7. Relationship between average packet forwarding delay and packet arrival rate

下载: 全尺寸图片幻灯片

实验设置不同的TCAM容量，可得到平均分组转发时延与分组处理速率之间的关系，如图8所示. 从图8可看出：当TCAM容量一定时，分组处理速率越高，分组在交换机中的逗留时间越短，平均分组转发时延越低；同时，当分组处理速率一定时，交换机的TCAM容量越大，流表命中率越高，发送给控制器的Packet-in消息越少，相应收到的Flow-mod消息也越少，平均分组转发时延越低. 此外，TCAM容量越大，交换机的分组处理速率需求越低. 具体而言，当交换机的TCAM容量n分别为4000，6000，8000，10000条流表项时，平均分组转发时延在分组处理速率μ^(s)分别小于16 kpkt/s，14.5 kpkt/s，13.7 kpkt/s，13.2 kpkt/s时急剧上升，且交换机允许的最小分组处理速率分别为14.3 kpkt/s，13.4 kpkt/s，12.7 kpkt/s，12.1 kpkt/s.

图 8 平均分组转发时延与分组处理速率的关系

Figure 8. Relationship between average packet forwarding delay and packet processing rate

下载: 全尺寸图片幻灯片

实验设置不同的TCAM容量，可得到平均分组转发时延与Packet-in消息处理速率之间的关系如图9所示. 从图9中可看出：当TCAM容量一定时，Packet-in消息处理速率越高，其在控制器中的逗留时间越短，平均分组转发时延越低. 同时，当Packet-in消息处理速率一定时，交换机的TCAM容量越大，流表容量越高，Packet-in消息的发送速率越小，其在控制器中的逗留时间越短，平均分组转发时延越低. 此外，交换机的TCAM容量越大，控制器允许的Packet-in消息处理速率越低. 具体而言，当交换机的TCAM容量n分别为4000，6000，8000，10000条流表项时，平均分组转发时延在Packet-in消息处理速率μ^(c)分别低于18 kmsg/s，15 kmsg/s，12 kmsg/s，8 kmsg/s时急剧上升，且控制器允许的最低Packet-in消息处理速率分别为18.9 kmsg/s，14.1 kmsg/s，10.6 kmsg/s，7.9 kmsg/s.

图 9 平均分组转发时延与Packet-in消息处理速率的关系

Figure 9. Relationship between average packet forwarding delay and Packet-in message processing rate

下载: 全尺寸图片幻灯片

4.3 TCAM最优容量

对于OpenFlow分组转发能效联合优化模型，不妨假设每条TCAM流表项的平均查找能耗e₁为1个单位，其他处理步骤的能耗e₀为3000个单位，分组转发能耗上限为E_max为15000个单位，即最大TCAM容量为12000条流表项. 同时，QoS要求的最大分组转发时延D_max=1.5 ms. 基于上述参数配置，将单目标优化函数f(n)中的权重ω设置不同值，进而实现OpenFlow分组转发能效联合优化算法，求解不同分组到达速率下的TCAM最优容量如图10所示.

图 10 不同分组到达速率下的TCAM最优容量

Figure 10. Optimal TCAM capacity with different packet arrival rates

下载: 全尺寸图片幻灯片

从图10中可看出：当每个交换机的分组到达速率增加时，TCAM最优容量将随之增大，以提高TCAM命中率，保证Packet-in消息发送速率不会过高，从而防止控制器过载，Packet-in消息逗留时间过大. 具体而言，当交换机的分组到达速率λ^(p)分别为5 kpkt/s，10 kpkt/s，15 kpkt/s，且权重ω = 0.8时，TCAM最优容量n_opt分别为1400，4600，10800条流表项. 当分组到达速率超过16 kpkt/s时，交换机需要继续增大TCAM容量，以保证分组转发时延，但分组转发能耗将会超出上限，因而无解. 此外，当分组到达速率一定时，分组转发时延的权重越高，TCAM最优容量越大，以使TCAM命中率越高，平均分组转发时延越小.

采用上述同样的参数配置，并将交换机的分组到达速率λ^(p)设为10 kpkt/s，进而求解不同分组处理速率下的TCAM最优容量，如图11所示. 从图11中可看出：当交换机的分组处理速率升高时，TCAM最优容量将随之减小，并趋于稳定. 这是因为在保证分组转发时延的情况下，交换机的分组处理速率越高，需要的TCAM容量越小. 具体而言，当交换机的分组处理速率μ^(s)分别为14 kpkt/s，16 kpkt/s，18 kpkt/s，且权重ω = 0.8时，TCAM最优容量n_opt分别为8900，5800，4900条流表项. 此外，当交换机的分组处理速率低于12 kpkt/s时，由于逐步接近于分组到达速率，平均分组转发时延将超出QoS规定的上限，因而无解.

图 11 不同分组处理速率下的TCAM最优容量

Figure 11. Optimal TCAM capacity with different packet processing rates

下载: 全尺寸图片幻灯片

采用上述同样的参数配置，并将交换机的分组处理速率μ^(s)设为20 kpkt/s，进而求解不同Packet-in消息处理速率下的TCAM最优容量，如图12所示. 从图12中可看出：当控制器的Packet-in消息处理速率升高时，TCAM最优容量将随之降低，并趋于稳定. 这是因为控制器的Packet-in消息处理速率越高，其允许的Packet-in消息到达速率越高，进而交换机所需的TCAM容量越少. 具体而言，当Packet-in消息处理速率μ^(c)分别为15 kmsg/s，25 kmsg/s，35 kmsg/s，且权重ω = 0.8时，TCAM最优容量n_opt分别为6600，3800，2900条流表项. 此外，当Packet-in消息处理速率小于7 kmsg/s时，交换机需要继续增加TCAM容量，以提高TCAM命中率，保证平均分组转发时延，但分组转发能耗将会超出上限，因而无解.

图 12 不同Packet-in消息处理速率下的TCAM最优容量

Figure 12. Optimal TCAM capacity with different Packet-in message processing rates

下载: 全尺寸图片幻灯片

5. 结　　论

本文针对SD-DCN网络场景，利用多优先级M/G/1排队模型刻画OpenFlow交换机的分组处理过程，进而构建OpenFlow分组转发时延模型. 进一步，基于网络流分布特性建立TCAM命中率模型，求解OpenFlow分组转发时延与TCAM容量的关系式. 在此基础上，结合TCAM查找能耗，建立OpenFlow分组转发能效联合优化模型，以求解TCAM最优容量. 实验结果表明：与已有排队模型相比，本文所提时延模型更能准确估计SD-DCN网络场景下的OpenFlow分组转发性能. 同时，数值分析结果表明：交换机的TCAM容量和控制器的Packet-in消息处理速率对OpenFlow分组转发时延有着关键性的影响，而交换机的分组到达速率和分组处理速率影响较弱. 最后，通过OpenFlow分组转发能效联合优化算法，求解出不同参数配置下的TCAM最优容量，为SD-DCN网络的实际部署提供参考依据.

作者贡献声明：罗可提出研究思路，并设计研究方案，以及修订论文最终版本；曾鹏完善论文创新点，并完成模型的建立和推导，以及撰写论文初稿主要部分；熊兵设计了实验思路，以及审查和修改润色论文；赵锦元协助创新点推导和论文修改；所有作者都参与了实验分析和手稿撰写.

图 1 4段握手协议

Figure 1. Four-phase handshake protocol

下载: 全尺寸图片幻灯片

图 2 2段握手协议

Figure 2. Two-phase handshake protocol

下载: 全尺寸图片幻灯片

图 3 单轨数据编码

Figure 3. Single-rail data coding

下载: 全尺寸图片幻灯片

图 4 双轨数据编码

Figure 4. Two-rail data coding

下载: 全尺寸图片幻灯片

图 5 以时间步为单位的SNN片上执行模式

Figure 5. SNN on-chip execution pattern in time step

下载: 全尺寸图片幻灯片

图 6 在1000个时间步中被激发的神经元数量

Figure 6. Number of fired neurons in 1000 execution time step

下载: 全尺寸图片幻灯片

图 7 类脑处理器片上互连通信NoC架构框图

Figure 7. Block diagram of NoC architecture for on-chip interconnection and communication of neuromorphic processor

下载: 全尺寸图片幻灯片

图 8 5端口双工路由器设计框图

Figure 8. Block diagram of 5-ports duplex router design

下载: 全尺寸图片幻灯片

图 9 数据报文格式设计

Figure 9. Design of data packet format

下载: 全尺寸图片幻灯片

图 10 输入模块设计和X-Y路由算法示意图

Figure 10. Design of input module and schematic of X-Y routing algorithm

下载: 全尺寸图片幻灯片

图 11 输出模块设计和轮询仲裁机制示意图

Figure 11. Design of output module and schematic of round robin arbitrating mechanism

下载: 全尺寸图片幻灯片

图 12 异步链路的数据通路和控制电路框图

Figure 12. Block diagram of data channel and control circuit of asynchronous link

下载: 全尺寸图片幻灯片

图 13 同步域与异步域数据转换电路写通道

Figure 13. Writing channel of data conversion circuit between synchronous domain and asynchronous domain

下载: 全尺寸图片幻灯片

图 14 同步域与异步域数据转换电路读通道

Figure 14. Reading channel of data conversion circuit between synchronous domain and asynchronous domain

下载: 全尺寸图片幻灯片

图 15 基于GALS技术的NosralC架构设计流程

Figure 15. Design flow of GALS based NosralC architecture

下载: 全尺寸图片幻灯片

图 16 不同注入率下的吞吐量变化

Figure 16. Throughput variation under different injection rates

下载: 全尺寸图片幻灯片

表 1 液体状态机SNN配置

Table 1 Configuration of Liquid State Machine SNN

参数	数量/类型
输入层神经元数量	256
液体层神经元数量	1000
液体层中的激活型神经元数量	800
液体层中的抑制型神经元数量	200
输出层	1000×10全连接层
激活型→激活型神经元连接概率	0.4
激活型→抑制型神经元连接概率	0.4
抑制型→激活型神经元连接概率	0.5
抑制型→抑制型神经元连接概率	0

下载: 导出CSV

表 2 同步同等设计基线与NosralC的功耗对比

Table 2 Power Comparison Between Synchronous Counter part Baseline and NosralC

测试数据集	功耗类型	功耗/mW		减幅/%
测试数据集	功耗类型	同步同等设计	NosralC	减幅/%
FSDD	静态	165.0	96.7	41.4
	动态	21.4	19.8	7.5
	总功耗	186.4	116.5	37.5
NTI-DIGITS	静态	165.0	96.7	41.4
	动态	19.7	16.3	17.4
	总功耗	187.4	113.0	38.8
DVS128 Gesture	静态	165.0	96.6	41.5
	动态	18.8	17.9	4.5
	总功耗	183.8	114.5	37.7
NMNIST	静态	166.0	96.9	41.6
	动态	24.8	19.7	20.6
	总功耗	190.8	116.6	38.9
平均	静态	164.0	96.1	41.4
	动态	20.8	18.2	12.4
	总功耗	184.8	114.3	38.1

下载: 导出CSV

表 3 同步同等设计基线与NosralC的平均延迟对比

Table 3 Average Delay Between Synchronous Counterpart Baseline and NosralC

测试数据集	平均延迟/周期		减幅/%
测试数据集	同步同等设计	NosralC	减幅/%
FSDD	1098	1010	8.0
NTI-DIGITS	1035	952	8.0
DVS128 Gesture	1097	1036	5.5
NMNIST	1062	996	6.2
平均	1072.9	998.7	6.9

下载: 导出CSV

表 4 同步同等设计基线与NosralC的吞吐量对比

Table 4 Throughput Comparison Between Synchronous Counterpart Baseline and NosralC

测试数据集	吞吐量/(报文/周期)		减幅/%
测试数据集	同步同等设计	NosralC	减幅/%
FSDD	6.8	6.7	1.9
NTI-DIGITS	6.5	6.4	2.4
DVS128 Gesture	6.9	6.8	1.3
NMNIST	6.7	6.6	0.8
平均	6.7	6.6	1.6

下载: 导出CSV

表 5 同步同等设计基线与NosralC的能效对比

Table 5 Energy Efficiency Comparison Between Synchronous Counterpart Baseline and NosralC

测试数据集	能效/(Mop/W)		增幅/%
测试数据集	同步同等设计	NosralC	增幅/%
FSDD	500.1	683.4	36.7
NTI-DIGITS	493.7	714.3	44.7
DVS128 Gesture	534.4	734.7	37.5
NMNIST	461.2	680.8	47.6
平均	497.4	703.3	41.4

下载: 导出CSV

表 6 同步基线与NosralC的资源利用量对比

Table 6 Resource Utilization Comparison Between Synchronous Counterpart Baseline and NosralC

FPGA资源	资源利用量		增幅/%
FPGA资源	同步同等设计	NosralC	增幅/%
LUT	563697	595769	5.7
FF	1332625	1367228	2.6
BUFG	1	1	0
平均			4.2

下载: 导出CSV

表 7 NosralC与先进相关工作的比较

Table 7 Comparison of NosralC and the State of the Art Work

配置	TrueNorth	Loihi	NosralC
工艺	65nm ASIC	14nm ASIC	FPGA
架构	2维Mesh	2维CMesh	2维Mesh
路由器	异步	异步	同步
链路	异步	异步	异步
节点数	4096	131	256
等效频率/MHz	0.001	153.8~243.9	20
平均延迟/ns		113~465	36440

下载: 导出CSV

参考文献(31)

[1]	Thonnart Y, Vivet P, Clermidy F. A fully-asynchronous low-power framework for GALS NoC integration [C] //Proc of the 13th Design, Automation & Test in Europe Conf & Exhibition. Piscataway, NJ: IEEE, 2010: 33−38
[2]	Peng Yuanxi, Zhou Feng, Hai Yue, et al. A multi-instruction streams extension mechanism for SIMD processor[J]. Chinese Journal of Electronics, 2017, 26(6): 1154−1160
[3]	Fang Jianbin, Liao Xiangke, Huang Chun, et al. Performance evaluation of memory-centric ARMv8 many-core architectures: A case study with Phytium 2000+[J]. Journal of Computer Science and Technology, 2021, 36(1): 33−43 doi: 10.1007/s11390-020-0741-6
[4]	Akopyan F, Sawada J, Cassidy A, et al. TrueNorth: Design and tool flow of a 65 mW 1 million neuron programmable neurosynaptic chip[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2015, 34(10): 1537−1557 doi: 10.1109/TCAD.2015.2474396
[5]	Lines A, Joshi P, Liu Ruokun, et al. Loihi: Asynchronous neuromorphic research chip[C] //Proc of the 24th IEEE Int Symp on Asynchronous Circuits and Systems (ASYNC). Piscataway, NJ: IEEE, 2018: 32−33
[6]	Kasapaki E, Schoeberl M, Sørensen R B, et al. Argo: A real-time network-on-chip architecture with an efficient GALS implementation[J]. IEEE Transactions on Very Large Scale Integration Systems, 2016, 24(2): 479−492 doi: 10.1109/TVLSI.2015.2405614
[7]	Jiang Weiwei, Bertozzi D, Miorandi G, et al. An asynchronous NoC router in a 14nm FinFET library: Comparison to an industrial synchronous counterpart[C] //Proc of the 20th Design, Automation & Test in Europe Conf & Exhibition (DATE 2017). New York: ACM, 2017: 732−733
[8]	Yakovlev A, Vivet P, Renaudin M. Advances in asynchronous logic: From principles to GALS & NoC, recent industry applications, and commercial CAD tools[C] //Proc of the 16th Design, Automation & Test in Europe Conf & Exhibition. Piscataway, NJ: IEEE, 2013: 1715-1724
[9]	Wang Bo, Zhou Jun, Wong Wengfai, et al. Shenjing: A low power reconfigurable neuromorphic accelerator with partial-sum and spike networks-on-chip[C] //Proc of the 23rd Design, Automation & Test in Europe Conf & Exhibition (DATE 2020). Piscataway, NJ: IEEE, 2020: 240−245
[10]	Frenkel C, Legat J D, Bol D. MorphIC: A 65-nm 738k-synapse/mm 2 quad-core binary-weight digital neuromorphic processor with stochastic spike-driven online learning[J]. IEEE Transactions on Biomedical Circuits and Systems, 2019, 13(5): 999−1010 doi: 10.1109/TBCAS.2019.2928793
[11]	Benjamin B V, Peiran G, Mcquinn E, et al. Neurogrid: A mixed-analog-digital multichip system for large-scale neural simulations[J]. Proceedings of the IEEE, 2014, 102(5): 699−716 doi: 10.1109/JPROC.2014.2313565
[12]	Moradi S, Qiao Ning, Stefanini F, et al. A scalable multicore architecture with heterogeneous memory structures for dynamic neuromorphic asynchronous processors (DYNAPs)[J]. IEEE Transactions on Biomedical Circuits and Systems, 2018, 12(99): 106−122
[13]	Mundy A, Knight J, Stewart T C, et al. An efficient SpiNNaker implementation of the neural engineering framework[C] //Proc of 2015 Int Joint Conf on Neural Networks (IJCNN). Piscataway, NJ: IEEE, 2015: 692−700
[14]	Jackson Z. Free spoken digit dataset[DB/OL]. (2019-12-24) [2021-10-12]. https://github.com/Jakobovski/free-spoken-digit-dataset
[15]	Anumula J, Neil D, Delbruck T, et al. Feature representations for neuromorphic audio spike streams[J]. Frontiers in Neuroscience, 2018, 12: 23−23
[16]	Amir A, Taba B, Berg D, et al. A low power, fully event-based gesture recognition system[C] //Proc of the 30th IEEE Conf on Computer Vision & Pattern Recognition. Piscataway, NJ: IEEE, 2017: 7388−7397
[17]	Garrick O, Ajinkya J, Cohen G K, et al. Converting static image datasets to spiking neuromorphic datasets using saccades[J]. Frontiers in Neuroscience, 2015, 9: 473−473
[18]	Benini L, Micheli G D. Powering networks on chips[C] //Proc of the 14th Int Symp on System Synthesis. Piscataway, NJ: IEEE, 2001: 33−38
[19]	Leon A S, Langley B, Shin J L. The UltraSPARC T1 processor: CMT reliability[C] //Proc of IEEE Custom Integrated Circuits Conf 2006. Piscataway, NJ: IEEE, 2006: 555−562
[20]	Bell S, Edwards B, Amann J, et al. TILE64-processor: A 64-core SoC with mesh interconnect[C] //Proc of the 55th Solid-State Circuits Conf 2008 (ISSCC 2008). Piscataway, NJ: IEEE, 2008: 88−598
[21]	Bainbridge J, Furber S. CHAIN: A delay-intensive chip area interconnect[J]. IEEE Micro, 2002, 22(6): 16−23
[22]	Fakhri A. QNOC: Quality network operation center[C] //Proc of the 1st Int Conf on Information & Communication Technologies. Piscataway, NJ: IEEE, 2004: 83−84
[23]	Bjerreg A R T, Sparso J. A router architecture for connection-oriented service guarantees in the MANGO clockless network-on-chip[C] //Proc of the 8th Design, Automation and Test in Europe 2005. Piscataway, NJ: IEEE, 2005: 1226−1231
[24]	Zhang Peng, Lin Chuang, Jiang Yixin et al. ANOC: Anonymous network-coding-based communication with efficient cooperation[J]. IEEE Journal on Selected Areas in Communications, 2012, 30(9): 1738−1745 doi: 10.1109/JSAC.2012.121018
[25]	Orchard G, Lagorce X, Posch C, et al. Live demonstration: Real-time event-driven object recognition on SpiNNaker[C/OL] //Proc of 2015 IEEE Int Symp on Circuits and Systems (ISCAS). 2015 [2021-10-12]. https://ieeexplore.ieee.org/document/7169036
[26]	Dominguez-Morales J P, Jimenez-Fernandez A, Rios-Navarro A, et al. Live demonstration: Multilayer spiking neural network for audio samples classification using SpiNNaker[C/OL] //Proc of 2017 IEEE Int Symp on Circuits and Systems (ISCAS). 2017 [2021-10-12]. https://ieeexplore.ieee.org/document/8050404/media#media
[27]	Gutierrez-Galan D, Dominguez-Morales J P, Perez-Pena F, et al. Live demonstration: Neuromorphic robotics, from audio to locomotion through spiking CPG on SpiNNaker[C/OL] //Proc of 2019 IEEE Int Symp on Circuits and Systems (ISCAS). 2019 [2021-10-12].https://ieeexplore.ieee.org/document/8702186
[28]	渠鹏,陈嘉杰,张悠慧,等. 实现软硬件解耦合的类脑计算硬件设计方法[J]. 计算机研究与发展,2021,58(6):1146−1154 doi: 10.7544/issn1000-1239.2021.20210170 Qu Peng, Chen Jiajie, Zhang Youhui, et al. A proposal of software-hardware decoupling hardware design method for brain-inspired computing[J]. Journal of Computer Research and Development, 2021, 58(6): 1146−1154 (in Chinese) doi: 10.7544/issn1000-1239.2021.20210170
[29]	Maass W, Natschl G T, Markram H. Real-time computing without stable states: A new framework for neural computation based on perturbations[J]. Neural Computation, 2002, 14(11): 2531−2560 doi: 10.1162/089976602760407955
[30]	Peeters A, Beest F T, Wit M D, et al. Click elements: An implementation style for data-driven compilation [C] //Proc of the 16th IEEE Symp on Asynchronous Circuits and Systems. Piscataway, NJ: IEEE, 2010: 3−14
[31]	Singh M, Nowick S M. MOUSETRAP: High-speed transition-signaling asynchronous pipelines[J]. IEEE Transactions on Very Large Scale Integration Systems, 2007, 15(6): 684−698 doi: 10.1109/TVLSI.2007.898732

施引文献(9)

期刊类型引用(6)

1.	齐锐，彭依明，万静. 基于边缘计算的异构集群混合式资源调度方法. 电气技术与经济. 2025(01): 57-59 . 百度学术
2.	任晓旭，仇超，邓辉，戴子明，刘泽军，王晓飞. 边缘智能融合区块链：研究现状、应用及挑战. 信息与控制. 2024(01): 1-16 . 百度学术
3.	王斌，马重阳，彭博，牛莹. 基于区块链的分布式算力资源调度机制. 中国宽带. 2024(05): 139-141 . 百度学术
4.	崔佳怡，谢人超，唐琴琴. 基于生成式人工智能的算力网络自智优化研究综述. 中兴通讯技术. 2024(06): 54-62 . 百度学术
5.	夏景旋，申国伟，郭春，崔允贺 . USPS:面向算力资源高效协同的用户态跨协议代理系统. 计算机科学. 2023(11): 348-355 . 百度学术
6.	周旭，李琢. 面向算力网络的云边端协同调度技术. 中兴通讯技术. 2023(04): 32-37 . 百度学术