4.2 基于反向路径转发的拓扑分发（TBRPF）协议

4.2.1 TBRPF协议术语及其应用范围

1.TBRPF协议术语

TBRPF协议的描述使用了如下术语：

（1）节点（Node）。实现了TBRPF协议的路由器。

（2）路由器身份识别码ID（Router ID，RID）。通过一个唯一的32比特的RID识别每个路由器。对于IPv4，RID等于其某个接口的IP地址。术语“节点u”表示其RID等于u的那个节点。

（3）接口（Interface）。一个节点与通信设备或者媒介的连接，该节点通过该连接能够与其他节点进行通信。一个节点可以有多个接口。一个接口可以是无线的或者有线的，以及可以是广播的（例如以太网）或者点对点的。每个接口通过其IP地址来识别。术语“接口I”表示IP地址等于I的接口。

（4）链（Link）。一条链（或者称为链路）是一对按顺序排列的接口（I，J），接口I和J处在两个不同的节点上，并且接口I最近已经接收到从接口J发送来的分组。假如节点i有接口I、节点j有接口J而使得（I，J）是一条链，那么就说从节点i到节点j存在一条链（i，j）。节点i叫做链（i，j）的“头”，节点j叫做链（i，j）的“尾”。

（5）双向链（Bidirectional Link）。指由一对能够相互接收到对方信息的接口I和J组成的一条链（I，J）。也叫做对称（2-Way）链。

（6）相邻节点（Neighbor Node）。假如节点i能够从某个接口上接收到节点j发送的信息，那么就说节点j是节点i的一个相邻节点。假如节点i和j之间存在一条双向链，那么就说节点j是一个双向相邻节点（即除了节点j是节点i的一个相邻节点，反之节点i也是节点j的一个相邻节点）。

（7）MANET接口（MANET Interface）。指任何无线接口，使得两个相邻节点在该接口上不必互为对方的相邻节点。MANET节点一般至少有一个MANET接口，但这并不是一种要求。

（8）拓扑（Topology）。一个网络的拓扑由一张图 G=(V，E)来描述，其中 V 是该网络中各个节点组成的集合，E是该网络中各条链（u，v）组成的集合。

（9）源节点树（Source Tree）。指由每个节点计算出来的定向树（用T表示），该树提供到达所有其他可达节点的最短路径。

（10）拓扑更新（Topology Update）。指报告一条或者多条链的状态的一条消息。

（11）父节点（Parent）。节点i关于节点u的父节点就是所计算出来的从节点i到达节点u的最短路径上的下一跳节点。

（12）前一跳节点（Predecessor）。节点v在源节点树上的前一跳节点就是这样一个节点u，节点u使得链（u，v）在该源节点树上。

（13）树叶节点（Leaf Node）。一棵源节点树的一个树叶节点就是该源节点树上的这样一个节点，该节点不是该源节点树上任何其他节点的前置节点。

（14）主动式路由协议（Proactive Routing Protocol）。指这样一类路由协议：使用这类路由协议的每个节点始终不停地维护到达所有可达目的节点的路由，而不论当前是否有分组需要交付给这些目的节点。与主动式路由协议正好相反的是，“按需”路由协议只有当需要的时候才寻找和维护路由。

2.TBRPF协议应用范围

TBRPF是一个主动式路由协议，是为MANET设计的。TBRPF协议支持的网络节点数高达数百个，可以与分层路由技术结合起来支持更大规模的网络。由于TBRPF协议使用了一些可以大幅度降低控制传输的技术，所以TBRPF协议能够支持比基于经典链路状态算法的路由协议（例如OSPF）规模更大、节点密度更高的网络。

TBRPF协议能够支持的网络节点数量取决于几个因素，其中包括MAC数据速率、拓扑变化速率，以及网络密度（平均相邻节点数量）。仿真已经表明，TBRPF协议能够支持500个节点。在使用IEEE 802.11 MAC协议、数据速率2Mb/s对100个节点和20个传输流（源）进行仿真的过程中，发现TBRPF协议在所考虑的各种仿真实验下产生大约80～120kb/s的路由控制流量，这与其他MANET路由协议是非常可比拟的。

3.IANA考虑

IANA已经为TBRPF协议分配了端口712。

本规范（RFC3684）指定的TBRPF泛洪机制使用IPv4多目标地址224.0.1.20，这个地址当前被IANA分配用于“任何专用实验”。由于本规范先于标准轨，为此将申请一个新的多目标地址。

4.2.2 TBRPF概述

TBRPF协议由两个主要模块组成：相邻节点寻找模块和路由模块（进行拓扑寻找和路由计算）。

1.相邻节点寻找概述

TBRPF协议的相邻节点寻找（TBRPF Neighbor Discovery，TND）协议允许每个节点i迅速检测出相邻节点j，这样在节点i的接口I和节点j的接口J之间存在一条双向链（I，J）。TND协议也能够迅速检测出一条双向链是否中断或者变成一条单向链。

TND协议的主要特征是TND协议使用“差异（differential）”HELLO消息，该消息只报告链路状态中已经发生变化的那部分。这就使得TBRPF协议具有比其他链路状态路由协议（例如OSPF）少得多的HELLO消息，后者的每条HELLO消息包含所有相邻节点的身份识别码IDs。所以，可以以更加快的速率发送HELLO消息，从而能够更加快地检测出拓扑的变化。

TND协议采用全模块化设计，与路由模块无关。TND协议只进行相邻节点的检测，即只确定哪些节点是一跳相邻节点。特别是TND协议不寻找二跳相邻节点（这由路由模块来完成）。因此，其他路由协议可以使用TND协议，TBRPF协议也可以使用其他相邻节点寻找协议（例如链路层提供的协议）代替TND协议。

具有多个接口的节点分别在各个接口上单独运行TND协议，这与OSPF协议类似。因此，为每个本地接口维护一张相邻节点表格，在某个特定的接口上发送的一条HELLO消息只包含在该接口上所接收到的相邻节点的信息。

在无线网络中，一个单独接口I可能接收到同一个相邻节点的多个接口J上的分组。例如，假如一个相邻节点使用具有多个接口代表不同波束的一根定向天线时就可能发生这种情况。因为这个原因，所以TBRPF协议在其HELLO消息中包含有相邻节点接口地址信息，这与OSPF协议不同，OSPF协议的HELLO消息只包含路由器身份识别码ID。

每个TBRPF节点为每个本地接口I维护一张相邻节点表格，该表格存储有在该本地接口I上接收到的每个相邻节点接口J的状态信息，即接口I和一个相邻节点接口J之间的每条链（I，J）的状态信息。每条链的状态可以为单向（1-Way）、双向（2-Way）或者丢失（LOST）。接口I的相邻节点表决定了在接口I发送的HELLO消息的内容，并且根据在接口I上接收到的HELLO消息（以及可能的链路层通知消息）进行更新。

每个TBRPF节点在每个HELLO_INTERVAL（HELLO消息发送周期时间）内最多（在每个接口上）发送一条HELLO消息。每条HELLO消息包含三个相邻节点接口地址列表（有可能是空的）：相邻节点请求（NEIGHBOR REQUEST）、相邻节点应答（NEIGHBOR REPLY）、相邻节点丢失（NEIGHBOR LOST）。每条HELLO消息还包含当前HELLO序列号（HELLO Sequence Number，HSEQ），每发送一条HELLO消息就将HSEQ加1。

