网络层服务

从发送主机向接收主机传送数据段

发送主机：将数据段封装到数据报中。

接收主机：向传输层交付数据段。

每个主机和路由器都运行网络层协议。

路由器检验所有穿越它的IP数据报的头部域。

网络层核心功能

转发与路由

转发(forwarding)：将分组从路由器的输入端口转移到合适的输出端口。

每个路由器维护一张转发表，转发表确定本路由器如何转发分组。

转发表的内容：地址-输出链路，如0100-3, 0101-2, 0111-2, 1001-1.

取出收到的数据报的地址信息，然后查转发表得到输出链路。

路由(routing)：确定分组从源到目的经过的路径。

如何得到路由信息？

网络层设备都会运行一些路由协议，或路由算法(routing algorithms)，根据路由算法确定通过网络的端到端路径。

连接的建立

数据分组传输之前两端主机需要首先建立虚拟/逻辑连接，网络设备（如路由器）参与连接的建立。

网络层连接与传输层连接的对比：

网络层连接：两个主机之间的连接，并且在路径上的每个网络层设备都要参与建立连接。
传输层连接：两个应用进程之间的连接（端到端的连接，对中间网络设备透明）。

网络层为发送端（主机）到接收端（主机）的数据报传送”通道(channel)”提供怎样的服务模型(service model)？

不同的网络架构(Network Architecture)提供的服务模型是不一样的。例如Internet提供的是best effort服务模型，不保障Bandwidth, Loss, Order或Timing，通过数据是否丢失来判断拥塞(congestion)。ATM的服务模型有CBR，VBR，ABR，UBR。

网络层服务模型

无连接服务(connection-less service)：
- 不事先为系列分组的传输确定传输路径
- 每个分组独立确定传输路径
- 不同分组可能传输路径不同
- 数据报网络(datagram network)
连接服务(connection service)：
- 首先为系列分组的传输确定从源到目的经过的路径（建立连接）
- 然后沿该路径（连接）传输系列分组
- 系列分组传输路径相同
- 分组传输顺序可以保证
- 传输结束后拆除连接
- 虚电路网络(virtual-circuit network)

虚电路网络和数据报网络

虚电路网络

数据报网络和虚电路网络是典型的两类分组交换网络。

数据报网络提供网络层无连接服务。

虚电路网络提供网络层连接服务。

类似于传输层的无连接服务（UDP）和面向连接服务（TCP），但是网络层服务：

是主机到主机的服务
网络核心实现（传输层是端到端实现）

虚电路：一条从源主机到目的主机，类似于电路的路径（逻辑连接）。

分组交换
每个分组的传输利用链路的全部带宽
源到目的路径经过的网络层设备共同完成虚电路功能
通信过程：呼叫建立(call setup)——数据传输——拆除呼叫
每个分组携带虚电路标识(VCID)，而不是目的主机地址
虚电路经过的每个网络设备（如路由器），都要维护每条经过它的虚电路的连接状态
链路、网络设备资源（如带宽、缓存等）可以面向VC进行预分配
- 预分配资源 = 可预期服务性能
- 如ATM的电路仿真(CBR)

每条虚电路包括：

从源主机到目的主机到一条路径
虚电路号(VCID)，沿路每段链路一个编号

链路带宽越大，允许建立的虚电路的数量就越大。

同一条虚电路在每一段链路上的VCID可能是不一样的。
沿路每个网络层设备（如路由器），利用转发表记录经过的每条虚电路。

沿某条虚电路传输的分组，携带对应虚电路的VCID，而不是目的地址。

同一条VC，在每段链路上的VCID通常不同：

路由器转发分组时依据转发表改写/替换虚电路号

虚电路信令协议(signaling protocols)

用于VC的建立、维护与拆除：路径选择

应用于虚电路网络：如ATM、帧中继(frame-relay)网络等

目前的Internet不采用。

初识呼叫——呼叫到达——接受呼叫——呼叫建立——数据流开始——接收数据

通信结束后，也通过虚电路信令协议进行呼叫的拆除。

数据报网络

网络层无连接

每个分组携带目的地址

路由器根据分组的目的地址转发分组：

基于路由协议/算法构建转发表
检索转发表
每个分组独立选路
每个分组走的路径可能不一样，因为如果在传输过程中路由器更新了转发表，那么后面的分组就会走新的路径

数据报中含有目的主机的IP地址。但是IP地址是32位的二进制数，一共有2^32种不同情况，严重降低了传输效率。解决方法是：转发表中的目的地址不是一个明确的地址，而是一个地址范围。这样就将许多具有共同列表地址的转发表进行了聚合。

