Chapter 4 Network Layer Computer Networking: A Top Down Approach 6th edition Jim Kurose, Keith Ross Addison-Wesley March 2012 A note on the use of these ppt slides: We’re making these slides freely available to all (faculty, students, readers). They’re in PowerPoint form so you see the animations; and can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously represent a lot of work on our part. In return for use, we only ask the following: If you use these slides (e.g., in a class) that you mention their source (after all, we’d like people to use our book!) If you post any slides on a www site, that you note that they are adapted from (or perhaps identical to) our slides, and note our copyright of this material. Thanks and enjoy! JFK/KWR All material copyright 1996-2012 J.F Kurose and K.W. Ross, All Rights Reserved Network Layer

Chapter 4: Network Layer Chapter goals: 理解网络层服务原理 网络层服务模型 网络层上的重要功能：转发和选路 路由器工作原理 选路算法 因特网的网络层 IP协议 ICMP协议 选路协议：RIP，OSPF，BGP Network Layer

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

网络层 作用：将报文段从发送主机传送到接收主机 每一台主机和路由器都运行网络层协议 发送主机：将传输层报文段封装到网络层分组中，发送给边缘路由器 路由器：将分组从输入链路转发到输出链路 接收主机：从边缘路由器接收分组，取出报文段交付给传输层 application transport network data link physical network data link physical application transport network data link physical Network Layer

网络层的两个主要功能 类比: 选路：从出发地到目的 地的路径规划过程 转发: 将分组从路由器的输入端口转移到合适的输出端口 转发: 在通过路口时， 从一条道路转移到另一 条道路的过程 转发: 将分组从路由器的输入端口转移到合适的输出端口 选路: 确定分组从源路 由器到目的路由器的路 径 Network Layer

选路和转发的相互作用 选路：计算转发表 转发：根据转发表转运分组 1 value in arriving packet’s header 2 3 0111 value in arriving packet’s header routing algorithm local forwarding table header value output link 0100 0101 1001 选路：计算转发表 转发：根据转发表转运分组 Network Layer

下一跳方法(next hop method) 路由表中只保留下一跳地址 各路由器的路由表须保持一致

Next-hop method

连接建立 某些网络架构还存在第3个重要的功能：建立连接 在传输分组之前，两个端系统之间建立连接（建立传输需要的状态信息） 例如：ATM，帧中继，X.25 在传输分组之前，两个端系统之间建立连接（建立传输需要的状态信息） 网络层连接 vs 传输层连接: 传输层连接：进程-进程，连接状态仅保存在端系统中 网络层连接：主机-主机，连接状态保存在源主机、目的主机及所有中间路由器上 Network Layer

网络服务模型 网络服务模型定义了分组在发送主机与接收主机之间传输时的特性。 可对分组流提供的服务 可对单个分组提供的服务 保证交付 有序交付 具有时延上界的保证交付 可对分组流提供的服务 有序交付 保证最小带宽 保证最大时延抖动（分组端到端时延的最大差异） Network Layer

Network layer service models: Guarantees ? Network Architecture Internet ATM Service Model best effort CBR ABR Congestion feedback no (inferred via loss) 无拥塞发生 yes Bandwidth none 恒定速率 最小速率 Loss no yes Order no yes Timing no yes 不同架构的网络提供的网络层服务可能不同 同一个网络也可以提供不同的网络层服务 Network Layer

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

面向连接的服务，无连接服务 两种基本的网络类型： 网络层服务 传输层服务 数据报网络：提供网络层无连接服务 虚电路网络：提供网络层面向连接服务 网络层服务 主机-主机 一个网络不能同时提供两种服务 在网络核心实现 传输层服务 进程-进程 可同时提供两种服务 在网络边缘实现 Network Layer

A connectionless packet-switched network

A connection-oriented packet switched network

虚电路（Virtual circuits） 网络层连接称为虚电路 虚电路是一条端到端路径，其行为类似于电话电路： 传输分组前建立虚电路，传输结束后拆除虚电路 每个路由器为经过它的虚电路维护状态 链路及路由器资源（带宽、缓存等）可以分配给虚电路，从而虚电路能提供可预期的网络服务。 建立虚电路的本质是预先选好源主机到目的主机的路径，此后分组仅沿选好的路径传输，是否分配资源是可选的。 每条虚电路应有标识（称虚电路号），每个分组应携带虚电路标识，表明其所属的虚电路。 Network Layer

虚电路（VC）实现 一条虚电路由以下几部分组成: 分组携带VC号，每一次转发前路由器用新的VC号替换分组中的VC号。 从源主机到目的主机的端到端路径 沿途每条链路上的VC号（VC号仅有本地意义） 沿途每个路由器中的转发表项（进入端口，进入VC号，输出端口，输出VC号） 分组携带VC号，每一次转发前路由器用新的VC号替换分组中的VC号。 Network Layer

转发表 Forwarding table in northwest router: 12 22 32 1 2 3 VC number interface number Forwarding table in northwest router: Incoming interface Incoming VC # Outgoing interface Outgoing VC # 1 12 3 22 2 63 1 18 3 7 2 17 1 97 3 87 … … … … Routers maintain connection state information! Network Layer

虚电路: 信令（signaling）协议 信令报文：专门用于建立、维护、拆除虚电路的控制报文 信令协议：交换信令报文的协议 application transport network data link physical application transport network data link physical 5. Data flow begins 6. Receive data 4. Call connected 3. Accept call 1. Initiate call 2. incoming call Network Layer

数据报网络 分组携带目的主机地址，路由器按目的地址转发分组 路由器中的转发表记录目的地址到输出链路的映射 转发表被选路模块修改，约1～5分钟更新一次 同一对主机之间传输的分组可能走不同的路径，从而可能重排序 application transport network data link physical application transport network data link physical 1. Send data 2. Receive data Network Layer

Datagram or VC network: why? Internet（数据报网络） 计算机之间交换数据 弹性服务，没有严格的时序要求 终端（计算机）具有智能 可将复杂的工作（如差错控制）推到网络边缘，以保持网络简单 数据报网络只提供最小服务 可以运行在各种链路之上 增加新服务只涉及终端 ATM（虚电路网络） 由电信网发展而来 严格的时序和可靠性要求 要求保证服务 终端无智能或很少智能 复杂工作由网络完成，以保持终端简单 Network Layer

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

路由器架构概述 路由器的两个主要功能: 选路：运行选路协议，计算转发表 转发：依据转发表，从输入链路到输出链路转发数据报 Network Layer

输入端口功能 Decentralized switching: 查表：每块线卡（line card）上都有转发表的一个镜像，查表仅在本地进行 Physical layer: 比特接收 Decentralized switching: 查表：每块线卡（line card）上都有转发表的一个镜像，查表仅在本地进行 排队: 当交换结构阻塞时，分组需在此排队 转发：将分组从输入端口转移到输出端口的过程也称交换（switch） Data link layer: 帧处理，解封装 Network Layer

三类交换结构 Network Layer

通过内存交换 第一代路由器： 现代路由器： 由传统计算机构成，选路和转发都由CPU完成 使用多端口内存连接输入端口和输出端口，控制器在端口之间传输控制消息（如存储地址） 仅适合小容量系统 Network Layer

通过总线交换 共享总线包括地址线、数据线和控制线 每个输入和输出端口都有一个接口硬件连接到总线上，每个端口被分配一个唯一的地址。 总线协议防止多个端口同时传输，比如让各个输入端口在总线上轮流广播分组。 Network Layer

通过互联网络交换 最初用于在多处理器内部连接各个处理器 在输入端口与输出端口间建立内部专用电路，多对端口间可以并行传输。 阻塞型与非阻塞型两种，阻塞型互联网络会产生阻塞。 先进设计：将分组划分成固定长度的信元（cell）送入交换结构，离开交换结构后再组装成分组。 Network Layer

输出端口 组装：（需要时）将交换结构输出的信元组装成分组 排队：若输出端口来不及发送，分组在此排队 调度：若有多个等待队列，选择一个队头分组发送 Network Layer

输入端口排队与丢包 当交换结构不能及时将输入端口的分组转移到输出端口时，输入端口处形成排队。 队头阻塞: 队头分组阻塞其后分组的转发。 当输入队列溢出时，发生丢包。 当交换结构速率至少为端口速率的n倍（n为输入端口数量）时，输入端口处不会出现排队。 Network Layer

输出端口排队与丢包 当多个输入端口同时向一个输出端口发送时，形成排队。 当输出队列满时，发生丢包。 输出端口排队是不可避免的，设置多大的输出队列是一个研究问题。 Network Layer

分组丢弃策略 弃尾（drop-tail）：队列满时，丢弃到达的分组 主动队列管理：在队列满之前就开始丢弃分组 Ramdom Early Detection（RED） 主动队列管理的一种，与TCP的拥塞控制机制一起使用 路由器在每个端口上维护输出队列的平均长度： AvgLen = (1- Weight)×AvgLen + Weight×SampleLen 当平均队列长度达到第一个阈值minth时，按照丢弃概率 p 丢弃到来的分组。 当平均队列长度达到第二个阈值maxth时，丢弃每一个到达的分组。 概率 p 是平均队列长度和上一次丢弃距当前时间的函数，分组队列长度越大，丢弃间隔越大，p也越大。

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

因特网的网络层 主机和路由器的网络层功能包括： 网络层 传输层: TCP, UDP 转发表 链路层 物理层 IP协议 选路协议 编址规则 数据报格式 数据报处理规则 选路协议 路径选择 RIP, OSPF, BGP 网络层 转发表 ICMP协议 错误报告 请求/响应路由层信息 链路层 物理层 Network Layer

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