在下列TND协议的概述中，假定接口I属于节点i、接口J属于节点j。当一个节点i改变链（I，J）的状态的时候，节点i就将相邻节点接口地址J写入到在接口I上连续发送的最多NBR_HOLD_COUNT（典型值为3）条HELLO消息中的某个列表（NEIGHBOE REQUEST/REPLY/LOST）中。这样可以确保节点j从接口J上至少接收到所发送的这些HELLO消息中的一条，或者丢失NBR_HOLD_COUNT条HELLO消息而声称链（J，I）已中断。这种技术使得一个节点没有必要无限期地将每个单向相邻节点或者双向相邻节点包含在HELLO消息中，这与OSPF协议不同。

为了避免建立寿命可能很短的链（即使用滞后作用），节点i必须在接口I上最近从相邻节点接口J发送来的HELLO_ACQUIRE_WINDOW（例如3）条HELLO消息中至少接收到HELLO_ACQUIRE_COUNT（例如2）条后，才能够声称链（I，J）是单向链。当发生这种情况的时候，节点i就将相邻节点接口地址J写入到随后在接口I上所发送的NBR_HOLD_COUNT条HELLO消息中的每条HELLO消息的NEIGHBOR REQUEST列表中，或者直到在接口I上接收到从相邻节点接口J发送来的包含接口I的一条相邻节点应答（NEIGHBOR REPLY）消息时为止。

假如节点j从接口J上接收到从接口I发送来的HELLO消息中的一条，并且该条HELLO消息的NEIGHBOR REQUEST列表包含接口J，那么节点j声称链（J，I）是双向链（除非已经是双向链），并且将接口I写入到随后在接口J上所发送的NBR_HOLD_COUNT条HELLO消息中的每条HELLO消息的NEIGHBOR REPLY列表中。节点i从接口I上接收到这些HELLO消息中的一条后，声称链（I，J）是双向链。

假如节点i从接口I上接收到一条HELLO消息，该条HELLO消息是从相邻节点接口J发送来的，其HSEQ指出至少NBR_HOLD_COUNT条HELLO消息已经被丢失；或者假如节点i在NBR_HOLD_TIME秒时间内没有从接口I上接收到从接口J发送来的任何HELLO消息，那么节点i将链（I，J）的状态改为丢失（LOST）（除非该条链已经丢失），并且将接口J写入到随后在接口I上所发送的NBR_HOLD_COUNT条HELLO消息中的每条HELLO消息的NEIGHBOR LOST列表中（除非链（I，J）的状态在完成这些HELLO消息传输之前发生了变化）。节点j或者从接口J上接收到所发的这些HELLO消息中的一条，或者丢失NBR_HOLD_COUNT条HELLO消息；对于这两种情况的任何一种，节点j都将声称链（J，I）已丢失。这样，两个节点i和j共同认为接口I和J之间的链不再是双向链，即使节点j仍然能够接收到节点i发出的HELLO消息也是如此。

每个节点可能为从一个本地接口I到达一个相邻节点接口J的每条链维护和更新一个或者多个用于表示该条链质量的链路参数。这些链路参数可以用作改变一个相邻节点的状态的附加条件，根据链路参数在门限值上下的变化改变相邻节点的状态。TBRPF协议允许将链路参数写入到拓扑更新消息而被广播，以及使用链路参数计算最短路径。

2.路由模块概述

运行TBRPF协议的每个节点维护一棵源节点树（用T表示），源节点树T提供到达所有可达节点的最短路径。每个节点根据其拓扑表中存储的部分拓扑信息，使用DIJKSTRA算法修改版计算和维护其源节点树。为了使开销最低，每个节点只将其源节点树的部分信息传输给相邻节点。

一个节点向其相邻节点发送的那部分源节点树T叫做“报告子树（Reported Subtree）”，用RT表示。每个节点以周期性（例如，以5 秒钟为周期）拓扑更新方式向其相邻节点发送RT，以更快的差异更新方式（例如，每隔1秒钟）向RT发送变化信息（添加和删除）。周期性更新将RT发送给新相邻节点，确保每个相邻节点即使在没有接收到所有更新的条件下也能最终获悉RT。差异更新（Differential Updates）确保每个拓扑更新快速传播到受到本更新影响的所有节点。所接收到的一个拓扑更新不会被转发，但是可能会引起RT的变化，在下一次差异更新或者周期性更新中将报告这个RT变化。只要可能，就将拓扑更新包含在同一个分组（例如同一条HELLO消息）之中，以便使所发送的控制分组数量最少。TBRPF协议不要求消息的可靠交付或者按序交付，也不使用ACKs和NACKs。

TBRPF协议支持多个接口、多个有关主机、多个网络前缀。类似于拓扑更新的发送方式那样，有关接口、主机、网络前缀的信息也是按照周期性更新方式或者差异更新方式被有效地发送。

报告子树RT由源节点树T的各条链（u，v）组成，节点u属于“报告节点集（Reported Node Set，RN）”。RN计算如下：当且仅当节点i确定其一个相邻节点可能选择自己作为其到达目的节点j的最短路径的下一跳的时候，节点i将相邻节点j放入RN集中。为了做出这个决策，节点i计算2跳的最短路径，从每个相邻节点到达每个其他相邻节点，只使用节点i的相邻节点（或者节点i本身）作为中间节点，使用转发优先权（包含在HELLO消息中）和RID做出判决。在一个节点确定哪些相邻节点属于RN集之后，当且仅当到达每个可达节点u的最短路径上的下一跳节点属于RN集，那么每个可达节点u属于RN集。一个节点本身还属于RN集。结果是RT包含T的子树，子树的根部在属于RN集的相邻节点，RT还包含到达相邻节点的所有本地链。

需要注意的是：RN集中的相邻节点类似于多点中继（MPR）选择器。因此，假如节点i选择RN集中的相邻节点j，那么节点i有效选择自己作为相邻节点j的一个MPR。这极不同于OLSR协议。在OLSR协议中，节点不会选择自己作为一个MPR，而是选择其相邻节点的一个子集作为MPRs。

一个具有较高转发优先权的节点报告其源节点树的较大一部分信息（平均来讲），并且很可能被其相邻节点选择为下一跳转发节点。一个转发优先权等于0 的节点叫做非转发节点，从不转发其他节点产生的分组。

TBRPF协议没有在拓扑更新中使用序列号，因此减少了消息开销，避免了序列号返转问题。但是，TBRPF协议使用一种类似于SPTA的技术，对于一个或者多个相邻节点所报告的每条链（u，v），就该条链的状态只认可到达节点u的下一跳p(u)。（但是，在SPTA中，每个节点报告完整的拓扑）。每个节点使用这种技术维护一张拓扑图（Topology Graph，TG），并按照属于TG的最短路径树计算T，TG包含最近所认可的各条链。为了允许立即重新选择路由，假如节点p(u)变成一个没有报告该条链的相邻节点，那么临时放宽TG中的每条链（u，v）必须被节点p(u)所报告的这一约束条件。

