Loading... # 计算机网络概论 ## 计算机网络的应用 - 商业应用: `Client-Server`服务模式 - 构建计算机网络的三个主要目标: 1. 数据共享 2. 个人信息共享 3. 电子商务 - 家庭应用: `B:Business, C:Consumer, G:Goverment, P:Peer` - 不采用点到点的通信的原因: 1. 通信设备相距太远 2. 通信链路数为终端数的平方,不实用 - 电路交换: 每次呼叫建立一个专用电路 是专用资源,不是共享的,可以保证性能 需要考虑链路带宽和交换容量 需要呼叫建立过程 - 分组交换: 数据以离散的数据块形式在网络上发送 统计复用——分组内部序列无固定模式 多个用户处于同一分组,共享网络资源 每个分组使用全部的链路带宽,资源按需使用 会出现资源竞争,拥塞——分组排队等待 节点接受整个分组后才转发 - 分组交换细节: 1. 内容: 消息或者报文 2. 分组: 网络上交换数据的基本单位 分组头: 源地址、目标地址 3. 帧: 在链路上传输数据的基本单位 帧头、帧尾: 地址、序号、校验位 4. 发送过程: 1. 发送端: 先将长报文划分为较短的、固定长度的数据段,每个数据段前添加首部构成分组 2. 分组交换网以“分组”作为数据传输单元,以此把各分组发送到接受端 3. 接收端收到分组后剥去首部还原为报文,最后再组合起来 - 分组交换的特点: 优点: 1. 高效: 动态分配带宽,逐段占用通信链路 2. 灵活: 以分组为单位传输、存储和转发,各链路速率可以不同 3. 迅速: 不必先建立连接,直接想其他主机发送分组,充分利用带宽 4. 可靠: 网络协议与路由选择协议提高网络的生存性 缺点: 1. 存储转发时需排队,增加时延 2. 分组增加首部,加大了开销 - 分组交换与电路交换对比: 分组交换更适用于突发数据,且资源共享,无需事先建立连接,但存在拥塞问题,增大延时和丢包率 - 分组交换的时延: 处理时延、排队时延、发送时延、传播时延 - `Entity`实体——表示发送或接收信息的硬件或软件 - `Protocol`协议——通信实体之间的规则和约定 - `Peers`对等体——不同机器上构成相同层的实体——对等体使用协议相互通信 - `Interface`接口:定义下层向上层提供哪些原语操作和服务 - 数据并非在两台机器的第n层之间直接传输,而是每一层将数据和控制信息直接传递给下层,一直至最底层 - 设计问题: 可靠性、检错、纠错、路由、协议分层、寻址、互联、可扩展、资源分配、流量控制、拥塞控制、服务质量、网络安全 - 每层向其上层提供两种服务: 1. 面向连接的服务: 电话模式、呼叫虚电路——信令 2. 无连接的服务: 因特网模式——无呼叫建立过程、不维护端对端的连接状态 - 服务原语——一个服务由一组原语说明,用户进程通过原语访问该服务.原语告诉服务要执行某个动作. - 服务是一层向其上层提供的一组原语(操作),服务定义了该层准备代表用户执行哪些操作,但并不包括如何实现 协议是一组规则,规定了对等实体之间所交换的报文格式和含义 服务和协议是完全独立的 - 网络体系结构模型: 应用层——提供网络应用、传输层——进程之间的数据传输、网络层——源到目的之间的数据报路由、链路层——临近网络部件间的数据传送、物理层——在线路上传输的位 - `OSI(Open Systems Interconnection)`模型的概念 1. 服务: 每一层向上层提供某些服务 2. 接口: 告诉上层如何访问本层,规定了参数以及结果,没有说明本层是如何工作的 3. 协议: 协议是内部的事情,可以使用或改变任意协议,只要能完成既定的任务,不影响上面的各层 - 网络标准化: 1. 电信领域: 国际电信联盟`ITU`有三个部门 `-T`电话电报数据接口 `-R`无线电通信分配无线频率 `-D`发展部门 2. 著名的国际标准化组织: 国际标准化组织`ISO(International Organization for Standardization)`,电器和电子工程师协议`IEEE` 3. 因特网标准: `IEEE`, `RFC(Request For Coments)` - 互联网标准: `802.3`——以太网、`802.11`——无线局域网、`802.15`——蓝牙&Zigbee、`802.16`宽带无线 ## 物理层 - 物理层: 定义了为建立、维护和拆除物理链路所需的机械、电气、功能和规程等特性,其作业是使比特流能在物理介质上传输. - 提供以下服务: 1. 提供传送和接收比特流的能力,物理连接的建立、维持和释放 2. 在两个相邻系统之间唯一地标识数据电路 ### 数据传输理论: 信道传输等限制 - 通信系统的一般模型 ![5cd5391c97dcd.jpg][1] 数据(`data`)——携带信息(即比特)的实体; 信号(`signal`)——信号是表示消息的物理量,随时间变化 - 通信系统的主要参数 1. 信号功率`S`,单位为瓦特(焦耳每秒`W`) 2. 信号带宽`B`,单位为赫兹(`Hz`): 与收发设备及传输介质的特性有关 3. 噪声功率`N`: 通信线路上的平均噪声功率 4. `SNR`: `S/N`是信噪比,单位为分贝(`dB`), $SNR_{dB}=10\log_{10}(S/N)$ 5. 数据率,单位为`bps`: 数据传输速率 6. 误码率: 数据传输错误的概率,衡量数据传输的质量,单位为 $1\times10^{-n}$ - 信号分析方法——傅立叶变换: 任一个周期为T的函数`g(t)`,可以用傅立叶级数来表示 $g(t)=\frac{c}{2}+\sum_{n=1}^\infty a_n\sin(2\pi nft)+\sum_{n=1}^\infty b_n\cos(2\pi nft)$, $\int_0^T\sin(2\pi kft)\cos(2\pi nft)=\delta_{k,n}\frac{T}{2}$ $a_n=\frac{2}{T}\int_0^Tg(t)\sin(2\pi nft)dt, b_n=\frac{2}{T}\int_0^Tg(t)\cos(2\pi nft)dt,c=\frac{2}{T}\int_0^Tg(t)dt$ - 信号带宽受限: 各频率分量的幅度$\sqrt{a_n^2+b_n^2}$表示信号传输的能量 - 传输带宽会影响数据率,正相关, 传输带宽与通信设备、传输介质有关 - 传输带宽: 传输中幅度衰减不明显的频率范围;定义为接收功率由最大将为1/2(3dB)的频率范围 - 奈奎斯特定理: 在理想无噪声的信道条件下最大数据率$=2B\log_2V$,其中B为信道带宽,V为信号中的状态数 - 香农容量公式: 信道极限信息传输速率或无误码容量C遵从公式: $C=B\log_2(1+S/N)\ b/s$ ### 传输介质: 常用传输介质的特性 - 双绞线:(STP)屏蔽双绞线, (UTP)无屏蔽双绞线, 传输距离为100米, 可传数字信号和模拟信号 | Type(Category) | 1 | 2 | 3 | 4 | 5 | 5e | 6 | 7 | | :- | :- | :- | :- | :- | :- | :- | :- | :- | | Use | Voice Only | Data to 4Mbps | 10Mbps | 20Mbps | 100Mbps | 100Mbps | 250MHz | 600MHz | | Where | Telephone Wire | Local Talk | Ethernet | 16Mbps Token Ring | Fast Ethernet | Fast Ethernet | Gigabit Ethernet | | - 同轴电缆: 1. 系带同轴电缆:阻抗匹配$50\Omega$,用于数字信号传输 1. 粗缆10Base-5,单段最长500米,最长5段2.5公里 2. 细缆10Base-2,单段最长185米,最长5段925米 2. 宽带同轴电缆:阻抗匹配$75\Omega$,用于电视信号传播 - 光缆: 由传导光波的高纯石英玻璃纤维和保护层构成,全反射原理,多根光纤封装在坚固的外壳中构成多芯光纤 - 光发射系统: 1. 光源: LED(发光二极管),ILD(注入型激光二极管),光信号的有无表示1和0 2. 检测器: 接收端由光电二极管构成的光检测器将光信号转换成电信号 - 光纤的连接: 机械式0.1dB快速无需特殊设备, 熔结,极低损耗0.05dB,昂贵的特殊设备,长距离链路唯一方法 - 无线传输: 中频0.3-3M、高频3-30M、甚高频30-300M、超高频0.3-3G 用于移动通信, 特高频3-30GHz用于数字通信 - 微波,利用抛物面天线聚集能量可沿直线实现视距传输(LOS),具有很高的信噪比 可以利用地面传播,地波传播——2MHz以下平行地表传播,天波传播——2-30MHz在地面与大气层之间来回反射 ### 数字调制技术: 比特与信号间的转换技术及常见通信系统 #### 基带传输 - 带宽效率——与一个符号承载的比特数有关: 1. 符号电平数多,则承载比特也多, 如8电平的符号可以表示3比特 2. 符号率: 信号改变的频率,单位为波特率,若带宽为B,则符号率为2B - 非归零码NRZ(Non-Return-Zero): 0为高电平,1为低电平 - 时钟恢复: 根据跳变来恢复时钟,可能因长时间发送0或1导致信号电平无跳变,导致收发之间难以同步 - 信号平衡(基线漂移):用接受信号的平均值确定信号电平的高低,连1或连0会改变信号均值 - 对于NRZ,若带宽为B,则数据率为2B - 非归零反转码NRZI(NRZ Inverted):是一种差分编码 - 信号跳变表示1, 无跳变表示0 - 解决了连1问题,未解决连0 - 弱带宽为B,则数据率为2B - 曼彻斯特编码(Manchester Encoding) - 发送0时,电平从高到低跳变, 发送1时,电平从低到高跳变 - 每比特时间必有一次电平跳变,接受方通过检测该跳变实现与发送方的位同步 - 带宽为B,则数据率为2B - 差分曼彻斯特编码 - 在每位信号起始处,没有跳变表示1,有跳变表示0, - 每比特时间仍有一个跳变用来同步 - 需要更复杂的设备,有更好的抗干扰性 - 4B5B编码 - 4比特数据用5比特编码,保证码组前部最多1个0,尾部最多2个0,即码流中连0不超过3个 - 对码组再用NRZI编码,每5比特至少有2个1,即有两次跳变 - 4B5B的编码效率为80%, 用于100Mb/s以太网和光纤分布式数据接口FDDI #### 通带传输 - 由于基带信号在信道上长距离传输会受到衰减、畸变和噪声影响,低频信号不适合远距离传输, 各个传输介质有其适于的信号频率范围, 需要将数字信号转换成一种适合于在信道上传输的信号,称转换过程为调制(modulation);相应的,从信号中提取数字信号的过程称为解调(demodulation) - 调制解调器(MODEM)就是调制器(MOdulator)和解调器(DEModulator)的组合 - 数字调制技术: - 用$A\sin(2nft+\Phi)$表示正弦信号,使A,f或$\Phi$随基带信号而变化,称为对载波进行调制 - 基本调制方法: 调幅(AM), 调频(FM), 调相(PM) - 调幅: 在幅度调制中,两个不同载波信号的幅值分别代表0和1,有时也用恒定幅度的载波的有和无代表1和0 - 调频: 频率调制是用两个不同频率的载波分别代表0和1, 抗干扰能力优于调幅,但频带利用率不高,常用于传输低速数字信号 - 调相: 相位调制是用不同相位的载波分别表示0和1, BPSK - 调制: QPSK正交相移键控:用信号的45度135度225度315度表示2比特 - 联合信号的幅度和相位,使一个符号表示更多比特,黑点表示合法的幅度和相位 - QAM正交振幅调制 QAM-16,振幅相位16种组合,可表示4比特 ![5cd5391ca0665.jpg][2] - 调制星座图: 数字通信中,将数字信号表示在复平面上,给出信号及信号之间的关系的图示就是星座图 ### 信道复用: 在一条传输介质上提供多个数据传输信道的方法 #### 频分复用 FDM(frequency division multiplexing) - 信号在同样时间占用不同频段 - 当信道带宽B为基带调制信号带宽的N倍时,将信道分割为N个子信道,在每个子信道上传输一路基带信号 - 子信道之间有保护间隔 - 基带滤波器 - 用各路基带信号调制不同频率的载波,将各路信号搬移到各个子信道上 - 举例: 广播系统、电话系统、电视系统 #### 时分复用 TDM(time division multiplexing) - 信号在不同时间占用同样的频段 - 所有用户占用同样频段的不同时隙,组成信道传输的帧 - 用户按照“轮”来访问信道,每一轮,每个用户得到固定长度的时隙 - 用户之间需要同步, 需要在时隙之间设置保护间隔,应对同步偏差和远近效应 - 举例: 电话系统骨干网中数据传输,第二代蜂窝无线通信系统,以太网中的数据传输 #### 码分复用 CDM(code division multiplexing) - 从代码集$C_k$中选取特有的“码序列”分配给每个用户,码序列特点是 $$ \frac{1}{m}\sum_{i=1}^mC_{ki}C_{ji}=\delta_{k,j} $$ - 所有用户共享相同频率,但每个用户用其特定码序列对数据进行编码或调制,允许多个用户“共存”并同时传输,具有最小的干扰,因为“码”是正交的 - 编码信号=原始数据x码序列, 解码信号=编码信号x码序列 ![5cd5391ca9ea8.jpg][3] - CDMA(Code Division Multiple Access) 码分多址,是无线广播信道的标准,扩展了频谱,通常码片速率为信息速率的m倍, 编码信号=原始数据x码片序列 - 原始数据经CDMA编码后,信号频谱被展宽,称为扩频,例如原始10Kbps,100倍扩频后码速率为1Mbps - 展宽的信号频谱不易被检测,已知码序列才能解调数据,因此扩频通信具有保密性 #### 各子载波正交 OFDM(Orthogonal frequency division Modulation) - M是调制不是复用, 其方法时:在某一子载波的中心采样,则其他正交子载波的干扰为0 - 用基带数据调制一个正交频率子载波, 子载波之间没有保护间隔,更有效地利用带宽(最大的频谱效率), 要求子载波间严格正交,接收频率严格对准 #### 对比 - FDMA:抑制带外信号,需设置保护频段 - TDMA:各信号严格同步,需设置保护时间间隔 - CDMA:需要功率控制 - OFDM:需要各子载波频率正交,接发频率对齐 #### 单双工 - 单工: 信道只能在一个方向上传输数据 - 双工(duplex): 信号可以在两个方向上同时传输数据 1. TDD(Time Division Duplex)——时分双工 2. FDD(Frequency Division Duplex)——频分双工 3. CDD(Code Division Duplex)——码分双工 #### 脉冲编码调制 PCM(Pulse Code Modulation) - 脉冲编码调制PCM是将模拟信号变换为数字信号的方法,包括采样、量化和解码三个步骤 - 编解码器codec - 采样: 奈奎斯特定理,若模拟信号带宽为WHz,则采样频率为2W时,足以捕获模拟信号的信息 - 量化: 对取样点信号幅值分级取整 - 编码: 将量化后的整数值用二进制表示 #### TDM复用——T1标准 - 长距离链路TDM传输语音和数据混合信号,24个信道总数据率为1.544Mbps, 每个信道8位数据(7语言1信令),数据率位56(7x8)Kbps ![5cd5391cc9eb0.jpg][4] - T1总速率 [(7+1)x24+1]x8k=193bx8k=1.544Mbps E1:2.048Mbps=8x32x8K(32个子信道,30个语音,2个控制信号及帧同步) - PDH(Plesiochronous Digital Hierarchy)准同步数字系列,各路时钟频率有一定偏差,复接时需插入一定脉冲实现同步 - SDH(Synchronous Digitial Hierarchy)同步数字系列, SONET(Synchronous Optical NETwork同步光网络), 系统由一个精度$10^{-9}$的时钟控制,精准同步,易于复接和分接 #### SONET/SDH 速率和复用 - SONET基本信道, $125\mu s$传输810字节(90列x9行),数据率=8bit x 810Byte x 8KHz=51.84Mbps 称为STS-1同步传输信号 - 多路STS-1复用:3路STS-1合成为STS-3.155.52Mbps,STS-n的光纤线路称为OC-n,从 OC-3开始 称作同步传输模块STM-1, #### GSM - 25MHz, FDM将25MHz分为124个信道,每个信道200KHz,再在每个子信道用TDM - 手机发送频率比接收频率高45MHz ## 数据链路层 ### 组帧及检错 #### 数据链路层 - 结点(node):主机及路由器 - 链路(link):连接**相邻**结点之间的通信信道,可分为有线链路、无线链路 - 帧(frame):在数据链路上传输数据的基本单位,用于承载数据 - 数据链路层: 负责在**一个结点与其相邻结点**之间经过一条链路传递数据 - 在每个主机中,链路实现是在适配器,即网卡(NIC)——网卡实现链路层及物理层,与主机的系统总线连接,是软件硬件及固件的结合,可分为以太网卡、PCMCI网卡、802.11网卡 - 适配器之间通信: 发端——将数据封装成帧,增加校验位,接收地址,实施流量控制等; 发端——检查错误,检查接收地址,实施流量控制等,提取数据,交由高层处理 ![5cd5391ceb181.jpg][5] #### 成帧——同步、透明传送 - 同步: 计算机之间的通信需要收发双方协调发送和接收之间的动作 1. 异步传输: 以字符为传输单位,字符之间的时间间隔是可变的,而字符中的位则以固定速率传送. - 起停位、数据为、校验位 - 传输字符之间无固定时间间隔 - 接收时钟与发送时钟存在偏差 - 特点: 简单、廉价、每帧一个字符 2. 同步传输: 发送和接收之间的每位都是同步的,接收端从接受的信号中提取时钟,以保持与发送信号的时钟同步 - 以数据块位传输单位 - 要求时钟同步——提供时钟线给接收端或从接收信号中提取时钟 - 适用于长距离的数据传输,效率高 - 举例: 以太帧——同步码:8个字节,前7 用于帧的位同步,最后1个是帧开始定界符,表示后面的信息是MAC帧 ![5cd5391d02acc.jpg][6] - 帧是链路层的基本单位,用于承载链路层的数据、实施差错控制 - 异步传输中的起始停止位、同步传输中的同步位之后需要确定帧开始. - 成帧方法: 1. 字节计数法: 利用头部的一个字段来标识该帧的字节数 - 问题:若头部字节出错,则会失去同步 - 解决:若能将一个**特殊的字节**作为帧的首尾标志,则帧失步后可以重新同步 2. 封装成帧: 在一段数据的前后分别加首部“SOH”(0x01)和尾部“EOT”(0x04),构成一个帧 - 首部和尾部的作用就是帧定界 - 问题: 若帧数据部分含有帧头或帧尾,则会导致同步出错,遗失信息 - 解决: 1. 字符填充实现透明传输: - 发送端若在数据中出现“SOH”或“EOT”,则在其前面插入一个转义符“ESC”(0x1B). - 接收端将数据送往高层之前删除插入的转义符. - 若转义符也在数据中出现,则在转义符前插入一个转义符,当接收段收到连续两个转义符时就删除一个 ![5cd5391e40b9c.jpg][7] 2. 用比特填充实现透明传输: - HDLC,帧标志位F为01111110,采用零比特填充, - 数据中某一段比特组合恰好和F一样时, - 发送端在连续发送5个连1后,填入一个0比特再发送出去, - 接收端将5个连1之后的0比特删除,恢复原帧 ![5cd5391e5fa9e.jpg][8] #### 差错控制技术:检错及纠错 - 差错: 数字通信系统中接收位与发送位不一致 - 信道误码率: $P_b=$误码位数/发送总位数 - 若误码率为$P_b$,帧长为L位,则无差错帧的概率为$P_1=(1-P_b)^L$ - 差错检测: 在信息位中加入冗余位——编码 - 信息位:要发送的数据 - 冗余位:按某种关系对信息位运算所得到的数据 - 发送过程:信息位+冗余位,构成**码字**,发送码字 - 接受过程: 检查信息位和冗余位之间的关系(校验过程),以发现传输过程是否初心啊差错 - 奇偶校验 - 增加冗余位,使码字中的1的个数为奇数或偶数个,称为奇(或偶)校验 - 一维奇偶校验: 检测单比特错,无法纠错 - 二维奇偶校验: 检测并纠正**单**比特错 - 检错码: 能自动发现差错的编码,如奇偶校验码、循环冗余码CRC(Cyclic Redundancy Code) - 纠错码: 不仅能发现差错而且能定位差错的位置:,如汉明码、卷积码等 - 汉明距离(码距)为两个码字中不相同位的个数 - 编码就是增大码距,解码就是找出距离码字最近的码字 - m位信息+r位校验,在$2^{m+r}$中仅传输$2^m$种码字,码距大于1,码字空间稀疏 - 码距与检错、纠错能力的关系(当d≤4) 1. 若码距d为奇数,则能发现d-1位错,或能纠正(d-1)/2位错. 2. 若码距d为偶数,则能发现d/2位错,并能纠正(d/2-1)位错. - 若要检测d位错,则需要码距为d+1,若要纠正d位错,则需要码距为2d+1 - 码率: 衡量编码效率——若码长为n的码字中含有信息位m位,则码率=m/n - 理论上, m位信息位,r位校验位,则$m+r+1\leq2^r$,给出了纠1位错r的下界 - **纠错码**——汉明码: - 校验位:(p1,p2,p4,p8,p16,...)r位,位于$2^n$,n=0,1,...,r-1 - 信息位:(m3,m5,m6,m7,m9,...)m位 - 第K位信息的校验位来自2的幂次只和,如5=1+4 - 例如(7,4)汉明码,码长7,信息位4,校验位3 - 信息位m3=p1+p2,m5=p1+p4,m6=p2+p4,m7=p1+p2+p4 - 根据校验位的计算结果,可以定位差错的位置——纠1位错 - **检错码**——交织与校验和 - 码字的检错能力有限,如奇偶校验码,汉明码只能纠检1位错 - **突发长度**:在码字中第1位错与最后1位错之间的间隔 - 交织:将信息位组成n列k行,按列计算校验位,按行顺序发送,只要突发长度$\leq$n,则可以检错, - 实现最多只有1位错 - 校验和:对发送数据位计算校验和,接收端实施同样运算以检错,例如IP头、UDP报文 - **检错码**——循环冗余校验CRC - d位数据,组成一个二进制数D, 选择r+1位生成式G,计算r位的CRC位R - 发送端使<D,R>能被G整除(模2),计算端已知G,用<D,R>除以G,若余数为0则保留,否则出错 - 可以检测所有突发长度小于等于r位的错误 - 用于Ethernet,802.11WiFi,ATM - 编码效率高 - G(X)能检出所有1比特错,因为G(X)不含$X^i$因子即含1 - G(X)能检出所有2比特错,因为G(X)不含$X^i$因子且对任何$0< e \leq n-1$的e除不尽$x^{e+1}$ - G(X)能检出所有奇数位错,因为G(X)含因式(X+1) - 能检出所有长度小于等于CRC长度的突发错 - 易于硬件实现——移位、异或 - 举例: CRC-12 $X^12+X^11+X^3+X^2+X+1$ - 差错控制方法: 1. 前向纠错FEC(Forward Error Correction):采用纠错码,接收端发现差错并纠正 - 纠错编码模型——发送端纠错编码送信道传输,接收端接收信号译码,检测到错误自动纠正 ![5cd5391e7084e.jpg][9] - 优点: 无需反向信道、单工即可,也可用于一对多的通信 - 缺点: 译码设备复杂,为纠错需附加冗余码 2. 自动请求重传ARQ(Automatic Repeat reQuest): 接收端检测到错误时,通知发送端重传,直到收到正确的数据 - 模型——发送端将数据发向信道,同时缓存数据.如果接到重发请求,则将放入缓存器的数据重新编码发送,接收端判决,如果接收正确则发送ACK,若检测到错误则发送NACK,要求重发. ![5cd5391e87e8f.jpg][10] - 三种ARQ方式:停发等候重发、返回重发、选择重发 3. 混合纠错HARQ(Hybrid ARQ)检错码+纠错码 - 若发现差错但在纠错范围内,则直接纠错; 当超出纠错能力时,则要求发端重传 4. 对比 FEC不需要重传,实时性好,常用于无线链路 ARQ常用于计算机网络 ![5cd5391e90b57.jpg][11] ### ARQ - 基本的数据链路层协议 - 检错及纠错:在帧头增加控制信息,帧尾增加帧校验 - 定义一系列函数,例如:`wait_for_event(&event); event表示发生的事件` - 发送方:发送帧给另一主机 - 接收方:收到数据后计算帧校验,设置event - 若有错,则event=chksum_err;否则event=frame_arrival - 停等协议: - 发送端发送数据时同时缓存;当收到确认帧后,才清除 - 只有收到确认帧ACK后,才发送新的数据帧 - 接收端受到数据帧后,发送确认; 若时新数据帧,则保存;若为重复帧,则丢弃 - 发送端自动对错帧重传,因此称为自动请求重传ARQ - 信道利用率: - 设数据帧长 $l_f$(bit) ,数据发送速率$R$(bit/s), 则一个数据帧的发送时间$t_f=l_f/R$ ![5cd5391e9d7b6.jpg][12] - 数据帧发送后若经过重传时间还没有收到确认帧,则重传数据帧,设重传时间为 $$ _{out}=t_p+t_{pr}+t_a+t_p+t_{pr} $$ - 一般处理时间$t_{pr}$和确认帧发送时间$t_a$远小于传播时延$t_p$,故忽略他们,得到$t_{out}=2t_p$ - 定义$\alpha=t_p/t_f$,表示传播时间(即延迟)与帧发送时间(为带宽倒数)之比,则信道利用率 $$ =t_f/(t_f+2t_p)=1/(1+2\alpha) $$ - 优点: 简单 缺点: 信道利用率不高,尤其不适于再长时延的信道上采用 - 连续ARQ: - 发送发连续发送多个分组,不必每发完一个分组就停下来等待确认,提高了信道利用率 - 若延迟为$t_p$,带宽为帧率$1/t_f$(单位时间发送的帧数), 则延迟带宽积为$\alpha=t_p/t_f$ - 若可连续发送的帧数为w,则利用率$\leq w/(1+2\alpha)$ - 接收确认帧ACKi表示期望收到的下一个帧的序号是i - 接收端: **按序接收**数据帧 - 发送端: 收到ACKn时取消n-1的计时器, n计时器超时时,重传第n个数据帧 - 又被称为**Go-back-N** ARQ - 滑动窗口: - 发送端和接收端分别设置发送窗口和接收窗口 - 发送窗口WT用来对发送端进行流量控制,表示发送端最多可发送的数据帧数量 - 接收端只接收发送序号落入接收窗口的数据帧 - 连续ARQ中,接收窗口WR=1,收发两端窗口不断向前滑动,协议又称滑动窗口协议 - 若WT=1,则为停止等待协议 - 当帧序号用n个比特编号时,若接收窗口为1,则发送窗口$W_T\leq 2^n-1$ - 选择重传ARQ: - 增大接受窗口WR, 接受序号不连续但仍在接收窗口的数据帧,等收到缺失序号的数据帧后再送交主机 - 避免重传正确到达接收端的数据帧,但需要接收端有缓存 - 若用n比特编号,则接受窗口最大为$W_R\leq2^{n-1}$ - 捎带确认与累计确认: - 累计确认:接收端不是每收到一个数据帧就发送一个确认帧,若确认序号为i,则表示 (i-1)及之前的所有数据帧均被确认,且期望收到的下一个帧的序号为i. - 捎带确认:当接收端向发送端发送确认信息时,如 果同时存在需要发送的数据,那么可以将确认信息和数据合并在一个帧中发送 ## MAC ### 信道分配与多路访问协议 一个共享信道, 两个或更多结点同时发送:干扰,碰撞:如果同时接收到两个或两个以上的结点的发射信号 - 介质访问控制MAC(Medium Access Control): - 决定结点如何共享信道,确定下一个使用信道的结点 - 信道共享的控制必须使用自身的信道 - 与信道复用的区别: MAC:关注多个用户如何使用共享的信道 ,分配算法 信道复用:关注信道如何划分为多个信道,TDM、FDM、CDM、OFDM - 划分信道 - 将总的信道资源分割为更小的信道(时隙,频率,码字) - 为需要使用信道的结点分配信道资源 - 通常需要一个信道分配中心,信道资源集中控制 - 随机接入 - 不分割信道,允许碰撞 - 接收端避免碰撞 #### 划分信道 - 时分多址TDMA(time division multiple access) - 按照“轮”来访问信道, 在每一轮,每个站得到固定长度的时隙(长度=分组发送时间) - 未使用的时隙成为空闲的 - 实现问题:需要时隙同步;设置保护间隔 - 频分多址FDMA(frequency division multiple access) - 将信道划分为频段, 为每个站分配固定的频段 - 不传输信号,则频段为空闲的 - 实现问题:需要带通滤波器,设置频率保护带 - 静态信道分配 - 传统的复用技术(FDM,TDM等),N个用户N个信道,信道数与用户数相同 - 面临的问题:用户数量很多且动态变化,例如当每个用户的数据为突发时 - 将信道划分为N个独立的信道,降低了信道效率 - 信道容量为C ,帧的平均长度为$1/\mu$ b,平均到达率为$\lambda$帧/s, 平均延迟时间为$T=\frac{1}{\lambda-\mu C}$ - 动态信道分配 - 划分信道,增大了平均延迟,降低了信道利用率 - 对于数据突发业务,N的数量动态变化,需要一种动态信道分配技术 1. 随机访问控制: 当结点有分组要发送时,以全信道速率R发送分组,结点之间没有优先级协同 - 两个或两个以上的发送结点——碰撞 1. ALOHA: - 假设: 帧长度相同,发送时间为1; 各个站不需要同步; 一个帧到达时,就立即发送 - 那么在$t_0$时刻发送的帧将与发送时刻位于[$t_0$-1,$t_0$+1] 的帧碰撞 - 效率: 当 N -> 无限,**最大利用率 = 1/(2e) = 0.18** 2. 时隙ALOHA - 假设: 帧长度相同、信道时间划分为相同的时隙(每个时隙发送一个帧)、 结点只有在时隙开始时刻才能发送,以降低碰撞的概率、 结点之间是同步的、 若在一个时隙中有2个以上的结点同时发送,所有结点都可以检测碰撞 - 当结点得到一个新的帧,则在下一个时隙发送 - 若没有碰撞:结点可以在后续时隙发送新的帧 - 若碰撞:结点在后续时隙中以概率p重传该帧,直到成功发送 - 效率(成功发送的时隙比率): 当N趋于无穷时,**最大效率 = 1/e = 0.37** - 优点: - 一个活动的结点可以 以全信道速率连续发 送数据 - 非集中式:只是结点 的时隙需要同步 - 简单 - 缺点: - 碰撞,浪费时隙 - 空闲时隙 - 结点在发送数据之前 不能够检测碰撞 - 时钟需要同步 3. 载波侦听CSMA(Carrier Sense Multiple Access) - 结点在发射信号前测试信道状态,如果信道空闲(即没有检测到载波),则按照以下算法来发送. - 1-坚持CSMA(1-persistent CSMA) 当信道空闲时,以概率1发送 - 非坚持CSMA(non-persistent CSMA) 若信道忙,则等待一随机时间,之后再进行载波侦听 - p坚持CSMA(p-persistent CSMA) 若信道空闲,则以概率P在当前时隙发送,而以概率1-p推迟到下一时隙发送 - 在低负载时,采用1坚持CSMA,吞吐率高于ALOHA的;在高负载时,非坚持更好;非坚持CSMA峰值吞吐率约比1-坚持CSMA高2倍 ![5cd5391ebcb39.jpg][13] - 仍然可能发送碰撞:传播延迟致使两个结点无法听到对方发送的信号 - CSMA/CD (碰撞检测) - 在短时间内做碰撞检测 - 终止有碰撞的发送, 降低信道的浪费 - 易于在LAN中实现:测量信号强度,比较发送、接收信号 - 难于在WLAN中实现:接收信号很小,而发送信号很大 2. 无冲突协议 碰撞降低了带宽、增加了帧的发送时延 通过竞争方式预约信道,而在预约的信道上用无冲突的方式传输数据 - 位图协议(预约协议reservation protocols) - N个站,每个站的地址为0~(N-1),忽略传播延迟 - 每个竞争周期有N个时隙 - 第j号站有帧要发送时,则在时隙 j 发送比特1预约 时隙,不允许其它站在该时隙发送 要求各站在预约时隙的尺度上是同步的 - 经过预约时隙后,每个站都知道哪些站要发送,每个站按顺序发送帧 - 低负载时的信道利用率: 平均等待时间为N个时隙 - 高负载时的信道利用率: 平均延迟:排队时间+N+(N-1)d - 轮询 - 主结点邀请从结点按序发送,典型地用于主从式通信环境 - 问题:轮询的开销、延迟、主结点故障 - 令牌环:控制令牌依次经过各个结点、携载信息 - WLAN中的PCF方式 3. 有限竞争协议 降低竞争的站数,则增加了获得信道的概率 有限竞争协议是适当调整竞争站点数 - 将结点划分为组 - 第0组的成员只允许在第0时隙竞争 - 若某个站竞争成功,则其占用信道并发送帧;若发生碰撞,则第1组的成员继续在第1时隙竞争 ### 以太网与WLAN #### IEEE802.3 以太网:CSMA/CD - 总线型:用同轴电缆连接,或用双绞线通过集线器连接 所有的节点在同一碰撞域,节点之间相互碰撞 - 星型拓扑 交换机:位于中心 每个链路执行以太网协议,节点之间不再相互碰撞 - ![5cd5391ed8c0e.jpg][14] - 8个字节前导码:前7字节是同步码,实现帧的位同步,最后1个字节是帧开始定界符,表示后面的信息是MAC帧 - 地址字段:目的地址首位为0的为普通地址,为1的为组播地址;全1的为广播地址;源地址前3字节为组织标识符,分配给网络制造商 - 类型字段:通知接收方帧内包含的协议类型 - 数据字段:最小长度 (64-18) 字节,不足时,插入填充字段 - 以太网以多点接入方式共享总线资源, CSMA/CD:Carrier Sense Multiple Access with Collision Detection,载波监听多点接入/碰撞检测 - $\tau$为端到端传播时延,发送数据帧后最多经过$2\tau$后,可判决是否发生碰撞;$2\tau$称为争用期 - 发生碰撞后,推迟一个随机时间再发送;退避时间由二进制指数退避算法决定 - 基本退避时间取$2\tau$ - 重传次数为k,每次退避后,K累加k = Min[k+1,10] - 随机选取一个数r, r$\in$[0,1,...,($2^k-1$)] - 重传时延为 r×2$\tau$ - 当重传10次仍不成功,则丢弃该帧并通知上层 - 以太网的争用期为51.2$\mu$s(5120m=2\*10^8 \*51.2*10^-6/2),10Mb/s可发送512b,即64B - 最短有效帧长为64B,长度小于64B的帧为无效帧。因检测到冲突就中止发送,此时的数据长度小于64字节 - 强化碰撞:当发送数据结点一旦检测到碰撞,立即停止发送数据,并要发送若干比特的干扰信号,让所有站都检测到碰撞 - CSMA/CD的信道利用率 - $t_{prop}$ = LAN上两节点的最长传播延迟 - $t_{trans}$ = 最长帧的发送时间 - $efficiency=1/(1+5t_{prop}/t_{trans})$ - 以太网信道利用率 - $T_0$为帧发送时间, 帧长为L(b),数据速率为R(b/s),则帧的发送时间 $T_0$ = L/R (s), 争用期为$2\tau$ - 当N无穷大时, $S\approx\frac{1}{1+4.44a}$,$a=\tau/T_0$ - 10 Mbps,512b争用期时,节点数与利用率的关系——增加帧长,则利用率更高 ![5cd5391ee4750.jpg][15] ####IEEE802.11 WLAN:CSMA/CA - 无线主机与基站之间的通信(基站 = AP) - 有固定基础设施下的基本业务集(BSS:Basic Service Set) - 无线主机 - AP(access point):基站 - ad hoc模式:仅有主机 - 没有基站、节点只能在其信号覆盖范围内将传输数据、节点构成网络——节点实现路由 - 与有线链路的区别: - 信号强度的衰减:无线信号强度与其传播路径有关 (路径损耗) - 各种信号间的干扰:标准的无线网络频段 (如 2.4GHz) 为其它设备共享;设备之间也存在干扰 - 多径传播:无线信号经地面及物体发射,使到达 目的节点的信号有不同的延迟 - 信噪比SNR:更高的SNR–易于从噪声中提取信号 - SNR与BER(Bit Error Rate)的折中 - 对给定的物理层 增加功率=增加SNR=降低BER - 对给定的SNR:为得到更高的吞吐量,选择不同的物理层技术,使之满足BER要求 SNR可以随移动而改变:动态 地调整物理层(调制技术,速率等) - 随着节点与BS距离的增加 ,SNR降低, BER增大 - 当BER太高时, 切换到更低的传输速率,BER随之降低 - 注册: AP周期性地(如每100ms)发送信标(Beacons)广播帧,建立同步,维持连通性或关联: 信标中含有BSS-ID用于指示AP及网络;业务指示(用于sleep mode);功率管理,用于站点的节能 节点: 基于信标测量RSS,与AP建立关联:节点向AP注册,节点发送请求,AP予以响应;只有注册后,节点才能发送接收数据DATA - 802.11b: 信道, 关联 - 信道管理与分配:AP管理所选择的信道;可能的干扰:工作信道可能被其他AP占用! - 主机:必须与AP关联 - 信道分配及注册: 节点周期性地扫描所有信道,对信道的接收信号强度进行估计(CCA Channel) - 关联: 由信道强度决定,选择一个 AP 并注册 - 重关联:与新的AP关联,出现在下述情况下: 节点离开当前AP覆盖区;当信号条件改变时;当有多个用户与当前的AP关联时 - 802.11b: 2.4GHz-2.485GHz,定义了11(13/14) 信道,信 道带宽22MHz,信道间隔5MHz,完全正交的信道是3个,如 1,6,11 - 802.11: 被动扫描与主动扫描 - 被动扫描: AP发送信标帧 - 主动扫描: 客户端以广播方式发送信标帧, AP发送探测响应帧 - 隐蔽终端问题 - 多点访问:碰撞避免: 2个以上的节点同时发送 - 802.11: CSMA – 在发送之前侦听,不与正在发送的节点发生碰撞 - 802.11: 没有碰撞检测 - **因信号衰落的原因,接收信号很弱,难以在发送的同时进行接收以检测碰撞** - **因存在信号衰落以及隐蔽节点,不能检测到碰撞** - 目的:避免碰撞CSMA/CA - 暴露节点 - 802.11 MAC: CSMA/CA - 发端: 若信道空闲DIFS,则发送一个帧(无CD); 若信道占用,则:启动随机退避定时器、若信道空闲,则计时、若定时时间到,则发送、若没有收到ACK,则增加随机退避时间间隔, 返回 - 收端: 若收到一个帧,则:等待SIFS时间之后,响应ACK(因隐蔽节点问题,需要ACK) - MACA: 为解决WLAN中存在的隐蔽节点问题,采用MACA(MultipleAccess with Collosion Avoidance) - 发送端采用CSMA先发送短RTS帧(RTS之间也可能发送碰撞,但它很短) - 收端收到RTS后,发送CTS - CTS可被附近节点检测到,从而避免隐蔽节点问题 - 发端发送更长的数据帧 - 其他节点延迟发送 - 完全避免数据帧的碰撞,采用更短的预约分组! - 载波侦听有两类,物理的和虚拟的 - 物理的载波侦听:通过PLCP在空闲信道评估(CCA:Clear Channel Assessment)阶段,侦听相关比特或检查 RSS(received signal strength)是否高于门限 - 虚拟的载波侦听:基于网络分配矢量(NAV, Network allocation vector),从RTS/CTS帧中提取NAV - 优先级:定义不同的帧间隔 - SIFS (Short Inter Frame Spacing):高优先级,用于ACK,CTS,轮询响应 - PIFS (PCF IFS):中等优先级, 用于PCF方式的有时限限制的业务 - DIFS (DCF IFS):低优先级, 用于异步数据业务 - PCF: 基于DCF之上,支持无竞争、有时限要求的传输方式 - 为可选的MAC功能 – 有些产品不支持 - 主要过程: - AP周期性地轮询所有设备,建立CFP; - 在PCF期间,设置设备的NAV为ON - PCF周期的长度可变,并占用CFP的固定位置;其他时段用于竞争并传送DCF帧 ### 高速局域网及链路层交换机 - 100BASE-T以太网 - MAC帧格式仍采用802.3 标准 - R增大10倍,$\tau$减小到1/10 - 保持最短帧长不变,但将一个网段的最大电缆长度减小到100m - 帧间时间间隔从原来的9.6$\mu$s改为0.96$\mu$s——网络设备在接收一个帧之后,需要一段 时间恢复并为接收下一帧做准备。固定的为96b的时间 - 千兆以太网——允许在1Gb/s下采用全双工和半双工(与集线器 连接)两种方式工作,使用802.3的帧格式 - 全双工方式:发送接收同时进行,无碰撞,不需要CSMA/CD - 在半双工方式下使用CSMA/CD协议,与10BASE-T和100BASE-T技术后向兼容 - 为使参数a较小并保持网段最大长度为200m,采用“载波延伸”(carrier extension)使最短帧长仍为64字节,将争用时间增大为512字节 (4.096$\mu$s, 409.6m) - 载波延伸: 若发送的MAC帧长不足512字节时(例如46字节数据)就在帧后填充一些特殊字符,使帧的发送长 度增大到512字节(此时链路利用率约为9%);接收端在收到MAC帧后,删除填充的特殊字节后 才交付给高层 - 帧突发: 允许发送方将多个帧级联在一起,一次传输、帧长最长为1500字节、若不足512字节,则采用载波延伸; - 集线器Hubs:物理层的转发器(repeaters) - 来自一个端口的数据以相同速率在所有端口上发送 - 连接到集线器的所有节点可以相互侦听到 - 没有帧的缓存 - 集线器不做CSMA/CD:主机NIC检测碰撞 - 交换式以太网: - 需要决定一个帧去往哪个端口 - 在不同端口上传输的帧不发生碰撞 - 更安全:因为以太网卡支持混杂模式,例如协议分析软件Wireshark可以捕获全部的帧 - 交换机Switch:链路层设备 - 比集线器更智能,其主要作用 - 存储,转发以太帧 - 检测输入帧的MAC地址,有选择地向一个或多个端口转发帧,在转发接口对应的网段上实施 CSMA/CD - 透明:主机不感知交换机是否存在 - 分类: 1. 学习网桥:即插即用,自学习;无需配置即可工作 2. 生成树网桥: 3. 虚拟局域网:VLAN - 网桥或以太网交换机:将多个局域网连接在一起,工作在链路层,检测MAC地址并转发帧 - 交换: 允许多点同时传输 - 主机通过专线与交换机相连 - 交换机缓存分组 - 在每条输入链路上采用以太协议,各个链路间没有碰撞; - 每条链路有各自的碰撞 - 全双工 - 交换表: 表项组成(主机的MAC地址,达到主机 的接口,时间标记)类似于路由表 - 自学习: 当收到帧,交换机知道其发送的位置:输入LAN网段;将发送“主机/位置”记入交换表 - 不知帧的目的地址的位置: flood(在除帧接收的端口以外的其它所有端口上转发) - 目的地址 A 的位置已知: 选择发送 - 交换机从某一端口上接收到来自H1的帧,则记录:由此端口可以发送数据给H1,不需要知道哪个AP与H1关联 - 生成树网桥:(环路问题) 网桥之间通信,构造一个连接各网桥的生成树——网桥周期地发送配置消息给邻居,并处理接收的消息;配置消息中含标识(基于MAC地址)及与其他节点的跳 数;选择最小标识作为生成树的根;构造由根到每个网桥的最短路径树 - VLAN:按照用户的组织结构而非物理结构,构建局域网 - 优点:1.安全;2.负载均衡 3.减少广播流量 - 方法:必须建立配置表,设置其端口属于G或W或GW [1]: https://blog.ruixiaolu.com/usr/uploads/20200312023138.jpg [2]: https://blog.ruixiaolu.com/usr/uploads/20200312023149.jpg [3]: https://blog.ruixiaolu.com/usr/uploads/20200312023159.jpg [4]: https://blog.ruixiaolu.com/usr/uploads/20200312023209.jpg [5]: https://blog.ruixiaolu.com/usr/uploads/20200312023222.jpg [6]: https://blog.ruixiaolu.com/usr/uploads/20200312023233.jpg [7]: https://blog.ruixiaolu.com/usr/uploads/20200312023241.jpg [8]: https://blog.ruixiaolu.com/usr/uploads/20200312023253.jpg [9]: https://blog.ruixiaolu.com/usr/uploads/20200312023304.jpg [10]: https://blog.ruixiaolu.com/usr/uploads/20200312023312.jpg [11]: https://blog.ruixiaolu.com/usr/uploads/20200312023319.jpg [12]: https://blog.ruixiaolu.com/usr/uploads/20200312023330.jpg [13]: https://blog.ruixiaolu.com/usr/uploads/20200312023338.jpg [14]: https://blog.ruixiaolu.com/usr/uploads/20200312023346.jpg [15]: https://blog.ruixiaolu.com/usr/uploads/20200312023355.jpg 最后修改:2020 年 10 月 11 日 © 禁止转载 打赏 赞赏作者 支付宝微信 赞 0 如果觉得我的文章对你有用,请随意赞赏