2020年秋季学期计算机网络课件link

1、计计 算算 机机 网网 络络第四讲刘威华中科技大学电信学院 2020回顾回顾: 网络连通性网络连通性什么是直连网络什么是直连网络? ?所有的主机通过某种物理媒质直接连接所有的主机通过某种物理媒质直接连接-2-直连网络直连网络直连网络 什么是直连网络什么是直连网络(Direct Link Network)? 所有的主机通过某种物理媒质直接连接所有的主机通过某种物理媒质直接连接 物理传输媒质物理传输媒质: 电缆电缆, 光纤光纤, 空气接口空气接口, 与距离无关与距离无关: 小的区域小的区域(例如例如, 一栋办公大楼一栋办公大楼) 或者一个大的区或者一个大的区域域(例如例如, 横贯大陆横贯大陆) 本

2、章的研究动机本章的研究动机(Motivation) 直连网络是最简单的网络形式直连网络是最简单的网络形式 我们从简单的场景入手，首先考虑用传输媒质将两台或多台我们从简单的场景入手，首先考虑用传输媒质将两台或多台主机主机(Host)连接起来连接起来 然后考虑更加复杂的场景：不同传输介质的网络互联、不同然后考虑更加复杂的场景：不同传输介质的网络互联、不同网络的互联网络的互联-3-回顾回顾: 网络体系结构网络体系结构 直连网络在体系结构中所处的层次主要在直连网络在体系结构中所处的层次主要在L2 L1(物理层物理层) ：物理传输媒质上的数字通信：物理传输媒质上的数字通信 L2(数据链路层数据链路层)

3、：网络数据在链路上的传输管理：网络数据在链路上的传输管理-4-应用层表示层会话层传输层网络层数据链路层物理层网际层网络接入运输层应用层IPLANPacketradioTCPUDPTelnetFTPDNSISO OSI 网络体系结构网络体系结构(7层参考模型层参考模型)Internet 体系结构体系结构 (4层层TCP/IP 协议栈协议栈)第2章的核心问题:如何连接到网络-5-第第2章章 开始连接开始连接 问题：连接到网络问题：连接到网络 2.1 连接概览连接概览 2.2 编码编码 2.3 组帧组帧 2.4 差错检测差错检测 2.5 可靠传输可靠传输 2.6 以太网和多路访问网络以太网和多路访问

4、网络 2.7 无线无线 2.8 小结小结-6-链路链路 物理传输媒质物理传输媒质 导向型媒质导向型媒质: 信号在固态媒质上传播信号在固态媒质上传播, 例如同轴电缆例如同轴电缆, 光纤光纤, 双双绞线绞线 非导向型媒质非导向型媒质: 信号自由传播信号自由传播, 例如电磁波例如电磁波-7-无线电微波红外线可见光紫外线X射线射线双绞线同轴电缆卫星地面微波 调幅无线电 调频无线电 海事无线电光纤电视(Hz)f (Hz)fLFMFHFVHF UHF SHFEHFTHF波段104 105 106 107 108 109 1010 1011 1012 1013 1014 1015 1016100 102 1

5、04 106 108 1010 1012 1014 1016 1018 1020 1022 1024 移动无线电 物理媒质: 有线 双绞线(twisted pair，TP)绝缘的铜线3类: 传统电话线, 10 Mbps 以太网5类: 100Mbps 以太网-8-类型类型简称简称频率带宽频率带宽数据速率数据速率传输距离传输距离应用应用一类线CAT1750kHz/语音传输二类线CAT21MHz4Mbps令牌环网三类线CAT316MHz10Mbps100m10M以太网四类线CAT420MHz16Mbps100m10M以太网五类线CAT5100MHz100Mbps100m100M以太网六类线CAT62

6、50MHz1Gbps100m高速以太网七类线CAT7600MHz10Gbps100m高速以太网物理媒质: 有线 -9-光纤采用玻璃纤维传递光脉冲, 一个脉冲代表一个比特高速、低误码率远距离中继转发同轴电缆宽带: 多信道 有线电视网 混合光纤同轴网（HFC）商业链路 租用线路 通常指通过电话网络的一个逻辑连接 价格昂贵 最后一公里链路 传统电话服务（POTS）和综合业务数字网（ISDN）: 网络接入网络 数字用户线（xDSL） 和电缆调制解调器：用户接入网络-10-物理媒质：无线 通过电磁波携带信号 不存在物理的“线路” 双向 易受环境影响: 反射 障碍物 干扰-11-典型无线链路类型:地面微波