每个节点被要求报告RT，但是也可以报告其他链路，例如，为高速移动网络提供增强的强壮性。更为精确地说，一个节点可以维护包含源节点树T的TG的任何子图H，可以报告报告子图（Reported SubgrapH，RH），RH包含子图H的各条链（u，v），节点u属于RN集。例如，子图H可以等于TG，假如所有节点参与的话，那么子图H为每个节点提供完整的网络拓扑。子图H还可以是一张包含源节点树T的双向连通（Biconnected）子图，假如所有节点参与的话，那么子图H为每个节点提供两条不相交路径到达每个其他节点。

TBRPF协议允许在拓扑更新中包含链路参数的选项，并且根据链路参数计算最短路径。这就允许沿着比最少跳数路径质量更高的路径发送分组。

可以对路径最优化进行折中，以降低大规模网络中的控制通信量，近似程度由可配置参数NON_TREE_PENALTY决定。

4.2.3 TBRPF分组

各个节点按照分组方式发送TBRPF协议数据。每个分组包含一个分组头、若干个可选的分组头扩展域，以及一个由一条或者多条消息和所需的填充选项组成的分组实体。为了帮助接收方高效处理，发送方应该插入必需的填充选项，在TBRPF分组里排放多字节字，各个字之间自然隔开（即，对于64/32/16比特字分别为模8/4/2的地址）。无论多字节字是否按照自然分隔方式排放在一起，接收方都必须能够处理多字节字。下面详细说明TBRPF协议的各个组成部分。

1.TBRPF分组头

TBRPF分组头的长度可变（最小一个字节）。TBRPF分组头的格式如图4-7所示。

各组成域含义如下：

（1）版本号（Version）（4比特）：表示TBRPF协议的版本号。本版本号等于4。

（2）标志（Flags）（4比特）：两个比特（L，I）说明随后有哪些分组头扩展（假如有的话）。两个比特（R，R）保留为今后使用，必须设为0。由这些比特指定的任何分组头扩展必须按照这些比特的顺序（即，首先L，然后I）排列如下：

① L：表示所包含的长度。假如低层交付服务提供一个长度域，那么发送方可以设置L=0，并且省略长度扩展。否则，发送方必须设置L=1，并且在任何前一个分组头域之后紧接一个16比特的无符号整数长度。长度包含所有的分组头和数据的字节数，按照网络字节顺序写入长度域中。

接收方通过检测L比特来确定长度域是否存在。假如L=1，那么读取长度域的信息，用于确定TBRPF分组的长度，其中包括TBRPF分组头的长度。假如低层交付服务和TBRPF分组头均没有提供分组长度，那么接收方丢掉所有这样的TBRPF分组。

② I：表示所包含的路由器身份识别码（RID）。假如低层交付服务对发送方的RID进行了编码，那么发送方可以设置I=0，并且省略RID域。否则，发送方必须设置I=1，并且在任何前一个分组头域之后紧接一个按照网络字节顺序排列的4 字节的RID。RID选项提供一种固有的网络层地址解析机制。检测到RID选项的接收方应该为出现在网络层头部的RID和源节点地址之间建立一种绑定关系（即约束关系）。

（3）保留（Reserved）：保留为今后使用，必须设为0。

2.TBRPF分组实体

TBRPF分组实体由一条或者多条TBRPF消息（以及所必需的填充选项）组成，各条消息按照串行方式一条接着一条。TBRPF分组实体中的消息和填充选项的编码如图4-8所示。

各组成域含义如下：

● 选项（OPTIONS）（4比特）：4个选项比特取决于类型（TYPE）。

● 类型（TYPE）（4比特）：消息类型或者填充选项的标识符。

● 取值（VALUE）：这是一个长度可变的组成域（其格式和长度取决于类型，随后有描述。）

必须严格按照TBRPF分组实体中的组成顺序处理各个组成部分的排列顺序；例如，接收方在处理所有前面的组成部分之前不必通过扫描整个分组实体来寻找某个特定的组成部分。TBRPF分组组成部分包含如下描述的填充选项和消息。

1）填充选项（类型=0～1）

发送方在必要的时候可以插入两种类型的填充选项。例如，为了满足其他组成部分的排列要求而插入填充选项。填充选项可以出现在TBRPF分组实体中的任何位置。下面定义两种填充选项：

第一种填充选项Pad1将一个字节的填充码插入TBRPF分组实体，省略取值域，如图4-9所示。假如需要多个字节的填充码，那么应该使用下面描述的第二种填充选项PadN，而不是使用多个第一种填充选项Pad1。

第二种填充选项PadN将二个或者更多字节的填充码插入TBRPF分组实体，如图4-10所示。取值（VALUE）域的第一个字节包含一个8比特的无符号整数长度域（LEN），其取值为0～253，说明随后紧接跟随的取0值的字节数量，最多可以插入255个填充字节。

2）消息（类型=2～10）

随后几节描述出现的其他消息类型。发送方按照单个消息格式对消息进行编码。接收方检测消息结构中的错误，例如，类型未被认可的消息、组成部分不完整的消息，或者组成部分少于所指定数量的消息等。在所有情况下，接收方检测到一个错误后，必须停止处理当前的TBRPF分组，丢掉所有未被处理的组成部分。

4.2.4 TBRPF相邻节点寻找

TBRPF相邻节点寻找（TBRPF Neigbor Discovery，TND）协议允许每个节点快速检测本地接口I和一个相邻节点接口J之间的双向链（I，J），以及快速检测这种链的丢失。TND协议和路由模块之间的接口由TND协议维护的相邻节点表和三个规程Link_Up(I，J)、Link_Down(I，J)、Link_Change(I，J)共同定义，TND协议通过规程Link_Up(I，J)声称出现一条新链，通过规程Link_Down(I，J)声称丢失一条链，通过规程Link_Change(I，J)声称一条链的参数发生了变化。

1.HELLO消息格式

HELLO消息有以下三个子类型：

● 相邻节点请求（NEIGHBOR REQUEST）（TYPE=2）；

● 相邻节点应答（NEIGHBOR REPLY）（TYPE=3）；

● 相邻节点丢失（NEIGHBOR LOST）（TYPE=4）。

每条HELLO消息的格式如图4-11所示。

各组成域含义如下：

（1）序列号（HSEQ）（8比特）：表示本条HELLO消息的序列号。

（2）优先级（Pri）（4比特）：这是一个取值在0～15之间的整数，表示发送节点的转发优先权。转发优先权较高的节点很可能被选为路由的下一跳节点。0保留为非转发节点使用，即，从不转发其他节点产生的分组的节点的转发优先权等于0。正常操作下的一个路由器的转发优先权应该等于7。路由器可以动态改变其转发优先权，例如，当其能量快要耗尽的时候。

（3）n（12比特）：表示本条HELLO消息中32比特相邻节点接口地址。

一条HELLO消息包含按照串行方式先后排列在一起的一条相邻节点请求消息、一条相邻节点应答消息、一条相邻节点丢失消息，假如相邻节点接口地址列表是空的，那么省略最后两条消息。因此，一条HELLO消息总是包含一条相邻节点请求消息（可能是空的）。

2.相邻节点表格

