《计算机网络:自顶向下方法》笔记5 网络层:控制平面

第五章

路由选择算法

分类方式多样,可以集中/分散,可以动态/静态,可以负载敏感/负载迟钝。

链路状态路由选择算法

链路状态广播使得每个节点都具有网络的统一完整的视图,每个节点都可以运行LS算法并计算出相同的最低开销路径集合。

其实就是个dijkstra。

如果链路开销等于链路上承载的负载这类的东西,就有可能出现振荡。

距离向量路由选择算法

距离向量DV算法是一种迭代的、异步的、分布式的算法。这个又和bellman-fiord方程相关。

每个点维护自己的距离向量:到所有节点的最低开销路径的开销(估计值),然后时不时给邻居发送方向向量副本。任何节点$x$从邻居$v$收到方向向量的时候更新自己的方向向量:$D_x(y)=\min_v{c(x,v)+D_v(y)}$。要是$x$的距离向量因为这个更新步骤改变,就向另据发送更新以后的距离向量。

其实$x$真正想知道的是沿着最短路径到$y$的下一跳路由器邻居节点$v^*(y)$。

dv

路径开销降低好说,但是增大就……

原来的话$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 AS3AS3

如果一台路由器在路径列表里看到了包含它自己的AS,它将拒绝通告,这样避免了环路。

NEXT-HOP是AS-PATH起始的路由器接口的ip地址。

nexthop

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数据报载荷运输。

打赏
  • © 2018-2020 poorpool
  • Powered by Hexo Theme Ayer
    • PV:
    • UV:

请我喝杯草莓芝士奶盖吧~

支付宝
微信