• 媒介

  • 类型

    • 有线、光纤、无线

  • 有线

    • 5类UTP双绞线：常见的以太网电线。绞线是为了减少噪音

    • 同轴电缆：这种哦线有更好的保护措施和更好的性能

  • 光纤

    • 光线是又长、又细、又纯净的玻璃

    • 有非常巨大的带宽

    • 分为多膜和单膜。单膜的性能更好

  • 无线

    • 所有的无线信号都是广播的

    • 邻近的设备同时通信时会相互干扰

    • 无线举例：3G  ISM（802.11b/g/n）   Wifi（802.11a/g/n

• 信号

  • 话题

    • 信号传输的时候发生了什么

  • 频率的表示方法

    • 用三角函数

  • 低带宽带来的影响

    • 让脉冲变得更加圆滑，增加了判断0或1的难度，导致传输速度变慢

  • 在电线中传输

    • 信号会延迟。传输速度大约为2/3光速

    • 信号会衰减

    • 高频信号会被吸收

    • 噪音会增多

    • 带宽可以理解为两种，一种是电子工程中的带宽，一种是网络工程中的带宽。两种这两种带宽的单位不同。电子工程中的带宽用Hz作为单位，而网络工程中的带宽用Mbps为单位

  • 在光纤中传输

    • 比特流通过三原色进行传输

    • 信号衰减程度非常低

  • 在无线中传输

    • 将信号调幅后发送

    • 传播速度是光速

    • 信号衰减速度很快，大于1/dist^2

    • 相同频率的无线传输之间会相互干扰

    • 从信号干扰衍生出了空间重用率的概念。只要不相互干扰，无线的频率是可以重用的

    • 无线传输还受到其他因素的影响。无线在空间中的传播是非常复杂的，和物理环境有关

    • 某些效果只出现在特定的频率中，比如微波的衍射性能强，可以绕过障碍物进行传播。比如802.11、3G

  • 无线的多路传播

    • 微波具有衍射特性和反射特性

    • 有些波是直接到达设备的，有些波经过反射到达了设备。两个波会叠加，有时候能增强信号，有时候削弱信号

    • 这种现象叫做OFDM

• 调制

  • 话题

    • 信号的表示方法

  • 简单的信号调制

    • 高压+V表示1，负压-V表示0

  • 其他的表示方法

    • 使用更多的电压表示更多的数据。比如一个电压表示2bit数据

  • 时钟同步

    • 如果一次发送非常多的0，那么接收方无法精确知道有多少个0

    • 所以有了Manchester coder孟彻斯特编码和scrambling编码

    • 孟彻斯特就是将0替换成01，1替换成10。

  • 4B/5B

    • 固定的编码

      • 0000 -> 11110

      • 0001 -> 01001

      • 。。。
        

      • 1110 -> 11100

      • 1111 -> 11101

    • 最多3个连续的0

  • NRZI编码：遇到1就改变电压，遇到0就保持原来的电压

  • Passband调制

    • baseband调制在电线中非常合适，但是在光纤/无线中无法很好地工作

    • 将每个比特进行调制，可以调频，调幅，调相

• 基本极限

  • 话题

    • Nyquist限制

    • Shannon容量

    • 为了达到极限而产生的发明

  • 信道的关键属性

    • 带宽B，强度S，信噪比N

  • Nyquist极限

    • 信号发送的最大速度是2B，也就是两倍带宽（电子工程中的带宽）

    • 假设有V种电平，信号发送速率R = 2B log_2(V) bits/sec

  • 香农极限

    • 信息论创始人

    • 信道可以提供多少种电平和信噪比有关

    • 信噪比用db来表示，信造比SNR=10log_10(S/N)

    • 香农容量 C = B log_2(1+S/N) bits/sec，表示一条信道的最大传输速率

  • 有线/无线对比

    • 有线/光纤：可以有固定的数据传输速率

    • 无线：没有固定的数据传输速率

  • DSL

    • 使用电话线的高频部分进行传输

    • DSL使用passband调制

    • 上传和下载是用的是两段不同的带宽

    • 高信噪比时可能1个信号表示15个比特，低信噪比的时候可能1个信号表示1个比特

数据链路层

• 链路层概述

  • 链路层结构

    • 关注如何传输消息，一则消息就是一帧

  • 链路层数据包结构为：Header-Packet-Tailer

  • 链路层的典型实现方法

    • 网卡上有链路层的模块和物理层的模块，操作系统中有链路层的驱动。链路层是同时分布在软件和硬件中的一个协议层。

  • 话题

    • 帧。区分帧的头和尾的方法

    • 错误检测，错误矫正，错误处理

• 帧

  • 话题

    • 如何通过物理层表示一系列帧呢？

  • 区分帧的方法

    • 字节数

    • 字节

    • 实际应用中物理层有时候也会帮助链路层来区分帧

  • 第一次尝试：字节数方法

    • 每一帧的头部是字节数

    • 这种方法很简单，看起来也很有用，但是出错后很难再次同步

  • 第二次尝试：用字节标志

    • 用特殊的标志字节来标志帧的头和尾

    • 缺点是数据的内容也要进行编码。例如数据内容：A FLAG B，编码后变成 A ESC FLAG B

    • 优点是出错后容易同步

  • 第三次尝试：用数据位来做标志

    • 6个1为头尾标志

    • 数据的内容进行编码，每5个1之后插入一个0。解码的时候，每5个1之后删除一个0

    • 举例：0110 1111 1111 1111 1111 0010，编码后0110 1111 1011 1111 0111 1101 0010

  • 链路举例：SONET上的PPP

    • PPP：点对点链路协议

    • SONET：光纤物理层协议

    • 分帧时使用字节标志，0x7E表示FLAG，0x7D表示ESC

    • 0x7E编码后变成0x7D5E，也就是增加了7D，并将第5位进行取反

    • 0x7D编码后编程0x7D5D

    • 这样编码之后数据中就彻底没有FLAG或ESC符号了

