概论

Internet

网络的网络

“网”的构成：点和边

Internet的构成

节点：主机（host）路由器交换机
通信链路：接入链路主干链路
协议

从网络类型构成来看，互联网可以分为三个子系统：边缘、接入、核心

ISP

Internet Service Provider 因特网服务提供商

端系统通过ISP接入因特网

网络边缘

由端系统（主机）构成

主机分为客户client 和服务器server

通信模式

C/S（客户/服务器模式）
- 客户端向服务器请求、接收服务
p2p（对等模式）
- 没用专门的服务器

通信方式

面向连接的方式：TCP服务
- TCP: Transmission Control Protocol 传输控制协议
- 需要握手，可靠的传输
- 适用于文件传送，登录
- 面向字节流：TCP 将数据视为一个连续的字节流，在传输过程中没有明确的边界。
无连接的方式：UDP服务
- UDP: User Datagram Protocol 用户数据报协议
- 无连接，不可靠传输
- 适用于流媒体，远程会议
- 面向报文：UDP 保持应用层数据的边界，并将应用层传递给 UDP 的数据块作为一个完整的单位进行传输。

网络核心

网络核心主要关注：在路由器的网状网络中，数据怎样传输

电路交换

为每个呼叫预留一条专有线路，如传统电话网

专用资源，不共享
保证性能

分片

网络资源（如带宽）被分成片，常见：频分，时分，波分三种方式

频分 FDM 是在可用频率内进行分片
时分 TDM 是按周期，在每个周期内分片
波分 WDM 可以看作是对于光波的频分

![[../../img/Pasted image 20230908185239.png]]

电路交换不适合计算机网络

建立连接时间长
计算机通信有突发性，若使用电路交换，易造成浪费
可靠性不高

分组交换

带宽资源不分片，在传输时使用全部带宽
无需建立电路，有数据包就发出去
传输数据被分组
特性：存储-转发
缺点：丢包、延时长、抖动

时延

发送、传播、处理、排队

排队延迟和丢失

如果到达速率 > 链路输出速率：

分组将会排队，等待传输
如果路由器缓存用完，则分组被抛弃

统计（时分）多路复用

多个源主机向同一段链路发送分组，此时用统计多路复用，每个源主机得到的带宽取决于每个源主机的发送量，发的越多，得到的带宽越大，发送一样多的数据则平分该链路的带宽

相当于一种不固定分配时间的时分复用，故也称异步时分多路复用

带宽

最大传输速率

有效速率

例题：链路带宽 50kbps，传播时延 250msec；数据长度 1000bits；采用应答方式，应答发送时延不计，求有效速率。

数据往返时间 $250*2 = 500$ 数据发送时延 $1000/50k = 20 ms$ 一个 transaction 完整延时 $520ms$ 有效速率（有效带宽）： $20/520 * 50kbps = 1.92kbps$

接入网和物理媒体

网络边缘通过 接入网 接入网络核心

DSL: Digital Subscriber Line 接入网
bps: bits per second 描述接入网的带宽

住宅接入网

modem：调制解调器

mo - 调制；dem - 解调

将上网数据调制加载在音频信号上，在电话线上传输，之后在局端将其中的数据解调出来

这是一种传统的接入网模式，会导致接听电话时网速受到影响，现在家庭接入网一般不走电话线。

线缆网络

有线电视信号线缆双向改造 FDM: 在不同频段传输不同信道的数据，数字电视和上网数据采用上下行的方式

低速上行，高速下行

单位接入网

端系统直接接到以太网络交换机上

无线接入网

各无线端系统共享无线接入网络（端系统到无线路由器）

无线局域 Wireless LAN ：建筑内部
无线广域 Wireless WAN ：范围10km

物理媒体

导引型媒体:（可见）信号沿着固体媒介被导引：同轴电缆、光纤、双绞线
非导引型媒体：（不可见）开放的空间传输电磁波或者光信号，在电磁或者光信号中承载数字数据

光纤：高速，低码率（长距离不受电磁噪音干扰）

Internet 结构和 ISP

之前的视角：网络边缘 通过接入网 网络核心

以下用另一种视角：==网络的网络==

端系统通过接入ISPs (Internet Service Providers)连接到互联网

住宅，公司和大学的ISPs
接入ISPs相应的必须是互联的

![[../../img/Pasted image 20230910221011.png]]

ICP

Internet Content Providers 互联网内容提供商

比如一些大企业，会在各地部署自己的网络，连接自己的DC(data center)，使自己的DC更靠近用户，避免各地的客户端通过ISP长途跋涉

![[../../img/Pasted image 20230913194835.png]]

分组延时、丢失和吞吐量

分组丢失和延时是怎样发生的？
在路由器缓冲区的分组队列：分组到达链路的速率超过了链路输出的能力，分组等待排到队头、被传输

![[../../img/Pasted image 20230913195652.png]]

四种分组延迟

节点处理延时
排队延时
传输延时
传播延时

传输 vs 传播

![[../../img/Pasted image 20230913214750.png]]

分组丢失

链路的队列缓冲区有限
分组到达一个满队列时会丢失
分组可能丢失之后会：
1. 被前一个节点重传（一些可靠的协议）
2. 被源端系统重传
3. 根本不重传（一些不可靠的协议）

吞吐量

在源端和目标端之间传输的速率

平均吞吐量是不同端到端中的最小吞吐量

协议层次及服务模型

