32 bit destination IP address 32 bits 数据报长度 (bytes) 首部长度 (bytes) head. len type of service ver length 用于 分包/ 重装 数据“类型” fragment offset 16-bit identifier flgs 余留步跳 (在经过 每个路由器后递减) time to live upper layer Internet checksum 32 bit source IP address 用来递交有效负荷的 上层协议 32 bit destination IP address Options (if any) E.g. 时间戳,纪录路 由标记, 定义要访问 的路由器 data (可变长度, 一般为一个 TCP 或UDP 数据段)

IP 分包 & 重组 较大的IP分组在网络中会被分割(“fragmented”) 网络链路具有 MTU (最大传输单位)属性 – 是有链路层最大帧的限制决定的. 不同类型的链路, 不同的 MTUs 较大的IP分组在网络中会被分割(“fragmented”) 一个分组就被分成了若干分组 分组只是在最终的信宿站点被重新“组装-reassembled” 在IP 分组的首部有些位标记用来确认和排序相关的组“片” fragmentation: in: one large datagram out: 3 smaller datagrams reassembly

IP 分片和重组 ID =x offset =0 fragflag length =4000 一个大的分组被划为若干较小的分组 ID =x =1 length =1500 ID =x offset =1480 fragflag =1 length =1500 ID =x offset =2960 fragflag =0 length =1040

ICMP: 因特网控制报文协议(Internet Control Message Protocol) 用于主机、路由器、网关之间交换网络层信息 报告错误: unreachable host, network, port, protocol 进行request/reply 应答(ping命令) 同处于网络层但“凌驾”于 IP之上: ICMP报文需要 IP分组来传输 ICMP 报文: type, code plus first 8 bytes of IP datagram causing error 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

因特网中的路由选择 全球因特网是由诸多 Autonomous Systems (AS)互联而成: 两层路由选择: 小型自治系统（Stub AS）: 中小型企业 分区自治系统（Multihomed AS）:大型企业 (非跨越的) 跨越式自治系统（Transit AS）: NBP等 两层路由选择: Intra-AS: 由网管决定 Inter-AS: 唯一性的标准

因特网的AS层次 Inter-AS 边界 (外部网关) 路由器 Intra-AS 内部 (网关) 路由器

Intra-AS路由选择 也称为内部网关协议 Interior Gateway Protocols (IGP) 最常用的 IGP有: RIP: Routing Information Protocol(路由选择信息协议) OSPF: Open Shortest Path First(开放式最短路径优先（协议）) IGRP: Interior Gateway Routing Protocol (内部网关路由选择协议，Cisco产权)

RIP ( Routing Information Protocol) 距离向量算法(Distance vector algorithm) 含在BSD-UNIX 1982版中 距离的度量单位: # of hops (max = 15 hops) Can you guess why? 距离向量: 通过Response报文每隔30秒交换一次 (也称为 广告-advertisement) 每次广告: 发布最多为 25 信宿的路由

RIP (Routing Information Protocol) z w x y A D B C Destination Network Next Router Num. of hops to dest. w A 2 y B 2 z B 7 x -- 1 …. …. .... 路由器D中的路由表

RIP: 链路失效和恢复 如果某条链路在180秒内没有被听到广告 --> 相邻结点/链路被申明取消(declared dead) 经由该结点的路由被终止 新的广告送往所有其他相邻结点 其他相邻结点依次发出新的广告 (如果路由表发生变化) 这样链路失效的信息迅速传遍整个网络 使用抑毒措施来防止乒乓循环 (设置有限距离 = 16 hops)

RIP路由表处理 RIP路由表通过应用层的进程 route-d (daemon-守护程序)来管理 由应用层进程管理的路由表为通过UDP的广告调用, 并周期性重复