32 bit destination IP address ver length 32 bits data (variable length, typically a TCP or UDP segment) 16-bit identifier header checksum time to live 32 bit source IP address IP协议版本号 报头长度（单位：4字节） 剩余最大跳数 （每次转发前减1） 用于分片/重组 数据报总长度 （字节） 处理载荷的上层协议 （多路分解） head. len type of service “type” of data flgs fragment offset upper layer 32 bit destination IP address Options (if any) E.g. timestamp, record route taken, specify list of routers to visit. 头部校验 how much overhead with TCP? 20 bytes of TCP 20 bytes of IP = 40 bytes + app layer overhead Network Layer

IP分片与重组 链路层帧能承载的最大数据字节数称为MTU （Max. Transmission Unit） 将数据报载荷划分为若干较小的数据块，每个数据块封装成一个独立的数据报传输 仅在目的主机上进行重组 分片: in: 一个大数据报 out: 3个较小的数据报 重组 Network Layer

与分片有关的字段 分片的报头取自原始数据报，有些字段需要修改。 与分片有关的字段： 标识：每个分片必须携带与原始数据报相同的标识。 标志位： MF（more fragments）：最后一个分片的MF=0，其余分片的MF=1 DF（don’t fragment）：DF=1表示不允许对数据报分片 偏移量：指示分片中的数据在原始数据报载荷中的位置

分片的长度 由于分片偏移量只有13比特，除最后一个分片外，其余分片的数据长度应为8字节的整倍数。 假设原始报头的长度为H，则分片的数据长度 N 应为满足以下条件的最大整数： N ≦ MTU - H N为8的倍数

分片的处理过程 根据报头长度H和输出线路的MTU，确定分片长度N 将数据报的载荷划分成长度为N的若干片段（最后一个分片可能不足N字节）。 将原始报头加到每一个分片的前面，修改报头中的以下字段： 总长度 ＝ H + 分片长度 最后一个报头的MF位置0，其余报头的MF位置1 偏移量 ＝ 分片在原始数据报载荷中的字节序号/8 计算头部检查和

分片的例子 例：要将一个长度为4000字节的IP包发送到MTU为1500字节的链路上，IP报头长度为20字节。 分片长度 N ＝ 1480字节。 原始数据报的载荷（3980字节）被分成三个分片，长度分别为1480字节、1480字节和1020字节。 分片序号 总长度 MF 偏移量 1 1500（=1480+20） 2 185（=1480/8） 3 1040（=1020+20） 370（=185+185)

Fragmentation example

Detailed fragmentation example

重组 将收到的分片重新组装成原始数据报的过程称为重组，重组在目的主机中进行： 收集分片：目的主机使用源地址和标识确定属于同一个数据报的分片 计算原始数据报长度：当MF=0的分片到达时，根据偏移字段和总长度字段计算原始数据报的总长度。 组装：按照各分片在原始数据报载荷中的偏移量重组分组。

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

IPv4编址 网络接口与IP地址： IPv4地址： 网络接口：主机或路由器与物理链路之间的边界 确切地说，每个网络接口对应一个IP地址 32比特的数，通常用点分十进制形式表示。 例如：11000001 00100000 11011000 00001001 用点分十进制形式表示为：193.32.216.9

Dotted-decimal notation TCP/IP Protocol Suite 47 47

基于类的编址（早期）

Occupation of address space TCP/IP Protocol Suite 49 49

Blocks in Class A TCP/IP Protocol Suite 50 50

Blocks in Class B TCP/IP Protocol Suite 51 51

Blocks in Class C TCP/IP Protocol Suite 52 52

The single block in Class D TCP/IP Protocol Suite 53 53

The single block in Class E TCP/IP Protocol Suite 54 54

单播地址结构 单播地址被划分成网络号和主机号两部分： 同一个物理网络上的网络接口，它们的IP地址具有相同的网络号 网络号：标识一个物理网络 主机号：标识该物理网络上的一个网络接口 同一个物理网络上的网络接口，它们的IP地址具有相同的网络号 分层的地址结构便于确定接口的位置

地址分配 因特网中的每个接口必须具有唯一的IP地址 为在因特网范围内保证IP地址的全局唯一性： 网络号由ICANN统一分配 主机号由网络管理员统一分配 建立私有网络的组织可以自己选择网络号，但同样必须保证每个网络号在私有网络内的唯一性

特殊的地址 全0或全1的网络号及主机号是特殊地址，从不分配给特定的网络接口： 网络号有效、主机号全为0的地址：保留给网络本身。 网络号有效、主机号全为1的地址：保留作为定向广播，即在网络号指定的网络中广播（仅用作目的地址） 32位全1的地址：本地广播地址，表示仅在发送节点所在的网络中广播（仅用作目的地址） 32位全0的地址：指示本机（仅用作源地址） 网络号为0、主机号有效的地址：指代本网中的主机。 形如127.xx.yy.xx的地址：保留作为回路测试，发送到这个地址的分组不输出到线路上，而是送回内部的接收端。

网络数量与地址数量 A、B、C类地址对应不同规模的网络 一个A类、B类及C类地址可提供的接口地址数： A类、B类、C类地址的个数：

Example An address in a block is given as 73.22.17.25. Find the number of addresses in the block, the first address, and the last address. Solution Following figure shows a possible configuration of the network that uses this block. 1. The number of addresses in this block is N = 232−n = 16,777,216. 2. To find the first address, we keep the leftmost 8 bits and set the rightmost 24 bits all to 0s. The first address is 73.0.0.0/8, in which 8 is the value of n. 3. To find the last address, we keep the leftmost 8 bits and set the rightmost 24 bits all to 1s. The last address is 73.255.255.255. TCP/IP Protocol Suite 59 59

Solution to above mentioned example TCP/IP Protocol Suite 60 60

子网（subnet） 管理员可以利用路由器，将一个较大的网络划分成若干较小的网络，每个网络使用一部分地址空间。 Network Layer

子网编址 从概念上说，引入子网仅略微改变了IP地址的解释： 管理员可以根据需要，选择合适的子网号长度 主机号进一步划分成子网号和主机号两部分 子网号标识网络内的一个子网，主机号标识子网中的一个网络接口 管理员可以根据需要，选择合适的子网号长度

子网掩码（subnet mask） 子网掩码用于指示IP地址中子网号与主机号的边界： 如何从IP地址中获取子网地址： 32比特的数，对应主机号的比特位均为0 点分十进制表示，如255.255.252.0 如何从IP地址中获取子网地址： 将IP地址与子网掩码做“与”运算 例如：128.10.7.1 AND 255.255.252.0 = 128.10.4.0

子网：更确切的含义 IP地址由两部分组成: 子网是什么? 子网部分（对应子网掩码中“1”的部分） 主机部分（对应子网掩码中“0”的部分） 具有相同子网地址、不需要通过路由器就可以相互到达的网络接口构成一个子网 223.1.1.1 223.1.2.1 223.1.1.2 223.1.1.4 223.1.2.9 223.1.2.2 223.1.1.3 223.1.3.27 subnet 223.1.3.1 223.1.3.2 由3个子网组成的网络 Network Layer

如何确定子网？ 将网络接口与主机或路由器分开，形成一些分离的网络岛，每个网络岛就是一个子网。 Subnet mask: /24 223.1.1.0/24 223.1.2.0/24 223.1.3.0/24 将网络接口与主机或路由器分开，形成一些分离的网络岛，每个网络岛就是一个子网。 Subnet mask: /24 Network Layer

举例 图示的系统中有6个子网 每个子网具有不同的子网地址 子网之间被路由器隔开 路由器的每个端口连接 一个子网 路由器是在子网之间转发的设备 223.1.1.2 图示的系统中有6个子网 每个子网具有不同的子网地址 子网之间被路由器隔开 路由器的每个端口连接 一个子网 路由器是在子网之间转发的设备 223.1.1.1 223.1.1.4 223.1.1.3 223.1.9.2 223.1.7.2 223.1.9.1 223.1.7.1 223.1.8.1 223.1.8.2 223.1.2.6 223.1.3.27 223.1.2.1 223.1.2.2 223.1.3.1 223.1.3.2 Network Layer

Example After subnetting, the whole network is still connected to the Internet through the same router. However, the network has used a private router to divide the network into four subnetworks. The rest of the Internet still sees only one network; internally the network is made of four subnetworks. Each subnetwork can now have almost 214 hosts. The network can belong to a university campus with four different schools (buildings). After subnetting, each school has its own subnetworks, but still the whole campus is one network for the rest of the Internet. Note that /16 and /18 show the length of the netid and subnetids. TCP/IP Protocol Suite 67 67

Figure Example of subnetworks TCP/IP Protocol Suite 68 68

The network address is the identifier of a network. Note The network address is the identifier of a network. TCP/IP Protocol Suite 69 69

Network addresses TCP/IP Protocol Suite 70 70

IP数据报转发 路由器转发数据报的两种情形： 直接交付（direct delivery）：目的路由器将数据包直接发送给目的主机（不涉及路由器）。 间接交付（indirect delivery）：中间路由器将数据包转发给另一个路由器处理。

直接交付和间接交付 如何判断使用直接交付还是间接交付？ 直接交付的实现： 间接交付的实现： 直接交付：数据包的目的地址与路由器的某一端口地址在同一个子网中（使用子网掩码计算）。 间接交付：数据包的目的地址不与路由器中的任何一个端口地址在同一个子网中。 直接交付的实现： Chapter 5 间接交付的实现： 路由器查找转发表，将数据包发送给下一跳路由器。

转发表 转发表中的路由表项有三种类型： IP使用逐跳路由： 每个表项记录一条路由，内容包括： 网络前缀路由：目的地址是一个网络而不是一个网络接口 特定主机路由：目的地址是一个特定的网络接口 缺省路由：一个默认的路由器端口，不匹配其它路由表项的数据包发送给该端口 IP使用逐跳路由： 每个路由表项只记录去往目的地址的下一跳信息，而不是一条完整的路由 每个表项记录一条路由，内容包括： 目的地址/掩码，下一跳，输出端口，…… 下一跳必须与输出端口在同一个子网中

