域间路由
罗忠文
http://xgxy.cug.edu.cn/rjgcx/lzw
内容取自UCB的教程
[email protected]
1
所讲内容?
• 讲完了基础 (可靠性, 路由)
• 讲完了当今网络架构的基础
– 名字（Naming）, web, TCP
• 现在重新回到基础
– 拥塞控制
– 路由: 域间和高级课题
• 然后讲各种主题cs:
– 以太网（Ethernet）,无线（wireless）,（安全）
security等.
2
路由
• 提供网络间的路径
– 前缀指地址的“网络”部分
• 目前为止,仅考虑在某个域内的路由
– 所有路由器都有相同的路由度量 (最短路径）
• 在此配置下，许多问题都可以忽略….
– 无自治: 中心管理控制
– 没有私密问题:中心管理控制
– 没有策略问题:中心管理控制
• 没有其他的了!
3
Internet不仅只有一个域…
• Internet不只是一组没有结构的网络
– “网络”是指前缀
• Internet由一组“自治系统”组成
– 独立运行的网络,一些是商业 ISPs
– 目前超过30,000个自治系统
– 如AT&T, China Telecom, France Telecom, UCB, IBM,
Intel, etc.
• 自治系统有时也称为“域”
– 因此“域间路由”
4
Internet: 大量自治系统
Large ISP
Large ISP
Stub
Small ISP
Dial-Up
ISP
Stub
Access
Network
Stub
5
路由分三层
• 位于单个网络中: 到达每个主机
– 将在“链路层”讲义中讲(Ethernet等)
• 域内（Intradomain）:网络间路由
– 前面的路由讲义中讲过了
• 域间（Interdomain）: 自治系统间的路由
– 今天的内容
• 需要域间路由协议
– BGP是当前的标准
6
一个全新的路由策略
• 网络寻路的思想早在Internet之前就已经熟知
– Dijkstra's algorithm 1956
– Bellman-Ford 1958
• 能实现其自己私有策略的“自治系统”的说法是新
的
• 匆忙设计出的BGP就是为了响应此需求
• 自此以后，它使我们迷惑不解…..
7
谁使用BGP?
AS2
BGP
AS1
R3
R2
R1
R
边界路由器
内部路由器
两种类型的网络
 边界路由器 (Edge), 内部路由器 (Core)
8
BGP的目的
you can reach
net A via me
AS2
BGP
AS1
R3
R2
traffic to A
R1
table at R1:
dest next hop
A
R2
A
R
border router
internal router
跨自治系统共享连接信息
9
I-BGP 和 E-BGP
IGP: Intradomain routing
Example: OSPF
I-BGP
R2
IGP
R3
A
AS1
E-BGP
announce B
AS2
R1
AS3
R5
R4
R
border router
internal router
B
10
进一步细节
6
2
3
4
3
边界路由
•
•
•
•
9
2
1
内部路由
提供内部可达 (IGP)
学习路由到外部目标 (eBGP)
分布式外部学习路由内部的 (iBGP)
选择最近出口 (IGP)
11
余下的讲义...
• BGP为什么是这样方式的动机
– 两个主要问题…..
• 讨论域间路由的一些问题
• 解释BGP的一些细节
– 非基础的, 只是一系列专门的设计决策
– 努力不涉及此部分的内容….
12
形成域间路由的考虑因子
• 无法使用之前路由方案的两个主要原因
13
1. 自治系统（AS）是自治的
• 希望选择其自己的内部路由协议
– 不同的算法和度量
• 希望基于策略自由路由到外部
– “我的流量不能在竞争者的网络中传播”
– “我不希望在我的网络中携带传输流量”
– 无法表示成整个Internet的“最短路径”!
• 希望保持其连接和策略私有
– 将揭示商业关系, 网络结构
14
2. 自主系统拥有商业关系
• 自主系统间的三种基本关系
– 自主系统A可以是自主系统B的客户
– 自主系统A可以是自主系统B的提供商
– 自主系统A可以是自主系统B的对等体
• 商业实现
– 客户付费给提供商
– 对等体相互不付费
 交换差不多相等的流量
• 策略实现: 包流遵循金钱流
– “当发送流量时, 相对于对等体更偏好到客户, 相对于服务
商更偏好对等体”
15
– “不把一个服务商的流量带到另一个服务商”
商业关系
自主系统间的关系
provider
peer
customer
peer
商业含义
•Customer pay provider
•Peers don’t pay each other
16
路由遵循金钱!
允许的流量
禁止的流量
• 对等体提供其客户间的传输
• 对等体不提供两个对等体间传输
17
自主系统层次拓朴
–目标是IP前缀 (如, 12.0.0.0/8)
–结点是自主系统 (ASes)
 内部被隐藏
–链路: 连接和商业关系
4
3
5
2
1
Client
7
6
Web server
18
我们可以使用何种路由算法?
• 要点是策略和私密性
• 无法使用最短路径
– 域没有任何公共的度量
– 策略选择可能不是最短路径
• 无法使用链路状态
– 可能需要泛滥策略偏好和拓朴
– 可能违反私密性
19
路由的基本要求
• 避免环和死路
• 如何同时满足基本要求和允许自由策略?
• 避免环的最简单方式?
– 路径向量!
20
路径向量路由
•距离向量路由扩展
–支持灵活路由策略
–更快的环路检测 (没有count-to-infinity)
•主要思路: 公告整个路径
–距离向量:对每个目标d发送距离度量
–路径向量: 对每个目标d发送整个路径
“d: path (2,1)”
3
“d: path (1)”
1
2
数据流量
数据流量
d 21
更快环路检测
•结点可以很容易检测环路
–结点在路径中查找其自己的结点标识
–例, 结点1看到其自己在路径 “3, 2, 1”中
•结点可以简单地丢弃有环路径
–例, 结点 1 简单地丢弃公告
“d: path (2,1)”
3
“d: path (1)”
2
“d: path (3,2,1)”
1
22
灵活策略
•每个结点可应用局部策略
–路径选择: 使用哪条路径?
–路径输出: 公告哪条路径?
•例
–相对于“2,1”结点2可能更偏好路径“2,3,1”
–结点1可能不让结点3知道路径“1, 2”
2
3
1
23
选择 vs 输出
• 选择策略
– 决定我希望我的流量取哪条路径
• 输出策略
– 决定我愿意携带谁的流量
• 注:
– 我携带的任何流量将遵循同样的路径, 因此两者之间有联
系
– 从协议的视角, 决策可以是任意的
 能依赖于整个路径 (PV方式的优点)
24
示例
路由输出
Customer
Competitor
路由选择
Primary
Backup
选择: 控制网络中出去的流量
输出: 控制网络中进来的流量
数据流方向与路由公告方向相反
25
标准策略示例
• 传输网络:
– 选择: 偏好序列“客户->对等体->提供商”
– 输出:




让客户使用你的任何路由
让任何路由通过你到你的客户
不输出给在路由中的人(毒性反转)
阻塞所有其他的
• Multihomed (nontransit) 网络:
– 输出: 不替其他域输出路由
– 选择: 优先选择原始的，其次选择备份的
 直接发送到对等体
26
策略改变的领域
• ISP现在是“眼球eyeball”和/或“内容”ISP
• 更少关注“传输”, 更多关注客户属性
• 目前，还没有实用的系统策略
27
路径向量策略路由的问题
• 可达性
• 安全
• 性能
• 缺乏独立
• 策略振荡
28
可达性
• 在正常的路由中, 如果图是连接的，可达性能保证
• 对于策略路由,这并不总能保证
Provider
AS 1
AS 3
AS 2
Provider
Customer
29
安全
• 某自主系统可能声称其能达某个前缀，但真实情况
是其无法到达路由 (黑洞流量)
– 不针对策略和路径向量的问题
– 其重要性是由于自治系统的自治
– 可解决: 让自治系统 “证明”其有路径
• 注: 自治系统也可能有诱因沿与公告的不同的路径
转发包
– 告诉客户关于虚构的最短路径…
– 解决更困难!
30
性能中不成问题的问题
• 内部路由 (non)
– 域典型地使用“热土豆hot potato”路由
– 不总是最优的, 但经济有效的
• 策略不是关于性能的 (non)
– 因此策略选择的路径不是最短的
• 策略相容路径中选择 (non)
– 基于最少AS跳数选取, 和实际延时没有关联
– 20%路径膨胀至少5个路由器跳
31
性能(示例)
• AS路径长度可能误导
– 自主系统可能有许多路由器层跳数
BGP 说路径4 1
比路径3 2 1好
AS 4
AS 3
AS 2
AS 1
32
实际性能问题
• 收敛时间:
– BGP 中断运转是Internet问题的最大源
• 主要是由于缺乏孤立
33
缺乏孤立性: 动力学
• 如果路径有变化, 路
径必须将此变化重新
向每个上游结点公告
BGP updates per day
(100,000s)
10
– 这对距离向量为什么不
是问题?
8
• “Route Flap
Damping” 假定支持
此, (但结果是产生更
多问题)
4
6
2
0
Date (Jan - Dec 2005)
Fig. from [Huston & Armitage 2006]
34
缺乏孤立性: 路由表大小
• 每个BGP路由器必须知道到每个其它IP前缀的路径
– 但路由器内存昂贵，从而受到限制
• 前缀数超过线性增加
• 当前研究的主题
180000
Number of prefixes in BGP table
100000
Jan ’02
Fig. from
[Huston &
Armitage 2006]
Jan ’06
35
Five Minute Break
Any questions?
36
由于策略产生的固有振荡
依赖于策略的相互作用
“1”到达 “0”更偏好
“1 3 0” 而非 “1 0”
130
10
1
0
210
20
2
3
320
30
37
由于策略产生的固有振荡
初始: 结点 “1”, “2”, 和 “3” 仅知道到 “0”的最短路
径
130
10
1
0
210
20
2
3
320
30
38
由于策略产生的固有振荡
“1” 向“2”公告其路径 “1 0”
130
10
1
0
210
20
2
3
320
30
39
由于策略产生的固有振荡
130
10
1
0
210
20
2
3
320
30
40
由于策略产生的固有振荡
“3”向“1”公告其路径 “3 0”
130
10
1
0
210
20
2
3
320
30
41
由于策略产生的固有振荡
130
10
1
0
210
20
2
3
320
30
42
由于策略产生的固有振荡
“1”从“2”收回其路径 “1 0”，因为不再使用
130
10
1
0
210
20
2
3
320
30
43
由于策略产生的固有振荡
130
10
1
0
210
20
2
3
320
30
44
由于策略产生的固有振荡
“2” 向 “3” 公告其路径 “2 0”
130
10
1
0
210
20
2
3
320
30
advertise: 2 0
45
由于策略产生的固有振荡
130
10
1
0
210
20
2
3
320
30
46
由于策略产生的固有振荡
“3” 从 “1” 回收其路径 “3 0” 因为不在使用
130
10
1
0
210
20
2
3
320
30
47
由于策略产生的固有振荡
130
10
1
0
210
20
2
3
320
30
48
由于策略产生的固有振荡
“1” 向 “2”公告其路径 “1 0”
130
10
1
0
210
20
2
3
320
30
49
由于策略产生的固有振荡
130
10
1
0
210
20
2
3
320
30
50
由于策略产生的固有振荡
“2” 从 “3” 收回 其路径 “2 0” 因为不再使用
130
10
1
0
210
20
2
3
320
30
withdraw: 2 0
51
由于策略产生的固有振荡
依赖于策略交互
130
10
1
0
210
20
2
3
320
30
回到起点!
52
由于策略产生的固有振荡
• 策略自治 vs 网络稳定
– 即使对于小规模自治系统，也有策略震荡
– 近来研究的关注点
• 非容易问题
– PSPACE-complete 确定给定的策略最终是否收敛!
• 但是, 如果策略遵循正常的商业活动,稳定性有保障
– “Gao-Rexford conditions”
53
理论结果 (细节)
• 如果偏好遵守Gao-Rexford, BGP是安全的
– 安全 = 保证收敛
• 如果没有 “争议dispute wheel”, BGP是安全的
– 但反过来不真
• 如果有两个稳定状态, BGP不安全
– 但反过来不真
• 如果域名无法对路由器说谎,并且没有争议（
dispute wheel）, BGP鼓励兼容
54
余下内容....
• BGP细节
• 尽量醒着吧.....
55
边界网关协议Border Gateway Protocol (BGP)
•用于Internet的域间路由协议
–基于前缀的路径向量协议
–基于策略的路由，依据自治系统路径
–过去20年里演化
• 1989 : BGP-1 [RFC 1105]
– Replacement for EGP (1984, RFC 904)
• 1990 : BGP-2 [RFC 1163]
• 1991 : BGP-3 [RFC 1267]
• 1995 : BGP-4 [RFC 1771]
– Support for Classless Interdomain Routing (CIDR)
56
BGP路由表
ner-routes>show ip bgp
BGP table version is 6128791, local router ID is 4.2.34.165
Status codes: s suppressed, d damped, h history, * valid, > best, i - internal
Origin codes: i - IGP, e - EGP, ? - incomplete
Network
Next Hop
Metric LocPrf Weight Path
* i3.0.0.0
4.0.6.142
1000
50
0 701 80 i
* i4.0.0.0
4.24.1.35
0
100
* i12.3.21.0/23
192.205.32.153
0
50
0 7018 4264 6468 ?
* e128.32.0.0/16
192.205.32.153
0
50
0 7018 4264 6468 25 e
0 i
57
BGP操作
在TCP 端口 179
建立会话
AS1
BGP 会话
交换所有
活动路由
AS2
交换增量
更新
只要链路是ALIVE 交换
路由更新消息
58
BGP 路由处理
Open ended programming.
Constrained only by vendor configuration language
Receive Apply Policy =
filter routes &
BGP
Updates tweak attributes
Apply Import
Policies
Based on
Attribute
Values
Best
Routes
Best Route
Selection
Best Route
Table
Apply Policy =
filter routes &
tweak attributes
Transmit
BGP
Updates
Apply Export
Policies
Install forwarding
Entries for best
Routes.
IP Forwarding Table
59
选择最佳路由
•
根据操作指令设置/修改 路由特性
•
使用标准化规则，基于特性路由比较
1.
2.
3.
4.
5.
6.
7.
最高本地偏好 (缺省时所有的都相等…
最短自治系统路径长度
…因此缺省时 = 最短路径)
最低源类型 (IGP < EGP < incomplete)
最低 MED
eBGP- 优于 iBGP-learned
最低 IGP 费用
最低 下一跳 路由器ID
60
特性
• 目标前缀 (如 128.112.0.0/16)
• 路由有特性, 包括
– 自治系统路径 (如, “7018 88”)
– 下一跳IP地址 (如, 12.127.0.121)
192.0.2.1
AS 7018
12.127.0.121
AT&T
AS 88
AS 12654
Princeton
RIPE NCC
RIS project
128.112.0.0/16
AS path = 88
Next Hop = 192.0.2.1
128.112.0.0/16
AS path = 7018 88
Next Hop = 12.127.0.121
61
自主系统路径特性
128.112.0.0/16
AS Path = 1755 1239 7018 88
128.112.0.0/16
AS Path = 1239 7018 88
AS 1239
Sprint
AS 1755
AS 88
Princeton
Global Access
128.112.0.0/16
AS Path = 1129 1755 1239 7018 88
Ebone
AS 12654
128.112.0.0/16
AS Path = 7018 88
AS7018
128.112.0.0/16
AS Path = 88
AS 1129
RIPE NCC
RIS project
128.112.0.0/16
AS Path = 3549 7018 88
AT&T
128.112.0.0/16
AS Path = 7018 88
AS 3549
Global Crossing
128.112.0.0/16
Prefix Originated
62
本地偏好特性
140.20.1.0/24
在不同的自主系统路径间选
择策略
值越高，越偏好
AS1
AS3
AS2
AS4
由IBGP携带, 局部于自治系
统.
BGP table at AS4:
Destination
AS Path
Local Pref
140.20.1.0/24
AS3 AS1
300
140.20.1.0/24
AS2 AS1
100
63
内部BGP和本地偏好
•例
– 两个路由器都偏好左边的通过AS 100的路径
– … 尽管右边路由器学习到一个外部路径
AS 200
AS 100
AS 300
Local Pref = 90
Local Pref = 100
I-BGP
AS 256
64
源特性
• 谁发起的公告?
• 某个前缀在何处注入到BGP中?
• IGP, BGP or Incomplete (通常用于静态路由)
65
Multi-Exit Discriminator (MED)特性
• 当自治系统通过两个或者多个链路
互连时
• AS公告前缀集MED (图中的AS2)
AS1
Link B
Link A
MED=50
• AS使用MED来选择链路接收前缀
MED=10
AS2
• 指定前缀与公布的链路有多近的一
种方式
AS4
AS3
66
IGP费用特性
• 被用于BGP来进行hot-potato路由
– 每个路由器选择最近的出口点
– … 基于域内协议的路径费用
• 与MED有点冲突
dst
A
3
4
F
D
3
8 E
5
B
9
8 10
4
G
C
hot potato
67
最低路由器ID
• 路由选择决策过程的最后一步
• “任意方式”打破平局
• 但到达此步我们会做一些事情,因此平局如何打破是
有关的
68
联合BGP和IGP信息
•边界网关协议(BGP)
–公布到达外部目标的可达性
–映射目标前缀到出口点
 128.112.0.0/16 reached via 192.0.2.1
•内部网关协议(IGP)
–用于在AS内计算路径
–将出口点映射到输出链路
 192.0.2.1 reached via 10.1.1.1
10.1.1.1
192.0.2.1
69
一些路由器不需要BGP
• 连接到单个上游ISP的客户
– ISP可将前缀引入到 BGP
– … 而客户可简单地使用缺省路由到ISP
Qwest
Nail up routes 130.132.0.0/16
pointing to Yale
Nail up default routes 0.0.0.0/0
pointing to Qwest
Yale University
130.132.0.0/16
70
小结
• BGP对Internet是基本的
– 把多个不同的机构连接在一起
• 产生一些基本的挑战....
– 导致使用路径向量做法
• ...各种细节
• 希望知道:
– 基础, 振荡, 标准策略
71

DB-450F/450B

4th Edition: Chapter 1

信息检索

Document

Alle offenen Seminartermine von Semprocon 2014