第4章网络层解释.ppt

有很多种解决线头阻塞的方法。 * * MTU maximum transmission unit 帧数据区的最大长度 分片 fragment 标志表明是否是最后一个分片 * * 拓扑 pu一声 topology 扑灭 Node edge * * * Iterative algorithm * 手工算一遍 * 采用堆，则为对数阶而不是平方阶，可减少其算法复杂性 算法复杂度computational complexity，即算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。 按数量级递增排列，常见的时间复杂度有： 常数阶O(1),对数阶O(log2n)(以2为底n的对数，下同),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...， k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 * OSPF使用LS * Distance vector RIP和BGP使用DV * Pseudocode /sudou/ 伪码（Pseudocode）是一种算法描述语言。类Pascal语言的伪码的语法规则是：在伪码中，每一条指令占一行（else if，例外）。指令后不跟任何符号（Pascal和C中语句要以分号结尾）。书写上的“缩进”表示程序中的分支程序结构。 * Dx(x)=0，已经最小，无需计算。 * 一开始Dy(x)=4, Dz(x)=5 * 本来逆时针最优，变化后顺时针最优 * 4变为60，但y得知z可以以5的代价去往x,所有把x作为下一跳 即互相以对方为下一跳 * Poisoned reverse Z通过y选路去往x，则z告诉y它去往x为无穷大，这样可避免y反过来通过z选路到x * 而不是只有两个直接相连的邻居节点 * LS用于因特网的OSPF DV用于英特网的RIP, BGP * * Ls地图中，一小块出错，对个路径计算影响很小。较远处的路由器基本不受影响 Dv中，如果每个路径出错，费用为0，会吸引很多节点通过其来转发。 * Autonomous system * * 3b 1d 3a 1c 2a AS3 AS1 AS2 1a 2c 2b 1b AS内部 选路算法 AS之间 选路算法 转发表 3c 例AS间的互联 三个自治系统：AS1、AS2和AS3。 四个网关路由器： 1b、1c、2a、3a。 各自治系统内分别运行各自的内部选路协议 自治系统间运行AS间选路协议。 * 3b 1d 3a 1c 2a AS3 AS1 AS2 1a 2c 2b 1b 3c 域间路由的任务 假定AS1中的路由器接收目的地是AS1外部的数据报 路由器应当将分组朝着哪一个网关路由器转发？ AS1需要: 知道通过AS2可到达哪些目的地，通过AS3到达哪些 传播这些可达信息到AS1中所有路由器 AS间选路的工作! * 例: 路由器1d的转发表 设一个子网x，AS1运行AS间选路协议后，得出： 子网x只经AS3到达 子网x可以经AS3或AS2到达 3b 1d 3a 1c 2a AS3 AS1 AS2 1a 2c 2b 1b 3c x * 子网x只能经网关1c从AS3到达 AS1向其所有路由器传播该信息； 路由器1d收到后，通过AS内部选路协议决定到网关1c的最低费用路径，并确定从接口I转发， 在其转发表增加表项（x，I）。 3b 1d 3a 1c 2a AS3 AS1 AS2 1a 2c 2b 1b 3c x * 从AS间协议得知，子网x经多个网关可达 使用来自AS内部协议选路信息，以决定到每个网关的最低费用路径 热土豆选路: 选择具有最小费用的网关 从转发表决定接口I 通向最低费用网关。表项 (x,I)加入 在转发表中 在多个AS之间选择 子网x可以经网关1c从AS3到达，也可以经网关1b从AS2到达 AS1向其所有路由器传播该信息； 路由器1d收到后，通过AS内部选路协议（如热土豆算法）决定到目的地具有最低费用的网关1c或1b 若确定从接口I转发，在其转发表增加表项（x，I） * AS间选路信息的交换 当一个AS知道从一个相邻的AS可以到达目的地，向所有其他的相邻AS通告该选路信息。 如，AS1从AS2处得知，经AS2可以到达子网x，AS1告诉AS3，经AS1可以到达子网x。 如果AS3向目的地x发送分组，先向AS1转发，AS1再向AS2转发。 3b 1d 3a 1c 2a AS3 AS1 AS2 1a 2c 2b 1b 3c x * 主机 h2 a b b a a C A B d c A.a A.c C.b B.a c b 主机 h1 在A内的域内路由 在 A和B之间的 域间路由 在 B内的域内路由 例 ：域内路由和域间路由