协议和服务的区别
服务(Service)：低层向上层提供它们之间的通信能力，是通过原语 (primitive)来操作的，垂直。
协议(protocol) ：对等层实体(peer entity)在相互通信的过程中，需要遵循的规则的集合，水平。

协议栈

封装和解封装

各层次的协议数据单元

应用层：报文(message)
传输层：报文段(segment) ：TCP段，UDP数据报
网络层：分组packet（如果无连接方式：数据报 datagram）
数据链路层：帧(frame)
物理层：位(bit)

应用层

应用层原理

应用架构

C/S 客户服务器模式
1. 拓展性差
2. 太依赖服务器，可靠性差
p2p 对等模式
- （迅雷，流媒体等）每个人不仅是下载者，还要用自己的pc贡献上传速度
混合

分布式进程通信

套接字 socket

套接字是进程与计算机网络的接口，是==应用层和传输层之间的接口==。

可以理解为应用层用传输层的服务时的一个约定，用个代号（sockect是==整数==）标示通信的双方或者单方。

TCP socket

4元组：源IP ，源port，目标IP ，目标port

sockect是本地存储的一个代表了通信双方信息的整数，每个客户端在本地有自己的socket

UDP socket

2元组：源IP，源port

UDP是无连接服务，不需要先握手确认连接
但是在==发送==报文时，必须要指定对方的ip和udp port

==x元组只是一种为了区分socket的标识，在实际的数据包传输过程中，UDP数据包的头部也包含了源IP地址和源端口号。==

安全 TCP

WEB and HTTP

http: 超文本传输协议

HTTP是无状态的，服务器并不维护关于客户的任何信息

HTTP 报文

request请求和 response响应两种

![[../../img/Pasted image 20231109190400.png]]

响应状态码

200: OK 400: Bad Request 403: Forbidden 404: Not Found

Cookies

cookie 是 sessionID 和其他相关数据 发送并存储 在客户端（浏览器）的载体

Cookie 生成过程：

新用户发送请求给服务器
服务器发现是新用户（不含cookie），在响应报文中添加一个cookie的首部行
用户接收之后，在用户端系统中保留有一个cookie文件，由用户的浏览器管理
用户再次给同一站点发送请求，服务器识别到cookie，站点得知用户信息，做出相应动作

![[../../img/Pasted image 20231109191231.png]]

有关session

==当最初的 HTTP请求到达服务器时，该Web站点产生一个唯一的 Session ID，并以此作为索引在服务器数据库中产生一个会话（Session），随后 Session ID 以 Cookie 的形式响应并存储在浏览器。==

用户第一次请求服务器的时候，服务器根据用户提交的相关信息，创建对应的 Session ，请求返回时将此 Session 的唯一标识信息 SessionID （以 cookie 的形式）返回给浏览器，浏览器接收到服务器返回的 SessionID 信息后，会将此信息存入到浏览器的 cookie 中，同时 Cookie 记录此 SessionID 属于哪个域名。
当用户第二次访问服务器的时候，请求会自动判断此域名下是否存在 Cookie 信息，如果存在自动将 Cookie 信息也发送给服务端，服务端会从 Cookie 中获取 SessionID，再根据 SessionID 查找对应的 Session 信息，如果没有找到说明用户没有登录或者登录失效，如果找到 Session 证明用户已经登录可执行后面操作。
Cookie 和 Session ：你真的了解 Cookie 和 Session 吗? - 纯洁的微笑 - 博客园

Web缓存（代理服务器）

目的：为了有更快的响应速度

下图是增加接入链路带宽和 web缓存两种方法的对比： ![[../../img/Pasted image 20231109192055.png]]

增加带宽是直接的解决方法，但价格昂贵
本地缓存是利用了用户访问数据趋同性，将一些经常被访问的数据保存在本地，不用每次都去接入服务器传输数据，成本低
- 问题是本地缓存可能过期（服务器更新数据了，但本地不知道），解决方法是在用本地缓存的数据返回给用户之前，先向服务器发送一个简单的请求（仅查询，不传数据，不用多少带宽，所以不会造成之前拥堵而速度很慢的问题），查询缓存对象是否是最新的。![[../../img/Pasted image 20231109192702.png]]

DNS

DNS默认使用UDP协议
Domain Name System 应用层协议，提供目录服务

人习惯主机名hostname，路由器习惯IP，DNS在中间做转换。

主机名Hostname 和域名Domain Name

hostname: www.google.com
domain name: google.com

DNS虽然叫域名解析，但是实际上是直接把hostname传给DNS服务器去解析的。

FTP

使用TCP协议

File Transfer Protocol 文件传输协议

一种早期的（经典）在网络上传输文件的协议
安全性弱，不加密

控制与数据

![[../../img/Pasted image 20240410155335.png|300]]

端口21：控制连接
端口20：数据连接
控制和数据分别在两个TCP协议上

Email

3个组成部分：

用户代理：outlook等邮箱软件
邮件服务器：outlook等公司的服务器
邮件传输协议：SMTP（Simple Mail Transfer Protocol）

![[../../img/Pasted image 20240410160129.png|300]]

原始的SMTP传输是ascii码
asc码相当于明文，安全性差
asc码范围不够，不能传输文件/汉字等等

多媒体扩展 MIME

多媒体邮件扩展 MIME （Multimedia Mail Extension）

在报文首部用额外的行申明MIME内容类型

![[../../img/Pasted image 20240410163832.png]]

常见有base64编码，相当于把asc码不能表示的东西用base64编码成可以用asc传输的东西

传输层

传输层概览：