RIP 路由表举例 Router: giroflee.eurocom.fr Destination Gateway Flags Ref Use Interface -------------------- -------------------- ----- ----- ------ --------- 127.0.0.1 127.0.0.1 UH 0 26492 lo0 192.168.2. 192.168.2.5 U 2 13 fa0 193.55.114. 193.55.114.6 U 3 58503 le0 192.168.3. 192.168.3.5 U 2 25 qaa0 224.0.0.0 193.55.114.6 U 3 0 le0 default 193.55.114.129 UG 0 143454 连接3个 C 类网络 (LAN) 路由器仅仅知道所连LAN的路由 默认路由器(Default router)用于 “go up(上行)” 组播地址路由(Route multicast address): 224.0.0.0 回授接口(Loopback interface ,for debugging)

OSPF (Open Shortest Path First) 开放式最短路径优先（协议） 使用链路状态算法(Link State algorithm) LS 分组传播 在每个结点存放网络的拓扑图 路由计算使用Dijkstra算法 OSPF 广告为每个相邻的路由器配置一个条目 广告弥散到 整个 AS (via flooding-泛洪法)

OSPF “先进”性 (RIP所不具备的) 安全性: 所有的 OSPF 报文须经认证 (以防止各种可能的攻击); 使用TCP连接 对每条链路来说, 对不同的TOS (eg, 在卫星链路上将尽力而为的服务设成“低值”; 而将实时应用设成高值)可产生多种成本计算标准 多种成本计算标准可以支持集成化的单播和组播(multicast) : 组播 OSPF (MOSPF)使用与 OSPF相同的拓扑数据库 在大型域中可以使用层次型OSPF

层次型OSPF

层次型OSPF 双层结构: 本地, 主干. 链路状态只是在本地范围内广告 每个结点具有详细的本地拓扑; 对其他区域中的网络仅知在某个方向 (最短路径) . 区界路由器(Area border routers): “汇总”了所在区域中到达各网络的距离,同时向其他区界路由器发广告. 主干路由器(Backbone routers): 仅限于在主干上运行 OSPF 路由算法. 边界路由器(Boundary routers): 连接其他的AS.

IGRP (Interior Gateway Routing Protocol)内部网关路由选择协议 CISCO产权; RIP 的后继者之一(mid 80s) 路由向量算法, 类似 RIP 采用若干成本计算标准 (delay, bandwidth, reliability, load etc) 使用TCP交换路由更新信息 通过基于扩散计算的分布式更新算法(DUAL) 产生无循环的路由选择

Inter-AS路由选择

因特网inter-AS路由选择: BGP BGP (Border Gateway Protocol，边界网关协议): 事实上的标准 路径向量(Path Vector) 协议: 与距离向量协议类似 每个边界网关(Border Gateway)向其对等的相邻实体(peers)广播通往信宿的整条路经 (I.e, 一系列 ASs) E.g., 网关 X可以发送从它通往信宿Z的路经: Path (X,Z) = X,Y1,Y2,Y3,…,Z

因特网inter-AS路由选择: BGP 假设: 网关X向对等网关W发送了它存有的路经 W 可以选择或不选择X所提供的路经 Path (W,Z) = w, Path (X,Z) 注意: X 可以通过向其他对等实体发布路由信息来控制所进入的通信流量: e.g., 不让路由通过Z -> 不要发布有关通向 Z的广告

因特网inter-AS路由选择: BGP BGP 使用 TCP交换报文. BGP报文: OPEN: 打开通往对等实体的 TCP连接并对发送者进行认证 UPDATE: 刊出新的路经 (或撤销旧路经) KEEPALIVE : 在不进行UPDATES时保持连接的激活; 也用来ACKs OPEN 请求 NOTIFICATION: 报告先前报文的错误;也用来关闭连接

为什么 Intra- 和 Inter-AS路由选择不同 ? 策略: Inter-AS: 网管需要控制自己信息流通的路经, 还有谁能路经并通过其管辖的网络. Intra-AS: 单一的管理体制, 无需选择策略 规模: 层次型路由选择可以缩小路由表, 并减少更新流量 性能: Intra-AS: 将注意力集中在性能上 Inter-AS: 策略的考虑要超过对性能的要求

路由器结构概述 路由器的两个关键功能: 运行路由算法/协议 (RIP, OSPF, BGP) 交换分组于输入链路到输出链路之间

