- 1 -
中国科技论文在线
Click 软件路由器的单机分布式结构实现
方案
刘晓佳，王振凯*
作者简介：刘晓佳，（1985-），男，硕士研究生，未来网络应用研究。
通信联系人：王振凯，男，副教授，主要研究方向：下一代网络、P2P技术、分布式多媒体、嵌入式系统。
（北京邮电大学信息与通信工程学院，北京 100876） 5
摘要：本文给出了一种以单机分布式方式来构建 Click 软件路由器的方案。文章首先讨论了
软件路由器的研究现状，并给出了 Click 软件路由器和单机分布式结构的介绍，分析了系统
设计中需要解决的难题，然后给出了系统的实现方案，并介绍了核心模块的主要功能和实现
方式，最后提出了用 NS-3 仿真软件结合 Click 来仿真单机分布式 Click 软件路由器的调试
方法。 10
关键词：软件路由器；单机分布式；Click；NS-3
中图分类号：TP311
A Scheme to Achieve Stand-alone Distributed Architecture
of Click Modular Software Router 15
Liu Xiaojia, Wang Zhenkai
(School of Information and Communication Engineering, Beijing University of Posts and
Telecommunications, Beijing 100876)
Abstract: The paper presents a scheme to build a stand-alone distributed click software
first, it discusses the software router research,and gives the introductions of the Click software 20
router and stand-alone distributed structure,and analysis of system design problems to
then it gives the system implementations, and describes the main features of the core module.
Finally it gives a method to debug the distributed system of Click using NS-3 and Click.
Keywords: Software router; Stand-alone distributed router; Click; NS-3
25
0 引言
近年来,随着新的互联网应用和业务不断出现,现有网络体系结构设计已不能满足需求的
增长,为了设计和开发新的网络协议和服务,支持可扩展的软件路由器在各大研究机构盛行。
主要有普林斯顿大学的 Scout[1]路由器，华盛顿大学的 Router Plugins[2]和麻省理工学院的
Click[3,4]路由器 。其中 Click软件路由器以灵活的体系结构而著称，开发者可以自由的按照30
自己的设计重新定义路由器，因此成为最受关注的开源软件路由器。
研究中发现，目前 Click软件路由器普遍采用单机集中式的方式来构建软件路由器，这
就使得软件路由器普遍存在的性能和吞吐量问题成为 Click软件路由器的一种约束。然而路
由器体系结构经过四代的发展，早已进入集群式结构阶段。即使在单机路由器领域，最为先
进的体系结构也是采用单机分布式 Crossbar结构。目前却没有一种方案来实现用单机分布式35
方式来构建 Click软件路由器。本文在设计和实现一个支持分布式和虚拟化的网络实验平台
过程中，提出一种以单机分布式方式构建 Click软件路由器的方案，希望能够为未来网络体
系结构的研究与发展提供一种参考和启发。
- 2 -
中国科技论文在线
1 技术背景与技术难题分析
Click软件路由器介绍 40
Click路由器由 element 组成，element 是分组处理功能模块的抽象。每个 element 实现
路由器中一项独立的简单功能，将不同 element组合起来就能完成一台路由器的基本功能。
路由器配置(router configuration)是一张以 element为顶点的有向图，分组沿着这张图的边从
一个 element 传递到下一个。Click 配置脚本是由一种声明型语言编写的，这种语言就叫做
Click 语言，它不但可读性非常强，而且十分适合被工具自动解析。基于模块化的 element45
和可配置的 Click语言这两大特性，使得 Click软件路由器具备非常强的扩展性。
支持负载平衡的单机分布式结构介绍
一般的单机分布式 Crossbar结构具有两个特点：一是线卡不仅仅是简单的网卡，而是具
有处理器、内存、网卡的独立子系统，具有独立的报文转发能力。二是通过 Crossbar交叉开
关代替共享总线，从而能在各数据流彼此不相关情况下，同时并发处理多个数据流。 50
支持负载平衡的两级交换结构[5,6]是台湾张正尚教授提出的一种单机分布式 Crossbar 结
构的改进版本。该结构提出在第一级负载平衡的条件下，第二级采用 Birkhoff-von Neuman
输入排队交换结构，对已完成负载均衡的通信量按照一个周期性的连接模式序列进行交换，
就能达到 100%的吞吐率。
技术难题分析 55
根据负载平衡的两级交换结构，第一级需要完成通信量的负载均衡，才能保证第二级交
换时达到 100%的吞吐量，因此第一个难题就是如何实现通信量的均衡。
Click 软件路由器不支持分布式架构，因此第二个难题就是如何实现分布式。由于每个
线卡需要具有独立转发能力，因此实现分布式也就是要解决各线卡之间相互转发报文的问
题。 60
为了保证服务质量，需要根据需求为不同的虚拟子网提供不同的带宽，因此第三个难题
是如何为不同虚拟子网提供需要的带宽。
在各线卡之间数据流相关的情况下，会出现端口争用的问题，进而产生链头阻塞问题，
因此第四个难题就是要解决链头阻塞问题。
2 软件流程设计 65
图 1 软件流程设计框图
Software process design diagram
- 3 -
中国科技论文在线
本文的软件设计方案是参考单机分布式 Crossbar 结构和负载平衡的两级交换结构而设
计的。如图 1所示，从左到右，横向分析，整个程序流程被交换机划分为两块，将交换机左70
侧定义为第一级，交换机右侧定义为第二级。其中，第一级有两个数据流向。一个为输入流
向，从第一级外部输出模块接受外部网络的数据，经过第一级相关模块处理，送至交换机，
并通过交换机送至第二级模块处理。另一个为输出流向，从交换机接收来自第二级模块处理
后的数据，并经过第一级相关模块的处理，送至第一级外部输出模块，并通过该模块将数据
发送至外部网络。第二级只有一个数据流向，从交换机输出的数据经过第二级各模块的处理75
又送回到交换机，并通过交换机送至第一级。如图 1所示，从上到下，纵向分析，交换机左
侧可划分为三个并行的程序流程，它们分别位于三块主板上，功能完全相同，为外部网络提
供软件路由器的三个输入输出网络接口，负责和外部网络的输入输出数据交互和将输入数据
流负载平衡到第二级各并行处理流程中。交换机右侧可划分为两个并行的程序流程，用来并
行处理输入的数据流，从而提高软件路由器的处理能力和吞吐量。此外，第一级和第二级的80
并行程序流程均可以根据需求扩展为多个。从左到右的整个程序流程也可以根据需求对程序
模块的组成进行扩展。
因此，该系统组成方案具有并行处理、吞吐量大、可扩展、可编程、可自定义等一系列
优点。
3 核心软件模块介绍 85
分布式子系统间报文转发模块
要实现分布式子系统间报文互相转发的功能，首先要对各子系统进行编号，将第一级三
个并行的输入输出子系统编号为 101、102、103，编号头部的 1表示第一级，若进行扩展依
次类推；将第二级两个并行的处理子系统编号为 201、202，编号头部的 2 表示第二级，若
进行扩展依次类推。 90
要完成各子系统之间报文相互转发的功能，需要知道各目的子系统的MAC地址，才能
对 IP 报文封装上以太网头部，并在局域网中正确的发送到目的子系统。设计的方案是在各
子系统上设计地址响应模块，该模块存储了本子系统的编号和MAC地址的一一对应关系，
并能对请求本系统MAC地址的源子系统发送应答报文。并且，在各子系统上设计地址查询
与封装模块，该模块接受到上游模块送来的目的系统编号信息，并将该信息以系统内自定义95
以太网报文的形式在局域网内发送广播报文，向其它子系统请求目的系统编号对应的 MAC
地址，并将接收到的响应信息存储在内部设计的缓存结构中，此后再向该目的系统发送报文
时只需要在缓存中查询对应MAC地址信息即可。每条缓存保存了编号信息与地址信息、缓
存有效的时间信息以及其它信息。将所有的缓存分别维护在STL的List容器和HashContainer
容器中。List容器根据时间先后顺序来插入缓存，这样方便将过期的缓存清掉。HashContainer100
容器根据关键字来存取缓存信息，便于快速查找。在系统运行一段时间达到平衡状态后，缓
存中维护了所有其它子系统的地址信息。若扩展后子系统较多，也可以尝试将不常用的地址
信息存储在磁盘文件中。
负载平衡模块
根据张正尚的两级交换结构思路，要实现第一级负载平衡的功能，需要采用轮转的方式105
将报文发送到第二级系统。这里，我们以轮转的方式将目的系统的编号信息作为信息封装在
Click用户层报文 Packet的标注域中，发送到下游模块即可。
- 4 -
中国科技论文在线
PGPS算法实现模块
要实现各虚拟化子网的服务质量保证，需要提供根据带宽需求来对各虚拟化子网处理后
的报文进行排队。虚拟化子网的划分是通过转发处理模块完成的。对各虚拟化子网进行服务110
质量保证是通过虚拟子网队列模块完成。
该模块实现了基于包的广义处理器共享算法[7]。首先定义了一个依据关键字从小到大有
序插入的一个链表模板结构来存储任何类型的结构。该结构支持按照插入排序思想来插入要
存储到结构中的数据，并提供每次从头部取得要输出的数据的操作。这符合 PGPS算法的思
想，报文按照虚拟完成时间的先后顺序来提供服务。虚拟完成时间可以通过包到达的虚拟时115
间来计算。虚拟时间在每个忙期的开始时定义为 0，当没有报文到达或离开时，虚拟时间与
真实时间间隔成线性关系，因此可以用真实时间间隔来求出下一次的虚拟时间。而当有报文
入队或出队后需要更新新的虚拟时间。具体的程序流程如图 2所示。
图 2 WFQ队列工作流程图 120
Flow chart of WFQ queue
- 5 -
中国科技论文在线
VOQ队列实现模块
第一级经过负载平衡后，报文是以轮转的形式发到第二级各主板，因而不会产生链头阻
塞问题。而第二级经过处理后报文是根据目的 IP地址的要求，将报文发回到目的 IP地址所
在网络与第一级接口的某线卡上，并经过该线卡输出处理后，发到目的网络。显然，如果在125
报文的目的地址不均衡的情况下，会发生链头阻塞的问题。为此，采用 VOQ[8]的方式来处
理链头阻塞。即对每个输出端口进行排队。根据报文的目的地址，对每个输出端口设置虚拟
子网队列，并已轮询的顺序调度输出后，实现了 VOQ队列的功能。这是通过输出端口标注、
地址查询与封装、输出分类、虚拟子网队列、轮询调度这五个模块共同完成的，如图 1所示。
4 基于 NS-3仿真单机分布式 Click软件路由器 130
单机分布式 Click软件路由器方案，需要将 Click软件安装到不同线卡上，为了进行系
统调试，需要将各子系统进行联合调试，这给程序调试一定的难度。此外，一旦出现问题，
也不易观察结果。而NS-3[9]仿真软件对Click协议的支持给本系统调试带来了一种解决方法。
NS-3仿真软件支持将 Click协议作为网络协议来处理真实的报文。原理是 NS-3系统将仿真
报文发送到 Click系统进行处理，处理完后送回至 NS-3系统。 135
因此我们可以建立八个 NS-3 仿真节点。其中五个节点组成单机分布式 Click系统，即
三个节点模拟第一级线卡、两个模拟第二级线卡。另外三个节点系统外节点连接到 Click系
统，其中两个为 Client节点、一个为 server结点，通过 TCP协议连接，用 socket发送报文，
来仿真系统的连通性。如图 3所示仿真结果。在系统达到平衡之前，每次发送 IP报文，均
通过查询地址的方式来得到目的MAC地址；而当系统达到平衡后，每次通过从缓存中查询140
地址信息后封装MAC地址的方式来发送 IP报文。
图 3 NS-3仿真结果
The NS-3 simulation results
145
- 6 -
中国科技论文在线
5 结论
本文给出了一种以单机分布式的方式来实现 Click软件路由器的方案，并给出了系统的
详细组成框图，描述了各核心模块的主要功能与实现方式，最后提出了一种用 NS-3仿真软
件结合 Click来调试单机分布式 Click路由器的方法。该方案已在硬件系统上实现。
下一步，将添加更多的模块来在该系统上完成一些新的网络协议和服务验证，以期能够150
用最经济的方式来验证对互联网的新的研究。
[参考文献] (References)
[1] The Scout Operating System[OL].
[2] Dan Decasper, Zubin Dittia, Guru Parulkar, Bernhard Plattner. Router Plugins:A Modular and Extensible 155
Software Framework for Modern High Performance Integrated Services Routers. IEEE/ACM Transactions on
Networking, 2000.
[3] Robert Morris, Eddie Kohler, John Jannotti, and M. Frans Kaashoek. The Click modular router. Operating
Systems Review, 1999, 35(4): 217-231.
[4] The Click Modular Router Project[OL]. 160
[5] C. S. Chang, D. S. Lee, Y. S. Jou. Load Balanced Birkhoff-von Neumann Switches, Part I: One-stage Buffering.
Computer Communications, 2002, 25: 611-622.
[6] C. S. Chang, D. S. Lee, C. M. Lien. Load Balanced Birkhoff-von Neumann Switches, Part II: Multi-stage
Buffering. Computer Communications, 2002, 25: 623-624.
[7] A. Parekh. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks. PhD 165
dissertation, Massachusetts Institute of Technology, 1992.
[8] Chao H J. Next Generation Routers[C]. Proceedings of the IEEE, 2002-09, 90(9):1518-1558.
[9] NS-3[OL].
