课程设计题目：基于JA V A的路由选择网络层的协议开发第1章绪论1.1 路由选择的意义路由(Route) 的概念出现于本世纪70 年代,当时的网络结构较简单,因此直至80 年代中期出现了大规模的网络结构后,路由技术才得到了广泛的应用。
在ISO/ OSI 体系结构中,路由技术是第三层(网络层) 的功能,路由选择(Routing)是分组交换系统中的一个重要概念,是指在互联网络中选择将信包(Package) 从信源机(Source Host) 传往信宿机(Destination Host) 的传输路径的过程。
实际的网络协议(如IP协议) ,其本身并不涉及具体的路由选择细节,它只说明路由选择的一般原理和规则,具体的路由选择是指路由表的建立与刷新机制,由一组独立的路由选择协议(RoutingProtocol) 描述。
路由选择的过程是由路由算法来完成的,路由算法可以运行在网络主机上,也可运行在专用的路由设备上,如路由器是一种网络互联设备,其主要功能就是进行路由选择。
1.1.1 路由选择技术的组成路由选择技术涉及两方面内容:最佳路径的选择及信包在网络上的传递。
信包的传递也可称为交换(Switching) , 交换过程相对简单,而路径的选择过程比较复杂。
最佳路径选择最佳路径依赖于不同的衡量标准,例如可使用路径长度作为衡量标准。
在确定最佳路径的路由算法中,路由表(Routing Tables) 是一个重要的数据结构,其中包含了网络的路由信息,算法通过建立和维护路由表进行最佳路径的确定。
路由算法根据算法要求在路由表中填写各种路由信息,其中最基本的是目标/ 驿站(Hop) 信息(见表1) 。
这一组信息告诉路由器,在信包发往信宿机的过程中,最佳选择是将信息转发至下一驿站(Next Hop) 所代表的节点。
当路由器接收到一个输入信息时,首先检查信包的目标地址,然后尝试找出与此目标地址相匹配的下一驿站,若匹配成功则进行信包转发,否则放弃该信包。
除了目标/ 驿站信息外,根据不同的路由算法,路由表中还包含有其它内容,例如最佳路径的衡量标准等信息。
在路由器之间传输的各种信息中,有关路由选择的信息称为路由刷新报文(Routing Update Message) 。
路由刷新报文通常是全部或部分路由表内容。
通过对所有路由信息的分析,路由器可建立一个详细的网络拓扑图。
例如,用于链接-状态路由算法的链接- 状态广播报文通知其它路由器有关自身的链接状态,通过这些信息,路由器可建立一个完整的网络拓扑图,通过拓扑图便可确定到达目标的最佳路径。
1.1.2 路由算法设计目标路由算法往往具有下列一种或多种目标: 最佳性、简单性、稳定性、快速收敛性及适应性等目标。
(1) 最佳性目标要求算法具有寻找最佳路径的能力,最佳路径依赖于算法所采用的衡量标准。
通常路由选择协议严格定义了计算时所采用的衡量标准。
(2) 简单性目标要求算法尽可能简单,即用尽可能小的软件开销提供有效的功能。
当算法运行在低档设备上时效率尤为重要。
(3) 稳定性目标算法必须是稳定可靠的。
在遇到特殊情况(如硬件故障、过载、误操作等) 时,算法能够稳定地运行。
由于路由器位于互联网络的连接点上, 有着相当重要的地位, 若算法不稳定将造成严重的后果。
优秀的路由算法经得起时间的检验并且在任何情况下都能稳定地工作。
(4) 快速收敛性目标路由算法要求能够快速收敛。
这里所指的收敛是指最佳路径能迅速被网上所有路由器所接受。
若发生网络故障导致线路断开或恢复, 相应路由器向网络发出路由刷新报文,促使其它路由器重新计算最佳路径,更新路由表,同时又向网络发送刷新报文,直至所有路由器都相互认可这些最佳路径。
收敛慢的算法将导致路由环问题及网络损耗。
(5) 适应性目标路由算法必须具有较强的适应能力,即能够迅速准确地适应各种网络环境的变化。
例如,如果发现某一网段出现故障,能迅速为所有经过该网段的路径选择另一条最佳路径。
另外,还必须能适应网络带宽、路由器队列大小、网络延迟或其它变化。
1.1.3 路由算法的分类(1) 静态或动态路由算法静态路由是由管理员在路由使用前建立的,只有管理员才能对路由表进行修改。
静态路由算法的设计简单,在可预知网络的通信量且网络结构简单的情况下使用静态路由算法。
静态路由算法不能适应网络情况的变化,因此不适用于目前的大规模及变化频繁的网络结构, 90 年代占主导地位的路由算法是动态路由算法。
动态路由算法通过分析路由刷新报文,能够进行实时调整以适应网络的变化。
当网络发生变化时,根据路由刷新信息, 路由软件重新计算最佳路径并将变化信息向网络上发送。
这些信息在网络上使得网络上的其它路由器也相应运行路由算法刷新其路由表。
(2) 单重路径或多重路径算法单重路径算法对同一信宿机提供一条最佳路径,多重路径算法对同一信宿机提供多条路径以供选择,允许在复杂的线路上进行多重通信。
多重路径算法不仅提高了通信量而且提高了通信的可靠性。
(3) 单层或多层结构算法单层结构中,网络上所有的路由器是对等的,而在多层结构中,存在主干路由器与分支路由器。
信包从分支路由器转发至主干路由器,再传送至信宿机所在区域的主干路由器,再从这一位置通过一个或多个分支路由器最终到达信宿机。
路由系统将一组逻辑节点称为域或自治系统。
在层次结构中,有些路由器只能在自治系统内相互通信,位于自治系统顶层的路由器可与其它自治系统的顶层路由器进行通信。
层次结构的主要优点在于模仿了公司的组织结构,因为网络的大部分通信量存在于分公司内部(自治系统) ,自治系统内的路由器只需清楚系统内其它路由器的情况。
因此系统内的路由算法可进行简化,相应减少了路由刷新时产生的通信量。
(4) 向量- 距离算法或链接- 状态算法这两种算法是两类基本的自动路径广播算法,在此基础上相应有多种协议,典型的有GGP 和SPF 协议。
1.1.4 路由算法衡量的标准路由信息表中包含了交换所需的如何确定最佳路径的要求, 即确定最佳路径的标准, 路由算法根据这些标准进行计算。
复杂的算法往往综合多种标准,常用的衡量标准有:(1) 路径长度路径长度是使用最普遍的标准,一些协议许可网络管理员对网络的线路赋予一定的代价值,在此类情况下,最佳路径就是所经过的每条线路的代价总和。
有些协议定义驿站数量为标准,即路径上所经过的网络设备(如路由器) 的数量。
(2) 可靠性在路由算法中, 可靠性是指每个网络连接的可靠性, 通常用每位的错误率表示。
有些网络连接可能经常发生故障,而发生故障时,有些网络连接能很快或很容易恢复。
可靠性可通过对网络连接赋予相应的数值来确定。
(3) 延迟延迟是指将信包从信源机发送到信宿机所经过的时间,延迟受很多因素影响, 例如: 网络带宽、路由器端口队列数量、网络负荷以及实际传输的距离等。
(4) 带宽带宽是指网络连接的通信能力,虽然带宽代表了网络连接所能达到的最高的通信速率,但往往宽带连接意味着网络更繁忙, 传送一个信包所需要实际时间可能更长, 因此宽带连接并不一定能提供更好的路由能力。
(5) 负载负载是指网络设备(如路由器) 的繁忙程度。
负载有多种计算方式, 如CPU利用率、每秒处理的信包数量等, 对这些参数的监控过程本身也是网络的一种负载。
1.2.目前常用的路由算法1.2.1 最短路径算法寻找两顶点间的最短路径的算法很多目前公认最好的算法是Dijkstra在1959 年提出的它不仅求出从始点到终点的最短路径而且最后所得到的实际上是始点到各顶点的最短路径对Dijkstra 算法进行补充得出的步骤如下：第一步：初始化V={1 2 N} S = {F} D [I ] = L[F I ] Y[ I ] = F 其中I=1，2 ，…N 。
F 表示路径的始点I 表示某一顶点N 表示网络中所有顶点的数目V 是所有顶点的集合L[F I]表示从F 点到I 点的距离S是顶点的集合D 为N 个元素的数组用来存储顶点F 到其它顶点的最短距离Y 为N 个元素的数组用来存储最短路径中在顶点I 之前经过的最近顶点第二步：从V S 集合中找一个顶点T 使得D[T] 是最小值并将T 加入到S 集合中如果V S 是空集合则结束运算第三步：调整Y D 数组中的值在V S 集合中对于顶点T 的邻接各顶点I 如果D[I ]> D[T]+L[I T] 那么令Y[I]=T D[I] = D[T]+L[I T] 继续执行第二步最短路径算法的不足Dijkstra 算法所采用的数据结构及其实现方法总体上说是比较复杂的其缺点也是明显的难以应付公交线路的网络拓扑中的复杂性主要表现如下：（1）数据结构复杂网络在教学和计算领域被抽象为图所以其基础是图的存储表示一般而言无向图可以用邻接矩阵和十字链表表示公交线路网络拓扑很难用现有的数据结构加以完整的表示如果采用现有的最短路径算法分析其建立的公交线路网络图的数据结构模型将非常复杂（2）算法时间长以Dijkstra 算法来计算公交路线最短路径在大数据量的情况下计算速度会慢得让人难以忍受系统设计中要求公交转车的查询必须在较短的时间内完成Dijkstra 算法难以实现（3） Dijkstra 最短路径算法对于网络拓扑图要求简捷对于复杂的广州公交网络拓扑必须对其进行复杂的抽象合并成简捷的网络拓扑图这无疑增加了程序的复杂性而蚁群算法是一种新型的模拟进化算法，自从1991 年M. Dorigo 等人首先提出蚁群算法以来,有许多研究人员对该算法进行研究,并成功地应用于解决复杂组合优化问题. 在研究该算法的过程中,研究人员提出一些改进的算法,研究表明该算法具有很好的通用性和鲁棒性,在离散的组合优化问题中实验,取得了良好的效果。
下章节就着重介绍一下蚂蚁算法。
第2章蚁群算法的基本原理2.1蚂蚁算法的产生蚂蚁是自然界中常见的一种生物，人们对蚂蚁的关注大都是因为“蚂蚁搬家，天要下雨”之类的民谚。
然而随着近代仿生学的发展，这种似乎微不足道的小东西越来越多地受到学者们的关注。
1991年M·Dorigo等人首先提出了蚁群算法（Ant Colony Algorithms）。
人们开始了对蚁群的研究：相对弱小，功能并不强大的个体是如何完成复杂的工作的（如寻找到食物的最佳路径并返回等）。
在此基础上一种很好的优化算法逐渐发展起来。
2.2 蚂蚁算法的算法思想蚁群算法是受到对真实的蚁群行为的研究的启发而提出的.为了说明人工蚁群系统的原理,先从蚁群搜索食物的过程谈起.象蚂蚁、蜜蜂、飞蛾等群居昆虫,虽然单个昆虫的行为极其简单,但由单个简单的个体所组成的群体却表现出极其复杂的行为,原因是什么呢?仿生学家经过大量细致观察研究发现,蚂蚁个体之间是通过一种称之为外激素(pheromone)的物质进行信息传递的.蚂蚁在运动过程中,能够在它所经过的路径上留下该种物质,而且蚂蚁在运动过程中能够感知这种物质,并以此指导自己的运动方向,因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大.蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。