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

README.md Unescape Escape

MLSR

介绍

功能模块简述

Hello模块

1、模块功能：