每日一言

什么都无法舍弃的人，什么也改变不了。

——《进击的巨人》

Network Layer Introduce

Overview

Hop-to-hop : 点到点，相邻两个设备之间的通信，一般是主机与路由，路由与路由之间。

end-to-end：端到端，主机到主机之间的通信，忽略中间的路由。

Network layer is the lowest layer that deals with end-to-end transmission (网络层是端到端传输的最底层)

• 数据链路层只负责点到点之间的传输。

Design Issues

• Network layer must know about topology
• Choose appropriate paths and avoiding overloading
• The source and destination are in different networks

Network Layer Functions

• Interconnecting 网络互联

  • Different networks and making them look the same to the transport layer
  • 传输层无需关心低层的物理网络即可发送信息

• Addressing 编址

  • The addresses of a host/router must be uniquely(唯一) and universally(规则统一)

• Packetizing 形成数据包

  • Encapsulated(封装) message received from upper layer

• Fragmenting 分片

  • The network layer must be able to operate on top of any data-link layer technology
  • 网络层必须能够在任何数据链路层之上运行
  • The network layer must be able to fragment transport layer PDUs(协议数据单元) into smaller units so that they can be transferred(转移) over various data-link layer technologies.

• Routing 路由 (核心功能)

  • Making the decision which routes to use
  • Filling in and updating the routing tables

Services Provided to Transport Layer

设计目标：

• 服务应该独立于路由技术。(降低对于特定路由的依赖，得以在任何路由网络中工作)
• 向Transport layer 隐藏路由器的数量，类型和拓扑关系。
• 传输层使用的网络应该有统一的编址方案

分类：两种都是分组交换

Connection-Oriented Service：Virtual Circuit 虚电路

Connectionless Service：Datagram 数据报

Datagram 数据报

无连接的，尽最大努力交付

Virtual Circuit 虚电路

建立一条逻辑上的连接，分组都沿着这条逻辑连接按照存储转发的方式传送，而并不是真正建立了一条物理连接。

• VCI：Virtual Circuit Identifier 虚拟电路号

当不同接口收到同一个VCI时，接收路由应该区分它们，否则后续路由都将无法区分。

问题	数据报子网	虚电路子网
电路设置	不需要	需要
编址	每个分组包含完整的源地址和目的地址	每个分组包含一个短的虚电路号
状态信息	路由器不持有关于连接的状态信息	每条虚电路在路由器中需要占用表空间
路由选择	每个分组独立路由	虚电路建立时选定路由，所有分组都沿此路由传输
路由器故障影响	除了故障期间丢失的分组外，无其他影响	经过故障路由器的所有虚电路都终止
服务质量	困难	如果能为每条虚电路预先分配足够资源则容易
拥塞控制	困难	如果能为每条虚电路预先分配足够资源则容易

虚拟电路依然是分组传送，只不过拥有相同VIC的数据报会沿着相同的路径进行传输，仿佛在一条电路上。

Routing Algorithms

Routing Algorithms：用于构造和更新路由表算法

Routing Protocolls：路由协议是一组规则和程序，当网络拓扑等发生变化时，路由器可借助它相互通告信息。它主要依靠不同网络中的路由器之间共享、整合信息，从而让路由器知晓网络的最新状态，以便正确地转发数据包。

Routing table ：

• 表里存完整路径：

• 表里存下一跳：

  

Routing

定义：决定定义的数据包应该从哪条线路传输

• 数据报Datagrams：对于每个数据包都选择最佳的传输路径，每个数据包都单独决策
• 虚电路Virtual circuits：仅在建立新虚电路时进行路由决策，后续数据包遵循先前建立好的路由。

Classification of Routing Algorithms

• Nonadaptive algorithms(Static Routing) 非自适应路由
  • 路由决策不基于对当前流量和拓扑结构的测量或估计。
  • 路由选择是提前离线计算好的，在启动时下载到路由器中。
