Click模块化路由器

【概述】

Click是一种基于软件控制的模块化路由器。其架构可以大致视为一系列数据包处理模块（称为elements）组成的。一个Click路由器可以看成一张由elements作为顶点，数据包传递路径作为边的图。这种模块化设计使得内部功能结构清晰且易于拓展。

1.介绍

现在的趋势下，路由器的功能已经不再是单纯用于包转发，往往还同时具有地址转换、包过滤等功能，并往往扮演着防火墙一类的角色。但是，现在的路由器设计的都很封闭，管理员仅仅能控制功能的开关，却很难实现各个功能之间更为复杂的交互，而第三方开发者也很难对路由器功能进行拓展。

因此就有了Click模块化路由器，它可以提供细粒度的网络控制。Click由一系列的称为element的功能模块组成。这些elements都具有很窄的功能interface，提供最为atomic的功能实现，但是可以通过多个elements互相之间的拓展来完成更为复杂的功能。这些elements拼成一个有向图（directed graph），就形成了一个模块化的路由器。要拓展一个路由器的功能，程序员可以自己写新的功能模块，也可以将已有的功能模块重新组装，完成不同的功能。 （文中提到这个idea和Unix很相似？我不太懂Unix，有空可以了解一下。）

2.架构

正如前面所说，Click由一系列的elements构成，而所有的Click路由器的原子化的功能都包含在elements中。具体来说，在一个running router 中，一个element就是一个C++对象，一条connection就是一个指向该对象的指针，而一个传递动作就是一次内部函数的调用。

一个element有如下重要的属性：

1） element类 （element class）

正如前面所述，一个element就是一个C++的对象，因此也就有一个class与之对应，element属于该element class。

2） 端口（port）

一个element可以由多个输入输出的端口。所有的connection都是始自于一个element的输出端口，终于另一个element的输入端口。

3）配置语句 （configuration string）

配置语句是一个可选项，用于在路由器初始化时配置其中的状态。

4）方法接口（method interface）

一个element可以提供一个或多个接口，如最基本的router可以提供packet transfer的接口，最基本的包转发功能，而支持队列的element可以提供回报queue length的接口。

2.1 push和pull连接

Click路由器中的连接分为push和pull两种类型。push连接是常规的包转发连接，由源element发送一个packet出来到目的element。而pull连接则是相反，由目的element向源element发出一个request索取一个包，再由源端口回复给它。一个连接是push还是pull和连接两端的端口有关。push端口到push端口的就是push连接，pull端口到pull端口的就是pull连接。而push到pull端口的连接非法。

路由器中还有一种端口称为agnostic，也就是未指定状态的端口，当它和push端口建立连接时就是push端口，当它和pull端口建立连接时就是pull端口，因此可以看作是一个中性的状态。但是需要注意的是，当一个router要进行propagation之前，所有沿途的端口都必须赋予相应且合法的状态，在此之前路由器无法进行转发功能（propagation constraint）。

2.2 数据包存储

element的端口上并不默认包含队列(queue)，在Click中，队列本身就是一个element，也就是一个对象（或说是一个类）。这也就意味着网络管理员可以显式的定义数据是如何存储的。一个Queue需要一个push的input端口和一个pull的output端口。

2.3 CPU调度

Click控制着一个任务队列（task queue），这个队列内的内容单元就是一个个element。通过调度这个队列，路由器可以安排在某个时间内哪个element的功能可以调用CPU的资源。换言之，element既是包处理的最小单元，也是CPU占用控制的任务队列中的最小单元。但是大多数element并不需要放在任务队列中，而是通过push和pull方*到它时自动隐性调用的。

Click目前是以单线程运行的，也就是说从一个包转发开始，CPU跟踪这个包走过一个个element，同一时间内只会有一个element在运行处理这个包，一直到这个包被drop或被store。

2.4 Flow-Based Router Context