应用层向下交付不同进程到传输层，通过端口号作区分
传输层向下交付 socket 和报文段到网络层，通过IP协议进一步封装

多路复用解复用

复用：传输层==向下==是网络层，向下把多个不同进程的内容封装，通信以==主机==为单位
解复用：传输层==向上==是应用层，向上根据 socket 拆封分发，提供以==进程==为单位的服务

所以，传输层实现的复用指的是传输上层不同进程需要的服务（信息），但通过下层传输时却用的是同一个socket

类比：纯正西海岸

UDP 和 TCP 的本质区别

UDP

下图中，从==目标视角==来看，对于不同源IP和port但是相同目标IP和port的进程，他们在传输到目标时，向上走到是同一个socket。

反过来，从==源视角==来看是很自然的，相同源IP和port的进程从同一个socket向下出发。

transport上面的黄色框表示一个socket

TCP

和上面的UDP图有明显的不同：还是同样从==目标视角==来看，对于不同源IP和port但是相同目标IP和port的进程，他们在传输到目标时，向上走到是不同socket，这就是TCP和UDP最本质的区别。

但是为什么会有这个区别呢？

本质原因在于连接，TCP在传输层的socket是四元组，而四元组相比二元组最大的区别就是产生了连接。

从这两个小节的两次“目标视角”的区别就可以很直观的理解这句话了。

UDP

User Datagram Protocol 用户数据报协议
错了就丢

UDP校验和

校验和：把报文段按16bits切分，然后求和，如有进位则回滚。

发送方：把计算的校验和写在UDP的校验和字段
接收方：计算校验和是否符合UDP的校验和字段
- 符合不一定对，可能有残存错误

可靠传输原理

渐增式地开发可靠数据传输协议（ rdt ）的发送方和接收方
只考虑单向数据传输，双向可以看作是两个单向

我理解的可靠数据传输协议：协议本身使用下层提供的不可靠服务，向上层提供可靠的服务。

RDT 1.0

下层的信道是完全可靠的：

RDT 2.0

下层信道可能会出错（下图中采用corrupt表示出错）

解决方案：

使用 ACK/NAK，实现停等协议

RDT 2.1

ACK/NAK 本身可能出错
发送方重复发送

解决方案：

发送方：
- 判断 ACK/NAK 本身是否出错（下图中采用corrupt表示出错）
- 出错 && NAK 都重传
- 发送方发包加上序号seq
接收方：
- 根据seq判断是否是当前等待的包，不是则丢弃，重发当前 ACK

发送方：

接收方：

RDT 2.2

弃用 NAK，为后续发多个分组做准备。

接收方重复发送 ACK0（替代NAK）表示 1号分组出错：

ack error的情况也OK，重发上一个ACK就完事了：

RDT 3.0

丢包会发生死锁：两边都在等待

解决方案：

引入==超时重传==
超时计时器时长应该超过一次往返的时间

bc是超时，d是不合理设置超时导致过早超时：

至此，我们已经得到了一个较完美的协议 RDT 3.0，但是它仍有一个问题：停等协议需要发一个等一个，信道利用率很低。

流水线协议

为了改善这一点，可以使用流水线协议 Pipeline Protocol：

流水线协议有回退N步(GBN)和选择重传(SR) 两种，下一节通过滑动窗口协议这种更通用的协议来具体介绍这两种流水线协议。

滑动窗口协议

根据滑动窗口大小，可以把协议分类：

协议大类	SW	RW	具体分类
停等协议	1	1
流水线协议	>1	1	回退N步 GBN
流水线协议	>1	>1	选择重传 SR

发送窗口

发送窗口存放了已发送的分组：

绿块的是缓冲区，红框是发送窗口
发送窗口大小 < = 发送缓冲区大小

接收窗口

接收窗口存放了已收到的分组：

接收窗口大小 = 接收缓冲区大小

两种流水线的差别：

GBN：接收窗口尺寸 Wr=1，则只能顺序接收
SR：接收窗口尺寸 Wr>1 ，则可以乱序接收

其实理解了发送和接收窗口的原理，就理解了GBN和SR的工作原理。

GBN 和 SR

GBN和SR的不同就在于接收窗口大小不同，所以这两个协议发送端相同，接收端不同。

GBN发送==累积型确认==：始终发送从0开始连续收到的最后一个
SR发送==非累积确认==：每个分组单独确认，接收哪个确认哪个

由于GBN出错的重传代价高，需要重传丢失分组之后的所有分组，所以GBN适合出错率低的场景，而SR适合出错率高的场景。

GBN 实例

SR 实例

TCP

概述

MSS

MSS是TCP中的最大报文段，而MTU是IP协议中的最大报文段。

MSS 是基于 MTU 的一个子集，用于限制 TCP 数据段的大小，确保数据报不会超过链路的 MTU，从而避免分片。
注意，MTU的大小包括IP头部，但是MSS不包括 TCP 和 IP 报头。

TCP报文段结构

ACK（确认号）辨析

注意，TCP中的ACK（确认号）和之前 RDT3.0 有两点==不一样==：

TCP中的确认号以字节为单位
TCP中的确认号x表示收到x==之前==的所有字节，希望收到x字节

往返延时 RTT 与超时

由于RTT变化很大，所以估计RTT时应当对几个最近的测量值求平均，而不是仅用当前的SampleRTT。

超时设置为平均RTT+4倍方差：

TCP 的往返时延估计（RTT）采用了一种自适应算法，通常使用以下公式来计算新的估计值：