• Adaptive algorithms 自适应路由
  • 会根据网络拓扑结构的变化，流量的变化，动态的改变路由决策。

最优化原则(The Optimality Principle)

如果路由器 J 在路由器 I 到路由器 K 的最优路径上，那么从 J 到 K 的最优路径也在同一条路线上。

Sink Tree

汇集树（Sink Tree）是指所有源节点到一个指定目标节点的最优路径的集合 ，它构成一棵以目标节点为根的树。在网络拓扑中，从各个不同的源点出发，寻找通往特定目的节点的最佳路由，这些最佳路由组合起来就呈现出树状结构，目的节点作为树根。

特点：

• 汇集树不包含任何回路（loops），有回路意味着会陷入无尽循环

Routing Algorithms 路由算法

Shortest Path Routing 最短路径算法

定义：

• 用于计算一个节点到其他所有结点的最短路径，主要特点是以起始点为中心向外逐层扩散，直到扩展到终点为止。
• Dijkstra算法思想，在网络图中找最短路径。

Flooding 泛洪

• 无需路由表
• Incoming packets retransmitted on every link except incoming link

问题：如果不控制，会产生无穷副本。

Damping the Flood 抑制泛洪

1. 跳计数器(hop counter)
2. 序号机制(sequence number)
3. 选择性泛洪(Selective flooding)

Distance Vector Routing 距离向量路由算法(DVR)

原理：Bellman-Ford 方程

• 假设$D_x(y)$是 从x到y最小代价路径的代价值

• 则：

  $$D_x(y) = \min \{c(x,m) + D_m(y) \}$$

  其中m为x的邻居，(c(x,m))为m到x的距离

路由表表项：

• Destination
• Distance(cost)
• NextHop

更新机制：

发送路由信息：

• 每个结点周期性地向邻居发送它自己到某些结点的距离向量
• 当路由表变化时立即发送

接收路由表：

• 当接收到邻居发送的路由信息后，如果发现有更好的路由，就更新本地路由。
• 若有表项一定时间未更新，则删除。

关键特征

1. 网络信息共享 ：路由器会与邻居分享关于整个网络的信息 ，让邻居知晓自身掌握的网络路径等情况。
2. 仅与直接邻居交互 ：只和直接相连的邻居路由器交换信息，通过自身所有接口将所掌握信息发送出去 ，不跨级传播。
3. 定期共享 ：按照固定时间间隔进行信息分享 ，如 RIP 协议中常见的每 30 秒分享一次路由信息 ，确保邻居间信息及时更新。

缺点

1. 收敛速度慢 ：网络拓扑发生变化（如链路故障、新增链路）后，所有路由器要达成对新拓扑一致认知并更新路由表耗时较长，影响网络性能和数据包转发效率 。
2. 对不同信息反应差异大 ：好消息反应快，坏消息反应慢。

Link State Routing 链路状态路由(LSR)

每个路由知道全局拓扑信息，然后计算路由。

步骤

1. 邻居发现 ：路由器要识别出与之直接相连的邻居路由器，并获取这些邻居的网络地址 ，为后续信息交互和路径计算打基础。
2. 度量设置 ：确定到每个邻居的距离或代价度量值，比如通过测量链路延迟、带宽占用等方式，量化与邻居间链路的情况 。
3. 构建链路状态包 ：把前两步获取的信息（邻居及对应链路度量值等 ），整合成链路状态包（LSP，Link - state Packet） 。
   • 定期构建LSP。
   • 发送重要事件时，立即构建LSP
4. 信息传播 ：将构建好的 LSP 可靠地发送给网络中的所有其他路由器，而非仅发送给直接邻居，使全网路由器能获取到网络拓扑和链路状态信息 。
   • 可靠分发
   • 使用泛洪传播LSP
   • 所有的LSP都需要被确认
