传输层提供的功能

1 传输层的功能

传输层位于网络层之上，为应用层提供通信服务，它是通信部分的最高层和用户功能的最低层。
传输层的功能：

• 提供进程之间的逻辑通信(端到端通信)
• 复用：不同进程可以使用同一传输层协议传递数据
• 分用：数据接收方能够将不同应用程序的数据正确交付
• 差错检测：对报文的首部和数据部分进行差错检测
• 提供两种传输协议：TCP和UDP

2 传输层的寻址与端口

1. 端口的作用
   端口用于标识主机中的应用进程
2. 端口号
   端口号长度为16bit,能够表示65536(2¹⁶)个不同端口号
   常用端口号：

1. 套接字

   套接字=(主机号：端口号)
   套接字唯一的标识了网络中一个主机和其上的一个进程

3 无连接服务与面向连接服务

1. TCP协议
   TCP协议是面向连接的传输控制协议，提供可靠的传输服务，不提供广播或组播服务。应用场合有：FTP、HTTP和TELNET等
2. UDP协议
   UDP是无连接的非可靠的传输层协议，UDP具有较好的速度，应用场合有：TFTP、DNS、SNMP和RTP等

UDP协议

1 UDP概述

UDP在IP数据报服务基础之上增加了复用和分用以及差错检测两个最基本服务。 UDP协议有以下优势：

- 无需建立连接：速度快
- 无连接状态：不用维护连接状态
- 分组开销小：TCP首部20字节，UDP首部8字节
- 没有拥塞机制：网络中拥塞不会影响主机发送效率

UDP常用于一次性传输较少量的数据，UDP不提供可靠传输，可靠性由应用层完成。

2 UDP的首部格式

UDP数据报包含首部和数据部分，其中首部占8字节平分成四段，分别为：

- 源端口
- 目的端口
- UDP长度(包含首部和数据部分)
- UDP校验和

3 UDP校验

伪首部：在UDP数据报前加上12字节的伪首部，形成临时UDP数据报，用于计算校验和，伪首部不传送或递交，其唯一功能就是计算校验和。
校验：IP数据报的校验只检验数据部分，而UDP的校验将首部和数据部分一起检验。
校验和计算：将临时UDP以16位为一个数，进行二进制反码运算求和，所得结果再求反即为校验和
反码：二进制数据第一位为符号位，符号位为‘0’表示正数，符号位为‘1’表示负数，正数的反码为其本身，负数的反码为其各个数位取反(符号位不变)。

TCP协议

1 TCP协议特点

TCP协议是在不可靠的IP层之上提供可靠的数据传输的协议。
TCP协议特点：

- 面向连接的传输层协议
- TCP连接是点对点连接
- 提供可靠的交付服务
- 提供全双工通信
- TCP是面向字节流的：TCP把应用程序交下来的数据看成无结构的字节流

2 TCP报文

TCP传输的数据单元是数据段，TCP数据段分为TCP首部和TCP数据两部分，TCP段作为IP数据报的数据部分封装。TCP首部前20字节是固定的，总长度是4N字节。
TCP报文段各字段含义：

- 源端口和目的端口：各占2字节
- 序号：标记本段的第一个字节的序列
- 确认字段：确认号=N，表示序号N-1前的数据都正确接收
- 数据偏移:首部长度
- 保留字段：
- 紧急为URG
- 确认位ACK：ACK=1时确认位有效
- 推送位
- 复位位RST
- 同部位SYN：SYN=1 表示连接请求或连接接收报文
- 终止位FIN：FIN=1表示要求释放连接
- 窗口字段：
- 校验和：检验首部和数据部分
- 紧急指针字段
- 选项字段
- 填充字段

3 TCP连接管理

1. TCP连接建立
   三次握手：
   
   第一步：客户机发起连接请求
   第二步：服务器同意建立连接后发回确认，为该连接分配缓冲和变量
   第三步：客户机收到确认报文后向服务器给出确认，为连接分配缓存和变量

   关键字段：

   1 2 3

   SYN=1, seq=x SYN=1, ACK=1,seq=y,ack=x+1 ACK=1, seq=x+1,ack=y+1

2. TCP连接释放
   四次挥手：
   
   第一步：客户机发送释放连接报文
   第二步：服务器收到释放报文后发出确认
   第三步：服务器发送连接释放报文
   第四步：客户机收到释放报文后，发出确认。

   关键字段：

   1 2 3 4

   FIN=1，seq=u ACK=1,seq=v,ack=u+1 FIN=1,ACK=1,seq=w,ack=u+1 ACK=1,seq=u+1.ack=w+1

TCP可靠传输

1. 序号：TCP首部的序号字段用来保证数据有序提交
2. 确认：TCP首部的确认号表示期望收到对方的下一个报文段的数据的第一的字节的序号
3. 重传：
   • 超时:每发送一个报文段，为其设置计时器，计时器到期还未收到确认则重传该报文
   • 冗余ACK：接收方每收到一个比期望序列号大的失序报文段，发送一个冗余ACK(指明下一个期待字节的序号)给发送方，发送方收到三个冗余ACK就重传.

TCP流量控制

流量控制：流量控制服务匹配发送方的发送速率和接收方的读取速率来防止发送方使接收方缓存溢出。TCP利用窗口机制来实现流量控制。
接收窗口rwnd：衡量接收方的接收容量，由TCP报文首部的窗口字段给出。
拥塞窗口cwnd：由当前网络的拥塞情况决定，反映网络的当前容量。
发送方的发送窗口大小为接收窗口和拥塞窗口中的最小值，反应。

TCP拥塞控制

拥塞表现为通信时延的增加，拥塞控制就是防止过多的数据注入网络中。
拥塞控制和流量控制：
拥塞控制是全局性的过程，涉及所有主机和路由器。
流量控制是点对点的通信量控制，由接收端控制发送端。