\text{新的 RTT} = (1 - \alpha) \times \text{旧的 RTT} + \alpha \times \text{新的 RTT 样本}

其中： • 旧的 RTT = 96ms • 新的 RTT 样本 = 104ms • 权值 $\alpha = \frac{1}{8}$

代入公式计算：

\text{新的 RTT} = (1 - \frac{1}{8}) \times 96 + \frac{1}{8} \times 104

\text{新的 RTT} = \frac{7}{8} \times 96 + \frac{1}{8} \times 104

\text{新的 RTT} = 84 + 13 = 97 , \text{ms}

因此，新的估计往返时延值为 97ms。

TCP的可靠数据传输

TCP是GBN和SR的结合：

采用了GBN的累积确认，确认连续收到的最后一个
采用了GBN的单个重传计时器
结合SR，接收窗口可以大于1，可以接收乱序的分组，分组可以丢弃或者缓存

快速重传

如果发送方收到同一数据的3个冗余（额外）ACK，重传最小序号的段。

piggybacking

Piggybacking 是指在一个方向传输数据时，附带返回另一个方向的 ACK 确认。例如，当接收方需要发送数据给发送方时，会把 ACK 信息和数据一起打包发送，减少额外的 ACK 数据包，从而提高效率。

piggybacking 优化了 TCP 的传输效率

TCP的流量控制

使用TCP的 rwnd 通知/接受窗口字段，向对方通告自己空闲的buffer大小，达到流量控制的效果。

TCP的连接管理

三次握手

关闭连接

客户端，服务器分别关闭它自己这一侧的连接

发送FIN bit = 1的TCP段

一旦接收到FIN，用ACK回应：

接收到FIN段，ACK段可以和它自己的FIN段一起发送

TCP拥塞控制

一种端到端的拥塞控制

拥塞感知

如何探测到拥塞：

网络拥塞：某个路由器缓冲区没空间了，被丢弃，概率大
出错被丢弃：各级错误，没有通过校验，被丢弃，概率小

拥塞窗口

维持一个拥塞窗口的值，CongWin：表示发送端限制已发送但未确认的数据量的上限。

具体控制方法：

超时：CongWin降为1
三个ACK：CongWin降为一半

需要结合后面讲的慢启动和AIMD，形成完整的TCP拥塞控制。

与流量控制的联合动作

取两者的最小值：

TCP慢启动

当连接开始时，==指数性==增加发送速率，直到发生丢失。

每一个RTT，CongWin加倍
每收到一个ACK，CongWin+1
这两句话含义是一样的，因为每一个RTT收到的ACK也是加倍的。

TCP的AIMD机制

Additive Increase Multiplicative Decrease

AIMD机制：

加性增：逐步增加发送速率
乘性减：在检测到拥塞时大幅减少发送速率

三个重复和超时的不同处理：

三个重复是快速重传机制快速重传

图解：

网络层：数据平面

网络层导论

路由和转发

网络层最主要的两大作用是==转发==和==路由==：

数据平面负责转发
- 局部功能：局部选择转发端口
控制平面负责路由️
- 全局功能：全局规划路由路径

IP协议

从传输层接收TCP/UDP报文，封装成IP报文传输
经过多跳转发、选择路由器
- 经过每个路由器也要进行小的解封装，以判断下一跳路径
到达目标之后，把IP报文解封装成TCP/UDP报文交给上层。

网络层在控制平面还有==信令协议ICMP==和一些==路由协议==，比如 RIP。

连接服务

网络层和传输层连接服务的区别：

网络层: 在2个主机之间，涉及到路径上的一些路由器
传输层: 在2个进程之间，很可能只体现在端系统上 (TCP连接)

路由器组成

路由器结构

路由：执行路由选择算法，生成路由表
转发（switch fabric）：根据路由表进行选择端口，进行分组的转发

输入端口 input ports

基于目标的转发：仅关注目标IP地址，使用==最长前缀匹配==。
通用转发：sdn的新方法，基于头部字段转发

输入端口缓存

同样地，输出端口也需要类似的缓存

交换结构 switch fabric

将==分组==从输入缓冲区传输到合适的输出端口

基于memory

需要通过bus（系统总线）两次：进memory、出memory

基于bus

500

通过共享总线避免了基于memory的需要经过两次总线的问题，同时，由于共享总线，产生了新的总线竞争的问题。

通过互联网络的交换

500

互联网络就是字面意思，不是指互联网的意思
互联网络有多种：榕树、crossbar等

IP：Internet Protocol

IP数据报格式

500

头部一般是20字节 $\begin{cases}20B=4B*5行\\1行占4B=32b\end{cases}$ ，不包含options

IP分片和重组

重组只在最终的目标主机进行

网络链路有==最大传输单元==MTU的限制，所以一个大的IP数据报在传输时需要分片fragmented。

分片成的每个小数据报有==相同的ID==、==不同的fragment offset==
最后一个分片的fragflag标记为0，表示这是最后一个分片

500

蓝笔标注的是fragment offset，==以8B为单位==

例题：根据MTU分片传输

500

注意，最后一个分片不满1480B，但是偏移仍然按照1480计算，对齐粒度是1480B

IPv4地址

32位标识，分为子网部分（高位）和主机部分（低位）

子网 subnet

IP地址的子网前缀部分一致的主机组成了一个子网。

子网内部的主机在IP层面==一跳可达==，不需要路由器，只需要交换机。

实例：有几个子网

