壹、计算机网络体系结构

1. 可靠服务与不可靠服务

• 可靠服务是指网络具有纠错、检错、应答机制,能保证数据正确、可靠地传送到目的地。

• 不可靠服务是指网络只是尽量正确、可靠地传送,而不能保证数据正确、可靠地传送到目的地，是一种尽力而为的服务。

• 对于提供不可靠服务的网络,其网络的正确性、可靠性要由应用或用户来保障。例如,用户收到信息后要判断信息的正确性,如果不正确,那么用户要把出错信息报告给信息的发送者,以便发送者采取纠正措施。通过用户的这些措施，可以把不可靠的服务变成可靠的服务。

2. 各层的传输单元

• 物理层：比特

• 数据链路层：帧

• 网络层：数据报

• 传输层：报文段

贰、物理层

一、通信基础

1. 单工、半双工、全双工

• 单工：单向信道

• 半双工：双方都可以进行收发，但不能同时收发

• 全双工：双方可以同时收发（两条信道）

2. 比特率和波特率

• 比特率：信息传输速率，单位是b/s或bps

• 波特率：码元传输速率，单位是波特Baud

• 若一个码元含n个比特，则波特率 * n = 比特率

3. 信道容量

• 奈奎斯特定理：理想无噪声信道容量，

其中C为信道容量，B为信道带宽（物理层的带宽单位是HZ），M为进制数（信号状态数）

• 香农定理：有噪声信道容量，，注意

其中S/N为信噪比，注意需要将以dB为单位的信噪比进行处理，转化为能量比，两者在数值上等价。
为什么需要有dB这个单位进行表示呢？——通常S/N是一个很大的数，取log比较方便。

例如：带宽为2MHz，信噪比为30dB
错误答案：C=2M * log31
正确答案：S/N = 10^(30 / 10) = 1000， C=2M * log(1 + 1000) ≈20MHz

4. 编码

• 将数据变换为数字信号的过程叫作编码

• 常见编码有：单双级归零码（前一半有效，中间归零）、单双级不归零码、双相码（曼彻斯特编码）、差分双相码。

• 曼彻斯特编码：每个时刻中间都会跳变，高到低为1，低到高为0。【有时可能相反，得看题目】以太网采用该编码。

• 差分曼彻斯特编码：只有两种波形，相邻波形变化为1，不变为0。

图片来自 https://blog.csdn.net/qq_34745941/article/details/128237381

5. 调制

• 将数据变换为模拟信号的过程称为调制

• 常见调制方法：2ASK，2FSK，2PSK，QAM

• 2ASK：二进制幅移键控，改变振幅来表示0和1。抗干扰弱。

• 2FSK：二进制频移键控，0和1采用不同载波。容易实现，抗干扰强，但频带利用率低。

• 2PSK：二进制相移键控，0和1差一个π的相位

• QAM：正交振幅调制，也称幅值相位联合键控，在相同频率下，将ASK与PSK结合起来。

对于QAM，设波特率为B，采用m个相位，每个相位n种振幅，QAM数据传输速率R。
则

6. 基带传输与频带传输

• 基带传输：在计算机内部或相邻设备之间近距离传输，可以不经过调制直接在信道上传输，常用于局域网。可以采用不同编码。

• 频带传输：远距离或无线传输，必须对数字信号进行调制。

二、传输介质

1. 导引型传输介质

导引型传输介质中沿固体媒介（铜丝或光纤）传播。

• 架空明线：易受干扰，对噪声敏感。

• 双绞线：主要用于基带传输。可以隔绝相邻导线的干扰，分为屏蔽双绞线STP和无屏蔽双绞线UTP。

• 同轴电缆：屏蔽性更好，主要用于频带传输。

• 光纤：利用光的全反射，多模光纤用于近距离，单模用于远距离。

2. 非导引型传输介质（无线电信号的介质）

• 地波传播：低频电磁波沿地球表面传播，有一定绕射能力，几百千米。

• 天波传播：高频电磁波可被电离层反射，可传播上万公里，但不稳定。