一个element想找到另一个element有两种方法，一种是通过名字来调用，另一种是通过Flow-based router context来调用（不知道怎么翻译了，简称FBRC吧）。FBRC可以用来声明一个从某一个element出来的packet经过若干次transfer以后在哪里停下来，也可以用来声明到达某一个element的packet是从哪里发出来的，说简单点就是“从哪来”和“到哪去”。更具体点说，一个element可能会向系统发问“如果我这个包从端口2发出去，它可能会到哪里去？”这类问题的答案都是FBRC经过计算以后加以回复的。FBRC使用的是一种配置拓扑图的简单数据流算法，一般来说elements会在初始化的时候询问一次FBRC，并在路由器运行期间使用这个结果作为快速reference，而element需要具有接受多个result并在结果过多或过少时报错的能力。

2.5 Click语言

Click语言中主要包含两个重要部分，声明(declaration)和连接(connection)。声明是用来创建element的，连接则用来指明element之间是怎么互相关联的。Click语言中还包含一种抽象机制称为“复合元素”(compound element)。它可以包含多个基本element，如一个queue元素加一个shaper元素可以合并为一个Shapedqueue元素，而其他配置则可以将其视为一个整体元素加以调用。

2.6 安装配置

目前Click可以运行在两种驱动平台上，一种是Linux内核驱动（Linux in-kernal driver），一种是用户层驱动（user-level driver）。用户层驱动一般是用来做调试使用的，而内核驱动则往往用来用作生产。我们暂时就关注于内核驱动。

要安装一个Click的配置，用户首先需要将一个写好的Click文件传到核心驱动中，由核心驱动通过分析该文件来生成相应的elements并将路由器加入网络中。一次新的配置的安装会移除旧的配置及其状态，如queue中的包等。但是，Click包含两种手段可以使得原配置不被丢失：

1） Handlers： Handlers如同一个element面向用户的界面。一个element中可以包含多个handler，如果这个element叫c，那么一个名为count的handler就是一个放在proc/click/c 路径下的名为count的文件。

2）Hot swapping（热插拔）：有的时候对于configuration的更改可能是增添或删除element，也就意味着无法使用element内部handler进行配置的保留。此时可以使用热插拔的方法，即写一个新的configuration file，只有当这个配置运行正常时才使用这个配置，如果这个配置出问题则会重新降级到原本的配置中。通过利用这种热插拔机制，Click还可以实现在路由器运行时动态增删elements。

2.7 Element的具体实现

简洁的说，一个element是一个element class的对象，一个element class是一个名为Element类的C++子类，Element中包含了20多种虚函数，但是由于大多数虚函数中已经有了默认的实现，因此在继承时其实只需要重载其中的五六种方法，而如果要实现最基本的路由功能则只需要三个方法就够了。

2.8 Element的设计体系及限制

一般来说，用户都倾向于细粒度的element和更为简单的标准。但是有的情况下粗粒度的控制会更好一些，特别是在Click中很多对于流的处理，往往不会对于一个流内部的不同包进行细粒度的控制，或者是一些复杂的域间协议也不会对内部的具体内容单元进行单独的控制。

传统的路由器中会包含一些并不实际参与具体路由动作的功能（而是起到一些路由前的决策和准备的作用），例如路由表，网络参数统计等，这些功能在Click中都包含在数据包的转发路径中的某些element中，例如路由表会包含在选择路径的element中，而网络统计也会包含在相应的收集模块中。这些模块也会向外界提供相应的方法来调用这些内部的功能。

Click也具有一些限制和待完善的地方：

1）Click无法让CPU针对每一个特定的流来调度；

2）Click提供的FBRC机制缺乏针对性（not specific）；

3）Click语言不提供配置变量，例如无法将一个Ethernet address赋值给一个变量a并调用它，而必须多次重复显式写出来这个地址值。

3. 一个IP 路由器