下图共有6个子网，每个蓝色部分是一个子网： 500

IPv4地址分类

500

IP地址分为三个部分：class号、network、host
class：ABC类是单播地址；D类是组播地址；E类是预留
路由器的表项是以network为单位，不关注具体的host

特殊的IP地址

一些约定：

子网部分: 全为0---本网络
主机部分: 全为0---本主机
主机部分: 全为1---广播地址，这个网络的所有主机

500

所以在算某类IP地址的总主机数时，计算network和host时都要分别减去2，network和host分别是全0/1的情况都不指向特定主机。

内网专用IP地址

500

IPv4编址：CIDR

CIDR: Classless InterDomain Routing （无类域间路由）

无类抛弃了原本分类的class部分，IP地址中network和host的划分可以在任意的位置。

无类通过子网掩码来实现

500

例题：分配网络前缀

DHCP

DHCP: Dynamic Host Configuration Protocol 动态主机配置协议
工作在应用层，使用UDP协议

主机获取IP地址的方法一般有两种：

系统管理员在某个系统文件中进行配置
使用 DHCP

DHCP允许主机在加入网络的时候，动态地从服务器那里获得IP地址。

动态获取的三次握手： 500

DHCP 返回四个元素：

IP 地址
子网掩码
第一跳路由器的IP地址（默认网关）
DNS服务器的域名和IP地址

实例

500 500

层次编址: 路由聚集

路由聚集 route aggregation

Q：如何获得一个网络的子网部分? A：从ISP获得地址块中分配一个小地址块

一个大的子网x.x.x.x/20，从host部分取3位可以分成8个小子网（子网的子网），每个以x.x.y.y/23表示。

500

路由聚集就是重新合并这些小子网：

500

Q: 一个ISP如何获得一个地址块?
A: ICANN: Internet Corporation for Assigned

路由聚集允许少量的空洞：

背景：一个大的子网x.x.x.x/20，从host部分取3位可以分成8个小子网（子网的子网），每个以x.x.y.y/23表示。
假如，现在一个大子网Y，Y中有这8个小子网中的7个，这个大子网Y也可以进行x.x.x.x/20的路由聚集，通过路由器向外通告自己接收x.x.x.x/20。
这时，假如8个小子网中剩下的那个子网x.x.y.z/23在另一个大子网Z中，即使Y的路由聚集存在空洞也不会影响Z。因为Z会通过路由器向外通告接收z.z.z.z/23，而根据==最长前缀匹配==的原则，z.z.z.z/23的消息不会被路由聚集的大子网Y接收。

NAT：网络地址转换

NAT实现内外网地址的转换，既节省IP资源，又增加内网安全性：

500

转换对存在NAT转换表中

使用NAT时，内网主动向外网发起的连接是没有问题的，可以发送并返回；但是对于外网主动向内网发起的连接就有问题了。

比如外网要访问这个内网的80端口的web服务，外网找到最后一跳的路由器之后，并不能指定到底访问哪个内网主机哪个端口，这时候就需要配置==内网穿透==。

ARP协议

ARP 是 地址解析协议（Address Resolution Protocol）的缩写，它是计算机网络中用来将 IP 地址 转换为对应的 MAC 地址 的一种协议。

ARP 是 TCP/IP 协议栈的重要组成部分，主要工作在网络层和数据链路层之间。

IPv6

IPv6 数据报格式

固定的40 字节头部
数据报传输过程中，不允许分片

IPv6头部

500

相比IPv4的变化：

500

隧道 tunneling

在IPv4路由器之间传输的IPv4数据报中携带IPv6数据报。

500

SDN和通用转发

之前介绍的网络层都是传统方式，而引入SDN是一种新型的网络层实现方式。

传统方式的缺点

==垂直集成==是传统方式实现的网络层的最根本问题：

==硬件、私有网络设备OS、协议私有实现==，三方面**集成在一个网络设备中
垂直集成意味着每个设备自己实现了数据平面和控制平面，无法实现逻辑上集中的控制平面，导致控制平面只能采取==固化的分布式==实现。
分布式带来了==控制逻辑固化、升级/管理困难、不利于创新==等多种问题

这里说的创新是集成的反义词，有关创新的理解可以参考IBM开放PC设计的故事：
1981年8月，IBM推出了IBM PC。 1982年，IBM公开了IBM PC上除BIOS之外的全部技术资料，从而形成了PC机的“开放标准”，使不同厂商的标准部件可以互换。开放标准聚拢了大量板卡生产商和整机生产商，大大促进了PC机的产业化发展速度和创新，但是不久之后IBM也没落了。

500

SDN的优点

逻辑上集中的控制平面，==水平集成==的控制平面。

500

数据平面：分组交换机
- 根据流表的不同设置，分组交换机可以很灵活地实现成（变成）路由器、交换机以及其他网络设备
控制平面：网络控制应用 + 控制器
- 逻辑上集中，网络管理容易
- 主要功能是下发流表给交换机

SDN架构

三层：SDN交换机 + 控制器 + 控制应用

通用转发

通用转发是==SDN集中下发流表==这一特点带来的新的转发模式：使用简单的分组处理规则，实现灵活地可编程式转发（严格来说不能写转发，交换机也可以做丢弃的行为）。

SDN下发的流表定义了路由器接收到分组的处理步骤：匹配 + 行动。

500

网络层：控制平面

路由选择算法

路由：按照某种指标（传输延迟、所经过的站点数目等）找到一条从源节点到目标节点的较好路径。

