计算机网络1

计算机网络基础

三种交换方式

1. 电路交换

优点：传输速度快
缺点：需要建立独占连接，利用率低

2. 报文交换（不定长存储转发思想）

优点：无需建立连接，利用率高；基于报文的存储转发，线路可灵活分配；支持差错控制
缺点：报文不定长，不方便操作系统转发管理

3.分组交换（定长存储转发思想）

优点：无需建立连接，利用率高；基于报文的存储转发，线路可灵活分配；支持差错控制；分组定长，方便操作系统管理
缺点：相比报文，控制信息变多了；相比电路，存在存储转发时延

交换方式性能分析

1. 电路交换

连接建立时延 = “A->B的传播时延” + “B内部建立连接的时延” + ... + “N处理时延” + ”N->A的回传时延（由于已建立连接，所以回传无需加上处理时延）“
电路发送时延 = ”A->N的传播时延“
连接释放时延 = ”A->B的释放时延“ + ”B内部解除连接的时延“ + ...

2. 报文交换

总时延 = ”A->B报文发送时延“ + “B存储转发时延” + ...

3. 分组交换

总时延 = ”A->B报文发送时延“ + “B存储转发时延” + ...

网络分类

范围：广域网WAN、城域网MAN、局域网LAN（无线局域网WLAN）、个域网PAN（无线个域网WPAN）
传输方式：广播式网络、点对点网络
拓扑结构：
总线型（广播式，但存在总线争用）
环型（广播式，令牌环网解决总线争用）
星型（点对点，不存在争用）
- 伪星型：由集线器构成的网络，在物理上是星型拓扑，在逻辑上是总线型，因此存在总线争用
网状（点对点）

网络性能分析1

信道：一条物理网线有发送信道和接收信道，它们是独立计算的
数据速率单位与数据量单位：
数据速率：$1K=10^3M=10^6G=10^9T$
数据量：$1K=2^{10}M=2^{20}G=2^{30}T$
带宽：单信道的最高数据速率
下行带宽=接收信道最大速率
上行带宽=发送信道最大速率
注：如果不特殊提及，那么带宽=上行带宽=下行带宽
吞吐量：通过某个网络（收发信道、接口）的实际数据速率（数据量=上下行的总数据量）

网络性能分析2

总时延 = 发送时延（或叫传输时延） + 传播时延 + (处理时延 + 排队时延)
发送时延：A将数据发送完所需的时间=$\frac{分组长度}{发送速率}$
发送速率：min{A网卡发送速率，信道带宽，B接口接收速率}
传播时延：A最后发送的1bit数据，经过信道传播到B的时间=$\frac{信道长度}{介质的传播速率}$
大数据量时，传播时延占主导；小数据量时，发送时延占主导
时延带宽积 = 传播时延 * 带宽
表示：从链路中的发送端发出，但尚未到达接收端的最大比特数（在介质中的数据量）
往返时延RTT = 发送端发出最后一个bit，到发送端接收回传的最后一个bit的总时间
RTT = [发->收的传播时延+(处理/排队时延)] + [收->发的发送时延+收->发的传播时延+(处理/排队时延)]
RTT = 收+发的总传播时延 + 中间节点的处理时延 + 中间节点转发时的发送时延
信道利用率 = 信道使用时长t0/总时长t = 传输期间，所有数据帧的总时长/(第一个数据帧传输时长+RTT+第一个确认帧传输时长)
太低浪费资源、太高容易导致网络堵塞
数据传输速率 = 信道利用比特数b/总时长t = 传输期间，所有数据帧的总比特数/(第一个数据帧传输时长+RTT+第一个确认帧传输时长)
信道吞吐率 = 信道利用率 * 发送方的发送速率

分层结构

实体：第n层的活动元素
协议数据单元PDU
服务数据单元SDU
协议控制信息PCI
协议：语法（怎么看懂协议） + 语义（协议中的控制内容） + 同步（时序等条件同步）

1. OSI参考模型（7层）

“物联网叔会使用”

2. TCP/IP模型（4层）

“介网叔用”

物理层

通信

