CN103685041B - 一种基于比特粒度可编程的路由器及路由方法 - Google Patents

Abstract

本发明提供一种可编程虚拟路由器及路由方法，其包括可编程硬件板卡、PCI/PCI‑E总线以及主机，所述硬件板卡通过所述总线与所述主机相连接，通过所述可编程硬件板卡实现比特粒度可编程的数据平面结构，所述数据平面结构支持数据包中任意比特的提取，支持在跨总线长度的边界部分任意比特长度的组合，从而数据包中任意域可被提取组合，通过多流水线的设计实现了多个虚拟路由器实例的并行运行；所述主机用于实现虚拟的控制平面，所述虚拟的控制平面与可编程硬件板卡中的多个虚拟路由器动态地连接来形成映射关系。本发明能够提供处理任意类型数据包的数据平面和在线编程能力。

Description

一种基于比特粒度可编程的路由器及路由方法

技术领域

本发明涉及互联网技术领域，具体涉及可编程路由器结构，尤其涉及一种基于比特粒度可编程的路由器及路由方法。

背景技术

互联网经历了30余年的发展，取得了巨大的成功，已经成为整个世界不可或缺的信息交流和获取的途径。随着计算机和通信技术的迅速发展，催生了大量新业务以及新协议，比如P2P,VOD,云计算，社交网络，移动互联网等；除此之外，针对以上互联网发展中遇到的问题，互联网领域的研究者们提出了各种新型网络体系结构及改进方案，如内容命名网络(Named Data Network)、服务导向网络、面向移动的网络等，新型网络体系架构在命名编址、路由转发等方面都引入了新的机制，为了满足新协议的需求，网络中传输的数据包格式已经不局限于IP的格式，研究人员不得不加入或减少现有的包头字段或引入自定义的包格式。但是现有的路由器设备难以支持这些新型的数据包处理，这就需要在路由器的数据平面上做相应的创新，使得路由器能够支持各种类型数据包的处理和转发。

现在已经涌现出一些设计结构来提供路由器的可编程能力，它们的可编程的能力和程度由其内部结构决定的。不同的结构具有不同的编程接口和不同的编程复杂度。Click，SwitchBlade采用基于模块的可编程结构，当用户需要添加新的处理功能时，需要了解设备编程原理以及C、Verilog等编程语言，并根据需要重新进行设计并编译整合，这样的编程结构带来较高的设计复杂度，并且在添加新功能时需要设备暂停工作，不提供在线的可编程能力。OpenFlow采用基于流表的结构可在线配置转发的规则，具有很高的灵活性，但OpenFlow的数据平面结构不能变动，如果需要在OpenFlow中添加与转发相关的新协议或功能，如部署非IP协议或基于TCP序号分流等功能则只能在控制器中编写软件实现，不能得到数据平面高速转发的支持，包转发速度将成为瓶颈，而基于IP数据包的十元组编程结构不能提供足够的编程灵活性。今后的数据包结构的改变可能出现在数据包的各个位置，因此需要数据平面具有处理任意类型数据包的能力。

发明内容

(一)技术问题

本发明要解决的问题是如何提供处理任意类型数据包的数据平面和在线编程能力。

(二)技术方案

本发明提供一种可编程虚拟路由器，其包括可编程硬件板卡、PCI/PCI-E总线以及主机，所述硬件板卡通过所述总线与所述主机相连接，通过所述可编程硬件板卡实现比特粒度可编程的数据平面结构，所述数据平面结构支持数据包中任意比特的提取，支持在跨总线长度的边界部分任意比特长度的组合，从而数据包中任意域被进行提取组合，通过多流水线的设计实现多个虚拟路由器；所述主机用于实现虚拟的控制平面，所述虚拟的控制平面与可编程硬件板卡中的多个虚拟路由器动态地连接来形成映射关系。

可选的，所述可编程硬件板卡包括：

多个输入端口，用于输入数据包，每个输入端口对应有各自的输入队列；