拥塞控制算法有两种：

1 慢开始和拥塞避免

1. 慢开始算法
   拥塞窗口大小随着传输次数增加而呈2的指数倍增长，当拥塞窗口增大到慢开始门限(ssthresh)时改用拥塞避免算法。

2. 拥塞避免算法
   拥塞窗口大小随着传输次数线性增长，当出现网络拥塞时的窗口大小为cwnd，将慢开始门限降至cwnd的一半。

3. 网络拥塞的处理
   发生拥塞时，将慢开始门限降至出现拥塞时的发送方cwnd的一半，再将拥塞窗口大小重新设为1，执行慢开始算法

2 快重传和快恢复

1. 快重传
   当发送方连续接到3个重复的ACK，直接重传该ACK对应报文段。

2. 快恢复
   当收到3个冗余ACK时，将慢开始门限设为此时cwnd值的一半，并从慢开始门限处继续执行拥塞避免算法

网络层功能

1 异构网络互联

网络互联通常指用路由器进行网络互联和路由选择，在TCP/IP体系中，参加互联的计算机网络使用相同的IP协议，组成一个虚拟互联网络，该网络对互联的具体网络异构细节是透明的。

2 路由与转发

路由器主要完成两个功能：路由选择(确定哪一条路径)和分组转发(分组到达时所采取的行动)

3 拥塞控制

通信子网中，由于出现过量的分组而引起网络性能下降的现象称为拥塞。

判断：
网络负载增加而网络吞吐量明显小于正常吞吐量则网络进入”轻度拥塞”状态；若网络吞吐量随着网络负载的增加反而下降，网络进入拥塞状态；若网络吞吐量下降到零，则网络进入死锁状态。

流量控制和拥塞控制：
流量控制只涉及发送端和接收端，通过控制发送端的数据发送速率，使接收端及时接收。拥塞控制是全局问题，涉及网络中所有主机、路由器和导致网络传输能力下降的所有因素。

拥塞控制方法：

• 开环控制：事先考虑拥塞因素，预防拥塞产生，是一种静态方法。
• 闭环控制：事先不做处理，检测到拥塞再处理，是一种动态方法。

路由算法

1 静态路由和动态路由

静态路由算法：网络管理员手工配置路由信息
动态路由算法：路由器之之间彼此交换路由信息，按照一定的算法获得最优寻路效果

2 距离-向量路由算法

距离-向量路由算法中，所有节点定期将它们的整个路由选择表传送给所有直接相邻结点。路由选择表包括：每条路径的目的地和路径的距离(跳数)

3 链路状态路由算法

链路状态路由中，每个结点都有完全的网络拓扑图，当链路状态发生变化时，结点通过广播方式向所有结点告知与自己直接相连的链路信息。
距离-向量路由算法和链路状态路由算法比较：

4 层次路由

路由选择按照层次方式进行以适应网路规模的扩大

1. 内部网关协议(IGP)：自治系统内部所使用的路由选择协议
   • RIP协议
   • OSPF协议
2. 外部网关协议(EGP):自治系统之间所使用的路由协议
   • BGP协议

IPv4

1 IPv4分组