k进制码元、比特率与波特率
k进制码元：即波特Baud，1 Baud=$log_2k$ bit（一个码元携带$log_2k$个比特）
- 例如，1个4进制码元有4种状态，需要2bit来表示，即1Baud=2b
N个码元携带的比特数$b =log_2k\cdot N$
波特率（码元速率） = N/T，单位为Baud/s
比特率（信息速率） = b/T = $log_2k \cdot N/T$ = $log_2k \cdot$波特率，单位为bit/s
带宽
（物理）带宽 = 最高频-最低频，单位为Hz
（数据）带宽 = 比特率，单位为bit/s

1. 两大原理

失真现象：码间串扰（频率过低或过高，导致无法区分码元）
原因：波特率、距离、噪声干扰等
奈氏准则：无噪声、低通的条件下，设物理带宽为W(Hz)
极限波特率 = 2W
极限比特率 = $\log_2k\cdot$极限波特率 = $\log_2k\cdot2W$
信噪比：设信号功率为S，噪声功率为N
信噪比 = S/N，无量纲
信噪比 = $10\log_{10}(S/N)$，单位为dB
香农定理：有噪声、低通的条件下，设信号功率为S，噪声功率为N，物理带宽为W(Hz)
极限比特率 = $\log_2(1+S/N)\cdot W$
实际的极限比特率 = min{奈氏准则（理论），香农定理（现实）}

2. 信号与编码

信道：
基带信号(编码过的数据)->数字信道
宽带信号(调制过的数据)->模拟信道
数-数的编码：
NRZ（高1低0） -> RZ -> NRZI
曼切斯特编码、差分曼切斯特编码
4B/5B编码
数-模的调制：
调幅ASK：有幅为1
调频FSK：高频为1
调相PSK：同相为1
调幅+调相(QAM调制)：1码元 = 相位数*振幅数 bit
模-数的编码：
PCM脉码调制步骤：
1. 抽样：f采样 >= f信号最高频
2. 量化：将样本转为数字量
3. 编码：数-数编码
模-模的调制：略

3. 交换方式

电路交换
报文交换：存储转发
分组交换：存储转发 + 限制长度(一般为128B)
数据报方式(无连接)：源S将报文分组后发送；中间节点N每次传递时都进行差错检测+路由选择
虚电路方式(有连接)：源S与目标T先建立连接路径，再发送报文；中间节点N建立路径时需要进行路由选择，建立好后无需再次路由选择

物理层设备

双绞线、电缆、光纤
中继器、集线器(多口中继器)
调制解调器

数据链路层

数据链路层的功能

1. 封装成帧和透明传输

帧定界与帧同步
帧定界：确定帧的界限，帧定界符在帧首部
帧同步：接收方能从比特流中区分帧开始和结束
封装成帧：帧首部+数据部分+帧尾部
数据部分放置IP数据报
数据部分的长度<=最大传送单元MTU
组帧的四种方式
1. 字符计数：帧首部第一个Byte记录帧字符数
2. 字符(节)填充：帧首部第一个Byte为SOH，帧尾部最后一个Byte为EOT
3. 为了防止误识别帧内数据的SOH/EOT，发送方需要在它们前面加上转义字符ESC（透明传输）
4. 0bit填充：帧首部第一个Byte = 帧尾部最后一个Byte = “0b01111110”
5. 为了防止误识别帧内数据的0b01111110，发送方每遇到5个1就立即填入1个0（透明传输）
6. 违规填充：用编码方式中不会出现的编码来作为首部和尾部

2. 差错控制

噪声类型：全局的随机噪声（热噪声）、局部的冲击噪声
差错：
位错
帧错：丢失、重复、失序
差错控制：针对位错
注：这里的编码用于针对1组bit，而物理层的编码是针对单个比特
检错编码：奇偶校验码、循环冗余码CRC
纠错编码：海明码
- 检d位错所需的码距：d+1
- 纠d位错所需的码距：2d+1
- 海明不等式：数据有m位，校验码为r位，则满足$2^r\geq m+r+1$
- 若已经确定m，则可以通过暴力枚举求出最小的r

3. 流量控制

