7 8 9 10 11 12
19 20 21 22 23 24
31 32 21
国防科大计算机学院网络所
13
核心路由器的基本特征和发展现状
基本特征
高背板交换带宽（40G以上） 高速的网络接口（支持OC-48/OC-192） 高可靠、稳定的路由协议软件，支持服务质量控制
发展现状
cisco GSR（Gigabit Switch Router）系列 40-320G交换带宽，支持OC-192c接口、DiffServ和MPLS Juniper M40/M160 40-160G交换带宽，支持OC-192c接口、DiffServ和MPLS Pluris 20000系列TNR（Terabit Network Router） 单机架90G交换带宽，可级连至184T，支持OC-192c接口、 DiffServ和MPLS
PHB的实现
yes P位为1？ No
高优先级队列 调度器 低优先级队列
RIO队列管理
国防科大计算机学院网络所 17
区分服务模型（3）
DS domain DS domain
MPLS
Non DS capable domain
DS domain Marking policing scheduling
marking DS domain
报文 缓冲 和 调 度
交换开关
国防科大计算机学院网络所
12
第四代IP路由器
1 2 3 4 5 6
1 2 3 4 5 6 7 8 9 10 11121314 15 16
13 14 15 16 17 18
25 26 27 28 29 30
17 1819 20 21 22 232425 26 27 28 29 30 3132
三、报文调度算法 四、缓冲区管理算法
国防科大计算机学院网络所
2
一、路由器基本工作原理
Internet基本结构
国防科大计算机学院网络所
4
路由器的分类
桌面/工作组路由器
基本接口为10/100M以太网 上行链路为ISDN、V.90、xHDL等 NAT功能，多用户共享IP地址
接入路由器
端口数目多、类型多（ISDN、V.90、xHDL等） 上行链路多为E1/T1接口
24
路由器支持QoS的基本机制（5）
调度算法
基于延时的调度 EDF(Earliest Deadline First) 基于带宽的调度 WFQ(Weighted Fair Queue)
不足
假定报文在开关输出端缓冲
国防科大计算机学院网络所
25
报文处理流程
分类
分类表 分类决策 分类表 分类决策
转发
转发表 转发决策 转发表 转发决策
区分服务的实现
IP头中一个字节的DS域 报文分类 流量调节
metering, marking, policing
报文调度
国防科大计算机学院网络所 16
区分服务模型（2）
PHB (Per Hop Behavior)
确定路由器如何处理一个报文 标准PHB Expedited Forwarding (低延时，低延时抖动） Assured Forwarding （高可靠性）
30
对查表性能的要求
Line T1 OC3 OC12 OC48 Line Rate Pkt-size=40B 1.5Mbps 155Mbps 622Mbps 2.5Gbps 4.68 Kpps 480 Kpps 1.94 Mpps 7.81 Mpps 31.25 Mpps Pkt-size=240B 0.78 Kpps 80 Kpps 323 Kpps 1.3 Mpps 5.21 Mpps
DMA DMA DMA
Line Card Local Buffer Memory
MAC
Line Card Local Buffer Memory
MAC
Line Card Local Buffer Memory
MAC
国防科大计算机学院网络所
39
Caching Addresses
LAN: Average flow < 40 packets WAN: Huge Number of flows
OC192 10 Gbps
Gigabit Ethernet (84B packets): 1.49 Mpps
国防科大计算机学院网络所 31
方法1: Ternary CAMs
Associative Memory Value 10.0.0.0 10.1.0.0 10.1.1.0 10.1.3.0 10.1.3.1 Mask 255.0.0.0 255.255.0.0 255.255.255.0 255.255.255.0 255.255.255.255 R1 R2 R3 R4 R4
报文的分类和调度
H P o n i f m e g r r c h e a S h n R t w c a o i i i d u n t n g g
e l T m c o C t e n r W o k s : p o h t e S ,4 .7 9 1
孙志刚
主要内容
一、路由器基本工作原理 二、报文查表和分类算法
Next Hop
Priority Encoder
国防科大计算机学院网络所
32
方法1: Ternary CAMs（续）
优点
一次匹配 修改简单
缺点
表项受CAM容量限制 功耗大
国防科大计算机学院网络所
33
方法2：Tries
0 1 Example Prefixes a) 00001 b) 00010 c) 00011 d) 001 e) 0101 f) 011 g) 100 h) 1010 i) 1100 j) 11110000
• 查找时间 • 存储空间 • 表修改时间 • 处理时间
国防科大计算机学院网络所
29
路由表的大小
About 10k new prefixes per year
Exponential growth before CIDR
Source: /ops/bgptable.html 国防科大计算机学院网络所
用户流量应满足A(t) <= min(M+pt,b+rt) policing 丢弃 降为best effort
国防科大计算机学院网络所 23
路由器支持QoS的基本机制（4）
缓冲区管理策略
RED(Random Early Discard )算法 RIO(RED with In and Out)算法
国防科大计算机学院网络所
9
第二代IP路由器
CPU
Buffer Memory
DMA
DMA
DMA
Line Card Local Buffer Memory
MAC
Line Card Local Buffer Memory
MAC
Line Card Local Buffer Memory
MAC
国防科大计算机学院网络所
10
第三代IP路由器
下一跳
到达报文
基于IPv4单播目的地址的路由查表
国防科大计算机学院网络所 28
最长前缀匹配
Prefix 128.9.16.14
65/24 128.9/16 128.9.16/20 128.9.19/24 128.9.25/24 128.9.176/20 142.12/19
Port
3 5 2 7 10 1 3
园区路由器
端口数目多，基本为局域网接口 上行链路为千兆口或POS口 软件复杂，支持协议多，安全性要求高
核路由器工作原理
用目的IP地址查转发表. TTL减1，修改IP头校验和 将报文交换到目的输出接口 向链路发出报文
国防科大计算机学院网络所
6
基本组成
拥塞控制 允许控制 资源预约
37
10.1.1, 10.1.2, 10.2.3
国防科大计算机学院网络所
方法4：Hash技术（续）
优点
低速、较小容量时，软件解决方案
缺点
表项修改复杂 可扩展能力差 多次hash操作
国防科大计算机学院网络所
38
方法5：硬件路由表Cache
Slow Path
CPU
Buffer Memory
Fast Path
国防科大计算机学院网络所
21
路由器支持QoS的基本机制（2）
报文分类
基于DS域的分类
简单，用于区分服务
基于多个域的分类 复杂，如利用5元组分类
分类必须线速进行
避免报文在分类前缓冲（HOL阻塞）
国防科大计算机学院网络所
22
路由器支持QoS的基本机制（3）
令牌桶
参数为（r, b, p, M, m)
r b p M m 平均速率 桶深 最大速率 最大包长 最小包长
存储器管理
交换
调度
分类表 分类决策
转发表 转发决策
国防科大计算机学院网络所
26
二、报文查表和分类算法
路由表查找过程
H E A D E R
目的地址
转发引擎 Next Hop Computation Forwarding Table Destination Next Hop -------------------
Switched Backplane
Line Card Local Buffer Memory
MAC
CPU Card
Line Card Local Buffer Memory
MAC
国防科大计算机学院网络所
11
核心路由器基本结构
协议软件 线卡 线卡 交换 开关 线卡 线卡