1. IPv4分组格式
   一个IP分组由首部和数据两部分组成，首部的前一部分长度固定为20(4*5)字节

   

   IP 首部重要字段：

    - 版本：IP协议版本
    - 首部长度：基本单位为4B(32位)
    - 总长度：基本单位为B(即字节)，最大长度为2<sup>16</sup>-1 = 65535 字节
    - 标识：每产生一个数据报，标识加一；一个数据报的不同分片标识相同
    - 标志：占3位，最低位为MF(more fragment),MF =1 表示还有分片，MF=0 表示最后一个分片；中间位为DF(Don't Fragment)，DF = 0 表示该数据报允许分片
    - 片偏移：基本单位为8字节(64位)
    - 首部检验和：只检验分组的首部，不检验数据部分
    - 生产时间TTL：数据报可通过路由器数的最大值
    - 协议：传输层协议
   

2. IP 数据报分片
   MTU：最大传输单元，指链路层数据报所能承受的最大数据量，以太网的MTU为1500字节。

3. 网络层转发分组的流程

IPv4地址与NAT

1. IPv4地址
   
   特殊IP地址：

   • 主机号全为0 表示本网络本身
   • 主机号全为1表示本网络的广播地址
   • 127.0.0.0用于环路自检，表示任意主机自身
   • 0.0.0.0表示本网络的本主机
   • 255.255.255.255 表示网络的广播地址

2. 网络地址转换(NAT)
   NAT：NAT通过将内网地址转化为公网地址，对外屏蔽内部IP地址。
   NAT转换表：储存{本地IP地址：端口}到{全球IP地址：端口}的映射关系
   NAT看得见端口，故工作在传输层

子网划分与子网掩码、CIDR

1. 子网划分
   从主机位借用若干比特作为子网号，如三级IP地址={网络号，子网号，主机号}

2. 子网掩码
   子网掩码(二进制)与主机IP地址作 与操作 得到 主机网络号

3. 无分类编址CIDR
   CIDR：取消传统ABCD类网络划分，采用{网络前缀，主机号}的两级编址
   路由聚合：将网络前缀相同的连续IP地址组成新的CIDR地址块
   最长前缀匹配：使用CIDR时查找路由表可能会得到多个匹配结果，应当在匹配结果中找具有最长网络前缀的路由。

ARP协议、DHCP协议与ICMP协议

1. ARP协议(地址解析协议)：
   每个主机本地高速缓存存放ARP表，用来维护IP地址到MAC地址的映射。A欲向B发数据时，查找ARP表，若找到，则将MAC地址写入MAC帧后发送；若找不到，则向局域网所有主机广播ARP请求，B收到请求后向A发出响应，A更新B的映射关系到ARP表，再次查询后将B的MAC地址写入MAC帧，发送数据。
   ARP协议工作在网络层。

2. 动态主机配置协议DHCP
   DHCP 常用于给主机动态地分配IP地址，DHCP是基于UDP的应用层协议
   DHCP工作原理：
   需要IP的主机广播发现报文，DHCP服务器收到报文后回答此广播报文，为其分配地址，称为提供报文。
   DHCP客户端和服务端通过广播方式进行交互。

网际控制报文协议ICMP

ICMP 是IP层协议，用来报告差错和异常情况。
ICMP报文种类：

• ICMP差错报告报文：
  • 终点不可达
  • 源点抑制
  • 时间超时
  • 参数问题
  • 改变路由
• ICMP询问报文
  • 会送请求和回答报文
  • 时间戳请求和回答报文
  • 掩码地址请求和回答报文
  • 路由器询问和通告报文
  • ICMP的应用：
• PING：工作在应用层
• traceroute：工作在网络层

IPv6

IPv6 采用128位地址

路由协议

自治系统

自治系统(AS)：单一技术管理下的一组路由器，使用内部路由选择协议确定分组在AS内的路由，使用域间路由协议确定分组在AS之间的路由。

域内路由与域间路由

1. 内部网关协议

• RIP协议
• OSPF协议

1. 外部网关协议

• BGP-4

RIP路由协议

RIP是一种分布式的基于距离向量的路由选择协议，是基于UDP的应用层协议
RIP 协议规定：

• 路由器维护自己到其他每一个路由器的距离记录(这样一组距离称为距离向量)
• 每经过一个路由器跳数加一，最多允许15跳，距离为16时表示网络不可达。
• 优先选择跳数小的路径

RIP 协议优点：实现简单，开销小
RIP协议缺点：

• 由于要交换完整路由表，网络规模越大，开销越大
• 网络故障时会出现慢收敛现象，俗称“坏消息传的慢”

OSPF路由协议

1. OSPF协议基本特点
   开发最短路径优先(OSPF)协议是使用分布式链路状态路由算法的典型代表。
   OSPF协议特点：

• 使用泛红法向所有路由器发送信息
• 发送信息为与本路由器相邻的所有路由器的链路状态
• 链路发生变化时，路由器才用泛红法向所有路由器发送此消息，更新收敛块
• OSPF是网络层协议,使用IP数据报传送；而RIP是应用层协议，使用UDP传送。
• 每隔一段时间刷新一次数据库中的链路状态

BGP路由协议

边界网关协议(BGP)是不同自治系统的路由器之间交换路由信息的协议。
BGP是基于TCP的应用层协议。
工作原理：每个自治系统选择一个“BGP”发言人，发言人之间要交换路由信息时，先建立TCP连接。
三种路由协议的比较：

网络层设备

路由器组成和功能

路由器是一种具有多个输入输出端口的专用计算机，其任务是连接异构的网络并完成路由转发。
路由器是网络层设备，它实现了物理层、数据链路层和网络层。

路由器组成：

• 路由选择：控制部分，其任务是根据路由选择协议构造路由表，并对路由表进行维护和更新。
• 分组转发：
  • 交换结构：处理分组
  • 一组输入端口：从比特流提取网络从数据
  • 一组输出端口：与输入端口进行相反操作

路由表与路由转发

路由表根据路由选择算法得出，用于路由选择。包含目的网络IP地址、子网掩码、下一跳IP地址和接口。
转发表由路由表得出，包含分组的目的地址和下一跳地址(MAC)

数据链路层的功能

为网络层提供服务

1. 无确认的无连接服务
2. 有确认的无连接服务
3. 有确认的面向连接服务

链路管理

数据链路层连接的建立、维持和释放过程称为链路管理

1. 帧定界、帧同步与透明传输

• 帧定界：数据加首部和尾部构成帧，首尾用于帧的定界
• 帧同步：接收端区分帧的起始和结束
• 透明传输：若在数据中出现与定界符相同的比特组合，进行转意

流量控制

限制发送方数据流量，使其处在接收方接受能力之内

差错控制

差错控制用于确保接收方正确接受数据

• 位错：帧中某位出现差错，通常采用循环冗余校验(CRC) 发现位错，通过自动重传请求(ARQ)来重传出错的帧
• 帧错： 帧的丢失、重复或失序等，引入定时器和编号机制。

组帧

组帧主要解决帧定界、帧同步、透明传输问题。实现组帧的方法有以下四种

字符统计法

在帧头部使用一个计数字段来标明帧内字符数

字符填充的首尾定界符法

使用特点的定界字符来定界一帧的开始和结束，使用转意字符来实现透明传输

比特填充的首尾标志法

用01111110(16进制为7E)来标志一帧的开始和结束。
透明传输实现：发送方信息中每遇到5个连续的‘1’则在其后插入一个‘0’，接受方每遇到5个连续的‘1’则自动删除其后的‘0’。

违规编码法

如，曼切斯特编码中使用未定义的高-高电平对和低-低电平对作为定界帧

差错控制

检错编码

1. 奇偶校验码
2. 循环冗余码(CRC):
   发送方和接收方商定除数P，二进制数据A采用模2运算(加法不进位，减法不借位，类似异或)除以P，得到余数加在A末尾，并令其为B，将B传输给接收方，接收方将B除以P，若余数为0则传输未出错。
3. 纠错编码
   最常见的纠错编码是海明码

流量控制与可靠传输机制

流量控制、可靠传输与滑动窗口机制

1. 停止-等待协议流量控制基本原理
   发送方每发一个帧要等待接收方应答才能继续发，接收方每接收一个帧都要反馈一个应答信号
2. 滑动窗口流量控制基本原理
   发送方维护发送窗口，接收方维护接收窗口，发送窗口用来对发送方进行流量控制，接收窗口用来对接收数据帧进行控制。
   滑动窗口特性：只有接受窗口向前滑动时(接受窗口发送确认帧)，发送窗口才能向前滑动；当滑动窗口大小为1，可保证帧的有序接受；数据链路层的滑动窗口大小在传输过程中是固定的。

1. 可靠传输机制

• 确认：接受方对接收数据进行确认并告知发送方
• 超时重传：
• 自动重传请求(ARQ)：
  • 停-等式
  • 后退N帧
  • 选择重传

单帧滑动窗口与停止-等待协议

源站发送单个帧之后必须等待确认，在目的站的回答到达源站之前，源站不能发送其他数据帧

多帧滑动窗口与后退N帧协议(GBN)

发送方发送N个帧，如果该N帧的前一个帧被判为出错或丢失，则发送方重传该出错帧及其后N帧。
发送窗口大小W_T: 1<= W_T<=2ⁿ-1 (n为对帧编码的比特数)：

多帧滑动窗口与选择重传协议(SR)

一般情况下，发送窗口=接受窗口=2^(n-1),只对出错或超时的数据帧进行重传。
信道的效率：发送方从开始发送数据，到接收到第一个确认帧为止，称为一个发送周期，设为T，发送方在这个周期内共发送L比特的数据，发送方的数据传输率为C，则发送方用于发送有效数据的时间为L/C ,在这种情况下，信道的利用率为(L/C)/T。
信道吞吐率：信道利用率 * 发送方的发送速率。

介质访问控制

介质访问控制的内容是：采取一定的措施，使任意两点之间的通信不会发送互相干扰的情况。

信道划分介质访问控制

1. 频分多路复用(FDM)
   多路信号调制成不同频率载波后叠加成复合信号
2. 时分多路复用(TDM)
   一条物理信道按时间分成若干时间片，轮流地分配给多个信号使用
3. 波分多路复用(WDM)
   即光的频分多路复用
4. 码分多路复用(CDM)
   码分多路复用靠不同的编码来区分各路原始信号。
   码分多址(CDMA)是码分复用的一种方式
   CMDA原理:
   向量S表示A站的码片向量，T表示B站的码片向量,S和T均为m比特，则 $$S\cdot T=\frac{1}{m}\sum_{i=1}^mS_iT_i=0$$ $$S\cdot S=\frac{1}{m}\sum_{i=1}^mS_iS_i=1$$ 即不同站码片正交，相同码片规格化内积为1，码片与其反码规格化内积为-1

随机访问介质访问控制

不采用集中控制方式解决发送信息的次序问题，胜利者通过争用获得信道，从而获得信息的发送权。

1. ALOHA协议

• 纯ALOHA协议：任意站点可以不经检测直接发送数据，若一段时间未收到确认，则等待一段时间再发送数据。
• 时隙ALOHA协议：将时间划分为一段段等长的时隙，每个时隙开始时只能发送一个帧。其效率是纯ALOHA协议的两倍

1. CSMA协议
   在ALOHA协议基础上增加了载波监听装置
   根据监听方式和处理方式不同，有3种CSMA协议

• 1-坚持 CSMA：信道闲则发送数据，忙则等待并继续监听侦听，若发生冲突则随机一段时间后，再重新开始侦听
• 非坚持 CSMA：信道闲则发送数据，忙则等待，并放弃侦听，等待一段时间后继续监听
• p-坚持CSMA：用于时分信道。信道忙则等待下一个时隙再侦听，闲则以概率P发送数据，以概率(1-p)推迟到下一个时隙。

CSMA/CD 协议

CSMA/CD协议是CSMA协议的改进方案，CSMA/CD 只能进行半双工通信
CSMA/CD的工作流程：

• 先听后发
• 边听边发
• 冲突停发
• 随机重发

计算相关：

• 单程传播时延/总线传播时延：数据从源点发送到目的点接收所用时间
• 争用期(冲突窗口/碰撞窗口)：数据的往返时间，两倍单程传播时延
• 最小帧长：为了确保发送数据的同时能检测可能的冲突，数据帧有个最小长度
  最小帧长=总线传播时延*数据传输速率*2

CSMA/CA 协议

CSMA/CD用于有线局域网，CSMA/CA用于无线局域网

轮询访问介质访问协议：令牌传递协议

令牌在环形网上游荡，只有持有令牌的计算机才能发送数据。

局域网

局域网的基本概念体系结构

1. 局域网三要素

• 拓扑结构
  • 星形
  • 环形
  • 总线形
  • 复合类型
• 传输介质
  • 双绞线
  • 铜缆
  • 光纤
• 介质访问控制方式
  • CSMA/CD
  • 令牌总线
  • 令牌环

以太网与IEEE 802.3

1. 以太网传输介质与网卡
   传输介质：粗缆、细缆、双绞线、光纤
   网卡：局域网中连接计算机和传输介质的接口，工作在物理层和数据链路层
   Mac地址：介质访问控制地址用于控制主机在网络上的数据通信
   广播：以太网中的数据以广播形式发送
2. 以太网的MAC帧
3. 高速以太网

IEEE 902.3

IEEE 902.3是无线局域网的一系列协议标准

广域网

广域网基本概念

广域网是覆盖范围很广的长距离网络。局域网主要使用协议在数据链路层而广域网主要使用协议在网络层。常见的广域网数据链路层协议有PPP协议和HDLC协议。

PPP协议

PPP协议是使用串行路线通信的面向字节协议。
PPP协议组成部分：

• 链路控制协议LCP
• 网络控制协议NCP：
• IP数据报封装到串行链路的方法
  PPP协议是点对点的，不是总线形的，故无需采用CSMA/CD，帧长度页没有限制。PPP协议只支持全双工通信

HDLC协议

HDCL协议是面向比特的数据链路层协议。与PPP协议不同，HDCL协议采用了编号和确认机制，可以实现可靠传输。

数据链路层设备

网桥

两个以太网通过网桥连接，原来的每一个以太网称为网段，网桥工作在数据链路层的MAC层，可以使以太网成为隔离开的碰撞域

1. 透明网桥(选择的不是最佳路径)
2. 源路径网桥(选择的是最佳路径)

交换机

交换机是一个多端口网桥，可以隔离冲突域和广播域

1. 原理：
   检测数据帧的源和目的Mac地址，然后与系统内部动态查找表进行比较，如果MAC不再表中，则将该地址加入表中，并将数据帧发送到相应目的端口。
2. 特点

• 工作在全双工方式
• 独占传输媒体的带宽

1. 交换模式

• 直通式
• 存储转发式

计算机网络概述

计算机网络的概念

计算机网络是互联的、自治的计算机系统的集合

计算机网络的组成

1. 组成成分：

• 硬件
• 软件
• 协议

1. 工作方式

• 边缘部分：用户主机
• 核心部分：提供连通性、服务的网络和路由器

1. 功能组成

• 通讯子网：传输介质、通讯设备、网络协议组成
• 资源子网：实现资源共享功能的设备及软件集合

计算机网络功能

1. 数据通信
2. 资源共享
3. 分布式处理
4. 提高可靠性
5. 负载均衡

计算机网络的分类

1. 按分别范围分类

• 广域网(WAN)
• 城域网(MAN)
• 局域网(LAN)
• 个人区域网(PAN)

1. 按传输技术分类

• 广播式网络
• 点对点网络

1. 按拓扑结构分类

• 星形网络
• 总线形网络
• 网络形网络

1. 按使用者分类

• 公用网
• 专用网

1. 按交换技术分类

• 电路交换网络：源结点和目标结点间建立专用通路用于传送数据
• 报文交换网络：数据封装成报文，通过结点转发传输整个报文，直到到达目的结点
• 分组交换网络：数据分成较短的固定长度数据块并封装成分组，以存储-转发方式传输

1. 按传输介质分类

• 有线网络
• 无线网络

计算机网络的性能指标

1. 带宽：网络通信线路所能传送数据的能力，单位是“比特每秒”(b/s)
2. 时延：数据从一端传送到另一端的时间

• 发送时延：
• 传播时延
• 处理时延
• 排队时延
• 总时延：以上四种时延之和

1. 时延带宽积：传播时延 X 信道带宽
2. 往返时延(RTT)：
3. 吞吐量： 单位时间通过某个网络的数据量，受网络带宽限制
4. 速率：主机传送数据的速率，最高数据率即为带宽，单位为b/s，Kb/s(K=10^3),Mb/s(M=10^6),Gb/s(G=10^9)

计算机网络体系结构与参考模型

计算机网络分层结构

1. 体系结构：计算机各层及其协议的集合
2. 分层基本原则

• 每一层实现功能相对独立
• 各层之间界面清晰，交流少
• 各层功能的定义独立于具体实现
• 下层对上层独立，上层单向使用下层服务
• 分层结构标准化

计算机网络协议、接口、服务的概念

1. 协议：控制对等实体进行通信的规则的集合
2. 接口：相邻两层交换信息的连接点
3. 服务：下层为紧相邻的上层提高的功能调用，交换命令称为服务原语：请求、指示、响应、证实。
4. 服务类型

• 面向连接服务与无连接服务
  • 面向连接服务：如TCP
  • 无连接服务：如IP、UDP
• 可靠服务和不可靠服务
  • 可靠服务：网络具有纠错、检错、应答功能，保证可靠传输
  • 不可靠服务：不保证可靠传输
• 有应答服务和无应答服务
  • 有应答服务：如文件传输服务
  • 无应答服务：如WWW服务

ISO/OSI参考模型和TCP/IP模型

1. OSI参考模型

• 物理层
• 数据链路层
• 网络层
• 传输层
• 会话层
• 表示层
• 应用层

1. TCP/IP 模型

• 网络接口层
• 网际层
• 传输层
• 应用层

通信基础

基本概念

1. 数据、信号、码元

• 数据：传送信息的实体
• 信号：数据的电气或电磁表现，是数据传输过程的存在形式
• 码元：一个固定时长的信号波形

1. 信源、信道、信宿

• 信源：产生数据的源头
• 信宿：接受数据的终点
• 信道：信号的传输介质
• 通信交互方式：
  • 单工通信：单向传输，一条信道
  • 半双工通信：双向传输，不可同时收发，两条信道
  • 全双工通信：双向传输，可同时收发，两条信道

1. 速率、波特、带宽

• 速率(数据率)：数据传输速率：
  • 码元传输速率：单位时间传输的码元数，单位为波特(Baud)
  • 信息传输速率：单位时间传输的二进制码元数(即比特数)，单位比特/秒(b/s)
• 带宽：单位时间内网络中两点间的最高数据率

奈奎斯特定理与香农定理

1. 奈奎斯特定理：
   理想低通信道下的极限数据传输率 = 2Wlog₂V
   其中W是理想低通信道的带宽,单位HZ，V是每个码元离散电平数目(如四位二进制有16种不同码元)

2. 香农定理：
   信道的极限数据传输速率 = Wlog₂(1+S/N)
   信噪比 = 10log₁₀(S/N) 单位(dB)

编码与调制

数据变换为模拟信号的过程称为调制，数据变换为数字信号的过程称为编码

1. 数字数据编码为数字信号

• 非归零码
• 曼切斯特编码
• 差分曼切斯特编码

1. 数字数据调制为模拟数据

• 幅移键控
• 频移键控
• 相移键控
• 正交振幅调制

1. 模拟数据编码为数字数据
2. 模拟数据编码为模拟信号

电路交换、报文交换、分组交换

1. 电路交换: 数据传输前，两结点间建立专用物理通信路径
2. 报文交换：利用报文进行存储转发
3. 分组交换：利用分组进行存储转发
   ！数据交换方式

数据报与虚电路

分组交换分为面向无连接的数据报方式和面向连接的虚电路方式

传输介质

双绞线、同轴电缆、光纤与无线传输介质

1. 双绞线
2. 同轴电缆
3. 光纤
4. 无线传输介质

物理层接口的特性

1. 机械特性：定义物理连接的边界点
2. 电气特性：规定信号电压高低和阻抗匹配等
3. 功能特性：指明电压意义和信号线用途等
4. 规程特性：定义物理接口的工作规范

物理层设备

1. 中继器：信号整形并放大(但是中继器的原理是将衰减信号再生，而不是放大)在转发。受信号延迟规范制约，中继器不能无限增加。
2. 集线器(Hub)：多端口中继器,只能够在半双工下工作，多个端口均分总带宽。

I/O管理概述

I/O设备

1. 按使用特性分类

• 人机交互类外部设备
• 存储设备
• 网络通讯设备

1. 按传输速率分类

• 低速设备
• 中速设备
• 高速设备

1. 按信息交换的单位分类

• 块设备
• 字符设备

I/O控制方式

1. 程序直接控制方式
2. 中断驱动方式： 允许IO设备打断CPU的运行并请求服务
3. DMA方式:IO设备和内存之间开通直接的数据交换通路
4. 通道控制方式：引入专门的IO处理机进行管理(“CPU代理”)4

I/O子系统的层次结构

1. 用户层I/O软件
2. 设备独立性软件
3. 设备驱动程序
4. 中断处理程序
5. 硬件部分

I/O 核心子系统

1. I/O调度：确定执行I/O请求的顺序
2. 磁盘高速缓存：

3. 缓冲区：

   • 单缓冲
   • 双缓冲
   • 循环缓冲
   • 缓冲池

4. 设备分配与回收

• 分类：
  • 独占式使用设备
  • 分时式共享使用设备
  • SPOOLing方式使用外部设备
• 设备分配原则：
  • 充分发挥设备使用效率
  • 避免死锁
  • 用户程序和具体设备无关
• 分配方式：
  • 静态分配：作业开始前，系统一次性分配作业要求设备
  • 动态分配：进程执行过程中根据需要进行分配

文件系统基础

文件的概念

1. 文件的定义
   　　文件是以计算机硬盘为载体存储在计算机上的信息集合。文件系统是管理文件的机构
2. 文件自底向上结构
   • 数据项：文件系统最低级数据组织形式
   • 记录：一组相关数据项的集合
   • 文件：创建者定义的一组相关信息集合
3. 文件属性
   • 名称
   • 大小
   • 类型
   • 位置
   • 保护
   • 时间、日期和用户标识
4. 文件基本操作
   • 创建文件
   • 读文件
   • 写文件
   • 文件重定位
   • 删除文件
   • 截断文件
5. 文件的打开和关闭
   打开文件信息
   • 文件指针
   • 文件打开计数
   • 文件磁盘位置

文件逻辑结构

1. 无结构文件(流式文件)
2. 有结构文件(记录式文件)

• 顺序文件：
  • 串结构：记录之间的顺序与关键字无关
  • 顺序结构：记录按照关键字排序
• 引索文件
• 引索顺序文件
• 直接文件或散列文件

目录结构

目录管理通过树形结构实现

1. 文件控制块(FCB)和索引结点
   • 文件控制块：
     • 基本信息
     • 文件控制信息
     • 使用信息
   • 索引结点
2. 目录结构
   • 目录操作
     • 搜索
     • 创建文件
     • 删除文件
     • 显示目录
     • 修改目录
   • 目录结构
     • 单级目录结构
     • 两级目录结构
     • 多级目录结构：如Linux的目录结构
     • 无环图目录结构

文件共享

文件共享：多个用户或进程共享一份文件，系统中只保留该文件一份副本

1. 基于索引结点的共享方式(硬链接)
   多个指针指向一个索引结点，只要还有指针指向该索引节点，该索引结点就不能删除
2. 利用符号链实现文件共享(软连链接)
   记录到达共享文件的路径，根据文件路径找文件。
3. 比较：硬链接比软链接查找速度快

文件保护

文件保护通过口令保护、加密保护和访问控制方式实现

1. 访问类型
   • 读
   • 写
   • 执行
   • 添加
   • 删除
   • 列表清单
2. 访问类型
   • 拥有者
   • 组
   • 其他用户

文件系统实现

文件系统层次结构

目录实现

1. 线性列表
2. 哈希表

文件实现

1. 文件分配方式

• 连续分配：每个文件在磁盘中占用一个连续的块，支持顺序访问和直接访问，有外部碎片。
• 链接分配：采用离散分配方式，只支持指针顺序访问，无外部碎片。
• 索引分配：每个文件的盘块号构成索引块，若要读第i块，则通过索引块的第i个条目的指针来操作所需的块，支持多层索引和混合索引。

1. 文件存储空间管理

• 空闲表：所有空闲块组织成表
• 空闲链表法：所有空闲块组织成链表
• 位示图：利用二进制的每位记录空闲块，1表示块已经使用，0表示空闲
• 成组链接法：结合空闲表和空闲链表，适合大型文件系统

磁盘组织和管理

磁盘的结构

1. 磁道：盘面的一组同心圆
2. 扇区：磁道划分为扇区，磁盘可寻址的最小存储单位
3. 柱面：相对位置相同的磁道组成柱面
4. 磁盘地址：用“柱面号.盘面号.扇区号”表示

磁盘调度算法

一次磁盘读写操作由寻道时间、延迟时间、传输时间组成

• 寻道时间：磁头移动到指定磁道的时间
• 延迟时间：磁头定位到某一磁道的扇区时间
• 传输时间：读写数据的时间

磁盘调度算法

• 先来先服务(FCFS)算法
• 最短寻找时间优先(SSTF)
• 扫描(SCAN)算法或电梯算法
• 循环扫描(C-SCAN)算法

磁盘的管理

1. 磁盘初始化：对磁盘进行低级格式化和逻辑格式化
2. 引导快：存放自举程序，
3. 坏块：对于损坏扇区的处理

内存管理概念

内存管理的概念

1. 内存管理：操作系统对内存的换分和动态规划称为内存管理

2. 内存管理的功能

   • 内存空间的分配与回收
   • 地址转换
   • 内存空间扩展
   • 存储保护

3. 进程运行的基本原理

   1. 程序装入与链接
      • 编译：将源代码编译成目标模块
      • 链接：将目标模块和库函数链接成装入模块
        • 静态链接
        • 装入时动态链接
        • 运行时动态链接
      • 装入：将装入模块装入内存运行
        • 绝对装入：程序逻辑地址和实际内存地址相同
        • 可重定位装入(静态重定位)：装入模块装入内存时，进行重定位(地址转换)
        • 动态运行时装入(动态重定位)：地址转换在程序执行时进行
   2. 逻辑地址空间和物理地址空间
      • 相对地址：目标模块从0号单元开始编址，相对该地址的地址即为相对地址
      • 逻辑地址：内存中物理单元的集合称为逻辑地址空间，它是地址转换的最终地址
      • 地址重定位：逻辑地址转换为物理地址
   3. 内存保护
      • 重定位寄存器
      • 界地址寄存器

覆盖和交换

1. 覆盖
   将用户空间分成固定区和覆盖区，固定区存放活跃的部分，覆盖区存放即将访的段，其它段存放在外存。覆盖用于一个进程或进程中，覆盖技术对程序员不透明，已成历史。
2. 交换
   将处于等待状态的进程序从内存移到辅存称为换出，将准备好竞争CPU运行的程序从辅存移到内存称为换入。交换技术用于不同进程之间

连续分配管理方式

连续分配方式指为一个程序分配一个连续的内存空间。

1. 单一连续分配
   内存分为系统区和用户区，系统区给操作系统使用，用户区给一道用户程序使用，只能用在单任务操作系统中

2. 固定分区分配
   用户空间划分为若干个固定大小的区域，每个分区只装入一道程序。分区有等大小分区和不等大小分区。固定分区有内部碎片

3. 动态分区分配
   动态分区分配又称为可变分区分配。在进程装入内存时，根据进程大小动态建立分区。动态分区分配会造成外部碎片。
   动态分区分配策略：

   • 首次适应算法（First Fit）
   • 最佳适应（Best Fit）
   • 最坏适应（Worst Fit）
   • 邻近适应（Next Fit）

非连续分配管理方式

1
2
3

非连续分配指一个程序分散地装入到不相邻的内存分区中。
按照分区分配是否固定分为分页存储管理和分段存储管理。
分页存储管理中又依据运行程序时是否把全部页面都装入内存才运行分为基本分页存储管理和请求分页存储管理。

1. 基本分页存储管理方式
   将主存空间划分为大小相等的块，进程执行时，以块为单位申请块空间。
   分页管理不会产生外部碎片，每个进程平均产生半个块大小的内部碎片（页内碎片）

   1. 分页存储的基本概念
      • 页面：进程中的块称为页，内存中的块称为页框，在外存的称为块
      • 地址结构：
        |31 … 12|11 … 0|
        |—-|—-|
        |页号P|页内偏移量W|
      • 页表：页表在内存中，用于建立进程页号到内存中物理块号的地址映射
   2. 基本地址变换机构： 将逻辑地址转换为物理地址
   3. 具有块表的地址变换机构
      
   4. 二级页表

2. 基本分段存储管理方式

   1. 分段
   2. 段表
   3. 地址变换机构
      
   4. 段的共享与保护
3. 段页式管理方式
   

虚拟内存管理

虚拟内存管理的基本概念

1. 传统存储管理方式特征
   • 一次性：作业要一次全部装入内存后才能运行
   • 驻留性：作业装入内存后，一直驻留在内存中
2. 局部性原理
   • 时间局部性：
   • 空间局部性：
3. 虚拟存储器定义和特征
   虚拟存储器指具有请求调入功能和置换功能，能从逻辑上对内存容量就那些扩展的一种存储系统。
   主要特征：
   • 多次性：允许作业分多次调入内存运行
   • 对换性：允许作业进行换入和换出
   • 虚拟性：逻辑容量=内存容量+外存容量
4. 虚拟存储技术的实现
   实现方式：
   • 请求分页存储管理
   • 请求分段存储管理
   • 请求段页式存储管理
     硬件支持：
   • 内存和外存
   • 中断机构
   • 地址变换机构
   • 页(段)表机制

请求分页管理方式

1. 页表机制
   页表项:
   • 页号
   • 物理块号
   • 状态位P：标记该页是否已调入内存
   • 访问字段A：记录本页的访问次数
   • 修改位M：标志该页调入内存后是否被修改
   • 外存地址： 该页的外存地址
2. 缺页中断机构
   • 在指令执行期间发生，属于内部中断
   • 一条指令执行期间可能发生多次缺页中断
3. 地址变换机构
   地址变换时先检索快表：
   • 如果在块表中找到对应页，修改页表项的访问位，利用页表项的物理块号和页内地址形成物理地址。
   • 如果找不到，则检索内存中的页表，找到对应页号，查看页表项中的状态位P，若该页未调入内存，则产生缺页中断，请求从外存中把该页调入内存。

页面置换算法

进程运行时，若其访问的页面不在内存中，且内存已经没有足够空间，则要从内存中换出页面，选择调出页面的算法称为页面置换算法。

1. 最佳置换算法(OPT):调出最长时间内不再使用的页面
2. 先进先出页面置换算法(FIFO)：调出最早调入的页面会产生Belady异常(分配物理块数增大而缺页次数反而增加)
3. 最近最久未使用置换算法(LRU)：
4. 时钟置换算法(CLOCK)或最近未用算法(NRU)：调入的页面使用位初始值设为1并形成一个循环，指针指向第一个页面。每次调换时从指针处开始扫描循环，若使用位为1则置为0，指针后移；若使用位为0，则置换该页面，指针后移。

页面分配策略

1. 置换策略
   固定/可变分配：考虑进程分配的物理块是否是固定的
   局部/全局置换：考虑是只在进程内部置换还是可以使用其他物理块
   组合策略有：
   • 固定分配局部置换
   • 可变分配全局置换
   • 可变分配局部置换
   • 因为固定分配限制进程的可用物理块所有没有固定分配全局置换
2. 调入页面时机
   • 预调页策略：运行前调页，由程序员指定调页策略
   • 请求调页策略：运行期间调页
3. 从何处调入页面
   文件区存放文件，采用离散分配；对换区存放对换页面，采用连续分配
   • 从对换区调入
   • 从文件区调入

抖动

抖动是指频繁的页面调度行为

工作集

工作集(驻留集)指某段时间间隔内，进程要访问的页面集合，合理选择工作集大小可以防止抖动现象

地址翻译

死锁的概念

1. 死锁的定义
   多个进程因为竞争资源和造成的一种相互等待的现象
2. 死锁产生原因
   • 系统资源竞争
   • 进程推进顺序非法
3. 死锁产生的必要条件
   • 互斥条件
   • 不剥夺条件
   • 请求和饱和条件
   • 循环等待条件

死锁的处理策略

1. 预防死锁：破坏死锁产生的四个必要条件中的一个或多个
2. 避免死锁：防止系统进入不安全状态
3. 死锁检测和解除：不采取限制，检测到再解除

死锁避免

1. 系统安全状态
   系统按照某种进程推进顺序（P1,P2,…,Pn),为每个进程Pi分配其所需资源，直到满足每个进程的最大资源需求，使每个进程都可以顺利完成，此时称P1,P2,…,Pn为安全序列，如果系统无法找到一个安全序列，则称系统处于不安全状态。
