概念与术语

什么是计算机网络

从服务角度

计算机网络是分布式服务 + 提供服务的基础设施（包括网络本身）

从具体构成角度

1. 边缘系统（edge）
2. 接入系统（access）
3. 网络核心（core）

什么是协议

规定了格式，次序，动作的规范、标准

边缘系统

模式

1. 客户端 - 服务端
   • 可扩展性不强
2. P 2 P 模式
   每个节点同时是客户端和服务器
   • 多用于文件传输（e.g.: 迅雷），可以同时从多个服务器请求数据片段

方式

1. 面向连接（TCP）
2. 无连接（UDP）

网络核心

线路交换（Circuit Switch）

通过信令系统为两个节点之间找到独享线路
性能有保障
将带宽分片
一般用于电话

带宽划分方式

1. 频分（Frequency-division multiplexing）
2. 时分（Time-division multiplexing）
3. 波分（Wave-division multiplexing）
   光纤通信
4. CDMA

不适合计算机通信

1. 建立时间长
2. 计算机数据交换有突发性，会造成资源浪费
3. 可靠性？

分组交换（Package Switch）

1. 把数据分成包
2. 使用线路全部带宽
3. 存储 - 转发：存储在一个传输主机上之后再传给下一个
   • 牺牲：消耗了额外的排队延迟和存储时间，并且如果路由器缓存用完，分组会被丢弃
   • 换取：不会一直独享线路，从而可以共享线路资源

路由算法（全局）：计算分组传输路径

转发（局部）：将分组从路由器输入链路转移到输出链路

存储转发方式

1. 虚电路（virtual circuit）
   有连接，查虚电路表建立虚电路
2. 数据报（Datagram）
   无连接，独立路由

分组延迟

每一跳（hop）要经历

1. 节点处理延迟
2. 排队延迟
   不确定
3. 传输延迟
4. 传播延迟
   1. LAN: 还没传输完已经收到，信道容量大
   2. WAN: 传输完了还没收到，信道容量小

排队延迟取决于流量强度（Intensity）

取值范围 $(0,1)$
R: 带宽
L: 每个分组长度（字节数）
a: 分组数量

分组丢失

三种处理方案

1. 上一条链路重传
2. 源主机重传
3. 不重传

吞吐量

在源端和目标端之间传输的速率（数据量/单位时间）

• 平均
• 瞬时

吞吐量 $=min(R_{1},R_{2},\dots,R_{n})$

瓶颈链路：路径上吞吐量最小的部分链路

一条链路使用的主机对越多，人均带宽越小，更可能是瓶颈链路

接入网和物理媒体

BPS（带宽）共享 or 独享

接入方式

住宅接入 - 调制解调（modem）

把上网数据调制加载到音频信号上，在电话线上传输，在局端解调出来

调制方式

1. 调频
2. 调幅
3. 调相位
4. 综合调制

DSL (Digital subscriber line) & ADSL

4 k 以下带宽用于语音通话，4 k 以上

拨号调制解调器

线缆网络

有线电视公司把电视信号线缆双向改造
FDM：在不同频道传输不同信道数据，数字电视和上网数据（上下行）

企业接入（Ethernet）

无线接入

物理媒体

导引型媒体

信号沿着固体媒介被导引：同轴电缆、光纤、双绞线
e.g.: 双绞线（TP）——两根绝缘铜导线拧合

非导引型媒体

开放的空间传输电磁波或者光信号，在电磁或者光信号中承载数字数据

物理媒体类型

1. 双绞线
   屏蔽双绞线（STP）——进一步减少电磁干扰；无屏蔽双绞线（UTP）
2. 同轴电缆
   两个铜导体同心而非并行
   用作引导型共享媒体
3. 光纤
4. 陆地无线电信道
5. 卫星无线电信道

ISPs

ISP(Internet Service Providers) 互联网服务提供商
组织和个人通过 ISP 接入互联网

那么 ISP 如何互联呢？

全局 ISP

（全局范围内覆盖）客户 ISPs 和提供者 ISPs 有经济合约
形成市场竞争、合作

ICP 自己部署 DC

靠近全局 ISP，解决全球服务问题和成本问题

Internet 结构

第一层 ISP
e.g.: UUNet, BBN/Genuity, Sprint, AT&T
国家国际覆盖，带宽大，速率高