• 视线传播：点对点直线传播，通过地面中继站或卫星中继站接力。

三、物理层设备

1. 中继器

• 将信号整形再生，再转发出去，以消除传输中的衰减。

• 没有存储转发功能，不能连接两个不同速率的网段。

2. 集线器

• 多端口的中继器

• 不能分割冲突域和广播域

叁、数据链路层

一、组帧

• 以帧为单位进行传输，可以在出错时只重传出错的帧，避免重传整个数据。

• 组帧时不仅要加上头部，还要加上尾部，明确区分帧在比特流中的起止位置。

为什么网络层的IP数据报不用加上尾部呢？
——因为IP数据报是链路层数据帧的数据部分，没必要加尾部。

二、差错控制

1. Internet校验和

将数据划分为16bit的序列，求和，最高位进位加到最低位。最后逐位取反得到checksum字段的值。

2. 循环冗余检验码CRC

用数据D除以r+1位的G（二进制除法），余下的r位就是待求的R。

3. 检错码与纠错码

略

三、多路访问协议

MAC协议针对广播链路

1. 信道划分MAC协议

• 多路复用技术

• 负载重时效率高

• 码分多址CDMA

2. 随机访问MAC协议

• 允许冲突，采用冲突恢复机制

• 负载轻时效率高

• 典型协议：ALOHA，时隙ALOHA，CSMA，CSMA/CD

• CSMA/CD的冲突检测不适用于无线局域网，接收信号会淹没在本地发射信号中

3. 轮转访问MAC协议

• 轮询；令牌传递

• 存在额外开销和单点故障问题，效率介于前两种之间

四、ARP协议

1. MAC地址

• 全世界每块网卡在出厂时都有一个唯一的MAC（介质访问控制）地址，在局域网内标识一个帧从哪一个接口发出，到达那个物理相连的接口。

• MAC地址含6个字节，采用16进制表示，每个字节之间用-隔开。如：12-34-56-78-9A-BC

• 每经过一个节点源MAC地址和目的MAC地址都会改变！

IP地址除了在穿透内网的时候会改变，其他时候不变。

2. ARP地址解析协议

网络层只有IP地址，在同一局域网内，已知目标的IP地址，如何确定其MAC地址呢？

• 局域网内每个结点（主机和路由器）维护一个ARP表，存储IP与MAC的映射关系。

若A不知道B的MAC地址，则A广播ARP查询分组（含有B的IP），B收到后应答，A将B的MAC存于ARP表中，直至TTL超时。

• ARP是即插即用协议，可自行创建ARP表。

五、以太网

1. 局域网

在以太网之前首先了解一下局域网

• 局域网(Local Area Network, LAN)是指在一个较小的地理范围（如一所学校)内，将各种计算机、外部设备和数据库系统等通过双绞线、同轴电缆等连接介质互相连接起来，组成资源和信息共享的计算机互联网络。

• 局域网的特性三个元素决定——拓扑结构、传输介质、介质访问控制方式。不同的局域网技术如以太网、令牌环网等。

2. 以太网

• 以太网是目前占据统治地位的有线局域网技术，逻辑结构是总线型，物理结构是星型。

早期的以太网物理结构是总线型（同轴电缆），目前基本采用星型物理拓扑结构，通过交换机分割冲突域。

• 以太网提供的是无连接不可靠服务。

无连接：发送方和接收方网卡之间 没有握手过程。
不可靠：接收方 不向发送方进行确认，差错帧直接丢弃，数据恢复依靠高层协议。

• 以太网的MAC协议采用二进制指数退避算法的CSMA/CD，由网卡NIC实现。

• 以太网的帧结构，其中最开始的8字节前导码用于时钟同步，默认不算在内（除非有特殊说明）。以太网帧中包含目的MAC、源MAC、类型、数据和CRC校验码。

