Skip to content

引言

协议与分层结构

面向连接 / 无连接

TCP 是面向连接, UDP 是无连接 (无连接也叫 datagram service)

UDP 无应答, 不保证数据能到达, 可能丢包 / 乱序

模型

alt text

标识

tcp: port ip: address

socket

调用不可靠的 UDP 和可靠的 TCP

多客户

服务端监听套接字在本地创建临时的连接套接字与客户端通信

系统调用

  1. connect()

    三次握手, 阻塞

  2. accept()

度量单位

时延

传输: 数据到链路上

传播: \(A\to B\)

RTT

ping

时延带宽积

有效吞吐量

除去头信息的有效信息

安全

DoS: Denial of Service

物理层

波特率

波特率为每秒钟发送的符号/码元数量

比特率为每秒钟发送的有效比特数量

波特率 = 比特率 \(\div\) 符号编码所需的比特数

例如, 在 4B/5B 编码中, 假设比特率是 \(100\text{ Mbps}\), 编码效率 \(80\%\), 说明线路中 \(5\) 个符号转换成原始数据的 \(4\) bit, 所以波特率 \(125\text{ Mbaud}\)

如果电压有 \(8\) 档, 那一个符号代表 \(\log_2 8=3\) 个 bit, 所以波特率是比特率的 \(3\) 倍

带宽

等于频谱的宽度

也与 Bps 相关

信道容量定理

Nyquist-Shannon Sampling Theorem

Shannon Channel Capacity Theorem

见 博客

复用

码分复用 CDMA

每个站有一个码片

对于两个不同站的码片 \(S,T\) 满足正交: \(\frac 1m \sum_{i=1}^m S_i\cdot T_i=0\)

对于一个站, 如果发送 \(1\), 把自己的码片发送出去, 接收端计算得到 \(S\cdot S=1\); 如果发送 \(0\), 把码片取反发送出去, 接收端计算得到 \(S\cdot (-S)=-1\)

多个站的码片叠加, 接收端依次用不同站的码片计算内积, 由于这个站的码片与其他站的码片正交, 结果只显示自己站发来的码片结果

这个想法与中国剩余定理/拉格朗日插值类似

数据链路层

检错与纠错

检查 \(d\) 个错需要 hamming distance \(d+1\) 的码, 因为有 \(d+1\) 个错可能没错; 有 \(r>d+1\) 个错等价于有 \((r\mod (d+1))\) 个错

纠正 \(d\) 个错需要 hamming distance \(2d+1\) 的码, 为了距离为 \(d\) 的范围不重叠

检错码

CRC

与有限域有关

参考 error correction, Galois Field

纠错码

单比特纠错: 对于 \(n=m+r\) 的编码, 有效信息 \(2^m\) 个, 且有 \(n\) 个 hamming distance 为 \(1\) 的编码, 把这 \(n+1\) 个编码看成一族

假设各个族之间不重叠, 则可以纠错; 并且总数量必须能用 \(2^n\) 完整表示

所以 \(2^m(n+1)\leq 2^n\)

hamming code

妙

Reed-Solomon code

同样与 有限域 有关

停等协议

滑动窗口协议

\[a=t_p/t_f\]
\[U=\left\{\begin{matrix}1&,W\geq 1+2a\\\frac{W}{1+2a}&,W<1+2a\end{matrix}\right.\]

Piggybacking

\[t_f=t_{ACK}\]
\[\frac{t_f+t_{ACK}+2t_p}{t_f}=2+2a\]
\[U=\left\{\begin{matrix}1&,W\geq 2+2a\\\frac{W}{2+2a}&,W<2+2a\end{matrix}\right.\]

有差错 ARQ

出错概率为 \(P\), 一个帧的期望传输是 \(N_r=\sum_i iP^{i-1}(1-P)=1/(1-P)\)

\[U=\frac{1}{N_r(1+2a)}=\frac{1-P}{1+2a}\]

回退 N

每出一次错需要重传 \(K\) 帧

\[N_r=\sum_i f(i)P^{i-1}(1-P)\]
\[f(i)=1+(i-1)K=Ki+(1-K)\]
\[\therefore N_r=\frac{1-P+KP}{1-P}\]
\[\therefore U=\left\{\begin{matrix}\frac{1-P}{1+2aP}&,W\geq 1+2a \to K=2a+1\\\frac{W(1-P)}{(1+2a)(1-P+WP)}&,W<1+2a \to K=W\end{matrix}\right.\]

选择重传

\[U=\left\{\begin{matrix}1-P&,W\geq 1+2a\\\frac{W(1-P)}{1+2a}&,W<1+2a\end{matrix}\right.\]

因为每个帧之间相互独立, 期望传输次数都是 \(N_r\)

竞争协议

ALOHA

符合泊松分布

信道利用率: \(Ge^{-2G}\) 和 \(Ge^{-G}\)

CSMA

非持续 CSMA

持续 1-CSMA

持续 p-CSMA

CSMA/CD

  • 二进制回退

    发送一帧的平均时间 \(P\) 秒, 一个站点获得信道的概率 \(A=kp(1-p)^{k-1}\), 时间槽 \(2\tau\)

    RTT = \(2\tau\)

    信道利用率 \(\frac{P}{P+2\tau/A}\)

    \(\min(1/A)=e\)

非竞争协议

位图

\(N\) 个时隙(1Byte), \(N\) 个站置 \(1\) 表示, 之后按序传输

信道利用率: 平均发送 \(d\) 帧, 低负载 \(d/(d+N)\), 高负载 \(d/(d+1)\)

令牌

转一圈, 数据附加在令牌上

二进制倒数

排序从大到小

\(d/(d+\log_2N)\)

对称协议

每个站以 \(p\) 概率抢信道

只有一个站抢到概率 \(kp(1-p)^{k-1}\)

最优解 \(p=1/k\)

优先竞争协议

自适应树搜索协议

二进制倒数改

假设维护了一个最近信道的 ready 站点数 \(q\)

假设从第 \(i\) 层开始, 每个节点下面有原树 \(2^{-i}\) 的节点, 对应了 \(2^{-i}q\) 个 ready 节点

如果每个节点期望只有 \(1\) 节点, 那么 \(i=\log_2 q\)

交换机

网桥的现代名称

与 Hub 不同, 交换机可以不每次都 flooding, 而是查 MAC 表转发到特定端口

只有查不到时在广播到 FF:FF:FF:FF:FF:FF 进行 flooding

三种交换模式

  1. 存储转发: 接受完整帧再转发, 延迟大, 不转发错帧
  2. 直通: 得到目的地址立即转发
  3. 无碎片: 接受前 64 帧再转发, 过滤冲突碎片

生成树协议

选优先级, ID 最小的根桥

每个交换机选到根桥路径开销最小的根端口

每个网段选到根桥路径开销最小的指定端口