流量控制协议概述
停止-等待协议S-W==WT=1，WR=1==
滑动窗口协议：
- 后退N帧协议GBN==WT>1，WR=1==
- 选择重传协议SR==WT>1，WR>1且WR<=WT==
帧序号
- 假设对帧序号进行二进制编号，采用n个bit，且发送窗口为$W_T$，接收窗口为$W_R$
- 那么有：$W_T+W_R \leq 2^n$
S-W协议
确认机制：接受方收到帧，且无差错，则发送确认帧ACK
数据/确认重传机制：超时重传，超时时间应略大于平均RTT
4种特殊情况
- 数据帧丢失、数据帧出错：数据帧编号（检测丢失和出错） + 重传准备（发送帧的同时，保留副本+启动超时计时）
- 确认帧丢失：确认帧编号（检测丢失） + 重传准备（发送帧的同时，启动超时计时）
- 确认帧迟到：确认帧编号（检测重复） + 丢弃重复接收的确认帧
信道利用率
- $U=\frac{T_D}{T_D+RTT+T_A}$，信道利用率太低
GBN协议
确认机制：累积确认，即如果确认帧中，确认号为N，那么代表0~N-1号帧全部正确接收
确认重传机制：同S-W协议
数据重传机制：累积超时重传，即如果超时，将重传未确认的所有帧；超时时间应略大于平均RTT
4种特殊情况：同S-W协议
信道利用率
- $U=\frac{NT_D}{T_D+RTT+T_A}$，其中N=发送窗口大小
SR协议
窗口的额外限制：WR<=WT
- 因为如果WR>WT，则会导致多出的窗口无接收内容，在一段时间内空闲，使得性能较低
确认机制：累积确认，即如果确认帧中，确认号为N，那么代表0~N-1号帧全部正确接收
否认机制：接受方收到帧，若出现差错，则发送否认帧NCK
确认重传机制：同GBN协议
数据重传机制：同GBN协议

两种信道

点对点信道（广域网）

PPP协议

广播信道（局域网）

适用于总线型网络、早期星型网络（逻辑总线型网络）
介质访问控制协议概述
介质访问控制：多个节点同时访问总线型网络可能会导致冲突
信道划分（静态划分）：TDM/STDM、FDM、WDM、CDM
轮询访问（动态划分）：令牌传递协议
随机访问（动态划分）：ALOHA、CSMA、CSMA/CD、CSMA/CA

1. 信道划分协议

时分复用TDM
原理

缺点
解决：提出STDM
统计时分复用STDM
原理：统计节点需求，动态按序分配时序
优点
频分复用FDM
原理
优点：各节点可同时发送信号；充分利用信道的物理带宽（Hz）
缺点：FDM只能用于模拟信号传输
波分复用WDM
原理：光的频率与波长负相关，所以波分复用可以转换为“光的频分复用”问题，将不同波长的光复合、分离。
码分复用CDM
允许信号之间相互叠加和干扰，而接受方必须将信号值分离出来
原理
1. 分配向量：分配m维码片向量，包含m个码片，分量通常取1或-1；一个向量代表一个信号值（如二进制0或1）；各节点必须互相知道彼此的向量。
2. 向量要求：各节点的向量==唯一且相互正交==。
3. 节点A发送数据：将信号值序列，用多个码片向量（如$\vec{A}={\vec{a_0},\vec{a_0},\vec{a_1}}$）表示，并发送出去
4. 节点B发送数据：出现信号叠加，即出现$\vec{S}=\vec{A}+\vec{B}$
5. 节点C接收数据
6. 查询码片序列：首先查询A节点的$\vec{a_0}$、B节点的$\vec{b_0}$
7. 规格化内积：然后遍历$\vec{S}$中的每一个向量，分别与$\vec{a_0}、\vec{b_0}$做规格化内积。若为1则说明发送了比特1，若为-1则说明发送了比特0。

2. 随机访问协议

纯ALOHA与时隙ALOHA