第二层 ISP：更小的 ISP（通常是区域性）

第三层 ISP：Local ISP

ISP 之间的连接

松散的层次结构

协议

协议层次

layer 好处

• 关注点分离 separation of concerns
• Modularity 层次首先将复杂问题分解为相互独立的子问题。
• 可以更好地组织和分配，结构清晰，不会混乱
• 同时子问题可以引进先进地解决方案，可迭代性强
• 下层向上册提供服务同时可以加入新的服务
• peer-to-peer communication
  害处
• 效率低

封装 Encapsulation

• 加上一个 header 和 footer

{
  "versionAtEmbed": "0.2.2",
  "filepath": "Ink/Writing/2024.5.24 - 0.30am.writing"
}

服务模型

服务访问点

• 用处：用来处理服务谁
• 形式：原语（primitive）
• 地方：层间接口
• 服务访问者通过 SAP 来请求服务，服务方通过原语告诉访问者提供什么服务
• 类型
  面向连接/无连接

• 协议和服务的关系
  

Internet 协议栈

各层次协议数据单元（五层）

• 应用层：message 报文
• 传输层：segment 报文段
• 网络层：packet 分组 datagram 数据报
• 链路层：frame 帧
• 物理层：bit 位

{
	"versionAtEmbed": "0.2.2",
	"filepath": "Ink/Writing/2024.5.23 - 22.47pm.writing"
}

• 应用层
  • 实现网络应用
  • 协议非常多
• 传输层
  • 功能
    1. 区分进程到进程
    2. 让不可靠变可靠
  • 协议
    TCP UDP
• 网络层
  在链路层基础上，传输以分组为单位的端到端（E2E）的数据
  • 功能
    • 转发
    • 路由
  • 协议
    IP 路由协议（一系列）
• 链路层
  点到点（P2P）之间传输以帧为单位数据
  • 协议
    PPP 802.11 (WIFI) Ethernet
• 物理层
  传输比特
  • 发送端
    把链路层传过来的帧（frame）变成物理信号
  • 接收端
    把物理信号还原成帧信号

物理层和链路层协议被封装在网卡中提供

• 表示层和会话层是干什么的？ ➕ 2024-06-19 ✅ 2024-06-24

应用层

应用层协议原理

对话形式

1. P2P
   参与的主机间歇性连接且可以改变 IP 地址
   • 优点
     自扩展性
   • 缺点
     难以管理
2. C/S
3. 混合模式
   C/S+P2P
   1. Napster
      文件搜索：集中
      文件传输：P2P
   2. 即时通信
      聊天：P2P
      在线检测：集中

进程标识和寻址

SAP+IP+Port

采用的传输层协议

• TCP or UDP

约定的端口

• HTTP: TCP 80 Mail: TCP 25 ftp: TCP 22

传输层如何向应用层提供服务

包含内容

• 谁发的
• 发给谁
• 货物

套接字 socket

为了减少传输的信息量，便于管理，发明了套接字（socket）

==用一个整数表示包含的内容 ==

TCP socket

• 4 元组 (源 IP，源 port，目标 IP，目标 port) 的一个具有本地意义的标示
• 维持端节点之间的会话关系

UDP socket

• 二元组（源 IP+ 源 port）的本地标识
• 传输报文时要附上目标 IP 和 UDP port
• 指定一个端节点，不维持会话关系

如何实现应用

根据应用层协议 -> 写程序

应用层协议

定义了运行在不同端系统上的应用 进程如何相互交换报文

• 公开协议
  • 由 RFC 文档定义
  • 允许==互操作 ==
  • 如 HTTP, SMTP
• 专用（私有）协议
  • 协议不公开
  • 如：Skype

衡量指标

1. 数据丢失率
2. 吞吐
3. 延迟
4. 安全性
   常见应用对传输服务的要求
   

传输层提供的服务

TCP & UDP 服务

UDP 存在意义

1. 端口支持
2. 工作量少（无需可靠性，建立连接需要）

Internet 应用及其应用层协议和传输协议

NAT

NAT 会建立一个映射，把公网 IP 的不同端口映射到不同的内网 IP

现在家庭一般都有内网和外网 IP，也就是都通过 NAT 和外网相连

Web 与 Http

Http 使用 TCP，端口号为 80

响应时间模型

往返时间 RTT：一个小分组从客户端到服务端，再回到客户端的时间
响应时间