7、可达到45 Mbps局域网(例如, 802.11)11 Mbps 54 Mbps较大区域 (例如, 蜂窝网)3G 蜂窝网: 1 Mbps4G 蜂窝网卫星网45Mbps 270 ms 端到端时延通信的基础概念通信的基础概念 通信方式通信方式 同步同步 vs. 异步异步 是否双方需要采用相同是否双方需要采用相同的时钟频率的时钟频率 通信模式通信模式 单工：只有单向的通信单工：只有单向的通信过程，例如广播电视过程，例如广播电视 半双工：通信双方仅能半双工：通信双方仅能交替通信，不能同时收交替通信，不能同时收发发 双工：通信双方可以同双工：通信双方可以同时双向通信时双向通信-12-通信的基础概念通信的

8、基础概念 数据传输速率数据传输速率 波特率（又称码元速率、调制速率、波形速率）：单位波特率（又称码元速率、调制速率、波形速率）：单位时间可以传输的码元个数（或者脉冲个数、信号变化个时间可以传输的码元个数（或者脉冲个数、信号变化个数），单位是数），单位是Baud 波特波特 比特率：单位时间内可以传输的二进制码元个数，即比特率：单位时间内可以传输的二进制码元个数，即bit数，单位为数，单位为bps 波特率与比特率的关系：比特率波特率与比特率的关系：比特率S（单位为（单位为bps）与调制）与调制速率速率B（单位为（单位为baud）之间关系可以表示为：）之间关系可以表示为：S=Blog2k，式中式中k

9、为多相调制的相数。为多相调制的相数。 log2k值表示一次调制状态的变化传输的二进制比特数。值表示一次调制状态的变化传输的二进制比特数。-13- 调制速率（baud） 多相调制的相数log2k值 数据传输速率（bps）2400QPSK-2（k=2）124002400QPSK-4（k=4）248002400QPSK-8（k=8）372002400QPSK-16（k=16）49600通信的基础概念通信的基础概念奈奎斯特采样准则奈奎斯特采样准则如果表示码元的窄脉冲信号以时间间隔为如果表示码元的窄脉冲信号以时间间隔为/（=2f=2f）通过理想通信信道，则前后码元之间不产生相互串扰。通过理想通信信道，则

10、前后码元之间不产生相互串扰。根据奈奎斯特准则，二进制数据信号的最大数据传输速率根据奈奎斯特准则，二进制数据信号的最大数据传输速率RmaxRmax与理想信道带宽与理想信道带宽B B（单位（单位HzHz）的关系可以写为：）的关系可以写为： Rmax=2BRmax=2B（bpsbps）。）。奈奎斯特定理描述了有限带宽、无噪声的理想信道的最大传奈奎斯特定理描述了有限带宽、无噪声的理想信道的最大传输速率与信道带宽的关系。输速率与信道带宽的关系。-14-通信的基础概念通信的基础概念香农定理香农定理在有随机热噪声的信道中传输数据信号时，传输速在有随机热噪声的信道中传输数据信号时，传输速率率RmaxRmax与

11、信道带宽与信道带宽B B、信噪比、信噪比S/NS/N的关系为：的关系为：Rmax=Blog2Rmax=Blog2（1+S/N1+S/N）式中，式中，RmaxRmax单位为单位为bpsbps，带宽，带宽B B单位为单位为HzHz香农定理则描述了有限带宽、有随机热噪声信道的香农定理则描述了有限带宽、有随机热噪声信道的最大传输速率与信道带宽、信号噪声功率比之间的最大传输速率与信道带宽、信号噪声功率比之间的关系。关系。-15-物理层 vs 数据链路层模拟信号数字信号比特流0 1 0 1 0 1 1 0 0 1 0 0 1 0数据帧0 0 0 0 Header/BodyHeader/BodyHeader