输入端口功能 分散化的交换: 物理层: 位流级的接收 数据链路层: 按照给出的分组信宿，使用输入端口的内存中存储的路由选择表，查找输出端口 目标: 以“线路速度”完成输入端口的处理 排队: 假如分组到达的数度快于转发到交换网络的（ switch fabric）速度时 数据链路层: e.g., Ethernet

输入端口上的排队 交换网络的处理速度低于所有输入端口之和 -> 导致分组在输入端口的队列中排队 排头（Head-of-the-Line (HOL)）阻塞: 在队列的排头上的分组挡住了其他分组的前移 由于输入缓存的溢出导致了排队延迟和数据丢失!

三类交换网络

内存交换（Switching Via Memory） 第一代路由器: 分组通过系统的（单个）CPU拷贝 速度受到内存带宽的限制 (每个分组需2次穿越系统总线) Input Port Output Memory System Bus 现代路由器: 输入端口处理器执行查询路由表、和拷贝的功能 Cisco Catalyst 8500

总线交换（Switching Via Bus） 分组通过一条共享的总线从输入端口的内存传递到输出端口的内存 总线竞争: 交换速率受限于总线的带宽 1 Gb/s总线, Cisco 1900: 对访问接入和企业级的路由器已经足够 (但还不适应在区域或主干级线路上使用)

通过内联网络交换（Switching Via An Interconnection Network） 克服了总线带宽的限制 Banyan networks, 内联网络技术在发展初期是用来连接多处理器系统中的处理器的 设计先进: 把分组分割成固定长度的单元, 再把这些单元送入交换网络 Cisco 12000: 通过内联网络交换速度为若干Gb/s

输出端口 缓存 当来自交换网络的分组到达速度高于传输速率时，需要进行缓存 调度原则 从队列中的分组中选择传输

输出端口的排队 当交换速度超过输出线路的速率时，需要进行缓存 输出端口的溢出会造成排队（延迟）和数据丢失!

IPv6 初始的动机: 32-bit 的地址空间预计在2008将全部分配出去. 其他动机: IPv6 分组格式: 改革首部格式帮助加速处理/转发 改革首部实现 QoS 新型 “任意播-anycast”地址的实现: 实现在若干备份服务器中寻求 “最佳”路由 IPv6 分组格式: 固定长度的40 byte首部 不支持分组分割

IPv6 首部 Priority: 确定数据流中分组的优先级 Flow Label: 确认同一“flow”中的分组 Next header: 定义用来传送数据的上层协议

其他不同于 IPv4的修改 Checksum: 完全取消，以减少每个步跳上的处理时间 Options: 允许使用, 但不再是首部的内容, 而是由 “Next Header” 字段说明 ICMPv6: ICMP的新版本 新增报文类型， e.g. “Packet Too Big” 组播管理功能

由 IPv4 向IPv6的迁移 并不是所有的路由器都能够在同一时刻升级 两种建议的途径: 不能采用 “易帜日”的办法 双栈(Dual Stack): 某些具有双栈 (v6, v4)的路由器 可以将两种地址格式进行 “翻译-translate” 隧道(Tunneling): IPv6可以作为IPv4的负荷(payload)通过IPv4的路由器

双栈(Dual Stack)方式

隧道(Tunneling) 在必要时将IPv6藏入 IPv4

网络层组播的路由选择 因特网的TCP,IP协议实际上解决的是点对点的数据传输，也称为单播(unicast) 在网络中存在大量的应用需要解决一个或多个发送方须将数据发送到一组接收方 一个网络软件的升级 流媒体的发送（网上实况转播） WWW的镜像站点的更新 此类应用的抽象称为多播或组播(Multicast)

网络层组播的路由选择 实现网络组播的两种基本途径 由发送端发送多个单播给不同的接受方 在网络层增加对多播的技术支持 +不必修改因特网网络层的现行结构 -不可能改善网络的流量状况 在网络层增加对多播的技术支持 +可以更有效的利用网络带宽（只需在链路上发送一份拷贝） -实现具有多播功能的网络层需要做大量的技术改进