转发表的例子

IP数据报的转发过程（主机/路由器） if D与自己的任何一个IP地址匹配 //本节点是数据报的目的节点 从数据报中提取目的IP地址 D，利用掩码计算网络前缀 N； if D与自己的任何一个IP地址匹配 //本节点是数据报的目的节点 then 将数据包交给protocol域指定的协议实体处理 else if N与自己的任何一个直连网络的地址匹配 //直接 交付 then 通过该直连网络把数据包直接交付到目的节点D else if 表中包含到D的特定主机路由 then 把数据包发送到表中指定的下一跳 else if 表中包含到网络N的一个路由 else if 表中包含一个缺省路由 then 把数据包发送到表中指定的默认路由器 else 宣告选路出错，向数据包的源地址发送一条错误报告消息

CIDR: Classless InterDomain Routing 分类编址的缺点： 只能按照三种固定的大小分配地址空间，地址浪费严重 路由表必须记录每个已分配的网络，路由表规模爆炸式增长 CIDR： 按照实际需要的地址数量分配地址空间，提高地址使用效率 允许将若干条路由聚合成一条路由，减小路由表规模

按照实际需要分配地址 举例： CIDR地址分配的原则： 网络地址的表示方法： 若一个网络需要2000个地址，可为其分配一个具有2048个连续地址的地址块。这些地址的前21位必须相同，从而可将其看成是一个具有21位网络号的网络。 CIDR地址分配的原则： 地址块的长度 L 必须是 2 的幂次 所有地址的前（32-log2L）位必须相同 网络地址的表示方法： 用掩码指示网络地址的长度，如194.24.0.0 ，255.255.248.0。 用“/长度”指示网络地址的长度，如194.24.0.0/21。

Example In classless addressing, an address cannot per se define the block the address belongs to. For example, the address 230.8.24.56 can belong to many blocks some of them are shown below with the value of the prefix associated with that block: TCP/IP Protocol Suite 78 78

机构如何获得其网络地址？ 从ISP的地址空间中分配： ISP's block 11001000 00010111 00010000 00000000 200.23.16.0/20 Organization 0 11001000 00010111 00010000 00000000 200.23.16.0/23 Organization 1 11001000 00010111 00010010 00000000 200.23.18.0/23 Organization 2 11001000 00010111 00010100 00000000 200.23.20.0/23 ... ….. …. …. Organization 7 11001000 00010111 00011110 00000000 200.23.30.0/23 Network Layer

Example An organization is granted a block of addresses with the beginning address 14.24.74.0/24. The organization needs to have 3 subblocks of addresses to use in its three subnets as shown below: ❑ One subblock of 120 addresses. ❑ One subblock of 60 addresses. ❑ One subblock of 10 addresses. Solution There are 232 − 24 = 256 addresses in this block. The first address is 14.24.74.0/24; the last address is 14.24.74.255/24. a. The number of addresses in the first subblock is not a power of 2. We allocate 128 addresses. The subnet mask is 25. The first address is 14.24.74.0/25; the last address is 14.24.74.127/25. TCP/IP Protocol Suite 80 80

Example Continued b. The number of addresses in the second subblock is not a power of 2 either. We allocate 64 addresses. The subnet mask is 26. The first address in this block is 14.24.74.128/26; the last address is 14.24.74.191/26. c. The number of addresses in the third subblock is not a power of 2 either. We allocate 16 addresses. The subnet mask is 28. The first address in this block is 14.24.74.192/28; the last address is 14.24.74.207/28. d. If we add all addresses in the previous subblocks, the result is 208 addresses, which means 48 addresses are left in reserve. The first address in this range is 14.24.74.209. The last address is 14.24.74.255. e. Figure 5.31 shows the configuration of blocks. We have shown the first address in each block. TCP/IP Protocol Suite 81 81

Figure Solution to the above mentioned example 82 82

CIDR地址分配的另一个例子 ISP有一块从194.24.0.0/16 开始的地址块 剑桥大学申请2048个地址 牛津大学申请4096个地址 爱丁堡大学申请1024个地址

采用CIDR后出现的问题 为匹配路由表项 Dest_addr/prefix_len，路由器用数据包目的地址的前prefix-len位，与Dest_addr的前prefix_len位进行比较。 采用CIDR后出现的问题： 地址前缀的长度prefix_len无法从IP地址本身得到，且不同路由表项的prefix_len可能不同，只有查找路由表项才能得到。 转发表中不同路由表项的地址前缀可能重叠，需选择前缀最长的匹配表项。 在大规模路由表中进行快速查找是一个难题

路由表更新 路由表中添加三个表项： 若路由器收到目的地址为194.24.17.4的数据包，其查表过程为： 194.24.0.0/21 （掩码：255.255.248.0 ） 194.24.8.0/22 （掩码：255.255.252.0 ） 194.24.16.0/20 （掩码：255.255.240.0 ） 若路由器收到目的地址为194.24.17.4的数据包，其查表过程为： 194.24.17.4 AND 255.255.248.0 = 194.24.16.0，与194.24.0.0不匹配 194.24.17.4 AND 255.255.252.0 = 194.24.16.0，与194.24.8.0不匹配 194.24.17.4 AND 255.255.240.0 = 194.24.16.0，与194.24.16.0匹配选择该路由项。

Longest mask matching

Simplified forwarding module in classless address

Simplified forwarding module in classful address without subnetting

Simplified forwarding module in classful address with subnetting

Forwarding based on destination address

Forwarding based on label interface and label address interface and label address 0012

路由聚合 路由表中符合聚合条件的若干条路由可以合并成一条路由： 这些路由的前缀可以聚合成一个更短的前缀（称地址前缀） 这些路由使用相同的下一跳 路由聚合的过程可以递归进行 Organization 0 200.23.16.0/23 Organization 1 “Send me anything with addresses beginning 200.23.16.0/20” 200.23.18.0/23 Organization 2 200.23.20.0/23 . Fly-By-Night-ISP . Internet Organization 7 200.23.30.0/23 “Send me anything with addresses beginning 199.31.0.0/16” ISPs-R-Us

特殊路由与最长前缀匹配 若个别路由不满足路由聚合的条件，可以给出一条聚合路由和若干条特定路由 最长前缀匹配：在所有匹配的路由表项中，选择前缀最长的路由表项 Organization 0 200.23.16.0/23 “Send me anything with addresses beginning 200.23.16.0/20” Organization 2 200.23.20.0/23 . Fly-By-Night-ISP . Internet Organization 7 200.23.30.0/23 “Send me anything with addresses beginning 199.31.0.0/16 or 200.23.18.0/23” ISPs-R-Us Organization 1 200.23.18.0/23 Network Layer

主机/路由器如何获得IP地址？ 路由器： 主机： 使用DHCP的好处： 管理员手工配置路由器各个接口的IP地址 管理员手工配置主机的IP地址 主机使用动态主机配置协议DHCP（Dynamic Host Configuration Protocol）自动获取IP地址、子网掩码、缺省路由器、本地DNS服务器等配置信息 使用DHCP的好处： 免去手工配置的麻烦（即插即用） 可用少量的IP地址服务较多的客户（地址重用） Network Layer

DHCP 目标: 允许主机加入网络时自动获取配置信息 DHCP是一个客户/服务器模式的应用协议，子网中应有一个DHCP服务器或一个DHCP代理。 A DHCP 223.1.2.1 223.1.1.1 server 223.1.1.2 223.1.1.4 223.1.2.9 B 223.1.2.2 arriving DHCP client needs address in this network E 223.1.1.3 223.1.3.27 223.1.3.1 223.1.3.2 Network Layer

DHCP概述 主机广播 “DHCP discover” 报文 DHCP服务器用 “DHCP offer” 报文进行响应 给出推荐的IP地址及租期、其它配置信息 主机用 “DHCP request” 报文请求IP地址 主机选择一个DHCP服务器，向其请求IP地址 DHCP服务器用“DHCP ack” 报文发送IP地址 响应客户的请求，确认所要求的参数 DHCP服务器使用UDP端口67，客户使用UDP端口68 Network Layer

DHCP客户-服务器交互 arriving DHCP server: 223.1.2.5 client DHCP discover src : 0.0.0.0, 68 dest.: 255.255.255.255,67 yiaddr: 0.0.0.0 transaction ID: 654 DHCP offer src: 223.1.2.5, 67 dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 transaction ID: 654 Lifetime: 3600 secs DHCP request src: 0.0.0.0, 68 dest:: 255.255.255.255, 67 yiaddrr: 223.1.2.4 transaction ID: 655 Lifetime: 3600 secs time DHCP ACK src: 223.1.2.5, 67 dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 transaction ID: 655 Lifetime: 3600 secs Network Layer

NAT: 网络地址转换 Motivation: 数据报使用形如 10.0.0.0/24的源 离开本地网络的数据报使用 地址和目的地址 rest of Internet 本地网络 (e.g., home network) 10.0.0.0/24 10.0.0.1 10.0.0.4 10.0.0.2 138.76.29.7 10.0.0.3 数据报使用形如 10.0.0.0/24的源 地址和目的地址 离开本地网络的数据报使用 相同的源IP址: 38.76.29.7 Motivation: 使用一个公用IP地址支持许多用户同时上网 仅为公共可访问的节点分配公用IP地址（减少需要的公用IP地址数） 网络内部节点对外是不可见的（安全考虑） Network Layer

NAT实现 外出的数据报: 将数据报中的（源IP地址，源端口号）替换为（NAT IP地址，新端口号） Network Layer