每个节点为其每个本地接口I维护一张相邻节点表，用于存储每个相邻节点接口J的状态信息，最近通过接口I从每个相邻节点接口J接收到HELLO消息。相邻节点表中接口I的相邻节点接口J条目包含如下变量：

● nbr_rid(I，J)：关于相邻节点接口J的一个节点的路由器身份识别码ID。

● nbr_status(I，J)：表示链（I，J）的当前状态，可以是丢失、单向、双向三种状态中的一种。

● nbr_life(I，J)：表示假如再也没有从接口J接收到HELLO消息，那么在必须将nbr_status(I，J)变成丢失状态之前剩余的时间（秒）。只要从接口I接收到从接口J发送来的一条HELLO消息，则设置NBR_HOLD_TIME。

● nbr_hseq(I，J)：表示最近从接口I接收到从接口J发送来的一条HELLO消息的序列号HSEQ，用于确定已经丢失的HELLO消息的数量。

● nbr_count(I，J)：表示必须在接口I上发送的包含接口J的相邻节点请求消息/相邻节点应答消息的剩余时间。

● hello_history(I，J)：表示最近从接口I接收到从接口J发送来的HELLO_ACQUIRE_WINDOW条HELLO消息的序列号列表。

● nbr_metric(I，J)：这是对链(I，J)的质量的一个可选测量，由位于1～255之间的一个整数表示，取值越小表示质量越好。假如没有使用这个选项，那么使用默认值1。

● nbr_pri(I，J)：表示跟接口J有关的本节点的转发优先权。

假如在最近的2×NBR_HOLD_TIME时间内没有从接口I接收到从接口J发送来的HELLO消息，那么可以删除相邻节点表中接口I的接口J条目。（当正在发送包含接口J的相邻节点丢失消息时，可以继续发送）。相邻节点表中没有一个给定接口J的条目等效于一个nbr_status(I，J)=LOST和hello_history(I，J)=NULL的条目。

nbr_status(I，J)的三种可能取值具有如下非正式意义（准确的意义由协议定义）：

● 丢失（LOST）：接口I最近没有从接口J接收到足够的HELLO消息。

● 单向（1-WAY）：接口I最近从接口J接收到足够的HELLO消息，但是本条链不是双向链。

● 双向（2-WAY）：接口I最近从接口J接收到足够的HELLO消息，同时接口J最近从接口I接收到足够的HELLO消息。

3.HELLO消息的发送

每个节点必须在每个HELLO_INTERVAL时间间隔内在每个本地接口上至少发送一条HELLO消息。HELLO消息的发送频率可以更快（例如，为了更快地检测拓扑变化）。但是，为了避免在一个停止接收HELLO消息的相邻节点将其链的状态改变到LOST状态之前可能出现HSEQ返转到相同序列号的问题，两条连续发送（在一个给定接口上发送）的HELLO消息之间的间隔时间必须大于NBR_HOLD_TIME/12秒。

为了避免控制消息的同步（控制消息可能产生碰撞），不应该按照等间隔时间发送各条HELLO消息。为了做到这一点，节点可以选择连续发送的HELLO消息的间隔时间为HELLO_INTERVAL-jitter，抖动时间差jitter从[0，MAX_JITTER]之间随机选择。

每条HELLO消息总是包含一条相邻节点请求消息，即使相邻节点地址列表是空的也是如此。相邻节点请求消息包含HSEQ（模256），每当发送一条HELLO消息的时候就将HSEQ加1。假如相邻节点地址列表不空，则HELLO消息还包含一条相邻节点应答消息和一条相邻节点丢失消息。按照以下步骤在节点i为每个接口I确定这三种消息的内容：

（1）对于每个使nbr_status(I，J)=LOST和nbr_count(I，J)>0的接口J，相邻节点丢失消息中包含接口J，递减nbr_count(I，J)。

（2）对于每个使nbr_status(I，J)=1-WAY和nbr_count(I，J)>0的接口J，相邻节点请求消息中包含接口J，递减nbr_count(I，J)。

（3）对于每个使nbr_status(I，J)=2-WAY和nbr_count(I，J)>0的接口J，相邻节点应答消息中包含接口J，递减nbr_count(I，J)。

假如一个节点重新启动，那么删除相邻节点表中的全部条目，然后该节点必须确保（对于每个接口）至少满足以下两个条件中的一个：

（1）重新启动之后发送的第一条HELLO消息与重新启动之前最后发送的一条HELLO消息之间的时间差至少等于2×NBR_HOLD_TIME。

（2）设HSEQ_LAST表示重新启动之前最后发送的一条HELLO消息的序列号，将重新启动之后发送的第一条HELLO消息的序列号设为HSEQ_LAST+NBR_HOLD_COUNT+1（模256）。

这两个条件中的任何一个确保：假如具有接口I的节点i重新启动，那么节点i的每个具有到达接口I的链（J，I）的相邻节点将该条链的状态设为LOST状态。

4.对所接收到的HELLO消息的处理

一个节点接收到一条HELLO消息后，从IP头中获得发送接口的IP地址。假如所接收到的HELLO消息的TBRPF分组头包含RID选项，那么从TBRPF分组头中得到发送节点的RID；否则发送节点的RID等于发送接口的IP地址。假如节点i（其RID等于i）从接口I上接收到节点j在接口J上发送的一条HELLO消息，那么节点i执行以下操作步骤：

（1）假如接口I的相邻节点表不包含接口J的条目，那么为接口J建立一个nbr_rid(I，J)=j、nbr_status(I，J)=LOST（临时丢失）、nbr_count(I，J)=0、nbr_hseq(I，J)=HSEQ的条目。

（2）更新hello_history(I，J)，以便反映所接收到的HELLO消息。假如nbr_hseq(I，J)>HSEQ（由于序列号返转重复），则设置nbr_hseq(I，J)= nbr_hseq(I，J)-256。

（3）假如nbr_status(I，J)=LOST，以及hello_history表示已经从接口J上接收到最近HELLO_ACQUIRE_WINDOW条HELLO消息中的HELLO_ACQUIRE_COUNT个：

a. 假如相邻节点请求列表或者相邻节点应答列表中没有包含接口I，那么设置nbr_status(I，J)=1-WAY、nbr_count(I，J)=NBR_HOLD_COUNT。

b.否则，设置nbr_status(I，J)=2-WAY、nbr_count(I，J)=NBR_HOLD_COUNT。调用规程Link_Up(I，J)。

（4）否则，假如nbr_status(I，J)=1-WAY:

a.假如HSEQ-nbr_hseq(I，J)>NBR_HOLD_COUNT，那么设置nbr_status(I，J)=LOST、nbr_count(I，J)=NBR_HOLD_COUNT。

b.否则，假如相邻节点请求列表中包含接口I，那么设置nbr_status(I，J)=2-WAY、nbr_count (I，J)=NBR_HOLD_COUNT。调用规程Link_Up(I，J)。

c.否则，假如相邻节点应答列表中包含接口I，那么设置nbr_status(I，J)=2-WAY、nbr_count (I，J)=0。调用规程Link_Up(I，J)。

（5）否则，假如nbr_status(I，J)=2-WAY：

a. 假如相邻节点丢失列表中包含接口I，那么设置nbr_status(I，J)=LOST、nbr_count(I，J)=0。调用规程Link_Down(I，J)。

