- 经验
- 3737
- 分贝
- 0
- 家园分
- 77131
- 在线时间：
- 10 小时
- 最后登录：
- 2017-8-22
- 帖子：
- 857
- 精华：
- 8
- 注册时间：
- 2003-4-10
- UID：
- 6039
注册：2003-4-10
|
发表于 2004-11-19 16:03:00
|显示全部楼层
路由选择的定义
路由选择的组成
路由选择算法
网络协议
一、路由选择的定义
路由选择（Routing）是指选择通过互联网络从源节点向目的节点传输信息的通道，而且信息至少通过一个中间节点。表面上看，路由选择与桥接完成的工作相同，但实际上它们并不相同，两者的区别在于桥接作用于OSI参考模型的第二层（数据链路层）而路由选择作用于第三层（网络层）。在从源节点向目的节点传输信息过程中，两者是利用不同的信息，采用不同的方法完成各自的任务。
在计算机科学文献中，路由选择这个概念已有二十多年的历史，但是直到八十年代中期，它才在商业领域得以发展，这是因为七十年代多是非常简单的同类网络，大规模网络互联只在近几年才开始胜行。
二、路由选择的组成
路由选择包括两个其本操作，即决定最佳躜 路径和通过互联网络传输信息。在本书后面的章节，路由选择即指交换，因为交换简单 明了，而路径的确定相对复杂。
计量标准是一个测量标准，路由选择算法常用它确定达目的节点的最佳路径的讨校酚裳≡袼惴ㄐ枰跏蓟臀ぢ酚裳≡癖恚╮outing table）路由选择表中包含路由选择信息根据路由选择算法的不同而不同。
路由选择算法把各种信息写入路由选择表。目的节点或相关节点会告诉当前路由器如何以最优路径传送数据包。当路由器接收到数据包后，检查目的地址，并将目的地址与相关节点进行比较。图5-1是一个简单的目的节点或相关节点的路由选择表。
路由选择表也可以包含其它信息，如有关预期路径的信息。路由器通过比较路径长度来决定最佳路由，路径长度根据所使用的路由选择算法的不同而有所不同。本章后面将先容几种不同的路径长度算法。
路由器之间通过传输多种消息来维护路由选择表，修正路由消息就是其中的一种。修正路由消息通常是由全部或部分路由选择表组成，路由器通过分析来自所有的其它路由器的最新消息，构造出一个完整的网络拓扑结构详图。链路状态广播是在路由器之间传递的另一种消息，它通知路由器有关发送链路的状态，并可以用来构造完整的网络拓扑结构图，从而使路由器决定到达网络目的节点的最佳路由。
交换算法
交换算法相对照较简单，且对于大多数路由选择协议来说，交换算法基本相同。当一台主机向另一台主机发送数据包进，类推主机通过某种方式获取路由器地址后，通过目的主机的协议（网络层）地址将数据包发送到指定的路由器物理（介质访问控制层）地址。
通过使用交换算法检查数据包的目的协议地址，路由器可确定其是否知道如何转发数据包，如果路由器不知道如何将数据包转发到下一个节点，将丢弃该数据包，如果路由器知道转发，就把物理目的地址变换成下一个节点的地址，然后转发该数据包。
实际上，下一个节点有可能是最终目的主机。如果不是目的主机，下一个节点通常是实行相同的处理过程的另一个路由器，数据包在互联网上传输时，其物理地址发生变化，但协议地址总是保持不变，图5-2说明了这个过程 。
以上讨论了末端系统中源端点之间的交换问题。国际标准化组织OSI已经颁布出一系列用于描述这个过程的术语，其中规定，没有在子网间转发数据封包能力的网络设备称作末端系统ES（end system），具有转发能力的物理设备称作中介系统IS（intermediate system）IS进一步划分为路由选择域 内IS和路由选择域间IS，路由选择域（routing domain）通过视为互联网络的一部分，它由一套特定的管理规则共同管理控制，也称作自治系统（autonomous system）采用某些协议，路由选择域可划分成路由选择区域（routing area）域内路由选择协议只能用于路由选择区域内和路由选择区域间的交换。
三、路由选择算法
由于某些关键特性的不同，各种路由选择算法也不同，首先，算法设计者的设计目标会影响路由选择协议的运行结果；其次现有各种路由选择算法对网络和路由器资源的影响不同；最后，不同的计量标准也会影响最佳路径的计算结果。下面分别讨论这些路由选择算法的特性。
设计目标
路由选择算法通常具有下列一个或多个设计要求：
（1） 最优性；
（2） 简易性和低开销
（3） 强壮性和稳定性
（4） 快速收敛性
（5） 灵活性。
最优性是指路由选择算法选择最优路径的能力。最优路径取决于计量标准和用于计算的权值，例如一个路由选择算法可以同时使用站点的数目和延迟开销，但在计算过程中更重视延迟开销，因此，路由选择协议必须严格定义其计算方法。
路由选择算法应尽可能地简单。换言之，路由选择算法必须用量少的App和最低的开销来提供最有效的功能，实现路由选择算法的App运行在有限物理资源的计算机上，效率显得尤为重要。
路由选择算法必须具有强壮性，这意味着它们必须在出现异常或非预见性情况时（如硬件故障，高负荷状态和不正确的操作），也能正常运行，由于路由器位于网络连接点上它们发生故障会引起更为严重的问题，因此，最佳路由选择算法必须经受时间的考验，且在各种不同的网络环境下有很好的稳定性。
此外，路由选择算法必须能够迅速收敛，收敛是所有路由器在最佳路径上取得一致的过程，当一个网络由于某种事件造成路由停机或开通时，路由器就会发送修正路由消息，该消息在网络上传播，引发路由器重新计算最优路由，并最终促使所有路由器承认新的最优路由。路由选择算法收敛过慢，会导致路由循环或网络发生故障。
假设数据包在时间t1到达路由器1此时路由器1已经被更新，它知道到达目的节点是最优路由，并要求路由器2成为下一节点，因此，路由器1 转发数据包到路由器2。但如果路由器2还未被更新，它仍认为最优的下一个节点是路由器1，路由器2又把数据包送回到路由器1 ，这样，数据包持续在这两个路由器之间来回传送，直到路由器2收到路由修正命令或者达到数据包允许转发的最大的次数为止。
路由选择算法还应当具有灵活性，这就意味着路由选择算法必须迅速准确地适应不同的网络环境。例如假设某一网段失败，路由选择算法在意识到这个问题后，应能尽快为所有路由选择最佳路径，避免使用那段网络。路由选择算法在设计时应能适应网络带宽，路由器队列大小和网络延迟以及其它的变化。
路由选择算法类型
按类型划分，路由选择算法主要包括以下几种：
（1） 静态和动态路由选择算法
（2） 单路径和多路径路由选择算法
（3） 平面和分层路由选择算法
（4） 主机智能和路由器智能路由选择算法；
（5） 域内和域间路由选择算法；
（6） 链接状态和距离向量路由算法
1． 静态和动态路由选择算法
严格地说，静态路由选择算法不是一种算法，因为网络管理员在路由选择开始前就已了建立映射表，如果网络管理员不改变它们，这此映射将保持不变。静态路由选择算法设计简单，并在网络信息流相对可以预见且网络设计相对简单的环境里运行较好。
由于静态路由选择算法不能对网络的变化作出反映，所以，它不能适合当今大型，易变的网络环境。九十年代以来，绝大多数优秀的路由选择算法都是动态的，这些动态路由选择算法通过分析接收的路由修正消息适应网络环境的变化。路由选择App接收到网络发生变化的消息后，就会重新计算路由，并发出路由修正消息。路由器接收到这些消息后，便重新进行计算，并改变路由选择表。
静态路由选择算法可以弥补动态路由选择路算法的某些不足。例如为所有无法选择路由的数据包指定一个最终路由器，即将所有无法选择路由的数据包转发到该路由器来，以保证所有数据包都得到某种方式的处理。
2． 单路径和多路径路由选择算法
一些复杂的路由选择协议支撑多路径到达同一目的节点，与单路径算法不同，这些多路径算法允许信息流在多条线上进行复制，多路径算法的优势是提高了数据吞吐率和可靠性。
3． 平面和分层路由选择算法
一些路由选择算法在平面空间运行，而另一些路由选择算法采用分层空间。在平面路由选择算法中，所有路由器的对等的，而在分层路由选择算法中，路由器被划分成主干路由和非主干路由器。来自非主干路由器的数据包先被传送到主干路由器中，然后通过主干路由器转发到目的节点域，最后通过一个或多个非主干路由器到达目的节点。
路由系统常将逻辑节点组称为域，自主系统或区域。在分层路由选择算法中，任一域中只有一部分路由器可以与其它域中的路由器通信，而其它路由器只能与该域 中的路由器通信。在超大型的网络中，可能还存在更多的层次，一般都是位于最高层的路由器形成路由器的主干。
分层路由类似企业的组织结构，其主要优点是能较好地支撑信息流模式。但由于大多数网络通信发生在小企业群（域）中，且域内路由器只需要了解域内的其它路由器即可，因此，可以简化它们的路由选择算法，以相应地减少路由修正消息流发布。
4．机智能和路由器智能路由选择算法
一些路由选择算法假定源节点决定整个发送路由，这就是通常所说的源路由选择（source routing）.在源路由选择系统里，路由器只是一个存储和发送设备，负责向下一节发送数据包。在这种系统中，主机具有路由选择的智能。
而其它的算法假定主机对路由器一无所知，路由器根据自己计算的结果来确定互联网上的路径。在这种系统中，路由器具有路由选择的智能。
如果把主机智路由选择算法与路由智能路由选择算法结合起来使用，倒是一种最佳方法。虽然主机智能路由选择算法在实际发送数据包之前就能发现到达目的节点的所有可能路由，并能根据不同系统对最优路由的不同要求做出选择，但这种选择所有路径的方法常常需要耗费大量的时间。
5． 域内和域间路由选择算法
一些路由选择算法只在域内运行，而另一些路由选择算法可在域内或域间运行。这两种算法在本质上有所不同。因此，一个最优的域内路由选择算法并不一定是最佳的域间路由选择算法。
6． 链接状态和距离向量路由选择算法
链接状态路由选择算法（也称作最短路径优先算法）将路由选择信息发送至互联网络的所有节点上，每个路由器只能传递描述其自身链接状态的那部分路由选择表。而距离向量路由选择算法（也称作贝尔曼---福特算法）要求每个路由器将路由选择表的全部或部分传送到与其相邻的路由器中，实际上，链接状态路由选择算法只传送小部分的更新消息，而距离向量路由选择算法将大部分或全部的更新消息传送到与其相邻的路由器中。
由于链接状态路由选择算法收敛速度较快，因此，它比距离向量路由选择算法更易避免路循环。但由于链接状态路由选择算法需要占用更多的CPU能量和内存资源，因此，它比距离向量路由选择算法难以支撑和实现。总的来说，这两种算法在大多数情况下运行良好。
路由选择计量标准
前面已经先容过，路由选择表中包含交换App选择最佳路由的信息，但路由选择表是如何建立的呢？路由选择表中包含的信息是什么性质的呢？路由选择算法又是如何决定最优路由的呢？
路由选择算法使用许多不同的计量标准确定最优路由，一些复杂的路由选择算法将多种计量标准融为一体。常用的计量标准有如下几种：
（1） 路径长度；
（2） 可靠性；
（3） 路由选择延迟；
（4） 带宽；
（5） 负载；
（6） 通信开销；
路径长度（path length）是最普通的一种计量标准。在路由选择协议允许网络管理员为每个网络链路分配任意权值的情况下，路径长度是指所经过的每条链路的权值之和，而在路由选择协议定义了站点数目情况下，路径长度是指数据包从源节点到目的节点过程中通过网络产品（如路由器）的数目。
在路由选择算法中，可靠性（reliability）是指每个网络链路的可靠性（通常用比特-错误率描述），即网络链链路是否容易出现网络故障；一旦发生故障，是否能迅速修复在进行可靠性等级分配时，应将所有影响可靠性因素都考虑在内。通常由网络管理员给网络链路分配可靠性等级，而这些等级一般用数值表示。
路由选择延迟（routing delay）指的是通过互联网络从源节点发送数据包所需的时间，延迟时间取决于诸多因素，其中包括网络链路的带宽及其网络堵塞程度，沿途每个路由器端口的队列和传输的物理距离等。由于延迟受几种重要因素的影响，因此，它是一种应用最广且最有用的计量标准。
带宽（banfwidth）是指链路传输信息流容量的能力。在所有其它条件相同的情况下，一个10Mbps以太网链路优于一个64Kbps的租用链路。尽管带宽越大表示链路的传输能力越强，但通过较大带宽链路的路由 并不一定比通过较慢链路的路由更好，因为如果较快的链路非常繁忙，那么，通过它向目的节点传送数据包所需的实际时间可能会更长。
负载（load）是指网络资源（如路由器）的繁忙程度，它可用多种方式进行计算，其中包括CPU的利用率和每秒处理数据包的次数，当然，持续不断地监控这些负载参数本身就要占用资源。
通信开销（communiation cost）是另外一种重要的计量标准，尤其是当企业关心运行费用胜过运行性能时。对于这些企业来说他们宁可将数据包在自己的链路上进行传输（即使这样可能增加链路延迟）也不愿花钱（省时间）在公用链路上传输。
四、网络协议
路由协议通过互联网上的路由选择协议进行传送。通常，路由协议也称作网络协议（network protocol）。根据用户在源设备与 目的设备间的通信需要，这些网络协议可实行多种功能，而这些功能在协议簇中存在巨大的差别。网络协议作用于OSI参考模型的上面四层，即传输层，会话层，表示层和应用层。
人们常将路由协议和路由选择协议混淆，路由协议是在互联网络上进行路由协议，其中包括网际协议（IP），DECnet,AppleTalk,Novell Netware,OSI,Banyan,Xerox NS等。而路由选择协议是指那些实行路由选择算法的协议，即通过互联网络操作网络的协议，其中包含内部网络关路由选择协议（IGRP）增强型内部网关路由选择协议（Enhanced IGRP）开放最短路径优先（OSOF）外部网关协议（EGP）边缘网关协议（BGP），中介系统到中介系统（IS-IS）和路由选择信息协议（RIP），本文后续章节还要详细讨论路由选择协议和路由选择协议。
|
|