输入仲裁模块，用于以轮询或加权轮询的方式分流数据包到各个数据处理单元；

多个数据处理单元，用于提取数据包的对应时序比特位，并处理固定位宽的数据；

转发单元，用于进行编程定制转发。

可选的，所述可编程硬件板卡为FPGA板卡。

可选的，所述可编程硬件板卡还包括交换单元，用于在数据包通过转发单元确定转发端口后，对确定转发端口的数据包再选择输出端口。

可选的，所述输入端口和输出端口在网口和PCI/PCI-E总线接口中进行选择。

可选的，所述多个数据处理单元结构相同，而且相互级联。

本发明还提供一种可编程的路由方法，其包括下列步骤：

1)利用可编程硬件板卡实现比特粒度可编程的数据平面结构，所述数据平面结构支持数据包中任意比特的提取，支持在跨总线长度的边界部分任意比特长度的组合，从而数据包中任意域被进行提取组合；

2)实现虚拟的控制平面，所述虚拟的控制平面与可编程硬件板卡中的多个虚拟路由器动态地连接来形成映射关系。

3)通过所述控制平面，对数据平面进行配置和编程。

可选的，所述控制平面还用于生成多个虚拟机来运行不同的控制平面协议，虚拟机的端口和可编程硬件板卡中的多个虚拟路由器动态地连接来形成映射关系。

可选的，所述步骤1)进一步包括：

10)通过输入端口输入数据包，每个输入端口对应有各自的输入队列；

11)以轮询或加权轮询的方式分流数据包到各个数据处理单元；

12)利用所述数据处理单元提取数据包的对应时序比特位，并处理固定位宽的数据；

13)利用转发单元进行编程定制转发。

可选的，所述步骤13)进一步包括：

131)用户通过编程接口定义数据包的格式和数据域处理方式；

132)采用统一定义的可扩展流水线结构来处理数据包的各个数据域，采用将条件表达式映射到TCAM的编程方案来实现转发的可编程控制。

133)通过用户设定的规则来选择控制的内部的处理功能。

(三)技术效果

本发明通过采用比特粒度可编程和虚拟化的技术手段使得路由器结构能够提供在线的可编程、数据平面高速并行转发、能够处理任意类型数据包的功能。

附图说明

图1表示本发明的基于比特粒度可编程的路由器的整体结构；

图2表示表示本发明的所述路由器的数据平面结构；

图3表示表示本发明的所述路由器的包处理单元内部结构；

图4表示本发明的所述路由器的处理级编程的格式；

图5表示本发明的所述路由器的转发级的内部结构；

图6表示本发明的所述路由器的转发级的编程原理；

图7表示IP数据包在数据平面中的处理格式；

图8表示编程配置IPv4路由器的处理级编程脚本格式；

图9表示编程配置IPv4路由器的转发级编程脚本格式。

具体实施方式

实施例1：

本发明提供一种可编程虚拟路由器，其包括可编程硬件板卡、PCI/PCI-E总线以及主机，所述硬件板卡通过所述总线与所述主机相连接，通过所述可编程硬件板卡实现比特粒度可编程的数据平面结构，所述数据平面结构支持数据包中任意比特的提取，支持在跨总线长度的边界部分任意比特长度的组合，从而数据包中任意域被提取和组合，通过多流水线的设计实现多个虚拟路由器；所述主机用于实现虚拟的控制平面，所述虚拟的控制平面与可编程硬件板卡中的多个虚拟路由器动态地连接形成映射关系。

可选的，所述可编程硬件板卡包括：

多个输入端口，用于输入数据包，每个输入端口对应有各自的输入队列；

输入仲裁模块，用于以轮询或加权轮询的方式分流数据包到各个数据处理单元；

多个数据处理单元，用于提取数据包的对应时序比特位，并处理固定位宽的数据；

转发单元，用于进行编程定制转发。

可选的，所述可编程硬件板卡为FPGA板卡。