b.否则，假如HSEQ-nbr_hseq(I，J)>NBR_HOLD_COUNT，那么设置nbr_status(I，J)=LOST、nbr_count(I，J)=NBR_HOLD_COUNT。调用规程Link_Down(I，J)。

c.否则，假如相邻节点请求列表中包含接口I，并且nbr_count(I，J)=0，那么设置nbr_count (I，J)=NBR_HOLD_COUNT。

（6）设置nbr_life(I，J)=NBR_HOLD_TIME、nbr_hseq(I，J)=HSEQ、nbr_pri(I，J)=PRI。

5.定时器期满时间nbr_life

节口I的相邻节点表中的定时器nbr_life(I，J)到期后，节点i执行下列操作：

如果nbr_status(I，J)=1-WAY或者2-WAY，则设置nbr_status(I，J)=LOST、nbr_count(I，J)=NBR_HOLD_COUNT。调用规程Link_Down(I，J)。

6.链路层失败通知

某些链路层协议（比如IEEE 802.11）提供到达某个特定相邻节点的链已经中断的通知消息，比如重传次数达到最大值后。假如链路层提供这种通知消息，那么节点i接收到链路层关于从本地接口I到达相邻节点接口J的链（I，J）中断的通知消息后应该执行下列操作：

如果nbr_status(I，J)=2-WAY，则设置nbr_status(I，J)=LOST、nbr_count(I，J)=NBR_HOLD_COUNT。调用规程Link_Down(I，J)。

7.可选的链路参数

每个节点可以为每条链（I，J）维护和更新一个或者多个表示链路质量的链路参数，比如信号强度、在某个时间间隔内接收到的HELLO消息的数量、可靠性、稳定性、带宽等。假如丢失NBR_HOLD_COUNT条HELLO消息、或者在NBR_HOLD_TIME秒时间内没有接收到任何HELLO消息，那么每个节点必须声称一个相邻节点已经丢失。节点也可以根据一个链路参数大于或者小于某个门限值来声称一个相邻节点已经丢失。每个节点在声称某个相邻节点是单向或者双向之前必须接收到该相邻节点最近发送的HELLO_ACQUIRE_WINDOW条HELLO消息中的至少HELLO_ACQUIRE_COUNT条。节点在声称一个相邻节点已经丢失之前，也可以根据另外某个条件来做出判决，这个条件的根据是某个链路参数大于或者小于某个门限值。本规范（RFC3684）没有指定任何特定的链路参数，但是使用这类链路参数实现TBRPF协议与本规范一致。

只要nbr_metric(I，J)发生了明显的变化，调用函数Link_Change(I，J)向路由模块发出告警。假如可配置参数USE_METRICS等于1，那么路由模块利用参数nbr_metric(I，J)计算路由，如稍后“TBRPF路由模块”部分所述。

8.可配置的参数

表4-2列出TND协议使用的参数及其默认值。必须按照表4-2中参数及其取值配置所有节点。

4.2.5 TBRPF路由模块

路由模块执行拓扑寻找和路由计算。

1.概念性数据结构

除了TND协议需要的信息以外，运行TBRPF协议的每个节点维护一张拓扑表（Topology Table，TT），TT用于存储网络中每个已知节点和每条已知链路的信息。各个节点按照其RID来识别，即节点u就是其RID等于u的那个节点。在节点i的TT中为每个节点u和每条链（u，v）存储以下信息：

（1）T(u，v)：假如链(u，v)处在节点i的源节点树T上，则T(u，v)=1；否则T(u，v)=0。以前的源节点树作为old_T来维护。

（2）RN(u)：假如节点u属于节点i的报告节点集RN，则RN(u)=1；否则RN(u)=0。以前的报告节点集作为old_RN来维护。

（3）RT(u，v)：假如链(u，v)处在节点i的报告子树RT上，那么RT(u，v)=1；否则RT(u，v)=0。因为将RT定义为在T上的各条链(u，v)的集合，并且节点u属于RN，所以不必明确地维护变量RT(u，v)。

（4）TG(u，v)：假如链(u，v)处在节点i的拓扑图TG上，则TG(u，v)=1；否则TG(u，v)=0。

（5）N：节点i的双向相邻节点的集合。

（6）r(u，v)：正在报告其报告子树RT上的链(u，v)的相邻节点列表。用RT_j表示被相邻节点j所报告的链(u，v)的集合。

（7）r(u)：正在报告其报告节点集RN中的节点u的相邻节点列表。

（8）p(u)：表示节点u的当前父节点，等于到达节点u的最短路径的下一跳节点。

（9）pred(u)：表示处在源节点树T上的节点u的前一跳节点。若节点u不可达，则pred(u)=NULL。

（10）pred(j，u)：表示被节点j所报告的处在子树RT_j上的节点u的前一跳节点。

（11）d(u)：表示到达节点u的最短路径的长度。假如USE_METRICS=0，那么d(u)等于到达节点u的跳数。

（12）reported(u，v)：假如TG中的链(u，v)被p(u)所报告，那么reported(u，v)=1；否则reported(u，v)=0。

（13）tg_expire(u)：表示TG中链(u，v)的期满时间。

（14）rt_expire(j，u)：表示子树RT_j上链(u，v)的期满时间。

（15）nr_expire(u，v)：表示TG中一条链(u，v)的期满时间，使得reported(u，v)=0。在重新寻找路由期间可以临时使用这种非报告的链路。

（16）metric(j，u，v)：表示被相邻节点j所报告的链(u，v)的参数。

（17）metric(u，v)：表示TG中链(u，v)的参数。对于一个相邻节点j，metric(u，v)表示从节点i到达节点j的所有双向链上的nbr_metric(I，J)的最小值。

（18）cost(u，v)：表示链(u，v)的开销。假如USE_METRICS=1，那么cost(u，v)=metric(u，v)，否则cost(u，v)=1。

（19）local_if(j)：表示用于将分组转发到相邻节点j的首选本地接口的地址。

（20）nbr_if(j)：表示相邻节点j的首选接口的地址。

路由表包含一个结构为（rt_dest，rt_next，rt_dist，rt_if_id）的数组列表，其中rt_dest表示目的节点IP地址或者前缀；rt_next表示该路由下一跳节点的接口地址；rt_dist表示该路由的长度；rt_if_id表示本地接口的身份识别码ID，通过这个本地接口可以到达下一跳节点。

每个节点还维护三张有关描述IP地址或者前缀的表格：“接口表”纪录与RID有关的接口IP地址，“主机表”纪录跟RID有关的主机IP地址，“网络前缀表”纪录与RID有关的网络前缀。

“接口表”由一个结构为（if_addr，if_rid，if_expire）的数组组成，其中if_addr表示与RID=if_rid的路由器有关的接口IP地址；if_expire表示本数组期满时间，并且本数组期满之后必须被删除。一个节点的接口表不包含if_addr等于自身RID的条目。因此，节点不会将自己的RID作为一个相关接口来广播。

“主机表”由一个结构为（h_addr，h_rid，h_expire）的数组组成，其中h_addr表示与RID=h_rid的路由器有关的主机IP地址；h_expire表示本数组期满时间，并且本数组期满之后必须被删除。