目的地址范围的匹配采用最长前缀匹配优先（在检索转发表时，优先选择与分组目的地址匹配前缀最长的入口[entry]）。

Internet（数据报网络）

计算机之间的数据交换：”弹性”服务，没有严格时间需求。
链路类型众多：特点、性能各异，统一服务困难。
“智能”端系统：可以自适应、性能控制、差错恢复
简化网络，复杂”边缘”

ATM（VC网络）

电话网络演化而来
核心业务是实时对话：严格的时间、可靠性需求，需要有保障的服务。
“哑”端系统（非智能）：电话机、传真机
简化”边缘”，复杂网络

IPv4协议

Internet网络层

主要功能就是路由和转发。

主机、路由器网络层主要功能：

路由协议：路径选择，如RIP，OSPF，BGP
转发表（路由表）
IP协议：寻址规约(conventions)，数据报（分组）格式，分组处理规约
ICMP协议（互联网控制报文协议）：差错报告，路由器”信令协议”
实现IP协议，通常也要实现ICMP协议。后者可以看做是前者的一个伴随协议。

IP数据报（分组）格式

IP数据报格式：首部 + 数据(e.g. TCP, UDP段)

数据报长度是32位，即从0到31位。

首部（固定部分5行、可变部分1行）

数据（1行）

首部分为固定部分和可变部分。

固定部分：

版本号(4位，0~3)，首部长度，服务类型(TOS)，总长度

标识，标识位，片偏移

生存时间(TTL)，协议，首部检验和

源IP地址

目的IP地址

可变部分：

选项字段（长度可变），填充

版本号：4位，如果是IPv4就是4，如果是IPv6就是6。
首部长度：4位。是IP分组的首部长度。
- 以4字节为单位（1行32比特，刚好4字节）
- IP固定部分首部长度为5*4=20字节
- 最典型的，例如是IPv4协议，那么版本号是0100(4d)，首部长度0101(5d)。
服务类型(TOS)：8位，指示期望获得哪种类型的服务。
- 1998年这个字段改名为区分服务
- 只有在网络提供区分服务(DiffServ)时使用
- 一般情况下不使用，通常IP分组的该字段（第2字节）的值为00H
总长度：16位，是IP分组的总字节数（首部+数据）
- 最大IP分组的总长度：65535B
- 最小的IP分组首部：20B（可变部分为0）
- IP分组可以封装的最大数据：65535-20=65515B
- 当然在实际中不会达到最大数据，因为一定会将它切分的。
生存时间(TTL)：8位，是IP分组在网络中可以通过的路由器数（或跳步数）
- 路由器转发一次分组，TTL减一
- 如果TTL=0，则路由器丢弃该IP分组
协议：8位，指示IP分组封装的是哪个协议的数据包
- 实现复用/分解
- 6为TCP，表示封装的是TCP段；17为UDP，表示封装的是UDP数据报
首部校验和：16位，实现对IP分组首部的差错检测
- 计算校验和时，该字段置为全0
- 采用反码算数运算求和，和的反码作为首部校验和字段
- 逐跳计算、逐跳检验
源IP地址、目的IP地址字段各占32位

IP分片

网络链路存在MTU（最大传输单元）——链路层数据可封装数据的上限。不同链路的MTU不同。

大IP分组向较小MTU链路转发时，可以被”分片”(fragmented)。

IP分片到达目的主机后进行”重组”(reassembled)。

路由器对IP分组只分片不重组。

如果此路由器不让分片，那么就把这个IP分组丢掉，一般地会再发一个ICMP的分组（具体是怎样再查查，这里只是粗略记录）。

IP首部中的总长度、标识、标识位和片偏移用来标识分片以及确定分片的相对顺序。

标识字段：16位，用于标识一个IP分组

IP协议利用一个计数器，每产生一个IP分组，计数器就加一，利用此时计数器的值和其他一些信息唯一标识该IP分组

标识位：3位

IP编址

接口：主机/路由器与物理链路的连接

实现网络层功能
路由器通常有多个接口
主机通常只有一个或两个接口（有线的以太网接口，无限的802.11接口）

IP地址：32比特(IPv4)编号用于标识主机、路由器的接口

一般用点分十进制的方式表示。

11011111 00000001 00000001 00000001 = 233.1.1.1

一个IP地址唯一标识一个接口。

IP地址与每个接口关联。

IP子网(subnets)

IP地址：

网络号(NetID) - 高位比特
主机号(HostID) - 低位比特

NetID HostID

233.1.1 .1