NAT举例 NAT转换表 因特网侧地址 本地地址 1: 主机10.0.0.1 发送数据报给 128.119.40.186, 80 因特网侧地址 本地地址 1: 主机10.0.0.1 发送数据报给 128.119.40.186, 80 2: NAT路由器将数 据报源地址 10.0.0.1, 3345改为 138.76.29.7, 5001, 更新转换表 138.76.29.7, 5001 10.0.0.1, 3345 …… …… S: 10.0.0.1, 3345 D: 128.119.40.186, 80 1 10.0.0.1 S: 128.119.40.186, 80 D: 10.0.0.1, 3345 4 S: 138.76.29.7, 5001 D: 128.119.40.186, 80 2 10.0.0.4 10.0.0.2 138.76.29.7 S: 128.119.40.186, 80 D: 138.76.29.7, 5001 3 10.0.0.3 4: NAT路由器将数据报 的目的地址138.76.29.7, 5001 改为10.0.0.1, 3345 3: 响应的数据报到达， 目的地址为: 138.76.29.7, 5001 Network Layer

NAT: Network Address Translation 16比特端口号: 允许一个NAT IP地址同时支持65535个对外连接 NAT的使用有争议: 路由器应当只处理三层以下的包头（端口号在传输层） 违反端到端原则（节点介入修改IP地址和端口号） NAT妨碍P2P应用程序：需要NAT穿越技术 Network Layer

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

ICMP: Internet Control Message Protocol 询问：用来请求一些信息，通常采用请求-响应模式交互 错误报告：发现错误的节点向源节点报告错误信息，不需响应 由于 ICMP报文可能需要经过几个网络才能到达源节点，ICMP报文被封装在IP包中传输。 ICMP通常被认为是IP协议的一部分，因为IP协议使用ICMP向源节点发送错误报告。

ICMP encapsulation

差错报告报文 ICMP的主要任务：报告差错 ICMP不能纠正错误(差错纠正交给高层协议) 差错报文发给源节点

查询 对某些网络问题进行诊断 目前尚在使用的两对查询报文 回送请求与回送应答 时间戳请求与时间戳应答

ICMP定义的报文例子 ICMP错误报告的例子： ICMP信息查询的例子： 源抑制：路由器没有缓存来容纳新到来的数据报 超时：数据报的TTL减为0，或主机的重组定时器超时 目的不可达：路由器判断一个数据报不可能到达它的最终目的地 重定向：路由器发现主机使用的路由有错或不是最佳路由 参数错误：数据报中某个参数有错 ICMP信息查询的例子： 回声请求/响应：用于发现对方是否在线 地址掩码请求/响应：用于获得本网的地址掩码 路由器请求：请求本网路由器的信息 路由器发现：路由器定期发送该消息通告自己的信息

不产生ICMP差错报文情形 对于携带ICMP差错报文的数据报，不再产生ICMP差错报文

ICMP报文格式 首部(8字节) 可变长度的数据部分 前4个字节所有类型的报文相同 后4个字节与报文类型相关 原始数据报的IP首部 该数据报数据的前8个字节：端口号(UDP,TCP)和序号(TCP)

ICMP报文格式 type：报文类型，共定义了15种 code：对某类报文作进一步的区分 Checksum：ICMP报文的检查和

校验和 在ICMP中，校验和的计算覆盖了整个报文(首部和数据)

ICMP报文类型举例 Type Code description 0 0 echo reply (ping) 3 0 dest. network unreachable 3 1 dest host unreachable 3 2 dest protocol unreachable 3 3 dest port unreachable 3 6 dest network unknown 3 7 dest host unknown 4 0 source quench (congestion control - not used) 8 0 echo request (ping) 9 0 route advertisement 10 0 router discovery 11 0 TTL expired 12 0 bad IP header Network Layer

目的节点不可达 目的节点不可达 差错报告 路由器无法为一个数据报找到路由或主机无法交付一个数据报 丢弃数据报 路由器或主机向源节点报告“目的节点不可达”

目的节点不可达种类 16种(代码0-15) 代码2、3由目的主机报告，其他类型由路由器报告

不报告目的节点不可达情形 若数据报通过以太网，路由器无法得知该数据报是否被交付(以太网不提供确认机制)

源节点抑制 当路由器或主机因拥塞而丢弃数据报时，向该数据报的源节点发送“源节点抑制”报文 作用 通知源节点数据报已被丢弃 警告源节点，在路径中的某处出现了拥塞，源节点必须放慢(抑制)发送过程

超时 数据报TTL字段值变成0 目的节点在规定的时间内没有收到一个分组的所有分片

参数问题 若路由器或目的节点发现数据报首部中的字段值出错(二义性)，丢弃该数据报 向源节点报告“参数问题”

改变路由 发送节点(主机)通常使用静态路由 当路由器收到发送节点发来的数据报，并发现存在更好的路由(即发送节点应发给另一个路由器)，路由器向发送节点发送“改变路由”报文，让发送节点更新路由表 路由器并不丢弃数据报，而是将该数据报发送给更合适的路由器

Redirection concept

Ping 与 ICMP Ping利用ICMP报文测试目的主机是否活跃，以及去往目的主机的路径是否正常： 源主机发送 Type=8，Code=0 的 Echo Request 报文 若目的主机收到，发送 Type=0，Code=0 的 Echo Response报文 源主机计算并报告RTT 若源主机连续几次超时（收不到Echo Response），向调用者报告目的不可达

Traceroute 与 ICMP Traceroute测试到达目的主机的路由（经过的路由器）： 源主机的Traceroute程序向目的主机发送一个Echo Request报文，IP报头的TTL设为1。 第一跳路由器对TTL减1，发现TTL变为0，向源主机发送一个TTL expired报文（IP报头中有路由器的IP地址）。 Traceroute记录第一跳路由器的IP地址，然后向目的主机发送第二个Echo Request报文，IP报头的TTL设为2。 若收到第二跳路由器的TTL expired报文，记录第二跳路由器的IP地址；接着发送一个TTL为3的Echo Request报文。 该过程不断重复，直至收到目的主机的Echo Response报文(使用错误端口号！)

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

IPv6 最初的动机: IPv4地址将很快耗尽 进一步的动机: IPv6与IPv4不兼容，但与其它所有因特网协议都兼容。 简化头部格式，加快数据报处理和转发 支持服务质量 支持多播 支持移动性 增强安全性 …… IPv6与IPv4不兼容，但与其它所有因特网协议都兼容。 Network Layer

IPv6地址 128位，使用冒号十六进制表示，每16位以十六进制的形式写成一组，组之间用冒号分隔，如8000:0:0:0:0123:4567:89AB:CDEF 地址表示的零压缩技术：可将连续的多组0压缩为一对冒号，如以上地址可表示为：8000::0123:4567:89AB:CDEF IPv6定义了三种地址类型： 单播地址：一个特定的网络接口 多播地址：一组网络接口 任播地址（anycast）：一组网络接口中的任意一个（通常是最近的一个）

IPv6数据报格式 IPv6数据报以一个40字节的基本头开始，后面跟零个或多个扩展头，然后是数据。

PRI（或traffic class） 作用： IPv6将网络流量划分为两大类： 发送方在该域定义数据报的优先级 路由器发现网络拥塞时，按优先级从低到高的顺序丢弃包 IPv6将网络流量划分为两大类： 受拥塞控制的流： 非实时流属于这一类，优先级0～7，按照重要性及用户体验设定 不受拥塞控制的流： 实时多媒体流属于这一类，优先级8～15，尚无标准，可以按照用户要求的服务质量等级定义

流（flow） 流是具有相同传输特性（源/目的、优先级、选项等）、并要求相同处理（使用相同的路径和资源、具有相同的服务质量和安全要求等）的一系列数据包。 流由源地址和流标签（flow label）唯一标识。流标签由发送方分配，不支持流的节点忽略该域。 支持流的路由器维护一张流表（flow table），记录每一个流需要的处理；收到数据包后，根据源地址和流标签查找流表，进行相应的处理。 流的引入使得IPv6具备了对数据包进行区分处理的能力。

扩展头部

IPv6包格式 与IPv4固定头相比，IPv6的基本头中去掉了以下一些字段： IPv6基本头中增加了： 改变了以下字段的作用： IHL：IPv6的基本头总是40字节长 与分片相关的字段：IPv6路由器不负责分片 头校验：计算校验和太花时间；现在的网络非常可靠，并且链路层和传输层上往往又都有校验和 IPv6基本头中增加了： 流标签：支持对数据包区分处理 改变了以下字段的作用： Type of Service：代之以Traffic Class 总长度：代之以载荷长度 Protocol：代之以Next header，允许任意扩展选项

IPv6的基本头与IPv4的固定头

ICMPv6 ICMPv6合并了IPv4中的ARP和IGMP，并取消了RARP（该协议的功能已被其它协议取代）。

ICMPv6 差错报告： 信息查询： 去掉了源抑制报文：优先级和流标签允许路由器控制拥塞，丢弃不太重要的数据包 增加了Packet Too Big报文：路由器丢弃长度超过MTU的包，并报告错误 信息查询： 去掉了一些不必要的查询报文 增加了一些查询报文，用于实现ARP（地址解析）和IGMP（多播组管理）的功能 Network Layer

从IPv4过渡到IPv6 因特网不可能一夜之间升级到IPv6，IPv4与IPv6如何共存？ 双协议栈方案： 源节点先查询DNS：若DNS返回IPv4地址，发送IPv4分组；若返回IPv6地址，发送IPv6分组 双栈节点同时拥有IPv4和IPv6地址 Network Layer

IPv6数据包如何穿越IPv4网络? 报头转换： IPv4/IPv6节点（如路由器B）在将数据报传递给IPv4路由器（如路由器C）之前，将IPv6报头转换成IPv4报头 缺点：报头转换不完全，有信息丢失。

IPv6数据包如何穿越IPv4网络? 建立隧道： IPv6/IPv4边界路由器将IPv6包封装到一个IPv4包中，送入IPv4网络，目的边界路由器取出IPv6包继续传输。 优点：保留原始数据报的全部信息。