12、/Body接收端发送端传输数据帧16物理层为上层提供比特流传输服务物理层为上层提供比特流传输服务物理层物理层数据链路层数据链路层直连网络的研究问题直连网络的研究问题 编码编码(Coding) 对发送到电缆或光纤上的比特进行编码，使其能被接收主机所解读对发送到电缆或光纤上的比特进行编码，使其能被接收主机所解读 组帧组帧(Framing) 把物理链路上传输的比特序列组装成数据单元，以便传送到目的节把物理链路上传输的比特序列组装成数据单元，以便传送到目的节点点-17-0101010110111 01010101 0011?直连网络的研究问题直连网络的研究问题 差错检测差错检测(Error Detec

13、tion) 检测帧传输过程中出现的错误检测帧传输过程中出现的错误 可靠传输可靠传输(Reliable Transmission) 通过特定机制在有差错链路上实现可靠的无差错的传输通过特定机制在有差错链路上实现可靠的无差错的传输-18-1100110111001101111111011100110111001101110011011111110111111101 直连网络的研究问题直连网络的研究问题 共享链路的通信共享链路的通信 /介质访问控制介质访问控制(Media Access Control) 静态共享：按序接入，易于实现静态共享：按序接入，易于实现 动态共享：随机接入，如何协调多个主机的

14、接入动作动态共享：随机接入，如何协调多个主机的接入动作? -19-第第2章章 开始连接开始连接 问题：连接到网络问题：连接到网络 2.1 连接概览连接概览 2.2 编码编码 2.3 组帧组帧 2.4 差错检测差错检测 2.5 可靠传输可靠传输 2.6 以太网和多路访问网络以太网和多路访问网络 2.7 无线无线 2.8 小结小结-20-比特和信号比特和信号 比特比特 编码编码/解码解码 信号信号-21-Signalling componentSignalBitsNodeNodeAdaptorAdaptor假设假设 假设处理离散信号假设处理离散信号( (忽略调制细节忽略调制细节), ), 高信号和

15、低信号高信号和低信号, , 对应编码为对应编码为1 1和和0 0 收发双方同步收发双方同步, , 即存在一个时钟进行信号采样即存在一个时钟进行信号采样 如果信号的幅值和持续时间足够大如果信号的幅值和持续时间足够大, , 接收机可以识别接收机可以识别出发送的信号出发送的信号. . -22-不归零不归零 NRZ (Non-Return to Zero) 编码编码 1 高信号高信号; 0 低信号低信号 问题问题: 连续的连续的1 或或 0 连续的连续的 0可能被误认为没有信号可能被误认为没有信号 连续的连续的 1可能导致基线漂移可能导致基线漂移 时钟恢复困难（同步问题）时钟恢复困难（同步问题）-23

16、-001010110NRZ(不归零)时钟不归零反转不归零反转 (NRZI) 编码编码 1 信号跳变信号跳变 0 信号保持信号保持 可以解决持续可以解决持续1的问题的问题, 未能解决连续未能解决连续 0的问题的问题-24-001010110时钟NRZI(不归零反转)曼彻斯特编码曼彻斯特编码 编码编码 1 高到低跳变高到低跳变 0 低到高跳变低到高跳变 有效恢复时钟有效恢复时钟 缺点缺点: 信号跳变速率翻倍信号跳变速率翻倍 比特率是信号跳变速率（波特率）的一半比特率是信号跳变速率（波特率）的一半 编码效率编码效率: 50%-25-001010110ClockManchester图示说明图示说明-2

17、6-BitsNRZClockManchesterNRZI00101111010000104-bit/5-bit 目标目标: 解决曼彻斯特编码的低效问题解决曼彻斯特编码的低效问题, 同时避免持续的同时避免持续的低信号低信号 解决方案解决方案: 用用5个比特对个比特对4个比特的数据进行编码个比特的数据进行编码, 其中每个代码其中每个代码 (5个比特个比特)中最多有中最多有1个前导个前导0, 且末端最多有且末端最多有2个个0 采用采用NRZI对对5比特的代码进行编码比特的代码进行编码 编码效率编码效率: 80%-27-0000 111100001 010010010 101000011 101010

18、100 010100101 010110110 011100111 011111000 100101001 100111010 101101011 101111100 110101101 110111110 111001111 111014-bit 5-bit4-bit 5-bit第第2章章 开始连接开始连接 问题：连接到网络问题：连接到网络 2.1 连接概览连接概览 2.2 编码编码 2.3 组帧组帧 2.3.1 Byte-Oriented Protocols (BISYNC, PPP, DDCMP) 2.3.2 Bit-Oriented Protocols (HDLC) 2.3.3 Clo