2. 银行家算法
   银行家算法是最著名的死锁避免算法。
   1. 数据结构描述
      • 可利用资源矢量Available：Available[i]=K表示系统现有Ri类资源K个
      • 最大需求矩阵Max：Max[i,j]=K，表示进程i需要Rj类资源的最大数目为K
      • 分配矩阵Allocation：Allocation[i,j]=K ,表示进程i已经分配到了Rj类资源数目为K
      • 需求矩阵Need：Need[i,j]=K，表示进程i还需要Rj类资源数目为K
   2. 算法描述
   3. 安全性算法

死锁检测和解除

1. 资源分配图
   请求边，分配边

2. 死锁定理
   S为死锁的条件是当且仅当S状态的资源分配图是不可完全化简的。
   资源分配图化简：

3. 死锁解除

   • 资源剥夺法
   • 撤销进程法
   • 进程回退法

生产者消费者问题

1. 问题描述
   生产者进程和消费者进程共享一个缓冲区，只有缓冲区未满时，生产者进程才可以吧消息放入缓冲区，只有当缓冲区非空时，消费者进程才可以从中取消息，缓冲区为临界资源
2. 思路
   解决互斥和同步PV操作问题
3. 代码

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   semaphore mutex=1; semaphore full=0; semaphore empty=n; producer(){ while（1）{ 生产数据； P(empty); P(mutex); 数据放入缓冲区； V（mutex）； V(full); } } comsumer(){ while（1）{ P(full); P(mutex); 从缓冲区中取出数据； V(mutex); V(empty); 消费数据； } }

