TinyOS CTP协议分析

【转自】http://qy.nwpu.info/?p=22

CTP论文：http://www.tinyos.net/tinyos-2.x/doc/html/tep123.html

               http://sing.stanford.edu/gnawali/ctp/

摘要：
本文档描述了CTP（汇聚树协议），它提供到网络中根节点的尽力、任意播数据报通信。

1、简介：
2、假设和限制
CTP是基于树的汇聚协议。网络中的一些节点将自己设为根节点。节点之间形成到根节点的树的集合。CTP是没有地址的，节点并不是向固定的根节点发送数据包，而是通过先择下一跳隐式地选择根节点。节点根据路由梯度形成到根的路由。
CTP协议假设链路层提供了以下功能：
(1) 提供有效的本地广播地址
(2) 为单播包提供同步的确认信息
(3) 提供协议分派字段以支持多种高层协议
(4) 具有单跳的源和目的地址字段
CTP假设它有一部分附近邻居节点的链路质量估计信息。该信息提供了本节点与某一邻居节点之间的通信过程中成功地传输了单播凶的次数。
CTP有一些提高传输可靠性的机制，但它并不保证100%可靠。它是尽力的，但有时即使尽力了也未必能办到。
CTP是为通信量相对较低的网络设计的。带宽有限的系统可能使用别的协议更合适，比如能将多个小的帧组装成单个数据链路层包的协议。

3、汇聚与CTP
CTP使用期望传输值（ETX，Expected Transmissions）作为路由梯度。根节点的ETX为0，其它节点的ETX为其父节点的ETX值加上到父节点链路的ETX值。这种相加的方法需要假设节点使用链路层重传。给出一种有效的路由，CTP选择ETX值最小的一种。ETX值用精度为0.01的16位定点实数表示。若ETX值为451则表示ETX为4.51，同样ETX值为109表示ETX为1.09。
路由循环是可能在CTP网络中出现的问题之一。路由循环通常发生在节点选择的路由的ETX值比原来的大的多的情况下，这可能是因为与侯选的节点失去连接造成的。如果它是新的路由选择的节点，那就产生了路由循环。
CTP通过两种方法处理路由循环。第一种是每个CTP包含有当前节点的ETX值，如果CTP接收到比自己的ETX值小的数据帧，则说明树中有不一致。CTP通过广播一个信息帧以期解决这种不一致性，希望发送这个数据帧的节点收到并相应地调整它的路由。如果一部分节点被隔开，那么它们会形成ETX值无限的死循环。CTP的第二种机制是不考虑ETX值大于一个固定常量的路由，这个值取决于实现。
包重复是CTP中可能发生的另外一个问题。包重复发生在节点收到一个数据帧，并回复一个ACK，但ACK中途丢失的情况。发送者将重传这个包，而接收者又将收到它。这在多跳中是灾难性的，因为重复是指数级的。例如，每跳产生一个重复，则第一跳有两个包第二跳四个，第三跳八个……
同时路由循环使重复抑制变得更复杂，因为路由循环可能使节点合法地收到一个包一次或多次。因此，如果仅仅根据源地址和顺序号，路由循环中的包可能被丢弃。因此，CTP数据帧具有一个已存活时间（THL，time has lived）字段，每过一跳都对该字段加1。链路层重传具有相同的THL值，但路由循环中的包就不会如此了。

4、CTP数据帧
CTP数据帧式如下：

1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P|C| reserved  |      THL      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|              ETX              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|             origin            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     seqno     |   collect_id  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    data ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

各字段定义如下：
- P：拉路由位。P位允许节点从其它节点请求路由信息。如果节点收到一个P位置位的包，它应当传输一个路由帧。
- C：拥塞标志位。如果节点丢弃了一个CTP数据帧，它必须在下一个传输的数据帧中置C位。
- THL：已存活时间。当节点产生一个CTP数据帧时，它必须设THL为0。当节点接收到一个CTP数据帧时，它必须增加THL值。如果节点接收到的数据包THL为255，则将它回绕为0
- ETX：单跳发送者的ETX值。当节点发送一个CTP数据帧时，它必须将到单跳目的地的路由ETX值填入ETX字段。如果节点接收到的路由梯度比自己的小，则它必须准 备发送一个路由帧。
- origin：包的源地址。转发的节点不可修改这个字段。
- seqno：源顺序号。源节点设置了这个字段，转发节点不可修改它。
- collect_id：高层协议标识。源节点设置了这个字段，转发节点不可修改它。
- data：数据负载。0个或多个字节。转发节点不可修改这个字段。
origin,seqno,collect_id合起来标识了一个唯一个源数据包，而origin,seqno,collect_id,THL合起来标识了网络中唯一一个数据包实例。两者的区别在路由循环中的重复抑制是很重要的。如果节点抑制源数据包，则它可能丢弃路由循环中的包；如果它抑制包实例，则它允许转发处于短暂的路由循环中的包，除非THL凑巧回绕到与上次转发时相同的状况。