可选的，所述可编程硬件板卡还包括交换单元，用于在数据包通过转发单元确定转发端口后，对确定转发端口的数据包再选择输出端口。

可选的，所述输入端口和输出端口在网口和PCI/PCI-E总线中进行选择。

可选的，所述多个数据处理单元结构相同，而且相互级联。

本发明还提供一种基于比特粒度可编程的路由方法，其包括下列步骤：

1)利用可编程硬件板卡实现比特粒度可编程的数据平面结构，所述数据平面结构支持数据包中任意比特的提取，支持在跨总线长度的边界部分任意比特长度的组合，数据包中任意域都可以被提取和组合；

2)实现虚拟的控制平面，所述虚拟的控制平面与可编程硬件板卡中的多个虚拟路由器动态地连接来形成映射关系。

3)通过所述控制平面，对数据平面进行配置和编程。

可选的，所述控制平面还用于生成多个虚拟机来运行不同的控制平面协议，虚拟机的端口和可编程硬件板卡中的多个虚拟路由器动态地连接来形成映射关系。

可选的，所述步骤1)进一步包括：

10)通过输入端口输入数据包，每个输入端口对应有各自的输入队列；

11)以轮询或加权轮询的方式分流数据包到各个数据处理单元；

12)利用所述数据处理单元提取数据包的对应时序比特位，并处理固定位宽的数据；

13)利用转发单元进行编程定制转发。

可选的，所述步骤13)进一步包括：

131)用户通过编程接口定义数据包的格式和数据域处理方式；

132)采用统一定义的可扩展流水线结构来处理数据包的各个数据域，采用将条件表达式映射到TCAM的编程方案来实现转发的可编程控制。

133)通过用户设定的规则来选择控制的内部的处理功能。

实施例2：

本实施例与交换芯片，网络处理器等ASIC结构的方案不同，采用可编程硬件如FPGA来构建数据平面的功能可以实现比特粒度可编程的数据平面结构，这是因为FPGA的内部逻辑都可以由开发人员定义，这样可以保证每个处理环节按照我们的思想进行设计和部署。

(1)总体结构

图1中所示为可编程数据平面的硬件结构，数据平面基于可编程硬件，如FPGA等，数据包通过输入端口如网口，PCI等总线接口输入到板卡中，每个输入端口对应有各自的输入队列，数据包在其中以FIFO方式排队。一个高速的输入仲裁模块以轮询或加权轮询的方式分流数据包到各个虚拟的数据平面，即相互分离的转发流水线中，这些流水线都是同构的。流水线的包头处理部分是由相同结构的包处理单元构成，为了实现数据包的比特粒度的可编程能力，处理流水线的每个处理单元可以将数据包的对应时序比特位提取出来，每个单元可以处理固定位宽的数据，前后级的处理单元也可组合成更长的处理宽度，用户可以通过配置处理规则来对各个处理单元的功能进行配置。在处理功能上可以选择TCAM查表，哈希匹配，基本运算等来处理比特组合成的数据域，所有处理单元的处理结果都会最终汇聚输出到转发级；在转发级，用户可以通过配置TCAM查找转发表来实现编程定制转发功能，但数据包的转发端口确定后，数据包发送到交换单元进行交换输出，输出的选择与输入端口一样可以在网口以及PCI等总线中选择。硬件板卡通过PCI/PCI-E与主机相连接，控制平面的功能位于主机中，主要的功能包括控制平面的虚拟化机制，虚拟机的端口和数据平面板卡的动态映射机制以及对数据平面的配置和控制功能。控制平面可以生成多个虚拟机来运行不同的控制平面协议，这些虚拟的控制平面可以与硬件中的多个虚拟路由器动态地连接来形成映射关系。数据平面的配置和编程也是通过控制平面实现，控制平面可以通过对硬件中寄存器配置来实现数据平面的编程功能。

(2)处理级流水线详细结构及编程规则