1. 用于发起 TCP 请求的 RTT
2. 用于发送 HTTP 请求并等待 HTTP 响应的 RTT
3. 文件传输时间

持久与非持久

持久

• 非流水线
• 流水线：不用等前一个请求响应收到后就发送下一个请求

HTTP 请求报文

ASCII 码（可读）

结构


注：cr（回车\r）lf（换行\n）是 http 标准的换行格式，sp 是空格

HTTP 响应报文

TCP 提供字节流服务，不负责字节数边界划分

HTTP 响应状态码

版本迭代

HTTP/1.0

• 简单的 TCP request & response
  HTTP/1.1
• keep-alive 字段，告诉 server 是否要继续请求（无需再次建立 TCP 连接）
• 用满带宽，提高并行（TCP 的拥塞控制起作用）
  SPDY → HTTP/2.0
• pipeline（图片等可以异步加载，先传输网页）
• 去掉冗余的头部（比如说浏览器信息）

Cookies

Web 缓存

网络的 2-8 定律：80% 的人访问 20% 的网站

优点

问题

• 对象有更改
• → conditional get: 加一个头部，有修改就获取，没修改只是传回一个无修改信息

FTP（文件传输协议）

再 C-S 间建立两个 TCP 连接，数据传输（20 端口）和控制传输（21 端口）分别进行

邮件软件是 FTP 的用户代理

STMP 协议

• 持久连接
• 收发邮件报文
• 使用 TCP 协议，25 端口传输报文
• 三个阶段：握手，传输，关闭
• ASCII 码格式（可读），报文必须为 7 位 ASCII 码
• 结构
  • 
  • 首部（From, To, Subject）
  • 主体，ASCII 码
    • MIME 多媒体邮件扩展（multimedia mail extension）<RFC 2045, 2056>：将主题进行 base64 编码，将 ASCII 之外的字符转化成更长的 ASCII 码字符
      

邮件拉取协议

POP3, TMAP, HTTP

DNS

DNS 是在应用层给其他应用（e.g.: Web 应用，FTP 应用，STMP 应用）使用的基础设施

IP 地址 -> 有意义的字符串

P2P 应用

分类

• 结构化
• 非结构化
  • 集中化目录
  • 完全分布式
  • 混合体

CDN

用来解决视频等占用大量带宽的杀手级应用

视频

• 高码率
• 压缩
  • 空间冗余
    同一帧的相同像素可压缩
  • 时间冗余
    相邻帧之间只保留变化的像素
  • CBR: (constant bit rate): 以固定速率编码
  • VBR: (variable bit rate): 视频编码速率随 时间的变化而变化

流化服务

多媒体流化服务 DASH（Dynamic, Adaptive Streaming over HTTP）

告示文件（manifest file）: 提供不同块的 URL

把一个视频分成若干块，每个块进行多种编码，在客户端通过告示文件（manifest file），测算（自身缓冲区大小，带宽…）出之后能最快下载的最高码率的视频块，从而最大程度提高视频码率和流畅度

自适应下载

• 下载什么码率（带宽，缓冲区大小…）
• 从哪里下载（带宽，距离…）
• 什么时候下载（缓冲区有多大）

CDN(Content Distribution Network)

在全网部署多个 CDN 服务器，提前拷贝需要的流媒体资源，用户向服务商请求该资源时，通过域名解析重定向，转到距离最近的 CDN 服务器请求该资源

对于用户来说，整个过程是被隐藏的，只需要配置好服务器的重定向和 CDN 节点

Socket 编程

• 控制报文 vs. 数据报文
• 带内、带外集中式 vs. 分散式
• 无状态 vs. 维护状态
• 可靠的 vs. 不可靠的报文 传输

传输层

多路复用 & 解复用

UDP（User Datagram Protocol 用户数据报协议）

不保证可靠

• 数据丢失
• 乱序

无连接 -> 减少延迟

• UDP 发送与接收端无需握手
• 每个 UDP 报文段被独立处理

适用于

• 流媒体
• DNS
• SNMP
  应用传输速度=主机网络速度

格式

头部

• 源端口和目标端口（2*2=4 字节）
• 长度（2 字节）
• 校验和：EDC（差错检测码）
• 一共 8 byte，32 bit

EDC(Error Detection Code)

