数据结构

串的模式匹配

简单模式匹配算法

概念

子串的定位操作通常称为串的模式匹配，它求的是子串（模式串）在主串中的位置

算法思想

将主串中与模式串长度相同的子串逐个与模式串匹配，暴力法

缺点

主串指针回溯导致时间开销，时间复杂度为：O(nm)，nm分别为主串和模式串的长度

KMP算法

基本概念

前缀

除最后一个字符外，字符串的所有头部子串

后缀

除第一个字符外，字符串的所有尾部子串

算法思想

主串指针不必回溯，模式串指针根据next数组部分回溯（如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，可以将模式串向后滑动到与这些相等字符对齐的位置）

next数组

表明当模式中第j个字符与主串中相应字符匹配失败时，在模式中需重新和主串中该字符进行比较的字符位置

即衡量模式串向后滑动的量

计算

以“abab”为例

序号j = 1时，属于j == 1情况，next[j] = 0

序号j = 2时，‘a’的前后缀都为空集，属于其他情况，next[j] = 1

序号j = 3时，‘ab’的前缀为{a}，后缀为{b}，交集为空，属于其他情况，next[j] = 1

序号j = 4时，‘aba’的前缀为{a,ab}，后缀为{a,ba}，交集为{a}，k - 1 = 1（长度），next[j] = k = 2（长度+1）

时间复杂度：O(m + n)

进一步优化

构造nextval数组

若模式串指向的位置的字符等于本身，可以直接赋值

举例

5号的a中next数组指向3号位置，3号位置也是a故直接把3号的next数组值复制过去

6号的a中next数组指向4号位置，两者字符不同，不能优化

并查集

基本思路

存储结构

顺序存储，每个集合组织成一棵树，采用双亲表示法

所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组内

通常用数组元素的下标代表元素名，用根结点的下标代表子集合名

并查集应用

Cruskal算法、无向图的连通性、无向图是否有环

优化

查并

O(n) O(n^2)

小树合并到大树

O(log2n) O(nlog2n)

压缩路径

O(α(n)) O(nα(n))

压缩路径：查找路径上所有结点都直接挂根结点

代码

