Hexo

网络层-控制平面

路由算法

产生路由表的算法

图论抽象

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 )

路由算法：找到开销最小的路径(路由器序列)

分散式算法–只知道和部分路径,通过和邻居交换信息

典型就是下面这个算法

• 距离向量路由算法

描述

1. 节点x维护距离向量

   Dx=[dx (y): yєN ]
   (如果y不是x的邻居节点, 则dx (y)=∞,否则dx (y)= c(x,y))

2. 每个节点周期性向其邻居节点发送它自己的 距离向量, 节点x保存其邻居节点的距离向量
   Dv = [dv (y): y є N ]

3. n当节点x接收到来自邻居的 新距离向量，它使用B-F方程更新自己的DV :
   Dx (y) ← minv {c(x,v) + Dv (y)} for each node y ∊ N
   Bellman-Ford方程：

   1. 定义
      $d_x$ (y) = 从x到y的最小开销路径的开销,c(x,v) = 从x到邻居节点v的链路的开销
   2. 则dx (y) = minv {c(x,v) + dv (y) }
   3. 取值最小的节点对应最短路径中的下一跳(只有一个地址)➜ 转发表

   示例<img src="https://s2.loli.net/2021/12/09/HhICGUakqft2zm1.png" alt="image-20211122134953146" style="zoom:50%;" />

• 链路状态路由算法 •

1. Discover its neighbors, learn their network address. 发现邻居，学习它们的网络地址
2. Measure the delay or cost to each of its neighbors. 测量到每一个邻居的时延或开销
3. Construct a packet (link state packet)telling all it has just learned. 构造一个分组(链路状态分组) 来通 告其学习到的所有信息
4. Send this packet to all other routers. 向所有路由器发送该分组
5. 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的特点

1. 安全性–报文经过签名鉴别
2. 使用多条开销相同的路径
3. 对每条链路,为不同的服务类型设置多种开销度量
4. 集成的单播和多播支持

层次ospf

自治系统内进一步再分

• BGP路由协议(border gateway protocol)

-自治系统间路由

算法-距离向量算法(改名—路径向量算法)

1. eBGP: Obtain subnet reachability information from

neighboring ASes.从相邻AS获得子网可达性信息

2. iBGP: Propagate reachability information to all AS-internal

routers. 向AS内部的所有路由器传播可达性信息

3. Determine “good” routes to subnets based on reachability

information and policy.根据可达性信息和策略，决定到子网

的“好”路由

•ICMP-The Internet Control

差错报告–不可达网络\主机\端口\协议

回声请求

trace route

源主机从ttl=1,一点点开始发送更大的ttl,目的端口号设置为一个不可能到达的端口,

当ttl超时时,该路由器发送一个ICMP报文到源主机,这样会获取路径上路由器的信息

到达目的主机后,会返回一个端口不可达报文,探测结束

Message Protocol

•网络管理——SNMP协议