[Angular, TypeScript, 路由算法] 模拟IP层路由协议

:

路由模拟项目介绍

链路状态协议（Link-state ）和距离向量路由协议（- ）是分组交换（ ）网络中最主要的两种路由协议。本项目的模拟路由器实现了LS路由算法、LS广播洪泛、DV路由算法，以及防止DV路由环路和无穷计数问题的策略。此外还实现了完整的前后端以便研究者通过UI界面自定义网络拓扑、控制路由器、查看路由器信息和日志。

链路状态算法（LS）

LS算法要求网络中每个节点都收集完整的网络信息，以邻接表的形式存储整个网络的拓扑结构和所有链路的费用，然后根据这个图来运行路由选择算法（在这里我们选择算法），计算出从本节点到网络中所有其他节点的最低费用路径。

LS广播

为了让每个节点都知道整个网络的拓扑结构和所有链路费用，每个节点都要将自己直连的链路信息广播给网络中的所有节点（LS广播）。要广播的信息包括自己的邻居有哪些、到达它们的链路开销分别是多少。

为了更新它本身存储的网络拓扑图，在接收到其他节点的LS广播时，要根据广播中的链路信息更新自己的邻接表。

同时，在接收到其他节点的LS广播时，要将它转发给自己的所有邻居，从而这个LS广播能散播到整个网络。为了避免广播风暴（广播包在网络中无休止地传播，导致网络瘫痪），每个路由器要辨别接收到的LS广播包是不是已经接收过。这可以通过一个广播包中的序列号字段来做到。每台ls路由器，每次广播使用一个递增的序列号，如果多次收到来自同一台路由器且序号相同的广播，则不更新邻接表，也不转发给邻居，防止广播风暴。

迪杰斯特拉算法（'s ）

算法能够计算出图中所有节点到某个节点的最短路径。对于一个图和一个给定的原点，算法不断选择一个距离源点最近且尚未扩展的节点w来扩展，并更新w的邻居节点到原点的距离。最终，所有被扩展的节点就是从原点可以到达的节点，它们被扩展时到原点的距离就是最终的最短距离。

什么时候触发算法计算出新的路由表

算法的输入就是节点维护的邻接表，因此只要邻接表有更新，就要触发算法计算出新的路由表。

那么邻接表什么时候会更新呢？有2种情况：

本节点的直连链路发生变化，要更新邻接表中对应的链路。接收到新的LS广播，要根据LS广播中的信息更新邻接表。 距离向量算法（DV）

DV算法不需要全局网络信息。每个节点只从直连邻居接收路由通告，执行DV计算，然后将计算结果分发给直连邻居。重复这个过程，直到每个节点的DV计算结果都与上一次的DV计算结果相同，此时网络中不再有路由通告，算法终止。

DV算法

DV算法的思想相对比较简单：邻居能到达的节点，我经过这个邻居也能到达，并且我去目标节点的费用 = 我到邻居的费用 + 邻居到目标节点的费用。一个节点的DV存储的就是这个节点能到达哪些节点、费用分别是多少。

DV算法的输入是所有邻居的DV和自己的直连链路信息，输出是自己的DV（也就是路由表）。如果输出的DV与上次输出的不同，也就是自己的DV发生了变化，那么要将自己的DV通告给所有邻居。

有几点需要注意：

为了保证DV算法的自我终止（网络中不再有DV通告，也不再运行DV算法），仅仅当DV发生变化时才通告给邻居。DV的计算完全不依赖于自己上次计算得到的DV（也就是自己当前的路由表）。 路由环路和无穷计数问题

由于DV算法没有全局网络信息，DV算法中可能会出现路由环路和无穷计数的问题。

The –Ford does not loops from and from the count-to- . The core of the count-to- is that if A tells B that it has a path , there is no way for B to know if the path has B as a part of it.

如果A告诉B：A能到达C。由于B没有全局网络信息，它无法知道自己是否已经处于从A到C的路径上。

为了避免路由环路和无穷计数，我们使用了Split- with 和的策略。详见路由器设计文档。

设计文档 路由器设计

类设计图：

我们的路由器实例是运行在同一台机器上的，它们之间通过UDP进行通信。

路由器类的主要成员

是路由器的路由表。用来转发数据包。

只在链路算法为ls的时候使用，它是存储了整个网络信息的邻接表。当接收到ls广播，或自己的直连链路变化（也就是变化），都要触发它的更新。

（在设计图中的DVs）维护了所有邻居发来的DV通告。为了加速存取，它的数据结构是以邻居port为key的Map。 前后端设计

前端是用和制作的简单UI，运行在浏览器中；后端是用Node.js写的服务器，模拟路由是完全在后端进行的。前端与后端之间通过而不是HTTP来通信，以便后端能主动、实时地发送信息给前端显示。

前端主要包含4个部分：

负责通过与后端进行通信；负责根据后端发来的消息来绘制UI，并响应用户在UI上的操作；负责展示用户选中的路由器或链路的信息，并提供一些针对选中对象的操作。（或其他浏览器）控制台。后端运行的路由器实例产生的日志将通过连接发送到前端，前端将日志打印在控制台。用户如果想要查看路由器的运行过程需要打开控制台再刷新页面。由于浏览器的控制台自带功能，用户可以选择只查看某个路由器发出的日志、某种操作发出的日志。

后端主要包含3个文件：

.ts负责监听端口、调用来操作路由器和链路；.ts负责维护并操作网络中所有的路由器实例，比如连接路由器、关闭路由器、改变路由器之间的链路，它提供操作网络的接口给.ts；.ts定义了路由器类，其实现了ls算法和dv算法，并提供操作单个路由器的接口给.ts。 配置和运行

先安装node.js。

克隆这个仓库，切换到dev分支。

运行后端程序。命令行进入文件夹，依次执行“npm ”来安装后端依赖，“npm run build”来编译后端项目（此命令会一直监视文件变化并重新编译）。再打开一个命令行窗口并进入文件夹，执行“npm run serve”来运行后端项目，看到 is on port 8999表示服务端成功运行。

运行前端程序。然后从命令行进入文件夹，依次执行“npm ”和“ng serve”。看到已下信息表示客户端网页已经可以可以访问。

打开浏览器，访问“:4200/”即可。如果还想要查看路由器日志可以打开浏览器控制台并刷新页面。如果出现“发生错误，点击确定刷新页面”弹窗，表示客户端无法通过连接到后端，请确保后端正在运行。

默认情况下，运行的是dv算法的路由器。如果要换成ls算法，修改“.ts”的这一行：

将“dv”改为“ls”（“npm run build”命令行窗口会监测到变化并重新编译）。然后重新执行“npm run serve”来运行后端项目。

运行结果

左上角的操作栏可以添加、删除路由器和链路。点击路由器或链路，会在右边栏显示它的信息和一些操作。路由日志显示在浏览器控制台中，如果想要只查看某个路由器的日志或某个操作的日志，只需要在控制带的输入框中输入过滤字符串，比如“”，或“route table has ”。

可以通过这个项目来自定义网络拓扑、操作网络拓扑，并观察路由表的变化。具体的例子在视频中展示。

阅读资料

《计算机网络 自顶向下方法 第六版》