相同的网络号构成IP子网。

IP子网：

IP地址具有相同网络号的设备接口
不跨越路由器（第三及以上层网络设备）可以彼此物理联通的接口

“有类”编址：

A类地址，50%：NetID(8位) + HostID(24位)

0.0.0.0 ~ 127.255.255.255

B类地址，25%：NetID(16位) + HostID(16位)

128.0.0.1 ~ 191.255.255.255

C类地址，12.5%：NetID(24位) + HostID(8位)

192.0.0.0 ~ 223.255.255.255

D类地址，6.25%：32位，1110

224.0.0.0～239.255.255.255

E类地址，6.25%：32位，1111

240.0.0.0～255.255.255.255

IP子网划分与子网掩码

子网划分：

IP地址——网络号(NetID) + 子网号(SubID) + 主机号(HostID)

就是将刚才的主机号划分为了：子网号(SubID) + 主机号(HostID)。即子网号是原主机号的部分比特。

子网划分定义：Internet组织机构定义了五种IP地址，有A、B、C三类地址。A类网络有126个，每个A类网络可能有16777214台主机，它们处于同一广播域。而在同一广播域中有这么多节点是不可能的，网络会因为广播通信而饱和，结果造成16777214个地址大部分没有分配出去。可以把基于每类的IP网络进一步分成更小的网络，每个子网由路由器界定并分配一个新的子网网络地址，子网地址是借用基于每类的网络地址的主机部分创建的。划分子网后，通过使用掩码，把子网隐藏起来，使得从外部看网络没有变化，这就是子网掩码。

比如，当一组IP地址指定给一个公司时，公司可能将该网络“分割成”小的网络，每个部门一个。这样，技术部门和管理部门都可以有属于它们的小网络。通过划分子网，我们可以按照我们的需要将网络分割成小网络。这样也有助于降低流量和隐藏网络的复杂性。

子网掩码：

形如IP地址：32位，点分十进制形式

取值：NetID, SubID位全取1，HostID全取0

例如：

A网的默认子网掩码为：255.0.0.0

B网的默认子网掩码为：255.255.0.0

C网的默认子网掩码为：255.255.255.0

借用3比特划分子网的B网的子网掩码为：255.255.224.0 （224就是11100000）

子网地址+子网掩码 —— 准确确定子网大小

将IP分组的目的IP地址与子网掩码按位与运算，提取子网地址。

CIDR与路由聚集

无类域间路由(CIDR: Classless InterDomain Routing)

消除传统的A、B、C类地址界限：将NetID和SubID合在一起变成Network Prefix(Prefix)，即统称为网络前缀，并且可以任意长度
融合子网地址与子网掩码，方便子网划分

无类地址格式：a.b.c.d/x，其中x为前缀长度

11001000 00010111 00010000 00000000

前面是前缀（长为8+8+7=23），后面是主机号HostID。

写成CIDR地址形式就是200.23.16.0/23。

优势

提高IPv4地址空间分配效率
提高路由效率
- 将多个子网聚合为一个较大的子网
- 构成超网
- 路由聚合(route aggregation)

DHCP协议

如何获得IP地址？

“硬编码”：静态配置
动态主机配置协议 - DHCP：Dynamic Host Configuration Protocol

从服务器动态获取：IP地址、子网掩码、默认网关地址、DNS服务器名称与IP地址

“即插即用”

允许地址重用

支持在用地址续租

支持移动用户加入网络

动态主机配置协议DHCP

主机广播”DHCP discover”（发现报文）等待是否有DHCP服务器响应
DHCP服务器利用”DHCP offer”（提供报文）进行响应，告诉客户端自己可以提供的一个IP地址
主机请求IP地址：客户端向服务器发送”DHCP request”（请求报文）表示愿意接受这个IP地址同时请求服务器将它真正分配给自己
DHCP服务器分配IP地址：服务器向客户端发送”DHCP ack”（确认报文）表示确认分配

DHCP协议在应用层实现：

请求报文封装到UDP数据报中
IP广播
链路层广播（例如，以太网广播）

DCHP服务器内建于服务器中。

DHCP服务器构造ACK报文，包括分配给客户的IP地址、子网掩码、默认网关、DNS服务器地址。

NAT网络地址转换

本地网络内通信的IP数据报的源与目的IP地址均在子网10.0.0/24（显然这是一个私有地址，比如说是家庭网络）内。

所有离开本地网络去往Internet的数据报的源IP地址需要替换为相同的NAT IP地址（例如138.76.29.7）以及不同的端口号。

动机：