把校验范围分成若干 16bit 的小块，每个块视作数字，求和得到的值为校验和

求和细节

• 进位回滚（多出来的位到最低位再加）
• 取反

结果检测

• 若校验范围 + 校验和 ≠ 111…，则错误
• 若和全为 1，则大概率正确（小概率校验码和检测范围出错结果刚好匹配：残存错误）

TCP

不出错，不乱序

超时重传
ACK
序列号

流量控制

拥塞控制

• slow start，开始时，$\times2$
• 没检测到拥堵，+1 MSS
• 检测到拥堵，/2

网络层

两大层面

• 宏观层面的 Control Plane，使用 routing 算法
• 微观层面的 Data Plane，使用 forwarding 算法

Data Plane

路由器 Router

line termination | link layer protocol (In)| swtich fabric |(Out) link layer protocol | line termination

IO 如何尽量做到不限速？

• 最早使用 CPU，通过内存读写
• Bus，bus contention
• interconnection network: $3\times3$ crossbar → $8\times8$ multistage switch → 并行组合成更高阶传输

{
	"versionAtEmbed": "0.2.2",
	"filepath": "Ink/Writing/2024.5.22 - 12.16pm.writing"
}

Queuing

Input Port 排队

• Head of Line(HOL) blocking
  Output Port 排队
• Bufferinng
  • 多大 buffer？N flows: $\frac{{RTT\cdot C}}{\sqrt{ N }}$，如果太大，会导致 TCP 的拥堵检测迟钝（一直填不满 Buffer），增加 RTT
  • → Drop policy(超出 buffer)
    • Priority Drop
    • Tail Drop
  • → Marking，网络辅助的拥塞控制时，标记一些拥堵标志位
• Sechedule discipline 选择谁下一个传输？
  • First Come First Serve(FCFS)
  • priority
  • round robin
  • weighted fair queuing

Forwarding

Destination-based Forward

• 只根据 dest IP address 决定转发（唯一动作）
• 分成多个 link interface，longest prefix matching(LPM) 区分
  Generalized Forward
• 多个 head fields，多种 action
• 04
  OpenFlow
• 应用
  • 局部
    • Router
    • Switch（链路层）
    • 防火墙
    • NAT
  • 全局
    • 与 router 相连的 openflow SDN统一管理 forward table 来控制整体上的转发策略

IPv4

statistical multiplexing

• 网络的使用一般是突发性的
• 让 packet switching 尽可能简单高效，只关注于数据的转发，就可以让每个人共享全部带宽

Address Structure

• 最早是分成固定类别
• 后来 Classless Inter-Domain Routing(CIDR)
  • e.g.: /16 表示长度 16 的 netmask 掩码，能表示 $2^{32-16}=2^{16}$ 的地址

网络层的 IP 地址和链路层的 MAC 地址，设计之初是低耦合但实际却是高耦合的。所以 ARP 协议直接把两者做了一个映射关系。
ARP 协议

• 广播 - 回应
• ARP 报文
  
• 在局域网内广播目标 IP，自己的 IP 和 MAC 地址，所有接收到报文的更新源 IP 和 MAC 的映射。从而维护了一个 IP 和 MAC 的映射关系
• 映射保存时间视设备而定

IPv6

• 09
  IPv6

• no checksum
• 40 bytes 固定长度头部

IPv4 → IPv6

• 通过一个 IPv4 的 tunnel 连接 IPv6 路由器

{
	"versionAtEmbed": "0.2.2",
	"filepath": "Ink/Writing/2024.5.30 - 14.12pm.writing"
}

• 假设一个 IPv6 报文 A → F
• B → C 时，会直接套一个 IPv4 的头，指定 src 为 B，dest 为 E，之后通过 IPv4 转发到 E
• E 会拆开 IPv4 的头部，得到里面的 IPv6 报文，之后通过 IPv6 转发到 E

Control Plane

Routing

对一个网络，找到某一个节点为根节点，叶子节点为端节点的最小生成树

Dijkstra

Bellman Ford

动态规划思想

每个节点执行三个步骤

• wait，等邻居给自己消息
• recompute，重新算到其他所有端节点的最小值 $\forall y\in N,D_{x}(y)\min_{v}\{c_{x,v}+D_{v}(y)\}$
  消息滞后
• good news travels fast
• bad news travels slow
  • infinity problem

OSPF

SDN

ICMP