计算机网络

引入（吹水这门课的topic1由引入、数据链路层（Data Link Layer）、网络层（Network Layer）构成。 引入部分涉及： 网络架构、服务、各层协议、网络连接及指标。 数据链路层涉及： 数据链路层简介 流控 差错控制 Medium Access Control （MAC） 局域网及网络设备（如路由、交换机等） 网络层涉及： 网络层简介 IP 计算机网络简介计算机网络由节点、连接、协议构成。网络服务的性能指标主要有延迟、带宽、损失率（loss rate）、终端数量等。 在计算机网络中，常见的协议有： TCP/IP：互联网的核心协议族，负责数据的封装、寻址、传输与校验。包括 IP 层负责路由与寻址，TCP 层负责可靠传输。 ATM：一种面向连接的协议，使用固定长度的53字节单元，适用于语音、视频和数据的统一传输，曾广泛用于骨干网。 MPLS：通过标签而非IP地址进行数据转发，提高路由效率，常用于构建虚拟专用网（VPN）和流量工程。 SONET：一种高速光纤传输协议，主要用于电信运营商的骨干网，支持高可靠性和同步传输。 Ethernet：最常见的局域网协议， ...

引入-计算机网络导论互联网（Internet）互联网是 “网络的网络”（network of networks），由大量互联网服务提供商（ISP） 相互连接而成，包括移动网络、家庭网络、机构网络、区域 ISP、全球 ISP 等层级。 网络结构（Network Structure）一个计算机网络可以被分为：Network Edge，Network Core，Access Network。 Network EdgeEdge由各种终端、应用等等组成。从edge的视角看，网络有两种模型： Client/Server 模型：在Client/Server模型下，设备朝服务器请求服务。典型的例子是万维网（www）、邮件等等。 Peer-peer 模型：在P2P模型下，没有专门的服务器。任何一个网络中的设备又作为客户端又作为服务端。典型的例子是BitTorrent。 Network CoreCore由路由、各种网络组成。在Core中，有两种通信方式： 电路交换：占用一个线路进行通信，例如电话线。 分组交换：将数据分为一个个小块发送。 Access Network接入终端到网络中。通常来说，新 ...

