mirror of
https://gitee.com/willfree/mlsr.git
synced 2026-06-05 16:49:32 +08:00
pxy
189 lines
20 KiB
Markdown
189 lines
20 KiB
Markdown
# MLSR
|
||
## 介绍
|
||
MLSR（MIN Link State Routing Protocol，多标识网络链路状态路由协议）是MIN（Mutil-Identifier Network，多标识网络）中的基本路由协议。
|
||
|
||
MLSR支持推式传输和拉式传输下的路由寻址。
|
||
|
||
## 功能模块简述
|
||
|
||
### Hello模块
|
||
#### 1、模块功能：
|
||
* Hello模块定期发送 Hello兴趣包以了解邻居MIR的活动状态。
|
||
* 如果邻居MIR响应 Hello兴趣包，则认为该邻居MIR已启动且处于活动状态。
|
||
* 如果邻居MIR未能响应可配置数量（如以配置条目hello-retries代表该数目）的 Hello 兴趣包，则认为邻居MIR已关闭且处于非活动状态。Hello协议继续每隔可配置时间间隔的（如以配置条目hello-interval代表该间隔）秒数向它的每个邻居MIR发送这些周期性的Hello兴趣包。
|
||
* 如果Hello协议检测到邻居MIR状态的变化（即先前处于活动状态的路由器没有响应Hello兴趣包，或先前处于INACTIVE的路由器响应了Hello兴趣包），它将通知 LSDB调度构建新的LSA，以包含更新的邻居信息
|
||
#### 2、故障检测：
|
||
* 如果发送给一个邻居MIR的hello兴趣包超时未响应的个数超过阈值，则认为到该邻居MIR的链路发生故障；
|
||
* 如果从其它MIR那里接收到带有某个邻居MIR的face已经被破坏的FaceEventNotification，则认为到该邻居MIR的链路发生故障。
|
||
* 当认为到某个邻居MIR的链路发生故障后，将执行以下动作：a.修改该邻居MIR的链路状态为INACTIVE；b.修改该邻居MIR的hello超时计数为最大值；c.发布一个表示到该邻居MIR的链路状态发生故障的LSA。
|
||
#### 3、故障恢复：
|
||
* 如果Hello模块收到某状态为INACTIVE的邻居MIR的有效应答信息，该应答为对Hello模块发出的Hello兴趣包的响应，则到该邻居MIR的链路已恢复。
|
||
* 当认为到某个邻居MIR的链路发生恢复后，将执行以下动作：a.修改该邻居MIR的链路状态为ACTIVE；b.修改该邻居MIR的hello超时计数重置为零；c.发布一个表示到该邻居MIR的链路状态已恢复的LSA。
|
||
|
||
|
||
### LSA模块
|
||
链路状态通告（LSA）表示路由器分发的路由信息。
|
||
#### 1、LSA基类
|
||
所有三个LSA 实现都继承自一个LSA基类——Lsa，它维护包含在每个LSA 中的信息。LSA 类包含以下成员变量：
|
||
* 源路由器 - 通告 LSA 的路由器。具体来说，这是一个遵循路由器命名的 NLSR 约定的名称前缀。
|
||
* Sequence Number - 用于指示 LSA 版本的数字。因为序列号在 NLSR 重新启动之间被保留，更高的序列号也总是表示更新的 LSA。
|
||
* 到期时间点- 指示LSA 何时不再有效的时间点。这当前表示为 Unix 时间戳（即自 1970 年 1 月 1 日以来的秒数）。
|
||
#### 2、邻接LSA
|
||
邻接 LSA 维护一个 AdjacencyList，其中包含有关源路由器当前所有活动邻居的信息。它还包括活动路由器的数量，而不仅仅是列表本身。这有助于序列化。
|
||
#### 3、坐标LSA
|
||
坐标LSA 保持原路由器的双曲角和双曲半径。
|
||
#### 4、名称LSA
|
||
名称 LSA 维护一个 NamePrefixList，其中包含在源路由器可到达的名称前缀。
|
||
|
||
### LSDB模块
|
||
链路状态数据库 (LSDB) 保存由网络中其他路由器分发的 LSA 信息。 LSDB 存储所有类型的 LSA，并在添加、更新或过期新 LSA 时触发事件。 LSDB 还处理 LSA 检索、执行 LSA 构建和触发路由表计算。
|
||
#### 1、检索LSA
|
||
* LSDB 提供 Lsdb::expressInterest() 方法作为公共接口从网络中检索 LSA。如果返回 LSA 数据，则 LSDB 将使用 Validator 模块验证数据。然后，它将执行必要的 LSDB 修改。如果 LSA Interest 超时，LSDB 将重试，直到达到可配置的最大尝试次数，或者经过可配置的期限。
|
||
* LSDB 使用 SegmentFetcher 系统来检索 LSA。 LSA 经常会超过最大 NDN 数据包大小。在这些情况下，需要将 LSA 拆分为分段发送，因此 LSDB 使用 SegmentFetcher 发送所有 LSA。 SegmentFetcher 可以决定数据是否真的需要拆分。
|
||
#### 2、调度LSA
|
||
构建 LSA 需要在路由信息 NLSR 发生变化时重新构建。这包括诸如邻居变为活动的事件，或者当前缀更新处理器插入广告前缀时，这将分别导致邻接 LSA 或名称 LSA 重建。为了提高性能，不是直接构建邻接 LSA，而是第一个请求调度构建，并且在调度之后但在实际事件之前发生的构建请求被聚合（换句话说，忽略），因为它们将被已经调度的满足建造。一些细节如下所示。
|
||
* 邻接 LSA——仅在启用链路状态路由时才会被调度。特别是，这意味着如果启用双曲线路由，则不会发生邻接 LSA 构建。请注意，如果启用了空运行双曲线路由，则将构建邻接 LSA，因为网络仍在使用链路状态路由来计算路径。
|
||
#### 3、一般程序
|
||
LSDB 负责构建、安装和发布 NLSR 的 LSA，以及安装和处理来自其他 NSLR 的 LSA。通常，LSDB 的功能是：
|
||
* 调度LSA 的构建。
|
||
* 构建LSA。
|
||
* 将LSA 安装到LSDB 中。
|
||
#### 4、构建LSA
|
||
构建LSA 有一个对所有 LSA 通用的部分和一个特定于每个 LSA 类型的部分。例如，所有 LSA 类型都会增加序列号并具有相同的到期长度，并且当然来自同一个路由器。此外，所有 LSA 构建都会导致同步更新发布。但是，每种 LSA 包含不同的数据，以表示 NLSR 具有的不同类型的信息。 特别是：
|
||
* 邻接 LSA——包括活动邻居的数量和列表。
|
||
* 坐标LSA——包括双曲半径和所有双曲角。
|
||
* Name LSA——包括在该路由器上可访问的名称前缀列表。
|
||
#### 5、安装和处理LSA
|
||
LSA 安装过程在任何类型的 LSA 中基本相同，但每种类型也具有特定于该类型的安装行为。对于任何 LSA 类型，我们都需要安排一个过期事件，并且我们需要更新 LSA 中的几个字段。但是，安装邻接或坐标 LSA 会导致路由表计算，但名称 LSA 不会。附加的，源路由器的名称作为“可路由前缀”添加到 NPT 中。
|
||
* 邻接 LSA——LSA 中的每个邻接都将作为“可路由前缀”添加到 NPT。如果自此 LSA 的上一个版本以来邻接关系发生了变化，则需要安排路由表计算，因为网络的状态已经改变。当然，如果 LSA 对我们来说是新的，这必然是正确的。需要注意的重要一点是，我们还将以这种方式安装和处理我们自己的邻接 LSA。
|
||
* 坐标LSA——LSA 来自的路由器将作为“可路由前缀”添加到NPT。如果自此 LSA 的上一个版本以来半径和坐标发生了变化，则需要安排路由表计算，因为网络的状态已经改变。如上所述，这适用于新的 LSA。仅当 LSA 来自外部路由器时才执行此操作。
|
||
* Name LSA – LSA 中的每个名称前缀都将添加到我们的 NPT 中。仅当 LSA 来自外部路由器时才执行此操作。
|
||
#### 6、LSA过期
|
||
LSA 过期，以便在路由器崩溃时清理网络。 LSA 的持续时间是可配置的。当一个 LSA 过期时，如果它是我们的 LSA，我们刷新它，如果不是，我们将它从 LSDB 中删除。有一个“宽限期”窗口附加到所有 LSA 的到期期限的末尾，为始发路由器提供时间来刷新 LSA 并将其传播回给我们。在所有到期情况下，源路由器的名称将从 NPT 中删除。当从 LSDB 中删除 LSA 时会发生什么因 LSA 的类型而异：
|
||
* 邻接 LSA – 需要进行路由表计算，因为网络状态已经改变，至少从我们的角度来看是这样。
|
||
* 坐标LSA——需要进行路由表计算，因为网络状态已经改变，至少从我们的角度来看是这样。
|
||
* Name LSA——从 NPT 中删除 LSA 中的名称前缀。
|
||
#### 7、LSA刷新
|
||
NLSR 只会刷新自己的 LSA。此外，刷新 LSA 的过程对于所有类型都是相同的：
|
||
* 增加 LSA 序列号
|
||
* 安排另一个到期事件。等待刷新的时间长度是可配置的，但它可能应该低于最初构建 LSA 时设置的过期时间。例如，这可以防止其他路由器因为网络速度慢而删除我们的 LSA。时间长度由配置文件中的 lsa-refresh-time 设置。
|
||
* 发布更新到sync
|
||
#### 8、实现考量与决策
|
||
##### （1）LSA存储
|
||
* ndn-cxx基于C++封装的多值索引容器（multi_index_container）进一步封装了in-memory-storge，实现了内存存储的查找、插入、删除等基本动作，并定义了进行这些操作之前或之后所需要做的诸如beforeErase、afterInsert等接口。
|
||
* 使用多值索引容器的好处就在于，在进行类检索时，可以根据这个类的多个成员变量进行索引，而不是只能指定一个成员变量进行索引；此外，它将按照索引对存储的数据进行升序或降序排序。
|
||
* nlsr基于ndn-cxx封装的in-memory-storage，定义了LsaStorage，用来存储LSA。
|
||
* MIN-LSR基于golang实现。Golang的container包中有关于堆heap、双向链表list、循环链表ring等数据结构的实现。可以利用golang原生库进行lsacontainer的实现，也可以寻找其它适用的第三方库。
|
||
|
||
##### （2）任务调度
|
||
* 在需要执行的操作，即任务非常多的时候，我们需要任务调度器去支持各种任务的调度：安排某任务在某时刻进行执行、删除任务、修改任务执行时间，等。
|
||
* ndn-cxx基于C++实现了scheduler实现了一个普适性较好的任务调度器。
|
||
* minlib基于golang实现了超时事件堆timeoutHeap，用以支持超时事件的触发。
|
||
* mir-go基于Golang实现了Dispatcher，用以对管理命令兴趣包进行处理和响应。该调度器内置了顶级域、行为模块、读写锁、签名验签等成员参数。
|
||
* LSDB需要任务调度器完成包括但不限于以下事件：邻接LSA的构建、LSA过期事件触发、更新事件触发、删除事件触发、兴趣包或GPPkt的循环发送事件触发。
|
||
|
||
##### （3）配置管理
|
||
* LSDB中涉及一些需要从配置文件中读写的参数，诸如本机路由器的名称前缀、一些默认间隔时间，等等。
|
||
* nlsr将以上功能实现为ConfParameter这个单例类。
|
||
* mir-go在common/config.go中实现了解析配置文件等功能，且基于golang语言实现的，可作为参考。
|
||
##### （4）序列号管理
|
||
* 不同类型的LSA均需要对递增的seq进行管理（增、查、改），并将其同步持久化到本地的文件中，以在MIN-LSR重启时保持序列号的连续。
|
||
##### （5）网络相关
|
||
* 主要支持从网络中检索其他MIR的LSA，及使用推式包或拉式包将自己的LSA不断组播给其他路由器。
|
||
* 这块功能需要在Hello模块、MIN-Sync协议、Sync逻辑处理模块几个模块实现之后，再在LSDB中进行相关功能的实现。可先预留实现接口。
|
||
|
||
##### （6）路由计算
|
||
* 不同类型LSA的安装将触发不同的处理动作。如安装邻接LSA时，将计算路由表，来自其他MIR的名称LSA则不会计算路由表，而会将其插入到名称前缀表。
|
||
|
||
|
||
|
||
### 路由表模块
|
||
路由表模块执行三个主要任务：它使用RoutingTableCalculator执行路由表计算，它将计算的路由表条目存储在一个表中，并在更改时通知名称前缀表（NPT）模块计算出的下一跳。
|
||
#### 1、路由表计算器
|
||
RoutingTableCalculator 是一个基类，它提供包括链路状态路由（link-state）和双曲路由（hyperbolic）共有的功能。路由表模块使用特定于当前启用的路由类型的实现类。
|
||
* 链路状态路由表计算器：
|
||
LinkStateRoutingTableCalculator 类计算路由表使用 Dijkstra 算法计算网络中的最短路径。当max-faces-per-prefix设置为1时，LinkStateRoutingTableCalculator可以简单地运行Dijkstra算法。当 max-faces-per-prefix大于1时，表示多路径计算，LinkStateRoutingTableCalculator 将迭代地执行 Dijkstra，仅使用单个邻居链路作为下一跳。这将使用每个邻居执行计算，以便了解每个目的地通过每个下一跳的路径成本。
|
||
* 双曲路由表计算器：
|
||
HyperbolicRoutingCalculator 类使用从网络中每个路由器接收到的坐标 LSA 来计算路由表，以确定从它的每个邻居到网络中每个其他路由器的成本。 HyperbolicRoutingCalculator 遍历每个路由器的邻居，计算从邻居到网络中所有其他路由器（不包括自身和邻居路由器）的双曲线距离。然后，HyperbolicRoutingCalculator 使用这些计算出的距离将路由表条目添加到目的地，并将邻居作为下一跳。 HyperbolicRoutingCalculator 还添加了一个路由表条目以到达邻居本身；添加使用邻居作为到邻居的下一跳的路由表条目，成本为零。
|
||
#### 2、通知最新计算的下一跳
|
||
路由表模块计算完路由表后，会更新所有名称前缀表的下一跳。然后，名称前缀表模块将根据新计算的路由表更新每个名称前缀的下一跳。这个过程在NPT模块一节中有更详细的描述。
|
||
#### 3、路由表表项设计
|
||
每一个路由表项都有一个目的地址和一条到该目的地址的路径。所谓路径，即许多条链路，这些链路使用NextHop结构体进行封装，其内容包括链路接口LogicFaceUri和链路开销Cost。
|
||
~~~
|
||
RoutingTableEntry：
|
||
ndn::Name m_destination;
|
||
NexthopList m_nexthopList;
|
||
|
||
NextHop：
|
||
std::string m_connectingFaceUri;
|
||
double m_routeCost;
|
||
~~~
|
||
|
||
### NPT模块
|
||
|
||
* NLSR 使用名称前缀表 (NPT) 来维护由其他路由器通告的所有已知名称前缀的列表，包括路由器名称。 NPT 维护 NPT 条目的集合，其中每个条目代表一个名称前缀及其所有关联的路由表条目。此外，为了优化路由表条目的存储和关联，NPT 还维护了一组重复的路由表条目，称为路由表池条目，它们具有额外的使用计数属性。 NPT 条目保留指向适当路由表池条目的共享指针。如果一个名称前缀被多个路由器发布，则该名称前缀将仅由一个名称前缀表条目表示，但会有多个路由表池条目对应每个源路由器。
|
||
* 如果名称 LSA 存在带有一些公布的名称前缀，则该前缀必须在 NPT 中有一个条目。因此，如果两个路由器通告相同的名称前缀，即它们的名称 LSA 包含一个公用名称前缀，即使一个路由器撤回该公用名称前缀，该条目也必须保留在 NPT 中，因为另一台路由器仍然通告它。
|
||
* 如果 LSDB 中存在远程路由器的任何类型的 LSA，则远程路由器的名称前缀必须在 NPT 中。只有当 LSDB 中不再有来自源路由器的 LSA 时，才能删除路由器名称的 NPT 条目。注意，即使某些 NPT 条目 nas 没有下一跳，也不会从 NPT 中删除；以后可能会路由到这个前缀。但是，这些前缀将从 FIB 中删除。
|
||
#### 1、添加NPT条目
|
||
* NamePrefixTable::addEntry() 方法是用于将名称前缀添加到 NPT 的公共接口。名称前缀以及源自名称前缀的路由器前缀作为参数传递给该方法。
|
||
* 如果名称前缀是新的，则不会有 NPT 条目，因此将创建一个。如果名称前缀不是新的，则现有条目将被更新，因此现有条目也将存储这个新源路由器的前缀。如果在更新后，NPT 条目具有与每个源路由器前缀相关联的任何下一跳，则 NPT 将更新 FIB 以包括该前缀及其下一跳。下一跳列表被排序并截断为仅与 max-faces-per-prefix 变量一样长。
|
||
#### 2、删除NPT条目
|
||
* NamePrefixTable::removeEntry() 方法是用于从 NPT 中删除名称前缀的公共接口。名称前缀以及源自名称前缀的路由器前缀作为参数传递给接口。
|
||
* 此方法从一些公布的名称前缀中删除源路由器前缀。在此之后，可能有其他源路由器提供此名称前缀，因此这并不能保证 NPT 条目将被删除。如果更新条目后有任何下一跳，NPT 将更新 FIB 以反映更改。由于下一跳列表按成本升序排序，并且其长度被截断为 max-faces-per-prefix，因此如果删除的源路由器前缀不在传递给 FIB 的列表中，则下一跳列表的内容不会改变。
|
||
* 请注意，即使条目不再有任何下一跳，它也会被保留。此前缀的所有 FIB 条目将从 FIB 中删除，这将导致从 NFD 注销，但将保留 NPT 条目。这是因为以后可能会再次路由到这些源路由器
|
||
#### 3、使用新的路由表条目更新NPT条目
|
||
* 当路由表模块完成计算后，它会使用 NamePrefixTable::updateWithNewRoute() 方法通知 NPT。然后 NPT 将对 addEntry 进行大约 m ×n 调用，其中 m 是 NPT 条目的数量，n 是每个 m 的源路由器的数量。也就是说，在大多数情况下，n 会随着 NPT 条目的不同而变化。
|
||
#### 4、路由表条目池
|
||
* Name Prefix Table 有一个内部数据结构来帮助去重路由表信息。如果没有这个，每个路由表条目必须存储 n 次，如果 n 是源路由器通告的前缀数。相反，每次获取路由表条目时，NPT 首先检查其内部数据结构以查看该路由表条目是否正在被另一个 NPT 条目使用。在这种情况下，这两个 NPT 条目可以共享一个指向路由表条目的缓存副本的指针。这个内部缓存是智能的，当它们从最后一个 NPT 条目中删除时，将从缓存中清除未使用的条目。
|
||
* NamePrefixTable将名称前缀与路由器相关联。要做到这一点，它需要知道某些路由器是否可以访问。这反过来需要访问RoutingTable中与名称前缀相关的条目。这样做每次都会天真地从RoutingTable复制条目，这是非常昂贵的。此类提供了一个重复数据消除系统，NamePrefixTable可以维护RoutingTablePoolEntries的集合。然后，这个新类可以与名称前缀相关联，而不是与原始条目相关联，这提供了一个最小的内存解决方案。
|
||
#### 5、NPT表表项设计
|
||
~~~
|
||
NamePrefixTableEntry：
|
||
ndn::Name m_namePrefix;
|
||
std::list<std::shared_ptr<RoutingTablePoolEntry>> m_rteList; // 使用它来减少对唯一路由表的反复访问
|
||
NexthopList m_nexthopList; // 根据上面的多条路径，计算出一条
|
||
|
||
RoutingTablePoolEntry（继承RoutingTableEntry）：
|
||
ndn::Name m_destination; // 路由表条目：目的路由器
|
||
NexthopList m_nexthopList;// 路由表条目：出口列表
|
||
std::unordered_map<ndn::Name, std::weak_ptr<NamePrefixTableEntry>>
|
||
namePrefixTableEntries; // 使用到了该RTPE条目的NPT条目列表
|
||
uint64_t m_useCount; // 该RTPE条目的使用次数
|
||
~~~
|
||
#### 6、路由计算逻辑
|
||
* 每间隔一段时间，从lsdb获取邻接lsa，使用最短路径算法，计算路由表；
|
||
* 路由表的更改，或lsdb中名称lsa的更新，都会触发名称前缀表的计算；
|
||
* 计算名称前缀表时，会根据名称lsa去获取路由表中的路由表项，将其变为路由表池项（内存优化），然后根据所有路由表项去累计起来，获得当前名称前缀的下一跳列表。
|
||
|
||
### 安全模块
|
||
* NLSR的信任模型是分层信任模型。如果要对现有的入网证书验签信任模型进行改进，则需要建立一个新的基于MIS系统的信任模型。
|
||
* MIR目前有包验签和证书验证的安全机制，第一个版本的路由协议可以暂时先不做新的信任模型。
|
||
|
||
|
||
## 开发规范
|
||
### 注释规范
|
||
* 源代码文件抬头注明开发者、时间、版本、组织等信息，请参考较早提交的代码文件。
|
||
* 结构体及函数需注明其作用，请参考较早提交的代码文件。
|
||
|
||
### 代码规范
|
||
* 函数之间留有确定行数的空行。
|
||
* 复杂函数内部可根据逻辑关系，用空行分割为若干块，并加入注释予以解释。
|
||
|
||
|
||
## 开发环境及依赖
|
||
### 开发环境
|
||
|
||
| 环境项 | 信息 |
|
||
| :----: | :----: |
|
||
| Golang | go 1.18 |
|
||
| IDE推荐 | GoLand |
|
||
|
||
### 软件依赖
|
||
minlib
|
||
注：请将minlib放置在与mlsr同目录下，注意，不是mlsr目录之下，是平行关系。
|
||
|
||
## 联系我们
|
||
MIN-Group
|
||
国家重大科技基础设施——未来网络北大实验室
|
||
深圳市信息论与未来网络重点实验室
|
||
开发者邮箱：wefree@stu.pku.edu.cn |