后页 退出前页路由选择
路由算法的基本特性
– 正确性
– 简当性
过于复杂、或对网络状态反应很快的算法反而会得不偿失
路由算法不能给各个节点带来的负担过重
– 健壮性：能适应拓扑结构和通信量等网络状态的动态变化
– 稳定性：防止网络状态的变化反应过于敏感或者过于迟缓
– 公平性
– 最优性
– 高效性：任何路由算法，每个节点都会一些处理开销，而且同时会带来传输的开销后页 退出前页扩散法
一个网络节点从某条输入线路收到一个分组之后，把该分组从除了分组到来的线路外的所有其他输出线路上发出
可以用于健壮性要求很高的场合，但也会产生大量的重复分组
– 每个分组头部包含一计数器，每个接收到该分组的节点将该字段减 1，如果计数器值为 0，扔掉该分组。
– 另一种方法是记录下分组扩散的路径，防止它第二次再扩散到已扩散过的路径中。
– 最后一种方法为选择扩散法。节点并不是简单地向所有其他节点转发分组，而是选择那些很可能向目的节点的方向去的节点。这里考虑的方向可以是地理上的方向，也可以是网络拓扑中的大致方向后页 退出前页固定路由选择
每个网络节点
– 存储有一张表格，每一项记录着为了到达某个目的节点而选择的下一节点或链路。
– 当一个分组到达该节点时，节点只要根据分组中的地址信息从表中找出对应的目的节点及所应选择的下一节点，将分组转发给该下一节点
简单，适合于在一个负载稳定、拓扑变化不大的网络中运行
一个改进办法就是在最优路由的下一节点之外提供几个替换节点，并且可以使这些替换节点的使用符合一定的概率后页 退出前页随机路由选择
当分组到达节点后，随意选择一条输出线路进行转发
或者采用概率数的方法，使得每个输出线路的选择是符合预定的概率的
由于随机性，分组可能会一直在网络中传递，从而无法到达目的地，很少使用后页 退出前页
Dijkstra算法定义,N＝网络中所有节点的集合
S＝源节点
M＝已由算法归并的节点的集合
L（ i,j）＝节点 i与 j之间链路的权值；若两个节点间没有直接连接则为 ∞。
C（ n）＝算法求得的当前从 S到 n的最少花费路由的花费
1,初始化：
M = {S}
C(n) = L(S,n) for n?S
2,从不在 M中的相邻节点中找出一个具有和节点 S的最少花费路由的节点，并且把该节点规约进 M中。可以表示如下,
寻找,使得 C(w)=
把 w加入到 M中
Mw?
)(m in jCMj?
后页 退出前页
Dijkstra算法 （续）
3,更新最少花费路径：
C(n)=min[C(n),C(n)+L(w,n)] 对所有如果后一项为最小值，则从 S到 n的路径变为从 S到 w的路径再加上从 w到 n的链路。
4,重复步骤 2和 3，直到 M=N。
Mn?
E(?,-) F(?,-)
D((?,1)
A
B C
DE F
G H
A
B(2,A) C(?,-)
D(?,-)
G(6,A) H(?,-)
2
7
32
2
3
22
46
A
B(2,A) C(9,B)
E(4,B)
F(6,E)
G(5,E)
A
C(9,B)
D(?,-)E(4,B)
F(?,-)
G(6,A) H H(?,-)
B(2,A)
(a) (b)
(c) (d)
后页 退出前页动态路由算法
静态策略不利用当前网络信息，最多由网管人员偶尔对网络状态变化作出反应。
动态策略是指节点的路由选择要依靠网络的当前状态信息来决定，以设法适应网络流量、拓扑的变化。
– 路由选择算法非常复杂,故可能增加网络节点的处理负担 。
– 大多数情况下,动态策略会使用别的节点来的状态信息来进行路由选择,因此会增加网络中的负载 。
– 一个动态策略算法有时会因反应太快而引起振荡，
或者反应太慢而起不到作用后页 退出前页动态路由算法 （续）
孤立路由选择
– 不利用其他节点来的网络信息，仅仅根据它自己所看到的情况来确定路由，比如选择所有输出链路上具有最短队列的那条链路
集中路由选择
– 根据所有节点的网络信息来选择路由
– 和固定路由选择一样，每个节点都保存了一张当前的路由表
固定路由算法中表格的建立是手工完成的
集中路由选择中设置了一个路由控制中心 RCC，定期收集所有节点的信息，然后根据它对整个网络全局性的了解，
利用这些信息使用最短路径算法计算出每对节点之间的最优路径，构造出路由表分发后页 退出前页动态路由算法（续）
分布路由选择
– 根据来自于相邻节点的信息，通过一个最短花费路由算法计算出到每个目的地的路由
– 两种常用的分布路由算法：
距离向量路由
– 每个节点开始只知道它直接连接的链路的花费，然后通过一轮一轮地与邻居路由器交换路由信息，并进行相应的计算后，
节点逐渐了解到某个目的地或者某些目的地的最小花费路径。
链路状态路由
– 节点通过相互之间交换路由信息，了解到整个网络的拓扑信息，包括网络中的链路以及链路的花费。然后每个节点基于它所了解到的网络的全局状况计算所有可能的最小花费路径后页 退出前页拥塞
什么是拥塞?
– 通信子网中某一部分的分组数高于一定的水平，使得该部分网络来不及处理这些分组，
从而使这部分以至整个网络的性能下降
– 仅仅通过资源升级无法完全消除拥塞，拥塞控制是一个动态的概念
路由器的缓冲区
通信线路的带宽
处理器速度后页 退出前页拥塞控制
流量控制机制用来保证发送端不以比接收者能承受的速率更高的速度传输数据，一般涉及到接收者通过向发送者发送反馈
拥塞控制确保通信子网能够有效为主机传递分组，这是一个全局性的问题，涉及到所有主机、
所有路由器、路由器中的存储－转发处理以及所有导致削弱通信子网能力的其他因素后页 退出前页拥塞控制策略
开环策略：
– 它试图避免拥塞的出现，比如决定何时接受新的通信，何时丢弃分组，以及丢弃那些分组等，它们在作出决定时不考虑当前网络的状态。
闭环策略：
– 首先监视子网的拥塞状况
– 将拥塞的信息传递到可能采取行动的地方，它可以传给源发送端，也可能是传给其他的路由器
– 收到反馈的系统采取相应措施来进行调整
– 闭环策略又分为显式反馈和隐式反馈。
显式反馈：由拥塞点发送反馈给其他采取行动的地方。
隐式反馈：源端通过本地的观察来判断是否存在拥塞后页 退出前页许可控制
用在虚电路子网中，一旦出现拥塞的信号，就不再建立任何虚电路，直到拥塞解除。
另一可选的方法是允许建立新的虚电路，
但通过仔细选择路由，以便所有新的虚电路会绕过那些有问题的区域
在建立虚电路时进行资源的预约后页 退出前页通信量整形
子网强迫分组以某种预定的速率传送
– 用户通过一个流规范说明自己的通信量模式，
并进行协商
– 通信子网通过通信量控制策略进行控制，调整分组传输的速率，从而减少拥塞发生可能
–
后页 退出前页漏桶算法
有恒定服务时间的单服务器排队系统
分组长度固定
– 漏桶由一个有限队列构成，当分组到达时，如果队列中尚有空位，则将其加入到队尾；如果队列满就丢弃该分组。每隔一个时间节拍，队列中的一个分组被发送出去（除非队列为空）
后页 退出前页规则的分组流主机漏桶模型网络包含一个漏桶的接口装有分组的漏桶分组不规则的分组流后页 退出前页漏桶算法
分组长度不固定
– 采用字节计数的机制，而不是根据分组的个数来计算。每个节拍允许发送一定数量的字节，而不是每个节拍发送一个分组。
– 每个节拍开始时，计数器初始化为 n（即每个节拍允许发送的字节数）。如果队列的第一个分组的字节数小于当前计数器，
就将该分组发送出去，并把计数器减去该分组的字节数。只要计数器的值足够大，在同一节拍内还可以继续发送其他分组。如果计数器值小于队列中下一个分组的字节数，传输便停止，直到下一个节拍开始，计数器被重新设置，开始另一轮发送过程。
后页 退出前页令牌桶算法
每隔?T秒生成一个令牌，而漏桶可以保留这些令牌。如果要发送分组，必须首先抓住一个令牌，在发送分组后令牌被销毁。
后页 退出前页主机网络每隔往桶中装入一个令牌 桶中装有令牌
（ a）
主机网络
（ b）
令牌桶算法后页 退出前页令牌桶算法
令牌桶和漏桶的区别
– 漏桶算法不允许主机把空闲时候的发送权保留下来，以备以后大的突发负载出现时使用。令牌桶算法则允许保留最多为桶的大小 n的发送权从而允许输出的分组流有一些突发性，并且对那些输入流的突发性提供更快的响应。
– 令牌桶算法在桶满时会丢失令牌，但绝不会把分组丢弃掉。
而漏桶算法则在桶满时会丢弃分组
字节计数的令牌桶：
– 每个令牌代表的不是发送一个分组的权力，而是 k个字节。只有当所有的令牌代表的字节长度超过分组长度，该分组才能被发送，否则这些令牌被保留起来供将来使用。
后页 退出前页令牌桶算法
令牌桶允许突发的通信量，但突发长度是有限的
– 假设突发时间长度为 S秒，令牌桶的容量为
C字节，令牌产生速率为?字节 /秒，最大输出速率为 M字节 /秒。
MSSC
)/( MCS
后页 退出前页反馈机制
路由器监视网络的状态，包括输出线路和其他资源的利用率等
发送反馈
– 抑制分组：通过分组形式从路由器发送给源端。
– 反馈包括在路由器间交换的路由消息中传递
– 源端发送端到端的探测分组
– 反向反馈：分组包括一个拥塞反馈字段，路由器在反方向的分组中填充该字段来传递拥塞指示
– 正向反馈：路由器填充正向分组的拥塞反馈字段
源端调整发送给特定目的地的通信量
– 改进方案是采用站到站的反馈机制，上游的路由器收到该反馈，路由器减少相应的流量
faa o ldn e w )1(
后页 退出前页公平队列
基本思想：
– 每条输出线路有多个队列，每个源端一个。
每当线路空闲时，路由器便循环扫描各队列，
从下一个队列中取出第一个分组。这样，当
n台主机竞争同一输出线路时，每台主机只有一个分组参与竞争，发送更多的分组也不会增加选中的几率
加权公平队列
– 给不同的源端以不同的优先级后页 退出前页负载脱落
丢弃分组
– 葡萄酒策略：旧分组比新分组更有价值
– 牛奶策略：新分组比旧分组更有价值
– 优先级策略，优先级的设置可以与通信量整形联系起来
允许主机以超过建立虚电路时所协商的服务质量发送，只是把超量的通信量标记为低优先级
路由算法的基本特性
– 正确性
– 简当性
过于复杂、或对网络状态反应很快的算法反而会得不偿失
路由算法不能给各个节点带来的负担过重
– 健壮性：能适应拓扑结构和通信量等网络状态的动态变化
– 稳定性：防止网络状态的变化反应过于敏感或者过于迟缓
– 公平性
– 最优性
– 高效性：任何路由算法，每个节点都会一些处理开销，而且同时会带来传输的开销后页 退出前页扩散法
一个网络节点从某条输入线路收到一个分组之后，把该分组从除了分组到来的线路外的所有其他输出线路上发出
可以用于健壮性要求很高的场合，但也会产生大量的重复分组
– 每个分组头部包含一计数器，每个接收到该分组的节点将该字段减 1，如果计数器值为 0，扔掉该分组。
– 另一种方法是记录下分组扩散的路径，防止它第二次再扩散到已扩散过的路径中。
– 最后一种方法为选择扩散法。节点并不是简单地向所有其他节点转发分组，而是选择那些很可能向目的节点的方向去的节点。这里考虑的方向可以是地理上的方向，也可以是网络拓扑中的大致方向后页 退出前页固定路由选择
每个网络节点
– 存储有一张表格，每一项记录着为了到达某个目的节点而选择的下一节点或链路。
– 当一个分组到达该节点时，节点只要根据分组中的地址信息从表中找出对应的目的节点及所应选择的下一节点，将分组转发给该下一节点
简单，适合于在一个负载稳定、拓扑变化不大的网络中运行
一个改进办法就是在最优路由的下一节点之外提供几个替换节点，并且可以使这些替换节点的使用符合一定的概率后页 退出前页随机路由选择
当分组到达节点后，随意选择一条输出线路进行转发
或者采用概率数的方法，使得每个输出线路的选择是符合预定的概率的
由于随机性，分组可能会一直在网络中传递，从而无法到达目的地，很少使用后页 退出前页
Dijkstra算法定义,N＝网络中所有节点的集合
S＝源节点
M＝已由算法归并的节点的集合
L（ i,j）＝节点 i与 j之间链路的权值；若两个节点间没有直接连接则为 ∞。
C（ n）＝算法求得的当前从 S到 n的最少花费路由的花费
1,初始化：
M = {S}
C(n) = L(S,n) for n?S
2,从不在 M中的相邻节点中找出一个具有和节点 S的最少花费路由的节点，并且把该节点规约进 M中。可以表示如下,
寻找,使得 C(w)=
把 w加入到 M中
Mw?
)(m in jCMj?
后页 退出前页
Dijkstra算法 （续）
3,更新最少花费路径：
C(n)=min[C(n),C(n)+L(w,n)] 对所有如果后一项为最小值，则从 S到 n的路径变为从 S到 w的路径再加上从 w到 n的链路。
4,重复步骤 2和 3，直到 M=N。
Mn?
E(?,-) F(?,-)
D((?,1)
A
B C
DE F
G H
A
B(2,A) C(?,-)
D(?,-)
G(6,A) H(?,-)
2
7
32
2
3
22
46
A
B(2,A) C(9,B)
E(4,B)
F(6,E)
G(5,E)
A
C(9,B)
D(?,-)E(4,B)
F(?,-)
G(6,A) H H(?,-)
B(2,A)
(a) (b)
(c) (d)
后页 退出前页动态路由算法
静态策略不利用当前网络信息，最多由网管人员偶尔对网络状态变化作出反应。
动态策略是指节点的路由选择要依靠网络的当前状态信息来决定，以设法适应网络流量、拓扑的变化。
– 路由选择算法非常复杂,故可能增加网络节点的处理负担 。
– 大多数情况下,动态策略会使用别的节点来的状态信息来进行路由选择,因此会增加网络中的负载 。
– 一个动态策略算法有时会因反应太快而引起振荡，
或者反应太慢而起不到作用后页 退出前页动态路由算法 （续）
孤立路由选择
– 不利用其他节点来的网络信息，仅仅根据它自己所看到的情况来确定路由，比如选择所有输出链路上具有最短队列的那条链路
集中路由选择
– 根据所有节点的网络信息来选择路由
– 和固定路由选择一样，每个节点都保存了一张当前的路由表
固定路由算法中表格的建立是手工完成的
集中路由选择中设置了一个路由控制中心 RCC，定期收集所有节点的信息，然后根据它对整个网络全局性的了解，
利用这些信息使用最短路径算法计算出每对节点之间的最优路径，构造出路由表分发后页 退出前页动态路由算法（续）
分布路由选择
– 根据来自于相邻节点的信息，通过一个最短花费路由算法计算出到每个目的地的路由
– 两种常用的分布路由算法：
距离向量路由
– 每个节点开始只知道它直接连接的链路的花费，然后通过一轮一轮地与邻居路由器交换路由信息，并进行相应的计算后，
节点逐渐了解到某个目的地或者某些目的地的最小花费路径。
链路状态路由
– 节点通过相互之间交换路由信息，了解到整个网络的拓扑信息，包括网络中的链路以及链路的花费。然后每个节点基于它所了解到的网络的全局状况计算所有可能的最小花费路径后页 退出前页拥塞
什么是拥塞?
– 通信子网中某一部分的分组数高于一定的水平，使得该部分网络来不及处理这些分组，
从而使这部分以至整个网络的性能下降
– 仅仅通过资源升级无法完全消除拥塞，拥塞控制是一个动态的概念
路由器的缓冲区
通信线路的带宽
处理器速度后页 退出前页拥塞控制
流量控制机制用来保证发送端不以比接收者能承受的速率更高的速度传输数据，一般涉及到接收者通过向发送者发送反馈
拥塞控制确保通信子网能够有效为主机传递分组，这是一个全局性的问题，涉及到所有主机、
所有路由器、路由器中的存储－转发处理以及所有导致削弱通信子网能力的其他因素后页 退出前页拥塞控制策略
开环策略：
– 它试图避免拥塞的出现，比如决定何时接受新的通信，何时丢弃分组，以及丢弃那些分组等，它们在作出决定时不考虑当前网络的状态。
闭环策略：
– 首先监视子网的拥塞状况
– 将拥塞的信息传递到可能采取行动的地方，它可以传给源发送端，也可能是传给其他的路由器
– 收到反馈的系统采取相应措施来进行调整
– 闭环策略又分为显式反馈和隐式反馈。
显式反馈：由拥塞点发送反馈给其他采取行动的地方。
隐式反馈：源端通过本地的观察来判断是否存在拥塞后页 退出前页许可控制
用在虚电路子网中，一旦出现拥塞的信号，就不再建立任何虚电路，直到拥塞解除。
另一可选的方法是允许建立新的虚电路，
但通过仔细选择路由，以便所有新的虚电路会绕过那些有问题的区域
在建立虚电路时进行资源的预约后页 退出前页通信量整形
子网强迫分组以某种预定的速率传送
– 用户通过一个流规范说明自己的通信量模式，
并进行协商
– 通信子网通过通信量控制策略进行控制，调整分组传输的速率，从而减少拥塞发生可能
–
后页 退出前页漏桶算法
有恒定服务时间的单服务器排队系统
分组长度固定
– 漏桶由一个有限队列构成，当分组到达时，如果队列中尚有空位，则将其加入到队尾；如果队列满就丢弃该分组。每隔一个时间节拍，队列中的一个分组被发送出去（除非队列为空）
后页 退出前页规则的分组流主机漏桶模型网络包含一个漏桶的接口装有分组的漏桶分组不规则的分组流后页 退出前页漏桶算法
分组长度不固定
– 采用字节计数的机制，而不是根据分组的个数来计算。每个节拍允许发送一定数量的字节，而不是每个节拍发送一个分组。
– 每个节拍开始时，计数器初始化为 n（即每个节拍允许发送的字节数）。如果队列的第一个分组的字节数小于当前计数器，
就将该分组发送出去，并把计数器减去该分组的字节数。只要计数器的值足够大，在同一节拍内还可以继续发送其他分组。如果计数器值小于队列中下一个分组的字节数，传输便停止，直到下一个节拍开始，计数器被重新设置，开始另一轮发送过程。
后页 退出前页令牌桶算法
每隔?T秒生成一个令牌，而漏桶可以保留这些令牌。如果要发送分组，必须首先抓住一个令牌，在发送分组后令牌被销毁。
后页 退出前页主机网络每隔往桶中装入一个令牌 桶中装有令牌
（ a）
主机网络
（ b）
令牌桶算法后页 退出前页令牌桶算法
令牌桶和漏桶的区别
– 漏桶算法不允许主机把空闲时候的发送权保留下来，以备以后大的突发负载出现时使用。令牌桶算法则允许保留最多为桶的大小 n的发送权从而允许输出的分组流有一些突发性，并且对那些输入流的突发性提供更快的响应。
– 令牌桶算法在桶满时会丢失令牌，但绝不会把分组丢弃掉。
而漏桶算法则在桶满时会丢弃分组
字节计数的令牌桶：
– 每个令牌代表的不是发送一个分组的权力，而是 k个字节。只有当所有的令牌代表的字节长度超过分组长度，该分组才能被发送，否则这些令牌被保留起来供将来使用。
后页 退出前页令牌桶算法
令牌桶允许突发的通信量，但突发长度是有限的
– 假设突发时间长度为 S秒，令牌桶的容量为
C字节，令牌产生速率为?字节 /秒，最大输出速率为 M字节 /秒。
MSSC
)/( MCS
后页 退出前页反馈机制
路由器监视网络的状态，包括输出线路和其他资源的利用率等
发送反馈
– 抑制分组：通过分组形式从路由器发送给源端。
– 反馈包括在路由器间交换的路由消息中传递
– 源端发送端到端的探测分组
– 反向反馈：分组包括一个拥塞反馈字段，路由器在反方向的分组中填充该字段来传递拥塞指示
– 正向反馈：路由器填充正向分组的拥塞反馈字段
源端调整发送给特定目的地的通信量
– 改进方案是采用站到站的反馈机制，上游的路由器收到该反馈，路由器减少相应的流量
faa o ldn e w )1(
后页 退出前页公平队列
基本思想：
– 每条输出线路有多个队列，每个源端一个。
每当线路空闲时，路由器便循环扫描各队列，
从下一个队列中取出第一个分组。这样，当
n台主机竞争同一输出线路时，每台主机只有一个分组参与竞争，发送更多的分组也不会增加选中的几率
加权公平队列
– 给不同的源端以不同的优先级后页 退出前页负载脱落
丢弃分组
– 葡萄酒策略：旧分组比新分组更有价值
– 牛奶策略：新分组比旧分组更有价值
– 优先级策略，优先级的设置可以与通信量整形联系起来
允许主机以超过建立虚电路时所协商的服务质量发送，只是把超量的通信量标记为低优先级