“网络前缀表”由一个结构为（net_prefix，net_length，net_rid，net_expire）的数组组成，其中net_prefix和net_length描述一个与RID=net_rid的路由器有关的网络前缀；net_expire表示本数组期满的时间，并且本数组期满之后必须被删除。可以将一个MANET网络配置为一个末端（Stub）网络，其中一个或者多个网关路由器可能广播一个默认前缀，从而使得net_prefix=net_length=0。对每张表格维持两个备份：一个备份叫“旧”拷贝，表示该备份最近已被传输给相邻节点；另外一个备份叫当前拷贝，表示当接收到相关消息时将被更新。

2.拓扑更新消息格式

拓扑更新消息有两种取决于消息大小的格式。拓扑更新消息的标准格式如图4-12所示。只要n、NRL、NRNL不大于255，则使用拓扑更新消息的标准格式。

拓扑更新消息实体包含节点u，v_1，v_2，…，v_n的n+1个RID，代表链(u，v_1)，(u，v_2)，…，(u，v_n)。节点v_k的第一个NRL被报告为树叶节点、第二个NRNL被报告为非树叶节点、最后一个n-(NRL+NRNL)未被报告（不属于RN集）。

比特“M”表示本条拓扑更新消息中是否含有链路参数。假如M=1，那么每条链(u，v_1)，(u，v_2)，…，(u，v_n)包含一个长度一字节的参数，这些链路参数位于最后一个RID之后。

比特“D”表示是否使用隐含删除（Implicit Deletion）。当且仅当IMPLICIT_DELETION=1，则必须设置D=1。

拓扑更新消息有如下三种子类型：

（1）全类型（FULL）（TYPE=5）。一个全更新（FULL，n，NRL，NRNL，u，v_1，v_2，…，v_n）报告链(u，v_1)，(u，v_2)，…，(u，v_n)属于发送路由器的报告子树RT，并且RT没有包含以节点u结尾的其他链。

（2）添加类型（ADD）（TYPE=6）。一个添加更新（ADD，n，NRL，NRNL，u，v_1，v_2，…，v_n）报告链(u，v_1)，(u，v_2)，…，(u，v_n)已经被添加到发送路由器的报告子树RT上。

（3）删除类型（RELETE）（TYPE=7）。一个删除更新（DELETE，n，NRL，NRNL，u，v_1，v_2，…，v_n）报告已经从发送路由器的报告子树RT上删除链(u，v_1)，(u，v_2)，…，(u，v_n)。

假如n、NRL或者NRNL大于255，那么使用较长的拓扑更新消息格式，将标准格式开始4个字节用8个字节替代就得到拓扑更新消息的较长格式，如图4-13所示。

3.接口、主机、网络前缀联合消息格式

接口关联（INTERFACE ASSOCIATION）消息（类型TYPE=8）和主机关联（HOST ASSOCIATION）消息（类型TYPE=9）的格式如图4-14所示。

接口关联消息和主机关联消息的实体包含源节点的RID、n个有关该RID的接口IP地址（类型TYPE=8）或者主机IP地址（类型TYPE=9）。ST域的定义下面给出。

网络前缀关联（NETWORK PREFIX ASSOCIATION）消息（类型TYPE=10）的格式如图4-15所示。

网络前缀关联消息的实体包含源节点的RID、n个网络前缀。每个网络前缀前面有一个长度为一字节的前缀长度，说明该前缀所需全部字节的最少数量。为了使开销最低，不按照字边界排列前缀长度和各个前缀。

接口关联、主机关联、网络前缀关联三种消息均有以下三种子类型（类似于拓扑更新消息的三种子类型）：

（1）全类型（FULL）（ST=0）：表示这是一个包含有关给定RID的所有接口地址、所有主机地址、所有网络前缀的全更新。

（2）添加类型（ADD）（ST=1）：表示所包含的IP地址或者网络前缀跟该RID有关，但是可能不包含跟该RID有关的所有IP地址或者网络前缀。

（3）删除类型（RELETE）（ST=2）：表示所包含的IP地址或者网络前缀不再跟该RID有关。

4.TBRPF路由操作

TBRPF路由模块的操作分成以下几个部分：周期性处理、源节点树和拓扑图的更新、路由表的更新、报告节点集的更新、周期性更新消息的产生、差异更新消息的产生、拓扑更新消息的处理、拓扑信息的期满时间、冗余拓扑信息的选择性报告、本地拓扑变化、关联消息的产生、关联消息的处理、非转发操作。按照规程（例如，规程Update_All）来描述TBRPF路由模块的操作。规程或者周期性执行，或者响应某个事件时执行规程，或者被其他规程所调用。在所有规程中，节点i就是执行本规程的节点。

1）周期性处理

每个节点周期性执行规程Update_All()，至少每隔DIFF_UPDATE_INTERVAL秒执行一次规程Update_All()。DIFF_UPDATE_INTERVAL通常等于HELLO_INTERVAL（HELLO消息间隔时间）。规程Update_All()的定义如图4-16所示。

2）源节点树和拓扑图的更新

规程Update_Source_Tree()是DIJKSTRA算法的改进版，被周期性地调用和响应拓扑变化时调用，用于更新源节点树T和拓扑图TG。这个算法计算出来的最短路径容易受到两个链路开销的不利影响。一个不利的链路开销NON_REPORT_PENALTY被加入到各条链(u，v)的开销中，这些链当前还未被父节点p(u)所报告，所以，只要可能，假如一条链(u，v)只有当前被父节点p(u)所报告，那么T就包含这条链(u，v)。为了在父节点p(u)发生变化之时能够立即重新寻找路由，可能必须临时使用一条当前还未被新父节点所报告的链(u，v)。另外一个不利的链路开销NON_TREE_PENALTY被添加到当前不属于T的各条链(u，v)的开销中，以便减少对T的改变。当存在多条相同开销路径到达一个给定节点的时候，根据RID做出选择。

本算法定义如图4-17所示（其中节点i是执行本规程的节点）。

3）路由表的更新

根据源节点树或者关联表（接口表、主机表、或者网络前缀表）的变化更新路由表。根据规程Update_Routing_Table()进行路由表的更新。规程Update_Routing_Table()定义如图4-18所示。

4）报告节点集的更新

回想前面将报告子树RT定义为源节点树T中使得节点u处在报告节点集RN中的各条链(u，v)的集合。每个节点正好在产生周期性更新或者差异更新之前立即更新其RN。

假如REPORT_FULL_TREE=1（一个节点报告其整个源节点树），那么RN由所有可达节点组成，即由使pred(u)≠NULL的所有节点u组成集合RN。按照这种方法计算RN的规程就是

Update_RN_Simple()。下面介绍在假定REPORT_FULL_TREE=0的条件下如何计算RN。

一个节点首先确定其哪些相邻节点属于RN集。当且仅当节点i确定其一个相邻节点可能选择自己作为到达节点j的最短路径的下一跳的时候，节点i将节点j放入RN集中。为了做出这个决策，节点i计算最长2跳的最短路径，从每个相邻节点到达每个其他的相邻节点，只使用相邻节点（或者节点i本身）作为中间节点，以及使用转发优先权和RID做出选择。假如使用一个链路参数，那么使用这个链路参数计算最短路径；否则计算最少跳数路径。