建立隧道 A B E F Logical view: A B C D E F Physical view: Src:B Dest: E tunnel Logical view: IPv6 IPv6 IPv6 IPv6 A B C D E F Physical view: IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 Flow: X Src: A Dest: F data Flow: X Src: A Dest: F data Src:B Dest: E Flow: X Src: A Dest: F data Src:B Dest: E Flow: X Src: A Dest: F data A-to-B: IPv6 E-to-F: IPv6 B-to-C: IPv6 inside IPv4 D-to-E: IPv6 inside IPv4 Network Layer

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

选路问题 选路问题的描述： 给定一组路由器和连接路由器的链路，寻找一条从源路由器到目的路由器的最佳路径。

什么是最佳路径？ 应用评价一条路径的好坏可能包括： 运营商关心一些全局性指标： 路由评价指标通常是矛盾的，需要折衷。 路径长度、数据速率、分组延迟、通信费用、安全性等 运营商关心一些全局性指标： 网络吞吐量最大、平均包延迟最小、平均通信费用最低、网络负载均衡、路由稳定、健壮等 路由评价指标通常是矛盾的，需要折衷。

图抽象 z x 图: G = (N,E) N = 路由器集合= { u, v, w, x, y, z } 2 1 3 5 图: G = (N,E) N = 路由器集合= { u, v, w, x, y, z } E = 链路集合={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) } Network Layer

图抽象: 代价 z x 选路算法: 寻找从源节点到目的节点的最小代价路径 代价可以反映链路长度、延迟、 负载等各种选路算法关心的因素 u y x w v z 2 1 3 5 令c(x,x’) = 链路 (x,x’) 的代价 代价可以反映链路长度、延迟、 负载等各种选路算法关心的因素 通常考虑无向图，但实际网络中 边是有方向的（代价不同） 路径 (x1, x2, x3,…, xp) 的代价 = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp) 选路算法: 寻找从源节点到目的节点的最小代价路径 Network Layer

选路算法分类 全局算法: 静态算法: 动态算法: 分布式算法: 全局算法还是分布式算法 静态算法还是动态算法 所有路由器具有关于拓扑和链路代价的全部信息 集中式计算 分布式算法: 路由器仅知道邻居节点以及到邻居节点的链路代价 通过与邻居交换信息，进行迭代计算 静态算法还是动态算法 静态算法: 路由随时间不变或缓慢变化（手工配置） 动态算法: 路由器根据拓扑及链路代价的变化而自动更新路由 Network Layer

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

Concept of Link state routing

Link state knowledge

链路状态（LS）选路算法 基本思想： 链路状态路由算法包括以下五个步骤： 每个节点利用可靠方法获得全网拓扑信息，抽象成一个带权拓扑图，计算到各个节点的最短路径。 链路状态路由算法包括以下五个步骤： 发现邻居（有链路直接相连的节点） 探测到每个邻居的代价 将以上信息构造成链路状态（LS）分组 向所有节点发送链路状态分组 利用收到的LS分组构造网络拓扑，计算到其它节点的最短路径

Dijsktra算法 1 Initialization: 2 N’ = {u} // N’为已找到最短路径的节点集合，初始时只有u 3 for all nodes v //标记源节点u到各个节点v的路径代价D(v) 4 if v adjacent to u 5 then D(v) = c(u,v) //c(u,v)为链路(u,v)的代价 6 else D(v) = ∞ 7 8 Loop 9 find w not in N’ such that D(w) is a minimum //下一条最短路径 10 add w to N’ //将找到最短路径的节点加入N’ 11 update D(v) for all v adjacent to w and not in N’ : 12 D(v) = min( D(v), D(w) + c(w,v) ) //更新到相关节点的路径代价 13 until all nodes in N' Network Layer

Dijkstra算法举例 z x Step 1 2 3 4 5 N' u ux uxy uxyv uxyvw uxyvwz 1 2 3 4 5 N' u ux uxy uxyv uxyvw uxyvwz D(v),p(v) 2,u D(w),p(w) 5,u 4,x 3,y D(x),p(x) 1,u D(y),p(y) ∞ 2,x D(z),p(z) ∞ 4,y P(v)：在当前从u到v的最短路径上，v的前一跳节点。 u y x w v z 2 1 3 5 Network Layer

Dijkstra算法举例（续） 以u为根的最短路径树: z x u的转发表: u y w v P(v) = u P(x) = u P(y) = x P(w) = y P(z) = y u y x w v z u的转发表: v x y w z (u,v) (u,x) destination link Network Layer

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

Bellman-Ford 方程 假设 x 和 y 分别为源节点和目的节点，N(x)是x 的邻居集合，c(x,p)为 x 到其邻居 p 的链路代价，dx(y)为从 x 到 y 的最小代价路径的代价，则： dx(y) = minp{c(x,p) + dp(y)}，p∈N(x) （Bellman-Ford方程） 从选路的角度来说，方程的解 p 正是从 x 到 y的最小代价路径上的下一跳 Network Layer

Bellman-Ford方程举例 计算从u到z的最小代价路径 已知：dv(z) = 5, dx(z) = 3, dw(z) = 3 y x w v z 2 1 3 5 已知：dv(z) = 5, dx(z) = 3, dw(z) = 3 B-F equation says: du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) } = min {2 + 5, 1 + 3, 5 + 3} = 4 最小代价路径经过的邻居节点 x 即为该路径的下一跳 Network Layer

The fact behind Bellman-Ford algorithm

距离矢量（DV）算法 距离矢量算法采用Bellman-Ford方程求解任意两个节点之间的最小代价路径 距离矢量算法的贡献在于给出了分布式求解B-F方程的方法 假设： 节点 x 知道其到每个邻居 v 的链路代价 c(x,v) Dx(y) 为 x 估计的到 y 的最小代价路径的代价 令节点 x 维护自己的距离矢量 Dx = [Dx(y): y є N ] 每个邻居v的距离矢量 Dv = [Dv(y): y є N ] Network Layer

距离矢量算法（续） 基本思想: 每个节点周期性地将它的距离矢量发送给邻居 当节点 x 从其邻居收到距离矢量后，使用B-F方程更新自己的距离矢量: Dx(y) ← minv{c(x,v) + Dv(y)} Network Layer

距离矢量算法的实现 节点的本地计算由以下两种事件引起: 节点仅在发现计算的距离矢量有变化时通知其邻居 本地某条链路的代价发生了变化 收到了邻居节点的距离矢量更新 节点仅在发现计算的距离矢量有变化时通知其邻居 距离矢量算法是迭代的、异步的、分布式算法。 Each node: wait for (change in local link cost or msg from neighbor) recompute estimates if DV to any dest has changed, notify neighbors Network Layer

z y x Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3 Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2 节点x的距离矢量表 x y z x y z 0 2 7 ∞ from cost to cost to x y z x 2 3 from y 2 0 1 z 7 1 0 节点y的表 cost to x z 1 2 7 y x y z x ∞ ∞ ∞ 2 0 1 y from z ∞ ∞ ∞ 节点z的表 cost to x y z x ∞ ∞ ∞ from y ∞ ∞ ∞ z 7 1 time Network Layer

z y x Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3 Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2 节点x的距离矢量表 x y z x y z 0 2 7 ∞ from cost to cost to cost to x y z x y z x 0 2 3 x 0 2 3 from y 2 0 1 from y 2 0 1 z 7 1 0 z 3 1 0 节点y的表 cost to cost to cost to x z 1 2 7 y x y z x y z x y z x ∞ ∞ x 0 2 7 ∞ 2 0 1 x 0 2 3 y from y from 2 0 1 from y 2 0 1 z z ∞ ∞ ∞ 7 1 0 z 3 1 0 节点z的表 cost to cost to cost to x y z x y z x y z x 0 2 7 x 0 2 3 x ∞ ∞ ∞ from y from y 2 0 1 from y 2 0 1 ∞ ∞ ∞ z z z 3 1 0 3 1 0 7 1 time Network Layer

链路代价变化：好消息传播快 在时刻 t0, y 检测到链路(y,x)的代价从4变为1，更新其距离矢量为（1,0,1），发送给邻居。 z 1 4 50 y 在时刻 t1, z 收到 y 的距离矢量，更新自己 的距离矢量为（2,1,0），发送给邻居。 在时刻 t2, y 收到 z 的距离矢量，更新自己 的距离矢量，发现没有改变，不向邻居发送。 算法两次迭代就达到收敛，好消息得到迅速传播。 Network Layer

链路代价变化：坏消息传播慢 计数至无穷问题 （路由出现环） y 检测到链路(y,x)的代价从4变为60，计算Dy(x)=6，更新 DV为（6,0,1），发送。 x z 1 4 50 y 60 z 收到 y 的DV，计算 Dz(x)=7，更新DV为（7,1,0），发送。 y 收到 z 的DV，计算Dy(x)=8，更新 DV为（8,1,0），发送。 计数至无穷问题 （路由出现环） 经过44次迭代后，z计算 Dz(x)=50（不经 过y），更新 DV为（50,1,0），发送。 Y 收到 z 的DV，计算Dy(x)=51，更新DV为（51,0,1），算法收敛。 Network Layer

Two-node instability

LS算法和DV算法的比较 链路状态LS 距离矢量DV 链路状态信息在全网传播 距离矢量仅向邻居发送 每个节点仅传播可靠的信息：亲自测量的本地链路代价 节点计算的路由不传播，错误不扩散 距离矢量DV 距离矢量仅向邻居发送 节点传播的信息可能不正确：有些距离矢量是“道听途说”的 节点计算的路由要传播，会造成错误扩散 Network Layer

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

层次选路 到目前为止，我们假设： 然而 所有路由器运行的选路算法是相同的 网络是平面结构的（选路信息在全网扩散） 平面结构的网络不具有扩放性: 路由表规模，信息交换开销 网络管理员希望对于网络有更多的控制权：选路算法的选择，隐藏网络内部组织 Network Layer

