4.1分布式路由算法导论： 二、通信延迟及其原因(cont'd) 2、路由 ·决定如何选择路径以便将消息传递到目的地。 ●本章主要考虑路由 2008.3.28 Advanced Operating System 7/91
2008.3.28 Advanced Operating System 7/91 4.1分布式路由算法导论： 二、通信延迟及其原因（cont'd） 2、路由 ⚫ 决定如何选择路径以便将消息传递到目的地。 ⚫ 本章主要考虑路由
4.1分布式路由算法导论： 二、通信延迟及其原因(cont'd) 3、流量控制 。流量控制决定在消息沿路径传递时如何分配网络资 源， ·网络资源包括： 。信道 。缓冲区 2008.3.28 Advanced Operating System 8/91
2008.3.28 Advanced Operating System 8/91 4.1分布式路由算法导论： 二、通信延迟及其原因（cont'd） 3、流量控制 ⚫ 流量控制决定在消息沿路径传递时如何分配网络资 源， ⚫ 网络资源包括： ⚫ 信道 ⚫ 缓冲区
4.1分布式路由算法导论： 二、通信延迟及其原因(cont'd) 4、交换技术 这是一个实际的机制，它决定消息如何从一个输入信 道转到一个输出信道。 交换技术 存储转发 分割-通过 分组交换 电路交换 虚拟分割通过 虫孔路由 2008.3.28 Advanced Operating System 9/91
2008.3.28 Advanced Operating System 9/91 4.1分布式路由算法导论： 二、通信延迟及其原因（cont'd） 4、交换技术 ⚫ 这是一个实际的机制，它决定消息如何从一个输入信 道转到一个输出信道。 交换技术 存储-转发 分割-通过 分组交换 电路交换 虚拟分割-通过 虫孔路由
4.1分布式路由算法导论： 三、路由算法类型 路由算法类型包括： 1. 特殊VS.一般 2. 最短VS.非最短 3. 确定型VS.适应型 4. 源路由Vs.目标路由 5. 容错型VS.非容错型 6. 冗余型VS.非冗余型 7.死锁避免型VS.非死锁避免型 2008.3.28 Advanced Operating System 10/91
2008.3.28 Advanced Operating System 10/91 4.1分布式路由算法导论： 三、路由算法类型 ⚫ 路由算法类型包括： 1. 特殊 vs. 一般 2. 最短 vs. 非最短 3. 确定型 vs. 适应型 4. 源路由 vs. 目标路由 5. 容错型 vs. 非容错型 6. 冗余型 vs. 非冗余型 7. 死锁避免型 vs. 非死锁避免型
4.1分布式路由算法导论： 1、一般型路由和特殊型路由 一般型路由算法 。适合于所有类型的网络 ·但是对于某种特定网络不是很有效 特殊型路由算法 。只对特定的网络类型有效，如超立方、网格等 这些算法由于利用了特定网络的拓扑属性，所以效 率往往较高。 2008.3.28 Advanced Operating System 11/91
2008.3.28 Advanced Operating System 11/91 4.1分布式路由算法导论： 1、一般型路由和特殊型路由 ⚫ 一般型路由算法 ⚫ 适合于所有类型的网络 ⚫ 但是对于某种特定网络不是很有效 ⚫ 特殊型路由算法 ⚫ 只对特定的网络类型有效，如超立方、网格等 ⚫ 这些算法由于利用了特定网络的拓扑属性，所以效 率往往较高