该部分展示了一种真实的Click路由器的配置。IP转发任务由于只包含本地信息，因此可以很自然的应用于Click的架构当中。举一个DecIPTTL的例子。DecIPTTL被用于检测一个进来的IP包的TTL（time-to-live）字段，如果一个包的TTL依然有效，则DecIPTTL会将该字段减1，修改checksum并从第一个端口转发出去；如果一个包的TTL已经过期，则DecIPTTL将会把这个包从端口2发送出去（往往发送至一个ICMPerror的element中），之所以这种操作都是基于本地信息，是因为诸如TTL字段的判别和decision只是包含在packet当中，而不受该包的转发路径上其他element的影响。

另一类情况就是一个element对于包的操作使受到其他element的影响的，也就不再是基于本地信息了。在Click中针对这类操作可以使用一种称为注释（annotations）的方法，注释往往由某个element添加并跟随在包的header当中，但是并不算packet data的一部分。在本部分所举的IP router的例子中也会使用这种注释的方法，具体有如下几种：

1）目标IP地址： 虽然一个IP包的header中包含了目标地址，但是由于在路由过程中的中间路由器可能并不需要知道IP的目标地址（例如仅仅需要知道下一跳网关地址），因此element之间可能就会频繁修改这个目标地址。但是这种转发操作不应该修改数据包本身字段，因此可以使用注释的方法，element之间仅仅查看和修改对应的目标地址注释从而确定转发路径。和目标IP地址注释一起使用的有几个方法：GetIPAddress用于从header中复制目标地址到annotation中；LookupIPRoute用于替换当前annotation到下一个IP网关地址；ARPQuerier则用于将当前annotation映射到下一个以太网地址。

2）着色（paint ）：着色element可以讲一个包标记为一个整型的“颜色”，CheckPaint可以将一个包从它的第一转发口发送出去，并在次转发口发送出该包着色以后的备份，IP路由器通过这种机制可以知道一个数据包是否是从它的接受端口发送出去，从而可以探测这种转发并触发ICMP重定向（ICMP Redirection）。

*附：什么是ICMP重定向【来源：百度百科】

ICMP重定向报文是ICMP控制报文中的一种。在特定的情况下，当路由器检测到一台机器使用非优化路由的时候，它会向该主机发送一个ICMP重定向报文，请求主机改变路由。路由器也会把初始数据包向它的目的地转发。

发生ICMP重定向通常有两种情况：

1)当路由器从某个接口收到数据还需要从相同接口转发该数据时；

2)当路由器从某个接口到发往远程网络的数据时发现源ip地址与下一跳属于同一网段时。

3）链路层广播标记（Link-level broadcast flag）：FromDevice用于设置这个标志位，表示一个包是以链路广播的形式发送过来的，当发现这类数据包将要发送至其他接口时，IP路由器使用DropBroadcast的方式来丢弃这类包。

4）ICMP参数错误指针（ICMP Parameter Problem pointer）：这个注释是由IPGWOptions设置的，用于声明该包的IP header字段中包含错误信息，并被ICMPError查看并用来生成ICMP错误信息。

5）修正IP源标记（Fix IP Source Flag）：由于ICMP Error消息包的源地址一定是发生错误的接口，但是ICMPError并不能预测这个接口，因此它发送出的数据包在该字段中使用默认值并伴随一个Fix IP Source 的注释，用于提醒沿途的FixIPSrc添加正确的源地址并重新计算校验。

还有一种情况下，状态参数的传递并不局限于elements之间，而可能是element需要获取到更为困难的全局变量，例如整个路由器在网络中的IP地址，或所处网络的广播地址，Click中的模块很多情况下必须掌握这些信息。每个模块都需要掌管一个list来存储所有这些全局信息，更为理想的情况是能自动获取这个list（例如通过FBRC）。

对于原有IP标准的一致性同时体现在Click的element本身以及elements之间的顺序上。单个的element表现为：例如CheckIPHeader会检查IP头是否符合规范且合法；IPFragment会把大于MTU的包进行分块，并把无法分块的过大的包发送到报错的端口；ICMP error 消息不会对广播包、ICMP错误消息保等进行回复。Elements之间的顺序表现为：例如DecIPTTL被安排在LookupIPRoute之后，因为只有判断这个包不是发送给自己的时候才会把TTL减1。