只需从ISP申请一个IP地址，因此面临IPv4地址耗尽
本地网络设备IP地址的变更，无需通告外界网络
变更ISP时，无需修改内部网络设备IP地址
内部网络设备对外界网络不可见，即不可直接寻址

实现：

替换：利用(NAT IP地址，新端口号)替换每个外出IP数据报的(源IP地址，源端口号)
记录：将每对(NAT IP地址，新端口号)与(源IP地址，源端口号)的替换信息存储到NAT转换表中
根据NAT转换表，用(源IP地址，源端口号)替换每个进入内网IP数据报的(目的IP地址，目的端口号)

NAT转换表包含：WAN端地址、LAN端地址。

NAT穿透问题：外部设备期望连接内网地址的服务器

方法1: 静态配置NAT（转换表），将特定端口的连接请求转发给服务器。

方法2: 利用UPnP(Universal Plug and Play)互联网网关设备协议(IGD-Internet Gateway Device)自动配置：学习到NAT公共IP地址，在NAT转换表中增删端口映射。

方法3: 中继(如Skype)

互联网控制报文协议ICMP

Internet Control Message Protocol支持主机或路由器

差错或异常报告

网络探询

两类ICMP报文：

差错报文

IPv6

最初动机：32位IPv4地址空间已分配殆尽

其他动机：改进首部格式：快速处理/转发数据报，支持QoS

IPv6数据报格式：

固定长度的40字节基本首部
不允许分片

虽然首部没有可选项、是固定长度，但是有可选的扩展首部。

IPv6数据报格式：

基本首部，扩展首部1，扩展首部2，…，扩展首部N，数据部分（例如TCP段）

路由算法

路由算法（协议）确定最佳路径，转发表确定在本路由器如何转发分组。

路由算法分类

静态路由&动态路由

静态路由：

手工配置
路由更新慢
优先级高

动态路由：

路由更新快
- 定期更新
- 及时响应链路费用或网络拓扑结构变化
由路由算法计算出来的

全局信息&分散信息

全局信息：

所有路由器掌握完整的网络拓扑和链路费用信息。
链路状态（LS）路由算法

分散信息：

路由器只掌握物理相连的邻居以及链路费用。
距离向量（DV）路由算法

链路状态路由算法

Dijkstra算法

c(x, y): 结点x到结点y的链路费用；如果x和y不直接相连，则为∞。
D(v): 从源到目的v的当前路径费用值。
p(v): 沿从源到v的当前路径，v的前序结点集合。
N’: 已经找到最小费用路径的结点集合。

初始化：
N'= {u}
for 所有结点v
	if v nextTo u
		D(v) = c(u, v)
	else
		D(v) = ∞

循环：
	找出不在N'中的结点w，使得D(w)最小
	将w加入N'
	更新w的所有不在N'中的邻居v的D(v): D(v) = min{c(v, w)+D(w), D(v)}
until 所有结点都在N'中

但是存在振荡现象。

距离向量路由算法

Bellman-Ford方程（动态规划）

Dx(y) := 从x到y最短路径的费用（距离）
Dx(y) = min{c(x, v) + Dv(y)}

异步迭代：

引发每次局部迭代的因素：
- 局部链路费用改变
- 来自邻居的DV更新

分布式：

每个结点只当DV变化时才通告给邻居

无穷计数问题

层次路由

将任意规模网络抽象为一个图计算路由——过于理想化。

标识所有路由器

“扁平”网络

网络规模巨大时，交换量会占用所有网络带宽。

聚合路由器为一个区域：自治系统AS

Internet路由

AS内部路由：

Internet采用层次路由
AS内部路由协议也称为内部网络协议IGP(interior gateway protocol)
最常见的AS内部路由协议：
- 路由信息协议：RIP(Routing Information Protocol)
- 开放最短路径优先：OSPF(Open Shortest Path First)
- 内部网关路由协议：IGRP(Interior Gateway Routing Protocol)
  - Cisco私有协议

RIP

早于1982年随BSD- UNIX操作系统发布

跳数指从源端口到达目的端口所经过的路由个数，每经过一个路由器，跳数加1 。数据包经过一台路由器就是一跳，经过的路由器数量，就是它的跳数。

距离向量路由算法：

距离度量：跳步数(max = 15hops)，每条链路1个跳步
每隔30秒，邻居之间交换一次DV，成为通告(advertisement)
每次通告：最多25个目的子网(IP地址形式)

LINK

OSPF(Open Shortest Path First)协议：

开放：公众可用
采用链路状态路由算法

Don’t let anyone rush yourself with their timelines.