计算机网络概论

计算机网络的应用

  • 商业应用: 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
    数据(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)123455e67
    UseVoice OnlyData to 4Mbps10Mbps20Mbps100Mbps100Mbps250MHz600MHz
    WhereTelephone WireLocal TalkEthernet16Mbps Token RingFast EthernetFast EthernetGigabit 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
    • 调制星座图: 数字通信中,将数字信号表示在复平面上,给出信号及信号之间的关系的图示就是星座图

信道复用: 在一条传输介质上提供多个数据传输信道的方法

频分复用 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
  • 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
  • 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

成帧——同步、透明传送

  • 同步: 计算机之间的通信需要收发双方协调发送和接收之间的动作

    1. 异步传输: 以字符为传输单位,字符之间的时间间隔是可变的,而字符中的位则以固定速率传送.

      • 起停位、数据为、校验位
      • 传输字符之间无固定时间间隔
      • 接收时钟与发送时钟存在偏差
      • 特点: 简单、廉价、每帧一个字符
    2. 同步传输: 发送和接收之间的每位都是同步的,接收端从接受的信号中提取时钟,以保持与发送信号的时钟同步

      • 以数据块位传输单位
      • 要求时钟同步——提供时钟线给接收端或从接收信号中提取时钟
      • 适用于长距离的数据传输,效率高
      • 举例: 以太帧——同步码:8个字节,前7 用于帧的位同步,最后1个是帧开始定界符,表示后面的信息是MAC帧
        5cd5391d02acc.jpg
  • 帧是链路层的基本单位,用于承载链路层的数据、实施差错控制
  • 异步传输中的起始停止位、同步传输中的同步位之后需要确定帧开始.
  • 成帧方法:

    1. 字节计数法: 利用头部的一个字段来标识该帧的字节数

      • 问题:若头部字节出错,则会失去同步
      • 解决:若能将一个特殊的字节作为帧的首尾标志,则帧失步后可以重新同步
    2. 封装成帧: 在一段数据的前后分别加首部“SOH”(0x01)和尾部“EOT”(0x04),构成一个帧

      • 首部和尾部的作用就是帧定界
      • 问题: 若帧数据部分含有帧头或帧尾,则会导致同步出错,遗失信息
      • 解决:

        1. 字符填充实现透明传输:

          • 发送端若在数据中出现“SOH”或“EOT”,则在其前面插入一个转义符“ESC”(0x1B).
          • 接收端将数据送往高层之前删除插入的转义符.
          • 若转义符也在数据中出现,则在转义符前插入一个转义符,当接收段收到连续两个转义符时就删除一个
            5cd5391e40b9c.jpg
        2. 用比特填充实现透明传输:

          • HDLC,帧标志位F为01111110,采用零比特填充,
          • 数据中某一段比特组合恰好和F一样时,
          • 发送端在连续发送5个连1后,填入一个0比特再发送出去,
          • 接收端将5个连1之后的0比特删除,恢复原帧
            5cd5391e5fa9e.jpg

差错控制技术:检错及纠错

  • 差错: 数字通信系统中接收位与发送位不一致
  • 信道误码率: $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
      • 优点: 无需反向信道、单工即可,也可用于一对多的通信
      • 缺点: 译码设备复杂,为纠错需附加冗余码
    2. 自动请求重传ARQ(Automatic Repeat reQuest): 接收端检测到错误时,通知发送端重传,直到收到正确的数据

      • 模型——发送端将数据发向信道,同时缓存数据.如果接到重发请求,则将放入缓存器的数据重新编码发送,接收端判决,如果接收正确则发送ACK,若检测到错误则发送NACK,要求重发.
        5cd5391e87e8f.jpg
      • 三种ARQ方式:停发等候重发、返回重发、选择重发
    3. 混合纠错HARQ(Hybrid ARQ)检错码+纠错码

      • 若发现差错但在纠错范围内,则直接纠错; 当超出纠错能力时,则要求发端重传
    4. 对比
      FEC不需要重传,实时性好,常用于无线链路
      ARQ常用于计算机网络
      5cd5391e90b57.jpg

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
      • 数据帧发送后若经过重传时间还没有收到确认帧,则重传数据帧,设重传时间为

        $$ _{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
        • 仍然可能发送碰撞:传播延迟致使两个结点无法听到对方发送的信号
        • 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

    • 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

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
最后修改:2020 年 10 月 11 日
如果觉得我的文章对你有用,请随意赞赏