4. Click拓展模块

Click的转发路径上总共要经过16个模块，在这章中要展示的就是模块化带来的易于拓展的好处。

4.1 调度（scheduling）

所谓调度的意思就是让一个路由器在多个输入的情况下复用(multiplex)一个输出端口。Click中的scheduler表现为一个pull element，当这个调度器被要求发送出一个数据包时，会按照一定的算法每次从多个输入端口中选取一个端口的数据包并将其返回。目前主要实现的有三种调度器：RoundRobinSched，PrioSched和StrideSched。

RoundRobinSched顾名思义使用的就是RoundRobin规则（即轮询算法）来进行输入端口的选取；PrioSched是严格依照优先级进行调度，它始终优先传送优先级最高的输入端口，在一次传送次优先级的端口内容；StrideSched使用了stride scheduling 算法，简单来说，stride scheduling就是一种按比例分配的算法，通过设定参数使得某个输入被轮到的频率是另一个输入被轮到频率的n倍。

由于常规的队列（queue）和一个调度器（scheduler）只是在输入端口的选择上内部处理不同，但对外表现都是一样的。具体来讲，它们的输出端口都是pull类型的，因此下游element并不知道数据是从队列传来还是从scheduler传来的。所以一个scheduler可以用作一个virtual queue，从而对外表现的像一个队列但是可以实现比FIFO更复杂的数据转发机制。

4.2 丢弃机制（dropping policies）

在一个Queue的element中往往会应用一个最简单的丢弃机制，即超出队列最大容量的所有包都会被丢弃，而另一些policies可能会在Queue的这种机制基础上加以改进，如使用替换的方式。例如一个RED（Random Early Dection）的element可能会使用RED方法来drop过多的包，而这种dropping policy是独立于queue的数据存储功能的，只是在Queue基础上增加功能而已。

RED在检测到网络拥挤时有较大概率开始drop数据包。当一个队列中有很多包是发往同一链路时，该链路就被认为是拥挤的，此时RED模块就会查看路由器中各个队列的长度来决定是否要丢弃数据包，而在实际应用，RED模块往往就看下游最近的Storage element（Storage是所有具有存储功能的element向外提供的共有的接口，如queue或类似的模块都会具有Storage的接口），这种查看是通过FBRC完成的。

RED可以支持下游的多个队列（而不只是查看一个）。如果RED下游有多个队列，返回的packet count会是所有队列模块的和（一个virtual count），这种机制可以使得RED有不同的变体：

a.例如把一个RED放在scheduler的两个队列之前，则会计算这两个队列总共的数据包。

b.另一个例子是使用weighted RED，即packet会根据它们的优先级按不同的概率进行丢弃。

c.第三种情况是RED放在了queue的后面（而不是前面），这时RED表现为一个pull element并会检测上游的Storage element（而不是下游的），从而应用类似于drop-from-front RED的策略。

最简单的RED dropping功能可以通过在queue之前加RED模块来实现。

4.3 复杂拓展与简单分组

Click可以同时胜任简单或复杂的任务，一个网络管理员可以让一个Click路由器完成特定的路由功能，也可以将Click路由器部分的element用于其他应用中。

4.4 区别化服务

在Click中，边界路由器和核心路由器可以共同提供区别化服务，管理聚合的数据流。边界路由器负责将不同服务等级的数据包进行分类并打上标签，保证相应服务等级的数据流不会以过高的速率进入网络；核心路由器则通过这些标签来对流进行调度和队列管理。

