主要学习网络层控制平面的工作原理
路由（route）的概念
**路由: 按照某种指标(传输延迟,所经过的站点数目等)找到一条 从源节点到目标节点的较好路径 **
较好路径: 按照某种指标较小的路径
指标:站数, 延迟,费用,队列长度等, 或者是一些单纯指标的加权平均
采用什么样的指标,表示网络使用者希望网络在什么方面表现突出,什 么指标网络使用者比较重视
** 以网络为单位进行路由（路由信息通告+路由计算） **
网络为单位进行路由，路由信息传输、计算和匹配的代价低
前提条件是：一个网络所有节点地址前缀相同，且物理上聚集
路由就是：计算网络 到其他网络如何走的问题
** 路由选择算法(routing algorithm):网络层软件的一部分,完成 路由功能 **
网络的图抽象
N = 路由器集合 = { u, v, w, x, y, z }
E = 链路集合 ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }边有代价
**边的代价： **
c(x,x’) = 链路的代价 (x,x’) - e.g., c(w,z) = 5
代价可能总为１
或是 链路带宽的倒数
或是 拥塞情况的倒数
**路由的输入：拓扑、边的代价、源节点 **
**输出的输出：源节点的汇集树（到其他节点的路径） **
汇集树下面解释
路由最优化原则 (optimality principle)
最优化原则
汇集树(sink tree)
**此节点到所有其它节点的最优路径形成的树 **
路由选择算法就是为所有路由器找到并使用汇集树
路由原则
**正确性(correctness):**算法必须是正确的和完整的,使分 组一站一站接力，正确发向目标站；完整：目标所有的 站地址，在路由表中都能找到相应的表项；没有处理不 了的目标站地址；
简单性(simplicity):算法在计算机上应简单：最优但复杂 的算法，时间上延迟很大，不实用，不应为了获取路由 信息增加很多的通信量；
**健壮性(robustness):**算法应能适应通信量和网络拓扑的 变化：通信量变化，网络拓扑的变化算法能很快适应； 不向很拥挤的链路发数据，不向断了的链路发送数据；
**稳定性(stability)**：产生的路由不应该摇摆
公平性(fairness)：对每一个站点都公平
**最优性(optimality)**：某一个指标的最优，时间上，费用 上，等指标，或综合指标；实际上，获取最优的结果代 价较高，可以是次优的
路由算法的分类
** 全局算法 —> “link state” 算法 **
** 所有的路由器拥有完整的拓扑 和边的代价的信息 **
**分布式算法 —-> “distance vector” 算法 **
路由器只知道与它有物理连接 关系的邻居路由器，和到相应 邻居路由器的代价值
叠代地与邻居交换路由信息、 计算路由信息
传统的路由选择算法
**“link state” 算法 **
LS路由的工作过程
配置LS路由选择算法的路由工作过程
各点通过各种渠道获得整个网络拓扑, 网络中所有链路 代价等信息（这部分和算法没关系，属于协议和实现）
使用LS路由算法,计算本站点到其它站点的最优路径(汇 集树),得到路由表
按照此**路由表转发分组(datagram方式) **
严格意义上说不是路由的一个步骤
分发到输入端口的网络层
LS路由的基本工作过程
发现相邻节点,获知对方网络地址
一个路由器上电之后,向所有线路发送HELLO分组
其它路由器收到HELLO分组,回送应答,在应答分组中,告 知自己的名字(全局唯一)
在LAN中,通过广播HELLO分组,获得其它路由器的信息, 可以认为引入一个人工节点
测量到相邻节点的代价(延迟,开销)
实测法
发送一个分组要求对方立即响应
回送一个ECHO分组
通过测量时间可以估算出延迟情况
组装一个LS分组**,描述它到相邻节点的代价情况**
发送者名称 序号,年龄
列表: 给出它相邻节点,和它到相邻节点的延迟
将分组通过扩散的方法发到所有其它路由器以上4步让每个路由器获得拓扑和边代价
顺序号:用于控制无穷的扩散,每个路由器都记录( 源路由器,顺序号),发现重复的或老的就不扩散
** 将分组通过扩散的方法发到所有其它路由器 **
通过Dijkstra算法找出最短路径（这才是路由算法）
每个节点独立算出来到其他节点（路由器=网络）的最短路径
迭代算法：第k步能够知道本节点到k个其他节点的最短路径
** 通过Dijkstra算法找出最短路径 (路由算法)前面的只是铺垫，通过协议发现邻居，通过网络的泛洪来散播路由信息**
链路状态路由选择(link state routing)
**符号标记: **
c(i,j): 从节点i 到j链路代价(初始状态下非相邻节点之间的 链路代价为∞)
D(v): 从源节点到节点V的当前路径代价(节点的代价)
p(v): 从源到节点V的路径前序节点
N’: 当前已经知道最优路径的的节点集合(永久节点的集合)
LS路由选择算法的工作原理
** 节点标记: 每一个节点使用(D(v),p(v)) 如： (3,B)标记 **
D(v)从源节点由已知最优路径到达本节点的距离
P(v)前序节点来标注
** 2类节点 **
临时节点(tentative node) :还没有找到从源 节点到此节点的最优路径的节点
永久节点(permanent node) N’:已经找到了从 源节点到此节点的最优路径的节点
**初始化 **
除了源节点外,所有节点都为临时节点
节点代价除了与源节点代价相邻的节点外,都为∞
从所有临时节点中找到一个
节点代价最小的临时节点,将 之变成永久节点(当前节点)W
对此节点的所有在临时节点集合中的邻节点(V)
如 D(v)>D(w) + c(w,v), 则重新标注此点, (D(W)+C(W,V), W)
否则，不重新标注
开始一个新的循环
**“distance vector” 算法 **
**距离矢量路由选择(distance vector routing) **
** 动态路由算法之一 **
** 距离矢量路由选择的基本思想 **
各路由器维护一张路由表,结构如图(其它代价)
各路由器与相邻路由器交换路由表
根据获得的路由信息,更新路由表
**代价及相邻节点间代价的获得 **
跳数(hops), 延迟(delay),队列长度
相邻节点间代价的获得：通过实测
** 路由信息的更新 **
根据实测 得到本节点A到相邻站点的代价（如:延迟）
根据各相邻站点声称它们到目标站点B的代价
计算出本站点A经过各相邻站点到目标站点B的代价
找到一个最小的代价，和相应的下一个节点Z，到达节点 B经过此节点Z，并且代价为A-Z-B的代价
其它所有的目标节点一个计算法
举例：
**距离矢量算法： **
** Bellman-Ford 方程(动态规划) **
递归找到最小值， 通过局部最小得到全局最小值。
** Dx (y) = 节点x到y代价最小值的估计 **[ x 节点维护距离矢量Dx = [Dx (y): y є N ] ]
** 节点x: **
知道到所有邻居v的代价: c(x,v)
收到并维护一个它邻居的距离矢量集
对于每个邻居, x 维护 Dv = [Dv (y): y є N ]
距离矢量算法核心思路
每个节点都将自己的距离矢量估计值传送给邻居，定时或者 DV有变化时，让对方去算
** 当x从邻居收到DV时，自己运算，更新它自己的距离矢量 **
**采用B-F equation: **
{ Dx (y) ← minv {c(x,v) + Dv (y)} 对于每个节点y ∊ N }
{ X往y的代价 x到邻居v代价 v声称到y的代价 }
** Dx (y)估计值最终收敛于实际的最小代价值dx (y) **
** 距离矢量算法 是 异步式迭代， 每次本地迭代 被以下事件触发 **
[1. 本地链路代价变化了 2. 从邻居来了DV的更新消息 ]
两个算法的比较
** 消息复杂度 DV算法更好一些**
LS: 有 n 节点, E 条链路,发送 报文O(nE)个
局部的路由信息；全局传播
DV: 只和邻居交换信息
全局的路由信息，局部传播
** 收敛时间 LS更好**
LS: O(n2) 算法 有可能震荡
DV: 收敛较慢 可能存在路由环路
** 健壮性: 路由器故障会发生什么 （LS胜出） **
LS:
节点会通告不正确的链路代价
每个节点只计算自己的路由表
错误信息影响较小，局部，路由较 健壮
因特网中自治系统内部的路由选择
内部网关协议： 自治区内部的协议
外部网关协议： 自治区之间的协议
RIP（ Routing Information Protocol ）
基于Distance vector 算法实现：
距离矢量:每条链路cost=1，# of hops (max = 15 hops) 跳数[ 15最大 ，如果是16 就是不可达 ]
DV每隔30秒和邻居交换DV，通告
每个通告包括：最多25个目标子网
RIP 通告（advertisements）
DV: 在邻居之间每30秒交换通告报文
定期，而且在改变路由的时候发送通告报文
在对方的请求下可以发送通告报文
每一个通告: 至多AS内部的25个目标网络的 DV
