- 从发送主机向接收主机传送数据段
- 发送主机：将数据段封装到数据报中
- 接收主机：向传输层交付数据段
- 每个主机和路由器都运行网络层协议
- 路由器检验所有穿越它的IP数据报的头部域
- 决策如何处理IP数据报
- 转发：将分组从路由器的输入端口转移到合适的输出端口
- 转发表确定在本路由器如何转发分组
- 路由：确定分组从源到目的经过的路径
- 路由算法
- 某些网络的重要功能：
- ATM，帧中继， X.25
- 数据分组传输之前两端主机需要首先建立虚拟/逻辑连接
- 网络设备(如路由器)参与连接的建立
- 网络层连接与传输层连接的对比：
- 网络层连接：两个主机之间(路径上的路由器等网络设备参与其中)
- 传输层连接：两个应用进程之间(对中间网络设备透明)
- 无连接服务
- 不事先为系列分组的传输确定传输路径
- 每个分组独立确定传输路径
- 不同分组可能传输路径不同
- 数据报网络
- 连接服务
- 首先为系列分组的传输确定从源到目的经过的路径(建立连接)
- 然后沿该路径(连接)传输系列分组
- 系列分组传输路径相同
- 传输结束后拆除连接
- 虚电路网络
- 数据报网络与虚电路网络是典型两类分组交换网络
- 数据报网络提供网络层无连接服务
- 虚电路网络提供网络层连接服务
- 类似于传输层的无连接服务(UDP)和面向连接服务(TCP)，但是网络层服务：
- 主机到主机服务
- 网络核心实现
- 虚电路：一条从源主机到目的主机，类似于电路的路径(逻辑连接)
- 分组交换
- 每个分组的传输利用链路的全部带宽
- 源到目的路径经过的网络层设备共同完成虚电路功能
- 通信过程：
- 呼叫建立->数据传输->拆除呼叫
- 每个分组携带虚电路标识(VCID)，而不是目的主机地址
- 虚电路经过的每个网络设备(如路由器)，维护每条经过它的虚电路连接状态
- 链路、网络设备资源(如带宽、缓存等)可以面向VC进行预分配
- 预分配资源 = 可预期服务性能
- 如ATM的电路仿真
- 每条虚电路包括：
- 从源到目的主机的一条路径
- 虚电路号(VCID)，沿路每段链路一个编号
- 沿路每个网络层设备(如路由器)，利用转发表记录经过的每条虚电路
- 沿某条虚电路传输的分组，携带对应虚电路的VCID，而不是目的地址
- 同一条VC，在每段链路上的VCID通常不同
- 路由器转发分组时依据转发表改写/替换虚电路号
- VC路径上每个路由器都需要维护VC连接的状态信息
- 用于VC的建立、维护与拆除
- 路径选择
- 应用于虚电路网络
- 如ATM、帧中继网络等
- 目前的Internet不采用
- 网络层无连接
- 每个分组携带目的地址
- 路由器根据分组的目的地址转发分组
- 基于路由协议/算法构建转发表
- 检索转发表
- 每个分组独立选路
- 路由算法(协议)确定通过网络的端到端路径
- 转发表确定在本路由器如何转发分组
- 在检索转发表时，优先选择与分组目的地址匹配前缀最长的入口
- Internet(数据报网络)
- 计算机之间的数据交换
- “弹性”服务，没有严格时间需求
- 链路类型众多
- 特点、性能各异
- 统一服务困难
- “智能”端系统(计算机)
- 可以自适应、性能控制、差错恢复
- 简化网络，复杂“边缘”
- 计算机之间的数据交换
- ATM(VC网络)
- 电话网络演化而来
- 核心业务是实时对话：
- 严格的时间、可靠性需求
- 需要有保障的服务
- “哑”端系统(非智能)
- 电话机
- 传真机
- 简化“边缘”，复杂网络
- 主机、路由器网络层主要功能
- 路由协议
- 路径选择
- RIP、OSPF、BGP
- IP协议
- 寻址规约
- 数据报(分组)格式
- 分组处理规约
- ICMP协议
- 差错报告
- 路由器“信令”
- 路由协议
- 版本号字段占4位：IP协议的版本号
- 4 -> IPv4, 6 -> IPv6
- 首部长度字段占4位：IP分组首部长度
- 以4字节为单位
- 5 -> IP首部长度为20(5 * 4)字节
- 服务类型(TOS)字段占8位：指示期望获得哪种类型的服务
- 1998年这个字段改名为区分服务
- 只有在网络提供区分服务时使用
- 一般情况下不使用，通常IP分组的该字段(第2字节)的值为00H
- 总长度字段占16位：IP分组的总字节数(首部+数据)
- 最大IP分组的总长度：65535B
- 最小的IP分组首部：20B
- IP分组可以封装的最大数据：65535-20=65515B
- 生存时间字段占8位：IP分组在网络中可以通过的路由器数(或跳步数)
- 路由器转发一次分组，TTL减1
- 如果TTL=0，路由器则丢弃该IP分组
- 协议字段占8位：指示IP分组封装的是哪个协议的数据包
- 实现复用/分解
- 6 -> TCP，表示封装的为TCP段；17 -> UDP，表示封装的是UDP数据报
- 首部校验和字段占16位：实现对IP分组首部的差错检测
- 计算校验和时，该字段置全0
- 采用反码算数运算求和，和的反码作为首部校验和字段
- 逐跳计算、逐跳校验
- 源IP地址、目的IP地址字段各占32位：分别标识发送分组的源主机/路由器(网络接口)和接收分组的目的主机/路由器(网络接口)的IP地址
- 选项字段占长度可变，范围在1~40B之间：携带安全、源选路径、时间戳和路由记录等内容
- 实际上很少被使用
- 填充字段占长度可变，范围在0~3B之间：目的是补齐整个首部，符合32位对齐。即保证首部长度是4字节的倍数
- 网络链路存在MTU(最大传输单元)——链路层数据帧可封装数据的上限
- 不同链路的MTU不同
- 大IP分组向较小MTU链路转发时，可以被“分片”
- 1个IP分组分为多片IP分组
- IP分片到达目的主机后进行“重组”
- IP首部的相关字段用于标识分片以及确定分片的相对顺序
- 标识字段占16位：标识一个IP分组
- IP协议利用一个计数器，每产生IP分组计数器加1，作为该IP分组的标识
- 标志位字段占3位：(保留， DF， MF)
- DF，禁止分片
- MF，更多分片
- DF=1：禁止分片;DF=0，允许分片
- MF=1：非最后一片;MF=0：最后一片(或未分片)
- 片偏移字段占13位：一个IP分组分片封装原IP分组数据的相对偏移量
- 片偏移字段以8字节为单位
- 假设原IP分组总长度为L，待转发链路的MTU为M
- 若L>M，且DF=0，则可以/需要分片
- 分片时每个分片的标识复制原IP分组的标识
- 通常分片时，除最后一个分片，其他分片均分为MTU允许的最大分片
- 一个最大分片可封装的数据应该是8的倍数，因此，一个最大分片可封装的数据为：d=floor((M - 20) / 8) * 8
- 需要的总片数为：n = ceil((L - 20) / d)
- 每片的片偏移字段取值为：Fi = (d / 8) * (i - 1), (1 <= i <= n)
- 每片的总长度字段为：除最后一片都是d+20，最后一片是L-(n-1)d
- 每片的MF标志位为：除最后一片外全部取1
- IP分组：
- 源地址——从哪儿来
- 目的地址——到哪去
- 接口：主机/路由器与物理链路的连接
- 实现网络层功能
- 路由器通常有多个接口
- 主机通常只有一个或两个接口(有线的以太网接口，无线的802.11接口)
- IP地址：32比特(IPv4)编号标识主机、路由器的接口
- IP地址与每个接口关联
- IP地址：
- 网络号——高比特位
- 主机号——低比特位
- IP子网：
- IP地址具有相同网络号的设备接口
- 不跨越路由器(第三及以上层网络设备)可以彼此物理联通的接口
“有类”编址：
- A类地址50%：0.0.0.0~127.255.255.255
- B类地址25%：128.0.0.0~191.255.255.255
- C类地址12.5%：192.0.0.0~223.255.255.255
- D类地址6.25%：224.0.0.0~239.255.255.255
- E类地址6.25%：240.0.0.0~255.255.255.255
| NetID | HostID | 作为IP分组源地址 | 作为IP分组目的地址 | 用途 |
|---|---|---|---|---|
| 全0 | 全0 | 可以 | 不可以 | 在本网范围内表示本机；在路由表中用于表示默认路由(相当于表示整个Internet网络) |
| 全0 | 特定值 | 不可以 | 可以 | 表示本网内某个特定主机 |
| 全1 | 全1 | 不可以 | 可以 | 本网广播地址(路由器不转发) |
| 特定值 | 全0 | 不可以 | 不可以 | 网络地址，表示一个网络 |
| 特定值 | 全1 | 不可以 | 可以 | 直接广播地址，对特定网络上的所有主机进行广播 |
| 127 | 非全0或非全1的任何数 | 可以 | 可以 | 用于本地软件环回测试，称为环回地址 |
| class | NetIDs | Blocks |
|---|---|---|
| A | 10 | 1 |
| B | 172.17 to 172.31 | 16 |
| C | 192.168.0 to 192.168.255 | 256 |
- IP地址：
- 网络号——高位比特
- 子网号——原网络主机号部分比特
- 主机号——低位比特
- 形如IP地址
- 32位
- 点分十进制形式
- 取值：
- NetID、SubId位全取1
- HostID位全取0
子网地址+子网掩码->准确确定子网大小
- 将IP分组的目的IP地址与子网掩码按位与运算，提取子网地址
- 无类域间路由
- 消除传统的A类、B类和C类地址界限
- NetID + SubID -> Network Prefix(可以任意长度)
- 融合子网地址与子网掩码，方便子网划分
- 无类地址格式：a.b.c.d/x，其中x为前缀长度
- 消除传统的A类、B类和C类地址界限
- 提高IPv4地址空间分配效率
- 提高路由效率
- 将多个子网聚合为一个较大的子网
- 构造超网
- 路由聚合
- 层级编址使得路由信息通告更高效
- 选用更具体的路由：最长前缀匹配优先
- “硬编码”
- 静态配置
- 动态主机配置协议——DHCP
- 从服务器动态获取：
- IP地址
- 子网掩码
- 默认网关地址
- DNS服务器名称与IP地址
- “即插即用”
- 允许地址重用
- 支持在用地址续租
- 支持移动用户加入网络
- 从服务器动态获取：
- 主机广播 “DHCP discover”(发现报文)
- DHCP服务器利用 “DHCP offer”(提供报文)进行响应
- 主机请求IP地址：“DHCP request”(请求报文)
- DHCP服务器分配IP地址：“DHCP ack”(确认报文)
- DHCP协议在应用层实现
- 请求报文封装到UDP数据报中
- IP广播
- 链路层广播(以太网广播)
- DHCP服务器构造ACK报文
- 包括分配给客户的IP地址、子网掩码、默认网关、DNS服务器地址
-
所有离开本地网络去往Internet的数据报的源IP地址需替换为相同的NATIP地址以及不同的端口号
-
本地网络内通信的IP数据报的源与目的IP地址均在子网内
-
动机：
- 只需/只能从ISP申请一个IP地址
- IPv4地址耗尽
- 本地网络设备IP地址的变更，无需通告外界网络
- 变更ISP时，无需修改内部网络设备IP地址
- 内部网络设备对外界网络不可见，即不可直接寻址(安全)
- 只需/只能从ISP申请一个IP地址
-
实现：
- 替换：
- 利用(NAT IP地址，新端口号)替换每个外出IP数据报的(源IP地址， 源端口号)
- 记录：
- 将每对(NAT IP地址，新端口号)与(源IP地址， 源端口号)的替换信息存储到NAT转换表中
- 替换：
- 根据NAT转换表，利用(源IP地址，源端口号)替换每个进入内网IP数据报的(目的IP地址，目的端口号)，即(NAT IP地址，新端口号)
- 替换：
-
16-bit端口号字段：
- 可以同时支持60000多并行连接
-
NAT主要争议：
- 路由器应该只处理第3层功能
- 违背端到端通信原则
- 应用开发者必须考虑到NAT的存在
- 地址短缺问题应该由IPv6来解决
- 客户期望连接内网地址为10.0.0.1的服务器
- 客户不能直接利用地址10.0.0.1直接访问服务器
- 对外唯一可见的地址是NAT地址:138.76.29.7
- 解决方案1：静态配置NAT，将特定端口的连接请求转发给服务器
- 解决方案2：利用UPnP互联网网关设备协议自动配置
- 解决方案3：中继
- NAT内部的客户与中继服务器建立连接
- 外部客户也与中继服务器建立连接
- 中继服务器桥接两个连接的分组
- 互联网控制报文协议ICMP支持主机或路由器
- 差错(或异常)报告
- 网络探寻
- 两类ICMP报文：
- 差错报告报文(5种)
- 目的不可达
- 源抑制
- 超时/超期
- 参数问题
- 重定向
- 网络探询报文(2组)
- 回声请求与应答报文
- 时间戳请求与应答报文
- 差错报告报文(5种)
- 几种不发送ICMP差错报告报文的特殊情况：
- 对ICMP差错报告报文不再发送ICMP差错报文
- 除第一个IP数据报分片外，对所有后续分片均不发送ICMP差错报告报文
- 对所有多播IUP数据报均不发送ICMP差错报告报文
- 对具有特殊地址的IP数据报不发送ICMP差错报告报文
- 几种ICMP报文已不再使用
- 信息请求与应答报文
- 子网掩码请求和应答报文
- 路由器询问和通告报文
- ICMP报文封装到IP数据报中传输
ICMP的前8字节 + IP数据报首部 + 8字节 -> ICMP差错报文
- 源主机向目的主机发送一系列UDP数据报
- 第一组IP数据报TTL=1
- 第二组IP数据报TTL=2，etc
- 目的端口号为不可能使用的端口号
- 当第n组数据报(TTL=n)到达第n个路由器时：
- 路由器丢弃数据报
- 向源主机发送ICMP报文(type=11,code=0)
- ICMP报文携带路由器名称和IP地址信息
停止准则：
- UDP数据报最终到达目的主机
- 目的主机返回“目的端口不可达”ICMP报文(type=3,code=3)
- 源主机停止
- 最初动机：32位IPv4地址空间已分配殆尽
- 其他动机：改进首部格式
- 快速处理/转发数据报
- 支持QOS
- IPv6数据报格式：
- 固定长度的40字节基本首部
- 不允许分片
- 优先级：标识数据报的优先级
- 流标签：标识同一“流”中的数据报
- 下一个首部：标识下一个选项首部或上层协议首部
- 校验和：彻底移除，以减少每跳处理时间
- 选项：允许，但是从基本首部移出，定义多个选项首部，通过“下一个首部”字段指示
- ICMPv6：新版ICMP
- 附加报文类型
- 多播组管理功能
- 把128bit的地址每16个一组用十六进制数表示，冒号分隔
- 一般形式：1080:0:FF:0:8:800:200C:417A
- 压缩形式：FF01:0:0:0:0:0:0:43
- 压缩->FF01::43
- IPv4嵌入形式：0:0:0:0:0:FFFF:13.1.68.3或::FFFF:13.1.68.3
- 地址前缀：2002:43c:476b::/48(IPv6不再使用掩码)
- 单播：一对一通信
- 多播：一对多通信
- 任意播：一对一组之一(最近一个)通信
- 不可能在某个时刻所有路由器同时被更新为IPv6
- 不会有“标志性的日期”
- IPv4和IPv6路由器共存的网络如何运行？
- 隧道：IPv6数据报作为IPv数据报的载荷进行封装，穿越IPv网络
- 路由算法(协议)确定去往目的网络的最佳路径
- 转发表确定在本路由器如何转发分组
图：G = (N, E) N = 路由器集合 E = 链路集合
- 每段链路的费用可以总是1，或者是带宽的倒数、拥塞程度等
- Dijkstra算法
- 所有结点(路由器)掌握网络拓扑和链路费用
- 通过“链路状态广播”
- 所有结点拥有相同信息
- 计算从一个结点(“源”)到达所有其他结点的最短路径
- 获得该结点的转发表
- 迭代：K次迭代后，得到到达K个目的的结点的最短路径
- 所有结点(路由器)掌握网络拓扑和链路费用
- 符号：
- c(x, y):结点x到结点y链路费用；如果x和y不直接相连，则=无穷
- D(v):从源到目的v的当前路径费用值
- p(v):沿从源到v的当前路径，v的前序结点
- N':已经找到最小费用路径的结点集合
初始化： N' = {u} for 所有结点v if v毗邻u then D(v) = c(u,v) else D(v) = 无穷 Loop 找出不在N'中的w，满足D(w)最小 将w加入N' 更新w的所有不在N'中的邻居v的D(v): D(v) = min(D(v), D(w) + c(w, v)) until 所有结点在N'中
算法复杂性：n个结点
- 每次迭代：需要检测所有不在集合N'中的结点w
- n(n+1)/2次比较：O(n^2)
- 更高效的实现：O(nlogn)
存在震荡可能
- Bellman-Ford方程(动态规划)
令： \(d_x(y):=\)从x到y最短路径的费用(距离)
重点：结合获得最短路径的下一跳，该信息用于转发表中
- \(D_x(y)\) = 从节点x到节点y的最小费用估计
- x维护距离向量(DV): \(D_x = [D_x(y): y \in N] \)
- 节点x：
- 一直到达每个邻居的费用：c(x, y)
- 维护其所有邻居的距离向量：\(D_x = [D_x(y): y \in N] \)
核心思想：
- 每个节点不定时地将其自身的DV估计发送给其邻居
- 当x接收到邻居的新的DV估计时，即依据B-F更新其自身的距离向量估计
- 将最终收敛于实际的最小费用
异步迭代：
- 引发每次局部迭代的因素
- 局部链路费用改变
- 来自邻居的DV更新 分布式：
- 每个结点只当DV变化时才通告给邻居
- 邻居在必要时(其DV更新后发生变化)再通告他们的邻居 每个结点：
- 等待(本地局部链路费用变化或者受到邻居的DV更新)
- 重新计算DV估计
- 如果DV中到达任一目的距离发生改变，通告所有邻居
- 结点检测本地链路费用变化
- 更新路由信息，重新计算距离向量
- 如果DV改变，通告所有邻居
- 毒性逆转
- 如果一个结点到达某目的的最小费用路径是通过某个邻居，则：
- 通告给该邻居结点到达该目的的距离为无穷大
- 如果一个结点到达某目的的最小费用路径是通过某个邻居，则：
- 定义最大度量：
- 定义一个最大的有效费用值，如15跳步，16跳步表示无穷
- 将任意网络抽象为一个图计算路由——过于理想化
- 标识所有路由器
- “扁平”网络——在实际网络(尤其是大规模网络)中，不可行！
- 网络规模：
- 路由表几乎无法存储
- 路由计算过程的信息交换量巨大，会淹没链路！
- 管理自治：
- 每个网络的管理可能都期望自主控制其网内的路由
- 互联网 = 网络之网
- 聚合路由器为一个区域：自治系统AS
- 统一AS内的路由器运行相同的路由协议(算法)
- 自治系统内部路由协议
- 不同自治系统内的路由器可以运行不同的AS内部路由协议
- 网关路由器：
- 位于AS“边缘”
- 通过链路连接其他AS的网关路由器
- 转发表由AS内部路由算法与AS间路由算法共同配置
- AS内部路由算法设置AS内部目的网络路由入口
- AS内部路由算法与AS间路由算法共同设置AS外部目的网络路由入口
- 假设AS1内某路由器收到一个目的地址在AS1之外的数据报：
- 路由器应该将该数据报转发给哪个网关路由
- AS1必须：
- 学习到哪些目的网络可以通过AS2到达，哪些可以通过AS3到达
- 将这些网络可达信息传播给AS1内部路由器
- 热土豆路由：将分组发送给最近的网关路由器
- Internet采用层次路由
- AS内部路由协议也称为内部网络协议IGP
- 最常见的AS内部路由协议：
- 路由信息协议：RIP
- 开放最短路径优先：OSPF
- 内部网关路由协议：IGRP
- Cisco私有协议
- 早于1982年随BSD-UNIX操作系统发布
- 距离向量路由算法
- 距离度量：跳步数(max = 15 hops),每条链路1个跳步
- 每隔30秒，邻居之间交换一次DV，成为通告
- 每次通告：最多25个目的子网(IP地址形式)
- 如果180秒没有收到通告->邻居/链路失效
- 经过该邻居的路由不可用
- 重新计算路由
- 向邻居发送新的通告
- 邻居再依次向外发送通告(如果转发表改变)
- 链路失效信息能否快速传播到全网？
- 可能发生无穷计数问题
- 毒性逆转技术用于预防乒乓环路(另外：无穷大距离=16hops)
- 经过该邻居的路由不可用
- RIP路由表是利用一个称作route-d(daemon)的应用层进程进行管理
- 应用进程实现
- 通告报文周期性地通过UDP数据报发送
- “开放”：公众可用
- 采用链路状态路由算法
- LS分组扩散（通告）
- 每个路由器构造完整的网络（AS）拓扑图
- 利用Dijkstra算法计算路由
- OSPF通告中每个入口对应一个邻居
- OSPF通告在整个AS范围泛洪
- OSPF报文直接封装到IP数据报中
- 与OSPF极其相似的一个路由协议：IS-IS路由协议
- 安全：所有OSPF报文可以被认证（预防恶意入侵）
- 允许使用多条相同费用的路径（RIP只能选一条）
- 对于每条链路，可以针对不同的TOS设置多个不同的费用度量
- 集成单播路由与多播路由：
- 多播OSPF协议（MOSPF）与OSPF利用相同的网络拓扑数据
- OSPF支持对大规模AS分层
- 两级分层：局部区，主干区
- 链路状态通告只限于区内
- 每个路由器掌握所在区的详细拓扑
- 只知道去往其他区网络的“方向”（最短路径）
- 区边界路由器：“汇总”到达所在区网络的距离，通告给其他区边界路由器
- 主干路由器：在主干区内运行OSPF路由算法
- AS边界路由器：连接其他AS。
- 边界网关协议BGP：事实上的标准域间路由协议
- 将Internet“粘合”为一个整体的关键
- BGP为每个AS提供了一种手段：
- eBGP：从邻居AS获取子网可达性信息
- iBGP：向所有AS内部路由器传播子网可达信息
- 基于可达性信息与策略，确定到达其他网络的“好”路径
- 允许子网向Internet其余部分通告它的存在
- BGP会话：两个BGP路由器（“Peers”）交换BGP报文
- 通告去往不同目的的前缀的路径
- 报文交换基于半永久的TCP连接
- BGP报文：
- OPEN：与peer建立TCP连接，并认证发送方
- UPDATE：通告新路径（或撤销原路径）
- KEEPLIVE：在无UPDATE时，保活连接；也用于对OPEN请求的确认
- NOTIFICATION：报告先前报文的差错，也被用于关闭连接
- 当路由器获得新的前缀可达性时，即在其转发表中增加关于该前缀的入口（路由项）
- 通告的前缀信息包括BGP属性
- 前缀+属性=“路由”
- 两个重要属性：
- AS-PATH（AS路径）：包含前缀通告所经过的AS序列
- NEXT-HOP（下一跳）：开始一个AS-PATH的路由器接口，指向下一跳AS。
- 可能从当前AS到下一跳AS存在多条路径
- 网关路由器收到路由通告后，利用其输入策略决策接受/拒绝该路由
- 基于策略路由
- 路由器可能获知到达某目的的AS的多条路由，基于以下准则选择：
- 本地偏好值属性：策略决策
- 最短AS-PATH
- 最近NEXT-HOP路由器：热土豆路由
- 附加准则
- 策略：
- inter-AS：期望能够管理控制流量如何被路由，谁路由经过其网络等。
- intra-AS：单一管理，无需策略决策。
- 规模：
- 层次路由节省路由表大小，减少路由更新流量
- 适应大规模互联网
- 性能：
- intra-AS：侧重性能
- inter-AS：策略主导