Yuchen You

传输层的目的是将从 终端-终端通信的 ip 协议转变为 app-app 的通信 IP 是一种弱连接服务模型, 数据包有可能损坏, 延迟, 丢包, 重复等, 以及物理线路流量问题(例如流量大的时候如何明智的选择时机发送包), 处理这些问题也可以让应用层避免考虑这些棘手的问题 多项选择与去选择 Mux: 发送端将不同软件的数据汇集到一起发送到网络层 Demux: 将汇总的数据发送到接收端不同的 socket 传输层的功能 事实上的通信是在 process 之间进行的, 通过 ports 进行实现收发 帮助软件层实现 end-to-end 服务, 要求可靠, 配送速度均匀 发送太快会占满带宽 发送太慢会导致低效 udp 是一种 最小运输协议 只提供 mux/demux 功能 socket 类型是 SOCK_DGRAM tcp 是一种可靠的, 有序的 byte stream abstraction socket 类型是 SOCK_STREAM 拥有拥塞控制 (Congestion Control) Socket 是一种软件的抽象, 作为 app process 与系统 (transmi ...

Resource Acquisition Is Initialization (RAII) Resource 资源 定义: 持有价值昂贵的，可以被获取和释放的对象为资源，常见的有 Memory, Mutex, File Lifetime 生命周期 一个变量通过调用构造函数来实现 introduction 和 initialization 在退出 {} 的时候，系统会按照与定义相反的方向进行析构函数 RAII 定义: 利用变量的生命周期来实现资源的构造和析构管理 优点 资源可以实现自动析构在退出定义域的时候，尤其是 return 和 throw 的情况下 对于一些底层的代码实现，例如根 root 线程对象的销毁处理，如果手动销毁，就会在结束前提前释放 stack 从而导致无法继续执行，而利用析构函数自动销毁就可以实现 不用担心手动释放资源 对于一个 mutex 结构如果在入口处进行一次 lock 而在每一种退出处 (return, throw) 都必须执行 unlock ，就会导致上锁解锁的不对称性，容易忘记且效果不好, 这时候应该依赖在对象的析构函数来进行解锁(构造函数实现上锁 ...

OS 抽象机制 OS 是一种对硬件功能映射到软件层的抽象机制 cpu -> process/thread ram -> address space disk -> files 进程属性 进程 process 是一个在执行中的程序, program 是一个静态 static 的实体，有能执行的潜能 每个线程拥有所有程序运行所需要的状态和属性 address space (memory) code (text) data (global -> heap) stack (运行状态) PC 表示程序运行进度 通用reg 通用 OS 资源如网络连接等 进程之间互相 isolate 即不可访问其他线程 线程属性 线程表示的是一系列执行流 execution stream 定义了 PC, SP, register, 没有定义单独的 address space, general process attributes (PID, open files…) 每个线程只能归属于一个 process, 一个进程可以有多个线程 同进程线程共享 进程内表示状态的资源： re ...

Socket 定义 socket 即套接字，是一个双向通信通道，两端为两个process或者两个机器 socket是对网络通信的一种抽象 提供了数据交换的 api 去处了一些网卡交互的细节 服务器工作流 server flow 用户工作流 client flow 工作流解读 SC 交互 socket() 构造 参数为 socket(int domain, int type, int protocol, 都使用宏定义进行输入的 domain 表示交流的范围，对于 IPv4 使用宏 AF_NET type 定义了交流的semantics, 对于双向交流的 socket，使用宏 SOCK_STREAM protocol 定义了协议，使用宏 IPPROTO_tCP 即可 整个函数定义在 <sys/socket.h> bind() 绑定 参数为 bind(int sockfd, const struct sockaddr_in * addr, socklen_t addrlen); sockfd: 上文构造的 socket 对象 addr 定义了一些参数包括 port ...

Message Integrity 信息完整性 定义 ensures that attackers cannot modify a message w/o being detected. MITM 模型 传输部分 并不完全相信网络的信息的真实性 希望 Bob 接收到的完全就是 Alice 发出的信息 威胁模型 threat model Mallory 可以 see/modify/forge(伪造) message Mallory 的目的是让 Bob 相信一个不是由 Alice 发出的信息 防御威胁的方法论 verifier 验证器 如图所示，在发送的时候额外传送一个验证码，即要求验证码 v=f(m)v = f(m)v=f(m) random function 完全随机函数 被 A/B 容易计算，但是不容易被 M 计算 (即不被知道) 如果被找到 x≠mx\neq mx​=m 且 f(m)=f(x)f(m) = f(x)f(m)=f(x) 的 collision 就失败了 表示方法：用一个很大的表格记录映射关系，需要内存非常大 优点: 完全安全，即 M 除了瞎猜没有更好的 ...

概述 网络信息传播需要遵循 应用(Application) -> 封装送货信息+路由选择(Transport) -> 国际地址封装(Network) -> 地区地址封装(Data Link) -> 物理层发送(Physical) 的五层收发结构 低层级 (后面的不需要知道前面发生了什么) 每一层只负责该层任务以及与相邻层的 api 交互 同层之间遵循同样的协议，可以互相交流 分层的优缺点 优点 reduce complexity improve flexibility better manageability increase redundancy (冗余多): 每一层都有自己的恢复措施，因此可靠性更强 缺点 high overhead cross layer information is often useful speed decreased 封装形式 Header: 每一层协议，除了物理层都会给数据包在前面 append 一个表头表示 instructions on how to process payload. Payload: 表示有效 ...

定义 一个图 G=(V,E)G = (V,E)G=(V,E) 由点的集合 VVV 和边的集合 EEE 组成 平行边 两个节点之间存在多条边界 self-loop 自循环 没有自循环的图称为 simple graph，两端不同的边称为 simple path connect path: 一个 simple path 存在于任意一对 vertices 之间 (节点间均间接/直接相连) cycle: 简单路径除了首尾 vertex 相同 稠密度 complete graph 任意两个 vertex 直接相连 dense graph 稠密图表示图内的 edge 数量很多 E∼V2E\sim V^2E∼V2 sparse graph 稀疏图 E∼VE\sim VE∼V 相邻关系表示 邻接矩阵 adjacency matrix 一个 0-1 矩阵，坐标 i,j 表示边 (i,j) 是否存在于图中 常用于无权图 距离矩阵 distance matrix 在这个距离矩阵中，对应坐标的值表示对应 edge 的距离 一般用 ∞\infty∞ 表示不存在通路 邻接表 adjacency list 点均边 ...

定理内容 SAT 问题是 NP-complete 问题 由于 SAT 问题在给定 certificate 的情况下只需要逐个检验是否符合, 复杂度是 polynomial -> NP, 因此这里只需要证明其是 NP-hard 即可 证明 NP-Hard 利用 NP-hard 的定义, 这里需要证明对所有的 language L∈NPL\in NPL∈NP 都有 L≤pSATL\le_p SATL≤p​SAT (因为 SAT 问题往往会作为 NP-hard origin 来归纳其他的问题是否 NP-hard, 这里不能用其他 NP-hard 来归纳之) 因此假设我们有一个任意 np 问题的 instance x 和一个输入语言 L ∈\in∈ NP, 即存在 Verify−LVerify-LVerify−L 可以在多项式时间内决定 L; 证明目的是是否存在一个 SAT instance ϕ\phiϕ satisfiable iff 存在 c 使得 Verify-L(x,c) accept 定义 VL 算法为一个 TM, 并将其编码为一个 ∣x∣k×∣x∣k|x|^k\times | ...

定义 A language LLL is NP-complete if L∈L\inL∈ NP LLL is NP-hard 证明方法: polynomial-time mapping reduction 定义归纳关系 A≤pBA\le_p BA≤p​B 表示 ∃f s.t. x∈A⇔f(x)∈B\exists f \text{ s.t. } x \in A\Leftrightarrow f(x) \in B∃f s.t. x∈A⇔f(x)∈B 引理 lemma B∈P⇒A∈PB\in P \Rightarrow A \in PB∈P⇒A∈P AAA NP-hard ⇒\Rightarrow⇒ B NP-hard 用法 选取一个已知的 NP-hard 问题 A 来归纳关系 A≤pBA\le_p BA≤p​B 定义问题转变映射: 如何将问题集合 A 的某个确定 instance 转变为 B 的对应的 instance 证明这个转变 f 的时间复杂度是 polynomial 证明 correctness: 证明一个能解决 A 的 answer 同样在转变的问题中可以以同样的答案 ...

树的定义 没有 cycle 的无向图 rooted tree 存在某个 node 作为根节点 每个节点事实上都可以作为 root 二叉树的操作复杂度 二叉树的方法时间复杂度看的主要是二叉树自身的结构形状，如果是 complete 树是最好情况; 如果是 每个节点都只有一个子枝，其复杂度最大，是 worst case 数组法 insert 最好 O(1) 最差 O(n) 和树的排布方式有关，如果树的根节点的某个字节点为空那么直接插入，复杂度 O(1); 如果全部排满我们需要遍历找到空节点位置那么时间复杂度 O(n) remove 最差 O(n) parent O(1) child O(1) space 最好 O(n) 最差 O(2^n) 这里取决于数据的排布方式, 如果是完全二叉树，那只需要 O(n) 空间; 如果是完全一叉树 (每个node最多只有一个节点) 就需要 O(2^n) 空间 指针法 insert 好 O(1) 坏 O(n) remove 坏 O(n) parent O(n) 因为没有爹指针 child O(1) space 好 O(n) 坏 ...