• 错误概述

  • 话题

    • 如何处理错误

    • 如何检测错误

    • 如何矫正错误

    • 如何重新发送数据

    • 链路层的可靠性

  • 问题

    • 噪音有时候会造成比特上的误差

  • 方法

    • 增加冗余

    • 错误检测：增加校验位

    • 错误矫正：增加更多的校验位

    • 关键问题是，如何通过最少的校验位来检测到最多的错误

  • 最简单的方法

    • 将数据发送两次。能检测到错误，但是不能矫正

  • 使用校验位

    • 发送方数据的末尾增加检测位，D为数据，检测位R=fn(D)

    • 接收方，接收到数据D和检测位R，计算R==fn(D)，根据计算结果判断是否出错

    • 将数据进行随机改动，一般情况下都能判断出数据中存在错误

  • Hamming距离

    • 距离=两个数据有多少个位是不一样的

    • 最少发生d+1次反转后检测位依然正确的校验方法，最多能稳定检测到d个错误

    • 最少发生2d+1次反转后检测位依然正确的校验方法，最多能稳定矫正到d个错误

    • 举例，一段数据增加了检测位，传输之后有2个位发生了反转，而且检测位依然正确，那么它的距离d就是2

• 错误检测

  • 话题

    • 数据在接收的时候可能会有误差，我们如何检测到它呢？

    • 方法：奇偶校验、校验和、CRC

    • 检测错误是为了后续的矫正错误，比如重发

  • 简单的错误检测方法：奇偶校验

    • 1001100 => 1

    • 性能如何？

    • hamming距离d=2，最多能稳定检测到1个错误，无法矫正错误

    • 大的误差很难检测

  • 校验和

    • TCP中1500bytes数据有16bit校验和

    • 比奇偶校验更强

  • 互联网校验和

    • Checksum：the checksum field is 16bit 1‘s complement of the 1‘complement sum of all 16bit words

    • 伪代码：x=sum([e for bit16 in data]); return x + x%0x10000;

    • 发送方步骤

      • 将数据排列成16位一组

      • 将0放在校验位，并把每组数据加入到校验位

      • 将溢出的进位加到校验位

      • 将结果取反

    • 接收方把接接收到的（数据+checksum）计算checksum，如果得到0，那么说明没有错误

    • 性能如何

      • 距离是2，能稳定检测1个错误，不能矫正错误

      • 连续出现16个位错误时就无法工作了

  • CRC

    • 更强的保护

    • 举例，数据为302，校验位数为1位，生成器为3，那么CRC=3020 % 3 = 2

    • 发送方步骤

      • 在数据后方增加k个0

      • 将数据除以C，取余数。除的时候注意：要将减法换成XOR运算，其实CRC中的除法并不是真正的除法

      • 调整k，使其可以被整除

    • 标准的CRC32生成器是10000010 01100000 10001110 110110111

    • 属性

      • HD=4 Hamming距离，能稳定检测3个连续的错误

      • 能检测奇数个错误

      • 连续出现k个错误时就无法正常工作了

    • 实际应用中的错误检测方法

      • CRC被广泛使用：以太网，802.11 ADSL 线缆

      • 互联网中也有使用：IP TCP  UDP

      • 奇偶校验很少使用

• 错误矫正

  • 话题

    • 有时候接收到的数据中有错误，如何矫正呢

    • 我们能够矫正错误，为什么还要使用检测错误呢

  • 为什么错误矫正很难

    • 缺少好的校验方法
      

    • 校验代码也可能出错

  • 错误矫正代码

    • 构建一种Hamming距离为3的错误编码，需要改变3个字节才能让编码成为另外一种正确的编码

    • 假设错误只有1位，那么我们可以将错误矫正到最近的编码上

  • Hamming距离

    • 举例：4位数据0101，3个检验位。检验1 检验2 数据1 检验3 数据2 数据3 数据4

    • 检验1覆盖了检验1 数据1 数据2 数据4

    • 检验2覆盖了检验2 数据1 数据3 数据4

    • 检验3覆盖了检验3 数据2 数据3 数据4

    • 每个检验位用奇偶检验法生成，结果是010，和原来的数据合成，得到0100101

    • 解码的时候计算检验位，得到检验1,2,3，按照（检验3，检验2，检验1）进行排列，得到二进制数。这个2进制数就表示出错的位置，0表示没有错误

    • ?具体计算方法见下文中的表格
      

  • 其他矫正错误的方法

    • 实际应用中的矫正方法比Hamming距离复杂得多

    • LDPC

  • 错误检测和错误矫正的对比

    • 假设每10000个位就会发生一个错误

    • 检测错误大约需要10位额外的比特位

    • 矫正错误大约需要1000个额外的比特位，大约占用了1/10的传输时间

    • 有时候检测错误的开销更小，有时候矫正错误的开销更小，主要看数据的传输情况

  • 应用

    • 在物理层中大量使用的是LDPC

    • 错误矫正在CD DVD中也有使用

Hamming代码计算方法

p1 p2 p4等表示校验位，d1 d2 d3等表示数据位。