物理和数据链路
# 计算机网络概述
# 基本概念
三大基本概念:协议、端口和服务
- 协议:水平的,由语法、语义和同步组成,是建立一层网络结构的规则
- 端口:SAP
- 服务:竖直的,层次间通过原语交互(请求、指示、响应、证实),分为面向连接的、可靠的、有应答的三类服务
数据传输 → 资源共享 → 透明网络
网络组成:三种不同角度
- 软硬件、数据
- 通信子网、资源子网
- 核心部分、边缘部分
网络功能:数据传输、资源共享、分布式处理、负载均衡、提高单机可靠性
网络分类
- 范围:广域网、城域网、局域网、个人区域网
- 拓扑:总线、星形、环形、网状
- 使用者:公有、个人
- 传输技术:广播、点播
- 交换技术:报文、电路、分组
- 介质:有线、无线
网络指标:带宽、速率、时延、吞吐、时延带宽积、信道利用率等等
# 参考模型
OSI 参考模型
网络接口层
- 物理层:电气特性、功能特性、机械特性、过程特性
- 数据链路层:成帧、差错控制、流量控制、传输管理
网络层(网际层,IP 层):路由选择、流量控制、拥塞控制、差错控制、网际互联
传输层(TCP 层):流量控制、差错控制、数据传输管理
应用层
- 会话层:建立、管理、同步、终止进程间的会话
- 表示层:编码解码、压缩
- 应用层:界面面向用户,最复杂
层层向下步步封装
对于下一层网络
即数据每向下传递一层,都要封装一个协议控制信息(PCI),同时当前层的协议数据单元(PDU)在一层作为其服务数据单元(SDU)
# 物理层协议
需要明确的是,在计算机网络中,所有的信息都要通过物理层来传播,两台主机就像两栋独立的楼,无论你住在哪一层,要给另一栋楼递东西,都要经过下楼再上楼的过程,并且在计算机网络的楼中,只有同层次的住户才可以识别并接受各自的信息
# 奈奎斯特与香农定理
信源、信道和信宿
波特(Baud):指单位时间内信号变化次数(单位 Hz),在某些具体题目中,波特常常等同于采样频率和带宽
一个信号可能需要用多个比特来表示,如有三个信号 a、b、c,则需要用 0/1 串进行编码,如 01 表示 a,10 表示 b,11 表示 c
很容易可以发现,n 个长度 0/1 串可以表示 2^n 种信号,设信号种类为 V,于是所需比特长度 n 为
波特率:即单位时间内传输波特的个数
比特率:即单位时间内传输比特的个数
在上面已经提到关于波特和比特的联系,即用比特流表示波特,满足数量关系 V = 2^n,自然比特率 R 和波特率 B 继承这样的关系,即
奈奎斯特定理
信噪比
香农定理
# 编码与调制
数字信号和模拟信号:也叫数字数据和模拟数据,数字信号为离散的数据,入方波,模拟信号为连续的信息,如 sin 函数
在物理信道上,分为数字信道和模拟信道,字面意思,数字信道传输数字信号,模拟信道传输模拟信号,将初始信号,转化为模拟信号的过程称作调制,转化为数字信号的过程称为编码
| 编码方法 | |
|---|---|
| 归零法 | 高电平表示 1,低电平表示 0,在时钟转换之前归零 |
| 非归零法 | 高电平表示 1,低电平表示 0,不归零,额外用一根时钟线来同步时钟 |
| 反向归零法 | 根据前后时钟的电平变化表示 0/1,前后电平不变,当前为 1,前后电平改变,当前为 0 |
| 曼彻斯特法 | 将每个时钟分为前后两段,从高电平变为低电平为 1,从低电平变为高电平为 0 |
| 差分曼彻斯特法 | 在将时钟分为两段的同时,根据前后电平变化表示 0/1,若上一个时钟的后半段和当前时钟的前半段相同,则表示为 1,否则表示 0 |
注意在反向归零法和差分曼彻斯特法中,对于第一个时钟信号,由于没有前驱,所以仅通过第一个时钟信号(曼彻斯特为第一个时钟的前半段)的电平判断 0/1,若为高电平则为 1,否则为 0
另外,以太网(网络层)的信号就是用的曼彻斯特编码,在这种编码下,两个电平变化才能表示一个 0/1 信息,即
其比特率等于其波特率的二分之一
| 调制方法 | |
|---|---|
| ASK | 用不同振幅表示 0/1,如有振幅为 1,无振幅为 0 |
| FSK | 用不同频率表示 0/1,如波越密集表示 1,越稀疏表示 0 |
| PSK | 用不同相位来表示 0/1 |
| QAM | 正交振幅调制 |
对于正交振幅调制,设振幅 m 种,相位 n 种,其比特率 R 和波特率 B 满足
编码脉冲调制(PCM):采样 - 量化 - 编码,将模拟数据编码为数字信号(方波),其中采样频率必须大于带宽的两倍才能采集完整(奈奎斯特定理)
频分服用调制(FDM):将模拟数据调制为模拟信号
基带传输、频带传输和宽带传输
| 基带传输 | 频带传输 | 宽带传输 |
|---|---|---|
| 传输数字信号,一般用于局域网 | 传输模拟信号,一般用于长距离传输 | 多路频带传输 |
# 交换技术
| 交换技术 | |
|---|---|
| 电路交换 | 电路直连,参考通电话 |
| 报文交换 | 一大段一大段发,再一大段一大段接收 |
| 分组交换(网络层) | 分为数据报交换和虚电路交换,采用流水线工作方式,直接提升了报文交换的的传输速率 |
复习一下:网络层的数据单位为分组,链路层为帧,物理层为比特,传输层为报文
数据报分组交换(UDP):邮件发送,不同分组通过不同结点任一通路传输,不保证有序性(不可靠)
虚电路分组交换(TCP):语音通话、语音信息,通过虚电路标识符(VCID)在网络中同一路径传输,可靠的(保证分组有序到达),面向连接的
都说了虚电路其实就是一个 TCP 连接,自然需要经过建立连接(三次握手)、数据传输和连接释放(四次挥手)三步骤
# 传输介质
| 传输介质 | |
|---|---|
| 双绞线 | 两根独立的绞合铜线,外加包皮,传递电信号 |
| 同轴电缆 | 内导体(铜制)加多层包皮,传递电信号 |
| 光纤 | 分为单模光纤和多模光纤,传递光波信号 |
| 无线介质 | 有无线电波(移动热点)、 微波、红外线和激光 |
传输速率:光纤 > 同轴电缆 > 双绞线
这和传播物理介质息息相关,显然光的传播速度大于电,而对于同样用电传播的双绞线和同轴电缆,后者的铜芯更大,于是速度更快
传输距离:光纤 > 同轴电缆 ≈ 双绞线
光更适合远距离传播(主要原因是传播过程中抗干扰能力远大于电,不需要额外维护),用光纤做远距离传播介质更加实惠经济,用电传播的双绞线和同轴电缆在进行远距离传播时,需要借用物理层设备如放大器或中继器用以恢复信号特征
传输介质,又被称作计算机网络的第 0 层,他和物理层的主要区别就是,物理层能够通过规定电气特性的功能识别信号中的有效信息,即 0 和 1,从单纯的波信号升级为所谓的比特流
# 物理层设备
| 物理层设备 | |
|---|---|
| 放大器、转发器 | 用以放大模拟信号 |
| 中继器 | 用以重整数字信号并转发,不能无限中继,必须满足 5-4-3 原则) |
| 集线器(Hub) | 具有多个端口的中继器集合 |
注意所有物理层设备都只认物理端口,即插拔的那个现实端口,通过不同端口进行转发,同时无法进行任何形式上的路由选择,只死认端口
物理层接口的特性:电气特性;机械特性;功能特性;过程特性
电气:特指电压、电流大小范围
机械:指摸得着的特征,如有几个引脚,几个插口
功能:指电压对应的逻辑信息,如 10-15V 对应信号 1
过程:指传输过程中的时序,各种事件的出现顺序
# 数据链路层
链路是一条逻辑信道,建立在物理信道之上,并不是物理存在的通路,网络层和更上层的连接也一样,所谓主机到主机的连接或者是端口到端口的连接,都是一种逻辑连接,在物理层之上通过各种协议封装而成,最终数据都是以比特流的形式通过物理信道传输,这是要明确的
# 链路层概述
为网络层提供服务:其基本功能就是把网络层的数据(分组)从源机器传输到目的机器的网络层
链路管理:链路层可以提供面向连接的可靠的服务,在这样的服务中链路管理是必须的
界定帧、帧同步和透明传输:通过封装比特流的头部和尾部将一个个帧分隔;接收方要给予某种反馈来实现帧传输的同步
流量控制:针对发送方的控制,防止发的太多导致接收方带宽不够接收出错
差错控制:出错了怎么办,ARQ 法,采用 CRC 冗余校验和 ARQ 自动重传请求,确认帧是否被正确接收,并保证每个帧最终都能有且只能有一次正确的接收
# 组帧及帧的界定
帧需要实现帧界定、透明传输、可靠传输等功能
帧的界定:帧需要首尾来界定,因为这是封装的第一层,封装的对象是比特流,需要首尾共同截取一段比特流来组成帧
| 界定帧的方法 | |
|---|---|
| 字符计数法 | 在首部用一个计数段来表示当前帧的长度,如 21354322 则表示三个帧 21、354、322,显然若计数段出错数据将发生毁灭性的错误 |
| 首尾字符串定界法 | 采用固定的字符 SOH / ETO 表示帧的开始和结束,同时用转义字符 ESC 来表示数据段中的 SOH 和 ETO 串 |
| 首尾比特串定界法 | 用 01111110 表示首尾,数据段每碰到五个连续的 1,追加一个 0,接收方再去掉数据段每五个连续的 1 之后的 0 得到源数据 |
| 违规编码法 | 适用于曼彻斯特编码,因为在这种编码中,每一个码元,高电平到低电平表 1,低电平到高电平表 0,高到高和低到低不存在(违规),于是很巧妙地用这种违规的码元来界定帧地开始和结束 |
举个栗子
信息段对界定方法的处理方式即为透明传输(信息段除了是一串二进制数之外没有任何含义,需要向上拆封识别)
# 差错控制
比特差错控制:奇偶校验码、循环冗余码、海明码
差错(比特差错):在比特流传输过程中,1 变为 0,0 变为 1,这样的错误叫做比特差错
利用编码技术进行差错控制,编码分为两类
- 检错编码,自动重传请求 ARQ
- 纠错编码,前向纠错 FEC
# 奇偶校验码
校验的是帧中 1 的个数,只能检验出奇数个比特差错,当差错个数为偶数个时,无法检测
奇校验指通过补一位比特使得帧中 1 个数为奇数,若接收帧中 1 个数为偶,说明出错;偶校验即补一位使帧中 1 个数为偶,若接收帧 1 个数为奇,则出错
# 循环冗余码
模 2 除法:最高位对齐(均为 1),余下位若相同,则余 0,若不同则余 1
除数:即为发送方和接收方所商定的多项式,多项式和数的转化如下(就是系数是否存在的 0/1 串)
若除数共 n 位,则余数一定是 n-1 位,于是在原帧后补上 n-1 位作为校验码,初始化位 0
被除数(帧比特本身)除以除数(多项式)所得的余数,即为 n-1 位的校验码,一定注意要高位的 0 不能略去
当接收方接收的帧的校验码不能被多项式整除时,说明数据出现差错,这样的校验能够检验小于等于 n-1 位的比特差错
# 海明码
又叫汉明码
设原始帧比特长度为 n,海明校验码长度为 k,其长度关系一定满足
举一个 1010 的海明码编码过程原理示例
# 流量控制与可靠传输
# 流量控制 - 滑动窗口
在链路层,流量控制和可靠传输是交叉实现的,流量控制使用滑动窗口实现,可靠传输通过自动重传请求实现
其中,滑动窗口根据发送/接收方窗口大小分为
- 停止 - 等待协议
- GBN 协议
- 选择重传协议
自动重传请求中,常常分别有 GBN 自动重传请求和选择重选,这建立在连续 ARQ 滑动窗口流量控制的基础上(所以说是交叉实现的)
| 流量控制 | |
|---|---|
| 停止 - 等待协议 | 发送窗口 1,接收窗口 1 |
| Go Back N 协议 | 发送窗口 n,接收窗口 1 |
| 选择重传协议(SR) | 发送窗口 n,接收窗口 n |
这里的窗口中的帧(窗口大小的单位为帧的个数)都是需要编号的,以保证发送帧的有序性和排错,所以需要 n 位比特位来对窗口进行编号
n 位比特位,对于 GBN,可以对发送窗口中最多 k1 个帧进行编号,还剩一个需要对接收窗口(1 个)进行编号,其中
对于 SR,可以对发送窗口中最多 k2 个帧进行编号,其中
因为发送窗口不能大于接收窗口,所以发送窗口最大是平分,另外,接收窗口大于发送窗口将没有意义,所以,接收窗口最大也是评分,均为全体编号数的 1/2
信道效率的求解,L 为帧长,C 为传输速率,T 为一个发送周期
T 由这几个部分组成:发送时间 - 传输时间 - 确认帧发送时间 - 传输时间
- 其中发送时间和带宽有关
- 传输时间和信道的传输速率有关
有时确认帧的发送时间可省略(确认帧很短,如停止等待协议只有一个比特),但两个传输时间是必须的
几个栗子:请重复做,答案为 C、B、D
# 可靠传输 - 自动重传
建立在 GBN 和 SR 的基础上
对于 GBN 协议,当接收方收到错误的帧时,将不会给发送方发送确认帧,发送方在该帧超时后,自动从该帧开始重发包括该帧之后的所有帧,以保证帧传输的有序性
很多时候,GBN 并不会一个一个返回确认帧(浪费),可能传输了 0,1,2,3,4 四个帧之后,接收方返回一个确认帧,假设确认的是 3,则说明 3(包括 3)之前的帧都已经被正确接收
对于 SR 协议,由于接收窗口大小为 n,其并不保证帧的有序到达,所有在返回处理发送错误的帧时,只会对没有确认的帧进行重发,而不会管已经确认过的帧
# 介质访问控制
就是如何在一条物理信道上划分不同独立的逻辑信道的方式方法
# 信道划分介质
逻辑划分物理信道
| 信道划分 | |
|---|---|
| FDM 频分多路复用 | 不同频率上传输不同信号,如收音机 |
| TDM 时分多路复用 | 时间片轮转算法 |
| WDM 波分多路复用 | 将光波通过合波器整合传输再通过分波器分开读取,每中频率的光波代表一条信道 |
| CDM 码分多路复用 | 通过正交编码向量区分不同信道的信号,CDMA 码分多址 |
时分复用 TDM 又分为
- 同步时分多路复用
- 异步时分多路复用(又叫统计时分多路复用 STDM),其时间片分配是动态的
频分复用 FDM 不能传输数字信号,所以在实际应用中 TDM 更广泛
波分多路复用用于光纤信道
CDMA(码分多址,码分复用)
每个站点占据一个唯一的码片,假设站点 A 码片为 1101,则 C 接收的 A 信号中,1101 表示 1,码片反码 0010 表示 0
- 为了方便计算,码片中用 -1 等价于 0
多个站点传输信号时,各位置直接相加,如有
| 站点 | 码片 |
|---|---|
| A | 1 1 -1 1 |
| B | 1 1 1 -1 |
码分多址中要求各站点码片正交
当 C 受到 A、B 的复合信号 T = 0 0 -2 2,如何区分各站点的信号?做规格化内积(向量内积除以向量维度)
所以识别出 A 传输的信号为 1,B 传输的为 0
# 随机访问介质 - 争用式
不划分信道,所有信号通通传输,但需要避让和优先级判断,传输失败的信号自动重传,争用式的使用信道
涉及的协议:ALOHA ——> 时隙 ALOHA ——> CSMA ——> CSMA-CD / CSMA-CA
- 从 ALOHA 到 CSMA 协议,加入了侦听
- 从 CSMA 到 CSMA-CD 加入了碰撞检测,即在传输的同时检测碰撞是否发生
- 从 CSMA 到 CSMA-CA 加入了碰撞避免,要求一个帧在传输过程中就要受到确认帧,否则认为发生碰撞,终止传输(最小帧)
注意,争用式的使用都无法完全避免冲突,即均有可能发生冲突
在 ALOHA 协议中,一旦传输错误,则立即重发帧,无需等待,加入时隙后,只在每个时隙的开始进行重发,能够避免一些冲突
CSMA 的三种类型
- 1-坚持:很执着,忙则一直侦听,空闲则立即发
- 非坚持:很随意,忙则随机停一段时间,再侦听
- p-坚持:比较随意,忙则持续侦听(根据时隙),空闲则有 p 的概率发送帧
CSMA-CD:先听后发,边听边发,冲突停发,随机重发
CSMA-CA:冲突避免,信道预约
二进制指数退避算法,设重发次数为 k,基本退避时间为争用期 2τ,则选取
等待时间 t 则为
需要注意的是,我们认为,距离重传的时间越长,越不容易再次发生冲突
CSMA-CA / CSMA-CD 的最小帧长度 L 为
其中 V 为信道的传输速率,其实就是两个 t2,一来一回两个传输时延,也叫往返时延,但需要严重注意,二者要求最小帧的原因是不同的
- CSMA-CD 为了保证能够在数据发送完毕之前检测到冲突,即在数据发送完前冲突信号要回传到发送点,当帧发送时间大于等于争用期时,无论发送的什么时间点发生冲突,都可以在发送完毕前收到冲突信号
- CSMA-CA 为了保证确认帧及时收到,即在数据发送完毕之前收到确认帧
CAMS-CA 的帧间间隔时间 IFS(InterFrame Space)
- DIFS(最长),数据帧发送前需等待一个 DIFS
- PIFS
- SIFS,确认帧,控制帧发送后需等待一个 SIFS
CSMA-CA 和 CSMA-CD 的异同
- CD 适用有连接局域网,CA 适用无线局域网
- 二者均有确认帧和最小帧长限制
# 轮询访问 - 令牌传输协议
常用于环形局域网,每个站点先拥有令牌,才可以进行帧的传输(此时单站独占所有带宽),且令牌的分配是动态的(这里可以参考动态时间片轮转算法)
也就是说,每个站点获取令牌后并不一定能发送完自己的帧
令牌传输(Token)非常适用于网络负载大的网络,因为令牌传输不存在冲突,而网络负载大造成的冲突可能会令争用式的代价非常之大