2020.6.5 计网 第四章 1
2020.6.10 计网 第四章 2
- 转发
- 路由选择
路由器的主要作用：将数据包从入链路转发到出链路。
【如何得到最优路径】
代价：成本，时延
方案：
1.全局（global）路由算法
知道所有网络的拓扑结构。
2.去中心的(decentralized)
并不需要知道全网的拓扑，只要知道邻居的路由表就可以了。
区别：是否需要用到全网的拓扑。
静态：一次生成后就不动了。
动态：实时了解全网/邻居的变化。
- LV链路状态
- DV距离矢量
路由协议
Dijkstra's algorithm
每个路由器会向全网公开（广播）自己的链路状态
算法复杂度：
问题：振荡oscillation
距离矢量算法
- 邻居能去的，一定能通过邻居到达
- 多个邻居能到的，选择代价最小的
Bellman-ford算法 （贝尔曼算法）
1,.初始化:将除源点外的所有顶点的最短距离估计值 d[v] -->+∞, d[s]-->0;
2.迭代求解:反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离;(运行|v|-1次)
3.检验负权回路:判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解;否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。
更新：
距离矢量：
好消息传得快，坏消息传得慢。
根本原因：距离矢量算法并不追求高代价的路径（那么它就不那么在意谁是更高的代价路径）
Z通过发送欺骗的信息给Y证明是否存在闭环，如果有闭环则置为无穷大。
图形反转的方法只适用于两个点
安全性：都不是太优，可能存在恶意的邻居
路由协议
层级结构
scalable
内部的路由算法
自治系统（理解为运营商）之间的算法
autonomous systems （AS） domain
内部：中大->中大
自治系统之间（域间）：中大->华工
Inter -AS Routing
域内网关协议
RIP:距离矢量
OSPF:Dijstra
问题：会增加网络的负担
但可以支撑层次化的IP
安全性：查看是否被授权，防止恶意节点广播恶意信息
支持多路径
单播：点到点
多播：一对多/多对多？
层次化OSPF
边界路由器（连接其他区域/国家/另外的自治系统）
局限广播范围/区限
可以减少洪泛导致的数据传播的数量