MAC地址：若目的MAC与当前MAC相同，或目的MAC为全F（广播地址）则接收，否则丢弃。
类型：指出封装的上层协议的类型，如IP数据报等。
数据：MTU为1500B，故至多1500B；为了满足L/R≥RTT，要求L≥64B，即数据部分≥46B。

图片来自 http://c.biancheng.net/view/6391.html

3. 交换机

• 交换机能够存储-转发以太网帧，检验帧的目的MAC并向一个或多个输出链路转发。

• 使用CSMA/CD协议

• 透明、即插即用（无需配置）、隔绝冲突域、不隔绝广播域

• 交换机的多个端口之间可以同时传输（交换机能够缓存帧）

• 通过交换表确定转发的接口，交换表可以由自学习过程进行构建

可能存在的疑问——交换机既然隔绝冲突域，为什么还要使用CSMA/CD协议呢？
事实上， 全双工的交换机是不需要CSMA/CD的，有些交换机为了支持半双工或考虑兼容性，才会需要用到CSMA/CD协议。

4. 虚拟局域网

• 将原先的一个局域网划分成多个组，一组形成一个虚拟局域网VLAN，每一个VLAN是一个小的广播域。

• 基于端口的VLAN：按端口分组，VLAN之间的转发需要通过路由器（实际中厂家会将交换机与路由器集成到一起）。

• 跨越多个交换机的VLAN：有时一个VLAN的端口分布在不同交换机上，可以通过在每个交换机上设置中继端口，实现不同交换机上的分组通信。

六、PPP协议

1. 特点

• 之前的MAC协议针对的是广播链路，而PPP协议针对的是点对点链路，因此无需介质访问控制MAC，也无需明确的MAC寻址。除了PPP，HDLC也是一种点对点链路控制协议。

2. 设计需求

• 组帧：封装任何类型的网络协议分组（不只是IP数据报）

• 比特透明传输：必须支持任何比特模式

• 差错检测：只检测，不纠正

• 无需支持差错纠正、流量控制，也不存在乱序交付

3. PPP数据帧

• 其中地址和控制字段可协商决定是否删去，协议、信息、校验字段可协商确定长度，最多可省5B

4. 字节填充

• 注意到PPP数据帧的定界符是一个特定的0-1串，若数据中出现相同的0-1串，可能被误认为定界符，违背了“比特透明传输”的原则。

• 发送端：在数据中的<01111110>字节和<01111101>字节之前插入额外的<01111101>字节

• 接收端：单个<01111101>为填充字节；连续两个<01111101>，只保留第2个；单个<01111110>为定界符。

肆、网络层

一、虚电路网络与数据报网络

网络服务模型包括 连接服务和 无连接服务，前者的代表是ATM的虚电路网络，后者的代表是Internet的数据报网络。

1. 虚电路VC

• 虚电路：一条从源主机到目的主机，类似于电路的路径(逻辑连接)，由沿路的网络设备共同完成虚电路功能。

• 虚电路综合了电路交换与分组交换的共同优点，有连接，每个分组选路相同，实时性好。

虚电路“虚”在哪里？——采用分组交换而非电路交换，无需多路复用，每个分组能够利用全部带宽。

• 每条虚电路包括一条路径、每段链路的虚电路号VCID，路由器利用转发表记录信息。

• 分组携带的是下一条的VCID而不是目的地址，路由器转发时根据转发表改写VCID。

2. 数据报网络

• 无连接，每个分组携带目的地址，每个分组独立选路，路由器根据目的地址转发。

• 路由聚合：IP太多，最长前缀匹配优先

• 简化网络，复杂边缘

二、IPv4

1. IPv4数据报分组格式

• 版本号为4

• 首部长度单位为4B，通常取5（无选项字段）

• 总长度单位为1B

• 片偏移单位为8B

2. 分片

• 注意计算

3. IP编址

• 接口：主机/路由器与物理链路的连接。路由器通常有多个接口，而主机一般1或2个。

• IP地址：标识主机、路由器的接口。通常用点分十进制表示。高位为网络号，地位主机号。

• IP子网：网络号相同的设备接口构成IP 子网，不跨越路由器就可以物理联通。