自治系统（AS） 自治系统是由处于同一个管理域下的网络和路由器组成的集合 网关路由器 在一个AS内、直接连接到其它AS的路由器 每个AS被赋予一个AS编号，由ICANN分配 同一个AS中的路由器运行相同的选路协议（称Intra-AS选路协议） 不同AS中的路由器可以运行不同的Intra-AS选路协议 网关路由器 在一个AS内、直接连接到其它AS的路由器 网关路由器之间运行Inter-AS选路协议 所有AS必须运行相同的Inter-AS选路协议 Network Layer

Inter-AS tasks AS1的网关路由器必须: 了解哪些目的网络通过自己可达 假设AS1内部的路由器需发送数据报到AS1外 路由器应当向哪个网关路由器发送？ 3b 1d 3a 1c 2a AS3 AS1 AS2 1a 2c 2b 1b 3c Network Layer

… 举例: 设置路由器1d的转发表 假设AS1中的1c通过inter-AS选路协议了解到网络 x 通过AS3可达 1c将该信息传播到AS1内部的所有路由器（inter-AS协议） 路由器1d 根据intra-AS选路信息得知，其接口 I 位于到路由器1c的最小代价路径上 在转发表中安装表项 (x,I) … x 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b AS1 1d Network Layer

… … 举例: 从多个AS中选择一个 假设AS1了解到网络 x 从AS3和AS2均可达，并将这些信息传播到了AS1内部（inter-AS） 为配置转发表，路由器1d 必须确定将目的地址为 x 的数据报转发给 1c 还是 1b 这是intra-AS选路协议的工作！ … 3b 1d 3a 1c 2a AS3 AS1 AS2 1a 2c 2b 1b 3c … x Network Layer

举例: 从多个AS中选择一个（续） 假设AS1了解到网络 x 从AS3和AS2均可达，并将这些信息传播到了AS1内部（inter-AS） 为配置转发表，路由器1d 必须确定将目的地址为 x 的数据报转发给 1c 还是 1b 这是intra-AS选路协议的工作！ 热土豆选路协议: 选择最近的网关路由器 从inter-AS协议 了解到subnet x 通过多个网关 路由器可达 使用intra-AS协议确定到各网关路由器的最小代价路径 热土豆选路协议: 选择路径代价最小的网关路由器 从转发表中得知到最小代价网关的接口I，添加表项Enter (x,I) 到转发表中 Network Layer

转发表由Inter-AS和Intra-As配置 3b 1d 3a 1c 2a AS3 AS1 AS2 1a 2c 2b 1b Intra-AS Routing algorithm Inter-AS Forwarding table 3c 转发表由intra-AS和inter-AS配置： intra-AS：设置到AS内部网络的路由 inter-AS & Intra-As：设置到外部网络的路由 Network Layer

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

因特网中的选路协议 Intra-AS选路协议也称内部网关协议IGP（Interior Gateway Protocols），最常见的有: RIP（Routing Information Protocol）：较低层ISP和企业网中使用 OSPF（Open Shortest Path First）：较顶层ISP中使用 Inter-AS选路协议也称外部网关协议EGP（Exterior Gateway Protocols），目前只有： BGP: Border Gateway Protocol Network Layer

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

RIP ( Routing Information Protocol) 距离测度（代价）是跳数（hop count） 跳（hop）：相邻路由器之间的链路为一跳 路径的跳数：从源路由器到目的子网（含）经过的子网数量 一条路径的最大代价限定为15跳 从路由器A到各子网的距离： D C B A u v w x y z destination hops u 1 v 2 w 2 x 3 y 3 z 2 Network Layer

RIP通告 距离向量： RIP响应报文（RIP通告） RIP响应报文的发送： 从路由器到AS内各个子网的最短路径跳数的估计值 每个报文携带一个目的子网列表（最多包含25个子网），以及到每个目的子网的最短距离 RIP响应报文的发送： 相邻路由器之间大约每30秒交换一次RIP响应报文 RIP报文封装在UDP报文中发送，使用UDP端口520（RIP是一个应用层协议！） Network Layer

RIP举例 z w x y A D B C y B 2 z B 7 x -- 1 目的网络 下一跳路由器 到目的网络的跳数 w A 2 目的网络 下一跳路由器 到目的网络的跳数 w A 2 y B 2 z B 7 x -- 1 …. …. .... 路由器D中的选路表 Network Layer

RIP举例 w x y z A C D B y B 2 z B A 7 5 x -- 1 D收到A的RIP通告 Dest hops w 1 x 1 z 4 …. … D收到A的RIP通告 w x y z A C D B 目的网络 下一跳路由器 到目的网络的跳数 w A 2 y B 2 z B A 7 5 x -- 1 …. …. .... D中的选路表 Network Layer

路由更新算法 返回 假设收到路由器A的RIP响应报文 对RIP响应报文中通告的每个目的网络，跳数加1 对响应报文中通告的每个目的网络，重复以下步骤： 若目的网络不在选路表中 //邻居报告了一个新的子网 把通告的子网添加到选路表中 若目的网络在选路表中 若目的网络在选路表中的下一跳为A，用通告的表项替换选路表中的表项 //路径代价发生了改变 否则 若通告的跳数小于选路表中的跳数 //找到一条更近的路由 更换选路表中的表项 返回

RIP: 链路失效与恢复 若超过180秒未收到某个邻居的RIP通告，认为该邻居不可达： 令通过该邻居的路径失效（距离设为16） 采用毒性逆转解决计数至无穷问题： 若选路表中到目的网络 x 的路由是 A 通告的，则向A通告该路由时，到 x 的距离设为16（阻止A使用这条路由）。 Network Layer

Example of RIP (1)

Example of RIP (2)

Example of a domain using RIP

Example of RIP Message

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

OSPF (Open Shortest Path First) 链路代价：由管理员配置（由选路策略决定） OSPF分组： OSPF定义了5种分组类型，分别用于探测邻居、通告链路状态等 OSPF分组被封装在IP包中传输，协议号为89 路由器周期性地、或在链路状态改变时发送OSPF链路通告 OSPF协议负责OSPF链路通告在网络中的广播及可靠传输 路由器根据收到的链路通告构造链路状态数据库 路由器利用链路状态数据库及Dijkstra算法，计算以路由器为根的最短路径树 Network Layer

Types of OSPF packet

链路状态类型 链路状态类型 路由器链路 网络链路 汇总链路到网络 汇总链路到AS边界路由器 外部链路

AS内部的层次选路 Network Layer

区域（area） 一个较大的自治系统可配置为若干区域： 路由器： 一个特殊区域称为主干，所有区域必须连接到主干上 每一个区域都有区域标识，主干的区域标识为0 路由器： 区域边界路由器：连接本地区域和主干的路由器 主干路由器：主干中的路由器，可以同时是区域边界路由器 内部路由器：区域内部的路由器

分层的OSPF 去往其它区域的分组： 两个选路层次：本地区域，主干 每个区域（包括主干）运行自己的OSPF协议 区域边界路由器 将本区域的选路信息汇总（有哪些子网），通告给其它区域 将收到的其它区域的选路汇总信息（包含哪些子网）通告给本区域的内部路由器 去往其它区域的分组： 首先选路到本地区域边界路由器，在主干上选路到目的区域边界路由器，然后再选路到目的子网 Network Layer

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

AS间选路的困难与目标 因特网规模极其庞大且结构非常复杂 一个AS可能不信任来自某个AS的选路信息 一个AS可能不愿意为其它AS转发数据包 因此，AS间选路只试图找到能够到达目的网络的路由，但不试图（也不可能）找到最佳路由。

边界网关协议BGP 当一对AS同意交换选路信息时，每个AS指定一个接近AS边缘的路由器（或主机），使用BGP协议交换选路信息。 运行BGP协议的边界路由器（或主机）称为BGP speaker。 一对BGP speaker通过一条半永久的TCP连接（端口179）建立BGP会话，交换BGP报文。 （BGP是应用层协议！） BGP会话的两个端点互为BGP对等方。 Network Layer

BGP会话 不同AS的两个边界路由器之间建立的BGP会话，称为外部BGP（eBGP）会话。 一个AS可能有多个边界路由器，它们必须通过半永久TCP连接构成全连通，它们之间的BGP会话称为内部BGP（iBGP）会话。 eBGP session 3c iBGP session 2c 3a 3b 2a AS3 2b 1c AS2 1a 1b 1d AS1 Network Layer

BGP报文 BGP定义了4种类型的报文： 打开报文：BGP路由器用来启动与邻居BGP路由器的联系。 通知报文：当检测到差错或路由器打算关闭连接时，发送通知报文。 更新报文：BGP路由器使用该报文宣布新路由，以及撤销以前通告的路由。

可达性信息 可达性信息：以AS枚举形式通告的、到达目的前缀的完全路径（便于检测路径环）。 路由器收到相邻AS的路由通告，在向下一个AS发送该路由之前修改报文，将自己的标识及AS号加入到完全路径中。 边界路由器的选路表中，每个表项包含目的前缀、下一跳路由器以及到达目的前缀的AS序列。 Network Layer

以AS枚举形式通报完全路径 AS2的BGP speaker通报：128.96, 192.4.153, 192.4.32, 192.4.3可从<AS2>到达 AS1的BGP speaker收到后通报：128.96, 192.4.153, 192.4.32, 192.4.3可经路径<AS1, AS2>到达

选路信息库 BGP speaker内部的选路信息库由三部分组成： Adj-RIBs-In： 每个Adj-RIBs-In对应一个BGP对等方，保存从该BGP对等方收到的选路信息 LOC-RIB：已被该BGP speaker计算出来的最佳路由 Adj-RIBs-Out：每个Adj-RIBs-Out对应一个BGP对等方，存放准备向该BGP对等方通告的选路信息 Network Layer