5. 路径计算 ：基于接收到的全网链路状态信息，运用算法（如 Dijkstra 算法 ）计算出到其他各个路由器的最短路径，更新路由表用于数据包转发 。

Details of Link State Packets

LSP信息中嵌入序号，用于判断接收到的LSP是否为新信息。

处理规则

• 新 LSP ：若 LSP 是新的，除了接收该 LSP 的链路外，在其他所有链路上转发它 ，实现信息扩散。

• 重复 LSP ：若 LSP 是重复的，执行选择性洪泛，将其丢弃，避免重复处理和网络资源浪费 。

• 过时 LSP ：若接收到的 LSP 序号低于当前已见过的最大序号，说明是过时的，将其拒绝。

  

Hierarchical Routing(层次路由/分级路由)

无层次路由

假设有一个包含 720 个路由器的子网，在无层次路由情况下，每个路由器的路由表需要有 720 个条目 ，用于记录到所有其他路由器的路由信息，随着路由器数量增加，路由表会非常庞大，占用大量内存和计算资源。

二级层次路由

将子网划分为 24 个区域，每个区域有 30 个路由器 。此时：

• 本地条目 ：每个路由器有 30 个本地条目，用于记录本区域内其他路由器的路由信息。
• 远程条目 ：有 23 个远程条目，记录到其他 23 个区域的路由信息 。这样路由表条目总数为 53 个，相比无层次路由，条目数大幅减少 。、

三级层次路由

子网划分为 8 个簇，每个簇包含 9 个区域，每个区域有 10 个路由器 。此时：

• 本地路由器条目 ：每个路由器有 10 个条目用于记录本区域内其他路由器的路由信息。
• 簇内区域间路由条目 ：有 8 个条目用于记录到本簇内其他区域的路由信息 。
• 远程簇路由条目 ：有 7 个条目用于记录到其他远程簇的路由信息 。路由表条目总数为 25 个，进一步减少了路由表规模，降低了管理和维护成本 。

层次路由通过将网络划分为不同层次结构，有效减少了路由表规模，提升了路由效率和网络可扩展性 。

Congestion Control Algorithms(拥塞控制算法)

拥塞：网络中存在太多的数据包导致数据包传输延迟或丢失，从而导致网络吞吐量下降。

拥塞控制

拥塞控制&流量控制

Conjestion：

• 避免网络拥堵(端到端)

Flow Control：

• 避免接收端被淹没(点到点)

拥塞控制的手段

• Network Provisioning(网络供给)
• Traffic-aware routing(流量感知路由)
• Admission Control(准入控制)
• Traffic throtting(节流)
• Load shedding(负载脱落)

Network Provisioning

有钱任性法：物理升级网络使之能够应对负载。

Traffic-aware Routing

常规方法：

• Used fixed(固定的) link weights(链路权重)，adapted to changes in topology,but not to changes in load

Traffic-aware Routing：

• 将链路的负载也纳入链路的权重。
• 问题：引发路由震荡

Admission Control

Widely used in virtual-circuit networks(虚拟电路)

没有足够的资源，就不允许建立VC。

使用模型：

• leaky bucket(漏桶)
• token bucket (令牌桶)

Traffic Throttling

When congestion is imminent (临近的), the network must tell the sender to throttling(节流) back their transmissions and slow down

网络通知源端拥塞发生，必须降速。

反馈方式：

• Choke packets 抑制包
• ECN 显式拥塞通知
• Hop-by-Hop backpressure 逐跳后压

Chock packets

• 向源端发送
• 对于原数据包进行标记，防止因一个数据包触发多次Chock packets
• 为了避免增加网络负载，chock packet以较低速率发送

ENC(Explicit Congestion Notification)

• 路由可以通过设置header中的标志位，表示一个数据包经历拥塞。
• 接收端在回复发送端时，会携带拥塞标记。
• 发送端收到标记，节流发送速率。

Hop-by-Hop Backpressure