1-坚持CSMA、非坚持CSMA、p-坚持CSMA：略，待补充
CSMA/CD
先听后发（同CSMA协议）、边发边听、冲突停发、随机重发
随机重发原理：截断二进制指数退避算法TBEB
1. 记录冲突次数，假设目前是第k次冲突
2. 若冲突次数很少（k<10）：在==区间$[0,(2^k-1)]$内==随机确定一个r，随机等待一段时间（等于r倍争用期）
3. 若冲突次数较少（10<=k<16）：在==区间$[0,(2^{10}-1)]$内==随机确定一个r，随机等待一段时间（等于r倍争用期）
4. 若冲突次数多（k>=16）：直接报错，报告网络层
争用期确定
- 争用期 = 最大RTT = 2 * 最大单向传播时延（考虑距离最远的两个节点）
- 最大单向传播时延的作用：一个节点发送数据后，需要最大花多久时间，才能让所有节点都知道总线已经被占用了
- 争用期的原理
- 假设A节点到B节点（两者是相距最远的）发送数据，在最后一瞬间，B以为不冲突也发送了数据。
- 此时B节点再下一瞬间发现冲突，于是停止发送；而B节点发送的数据需要经过一个最大单向传播时延，才会传到A节点，然后A节点才会发现冲突，于是停止发送。
- A节点发送到发现冲突的整个过程中，总时间 = 2 * 最大单向传播时延，于是用这个时间表示争用期
- 争用期的作用
- 在争用期内未发现冲突，则一定不会再发生冲突
- CSMA没有ACK机制，若无冲突，则认为帧发送成功
- 最短帧长
- 即争用期内的时延带宽积
- 最短帧长 = 2 * 最大单向传播时延 * 信道带宽
- 若收到的帧小于最短帧长，视为无效帧
- 最长帧长
- 防止某些节点的帧太长，一直占用信道
- CSMA/CA：略，待补充

3. 轮询访问协议

令牌传递：略，待补充

局域网

1. 802概述

802.3工作组处理“以太网技术”（有线局域网的一种技术），802.11工作组处理“WI-FI技术”（无线局域网的一种技术）
802负责OSI7层中的“物理层”、“逻辑链路层”
802细分了逻辑链路层，即：逻辑链路层 = LLC子层（逻辑链路控制，已经名存实亡）+MAC子层（介质访问控制）

2. 局域网概述

支持单播（一对一）、广播（一对全部）、多播（一对部分）
分类：有线局域网LAN、无线局域网WLAN
有线局域网LAN
令牌环网（环形）：令牌传递协议
以太网（总线形，逻辑总线形）：CSMA/CD协议或无协议
- 当使用半双工信道时，会出现信道冲突，则==使用CSMA/CD协议==
- 当使用全双工信道时，不会出现信道冲突，则不使用协议
无线局域网WLAN
无线网（星形，逻辑星形）：CSMA/CA协议

3. MAC帧格式

分为两种标准（DIX Ethernet V2和IEEE 802.3），这里只介绍常用的V2标准
插入部分+MAC帧内容（目的MAC地址、源MAC地址、网络层协议类型、数据部分、FCS）：记忆，662N4，收发协数验
目的地址：全1表示“广播帧”
数据部分：46B~1500B，短了就填充，长了就分片
插入部分：前同步码+帧开始定界符
冲突域与广播域
冲突域：若两个节点同时发送数据，会导致冲突
广播域：若一个节点发送数据，可以被另一个节点接收
路由器、交换机、集线器对两种域的隔离作用

4. 虚拟局域网VLAN概述

目的：将局域网中的广播域进行细分，每一个细分的网络叫一个VLAN（局域网内有唯一的VID），使得每一个VLAN就是一个广播域
安全性、防止广播风暴：如果交换机实现了VLAN，那么就算交换机不隔离广播域，VLAN-1也无法广播到VLAN-2中去
连接多个广播域：如果路由器实现了VLAN，那么可以将多个局域网的主机组成VLAN，突破路由器隔离广播域的限制
划分VLAN方式：
基于交换机接口
基于MAC地址
基于IP地址：这种方法可以跨越路由器，让多个局域网的主机组成VLAN（需网络层支持）
干线链路或汇聚链路：连接两个交换机端口的链路

链路层设备

网桥、交换机(多网桥)、无线接入点(WAP)
网络适配器（即网卡）
不同局域网使用不同的网卡
作用：1)发送帧到局域网 2)从局域网中接收帧 3) 根据局域网类型实现数据链路层+物理层 4)后略