BGP进程的处理过程 接收从各个BGP 对等方发来的更新报文，更新与之相对应的Adj-RIB-In（添加、替换或删除路由） 对于每一个目的前缀，从所有可达的路径中按照BGP指定的决策顺序确定一条最佳路由，装入LOC-RIB。 输出策略引擎根据出境过滤规则（由管理员定义），计算要通告给每一个BGP对等方的路由更新，放入对应的Adj-RIB-Out中。（路由聚合也在这个阶段完成） BGP进程利用Adj-RIB-Out，向每个BGP对等方发送路由更新报文。 Network Layer

Intra-AS和Inter-AS选路协议 用于在AS内部交换选路信息，如OSPF、RIP 使用某个路由测度（代价）选择到目的节点的最优路径 Inter-AS选路协议: 用于在不同的AS之间交换选路信息，如BGP 主要依据策略而不是路由测度去寻找可达路径（不追求最佳路径） Network Layer

Chapter 4: Network Layer 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Broadcast routing Multicast routing 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 Network Layer

creation/transmission 广播选路 广播：将数据包从源节点发送到所有其它节点 用N次单播实现广播（在源节点上复制分组）的缺点 低效：相同的分组在某些链路上可能重复传输 需其它机制支持：源节点需知道所有目的节点的地址 R1 R2 R3 R4 在源节点复制分组 在网络中复制分组 duplicate creation/transmission Network Layer

在网络中复制分组 理想的广播选路： 源节点不需要知道网络中其它节点的地址，只需将数据包的目的地址设置为广播地址，交给路由器，路由器负责转发到全网。（在网络中复制分组） 网络中产生的分组拷贝最少 洪泛 节点收到广播分组后，向所有邻居节点（分组到来的链路除外）发送该分组的拷贝。 缺点：在有环的网络中，广播分组在网络中无休止地循环，甚至产生广播风暴。 Network Layer

在网络中复制分组—受控洪泛 受控洪泛 目标：每个路由器仅转发它之前未转发过的广播分组 两种方法： 节点记录之前转发过的分组ID，不重复转发分组（OSPF使用此方法：源地址+分组ID）。 反向路径转发: 利用节点内部的单播路由表，节点仅转发从本节点->源节点最短路径的反向路径上到来的广播分组。 Network Layer

Reverse Path Forwarding (RPF) 基本思想： 当广播分组到达路由器时，路由器检查分组的源地址与输入端口； 用分组的源地址查找单播路由表，找到去往该源地址的输出端口； 若分组的输入端口与去往该地址的输出端口相同，则扩散该分组，否则丢弃分组。 优点： 算法合理、易于实现且开销不大 Network Layer

Reverse Path Forwarding(RPF) 在所有接口上转发分组(除了在反向网络源端最短路径的接口上) (1)idea 当一个组播分组到达路由器的一个接口时，若此接口是用于向发送者发送单播分组的接口，那么就将组播分组转发到所有其它的接口上； 否则，丢弃该分组。 (2)问题 如何知道哪个接口用于向发送者发送单播分组？ 组的建立：组播路由器广播IGMP Host Membership Query，希望加入的Host回应IGMP Host Membership Report。

Reverse Path Forwarding(RPF) 分组在何种情形下被丢弃？(不在反向路径上) 分组会被转发到哪些接口上？(除反向路径的接口) 缺点：产生一些不必要的分组复制；分组会被转发到一条不存在活动组播组成员的链路上。 原因：转发时路由器并不关心组播组成员的资格； 改进：对网络进行修剪，只保留包含组成员那些网络。 TRPB：截短的反向路径广播 RPM：反向路径组播;用于DVMRP、PIM-DM协议 TRPB (Truncated Reverse Path Broadcast) DVMRP (Distance vector Multicast Routing Protocol) PIM (Protocol Independent Multicast) DM (Dense Mode)

Reverse Path Forwarding(RPF) Reverse path forwarding. (a) A subnet. (b) a Sink tree. (c) The tree built by reverse path forwarding.

反向路径转发举例 源节点为A 粗线表示各个路由器中去 往A的最短路径 网络中产生12个分组拷贝 Network Layer

在网络中复制分组—生成树 生成树G’=(N, E’)是图G=(N,E)的一个无环连通子集 各节点仅在属于生成树的链路上转发广播分组 基于生成树的广播不会产生冗余的分组拷贝 A B G D E c F (a) 由A启动的广播 (b) 由D启动的广播 Network Layer

生成树的构造—基于核心的方法 选择一个节点作为核心（也称汇聚点） 其它节点向核心发送单播的加入报文： 路由器利用单播路由表向核心转发加入报文时，记录报文的输入端口及输出端口，这些端口就是位于生成树上的端口 当加入报文到达已在生成树上的一个节点时，报文经过的路径被添加到生成树上 A A 3 B B c c 4 2 D D F E F E 1 5 G G Stepwise construction of spanning tree (b) Constructed spanning tree Network Layer

Chapter 4: Network Layer 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Broadcast routing Multicast routing 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 Network Layer

关于多播（multicast） 多播：将分组交付给网络中的一组节点 多播组是动态的： 多播组：多播通信的所有接收者形成一个多播组（源节点可以不在多播组中） 多播地址：多播组的ID（网络层多播地址为一个D类地址） 多播分组：目的地址为多播地址的分组 多播组是动态的： 任何节点可在任何时候加入或离开一个组 多播组管理： 每个组有哪些成员？它们分别在网络中什么位置？ IGMP协议 多播选路： 构造一棵连接源节点和所有组成员节点的路径树 多播选路协议 Network Layer

单播和组播的比较 Unicast Multicast Server Router Server Router Unicast transmission sends multiple copies of data, one copy for each receiver Ex: host transmits 3 copies of data and network forwards each to 3 separate receivers Ex: host can only send to one receiver at a time Multicast transmission sends a single copy of data to multiple receivers Ex: host transmits 1 copy of data and network replicates at last possible hop for each receiver, each packet exists only one time on any given network Ex: host can send to multiple receivers simultaneously Multicast Server Router

多播组管理 IGMP协议用于将局域网中主机的组成员关系报告给本网段的多播路由器 主机或多播路由器都可以是一个组中的成员： 当主机是组成员时，表明它的一个应用进程要从该组接收多播分组 当路由器是组成员时，表明它所连接的网络上有节点要从该组接收多播分组

加入一个组 主机： 多播路由器： 每个主机维护一张应用进程与多播组的对应表 当主机上的一个进程要加入一个多播组时，向主机发送请求；若这是一个新组，主机向路由器发送加入组的报文。 多播路由器： 多播路由器维护一张各个网络接口与多播组的对应表 当某个接口上出现一个新的多播组时，多播路由器在所有其它接口上发送加入组的报文。

退出一个组 主机发现某个多播组为空时，从表中清除该组，向路由器发送退出组的报文 多播路由器收到退出报文后： 在该网络接口上发送关于该多播组的查询报文（询问是否有成员属于该组） 若在规定的时间内没有收到该多播组的任何成员关系报告，从表中清除该组，在其它网络接口上发送退出组的报文

多播选路的目标 为每个组建立多播转发树（可到达该组所有成员主机的路径树） 多播组的每个成员应当只收到一个多播分组的拷贝 非多播组的成员不能收到多播分组 从源节点到每一个组成员节点的路径必须是最佳的（最短路径）

建立多播树的两种方法 基于源的树: 组共享树: 每个多播组使用一棵树，树根为该多播组的核心。 源节点建立一棵到多播组所有成员的最短路径树，源节点S和组G的每一种组合<S,G>构成一棵树。 路由器必须有每棵<S,G>树的信息，根据多播分组的源地址及组地址确定使用哪棵多播树转发。 优点：多播分组总是使用最佳路径转发 缺点：路由器需要维护大量的多播树 每个多播组使用一棵树，树根为该多播组的核心。 源节点先将多播分组发送给核心，核心再在多播树上发送。 优点：路由器对于每个组只维护一棵多播树 缺点：多播分组使用的转发路径可能不是最佳的 Notes: 3.3 Network Layer: Multicast Routing Algorithms 3-11

基于源的树--最短路径树 MOSPF通过扩展OSPF协议实现最短路径多播选路 基本思想： 扩展链路状态，使之包含链路上的组成员关系 所有参与多播的主机在局域网上定期通报其所属的多播组（IGMP） 路由器将每条直连链路上对应的多播组集合作为链路状态在网上广播 当路由器第一次遇到某个<S,G>多播分组时，计算从源节点S到多播组G的最短路径多播树。（按需计算）

基于源的树—距离矢量多播选路 DVMRP通过扩展RIP协议实现多播选路 基本思想（广播+剪枝）： 起始时路由器并不知道网络中有哪些组，以及组成员都在什么地方 基本思想（广播+剪枝）： RPF广播：确保多播分组到达每一个局域网 路径剪枝：路由器删除不包含组成员的路径分支 S: source R1 R4 连接了组成员的路由器 R2 未连接组成员的路由器 P P R5 剪枝报文 P 多播树上的链路 R3 R6 R7

DVMRP（续） 参与多播的主机定期在局域网上通报所属的多播组，局域网上的路由器记录这些信息（IGMP）。 当路由器收到发往组G的多播分组，但它并没有从局域网上监听到组G的报告时，向上游路由器发送一个剪枝报文，上游路由器停止通过这个接口发送该组的多播分组。 如果一个路由器从它的每个下游路由器都收到剪枝报文，路由器向其上游路由器转发剪枝报文。 该过程递归进行，直至所有的无关分支都被删除，最终得到一棵<S,G>树。

组共享树--基于核心的树 选择一个路由器作为组G的核心，所有路由器知道该核心所属的组及单播IP地址。 R1 R4 连接了组成员的路由器 3 R2 未连接组成员的路由器 2 i R5 加入报文生成的路径的顺序 R3 Notes: 1. It’s always nice to see a PhD dissertation with impact. The earliest discussion of center-based trees for multicast appears to be D. Wall, “Mechanisms for Broadcast and Selective Broadcast,” PhD dissertation, Stanford U., June 1980. 3.3 Network Layer: Multicast Routing Algorithms 3-17 1 R6 R7 假设R6被选为核心

