- 1.16 MB
- 2021-05-14 发布
- 1、本文档由用户上传,淘文库整理发布,可阅读全部内容。
- 2、本文档内容版权归属内容提供方,所产生的收益全部归内容提供方所有。如果您对本文有版权争议,请立即联系网站客服。
- 3、本文档由用户上传,本站不保证质量和数量令人满意,可能有诸多瑕疵,付费之前,请仔细阅读内容确认后进行付费下载。
- 网站客服QQ:403074932
IP
网络技术
第
6
部分
——
IP
路由协议与技术
参考内容:
(
1
)
《
用
TCP/IP
进行网际互连
》
第一卷:原理、协议与体系结构(第五版)
第
13
、
14
、
15
、
16
章
(
2
)
《TCP/IP
协议族
》
(第
4
版)
第
11
、
12
章
1
内容提纲
1
、引言
2
、域内和域间路由选择
3
、距离向量路由选择与
RIP
4
、链路状态路由选择与
OSPF
5
、路径向量路由选择与
BGP
6
、多播和多播路由选择协议
2
1
、引言
互联网由许多
路由器
连接起来的网络组成
数据从源站到目的站,可能经过多个路由器
一个
路由器
连接多个网络,当路由器收到分组,应该将分组转发到哪个网络?
按照路由表(选路表)转发!
路由表
是怎样形成的?
何时如何发现路由?
如何建立和管理路由表?
lxm
3
1
、引言
根据何时和如何发现路由,路由可分为:
先应式路由
表驱动路由(事先建立路由表,查表转发)
适合静态网络的路由
反应式路由
按需路由(需要时发现并建立路由,按实时路由转发)
适合动态移动网络路由(如移动多跳
Ad-hoc
网络)
根据路由表的建立方式,路由可分为:
静态路由
——
路由表管理者人工配置和维护
建表不需要额外网络开销
不能及时自动反映网络变化
可能出现路由与网络不一致的情况
动态路由
——
路由表由路由协议动态创建和维护
路由发现过程需要占用网络资源,额外开销
表的形成需要一定时间
能自动适应网络变化,更灵活
lxm
4
1
、引言
路由协议的目的
——
使路由器能够找到到达目的地的最佳路径
路由协议的共同特点
路由器协同工作
彼此共享对互连网络的信息
计算路径,建立路由表
根据拓扑或某些策略
规定信息交互的周期,定期更新路由表
网络拓扑变化时,触发更新路由
lxm
5
交互信息(报文)不同,体现了不同路由协议特点
不同的路由协议,计算方法不同
:
可能局部路由,可能全局路由,可能依赖邻居
关键词
——Metric
(度量)
Metric
:用来衡量
通过某一网络
所需的代价
代价
是什么?
代价的度量取决于
Routing Protocol
Hop count
(跳数)
, bandwidth
(带宽)
, delay
(延迟)
, MTU, load
(负载)
, reliability
(可靠性)
, …
Routing protocol
使用
Metric
来选择一条
best path
(最优路)
for routing
Metric
之和最小的路径
64K
64K
10M
10M
10M
Hop count: A
B Net
Bandwidth: A C D Net
A
D
C
B
Net
lxm
6
关键词
——Convergence
(收敛)
Convergence
网络中的所有路由器都认为一致的
topology
Convergence time
(收敛时间)
网络发现到网络形成或网络变化到恢复的时间
反应了网络形成或恢复的快慢
从不一致到一致所经历的时间
体现路由算法的效率
影响收敛的因素
使用的路由协议
变化点到路由器的距离
网络中路由器的数量
通信链路的带宽和负载
路由器的负载
。。。。。。
lxm
7
2
、域内路由与域间路由
Internet
十分庞大,需要划分多个自治系统
AS
Autonomous system
(自治系统,
AS
)
一个管理机构管辖的一组网路和路由器
每个
AS
可选择一个或多个路由协议处理本
AS
内的路由选择
AS
内部的路由选择称为
域内路由选择
AS
的编号
每个
AS
都赋予一个编号
Range: 1~65535
Private AS number: 64512~65535
lxm
8
2
、域内路由与域间路由
Internet
十分庞大,需要划分多个自治系统
AS
Autonomous system
(自治系统,
AS
)
一个管理机构管辖的一组网路和路由器
每个
AS
可选择一个或多个路由协议处理本
AS
内的路由选择
AS
内部的路由选择称为
域内路由选择
AS
的编号
每个
AS
都赋予一个编号
Range: 1~65535
Private AS number: 64512~65535
lxm
9
2
、域内路由与域间路由
Internet
由若干
AS
互相连接构成
每个
AS
内可能有多个网络存在
核心主干网也可以构成一个
AS
核心主干网提供到所有可能的目的地的可靠的、统一的、权威的路由
lxm
10
ASx
ASy
AS1
核心主干网
AS3
AS2
IGP
与
EGP
IGP: Interior Gateway Protocol
(内部网关协议)
适用于
AS
内部路由,寻找
AS
内的最佳路径
Example
:
RIP
、
OSPF
、
IS-IS
EGP: Exterior Gateway Protocol
(外部网关协议)
适用于
AS
之间路由,寻找到
AS
的最佳路径
Example
:
BGP-4
Note
The static routing or an IGP could also be used between autonomous systems in some case
AS1
AS2
R
R
EGP
IGP
IGP
lxm
11
IGP
:动态路由协议
RIP
:适用于密集型网络
采用广播方式与邻居网关交互路由信息
V-D
路由算法
RIPv1
:
RFC1058(STD 34, 1988)
, 基本协议
RIPv2
:
RFC1723(1994)
, 增加
CIDR
支持
OSPF
:适用于稀疏型网络
采用扩散方式与所有网关交互路由信息
Open SPF
,具有开放性的链路状态路由算法
OSPF V2
:
RFC2178
,
. J. Moy. April 1998.
lxm
12
3
、距离向量路由选择与
RIP
协议
3.1
距离向量路由选择
3.1.1
距离向量路由选择算法
3.1.2
环路问题分析
3.1.3
解决环路的措施
3.2 RIP
协议
lxm
13
距离
向量
法(
V-D
:
Vector Distance
)
根据协议的设计者命名,也称为
Bellman-Ford
路由算法
V-D
算法通常以跳数作为
Metric
(
cost
)
当然也可以是其他度量参数:如时延、带宽等
基本
思想
每个节点都保持一张到其他节点的路由表
(
目的
网络
,距离,下一
节点
)(如以跳数为
cost
,则距离就是跳数)
邻居
之间交换路由信息(
目的
网络
,
距离)
根据收到相邻节点的信息,判断并决定是否更新路由
算法涉及的内容
初始的路由表如何建立?
邻居交换哪些信息
?
如何根据邻居信息计算并更新自己的路由表?
V-D
路由算法
算法的几个步骤
初始化
建立初始路由表
——
直连路由表
扩散
向邻居扩散自己的路由表信息
计算
根据收到相邻节点的信息,计算最短路径,更新路由表
再扩散、再计算
这样就逐渐形成了到全网路由
使每个节点都计算出了到其他节点的路径信息
值得注意的是:何时向邻居扩散路由信息?
定期
拓扑发生变化时
V-D
算法案例
1
)初始路由表建立
(目的网络,距离,下一跳)(初始都是直连网路
2
)路由表向邻居扩散
2
1
3
4
5
特别说明:
为方便讲解,本教案采用跳数作为
metric
到直连网络的最短距离为
1
跳,因此“距离”记为
1
注意:
度量值也可以是其他参数
1
2
3
4
5
6
目的
网络
距离
下
一跳
1
1
---
2
1
--
目的
网络
距离
下
一跳
1
1
--
3
1
--
目的
网络
距离
下
一跳
2
1
--
4
1
--
5
1
--
目的
网络
距离
下
一跳
3
1
--
4
1
--
6
1
--
目的
网络
距离
下
一跳
5
1
--
6
1
--
V-D
算法案例
3
)节点计算并更新本节点的路由表
相邻
节点定期交换信息
(目的网络,距离)
———
(目的网络,跳数)
更新路由表的原则
(以跳数为例)
将收到的路由表信息与
本
节点
原
路由表比较
(
1
)若原表项
无该项
,则代价
+1
,添加该项
(
2
)若原表项中
有该项
若具有不同
的下一跳,但
代价
+1
小于
原表项,更新
;
否则
,保留原表项
若具有相同的下一跳,无论代价是否
=
原代价,都必须更新!
Why
?
距离矢量算法
节点
1
路由表更新
初始值
目的
网络
距离
下
一跳
1
1
---
2
1
--
收到节点
2
信息
目的
网络
距离
1
1
3
1
更新
1
目的
网络
距离
下
一跳
1
1
---
2
1
--
3
2
2
2
1
3
5
1
2
3
4
5
6
4
目的
网络
距离
2
1
4
1
5
1
收到节点
3
信息
目的
网络
距离
下
一跳
1
1
---
2
1
--
3
2
2
4
2
3
5
2
3
更新
2
目的
网络
距离
下
一跳
1
1
---
2
1
--
3
2
2
4
2
3
5
2
3
多次更新的
稳定的表项
6
3
2
也可能是
3
,取决于节点
1
先收到
2
还是
3
的再次路由信息发布
同理,其他节点也能得到稳定的路由表
Count to Infinity
,计数到无穷大
2-node loop
Net 1
Net 2
Net 3
Net1
……
…
…
Routing table
Net1
A
……
…
…
Routing table
A
B
You can reach net1 through me with length 2
B can reach net1 ! Great !
Hop count changed !
-
1
16
2
3
Hop count changed !
4
-
B
∞
∞
B: ( net1, 2 )
A: ( net1, 3 )
B: ( net1, 4 )
lxm
19
定义
16
代表无穷大
A
C
B
D
平时:
A
收到
C
告知:
D
有两跳
A
收到
B
告知:
D
有一跳
选
B
C
收到
A
告知:
D
有两跳
C
收到
B
告知:
D
有一跳
选
B
当
B
到
D
的链路断掉后,一种可能的情形:
B
告诉
A
、
C
:
D
不可达
A
重新选路,正好收到
C
告知
D
有两跳(
C
还没收到
B
的更新信息)
A
选择到
D
经过
C
,距离为三跳
A
告知
B
:
D
有三跳
B
选择到
D
经过
A
,距离为四跳
C
收到
B
先前的
D
不可达更新,重新选路
B
告知
C
:
D
有四跳
C
选择到
D
经过
B
,距离为五跳
出现路由环路,
并计数到无穷大
几种解决措施
Defining infinity
(定义无穷大)
U
se a
finite
metric value to represent “infinity“
(
典型值
16
)
Th
e
value must be large enough that no real metric would ever get that large
Triggered update
(触发更新)
Split horizons
(水平分割)
Poison reverse
(毒性逆转)
A variation of split horizons
None of them are 100% effective !
lxm
21
触发更新
目的:促进快速收敛
如网络无变化
每隔
30
秒定期发送路由更新消息
如网络有变化
立即触发发送路由更新消息
lxm
22
Split Horizons
(水平分割)
Net 1
Net 2
Net 3
A
B
Net2 1
Net3 2
Net3 1
Net1 2
Net2 1
节点没有必要将从某节点
收到的信息再传回给该节点
lxm
23
Net1 1 ----
Net2 1 ----
Net3 2 B
A
路由表
Net2 --
Net3 --
B
发给
A
Net1 1
A
传给
B
Poison Reverse
(毒性反转)
Net 1
Net 2
Net 3
A
B
Net2 1
Net3 2
Net1 16
Net2 16
Net3 16
Net1 1
Net2 16
Net3 1
Net1 16
Net2 1
Net3 16
Net1 2
节点将从某节点收到的信息再传回给该节点时,告诉对方不能从我这里过(设置成
16
)
lxm
24
Hold-down Timer,
抑制定时器
当路由器收到一个路由不可达更新消息时,启动抑制定时器
( 60s
、
120s)
路由器收到某条路由不可达的消息后,在一段时间内(典型
60
秒),忽略关于该网络的任何路由信息
确保有较大范围内的站点都收到该坏消息,避免过时的路由通告,但抑制期间环路依然存在
V-D
算法小节
特点:
只与邻节点交换路由信息
各节点独立计算最优路径(但依赖邻居的计算结果)
能适应网络拓扑的变化
稳定后,形成最短路径
算法简单
缺点:
网络变化扩散到全网速度慢
扩散时间:所有节点都发现变化的速度
路由收敛慢
经过多轮邻居信息交换才能趋于一致
存在路由环--在网络变化未扩散完全时。
适用于
小网
lxm
26
3.2 RIP
协议
3.2.1 RIP
概述
3.2.2 RIP
操作
3.2.3 RIP
定时器
3.2.4 RIP
消息格式
3.2.5
相关讨论
lxm
27
3.2.1 RIP
概述
标准
RIPv1
:
RFC1058(STD 34, 1988)
, 基本协议
RIPv2
:
RFC2453
, 增加
CIDR
支持
采用
V-D
算法
采用跳数作为度量
采用
UDP
封装
平面路由协议,仅适合小网
lxm
28
3.2.1 RIP
协议
Routing Information Protocol
,
RIP
v1
:
RFC 1058
,
v2
:
RFC 2453
,路由信息协议
IP
LANs
MANs
WANs
ICMP
IGMP
ARP
RARP
Network
Layer
Network
Access Layer
TCP
UDP
Transport
Layer
RIP
Application
Layer
520
软件实现层次
RIP = RIPv1
lxm
29
yn@uestc.edu.cn
30
Example of a domain using RIP
Metric: hop count
(跳数)
Infinity = 16, means unreachable
The maximum hop count = 15
3.2.2 RIP
操作
Discovery
Topology change
Calculating
RIP updating algorithm
Initialize
RT
Send
RT
Update RT
Update?
Send RT per 30s
No
Yes
Find the change
Update
RT
Send RT
on schedule
Like discovery
Split horizons & poison reverse
Triggered update
lxm
31
yn@uestc.edu.cn
32
RFC1058
:
发送时
unchanged
接收时
Metric + 1
某些实现:
发送时
Metric + 1
接收时
unchanged
lxm
32
网络发现
A
B
C
N1
N2
N3
N4
1
2
1
2
1
2
N3
-
1
0
N4
-
2
0
N1
-
1
0
N2
-
2
0
N2
-
1
0
N3
-
2
0
路由表:
目的网络
下一跳
发送接口
Metric
N3
N1
N2
B1
2
1
A2
1
1
B2
1
1
C1
2
1
N4
A: (N1, 1) (N2, 1)
B: (N2, 1) (N3, 1)
C: (N3, 1) (N4, 1)
B: (N2, 1) (N3, 1)
N4
B1
2
2
N1
B2
1
2
A: (N1,1) (N2,1) (N3,2)
B: (N2,1) (N3,1)
(N1,2) (N4,2)
C: (N3,1) (N4,1) (N2,2)
B: (N2,1) (N3,1)
(N1,2) (N4,2)
A:(N1,1)(N2,1)(N3,2)(N4,3)
B: (N2,1) (N3,1)
(N1,2) (N4,2)
C:(N3,1)(N4,1)(N2,2)(N1,2)
B: (N2,1) (N3,1)
(N1,2) (N4,2)
lxm
33
拓扑变化
A
B
C
N1
N2
N3
N4
1
2
1
2
1
2
N3
-
1
0
N4
-
2
0
N1
-
1
0
N2
-
2
N2
-
1
N3
-
2
0
N3
N1
N2
B1
2
1
A2
1
1
B2
1
1
C1
2
1
N4
N4
B1
2
2
N1
B2
1
2
B: (N2,16) (N3,1)
(N1,16) (N4,2)
A: (N1,1) (N2,16)
(N3,16) (N4,16)
0
0
∞
∞
∞
C: (N3,1) (N4,1)
(N2,16) (N1,16)
∞
∞
∞
∞
lxm
34
3.2.3 RIP
的定时器
Timers
无用信息收集
60
或
120 s
(for each route)
截至期
180 s
(for each route)
定期
30 s
(for each router)
控制更新报文定期通告,
通常为
25-35s
的随机数
避免同时更新引起过载
触发更新例外
管理路由的有效性
正常情况下,每
30s
复位一次,如故障,在
180s
未收到更新报文,则过期,跳数设置为
16
当某条路由信息成为无效时(
16
),路由器并不立即清除该表项,而是继续通告,待
120s
后才清除该表项
lxm
35
3.2.4 RIP
消息格式(
V1)
RIP
只定义了有一种报文格式
交换(
IP address
,
Metric
)对
IP address
可为
A
、
B
、
C
类网络地址或主机地址
Command
Version=1
IP address
All 0s
All 0s
All 0s
Metric ( hop count )
All 0s
Family = 2
Repeated
lxm
36
3.2.4 RIP
消息格式(
V1)
Command
1=Request
请求部分或全部选路信息
2=Response
发送方给出自己选路表的
(V
,
D)
9=
更新请求
10=
更新响应
11=
更新确认
Address Family Identifier
2
=
IPaddress
V1
版未定义掩码,只能用于有类地址方式
lxm
37
RIPv2
的扩展
RIPv2
格式
路由标记:路由起点、自治域号等额外信息
RIP2
实现对
CIDR
的扩展
0
8
16
24 31
Command
Version=2
Must be 0
Address Family Identifier
目的网的路由标记
目的网地址(
IP Addr
)
目的网掩码(
Mask
)
到目的网的下一网关(
Next Hop
)
到目的网的距离(
Metric
)
重复
25
次
lxm
38
3.2.5 RIP
的讨论
距离=
16
指网络的跨度,而不是路由器的数目
RIP
适合于不大的网络
简单的路由,无法处理时延、容量要求
相对固定的路由,较长时间不变
无法对网络性能变化(负载、时延等)做出反应(调整路由)
仍有大量的应用
lxm
39
4
、链路状态路由选择与
OSPF
4.1
链路状态路由选择
4.1.1
算法基本思想
4.1.2
链路状态算法的操作
4.2 OSPF
协议
lxm
40
4.1.1 L-S
路由选择算法基本思想
参与该算法的所有路由器都需要掌握全部拓扑结构
拓扑结构:
点:路由器
边:路由器相连的网络
算法基本思想
周期地检查邻接路由器的状态(可达性)
向所有路由器通告自己的链路状态(全网扩散)
每个路由器根据自己掌握的拓扑结构,独立计算到所有目网络的路由
典型算法:
Dijkstra
最短路径算法
lxm
41
4.1.1 L-S
路由选择算法基本思想
涉及到的主要问题
(
1
)各路由器如何知道全部拓扑?
(
2
)路由器如何扩散自己的链路状态
(
3
)路由器如何计算到各网的最短路径
lxm
42
4.1.2
链路状态算法的操作
发现邻居
探寻邻居,得到邻居的唯一地址
测量链路开销
测量到各邻居节点的延迟(链路质量)
交换路链路状态信息
形成链路状态分组,向所有节点扩散
充实路由信息库
根据收到各节点的链路状态信息,进而得出全网拓扑
计算到各网络的最佳路径
根据自己掌握的路由信息,独立计算本节点到其他节点的最佳路由
特别注意:
交流的路由信息:链路状态信息
交流的对象:向所有的节点
交流的方法:扩散法
路由的计算:只根据自己掌握的路由信息,独立计算最佳路由(不依赖别人的计算)
lxm
43
链路状态算法
——
发现邻居
初始时,每个节点都向每个出口(直接链路)发送
“
Hello
”
分组,告知自己的
IP
地址
收到分组的节点则回应一个分组告知自己的
IP
地址
特别强调:每个节点的地址必须唯一
A
B
Hello
,
I am A
Hello
,
I am B
lxm
44
链路状态算法
——
测量链路开销
测量链路开销(以链路时延为例)
向邻居发送
“
Echo
”
分组(对方必须应答)
对方发送应答
计算来回延时除以
2
,得到时延(可计算几次得平均值)
计算链路开销时值得讨论的问题
是否考虑负荷?
两种观念
考虑负荷,从进入发送队列排队开始算
忽略负荷,从发送开始算
正反方向延时是否一样?
可能不一样
为分析简便,通常忽略差异,用平均值
A
B
T
“Echo”
“Echo”Response
lxm
45
链路状态算法
——
测量并计算链路开销
通过测试计算出到邻居的开销
假设各节点测得的开销如下所示
A
节点
B
节点
4
C
3
B
开销
邻居
6
C
5
D
3
A
开销
邻居
2
D
6
B
1
E
4
A
开销
邻居
3
E
2
C
2
F
5
B
开销
邻居
3
D
2
F
1
C
开销
邻居
2
E
2
D
开销
邻居
C
节点
D
节点
F
节点
E
节点
lxm
46
链路状态算法
——
交换链路状态信息
创建链路状态分组并向全网发布
根据测得的到所有邻居的的延时,形成链路状态分组
链路状态分组的内容
发布者:发布信息的节点名称
序号:序号的大小表示信息的新旧
年龄:一个分组在网络中的存活时间
B
A
C
D
E
F
1
2
2
5
6
2
4
3
3
4
C
3
B
时间
序号
A
发布者
6
C
3
A
时间
序号
B
发布者
5
D
6
B
4
A
时间
序号
C
发布者
2
D
1
E
2
C
5
B
时间
序号
D
发布者
3
E
2
F
3
D
1
C
时间
序号
E
发布者
2
F
2
E
2
D
时间
序号
F
发布者
lxm
47
链路状态算法
发布链路状态分组
发布对象:所有节点
发布时间:定期,连路状态发生改变时
发布方法:扩散法(洪泛)
采用扩散法一定可以到达全网各节点
节点可能收到多个相同的分组
可根据序号判别,相同的序号则丢弃重复的
节点也可能收到同一个发布者不同序号的分组
根据发布时间判别,丢弃老的,处理新的
为避免分组可能在网中循环
通过年龄字段避免(年龄按时间递减,到
0
时将被丢弃)
lxm
48
链路状态算法
——
绘制全局拓扑
根据逐步收到的链路分组,充实路由信息库,逐步
“
绘出
”
拓扑图
以节点
A
为例,各节点发布链路分组后,
A
逐步得到了分组
4
C
3
B
时间
序号
A
发布者
6
C
3
A
时间
序号
B
发布者
5
D
6
B
4
A
时间
序号
C
发布者
2
D
1
E
2
C
5
B
时间
序号
D
发布者
3
E
2
F
3
D
1
C
时间
序号
E
发布者
2
F
2
E
2
D
时间
序号
F
发布者
B
A
C
D
E
F
1
2
2
5
6
2
4
3
3
lxm
49
链路状态算法
——
计算最佳路径
计算到各节点的最佳路由
计算方法:
把本节点作为源节点,计算到其他节点的路由
采用著名的
Dijkstra
算法(最短路径算法)
计算的依据
只根据自己掌握的路由信息库(拓扑)
独立计算最佳路由(不依赖别人的计算)
lxm
50
链路状态算法
Dijkstra
算法的基本思想
以计算路由的节点
V0
为源节点(出发点)
1
)设置源节点到其他所有节点的初始开销
相邻的节点设置为测得的开销值(
Ci
,
Vi
)
Ci
:源节点到相邻节点
Vi
的代价(
cost
)
不相邻的节点设置为(
∞,
-
)
2
)将具有最小
Ci
的节点
Vi
及链路加入到
V0
的路由中
3
)根据加入的
Vi
节点计算与之相邻节点到
V0
的最小代价
并将到
V0
代价最小的节点及链路加入到路由中(已加入的节点和链路除外)
4
)依此,不断重复
3
),直到包含所有节点和最佳链路为止
lxm
51
链路状态算法
Dijkstra
算法案例
假设
A
收到
B
的链路分组,
以
A
为源节点,
计算
A
到其他节点的路由
B
A
C
D
5
6
4
3
A
B
C
D
3
4
∞
A
B
4
8
A
B
C
8
A
B
C
D
8
节点的逐步加入
链路的逐步加入
A
到其他节点代价的逐步优化
A-B
A-C
B-D
6
C
3
A
时间
序号
B
发布者
5
D
B
A
C
D
5
4
3
A
的路由 转发表
目的节点
下一节点
开销
B
B
3
C
C
4
D
B
8
A
节点
4
C
3
B
开销
邻居
lxm
52
链路状态算法
Dijkstra
算法案例
假设
A
收到
B
、
C
的链路分组,
以
A
为源节点,
计算
A
到其他节点的路由
6
C
3
A
时间
序号
B
发布者
5
D
6
B
4
A
时间
序号
C
发布者
2
D
1
E
B
A
C
D
E
1
5
6
2
4
3
A
B
C
D
E
3
4
∞
∞
A
B
4
8
∞
A
B
C
6
5
A
B
C
E
6
A
B
C
E
D
节点的逐步加入
链路的逐步加入
A
到其他节点代价的逐步优化
A-B
A-C
C-E
C-D
B
A
C
D
E
1
2
4
3
A
的路由转发表
目的节点
下一节点
开销
B
B
3
C
C
4
D
C
6
E
C
5
lxm
53
A
的路由转发表
链路状态算法
Dijkstra
算法案例
A
点收到所有节点分组后
以
A
为源节点,
计算
A
到其他节点的路由
B
A
C
D
E
F
1
2
2
5
6
2
4
3
3
A
B
C
D
E
F
3
4
∞
∞
∞
A
B
4
8
∞
∞
A
B
C
6
5
∞
A
B
C
E
6
7
A
B
C
E
D
7
A
B
C
E
D
F
节点的逐步加入
链路的逐步加入
A
到其他节点代价的逐步优化
A-B
A-C
C-E
C-D
E-F
lxm
54
链路状态算法
Dijkstra
算法案例
计算的结果,
A
点到其他节点形成了一棵以
A
为根的树
根据最优判决原理,这是一棵最佳路由树
也称为信源树或汇集树
B
A
C
D
E
F
1
2
2
5
6
2
4
3
A
B
C
E
D
F
3
3
4
2
1
2
lxm
55
链路状态算法
Dijkstra
算法案例
根据计算结果,
A
节点的路由转发表如下:
A
B
C
E
D
F
3
4
2
1
2
目的节点
下一节点
开销
B
B
3
C
C
4
D
C
6
E
C
5
F
C
7
A
节点的路由转发表
B
A
C
D
E
1
2
2
5
6
2
4
3
3
F
lxm
56
链路状态算法小结
特点
与全网节点交换路由信息--路由信息的扩散
各节点独立计算最优路径--一致性、准确性有较好的保证
不是建立在别人的计算结果上(如距离矢量算法以来邻居的计算结构)
能适应网络拓扑的变化,稳定后能形成最短路径
收敛速度快--可在大网中使用
拓扑改变立即独立计算
算法复杂,存储空间需求大
需要记录全网所有的链路状态
lxm
57
4.2 OSPF
4.2.1 OSPF
概述
4.2.2 OSPF
的分区
4.2.3 OSPF
路由器类型
4.2.4 OSPF
链路类型
4.2.5 OSPF
分组格式
4.2.6 OSPF
的
LSU
分组
4.2.7 OSPF
的
LSA
类型
4.2.8 OSPF
的操作
lxm
58
4.2.1 OSPF
概述
OSPF: O
pen
S
hortest
P
ath
F
irst
一种适合与
AS
内的路由协议
采用
L-S
算法计算最短路径
OSPF
直接使用
IP
实体提供的服务
IP
协议
ID 89
是一种分层的路由协议,适合于大网
lxm
59
4.2.1 OSPF
概述
lxm
60
IP
LANs
MANs
WANs
ICMP
IGMP
ARP
RARP
Network
Layer
Network
Access Layer
TCP
UDP
Transport
Layer
OSPF
Application
Layer
89
软件实现层次
RIP
520
OSPF
算法核心思想
掌握网络拓扑结构
掌握网络拓扑
=
掌握所有路由器与邻居的连接关系
通过路由器之间彼此共享链路状态
拓扑有变化时更新并共享
路由计算
根据网络拓扑结构,计算到任意站点的最短路径
(SPF)
Dijkstra
经典算法
从最短路径确定下一跳地址
(FIB
内容
)
关键点
只要掌握了网络拓结构,路由器就能计算所有路由
R1,1
R2,2
R3,3
R0,2
R1,2
R5,25
R2,25
R3,35
R4,45
R6,56
R8,58
邻居关系:
R0
R2
R5
R0,1
R2,12
R4,14
R8,18
R1
lxm
61
4.2.2 OSPF
的分区
分区域理由:大规模的网络会给
OSPF
路由器带来沉重的负担
链路状态的改变,可能会使路由器经常执行
SPF
(最短路径优先)算法
路由表膨胀
每个路由器需要保持的完整网络拓扑(链路数据库)
OSPF
将网络划分成若干较小的区域
区域内的路由器执行
SPF
算法
区域间:交换汇总后的路由信息,而不是详细的路由信息
lxm
62
4.2.2 OSPF
的分区
lxm
63
多区域
每个区域是独立的
OSPF
路由协议范围
网络拓扑数据库只包含区域内部分
OSPF
协议在区域边界处终止
某些路由器会属于多个区域
称为:区域边界路由器
区域边界路由器构成另一个路由域(主干域)
形成分层路由结构
一级路由:区域间路由
——
主干路由
二级路由:区域内路由
OSPF
域
OSPF
域
OSPF
域
OSPF
域
OSPF
域
OSPF
域
AS
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
2
级路由
区域内路由
1
级路由
区域间路由)
3
级路由
R
R
R
区域内路由器
R
区域间路由器
R
AS
边界路由器
分级路由结构
OSPF
多区域模型
2
级路由
区域内路由
2
级路由
区域内路由
3
级路由
lxm
63
4.2.2 OSPF
的分区
Area
:包含在
AS
中的一些网络、主机和路由器的集合
类型:标准区域、主干区域(
Backbone area
)、残桩区域(
Stub area
)
Autonomous System
Area 1
Area 2
Area 0 (backbone)
To
other
ASs
lxm
64
OSPF
区域类型
区域的类型:决定
了该区域内路由器所能接收的路由信息的类型
标准区域:区域内路由器能够接收
链路状态更新
和
路由归纳(区间路由)
主干区域:具有标准区域的一切属性,特殊之处在于:它需要负责
互连
其它所有
区域
残桩区域:这种区域
不接收
那些
自治系统以外
的路由信息
如果需要发送分组到自治系统之外的网络,区域内路由器将使用
默认路由
lxm
65
Area 2
Area 3
Area 0
Area 1
Area 0
主干区域
负责分发非主干区域间的路由信息
AS
中的其他所有区域必须与主干区邻接
并不要求一定是物理连接
可以是
Virtual link
(可以人工配置)
Area 0
Area 0
Area 2
Area 1
Area 3
lxm
66
67
4.2.3 OSPF
路由器类型
Autonomous System
Area 1
Area 2
Area 0 (backbone)
To other
AS
ABR
,
BR
IR
ASBR
,
BR
IR
,
BR
Internal router
(内部路由器)
, IR
Backbone router
(主干路由器)
, BR
Area Border Router
(区域边界路由器)
, ABR
AS Border Router
(
AS
边界路由器)
, ASBR
lxm
67
68
4.2.3 OSPF
路由器类型
Autonomous System
Area 1
Area 2
Area 0 (backbone)
To other
AS
ABR:ABR
接口连接不同区域
ABR
为其连接的每个区域维护单独的链路状态数据库
并从中归纳路由,将汇总路由发布到主干区域,而主干区域中的
ABR
再将其扩散到其它区域
IR
:
IR
所有接口都在同一区域,同区的
IR
有相同的链路状态库
ASBR
:向
AS
通告
AS
以外的路由
IR
,
BR
lxm
68
4.2.4 OSPF
的链路类型
Types of links
Stub
Transient
Point-to-point
Virtual
Connect two routers directly
Each router has many neighbors
A special case of the transient network
Created when link is broken
lxm
69
4.2.4 OSPF
的链路类型
Point-to-point network
,点到点网络(链路)
Stub network
,残桩网络(链路)
Transit network
,转接网络(穿越网络,链路)
Broadcast
Frame Relay
X.25
RFC2328
lxm
70
yn@uestc.edu.cn
71
3
3
3
2
2
5
2
2
5
Stub
network
Point-to-point network
Point-to-point network
Transit network
Stub
network
Stub network
lxm
71
穿越网络中的指定路由器
DR
和备份路由器
BDR
Ethernet
A
B
C
D
E
Transient network
A
B
C
D
E
Unrealistic representation
A
B
C
D
E
Realistic representation
Designated Router
A designated router is used to show the connectivity of each router and one single network, so each router has only one neighbor now
A transient link is a network with several routers attached to it
lxm
72
4.2.5 OSPF
分组
Format
Multicasting: 224.0.0.5, 224.0.0.6
224.0.0.5
所有
OSPF
路由器组播地址
224.0.0.6
穿越网络中的
DR/BDR
组播地址
Encapsulation: IP ( protocol 89 )
Version
Type
Router ID
Area ID
Packet Length
Authentication
Authentication
Authentication Type
Checksum
Header
OSPF Packet Data
路由器在
AS
内的唯一标识,发送该分组的源路由器。
32
位,采用路由器最大接口或最小接口的
IP
地址
lxm
73
TYPE
字段:分组类型
1: Hello packet
:问候分组(类型
1
)
A 64-byte packet
(周期性发送 以保持链路
“alive”
)
2: DBD ( Database Description )
,数据库描述分组(类型
2
)
路由器间交换网络拓扑数据库
3: LSR ( Link-State Request )
,链路状态请求分组(类型
3
)
用于路由器向相邻路由器请求查询特定链路的当前信息
4: LSU ( Link-State Update )
,链路状态更新分组(类型
4
)
对
LSR
的响应,通告链路状态
5: LSAck ( Link-State Acknowledgement )
,链路状态确认分组(类型
5
)
对链路状态通告(
LSA
)的确认
4.2.5 LSU
分组格式
OSPF common header
24 bytes, Type = 4
Repeated
LSAs
(any combination of different kinds)
# LSAs
( 1 byte )
链路状态通告:五种不同类型的任意组合
链路状态通告数
lxm
75
LSA
格式
Header
LSA data
LS
sequence
number
Advertising Router ID
Link state ID
LS checksum
length
LS age
Options
LS type
创建
LSA
的路由器
ID
链路状态类型:
5
种
lxm
76
Link State ID & Link ID
Link state ID —— in LSA header
Link ID —— in Router-LSA ( type 1 LSA )
LS type
Link State ID
1: router-LSA
The originating router's Router ID
2: network-LSA
The IP interface address of the network's DR
3: summary-LSA
The destination network's IP address
4: summary-LSA
The Router ID of the described ASBR
5: AS-external-LSA
The destination network's IP address
Link type
Link State ID
1: Point-to-point link
Neighbor Router ID
2: link to transit network
Interface address of DR
(指定路由器)
3: link to stub network
IP network address
4: virtual link
Neighbor Router ID
lxm
77
4.2.6 OSPF
的
LSA
类型
Intra-area
(区域内)
Type 1: Router–LSA
Type 2: Network–LSA
Inter-area
(区域间)
Type 3: Summary–LSA
Type 4: Summary–LSA
External
(
AS
外)
Type 5: AS–external–LSA
lxm
78
Intra-area LSAs
Type 1: Router–LSA
由所有路由器创建
描述连接真路由器的一条链路
仅在一个区域内洪泛
Type 2: Network–LSA
由指定路由器
DR
创建
包含连接到该网路的所有路由器
仅在一个区域内洪泛
lxm
79
Inter-area LSAs
Type 3: Summary–LSA(
汇总链路到网络
)
:由
ABR
产生,在其
所属的每个区域
里中发布
到达其它区域
的路由信息
lxm
80
R1/R2
:两个路由表(区域
1/
区域
2
,区域
0
)
向区域
1/
区域
2
发布如何到达区域
0
的信息
ABS
产生的
LSA
(汇总链路到网络) 举例
当子网
1
恢复连通以后,在子网
4
中收到的链路状态通告
lxm
81
Inter-area LSAs
Type 4: Summary–LSA (
汇总链路到
ASBR)
:由
ABR
产生,在本
AS
内的
所有区域中
发布到达
ASBR
的路径信息
lxm
82
ABS
产生的
LSA
(汇总链路到
ASBR
) 举例
lxm
83
External LSAs
Type 5: AS–external–LSA
:由
ASBR
产生,在
本
AS
内的某些区域
中发布到达
AS
以外网络
的路径信息
Originated by ASBR
Describes a route to a destination in another AS
Flooded throughout the AS except the stub area
lxm
84
OSPF LSA Example
哪些路由器会发送
Router–LSA
?
Solution
All routers advertise router link LSAs.
R1 has two links, Net1 and Net2.
R2 has one link, Net2 in this AS.
R3 has two links, Net2 and Net3
lxm
85
OSPF LSA Example
哪些路由器发送的
LSA
中含有网络信息?
Solution
All three network must advertise network links:
R1
通告
Net1
Because it is the only router and therefore the designated router.
Net2
可能由
R1, R2, R3
中任意一个通告
depending on which one is chosen as the designated router.
R3
通告
Net3 is done
because it is the only router and therefore the designated router.
lxm
86
LSA
的发送方式
LSA
采用组播发送,所有
OSPF
路由器的组播地址都是:
224.0.0.5
在转接(穿越)网络中,
DR
和
BDR
还具有自己的组播地址:
224.0.0.
6
转接网络中,由于一般路由器只与
DR/BDR
存在邻居关系,所以其
LSA
将发送到
224.0.0.
6
lxm
87
OSPF Databases
Adjacency database
(邻接数据库)
All the neighbors to which a router has established bidirectional communication
Unique for each router
Link-state database
(链路状态数据库)
The relationship between each router and its neighbors
All routers within an area have identical link-state databases
Forwarding database ( routing table )
转发表
The routes generated when an SPF algorithm is run on the link-state database
The routing table on each router is unique
lxm
88
4.2.7 OSPF
操作
1. Establish router adjacencies
(建立邻接关系)
Done with the exchange of Hellos
2. Elect the DR / BDR ( if necessary )
如需要选择
DR/BDR
Done on multiaccess network only
3. Discover routes
(发现路由)
Done in the ExStart and Exchange states
4. Select appropriate routes
选择合适路由
Done through the calculation of SPF algorithm
5. Maintain routing information
维护路由信息
Done through the regular exchange of Hellos
lxm
89
Step 3. Discover routes
Hello Packet
A
B
Exstart
Exchange
Loading
Full
Hello Packet
DBD Packet
DBD Packet
LSAck Packet
LSAck Packet
LSR Packet
LSU Packet
LSAck Packet
lxm
90
5
、路径向量路由选择与
BGP
5.1
路径向量路由选择
5.1.1
问题的提出
5.1.2
基本思路
5.2 BGP
lxm
91
5.1
问题的提出
RIP
与
OSPF
适合
AS
内的路由协议
当运行区域变大时,
RIP
和
OSPF
变得不可用
RIP
变得不稳定,很难收敛
OSPF
计算路由表需要大量资源
引出
AS
间路由选择
——
路径向量路由选择
Path vector routing
一种策略路由选择:
基于路径属性选择到达目的地的最佳路径
lxm
92
5.2
基本思路
每个
AS
中指定一些发言节点
——
代表整个
AS
发言节点创建到达其他网络的路由表,并将其通知给相邻
AS
中发言节点
路由信息:(网络,路径)
路径:
AS
列表组成
lxm
93
yn@uestc.edu.cn
94
Initial Routing Tables
AS 3
AS 1
AS 2
AS 4
yn@uestc.edu.cn
95
Stabilized Routing Tables
A1
B1
C1
D1
AS1
B2
B3
B4
A4
A2
A3
A5
C2
C3
D2
D3
D4
AS2
AS3
AS4
3
3
路径向量路由选择路由表
路由表:
{
目的地,
Next-hop
,
Path
}
An ordered list of ASs that a packet should travel through to reach the destination
Example
Loop prevention
如果自己的
AS
在到达终点路径上,直接丢弃该报文。
Network
Next Router
Path
N01
R01
AS1
4
, AS23, AS67
N02
R05
AS22, AS67, AS05, AS89
N03
R06
AS67, AS89, AS09, AS34
N04
R12
AS62, AS02, AS09
lxm
96
4.2 BGP-4
Border Gateway Protocol
,
BGP
v4
:
RFC 1771
,
RFC 1772
,边界网关协议
IP
LANs
MANs
WANs
ICMP
IGMP
ARP
RARP
Network
Layer
Network
Access Layer
TCP
UDP
Transport
Layer
BGP-4
Application
Layer
179
软件实现层次
lxm
97
从
BGP
的观点来看互联网
AS10
AS20
AS30
AS50
AS40
到
AS60
的路由是:
AS20
、
AS10
、
AS30
AS60
lxm
98
AS
的类型
Stub AS
(
Single-homed AS
,残庄
AS
)
Only one connection to another AS
Example: AS 1, AS 3
Multihomed AS
(多归属
AS)
More than one connection to other ASs
Only a source or sink for data traffic
not allow transit traffic to pass through it
Example: the campus network of UESTC
Transit AS
(转接 或穿越
AS)
A multihomed AS that allows transient traffic
Example: ChinaNET, CERNET, …
AS 1
AS 2
R
R
R
AS 3
R
lxm
99
外部网关协议实例
两个
AS
:
CerNet
和
ChinaNet
沈阳
北京
上海
武汉
成都
广州
CerNet
ChinaNet
担心:存在过度侵占其它
AS
资源的可能性
AS
间的路由需求问题
--
不合理路由
--
外部进入的访问保护
--
穿越
AS
能力
(ISP)
--
穿越
AS
时选择避开非友好
AS
--
存在多条链路的协议交互
lxm
100
BGP,Border Gateway Protocol
一种
BGP
协议
BGP Speaker
BGP Speaker
两个
AS
的多对网关连接和路由选择
AS1
核心网
AS2
核心网
用少量网关代言
(speaker)
所有网关
BGP
核心功能
向对方通告本方可达性信息及对应网关
Net-A
Net-B
G
a
G
b
G
c
G
d
BGP
基本操作
Gc
向对方通告:
<
经
Gc
可达
Net-B>
<
经
Ga
可达
Net-A>
效果:
到
Net-A
只能通过
Ga
到
Net-B
只能通过
Gc
lxm
101
BGP
的工作模型
BGP
对等实体间通信方式
采用
TCP
保持长期连接,交互可达信息
两端
BGP
路由器不必有直接的链路连接
向内部路由器通告外部路由
BGP
BGP
TCP
连接
链路
链路
向
AS
内其它路由通告外部路由
lxm
102
BGP
协议交互
BGP
定义
5
个交互报文
OPEN
建立于对方
AS
speaker
的
BGP
通信连接、进行认证等
UPDATE
通告路由项:增加、删除操作
(
核心报文
)
NOTIFICATION
通告报文出错情况
KEEPALIVE
维持和测试通信连接
REFRESH
请求对方重传路由通告
TCP
的好处
可靠的通信,因此不需要应答、重传等复杂交互过程
为了保证可靠,仍设计了
refresh
报文,在需要的时候让对方重传
lxm
103
BGP
核心报文解析
通告对方增加和
/
或删除的路由项目
UPDATE(
删除
(
路由列表
)
,新增
<
路由属性、路由列表
>)
到该路由所经过的
AS
列表
该路由下一跳网关
Speaker
功能
让对方选择使用或弃用的参考
网关通过策略控制向对方有选择地通告路由项
--
选择权在通告方
--
由
AS
管理者制定策略
lxm
104
BGP
的功能
通告可达性
BGP
BGP
AS1
AS2
新增可达区域
N3
原可达区域
N1
R1
R2
原可达区域
N2
AS2 BGP
通告
UPDATE(
删除
N1
,新增
N3(via R1))
可访问:
AS2
的
N1
和
N2
网络部分
可访问:
AS2
的
N2
和
N3
网络部分,
N1
部分已不可访问
通知
R2
拒绝来访
N1
通知
R1
开放
N3
的来访
lxm
105
BGP
协议交互过程
设计交互过程的因素
TCP
提供了可靠通信,因此,信息传递是可靠的
通告给对方的可达性信息不会经常改变
一旦信息传递发生错误
(
小概率
)
,有恢复措施
某条链路若出现故障时的预案
交互过程设计
信息传递及握手过程该如何实现?
可达性信息传递是全部还是部分,周期还是非周期?
链路状态如何探测?
出错或重新连接时,如何得到可达性信息?
链路故障时,采取什么预案,如何交互?
lxm
106
BGP
应用
—Cernet
对外路由
教育网和电信网两个自治系统
两个网络有多处互连
成都
武汉
西安
北京
上海
哈尔滨
广州
成都
武汉
西安
北京
上海
哈尔滨
广州
Cernet
Chinanet
Uestc
校园网
从
uestc
到新浪网经过的是哪条路?
从
uestc
到清华校园网经过哪条路?
lxm
107
BGP
应用
—
负载均衡
为了增加某条链路容量,设置两条或更多的并行链路,把网间通信流量均衡分配到这些链路上
如何用
BGP
进行流量均衡?
方法
1
、。。。
方法
2
、。。。
lxm
108
BGP
小结
自治系统间的路由协议
传递路由可达性信息
可达性路由信息与我们常说的路由信息有什么不同?
自治系统对外开放窗口
BGP
如何处理到达的
IP
报文?
BGP
交互特性
TCP
可靠连接下的交互
交互过程的特点、实现的功能
自治系统内应用
网络之间互联与访问控制
例如:我校学院间的互访、与学校其它部门的互访
负载均衡
网络间多条链路的负载平衡
lxm
109
5
、多播和多播路由选择协议
引言
多播特点
IP
多播地址
IP
多播在物理网上是如何实现的?
路由器如何掌握子网上是否需要多播?
多播的路由问题
lxm
110
引言
单播
(unicast)
、广播
(broadcast)
、多播
(multicast)
单播:目的地址
=
单播地址
跨子网
本地广播:目的地址
=
全
1
地址
子网广播:目的地址
=
子网
+
全
1
主机
某个子网内
子网广播地址作单播地址看待
多播
目的地址
=
多播地址
跨子网
引言
IP
协议接收和处理多播报文的条件
IP
协议加入指定的多播组
IP
实体
报文
To:224.1.2.3
(
丢弃报文
)
未加入
224.1.2.3
多播组时
IP
实体
报文
To:224.1.2.3
(
处理报文
)
加入了
224.1.2.3
多播组时
每一个多播地址代表一个多播组
IP
实体可同时加入多个多播组
lxm
112
多播的用途
子网内路由器多播
RIP
路由器之间用多播传播路由信息
IPTV
一路电视网上只有一个视频流
极大减轻网络负担
多播在
Internet
应用广泛
VOD
Net-Meeting
远程教学
…
TV1
TV2
lxm
113
多播特点和多播类型
多播组
多播组由多播地址来定义
站点加入多播组来接收多播报文
加入多播组:设置接口允许接收该多播地址的报文
退出多播组:设置接口禁止接收该多播地址的报文
多播域
多播的传播范围,最大范围是
AS
内所有子网
站点
可随时加入或退出一个或多个多播组
多播路由器
专门的多播路由器
或在常规路由器中增加多播路由功能
lxm
114
IP
多播地址
地址范围
224.0.0.0~ 239.255.255.255
,共
2
28
个多播地址
每个多播地址定义一个多播组
多播地址属性
子网多播地址:多播域有效范围在一个子网内
全局多播地址
每个多播地址的用途在所有多播域是一致的
如同电话的
110,119
等
本地多播地址
多播用途只在该多播域内有效,其它多播域可重用
lxm
115
IETF
规定的一些
IP
多播地址
224.0.0.1
:本子网上的所有站点
224.0.0.2
:本子网上的所有路由器
224.0.0.5
:多播域内所有
OSPF
路由器
224.0.0.9
:多播域内所有
RIP
路由器
224.0.0.11
:移动代理
224.0.1.7
:语音新闻广播
224.0.1.27-224.0.1.255
:未定义,本地多播
224.2.0.0-224.2.255.255
:多媒体会议
224.0.5.128-224.0.5.255
:未定义,本地多播
224.0.6.128-224.0.6.255
:未定义,本地多播
lxm
116
IP
多播技术
IP
多播如何在
IP
子网内实现?
路由器如何掌握和管理子网内的多播组?
路由器如何为多播选择路由
(
多播路由
)
?
lxm
117
IP
多播在子网内实现
IP
多播实现策略
利用物理网的多播机制
或利用物理网的广播机制
关键是让组播成员收到应该收到的组播报文
非多播成员收到多网报文会自动滤除
局域网都支持多播和广播
广域网通常
不
支持多播和广播
则采用单播方式实现多播
在支持多播的物理网上实现多播
如:以太网具备多播功能
关键问题是
IP
多播地址到
物理网地址映射
lxm
118
以太网上实现多播
以太网的多播机制
多播地址
=1xxxxxxxx…xxxxxxxx (x
不全为
1)
MAC
MAC
MAC
MAC
MAC
多播组列表
MAC
协议中需配置多播组列表
MAC
接收以太网帧种类:
目的地址
=
自身
目的地址
=
广播地址
目的地址
in (
多播组列表
)
配置接口
MAC
最多设
16
个多播地址
当地址多于
16
个时,
MAC
进入全收状态
lxm
119
IP
多播映射到
MAC
多播
IP
多播到以太网多播
IETF
规定的映射规则
将
IP
多播地址的低
23bit
放置到
MAC
地址
01.00.5E.00.00.00
的低
23bit
上
B0
1110
xxxx
B1
xxxxxxxx
B2
xxxxxxxx
B3
xxxxxxxx
01
00
5E
00
00
00
IP
地址
MAC
地址
IP
MAC
发送:以太网多播地址
=
ARP
(IP
多播地址
)
接收:根据多播组地址列表进行过滤
IP
多播组列表
lxm
120
接收多播报文
以太网接收多播报文
MAC
对接收帧的过滤,只接收规定目的地址的帧
IP
接收多播报文
加入多播组
设置
MAC
实体的多播表
加入多个多播组
=
多次设置
MAC
实体的多播表
(
设置计数加
1)
IP
实体退出多播
撤销加入多播组
=
撤销
MAC
多播表对应地址
(
设置计数减
1)
MAC
的设置计数为
0
,则删除对应多播
MAC
地址
MAC
SAP=0800H
IP
允许接收:
1
、目的
MAC
是自己
2
、目的
MAC
是广播
3
、目的
MAC
是预设的多播
MAC
之一
多播表
未加入多播组的站点不会收到多播报文
lxm
121
IP
多播管理协议
(IGMP)
路由器掌握子网的多播组信息,能更高效地实现多子网区域的多播中继
见示意图
IGMP
协议功能
站点向路由器报告加入或退出某个多播的情况
路由器查询子网的多播组情况
IP
IP
IP
若路由器知道
B
网没有多播组
1
的成员,则可以不向
B
网转发多播组
1
的报文
B
A
多播组
1
MAC
IP
IGMP
内部接口
lxm
122
IGMP
协议
路由器掌握子网的多播组情况,是实现多子网区域组播的关键
(
将多播报文从其它子网中继进来
)
站点加入或退出多播组时,需向物理网的路由器报告
站点需确信路由器掌握自己加入多播组信息
IP
A
lxm
123
IGMP
协议设计
路由器查询、站点报告的协议
使用多播机制
(224.0.0.1)
实现
IGMP
协议通信
路由器查询(
查询范围,路由器接口所在的子网)
周期性查询,重新登记多播组记录
发出查询时,路由器将“清空”组播记录
成员报告
每个组有一个成员发出报告即可
IP
IP
IP
IP
IP
IP
IP
IP
组
1
组
1
组
2
定期查询
(125s)
报告
224.0.0.1
lxm
124
IGMP
协议说明
使用多播机制
(224.0.0.1)
实现
IGMP
通信
不参与多播的站点不受干扰
加入多播组的站点,一定同时要加入
224.0.0.1
组
路由器实际上只关心子网上有哪些多播组
哪些多播报文需要向该子网转发,与成员多少无关
查询时清空记录,以清空不存在的多播组
站点报告
组内有一个成员报告即可
路由器中有了多播组记录,站点才能成为多播组成员
在向路由器报告前,站点不算成员,故称为“延迟的成员”
lxm
125
多播组成员状态转换
路由器周期性查询,站点的多播成员也随着周期性发生改变
路由器开始查询时,站点暂时退出“正式”成员,直到发出报告为止
站点刚加入某多播组时,不清楚路由器是否有该组的记录,所以站点不能算正式成员
非成员
延迟的
成员
成员
加入
/
定时
退出
/
取消定时
超时
/
发出报告
其它站点报告
/
取消定时
计数为
0/
退出群组
查询
/
定时
lxm
126
IGMP
报文格式
IGMPv3
比以前版本有较大改变,但基本思路没变
查询报文
通用查询功能:要求任何群组都发出报告
特定查询功能:要求报文中指定的群组发出报告
报告报文
站点在报告中列出自己加入的一个或多个群组
IGMP
目前的不足
IGMP
没有为站点提供多播地址查询功能
除了永久分配的群组地址,站点不知道该子网上正在使用或可以使用哪些群组地址,也不知道这些群组地址的用途,也无法查询
没有站点主动退出时的报告机制
(
造成路由器定时清空处理
)
lxm
127
多播转发和多播路由
多子网区域的多播,路由器转发多播报文
多播转发的特征:
动态:成员在动态变化
无方向性:应该向各处转发
A
B
C
动态路由选择:
1
、当网络
C
没有该多播组成员时,路由器不应该向网络
C
转发多播报文
2
、网络
C
的其它站点也可向该组发送多播报文,路由器应该转发此报文
2
、当网络
C
有站点加入该多播组时,路由器应当向网络
C
转发多播报文
某多播组成员
多播路由环路:
多播的路由极易形成环路
lxm
128
用洪泛方式实现多播
思想:确保多播报文送达多播域各处
从一个接口收到多播,向其余接口转发
洪泛控制
转发次数控制(
IP
报文中的
TTL
值)
序号控制转发
(IP
报文中的
ID
值
)
记住并停止转发已转发过的多播报文
(
源
IP
,
ID)
第
k
次转发
1
2
2
3
3
3
3
k
3
3
3
极易形成“广播风暴”
lxm
129
用洪泛方式实现多播
洪泛的性能
多播报文在网络中的信道出现次数
A
A
处发出多播报文
计算
TTL
控制法和序号控制法的洪泛性能
lxm
130
经典的多播路由
反向路径转发
(RPF)
与单播路由结合,实现多播转发
A
G1
G2
目的
Next
接口
Net1
A
Net1
G1
1
2
3
3
当
G2
从接口
3
收到源为
A
的多播报文时,向其余接口转发
当
G2
从其它接口收到源为
A
的多播报文时,拒绝转发
G2
关于
Net1
的路由表项
与路由方向相反时转发多播,否则拒绝
lxm
131
经典的多播路由
截尾反向路径转发
(TRPF)
对
RPF
的多播性能改进
A
Net1
Net2
R1
R2
R3
R4
R5
R6
1
、当
Net2
中
没有
站点加入
A
的多播组时,
R3
应该
不再
向
R4
转发多播报文
2
、当
Net2
中
又有
站点加入
A
的多播组时,
R3
应该
恢复
向
R4
转发多播报文
lxm
132
反向路径多播
(RPM)
RPM
本质同
TRPF
增加路由器之间的多播组信息传递,动态修剪树枝
广播并剪除
(
截尾技术
)
如果某路由器下没有该多播组成员,则将此信息
(
剪除请求
)
通知路径的上一路由器,从而在多播传输上剪除该树枝
实现该截尾技术的条件是,第一个多播尽可能传递到所有子网,让路由器知道多播源站的方向,便于回溯多播信息
嫁接请求
若某路由器获知又有站点加入该多播组,则向上一路由器发出嫁接请求,把剪除的树枝再接上
第一次多播用“广播”到所有子网,路由器才考虑多播树的方向
然后路由器开始考虑发送“剪除请求”
剪除
剪除
嫁接
lxm
133
多播树
树可能是实现多播转发的“最好”的方法
树的形状
根、枝、叶
RPF
、
TRPF
、
RPM
的树
是一个以多播源站为“根”的树
值得思考的是
一个网络上有多个多播源,就有了多颗树
路由器就需要为多棵树考虑不同方向的转发
记录每个 (多播群组,源站)
问题的复杂性在于:
网络有多个群组
每个群组有多个源
(
多播群组
1,
源站
11) (
多播群组
1,
源站
12) (
多播群组
1,
源站
13)
(
多播群组
2,
源站
21) (
多播群组
2,
源站
22) (
多播群组
2,
源站
23)
(
多播群组
3,
源站
31) (
多播群组
3,
源站
32) (
多播群组
3,
源站
33)
多播组
1
多播源
1
转发接口
1
转发接口
2
转发接口
3
多播源
2
转发接口
1
转发接口
2
多播组
2
lxm
134
核心基干树
(CBT)
考虑图论“树根”的性质
树的任意“点”都可以看作树根
由此,网络上只需要一颗多播树即可
(
共享树
)
即使没有“最短路径”的优势
可以在网络拓扑的众多树中选择一颗“最佳”的树
每个路由器只需考虑自己的哪些接口是“树枝”
CBT
的形成:静态
+
动态
静态:
把网络划分成多个“区段”,指定区段内“核心路由器”
动态:
其它路由器通过“发现机制”找到“核心路由器”,形成区段内的树
树枝
树枝
树枝
lxm
135
多播
从任意节点进行多播,多播到所有节点
lxm
136
多播树
从任意节点进行多播
只需要树上的几个节点实现多播报文转发和多播发送
lxm
137
PIM—DM
、
SM
PIM
:
Protocol Independent Multicast
实际指:本身与单播路由协议有关,但仅
用单播路由表来建立多播树
PIM-DM
密集模式,站点密集的子网组成的多子网区域
多播技术:
RPM
多播报文向所有路由器扩散,直到收到某路由器“剪除请求”后,后续报文才不向该路由器扩散
PIM-SM
稀疏模式,网络上有很多点对点信道
多播技术:
CBT
指定一个“多播汇聚点”的路由器
(
只有一个区段的
CBT
技术
)
lxm
138
可靠多播?
一般情况下,广播和多播都不采用可靠传输技术
可靠传输技术
(
按序
)
需要应答和重传机制
如果要实现可靠多播,主要问题在于:
所有多播成员都向多播源发送
ACK
信息、或请求重传
多播源站无法承受非常多、来自多个子网的
ACK
如果非要实现可靠多播,该怎么办?
确认聚集器:分散处理
ACK
应答
多子网区域
1
多子网区域
2
多子网区域
3
确认聚集器
缓存多播报文,处理
ACK
及重传
减少
ACK
措施
不使用
ACK
,仅使用
NAK
lxm
139
多播小结
IP
的
D
类地址为多播地址
IP
多播要求物理子网至少支持广播通信
点对点的子网除外
子网内的多播群组是动态变化的
多播分为:本地多播和多子网区域多播
IGMP
:供路由器掌握子网的多播群组情况
路由器增加多播报文转发功能
依靠“树”形拓扑形成多播路由
RPF
、
TRPF
、
RPM
、
CBT
、
…
靠分散处理
ACK
来实现可靠多播
lxm
140