在一个节点确定完其哪些相邻节点属于RN集之后，当且仅当到达节点u的下一跳p(u)处在RN集中的时候，RN集包含拓扑表中的每个节点u（而不是节点i）。同样，当且仅当节点u处在以某个相邻节点j为根部的子树上，并且该相邻节点j属于RN集的时候，RN集包含节点u。因此，报告子树RT包含源节点树T的子树，这些子树的根部是RN集中的相邻节点。RN集还包含节点i本身；因此，报告子树RT还包含到达相邻节点j的所有本地链。

更新RN集的精确规程定义如图4-19所示。

5）周期性更新消息的产生

每隔PER_UPDATE_INTERVAL秒，每个节点产生一组全拓扑更新消息（RN集中每个非源节点树T树叶节点的节点一条消息），并将这些消息发送到所有的接口上，这些消息描述报告子树RT。只要可能，就将这些消息封装在一个分组中，使发送的控制分组数量最少。

每条拓扑更新消息包含n+1个节点u，v_1，v_2，…，v_n的RIDs，代表n条链(u，v_1)，(u，v_2)，…，(u，v_n)。n个头节点v_1，v_2，…，v_n被分成三个列表，以便传输其他信息，因此减少了必须产生的消息的数量。特别是，第一个NRL头节点是源节点树T的树叶节点，因此，避免了为各个树叶节点u单独产生拓扑更新消息。类似地，最后n-(NRL+NRNL)个头节点不在RN集中，因此，避免了为已经从RN集中删除的各个节点u单独产生拓扑更新消息。

根据如下定义的规程Generate_Periodic_Update()产生周期性更新消息（其中节点i是执行本规程的节点）。

规程Generate_Periodic_Update()

对于RN集中不是源节点树T树叶节点的每个节点u（包括节点i本身），将更新（FULL，n，NRL，NRNL，u，v_1，v_2，…，v_n）添加到每个接口I的消息列表msg_list(I)中，其中：

① 节点v_1，v_2，…，v_n是使链(u，v)处在源节点树T上的那些节点v，其中第一个NRL是源节点树T树叶节点并且是在RN集中的节点，第二个NRNL不是源节点树T树叶节点、但是在RN集中的节点，最后n-(NRL+NRNL)节点不在RN集中。

② 假如USE_METRICS=1，那么将控制比特“M”设为1，将链路参数metric(u，v_1)，metric(u，v_2)，…，metric(u，v_n)放入更新消息中。

6）差异更新消息的产生

每隔DIFF_UPDATE_INTERVAL秒，假如不是产生周期性更新消息的时间，并且RT自最近一次产生拓扑更新以来已经发生了变化，那么产生一组描述RT变化的拓扑更新消息，并将其发送到所有的接口上。按照如图4-20定义的规程Generate_Differential_Update()构造这些消息。

7）拓扑更新消息的处理

当从节点j接收到一个包含拓扑更新消息列表（msg_list）的分组的时候，根据图4-21定义的规程Process_Updates(j，msg_list)处理这个更新消息列表。特别是，规程Process_Updates(j，msg_list)更新拓扑表TT、拓扑图TG、以及报告相邻节点列表r(u)和r(u，v)。假如从TG中删除了源节点树T上任何一条链，那么调用规程Update_Source_Tree()和Update_Routing_Table()，立即重新寻找路由。

8）拓扑信息的期满时间

每个节点根据期满定时器tg_expire(u)、rt_expire(j，u)、nr_expire(u，v)周期性地检查过时的拓扑信息，删除TG、r(u)和r(u，v)中的过时条目。这些都是根据图4-22定义的规程Expire_Links()来完成。在更新源节点树T之前周期性调用规程Expire_Links()。

此外，应该周期性执行以下删除操作步骤，删除拓扑表TT中不必要的条目。假如一条链(u，v)既不在TG中、也不在old_T树上，则应该从TT中删除这条链(u，v)。假如一个节点u满足以下所有条件，则应该从TT中删除这个节点u：① r(u)为空，② r(w，u)对于所有节点w也为空，③ TG中没有任何一条链将节点u作为头节点或者尾部节点。

9）冗余拓扑信息的选择性报告

要求每个节点向相邻节点报告其报告子树RT。但是，每个节点（与其他节点无关）可以报告其他的链路，例如，为了提高高速移动网络中的强壮性而报告其他链路。例如，一个节点可能计算包含源节点树T的TG的任何子图H，也可能报告“报告子图”RH，RH包含使得节点u在RN集中的子图H的链(u，v)。在这种情况下，每个周期性更新描述的是RH而不是RT，每个差异更新描述的是RH的变化。假如使用这个选项，那么必须将参数IMPLICIT_DELETION清0，这是因为假如报告冗余拓扑信息，那么增加一条链并不意味着删除另外一条链。

10）本地拓扑变化

下面描述相邻节点寻找模块检测到一条新链、丢失一条链、或者一条链的参数发生了变化之后的操作规程。

当通过相邻节点寻找模块发现一条从一个本地接口I到达一个相邻节点接口J的链(I，J)的时候，执行图4-23定义的规程Link_Up(I，J)。设节点j是一个与相邻节点接口J有关的相邻节点，规程Link_Up(I，J)将节点j添加到N集中（假如节点j不属于集合N），更新首选本地接口local_if(j)和相邻节点接口nbr_if(j)，使得在从节点i到达节点j的所有链中，从local_if(j)到达nbr_if(j)的链具有最小的链路参数，规程Link_Up(I，J)更新链路参数metric(i，j)而使其最小。

当相邻节点寻找模块检测出丢失一条从一个本地接口I到达一个相邻节点接口J的链（I，J）的时候，执行图4-23定义的规程Link_Down(I，J)。当丢失一条链的时候立即更新路由，并且假如这条丢失链是来源于一个链路层中断通知，则立即发送差异拓扑更新消息。

假如相邻节点寻找模块检测出一条从一个本地接口I到达一个相邻节点接口J的链(I，J)的链路参数发生了变化，则调用图4-23定义的规程Link_Change(I，J)。

11）关联消息的产生

图4-24 描述了接口关联消息、主机关联消息、网络前缀关联消息的生成规程。每隔IA_INTERVAL秒就将接口表中的地址报告给相邻节点，每隔HA_INTERVAL秒就将主机表中的地址报告给相邻节点，每隔NPA_INTERVAL秒就将网络前缀表中的前缀报告给相邻节点。此外，如果不是周期性更新的时候，则每隔DIFF_UPDATE_INTERVAL秒就报告这些表格的差异变化（类似于差异拓扑更新）。每个节点只报告跟所报告节点集RN中的节点有关的地址或者前缀，这样可以确保将所有有关地址和前缀有效地广播到网络中的所有节点。

将所产生的关联消息发送到每个接口上。只要可能，就将这些关联消息封装到同一个分组中，以便使所发送的控制分组的数量最少。

12）关联消息的处理

当接收到节点j发送出来的一条接口关联消息、一条主机关联消息、或者一条网络前缀关联消息的时候，按照图4-25所描述的三个规程分别更新接口表、主机表、网络前缀表。

13）非转发操作