上图就是一个区别化服务的具体应用框架。输入的数据包通过IP头部的DSCP(Diffierentiated Services Code Point)字段来划分为4个不同的traffic streams。前三个（A,B,C）流是速率受控（rate limited）即提供保障的流，第四个（D）是提供最普通的尽力而为服务的数据流。具体来说：A通过使用dropping机制来达到速率控制，既当每秒有超过7500个包到达时就会把多于的包丢弃；B是使用shaper进行整形，每秒允许10000个包通过shaper，多的包则存在前面的queue中；C是使用重分类（reclassification）机制，即超过设定数量的包会被重新标记为D类，降级进行尽力而为的传输。

4.5 以太网交换机

Click也可以用来构造非IP层的交换机，如下图中给出的就是一个符合IEEE 802.1d标准的以太网交换机。

该交换机自身以学习网桥（learning bridge）的方式运行，并可以和其他的802.1d网桥一起在网络中运行生成树协议。在该交换机中，EthernetSwitch提供简单的学习网桥功能，EthernetSpanTree和Suppressor两个element则只是为了当LAN中存在多个交换机时防止环路的发生。其中EthernetSpanTree使用IEEE802.1d协议来为网络构建生成树，Suppressor用于控制将一个数据包从某一个特定的端口转发出去，同时Suppressor也对外提供方法接口来*或解锁一个特定的端口，所有到达Supressed的端口都会被丢弃（就是STP中的Block状态）。需要注意的是，Supressors无法通过FBRC来找到，因此使用者必须使用配置字符串(configuration string)使用名字来定位到它（在第二章提过）。

5. 内核环境

Click的核心线程是运行在linux2.2内核基础上的，核心线程启动路由器驱动并从而运行task queue中的多个任务。理论上只有中断才可以占据一个运行的线程，但是出于对系统交互性(responsive)的考虑，Click会主动每隔一段时间将线程控制权交还于Linux来执行一些系统级操作。一般来说，在一个时间内只会有一个driver thread在运行，但是在thread初建立时可能会存在多个driver thread其中包含一个新线程和多个将要过期的老router thread。

Click运行在linux内核中，并使用linux的proc文件夹与用户进行交互。如果想要编写一个Click路由器，开发者可以将写好的代码放在proc/click/config文件夹中。当安装配置时，Click会在proc/click为每个element创建子文件夹，其中包含了每个element的handler(2.6中提到)。

一个Click路由器中包含有四种对象类别：

1） Elements： 系统为每一个当前运行的element生成一个element对象。

2） Router： 一个router object会根据给定的router配置收集相关信息，包括配置elements，检查connections，将router上线，并管理任务队列。

3） Packets：Click的packet数据存储于内存块中，packet数据使用写时拷贝技术（copy-on-write），即当需要copy一个packet时，系统只会copy这个包的header而不会copy它的data。注释会以固定顺序存储于packet的header中，且无法动态增加新的注释。

4）Timers： 在Linux内核中，Click的timer通过Linux的timer queue来实现，在一个Intel PC上可以由0.1s的分辨率。

5.1Poll和设备处理

最原始的Click是和Linux共享中断机制和设备处理。虽然Click的宗旨还是尽量少的修改Linux，但是中断的开销和对于设备处理会很大程度影响performance，而且Click运行在较中断更低的优先级上，因此会导致“活锁“现象（livelock），即当input变多的时候，中断处理就会渐渐starve其他的操作，从而减少吞吐量。

现在的Click使用Polling代替了interrupt。用于设备处理的element（也就是FromDevice和ToDevice）将它们自己放在task queue中。Fromdevice会查看（poll）它的receive DMA queue是否有新到达的packets，如果有就依照configuration来push这些packet；ToDevice会检查它的device transmit DMA queue来看是否有空的slot，如果有的话就从它的input中pull出packets并装填进queue中。由于这种内部运作机制，两端的设备本身永远不会调用中断，从而使用Polling机制解决了中断问题。不过，虽然由于中断调用的过分昂贵，在低强度的工作环境下，传统的中断还是被允许的。

由于这种Polling机制，Click会在原来的linux结构上有所调整，包括增加中断的开关控制，查看接收数据包，以及清理transmitted DMA ring.