数据报网络.ppt

4.4 网际协议:因特网中的转发和编址 从 1985 年起在 IP 地址中又增加了一个“子网号字段”，使两级的 IP 地址变成为三级的 IP 地址。 从两级 IP 地址到三级 IP 地址 IP 地址空间的利用率有时很低。 两级的 IP 地址不够灵活。 * * * * * * * * * * * * * * * * * * * * * * 讲课备注： 如何找出一条最优的路径呢？ 我们可以把网络形式化为一张图，应用图论和算法的知识解决问题 当然在网络中我们仅考虑无向图，即假定双向的费用一致 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * BGP 发言人和自治系统 AS 的关系 BGP 发言人 BGP 发言人 BGP 发言人 BGP 发言人 BGP 发言人 AS1 AS3 AS2 AS5 AS4 * * BGP 发言人交换路径向量 主干网 （AS1） 地区 ISP （AS2） 地区 ISP （AS3） 本地 ISP（AS4） N1， N2 本地 ISP（AS5） N3， N4 本地 ISP（AS6） N5 本地 ISP（AS7） N6， N7 自治系统 AS2 的 BGP 发言人通知主干网的 BGP 发言人：“要到达网络 N1, N2, N3 和 N4 可经过 AS2。” * * BGP 发言人交换路径向量 主干网 （AS1） 地区 ISP （AS2） 地区 ISP （AS3） 本地 ISP（AS4） N1， N2 本地 ISP（AS5） N3， N4 本地 ISP（AS6） N5 本地 ISP（AS7） N6， N7 主干网还可发出通知：“要到达网络 N5, N6 和 N7 可沿路径（AS1, AS3）。” * * 路由协议小结 4.5 选路算法 RIP OSPF BGP 协议类型 IGP IGP EGP 信息表达格式 距离－向量协议 链路－状态协议 路径向量 交换信息范围 相邻路由器 自治系统或区域内路由器 BGP发言人 交换信息内容 路由表 链路状态 路径向量 交换信息时间 30S 当链路状态发生变化 有变化 原则 最短路径 最小代价 可达性 收敛过程 较快 快 快 传输协议 UDP IP TCP 适用网络类型 小型网络 大型网络 自治系统之间 衡量标准 距离 可有多种度量标准 无 * * 课后思考题 复习题 1、3、9、15、17、22、24 习 题 1、4、7、14、15、18、19、21、 23、25、 讨论题 5、6 * * 作业题 习题 1、15、16、22、26 * * * * * * * * * * * * * * * * * * * * * * * * * * * * 4.5 选路算法 路由算法的目标 如何找到一个路径序列（x1, x2, x3,…, xp） 使路径费用最小？ * * 4.5 选路算法 选路算法分类 根据信息是全局性还是分散式的进行分类 全局选路算法 所有路由器都知道整个网络拓扑图以及链路的费用信息 链路状态算法 分散式选路算法 每个路由器仅有与其相连链路的费用信息 通过迭代计算过程与相邻节点交换信息 距离向量算法 * * 4.5 选路算法 根据信息是静态还是动态的进行分类 静态选路算法 随着时间的流逝，路由的变化非常缓 动态选路算法 路由信息可以更快地发生变化 周期性的更新 可以响应拓扑或链路费用的变化 * * 4.5 选路算法 根据是否对负载敏感进行分类 负载敏感算法 链路费用会动态地变化以反映出链路的当前状况 负载迟钝算法 链路费用不明显地反映链路的当前状况 * * 4.5 选路算法 链路状态选路算法 所有节点都知道网络拓扑和链路费用 所有节点具有该网络的同一个完整的视图 通过链路状态广播获得信息 计算从某节点到网络中所有其他节点的最低费用 迭代计算，获得该节点到所有其他节点的最低费用路径 为该节点提供转发表 * * 4.5 选路算法 链路状态选路算法——符号定义 c(x,y): 从节点x到节点y的链路费用 D(v): 从源节点到目的v的最低费用路径的费用 p(v): 从源节点到v沿着当前最低费用路径的前一节点 N‘: 节点子集。 若x和y不直接相连，则c(x,y)=∞ 若源节点到x的最低费用路径已知，则x在该集合中。 * * 4.5 选路算法 步骤 0 1 2 3 4 5 N u ux uxy uxyv uxyvw uxyvwz D(v),p(v) 2,u 2,u 2,u D(w),p(w) 5,u 4,x 3,y