没有合适的资源?快使用搜索试试~ 我知道了~
路由算法大概综述.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 15 浏览量
2022-05-30
21:25:09
上传
评论
收藏 102KB DOC 举报
温馨提示
试读
26页
路由算法大概综述.doc
资源推荐
资源详情
资源评论
因特网的路由选择算法
摘要:路由选择协议是路由器用来完成路由表建立和路由信息更新的通信协议。
路由算法在路由协议中起着至关重要的作用,采用何种算法往往决定了最终寻
径结果。本文主要讨论设计路由算法应具有的原则以及第一个得到广泛使用的
路由算法 RIP 和最短路径 Dijkstra 算法。
1 路由算法概述
1.1 路由算法的特点
路由选择协议的核心就是路由算法,即需要何种算法来获得路由表中的个
项目。一个理想的路由算法应该具有如下特点。
(1)算法必须是正确的和完整的。这里,“正确”的含义是指沿着各路由表
所指引的路由,分组一定能够最终到达目的网络和目的主机。
(2)算法在计算上应简单。路由选择的计算不应使网络通信量增加太多的
额外开销。。
(3)算法应能适应通信量和网络拓扑的变化,这就是说要有自适应性。当
网络中的通信量发生变化时,算法能自适应的改变路由以均衡个链路的负载。
等某个或某些节点、链路发生故障不能工作,或者修理好了再投入运行时,算
法也能及时的改变路由。有时称这种自适应性为“稳健性”( robustness)。
(4)算法应具有稳定性。在网络通信量和网络拓扑结构相对稳定的情况下,
路由算法应收敛于一个可以接受的解,而不应使得出的路由不停的变化。
(5)算法应是公平的。路由选择算法应对所有用户(除了少数优先级高的
用户)都是平等的。例如,若仅仅使某一对用户的端到端时延为最小,但却不
考虑其他的广大用户,这就明显的不符合公平性的要求。
(6)算法应是最佳的。路由选择算法应当能够找出最好的路由,使得分组
平均延时最小而网络的吞吐量最大。我们希望得到“最佳”的算法,但这并不是
最重要的。对于某些网络,网络的可靠性有时要比最小的分组平均延时或最大
吞吐量更加重要。因此,所谓“最佳”只能是相对于某一种特定要求下得出的较
为合理的选择而已。
一个实际的路由选择算法,应该尽可能接近于理想的算法。在不同的应用
条件下,对以上提出的六个方面也可有不同的侧重。
1.2 路由算法的分类
路由选择算法是个非常复杂的问题,因为它是网络中的所有节点共同协调
工作的结果。其次,路由选择的环境往往是不断变化的,而这种变化有时无法
事先知道,例如,网络中出现了某些故障。此外,当网络发生拥塞时,就特别
需要有能缓解这种拥塞的路由选择策略,但恰好在这种条件下,很难从网络中
的各结点获得所需的路由选择信息。
倘若从路由算法能否随网络的通信量或拓扑自适应的进行调整变化来划分,
则只有两大类,即静态路由选择策略与动态路由选择策略。静态路由也叫做非
自适应路由选择,其特点是简单和开销较小,但不能及时适应网络状态的变化。
对于很简单的小网络,完全可以采用静态路由选择,用人工配置每一条路由。
动态路由选择也叫做自适应路由选择,其特点是能较好的适应网络状态的变化,
但实现起来较为复杂,开销也比较大。因此,动态路由选择适用于较复杂的大
网络。
1.3 路由算法的度量标准
路由算法使用了许多种不同的度量标准去决定最佳路径。复杂的路由算法
可能采用多种度量来选择路由,通过一定的加权运算,将它们合并为单个的复
合度量、再填入路由表中,作为寻径的标准。
通常所使用的度量有:路径长度、可靠性、时延、带宽、负载、通信成本
等。
路径长度是最常用的路由 metric。一些路由协议允许网管给每个网络链接
人工赋以代价值,这种情况下,路由长度是所经过各个链接的代价总和。其它
路由协议定义了跳数,即分组在从源到目的的路途中必须经过的网络产品,如
路由器的个数。
可靠性,在路由算法中指网络链接的可依赖性(通常以位误率描述),有
些网络链接可能比其它的失效更多,网路失效后,一些网络链接可能比其它的
更易或更快修复。任何可靠性因素都可以在给可靠率赋值时计算在内,通常是
由网管给网络链接赋以 metric 值。
路由延迟指分组从源通过网络到达目的所花时间。很多因素影响到延迟,
包括中间的网络链接的带宽、经过的每个路由器的端口队列、所有中间网络链
接的拥塞程度以及物理距离。因为延迟是多个重要变量的混合体,它是个比较
常用且有效的 metric。
带宽指链接可用的流通容量。在其它所有条件都相等时,10Mbps 的以太
网链接比 64kbps 的专线更可取。虽然带宽是链接可获得的最大吞吐量,但是
通过具有较大带宽的链接做路由不一定比经过较慢链接路由更好。例如,如果
一条快速链路很忙,分组到达目的所花时间可能要更长。
负载指网络资源,如路由器的繁忙程度。负载可以用很多方面计算,包括
CPU 使用情况和每秒处理分组数。持续地监视这些参数本身也是很耗费资源的。
通信代价是另一种重要的 metric,尤其是有一些公司可能关系运作费用甚
于性能。即使线路延迟可能较长,他们也宁愿通过自己的线路发送数据而不采
用昂贵的公用线路。
2 典型的路由算法
2.1 内部网关协议 RIP
路由信息协议 RIP(Routing Information Protocol)是内部网关协议 IGP 中最
先得到广泛应用的协议。它最初于 1980 年使用在 XNS 中,现在主要应用在
Unix 中。
RIP 是一种分布式的基于距离向量的路由选择协议,是因特网的标准协议,
其最大优点就是简单。RIP 属于一类被称为距离矢量路由的路由算法,即达到
目的地的最佳路径是条数最少的路径,然而,最佳路径也可以由除跳数以外的
其他度量指标决定。
RIP 协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的
网络的距离记录(因此,这是一组距离,即“距离向量”)。
RIP 不能在两个网络之间同时使用多条路由。RIP 选择一条具有最少路由器
的路由(即最短路由),即使还存在另一条高速(低时延)但路由器较多的路
由。
RIP 具有一下特点:
(1)仅和相邻路由器交换信息。如果两个路由之间的通信不需要经过另一
个路由器,那么这两个路由器就是相邻的。RIP 协议规定,不相邻的路由器不
交换信息。
(2)路由器交换的信息是当前本路由器所知道的全部信息,即自己的路由
表。也就是说,交换的信息是:“我到本自治系统中所有网络的(最短)距离,
以及到每个网络应经过的下一跳路由器”。
(3)按固定的时间间隔交换路由信息,例如,每隔 30 秒。然后路由器根
据收到的路由信息更新路由表。当网络拓扑发生变化时,路由器也及时向相邻
路由器通告拓扑变化后的路由信息。
RIP 的缺点:
超过 15 跳便无法到达。
协议以跳数,即报文经过的路由器个数为衡量标准,并以此来选择路由,
这一措施欠合理性。
该路由协议应用到实际中时,很容易出现“计数到无穷大”的现象,这使得
路由收敛很慢。
RIP 采用的是 D-V 算法(距离矢量路由算法),下面是 D-V 算法的优缺点。
优点:算法简单。
缺点:交换的路径信息量大
路径信息传播慢,使得路径信息可能不一致。
收敛速度慢,存在无穷计算问题。
不适合大型网络。
随着 OSPF 和 IS-IS 的出现,许多人认为 RIP 已经过时了。但事实上 RIP
也有它自己的优点。对于小型网络,RIP 就所占带宽而言开销小,易于配置、
管理和实现,并且 RIP 还在大量使用中。但 RIP 也有明显的不足,即当有多个
网络时会出现环路问题。为了解决环路问题,IETF 提出了分割范围方法,即路
由器不可以通过它得知路由的接口去宣告路由。分割范围解决了两个路由器之
间的路由环路问题,但不能防止 3 个或多个路由器形成路由环路。触发更新是
解决环路问题的另一方法,它要求路由器在链路发生变化时立即传输它的路由
表。这加速了网络的聚合,但容易产生广播泛滥。总之,环路问题的解决需要
消耗一定的时间和带宽。若采用 RIP 协议,其网络内部所经过的链路数不能超
过 15,这使得 RIP 协议不适于大型网络。
2.2 Dijkstra 算法
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点
到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到
扩展到终点为止。Dijkstra 算法是很有代表性的最短路径算法,在很多专业课程
中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。Dijkstra 一
般的表述通常有两种方式,一种用永久和临时标号方式,一种是用 OPEN,
CLOSE 表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不
存在负权回路。
3 小结
本文简单介绍了设计路由算法时算法应具有的特点,基于算法的这些特性
可以保证生成路由表的开销、寻径和性能合理。介绍了路由算法的分类度量标
准,对常见的两种路由算法——内部网关协议 GIP 和 Dijkstra 算法进行了简单
的介绍。
参考文献
【1】 谢希仁,计算机网络,2007,05
【2】 Timothy S.Ramteke,网络,2004,11
吴功宜,计算机网络文案 编辑词条
B 添加义项 ?
文案,原指放书的桌子,后来指在桌子上写字的人。现在指的是公司或企业中从事文字工
作的职位,就是以文字来表现已经制定的创意策略。文案它不同于设计师用画面或其他手
段的表现手法,它是一个与广告创意先后相继的表现的过程、发展的过程、深化的过程,
多存在于广告公司,企业宣传,新闻策划等。
基本信息
中文名称
文案
外文名称
Copy
目录
1 发展历程
2 主要工作
3 分类构成
4 基本要求
5 工作范围
6 文案写法
7 实际应用
折叠编辑本段发展历程
汉字"文案"(wén àn)是指古代官衙中掌管档案、负责起草文书的幕友,亦指官署中的公文、
书信等;在现代,文案的称呼主要用在商业领域,其意义与中国古代所说的文案是有区别的。
在中国古代,文案亦作" 文按 "。公文案卷。《北堂书钞》卷六八引《汉杂事》:"先是公府
掾多不视事,但以文案为务。"《晋书·桓温传》:"机务不可停废,常行文按宜为限日。" 唐
戴叔伦《答崔载华》诗:"文案日成堆,愁眉拽不开。 "《资治通鉴·晋孝武帝太元十四
年》:"诸曹皆得良吏以掌文按。"《花月痕》第五一回:" 荷生 觉得自己是替他掌文案。"
旧时衙门里草拟文牍、掌管档案的幕僚,其地位比一般属吏高。《老残游记》第四回 :"像
你老这样抚台央出文案老爷来请进去谈谈,这面子有多大!"夏衍《秋瑾传》序幕:"将这 阮
财富 带回衙门去,要文案给他补一份状子。"
文案音译
文案英文:copywriter、copy、copywriting
文案拼音:wén àn
现代文案的概念:
文案来源于广告行业,是"广告文案"的简称,由 copy writer 翻译而来。多指以语辞进行广
告信息内容表现的形式,有广义和狭义之分,广义的广告文案包括标题、正文、口号的撰
写和对广告形象的选择搭配;狭义的广告文案包括标题、正文、口号的撰写。
剩余25页未读,继续阅读
资源评论
oligaga
- 粉丝: 52
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功