路由基本原理及路由协议
一．OSI/RM参考模型中分组交换网络的（网络层）路由选择1．路由选择
路由选择也较路径选择。
路由选择是指选择和建立一条合适的物理或逻辑的通路，以供进网数据从网络的源节点到达宿节点的控制过程。
2．路由问题概述
分组交换网结构可以抽象成以下网络拓扑图
数据分组从源节点A到达宿节点D的路径（通路）有：
l1,l3（A-B-D）
l2,l6（A-C-D）
l2,l4,l7（A-C-E-D）
问题：
哪条通路是最佳的？
最佳－即最短路径问题。
假如上图中每条边都有权值，A到D的最短路径应该是所有路径中，构成路径的边的权值之和最小的哪条路径。
权值：在网络中主要是数据传输时延和距离。
3．对路由选择算法的要求
a.能正确、迅速、合理地传输数据分组
b.能适应由于节点或链路故障引起的拓扑变化
c.能适应网络通信量的变化，使网络内的通信负载达到均衡
d.算法应尽量简单
4．路由选择算法的两大策略
a．静态路由选择算法——基于网络拓扑（距离）和时延的要求，以固定的准则来选择路由。因此这类算法也叫做确定型（非自适应）路由算法。这类算法简单，速度快，但不能适应因种种原因而引起的网络拓扑变化和网络内部通信量的变化。这类算法使用于那些网络拓扑结构不经常变化的小型网络。
b.动态路由选择算法——基于网络状态参数的变化，来选择某段时间内有效的路由。这类算法能够适应网络拓扑状态和其它状态参数的变化而调整路由。因此这类算法也叫做自适应路由算法
5．实现路由选择算法的一般方法
a.标头指示法
b.路由表法
在每个交换节点（路由器）中建立路由表。
二、互联网中的路由算法——IP路由技术
1．IP路由
互联网中的路由主要有路由器的路由功能完成。
2．路由器中的路由功能
a.实现网间中继IP数据包的功能，包括：数据帧的封装和拆封、IP地址到MAC地址的映射等
b.对IP数据包的控制，例如ttl=0时丢弃数据包
c.依据路由表选择最佳路由。
d.支持有关的路由算法和路由协议
3．路由表
互联网路由器中的路由表只保存部分路由信息。即每个表项只给出目的网络号，和下一（个路由器）站的地址。
路由表中的一个表项包含的信息：
目的网络编号
目的网络子网掩码
下一站路由器（网关）的IP地址
下一个网关的距离（以hops）为单位
从本网络到达下一网关的输出接口地址
可以用c++描述该表项结构：
struct rout{
long DsNetworkIP;
long DsNetworkMask;
long NextHopIP;
short Distance;
short IntNum;
short SortKey;
short TimeToLive;
}
4．直接路由和间接路由
直接路由——在一个（子）网络内的路由，即本地路由
间接路由——不同网络之间路由的选择过程
如下图所示，有3个网络202.1.2.0、202.1.3.0和202.1.4.0，据此主机A的路由表是：
目的网络直接/间接路由器IP地址网络接口号
202.1.2.0 直接 1
202.1.3.0 间接202.1.2.4 1
202.1.4.0 间接202.1.2.4 1
路由器上的路由表如下：
目的网络直接/间接路由器IP地址网络接口号
202.1.2.0 直接 1
202.1.3.0 直接 2
202.1.4.0 直接 3
5．IP路由算法
a.向量距离法（RIP）
主要完成以下工作：
最佳路径选择，以跳数最为距离，衡量最短路径
与其它路由器交换路由表中的全部信息
根据接收到的最新路由信息更新本路由器的路由表
路由器之间交换路由表信息使用路由协议
特点：
算法简单，易实现
每隔30秒钟广播一次路由信息，加重了网络通信负载，即增加了网络带宽开销
会产生路由的不一致性，形成环路路由
最大跳数受到限制（1－15）
该算法适用与小型网络
b．链路状态法（开放式最短路经优先）算法（OSPF）
主要完成的工作与RIP相同
特点：
以链路状态和距离最为选择最佳路径的依据（权值）
相邻路由器之间在链路状态发生变化时交换状态信息
更新状态信息后即计算最佳路由，更新路由表
在网络中传输的路由信息大大减少，网络带宽开销少
距离不受限制
6．自治系统和核心网关（核心路由器）
a．自治系统(AS-Autonomous System)：由有独立管理能力的并采用相同路由选择策略的一组路由器和网络构成的整体系统。单个物理网络或者由多个路由器互联而成的组织性或地区性网络，都可以是自治系统。互联网中心为每个自治系统分配统一的自治系统编号。
b．核心网关（核心路由器）
骨干网络（中转性网络）网络是互联网的核心结构。核心结构中用来与组织性或地区性网络互联的网关叫做核心网关。核心网关包括到全部目的网络的路由信息，由互联网营运中心管理。
用来连接组织性或地区性互联网的路由器叫做非核心网关。非核心网关只包括到部分目
的网络的路由信息，这些路由信息由非核心网关自己管理。通常一个局域网连接到互联网的路由器就是非核心路由器。
核心网关之间需要不断地交换各自的路由信息，确保整个互联网路由的一致性。非核心网关通过默认的路径向核心网关报告本地的路由信息，使核心网关能完成对任何目的网络的路由选择。
c．内部网关协议（IGP）——一个自治系统内部的所有网关叫做内部网关，内部网关之间交换路由信息的协议叫做内部网关协议，例如：RIP、OSPF、IGRP等
d．核心网关到核心网关的路由协议（GGP）——，采用向量距离路由选择算法
e．外部网关协议（EGP）——外部网关属于非核心网关，是用于一个自治系统与另一个自治系统交换路由信息的网关。外部网关采用距离向量路由协议。外部网关协议仅仅用于交换路由信息。
外部网关有三个主要功能：
●邻机测试——邻机之间不断互相测试是否可达
●交换信息——邻机之间通过周期性的路径刷新报文来交换路由信
息
●邻机获取——某个自治系统中的一个网关向另一个自治系统的某
个网关请求作为自己的邻机，以便交换路由信息
f．边界网关协议（BGP）——与外部网关协议一样，也是一种在自治系统之间交换路由信息的外部网关协议。它增加了测试循环路由的功能。因此BGP是新一代的EGP，将会逐步取代EGP。