计算机网络（自顶向下方法）-网络层

5.1 路由选择算法

路由(route)的概念

路由:按照某种指标(传输延迟,所经过的站点数目等)找到一条从源节点到目标节点的较好路径
 较好路径: 按照某种指标较小的路径
 指标:站数, 延迟,费用,队列长度等, 或者是一些单纯指标的加权平均
 采用什么样的指标,表示网络使用者希望网络在什么方面表现突出,什么指标网络使用者比较重视
 以网络为单位进行路由（路由信息通告+路由计算）
 网络为单位进行路由，路由信息传输、计算和匹配的代价低
 前提条件是：一个网络所有节点地址前缀相同，且物理上聚集
 路由就是：计算网络 到其他网络如何走的问题路

 网络到网络的路由= 路由器-路由器之间路由
 网络对应的路由器到其他网络对应的路由器的路由
 在一个网络中：路由器-主机之间的通信，链路层解决
 到了这个路由器就是到了这个网络
 路由选择算法(routing algorithm):网络层软件的一部分,完成路由功能

路由选择算法的原则

 正确性(correctness):算法必须是正确的和完整的,使分组一站一站接力，正确发向目标站；完整：目标所有的站地址，在路由表中都能找到相应的表项；没有处理不了的目标站地址；
 简单性(simplicity):算法在计算机上应简单：最优但复杂的算法，时间上延迟很大，不实用，不应为了获取路由信息增加很多的通信量；
 健壮性(robustness):算法应能适应通信量和网络拓扑的变化：通信量变化，网络拓扑的变化算法能很快适应；不向很拥挤的链路发数据，不向断了的链路发送数据；
 稳定性(stability)：产生的路由不应该摇摆
 公平性(fairness)：对每一个站点都公平
 最优性(optimality)：某一个指标的最优，时间上，费用上，等指标，或综合指标；实际上，获取最优的结果代价较高，可以是次优的

路由算法分类

link state

distance vector

距离矢量算法

 Dx(y) = 节点x到y代价最小值的估计
 x 节点维护距离矢量Dx= [Dx(y): y є N ]
 节点x:
知道到所有邻居v的代价: c(x,v)
收到并维护一个它邻居的距离矢量集
对于每个邻居, x 维护Dv = [Dv(y): y є N ]

距离矢量路由选择(distance vector routing)

LS 和 DV 算法的比较

5.2 因特网中自治系统内部的路由选择

RIP

OSPF

5.3 ISP之间的路由选择: BGP

为什么内部网关协议和外部网关协议如此不同?

策略:
 Inter-AS: 管理员需要控制通信路径，谁在使用它的网络进行数据传输；
 Intra-AS: 一个管理者，所以无需策略;
 AS内部的各子网的主机尽可能地利用资源进行快速路由
规模:
 AS间路由必须考虑规模问题，以便支持全网的数据转发
 AS内部路由规模不是一个大的问题
 如果AS 太大，可将此AS分成小的AS；规模可控
 AS之间只不过多了一个点而已
 或者AS内部路由支持层次性，层次性路由节约了表空间, 降低了更新的数据流量
性能:
 Intra-AS: 关注性能
 Inter-AS: 策略可能比性能更重要

5.4 ICMP: 因特网控制报文协议

5.5 网络管理和SNMP(略）

网络管理

SNMP