抑制包不止抑制源端，而抑制经过的每一个路由。

优点：反应快

缺点：路由需要较大缓存

Loading Shedding

When routers are being inundated(不堪重负) by packets, just throw them away.主动丢弃数据包。

RED(Random Early Detection) 早期随机检测：

• Drop packets before sitution becomes hopeless 在拥塞严重之前随机丢弃数据包。

Quality of Service(服务质量)

服务质量包含以下方面：

• Reliable 可靠性
• Delay
• Jitter 抖动：the variation(变化) in delay of packets belonging to the same flow.
• Bandwidth

提升QoS的几种手段：

• Traffic shaping 流量整型
• Packet scheduling 数据包调度
• Admission control 准入控制
• Resource reservation 资源预留

Traffic Shaping 流量整型

通过调节数据传输的平均速率和突发性，平滑流量。

漏桶 The Leaky Bucket Algorithm

• 到达的数据包被放在底部具有漏孔的桶中
• 漏桶最多可以排队B个字节，如果数据包到达的时候漏桶已满，那么数据包应该被丢弃。
• 数据包从漏桶中漏出，以常量速率(R字节/秒)注入网络，因此平滑了突发流量。

令牌桶The Token Bucket Algorithm

• 产生令牌：周期性的以速率R向令牌桶中增加令牌，桶中的令牌不断增多。如果桶中令牌数已达上限B，则丢弃多余的令牌。
• 消耗令牌：输入数据包会消耗桶中的令牌。在网络传输中，数据包的大小通常不一致。大的数据包相较于小的数据包消耗的令牌要多。
• 判断是否通过：输入数据包经过令牌桶时存在两种可能：输出该数据包或者等待。
  • 当桶中的令牌数量可以满足数据包对令牌的需求，则将数据包输出。
  • 否则等待

突发传输时间

Packet Scheduling数据包调度

Packet scheduling ： allocate(分配) router resources among the packets of a flow and between competing flows.

调度：决定谁先用资源，谁后用资源。

算法：

• FIFO 先进先出

  

• Fair Queueing 公平队列

  

• Weighted Fair Queueing 加权公平队列

  

• Prirority Queueing 优先级队列：高级数据优先发送

  

Internetworking(网络互联)

Tunneling 隧道技术

Source and destination host are on the same type of network,but there is a different network in between.

• 源主机和目的主机使用相同的网络协议，但中间存在不同协议的网络时，采用隧道技术(Tunneling)

Packet from source is encapsulated(封装) inside packet of the intermediate(中间层) network.

Packet Fragmentation 数据包分片/分段

Each network or link imposes(迫使) some maximum size on its packets.

MTU：Maximum Transmission Unit 最大传输单元

Packet Fragmentation数据包分片

透明分片：每个路由器必须接收到所有分片后才能进行下一步，路由器会重组所有分片，尽管之后可能还需要重新分片。

非透明分片：仅仅由目的计算机重组分片，路由仅仅负责转发。

Numbering the Fragment

假设一个完整的数据包如下：

头部占用三个字节：

• 第一个字节为数据包编号，每个数据包一个编号
• 第二个字节表示当前分片第一个数据字节在数据包中的位置。
• 第三个字节为0时，表示当前分片不是最后一片，为1时表示当前分片为最后一片。

一次分片后：

I 在整个数据包中的下标为8，所以第二个分片的第二个数据为8。

分为三片：

Getting Rid of Fragmentation 避免分片

PATH MTU discovery 路径MTU发现

Source：IP packet is sent with its header bits set to indicate that no fragmentation is allowed.

• 源主机发送一个数据包并且在头中标明此数据包不可分片

Router：If a router receives a packet that is too large, it generates an error packet, returns it to source, and drop the packet

Souce：When the source receives the error packet, it uses the information inside to refragment packet into pieces that are small enough

If a router further down the path has an even smaller MTU, the process is repeated.