以网络（一个个子网）为单位进行路由：路由信息通告 + 路由计算

这里的“网络”是指所有节点地址前缀相同，且物理上聚集，大致可以理解成子网或者经过某种程度的路由聚集之后的子网
有关子网内部的“路由”将在链路层具体讨论

网络层和链路层功能辨析：

网络层实现：网络 - 网络的路由（ = 路由器 - 路由器之间路由）
链路层实现：路由器 - 主机之间的通信

最优化原则

汇集树就是最优路径形成的树。

路由选择算法最终会从原始==拓扑==（a）中找到==汇集树==（b）

LS算法

link state 链路状态路由选择算法
全局算法
Dijkstra算法：Find Shortest Paths from Source to all Vertices using Dijkstra’s Algorithm

工作过程：

发现相邻节点，获知对方网络地址
测量到相邻节点的代价（延迟，开销）
组装一个LS分组，描述它到相邻节点的代价情况
将分组通过扩散的方法发到所有其它路由器
- 以上4步和算法没关系，目的是让路由器获得==拓扑==和==边代价==，为算法做准备
通过==Dijkstra算法==找出最短路径（真正的路由算法）
1. 每个节点独立算出来到其他节点（路由器=网络）的最短路径
2. 迭代算法：第k步能够知道本节点到k个其他节点的最短路径

算法准备部分

前四步让路由器获得==拓扑==和==边代价

算法部分

选择算法：Dijkstra

例子

标黑的节点是永久节点
最终的红色路径就是汇集树

缺点：可能带来==震荡==，比如当使用链路流量作为算法的边代价时

DV算法

距离矢量路由选择（distance vector routing）
分布式算法

基本思想：

每个路由器维护一张路由表
每个路由器与相邻路由交换路由表信息，以更新（优化）自己的路由表
以此迭代更新，最终会形成最优路径

实例

算法原理

好消息传得快

好消息：下图A节点新接入链路（A可达，之前不可达）

坏消息传得慢

坏消息：A节点突然断链。

这时候B、C节点陷入了相互交换的无限循环中，最终这两个节点到A的距离变成INF
本质原因是C可达A的前提是B可达A，但是突发坏消息（B不可达A）之后，BC仍旧交换路由表更新，造成了无限交换的问题

解决方案：水平分裂算法

还是以上面坏消息的例子来看，解决方法在于使C分裂，向左右传递不一样的消息：C知道要经过B才能到达A，所以C向B报告它到A的距离为INF（避免了循环），而C告诉D它到A的真实距离

但是水平分裂算法在==环路==的情况下，仍然无效。

AS内部的路由选择

前一节路由选择算法是从算法的角度入手，本节是从协议的角度具体去看。

AS（Autonomous System，自治系统）
是指一个网络或一组网络，由一个或多个网络运营者在统一的路由策略下进行管理和控制。
在路由协议中，AS是重要的基本单位，主要用于区分不同的网络域。

RIP

RIP ( Routing Information Protocol)

采用了==DV算法==：

最多25个子网反映了RIP只适用于小的网络范围

RIP图示：

RIP进程处理

网络层的协议使用了传输层的服务，以应用层实体的方式实现：