引入在掌握了矩阵理论和图论的基础工具后，我们现在要将视角转回到第一章曾介绍过的“平均模型”。第一章中的三个例子（社会学中的意见形成、传感器网络中的数据融合、机器人编队控制）虽然应用场景大相径庭，但在数学本质上，它们都可以被抽象为一个经典的离散时间动态系统。 回顾第一章中的状态转移式子： x(k + 1) = Ax(k) $x(k)$：代表系统在时刻 $k$ 的状态向量。比如网络中各个节点的温度读数，或者多智能体系统中各个机器人的位置。 $A$：是状态转移矩阵。它是行随机矩阵 (row-stochastic matrix)。 既然每个节点都在做局部平均，那么随着时间推移（$k \to \infty$），整个系统最终会演变成什么样？这就是系统的渐近行为 (asymptotic behavior)。这一章我们将基于 Perron-Frobenius 理论和代数图论来给出全面的收敛性结论。核心观点是：网络的拓扑结构决定了系统的宏观功能 我们主要关注以下几个维度： 达成一致 (Emergence of consensus)： 如果网络对应的矩阵是素矩阵 (primitive matri ...

拉普拉斯矩阵定义有向加权图（Weighted Digraph）的拉普拉斯矩阵的通用定义是： L = D_{out} - A $A$ (Adjacency matrix，邻接矩阵)：代表图的“骨架”和“权重”。节点 $i$ 指向节点 $j$ 有边，且权重是 $a_{ij}$，那么矩阵的第 $i$ 行第 $j$ 列就是 $a_{ij}$。 $D_{out}$ (Out-degree matrix，出度矩阵)：代表每个节点“向外输出”的总能量或总权重。它是一个对角矩阵（只有主对角线上有数字），对角线上的值是该节点所有出边权重之和。 $L$ (拉普拉斯矩阵)：两者相减。 对于加权有向图： 非对角线元素 ($i \neq j$): $\ell_{ij} = -a_{ij}$。即节点 $i$ 指向节点 $j$ 的边权重的相反数。如果节点间没有该方向的连边，则为 0。 对角线元素 ($i = j$): $\ell_{ii} = \sum_{h=1, h \neq i}^n a_{ih}$。这是节点 $i$ 的出度（注意求和条件 $h \neq i$ 明确排除了自环）。它等于该节点所有指向其他节 ...

引入：发展动力与系统这一章节旨在通过一些例子，阐述为什么要学习计算机控制网络，与了解计算机控制网络的一些基础。将会通过四个不同领域的系统（社会、WSN、动物集群、生态系统），引出了本课程的核心研究对象 ——网络化分布式系统。 核心数学工具：行随机矩阵、拉普拉斯矩阵、Metzler 矩阵。 核心科学问题：收敛性、平衡态、收敛速度。 例子1：社会影响网络中的观点这个模型叫French-Harary-DeGroot 模型，是观点动力学领域最经典的线性模型。 让我们考虑一组 n 个个体（这些个体可以被代换为网络系统中的个体、智能体，信号发生器或节点），需要共同决策某个未知参数的值（比如项目预算、产品定价）。每个人一开始都有自己的主观判断（用概率密度函数$p_i$表示，简单理解就是 “我认为这个值是多少”）。每个人都能看到其他人的观点，并且会通过加权平均的方式更新自己的观点。 p_{i}^{+}=\sum_{j=1}^{n} a_{i j} p_{j} $p_i^+$：更新后个体 i 的观点 $a_{ij}$：个体 i 给个体 j 的 “信任权重”(其中$a_{ii}$是”自我权重”—— ...

引入这一章节，主要讨论数据链路层的帧（frames） 数据链路层的主要作用是将一帧数据从一个节点传输到另一个临近的节点，它是物理层之上的一层逻辑，为网络层提供服务。链路层通常在网络适配器（NIC，网卡）中实现，比如以太网网卡、PCMCIA 卡等硬件设备。 在数据链路层中，有两种信道：点对点（Point-to-Point）和广播（Broadcast）。 链路层的核心功能有： 成帧（Framing）：将网络层传递下来的数据报（datagram）封装成帧（frame），并添加必要的头部（header）和尾部（trailer）开销。 流量控制（Flow control）：调节相邻发送节点和接收节点之间的发送速率，避免接收方缓冲区溢出，导致数据丢失。 差错控制（Error control）：接收方检测帧中是否存在传输错误。如果检测到错误，接收方会通过信号通知发送方重传该帧，或者直接丢弃出错的帧。 链路访问（Link access）：由介质访问控制（MAC）协议规定，解决多个节点共享同一通信信道时的访问规则问题。例如：以太网的 CSMA/CD、WiFi 的 CSMA/CA，都是典型的 MAC 协议 ...

图论基础图和有向图（Graphs and Diagraphs）无向图（Graphs）一个无向图 (Undirected graph)，简称为图 (Graph)，由两个集合组成： 节点集 (Nodes/Vertices)：用 $V$ 表示。 边集 (Edges)：用 $E$ 表示。 在无向图中，边是无序对（Unordered pairs）。也就是说，连接节点 $u$ 和 $ v $ 的边记作 $\{u, v\}$，它没有方向，从 $u$ 到 $ v $ 和从 $ v $ 到 $u$ 是一样的。 邻居 (Neighbors)：如果两个节点之间有一条边相连，我们就说它们互为邻居。节点 $ v $ 的所有邻居组成的集合，我们用 $\mathcal{N}_G(v)$ 来表示。 度数 (Degree)：一个节点 $ v $ 的“度”，就是它拥有的邻居的数量（或者说连着多少条边）。 正则图 (Regular Graph)：这是一个特殊的图类。如果一个图里所有节点的度数都一模一样，我们就叫它正则图。 下面是几种在实际应用中经常用到的基础图结构： 路径图 (Path graph)：像一根线一样， ...

链路层 若单帧出错概率是P，那么，$Nr=\frac{1}{1-p}$ ALOHA 脆弱期 2F， Slotted ALOHA F, CSMA $t_{prop}$ CSMA碰撞浪费$t_{frame}$的时间，CSMA/CD碰撞浪费$2t_{prop}$的时间 CSMA/CD最大吞吐量公式$\rho_{max}=\frac{t_{frame}}{t_{frame}+t_{prop}+2et_{prop}}$ 网络层 IP 分段相关字段： Identification：分段标识符 DF：Don’t Fragment，不分段标识符 MF：More Fragment，还有分段标识符 Offset：数据片段在原数据中的offset，单位为8byte HLEN：IP头长度，单位为4Bytes，最低为5 Total Length：整个IP包长度，单位为Bytes Dijikstra算法： 初始化：记目标节点邻接的节成本为$D(v)=c(u,v)$；非邻接$D(v)=\infty$ 找到拥有最小的$D(v)$的未着色节点$w$，前往着色。并更新所有节点的$D(v)=\min{D(v),D(w ...

引入：网络安全本章节是密码学与网络安全的简要介绍。 网络安全美国国家标准与技术研究院（NIST）对计算机安全的定义是：对自动化信息系统的保护，以实现保护信息系统资源（包括硬件、软件、固件、信息 / 数据和电信）的可用性、完整性和保密性的适用目标。其中，可用性、完整性和保密性被称为CIA三元组： Confidentiality（保密性） Data confidentiality：私有或机密信息不被未授权个体获取或披露。 Privacy：确保个人能够控制或影响与其相关的信息的收集、存储以及披露的对象和方式。 Integrity（完整性） Data integrity：确保信息和程序仅以特定且授权的方式被修改。 System integrity：确保系统以预期的方式运行，不受故意或无意的操纵。 Availability（可用性）：确保系统及时、充分地为授权用户提供服务，不被拒绝。 除了CIA三元组之外，网络安全需求还可以包括： Authenticity（真实性）：具有真实性，能够被验证和信任的属性。 Accountability（可问责性）：要求实体的行为可被唯一追溯到该实体的 ...

引入章节重点这一章节主要聚焦于套接字编程之上，HTTP这样的应用层协议。最后介绍P2P通信和其应用。 Web和HTTP是这一章节的重点，一些其他的应用层协议也会被简要介绍。 应用层在应用程序中，同一主机内的进程可通过进程间通信（inter-process communication） 交互，进程间通信遵循操作系统规则。而不同主机的进程通过计算机网络交换消息来通信。 而支持这些应用在设备-设备间通信、设备-服务器间通信，就是网络的终极目标。 在开发应用程序时，我们需要让程序员只专注于应用的功能，而无需关注网络和通信方面的实现，这就是应用层需要干的事情：使用应用层协议，让程序员轻易地迭代升级他们需要的功能。 两种通信架构客户端-服务端架构如其名字，客户端-服务端架构下，服务器为用户客户端提供服务。 服务器使用固定的IP地址，几乎始终在线。通过数据中心实现规模扩展（支持大量用户访问） 客户端可能是动态IP，甚至IP经过多层NAT。客户端与服务器通信，客户端与客户端之间不直接通信。 在客户端-服务端架构下，如果多个设备间需要相互通信（例如多人游戏），他们的数据会先被汇总到服务器，再由服务器 ...