4. 有类IP地址

• ABC类可用于标识接口，D类用于多播地址，E类供研究使用。

• 部分特殊IP

• 私有IP，在公共互联网上无效

5. 子网划分

略

三、CIDR与路由聚合

1. CIDR无类域间路由

• CIDR消除了ABC类地址界限，把网络号和子网号统称为网络前缀，并融合了子网地址与掩码，形如1.2.3.4/22

• CIDR的优势——提高地址分配效率；通过路由聚合提高路由效率

四、DHCP协议

主机在互联网中如何获取一个IP地址呢？

• 静态配置：手动设置IP、掩码、默认网关、DNS服务器等

• 动态主机配置协议DHCP：即插即用，允许地址重用（不使用的时候可以给别人用）

• DHCP是应用层协议，封装到UDP数据报

五、网络地址转换NAT

• 通过替换解决

外网客户如何连接内网服务器？——NAT穿透问题

• 静态配置NAT（手动配置转换表）

• 互联网网关设备协议IGD

• 中继服务器

六、互联网控制报文协议ICMP

• ICMP主要功能——差错报告和网络探询

• 差错报告：目的不可达；源抑制（缓存已满）；超时；参数问题；重定向……

• 网络探询：回声请求；应答报文

• ICMP报文会封装到IP数据报中进行传输（给出错的IP数据报加上ICMP的头部，再加上一个新的IP头）

七、IPv6

1. 介绍

• 32位IPv4地址已经分配殆尽，提出了128位的IPv6地址

• IPv6数据报有固定40B的基本首部，并且不允许分片

相比于IPv4，IPv6的基本首部移除了校验和（减少处理时间）与选项字段

2. 地址表示

• 地址表示：128位分成8组，以十六进制进行表示，用冒号分割，连续的0可用::代替（但只能使用一次）。

eg:
FF01 : 0 : 0 : 0 : 0 : 0 : 0 : 43 = FF01 :: 43

• IPv4嵌入形式：IPv4地址为a.b.c.d，则相应的IPv6地址为 :: FFFF : a.b.c.d

• 采用地址前缀，不使用掩码

eg:
FF01 : 4321 :: / 32

3. 其他

• IPv6有三种基本地址类型——单播，多播，任意播

• 单播：一对一通信

• 多播（组播）：一对多通信，只能作为目的地址，向一个多播组发送数据报

• 任意播：与一组中的一个通信（通常是最近的一个）

IPv6没有广播地址，取而代之的是多播

• 隧道技术：把IPv6作为数据部分封装到IPv4数据报中

八、 路由算法

1. 链路状态路由算法

• Dijkstra算法

• 基于全局信息

• 存在“震荡”的可能（选择链路通信量作为代价）

2. 距离向量路由算法

• Bellman-Ford算法

• 异步迭代（只在变化时通知邻居）

• 分布式

• “好消息”传播快，“坏消息”传播慢（无穷计数问题，采用毒性逆转、定义最大度量等方法）

3. 层次化路由

将任意规模的网络抽象成图来计算路由——过于理想化。
一个拥有6亿节点的网络，路由表几乎无法存储，并且单纯的路由信息就会淹没网络！
此外还存在管理自治问题。

• 自治系统AS：聚合路由器为一个区域，AS内路由器运行相同的路由算法。

• 网关路由器：位于AS边缘，连接其他AS的网关路由器。

• AS间路由：需要获取可达性信息。当存在多个网关可以到达目的时，选择最近的网关路由器（热土豆路由）

九、Internet路由

Internet采用层次路由，AS内部路由也称IGP。常见的有RIP、OSPF等。

1. RIP协议

• 距离向量路由算法

• 跳步数作为距离，采用毒性逆转技术，最大有效距离为15，邻居之间每30s交换一次距离向量。若180s未收到通告则认定邻居/链路失效，需重新计算路由。

• RIP的路由表通过一个应用层进程进行管理，通过UDP数据报发送。

2. OSPF协议

• 链路状态路由算法