流水线结构图如图2所示，处理级部分是由完全同构的包处理单元级联而成的，数据包输入到处理级有两条路径，一条是进入包处理单元进行查找，判断等操作，处理结果供转发级判断输出的端口和目的地址；还有另一条路径是基于这样的考虑：输出的端口判断是在包头处理完毕后才能决定，而此时的总线数据已经没有了包头的数据，就需要包头的数据在FIFO中缓存以供输出。

每个包处理单元在时序控制模块的统一控制下实现对应数据域的处理，每个模块中都有很多寄存器来分别存储可编程的信息，这些寄存器的位宽和功能也是不同的，如两种输入的掩码选择，处理的运算选择，运算的操作数，输出的目的模块选择，输出的结果选择，以及输出的偏移量等等。对数据域的选择和处理都是基于用户对这些寄存器的编程控制，整个处理单元结构如图3所示，它的数据输入包括两个部分：当前总线上需要处理的数据和前一级处理完后的数据，这两部分的数据可根据输入规则进行任意组合，组合后的数据可以选择匹配规则及相应的处理方式，预定义的匹配规则包括哈希匹配、TCAM查找以及比较操作，哈希匹配用于最基本的匹配情况，如MAC地址的分类，包类型的识别，都只需要将某一数据域与特定的数值进行比较；TCAM查找功能用于路由表查找，ARP表查找等需要进行高速查表操作的情况；比较操作用于TTL比较等需要进行数据比较的场合。处理结果有两个输出方向，某些规则的处理结果会输出到下一级，如最长前缀匹配的结果；其他规则的处理结果会输出到转发级，这些处理结果会决定数据包的最终输出格式及输出端口。

处理级的配置规则格式如图4所示，整体来讲它包括13个域，分别为字选择，用于选择当前规则使用的处理流水单元所处位置；偏移量用于选择所需要处理的比特在两种输入数据部分所处位置；匹配模式用于选择匹配操作的类型；操作部分定义了操作的类型以及操作数的数值；输出控制部分主要用于选择输出的格式以及输出方向，每条规则都可以定义自己处理后的输出在整个输出数据中的偏移量，输出目的的选择是为了确定模块的输出是到下一级还是最终的转发级。

(3)转发级详细结构及编程规则

转发级由单个模块构成，其结构如图5所示，来自各个处理单元的输出结果作为该模块的输入，这些输入包括了用于数据包更改的信息以及用于确定输出端口的判断选择信息，该模块内部也有寄存器来区分这两部分的数据，包括每个输入的偏移量，功能和处理方式可以在寄存器中做相应的控制。用于更改数据包的信息可以在输出时直接替换所需更改的数据域；而用于输出端口判断的信息会一般经过复杂的逻辑选择来确定最终的输出端口，对于普通的路由器或中间盒来讲，这些输入会在有限状态机中以条件表达式的方式进行处理，但是这种方式不易于可编程的实现，为了解决这一问题，我们采用了条件表达式映射的方式来解决这一问题。以图6为例，输入信号包括L,M,N三个判断信号，每个占用1比特的宽度，条件表达式如最左侧代码所示，不同的逻辑组合导致丢包，转发到网络端口以及转发到控制平面等决策。这样一个结构很容易通过树形结构的决策树来表示，如中间的图形所示，而我们知道为了表示3个比特的所有组合关系需要用到23＝8个树节点来表示，当比特宽度增加时，需要表示的节点数将会指数增加，这就意味着需要与节点数目相同的表项来表示，使得编程的复杂度和资源占用率极高，为了解决这一问题进而我们利用TCAM的三态查找的特点来进行可编程能力的优化，以图中表达式为例，与所需要的状态无关的组合可以用TCAM中的不定态来替代，这样就可以将8条规则压缩到4条，而当比特宽度增加时，压缩比将会进一步增大。通过这种方式可以实现转发目的端口的可编程选择。

