网络层
网络层-控制平面
路由算法
产生路由表的算法
图论抽象
Graph: G = (N,E)
N = set of routers = { u, v, w, x, y, z } 节点是路由器
E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) } 边是物理链路
链路开销Cost of link:时延、费用或拥塞等级 路径开销Cost of path:c(x1 , x2 , x3 ,…, xp ) = c(x1 ,x2 ) + c(x2 ,x3 ) + … + c(xp-1 ,xp )
路由算法:找到开销最小的路径(路由器序列)
分散式算法–只知道和部分路径,通过和邻居交换信息
典型就是下面这个算法
• 距离向量路由算法
描述
节点x维护距离向量
Dx=[dx (y): yєN ]
(如果y不是x的邻居节点, 则dx (y)=∞,否则dx (y)= c(x,y))每个节点周期性向其邻居节点发送它自己的 距离向量, 节点x保存其邻居节点的距离向量
Dv = [dv (y): y є N ]n当节点x接收到来自邻居的 新距离向量,它使用B-F方程更新自己的DV :
Dx (y) ← minv {c(x,v) + Dv (y)} for each node y ∊ N
Bellman-Ford方程:- 定义
$d_x$ (y) = 从x到y的最小开销路径的开销,c(x,v) = 从x到邻居节点v的链路的开销 - 则dx (y) = minv {c(x,v) + dv (y) }
- 取值最小的节点对应最短路径中的下一跳(只有一个地址)➜ 转发表
示例
<img src="https://s2.loli.net/2021/12/09/HhICGUakqft2zm1.png" alt="image-20211122134953146" style="zoom:50%;" />
- 定义
• 链路状态路由算法 •
- Discover its neighbors, learn their network address. 发现邻居,学习它们的网络地址
- Measure the delay or cost to each of its neighbors. 测量到每一个邻居的时延或开销
- Construct a packet (link state packet)telling all it has just learned. 构造一个分组(链路状态分组) 来通 告其学习到的所有信息
- Send this packet to all other routers. 向所有路由器发送该分组
- Compute the shortest path to every other router. 计算到其他路由器的最短路径
使用Dijkstra算法计算最短路径<img src="https://s2.loli.net/2021/12/09/mCdF4G2wO7vxpUW.png" alt="image-20211122143134224" style="zoom:50%;" />
路由协议
受到分组压力,单位需求的影响,产生了as(自治系统)
系统内可以用之前的算法,系统外–?自治系统间专门的路由协议
• O(pen)S(hortest)P(ath)F(irst)路由协议
自治系统内路由-开放最短路径优先
使用的算法是链路状态算法
OSPF的特点
- 安全性–报文经过签名鉴别
- 使用多条开销相同的路径
- 对每条链路,为不同的服务类型设置多种开销度量
- 集成的单播和多播支持
层次ospf
自治系统内进一步再分
• BGP路由协议(border gateway protocol)
-自治系统间路由
算法-距离向量算法(改名—路径向量算法)
- eBGP: Obtain subnet reachability information from
neighboring ASes.从相邻AS获得子网可达性信息
- iBGP: Propagate reachability information to all AS-internal
routers. 向AS内部的所有路由器传播可达性信息
- Determine “good” routes to subnets based on reachability
information and policy.根据可达性信息和策略,决定到子网
的“好”路由
•ICMP-The Internet Control
差错报告–不可达网络\主机\端口\协议
回声请求
trace route
源主机从ttl=1,一点点开始发送更大的ttl,目的端口号设置为一个不可能到达的端口,
当ttl超时时,该路由器发送一个ICMP报文到源主机,这样会获取路径上路由器的信息
到达目的主机后,会返回一个端口不可达报文,探测结束