5、CTP路由帧
CTP路由帧格式如下：

1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P|C| reserved  |      parent   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     parent    |       ETX     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|      ETX      |
+-+-+-+-+-+-+-+-+

各字段意义如下：
- P：与数据帧相同
- C：拥塞标识。如果节点丢弃了一个CTP数据帧，则必须将下一个传输路由帧的C位置位。
- parent：节点的当前父节点
- metric(ETX)：点的当前ETX值
当节点接收到一个路由帧时，它必须更新路由表相应地址的ETX值。如果节点的ETX值变动很大，那么CTP必须传输一个广播帧以通知其它节点更新它们的路由。与数据帧相比，路由帧用父节点地址代替了源节点地址。父节点可以发现子节点的ETX值远低于自己的ETX值的情况，并准备传输一个路由帧。

6、实现
CTP的一种实现可以在tos/lib/net/ctp目录中找到。本节描述了该实现的架构，但这并不是CTP的规范说明。
该实现由三个主要的子组件：
(1) 链路质量估计器，负责估计单跳的ETX值
(2) 路由引擎，它根据链路估计和网络层的信息（如拥塞情况）来决定哪个邻居节点作为路由的下一跳
(3) 转发引擎，它维护发送包队列，决定是否发送和发送的时机。它的名字有点令人混淆：转发引不仅要转发从其它节点过来的数据包，同时也要发送自己产生的数据包。
6.1 链路估计
该实现使用两种机制来估计链路质量：周期性的LEEP包和数据包。该实现使用LEEP包作为信息帧。这些包中填入邻居节点地址和相应的ETX值。信息帧的发送速率由一种与trikle dissemination协议类似的算法计算，它根据网络的状况动态地计算。信息帧使用一个以指数级随机递增的定时器控制发送，当发生以下状况之一时，该实现重置定时器为一个较小的值。
(1) 路由表为空（这也将设置P位）
(2) 在>=1次传输后ETX值增大
(3) 节点收到一个P位置位的包
该实现通过数据传输改变对LEEP的链路估计。这是计算ETX最直接的方法。当数据通路传输一个数据包时，它千知链路估计器传输的目的地和传输成功与否。估计器对每5次传输产生一个ETX估计值，ETX为6表示一次也没传成。
估计器通过指数权重的移动平均线合并信息帧的ETX值和数据估计产生的ETX值。基于信息帧的估计会填充邻居表。期望的状况是在已称定的网络中，较低的信息帧速率意味着对选定的路由来谘，数据估计占的比重比信息帧估计的大。
此外，CTP收集数据估计的速率与传输速率是成比例的，因此它可以快速地检测到断开的连接并切换到新的侯选邻居节点。
组件tos/lib/net/le/LinkEstimatorP实现了链路估计器。它结合了基于LEEP和数据的估计。
6.2 路由引擎
该实现的路由引擎负责选择数据传输的下一跳。它记录了链路估计表中所维护节点的一个子集的路径ETX值。最小耗费的路由即路径ETX值和连接ETX值之和最小的那条。因此路径ETX值整条路由的连接ETX值。组件tos/lib/net/ctp/CtpRoutingEngineP实现了该路由引擎。
6.3 转发引擎
组件tos/lib/net/ctp/CtpForwardingEngineP实现了转发引擎。它具有以下5种职责：
(1) 向下一跳传递包，当需要时重传，并根据是否收到ACK向链路估计器传递相应信息。
(2) 决定何时向下一跳传递包
(3) 检测路由中的不一致性，并通知路由引擎
(4) 维护需要传输的包队列，它混杂了本地产生的包和需要转发的包。
(5) 检测由于丢失ACK引起的单跳重复传输
转发的四个关键函数为包接收(SubReceive.receive())，包转发(forward())，包传输(SendTask())和决定传完之后做什么(SubSend.sendDone())。
reserve函数决定节点是否转发一个包。它有一个缓冲区保存了最近收到的包，通过检查这个缓冲区可以确定它是否是重复的。如果不是，则调用转发函数。
转发函数格式化需要转发的包。它检查收到的包是否有路由循环，检查传输队列中是否有足够的空间，如果没有，则丢弃该包并置C位。如果传输队列为空，则post Send任务。
Send任务检查位于传输队列头部的包，为到下一跳的传输作好准备（请求路由层的路由信息），并提交到AM层。
当发送结束时，sendDone检查发送的结果。如果包被确认，则将包从传输队列中拽出。如果包是本地产生的，则将sendDone信号向上传。如果包是转发的，则将包返回到转发消息缓冲池。如果队列中还有剩余的包（比如没有被确认的），它启动一个随机定时器以重新post这个任务。该定时器实质上用于限制CTP的传输速率，不让它尽快地发包，这是为了防止在通路上自我冲突。