• OSPF通告在整个AS范围内泛洪，报文直接封装到IP数据报，不经过传输层协议

• 优点：所有的OSPF报文可以被认证，安全；允许同时使用多条相同费用的路径（RIP只能选一条）；对每条链路可以针对不同TOS设置不同费用度量（分流）；集成单播路由与多播路由；支持对大规模AS再次分层。

3. BGP协议

• Internet的AS间路由协议——边界网关协议BGP，将Internet粘合为一个整体

• BGP会话通告去往不同目的前缀子网的路径（不是长度），报文交换基于半永久的TCP连接。

• 通告包括前缀和属性，两个重要的属性——AS路径，下一跳边界路由接口

• AS内路由侧重性能，AS间路由策略主导

伍、传输层

一、传输层服务

• 传输层协议为不同主机的进程之间提供了端到端的逻辑通信机制，而网络层则是主机之间

• Internet的传输层协议包括TCP和UDP，均不保障时延与带宽

二、多路分用与复用

• 如果某层的协议对应直接上层的多个实体/协议，则需要分用和复用

• 接收端：多路分用，根据头部信息给到不同进程

• 发送端：多路复用，多个socket一起发过去

• UDP的socket用二元组（目的IP，目的端口）标识

• TCP还引入了源IP与源端口，用四元组标识

三、用户数据报协议UDP

1. 功能

• 复用/分用

• 简单的错误校验【注意没有纠正】

• 可能丢失或乱序到达【需要在应用层增加可靠性机制并采用特定的错误恢复机制】

2. 优点

• 无需连接，低延时

• 实现简单，无需维护连接

• 头部开销小

• 无拥塞控制，应用可更好地控制发送时间与速率

3. 校验和

四、可靠数据传输

何为可靠数据传输？
不错，不乱，不丢。

1. Rdt1.0——可靠信道上的可靠数据传输

• 底层信道完全可靠，只要发出就能被正确接收，收发方的FSM独立

2. Rdt2.0——产生位错误的信道

不乱，不丢，只有位错误

• 停等协议

• 利用校验和检测位错误

• 用ACK和NAK显示确认

• 引入重传机制

3. Rdt2.1——序列号

如果ACK和NAK在传输中出错怎么办呢？——让发送方重传
重传会产生重复分组，因此要引入序列号。

• 停等协议，只需要两个序列号

• 序列号不匹配代表已经正确接收文件，只是ACK/NAK出错

4. Rdt2.2——无NAK

• 取消了NAK，用ACK告知发送方最后一个被接收的分组序号

5. Rdt3.0——超时重传

分组可能丢失，引入计时器

五、滑动窗口协议

1. 流水线机制

• 一次发送多个分组，提高3.0性能

• 需要更大的序列号范围和存储空间

• 采用滑动窗口协议管理已发送而未确认的消息

2. GBN协议

• 累计确认

• 只有一个计时器

• 无缓存，只记住期望收到的序列号，丢弃乱序分组

• 窗口大小N，序列号k位，满足

3. SR协议

GBN的累计确认会导致大量重传

• 设置缓存，每个分组单独确认

• 每个分组设置定时器

• 接收方也有窗口，与发送方不同步

• 

六、TCP协议

1. 概述

• TCP提供可靠的按序字节流机制

• 发送方和接收方都有缓存

• 连接状态只在两端维护

• 全双工

• 段结构如下，TCP中的ACK号是指希望收到的下一个字节序号

特别注意这里的序号和ACK号都指的是 字节序号而非段本身的编号

图片来自 https://www.cnblogs.com/ts65214/p/12968246.html

• TCP没有规定如何处理乱序到达的段，由实现者自行决定

2. TCP可靠数据传输

• 采用流水线机制和累计确认

• TCP使用单一计时器，触发重传的事件包括超时和重复ACK

• 如何设置超时时间？——应大于RTT——如何估计RTT？

超时时间 = EstimatedRTT + 4 * DevRTT
其中E = (1 - α) * E + α * SampleRTT
D = (1 - β) * D + β * |SampleRTT - E|