共享树的形成 希望加入多播组G的路由器S向组G的核心发送加入报文 当加入报文到达树上的某个节点或核心时，报文经过的路径被添加到树上

基于共享树的多播发送 任何一个源节点想要发送多播分组时，首先将多播分组发送给核心，核心再在多播树上发送多播分组。 多播分组如何到达核心？ 多播分组的目的地址为G 不在组G多播树上的路由器，并不知道如何转发多播地址为G的分组

基于共享树的多播发送 任何一个源节点想要发送多播分组时，首先将多播分组发送给核心，核心再在多播树上发送多播分组。 多播分组如何到达核心？ 建立隧道： 源节点将多播分组封装到一个单播分组中，单播分组的目的地址为核心的单播地址。

因特网上的多播选路协议 第一个用于因特网的多播选路协议是DVMRP 最广泛使用的因特网多播选路协议是PIM（Protocol-Independent Multicast）： 不依赖于网络中所使用的单播选路协议 PIM有两种工作模式： 稠密模式：许多或大多数路由器涉及多播选路过程，使用广播+剪枝方式建立多播树 稀疏模式：只有很小一部分路由器涉及多播选路过程，采用共享树的方法；当源节点流量很高时切换到基于源的树 Network Layer

多播分组如何穿越单播网络？ 因特网中只有一小部分路由器是多播路由器，多播路由器之间可能没有直接的链路连接。 多播分组在从一个多播路由器传递到另一个多播路由器时必须通过单播网络。 多播分组如何穿越单播网络？

多播分组如何穿越单播网络？ 因特网中只有一小部分路由器是多播路由器，多播路由器之间可能没有直接的链路连接。 多播分组在从一个多播路由器传递到另一个多播路由器时必须通过单播网络。 在多播路由器之间建立隧道：把多播分组封装在单播分组中传输。

MBONE 因特网中的多播路由器以及这些多播路由器之间的隧道构成了因特网多播骨干网，称为Multicast BONE （MBONE）。

Chapter 4: summary 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What’s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer

路由器体系结构和关键技术

What is Routing? R3 A B C R1 R2 R4 D E F R5 D D R5 F R3 E D Next Hop Destination

What is Routing? R3 A B C R1 R2 R4 D E F R5 20 bytes D 32 Data 16 32 4 1 Data Options (if any) Destination Address Source Address Header Checksum Protocol TTL Fragment Offset Flags Fragment ID Total Packet Length T.Service HLen Ver 20 bytes D D D R5 F R3 E D Next Hop Destination

What is Routing? A B C R1 R2 R3 R4 D E F R5

What a Router Looks Like Cisco GSR 12416 Juniper M160 19” 19” Capacity: 160Gb/s Power: 4.2kW Capacity: 80Gb/s Power: 2.6kW 6ft 3ft 2ft 2.5ft

Why are Fast Routers Difficult to Make? 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. 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 Moore’s Law 2x / 18 months 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. 1.1x / 18 months

Moore’s Law and Fiber Law Packet processing Power Link Speed 10000 1000 2x / 18 months 2x / 7 months 100 Fiber Capacity (Gbit/s) 10 1 1985 1990 1995 2000 0,1 TDM DWDM Source: SPEC95Int & David Miller, Stanford.

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 Data Hdr Lookup IP Address Update Header Header Processing Address Table Data Hdr Buffer Manager Buffer Memory Data Hdr Lookup IP Address Update Header Header Processing Address Table Data Hdr Buffer Manager Data Hdr Buffer Memory Data Hdr Lookup IP Address Update Header Header Processing Address Table Buffer Manager Buffer Memory

路由器体系结构的发展 单总线，单处理器 单总线，多处理器，每个接口卡上有一个处理器，主处理器负责协调。 传统的计算机结构，处理器成为处理瓶颈 单总线，多处理器，每个接口卡上有一个处理器，主处理器负责协调。 包转发由本地处理器完成，减少总线负担 交换结构 + 专用硬件（ASIC，FPGA，NP） 交换结构实现无阻塞转发 硬件实现对IP包的处理和路由查找 Internet Routing Matrix 多结点级连，类似并行计算机

First Generation Routers Shared Backplane Route Table CPU Buffer Memory Line Interface MAC Typically <0.5Gb/s aggregate capacity CPU Memory Line Interface

Second Generation Routers CPU Route Table Buffer Memory Line Card Line Card Line Card Buffer Memory Buffer Memory Buffer Memory Fwding Cache Fwding Cache Fwding Cache MAC MAC MAC Typically <5Gb/s aggregate capacity

Third Generation Routers Switched Backplane Line Card CPU Card Line Card Local Buffer Memory Local Buffer Memory CPU Line Interface Routing Table Memory Fwding Table Fwding Table MAC MAC Typically <50Gb/s aggregate capacity

0.3 - 10Tb/s routers in development Fourth Generation Routers/Switches Optics inside a router for the first time Optical links 100s of metres Switch Core Linecards 0.3 - 10Tb/s routers in development

路由器基本结构 网络接口 转发引擎 内部交换 路由引擎 路由表 完成网络报文的接收和发送。 负责决定报文的转发路径。 为多个网络接口以及路由引擎模块之间的报文数据传送提供高速的数据通路。 路由引擎 由运行高层协议（特别是路由协议）的内部处理模块组成。 路由表 路由表包含了能够完成网络报文正确转发的所有路由信息，它在整个路由器系统中起着承上启下的作用。

报文处理路径 路由器提供了两种不同的报文处理路径： 数据路径：处理目的地址不是本路由器而需要转发的报文，因此数据路径是整个路由器的关键路径，它的实现好坏直接影响着路由器的整体性能。 控制路径：处理目的地址是本路由器的高层协议报文，特别是各种路由协议报文。虽然控制路径不是路由器的关键路径，但是它负责完成路由信息的交互，从而保证了数据路径上的报文沿着最优的路径转发。

数据路径的工作流程 RFC1812规定IP路由器必须完成两个基本功能： 首先路由器必须能够对每个到达本路由器的报文做出正确的转发决策，决定报文向哪一个下一跳路由器转发。为了进行正确的转发决策，路由器需要在转发表中查找能够与转发报文目的地址最佳匹配的表项，这个查找过程被称为路由查找（Route Lookup）。 其次路由器在得到了正确的转发决策之后必须能够将报文从输入接口向相应的输出接口传送，这个过程被称为内部交换过程（Switching）。

IP Address Lookup Buffer Manager Buffer Manager Buffer Manager Update Header Header Processing Address Table Buffer Manager Lookup IP Address Address Table Buffer Memory Header Processing Buffer Manager Lookup IP Address Update Header Address Table Buffer Memory Lookup IP Address Update Header Header Processing Address Table Buffer Manager Buffer Memory

路由查找过程示意图 Router Packet payload header Routing Lookup Data Structure Destination Address Routing Lookup Data Structure Outgoing Port Forwarding Table Destination Next Hop 65.0.0.0/8 3 128.9.0.0/16 1 149.12.0.0/19 7

IP Address Lookup Why it’s thought to be hard: It’s not an exact match: it’s a longest prefix match. The table is large: about 120,000 entries today, and growing. The lookup must be fast: about 30ns for a 10Gb/s line.

Packet Buffering Queue Packet Buffer Manager Queue Packet Queue Packet Lookup IP Address Update Header Header Processing Address Table Queue Packet Buffer Manager Memory Buffer Memory Lookup IP Address Update Header Header Processing Address Table Queue Packet Buffer Memory Lookup IP Address Update Header Header Processing Address Table Queue Packet Buffer Memory

Example: 40Gb/s packet buffer Fast Packet Buffers Example: 40Gb/s packet buffer 40 byte packets Write Rate, R Buffer Manager Read Rate, R 1 packet every 8 ns 1 packet every 8 ns Buffer Memory How fast? Get into the motivation – say OC768 line rate buffering is a goal. - Just mention directly the amount of buffering required. Why is it not possible today? Why is it intersting…. Talks abut SRAM/DRAM. 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).

Packet Caches Buffer Manager SRAM DRAM Buffer Memory Small ingress SRAM cache of FIFO heads cache of FIFO tails 55 56 96 97 87 88 57 58 59 60 89 90 91 1 Q 2 5 7 6 8 10 9 11 12 14 13 15 50 52 51 53 54 86 82 84 83 85 92 94 93 95 DRAM Buffer Memory Buffer Manager SRAM Arriving 4 3 2 1 Departing 2 Packets 5 4 3 2 1 Packets Q 6 5 4 3 2 1 b>>1 packets at a time DRAM Buffer Memory

Switching Data Hdr 1 1 2 2 N times line rate N times line rate N N Lookup IP Address Update Header Header Processing Address Table Data Hdr 1 1 Queue Packet Buffer Memory Lookup IP Address Update Header Header Processing Address Table 2 2 N times line rate Queue Packet Buffer Memory N times line rate Lookup IP Address Update Header Header Processing Address Table N N Queue Packet Buffer Memory

Switching Scheduler Data Hdr Data Hdr 1 2 N Data Hdr Queue Packet Lookup IP Address Update Header Header Processing Address Table Data Hdr Queue Packet 1 2 N Buffer Memory Lookup IP Address Update Header Header Processing Address Table Data Hdr Queue Packet Buffer Memory Scheduler Lookup IP Address Update Header Header Processing Address Table Queue Packet Buffer Memory

A Router with Input Queues The best that any queueing system can achieve.

A Router with Input Queues Head of Line Blocking The best that any queueing system can achieve.

Head of Line Blocking

Virtual Output Queues

A Router with Virtual Output Queues The best that any queueing system can achieve.