为了使得我们的结构能够与集中式的网络协议和控制系统相匹配，如OpenFlow等协议，数据平面允许利用流表的格式进行配置，比如OpenFlow的十元组流表匹配域可以先转换成处理级的对应比特的操作，而流表的Action域则可以转化为TCAM表形式进行转发，这样我们的数据平面既可以基于分布式的路由协议进行编程又可以基于集中式的控制器进行流表等配置实现集中控制。

实施例3：

本发明具体可实施的场景包括：

实施场景一：商用网络，包括当前基于IPv4的互联网以及基于IPv6的网络，路由器的灵活可编程性兼容当前的网络协议和标准。

实施场景二：网络创新实验平台，网络体系结构的创新需要实验平台来进行实验测试，它有内在的可编程路由器的需求。

实施场景三：数据中心网络，为了使得数据中心内部的网络高效运行，研究人员提出很多新的协议，这些协议也对中间盒的可编程能力提出了要求。

我们以最常用的商用网络中IPv4路由器为例来描述可编程能力，IP包在数据平面中的处理格式如图7所示，图中每64比特划分为一个字，每个字单独由一个包处理单元处理，以每个字需要处理的内容我们划分每个字的功能：字0是数据包的控制字，包括包长度以及包的输入端口信息，这一部分由于不是包头信息，所以不用处理；字1包括目的MAC地址(63位-16位)，路由器需要判断目的MAC地址是否发到本地以及是否为广播数据包，如果是广播包则需要发送的控制平面；字2中需要判断数据包的类型(31位-16位)，确定它是否为IP包或非IP如ARP包；字3中需要判断TTL的数值(15位-8位)是否正确，如果正确的话需要做TTL减一的操作；字4中需要判断校验值(63位-48位)是否正确，并且把目的IP地址高16位(15位-0位)发送到下一级；字5需要将目的IP地址低16位(63-48位)与上级的输入组合成32位的目的IP地址，并进行LPM的查找，查找结果输出到下一级(第6级)进行ARP查找的处理。我们定义的规则如图8所示，这些处理的输出最终汇聚到转发级。

转发级将判断信号分离出来后会得到9种判断信号，路由器需要根据这些信号来进行转发的处理，用户可以通过图9中所示的TCAM查找表的规则来定义数据包的转发目的端口及地址。第一条规则描述了从控制平面发来的数据可以直接从相应端口输出，第二条到第七条规则做了如下定义，以下类型的包需要发送到控制平面：非IP包、校验错误的数据包、指定发到控制平面、包头有选项、TTL错误以及LPM查找未命中和ARP查找未命中的都会发送到控制平面，只有正常的数据包在LPM和ARP查找都命中后才会从查找后的端口输出。

由前面的详细说明可知，本发明提出的基于比特粒度可编程虚拟路由器由两部分组成，基于在操作系统运行软件构成控制平面及基于可编程硬件构成数据平面。本发明设计的比特粒度可编程的路由器结构上可以部署各种已有的和今后可能的协议。

它具有如下的特性：

比特粒度可编程：为了适应网络发展的需求，路由器需要支持新业务和新体系架构的创新，网络中间盒不能仅在控制平面有所创新，更需要数据平面的创新来支持各种类型数据包的处理。数据平面允许任意比特的提取，在跨总线长度的边界部分允许任意比特长度的组合，实现数据包中任意域的提取组合能力，提取出的数据域允许用户定义处理功能，比如TCAM查找，哈希匹配，比较，运算等操作，以实现数据包处理的可编程能力；包的转发目的端口和目的地址决定于包头的处理结果，为了使得包转发的方式也能够通过编程实现，数据平面将包头处理结果编码并利用TCAM的三态查找能力来确定数据包的最终输出。

虚拟化支持：为了使得路由器可以允许多个不同网络同时运行，这些网络既可以是同构的也可以是异构的，路由器需要能够支持虚拟化，即多个路由器实例同时运行。路由器需要在控制平面上需要完全分离的功能，功能独立运行，可以分别配置各自协议，他们之间互不影响，具有良好隔离性；在数据平面上，各路由器实例中的数据能够分别进行高速的处理，处理后的数据能够以一种有效地方式进行重新聚合。