int find(int x){ //并查集核心代码，就两行！！！！ if (p[x] != x) p[x] = find(p[x]); return p[x]; }

红黑树

红黑树的概念

定义

红黑树是二叉排序树（左子树结点值 < 根结点值 < 右子树结点值）

根结点是黑色的（每个结点不是黑，就是红）

叶结点（外部结点/NULL结点/失败结点）均是黑色

不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色）

对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数目相同

口诀

左根右，根叶黑；不红红，黑路同

性质

根到叶结点最长路径不大于最短路径（全黑）2倍

n个结点高度h<=2log2(n+1)

黑高bh

从某结点出发（不包含该结点）到达任一空叶结点路径上黑色结点数

结论：若根结点黑高为h，内部结点数（关键字）最少有2^h-1个

红黑树的插入（删除）

考前看一看，记不住

红黑树的性能分析

计算机组成原理

补码加减运算器

布尔代数和基本逻辑电路

基本逻辑运算：与或非，任何逻辑表达式可写成三种基本运算的逻辑组合

组合逻辑电路：没有存储功能，输出仅依赖于当前输入

时序逻辑电路：具有存储功能，其输出不仅依赖于当前输入，还依赖于存储单元当前状态

一位加法器（全加器）

输入：加数A和B，低位进位Cin

输出：和：F = A ⊕ B ⊕ Cin 高位进位：Cout=A·B + A·Cin + B·Cin

串行加法器

n个全加器相连，进位触发器用来寄存进位信号，每一级进位依赖于前一级进位，进位信号逐级形成 Cout=A·B + (A⊕B)·Cin

并行加法器（单级/多级）

各级进位信号同时形成，又称先行进位，各进位之间无等待，相互独立并同时产生

辅助函数：进位生成信号 Gi = Ai·Bi 进位传递信号 Pi = Ai ⊕ Bi 全加逻辑方程：Si = Pi⊕Ci Ci+1 = Gi + Pi·Ci

C1 = G0 + P0·C0 C2 = G1 + P1·C1 = G1 + P1·G0 + P1·P0·C0 C3 = G2 + P2·C2 = G2 + P2·G1 + P2·P1·G0 + P2·P1·P0·C0 由上式可知：各进位之间无等待，相互独立并同时产生

ALU

利用二路选择器+带标志加法器构造加/减运算器

加/减运算器基础上加寄存器、移位器、控制逻辑可实现ALU

算数运算：取负、移位、加减乘除、扩展

逻辑运算：与或非

标志位的生成

n位带标志加法器

溢出标志OF（仅有符号数加减法有意义）

含义：有符号数的加减法是否发生了溢出

计算：OF=最高位产生的进位⊕次高位产生的进位

符号标志SF（仅有符号数加减法有意义）

含义：有符号数加减运算结果的正负性

SF=最高位的本位和

零标志ZF

含义：运算结果是否为0

计算：n 位全0，ZF=1

进/借位标志CF（仅无符号加减法有意义）

含义：加法时为进位标志，减法时为借位标志

计算：CF=最高位进位⊕sub（减法sub=1，加法sub=0）

乘法电路、除法电路的基本结构

加减乘除操作复杂建议考前听一遍王道课程

固态硬盘SSD

固态硬盘SSD

原理：Flash Memory，电可擦除ROM，即EEPROM

存储元由MOS管组成，是一种半导体存储器

组成

闪存翻译层：负责翻译逻辑块号，找到对应页

存储介质：闪存芯片组

读写

页为单位，相当于磁盘扇区

以块为单位擦除，每页可以写一次，读无限次

随机访问。读快写慢，写的页如果有数据不能写入，需要将块内其他页复制到新的块中，写入新的页

同一块擦除过多可能坏掉

磨损均衡技术

动态磨损均衡

写入数据时，优先选择累计擦除次数少的新闪存块

静态磨损均衡

SSD监测并自动进行数据分配、迁移，让老旧的块承担更多读为主的任务

静态磨损均衡算法比动态磨损算法的表现更优秀

高级语言程序与机器级代码之间的对应

编译器、汇编器和链路器的基本概念

程序的转换处理过程

编译方式：预处理程序、编译器、汇编器、链接器

解释方式：解释程序

选择结构、循环结构语句、过程（函数）调用对应的机器级表示

大题考察

多处理器基本概念

SISD、SIMD、MIMD的基本概念

SISD 单指令流单数据流

特性

各指令序列只能并发，不能并行，每条指令处理一两个数据

不是数据级并行技术

硬件组成

一个处理器+一个主存储器

若采用指令流水线，需多个功能部件，采用多模块交叉存储器

SIMD 单指令流多数据流

特性

多指令序列只能并发，不能并行，但每条指令可同时处理很多相同特征数据

数据级并行技术

硬件组成

一个指令控制部件（CU）+多个处理单元/执行单元 + 多个局部存储器 + 一个主存储器

每个执行单元有各自寄存器组、局部存储器、地址寄存器

不同执行单元执行同一条指令，不同数据

MISD 多指令流单数据流

不存在

MIMD 多指令流多数据流

特征

各指令序列并行执行，分别处理多个不同数据

是一种线程级并行，甚至线程级以上并行技术

分类（联想一下现实）

多处理器系统（共享内存多处理器/多处理器系统/多核处理器）

各处理器间，通过LOAD/STORE访问同一主存

多个处理器（共享单一物理地址空间）+一个主存储器

多计算机系统

不能直接访问不同计算机的存储器，只能通过“消息传递”通信

向量处理机（SIMD进阶）

指令处理对象是向量

主存储器采用“多端口同时读取”的交叉多模块存储器

多核处理器的基本概念

共享内存多处理器SMP的基本概念

一个CPU芯片中包含多个处理器（一块芯片上集成了多个处理器）

所有核共享一个LLC（Last-Level-Cache），并共享主存储器

两种架构

UMA

NUMA

多处理器访问统一的内存空间

优先给CPU分配最接近的内存

运算扩展性差

运算扩展性强

有Cache一致性问题

超线程技术

能够把一个物理处理器在软件层变成两个逻辑处理器

需要芯片组的支持才能发挥技术优势

硬件多线程的基本概念

指令发射

轮流发射各线程指令（每个时钟周期）

发射同一线程指令仅当流水线阻塞时切换

一个时钟周期内，同时发射多个线程指令

线程切换频率

每个时钟周期切换一次线程

仅流水线阻塞时切换

NULL

线程切换代价

低

高，需要重载流水线

NULL

并行性

指令级并行，线程间不并行

指令级并行，线程间不并行

指令级并行，线程级并行

总线事务

请求操作（请求阶段）

仲裁操作（仲裁阶段）

地址传输（寻址阶段）

数据传输（传输阶段）

总线释放（释放阶段）

总线的猝发传输

一个总线周期内传输存储地址连续的多个数据字的总线传输方式

I/O接口的基本结构（复杂，考前过一遍）

系统总线

数据线：读写数据、状态字、控制字（命令字）、中断类型号

地址线：指明I/O端口

控制线：读/写、I/O端口信号、中断请求类型号

步骤

发命令：发送命令字到I/O控制寄存器，向设备发命令（驱动程序协助）

读状态：从状态寄存器读取状态字，获得设备或I/O控制器状态

读/写数据：从数据缓冲寄存器发送或读取数据，完成主机与外设的数据交换

DMA控制（复杂，考前过一遍）

I/O设备需要进行数据传送时，向DMA发送DMA请求，DMA控制器向CPU发送I/O请求，CPU响应后让出系统总线，由DMA控制器接管总线，磁盘等高速外设成批地直接和主存进行数据交换

主存地址计数器AR：存放要交换数据的主存地址

传送长度计数器WC：记录传送数据的长度，计数溢出时，数据即传送完毕，自动发中断请求信号

数据缓冲寄存器：暂存每次传送的数据

DMA请求触发器：I/O发出控制信号，使得DMA请求触发置位

“控制/状态”逻辑：由控制和时序电路及状态标志组成，用于指定传送方向，修改传送参数，并对DMA请求信号和CPU响应信号进行协调和同步

中断机构：当一个数据块传送完毕后触发中断机构，向CPU提出中断请求

操作系统

程序运行时内存映像与地址空间

PCB

进程描述信息

进程标识符PID（标志进程）、用户标识符UID（标识归属用户，为共享和保护服务）

进程控制和管理信息

进程当前状态、进程优先级、代码运行入口地址、程序的外存地址、进入内存时间、处理机占用时间、信号量的使用

资源分配清单

说明有关内存地址空间或虚拟地址空间状况，所打开的文件列表和所使用的输入/输出设备信息

代码段指针、数据段指针、堆栈段指针、文件描述符、键盘、鼠标

处理机相关信息

处理机中各寄存器的值（代码段指针、数据段指针、堆栈段指针、文件描述符、键盘、鼠标）

程序段

概念

能被进程调度程序调度到CPU执行的程序代码段（指令序列）

共享正文段

常量 + 代码

数据段

概念

进程对应的程序加工处理的原始数据或者程序执行时产生的中间和最终结果

数据堆段

动态分配变量 new malloc()

数据栈段

未赋值变量/函数实参

全局区（静态区）

全局变量/静态变量

操作系统体系结构（新考点）

分层结构

内核分多层，每层可单向调用更低一层提供的接口

便于调试和验证（逐层调试验证），易扩充维护

难以定义各层边界，效率低，不可夸层调用

模块化

将内核分为多个模块，模块间相互协作，内核=主模块+可加载内核模块

易维护，可多模块同时开发；支持动态加载新的内核模块；任何模块可以直接调用其他模块

模块间相互依赖，难以调试

宏内核（大内核）

所有功能都放在内核中

性能高，内核内部功能可以互相直接调用

内核功能复杂，难以维护，内核某个功能模块出错，可能导致系统崩溃

微内核

只把中断、原语、进程通信等核心功能放入内核。进程管理、文件管理、设备管理等功能以用户进程的形式运行在用户态

内核小功能少、易于维护，可靠性高；功能模块崩溃不会导致整个系统崩溃

性能低不高效，需要频繁切换用户态/核心态，用户态下各功能模块不可以直接互相调用，只能内核的“消息传递”间接通信

基于C/S模式

外核

内核负责进程调度、进程通信等功能，外盒负责为用户进程安全分配硬件资源

外核可直接给用户进程分配“不虚拟、不抽象”的硬件资源

减少虚拟硬件资源的“映射层”，提升效率

降低了系统一致性，系统复杂

操作系统引导

CPU执行ROM中引导程序（硬件自检，再开机）

CPU执行指令跳转到BIOS，登记中断程序入口地址，硬件自检，进行操作系统引导

磁盘第一块------主引导记录读入内存，执行磁盘引导程序，扫描分区表

以活动分区读入分区引导记录，并执行

以根目录下找到完整操作系统初始化程序（启动管理器）并执行、开机

操作系统在初始化过程中创建中断向量表，磁盘相关在磁盘格式化化时完成

虚拟机

第一类VMM

安装Guset OS时，VMM要在原本的硬盘上自行分配存储空间

性能更好，可迁移性更差

第一类VMM运行在最高特权级，可以执行最高特权指令

第二类VMM

拥有自己的虚拟磁盘，实际上上Host OS文件系统中的一个大文件，分配到的是虚拟内存

性能差，需要Host OS为中介

第二类VMM部分运行在用户态，部分运行在内核态。Guest OS发出系统调用会被VMM截获，转化为VMM对Host OS的系统调用

线程的状态与转换、线程的组织与控制

线程控制块TCB

线程标识符、线程运行状态、优先级

线程切换保存/恢复

程序计数器PC、其他寄存器、堆栈指针

内核级线程与用户级线程调度

多对一模型

一对一模型

多对多模型

用户级线程：代码逻辑载体

内核级线程：运行机会载体

调度器/调度程序

决定让谁运行（调度算法）、运行多少时间（时间片大小）

处理对象可以是进程或内核级线程

闲逛进程

优先级最低

可以是0地址指令（占一个完整指令周期）

能耗低

多级队列调度算法

设置多个就绪队列，将不同类型或性质的进程固定分配到不同就绪队列

队列间可采用

固定优先级：高优先级空时优先级低才能调用

时间片划分：例如，列队分配时间50%、40%、10%

各队列可不同调度策略：系统队列采用优先级调度、交互式队列采用RR、批处理队列采用FCFS

上下文及其切换机制

上下文切换只能发生在内核态

进程切换（运行态<-->就绪态，内核态下完成）

引起

时间片到

更高优先级到达

进程主动阻塞

当前进程终止

原语执行过程

挂起一个进程，保存处理机上下文，包括程序计数器和其他寄存器

更新PCB信息

把进程的PCB移入相应队列（就绪/阻塞队列）

选择另一个进程执行，更新其PCB，更新内存管理的数据结构

跳转到新进程PCB中的程序计数器所指位置

恢复处理机上下文

互斥锁（自旋锁）

如TSL指令、swap指令、单标志法

忙等待，违反“让权等待”

等待期间不用切换进程上下文，在多处理器系统中，若上锁的时间短，则等待代价很低

条件变量

x.wait

当x对应条件不满足，正在调用管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程

x.signal

x对应的条件发生了变化，则调用x.signal，唤醒一个因x条件而阻塞的进程

类似于信号量的PV操作，但条件变量没有值，仅实现了“排队等待”功能

经典同步问题（比较复杂考前看看）

核心

实现互斥

初值为1，前P后V

实现同步

期望消息未产生则初值为0，反之为非0正数，前V后P

实现前驱关系

以下具体问题，提一下王道的重点思路，可以考前听王道

生产者-消费者问题

多生产者-多消费者问题

若盘子数为1，可省去mutex，本身访问互斥

吸烟者问题

读者-写者问题

增加P(w)、V(w)使写优先，防止源源不断读者，饥饿问题

增加互斥信号量使count--和if(count==0)一气呵成

哲学家进餐

思路一：最多允许四位同时吃饭

思路二：奇数号哲学家先拿左筷子，偶数号相反

思路三：仅当哲学家左右能同时拿起筷子时进食（拿筷子的动作加互相信号，一气呵成）

文件的打开：具体叙述了上文从文件名找到inode的过程（便于理解）

（首次使用文件）open系统调用，首先将外存中的目录复制到主存，检索目录项并找到文件名匹配的目录项（FCB），复制目录项到系统打开文件表（打开计数为1），在进程的打开文件表中新建一个条目（记录打开方式和系统打开文件表的索引）并返回文件描述符

解释：返回文件描述符fd，即返回一个指向进程用户打开文件表的指针，用户得到fd，即能建立文件描述符到外存中该文件inode的映射

（非首次使用文件）调用open请求，进程就可以打开文件，open会返回一个指向打开文件表中的一个条目的指针，通过使用该指针进行I/O操作

安装表：包含每个已安装文件系统分区的有关信息

目录结构缓存包：包含最近访问目录的信息

系统的打开文件表

见上文open系统调用讲解

进程的打开文件表

成组链接法（复杂，回收等细节可考前听一遍）

UNIX使用，结合了空闲表和空闲链表法，克服表太大的缺点

把顺序的n个空闲扇区地址保存在第一个空闲扇区中，其后一个空闲扇区内则保存另一个顺序空闲扇区的地址

目录区中专门磁盘块为“超级块”

系统启动时，超级块读入内存，与外存超级块保持一致

文件元数据

描述数据的数据，对数据及信息资源的描述性信息

目录的操作

搜索、创建文件、删除文件、创建目录、删除目录、移动目录、显示目录、修改目录

文件系统的全局结构

主引导记录MBR：计算机启动时，BIOS读入并执行MBR，MBR确定活动分区，读入它的第一块，即引导块

引导块：负责启动操作系统

超级块和空闲空间管理：分区块的数量、块的大小、空闲块相关

i结点区：存放索引结点

根目录：存放根目录

虚拟文件系统 VFS

VFS向用户提供了统一标准的系统调用接口

VFS要求下层文件系统必须实现某些规定的函数功能

每打开一个文件，VFS就在主存建立一个vnode，用统一的数据结构表示文件

vnode中函数功能指针指向不同文件系统的函数功能列表，然后执行具体文件系统的功能函数

文件系统挂载（插入U盘）

在VFS中注册新挂载的文件系统，内存中的挂载表（每个文件系统的相关信息）

新挂载的文件系统，要向VFS提供一个函数地址列表

将新文件系统加到挂载点，也就是将新文件系统挂载在某个父目录下

输入/输出应用程序接口、设备驱动程序接口

字符设备接口

字符设备是指数据存取和传输是以字符为单位的设备

get/put系统调用：读写一个字符

块设备接口

块设备指数据的存取和传书是以数据块为单位的设备

read/write系统调用：向块设备读写指针位置读写多字符

seek：修改指针位置

网络设备接口（网络套接字接口）

提供面向网络的通信的接口

socket：创建一个网络套接字

bind：套接字绑定某“端口”

connect：套接字连接到远程地址

read/write：从套接字读/写数据

阻塞/非阻塞I/O

阻塞I/O

程序发出I/O系统调用，进程转为阻塞态（键盘读）

非阻塞I/O

无需阻塞（磁盘写数据）

设备驱动程序接口

要求每个设备驱动程序与操作系统之间都有着相同或相近的接口

会使添加一个新设备驱动程序变得很容易，同时也便于开发人员编制设备驱动程序

计算机网络

虚拟局域网 VLAN

VLAN概述

一个或多个以太网交换机互连起来的交换式以太网，其所有站点都在同一个广播域

巨大的广播域会带来弊端

广播风暴（会浪费网络资源和各主机的CPU资源）

难以管理和维护

潜在的安全问题

网络上会频繁出现广播信息（TCP/IP协议栈很多协议会用到，例如ARP、RIP、DHCP等）

分隔广域网方法：路由器（成本高），虚拟局域网VLAN技术应运而生

虚拟局域网VLAN是一种将局域网内的设备划分成与物理位置无关的逻辑组的技术，逻辑组具有某些共同需求

划分VLAN的方式：基于交换机端口、基于MAC地址、基于IP地址

IEEE 802.1Q帧

VLAN标记的最后12比特称为VLAN标识符VID，它唯一标志了以太网帧属于哪一个VLAN

802.1Q帧是由交换机来处理的，而不是用户主机来处理的

当交换机收到普通的以太网帧时，会将其插入4字节的VLAN标记转变为802.1Q帧，简称“打标签”

当交换机转发802.1Q帧，可能会删除其4字节VLAN标记转变为普通以太网帧，简称“去标签”

交换机的端口类型

Access

Trunk

Hybrid

检验一下会没会

SDN基本概念

数据平面（转发具体过程、位于路由器中、硬件）

控制平面（路由选择、软件）

传统方法：位于路由器中（路由选择处理器）

SDN：位于远程控制器中

网络控制应用程序：根据SDN控制器提供的方法，应用程序能够监视、编程和控制下面的设备

SDN控制器：维护准确网络状态信息，为网络控制应用程序提供这些信息

北向接口：SDN控制器通过“北向接口”与网络控制应用程序交互

网络范围状态管理层：做出最终控制决定，要求有网络主机、链路等最新状态信息

通信层（南向接口、通信协议）：SDN控制器与受控网络设备之间的通信（Overflow协议），包含“南向接口”

受控网络设备

计算机网络体系结构通信过程（便于理解）

应用层按HTTP协议规定，构建一个HTTP请求报文，将HTTP请求报文交付给运输层处理

运输层给HTTP请求报文添加一个TCP首部，成为TCP报文段，将TCP报文段交付给网络层处理

网络层给TCP报文段添加一个IP首部，成为IP数据报，将IP数据报交付给数据链路层处理

数据链路层给IP数据报添加一个首部和一个尾部，成为帧，数据链路层将帧交付给物理层

物理层将帧看作比特流，给比特流前面添加前导码，将比特流变换成相应的信号发送给传输媒体，到达路由器

路由器处理过程

物理层将信号变换为比特流，去掉前导码后交付给数据链路层（交付的是帧）

数据链路层将帧的首部和尾部去掉，交付给网络层（交付的是IP数据报）

网络层解析IP数据报首部，从中提取目的网络地址，查找自身路由表，确定转发端口以便转发

网络层将IP数据报交付给数据链路层，数据链路层给IP数据报添加首部尾部，将帧交付给物理层，物理层加前导码，转换为信号发送到传输媒体，最好到达Web服务器

从物理层开始依次去掉首部，并交付给上层，最后将HTTP请求报文交付给应用层，应用层对HTTP报文解析，然后发回HTTP响应报文

IP数据报的发送（便于理解）

数据报数据部分

最大传送单元 MTU：一个链路层数据报能承载的最大数据量

以太网：1500B

广域网：576B

分片：当数据报长度大于链路MTU时，就要对其进行分片传输，分片会在目的地进行组装，不会在中间路由处组装

主机发送IP数据报

判断主机是否与自己在同一个网络（本机IP地址与子网掩码相与得到主机的网络地址，目的IP地址与本机的子网掩码相与得到目的网络地址，判断是否相等）

若在同一个网络，则属于直接交付

若不在同一个网络，则属于间接交付，传输给主机所在的默认网关

路由器转发IP数据报

检查IP数据报首部是否出错

若出错，则直接丢弃该IP数据报并通告源主机

若未出错，则进行转发

根据IP数据报的目的地址在路由表中查找匹配的条目

若找到匹配的条目，则转发给条目中指示的下一跳

若找不到，则丢弃该IP数据报并通告源主机

某主机发送本网段或其他网段的广播数据报，路由器不会转发

静态路由配置及其可能产生的路由环路问题

静态路由配置：给路由器人工配置路由表

方式简单、开销小。但不能及时适应网络状态（流量、拓扑等）的变化

一般在小规模网络中采用

路由环路的错误（三种）

配置错误

聚合了不存在的网络

以此举例，解决：给R2路由表添加黑洞路由

网络故障

路由表条目类型

直连网络

静态路由（人工配置）

动态路由（路由选择协议）

特殊的静态路由条目

默认路由（目的网络0.0.0.0，地址掩码0.0.0.0）

特定主机路由（目的网络为特定主机的IP地址，地址掩码为255.255.255.255）

黑洞路由（下一跳null 0）

CSMA/CA协议（复杂，考过IFS）

把碰撞检测改为碰撞避免，“碰撞避免”指协议的设计要尽量降低碰撞发送的概率

由于接受信号强度远小于发送信号强度，若实现碰撞检测，对硬件要求非常高

隐蔽站问题

站A、C检测不到对方无线信号，都给B发送帧时发生碰撞，且A、C无法检测

碰撞避免

ACK帧

所有站点在正确接收到发给自己的数据帧（除广播帧和组播帧），都需要向发送方发回一个ACK帧

帧间间隔IFS

所有的站点必须在持续检测到信道空闲一段指定时间后才能发送帧，该时间称为帧间间隔IFS

帧间间隔的长短取决于该站点要发送的帧的类型

高优先级帧需要等待的时间短，可获得优先发送权

短帧间间隔 SIFS

最短的帧间间隔，用来分隔开属于一次对话的各帧。一个站点应当能够在这段时间内从发送方式切换到接收方式

ACK帧、CTS帧、由过长的MAC帧分片后的数据帧、以及所有回答AP探询的帧和在PCF方式中接入点AP发送的任何帧

DCF帧间间隔DIFS

在DCF方式中用来发送数据帧和管理帧（用于异步竞争访问的时延）

退避算法

信道由忙转为空闲且经过DIFS时间后，还需要退避一段随机时间才能使用信道

使用退避算法

在发送数据帧之前检测到信道处于忙状态时

在每一次重传一个数据帧时

在每一次成功发送后要连续发送下一个帧时（避免站点长时间占用信道）

当退避计时器时间减少到0时，就开始发送数据

当退避计时器的时间还未减小到0时而信道又转变为忙状态，这时就冻结退避计时器的数值，重新等待信道变为空闲，再经过DIFS后，继续启动退避计时器

第i次退避，退避时间在{0, 1, ... , 2^(2+i)-1}中随机选择一个，然后乘以基本退避时间（一个时隙的长度），当时隙编号到255时（第六次退避）不再增加

信道预约和虚拟载波监听

信道预约

发送方在发送数据的同时向其他站点通知自己传输数据要的时间长度，让其他站点在这段时间内不发送数据，避免碰撞

RTS/CTS帧（广播帧）

可选的碰撞避免机制，解决隐蔽站问题

除源站和目的站以外的其他各站，在收到CTS帧（或数据帧）后推迟接入到无线局域网中，保证通信不会受其他站干扰

由于RTS帧和CTS帧很短，发送碰撞的概率、碰撞产生的开销及本身的开销都很小

隐蔽站问题

虚拟载波监听机制（解决隐蔽站问题）

除RTS帧和CTS帧会携带通信需要持续的时间，数据帧也能携带通信需要持续时间

A在给B发送数据帧前，可以使用RTS帧来预约信道，尽管C收不到RTS帧，但是C可以收到B发送给A的CTS帧，解决隐蔽站问题

路由转发过程（过程复杂）

路由算法

静态路由算法

非自适应路由算法，由网络管理员手工配置的路由信息

大型和复杂的网络环境通常不宜采用，管理员难以全面了解网络拓扑变化；发生改变后需大范围修改和调整路由信息

动态路由算法

距离-向量路由算法

所有结点都定期地将它们的整个路由选择表传送给所有与之之间相邻的结点

路由选择表内容

每条路径的目的地（另一结点）

路径的代价

更新条件

被通告一条新的路由，该路由在本结点的路由表中不存在，此时本地系统加入这条路由

来的路由信息中有一条到达某个目的地的路由，该路由与当前使用的路由相比，有较短的距离（较小的代价）

容易出现路由环路问题，RIP

链路状态路由算法

原理

链路状态路由算法要求每个参与该算法的结点都具有完全的网络拓扑信息

主动测试所有邻接结点的状态

定期地将链路状态传播给所有其他结点（或称路由结点）

特点

使用洪泛法向所有相邻的路由器发送信息，然后相邻路由器又向其他相邻路由器发送信息

发送的信息是与路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息

只有当链路状态发生变化时，路由器才向所有路由器发送此信息

用于大型或路由变化骤敛的环境，OSPF

层次路由

内部网关协议IGP

路由信息协议RIP（基于距离向量）

开放式最短路径优先OSPF（基于链路状态）

外部网关协议EGP

边界网关协议BGP

路由收敛

网络设备的路由表与网络拓扑结构保持一致

路由信息协议RIP

概述

RIP要求自治系统AS内每个路由器维护从它自己到AS内其他每个网络的距离记录。这是一组距离，称为“距离向量”

RIP使用跳数作为度量来衡量到达目的网络的距离，距离等于16时不可达，因此RIP只适用于小型互联网

当到达同一目的网络有多条“距离相等”的路由时，可以进行等价负载均衡

应用层协议，使用UDP

要点

和谁交换信息

仅和相邻路由器交换信息

交换什么信息

自己的路由表

何时交换信息

周期性交换（例如每30秒）

基本过程

路由器刚开始工作时，只知道自己到直连网络的距离为1

每个路由器仅和相邻路由器周期性地交换并更新路由信息

若干次交换和更新后，每个路由器都知道到达AS内各网络的最短距离和下一跳地址，称为收敛

坏消息传播得慢

又称路由环路或距离无穷计问题，这是距离向量算法的一个固有问题

解决

限制最大路径距离为15（16不可达）

当路由器发生变化时就立即发送更新报文“触发更新”，而非周期性发送

让路由器记录收到某特定路由信息的接口，不让同一路由信息再通过此接口的反方向传送“水平分割”

开放最短路径优先OSPF

概述

OSPF是基于链路状态的，而不像RIP基于距离向量

采用最短路径算法SPF计算路由，保证不会产生路由环路，不限制网络规模，更新/收敛速度快

链路状态

指路由器都和哪些路由器相邻，以及相应链路的“代价”（代价：费用、距离、时延、带宽等）

基本过程

OSPF的每个路由器都会产生链路状态通告LSA，包含

直连网络的链路状态信息

邻居路由器的链路状态信息

LSA被封装在链路状态更新分组LSU中，采用洪泛法发送

使用OSPF的每个路由器都有一个链路状态数据库LSDB，用于存储LSA

通过各路由器洪泛发送封装有自己LSA的LSU分组，各路由器的LSDB最终一致（30min刷新链路状态）

使用OSPF的各路由器基于LSDB进行最短路径优先SPF计算（基于Dijkstra算法），构建出各自达到其他路由器的最短路径，即构建各自路由表

分组类型

问候分组：用来发现和维持邻站的可达性

数据库描述分组：向邻站给出自己的链路状态数据库中的所有链路状态项目的摘要信息

链路状态请求分组：向对方请求发送某些链路状态项目的详细信息

链路状态更新分组：用洪泛法对全网更新链路状态

链路状态确认分组：对链路更新分组的确认

为了使OSPF能够用于规模很大的网络，OSPF把一个自治系统再划分为若干个更小的范围，叫做区域

边界网关协议BGP

概述

自治系统之间的路由选择必须考虑相关政策（政治、经济、安全等）

BGP只能是力求寻找一条能够到达目的网络且比较好的路由（不能兜圈子），而非要寻找一条最佳路由

BGP支持CIDR，所以路由表也该包括目的网络前缀

在BGP刚运行时，BGP的邻站交换整个BGP路由表，但以后只需在发生变化时更新有变化的部分

过程

在每个自治系统的管理员要选择至少一个路由器作为该自治系统的“BGP发言人”（BGP边界路由器）

一个BGP发言人与其他自治系统中的BGP发言人要交换路由信息，先建立 TCP连接

应用层协议、基于TCP

交换：到达某个网络所要经过的一系列AS（完整路径）

再利用BGP会话交换路由信息

所有BGP发言人都互相交换网络可达性的信息后，各BGP发言人就可找出到达各个自治系统的较好路由

报文类型

OPEN（打开）报文：用来与相邻的另一个BGP发言人建立关系，使通信初始化

UPDATE（更新）报文：用来通告某一路由的信息，以及列出要撤销的多条路由

KEEPALIVE（保活）报文：用来周期性地证实邻站的连通性

NOTIFICATION（通知）报文：用来发送检测到的差错

比较

协议

RIP

OSPF

BGP

类型

内部

内部

外部

传递协议

UDP

IP

TCP

可以巧记IU（大美女），IO（IO总不会忘吧），BT（变态）

层级

应用层

网络层

应用层

路由算法

距离-向量

链路状态

路径-向量

路径选择

跳数最少

代价最低

较好、非最佳

交换结点

和本结点相邻路由器

网络中所有路由器

和本结点相邻路由器

交换内容

当前本路由器全部信息，即自己路由表

与本路由器相邻的所有路由器的链路状态

首次：整个路由表更新：有变化的部分

间隔时间

每隔固定时间（30s）交换信息

链路状态发生变化

发生变化时

DHCP

概述

用于主机动态地分配IP地址，提供了即插即用的联网机制（地址可复用）

DHCP客户机广播“DHCP发现”消息，找网络中的DHCP服务器

DHCP服务器收到“DHCP发现”消息后，向网络中广播“DHCP提供”消息，其中包括提供DHCP客户机的IP地址和相关配置信息

DHCP客户机收到“DHCP提供”消息，如果接收DHCP服务器所提供的相关参数，那么通过广播“DHCP请求”消息向DHCP服务器请求提供IP地址

DHCP服务器广播“DHCP确认”消息，将IP地址分配给DHCP客户机

实现

若DHCP在另外的网段，可使用DHCP中继代理

DHCP服务器分配给DHCP客户的IP地址是临时的，因此DHCP客户只能在一段有限的时间内使用这个分配到的IP地址

DHCP的客户端、服务器用广播方式交互

基于UDP的应用层协议

IP组播（考前过一遍）

组播的概念

组播机制是让源计算机仅发送一次数据，被传递的数据到达尽可能近的结点才开始复制和分发，是种一对多的传输方式

实现过程

主机使用一个称为IGMP（因特网组管理协议）的协议加入组播组

使用该协议通知本地网络上的路由器关于要接收发送给某个组播组的分组的愿望，为组播数据报建立传播分发树

通过扩展路由器的路由选择和转发功能，可以在许多路由器互联的支持硬件组播的网络上面实现因特网组播

优点

数据只需发送一次就可发送到所有接收者，大大减轻了网络的负载和发送者的负担

组播需要路由器的支持才能实现，能够运行组播协议的路由器称为组播路由器

IP组播地址

属于多组播的设备将被分配一个组播组IP地址

结构

IP组播使用D类地址格式，地址范围为：224.0.0.0 - 239.255.255.255

组播数据报和一般IP数据报区别

组播数据报也是“尽最大努力交付”，不提供可靠交付

组播地址只能用于目的地址，而不能用于源地址

对组播数据报不产生ICMP差错报文，因此，若PING命令后面键入组播地址，将永远不会收到响应

并非所有的D类地址都可作为组播地址

分类

一种只在本局域网上进行硬件组播

一种在因特网的范围内进行组播，然后把组播数据报在局域网上用硬件组播交付给组播组的所有成员

硬件地址的映射关系不是唯一的，因此收到组播数据报的主机，还要在IP层利用软件进行过滤，把不是本主机要接收的数据报丢弃

IGMP与组播路由算法

概述

利用因特网管理协议（IGMP）使路由器知道组播组成员的信息

IGMP是TCP/IP的一部分

工作阶段

第一阶段

主机加入新的组播组时，该主机向组播组的组播地址发送一个IGMP报文，声明要成为该组的成员

本地的组播路由器收到IGMP报文后，将组成员关系转发给因特网上的其他组播路由器

第二阶段

本地组播路由器周期性地探询本地局域网上的主机，以便知道这些主机是否仍继续是组的成员

响应结果

只要对某个组有一台主机响应，那么组播路由器就认为这个组是活跃的

一个组在经过几次的探询后仍然没有一台主机响应时，则不再将该组的成员关系转发给其他的组播路由器

实现因特网组播的路由算法

基于链路状态的路由选择

基于距离-向量的路由选择

协议无关的组播（PIM）

移动IP（考前过一遍）

移动IP概述

概念

移动IP技术是移动结点（计算机/服务器等）以固定的网络IP地址，实现跨越不同网段的漫游功能，并保证了基于网络IP的网络权限在漫游过程中不发生任何改变

三种功能实体+两种地址

移动结点：具有永久IP地址的移动设备

归属代理（本地代理）：一个移动结点的永久“居所”称为归属网络，在归属网络中代表移动结点执行移动管理功能的实体叫做归属代理

外部代理（外地代理）：在外部网络中帮助移动结点完成移动管理功能的实体

永久地址（归属地址/主地址）：移动站点在归属网络中的原始地址

转交地址（辅地址）：可以是外部代理的地址或动态配置的一个地址

移动IP通信过程

移动结点刚进入外部网络

获得外部代理的转交地址（外部代理广播报文）

移动结点通告外部代理发送注册报文给归属代理（包含永久地址&转交地址）

归属代理接收请求，并将移动结点的永久地址和转交地址绑定（以后到达该归属代理的数据报且要发往移动结点的数据报将被封装并以隧道方式发给转交地址），并返回一注册响应报文

外部代理接收注册响应，并转发给移动结点

移动结点移动到了下一个网络

在新外部代理登记注册一个转交地址

新外部代理给本地代理发送新的转交地址（覆盖旧的）

通信

移动结点回到了归属网络

移动结点向本地代理注销转交地址

按原始方式通信

各种帧格式

以太网的MAC帧

网卡从网络上每收到一个MAC帧，首先要用硬件检查MAC帧中的MAC地址。如果是发往本站的帧，则收下，否则丢弃

局域网两个设备有相同MAC地址，两个设备都不能正常通信

前导码：使接收端与发送端时钟同步（MAC帧与PPP帧不同，没有帧界定符，用前导码同步）

目的/源地址：通常使用6字节（48bit）地址

类型：2字节，指出数据域中携带的数据应交给哪个协议实体处理

数据：46-1500字节，包括高层的协议信息。由于CSMA/CD算法的限制，以太网帧必须满足最小长度要求64字节，数据较少时必须加以填充（0-46字节）

填充：0-46字节，当帧长太短时（<64字节）填充帧

校验码FCS：采用CRC循环冗余码

PPP帧

IPv4数据报

版本：指IP版本，目前广泛使用的版本号是4

首部长度：最大值为60B，最常用20B

基本单位为4B

总长度：首部与数据之和，最大为65535B

基本单位为1B

标识：计数器，每产生一个数据报就+1

标志：3位，最低位MF，中间位DF

MF：More Fragment（1表还要分片，0表最后一个分片）

DF：Don't Fragment（1表不能分片，0表可以分片）

片偏移：指出分片后，某片在原分组中的相对位置

基本单位为8B

生存时间 TTL：防止路由环路，每次转发TTL - 1，当TTL为0则丢弃

协议：指出该分组使用的协议（TCP：6，UDP：17）

首部校验和：仅校验分组的首部

源地址字段/目的地址字段：IP地址

IPv6（特点难记，考前过一遍）

特点

IPv6将地址32位扩大到128位，扩展的地址层次结构

移除校验和字段，较少每跳的处理时间

将可选字段移出首部，变成扩展首部，成为灵活首部格式

IPv6支持即插即用，不需要DHCP协议

支持资源的预分配

IPv6只能在主机处分片，IPv4可以在主机/路由器分片

IPv6的首部长度需是8B整数倍，IPv4是4B整数倍

增大了安全性

数据报格式（40B）

版本：指明协议版本，6

优先级：区分数据报类别和优先级

流标签：属于同一个流的数据报有同样的流标签

下一个首部：标识下一个扩展首部或上层协议首部

跳数限制：等于 TTL

优势

增加空间

改进首部格式--->快速处理

支持QoS（网络安全机制，解决网络延迟与阻塞）

IPv6地址

基本类型地址

单播：传统点对点通信

多播：多播是一点对多点的通信，分组被交付到一组计算机的每台计算机

任播：目的站是一组计算机，但数据报在交付时只交付其中的一台计算机，通常是距离最近的一台计算机

压缩中双冒号只能出现一次

IPv4向IPv6的过渡

双协议栈

指一台设备上，同时装有IPv4和IPv6协议栈，那么该设备既能和IPv4通信，又能和IPv6通信

隧道技术

将整个IPv6数据报封装到IPv4数据报的数据部分，使得IPv6数据报可以在IPv4的隧道中传输

UDP

UDP数据报

UDP首部格式（8B）

长度；UDP数据报的长度（首部+数据），其最小值是8（单位是1B）

校验和：检测UDP数据报在传输中是否有错，有错就丢弃。该字段是可选的，当主机不想计算则为0

UDP校验

伪首部只有在计算校验和时才出现，不向下传送也不向上递交

17：封装UDP报文的IP数据报首部协议字段是17

UDP长度：UDP首部8B+数据部分长度（不包括伪首部）

校验过程

若主机不想计算校验和，则校验和段全0

TCP报文段首部格式（20B）

源端口和目的端口：标识该TCP报文段的应用进程

序号：指出本TCP报文段数据载荷的第一个字节的序号

确认号：期望收到对方下一个数据报的数据载荷的第一个字节的序号，也是对收到所有数据的确认

若确认号=n，n-1数据已经正确接收

数据偏移：指出TCP报文段的数据起始处距离TCP报文段的起始处有多远（指出首部长度）

单位为4字节

保留：今后使用

URG：紧急指针字段有效

ACK：取值为1时确认号字段才有效

PSH：报文段尽快上交应用进程，不必等到接收缓存都填满后再向上交付

RST：用来复位TCP连接，为1时，表明TCP连接出现了异常，必须释放连接再重新建立连接；还用来拒绝一个非法的报文段或拒绝打开一个TCP连接

SYN：在TCP连接建立时用来同步序号

FIN：用来释放TCP连接

窗口：指出发送本报文段一方的接收窗口

校验和：检查包括TCP报文段首部和数据载荷两部分（校验时需加上前面12字节伪首部）

紧急指针：指出在本报文段中紧急数据共有多少字节（当发送方有紧急数据时，可将紧急数据插队到发送缓存的最前面）

选项

最大报文段长度MSS选项：TCP报文段数据载荷部分的最大长度

窗口扩大选项：为了扩大窗口（提高吞吐率）

时间戳选项：用来计算往返时间RTT；用于处理序号超范围情况

选择确认选项

填充：使整个首部长度是4B的整数倍