网络层的组播 在多播通信中，我们面临两个严重的问题，而在单播通信中这些问题是不存在的 如何确认多播分组的接受方 如何给多播分组编址 在单播通信中，IP分组中的地址指明了唯一的接受方，但在多播分组中是否可以通过增加接收方的地址来解决 即使这个方案可行，也只能满足少量的用户，如果有成千个接受方，IP的数据承载空间就会让地址蚕食掉

网络层的组播 显式的定义接受方，发送方就需要接受方的身份和地址 因此，在因特网和ATM网络中，使用了地址间接（address indirection）的方法，也就是一组用户使用唯一性的单一的标识。多播的分组使用该标识将分组传到所有加入该组的接收方 在因特网中，专门保留了一类地址（Class D）用来处理多播，称为多播组（multicast group）

网络层组播的示意 128.59.16.20 128.119.40.186 128.34.108.63 Mcast group 226.17.30.197 128.34.108.60

网络层组播的工程问题 这里要说明的是，多播地址和主机地址的“两张皮”的问题必须要解决 虽然多播问题的抽象很简单，但会出现成堆的问题： 何时成组，何时撤销？ 如何选择组地址？ 无论作为发送方或者是接受方，新主机如何加入多播组？ 入组是否来去自由，或由谁来控制？ 在因特网中这些问题的解决需要由IGMP来完成

IGMP, Internet Group Management Protocol v2 [RFC 2236] 该协议在主机和其直接连接的路由器之间进行交互 IGMP为需要加入多播的主机提供了一种手段，通过这种手段，主机可以申请加入多播组 当然还需要其他协议，来协调所有的路由器将多播分组穿越网络到达信宿 这些协议通过网络层多播路由选择算法来完成相应的功能(PIM,DVMRP,MOSFP)

IGMP的工作范围 IGMP Wide area Multicast routing

IGMP报文工作过程 IGMP报文类型 Membership query: general Membership query: specific Membership report Leave group 发送方 路由器 主机 目的 查询加入多播组的主机 查询加入多播组的特定主机 报告申请或已经加入多播组 报告推出特定的多播组 Query report

组播的路由选择问题 A B C D E F

组播的路由选择问题 A A B B C C D D E F E F A single,share tree 多播分组仅沿粗线传递链路为双向的 Two source-based trees 按发送端来组建路由选择树 某些链路可能只是单向传输

因特网的多播路由选择 DVMRP:Distance Vector Routing Protocol MOSPF:Multicast Open Shortest First CBT:Core-Based Trees PIM:Protocol Independent Multicast 现实的问题是，因特网中具有多播功能的路由器是极少数，如果某个多播路由器处于“孤岛”状态，它将如何进行工作 用“隧道方案”加以解决

因特网的多播路由选择 DVMRP:在因特网中得到广泛应用 MOSPF:在一个使用OSPF的AS内部运行 使用基于信源树(source-based tree)方案 实现了反向路径转发(reverse path forwarding) 实现了路径的嫁接,修剪 MOSPF:在一个使用OSPF的AS内部运行 扩展了OSPF,在链路状态广告中加入了多播组信息 所有路由器不仅了解网络拓扑,而且知道网络边缘路由器上多播组

因特网的多播路由选择 CBT:在一个核心(core)的基础上,实现双向,同组共享的路由树 PIM:独立于网络层的协议,分成两种实现模式 紧密型(dense mode),泛洪+修剪+RPF 松散型(spare mode),基于核心的模式

Inter-AS 的多播路由 上述的多播讨论是基于使用同样的多播协议 但在不同的AS之间可能采用的多播协议不同 DVMRP目前是事实上(de facto)的Inter-AS 的多播路由协议,但对因特网上松散的入组用户并不适宜 这个领域的工作尚在进行…

本讲小结 网络层的服务 路由选择原理 分层的路由选择 IP协议 因特网的路由选择协议 路由器组成原理 IPv6 组播的路由选择 域内路由选择 域间路由选择 路由器组成原理 IPv6 组播的路由选择 因特网的网络层现状: 无带宽承诺 无实时性保障 无QoS 有待于逐步改进