计算机网络
网络协议栈各层作用
应用层：通过应用进程间交互完成特定的互联网应用，定义应用进程之间通信和交互的规则。
传输层：进程之间通信的通用数据传输服务。
网络层：网络中不同主机提供通信服务
链路层：两个相邻网络结点之间传送数据
物理层：如何在传输媒介中传输比特流
应用层
C-S和P2P工作特点
客户-服务器是需要服务器打开，客户连接通信；P2P各方之间是对等的。
优缺点
客户-服务器
优点：客户、服务器分离，允许网络分布操作；一个服务器可以服务于多个客户端；
缺点：客户机会比较依赖于服务器工作。
P2P
- 优点：可扩展性强，传播速度优化；
- 缺点：用户直连，没有确保安全性，管理困难。
为什么引入域名，DNS缓存作用
方便人们记住主机名标识，同时适应路由器需要定长有层次的IP地址，需要一种从主机名到IP地址的转换服务，因此DNS系统产生了；缓存就是对重复的访问，省去一些重复的解析，节省时间。
传输层
TCP
最大报文段长度( Maximum Segment Size,MSS) 。MSS 通常根据最初确定的由本地发送主机发送的最大链路层 帧 长度（ 即所谓的最大传输单元(Maximum Transmission Unit, MTU))
来设置 。 设置该 MSS 要保证一个 TCP报文段（当封装在一个 IP 数据报中）加上 TCP/ IP 首部长度（通常 40 字节） 将适合单个链路层帧 。
注意到 MSS 是指在报文段里应用层数据的最大长度，而不是指包括首部的 TCP 报文段的最大长度 。
当 TCP 发送一个大文件 ，例如 某 Web 页面上的一个图像时，TCP 通常是将该文件划分成长度为 MSS 的 若干块（最后一块除外，它通常小于 MSS)
拥塞控制
运行在发送方的 TCP 拥塞控制机制跟踪 一 个额外的变量，即拥塞窗口(congestion window) 。 拥塞窗口表示为 cwnd它对一个 TCP 发送方能向网络中发送流量的速率进行了限制 。
\[
LastByteSent - LastByteAcked\leq \min \{cwnd,rwnd\}
\]
网络层
因特网的地址分配策略被称为 无类别域间路由选择(Classless Interdomain Routing,CIDR) [ RFC 4632 ] CIDR 将 子网寻址的概念 一般化了）当使用子网寻址时，32 比特的IP 地址被划分为两部分，并且也具有点分十进制数形式 $ a. b. c. d/x$, 其中x指示了地址的第一部分中的比特数
Best effort service model 为尽力而为服务。
工作特点：尽最大的可能性发送报文，传送的分组既不能保证以它们发送的顺序被接收，也不能保证它们最终交付；既不能保证端到端时延，也不能保证有最小的带宽。
优点：适用于绝大多数网络应用。尽力而为服务模型与适当带宽供给相结合已被证明超过“足够好”，能够用于大量的应用，包括语音、视频等流式视 频服务以及实时会议应用。
不足：对时延、可靠性不提供任何保证。
距离向量路由选择算法
令 \(d_x (y)\) 是从节点 x 到节点 y 的最低开销路径的开销 。 则该最低开销与著名的Bellman- Ford 方程相关，即
\[
d_x (y) = \min_v \{c(x,v) + d_v(v)\}
\]
v为x的临近节点， \(c(x,v)\) 意为cost
总结常见的传统路由协议，并指出其使用的是什么路由算法。传统路由协议有什么弊端？
OSPF：Dijkstra RIP：距离向量路由算法
弊端：拓扑维护，影响路由器性能和效率；流量路径缺乏灵活调整能力；网络协议实现复杂，运维难度大等。
什么是SDN，它有哪些特点？
软件定义网络，是在数据平面和控制平面作明确分割的网络设计理念
特点：基于流的转发；数据平面与控制平面分离；网络控制功能位于数据平面交换外部；可编程网络
相较于传统路由协议，SDN的优势是什么？
- 数据控制解耦合，将控制器，交换机分离，开放生态；
- 基于流的转发更加灵活
- 可编程网络便于开发
- 控制逻辑中心化，集中式便于管理
链路层
CRC纠错
所有计算（加减乘除）都是模2运算，没有进位借位，相当于直接异或
发送方需要选择长度为r的bits附加到数据D后，然后会构造一个长度为r+1的生成多项式G（同样是二进制数）
发送的数据为
\[
D\cdot 2^r \ \text{XOR} \ R
\]
并且要求该数据能够正好被G整除
\[
D\cdot 2^r \ \text{XOR} \ R = nG
\]
可以推导
\[
D\cdot 2^r =nG \text{XOR} \ R \\
R = \text{remainder} \frac{D\cdot 2^r}{G}
\]
每个 CRC 标准都能检测小于 r + 1 比特的 突发差错 。此外，在适当的假设下，长度大于 r + 1 比特的突发
差错 以概率 $1 -0. 5^r $ 被检测到。每个 CRC 标准也都能检测任何奇数个比特差错 。
随机接入协议
时隙 ALOHA
分为一个个时隙，每个时隙为 \(L/R\) 秒，其中L为帧的长度，则每个时隙够发一帧。
如果没碰撞，正常，有碰撞，则节点在之后的每个时隙中按照 \(p\) 的概率重传直至成功。
一 个给定节点传输的概率是 p; 剩余节点不传输的概率是\((1 -p)^{N-1}\) 。因此，一个给定节点成功传送的概率是 \(p(1 -p)^{N-1}\) 因为有 N 个节点 ，任意一个节点成功传送的概率是
\[
Np(1 -p)^{N-1}
\]
找到最大化的\(p^*\) 可以计算当 \(N \to \infty\) 时，效率为 \(1/e = 0.37\)
ALOHA
纯ALOHA，不分割时隙，任何时间都能传，没碰撞正常，有碰撞就在碰撞传输完后每帧时间按照p概率重传，各个节点时间都不同步，最大效率 \(1/(2e)\)
载波侦听多路访问(CSMA)
载波侦听(carrier sensing) ，即一个节点在传输前先听信道 。 如果来自另 一个节点的帧正向信道上发送，节点则等待直到检测到 一 小段时间没有传输，然后开始传输 。
碰撞检测(collision detection ) , 即当 一个传输节点在传输时 一直在侦听此信道。如果它检测到另一个节点正在传输干扰帧， 它就停止传输，在重复“侦听-当 空 闲时传输”循环之前等待一段随机时间 。
中止传输后，适配器等待一个随机时间量，之后传输。
随机时间量执行二进制指数后退(binary exponenlial backoff )算法 ：在该帧经历了 一连串的 n 次碰撞后，节点随机地从 \(\{0,1,2,\cdots, 2^n-1\}\) 中选择一个 K 值 。对于以太网，一个节点等待的实际时间量是 $ K $ 比特时间，即发送 512 比特进入以 网所需时间的K倍