Network Layer in the Internet

IPV4

IPv4协议,网际协议版本4,一种无连接的协议, 是互联网的核心,也是使用最广泛的网际协议 版本,其后继版本为IPv6

IPv4 datagram format

IP数据报由首部和数据两部分组成：

头部的组成如下：(重要)

• Version(4 bits): 表示协议版本，多为IPv4
• IHL(4 bits)：IP数据报首部的长度，4Bytes为一个单位。
• Differentiated services (8 bits)：
  • 前6bit表示服务类别
  • 后2bit用于携带显式拥塞通知(ENC)
• Total Length (16 bits)：包含首部和数据部分的最大长度，最大值为65535 字节
• Identification (16 bits)：数据报的身份标识，每个数据报的分片都有同一个Identification
• DF (1 bit)：不能分片标志，置0表示允许分片，1表示不能分片
• MF (1 bit)：置1表示后面还有分片，置0表示数据报分片的最后一个
• Fragment offset (13 bits)：ip分片后，相应的IP片在总的IP片的相对位置。8Bytes为一个偏移量。

• TTL：Time to live(8 bits) 生存时间
• Protocol field(8 bits)：
• The Header checksum(16 bits)
  • Verifies the header only
  • Must be recomputed at each hop 每一跳必须重新计算，TTL一定会变
• Source & Destination address(32 bits + 32 bits)
  • 用16进制表示
• Options：不要求知道有就行

IPv4 Address(32bits)

IP地址，网路上的每一台主机(包括路由器)的每一个接口都会分配一个全球唯一的32位的标识符

点分十进制记法：每一段取值范围为0到255。

每一个IP地址都被划分为网络号和主机号,根据网络号的长度，将IP地址划分为5类：A,B,C,D,E。

其中ABC为单播地址

网络地址

网络地址保留，主机号部分为0。

IP地址与default mask(默认掩码)按位与运算。

• Class A: 255.0.0.0
• Class B: 255.255.0.0
• Class C: 255.255.255.0

网络号m位，主机号n位，该网络可分配地址数：$2^n -2$

• 同一局域网上的主机或路由器的IP地址中的网络号必须是一样的。
• 路由器总是具有两个或两个以上的IP地址，路由器的每一个接口都有一个不同的网络号的IP地址。

子网划分 subnetting

• 子网划分：在网络内部将一个网络块进行划分以供多个内部网络使用，对外仍是一个网络。
• 子网：一个网络进行子网划分后得到的一系列结果称为子网。
• 子网掩码(subnet mask)：与IP地址一一对应，是32 bit 的二进制数，置1表示网络位，置0表示主机位。

例题：将IP地址空间192.168.1.0/24按网络号递增顺序分配给3个局域网LAN1~LAN3。

LAN1：必须分配128个地址

LAN2.LAN3：每个分配64个地址。

子网	分配地址数	网络地址	子网掩码
LAN1	95	192.168.1.0	255.255.255.128
LAN2	56	192.168.1.128	255.255.255.192
LAN3	60	192.168.1.192	255.255.255.192

Classless Inter Domain Routing(CIDR)

• 去除IP类别
• 使用掩码进行路由
• 地址聚合
• 灵活(Arbitrary)划分网络号和主机

Routing Table

组成：IP address，netmask，outgoing inrerface，next hop address

路由器表项匹配和转发流程

Longest matching prefix routing 最长前缀匹配原则:

1. 从收到的分组的首部提取IP地址D
2. 对路由表中的每一行，将子网掩码和D逐位相与，若结果与该行的目的网络地址匹配，则将分组传送给该行指明的下一跳路由器，如果有多个匹配项，则选择前缀匹配最长的表项。若没有匹配项，则执行3
3. 若表中有一个默认路由，则将分组传送给路由表中所指明的默认路由。

DHCP(Dynamic Host Configuration Protocol)

