计算机网络（十四）——因特网的路由选择-Toy模板网

这篇具有很好参考价值的文章主要介绍了计算机网络（十四）——因特网的路由选择。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

随着路由器数量的增大，传统的距离向量算法是无法在如此大量的路由器中收敛的。同时每隔ISP管理着自己的路由器网络，希望按照自己的意愿运行路由器，而不是互联网中所有的路由器都运行一种路由选择协议。这些都可以通过自洽系统（Autonomous System）解决。

（1）自洽系统

1. 因特网自洽系统内部的路由选择

在一个AS内运行的路由选择算法叫做自洽系统内部路由选择协议。

OSPF是一种公众可用的链路状态协议。
（1）定义

（2）优点

安全：只有被信任的路由器才能参与一个AS内的OSPF协议。
允许使用多条相同费用路径：无需仅选择一条路径承载所有流量。
对单播和多播路由选择的综合支持
支持在单个AS中的层次结构
①主干区域包含AS中所有区域边界路由器，它的主要作用是为AS内部区域之间提供路由选择。
②区域边界路由器负责为流向区域以外的分组提供路由选择。
③AS边界路由器负责连接其他AS。

在AS内部的分组选路完全遵循AS内部路由选择协议，如OSPF。当分组跨越多个AS路由时，需要AS间路由选择协议，如BGP。
在因特网中，所有AS运行相同的AS间路由选择协议：边界网关协议BGP（Border Gateway Protocol）。

BGP是众多ISP的粘合剂。作为所有AS都运行的AS间路由选择协议，它有以下作用：

（1）问题：为什么采用不同的AS内与AS间路由协议？
策略

规模

性能

BGP允许AS向其他AS发送BGP报文，通告它的可达性信息。因此对于任意一个AS可以从它的邻居节点收到BGP报文获得可达性信息。那么BGP报文是如何从一个AS传递到它的邻居AS中的呢？
热土豆算法,计算机网络,网络,网络协议
首先，在每个AS中，路由器被划分为两种类型：

AS正是通过路由器间发送报文实现通告BGP可达信息。在BGP中，每对路由器通过使用179端口的半永久TCP连接交换路由选择信息。每条TCP连接以及通过该连接发送的BGP报文，称为BGP连接。BGP连接可以根据建立连接的两个路由器所在的AS划分为两种类型：

这样AS通过eBGP将BGP报文传送到相邻AS中。相邻AS再通过iBGP将BGP报文传送到AS内所有路由器。按照上述步骤反复执行下去，直到通告完成所有AS。

由上文所述我们可以归纳出BGP通告的两个特征：

BGP报文：
①OPEN：与peer建立TCP连接，并认证发送方。
②UPDATE：通告新路径（或撤销原路径）。
③KEEPALIVE：在无UPDATE时，定期发送保持BGP会话的TCP连接。也用于对OPEN请求的确认。
④NOTIFICATION：报文先前报文的差错。也用于关闭连接。

因为在真实网络中，给定源到目的地可能有多条路径。我们不可能将这些路径都加入路由器的转发表中。因此需要通过BGP路由选择获得最好的路径。

在介绍BGP路由选择之前，先介绍以下BGP路由的结构。BGP路由由两个部分组成，路由=前缀+BGP属性：

前缀
BGP属性
①AS-PATH(AS路径)：前缀通告经过的AS序列。还可以用于防止通告环路。
②NEXT-HOP（下一跳）：是AS-PATH起始路由器的IP地址。

下面，我们将介绍最简单的热土豆算法，和在更复杂的路由选择算法下的三条准则。
（1）热土豆算法
从名字不难看出，热土豆算法应该是一种自私的算法，就是将烫手的山芋赶快扔出去。因此热土豆算法的思想如下：

思想：选择具有最小开销的NEXT-HOP的路由。
①理解：热土豆路由选择会使用到AS内部选择协议（OSPF），用于计算最低开销路径。当存在多条最低开销路径时，就会根据NEXT-HOP的开销选择路由。
缺点：忽略了在AS间端到端的开销（时延）。
①因为自私的只考虑了AS内部的开销，而忽略了AS间的开销。

在更复杂的BGP路由选择算法中，会依据三条准则逐个判断，是一种基于决策的路由选择算法。
（2）三条准则

本地偏好：本地偏好是一种策略属性，完全由AS网络管理员设置。具有最高本地偏好值的路由被选择。

①路由器只为客户提供路由。因此B不会向C通告路径BAW。
②X不会转发B到C之间的路由。
最短AS-PATH：对于具有相同本地偏好值得路径，将选择具有最短AS-PATH的路由。
最近NEXT-HOP：在前面两个条件满足后，在根据热土豆算法选择具有最小NEXT-HOP开销的路由。