以上实施方式仅用于说明本发明，而并非对本发明的限制，如本发明还可用于收割其他农作物，有关技术领域的普通技术人员，在不脱离本发明的精神和范围的情况下，还可以做出各种变化和变型，因此所有等同的技术方案也属于本发明的范畴，本发明的专利保护范围应由权利要求限定。

Claims (10)

1.一种可编程虚拟路由器，其特征在于包括可编程硬件板卡、总线以及主机，所述硬件板卡通过所述总线与所述主机相连接，通过所述可编程硬件板卡实现比特粒度可编程的数据平面结构，所述数据平面结构支持数据包中任意比特的提取，支持在跨总线长度的边界部分任意比特长度的组合，从而数据包中任意域被进行提取组合，通过多流水线的设计实现多个虚拟路由器；所述主机用于实现虚拟的控制平面，所述虚拟的控制平面与可编程硬件板卡中的多个虚拟路由器动态地连接来形成映射关系；

其中，所述可编程硬件板卡输出的端口判断是在包头处理完毕后才能决定，而此时的总线数据已经没有了包头的数据，需要包头的数据在FIFO中缓存以供输出。

2.如权利要求1中所述的可编程虚拟路由器，其特征还在于，所述可编程硬件板卡包括：

多个输入端口，用于输入数据包，每个输入端口对应有各自的输入队列；

输入仲裁模块，用于以轮询或加权轮询的方式分流数据包到各个数据处理单元；

多个数据处理单元，用于提取数据包的对应时序比特位，并处理固定位宽的数据；

转发单元，用于进行编程定制转发。

3.如权利要求1中所述的可编程虚拟路由器，其特征还在于，所述可编程硬件板卡为FPGA板卡。

4.如权利要求2中所述的可编程虚拟路由器，其特征还在于所述可编程硬件板卡还包括交换单元，用于在数据包通过转发单元确定转发端口后，对确定转发端口的数据包再选择输出端口。

5.如权利要求4中所述的可编程虚拟路由器，所述输入端口和输出端口在网口和总线接口中进行选择。

6.如权利要求4中所述的可编程虚拟路由器，其特征还在于：所述多个数据处理单元结构相同，而且相互级联。

7.一种可编程的路由方法，其特征在于，该方法包括下列步骤：

1)利用可编程硬件板卡实现比特粒度可编程的数据平面结构，所述数据平面结构支持数据包中任意比特的提取，支持在跨总线长度的边界部分任意比特长度的组合，从而数据包中任意域被进行提取组合；

2)实现虚拟的控制平面，所述虚拟的控制平面与可编程硬件板卡中的多个虚拟路由器动态地连接来形成映射关系；

3)通过所述控制平面，对数据平面进行配置和编程；

其中，在包头处理完毕后利用所述可编程硬件板卡决定输出的端口，此时的总线数据已经没有了包头的数据，需要包头的数据在FIFO中缓存以供输出。

8.如权利要求7所述的可编程的路由方法，其特征还在于：所述控制平面还用于生成多个虚拟机来运行不同的控制平面协议，虚拟机的端口和可编程硬件板卡中的多个虚拟路由器动态地连接来形成映射关系。

9.如权利要求7所述的可编程的路由方法，所述步骤1)进一步包括：

10)通过输入端口输入数据包，每个输入端口对应有各自的输入队列；

11)以轮询或加权轮询的方式分流数据包到各个数据处理单元；

12)利用所述数据处理单元提取数据包的对应时序比特位，并处理固定位宽的数据；

13)利用转发单元进行编程定制转发。

10.如权利要求9所述的可编程的路由方法，所述步骤13)进一步包括：

131)用户通过编程接口定义数据包的格式和数据域处理方式；

132)采用统一定义的可扩展流水线结构来处理数据包的各个数据域，采用将条件表达式映射到TCAM的编程方案来实现转发的可编程控制；

133)通过用户设定的规则来选择控制的内部的处理功能。