第五章
路由选择算法
分类方式多样，可以集中/分散，可以动态/静态，可以负载敏感/负载迟钝。
链路状态路由选择算法
链路状态广播使得每个节点都具有网络的统一完整的视图，每个节点都可以运行LS算法并计算出相同的最低开销路径集合。
其实就是个dijkstra。
如果链路开销等于链路上承载的负载这类的东西，就有可能出现振荡。
距离向量路由选择算法
距离向量DV算法是一种迭代的、异步的、分布式的算法。这个又和bellman-fiord方程相关。
每个点维护自己的距离向量：到所有节点的最低开销路径的开销（估计值），然后时不时给邻居发送方向向量副本。任何节点$x$从邻居$v$收到方向向量的时候更新自己的方向向量：$D_x(y)=\min_v{c(x,v)+D_v(y)}$。要是$x$的距离向量因为这个更新步骤改变，就向另据发送更新以后的距离向量。
其实$x$真正想知道的是沿着最短路径到$y$的下一跳路由器邻居节点$v^*(y)$。
路径开销降低好说，但是增大就……
原来的话$D_y(x)=4$，$D_y(z)=1$，$D_z(x)=5$，$D_z(y)=1$。更新以后$D_y(x)=\min{c(y,x)+D_x(x), c(y,z)+D_z(y)}=6$，距离向量发生变化，通知$z$。然后$D_z(x)$更新，……居然需要44轮迭代。这有时被称为无穷计数问题。
毒性逆转
如果$z$通过$y$路由选择到目的地$x$，那么$z$通告$y$ $D_z(x)=\infty$，这就让$y$不可能通过$z$到达$x$（这就成回路了）。但是它没有解决一般的无穷计数问题。涉及三个或更多节点的环路没法检测到。
优劣
ls算法是求$O(NE)$个报文的$O(N^2)$算法。dv报文少，收敛慢，会遇到选择环路。LS的路由计算某种程度上是分离的，一定的健壮性。DV却可能向任意节点通告不正确的最低开销路径。
因特网中自治系统内部的路由选择：OSPF
开放最短路优先OSPF，路由器向自治系统内所有其他路由器广播路由选择信息。每台路由器确定一个以自身为根节点到所有子网的最短路径树。链路开销由管理员配置。
当一条链路的状态发生变化或者是每个一段时间，路由器就会广播链路状态信息。
它安全，允许使用多条相同开销的路径，综合支持单播多播路由选择，支持在单个AS内的层次结构。
一个ospf自治系统能配置多个区域，AS中只能有一个ospf区域配置成主干区域，包含本AS所有区域边界路由器和一些非边界路由器。主干区域为AS中其他区域之间的流量提供路由选择。AS中区域间路由选择要求分组先路由到一个区域边界路由器（区域内路由选择）然后通过主干路由到位于目的区域的区域边界路由器，然后路由到最终目的地。
ISP之间的路由选择：BGP
所有AS都运行相同的AS间路由选择协议：边界网关协议BGP。
BGP是路由到CIDR化的前缀，例如138.16.6.8/22。
他使得AS可从邻居AS获得前缀的可达性信息，确定到该前缀的“最好的”路由。
通告bgp路由信息
对于每个as，路由器要么是网关路由器，要么是内部路由器。网关路由器直连其他as中一台或多台路由器。
跨越两个as的bgp连接称为外部bgp连接（eBGP），自然也有内部iBGP。
确定最好的路由
bgp前缀和属性称为路由。比较重要的属性是AS-PATH和NEXT-HOP。
当一个前缀通过某AS时，该ASN加入AS-PATH的现有列表。
例如在AS1，AS2，AS3构成的环路中从AS1到子网x（在AS3内）可以有两条路，AS-PATH分别为AS2 AS3，AS3。
如果一台路由器在路径列表里看到了包含它自己的AS，它将拒绝通告，这样避免了环路。
NEXT-HOP是AS-PATH起始的路由器接口的ip地址。
NEXT-HOP属性是不属于AS1的某路由器的ip地址，但是包含该ip地址的子网直接连接到AS1。
路由选择算法
热土豆（烫手山芋2333）路由选择：对于一个路由器来说，它选择的路由到开始该路由的NEXT-HOP路由器要有最小开销。哪个开销小选那个。
真正的路由选择：
- 路由被指派一个本地偏好值作为属性之一。最高的将被选择
- 余下路由（如果没选好的话）选AS-PATH最短的。如果该路由是路由选择的唯一规则，那么bgp用dv算法决定路径。距离测度用的是AS跳数而不是路由器跳数。
- 余下路由（没选好，这时候最高本地偏好值和AS-PATH长度均相同），热土豆
- 还有就用bgp标识符选择
IP任播
一个例子：CDN公司给多台服务器指派相同的ip地址，并且使用标准的bgp从每台服务器通告该ip地址。配置路由选择表的时候每台路由器将本地化地使用bgp路由选择算法来挑选到该ip地址最好的路由。
路由选择测略
路由选择算法先根据本地偏好属性选择路由，本地偏好值由本地AS策略决定。
如果一个AS，自身是进入/离开它的所有流量的源/目的地，它就是桩网络。它可以向邻居通告它没有通向任何其他目的地的路径。
SDN控制平面
这东西太难懂了，不看了。
ICMP：因特网控制报文协议
icmp被主机和路由器用来彼此沟通网络层的信息，例如差错报告。
icmp报文作为ip有效载荷。
traceroute用icmp数据报实现。每个数据报携带一个具有不可达udp端口号的udp报文段，第一个数据报ttl为1，第二个为2,……第$n$个数据报到达第$n$个路由器的时候刚好过期，返回一个icmp告警报文，包含路由器名字和ip地址。源主机从定时器得到往返时延，从icmp报文得到第n台路由器的名字和ip地址。停止的时候收到的是端口不可达的icmp报文，知道不需要再发送另外的探测分组。
网络管理和SNMP
网络管理的关键组件是管理服务器，被管设备，管理信息库（MIB），网络管理代理（被管设备中的进程）和网络管理协议。
简单网络管理协议SNMP是个应用层协议。常用的是请求响应模式：SNMP管理服务器向snmp代理发送请求，代理收到请求执行动作发送回答。还有陷阱报文，用于通知管理服务器异常情况导致mib对象值改变。
snmp定义了7种类型的报文，一般称为协议数据单元PDU。通常作为udp数据报载荷运输。