• 若正常收到按序到达的段，接收方会等待500ms，若期间收到另一个按序到达的段，则立刻发送两个ACK。

• 快速重传机制——3个重复ACK

3. 流量控制

• 流量控制针对发送方和接收方，接收方会在段的头部字段把自己的RcvWindows告知发送方，让发送方限制自己已发送但未收到ACK的数据大小

• 若RcvWindows=0，发送方也可以发送很小的段，用于从接收方获取RcvWindows信息

4. TCP连接管理

• 三次握手建立连接，前两次SYN标志为1

• 四次挥手关闭连接，可以由客户端发起，也可服务器端发起

七、拥塞控制原理

• 拥塞控制针对网络，不同于流量控制

• 拥塞控制方法——端到端拥塞控制（端系统通过隐式观察延迟、丢包率判断拥塞），网络辅助的拥塞控制（路由器显式反馈拥塞信息）

八、TCP拥塞控制

1. 基本原理

• 根据拥塞窗口大小CongWin限制发送速率

• 策略——加性增-乘性减AIMD，慢启动SS

AIMD：每个RTT将CongWin增大一个MSS（最大段长度）
SS：每收到一个ACK令CongWin增大一个MSS，每个RTT实现翻倍

• 何时由SS变为AIMD——Threshold变量。当loss事件发生时，设为loss前CongWin的一半，达到Threshold之前慢启动。

• loss事件的处理——3个重复ACK，将CongWin减半，然后AIMD；超时，减为1.

2. 性能分析

• 平均吞吐率

• TCP具有公平性，但UDP和并发TCP会产生不公平

陆、应用层

一、网络应用基本原理

1. 网络应用体系结构

• 客户机/服务器结构（c/s结构）

• 点对点结构（P2P结构）

没有永久在线的服务器，任意节点之间可直接通讯

• 混合结构

2. 网络应用进程通信

• 进程间的通信是网络应用的基础，不同主机进程的通信依靠套接字socket

• 进程寻址的标识符——IP地址+端口号

• 协议内容——消息类型【请求/响应】，消息格式，字段的语义，规则【进程何时以及如何发送/接收信息】

二、Web应用

1. Web应用概述

• 网页：包含多个对象，如HTML文件、JPEG图片等

• 对象的寻址：URL统一资源管理器

• 超文本传输协议HTTP：C/S结构，使用TCP ，是无状态协议

无状态指服务器不维护任何在客户端过去请求的消息

2. HTTP连接类型

• 建立连接需要1个RTT

• 持久性与非持久性连接

• 带流水的持久性连接，理想状态下所有对象只需1个RTT

3. HTTP消息格式

• 两类消息——请求信息与响应消息

• 请求消息的格式：请求行+头部行+换行+消息体

• 方法类型

GET和POST都是上传输入方法
GET在 请求行的URL字段上传输入
POST在 消息体中上传输入

4. Cookie技术

• Cookie技术，数据是保存在用户本地的

5. Web缓存技术

• 设置代理服务器

• 条件性GET：如果缓存最新，则响应不包含对象

三、Email应用

1. Email应用概述

• 构成组件：邮件客户端，邮件服务器，SMTP协议【服务器之间传递】

为什么需要服务器，而不是用户之间直接传递？
——不能保证用户24小时在线，未进入Internet时将无法成功发送

• SMTP协议：TCP，端口号为25，使用持久性连接和命令/响应交互模式，消息只能包含7位ASCII码

HTTP与SMTP都采用命令/响应交互模式，命令和状态代码都是ASCII码。

HTTP：拉式（PULL），浏览器把网页拉到本地；每个对象封装在独立的响应消息中
SMTP：推式（PUSH），发送方把消息推到接收方；多个对象在有多个部分组成的信息中

2. Email消息格式

• 通过多媒体扩展，可以发送ASCII码之外的其他格式

3. 邮件访问协议

• 从服务器获取邮件：POP协议，IMAP，HTTP