读者-写者问题

1. 问题描述
   有读者进程和写者进程，关系如下：
   • 多个读者可同时对文件进行读操作
   • 只允许一个写者往文件写数据
   • 写者完成工作之前，不允许其他读者或写者操作
   • 写者执行操作之间，应让已有读者和写者全部退出
2. 思路
   写者和写者、读者都互斥；读者与写者互斥，读者间同步
   利用count记录读者数目，mutex用于count的互斥访问，rx用于读写者的互斥访问
3. 代码

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

   int count =0; semaphore mutex=1; semaphore re=1; writer(){ while(1){ P(rw); 写入数据； V(rw)； } } reader(){ while(1){ P(mutex); if(count == 0) P(rw); count++; V(mutex); 读； P(mutex); count--; if(count == 0) V(rw); V(mutex); } }

哲学家进餐问题

1. 问题描述
   一张圆桌上坐在五个哲学家，每个哲学家左右两边各有一只筷子，哲学家一次只能拿一只筷子，拿到两只筷子才可以进餐，否则等待，进餐后放下筷子，继续思考。

2. 思路
   定义互斥型号量数组chopstick[5]={1,1,1,1,1},用于对筷子的互斥访问,哲学家编号0—4，哲学家i左边的筷子为编号i；右边的筷子为编号（i+1）%5;mutex表示对筷子的互信号量

3. 代码

   1 2 3 4 5 6 7 8 9 10 11 12 13

   semaphore chopstick[5]={1,1,1,1,1} Pi(){ do{ p(mutex); P(chopstick[i]); P(chopstick[(i+1)%5]); V(mutex); eat; V(chopstick[i]); V(chopstick[(i+1)%5]); think; }while(1); }

吸烟者问题