高级操作系统advancedoperatingsystem

高级操作系统advancedoperatingsystem内容摘要：

P2 4 P3 6 P5 2∞  ARPA路由算法： 举例（ cont39。 d） P 1P 2P 3P 4 P 54531222 0P2 7 P3 9 P1 11 P3 7 P4 35 P1 12 P2 6 P4 46 P5 20 P2 4 P3 6 P5 ∞  P 1P 2P 3P 4 P 54531222 0P2 79 P3 911 P1 11 P3 79 P4 5 P1 12 P2 68 P4 6 P5 20 P2 46 P3 68 P5 ∞  …… ARPA路由算法： 举例（ cont39。 d）  上述过程一直持续到达到一个新的稳定点， P1， P2， P3， P4分别用了 20， 19， 17， 20个时间间隔，如下图所示。 ARPA路由算法（ cont39。 d）  ARPA路由算法 中 每个节点对所有邻居都发送相同消息，对接收节点不做任何标识。  这样，某些节点就会接收无用消息。  在链接节点失效时候，这些消息会导致我们 不期望的循环。  例如 ARPA路由算法： 不期望的循环，举例  例如， P4和 P5链接失效时，P4的最短路径为 4，但是这个 4来自于 P2，而 P2到 P5的最短路径原来就依赖于P4与 P5的链接，由于 P4使用 P2的信息时， P2的信息尚未得到更新，导致出现不期望的循环：P4P2P4 P 1P 2P 3P 4 P 54531222 0P2 7 P3 9 P1 11 P3 7 P4 3 P1 12 P2 6 P4 4 P5 20 P2 4 P3 6 P5 2∞  ARPA路由算法： 不期望循环的消除  循环的消除是在路由消息中包含路径的所有节点，并把这些消息发给邻居节点。  然而，它的效率较底，因为它的额外开销太大。  Shin和 Chou，提出了一个避免循环算法：只需在路由消息中存储路径中最近的 个节点， 与相应网络中循环的最大长度有关 l l  一般类型网络的路由算法适用于所有拓扑类型的网络。 但是，  每个节点需要维持路由延迟表，而且  不适用于特殊类型的网络，原因是效率太低。  得益于特殊网络的拓扑特性，可以不使用路由延迟表而构造最短路径路由算法  本节介绍三种特殊网络的单播路由算法：  双向环单播路由算法  网格和圆环单播路由算法  超立方单播路由算法 双向环单播路由算法  在双向环上进行决定型单播路由非常简单：  消息沿着一个方向被转发：顺时针或者逆时针  由于消息可以沿两个方向发送，所以由源节点根据目标节点的位置决定发送方向：  如果目标离顺时针方向近，则用顺时针方向；  否则选择逆时针方向。  一个消息通过几个中间节点按照顺时针或逆时针方向传递，直到到达目标节点。 双向环单播路由算法（ cont39。 d ）  因此，双向环上的单播路由算法可以使用两条路径：  一条沿着顺时针，  另一条沿着逆时针。  消息  也可以被复制，然后每个方向发一个拷贝；  也可以分成两半，每半转发到一个方向。 双向环单播路由算法： 算法一般化  双向环是 k元 1维立方，即只有一维度。  若维度大于 1，例如网格和超立方，就用 有序维度路由  每次将每个消息向一个维度路由  圆环：在一个维度中的各点以环的方式连接起来，带有周边连接  网格：一个维度中的各点以线性排列的形式连接起来，没有周边连接 双向环单播路由算法： 算法一般化（ cont39。 d ）  环形路由方法 可用于在一个维度中对消息进行路由。  沿着一个线性排列路由是很简单的。  当消息到达每个维度的对等者时，就使用下一个维度。  通过使经过的各个维度保持一个单调的顺序，就可以保证不会发生死锁。  但这种方法适应性差。 网格和圆环单播路由算法  网格和圆环是 k元 2维立方。  圆环有周边邻接，  网格没有周边连接。  类似地， 3维网格和圆环是 k元 3维立方。  本小节介绍  2维网格的 XY路由  最短且完全适应路由  折线路由  最大最短路径路由 网格和圆环单播路由算法： 2维网格的 XY路由  在 2维网格中， 有序维度路由 叫 XY路由。  每个节点的地址为 (x,y)。  消息首先沿着 X维度转发，然后沿着 Y维度路由。  特别地，若源和目标分别为 (sx,sy)和 (dx,dy)，则路由消 息将在 X维度上走 |dx – sx| 步， 然后在 Y维度上走 |dy– sy|步 网格和圆环单播路由算法： 最短且完全适应路由  在最短且完全适应路由中，  每个中间节点，包括源节点，都要充分利用所有可行的最短路径。  在 2维网格中，  只要 dx–sx≠0且 dy–sy≠0，每个节点在选择邻居时总有两个选择。  一个好的适应性路由算法应该能选择任意－个邻居并能尽可能地保持 dx –sx≠0且 dy–sy≠0的情况。  显然， XY路由是最不灵活的一个。 网格和圆环单播路由算法： 适应性路由图示 只要 dx–sx≠0且 dy–sy≠0， 每个节点在选择邻居时总有 两个选择： X方向或者 Y方向 网格和圆环单播路由算法（ cont39。 d ）  如果每个链接（信道）拥塞的概率是一样的，那么在最短路由的限制下，哪一个是最好的路由方法呢。  这里的最好是指在这种路由方法下，消息到达目标的延迟最小。 网格和圆环单播路由算法： 折线路由  Badr和 Podar提出了一个 2维网格的折线路由方法  首先建立一个包含源和目标的矩形．  源 s=(sx, sy)和目标 d=(dx, dy)分别位于矩形的两个对角  从目标 d=(dx,dy)引出一条线 L，这条线将平分经过点 d的矩形的两边所组成的角。 消息将沿着直线 L 路由，但仍在矩 形内部。 即所有的中间节点都是依照它们到 L的距离来选择的 ——在所有合格 的节点中，总是选择距离 L 最近的 一个。 直线 L 网格和圆环单播路由算法： 折线路由（ cont39。 d ）  在 2维 圆环 中，折线路由可能不是最优的，因为一个中间节点可能有多于两个的合格邻居。  特别，对一个 n为偶数的 n n的圆环，存在一个具有四个合格邻居的节点。 而且，有 2(n2)个节点，它们和源的距离为 n／ 2个行或列，因此，在最短路径上就有三个方向。 网格和圆环单播路由算法（ cont39。 d ）  对于最优解， Wu在 k元 M维立方 的最短路径路由算法的基础上提出了一个最大最短路径 (MP)路由算法：  路由消息总是被转发到与目标节点存在最大个数的最短路径的那个邻居节点。  基于最大最短路径的路由算法是一个对 2维网格和 M维立方都是最优的路由算法。  然而，关于最大最短路径对 2维圆环是不是最优的仍然是一个未决的问题。 网格和圆环单播路由算法（ cont39。 d ）  若源和目标都有四个邻居， 那么很容易在它们之间建立 四个边（或点）分离的路径， 如图。  一般地，设 k(k≤4)是源和目 标节点所具有的最小的邻居 的数目，那么，在源和目标 之间就存在 k个边（点）分离 的路径。 超立方单播路由算法  对超立方的单播路由可采用一种相对简单的方法，不必在每个节点中存储路由延迟表。  一个 n维超立方（ ncube）可定义为。