动态主机配置协议

DHCP服务器能为接入网络的主机自动分配IP地址，同时还能分配子网掩码，DNS服务器地址，默认网关等。

IP与MAC地址

ip地址在IP数据包的首部，而MAC地址在MAC帧的首部。

IP地址生命周期为整个传输过程，而MAC地址的声明周期只有1跳。

ARP 地址解析协议

ARP表：IP地址与MAC地址的映射

• A已知B的IP地址，需要获得B的MAC地址。
• 如果A的ARP表中缓存有B的ip地址与MAC地址的映射关系，直接从ARP获取。
• 如果A的ARP表中未缓存B的ip地址与MAC地址映射，则A广播包含B的IP地址的ARP query 分组
• B收到ARP query分组后，将自己的MAC地址发送给A
• A缓存B的ip与MAC映射

NAT(Network Address Translation)

网络地址转换(NAT)：将私有地址转化为公有IP地址的转换技术。

• A类地址：10.0.0.0/8
• B类地址：172.16.0.0/12
• C类地址：192.168.0.0/16

动态NAT表项

• A：发送TCP报 10.0.0.1:3723 -> 18.7.22.83:80
• R：路由器动态创建NAT表项： (Local)10.0.0.1:3723—(Global)123.116.156.133:33120—(Peer)18.7.22.83:80 改TCP报为123.116.156.133:33120 ->18.7.22.83:80
• S：服务S回数据18.7.22.83:80 -> 123.116.156.133:33120
• R：查NAT表，改TCP报为18.7.22.83:80 -> 10.0.0.1:3723
• A：收到数据包18.7.22.83:80 -> 10.0.0.1:3723
• (连接过程中使用该NAT表项，当连接关闭时或长久未使用的NAT表项，删除)

IPV6

• Address space
  • 128bits,Total $3*10^{38}$
• 不再支持分片，
• 没有校验码，由上层进行校验

Header:

16位为一段，：分割，每段用四个16进制数表示：

简化表示：8000:0000:0000:0000:0123:4567:89AB:CDEF

• 省略前导零：

  8000:0:0:0:123:4567:89AB:CDEF

• 零位组压缩:一组或多组 16 位全零可替换为双冒号

  8000::123:3456:89AB:CDEFS

ICMP(Internet Control Message Protocol)

功能一：向源端报告意外事件

• 目的不可达(Destination Unreachable)：路由器无法定位目标地址；带有不分片(DF)位的数据包，应网络不支持大数据包而无法传递
• 超时(Time Exceeded)：数据包计数器(TTL生存时间)归零，导致数据包被丢弃
• 源抑制(Source Quench)：主机收到该消息后，降低发送速率，缓解网络拥塞
• 重定向(Redirect)：路由器发现数据包路由错误，通知源主机采用更好的路由

功能二：用于网络测试

• 回显请求与回显应答(ECHO and ECHO Reply)：ping命令的原理，用于网络连通性测试
• 时间戳请求与应答(Time Stamp Request and Reply)：可用于测量网络延迟等
• 路由通告/请求(Router advertisement)：帮助主机发现附近的路由

ICMP报文格式

• ICMP报文的前四个字节是统一的格式

路由协议

每一个区域内属于：Interior gateway Protocol 内部网关协议

区域与区域之间属于：Exterior gateway protocol 外部网关协议

RIP(路由信息协议)

• Direct implementation(实现) of Distance Vector Routing(距离向量路由算法)
• Path costs are based on number of hops
• RIP messages are transmitted in UDP packets
• Interior gateway Protocol 内部网关协议

OSPF

• Dynamic algorithm:adapt to changes in the topology automatically and quickly(自动适应网络拓扑图的变化)
• Internal routers 内部路由器

BGP(Border Gateway Protocol) 边界网关协议

• Policies are typically manually(手动的) configured into each BGP router.
• Exterior gateway protocol 外部网关协议