转发优先权等于0 的节点叫做非转发节点，不转发所接收到的其他节点发送来的分组（任何类型）。通过既不产生拓扑更新消息也不发送拓扑更新消息就可实现非转发节点。非转发节点可以报告跟自己有关的地址或者前缀（在关联消息中），但是不报告跟其他节点有关的地址或者前缀。为了建立与相邻节点的链路，必须发送HELLO消息。在非转发节点中可以省略以下规程：Update_RN()，Generate_Periodic_Update()，Generate_Diff_Update()。

14）可配置参数

表4-3列出TBRPF协议路由模块使用的可配置参数及其默认值。必须按照表4-3中参数及其取值配置所有节点，但是参数REPORT_FULL_TREE和IMPLICIT_DELETION除外。

4.2.6 TBRPF泛洪机制

下面描述一种机制，用于将分组有效地、最大努力地泛洪到（或者全网广播）整个连通Ad Hoc网络中的所有节点。可以将这个机制看成是经典泛洪算法的优化版，经典泛洪算法要求每个分组被网络中的每个节点所发送。在TBRPF协议的泛洪算法中，根据TBRPF协议提供的信息决定所接收到的一个泛洪分组是否应该被转发。因此，每个分组只会被相对较少的一组节点所转发，所占用的带宽比经典泛洪算法少。

本规范（RFC3684）指定这个泛洪机制使用IPv4多目标地址224.0.1.20。每个节点维护一个备份存储器，用于跟踪已经接收到的泛洪分组。备份存储器包含每个泛洪分组的身份识别码（Flooded Packet Identifier，FPI）。对于IPv4，FPI由源节点IP地址、IP标识符、以及从IP头中得到的分片偏移值组成。

一个节点接收到一个其IP地址等于泛洪地址（224.0.1.20）的分组后，检查其备份存储器，寻找与该分组匹配的条目。假如存在这样的条目，那么该节点已经接收过这个泛洪分组，因此只需丢掉而不必再次转发该泛洪分组。否则，当且仅当满足以下条件的时候，该节点将这个泛洪分组重新发送到所有接口上：

（1）与该泛洪分组源节点IP地址有关的TBRPF节点属于TBRPF协议计算出来的报告节点集RN。

（2）IPv4分组头中的“IP_TTL（IP的有效时间）”（在IPv6分组头中则是“HOP_COUNT（跳数）”）递减后仍然大于0。

如果重传一个分组，那么在一小段随机时延之后发送这个分组，以便避免分组的碰撞。如果该分组的接收接口不是MANET网络接口，那么不应该在这个接收接口上重传这个分组。

4.2.7 TBRPF在移动Ad Hoc网络中的操作

TBRPF协议特别适合于由移动节点构成的MANET网络，各个移动节点具有无线网络接口，在一个多址访问通信信道上按照对等方式操作。尽管TBRPF协议的应用范围较广，但是TBRPF协议特别适合于支持标准的DARPA互联网协议。下面讨论TBRPF协议在MANET网络中的操作的实际考虑。

1.数据链路层的假设

假定一个MANET网络数据链路层支持广播、多目标传输、单目标传输的选址，在相邻节点之间（即，相互处在对方的传输范围内的一对节点）提供最大努力（没有保证的）交付服务。假定MANET网络节点的每个接口分得有一个单目标数据链路层地址，这个地址在整个MANET网络范围内是唯一的。尽管这种唯一性没有得到严格保证，但是这个唯一性假设与特定链路层上互联网协议的当前实际使用情况一致。链路层重复地址的检测与排除方法不在本规范（RFC3684）讨论范围之内。

2.网络层的假设

MANET网络由一组路由器节点和非路由节点构成，使用网络层地址计算MANET网络拓扑。假定每个节点至少有一个数据链路层接口（上面已描述），每个数据链路层接口分得有一个在本MANET网络内唯一的网络层地址（网络层地址分配可参阅第11章）。假定每个节点选择一个唯一的RID用于TBRPF协议消息，不论该节点是否作为一个MANET网络路由器。假定每个MANET网络路由器在网络层支持多跳转发，即每个路由器通过网络层主机路由提供节点间的转发服务，该路由反映了TBRPF协议所认识到的当前MANET网络拓扑。

3.选择性自动地址解析

TBRPF协议在网络层使用主动式相邻节点寻找协议，通过周期性发送消息来维护相邻节点的双向链状态。由于TBRPF相邻节点寻找消息包含发送方的数据链路层和网络层的地址，所以TBRPF协议的实现可能需要自动为构成链路的节点进行网络层到数据链路层的地址解析。TBRPF协议的实现也可能使用跟诸如ARP或者IPv6相邻节点寻找之类的按需地址解析机制有关的这种机制来避免额外的消息开销和可能的分组丢失。TBRPF协议的实现必须按照标准方式响应按需地址解析的请求。

4.多接口和（或者）虚地址的支持

MANET网络可能由多个接口组成，每个接口具有唯一的网络层地址。此外，MANET网络节点可能需要广播虚地址（Alias Address），就像多个网络层地址被分配给同一个接口或者一个MANET网络节点正在按照移动IP主代理进行服务那样。使用接口关联消息广播多个接口地址和虚地址，接口关联消息将每个这种地址封装成该节点的RID。

5.网络前缀的支持

MANET网络路由器可能广播网络前缀，网络前缀可以通过连接到网络上的路由器、其他协议广播的外部路由、或者其他手段得到。网络前缀放在网络前缀关联消息中而被广播，网络前缀关联消息将每个这样的前缀封装成该节点的RID。

6.非MANET网络主机的支持

非MANET网络主机可能通过诸如ARP或者IPv6相邻节点寻找之类的按需机制建立到达MANET网络路由器的连接。这种连接不会建立MANET网络链，因此不会安排在TBRPF拓扑更新消息中而被报告。非MANET网络主机安排在主机关联消息中而被广播，主机关联消息将每个主机的IP地址封装成该节点的RID。

7.INTERNET协议考虑

使用UDP/IP发送TBRPF分组。IANA已经分配端口712给TBRPF协议专门使用。在专用网络中的实现可能使用交替数据交付服务（即纯IP封装或者本地数据链封装）。选择一种交替数据交付服务必须在本专用网络中所有MANET网络路由器之间是一致的。在各种实现中，数据交付服务必须提供校验和功能。

下面说明在UDP/IP上的TBRPF协议操作。

1）IPv4操作

当使用IPv4时，TBRPF节点服从IPv4主机和路由器要求。TBRPF分组被发送到多目标地址224.0.0.2（所有路由器），因此，TBRPF分组传输到达发送方一跳范围内的所有TBRPF路由器。对于发送至224.0.0.2的分组，TBRPF路由器不必转发。

由于不可忽视链路中断、干扰等产生的分组丢失，所以TBRPF协议的实现应该避免IPv4的分片/重组，只要可能，就在应用层将一个大TBRPF协议分组分成多个较小的分组。当分片不可避免时，发送方不应该给网络中的所有接收方发送大于最小重组缓存器容量的TBRPF分组。

2）IPv6操作

IPv6的TBRPF协议规范与IPv4的TBRPF协议规范相同，只是32比特IPv4地址被128比特IPv6地址所代替。但是，为了使开销最低，RID仍然保留32比特，类似于IPv6的OSPF。