19、ck-Based Framing (SONET) 2.4 差错检测差错检测-28-帧定界问题帧定界问题 两个节点之间的数据传输以块为单位两个节点之间的数据传输以块为单位(帧帧) 能够识别数据帧的开始和结束能够识别数据帧的开始和结束-29-FramesBitsNode ANode BAdaptorAdaptor面向字节的协议面向字节的协议 面向字节面向字节 把每一帧看做一个字节把每一帧看做一个字节(字符字符)集合集合 两种方法两种方法 字符计数法字符计数法 起止标记法起止标记法-30-字节计数法字节计数法DDCMP (Digital Data Communication Message Prot

20、ocol) DEC 公司公司(Digital Equipment Corporation), 1974 特点特点帧首部有一个字段注明帧的字节数帧首部有一个字段注明帧的字节数缺点缺点一旦发生错误一旦发生错误, 错误会发生累积效应错误会发生累积效应-31-HeaderBody884214168CRCCountCount: Specifies # of bytes in the body起止标记法起止标记法BISYNC (Binary Synchronous Communication) IBM公司在公司在1960s末期开发末期开发特点特点起止字符起止字符: 开始和结束字符开始和结束字符STX (正

21、文开始符正文开始符), ETX (正文结束符正文结束符)问题问题ETX字符可能出现在数据帧的数据部分字符可能出现在数据帧的数据部分解决方案解决方案 字符填充字符填充在数据部分的在数据部分的ETX前填充前填充DLE (数据链路转义数据链路转义)数据部分的数据部分的DLE前也重复填充前也重复填充DLE-32-HeaderBody8888168CRCSYN: Synchronization characterSOH: Start of headerSTX, ETX: Start of text, End of textCRC: Cyclic redundancy check起止标记法起止标记法PPP

22、 (Point-to-Point Protocol )IETF, 首次提出在首次提出在 1992 正式版版本正式版版本 RFC 1661 , 1994特点特点成帧成帧STX和和ETX: 0 x7E链路控制功能：链路控制功能：LCP (链路控制协议链路控制协议)，可用于启动路线、测试线，可用于启动路线、测试线路、协商参数以及关闭线路路、协商参数以及关闭线路网络控制功能：网络控制功能：NCP (网络控制协议网络控制协议)，协商网络参数，常用于，协商网络参数，常用于在连接时刻协商在连接时刻协商IP地址地址-33-ProtocolControlAddressFlagPayload88816168Fla

23、gChecksum第第2章章 开始连接开始连接 问题：连接到网络问题：连接到网络 2.1 连接概览连接概览 2.2 编码编码 2.3 组帧组帧 2.3.1 Byte-Oriented Protocols (BISYNC, PPP, DDCMP) 2.3.2 Bit-Oriented Protocols (HDLC) 2.3.3 Clock-Based Framing (SONET) 2.4 差错检测差错检测-34-面向比特的协议面向比特的协议 面向比特的协议面向比特的协议 把数据帧看做比特的集合把数据帧看做比特的集合 HDLC (High-Level Data Link Control) 基于

24、基于IBM的的SDLC协议开发，经由协议开发，经由ITU标准化，在标准化，在X.25协议协议栈中被采纳，编制时间栈中被采纳，编制时间70年代初年代初 最终版本是最终版本是ISO 3309 起止比特位串起止比特位串:- 01111110 问题问题: 数据字段可能出现数据字段可能出现01111110 解决方法解决方法 零比特填充零比特填充-35-HeaderBody816168CRCBeginningsequenceEndingsequenceHDLC (高级链路控制规程高级链路控制规程) 发送端发送端, 每连续发送每连续发送5个个1 插入一个比特插入一个比特0 接收端接收端, 每连续收到每连续收

25、到5个个1 如果后续比特为如果后续比特为0: 删除删除0比特比特 如果后续比特为如果后续比特为10: 帧结束帧结束 如果后续比特为如果后续比特为11: 出错出错 比特填充的特点比特填充的特点 可能连续两次接收失败可能连续两次接收失败 帧的长度由帧中有效载荷中传送的数据决定帧的长度由帧中有效载荷中传送的数据决定-36-零比特填充案例零比特填充案例-37-第第2章章 开始连接开始连接 问题：连接到网络问题：连接到网络 2.1 连接概览连接概览 2.2 编码编码 2.3 组帧组帧 2.3.1 Byte-Oriented Protocols (BISYNC, PPP, DDCMP) 2.3.2 Bit

