某篇论文涉及到该部分内容，故翻出之前的笔记重整理了下

<h1 id="heading">互联网自治系统</h1>
<p>当互联网的范围越来越大，路由表也将变得越来越大，难以存储，甚至难以在短时间内计算出最优的路由。</p>
<p>要解决该问题，需要将互联网划分为多个自治的子集，称为自治系统(Autonomous System, AS)。系统内部的设备数目有限，可以直接使用路由表等技术进行路由选择，而系统间则无需过多考虑路由细节，只需要对自治系统进行选择即可。<br>
这种分层次的路由选择可以极大地减轻互联网路由选择的负担。</p>
<h2 id="igp">内部网关协议（IGP）</h2>
<p>自治系统内部所使用的路由选择协议，也称为域内路由选择协议<br>
主要有 RIP 和 OSPF</p>
<h3 id="rip">RIP算法</h3>
<p>RIP 是应用层协议，使用 UDP 传送数据（520端口）</p>
<p>其选择的原则是：好的路由就是通过路由器少的路由（跳数少）。因此其选择的不是时间最短的路由，而是跳数最少的路由。RIP 允许一条路径最多包含 15 个路由器（最多 15 跳），当距离为 16 时表示不可达。因此 RIP 只适用于小型网络。这样做目的是为了防止环路，导致拥塞。</p>
<p>任意两个使用 RIP 协议的路由器之间每 30s 广播一次 RIP 路由更新信息。默认不支持子网掩码的 RIP 广播，在 RIP2 中支持变长子网掩码和 CIDR。默认超时时间是 180s</p>
<p><strong>特点</strong></p>
<ul>
<li>仅和相邻路由器交换信息</li>
<li>路由器交换的信息是当前路由器知道的所有信息（路由表）</li>
<li>按规定时间定时交换信息</li>
</ul>
<p><strong>优点</strong></p>
<ul>
<li>实现简单</li>
<li>开销小</li>
<li>收敛过程快</li>
</ul>
<p><strong>缺点</strong></p>
<ul>
<li>限制了网络规模</li>
<li>路由器间交换完整路由表，网络规模越大，开销也越大</li>
<li>网络故障时，会出现慢收敛现象：需要较长时间才能将此消息传到所有路由器</li>
</ul>
<h4 id="-">距离-向量路由算法</h4>
<p>所有的结点定期将他们的整个路由选择表传送给所有与之直接相连的结点</p>
<ul>
<li>每条路径的目的地（另一节点）</li>
<li>路径的代价（距离、跳数）</li>
</ul>
<p>所有结点都必须参与向量交换，以保证路由的有效性和一致性。同时所有结点都监听从其他结点传送来的路由选择更新信息，并在下列情况更新路由选择表：</p>
<ul>
<li>被通告一条新的路由，该路由在本结点的路由表中不存在，此时本地系统加入这条新路由</li>
<li>发送来的路由信息中有一条到达某个目的地的路由，该路由比当前使用的路由有较短的距离。此时就用经过发送路由信息的结点的新路由替换路由表中到达那个目的地的现有路由</li>
</ul>
<p>距离-路由算法的实质是迭代计算一条路由中的站段数或延迟时间，从而得到到达一个目标的最短通路。</p>
<p><strong>缺点</strong></p>
<ul>
<li>更新报文的大小与通信子网的结点个数成正比，大的通信子网将会导致很大的更新报文。</li>
<li>可能会遇到路由环路问题</li>
</ul>
<h3 id="ospf">OSPF算法</h3>
<p>开放最短路径优先（OSPF）是网络层协议，不使用 UDP 或 TCP 传输，而是直接使用 IP 数据报传输（协议字段为 89）</p>
<p>可以将不同链路设置成不同的代价，针对不同类型业务计算出不同的路由，更为灵活。可以做到多路径的负载均衡</p>
<p>在层次路由中，OSPF 将每个自治系统划分成更多区域，每个路由器都知道在本区域内如何把分组路由到目的地的细节，但不知道别的区域的内部结构。采用分层次划分的方法可以使交换信息的种类增多的， 但是也使 OSPF 协议更加复杂了。这样做能使每一个区域内部路由信息的交换量大大减小，因此可用于规模很大的自治系统。</p>
<p>OSPF 采用泛洪法广播消息。由于 OSPF 本身会在 AS 的基础上继续划分区域，泛洪仅限于当前路由器所在的区域，因此并不会对网络造成额外的负担，反而可以很快地实现数据的统一。</p>
<p>共包含五种分组类型</p>
<ul>
<li>问候分组：用来发现和维持邻站的可达性</li>
<li>数据库描述分组：向邻站给出自己链路状态数据库中的所有链路状态项目的摘要信息</li>
<li>链路状态请求分组：向对方请求发送某些链路状态项目的详细信息</li>
<li>链路状态更新分组：用洪泛法对全网更新链路状态</li>
<li>链路状态确认分组：对链路更新分组的确认</li>
</ul>
<p>OSPF 通常每10s交换一次问候分组，每30min刷新一次数据库链路状态。不存在慢收敛现象</p>
<h4 id="heading-1">链路状态路由算法</h4>
<p>链路状态路由算法要求每个参与该算法的结点都有完全的网络拓扑信息，它们执行两项任务：</p>
<ul>
<li>主动测试所有邻接结点的状态，两个共享一条链路的结点是相邻结点，它们连接到同一条链路或同一广播型物理网络</li>
<li>定期将链路状态广播给所有其他结点</li>
</ul>
<p>当链路状态报文到达时，路由节点便使用这些信息去更新自己的网络拓扑和状态视野图，一旦链路状态发生变化，结点对更新了的网络图利用 Dijkstra 最短路径算法重新计算路由。</p>
<p><strong>特征</strong></p>
<ul>
<li>向本自治系统中所有路由器发送信息，使用泛洪法</li>
<li>发送的信息就是路由器相邻的所有路由器的链路状态，之包括该路由器已知的部分信息。</li>
<li>只有链路状态发生变化时，路由器才向所有路由器发送此消息<br>
路由器的链路状态只涉及到与路由器相邻的所有路由器的连通状态，与整个互联网的规模无直接关系，适用于大型或路由信息变化聚敛的互联网环境</li>
</ul>
<p><strong>优点</strong></p>
<ul>
<li>每个路由节点都是用相同的原始状态数据独立计算路由，不依靠中间结点的计算</li>
<li>链路状态报文不加改变地传播，易于查找故障</li>
<li>当一个结点收到报文时，可以在本地立即计算出正确通路，保证一步会聚</li>
<li>链路状态报文仅包含来自单个结点关于直接链路的信息，与结点个数无关，有更好的规模可拓展性</li>
</ul>
<h2 id="egp">外部网关协议（EGP）</h2>
<p>自治系统之间所使用的路由选择协议，也称域间路由选择协议，用于不同自治系统的路由器之间交换路由信息，并负责为分组在不同自治系统之间选择最优路径。</p>
<h3 id="bgp">BGP路由协议</h3>
<p>设法使一个消息<strong>尽可能有效</strong>地从源 AS 传送到目的 AS。</p>
<p>与内部网关协议不同，因特网规模太大，自治系统直接进行路由选择非常困难。因此对于自治系统之间的路由选择，要寻找最佳路由是很不现实的。自治系统之间的路由选择必须考虑有关策略。BGP只是力求寻找一条能够到达目的网络且比较好的路由（不兜圈子），而非一定要寻找最佳路由。</p>
<p>BGP 采用路径向量路由选择协议（不同于距离向量），是基于TCP的应用层协议</p>
<p><strong>工作原理</strong></p>
<p>每一个自治系统的管理员至少要选择一个路由器作为 BGP 发言人（边界路由器），与别的自治系统的 BGP 发言人交换路由信息。（需要建立 TCP 连接，BGP 报文是 TCP 报文的数据部分）<br>
在此连接上交换 BGP 报文以建立 BGP 会话，从而交换路由信息<br>
每个 BGP 发言人除了必须运行 BGP 协议外，还需要运行 AS 所使用的内部网关协议</p>
<p><strong>特点</strong></p>
<ul>
<li>BGP 协议要交换路由信息的结点数量级是自治系统的数量级，比这些自治系统中的网络数少很多</li>
<li>每一个自治系统的 BGP 发言人是很少的，使得路由选择不至于特别复杂</li>
<li>支持 CIDR，因此路由表包括网络前缀、下一跳路由器、以及到达该目的网络要经过的各个自治系统序列</li>
<li>刚运行时，BGP 的邻站是交换整个的 BGP 路由表。但以后只交换变化部分，节省网络带宽和减少路由器处理开销</li>
</ul>
<p><strong>报文类型</strong></p>
<ul>
<li>打开报文：用来与相邻的另一个BGP发言人建立关系</li>
<li>更新报文：用来发送某一路由的信息，以及列出要撤销的多条路由</li>
<li>保活报文：用来确认打开报文和周期性证实邻站关系</li>
<li>通知报文：用来发送检测到的错误</li>
</ul>
<h2 id="heading-2">对比</h2>
<table>
<thead>
<tr>
<th style="text-align:left">协议</th>
<th style="text-align:left">RIP</th>
<th style="text-align:left">OSPF</th>
<th style="text-align:left">BGP</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:left"><strong>类型</strong></td>
<td style="text-align:left">内部</td>
<td style="text-align:left">内部</td>
<td style="text-align:left">外部</td>
</tr>
<tr>
<td style="text-align:left"><strong>路由算法</strong></td>
<td style="text-align:left">距离-向量</td>
<td style="text-align:left">链路状态</td>
<td style="text-align:left">路径-向量</td>
</tr>
<tr>
<td style="text-align:left"><strong>传递协议</strong></td>
<td style="text-align:left">UDP</td>
<td style="text-align:left">IP</td>
<td style="text-align:left">TCP</td>
</tr>
<tr>
<td style="text-align:left"><strong>路径选择</strong></td>
<td style="text-align:left">跳数最少</td>
<td style="text-align:left">代价最低</td>
<td style="text-align:left">较好</td>
</tr>
<tr>
<td style="text-align:left"><strong>交换结点</strong></td>
<td style="text-align:left">和本结点相邻的路由器</td>
<td style="text-align:left">网络中所有路由器</td>
<td style="text-align:left">和本结点相邻的路由器</td>
</tr>
<tr>
<td style="text-align:left"><strong>交换内容</strong></td>
<td style="text-align:left">自己的路由表</td>
<td style="text-align:left">相邻路由器的链路状态</td>
<td style="text-align:left"><ul><li>首次: 整个路由表</li><li>非首次: 有变化部分</li></ul></td>
</tr>
</tbody>
</table>
