模拟路由器设计图
2018-01-07 11:44:18 11 举报
登录查看完整内容
模拟路由器设计图
作者其他创作
大纲/内容
输出
输入
LS还需要定时广播：比如两个比较大的网络原本不连通，现在用一条链路练起来，那么不仅新链路两端的节点需要广播，其他节点虽然直连链路没有变化，但是也要发送LS广播。
每次执行Dijkstra时，要顺便验证每条链路都是双向的。也就是说，如果A的邻居中有B，但B的邻居中没有A，那么不算这条链路。（这种情况可能出现在：disconnect A和B之间的链路以后，B的通告先到达）
connect()、disconnect()模拟链路的连通与断开
更新
DVInform
触发
这里的v不能是x，但可以是y。当v为y时（y是x的邻居），我们需要确保v的DV中存在条目D_v(y)=0，也就是说要确保每个节点的DV中都有到自己的条目，否则x无法算出自己到v的开销。
routeTable（也就是自己的DV）
路由毒化
定期检查每个邻居的活跃情况，清除已经无活动的邻居
直接修改链路双方的neighbors
毒化经过一段时间以后，可以认为毒化信息已经传播到整个网络，网络中已经没有路由器再使用这个被毒化的路由，可以解除该路由的毒化。此时要再触发一次DV算法，利用网络稳定后的DVs（不包含错误路由信息）来计算出自己的DV。因为对于被毒化的路由，可能存在去往它的目标节点的其他路径。这一次DV算法会计算出这个路径。
完整代码实现在https://github.com/csr632/network-routing-simulation
注意，要完全清除旧的路由表，然后用新输出作为路由表。而不能只是往路由表中插入更新。
不需要定期清除routeTable条目。因为：如果跑的是DV算法，那些不可达的节点会从邻居的DV通告中消失，自然也就不会出现在计算出来的DV中。如果跑的是LS算法，那些不可达的节点无法被Dijkstra算法扩展到，因此不会出现在输出的路由表中。
DV算法：对于网络N中的每个节点，看看经过哪个邻居到达它的开销最小。（根据所有邻居的DV计算出自己的DV）
neighbors
LSBroadcast
Dijkstra算法：从本节点出发，不断寻找cost最低且尚未扩展的节点，扩展这个节点（更新这个节点的邻居的cost），循环往复直到找不到可以扩展的节点。那些已扩展的节点就是从本节点可达的，它们被扩展时的cost就是去往它们的最小路径开销。
删除不可达的节点的链表
它的更新立即触发的adjacencyList的更新（在链路双方的邻居表中增加、删除邻居），然后触发Dijkstra算法
网络状态变化的根本来源
DV算法需要这个条件来保证算法会自我中止。
每次进行DV算法之前，要先计算出网络中所有从本节点可达的节点集合N（邻居以及邻居DV中包含的节点）。然后再执行DV算法：
收到邻居节点的DV通告
收到所有可达节点的邻居信息
neighbors的更新会触发：向网络中所有节点广播自己的邻居信息
有些节点只是暂时不可达；或者实际可达但是有些中间节点的广播还没有到达，导致本节点仍然以为这个节点不可达。如果删掉这些节点的邻居表，会减慢网络的收敛速度。因此暂时取消这一步。
如果新的DV与上次不同，则触发：向邻居通告自己的新DV
adjacencyList
DVs（所有邻居的DV，不包括自己的）
邻居检测机制
网络状态信息在路由器中的更新，以及网络状态信息在路由器之间的传播
fault()模拟路由器故障，无法正常发出数据包
0 条评论
回复 删除
下一页
