第七章网络层协议主要内容
7.1 网络层概述
7.2 路由算法
7.2.1 最优化原则
7.2.2 最短路径路由算法
7.2.3 洪泛算法
7.2.4 基于流量的路由算法
7.2.5 距离向量路由算法
7.2.6 链路状态路由算法
7.2.7 分层路由
7.2.8 移动主机的路由
7.3 拥塞控制算法
7.3.1 拥塞控制的基本原理
7.3.2 拥塞控制算法
7.4 网络互连
7.4.1 级联虚电路
7.4.2 无连接网络互连
7.4.3 隧道技术
7.4.4 互联网路由
7.4.5 分段
7.4.6 防火墙
7.5 INTERNET网络层协议
7.5.1 IP协议
7.5.2 Internet控制协议
7.5.3 内部网关路由协议,OSPF
7.5.4 外部网关路由协议,BGP
7.6 路由器体系结构和关键技术
7.1 网络层概述（ 1）
ISO 定义
- 网络层为一个网络连接的两个传送实体间交换网络服务数据单元提供功能和规程的方法，它使传送实体独立于路由选择和交 换的方式。
网络层是处理端到端传输的最低层。
网络层要解决的关键问题,向传输层提供服务、选择路由
、拥塞控制。
了解通信子网的拓扑结构
网络层设计的有关问题
- 设计目标：
服务与通信子网技术无关。
通信子网的数量、类型和拓扑结构对传输层隐蔽。
传输层能获得同一的网络地址，即使跨越多个 LAN或 WAN。
7.1 网络层概述（ 2）
- 为传输层提供服务
面向连接服务传统电信的观点：通信子网应该提供可靠的、面向连接的服务。
无连接服务
Internet的观点：通信子网无论怎么设计都是不可靠的，
因此网络层只需提供无连接服务。
- 网络层的内部组织
虚电路（ virtual circuit）
数据报（ datagram）（对每个分组进行路由计算）
7.1 网络层概述（ 3）
- 虚电路子网与数据报子网的比较
路由器内存空间与带宽的权衡
虚电路方式，路由器需要维护虚电路的状态信息；
数据报方式，每个数据报都携带完整的目的 /源地址，浪费带宽
连接建立时间与地址查找时间的权衡
虚电路需要在建立连接时花费时间
数据报则在每次路由时过程复杂
虚电路方式很容易保证服务质量 QoS（ Quality of
Service），但比较脆弱
虚电路方式很容易保证服务质量 QoS(Quality of
Service)，适用于实时操作，但比较脆弱。
数据报不太容易保证服务质量，但是对于通信线路的故障，适应性很强。
7.1 网络层概述（ 4）
7.1 网络层概述（ 5）
网络层为传输层提供的服务
- 面向连接服务：将复杂的功能放在网络层 (通信子网 )。
- 无连接服务：将复杂的功能放在传输层。
- 通信子网提供的服务（面向连接或无连接）与通信子网技术（虚电路或数据报）没有必然联系。
- 服务与子网结构的不同组合的例子小结
网络层的地位
- 位于数据链路层和传输层之间，使用数据链路层提供的服务，
为传输层提供服务；
- 通信子网的最高层；
- 处理端到端传输的最低层。
网络层的作用
- 屏蔽各种不同类型网络之间的差异，实现互连
- 了解通信子网的拓扑结构，选择路由，实现报文的网络传输
网络层的两种实现方式 ——数据报和虚电路
- 都属于分组交换，采用存储转发机制。
- 数据报 (datagram)：每个分组被单独路由，分组带有全网唯一的地址
- 虚电路 (virtual circuit)：先在源端和目的端之间建立一条虚电路
，所有分组沿虚电路按次序存储转发，最后拆除虚电路。在虚电路中，每个分组无须进行路径选择。
网络层提供的服务
- 面向连接的服务和无连接的服务。
7.2 路由算法（ 1）
路由算法是网络层软件的一部分
- 子网采用数据报方式，每个包都要做路由选择；
- 子网采用虚电路方式，只需在建立连接时做一次路由选择。
路由算法应具有的特性
- 正确性（ correctness）
- 简单性（ simplicity）
- 健壮性（ robustness）
- 稳定性（ stability）
- 公平性（ fairness）
- 最优性（ optimality）
路由算法分类
- 非自适应算法，静态路由算法
- 自适应算法，动态路由算法
7.2 路由算法（ 2）
7.2.1 最优化原则
最优化原则（ optimality principle）
- 如果路由器 J 在路由器 I 到 K 的最优路由上，那么从 J
到 K 的最优路由会落在同一路由上。
汇集树（ sink tree）
- 从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为汇集树；
- 路由算法的目的是找出并使用汇集树。
7.2 路由算法（ 3）
7.2.2 最短路径路由算法（ Shortest Path Routing）
属于静态路由算法
基本思想
- 构建子网的拓扑图，图中的每个结点代表一个路由器，
每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。
测量路径长度的方法
- 结点数量
- 地理距离
- 传输延迟
- 距离、信道带宽等参数的加权函数
算法一（ Dijkstra算法）,
设源节点为 1，计算源节点到所有节点的最短路径。
令 D(v)为源节点到节点 v的距离，是沿某一通路的所有链路的长度之和。再令 L(i,j)为相邻节点 i到 j的距离，不相邻节点 i到 j
的 L(i,j) 为无穷大。算法如下：
（ 1）初始化：令 N表示网络节点的子集，初始时 N={1}。对于所有不在 N中的节点有：
D(v)=L(I,j)，若节点 v与节点 1直接相连
D(v)=无穷大，若节点 v与节点 1不相连
（ 2）寻找一个不在 N中的节点 w，其 D(w)最小。把 w加入到 N
中，然后对所有不在 N中的节点，用 [D(v),D(w)+L(w,v)]中较小的值更新所有的 D(v)值。
（３）重复步骤（２），直到网络中所有的节点都在Ｎ中为止
算法二对每个节点赋予标记（ n,D(v)），其中 D(v) 代表从节点 v到目的节点的最段距离的当前值，而 n则为沿着当前已算出的最短通路的后继节点的编号。
（１）初试化：设节点１为目的节点，将其他所有节点标上 （,,无穷大），符号,表示暂时空缺，而无穷大可以用任何足够大的数值表示。
（ 2）对所有除目的节点以外的节点标上最短距离，即对任何 v
不等于 1的节点做如下运算：对所有的与节点 v相邻的节点 w
，用节点 w的当前值 D(w)计算 D(w)+L(w,v)，其中 w包括 1，
找出其最小值，用此最小值更新原来的 D(v)。同时更新 n的值。可以从所得到的当前最小 D(v)的通路中找到节点 v的后继节点，此后继节点的标号就是 n的当前值。
当对所有 v不等于 1的节点全部都进行完上述计算，重复（ 2）
。若计算结果与前次一致，计算结束。
7.2 路由算法（ 5）
7.2.3 洪泛算法（ Flooding）
属于静态路由算法
基本思想
- 把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。
主要问题
- 洪泛要产生大量重复包。
解决措施
- 每个包头包含站点计数器，每经过一站计数器减 1，为 0
时则丢弃该包；
- 记录包经过的路径
7.2 路由算法（ 6）
选择性洪泛算法（ selective flooding）
- 洪泛法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上。
应用情况
- 路由器和线路的资源过于浪费，实际很少直接采用；
- 具有极好的健壮性，可用于军事应用；
- 作为衡量标准评价其它路由算法。
7.2 路由算法（ 7）
7.2.4 基于流量的路由算法（ Flow-Based Routing）
属于静态路由算法
基本思想
- 既考虑拓扑结构，又兼顾网络负荷；
- 前提：每对结点间平均数据流是相对稳定和可预测的；
- 根据网络带宽和平均流量，可得出平均包延迟，因此路由选择问题归结为找产生网络最小延迟的路由选择算法。
- 提前离线（ off-line）计算
需要预知的信息
- 网络拓扑结构；
- 通信量矩阵 Fij；
- 线路带宽矩阵 Cij；
- 路由算法（可能是临时的）。
1/? = 800 bits
根据排队论，平均延迟 T = 1/ (?C -?)
7.2 路由算法（ 8）
7.2.5 距离向量路由算法（ Distance Vector Routing）
属于动态路由算法，也称 Bellman-Ford路由算法和
Ford-Fulkerson算法，最初用于 ARPANET，被 RIP协议采用。
基本思想
- 每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与 相邻路由器 交换距离信息来更新表；
- 以子网中其它路由器为表的索引，表项包括两部分：到达目的 结点的最佳输出线路，和到达目的结点所需时间或距离；
- 每隔一段时间，路由器向所有邻居结点发送它到每个目的结点 的距离表，同时它也接收每个邻居结点发来的距离表；
- 邻居结点 X发来的表中,X到路由器 i的距离为 Xi,本路由器到 X
的距离为 m，则路由器经过 X到 i的距离为 Xi + m。根据不同邻居发来的信息，计算 Xi + m，并取最小值，更新本路由器的路由表；
- 注意：本路由器中的老路由表在计算中不被使用。
7.2 路由算法（ 9）
7.2 路由算法（ 10）
无限计算问题
- 算法的缺陷：对好消息反应迅速,(当 A 连上网时）对坏消息反应迟钝
7.2 路由算法（ 11）
水平分裂算法
- 工作过程与距离向量算法相同，区别在于到 X的距离不向真正通向 X的邻居结点报告，使得坏消息传播的也快。
Fig,5-11
- 虽然广泛使用，但有时候会失败。
7.2 路由算法（ 12）
7.2.6 链路状态路由算法（ Link State Routing）
距离向量路由算法的主要问题
- 实际应用选择路由时，用队列长度衡量时延没有考虑线路带宽；
- 路由收敛速度慢。
链路状态路由算法
- 发现邻居结点，并学习它们的网络地址；
路由器启动后，通过发送 HELLO包发现邻居结点；
- 测量到每个邻居结点的延迟或开销；
一种直接的方法是：发送一个要对方立即响应的 ECHO包
，来回时间除以 2即为延迟。
载荷的考虑,从 ECHO包进入队列时算时或开始发送时计时
7.2 路由算法（ 13）
- 将所有学习到的内容封装成一个包；
包以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表；
列表中对应每个邻居结点，都有发送方到它们的延迟或开 销；
Fig,5-15
链路状态包定期创建或发生重大事件时创建。
- 将这个包发送给所有其它路由器；
基本思想：洪泛链路状态包，为控制洪泛，每个包包含一 个序号，每次发送新包时加 1。路由器记录信息对（源路由器，序号），当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最 大序号小，则认为过时而丢弃；
改进
序号循环使用会混淆，解决办法：使用 32位序号；
7.2 路由算法（ 14）
路由器崩溃后，序号重置；
序号出错；
第二、三问题的解决办法：增加年龄（ age）域，每秒钟年龄减 1，为零则丢弃。
链路状态包到达后，延迟一段时间，并与其它已到达的来自同一路由器的链路状态包比较序号，丢弃重复包，保留新包；
链路状态包需要应答；
Fig,5-16
- 计算到每个其它路由器的最短路径。
根据 Dijkstra算法计算最短路径；
实用协议
- OSPF
- IS-IS
7.2 路由算法（ 15）
链路状态算法（ LS）和距离向量算法（ DV）的比较
- 路由信息的复杂性
LS
路由信息向全网发送
with n nodes,E links,O(nE) msgs sent each
DV
exchange between neighbors only
- 收敛（ Convergence）速度
LS
使用最短路径优先算法，算法复杂度为 O(n**2)
n个结点（不包括源结点），需要 n*(n+1)/2 次比较
使用更有效的实现方法，算法复杂度可以达到 O(nlogn)
可能存在 路由振荡（ oscillations）
DV
convergence time varies
may be routing loops
count-to-infinity problem
7.2 路由算法（ 16）
- 健壮性,what happens if router malfunctions?
LS
node can advertise incorrect link cost
each node computes only its own table
DV
DV node can advertise incorrect path cost
each node’s table used by others
error propagate thru network
7.2 路由算法（ 18）
7.2.7 分层路由（ Hierarchical Routing）
网络规模增长带来的问题
- 路由器中的路由表增大；
- 路由器为选择路由而占用的内存,CPU时间和网络带宽增大。
分层路由
- 分而治之的思想；
- 根据需要，将路由器分成区域（ regions）、聚类（
clusters）、区（ zones）和组（ groups） …
- Fig,5-17，路由表由 17项减为 7项。
分层路由带来的问题
- 路由表中的路由不一定是最优路由。
小结
最优化原则
- 路由算法的目的是找出并使用汇集树。
静态路由算法
- 最短路径路由算法
- 洪泛算法
- 基于流量的路由算法
动态路由算法
- 距离向量路由算法
将自己对全网拓扑结构的认识告诉给邻居
无穷计算问题，水平分裂算法
- 链路状态路由算法
将自己对邻居的认识洪泛给全网
分层路由
移动主机的路由
7.3 拥塞控制算法（ 1）
拥塞（ congestion）
- 网络上有太多的包时，性能会下降，这种情况称为 拥塞 。
- Fig,5-22
拥塞产生的原因 (资源分配 )
- 多个输入对应一个输出；
- 慢速处理器；
- 低带宽线路。
解决办法
- 针对某个因素的解决方案，只能对提高网络性能起到一点点好处，甚至可能仅仅是转移了影响性能的瓶颈；
- 需要全面考虑各个因素。
7.3 拥塞控制算法（ 2）
拥塞控制与流量控制的差别
- 拥塞控制（ congestion control）需要确保通信子网能够承载用户提交的通信量，是一个全局性问题，涉及主机
、路由器等很多因素；
- 流量控制（ flow control）与点到点的通信量有关，主要解决快速发送方与慢速接收方的问题，是局部问题，一般都是基于反馈进行控制的。
7.3 拥塞控制算法（ 3）
7.3.1 拥塞控制的基本原理
根据控制论，拥塞控制方法分为两类
- 开环控制
通过好的设计来解决问题，避免拥塞发生；
拥塞控制时，不考虑网络当前状态；
- 闭环控制
基于反馈机制；
工作过程
监控系统，发现何时何地发生拥塞；
把发生拥塞的消息传给能采取动作的站点；
调整系统操作，解决问题。
7.3 拥塞控制算法（ 4）
衡量网络是否拥塞的参数
- 缺乏缓冲区造成的丢包率；
- 平均队列长度；
- 超时重传的包的数目；
- 平均包延迟；
- 包延迟变化（ Jitter）。
反馈方法
- 向负载发生源发送一个告警包；
- 包结构中保留一个位或域用来表示发生拥塞，一旦发生 拥塞，路由器将所有的输出包置位，向邻居告警；
- 主机或路由器主动地、周期性地发送探报（ probe）,查询是否发生拥塞。
7.3 拥塞控制算法（ 5）
7.3.2 拥塞控制算法
拥塞预防策略
- 开环控制
- 影响拥塞的网络设计策略
7.3 拥塞控制算法（ 6）
流量整形（ Traffic Shaping）
- 开环控制
- 基本思想
造成拥塞的主要原因是网络流量通常是突发性的；
强迫包以一种可预测的速率发送；
在 ATM网中广泛使用。
- 漏桶算法（ The Leaky Bucket Algorithm）
Fig,5-24
将用户发出的不平滑的数据包流转变成网络中平滑 的数据包流；
可用于固定包长的协议，如 ATM；也可用于可变包长的协议，如 IP，使用字节计数；
例,Fig,5-25(a)(b)；
无论负载突发性如何，漏桶算法强迫输出按平均速率进行，不灵活。
7.3 拥塞控制算法（ 7）
- 令牌桶算法（ The Token Bucket Algorithm）
漏桶算法不够灵活，因此加入令牌机制；
基本思想：漏桶存放令牌，每?T秒产生一个 令牌，
令牌累积到超过漏桶上界时就不再增加。包传输之前必须获得一个令牌，传输之后删除该令牌；
Fig,5-26
- 漏桶算法与令牌桶算法的区别
流量整形策略不同：漏桶算法不允许空闲主机积累发送权，以便以后发送大的突发数据；令牌桶算法允许，最大为桶的大小。
漏桶中存放的是数据包，桶满了丢弃数据包；令牌桶中存放的是令牌，桶满了丢弃令牌，不丢弃数据包。
7.3 拥塞控制算法（ 8）
流说明（ Flow Specification）
- 一个数据流的发送方、接收方和通信子网三方认可的、
描述发送数据流的模式和希望得到的服务质量的数据结构，称为 流说明 。
- 对发送方的流说明，子网和接收方可以做出三种答复：
同意、拒绝、其它建议。
7.3 拥塞控制算法（ 9）
虚电路子网中的拥塞控制
- 许可控制（ admission control），基本思想：一旦发生拥塞，在问题解决之前，不允许建立新的虚电路；
- 另一种方法是发生拥塞后可以建立新的虚电路，但要绕开发生拥塞的地区；
- 资源预留：建立虚电路时，主机与子网达成协议，子网根据协议在虚电路上为此连接预留资源。（ RSVP）
7.3 拥塞控制算法（ 10）
抑制包（ Choke Packets）
- 基本思想
路由器监控输出线路及其它资源的利用情况，超过某个阈值，
则此资源进入警戒状态；
每个新包到来，检查它的输出线路是否处于警戒状态；
若是，则向源主机发送抑制包，包中指出发生拥塞的目的地址
。同时将原包打上标记（为了以后不再产生抑制包），正常转发；
源主机收到抑制包后，按一定比例减少发向特定目的地的流量
，并在固定时间间隔内忽略指示同一目的地的抑制包。然后开始监听，若此线路仍然拥塞，则主机在固定时间内减轻负载、
忽略抑制包；若在监听周期内没有收到抑制包，则增加负载；
通常采用的流量增减策略是：减少时，按一定比例减少，保证快速解除拥塞；增加时，以常量增加，防止很快导致拥塞。
7.3 拥塞控制算法（ 11）
加权公平队列（ Weighted Fair Queueing）
- 公平队列（ Fair Queueing）算法
路由器的每个输出线路有多个队列；
路由器循环扫描各个队列，发送队头的包；
所有主机具有相同优先级；
一些 ATM交换机、路由器使用这种算法；
一种改进：对于变长包，由逐包轮讯改为逐字节轮讯
Fig,5-29
- 加权公平队列算法
给不同主机以不同的优先级；
优先级高的主机在一个轮讯周期内获得更多的时间片。
7.3 拥塞控制算法（ 12）
逐跳抑制包（ Hop-by-Hop Choke Packets）
- 在高速、长距离的网络中，由于源主机响应太慢，抑制包算法对拥塞控制的效果并不好，可采用逐跳抑制包算法；
Fig,5-30(a)
- 基本思想
抑制包对它经过的每个路由器都起作用；
能够迅速缓解发生拥塞处的拥塞；
上游路由器要求有更多的缓冲区；
Fig,5-30(b)
7.3 拥塞控制算法（ 13）
负载丢弃（ Load Shedding）
- 上述算法都不能消除拥塞时，路由器只得将包丢弃；
- 针对不同服务，可采取不同丢弃策略
文件传输，优先丢弃新包,wine策略；
多媒体服务，优先丢弃旧包,milk策略；
- 早期丢弃包，会减少拥塞发生的概率，提高网络性能。
7.4 网络互联（ 1）
互联网（ internet）：两个或多个网络构成互联网。
多种不同网络（协议）存在的原因
- 历史原因：不同公司的网络产品大量使用；
- 价格原因：网络产品价格低，更多的人有权决定使用何种网络；
- 技术原因：不同网络采用不同技术、不同硬件、不同协议。
7.4 网络互联（ 2）
网络互连设备
- 中继器（ repeater）
物理层设备，在电缆段之间拷贝比特；
对弱信号进行放大或再生，以便延长传输距离。
- 网桥（ bridge）
数据链路层设备，在局域网之间存储转发帧；
网桥可以改变帧格式。
- 多协议路由器（ multiprotocol router）
网络层设备，在网络之间存储转发包；
必要时，做网络层协议转换。
- 传输网关（ transport gateway）
传输层设备，在传输层转发字节流。
- 应用网关（ application gateway）
应用层设备，在应用层实现互连；
half-gateway（为了满足不同国家、组织的管理需要）
Fig,5-34
7.4 网络互联（ 3）
网络之间的区别
7.4 网络互联（ 4）
7.4.1 级联虚电路（ Concatenated Virtual Circuits）
工作过程
- 级联虚电路工作过程与虚电路子网工作过程相似；
- 建立连接
当目的主机不在子网内时，则在子网内找一个离目的网络 最近的路由器，与之建立一条虚电路；
该路由器与外部网关建立虚电路；
该网关与下一个子网中的一个路由器建立虚电路；
重复上述操作，直到到达目的主机。
- 传输数据
相同连接的包沿同一虚电路按序号传输；
网关根据需要转换包格式和虚电路号。
- 拆除连接
7.4 网络互联（ 5）
7.4.2 无连接网络互连（ Connectionless Internetworking）
工作过程
- 无连接网络互连的工作过程与数据报子网的工作过程相似；
- 每个包单独路由，提高网络利用率，但不能保证包按顺序到达；
- 根据需要，连接不同子网的多协议路由器做协议转换，包括包格式转换和地址转换等。
7.4 网络互联（ 6）
级联虚电路与无连接网络互连的比较
- 级联虚电路的优点
路由器预留缓冲区等资源，保证服务质量；
包按序号传输；
短包头。
- 级联虚电路的缺点
路由器需要大量内存，存储虚电路信息；
一旦发生拥塞，没有其它路由；
健壮性差；
如果网络中有一个不可靠的数据报子网，级连虚电路很难实现。
7.4 网络互联（ 7）
- 无连接网络互连的优点
能够容忍拥塞，并能适应拥塞；
健壮性好；
可用于多种网络互连。
- 无连接网络互连的缺点
长包头；
包不能保证按序号到达；
不能保证服务质量。
7.4 网络互联（ 8）
7.4.3 隧道技术（ Tunneling）
隧道技术
- 源和目的主机所在网络类型相同，连接它们的是一个不同类型的网络，这种情况下可以采用隧道技术。
7.4 网络互联（ 9）
工作过程（以 Fig,5-38为例）
- 主机 1发送一个包，目的 IP地址 = 主机 2-IP，将包封装到局域网帧中，帧目的地址 = 路由器 1-MAC；
- 局域网传输；
- 路由器 1剥掉局域网帧头、帧尾，将得到的 IP包封装到广域网 网络层包 中，包目的地址 = 路由器 2地址；
- 广域网传输；
- 路由器 2剥掉广域网包头，将得到的 IP包封装到局域网帧中，包目的 IP地址 = 主机 2-IP，帧目的地址 = 主机 2-
MAC地址；
- 局域网传输；
- 主机 2接收。
7.4 网络互联（ 10）
7.4.4 互联网路由（ Internetwork Routing）
工作过程
- 互联网络的路由与单独子网的路由过程相似，只是复杂性增加；
- 两级路由算法
内部网关协议（ IGP,Interior Gateway Protocol）
RIP,OSPF
外部网关协议（ EGP,Exterior Gateway Protocol）
BGP
自治系统 AS（ Autonomous System）
7.4 网络互联（ 11）
7.4.5 分段（ Fragmentation）
每种网络都对最大包长有限制，有以下原因
- 硬件，例如 TDM 的时槽限制；
- 操作系统；
- 协议，例如包长度域的比特个数；
- 与标准的兼容性；
- 希望减少传输出错的概率；
- 希望避免一个包占用信道时间过长。
大包经过小包网络时，网关要将大包分成若干段
（ fragment），每段作为独立的包传输。
7.4 网络互联（ 12）
段重组策略
- 分段重组过程对其它网络透明
网关将大包分段后，每段都要经过同一出口网关，
并在那里重组；
Fig,5-41(a)
例,ATM网络；
带来的问题
出口网关需要知道何时所有分组都到齐；
所有分组必须从同一出口网关离开；
大包经过一系列小包网络时，需要反复地分段重组，
开销大。
7.4 网络互联（ 11）
- 分段重组过程对其它网络不透明
中间网关不做重组，而由目的主机做；
Fig,5-41(b)
带来的问题
对主机要求高，能够重组；
每个段都要有一个包头，网络开销增大；
7.4 网络互联（ 12）
标记段
- 树型标记法
例，包 0分成三段，分别标记为 0.0,0.1,0.2，段 0.0构成的包被分成三段，分别标记为 0.0.0,0.0.1,0.0.2；
存在的问题
段标记域要足够长
分段长度前后要一致
- 偏移量法
定义一个基本段长度，使得基本段能够通过所有网络；
包分段时，除最后一个段小于等于基本段长度外，所有段长度都等于基本段长度；
一个包可以包括几个段，包头中包括；原始包序号，包 中第一个基本段的偏移量，最后段指示位；
Fig,5-42
7.4 网络互联（ 13）
7.4.6 防火墙（ Firewalls）
什么情况下使用防火墙？
- 为防止网络中的 信息泄露出去或不好的信息渗透进来，
在网络边缘设置防火墙；
- Fig,5-43
防火墙分类：包过滤，应用网关（代理）、电路级网关（状态检测器）、检查放火墙（三种结合
）
防火墙的一种常用配置
- 两个路由器，根据某种规则表，进行包过滤；
- 一个应用网关，审查应用层信息。
小结
互联网（ internet）：两个或多个网络构成互联网
网络互连设备：中继器、网桥、路由器、传输网关、应用网关
虚电路网络互联
数据报网络互联
隧道技术
分段和重组
防火墙
7.5 INTERNET网络层协议（ 1）
在网络层,Internet可以看成是自治系统的集合，
是由网络组成的网络。
网络之间互连的纽带是 IP（ Internet Protocol）协议。
网际协议 IP 是 TCP/IP 体系中两个最主要的协议之一 。与 IP 协议配套使用的还有四个协议：
地址解析协议 ARP
(Address Resolution Protocol)
逆地址解析协议 RARP
(Reverse Address Resolution Protocol)
因特网控制报文协议 ICMP
(Internet Control Message Protocol)
因特网组管理协议 IGMP
(Internet Group Management Protocol)
网际协议 IP 及其配套协议各种应用层协议网络接口层
(TELNET,FTP,SMTP 等 )
物理硬件运输层 TCP,UDP
应用层
ICMP
IP
RARP ARP
与各种网络接口网际层
IGMP
7.5 INTERNET网络层协议（ 2）
7.5.1 IP协议
IP头格式
- IP头包括 20个字节的固定部分和变长（最长 40字节）的可选部分，从左到右传输；
- 版本域（ version）；
- IHL,IP包头长度，最小为 5，最大为 15，单位为 32-bit word；
7.5 INTERNET网络层协议（ 3）
- 服务类型域（ Type of Service）
3个优先级位；
3个标志位,D（ Delay）,T（ Throughput）、
R（ Reliability）；
2个保留位；
目前，很多路由器都忽略服务类型域。
- 总长度域（ Total length：包括头和数据。 65535字节
- 标识域（ Identification）：同一分组的段相同
- DF,Don’t Fragment；
所有机器必须能够接收小于等于 576字节的段。
- MF,More Fragments
除最后一个段外的所有段都要置 MF位。
7.5 INTERNET网络层协议（ 4）
- 段偏移量（ Fragment offset）
除最后一个段外的所有段的长度必须是 8字节（基本段长）的倍数。
ID
=x
offset
=0
fragflag
=0
length
=4000
ID
=x
offset
=0
fragflag
=1
length
=1500
ID
=x
offset
=1480
fragflag
=1
length
=1500
ID
=x
offset
=2960
fragflag
=0
length
=1040
One large datagram becomes
several smaller datagrams
7.5 INTERNET网络层协议（ 5）
- 生存期（ Time to live）
实际实现中,IP包每经过一个路由器 TTL减 1，为 0则丢弃，并给源主机发送一个告警包。
- 协议域（ Protocol）：上层为哪种传输协议,TCP、
UDP…
- 头校验和（ Header checksum）
只对 IP包头做校验；
算法：每 16位求反，循环相加（进位加在末尾），
和再求反。
- 源地址（ Source address）和目的地址（ Destination
address）
7.5 INTERNET网络层协议（ 6）
- 选项（ Options）
变长，长度为 4字节的倍数，不够则填充，最长为 40
字节；
IP 地址的编址方法
分类的 IP 地址 。 这是最基本的编址方法,在 1981
年就通过了相应的标准协议 。
子网的划分 。 这是对最基本的编址方法的改进,其标准 [RFC 950]在 1985 年通过 。
构成超网 。 这是比较新的无分类编址方法 。 1993 年提出后很快就得到推广应用 。
分类 IP 地址
每一类地址都由两个固定长度的字段组成,其中一个字段是网络号 net-id,它标志主机 （ 或路由器 ） 所连接到的网络,而另一个字段则是主机号 host-id,它标志该主机
（ 或路由器 ） 。
两级的 IP 地址可以记为：
IP 地址,:= { <网络号 >,<主机号 >} (6-1)
分组转发算法
(1) 从数据报的首部提取目的站的 IP 地址 D,得出目的网络地址为 N。
(2) 若网络 N 与此路由器直接相连,则 直接 将数据报交付给目的站 D；否则是 间接 交付,执行 (3)。
(3) 若路由表中有目的地址为 D 的特定主机路由,则将数据报传送给路由表中所指明的下一跳路由器；否则,执行 (4)。
(4) 若路由表中有到达网络 N 的路由,则将数据报传送给路由表指明的下一跳路由器；否则,执行 (5)。
(5) 若路由表中有一个默认路由,则将数据报传送给路由表中所指明的默认路由器；否则,执行 (6)。
(6) 报告转发分组出错 。
IP 地址的一些重要特点
(1) IP 地址是一种分等级的地址结构 。 分两个等级的好处是
：
第一,IP地址管理机构在分配 IP地址时只分配网络号,
而剩下的主机号则由得到该网络号的单位自行分配 。 这样就方便了 IP地址的管理 。
第二,路由器仅根据目的主机所连接的网络号来转发分组 （ 而不考虑目的主机号 ）,这样就可以使路由表中的项目数大幅度减少,从而减小了路由表所占的存储空间
。
IP 地址的一些重要特点
(2) 实际上 IP 地址是标志一个主机 （ 或路由器 ） 和一条链路的接口 。
当一个主机同时连接到两个网络上时,该主机就必须同时具有两个相应的 IP 地址,其网络号 net-id 必须是不同的 。 这种主机称为多接口主机 (multihomed host)。
由于一个路由器至少应当连接到两个网络 （ 这样它才能将 IP 数据报从一个网络转发到另一个网络 ）,因此一个路由器至少应当有两个不同的 IP 地址 。
IP 地址的一些重要特点
(3) 用转发器或网桥连接起来的若干个局域网仍为一个网络
,因此这些局域网都具有同样的网络号 net-id。
(4) 所有分配到网络号 net-id 的网络,范围很小的局域网,
还是可能覆盖很大地理范围的广域网,都是平等的 。
互联网中的 IP 地址
B
222.1.1.
222.1.1.1 222.1.1.2 222.1.1.3
222.1.1.4R
1
222.1.2.5 222.1.2.2
222.1.2.1
222.1.2.3222.1.2.4
222.1.2.
222.1.6.1222.1.5.1
222.1.5.2 222.1.6.2
222.1.4.1222.1.4.2
222.1.3.3
222.1.3.2
222.1.3.1 R3 R2
222.1.3.
LAN3
N3
N2
222.1.4.
222.1.5.
222.1.6.
N1
LAN2
LAN1
互联网在同一个局域网上的主机或路由器的 IP 地址中的网络号必须是一样的。图中的网络号就是 IP 地址中的 net-id
2,常用的三种类别的 IP 地址
IP 地址的使用范围网络 最大 第一个 最后一个 每个网络类别 网络数 可用的 可用的 中最大的网络号 网络号 主机数
A 126 (27 – 2) 1 126 16,777,214
B 16,384 (214) 128.0 191.255 65,534
C 2,097,152 (221) 192.0.0 223.255.255 254
划分子网和构造超网
1,从两级 IP 地址到三级 IP 地址
在 ARPANET 的早期,IP 地址的设计确实不够合理 。
- IP地址空间的利用率有时很低 。
- 给每一个物理网络分配一个网络号会使路由表变得太大因而使网络性能变坏 。
- 两级的 IP 地址不够灵活 。
划分子网纯属一个 单位内部的事情 。 单位对外仍然表现为没有划分子网的网络 。
从主机号 借用 若干个比特作为 子网号 subnet-id,而主机号 host-id 也就相应减少了若干个比特 。
IP地址,:= {<网络号 >,<子网号 >,<主机号 >}
凡是从其他网络发送给本单位某个主机的 IP 数据报,仍然是根据 IP 数据报的 目的网络号 net-id,先找到连接在 本单位网络上的路由器 。
然后 此路由器 在收到 IP 数据报后,再按目的网络号 net-id 和子网号
subnet-id 找到目的子网 。
最后就将 IP 数据报直接交付给目的主机 。
划分子网的基本思路
145.13.3.10
145.13.3.11 145.13.3.101 145.13.7.34
145.13.7.35
145.13.7.56
145.13.21.23
145.13.21.9
145.13.21.8所有到网络145.13.0.0的分组均到达此路由器我的网络地址是 145.13.0.0
R1
R3
R2
网络
145.13.0.0
一个未划分子网的 B 类网络 145.13.0.0
划分为三个子网后对外仍是一个网络
145.13.3.10145.13.3.11
145.13.3.101 145.13.7.34
145.13.7.35
145.13.7.56
145.13.21.23
145.13.21.9
145.13.21.8
…
…
…
子网 145.13.21.0
子网 145.13.3.0
子网
145.13.7.0
所有到达网络
145.13.0.0
的分组均到达此路由器网络
145.13.0.0
R1R
3
R2
IP 地址的各字段和子网掩码网络号 net-id 主机号 host-id两级 IP 地址网络号
net-id host-id三级 IP 地址主机号
subnet-id
子网号子网掩码因特网部分 本地部分因特网部分 本地部分划分子网时的网络地址
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
net-id subnet-id host-id 为全 0
在划分子网的情况下路由器转发分组的算法
(1) 从收到的分组的首部提取目的 IP 地址 D。
(2) 先用各网络的子网掩码和 D 逐比特相“与”，看是否和相应的网络地址匹配。若匹配，则将分组直接交付。
否则就是间接交付，执行 (3)。
(3) 若路由表中有目的地址为 D 的特定主机路由，则将分组传送给指明的下一跳路由器；否则，执行 (4)。
(4) 对路由表中的每一行的子网掩码和 D 逐比特相
“与”，
若其结果与该行的目的网络地址匹配，则将分组传送给该行指明的下一跳路由器；否则，执行 (5)。
(5) 若路由表中有一个默认路由，则将分组传送给路由表中所指明的默认路由器；否则，执行 (6)。
(6) 报告转发分组出错。
因此 H1 必须把分组传送到路由器 R1
然后逐项查找路由表
128.30.33.1 0
目的网络地址 子网掩码 下一跳
128.30.33.0
128.30.33.128
128.30.36.0
255.255.255.128
255.255.255.128
255.255.255.0
接口 0
接口 1
R2
R1 的路由表（未给出默认路由器）
128.30.33.13
H1 子网 1：网络地址 128.30.33.0
子网掩码 255.255.255.128
128.30.33.130
R1
1
R2
子网 2：网络地址 128.30.33.128
子网掩码 255.255.255.128
H2 128.30.33.138
0
1
128.30.33.129
H3
128.30.36.2
子网 3：网络地址 128.30.36.0
子网掩码 255.255.255.0128.30.36.12
路由器 R1 收到分组后就用路由表中第 1 个项目的子网掩码和 128.30.33.138 逐比特 AND 操作
128.30.33.1 0
目的网络地址 子网掩码 下一跳
128.30.33.0
128.30.33.128
128.30.36.0
255.255.255.128
255.255.255.128
255.255.255.0
接口 0
接口 1
R2
R1 的路由表（未给出默认路由器）
128.30.33.13
H1 子网 1：网络地址 128.30.33.0
子网掩码 255.255.255.128
128.30.33.130
R1
1
R2
子网 2：网络地址 128.30.33.128
子网掩码 255.255.255.128
H2 128.30.33.138
0
1
128.30.33.129
H3
128.30.36.2
子网 3：网络地址 128.30.36.0
子网掩码 255.255.255.0128.30.36.12
255.255.255.128 AND 128.30.33.138 = 128.30.33.128
不匹配 !
（因为 128.30.33.128 与路由表中的 128.30.33.0 不一致）
R1收到的分组的目的 IP 地址,128.30.33.138
不一致路由器 R1 再用路由表中第 2 个项目的子网掩码和 128.30.33.138 逐比特 AND 操作
128.30.33.1 0
目的网络地址 子网掩码 下一跳
128.30.33.0
128.30.33.128
128.30.36.0
255.255.255.128
255.255.255.128
255.255.255.0
接口 0
接口 1
R2
R1 的路由表（未给出默认路由器）
128.30.33.13
H1 子网 1：网络地址 128.30.33.0
子网掩码 255.255.255.128
128.30.33.130
R1
1
R2
子网 2：网络地址 128.30.33.128
子网掩码 255.255.255.128
H2 128.30.33.138
0
1
128.30.33.129
H3
128.30.36.2
子网 3：网络地址 128.30.36.0
子网掩码 255.255.255.0128.30.36.12
255.255.255.128 AND 128.30.33.138 = 128.30.33.128
匹配 !
这表明子网 2 就是收到的分组所要寻找的目的网络
R1收到的分组的目的 IP 地址,128.30.33.138
一致 !
无分类的两级编址的记法是：
IP地址,:= {<网络前缀 >,<主机号 >}
CIDR 还使用,斜线记法,(slash notation),它又称为
CIDR记法,即在 IP地址后面加上一个斜线,/”,然后写上网络前缀所占的比特数 （ 这个数值对应于三级编址中子网掩码中比特 1 的个数 ） 。
CIDR 将网络前缀都相同的连续的 IP 地址组成,CIDR地址块,。
无分类 的两级编址
CIDR 地址块
128.14.32.0/20 表示的地址块共有 212 个地址 （ 因为 斜线后面的 20 是网络前缀的比特数,所以主机号的比特数是 12）
。
这个地址块的起始地址是 128.14.32.0。
在不需要指出地址块的起始地址时,也可将这样的地址块简称为,/20 地址块,。
128.14.32.0/20地址块的最小地址,128.14.32.0
128.14.32.0/20地址块的最大地址,128.14.32.255
全 0 和全 1 的主机号地址一般不使用 。
最长前缀匹配
使用 CIDR 时,路由表中的每个项目由,网络前缀,
和,下一跳地址,组成 。 在查找路由表时可能会得到不止一个匹配结果 。
应当从匹配结果中选择具有最长网络前缀的路由,最长前缀匹配 (longest-prefix matching)。
网络前缀越长,其地址块就越小,因而路由就越具体
。
最长前缀匹配又称为 最长匹配 或 最佳匹配 。
7.5 INTERNET网络层协议（ 6）
7.5.2 Internet控制协议
Internet控制报文协议 ICMP（ The Internet Control
Message Protocol）
- 主要用来报告出错和测试；
- 报文类型
- ICMP报文封装在 IP包中。
7.5 INTERNET网络层协议（ 7）
地址解析协议 ARP（ The Address Resolution Protocol）
- 解决网络层地址（ IP地址）与数据链路层地址（ MAC地址）的映射问题；
- Fig,5-51
- 工作过程
建立一个 ARP表，表中存放（ IP地址,MAC地址）对；
若目的主机在同一子网内，用目的 IP地址在 ARP表中查找
，否则用缺省网关的 IP地址在 ARP表中查找。若未找到，
则发送广播包，目的主机收到后给出应答,ARP表增加一项；
每个主机启动时，广播它的（ IP地址,MAC地址）映射；
ARP表中的表项有生存期，超时则删除。
ARP是在同一个局域网主机或路由器 IP地址与 MAC地址映射
7.5 INTERNET网络层协议（ 8）
反向地址解析协议 RARP（ The Reverse Address
Resolution Protocol）
- 解决数据链路层地址（ MAC地址）与网络层地址（ IP地址）的映射问题；机器启动后发送带 MAC地址的广播帧
，询问 RARP服务器他的 IP地址。 要设定 RARP服务器
。
- 主要用于无盘工作站启动；
- 缺点：由于路由器不转发广播帧,RARP服务器必须与无盘工作站在同一子网内。一种替代协议 BOOTP（使用
UDP）。
因特网控制报文协议 ICMP：允许主机或路由器报告差错情况和提供异常情况的报告。
7.5 INTERNET网络层协议（ 12）
7.5.3 内部网关路由协议,OSPF
开放最短路径优先 OSPF（ Open Shortest Path
First）
- 开放，公开发表；
- 支持多种距离衡量尺度，例如，物理距离、延迟等；
- 动态算法；
- 支持基于服务类型的路由；
- 负载平衡；
- 支持分层系统；
- 适量的安全措施；
- 支持隧道技术。
7.5 INTERNET网络层协议（ 13）
构造有向拓扑图
- 根据实际的网络、路由器和线路构造有向图；
- 每个弧赋一个开销值；
- 两个路由器之间的线路用一对弧来表示，弧权可以不同；
- 多路访问（ multiaccess）网络，网络用一个结点表示，每个路由器用一个结点表示，网络结点与路由器结点的弧权为 0；
- Fig,5-52
7.5 INTERNET网络层协议（ 14）
分层路由
- 自治系统 AS可以划分区域（ areas）；
- 每个 AS有一个主干（ backbone）区域，称为区域 0，所有区域与主干区域相连；
- Fig,5-53
- 一般情况下，有三种路由
区域内
区域间
从源路由器到主干区域；
穿越主干区域到达目的区域；
到达目的路由器。
自治系统间
7.5 INTERNET网络层协议（ 15）
- 四类路由器，允许重叠
完全在一个区域内的内部路由器；
连接多个区域的区域边界路由器；
主干路由器；
自治系统边界路由器。
信息类型
7.5 INTERNET网络层协议（ 16）
7.5.4 外部网关路由协议,BGP
Why different Intra- and Inter-AS routing?
- Policy
Inter-AS,admin wants control over how its traffic
routed,who routes through its net,
Intra-AS,single admin,so no policy decisions
needed
- Scale
hierarchical routing saves table size,reduced
update traffic
- Performance
Intra-AS,can focus on performance
Inter-AS,policy may dominate over performance
7.5 INTERNET网络层协议（ 17）
边界网关协议 BGP（ Border Gateway Protocol）
- 通过 TCP连接传送路由信息；每个 AS设定一个 BGP代言人，主干网也有 BGP代言人，由 ASBGP代言人向主干
BGP代言人发送信息。
- 采用路径向量（ path vector）算法，路由信息中记录路径的轨迹
similar to Distance Vector protocol
each Border Gateway broadcast to neighbors
(peers) entire path (I.e,sequence of ASs) to
destination
E.g.,Gateway X may send its path to dest,Z:
Path (X,Z) = X,Y1,Y2,Y3,…,Z
Fig,5-55
7.5 INTERNET网络层协议（ 18）
Suppose,gateway X send its path to peer gateway
W
W may or may not select path offered by X
cost,policy (don’t route via competitors AS),
loop prevention reasons.
If W selects path advertised by X,then:
Path (W,Z) = w,Path (X,Z)
Note,X can control incoming traffic by
controling it route advertisements to peers:
e.g.,don’t want to route traffic to Z -> don’t
advertise any routes to Z
7.5 INTERNET网络层协议（ 19）
- BGP messages:
OPEN,opens TCP connection to peer and
authenticates sender
UPDATE,advertises new path (or withdraws old)
KEEPALIVE keeps connection alive in absence of
UPDATES; also ACKs OPEN request
NOTIFICATION,reports errors in previous msg;
also used to close connection
7.5 INTERNET网络层协议（ 20）
7.5.5 无类域间路由 CIDR
（ Classless InterDomain Routing）
CIDR的提出
- Internet指数增长,IP地址即将用完，
IP is rapidly becoming a victim of its own popularity.
- 基于分类的 IP地址空间的组织浪费了大量的地址
The real villain is the class B network.
CIDR
- RFC 1519
- 基本思想：将剩余的 C类地址分成大小可变的地址空间；
- 例如，需要 2000个地址，则分配一个 2048个地址（ 8个 C
类地址）的连续地址块，而不是一个 B类地址；
7.5 INTERNET网络层协议（ 15）
- RFC 1519 改变了过去 C类地址的分配规则，将世界分成
4个区，每个区分配一块连续的 C类地址空间；
欧洲,194.0.0.0 ~ 195.255.255.255
北美,198.0.0.0 ~ 199.255.255.255
中、南美,200.0.0.0 ~ 201.255.255.255
亚太,202.0.0.0 ~ 203.255.255.255
- 路由表中增加一个 32位的掩码（ mask）域
- 最长匹配原则：路由查找时，若多个路由表项匹配成功
，选择掩码长（ 1比特数多）的路由表项；
Figure
- CIDR思想可用于所有 IP地址，没有 A,B,C类之分。
- address format,a.b.c.d/x,where x is # bits in network
portion of address
7.5 INTERNET网络层协议（ 16）
例
- Cambridge University 需要 2048个地址,194.24.0.0 ~
194.24.7.255，掩码 255.255.248.0；
Oxford University 需要 4096个地址,194.24.16.0 ~
194.24.31.255，掩码 255.255.240.0；
Edinburgh University 需要 1024个地址,194.24.8.0 ~
194.24.11.255，掩码 255.255.252.0；
- 路由表内容地址 掩码
11000010 00011000 00000000 00000000 11111111
11111111 11111000 00000000
11000010 00011000 00010000 00000000 11111111
11111111 11110000 00000000
11000010 00011000 00001000 00000000 11111111
11111111 11111100 00000000
7.5 INTERNET网络层协议（ 17）
- 一个目的地址为 194.24.17.4的包到达路由器，路由表查找过程如下：
194.24.17.4的二进制表示为
11000010 00011000 00010001 00000100
该地址与第一项 Cambridge的掩码做 AND 操作，得到
11000010 00011000 00010000 00000000
与 Cambridge的地址不同，匹配不成功；
该地址与下一项 Oxford的掩码做 AND 操作，得到
11000010 00011000 00010000 00000000
与 Oxford的地址相同，匹配成功。
继续匹配，最后选择前缀最长的路由表项
7.5 INTERNET网络层协议（ 18）
7.5.6 IPv6
IPv6的提出
- CIDR仅仅是一种临时补救措施，不能从根本上解决 IP地址空间匮乏的问题；
- 移动电话、家电上网等需要大量的 IP地址；
- 1990年,IETF开始 IPv6的工作，收到 21个建议；
- 1992年,7个建议被讨论；
- 1993年,3个比较好的建议发表在 IEEE Network上，进一步讨论、修改、结合后，形成 IPv6；
- IPv6与 IPv4不兼容，但与其它 Internet协议兼容，如 TCP、
UDP,OSPF,BGP,DNS等，但实际上还是需要开发另外一套协议栈。
7.5 INTERNET网络层协议（ 19）
IPv6的目标
- 即使在不能有效分配地址空间的情况下，也能支持数十亿的主机；
- 减少路由表的大小；
- 简化协议，使得路由器能够更快的处理包；
- 提供比 IPv4更好的安全性；
- 更多的关注服务类型，特别是实时数据；
- 支持 Multicast；
- 支持移动功能；
- 协议具有很好的可扩展性；
- 增强安全性
- 在一段时间内，允许 IPv4与 IPv6共存。
7.5 INTERNET网络层协议（ 20）
与 IPv4相比,IPv6的主要变化
- 地址变长，由 32位变成 128位；
- IP头简化，由 13个域减少为 7个域，提高路由器处理速度
由于 IPv6包头定长，取消 IHL域；
Protocol域取消，用 Next header域表示；
取消与分段有关的域,IPv6采用不同的分段方法：所有主机和路由器必须支持 576字节的包，当主机发送一个大包时，路由器不做分段，而是给主机发一个错误信息，由主机做分段；
取消 Checksum域。
- 更好的支持选项功能；
- 安全性提高；
- 更注重服务类型。
7.5 INTERNET网络层协议（ 21）
IPv6包头
- Fig,5-56
- Version，值为 6；
- Priority，用来区分源端可以流控或不能流控的包，值 0 ~ 7表示发生拥塞时源端可以降速，值 8 ~ 15表示发送速率固定的实时负载，值越小优先级越低；
- Flow label,用来允许源和目的建立一条具有特殊属性和需求的伪连接；
- Payload length，用来指示 IP包中 40字节包头后面部分的长度
，与 IPv4的 total length域不同；
- Next header，指示扩展包头，若是最后一个包头，则指示传输协议类型（ TCP/UDP）；
- Hop limit,IP包的生存时间；
- Source address,destination address,16字节定长地址
7.5 INTERNET网络层协议（ 22）
IPv6地址表示
- 16字节地址表示成用冒号（,）隔开的 8组，每组 4个 16进制位，例如，
8000:0000:0000:0000:0123:4567:89AB:CDEF
- 由于有很多,0”，有三种优化表示
打头的,0”可以省略,0123可以写成 123；
一组或多组 16个,0”可以被一对冒号替代，但是一对冒号只能出现一次。上面的地址可以表示成
8000::123,4567:89AB:CDEF
IPv4地址可以写成一对冒号和用,.”分隔的十进制数
，例如
::192.31.20.46
7.5 INTERNET网络层协议（ 23）
扩展包头
- 目前定义了六种类型的扩展包头
- hop-by-hop header，用来指示路径上所有路由器必须检查的信息；
- routing header，列出路径上必须要经过的路由器，
- fragmentation header，与 IPv4相似，扩展头中包括 IP包标识号
、分段号和判断是否还有分段的位，只有源主机可以分段；
7.5 INTERNET网络层协议（ 24）
Transition From IPv4 To IPv6
- Not all routers can be upgraded simultaneous
no,flag days” (not like Y2K):逐步完成
How will the network operate with mixed IPv4 and
IPv6 routers? 地址的兼容
- Two proposed approaches:
Dual Stack,some routers with dual stack (v6,v4)
can,translate” between formats
Tunneling,IPv6 carried as payload in IPv4
datagram among IPv4 routers
Header translation
7.5 INTERNET网络层协议（ 25）
Dual Stack Approach
7.5 INTERNET网络层协议（ 26）
Tunneling
IPv6 inside IPv4 where needed
小结
IPv4协议
- 分段与重组
- IPv4地址
ICMP协议
- ICMP报文封装在 IP包中
ARP协议
- ARP协议工作过程
RARP协议
- RARP与 BOOTP的区别
RIP
- 内部网关协议
- 距离向量算法
- 基于 UDP
OSPF
- 内部网关协议
- 链路状态算法
- 分层思想
- 四种类型路由器
BGP
- 外部网关协议
- 路径向量算法
- 基于 TCP
CIDR
- CIDR的思想
- IP地址分配和掩码配置
- 最长匹配原则
IPv6
- IPv6与 IPv4的主要区别
- IPv6地址
- 双栈模式与隧道模式移动 IP
移动 IP解决的问题
（ 1）移动主机在改变链路层接入点后，不改变 IP
仍能与其他主机通信
（ 2）其他主机不改变协议
（ 3）链路误码率较高、减少公耗等
移动 IP解决的特殊问题
（ 1） 漫游
（ 2）位置登记
（ 3）鉴权
移动 IP的传输技术
（ 1）共享无线信道
（ 2）扩频技术
（ 3）红外发射移动 IP的路由
需要解决的问题
- 为了能够将数据包转发给移动主机，网络必须首先要找到移动的主机。
网络结构示意图
7.2 路由算法（ 20）
一些基本概念
- 移动用户（ mobile users）：包括位置发生变化，通过固定方式或移动方式与网络连接的两类用户；
- 家乡位置（ home location）：所有用户都有一个永久的家乡位置，用一个地址来标识；
- 外部代理（ foreign agent）：每个区域（一个 LAN或一个
wireless cell）有一个或多个外部代理，它们记录正在访问该区域的移动用户；
- 家乡代理（ home agent）,每个区域有一个家乡代理，
负责记录家乡在该区域，但是目前正在访问其它区域的用户。
7.2 路由算法（ 21）
移动用户进入一个新区域时，必须首先向外部代理注册
- 外部代理定期广播声明自己的存在和地址的包，新到达的移动主机接收该信息；若移动用户未能收到该信息，
则移动主机广播包，询问外部代理的地址；
- 移动主机向外部代理注册，告知其家乡地址、目前的数据链路层地址和一些安全信息；
- 外部代理与移动主机的家乡代理联系，告知移动主机的目前位置、自己的网络地址和一些安全信息；
- 家乡代理检查安全信息，通过，则给外部代理确认；
- 外部代理收到确认后，在登记表中加入一项，并通知移动主机注册成功。
7.2 路由算法（ 22）
移动用户的路由转发过程
- 当一个包发给移动用户时，首先被转发到用户的家乡局域网；
- 该包到达用户的家乡局域网后，被家乡代理接收，家乡代理查询移动用户的新位置和与其对应的外部代理的地址；
- 家乡代理采用隧道技术，将收到的包作为净荷封装到一个新包中，发给外部代理；
- 家乡代理告诉发送方，发给移动用户的后续包作为净荷封装成包直接发给外部代理；
- 外部代理收到包后，将净荷作为数据链路帧发给移动用户；
- Fig,5-19
IP的传输 1 -IP over ATM
ATM引入 INTERNET的优势
（ 1）提高网络性能：速率高 622M,2.5G
（ 2）降低设备费用,10G的 ATM端口每秒可处理
2000万个 IP包，价格与每秒 200万 IP包处理能力的路由器相当
（ 3）服务质量保证
重叠模型
IP协议在 ATM网络上运行,ATM作为 IP层的低层传输链路，各自定义自己的地址和路由协议，需要服务器实现两种地址的映射（如 ARP协议）
局域网仿真定义了 ATM作为骨干网互连现有 LAN，以及现有的以太网或令牌网上主机如何在对等环境下与具有
ATM接口的主机或其他符合 ATMUNI标准的服务器等设备进行通信（图、协议栈）
集成模型将 IP路由器的智能和管理性能集成到 ATM交换中形成的一体化平台。 ATM层被看作 IP层的对等层，
ATM只需使用 IP地址，在建立连接时使用非标准的 ATM信令协议。不需要地址解析,ATM交换机象一个多协议路由器，增加了 ATM交换机的复杂性。
IP交换技术
TAG交换
IP传输 2- Ip over SDH
IP over SDH分层模型
IP over SDH的优点
（ 1）通过 PPP映射，效率高
（ 2）可兼容不同的技术和标准，实现网络互联
（ 3）采用 PPP协议，支持多协议传输
（ 4）在需要传输大量数据报较理想
IP over SDH的缺点
（ 1）不支持 VPN和电路仿真
（ 2）不能提供较好的 QOS
（ 3）需要处理庞大、复杂的路由表
IP传输技术 3-IP over DWDM
IP over DWDM分层模型
IP over DWDM优点
（ 1）效率高、容量大、成本低
（ 2）网络设计有较大的灵活性、自由度，扩容方便
（ 3）可在一根光纤中实现多媒体信息的双向传输
（ 4）降低器件成本
（ 5） DWDM采用无源器件，可靠、省电、故障率低
GFP（ Generic Framing Procedure）作为服务承载的通信协议,GFP已是 ITU－ T的规范
G.7041,GFP提供一个通用的机制，来适应流量自高层客户信息至传输网络上的传送。传输网络可以是任何类型的，例如 SONET/SDH,ITU-
T G.709（ ONT）。客户信息可以是以封包的模式
，或者恒定速率的数据或其他类型的信息模式。
路由器体系结构和关键技术
What is Routing?
R3
A
B
C
R1
R2
R4 D
E
FR5
R5F
R3E
R3D
Next HopDestination
What is Routing?
R3
A
B
C
R1
R2
R4 D
E
FR5
R5F
R3E
R3D
Next HopDestination
16 3241
Data
Options (if any)
Destination Address
Source Address
Header ChecksumProtocolTTL
Fragment OffsetFlagsFragment ID
Total Packet LengthT.ServiceHLenVer
20
by
te
s
What is Routing?
A
B
C
R1
R2
R3
R4 D
E
FR5
What a Router Looks Like
Cisco GSR 12416 Juniper M160
6ft
19”
2ft
Capacity,160Gb/s
Power,4.2kW
3ft
2.5ft
19”
Capacity,80Gb/s
Power,2.6kW
Why are Fast Routers Difficult to Make?
1,It’s hard to keep up with Moore’s Law:
- The bottleneck is memory speed.
- Memory speed is not keeping up with
Moore’s Law,
2,Moore’s Law is too slow:
- Routers need to improve faster than
Moore’s Law.
Why are Fast Routers Difficult to Make?
Speed of Commercial DRAM
1,It’s hard to keep up with Moore’s Law:
- The bottleneck is memory speed.
- Memory speed is not keeping up with Moore’s Law.
0,0 0 1
0,0 1
0,1
1
10
1 0 0
1 0 0 0
1 9 8 0 1 9 8 3 1 9 8 6 1 9 8 9 1 9 9 2 1 9 9 5 1 9 9 8 2001
A
c
c
es
s
T
im
e
(
n
s
)
Moore’s Law
2x / 18 months
1.1x / 18 months
0,1
1
10
100
1000
10000
1985 1990 1995 2000
Spe
c95Int CPU re
sults
0,1
1
10
100
1000
10000
1985 1990 1995 2000
Fib
er
C
ap
ac
ity
(G
bit
/s)
TDM DWDM
Packet processing Power Link Speed
2x / 18 months 2x / 7 months
Source,SPEC95Int & David Miller,Stanford.
Moore’s Law and Fiber Law
Router Performance Exceeds Moore’s Law
Growth in capacity of commercial routers:
- Capacity 1992 ~ 2Gb/s
- Capacity 1995 ~ 10Gb/s
- Capacity 1998 ~ 40Gb/s
- Capacity 2001 ~ 160Gb/s
- Capacity 2003 ~ 640Gb/s
Average growth rate,2.2x / 18 months.
Generic Router Architecture
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Data Hdr
Data Hdr
Data Hdr
Buffer
Manager
Buffer
Memory
Buffer
Manager
Buffer
Memory
Buffer
Manager
Buffer
Memory
Data Hdr
Data Hdr
Data Hdr
路由器体系结构的发展
单总线,单处理器
- 传统的计算机结构,处理器成为处理瓶颈
单总线,多处理器,每个接口卡上有一个处理器
,主处理器负责协调 。
- 包转发由本地处理器完成,减少总线负担
交换结构 + 专用硬件（ ASIC,FPGA,NP）
- 交换结构实现无阻塞转发
- 硬件实现对 IP包的处理和路由查找
Internet Routing Matrix
- 多结点级连，类似并行计算机
Route
TableCPU
Buffer
Memory
Line
Interface
MAC
Line
Interface
MAC
Line
Interface
MAC
Typically <0.5Gb/s aggregate capacity
First Generation Routers
Shared Backplane
Second Generation Routers
Route
TableCPU
Line
Card
Buffer
Memory
Line
Card
MAC
Buffer
Memory
Line
Card
MAC
Buffer
Memory
Fwding
Cache
Fwding
Cache
Fwding
Cache
MAC
Buffer
Memory
Typically <5Gb/s aggregate capacity
Third Generation Routers
Line
Card
MAC
Local
Buffer
Memory
CPU
Card
Line
Card
MAC
Local
Buffer
Memory
Switched Backplane
Fwding
Table
Routing
Table
Fwding
Table
Typically <50Gb/s aggregate capacity
Fourth Generation Routers/Switches
Optics inside a router for the first time
Switch Core Linecards
Optical links
100s
of metres
0.3 - 10Tb/s routers in development
路由器基本结构路由引擎
(Routing Engine)
网络接口
（Interface)
路由更新
（Update)
路由查找
（Search)
转发引擎
(Forwarding Engine)
网络接口
（Interface)
路由表
（Routing Table)
内部交换
（Switching)
控制路径
（Control Path)
数据路径
（Data Path)
控制路径
（Control Path)
网络接口
- 完成网络报文的接收和发送。
转发引擎
- 负责决定报文的转发路径。
内部交换
- 为多个网络接口以及路由引擎模块之间的报文数据传送提供高速的数据通路。
路由引擎
- 由运行高层协议（特别是路由协议）的内部处理模块组成。
路由表
- 路由表包含了能够完成网络报文正确转发的所有路由信息，它在整个路由器系统中起着承上启下的作用。
报文处理路径
路由器提供了两种不同的报文处理路径：
- 数据路径,处理目的地址不是本路由器而需要转发的报文，因此数据路径是整个路由器的关键路径，它的实现好坏直接影响着路由器的整体性能。
- 控制路径,处理目的地址是本路由器的高层协议报文，特别是各种路由协议报文。虽然控制路径不是路由器的关键路径，但是它负责完成路由信息的交互，从而保证了数据路径上的报文沿着最优的路径转发。
路由引擎
(Routing Engine)
网络接口
（Interface)
路由更新
（Update)
路由查找
（Search)
转发引擎
(Forwarding Engine)
网络接口
（Interface)
路由表
（Routing Table)
内部交换
（Switching)
控制路径
（Control Path)
数据路径
（Data Path)
控制路径
（Control Path)
数据路径的工作流程
RFC1812规定 IP路由器必须完成两个基本功能：
- 首先路由器必须能够对每个到达本路由器的报文做出正确的转发决策，决定报文向哪一个下一跳路由器转发。为了进行正确的转发决策，路由器需要在转发表中查找能够与转发报文目的地址最佳匹配的表项，这个查找过程被称为路由查找（ Route
Lookup）。
- 其次路由器在得到了正确的转发决策之后必须能够将报文从输入接口向相应的输出接口传送，这个过程被称为内部交换过程（ Switching）。
决定报文应该转发的目的地址以及相关接口路由查找通过交换结构将报文转发到输出端口内部交换接口卡 交换结构转发报文
IP Address Lookup
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Buffer
Manager
Buffer
Memory
Buffer
Manager
Buffer
Memory
Buffer
Manager
Buffer
Memory
路由查找过程示意图
headerpayload
Packet
Router
Destination
Address
Outgoing
Port
Destination Next Hop
Forwarding Table
Routing Lookup
Data Structure
65.0.0.0/8
128.9.0.0/16
149.12.0.0/19
3
1
7
IP Address Lookup
Why it’s thought to be hard:
1,It’s not an exact match,it’s a longest
prefix match,
2,The table is large,about 120,000 entries
today,and growing,
3,The lookup must be fast,about 30ns for a
10Gb/s line,
Packet Buffering
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Queue
Packet
Buffer
Memory
Queue
Packet
Buffer
Memory
Queue
Packet
Buffer
Memory
Buffer
M nager
Buffer
M nager
Buffer
M nager
Fast Packet Buffers
Example,40Gb/s packet buffer
40 byte packets
Write Rate,R
1 packet
every 8 ns
Read Rate,R
1 packet
every 8 ns
Buffer
Manager
Buffer
Memory
Use SRAM?
+ fast enough random access time,but
- too low density to store 10Gb of data.
Use DRAM?
+ high density means we can store data,but
- too slow (50ns random access time).
DRAM Buffer Memory
Packet Caches
Buffer
Manager
SRAM
Arriving
Packets
Departing
Packets12
Q
2
1234
345
123456
Small ingress SRAM
cache of FIFO headscache of FIFO tails
5556
9697
8788
57585960
899091
1
Q
2
Small ingress SRAM
1
57 6810 9
79 81011
1214 1315
5052 515354
8688 878991 90
8284 838586
9294 9395 68 7911 10
1
Q
2
DRAM Buffer Memory
b>>1 packets at a time
Switching
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Queue
Packet
Buffer
Memory
Queue
Packet
Buffer
Memory
Queue
Packet
Buffer
Memory
Data Hdr
Data Hdr
Data Hdr
1
2
N
1
2
N
N times line rate
N times line rate
Switching
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Queue
Packet
Buffer
Memory
Queue
Packet
Buffer
Memory
Queue
Packet
Buffer
Memory
Data Hdr
Data Hdr
Data Hdr
1
2
N
1
2
N
Data Hdr
Data Hdr
Data Hdr
Scheduler
0% 20% 40% 60% 80% 100%
L o a d
D
e
l
a
y
A Router with Input Queues
The best that
any queueing
system can
achieve.
0% 20% 40% 60% 80% 100%
L o a d
D
e
l
a
y
A Router with Input Queues
Head of Line Blocking
The best that
any queueing
system can
achieve.
2 2 5 8 %
Head of Line Blocking
Virtual Output Queues
0% 20% 40% 60% 80% 100%
L o a d
D
e
l
a
y
A Router with Virtual Output Queues
The best that
any queueing
system can
achieve.
7.1 网络层概述
7.2 路由算法
7.2.1 最优化原则
7.2.2 最短路径路由算法
7.2.3 洪泛算法
7.2.4 基于流量的路由算法
7.2.5 距离向量路由算法
7.2.6 链路状态路由算法
7.2.7 分层路由
7.2.8 移动主机的路由
7.3 拥塞控制算法
7.3.1 拥塞控制的基本原理
7.3.2 拥塞控制算法
7.4 网络互连
7.4.1 级联虚电路
7.4.2 无连接网络互连
7.4.3 隧道技术
7.4.4 互联网路由
7.4.5 分段
7.4.6 防火墙
7.5 INTERNET网络层协议
7.5.1 IP协议
7.5.2 Internet控制协议
7.5.3 内部网关路由协议,OSPF
7.5.4 外部网关路由协议,BGP
7.6 路由器体系结构和关键技术
7.1 网络层概述（ 1）
ISO 定义
- 网络层为一个网络连接的两个传送实体间交换网络服务数据单元提供功能和规程的方法，它使传送实体独立于路由选择和交 换的方式。
网络层是处理端到端传输的最低层。
网络层要解决的关键问题,向传输层提供服务、选择路由
、拥塞控制。
了解通信子网的拓扑结构
网络层设计的有关问题
- 设计目标：
服务与通信子网技术无关。
通信子网的数量、类型和拓扑结构对传输层隐蔽。
传输层能获得同一的网络地址，即使跨越多个 LAN或 WAN。
7.1 网络层概述（ 2）
- 为传输层提供服务
面向连接服务传统电信的观点：通信子网应该提供可靠的、面向连接的服务。
无连接服务
Internet的观点：通信子网无论怎么设计都是不可靠的，
因此网络层只需提供无连接服务。
- 网络层的内部组织
虚电路（ virtual circuit）
数据报（ datagram）（对每个分组进行路由计算）
7.1 网络层概述（ 3）
- 虚电路子网与数据报子网的比较
路由器内存空间与带宽的权衡
虚电路方式，路由器需要维护虚电路的状态信息；
数据报方式，每个数据报都携带完整的目的 /源地址，浪费带宽
连接建立时间与地址查找时间的权衡
虚电路需要在建立连接时花费时间
数据报则在每次路由时过程复杂
虚电路方式很容易保证服务质量 QoS（ Quality of
Service），但比较脆弱
虚电路方式很容易保证服务质量 QoS(Quality of
Service)，适用于实时操作，但比较脆弱。
数据报不太容易保证服务质量，但是对于通信线路的故障，适应性很强。
7.1 网络层概述（ 4）
7.1 网络层概述（ 5）
网络层为传输层提供的服务
- 面向连接服务：将复杂的功能放在网络层 (通信子网 )。
- 无连接服务：将复杂的功能放在传输层。
- 通信子网提供的服务（面向连接或无连接）与通信子网技术（虚电路或数据报）没有必然联系。
- 服务与子网结构的不同组合的例子小结
网络层的地位
- 位于数据链路层和传输层之间，使用数据链路层提供的服务，
为传输层提供服务；
- 通信子网的最高层；
- 处理端到端传输的最低层。
网络层的作用
- 屏蔽各种不同类型网络之间的差异，实现互连
- 了解通信子网的拓扑结构，选择路由，实现报文的网络传输
网络层的两种实现方式 ——数据报和虚电路
- 都属于分组交换，采用存储转发机制。
- 数据报 (datagram)：每个分组被单独路由，分组带有全网唯一的地址
- 虚电路 (virtual circuit)：先在源端和目的端之间建立一条虚电路
，所有分组沿虚电路按次序存储转发，最后拆除虚电路。在虚电路中，每个分组无须进行路径选择。
网络层提供的服务
- 面向连接的服务和无连接的服务。
7.2 路由算法（ 1）
路由算法是网络层软件的一部分
- 子网采用数据报方式，每个包都要做路由选择；
- 子网采用虚电路方式，只需在建立连接时做一次路由选择。
路由算法应具有的特性
- 正确性（ correctness）
- 简单性（ simplicity）
- 健壮性（ robustness）
- 稳定性（ stability）
- 公平性（ fairness）
- 最优性（ optimality）
路由算法分类
- 非自适应算法，静态路由算法
- 自适应算法，动态路由算法
7.2 路由算法（ 2）
7.2.1 最优化原则
最优化原则（ optimality principle）
- 如果路由器 J 在路由器 I 到 K 的最优路由上，那么从 J
到 K 的最优路由会落在同一路由上。
汇集树（ sink tree）
- 从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为汇集树；
- 路由算法的目的是找出并使用汇集树。
7.2 路由算法（ 3）
7.2.2 最短路径路由算法（ Shortest Path Routing）
属于静态路由算法
基本思想
- 构建子网的拓扑图，图中的每个结点代表一个路由器，
每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。
测量路径长度的方法
- 结点数量
- 地理距离
- 传输延迟
- 距离、信道带宽等参数的加权函数
算法一（ Dijkstra算法）,
设源节点为 1，计算源节点到所有节点的最短路径。
令 D(v)为源节点到节点 v的距离，是沿某一通路的所有链路的长度之和。再令 L(i,j)为相邻节点 i到 j的距离，不相邻节点 i到 j
的 L(i,j) 为无穷大。算法如下：
（ 1）初始化：令 N表示网络节点的子集，初始时 N={1}。对于所有不在 N中的节点有：
D(v)=L(I,j)，若节点 v与节点 1直接相连
D(v)=无穷大，若节点 v与节点 1不相连
（ 2）寻找一个不在 N中的节点 w，其 D(w)最小。把 w加入到 N
中，然后对所有不在 N中的节点，用 [D(v),D(w)+L(w,v)]中较小的值更新所有的 D(v)值。
（３）重复步骤（２），直到网络中所有的节点都在Ｎ中为止
算法二对每个节点赋予标记（ n,D(v)），其中 D(v) 代表从节点 v到目的节点的最段距离的当前值，而 n则为沿着当前已算出的最短通路的后继节点的编号。
（１）初试化：设节点１为目的节点，将其他所有节点标上 （,,无穷大），符号,表示暂时空缺，而无穷大可以用任何足够大的数值表示。
（ 2）对所有除目的节点以外的节点标上最短距离，即对任何 v
不等于 1的节点做如下运算：对所有的与节点 v相邻的节点 w
，用节点 w的当前值 D(w)计算 D(w)+L(w,v)，其中 w包括 1，
找出其最小值，用此最小值更新原来的 D(v)。同时更新 n的值。可以从所得到的当前最小 D(v)的通路中找到节点 v的后继节点，此后继节点的标号就是 n的当前值。
当对所有 v不等于 1的节点全部都进行完上述计算，重复（ 2）
。若计算结果与前次一致，计算结束。
7.2 路由算法（ 5）
7.2.3 洪泛算法（ Flooding）
属于静态路由算法
基本思想
- 把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。
主要问题
- 洪泛要产生大量重复包。
解决措施
- 每个包头包含站点计数器，每经过一站计数器减 1，为 0
时则丢弃该包；
- 记录包经过的路径
7.2 路由算法（ 6）
选择性洪泛算法（ selective flooding）
- 洪泛法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上。
应用情况
- 路由器和线路的资源过于浪费，实际很少直接采用；
- 具有极好的健壮性，可用于军事应用；
- 作为衡量标准评价其它路由算法。
7.2 路由算法（ 7）
7.2.4 基于流量的路由算法（ Flow-Based Routing）
属于静态路由算法
基本思想
- 既考虑拓扑结构，又兼顾网络负荷；
- 前提：每对结点间平均数据流是相对稳定和可预测的；
- 根据网络带宽和平均流量，可得出平均包延迟，因此路由选择问题归结为找产生网络最小延迟的路由选择算法。
- 提前离线（ off-line）计算
需要预知的信息
- 网络拓扑结构；
- 通信量矩阵 Fij；
- 线路带宽矩阵 Cij；
- 路由算法（可能是临时的）。
1/? = 800 bits
根据排队论，平均延迟 T = 1/ (?C -?)
7.2 路由算法（ 8）
7.2.5 距离向量路由算法（ Distance Vector Routing）
属于动态路由算法，也称 Bellman-Ford路由算法和
Ford-Fulkerson算法，最初用于 ARPANET，被 RIP协议采用。
基本思想
- 每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与 相邻路由器 交换距离信息来更新表；
- 以子网中其它路由器为表的索引，表项包括两部分：到达目的 结点的最佳输出线路，和到达目的结点所需时间或距离；
- 每隔一段时间，路由器向所有邻居结点发送它到每个目的结点 的距离表，同时它也接收每个邻居结点发来的距离表；
- 邻居结点 X发来的表中,X到路由器 i的距离为 Xi,本路由器到 X
的距离为 m，则路由器经过 X到 i的距离为 Xi + m。根据不同邻居发来的信息，计算 Xi + m，并取最小值，更新本路由器的路由表；
- 注意：本路由器中的老路由表在计算中不被使用。
7.2 路由算法（ 9）
7.2 路由算法（ 10）
无限计算问题
- 算法的缺陷：对好消息反应迅速,(当 A 连上网时）对坏消息反应迟钝
7.2 路由算法（ 11）
水平分裂算法
- 工作过程与距离向量算法相同，区别在于到 X的距离不向真正通向 X的邻居结点报告，使得坏消息传播的也快。
Fig,5-11
- 虽然广泛使用，但有时候会失败。
7.2 路由算法（ 12）
7.2.6 链路状态路由算法（ Link State Routing）
距离向量路由算法的主要问题
- 实际应用选择路由时，用队列长度衡量时延没有考虑线路带宽；
- 路由收敛速度慢。
链路状态路由算法
- 发现邻居结点，并学习它们的网络地址；
路由器启动后，通过发送 HELLO包发现邻居结点；
- 测量到每个邻居结点的延迟或开销；
一种直接的方法是：发送一个要对方立即响应的 ECHO包
，来回时间除以 2即为延迟。
载荷的考虑,从 ECHO包进入队列时算时或开始发送时计时
7.2 路由算法（ 13）
- 将所有学习到的内容封装成一个包；
包以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表；
列表中对应每个邻居结点，都有发送方到它们的延迟或开 销；
Fig,5-15
链路状态包定期创建或发生重大事件时创建。
- 将这个包发送给所有其它路由器；
基本思想：洪泛链路状态包，为控制洪泛，每个包包含一 个序号，每次发送新包时加 1。路由器记录信息对（源路由器，序号），当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最 大序号小，则认为过时而丢弃；
改进
序号循环使用会混淆，解决办法：使用 32位序号；
7.2 路由算法（ 14）
路由器崩溃后，序号重置；
序号出错；
第二、三问题的解决办法：增加年龄（ age）域，每秒钟年龄减 1，为零则丢弃。
链路状态包到达后，延迟一段时间，并与其它已到达的来自同一路由器的链路状态包比较序号，丢弃重复包，保留新包；
链路状态包需要应答；
Fig,5-16
- 计算到每个其它路由器的最短路径。
根据 Dijkstra算法计算最短路径；
实用协议
- OSPF
- IS-IS
7.2 路由算法（ 15）
链路状态算法（ LS）和距离向量算法（ DV）的比较
- 路由信息的复杂性
LS
路由信息向全网发送
with n nodes,E links,O(nE) msgs sent each
DV
exchange between neighbors only
- 收敛（ Convergence）速度
LS
使用最短路径优先算法，算法复杂度为 O(n**2)
n个结点（不包括源结点），需要 n*(n+1)/2 次比较
使用更有效的实现方法，算法复杂度可以达到 O(nlogn)
可能存在 路由振荡（ oscillations）
DV
convergence time varies
may be routing loops
count-to-infinity problem
7.2 路由算法（ 16）
- 健壮性,what happens if router malfunctions?
LS
node can advertise incorrect link cost
each node computes only its own table
DV
DV node can advertise incorrect path cost
each node’s table used by others
error propagate thru network
7.2 路由算法（ 18）
7.2.7 分层路由（ Hierarchical Routing）
网络规模增长带来的问题
- 路由器中的路由表增大；
- 路由器为选择路由而占用的内存,CPU时间和网络带宽增大。
分层路由
- 分而治之的思想；
- 根据需要，将路由器分成区域（ regions）、聚类（
clusters）、区（ zones）和组（ groups） …
- Fig,5-17，路由表由 17项减为 7项。
分层路由带来的问题
- 路由表中的路由不一定是最优路由。
小结
最优化原则
- 路由算法的目的是找出并使用汇集树。
静态路由算法
- 最短路径路由算法
- 洪泛算法
- 基于流量的路由算法
动态路由算法
- 距离向量路由算法
将自己对全网拓扑结构的认识告诉给邻居
无穷计算问题，水平分裂算法
- 链路状态路由算法
将自己对邻居的认识洪泛给全网
分层路由
移动主机的路由
7.3 拥塞控制算法（ 1）
拥塞（ congestion）
- 网络上有太多的包时，性能会下降，这种情况称为 拥塞 。
- Fig,5-22
拥塞产生的原因 (资源分配 )
- 多个输入对应一个输出；
- 慢速处理器；
- 低带宽线路。
解决办法
- 针对某个因素的解决方案，只能对提高网络性能起到一点点好处，甚至可能仅仅是转移了影响性能的瓶颈；
- 需要全面考虑各个因素。
7.3 拥塞控制算法（ 2）
拥塞控制与流量控制的差别
- 拥塞控制（ congestion control）需要确保通信子网能够承载用户提交的通信量，是一个全局性问题，涉及主机
、路由器等很多因素；
- 流量控制（ flow control）与点到点的通信量有关，主要解决快速发送方与慢速接收方的问题，是局部问题，一般都是基于反馈进行控制的。
7.3 拥塞控制算法（ 3）
7.3.1 拥塞控制的基本原理
根据控制论，拥塞控制方法分为两类
- 开环控制
通过好的设计来解决问题，避免拥塞发生；
拥塞控制时，不考虑网络当前状态；
- 闭环控制
基于反馈机制；
工作过程
监控系统，发现何时何地发生拥塞；
把发生拥塞的消息传给能采取动作的站点；
调整系统操作，解决问题。
7.3 拥塞控制算法（ 4）
衡量网络是否拥塞的参数
- 缺乏缓冲区造成的丢包率；
- 平均队列长度；
- 超时重传的包的数目；
- 平均包延迟；
- 包延迟变化（ Jitter）。
反馈方法
- 向负载发生源发送一个告警包；
- 包结构中保留一个位或域用来表示发生拥塞，一旦发生 拥塞，路由器将所有的输出包置位，向邻居告警；
- 主机或路由器主动地、周期性地发送探报（ probe）,查询是否发生拥塞。
7.3 拥塞控制算法（ 5）
7.3.2 拥塞控制算法
拥塞预防策略
- 开环控制
- 影响拥塞的网络设计策略
7.3 拥塞控制算法（ 6）
流量整形（ Traffic Shaping）
- 开环控制
- 基本思想
造成拥塞的主要原因是网络流量通常是突发性的；
强迫包以一种可预测的速率发送；
在 ATM网中广泛使用。
- 漏桶算法（ The Leaky Bucket Algorithm）
Fig,5-24
将用户发出的不平滑的数据包流转变成网络中平滑 的数据包流；
可用于固定包长的协议，如 ATM；也可用于可变包长的协议，如 IP，使用字节计数；
例,Fig,5-25(a)(b)；
无论负载突发性如何，漏桶算法强迫输出按平均速率进行，不灵活。
7.3 拥塞控制算法（ 7）
- 令牌桶算法（ The Token Bucket Algorithm）
漏桶算法不够灵活，因此加入令牌机制；
基本思想：漏桶存放令牌，每?T秒产生一个 令牌，
令牌累积到超过漏桶上界时就不再增加。包传输之前必须获得一个令牌，传输之后删除该令牌；
Fig,5-26
- 漏桶算法与令牌桶算法的区别
流量整形策略不同：漏桶算法不允许空闲主机积累发送权，以便以后发送大的突发数据；令牌桶算法允许，最大为桶的大小。
漏桶中存放的是数据包，桶满了丢弃数据包；令牌桶中存放的是令牌，桶满了丢弃令牌，不丢弃数据包。
7.3 拥塞控制算法（ 8）
流说明（ Flow Specification）
- 一个数据流的发送方、接收方和通信子网三方认可的、
描述发送数据流的模式和希望得到的服务质量的数据结构，称为 流说明 。
- 对发送方的流说明，子网和接收方可以做出三种答复：
同意、拒绝、其它建议。
7.3 拥塞控制算法（ 9）
虚电路子网中的拥塞控制
- 许可控制（ admission control），基本思想：一旦发生拥塞，在问题解决之前，不允许建立新的虚电路；
- 另一种方法是发生拥塞后可以建立新的虚电路，但要绕开发生拥塞的地区；
- 资源预留：建立虚电路时，主机与子网达成协议，子网根据协议在虚电路上为此连接预留资源。（ RSVP）
7.3 拥塞控制算法（ 10）
抑制包（ Choke Packets）
- 基本思想
路由器监控输出线路及其它资源的利用情况，超过某个阈值，
则此资源进入警戒状态；
每个新包到来，检查它的输出线路是否处于警戒状态；
若是，则向源主机发送抑制包，包中指出发生拥塞的目的地址
。同时将原包打上标记（为了以后不再产生抑制包），正常转发；
源主机收到抑制包后，按一定比例减少发向特定目的地的流量
，并在固定时间间隔内忽略指示同一目的地的抑制包。然后开始监听，若此线路仍然拥塞，则主机在固定时间内减轻负载、
忽略抑制包；若在监听周期内没有收到抑制包，则增加负载；
通常采用的流量增减策略是：减少时，按一定比例减少，保证快速解除拥塞；增加时，以常量增加，防止很快导致拥塞。
7.3 拥塞控制算法（ 11）
加权公平队列（ Weighted Fair Queueing）
- 公平队列（ Fair Queueing）算法
路由器的每个输出线路有多个队列；
路由器循环扫描各个队列，发送队头的包；
所有主机具有相同优先级；
一些 ATM交换机、路由器使用这种算法；
一种改进：对于变长包，由逐包轮讯改为逐字节轮讯
Fig,5-29
- 加权公平队列算法
给不同主机以不同的优先级；
优先级高的主机在一个轮讯周期内获得更多的时间片。
7.3 拥塞控制算法（ 12）
逐跳抑制包（ Hop-by-Hop Choke Packets）
- 在高速、长距离的网络中，由于源主机响应太慢，抑制包算法对拥塞控制的效果并不好，可采用逐跳抑制包算法；
Fig,5-30(a)
- 基本思想
抑制包对它经过的每个路由器都起作用；
能够迅速缓解发生拥塞处的拥塞；
上游路由器要求有更多的缓冲区；
Fig,5-30(b)
7.3 拥塞控制算法（ 13）
负载丢弃（ Load Shedding）
- 上述算法都不能消除拥塞时，路由器只得将包丢弃；
- 针对不同服务，可采取不同丢弃策略
文件传输，优先丢弃新包,wine策略；
多媒体服务，优先丢弃旧包,milk策略；
- 早期丢弃包，会减少拥塞发生的概率，提高网络性能。
7.4 网络互联（ 1）
互联网（ internet）：两个或多个网络构成互联网。
多种不同网络（协议）存在的原因
- 历史原因：不同公司的网络产品大量使用；
- 价格原因：网络产品价格低，更多的人有权决定使用何种网络；
- 技术原因：不同网络采用不同技术、不同硬件、不同协议。
7.4 网络互联（ 2）
网络互连设备
- 中继器（ repeater）
物理层设备，在电缆段之间拷贝比特；
对弱信号进行放大或再生，以便延长传输距离。
- 网桥（ bridge）
数据链路层设备，在局域网之间存储转发帧；
网桥可以改变帧格式。
- 多协议路由器（ multiprotocol router）
网络层设备，在网络之间存储转发包；
必要时，做网络层协议转换。
- 传输网关（ transport gateway）
传输层设备，在传输层转发字节流。
- 应用网关（ application gateway）
应用层设备，在应用层实现互连；
half-gateway（为了满足不同国家、组织的管理需要）
Fig,5-34
7.4 网络互联（ 3）
网络之间的区别
7.4 网络互联（ 4）
7.4.1 级联虚电路（ Concatenated Virtual Circuits）
工作过程
- 级联虚电路工作过程与虚电路子网工作过程相似；
- 建立连接
当目的主机不在子网内时，则在子网内找一个离目的网络 最近的路由器，与之建立一条虚电路；
该路由器与外部网关建立虚电路；
该网关与下一个子网中的一个路由器建立虚电路；
重复上述操作，直到到达目的主机。
- 传输数据
相同连接的包沿同一虚电路按序号传输；
网关根据需要转换包格式和虚电路号。
- 拆除连接
7.4 网络互联（ 5）
7.4.2 无连接网络互连（ Connectionless Internetworking）
工作过程
- 无连接网络互连的工作过程与数据报子网的工作过程相似；
- 每个包单独路由，提高网络利用率，但不能保证包按顺序到达；
- 根据需要，连接不同子网的多协议路由器做协议转换，包括包格式转换和地址转换等。
7.4 网络互联（ 6）
级联虚电路与无连接网络互连的比较
- 级联虚电路的优点
路由器预留缓冲区等资源，保证服务质量；
包按序号传输；
短包头。
- 级联虚电路的缺点
路由器需要大量内存，存储虚电路信息；
一旦发生拥塞，没有其它路由；
健壮性差；
如果网络中有一个不可靠的数据报子网，级连虚电路很难实现。
7.4 网络互联（ 7）
- 无连接网络互连的优点
能够容忍拥塞，并能适应拥塞；
健壮性好；
可用于多种网络互连。
- 无连接网络互连的缺点
长包头；
包不能保证按序号到达；
不能保证服务质量。
7.4 网络互联（ 8）
7.4.3 隧道技术（ Tunneling）
隧道技术
- 源和目的主机所在网络类型相同，连接它们的是一个不同类型的网络，这种情况下可以采用隧道技术。
7.4 网络互联（ 9）
工作过程（以 Fig,5-38为例）
- 主机 1发送一个包，目的 IP地址 = 主机 2-IP，将包封装到局域网帧中，帧目的地址 = 路由器 1-MAC；
- 局域网传输；
- 路由器 1剥掉局域网帧头、帧尾，将得到的 IP包封装到广域网 网络层包 中，包目的地址 = 路由器 2地址；
- 广域网传输；
- 路由器 2剥掉广域网包头，将得到的 IP包封装到局域网帧中，包目的 IP地址 = 主机 2-IP，帧目的地址 = 主机 2-
MAC地址；
- 局域网传输；
- 主机 2接收。
7.4 网络互联（ 10）
7.4.4 互联网路由（ Internetwork Routing）
工作过程
- 互联网络的路由与单独子网的路由过程相似，只是复杂性增加；
- 两级路由算法
内部网关协议（ IGP,Interior Gateway Protocol）
RIP,OSPF
外部网关协议（ EGP,Exterior Gateway Protocol）
BGP
自治系统 AS（ Autonomous System）
7.4 网络互联（ 11）
7.4.5 分段（ Fragmentation）
每种网络都对最大包长有限制，有以下原因
- 硬件，例如 TDM 的时槽限制；
- 操作系统；
- 协议，例如包长度域的比特个数；
- 与标准的兼容性；
- 希望减少传输出错的概率；
- 希望避免一个包占用信道时间过长。
大包经过小包网络时，网关要将大包分成若干段
（ fragment），每段作为独立的包传输。
7.4 网络互联（ 12）
段重组策略
- 分段重组过程对其它网络透明
网关将大包分段后，每段都要经过同一出口网关，
并在那里重组；
Fig,5-41(a)
例,ATM网络；
带来的问题
出口网关需要知道何时所有分组都到齐；
所有分组必须从同一出口网关离开；
大包经过一系列小包网络时，需要反复地分段重组，
开销大。
7.4 网络互联（ 11）
- 分段重组过程对其它网络不透明
中间网关不做重组，而由目的主机做；
Fig,5-41(b)
带来的问题
对主机要求高，能够重组；
每个段都要有一个包头，网络开销增大；
7.4 网络互联（ 12）
标记段
- 树型标记法
例，包 0分成三段，分别标记为 0.0,0.1,0.2，段 0.0构成的包被分成三段，分别标记为 0.0.0,0.0.1,0.0.2；
存在的问题
段标记域要足够长
分段长度前后要一致
- 偏移量法
定义一个基本段长度，使得基本段能够通过所有网络；
包分段时，除最后一个段小于等于基本段长度外，所有段长度都等于基本段长度；
一个包可以包括几个段，包头中包括；原始包序号，包 中第一个基本段的偏移量，最后段指示位；
Fig,5-42
7.4 网络互联（ 13）
7.4.6 防火墙（ Firewalls）
什么情况下使用防火墙？
- 为防止网络中的 信息泄露出去或不好的信息渗透进来，
在网络边缘设置防火墙；
- Fig,5-43
防火墙分类：包过滤，应用网关（代理）、电路级网关（状态检测器）、检查放火墙（三种结合
）
防火墙的一种常用配置
- 两个路由器，根据某种规则表，进行包过滤；
- 一个应用网关，审查应用层信息。
小结
互联网（ internet）：两个或多个网络构成互联网
网络互连设备：中继器、网桥、路由器、传输网关、应用网关
虚电路网络互联
数据报网络互联
隧道技术
分段和重组
防火墙
7.5 INTERNET网络层协议（ 1）
在网络层,Internet可以看成是自治系统的集合，
是由网络组成的网络。
网络之间互连的纽带是 IP（ Internet Protocol）协议。
网际协议 IP 是 TCP/IP 体系中两个最主要的协议之一 。与 IP 协议配套使用的还有四个协议：
地址解析协议 ARP
(Address Resolution Protocol)
逆地址解析协议 RARP
(Reverse Address Resolution Protocol)
因特网控制报文协议 ICMP
(Internet Control Message Protocol)
因特网组管理协议 IGMP
(Internet Group Management Protocol)
网际协议 IP 及其配套协议各种应用层协议网络接口层
(TELNET,FTP,SMTP 等 )
物理硬件运输层 TCP,UDP
应用层
ICMP
IP
RARP ARP
与各种网络接口网际层
IGMP
7.5 INTERNET网络层协议（ 2）
7.5.1 IP协议
IP头格式
- IP头包括 20个字节的固定部分和变长（最长 40字节）的可选部分，从左到右传输；
- 版本域（ version）；
- IHL,IP包头长度，最小为 5，最大为 15，单位为 32-bit word；
7.5 INTERNET网络层协议（ 3）
- 服务类型域（ Type of Service）
3个优先级位；
3个标志位,D（ Delay）,T（ Throughput）、
R（ Reliability）；
2个保留位；
目前，很多路由器都忽略服务类型域。
- 总长度域（ Total length：包括头和数据。 65535字节
- 标识域（ Identification）：同一分组的段相同
- DF,Don’t Fragment；
所有机器必须能够接收小于等于 576字节的段。
- MF,More Fragments
除最后一个段外的所有段都要置 MF位。
7.5 INTERNET网络层协议（ 4）
- 段偏移量（ Fragment offset）
除最后一个段外的所有段的长度必须是 8字节（基本段长）的倍数。
ID
=x
offset
=0
fragflag
=0
length
=4000
ID
=x
offset
=0
fragflag
=1
length
=1500
ID
=x
offset
=1480
fragflag
=1
length
=1500
ID
=x
offset
=2960
fragflag
=0
length
=1040
One large datagram becomes
several smaller datagrams
7.5 INTERNET网络层协议（ 5）
- 生存期（ Time to live）
实际实现中,IP包每经过一个路由器 TTL减 1，为 0则丢弃，并给源主机发送一个告警包。
- 协议域（ Protocol）：上层为哪种传输协议,TCP、
UDP…
- 头校验和（ Header checksum）
只对 IP包头做校验；
算法：每 16位求反，循环相加（进位加在末尾），
和再求反。
- 源地址（ Source address）和目的地址（ Destination
address）
7.5 INTERNET网络层协议（ 6）
- 选项（ Options）
变长，长度为 4字节的倍数，不够则填充，最长为 40
字节；
IP 地址的编址方法
分类的 IP 地址 。 这是最基本的编址方法,在 1981
年就通过了相应的标准协议 。
子网的划分 。 这是对最基本的编址方法的改进,其标准 [RFC 950]在 1985 年通过 。
构成超网 。 这是比较新的无分类编址方法 。 1993 年提出后很快就得到推广应用 。
分类 IP 地址
每一类地址都由两个固定长度的字段组成,其中一个字段是网络号 net-id,它标志主机 （ 或路由器 ） 所连接到的网络,而另一个字段则是主机号 host-id,它标志该主机
（ 或路由器 ） 。
两级的 IP 地址可以记为：
IP 地址,:= { <网络号 >,<主机号 >} (6-1)
分组转发算法
(1) 从数据报的首部提取目的站的 IP 地址 D,得出目的网络地址为 N。
(2) 若网络 N 与此路由器直接相连,则 直接 将数据报交付给目的站 D；否则是 间接 交付,执行 (3)。
(3) 若路由表中有目的地址为 D 的特定主机路由,则将数据报传送给路由表中所指明的下一跳路由器；否则,执行 (4)。
(4) 若路由表中有到达网络 N 的路由,则将数据报传送给路由表指明的下一跳路由器；否则,执行 (5)。
(5) 若路由表中有一个默认路由,则将数据报传送给路由表中所指明的默认路由器；否则,执行 (6)。
(6) 报告转发分组出错 。
IP 地址的一些重要特点
(1) IP 地址是一种分等级的地址结构 。 分两个等级的好处是
：
第一,IP地址管理机构在分配 IP地址时只分配网络号,
而剩下的主机号则由得到该网络号的单位自行分配 。 这样就方便了 IP地址的管理 。
第二,路由器仅根据目的主机所连接的网络号来转发分组 （ 而不考虑目的主机号 ）,这样就可以使路由表中的项目数大幅度减少,从而减小了路由表所占的存储空间
。
IP 地址的一些重要特点
(2) 实际上 IP 地址是标志一个主机 （ 或路由器 ） 和一条链路的接口 。
当一个主机同时连接到两个网络上时,该主机就必须同时具有两个相应的 IP 地址,其网络号 net-id 必须是不同的 。 这种主机称为多接口主机 (multihomed host)。
由于一个路由器至少应当连接到两个网络 （ 这样它才能将 IP 数据报从一个网络转发到另一个网络 ）,因此一个路由器至少应当有两个不同的 IP 地址 。
IP 地址的一些重要特点
(3) 用转发器或网桥连接起来的若干个局域网仍为一个网络
,因此这些局域网都具有同样的网络号 net-id。
(4) 所有分配到网络号 net-id 的网络,范围很小的局域网,
还是可能覆盖很大地理范围的广域网,都是平等的 。
互联网中的 IP 地址
B
222.1.1.
222.1.1.1 222.1.1.2 222.1.1.3
222.1.1.4R
1
222.1.2.5 222.1.2.2
222.1.2.1
222.1.2.3222.1.2.4
222.1.2.
222.1.6.1222.1.5.1
222.1.5.2 222.1.6.2
222.1.4.1222.1.4.2
222.1.3.3
222.1.3.2
222.1.3.1 R3 R2
222.1.3.
LAN3
N3
N2
222.1.4.
222.1.5.
222.1.6.
N1
LAN2
LAN1
互联网在同一个局域网上的主机或路由器的 IP 地址中的网络号必须是一样的。图中的网络号就是 IP 地址中的 net-id
2,常用的三种类别的 IP 地址
IP 地址的使用范围网络 最大 第一个 最后一个 每个网络类别 网络数 可用的 可用的 中最大的网络号 网络号 主机数
A 126 (27 – 2) 1 126 16,777,214
B 16,384 (214) 128.0 191.255 65,534
C 2,097,152 (221) 192.0.0 223.255.255 254
划分子网和构造超网
1,从两级 IP 地址到三级 IP 地址
在 ARPANET 的早期,IP 地址的设计确实不够合理 。
- IP地址空间的利用率有时很低 。
- 给每一个物理网络分配一个网络号会使路由表变得太大因而使网络性能变坏 。
- 两级的 IP 地址不够灵活 。
划分子网纯属一个 单位内部的事情 。 单位对外仍然表现为没有划分子网的网络 。
从主机号 借用 若干个比特作为 子网号 subnet-id,而主机号 host-id 也就相应减少了若干个比特 。
IP地址,:= {<网络号 >,<子网号 >,<主机号 >}
凡是从其他网络发送给本单位某个主机的 IP 数据报,仍然是根据 IP 数据报的 目的网络号 net-id,先找到连接在 本单位网络上的路由器 。
然后 此路由器 在收到 IP 数据报后,再按目的网络号 net-id 和子网号
subnet-id 找到目的子网 。
最后就将 IP 数据报直接交付给目的主机 。
划分子网的基本思路
145.13.3.10
145.13.3.11 145.13.3.101 145.13.7.34
145.13.7.35
145.13.7.56
145.13.21.23
145.13.21.9
145.13.21.8所有到网络145.13.0.0的分组均到达此路由器我的网络地址是 145.13.0.0
R1
R3
R2
网络
145.13.0.0
一个未划分子网的 B 类网络 145.13.0.0
划分为三个子网后对外仍是一个网络
145.13.3.10145.13.3.11
145.13.3.101 145.13.7.34
145.13.7.35
145.13.7.56
145.13.21.23
145.13.21.9
145.13.21.8
…
…
…
子网 145.13.21.0
子网 145.13.3.0
子网
145.13.7.0
所有到达网络
145.13.0.0
的分组均到达此路由器网络
145.13.0.0
R1R
3
R2
IP 地址的各字段和子网掩码网络号 net-id 主机号 host-id两级 IP 地址网络号
net-id host-id三级 IP 地址主机号
subnet-id
子网号子网掩码因特网部分 本地部分因特网部分 本地部分划分子网时的网络地址
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
net-id subnet-id host-id 为全 0
在划分子网的情况下路由器转发分组的算法
(1) 从收到的分组的首部提取目的 IP 地址 D。
(2) 先用各网络的子网掩码和 D 逐比特相“与”，看是否和相应的网络地址匹配。若匹配，则将分组直接交付。
否则就是间接交付，执行 (3)。
(3) 若路由表中有目的地址为 D 的特定主机路由，则将分组传送给指明的下一跳路由器；否则，执行 (4)。
(4) 对路由表中的每一行的子网掩码和 D 逐比特相
“与”，
若其结果与该行的目的网络地址匹配，则将分组传送给该行指明的下一跳路由器；否则，执行 (5)。
(5) 若路由表中有一个默认路由，则将分组传送给路由表中所指明的默认路由器；否则，执行 (6)。
(6) 报告转发分组出错。
因此 H1 必须把分组传送到路由器 R1
然后逐项查找路由表
128.30.33.1 0
目的网络地址 子网掩码 下一跳
128.30.33.0
128.30.33.128
128.30.36.0
255.255.255.128
255.255.255.128
255.255.255.0
接口 0
接口 1
R2
R1 的路由表（未给出默认路由器）
128.30.33.13
H1 子网 1：网络地址 128.30.33.0
子网掩码 255.255.255.128
128.30.33.130
R1
1
R2
子网 2：网络地址 128.30.33.128
子网掩码 255.255.255.128
H2 128.30.33.138
0
1
128.30.33.129
H3
128.30.36.2
子网 3：网络地址 128.30.36.0
子网掩码 255.255.255.0128.30.36.12
路由器 R1 收到分组后就用路由表中第 1 个项目的子网掩码和 128.30.33.138 逐比特 AND 操作
128.30.33.1 0
目的网络地址 子网掩码 下一跳
128.30.33.0
128.30.33.128
128.30.36.0
255.255.255.128
255.255.255.128
255.255.255.0
接口 0
接口 1
R2
R1 的路由表（未给出默认路由器）
128.30.33.13
H1 子网 1：网络地址 128.30.33.0
子网掩码 255.255.255.128
128.30.33.130
R1
1
R2
子网 2：网络地址 128.30.33.128
子网掩码 255.255.255.128
H2 128.30.33.138
0
1
128.30.33.129
H3
128.30.36.2
子网 3：网络地址 128.30.36.0
子网掩码 255.255.255.0128.30.36.12
255.255.255.128 AND 128.30.33.138 = 128.30.33.128
不匹配 !
（因为 128.30.33.128 与路由表中的 128.30.33.0 不一致）
R1收到的分组的目的 IP 地址,128.30.33.138
不一致路由器 R1 再用路由表中第 2 个项目的子网掩码和 128.30.33.138 逐比特 AND 操作
128.30.33.1 0
目的网络地址 子网掩码 下一跳
128.30.33.0
128.30.33.128
128.30.36.0
255.255.255.128
255.255.255.128
255.255.255.0
接口 0
接口 1
R2
R1 的路由表（未给出默认路由器）
128.30.33.13
H1 子网 1：网络地址 128.30.33.0
子网掩码 255.255.255.128
128.30.33.130
R1
1
R2
子网 2：网络地址 128.30.33.128
子网掩码 255.255.255.128
H2 128.30.33.138
0
1
128.30.33.129
H3
128.30.36.2
子网 3：网络地址 128.30.36.0
子网掩码 255.255.255.0128.30.36.12
255.255.255.128 AND 128.30.33.138 = 128.30.33.128
匹配 !
这表明子网 2 就是收到的分组所要寻找的目的网络
R1收到的分组的目的 IP 地址,128.30.33.138
一致 !
无分类的两级编址的记法是：
IP地址,:= {<网络前缀 >,<主机号 >}
CIDR 还使用,斜线记法,(slash notation),它又称为
CIDR记法,即在 IP地址后面加上一个斜线,/”,然后写上网络前缀所占的比特数 （ 这个数值对应于三级编址中子网掩码中比特 1 的个数 ） 。
CIDR 将网络前缀都相同的连续的 IP 地址组成,CIDR地址块,。
无分类 的两级编址
CIDR 地址块
128.14.32.0/20 表示的地址块共有 212 个地址 （ 因为 斜线后面的 20 是网络前缀的比特数,所以主机号的比特数是 12）
。
这个地址块的起始地址是 128.14.32.0。
在不需要指出地址块的起始地址时,也可将这样的地址块简称为,/20 地址块,。
128.14.32.0/20地址块的最小地址,128.14.32.0
128.14.32.0/20地址块的最大地址,128.14.32.255
全 0 和全 1 的主机号地址一般不使用 。
最长前缀匹配
使用 CIDR 时,路由表中的每个项目由,网络前缀,
和,下一跳地址,组成 。 在查找路由表时可能会得到不止一个匹配结果 。
应当从匹配结果中选择具有最长网络前缀的路由,最长前缀匹配 (longest-prefix matching)。
网络前缀越长,其地址块就越小,因而路由就越具体
。
最长前缀匹配又称为 最长匹配 或 最佳匹配 。
7.5 INTERNET网络层协议（ 6）
7.5.2 Internet控制协议
Internet控制报文协议 ICMP（ The Internet Control
Message Protocol）
- 主要用来报告出错和测试；
- 报文类型
- ICMP报文封装在 IP包中。
7.5 INTERNET网络层协议（ 7）
地址解析协议 ARP（ The Address Resolution Protocol）
- 解决网络层地址（ IP地址）与数据链路层地址（ MAC地址）的映射问题；
- Fig,5-51
- 工作过程
建立一个 ARP表，表中存放（ IP地址,MAC地址）对；
若目的主机在同一子网内，用目的 IP地址在 ARP表中查找
，否则用缺省网关的 IP地址在 ARP表中查找。若未找到，
则发送广播包，目的主机收到后给出应答,ARP表增加一项；
每个主机启动时，广播它的（ IP地址,MAC地址）映射；
ARP表中的表项有生存期，超时则删除。
ARP是在同一个局域网主机或路由器 IP地址与 MAC地址映射
7.5 INTERNET网络层协议（ 8）
反向地址解析协议 RARP（ The Reverse Address
Resolution Protocol）
- 解决数据链路层地址（ MAC地址）与网络层地址（ IP地址）的映射问题；机器启动后发送带 MAC地址的广播帧
，询问 RARP服务器他的 IP地址。 要设定 RARP服务器
。
- 主要用于无盘工作站启动；
- 缺点：由于路由器不转发广播帧,RARP服务器必须与无盘工作站在同一子网内。一种替代协议 BOOTP（使用
UDP）。
因特网控制报文协议 ICMP：允许主机或路由器报告差错情况和提供异常情况的报告。
7.5 INTERNET网络层协议（ 12）
7.5.3 内部网关路由协议,OSPF
开放最短路径优先 OSPF（ Open Shortest Path
First）
- 开放，公开发表；
- 支持多种距离衡量尺度，例如，物理距离、延迟等；
- 动态算法；
- 支持基于服务类型的路由；
- 负载平衡；
- 支持分层系统；
- 适量的安全措施；
- 支持隧道技术。
7.5 INTERNET网络层协议（ 13）
构造有向拓扑图
- 根据实际的网络、路由器和线路构造有向图；
- 每个弧赋一个开销值；
- 两个路由器之间的线路用一对弧来表示，弧权可以不同；
- 多路访问（ multiaccess）网络，网络用一个结点表示，每个路由器用一个结点表示，网络结点与路由器结点的弧权为 0；
- Fig,5-52
7.5 INTERNET网络层协议（ 14）
分层路由
- 自治系统 AS可以划分区域（ areas）；
- 每个 AS有一个主干（ backbone）区域，称为区域 0，所有区域与主干区域相连；
- Fig,5-53
- 一般情况下，有三种路由
区域内
区域间
从源路由器到主干区域；
穿越主干区域到达目的区域；
到达目的路由器。
自治系统间
7.5 INTERNET网络层协议（ 15）
- 四类路由器，允许重叠
完全在一个区域内的内部路由器；
连接多个区域的区域边界路由器；
主干路由器；
自治系统边界路由器。
信息类型
7.5 INTERNET网络层协议（ 16）
7.5.4 外部网关路由协议,BGP
Why different Intra- and Inter-AS routing?
- Policy
Inter-AS,admin wants control over how its traffic
routed,who routes through its net,
Intra-AS,single admin,so no policy decisions
needed
- Scale
hierarchical routing saves table size,reduced
update traffic
- Performance
Intra-AS,can focus on performance
Inter-AS,policy may dominate over performance
7.5 INTERNET网络层协议（ 17）
边界网关协议 BGP（ Border Gateway Protocol）
- 通过 TCP连接传送路由信息；每个 AS设定一个 BGP代言人，主干网也有 BGP代言人，由 ASBGP代言人向主干
BGP代言人发送信息。
- 采用路径向量（ path vector）算法，路由信息中记录路径的轨迹
similar to Distance Vector protocol
each Border Gateway broadcast to neighbors
(peers) entire path (I.e,sequence of ASs) to
destination
E.g.,Gateway X may send its path to dest,Z:
Path (X,Z) = X,Y1,Y2,Y3,…,Z
Fig,5-55
7.5 INTERNET网络层协议（ 18）
Suppose,gateway X send its path to peer gateway
W
W may or may not select path offered by X
cost,policy (don’t route via competitors AS),
loop prevention reasons.
If W selects path advertised by X,then:
Path (W,Z) = w,Path (X,Z)
Note,X can control incoming traffic by
controling it route advertisements to peers:
e.g.,don’t want to route traffic to Z -> don’t
advertise any routes to Z
7.5 INTERNET网络层协议（ 19）
- BGP messages:
OPEN,opens TCP connection to peer and
authenticates sender
UPDATE,advertises new path (or withdraws old)
KEEPALIVE keeps connection alive in absence of
UPDATES; also ACKs OPEN request
NOTIFICATION,reports errors in previous msg;
also used to close connection
7.5 INTERNET网络层协议（ 20）
7.5.5 无类域间路由 CIDR
（ Classless InterDomain Routing）
CIDR的提出
- Internet指数增长,IP地址即将用完，
IP is rapidly becoming a victim of its own popularity.
- 基于分类的 IP地址空间的组织浪费了大量的地址
The real villain is the class B network.
CIDR
- RFC 1519
- 基本思想：将剩余的 C类地址分成大小可变的地址空间；
- 例如，需要 2000个地址，则分配一个 2048个地址（ 8个 C
类地址）的连续地址块，而不是一个 B类地址；
7.5 INTERNET网络层协议（ 15）
- RFC 1519 改变了过去 C类地址的分配规则，将世界分成
4个区，每个区分配一块连续的 C类地址空间；
欧洲,194.0.0.0 ~ 195.255.255.255
北美,198.0.0.0 ~ 199.255.255.255
中、南美,200.0.0.0 ~ 201.255.255.255
亚太,202.0.0.0 ~ 203.255.255.255
- 路由表中增加一个 32位的掩码（ mask）域
- 最长匹配原则：路由查找时，若多个路由表项匹配成功
，选择掩码长（ 1比特数多）的路由表项；
Figure
- CIDR思想可用于所有 IP地址，没有 A,B,C类之分。
- address format,a.b.c.d/x,where x is # bits in network
portion of address
7.5 INTERNET网络层协议（ 16）
例
- Cambridge University 需要 2048个地址,194.24.0.0 ~
194.24.7.255，掩码 255.255.248.0；
Oxford University 需要 4096个地址,194.24.16.0 ~
194.24.31.255，掩码 255.255.240.0；
Edinburgh University 需要 1024个地址,194.24.8.0 ~
194.24.11.255，掩码 255.255.252.0；
- 路由表内容地址 掩码
11000010 00011000 00000000 00000000 11111111
11111111 11111000 00000000
11000010 00011000 00010000 00000000 11111111
11111111 11110000 00000000
11000010 00011000 00001000 00000000 11111111
11111111 11111100 00000000
7.5 INTERNET网络层协议（ 17）
- 一个目的地址为 194.24.17.4的包到达路由器，路由表查找过程如下：
194.24.17.4的二进制表示为
11000010 00011000 00010001 00000100
该地址与第一项 Cambridge的掩码做 AND 操作，得到
11000010 00011000 00010000 00000000
与 Cambridge的地址不同，匹配不成功；
该地址与下一项 Oxford的掩码做 AND 操作，得到
11000010 00011000 00010000 00000000
与 Oxford的地址相同，匹配成功。
继续匹配，最后选择前缀最长的路由表项
7.5 INTERNET网络层协议（ 18）
7.5.6 IPv6
IPv6的提出
- CIDR仅仅是一种临时补救措施，不能从根本上解决 IP地址空间匮乏的问题；
- 移动电话、家电上网等需要大量的 IP地址；
- 1990年,IETF开始 IPv6的工作，收到 21个建议；
- 1992年,7个建议被讨论；
- 1993年,3个比较好的建议发表在 IEEE Network上，进一步讨论、修改、结合后，形成 IPv6；
- IPv6与 IPv4不兼容，但与其它 Internet协议兼容，如 TCP、
UDP,OSPF,BGP,DNS等，但实际上还是需要开发另外一套协议栈。
7.5 INTERNET网络层协议（ 19）
IPv6的目标
- 即使在不能有效分配地址空间的情况下，也能支持数十亿的主机；
- 减少路由表的大小；
- 简化协议，使得路由器能够更快的处理包；
- 提供比 IPv4更好的安全性；
- 更多的关注服务类型，特别是实时数据；
- 支持 Multicast；
- 支持移动功能；
- 协议具有很好的可扩展性；
- 增强安全性
- 在一段时间内，允许 IPv4与 IPv6共存。
7.5 INTERNET网络层协议（ 20）
与 IPv4相比,IPv6的主要变化
- 地址变长，由 32位变成 128位；
- IP头简化，由 13个域减少为 7个域，提高路由器处理速度
由于 IPv6包头定长，取消 IHL域；
Protocol域取消，用 Next header域表示；
取消与分段有关的域,IPv6采用不同的分段方法：所有主机和路由器必须支持 576字节的包，当主机发送一个大包时，路由器不做分段，而是给主机发一个错误信息，由主机做分段；
取消 Checksum域。
- 更好的支持选项功能；
- 安全性提高；
- 更注重服务类型。
7.5 INTERNET网络层协议（ 21）
IPv6包头
- Fig,5-56
- Version，值为 6；
- Priority，用来区分源端可以流控或不能流控的包，值 0 ~ 7表示发生拥塞时源端可以降速，值 8 ~ 15表示发送速率固定的实时负载，值越小优先级越低；
- Flow label,用来允许源和目的建立一条具有特殊属性和需求的伪连接；
- Payload length，用来指示 IP包中 40字节包头后面部分的长度
，与 IPv4的 total length域不同；
- Next header，指示扩展包头，若是最后一个包头，则指示传输协议类型（ TCP/UDP）；
- Hop limit,IP包的生存时间；
- Source address,destination address,16字节定长地址
7.5 INTERNET网络层协议（ 22）
IPv6地址表示
- 16字节地址表示成用冒号（,）隔开的 8组，每组 4个 16进制位，例如，
8000:0000:0000:0000:0123:4567:89AB:CDEF
- 由于有很多,0”，有三种优化表示
打头的,0”可以省略,0123可以写成 123；
一组或多组 16个,0”可以被一对冒号替代，但是一对冒号只能出现一次。上面的地址可以表示成
8000::123,4567:89AB:CDEF
IPv4地址可以写成一对冒号和用,.”分隔的十进制数
，例如
::192.31.20.46
7.5 INTERNET网络层协议（ 23）
扩展包头
- 目前定义了六种类型的扩展包头
- hop-by-hop header，用来指示路径上所有路由器必须检查的信息；
- routing header，列出路径上必须要经过的路由器，
- fragmentation header，与 IPv4相似，扩展头中包括 IP包标识号
、分段号和判断是否还有分段的位，只有源主机可以分段；
7.5 INTERNET网络层协议（ 24）
Transition From IPv4 To IPv6
- Not all routers can be upgraded simultaneous
no,flag days” (not like Y2K):逐步完成
How will the network operate with mixed IPv4 and
IPv6 routers? 地址的兼容
- Two proposed approaches:
Dual Stack,some routers with dual stack (v6,v4)
can,translate” between formats
Tunneling,IPv6 carried as payload in IPv4
datagram among IPv4 routers
Header translation
7.5 INTERNET网络层协议（ 25）
Dual Stack Approach
7.5 INTERNET网络层协议（ 26）
Tunneling
IPv6 inside IPv4 where needed
小结
IPv4协议
- 分段与重组
- IPv4地址
ICMP协议
- ICMP报文封装在 IP包中
ARP协议
- ARP协议工作过程
RARP协议
- RARP与 BOOTP的区别
RIP
- 内部网关协议
- 距离向量算法
- 基于 UDP
OSPF
- 内部网关协议
- 链路状态算法
- 分层思想
- 四种类型路由器
BGP
- 外部网关协议
- 路径向量算法
- 基于 TCP
CIDR
- CIDR的思想
- IP地址分配和掩码配置
- 最长匹配原则
IPv6
- IPv6与 IPv4的主要区别
- IPv6地址
- 双栈模式与隧道模式移动 IP
移动 IP解决的问题
（ 1）移动主机在改变链路层接入点后，不改变 IP
仍能与其他主机通信
（ 2）其他主机不改变协议
（ 3）链路误码率较高、减少公耗等
移动 IP解决的特殊问题
（ 1） 漫游
（ 2）位置登记
（ 3）鉴权
移动 IP的传输技术
（ 1）共享无线信道
（ 2）扩频技术
（ 3）红外发射移动 IP的路由
需要解决的问题
- 为了能够将数据包转发给移动主机，网络必须首先要找到移动的主机。
网络结构示意图
7.2 路由算法（ 20）
一些基本概念
- 移动用户（ mobile users）：包括位置发生变化，通过固定方式或移动方式与网络连接的两类用户；
- 家乡位置（ home location）：所有用户都有一个永久的家乡位置，用一个地址来标识；
- 外部代理（ foreign agent）：每个区域（一个 LAN或一个
wireless cell）有一个或多个外部代理，它们记录正在访问该区域的移动用户；
- 家乡代理（ home agent）,每个区域有一个家乡代理，
负责记录家乡在该区域，但是目前正在访问其它区域的用户。
7.2 路由算法（ 21）
移动用户进入一个新区域时，必须首先向外部代理注册
- 外部代理定期广播声明自己的存在和地址的包，新到达的移动主机接收该信息；若移动用户未能收到该信息，
则移动主机广播包，询问外部代理的地址；
- 移动主机向外部代理注册，告知其家乡地址、目前的数据链路层地址和一些安全信息；
- 外部代理与移动主机的家乡代理联系，告知移动主机的目前位置、自己的网络地址和一些安全信息；
- 家乡代理检查安全信息，通过，则给外部代理确认；
- 外部代理收到确认后，在登记表中加入一项，并通知移动主机注册成功。
7.2 路由算法（ 22）
移动用户的路由转发过程
- 当一个包发给移动用户时，首先被转发到用户的家乡局域网；
- 该包到达用户的家乡局域网后，被家乡代理接收，家乡代理查询移动用户的新位置和与其对应的外部代理的地址；
- 家乡代理采用隧道技术，将收到的包作为净荷封装到一个新包中，发给外部代理；
- 家乡代理告诉发送方，发给移动用户的后续包作为净荷封装成包直接发给外部代理；
- 外部代理收到包后，将净荷作为数据链路帧发给移动用户；
- Fig,5-19
IP的传输 1 -IP over ATM
ATM引入 INTERNET的优势
（ 1）提高网络性能：速率高 622M,2.5G
（ 2）降低设备费用,10G的 ATM端口每秒可处理
2000万个 IP包，价格与每秒 200万 IP包处理能力的路由器相当
（ 3）服务质量保证
重叠模型
IP协议在 ATM网络上运行,ATM作为 IP层的低层传输链路，各自定义自己的地址和路由协议，需要服务器实现两种地址的映射（如 ARP协议）
局域网仿真定义了 ATM作为骨干网互连现有 LAN，以及现有的以太网或令牌网上主机如何在对等环境下与具有
ATM接口的主机或其他符合 ATMUNI标准的服务器等设备进行通信（图、协议栈）
集成模型将 IP路由器的智能和管理性能集成到 ATM交换中形成的一体化平台。 ATM层被看作 IP层的对等层，
ATM只需使用 IP地址，在建立连接时使用非标准的 ATM信令协议。不需要地址解析,ATM交换机象一个多协议路由器，增加了 ATM交换机的复杂性。
IP交换技术
TAG交换
IP传输 2- Ip over SDH
IP over SDH分层模型
IP over SDH的优点
（ 1）通过 PPP映射，效率高
（ 2）可兼容不同的技术和标准，实现网络互联
（ 3）采用 PPP协议，支持多协议传输
（ 4）在需要传输大量数据报较理想
IP over SDH的缺点
（ 1）不支持 VPN和电路仿真
（ 2）不能提供较好的 QOS
（ 3）需要处理庞大、复杂的路由表
IP传输技术 3-IP over DWDM
IP over DWDM分层模型
IP over DWDM优点
（ 1）效率高、容量大、成本低
（ 2）网络设计有较大的灵活性、自由度，扩容方便
（ 3）可在一根光纤中实现多媒体信息的双向传输
（ 4）降低器件成本
（ 5） DWDM采用无源器件，可靠、省电、故障率低
GFP（ Generic Framing Procedure）作为服务承载的通信协议,GFP已是 ITU－ T的规范
G.7041,GFP提供一个通用的机制，来适应流量自高层客户信息至传输网络上的传送。传输网络可以是任何类型的，例如 SONET/SDH,ITU-
T G.709（ ONT）。客户信息可以是以封包的模式
，或者恒定速率的数据或其他类型的信息模式。
路由器体系结构和关键技术
What is Routing?
R3
A
B
C
R1
R2
R4 D
E
FR5
R5F
R3E
R3D
Next HopDestination
What is Routing?
R3
A
B
C
R1
R2
R4 D
E
FR5
R5F
R3E
R3D
Next HopDestination
16 3241
Data
Options (if any)
Destination Address
Source Address
Header ChecksumProtocolTTL
Fragment OffsetFlagsFragment ID
Total Packet LengthT.ServiceHLenVer
20
by
te
s
What is Routing?
A
B
C
R1
R2
R3
R4 D
E
FR5
What a Router Looks Like
Cisco GSR 12416 Juniper M160
6ft
19”
2ft
Capacity,160Gb/s
Power,4.2kW
3ft
2.5ft
19”
Capacity,80Gb/s
Power,2.6kW
Why are Fast Routers Difficult to Make?
1,It’s hard to keep up with Moore’s Law:
- The bottleneck is memory speed.
- Memory speed is not keeping up with
Moore’s Law,
2,Moore’s Law is too slow:
- Routers need to improve faster than
Moore’s Law.
Why are Fast Routers Difficult to Make?
Speed of Commercial DRAM
1,It’s hard to keep up with Moore’s Law:
- The bottleneck is memory speed.
- Memory speed is not keeping up with Moore’s Law.
0,0 0 1
0,0 1
0,1
1
10
1 0 0
1 0 0 0
1 9 8 0 1 9 8 3 1 9 8 6 1 9 8 9 1 9 9 2 1 9 9 5 1 9 9 8 2001
A
c
c
es
s
T
im
e
(
n
s
)
Moore’s Law
2x / 18 months
1.1x / 18 months
0,1
1
10
100
1000
10000
1985 1990 1995 2000
Spe
c95Int CPU re
sults
0,1
1
10
100
1000
10000
1985 1990 1995 2000
Fib
er
C
ap
ac
ity
(G
bit
/s)
TDM DWDM
Packet processing Power Link Speed
2x / 18 months 2x / 7 months
Source,SPEC95Int & David Miller,Stanford.
Moore’s Law and Fiber Law
Router Performance Exceeds Moore’s Law
Growth in capacity of commercial routers:
- Capacity 1992 ~ 2Gb/s
- Capacity 1995 ~ 10Gb/s
- Capacity 1998 ~ 40Gb/s
- Capacity 2001 ~ 160Gb/s
- Capacity 2003 ~ 640Gb/s
Average growth rate,2.2x / 18 months.
Generic Router Architecture
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Data Hdr
Data Hdr
Data Hdr
Buffer
Manager
Buffer
Memory
Buffer
Manager
Buffer
Memory
Buffer
Manager
Buffer
Memory
Data Hdr
Data Hdr
Data Hdr
路由器体系结构的发展
单总线,单处理器
- 传统的计算机结构,处理器成为处理瓶颈
单总线,多处理器,每个接口卡上有一个处理器
,主处理器负责协调 。
- 包转发由本地处理器完成,减少总线负担
交换结构 + 专用硬件（ ASIC,FPGA,NP）
- 交换结构实现无阻塞转发
- 硬件实现对 IP包的处理和路由查找
Internet Routing Matrix
- 多结点级连，类似并行计算机
Route
TableCPU
Buffer
Memory
Line
Interface
MAC
Line
Interface
MAC
Line
Interface
MAC
Typically <0.5Gb/s aggregate capacity
First Generation Routers
Shared Backplane
Second Generation Routers
Route
TableCPU
Line
Card
Buffer
Memory
Line
Card
MAC
Buffer
Memory
Line
Card
MAC
Buffer
Memory
Fwding
Cache
Fwding
Cache
Fwding
Cache
MAC
Buffer
Memory
Typically <5Gb/s aggregate capacity
Third Generation Routers
Line
Card
MAC
Local
Buffer
Memory
CPU
Card
Line
Card
MAC
Local
Buffer
Memory
Switched Backplane
Fwding
Table
Routing
Table
Fwding
Table
Typically <50Gb/s aggregate capacity
Fourth Generation Routers/Switches
Optics inside a router for the first time
Switch Core Linecards
Optical links
100s
of metres
0.3 - 10Tb/s routers in development
路由器基本结构路由引擎
(Routing Engine)
网络接口
（Interface)
路由更新
（Update)
路由查找
（Search)
转发引擎
(Forwarding Engine)
网络接口
（Interface)
路由表
（Routing Table)
内部交换
（Switching)
控制路径
（Control Path)
数据路径
（Data Path)
控制路径
（Control Path)
网络接口
- 完成网络报文的接收和发送。
转发引擎
- 负责决定报文的转发路径。
内部交换
- 为多个网络接口以及路由引擎模块之间的报文数据传送提供高速的数据通路。
路由引擎
- 由运行高层协议（特别是路由协议）的内部处理模块组成。
路由表
- 路由表包含了能够完成网络报文正确转发的所有路由信息，它在整个路由器系统中起着承上启下的作用。
报文处理路径
路由器提供了两种不同的报文处理路径：
- 数据路径,处理目的地址不是本路由器而需要转发的报文，因此数据路径是整个路由器的关键路径，它的实现好坏直接影响着路由器的整体性能。
- 控制路径,处理目的地址是本路由器的高层协议报文，特别是各种路由协议报文。虽然控制路径不是路由器的关键路径，但是它负责完成路由信息的交互，从而保证了数据路径上的报文沿着最优的路径转发。
路由引擎
(Routing Engine)
网络接口
（Interface)
路由更新
（Update)
路由查找
（Search)
转发引擎
(Forwarding Engine)
网络接口
（Interface)
路由表
（Routing Table)
内部交换
（Switching)
控制路径
（Control Path)
数据路径
（Data Path)
控制路径
（Control Path)
数据路径的工作流程
RFC1812规定 IP路由器必须完成两个基本功能：
- 首先路由器必须能够对每个到达本路由器的报文做出正确的转发决策，决定报文向哪一个下一跳路由器转发。为了进行正确的转发决策，路由器需要在转发表中查找能够与转发报文目的地址最佳匹配的表项，这个查找过程被称为路由查找（ Route
Lookup）。
- 其次路由器在得到了正确的转发决策之后必须能够将报文从输入接口向相应的输出接口传送，这个过程被称为内部交换过程（ Switching）。
决定报文应该转发的目的地址以及相关接口路由查找通过交换结构将报文转发到输出端口内部交换接口卡 交换结构转发报文
IP Address Lookup
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Buffer
Manager
Buffer
Memory
Buffer
Manager
Buffer
Memory
Buffer
Manager
Buffer
Memory
路由查找过程示意图
headerpayload
Packet
Router
Destination
Address
Outgoing
Port
Destination Next Hop
Forwarding Table
Routing Lookup
Data Structure
65.0.0.0/8
128.9.0.0/16
149.12.0.0/19
3
1
7
IP Address Lookup
Why it’s thought to be hard:
1,It’s not an exact match,it’s a longest
prefix match,
2,The table is large,about 120,000 entries
today,and growing,
3,The lookup must be fast,about 30ns for a
10Gb/s line,
Packet Buffering
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Queue
Packet
Buffer
Memory
Queue
Packet
Buffer
Memory
Queue
Packet
Buffer
Memory
Buffer
M nager
Buffer
M nager
Buffer
M nager
Fast Packet Buffers
Example,40Gb/s packet buffer
40 byte packets
Write Rate,R
1 packet
every 8 ns
Read Rate,R
1 packet
every 8 ns
Buffer
Manager
Buffer
Memory
Use SRAM?
+ fast enough random access time,but
- too low density to store 10Gb of data.
Use DRAM?
+ high density means we can store data,but
- too slow (50ns random access time).
DRAM Buffer Memory
Packet Caches
Buffer
Manager
SRAM
Arriving
Packets
Departing
Packets12
Q
2
1234
345
123456
Small ingress SRAM
cache of FIFO headscache of FIFO tails
5556
9697
8788
57585960
899091
1
Q
2
Small ingress SRAM
1
57 6810 9
79 81011
1214 1315
5052 515354
8688 878991 90
8284 838586
9294 9395 68 7911 10
1
Q
2
DRAM Buffer Memory
b>>1 packets at a time
Switching
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Queue
Packet
Buffer
Memory
Queue
Packet
Buffer
Memory
Queue
Packet
Buffer
Memory
Data Hdr
Data Hdr
Data Hdr
1
2
N
1
2
N
N times line rate
N times line rate
Switching
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Lookup
IP Address
Update
Header
Header Processing
Address
Table
Queue
Packet
Buffer
Memory
Queue
Packet
Buffer
Memory
Queue
Packet
Buffer
Memory
Data Hdr
Data Hdr
Data Hdr
1
2
N
1
2
N
Data Hdr
Data Hdr
Data Hdr
Scheduler
0% 20% 40% 60% 80% 100%
L o a d
D
e
l
a
y
A Router with Input Queues
The best that
any queueing
system can
achieve.
0% 20% 40% 60% 80% 100%
L o a d
D
e
l
a
y
A Router with Input Queues
Head of Line Blocking
The best that
any queueing
system can
achieve.
2 2 5 8 %
Head of Line Blocking
Virtual Output Queues
0% 20% 40% 60% 80% 100%
L o a d
D
e
l
a
y
A Router with Virtual Output Queues
The best that
any queueing
system can
achieve.