RIP 以==应用进程==的方式实现：route-d (daemon 守护程序）
通告报文通过传输层==UDP报文==传送，周期性重复

OSPF

OSPF (Open Shortest Path First)

使用LS算法：

LS 分组在网络中（一个AS内部）分发
全局网络拓扑、代价在每一个节点中都保持
路由计算采用Dijkstra算法

OSPF相比于RIP

安全: 所有的OSPF报文都是经过认证的
- 在IP数据报上直接传送OSPF报文 (而不是通过UDP和TCP)
允许有多个代价相同的路径存在 (在RIP协议中只有一个)
对于每一个链路，对于不同的TOS有多重代价矩阵
- 例如：卫星链路代价对于尽力而为的服务代价设置比较低，对实时服务代价设置的比较高，支持按照不同的代价计算最优路径，如：按照时间和延迟分别计算最优路径
对单播和多播的集成支持
- Multicast OSPF (MOSPF) 使用相同的拓扑数据库，就像在OSPF中一样
在大型网络中支持层次性OSPF

层次化 OSPF

把一个大型AS的分为骨干（==backbone==）和本地区域（==area n==）：

链路状态通告分别仅在backbone内部和area内部进行
areas和backbone之间通过区域边界路由器（area border routers）通告

最终这个大型AS通过边界路由器（boundary router）和其他AS通信。

AS之间的路由选择：BGP

上一节介绍了一个AS内部的路由选择，本节介绍AS之间的路由选择

为什么要把互联网分成一个个AS的形式？
由于规模太大，所有节点都在一个平面是不行的，必须层次化路由设计，把网络分为2个层次路由：AS内部和AS外部。
AS内部采用自定义的路由选择；从AS外部看，一个AS/子网用一个ASN（AS Number）唯一标识，解决了规模太大的问题。

BGP （Border Gateway Protocol）：自治区域间路由协议

BGP 提供给每个AS以下方法：

eBGP: 从相邻的ASes获得子网可达信息
iBGP: 将获得的子网可达信息传遍到AS内部的所有路由器
根据==子网可达信息==和==策略==来决定到达子网的“好”路径

两个BGP路由器之间通告的例子：

BGP报文使用==TCP协议==传输

路由表项是由AS内部和AS外部的路由共同决定的：

热土豆路由

一种路由选择策略：选择最小域内代价的网关，不考虑域间代价

内/外部网关协议的不同

策略方面:

Inter-AS 外部网关：管理员需要控制通信路径，谁在使用它的网络进行数据传输
Intra-AS内部网关：一个管理者，所以无需策略；AS内部的各子网的主机尽可能地利用资源进行快速路由

规模方面:

外部的AS间路由必须考虑规模问题，以便支持全网的数据转发
AS内部路由规模上不存在问题
- 如果AS 太大，可将此AS分成小的AS，规模可控，AS之间只不过多了一个点而已
- 或者AS内部路由支持层次性，层次性路由节约了表空间, 降低了更新的数据流量

性能方面：

Intra-AS: 关注性能
Inter-AS: 策略可能比性能更重要

SDN控制平面

4.5 SDN和通用转发

ICMP：因特网控制报文协议

ICMP: Internet Control Message Protocol

由主机、路由器、网关用于传达网络层控制信息：

错误报告：主机不可到达、网络、端口、协议
Echo 请求和回复（ping）

ICMP处在网络层，但是在IP协议的上面：

ICMP消息由IP数据报承载

ICMP 报文:

类型
编码
加上IP数据报的头8B：第一个导致该ICMP报文的IP数据报

traceroute

链路层

引论

网络层解决了一个网络如何到达另外一个网络的路由问题。

而链路层则解决在一个网络内部如何由一个节点（主机或者路由器）到达另外一个相邻节点。

在链路层，我们基本只讨论局域网内的链路层功能，因为广域网由于节点之间距离非常远（网课的例子是中国到日本到夏威夷），所以广域网链路层是采用点到点的链路，非常简单，没什么好讲的。

而局域网中，链路层采用的是多点连接的方式，其中就包含集线器hub、交换机switch等结构。

链路层术语

旅行者例子

旅行者是数据报，交通段是链路，交通工具是链路层协议。

链路层服务

成帧，链路接入：

将数据报封装在帧中，加上帧头、帧尾部
如果采用的是共享性介质，信道接入获得信道访问权
在帧头部使用 “MAC” （物理地址）而不是IP地址来标示源和目的

其他：

流量控制
差错检测和纠正

链路层功能在 “适配器”上实现 (aka network interface card NIC) ，最常见的就是以太网卡。

差错检测和纠正

计算机网络中一般采用奇偶校验和循环冗余校验两种方式作差错检测，但是这两种方式不能定位错误，因此无法纠错。

循环冗余校验漏检率低，检错能力强，虽然计算复杂，但是非常易于用硬件实现，因此被广泛应用于链路层

最常见的纠错码，如海明码，可以进行前向纠错。但是由于纠错码的开销较大，一般不在计算机网络中使用。计网中采用检错重传的方式实现纠错或者直接丢弃不纠错。

奇偶校验

CRC 循环冗余校验

前置知识

双方采用同一个生成多项式
采用模2除法运算
1. 模2就是异或
2. 模2除法是指原来除法的竖式减法部分的减法改成模2运算
3. 注意，模2除法判断是否够除（商写1还是0），只看位数，不看大小，
4. 详见例题
余数作为冗余码（EDC）

生成多项式：

校验过程

sender：

receiver：

例题

CRC 性能

多点访问协议

单个共享信道的广播型链路

当2个或更多站点同时传送时会产生冲突（collision），所以需要一个协议来控制如何使用共享信道。

MAC（媒体访问控制）协议

MAC协议大致有三大类：

信道划分
- 把信道划分成小片（时间、频率、编码）
- 分配片给每个节点专用
随机访问
- 信道不划分，允许冲突
- 冲突后恢复
依次轮流
- 节点依次轮流
- 但是有很多数据传输的节点可以获得较长的信道使用权

信道划分

TDMA FDMA

随机访问

CSMA

在传输之前先侦听信道：

如果侦听到信道空闲，传送整个帧
如果侦听到信道忙，推迟传送

以太网 CSMA/CD

以太网是有线局域网，便于冲突检测CD
而无线局域网无法直接检测冲突，所以采用了冲突避免CA的方法（下一节）

增加了冲突检测CD技术：没有传完一个帧就可以在短时间内检测到冲突 检测到冲突发生：放弃传输终止，减少对信道的浪费
放弃传输之后，适配器进入指数退避状态：在第 $m$ 次失败之后，随机选择一个 $K \in \{1,2,...,2^{m-1}\}$ ，等待 $K*512$ 位时后，重新开始侦听信道。

位时（bit time）：网络通信中用于描述时间长度的一个单位，具体是指传输一个比特（bit）所需要的时间。

无线局域网 CSMA/CA

无法CD，尽量事先避免冲突

SIFS：Short Interframe Space 最小帧间间隔
- 在802.11系列无线局域网中SIFS是固定值
DIFS：DCF Interframe Space 分布式帧间间隔
- $DIFS = SIFS + (2 * Slot time)$

LANs

MAC 地址和ARP

网络层用IP地址，链路层用MAC地址，ARP是IP和MAC之间的转换协议。

补充：其实网络层不止有IP协议，还有别的协议走别的地址，不用IP地址

LAN（MAC/物理/以太网）地址:

用于使帧从一个网卡传递到与其物理连接的另一个网卡 (在同一个物理网络中 )
48bit MAC地址一般固化在适配器的 ROM，有时也可以通过软件设定
理论上全球任何2个网卡的MAC地址都不相同
e.g.: 1A-2F-BB-76-09-AD

网络地址和物理地址分离的好处：

ARP 协议

路由到其他LAN的过程

主机A在链路层为IP数据报封装上以太网帧（MAC地址）
交换机R从链路层开始解封装，提取出IP分组，交给上层IP协议
交换机R在网络层的路由分析之后，再次在链路层为IP数据报封装上==新的以太网帧==，发送给B

以太网帧结构

以太网使用 CSMA/CD

以太网 CSMA/CD

Hubs and Switches

链路层链路的发展大致是：

同轴电缆：共享总线，广播，容易冲突，容易断
集线器 hub：逻辑上还是共享总线，物理上把那根总线放到一个盒子里面集中，让所有主机来连盒子上的端口，好处是总线不暴露在外面，暴露在外面的只是各个主机到盒子的线，所以总线不容易断了。
交换机 switch ：不再是共享总线了，不广播，改为由 switch table 进行端口转发

Hubs

Switches

从前面的章节，我们知道路由器负责子网与子网之间的分组传送。

而交换机可以看作子网内部的小“路由器”，是链路层的存储转发设备，有和路由表类似的 switch table 进行端口转发。

多路同时传输，解决了共享总线的问题
不广播了，选择性转发，偶尔广播泛洪（比如交换表中找不到表项的时候）
可以级联
switch table 是自学习得到的，不需要管理员设置

物理层

物理层的主要功能是提供透明比特流的传输服务

AM FM

码元

码元是指用一个固定市场的信号波形（数字脉冲），代表不同离散数值的基本波形，是数字通信中数字信号的计量单位，这个时长内的信号称为k进制码元，而该时长称为码元宽度。当码元的离散状态有M个时（M大于2），此时码元为M进制码元。 1码元可以携带多个比特的信息量。例如，在使用二进制编码时，只有两种不同的码元，一种代表0状态，另一种代表1状态。

![[../../img/Pasted image 20240410203404.png]]

速率、波特、带宽

速率也叫数据率，是指数据的传输速率，表示单位事件内传输的数据量。
可以用码元传输速率和信息传输速率表示。

码元传输速率

又叫码元速率、波形速率、调制速率、符号速率等。

它表示单位时间内数字通信系统所传输的码元个数(或称脉冲个数、信号变换次数），单位为波特（Baud），波特是速度单位。

1波特表示数字通信系统每秒传输一个码元，这里的码元可以是多进制的，也可以是二进制的，但==码元速率与进制数无关。==

曼彻斯特编码下，码元速率是传输速率的两倍

信息传输速率

又叫信息速率、比特速率，表示单位事件内数字通信系统传输的二进制码元个数（即比特数），单位为比特/秒（b/s）。（即1s传输多少比特）

码元传输速率和信息传输速率的关系

若一个码元携带 n 比特的信息量，则 M Baud 的码元传输速率所对应的信息传输速率为 M x n 比特/秒。

N 进制就是携带 $n = log_2N 个比特（2^n=N）$

带宽

频带宽度，表示在单位事件内从网络中的某一点道另一点所能哦通过的“最高数据率”，常用来表示网络的通信线路所能传输数据的能力，单位为b/s。

例题

带宽 = 两个波长相减

香农公式

香农公式表示极限传输速度：

$C = W*log_2 (1+\frac{S}{N}), \text{(bit/s)}$

W是带宽，单位为Hz

其中，S/N 一般需要通过信噪比 SNR 来计算，相关公式如下：

\begin{cases}SNR=10*log_{10}\frac{S}{N}\\ \frac{S}{N}=10^{\frac{SNR}{10}}\end{cases}

信噪比SNR单位为dB

奈氏准则

在理想低通（没有噪声、带宽有限）的信道中，为了避免码间串扰，极限码元传输率为 2W Baud。

W 是理想低通信道的带宽，单位为Hz
转换为以 bit 为单位：V 表示每个码元离散电平的数目（码元的离散电平数目是指有多少种不同的码元）
- 比如有16种不同的码元，则需要4位二进制位，因此数据传输率是码元传输率的4倍

计算机网络

概论

Internet

Internet的构成

ISP

网络边缘

通信模式

通信方式

网络核心

电路交换

分片

电路交换不适合计算机网络

分组交换

时延

排队延迟和丢失

统计（时分）多路复用

带宽

有效速率

接入网和物理媒体

住宅接入网

线缆网络

单位接入网

无线接入网

物理媒体

Internet 结构 和 ISP

ICP

分组延时、丢失和吞吐量

四种分组延迟

传输 vs 传播

分组丢失

吞吐量

协议层次及服务模型

协议栈

封装和解封装

各层次的协议数据单元

应用层

应用层原理

应用架构

分布式进程通信

套接字 socket

TCP socket

UDP socket

安全 TCP

WEB and HTTP

HTTP 报文

响应状态码

Cookies

有关session

Web缓存（代理服务器）

DNS

主机名Hostname 和 域名Domain Name

FTP

控制 与 数据

Email

多媒体扩展 MIME

传输层

多路复用 解复用

类比：纯正西海岸

UDP 和 TCP 的本质区别

UDP

TCP

UDP

UDP校验和

可靠传输原理

RDT 1.0

RDT 2.0

RDT 2.1

RDT 2.2

RDT 3.0

流水线协议

滑动窗口协议

发送窗口

接收窗口

GBN 和 SR

GBN 实例

SR 实例

TCP

概述

MSS

TCP报文段结构

Internet 结构和 ISP

主机名Hostname 和域名Domain Name

控制与数据

多路复用解复用