26、-Oriented Protocols (HDLC) 2.3.3 Clock-Based Framing (SONET) 2.4 差错检测差错检测 2.4.1 Two-Dimensional Parity 2.4.3 Cyclic Redundancy Check 2.4.2 Internet Checksum Algorithm -38-直连网络的研究问题直连网络的研究问题 差错检测差错检测(Error Detection) 检测帧传送过程种可能出现的错误检测帧传送过程种可能出现的错误, 并采取相应的动作并采取相应的动作-39-11001101110011011111110111001101

27、 比特错误比特错误 问题问题 电磁干扰和热噪声可能导致比特错误电磁干扰和热噪声可能导致比特错误 数据帧有时会发生比特错误数据帧有时会发生比特错误 解决方案解决方案 差错检测差错检测(Error Detection) 接收方可以通过编码方式检测到差错接收方可以通过编码方式检测到差错 差错纠正差错纠正(Error Correction), 通常有两种方法通常有两种方法: 接收方通知发送方重发消息接收方通知发送方重发消息 接收方重新构造消息接收方重新构造消息-40-差错检测的基本原理差错检测的基本原理-41-EDC/ECC = 检错和纠错的比特检错和纠错的比特(冗余填充冗余填充)D = 受差错保护的

28、数据部分受差错保护的数据部分, 包括首部字段包括首部字段otherwise差错检测的基本原理差错检测的基本原理 主要目标主要目标 冗余度冗余度 n = 数据长度数据长度, k = EDC长度长度 k 远小于远小于 n 检错概率检错概率 概率最大化概率最大化 差错检测并不一定差错检测并不一定100% 可靠可靠! 协议可能出现错误协议可能出现错误(极少数极少数) EDC字段越长检错效果越好字段越长检错效果越好-42-二维奇偶校验二维奇偶校验-43-“1” x 9 in 16 bits odd parity bit奇数校验二维奇偶校验二维奇偶校验 可以检测并纠正单比特错误可以检测并纠正单比特错误-4

29、4-00偶数校验第第2章章 开始连接开始连接 问题：连接到网络问题：连接到网络 2.1 连接概览连接概览 2.2 编码编码 2.3 组帧组帧 2.3.1 Byte-Oriented Protocols (BISYNC, PPP, DDCMP) 2.3.2 Bit-Oriented Protocols (HDLC) 2.3.3 Clock-Based Framing (SONET) 2.4 差错检测差错检测 2.4.1 Two-Dimensional Parity 2.4.3 Cyclic Redundancy Check 2.4.2 Internet Checksum Algorithm -4

30、5-循环冗余校验的数学基础循环冗余校验的数学基础 原理原理 数学有限域数学有限域(Finite field)的理论的理论 有限域有限域GF(2)(关于关于2同余同余)的多项式环：所有系数都为的多项式环：所有系数都为0或或1（又叫做二进制）的多项式系数的集合，该集合对于所有的（又叫做二进制）的多项式系数的集合，该集合对于所有的代数操作都是封闭的，对系数的加法都会模代数操作都是封闭的，对系数的加法都会模2 有限域封闭的特性，便于设计各种二进制运算，例如加密、有限域封闭的特性，便于设计各种二进制运算，例如加密、纠错编码等纠错编码等-46-循环冗余校验的原理循环冗余校验的原理 通过生成元多项式构造整除

31、关系式通过生成元多项式构造整除关系式其中其中 是原始的信息多项式是原始的信息多项式 是生成元多项式是生成元多项式 是余数是余数发送方发送方首先将原始多项式扩充首先将原始多项式扩充n阶，构成零扩展的消息阶，构成零扩展的消息然后除以然后除以 获得获得 ，构造校验和，构造校验和最后构造包含校验和的编码后的消息最后构造包含校验和的编码后的消息接收方接收方检验收到的消息检验收到的消息 能否被能否被 整除整除如是，则收到无误如是，则收到无误如否，则存在错误如否，则存在错误-47-循环冗余校验的原理循环冗余校验的原理 -48-发送数据M(x)生成多项式G (x)M(x)xn.C(x)=Q(x)+R(x)C(x)实际发送: M(x)xn.+ R(x).R(x)接收数据M (x)生成多项式G (x)R(x)= R(x) 接收正确R(x) R(x) 接收错误发送M (x)xn.C(x)=Q (x)+R(x)C(x)+数据字段校验字段发送端接收端M(x)xn.R(x)+M(x)xn接收模2运算 类似于二进制运算, 但不存在借位 示例: 模2运算中的加法和减法等同于XOR操作aba b00001110111049101 +010111101 +0011001011 +011111001011 -01111100101 -0101