第二讲

• 重点：

  • 组播技术
  • 网络技术
  • 评判网络的性能指标

• 计算机网络的定义

  • 地理分散
  • 独立功能
  • 通信系统
  • 共享资源
  • 信息交流
• 计算机网络的元素
  • 主机（用户终端，服务器）
  • 通信链路
  • 交换节点
  • 拓扑结构
  • 通信软件
• 计算机网络的分类
  • 有线网络 无线网络(同频，单信道 -> 信号检测困难，信道管理复杂 -> 以太网， wifi 协议控制)
  • 范围小到大
    • 个域网 10m 左右 段距离无线通信标准：蓝牙
    • 局域网 有线/无线
    • 城域网
    • 广域网
  • 广播网络 点-点网络
    • 广播网络
      • 广播信道：只有一个通信信道(共享介质)
      • 单播：一对一的通信模式， 发送者将消息发给制定的某个接收者
        节点标识自己的 ID， 发送时指定， 接收方检查
      • 广播：一对全部的通信模式
        必须有表示全体接收者的ID/发送节点对每个结点单播
      • 组播：一对多的通信模式
        必须有标识某个组成员的ID
    • 点-点网络：由许多一对对计算机之间的链路组成
      • 多跳传输， 消息需要借助其他结点辅助完成
    • 小型，位置集中->广播
      大型，位置分散->点-点网络
  • 电路交换网络 包交换网络
    • 交换
      • 主叫和被叫必须建立一条专用网络
      • 通信器件该电路保持连接并不为他人用
    • 基于电路交换的数据传输
      • 类似长途电话，按时间收费(链接建立就不为他用)
      • 硬交换，分成 20W 条线路就只能同时连同 20W 的链接
      • 优点：
        • 实时性好，传输时间+建立时间
        • 稳定的数据传输速率
        • 不存在信道访问延迟
      • 缺点
        • 不能充分发挥传输介质潜力
        • 长距离连接的建立过程长
        • 扩展性较差(硬件成本)
    • “存储-转发”技术
      • 存储-转发：交换节点接受并存储包， 然后根据包的目标地址转发到通往目的地的出境线路上(处理速率小于包文到达速率，必须存储)
      • 报文 vs 数据报/包
        • 报文：用户发的原始数据(文件)
        • 数据报包：数据块大小固定
        • packet： 数据报，包，分组
          文件分成多个packet
      • “存储-转发”时延：处理时延(处理+发送包)+排队时延(包排队等待发送)
        现在处理时间极小可以忽略看作 发送+排队时间
      • 包交换并发传输
      • 包交换技术优点：
        • 宽带有效利用
        • 链路故障可选择其他链路
      • 包交换技术缺点
        • 存储，排队延时
• 如何评价计算机网络：
  • 传输能力：带宽/吞吐量： 信号的频带宽度 单位赫兹Hz，通信线路允许通过的信号频带范围
  • 数据率/比特率： 传送数字信号的速率， 单位bps ，每秒二进制位传输数量
  • 传输速度
    • 延迟：一个报文/包从一个网络(或一条链路)的一端传送到另一端所需要的时间。
    • 发送时延/传输时延： 使数据块从节点进入传输介质的时间
    • 传播延迟：信号在信道中传播一定距离而花费的时间(传播延迟 = 信道长度 / 电磁波的传播速率)
    • 处理时延：交换节点存储转发儿进行必要处理所花费的时间时延（包处理，路径选择，排队）
  • 丢包率：丢失的包与发送的包的比率
  • 吞吐量：发送者和接收者之间传输数据获得的比特率
  • 瓶颈链路： 制约着端-端吞吐量的那条链路

第三讲

• 计算机网络协议的要素
  • 语法：数据结构，编码和信号电平等
  • 语义：用于协调和差错处理的的控制信息
  • 时序：传输速率匹配和事件先后顺序
• 服务分类
  • 有连接服务：类似于电话，本质是一个管道，需要双方共同参与， 根据数据发送时是否保持原样又分为两类
    • 报文序列： 保持发送数据边界（发送方分四次， 接收方收四次）
    • 字节流： 接收方的报文不需要保持数据边界
  • 无连接服务： 类似于邮政服务
    • 无确认： 用户不能确定接收方是否收到
    • 有确认： 用户能确认接收方是否已经收到
• 如何使用下层服务
  • 原语
    • Request， Indication， Response， Comfirm
    • （上）发送请求， （下）通知发生某事件（给另一个上层对等实体）， （另一个上）做出回应，（下）报告另一个上层对某事的响应
  • 参数

第四讲

通讯系统模型

• 传输系统： 一条传输线路或一个复杂网络
• 网卡： 同时具备发送和接收
• 直接数据通信
  • (1)输入信息 m （2）输入数据 g(t) （3） 传输信号 s(t)
  • (4)接收信号 r(t) (3) 输出数据 g’(t) （6） 输出信息 m’
  • 数据通信发生在两个通过某种点点传输戒指直接连接的设备上
  • 发送信号和接收信号不一定一样，有能量消耗
• 间接数据通信
  • 数据通信发生在两个通过某种传输系统间接连接在设备上
• 信道通信方式
  • 单工通信： 在任何时候只允许按照一个方向传输信息
  • 半双工通信： 通信双方可交替地向对方传输信息， 但任何时候只允许在一个方向上传输
  • 全双工通信： 允许在两个方向同时传送信息

信号 数据 与 传输

• 数据： 涉及事物的形式， 定义为携带有意义的实体
• 信号： 是数据的电子或电磁编码
  载波： 运载数据的载体

• 传输： 通过信号的传播和处理进行的数据通信

• 数据 —— 模拟与数字

  • 数字数据： 具有离散的值
    Morse 码， ASCII 码
  • 模拟数据： 在某个时间间隔内具有连续值的数据
    声波
• 信号 —— 连续与离散
  • 连续信号： 由连续可变电压表示
  • 离散信号： 由一串特定电压表示
• 信号 —— 模拟与数字： 对应于连续与离散
• 信号 —— 周期信号
  • 振幅
  • 频率， 周期
  • 相位： 信号出现的时间
    根据两个波出现的时间差区分
  • 傅立叶变换： 任何一个行为合理周期为 T 的函数 g(t) 都可以表示成由正弦函数和余弦函数组成的级数
    时域->频域
• 数据传输途径 —— 模拟信号
  • 用模拟信号传输表示数据
    电话
  • 数字数据转换成模拟信号 调制解调技术
• 数据传输途径 —— 数字信号
  • 数字传输： 模拟数据 编码解码技术
• 传输系统分类
  • 模拟传输： 指介质上传输的是模拟信号(先在几乎都是)
    • 不考虑其内容模拟信号传输
    • 长途传输需要放大器
    • 放大器会把已失真信号中的噪声一起放大
  • 数字传输： 指截至传输的是数字信号
    • 涉及信号内容的传输
    • 长途传输时采用中继器
    • 中继器还原真实数据后再生成信号(现在都用中继器处理模拟信号)

信道容量

• 信号的强度
  • 信号的耗衰： 输出电功率小于输出电功率， 就说信号在传输系统中遭到耗衰
  • 信号的增益： 输出电功率大于输出电功率， 就说信号在传输系统中得到增益
  • 计量单位： 分贝
• 传输减损
  • 信号衰减： 信号幅度的降低就称为信号衰减
  • 延迟失真： 信号波形的畸变称为失真
• 噪声： 实际通信系统中客观存在的干扰源
  • 噪声的危害： 信号变形失真， 信号强度衰减
  • 噪声的度量： 信噪比 10lg（S/N）
    S 平均信号功率
    N 噪声功率
• 信道容量
  • 数据速率： 每秒多少个二进制位 bps
  • 带宽： 被传信号所占频带的宽度， 以每秒多少个周期表示 或 Hz
  • 比特率： 单位时间内传送的比特数
  • 波特率： 单位时间内波形个数
  • Nyquist 准则
    • C = 2WlogL
      C 数字信道容量 W 带宽 L 代码用的进制数
  • Shannon 定律
    • C = Wlog（1+S/N）
      C 模拟信道容量 S 信号功率 N 噪声功率 W 带宽

数字编码

• 数字化： 模拟数据转数字信号

• 基带传输： 基本频带信号， 来自信号源的信号

  • 计算机输出的文字图像
  • 电话原始语音
• 通带信号： 把基带信号经过载波调制后，把信号的频率范围搬移到较高的频段以便在信道中传输(即仅在一段频率范围内能够通过信道)
  不同频道可以不互相干扰
• 数字数据 VS 数据信号
  • 直接传输数字信号
    • 有失真但是可识别
    • 失真大， 无法识别
  • 不归零(NRZ)
    • 不归零 NRZ-L： 正负电压表示两个二进制位
      比特率 = 波特率
    • 不归零反转 NRZ-I： 在一位事件内维持已常量电压脉冲
      0 在一位时间开始处没有变化
      1 在一位开始处变化
      
    • 优点： 简单， 带宽利用率高
    • 缺点： 缺少同步能力 （一长串 0 或 1 易逝的接收端错位）
  • 双相编码
    • 曼彻斯特： 在每一位中间有一个跳变（接收器同步）
    • 差分曼彻斯特： 数据定义成每一位起始处是否存在跳变
  • 相位彼岸花解决信号接反问题
    跳变解决同步问题
• 数字数据 VS 模拟信号
  • 数字调制： 把低频数字信号变换成适合于信道传输的处理过程
  • 数字解调： 逆操作
  • 调制解调： 把低频信号变换成高频信号以便于数字信号的传输，即将待传信号的频谱进行搬移和还原
  • 基带传输的调制方式
    • 调幅： 如 0 振幅为0， 1 振幅为特有振幅
    • 调频： 频率快慢区分
    • 调相： 前后两个波出现的时间， 相位不同
• 模拟数据 VS 数字信号 ： 编码解码技术
  • 数字化一定失真
  • 脉冲编码调制
  • 增量调制
• 模拟数据 VS 模拟信号
  • 模拟调制
  • 为什么要对模拟数据调制
    • 对于无线传输， 无法传送系带信号
    • 有了调制解调技术， 可以进行多路复用

第五讲

• 决定网络特性的主要技术

  • 传输数据的传输介质
  • 连接各种设备的拓扑结构
  • 共享信道的介质访问控制方法

• 本地回路 vs 中继线

  • 本地到城控， 双绞线
  • 端局之间：光纤

传输介质 vs 多路复用

传输介质

• 传输介质分类

  • 引导性介质（线缆介质）： 电磁波沿着一个固态介质传播
  • 非引导性介质： 提供了传输电磁信号的手段， 但不引导

• 引导性介质

  • 双绞线（理论不超过 100m ， 信号强度衰减）
    • 非屏蔽双绞线
    • 屏蔽双绞线
    • 直连(电脑-设备) vs 交叉(电脑-电脑)
  • 同轴电缆
    • 两种道题共享同一根中心轴： 铜芯->绝缘层->屏蔽层->塑料外套
  • 光纤
    • 传输的是光信号， 而不是电信号
    • 光源为发光二极管和激光
    • 多模光纤 vs 单模光纤
      • 单模光纤： 一条线缆只包含了一条光纤， 使用注入型激光二极管
      • 多模光纤： 数条光纤以不同角度来回反射传播（便宜，单段的距离短）， 使用发光二极管
    • 不可肉眼直视光纤
    • 光的传输： 光子在纤芯中传输的方式是不断的全反射
  • 电线

• 非引导性介质

  • 无线电
    • 射频信号的能量由天线和收发器决定
    • 能穿透墙壁， 到达普遍网络线无法到达的地方
    • 不受雨雪天气干扰
    • 可全方向广播， 也可定向广播
  • 微波： 发射能量定向
    • 地面系统： 利用定向抛物线在较低的 GHz 范围内收发信号
    • 卫星微博系统：在定向抛物线和天线之间传输信号
  • 红外线
    • 不能穿越障碍物
    • 点-点： 光束高度集中， 朝特定方向发送
    • 广播： 将信号扩展到一个更广的区域， 允许信号由几个接收器同时接收
    • 不穿透， 安全性高
  • 可见光
    • LED 和 显示屏， 照明光源
    • 利用路灯下载电影
    • LiFi
    • 其他：
      • 二维码
      • 车灯信号通信….

• 传输介质总结

  • 影响选择介质的因素： 成本， 传输速率&带宽， 距离

多路复用

• 多路复用的需求
  • 大多数个人数据通信设备要求相对低的数据率
  • 数据速率越高传输设施的成本就越有效
• 多路复用器：
  • 复用： 将来自 n 条输入线路的数据结合在一起， 发送一条高容量数据链路
  • 分用/解复用
• 关键： 多路信号汇合后， 接收端必须能正确的分割
• 分割信号的一句： 信号之间的差别
  • 频率上的不同 -> 频分多路复用
  • 信号出现时间上的不同 -> 时分多路复用
  • 信号码型结构上的不同 -> 码分多路复用
• 频分多路复用：每个数据信号被调制到具有不同频率的载波上，所有的信号在一个信道上同时传送。
  • 发送端： 调制解调器调频
  • 接收端： 带通滤波器->解调器
• 波分复用： 光的频分复用
• 正交频分多路复用：
  • 正交性： 信号重叠但不会干扰。
  • 信号（函数）的正交性
    • 例如 sin(t) 和 sin(2t) 正交
• 如何实现频分多路复用
  • 调制解调技术：
    • 数字调制： 当只有模拟传输设施可用时
    • 模拟调制： FDM 需要把相同频谱的输入搬移到不同频谱

• 时分多路复用：一时间作为分割信号的依据。利用每个信号在时间上交叉，可在一个传输通路上传输多个数字信号（或运载数字数据的模拟信号）。
  • 发送端： TDM 帧
  • 关键： 发送方和接收方必须严格的同频同相
  • 复用器输出线路容量 = 复用起输入线路容量之和
  • 总时间 T 划分的时间片数 N = 复用器输入端的低速线路数
• 时分多路复用应用
  • 高速数字线路的多路复用

• 码分多路复用
  • CDMA 特点：
  • 每个站使用整个频段发送信号(同频)
    • 多个站的信号可以线性叠加(同时)
    • 利用编码技术分离并发的传输
  • CDMA 关键： 接收端能提取出期望的信号，同时拒绝所有其他的信号，并把这些信号当作噪声。
  • CDMA 重要特征： 允许所有用户在同一频带上同一时间片内同时发送信息，但需要使用不同的码字。
  • CDMA 正交性
    • 码片序列的正交特性： 任何两个不同的码偏序列 S 和 T 的归一化内积为 0

第六讲 数据链路层概述与流量控制

• 向网络层提供的服务
  • 无确认的无连接服务
  • 有确认的无连接服务
  • 面向连接的服务
• 帧： 在数据链路上交换数据的单位
  • 如何识别帧的开始
  • 帧传错， 丢失， 重复怎么办
  • 来不及接收怎么办
  • 回复确认还要发送数据如何
  • 共享介质如何访问控制

链路层的实现

• 网卡硬件/固件和驱动程序
  • 软硬件两个部分
  • 衔接物理层和网络层6

如何形成数据帧

• 涉及的问题
  • 将上层数据包按照所用协议规定的格式封装成一定形式的帧
  • 考虑接收双方的问题
  • 计算帧的校验和并放入帧中一起传送给接收方以便差错校研
• 字符计数法
  • 用第一个字节说明帧的长度
• 字符填充的首尾定界法
  • 标志放在帧的头尾
  • flag 出现在内容内： 加入转义字符
• 比特填充的首尾定界法
  • 比特填充： 每发送五个“1” 插入一个 “0”， 接收时删除填入的0
• 物理层编码违例法
• 通常采用综合法
  • 用计数值确定帧尾
  • 检查帧定界符是否出现在应该出现的地方
  • 计算校验和来验证是否传输的数据出错

流量控制

• 流量控制：用来确保发送 实体发出的数据不会覆盖 接收实体已接收的数据
• 限制发送方放松速度的一种机制， 使发送速率不能超过接收方能处理的速率
• 流量控制的特点：
  • 动态的：
    • 流量速度与发送方速度相关
    • 流量速度与网络当前拥挤程度有关
  • 反馈的： 使发送方了解接收方当前处理能力
  • 网络层实体控制从数据链路层接收数据速率
  • 数据链路层控制从对等实体接收帧的速率
• 停——等流量控制
  • 停等式控制： 发送尸体发送一个帧， 接收实体收到后发回一个对该帧的确认， 表示同意接受下一个帧；发送实体必须等待收到确认后才能发送下一个帧。
  • 半双工
  • 优点：
    • 控制简单
    • 适用于当包被分成数量不多较大帧发送时
  • 缺点
    • 效率不高
    • 当一个包用多个帧发回等待
    • 链路的比特长度大于帧长时： 链路的大部分时间空闲
      
      链路的比特长度： 信号从链路一端传播到另一端的时间，以发送比特数计量
  • 利用率 传播时延 p， 发送时间 f
    
    U = f / (2p + f)
• 为什么要分拆数据包
  • 可能的原因：
    • 接收缓冲区大小受到限制
    • 传输的数据越长， 出错的可能性越大， 重传的数据量也越大
    • 一个站不能占用信道时间过长， 一面导致其他站的长时延
• 利用传播延迟连续发送 n 帧
  • n = 1 + （传播延迟/发送一帧的的时间）

基于滑动窗口的流量控制机制

• 滑动窗口控制：利用发送和接收窗口来控制连续发送的数据量
• 控制工作描述：
  • 两个站（T，R） 全双工
  • 每个站为 n 个帧分配缓冲区
  • 为每个发送的帧分配一个序号（必须）
• 序号空间及其特性
  • 序号空间
    • 帧序号的取值范围
    • 通常协议规定了帧格式中表示序号的二进制比特数
  • 序号空间的循环特性
    • 被发送的帧按顺序编号
    • 当用尽最大序号后下一帧的序号回到 0
• 发送窗口： 给出允许发送站发送的帧序号
• 接收窗口： 给出允许接收站接收的帧序号
• 发送窗口和接收窗口可以不一样大， 窗口不是输出/输入缓冲区，只存放待发送/接收帧的序号
• 流量控制方式
  • 肯定确认帧： RRn
    • 准备接收从 n 开始的帧
  • 否定确认帧： RNRn
    • 已经接收知道 n-1 的所有帧， 但不能再接收了
• 捎带确认技术： 既有数据又有确认时，将两者合在一个帧中发送，即以数据帧捎带上确认信息。
• 累计确认技术： 接收方可对接收到的 K 个帧发一个 ACK 告知发送方已正确接收前 （K-1） 帧并期待第 K 个帧
  • 时机：
    • 当收到的帧数达到某个值或接收第一帧开始等待的时间超过某定值时， 要单独发送 ACK， 以免发送方因超时而重发
    • 当收到的第i帧有错时，则马上用 NAK 应答
  • 需要考虑：发送窗口的大小以及发送方丢失确认
• 性能：
  • 当窗口大小 N > 2a + 1：不停并发运行， 效率最大 100%
  • 当窗口大小 N < 2a + 1：会出现等待

• 推广： 管道化技术

  • 管道化技术：发送端为达到信道最大效率必须连续不断地发送数据
  • 带宽与延迟乘积：用来衡量两个进程之间信道的容量。（吞吐量）
  • 如果发送方没有填满管道就停下来等待接收方的确认，发送方就无法充分利用网络资源

    差错控制

• 检错和纠错

• 顺序到达： 指保证所有的帧最终都按正确的发送次序到底目的地
  • 确认方式
    • ACK 肯定确认
    • NAK 否则确认
  • 计时器
    • 计时器值的设定要保证一帧到达对方并作处理后， 相应的确认帧返回
    • 计时结合序号才能保证每一帧的正确次序

介质访问控制（MAC）

• 广域网： 点-点链接， 不存在信道竞争问题

• 局域网： 多路复用信道， 即多个站点共享同一个传输介质

• 介质访问控制： 在广播信道中， 当信道的使用产生竞争时如何确定信道使用权

• 寻址
  • 硬件地址（物理地址）：每个网络接口设备在出厂时都有一个全球唯一的固定值

第七讲 差错控制与差错检测

差错控制

• 正确接收： 帧按发出的次序到达， 且每个帧有不定长的传输时延
• 检错能力： 当发现错误时， 丢弃错误信息并要求重新传输该信息

• 纠错能力： 当发现错误时， 就地立即加以改正

• 自动重发检测 ARQ

  • 纠错编码： 在信息序列中根据某种规则加入一定校验码
  • 发送方根据被传送的数据信息， 按一定规律加入一些校验码， 使数据和校验码有某种相关性， 然后一起发送给接收方
  • 接收方根据数据与校验码之间的规律进行检验， 确定是否出错并返回结果

停等式 ARQ

• 发送方仅在收到当前帧的肯定确认后才能发送下一帧
• 发送方发出数据破坏可能导致地址信息出错， 有时无法给出错误回复， 需要设置超时重发
• ACK 丢失/破坏时发送方需要重传时，发送方会重发，如果没有编号接收方会认为重发的帧是下一个帧从而导致错误， 因此停等式 ARQ 也需要帧序号（1bit 即可）

连续式 ARQ

• 回退-N ARQ
  • 控制策略： 发送方连续发出 N 个帧， 一旦某个帧有错， 丢弃该帧和它之后的所有帧
  • 顺序收发方式： 接收方只能按照帧的序号接收数据帧
  • 窗口越大越好， 但要比序号空间少 1
  • 特点：
    • 要求每一帧的确认在其后第N个帧尚未结束发送之前到达
    • 发送方必须有存放N帧信息的缓存以便出错时重发
    • 接收方只要求存放一大小的缓冲区
    • 全链路双工
    • 优点： 消除了停—等ARQ的等待应答时间
    • 缺点： 正确帧的重发无疑浪费了信道
• 选择重传 ARQ
  • 控制策略： 一次连续发送 N 个帧， 发现有错时反馈要求重发帧的序号， 其余正确帧被接收方存储
  • 确认全部丢失的情况下， 前一个发送窗口和后一个接收窗口的序号空间不能出现重叠， 窗口大小 w ≤ 序号空间大小 m/2
  • 特点：
    • 接收方必须有足够的存储空间以便缓存 (N-1) 个帧
    • 接收方的接收顺序可能会打乱原发送顺序
    • 全链路双工
    • 优点： 信道利用率高
    • 缺点： 实现复杂， 接收方要有足够空间

差错检测原理

• 差错控制的根本措施：采用抗干扰编码（纠错编码）
  • 码组： n 个码元 组成的 01 串的每一组合
  • 信息码： 代表爆文的 0 和 1
  • 校验码： 插入的 0 和 1
• 一般来说，校验码引入越多，检错纠错能力越强，但信道的传输效率下降也越快
• 码距： 两个码组对应码位码元不同的个数
• 汉明距离： 一个码组集合中任意两个码组间的最小码距
  • 为了检出 e 个错码，汉明距离 d ≥ e + 1
  • 为了纠正 t 个错码，要求码集的汉明距离 d ≥ 2t+1
  • 为了检出 e 个错码，同时能纠正 t 个错码，则应满足 d ≥ e + t + 1 (e > t)
  • d ≥ 2t+1, d ≥ e + 1, d < e+t+1 时不能同时检错2位和纠错1位
    • 例子 A: 000 B: 111
    • d = 3, 可以检验两位错， 可以纠正一位错
    • 但只能同时约定一个功能， 即在可能两位出错的信道内， 不能进行纠错， 在需要纠错1位的情况下不能检验出两位出错（会讲剩下一位纠错）
    • 而 A:0000 B:1111 在两位出错的情况下可能报告错误， 在只有一位出错的时候可以直接纠错 此时 d≥e+t+1
• 编码效率： 指一个码组中信息所占的比重， 用 R 表示（衡量编码性能的重要参数）
  
  R = k/n = k/k+r

奇偶校验

CRC 循环冗余校验码

• 码多项式及其算术运算 C(x)
• 循环码形式： 对于一个码长伟 n， 数据码为 k 位的循环码（n, k）构成为：
  
  1 2 … k k+1 k+2 … n
  
  每个码多项式的前面k项与待编码的信息多项式相同
  
  后面r=n-k项与校验码元序列对应的校验多项式相同
• 循环码的生成多项式
  • 定理:在一个(n，k)循环码中，存在一个且只有一个(n-k)次的码多项式 g(x) = x^n-k + g_(n-k-1)x^(n-k-1) + …. g_2 x^2 + g_1 x + 1
  • 满足下列两个条件:
    • 此循环码中任一码多项式都是g(x)的倍式
    • 任意一个(n-1)次或(n-1)次以下又是g(x)倍式的多项式必定是此循环码的一个码多项式
  • 生成过程：
    • 设生成多项式G(x)的最高幂次为r=n-k
    • 将待编码码元序列表示为m(x)，乘以x^r，结果左移r位x^r·m(x)
    • 用G(x)去除 x^r·m(x)，求得商式Q(x)和余式R(x)
    • x^r·m(x) + R(x) = Q(x)·G(x)
    • 取等式左边对应的信息码为实际发送的码
    • 用 m(x) 计算 R’(x) 检验是否与 R(x) 相等
  • 不能检错

汉明纠错码

• 一般的， r 个监督关系式指示一位错码的（2^r-1）种可能的位置
• 对(n, k)分组码，监督位数 r =n-k;
• 若用r个监督位构造出r个监督关系式用来指示一位错误的n种可能位置， 则
  • 2^r-1 ≥ n
  • 2^r ≥ k + r + 1 （汉明公式）
• 汉明码:码长为n = 2^r –1的线性分组码(n, k) 即(2^r –1, 2^r –1–r)码

第八讲 局域网概述与IEEE802.3协议

IEEE802体系结构

• 局域网的两个特性
  • 用带地址帧来传送数据（广播网络， 指明目的对象）
  • 不存在中间交换
• 局域网所需要的层次
  • 层1: 物理连接必须
  • 层2: 通过局域网传送的数据必须组成帧并进行一定控制
  • 层3: 不需要中间节点存储转发，不需要第 3 层
• 将 DL(Data Link) 分为二个子层
  • 逻辑链路控制层(LLC)： 面向上层， 提供服务接口
  • 介质访问控制(MAC)： 面向具体介质， 采用不同访问控制机制
• 各种MAC与LLC的界面保持一致：LLC子层与所用介质、介质访问方法无关， MAC子层却和介质密切相关

介质访问控制技术

• 针对共享介质
• 访问控制技术：
  • 同步：为每个站点分配一个专用规定的传输容量，类似 TDMA 和 FDMA
  • 异步： 动态分配每个站点的传输量， 响应用的即时需求

异步控制的实现方法

• 分布式： 由各站点共同完成介质访问控制， 动态确定站的发送顺序
  • 优缺点和集中式相反
• 集中式： 制定某个控制器拥有网络访问的权利
  • 优点：
    • 提供优先权等其他功能
    • 每个站的逻辑相对简单
    • 避免协调问题
  • 缺点：
    • 单点故障会影响全网
    • 易形成瓶颈
    • 降低效率增加传播延迟

共享介质访问控制

假设：

• 流量独立产生
• 仅单信道可用（控制和数据都在同一信道）
• 冲突可观察到
• 连续时间发送（任意时间点发送）
• 按时间槽发送（固定时间点发送）
• 载波侦听（发送前先检查信道是否为空）
• 非载波侦听

竞争系统及其三大问题

• 竞争系统： 多个用户以某种可能导致冲突的方式共享共用信道的系统
• 三大问题：
  • 访问时机
  • 冲突检测
  • 重试策略
• 用户节点通过一公用频带采用随机方式与中心节点相连
• 中心节点用另一专用频带采用广播方式向用户节点传播信息

纯ALOHA协议

• 基本思想：不按时间槽 —— 不监听 —— 随机重发
• 假设 —— t: 发送一帧所需的平均时间
  • 设发送开始时间为 t0+t
  • 则 t0～t0+2t 为冲突危险区
  • 冲突危险区:在此期间有两个(或更多)帧发送将导致冲突
• 性能分析：
  • 轻负载下，冲突较少，故重传很少
  • 重负载下，冲突较多，故重传亦多
  • 能够期待的信道利用率最多为18%
  • 提高效率： 减小冲突危险区

分槽ALOHA协议

• (时间槽)发送 —— 冲突 —— 再(时间槽)发送
• 假设
  • 时间槽长度 ≥ 1帧时
  • 各节点只能在下一时间槽的 起始时刻开始发送信息。
• 冲突危险区减少一半
• 能够期待的信道利 用率最多为36%
• 关键: 所有用户必须同步

载波侦听多路访问(CSMA)

• LAN 主要特性: 站间传播延迟 < 帧的传输时间
• 载波侦听协议: 网络站点监听载波是否存在(即有无传输)并随之采取相应的行动。
• 基本思想
  • 要传输的站点首先听一听介质 上是否有其他站点在传输(载 波侦听)
  • if 介质忙，then 必须等待; else 传输
• 影响协议性能的因素: 帧的长度和传播延迟
• CSMA 协议的三种形式
  • 1-坚持 CSMA：
    • 若介质空闲，传输
    • 若介质忙，一直侦听直到空闲马上传输
    • 若发生冲突，等待一个随机长的时间
    • 冲突可能性大
  • 非坚持CSMA
    • 若介质空闲，则传输
    • 若介质忙，不再侦听信道，等待一个随机时间
    • 容量可被浪费无法有效利用
  • P-坚持 CSMA
    • 若介质空闲，则以概率P传输，以概率(1-P)把此次传输推迟一个时间槽
    • 若介质忙，等待一个时间槽
    • 适用于分时插槽信道

      带冲突检测的CSMA协议

• CSMA/CD 协议
  • 若介质空闲，则传输
  • 若介质忙，一直监听直到信道空闲，马上传输
  • 若检测到冲突，立即停止传输;等待一个随机时间
• CSMA/CD 模型
  • 竞争:发送站检测到正发送帧冲突的最短时间
  • 传输:发送站传输帧
  • 空闲:所有站都处于静止状态(无帧发送)
• 如何确定竞争是否胜出
  • 设A和B是两个相距最远的节点 ，并且A到B的传播时延为τ.
  • 等2τ长的时间未听到冲突才能确信竞争成功可以继续发送。
• CSMA/CD 与 CSMA 性能比较
  • CSMA/CD的信道利用率高于CSMA
  • 一个帧所对应的时间宽度:T = 15188/(10106) ≈ 1.2ms
  • 最大端-端的往返传播延迟:2τ = 1500*2/0.77C ≈ 13us

IEEE 802.3 协议

• 介质访问规则
  • 802.3采用 1-坚持 的 CSMA/CD
  • 如果介质空闲，则传输
  • 如果介质忙，继续监听;直到介质空闲马上传输
  • 如果在传输期间检测到冲突发送一简短的JAM信号
  • 发出JAM信号后，等待一随机时间;从头开始
  • JAM信号(“冲突加强”信号): 4~6字节 （保证所有站点能看到冲突）
• 冲突检测过程 （PPT 29页）
• 冲突检测窗口
  • 冲突窗口： 开始发送帧后侦听到是否发生冲突的那段时间。
  • 2τ(+ tCD + tJAM ) （tCD是冲突检测所需的时间， tJAM是阻塞信号JAM的传送时间， 都可忽略）
  • 冲突处理
    • 立即停止发送帧的其余内容，并发阻塞信号JAM
    • 按后退算法计算重发时间延迟
    • 若重发16次仍不成功，则放弃

后退算法

• 二进制指数后退算法 BEB：
  • 平均等待延迟为: M_BEB = (2^i-1)*2τ (不是固定时间， 是随机的)（i为冲突次数）
• 截断二进制指数后退算法（Truncated BEB）
  • 平均重发延迟为： MBEN = (2^i-1)*2τ （限制 i ≤ 10）
• 冲突等待重发时间：每冲突一次，将等待窗口大小加倍；从该窗口中随机选择一个等待时间

MAC 帧结构

• PPT 34 页
• DA： 目标地址
  • 48b
  • I/G 地址类型标志： 0——但地址 1——组地址
  • U/L 管理权限位： 0——全局 1——局部
• SA： 源地址
  • 与 DA 长度相同， 一般只能是单地址
• PAD？
  • 为区分有效帧/垃圾802.3规定有效帧必须至少64字节长
  • 为了冲突检测规定了最小帧长为2τ*数据速率
• MAC 服务
  • MA_UNITDATA.request(DA, m-sdu（数据）, service_type) 发送
  • MA_UNITDATA.indication(DA, SA, m-sdu, receive_status) 接收
  • MA_UNITDATA_STATUS.indication(send_status) 给上层报告发送状态

快速以太网

交换机和集线器

• 冲突域:两个或以上站点同时发送将产生冲突的区域
  • 集线器（Hub）： 所有站点在一个冲突域内
  • 交换机（Switch）： 一个站点一个冲突域
• 内部结构
  • 集线器： 无法增加容量， 本质上等同于单根电缆的以太网， 一个比特在全网广播
  • 交换机： 站和交换机端口可以同时发送， 因而不需要 CSMA/CD

快速以太网

PPT 43页

虚拟局域/专用网

• 虚拟局域网
  • 由一些局域网网段构成的与物理位置无关的逻辑组，这些网段反映了用户的组织结构
  • 每个 VLAN 帧有一个明确的标识符，指明此帧的发送者属于哪个 VLAN
• 实现途径
  • 以太交换机
  • 交换机不会向虚拟局域网之外的站点传送广播信息
• 优点
  • 提高安全性
  • 均衡了负载
  • 限制广播流量
• 虚拟专用网 VPN：把局域网直接联至 Internet， 两个局域网之间通过虚拟链路相互连接
  • 扩展性好
  • 虚拟链路容量不能保证

第十讲 局域网互连与接入网络（顺序有调换）

网桥基本功能

• 工作在第二层， 处理单元 帧
• 两大功能： 过滤和转发
  • 过滤掉内部通信的帧
  • 转发局域网间的通信

IEEE 802.1 透明网桥

• 功能
  • 将一个LAN上的MAC帧中继到另一个LAN上
  • 如果两个LAN使用了不同MAC协议，那么网桥必须将入境帧的内容映射到符合出境LAN的帧格式中
  • 路由机制是一种称为生成树的技术
• 处理的 MAC 帧
  • 局域网路由帧
  • MAC 控制帧
  • 用户数据帧

802.1 过滤数据库

• 过滤数据库(哈希表):列出了port号与通过该port可达的全部站的地址信息。
  • port号 一组MAC地址 生存期
• 转发规则
  • 搜索数据库确定MAC地址是否列在某个port上(X或Y)
  • 如果没找到，则将该帧flooding到所有端口(除入境端口X外)
  • 如果目标地址列在某个端口y(≠x) 上则检查端口y处于阻塞还是转发状态 （阻塞： 只接收不转发）
  • 如果y不阻塞，则将帧转发到与y相连的LAN上

802.1 后向学习过程（构造路由表）

• 后向学习过程
  • 到达某个端口的帧其源地址域说明它来自那个入境端口所连的LAN方向(例如:从X收到a发给b的帧 -> 通过X可到达a)
  • 网桥根据该MAC地址更新过滤数据库内容(添加条目/更新方向)
• 老化计时器(生存期)
  • 当往数据库增加一新条目时设置该计时器(缺省300秒)
  • 当某个条目的计时器超时从库中删去该条目
  • 每当接收一个帧时将其源地址与DB作比较
    • 条目存在：如果需要更新方向则更新， 然后重置计时器
    • 条目不存在： 创建新条目， 设置计时器

虚拟局域网 802.1Q

VLAN 的工作原理

• VLAN 配置表： 指明通过哪些端口可以到达哪些 VLAN

接入网络技术

数字订户线路（DSL）

• xDSL 设计目标
  • 服务必须能在已有的三类双绞线本地回路上工作
  • 不能影响用户已有的电话和传真功能
  • 必须比56kbps快(传统的拨号上网)
• DSL 的传输特性
  • 用户独占到交换机的本地回路带宽
  • 用户上网的速率受制于交换机之间的距离

非对称 DSL （ADSL）

• 上下行速率不同（下行速率高）
• 应用：视频点播， 多媒体应用， internet 访问等
• 典型配置： 一个高速下行通道， 一个中速双工通道， 一个 POTS 通道

有线电视接入技术 CABLE

• 单向传播
• 混合光纤结构(HFC)系统： 中长距离使用光纤，连接到家庭使用同轴电缆。
• 通过线缆访问Internet
  • 利用有线电视系统接入Internet
    • 专用调制解调器
  • 线缆服务接口规范(DOCSIS)
  • 头端(简单的放大器→智能CMTS：Cable Modem Termination System)
  • 请求发送->头端发回允许发送的时间段->在时间段内发送
• 通过 FDM 实行双向通信
  • 下行上行速率不同
• 头端(CMTS)控制下行信道的使用
  • 采用TDM方式
  • 固定204字节数据包(纠错码+184字节有效负载)

CABLE VS ADSL

• ADSL 采用星形结构
  • 每个用户具有固定独占带宽
  • 点-点通信模式
• CABLE 采用总线形
  • 带宽由一群用户共享
  • 基于广播机制
  • 上行和下行数据必须加密
• 就访问Internet而言，ADSL和有线电缆的相同性多于差异 性，它们提供的服务类似。

PPP 点到点协议

• 可选功能
  • 差错纠正
  • 流量控制： 不是PPP发送者控制传输速率，而是高层协议控制将包传给PPP发送的速率。
  • 顺序性
  • 多点链路
• 标准组成： PPP是一个可用于调制解调器、比特串行线路、SONET和其他物理层的多协议成帧机制。
  • 明确的成帧方法
  • 一个 链路层的控制协议
  • 一组 网络层的控制协议
• 工作过程
  • 建立物理连接
  • 选择 PPP 参数
  • 配置网络层（如：获得 IP 地址）
  • 交换数据
  • 撤销网络层
  • 断开连接
• PPP 帧格式
  • flag addr control protocol（2） payload CRC（2/4） flag（1B）
  • 字节填充技术：在信息字段，若出现flag模式则在前面加一个转义字符01111101;对于 信息字段出现转义字符也作相同的处理。
• PPP 信息帧
  • protocol：
    • 0XXX 网络层协议
    • 1XXX 协商其他协议
• LCP帧:用来协商最大帧长、认证协议等。
• NCP帧:协商报头是否压缩;协商IP地址
• PPPLCP 功能
  • 协商选项： 哪些字符用于转义， 是否发送地址字段， 是否压缩协议字段
    • 一方提出， 一方响应是否接收
  • 关闭线路
  • 拒绝请求
  • 测试线路质量
  • 调试

第九讲 无线传输与IEEE802.11协议

无线传输问题

无线传输的范围

• 传输范围(TX_range) 成功接收帧的通信范围，取决于发送能量和无线电波传输特性。 （发送模式）
• 侦听范围(PCS_range) 可检测到传输的范围，取决于接收器灵敏度和无线电波传输特性。（发送模式）
• 干扰范围(IF_range) 此范围内节点发送帧将干扰接收方的接收并导致丢帧。（接收模式）
• 隐藏节点问题:由于距离太远而导致一个站点无法检测到介质竞争对手的存在。
  • 隐藏节点能够干扰接收方但不能侦听到发送方。
• 暴露节点问题:由于侦听到其他站点的发送而误以为介质忙导致不能发送。 （B->A C->D）
  • 暴露节点能够侦听到发送方但不会干扰接收方。

IEEE 802.11 体系结构

• 802.11满足与其他有线802.x系列的无缝融合
  • 应用程序感觉不到任何不同(除了带宽低、接入时间长)
  • 无线节点的高层协议(应用协议、 TCP、IP)与有线节点的高层协议一样
• Basic Service Set (BSS) 一组能相互通信的站点
  • 独立BSS(Independent BSS) 各节点只能直接通信，网络没有中继功能
  • 有架构BSS(Infrastructure BSS): AP(接入点)提供到有线网络连接的中继功能，站点之间不能直接通信（全部通过 AP 中转）
• IEEE 802.11 协议栈
  • PHY： 无线传输信号等规范
  • MAC： 寻址方式   访问控制   帧校验码生成/检查

IEEE 802.11介质访问控制

• 三大功能
  • 可靠数据传输
  • 访问机制控制
  • 安全保障机制
• 基本访问机制
  • 基于CSMA/CA的强制基本功能
  • 避免隐藏节点的可选功能
  • 实时服务的无冲突 polling 方法

使用 CSMA/CA 的基本 DCF

• 冲突避免
  • 随机回退
  • 优先级确认协议
• 如果介质持续为空的时间大于 DIFS，则节点可以立即访问介质
  • 网络负载较轻时可缩短访问延迟
  • 网络规模增大时需要其他机制的协助
• 如果介质为忙，则等待一段随机时间
  • 等待介质为空并等待DIFS时间
  • 从竞争窗口中随机选择一个等待时间
  • 等待时间结束后再次侦听介质是否为忙
• 随机后退(Backoff)过程
  • 指数后退算法:竞争窗口初始化为某个最小值，发生冲突时加大窗口，直到达到最大值。
  • 当介质空闲时间 ≥ 某个帧间间隔(视待发帧类别而定)和随机等待时间，则立即传输
  • 当介质忙，延迟直到(当前传输结束 + 某个帧间间隔)
  • 开始随机后退过程
    • 选择一个随机数 ( 0, CW)
    • 等待选择的随机数对应的时间
    • 侦听介质是否为空，重复上述过程
  • 使用后退过程延迟发送的目的:在于避免多个站点同时传输引起的冲突。
• 优先级 —— 控制等待时间的参数
  • 帧间隔定义了帧的优先级
    • SIFS (Short IFS)： 最高优先级
      • 用途： ACK CTS 轮询响应
    • PIFS (PCF IFS)： 中等优先级
      • 时间 SIFS + slot
      • 使用 PCF 时限服务
    • DIFS (DCF IFS)： 最低优先级
      • 时间 SIFS + 2slot
      • 异步数据服务
• 竞争窗口对DCF性能的影响
  • 当网络负载大时，竞争窗口越小，站点选择的随机值越接近。导致太多冲突
  • 当网络负载轻时，竞争窗口越大，站点等待时间越长。导致不必要延迟
  • 指数后退算法:竞争窗口初始化为某个最小值，发生冲突时加大窗口，直到达到最大值。
    • 不成功传输（无 CTS 响应）后 Cw 加倍
    • 成功后减半
• 公平性： 每个节点在下一次竞争时具有同样的发送数据机会
• 改进的随机后退过程
  • 后退过程中介质为忙时挂起backoff过程
  • 在当前帧传输结束后恢复后退过程
  • 即 累计已等待的时候 来缩短下次等待时间
  • 目的： 更公平

单播数据的可靠传输

• CSMA/CA + ACK
• 接收方在校验CRC正确时立即返回ACK， 没有收到ACK则随机后退后重传该数据帧

解决“隐藏”节点问题

• 解决办法:通过短的控制包预留带宽
• 带有RTS/CTS的扩展DCF
• RTS/CTS机制
  • 机制的使用是可选的
  • 每个802.11节点必须实现该功能
• 明确预留信道
  • 发送方发送“RTS(请求发送)”报文：接收方地址/发送数据帧时间/发送ACK时间
  • 接收方用“CTS”回应发送请求
  • CTS为发送方预留带宽的同时通告所有节点(包括隐藏的)
  • RTS和CTS长度很短，冲突的概率减少
• 避免“隐藏节点”冲突
• RTS/CTS机制
  • 所有侦听到RTS的节点等待足够长时间
  • 被请求节点(接收方)以CTS响应
  • 所有侦听到 CTS 节点等待足够长时间
• 如何应付无线链路高比特出错率
  • 解决方法:将长帧划分为较小的帧，逐个传输，逐个确认。

第十一讲 网络层概述与网络互联

网络层概述

• 网络层作用
  • 两个端系统需要一种命名和路由选择机制
  • 路由器沿着目标端方向转发数据包
• 端到端通信： 两个计算机系统传输实体之间的通信
  • 网络层在其与传输层的接口为传输层提供服务
  • 网络层是处理端到端数据传输的最底层
• 端到端 vs 点到点
  • 端到端
    • 传输层两个对等实体通信依赖于所在主机的网络层对等实体通信
  • 点到点
    • 任意相邻两个节点的通讯就是点到点的通讯， 由网卡完成
  • 网络层连接从源端到目标端包含了若干个中间系统
  • 数据链路层仅将数据帧从传输介质的一边送到另一边
• 网络层的功能
  • 报文的发送/转发
  • 路由选择/呼叫
• 路由器内部体系
  • 输入端口 + 输出端口 + 路由选择处理题 + 交换结构（连接输入输出）
• 网络层其他功能
  • 呼叫建立（面向连接）： 某些网络层需要所选路径沿途上的路由器，在真正数据交换之前握手协商状态信息(如序号、初始流控的窗口大小)。
  • 拥塞控制： 网络交通拥塞会增加包传输延迟，从而降低吞吐量。路由器要调节数据包通过网络的流动
• 网络层向传输层提供的服务
  • 无连接的服务
    • 认为通信子网总是不可靠的
    • 每个包携带完整的目标端地址
    • 没有排序和流量控制功能
    • 服务由少量原语组成
    • 主机进行差错控制和流量控制
  • Internet 边缘论
    • 一种功能如果需要应用知识或者帮助才 能完整和正确的实现，该功能就应该位于网络的端点。
    • 核心简单 边缘复杂
    • 一次发送确保中间每一步的可靠性
  • 面向连接的服务
    • 认为子网提供可靠的连接服务
    • 交换数据前必须建立网络层的连接， 连接建立时双方课协商服务参数，质量及开销
    • 具有排序和流量控制功能
    • 服务原语涉及连接管理，数据传输，差错控制，流量控制等
    • 路由器承担并完成差错控制，流量控制，排序等复杂的网络操作
  • 服务方式 —— 有连接/无连接 （不决定可靠性）
  • 可靠性（服务质量）

子网内部结构

• 包交换的实现技术 —— 数据报子网
  • 特点： 同一对端系统之间的数据报可能走不通的路径
  • 实现
    • 每个包必须包含目标端的完整地址
    • 路由器用一张表之处通向目标端的处境路线
    • 当一个包入境时， 路由器查找路由表并将包沿出镜线路发出， 无需修改包中的任何内容
    • 路由表内容： 目标端地址 / 出镜路线（下一跳） / 度量（体现连接质量 如 带宽等评判数据）
• 包交换实现技术 —— 虚电路子网
  • 流程： A 发出呼叫 - B 入境呼叫 - B 接受呼叫 — A 呼叫建立
  • 建立后 A->B 所有包通过这条建立的链路进行通信（不会改变）， 沿途路由器为这条链接预留资源（缓存等）， 这条链路就是虚电路
  • 特点： 同一对端系统之间的数据报遵循统一条路径， 路由器依据包头的虚电路号转发（不要求包中有完整的地址信息）
  • 实现
    • 虚电路（VC） 转换表
      • 建立虚电路时选择一个当前未用的最低虚电路号
      • 数据报包头包含一个虚电路号
      • 转发数据报时要修改报头中原来的虚电路号
    • VC 转换表的维护
      • 每当建立了一条新 VC 时在表中添加一项
      • 每当终止一条 VC 时在表中删去相应条目
    • 表项：
      • 入境： 入境线路（端口） + 虚电路号
      • 出镜： 出镜线路 + 虚电路号
• 数据报与虚电路比较（自己回顾）

用户外部操作

• 网络的使用方式 —— 外部操作
• 子网对外提供的服务
  • 有连接服务
    • 借点执行一个到另一个节点的呼叫请求
    • 提交给网络的所有报文都标识为属于某个特定逻辑连接，并被顺序编号
  • 无连接服务
    • 不仅独立处理报文，且不按序或可靠地传送报文
• 有连接服务 + 虚电路结构
• 有连接服务 + 数据报结构
  • 网络单独处理每个包。同一条外部连接上的不同报文可能走不通的路由
  • IP 之上的 TCP
  • 需要时在目标节点缓存包， 以便按正确次需递交给上层用户
• 无连接服务 + 虚电路结构
  • 用户看不到任何连接
  • 网络为传递报文在两站点之间建立虚电路
• 无连接服务 + 数据报结构
  • 用户传输不建立连接， 网络传输也不建立连接

网络互联

互联设备

• 中继器 —— 物理层
  • 特性：放大电子信号的低级设备。它将来自一个接口的比特简单广播到所有的其他接口。
  • 用于连接以太制式的总线式网络，起到扩展网络连接距离的作用。
  • 分类
    • 放大器： 单纯放大（噪声也放大）
    • 信号再生器： 先过滤掉噪声再放大
  • 缺点： 不具备检错纠错能力， 不能形成环路
  • 中继器的多级配置
    • 独立的冲突域变成一个大的公共冲突域
    • 主干Hub无法互连采用不同 Ethernet技术LAN
• 网桥 —— 链路层
  • 特性：接收整个帧传递到数据链路层做校验和检查。
  • 向下传到物理层转发到不同的网络
  • 按照帧的目标地址(MAC地址)转发帧
  • 通常有两类网桥:透明网桥，源路由网桥
  • 保持 LAN 各冲突域独立， 能互连不同的LAN技术， 理论上说用网桥建立多大的LAN没有限制
• 路由器 —— 网络层
  • 一种用于连接两个运行相同/不同协议的中间系统
  • 针对网络层地址协议(如IP地址)进行选择与判断
  • 需要有二层地址与三层地址的映射能力(地址解析)
  • 对相同高层协议提供多个网络/介质之间网络互连能力
• 路由器 vs 网桥
  • 路由器检查包头，并根据头包含的目标地址作出路由决策
    
    仅检查帧头，并不检查或修改帧包含的网络层包
  • 路由器当将包交给数据链路层时， 它并不了解也不在意包封装在以太帧或非以太帧中。
    
    网桥不知道也不在意它正从 802.x LAN转发到802.y LAN的帧包含什么协议的包
• 桥路器
  • 可同时作为网桥使用的一种路由器
  • 然后用物理地址发送数据
• 桥路器与路由器的区别
  • 如果数据库没有正确逻辑地址路由器就将包丢弃
  • 桥路器不识别逻辑地址时改用物理地址传输
• 网关
  • 用于连接两个异构的相互独立的网络
  • 网关有三种： 协议网关， 应用网关， 安全网关

互联问题 —— 分段与重组（其他下去自己思考）

• 问题的提出 —— 包的长度受到限制
• 分段技术:将大的包分成网络能容纳的一系列段，将每一段作为一个独立的包发送
• 透明分段
  • 分段策略： 包遇到同步过的子网时， 进入之前由路由器按子网 MTU 大小进行分段， 前面的分段对后面的网络透明， 离开子网时重组还原原始数据报
  • 如果小包走了不同路径到达不同的出口网关会怎么样？
  • 特点：
    • 出口网关必须确定何时收到全部小包
    • 所有小包必须经同一网关出口
    • 不断地分段与重组会增大开销
• 不透明分段
  • 分段策略： 任一中间网关都不重组， 必要时只进行分段， 仅在目标主机进行一次重组
  • 要求每个主机都能重组， 总的开销增大
• 重组
  • 方法： 一般采用树形结构编号
• 虚电路子网的互联
  • 数据报沿着特定路径发送
  • 每个路由器负责中继包并在需要时进行包格式和虚电路号转换
• 数据报子网的互联
  • 不同包选择的路由可能不同
  • 包的到达次序可能与发送次序不同
• 隧道技术
  • 隧道:在两个端点建立传输数据报的虚拟管道，使所传输的数据报不为途径的节点所知。通常采用封装技术.

第十二讲 路由算法及Internet路由体系

路由基本概念

• 源路由:在出发前确定/规划好路由。 需要完整信息
• 走一步看一步：
  • 可以获取全局信息
    • 每个中转站(路由器)指出到达目的地“最好”路由(独立计算)
    • 每个中转站(路由器)拥有全部的道路信息(拓扑结构)
    • 边走边确定下一步路线和走法
  • 不能获得全局信息， 可以获得邻居信息
• 路由器的内部结构
• 路由选择算法:给定一组路由器及连接路由器的链路，找出一条从源端到目标端的“好”路径。

  静态路由算法

• 非自适应
  • 不根据实测或估计的网络当前通信量和拓扑结构作路由选择。
• 最短路径选择
  • 测量路径长度的算法： 最小跳计数， 信道带宽， 传输延迟， 平均通信量
  • Dijkstra 算法
  • 优点：可以根据用户需求选择一条“最好”的路径
  • 缺点：
    • 必须事先获得全局的网络拓扑信息
    • 必须拥有每条连接路由器的边的状态信息（带宽 拥塞等）
    • 无法根据网络状态变化做动态调整
• 扩散法：尝试所有可能路由
  • 优点：
    • 尝试所有可能路由
    • 至少有一个包通过最小跳路由到达
    • 所有与源节点连接的 节点都被访问
  • 缺点： 包的拷贝呈指数增长

距离矢量算法 DV

• 通过和邻居交换路由信息，独立计算本地抵达所有目的地的每条路经距离，选择最短的那条路径作为目标路由。
• 特点
  • 分布的：每个节点接收来自与其直接邻接节点的路由信息，并执行路由计算， 将计算结果回传给直接邻接的节点
  • 迭代的
  • 异步的
• 距离矩阵
• 主要数据结构
  • 每个节点维护一张经过所有邻居到全部目的地的距离表
  • 一个节点能得到的信息
  • 与其直接相连的链路(本地链路)的成本
  • 来自邻接节点的路由信息
• 用估算延迟作为性能指标 ， 基于Bellman-Ford算法
• 优点： 好消息传得快
• 缺点： 无穷计算（慢收敛）

链路状态算法 LS

• 链路状态:每个节点在获得了全部网络拓扑信息的基础上独立计算到全部目的地的路由。
• 算法特性
  • 每个节点都有完整拓扑图
  • 每个节点维护到邻居的连通性与链路成本
  • 每个节点向网络中所有其他节点广播自己和邻居的连接信息
  • 每当接收到来自其他节点信息就用Dijkstra算法重新计算路由
• 延迟计算方法(在每个节点)
  • 发出去的包被盖上时间戳，记录其离开时间
  • 收到返回的肯定确认时，计算该包的延迟
  • 收到返回的否定确认时，更新包的离开时间
• Dijkstra 算法
• 执行过程
  • 发现邻接节点： 在一跳范围内广播一个HELLO报文，邻居的响应报文把自己的地址带了过来。
  • 测量链路成本： 收到ECHO报文后立即返回， 用来测试链路的往返时间 (延迟)
  • 封装链路状态包： 把本地链路(与邻居相连)成本以及邻居 ID 封装在一个报文中
    • 带序号 后发可能先到
    • 生存期
  • 广播链路状态信息：发送链路状态包的时机
    • 定期发送
    • 出现重大事件时
  • 计算新路由

• Dijkstra 缺点

  • 路由震荡： 路由来回切换， 造成路由不稳定

• DV 与 LS 比较

  • 消息复杂性
  • 算法收敛速度
  • 健壮性

    因特网路由体系

Internet 基本体系结构

• 用部分信息进行路由选择
  • 主机可把所有本地的数据报送给本地路由器，而把所有
    非本地数据报通过省缺路由发送。
  • 即使只有部分的路由信息，主机也能成功地传输数据报。
• 路由器系统组成了 Internet 的基本体系结构 。
• 相信路由指示道路的正确性和最优性
• 需要一种体系，允许某个组(Group)管理当地的路由器，当添加新的网络互连和路由信息时不必更改远程路由器的路由表.

原始 Internet 结构

• 原始Internet体系结构： 由少量集中路由器保存关于全部目的地的路由信息，其他大量的外部路由器仅包含部分信息。
• 优点： 本地管理者能够管理本地结构变化而不必影响 Internet 的其他部分。
• 缺点：
  • 会带来潜在的不一致性
  • 计算路由表的算法出错
  • 提供给算法的数据出错
  • 在把算法结果传到其他路由器的过程中出错

核心路由体系

• 核心路由器： 由Internet网络运营中心(INOC)控制
• 核心系统
  • 提供到所有可能目的地的可靠的、一致的且可信任的路由
  • 每个网点经过许可获得一个Internet网络地址，再把该地址通告核心系统
  • 核心系统内部互相通信以确保共享信息的一致性
  • 有一个中央管理机构监测和控制这些核心路由器，因而具有很高的可靠性
• 核心系统构成了整个Internet 网络，提供统一的网络互联。
• 多一跳问题:无论怎么选择核心路由器总存在多一跳的传输情况
  • 建立一个机制，允许非核心路由器从核心路由器处得到路由信息， 以便形成最佳的骨干网络
• 核心路由体系无法处理复杂网络:核心系统将不能与所有网络直接相连
  • 需要一个机制把隐藏的这些本地网络可达信息送给核心系统。
  • 自治系统的引入 AS
    • 不把互联网络看作多个独立的网络，而是当作一个独立的组织，所有该网点的网络处于这个组织的控制之下。
    • 特性
      • 可自由地选择其内部的路由体系结构
      • 收集内部所有网络信息， 并责成若干路由器把这些可达信息送给其他自治系统
• Internet路由体系： 使用核心体系结构，每个与之相连的自治系统都要 把可达信息送到Internet核心路由器

内部网关协议 IGP

• 内部路由器： 用来交换网络可达信息及路由信息算法的统称。
• 边界路由器： 除了内部网关协议， 还要和其他自治系统通信
• OSPF 开放最短路径优先
  • 开放性： 公开算法
  • 使用链路状态路由算法
  • OSPF 广播包： 每个邻居占一项
  • 广播包在整个 AS 内 泛洪
  • 安全性： 所有 OSPF 消息都经过认证
  • 多路径： 允许存在多条同等成本路径
  • 服务分类： 针对每条链路， 给出不同传输服务种类的多个成本
  • 层次性： 大型自治系统中的层次化 OSPF

外部网关协议

• 外部邻居： 两个交换路由信息的路由器分属两个AS。
• 内部邻居： 两个交换路由信息的路由器属于各自AS。
• 边界网关协议(BGP）
  • BGP会话:两个BGP路由器(“peers”)交换BGP消息
    • 广播到不同目的网络前缀的paths (“path vector” 协议)
    • 通过TCP连接交换消息（不能出错）
  • eBGP从邻居AS获取子网可达信息
  • iBGP将可达信息传播至所有AS内部路由器
• 基本操作
  • 分发路径信息
    • 一旦路由器了解到新前缀，它便在自己的转发表中创建到达该前缀的新条目
    • 会记录经过的路径上的所有自治系统， 防止出现回路。

第十三讲 Internet 互联协议

• 数据报子网
  • 每个数据报具有完整的地址信息
  • 同一对端系统之间的数据报可走不同的路径发送数据
• IP 沙漏模型
  • 上下很大（扩展性好）
  • 所有网络通信都要穿过细腰
  • Internet 核心网由细腰构成

IPV4 协议

• IP(Internet Protocol):提供了无连接、不可靠的包传递服务。
• IP标准
  • 全局编址
  • 封装和拆封
  • 分段和重组

IP 数据报

• 传统的硬件帧格式
  • 路由器要连接异构网络
  • 不同类型网络的帧格式不同
• 虚拟包
  • 一个独立于底层硬件的包格式
  • IP数据报(datagram)、分组、包
• 格式
  • 见图
  • 头以字计算长度而不是字节
  • TTL（Time to Live）： 可以防止垃圾报文在无限循环路由中堆积
    • 路由收到一次减少 1
  • 协议： 指明该 IP 包携带的协议
  • IP 头校验和： 只对 IP 头校验
• IP 服务类别
  • 字段 Precedence(优先级) D(delay) T(吞吐量) R(可靠性) C(成本) 0
  • D T R C 每次只能满足一个
  • 演化 ： 区分服务（字段： Type of Service + Notify）
• IP 选项
  • 记录路由选项
    • 选项中包含一个地址空表， 由所有处理过该数据报的路由器把自己IP地址填入表中， 路由器在指针所指的位置插入自己的IP地址
  • 源路由选项
    • 选项中包含一个IP地址序列来指定一条路由
    • 严格源路由—两个相邻地址必须处在同一物理网络上， 松散源路由—允许相邻两个地址之间跳过多个网络
  • 时间戳选项
    • 选项包含一个记录时间空表， 途径的每个路由器均在表中填入时间
  • 分段时选项的处理
    • 针对选项功能作不同的处理
    • 记录路由选项只拷贝到其中一个段中
    • 源路由选项必须拷贝到所有段中

IP 封装

• 多次封装
• IP 数据包分段
  • 每一段携带取之源数据包的部分数据， 具有一个类似于原包的报头
  • 头中 flag 字段： DF（是否允许分段） MF（当前包是否为最后一段）
  • 头中 fragment offset： 在源包重的位置
  • identific ： 分段时临时分配
• IP 数据报重组
  • 标准规定在目的主机重组

IP 编址

• 协议地址:协议软件定义一个与底层物理地址无关的编址方案，给每台主机分配一个唯一的地址。
• 用 IP 地址进行路由选择
• IP 地址层次及分类
  • 前缀： 确定计算机所属的物理网络
  • 后缀： 确定物理网络上一台计算机
• 四类地址， 点分十进制
  • A 类： 8位前缀， 网络太大
  • C 类： 24位前缀， 网络太小
• 特殊的 IP 地址
  • 保留地址： 一种特殊的地址格式，从不分配给主机。
  • 全0， 全1 等
• IP 子网编址
  • 子网编址:在分类体系中增加一级，将主机号进一步划分成子网号和主机号。
  • 子网掩码(subnet mask):用来确定子网划分的特殊比特模式;
• 无类域路由： 没有地址分类以及 子网划分概念的地址分配方法。
  • CIDR 的表示
    • 采用斜线标记法取代子网掩码(a.b.c.d/x)
    • IP地址/网络前缀比特个数
  • CIDR 促进 IPv4 地址空间有效分配
    • 将A类地址分成几个大小不等的IP前缀
    • 将几个C类IP地址聚合成一个网络前缀
    • 路由聚合:将具有相同网络前缀的地址合并成CIDR地址块
  • 最长前缀匹配规则:路由器在转发数据报时，如果有多个路由表项的 前缀有重叠，则选择与目标地址具有最长地址前缀的路由(即具有最 少主机IP地址的前缀)
    详细的优先

IP 数据报传递

• IP数据报转发
  • 网络一般配置
    • 每个路由器与两个或更多个物理网络直接连接
    • 主机通常只与一个物理网络连接
• 直接投递： 在一个物理网络上，数据报从一台机器直接被传送到另一台机器。
• 间接投递:发送方必须把数据报发送给某个路由器，由该路由器把数据报转发到目的网络。
  • 基于路由表
    • 决定网络地址的子网掩码
    • 目的地的网络地址
    • 下一个转发路由器的IP地址
  • 省缺路由： 如果路由表中没有目的地的路由信息，则把数据报发送到一个缺省路由器上。
  • 缺省路由适用于本地与互联网只有一个连接时的配置。
• IP 的成功与不足
  • best-effort 传递服务： 虽然可能出错， 但满足边缘论
  • 异构性， 扩展性
  • 变革的动机：

IPV6 协议

• 特点： 灵活性和安全性
  • 简化的报头和灵活的扩展
  • 内置的端-端安全认证和加密
• 特点： 即插即用和QoS
  • 地址的自动配置（接电自动生成）
  • 支持服务质量QoS： 提供不同服务水平的服务
• 特点： 移动计算
  • 节点通信使用 IP 地址
  • 数据报的转发依据是 IP 地址
  • 网络应用通常由两个端点的 IP 地址标示
  • 当节点移动时必须改变IP地址才能正常通信，节点地址的改变将中断当前服务
  • Mobile IP 切换 AP 时自动切换服务
• 报文格式： 基本头
  • 区分服务
  • 流标签
  • Payload Length
  • Next header （可扩展头部）
  • Hop limit （等于 v4 中的 TTL）
  • 没有校验和
• 扩展头格式
  • 下一个扩展头或上层报文
  • 适应可变长的扩展头内容
  • 引入原因
    • 经济性： 将数据报的功能划分到单独的头可节省空间。一个数据报只用很小的一个子集。
    • 扩展性： 如要为协议增加一个新的功能只要定义一种新的next header类型和格式;
• IPv6 逐跳头选项
  • 逐跳头(hop-hop header):给出了要求沿途每个路由器必须检查的信息。 用于传递超过64KB的数据报(巨型数据报)
  • 固定头的 Payload Length 必须为 0
  • 路由器将丢弃长度小于 65535 字节的包（返回一个 ICMP 报文）
• IPv6 路由扩展头
  • 路由扩展头(routing header):给出了包必须经过的一个或多个路由器 (类似IPv4的松散路由)。
• IPv6 分段扩展头
  • 分段扩展头(fragment header):给出了分段重组所需要的信息。
  • 每段组成
    • 新的基本头
    • 分段扩展头（偏移量， 不分段则没有）
    • 数据区域
  • IPv4 路由器负责分段
  • IPv6 发送数据报的主机负责分段
• IPv6 编址
  • 冒分十六进制
• IPv4 向 IPv6 过渡
  • 隧道技术的应用
  • v4 封装进 v6 的包或反过来
  • 原地址位隧道入口， 目的地址为隧道出口

    第十四讲 Internet 控制及地址管理协议

Internet 报文控制

ICMP

• ICMP协议
  • ICMP报文封装在IP数据报的有效负载部分
  • ICMP报文的最终目的地是处理它的 Internet 协议软件模块
  • 格式： 类型 + 详细信息 + 校验和 + data
• 特点
  • ICMP不是高层协议
  • ICMP不具备可靠性和优先级
  • 携带ICMP报文的IP数据报传递出错时不再报告
  • 携带ICMP报文的IP数据报与携带用户数据的IP数据报具有完全相同的路由选择
• 工作过程
  • 当数据报产生差错时ICMP向数据报的源端汇报差错情况
  • 源端必须把差错交给一个应用程序或采取其他措施来纠正
  • 不会通知路径路由器， 因为当前路由器不知道该报文实际应该走哪条路由
• 功能
  • 可达性检测：
    • 主机或路由器向指定目标发送ICMP ECHO请求报文，请求报文包含 一个可选的数据区
    • 收到ECHO请求报文(8)的机器应立即回应一个应答报文(0)，应答报文包含了请求报文中数据的拷贝
    • 示例： ping 指令
  • 目标端不可达报告： 当路由器无法投递包时（如主机关机了）
    • 向远端发挥一个目标端不可达报文， 并丢弃该数据报
  • 拥塞控制
    • 拥塞形成的原因
      • 高速计算机产生的通信量比网络能传输的报文多时
      • 许多计算机发送的数据报同时需要通过某个路由器时
  • 重定向路由
    • 主机的路由学习能力
      • 假定路由器知道正确路由
      • 主机从最少路由信息开始逐渐从路由器了解新的路由信息
    • 当路由器检测到主机使用了一条非优化路由时就向主机发送一个重定向的ICMP报文，请求主机改变路由，同时转发初始数据报。
  • 检测循环路由
    • 应付错误路由/丢包
      • 一旦路由器因数据报的TTL计数器为0或主机等待包重组超时而丢弃该数据报时，向源端发回一个ICMP超时报文。
      • 包重组超时： 分段后一小段超时则丢弃余下的（下次重发可能走不同的路由分段也不同）
  • 报告其他问题（如不正确的数据报头）
  • 传送时间估计值
  • 请求子网地址掩码
• 应用实例
  • trace route 工具， 利用 ICMP超时 报文发现到目的地一条路径上的路由器列表。
  • 用 ICMP 发现路径 MTU
    • 利用数据报头的 “不能分（DF）” 标志位
    • 途经路由器无需对数据报进行分段
    • 目的主机无需重组完整数据报

地址解析技术

• 直接投递和间接投递
  • 发送/转发报文时
    • 网络不知道IP地址后缀与特定计算机的关系
    • 物理网络硬件不知道如何用协议地址来定位一台计算机
• 包投递 vs 帧发送
  • LAN内通信
    • 主机A发一个包给B
    • A网络层把IP包交给下层(802.3)
    • A网卡把该IP包封装在802.3帧发给B
  • LAN外通信
    • 主机A给主机F发一个包
    • A网络层把IP包交给下层(802.3)
    • A网卡把该包封装在802.3帧发给R1
• 地址解析技术
  • 将 IP 地址解析成相应硬件地址的过程
  • 一台计算机只需要解析连在同一网络上计算机地址
• Internet地址解析协议(ARP)
  • ARP request
    • 广播： 请求 IP 地址为 D 的物理地址是什么
  • ARP reply
    • 单播： 返回 MAC 地址
  • 格式：
    • 硬件地址类型 + 协议地址类型
    • 引入了硬件地址 和 协议地址的长度
  • 特点： 可用于任何硬件协议和软件协议（扩展性好）
• ARP的缓存技术及优化策略
  • ARP消息的处理
    • 从接收到的消息中取出发送方的地址绑定信息
    • 检查消息中的“操作”字段确定收到的是请求/应答消息
  • ARP的高速缓存(ARP表)
    • ARP有一个高速缓存，用来存放最近获得的IP地址与硬件地址绑定信息

动态地址分配

动态主机配置协议（DHCP）

• DHCP协议
  • 允许计算机快速、动态地获取IP地址
  • 只要有新计算机连到网络，新计算机就与服务器联系并申请一个地址
  • DHCP服务器从管理员指定的地址中选择一个未分配的地址，并将它分配给该计算机。
  • 动态地址分配是临时的
• 报文格式
  • Code(53) + Length(1) + Type(1-7)
  • discover： 广播
  • 使用 UDP 发送

NAT 协议

• 内联网及私有地址
  • 私有地址:不能用在Internet上(路由器将丢弃寻址这种地址的包)的内部地址。
  • 特点：
    • 可以任意分配IP地址
    • 所用的IP地址仅本地有效
    • 所用的IP地址可被不同企业重复使用
    • 节点不能与外部Internet上的节点通信
  • 好处
    • 无需申请全球合法的IP地址
    • 网络规模完全自主选择
• 虚拟专用网： 内联网的互联
  • 利用隧道技术将内联网包封装成 Internet 上的 IP 包
  • 前提： 每个内联网必须拥有至少一个合法IP地址的路由器
• 网络地址转换协议(NAT)
  • 引入NAT协议的动机
    • 增加内部网络的安全性
    • 内联网用户需要访问Internet
    • DHCP只能部分缓解IP地址资源的不足
    • 小型企业和家庭用户需要全程在线连接Internet
• NAT 设备 —— NAT 路由器
  • 负责源IP地址和目的IP地址转换
  • 地址转换可以静态或者动态设置
  • 针对出境包源地址进行替换
    
    (源IP地址, port #) -> (NAT IP地址, 新port #)
  • 在NAT转换表中记录映射关系
    
    (源IP地址, port #) -> (NAT IP地址, 新port #)
  • 针对入境包目标地址进行替换
    
    (NAT IP地址, 新port #) -> NAT转换表(源IP地址, port #)
• NAT 实现 —— 地址转换表
  • 对于入境包，路由器以目的port号作为索引查找转换表，以对应的源IP/Port置换回去
  • 转换表中的条目动态加入并在空闲超时后删除
  • 对每一个 IP+端口的组合 分配一个新的端口号

地址转换协议

第十五讲 IP 组播技术概述

组播基本概念

• 一对多， 多对多， 有反馈的一对多
  • 强调一次通信
• 应用层组播
  • 特点：
    • 网络层没有组播功能
    • 发送这对每个接受者采用单播传输（需要知道所有接受者）， 不是一次通信
• 网络层组播
  • 特点：
    • 发送主机仅发送一个包
    • 一旦这个包需要转发到多条出境链路上， 路由器就复制该包的成本
• 网络层的组播与单播
  • 与单播路由的相同之处： 路由算法在网络层仍发挥着重要作用
  • 与单播路由的不同之处： 处理组播包的路由器必须建立和维护组播连接的状态信息
• 组播地址标示
  • 在数据报中列出所有接收者的地址
    • 数据报中的地址信息将远远超过其有效负载中的实际数据
    • 发送者必须知道所有接收者的标识及地址
  • 间接方式组播
    • 每一组接收者有一个“标识符”
    • 将包传送到与该“标识符”相连的所有接收者
    • D类地址： 组播地址
• 网络层的一对多通信
  • 路由器具有网络层知识， 是实现组播的最佳位置
  • 网络层实现组播可节省网络带宽，对应用层透明
• IP 组播地址
  • D 类地址
    • 224.0.0.0 - 239.255.255.255
    • 224.0.0.0 - 224.0.0.255 保留为特殊地址
    • 239.0.0.0 - 239.255.255.255 私有组播地址， 类似于 IP 的内网地址
  • 永久组播地址(用于本地组播)
    • 如： 224.0.0.1:LAN上的所有系统
      224.0.0.2:LAN上的所有路由器
  • 临时组播地址
    • 为某个网络应用临时创建的组播组
    • 主机可动态加入到/退出某个指定的组
• 组播路由器
  • 了解所有本地链路上是否存在组成员
  • 用组成员来标识这些链路(以便转发组播包)
  • 建立路由组播包的状态
    • 必要时在某些网络接口复制数据包
    • 构建组播路由条表中的相应条目
• IP组播体系结构
  • IP组播基本思想
    • 组播发送者向组播地址发送数据包
    • 组成员告知本网段的路由器它们需要接收哪些数据包
      • 通过组管理协议进行
    • 发送者和接收者之间的路由器构造组播树
      • 组播包沿该树到达接收者网络
      • 组播树由组播路由协议构造
    • IP组播的组成
      • 组管理协议工作在网络边缘的路由器及附接主机之间
      • 组播路由协议工作在组播路由器，确保相关路由器能收到组播包

IGMP 协议

• 组管理协议： 用户进程通过该协议提出加入/退出某个组的请求
  • 组播路由器通过该协议了解本地哪些主机加入了哪些组。
  • 路由器将为这些组创建组播传输所需的组播树
• Internet组管理协议(IGMP： Internet Group Management Protocol)
  • 工作在主机与其直接相连的路由器之间
  • 主机用它来通告它想加入某个组播组
  • 路由器用它来发现所连网络上是否有主机属于某个组播组
    • 每个接口维护组成员列表并定期检查成员是否还存在
  • 直接相连路由器:第一跳和最后一跳路由器
• IGMP 报文类型
  • 路由器：
    • 查询主机是否在某个特定组
    • 查询主机是否在任何组
  • 主机
    • 加入组
    • 退出组
  • 封装在 IP 包中
  • type（1）+ max.resp.time(1) + checksum(2) + Multicast group address

组播树类别

• 组播路由算法
  • 组播路由器功能： 在路由器之间共享组信息， 为组播数据报的分发提供路由
  • 组播路由目标
    • 找出一棵树，它连接所有附接主机属于组播组的路由器
    • 根据这棵树路由组播包从 发送者到达属于这棵组播树的所有主机
    • 注意:这棵树可能包含了没有附接主机属于组播组的路由器。

• 共享树

  • 共享树ST
    • 用二元组(*，G)表示
      • • = all sources
          G = Group
    • 以某个路由器为根(RP或Core)到所有接收者的树
    • 一棵树被多个发送者共享，维护较少的状态信息
    • 转发路径未必最优
    • 树根的位置很重要
  • 协议例子： CBT (core based tree)， PIM-SM
  • 组播路由问题
    • 只要找到一棵树，连接网络中所有附接主机属于该组播组的路由器。
    • 一类路由器的主机属于该组播组， 另一类路由器没有主机属于组播组
  • 汇集树（sink tree）： 生成树的一种
  • 特性：
    • 路由器上的存储量少 O (G)
    • 从源到接收者的路径非优： 引入额外的延迟 (源->根)
    • 可能重复数据传送 (从源根接收者的路径可能重复)
  • 适用于
    • 多数共享树与源树相同的环境
    • 有许多低带宽的发送者 (例如共享的白板)
  • 共享组播树构造
    • 在共享组播路由树中定义一个中心点(或称为核心)
    • 具有组播组成员的路由器向中心节点单播“join” 控制报文
    • 用单播路由转发“join” 控制报文（如果传到了某个已经在树中的节点时， 这个节点直接返回确认而不继续向上传）
    • join 报文经过的路径定义了发出该join报文的边缘路由器和中心节点的路由树。

• 基于源的树

  • 源树
    • 也称最短路径树(SPT)
    • 用二元组(s, G)表示，s为组播发送者
    • 以发送者为树根到每一个接收者的最短路径构成一棵转发树
    • 从发送者到接收者的路径最优，但需要维护较多的状态信息
  • 协议例子： DVMRP， MOSPF， PIM-DM
  • 源树组播问题： 在具有N个主机的组播组中， 需要构造N棵不同的路由树
  • 特性
    • 路由器需要更多的存储空间O (G * S)
    • 从源到接收者的路径是最优的(最小化延迟)
  • 适用于： 发送者数量较少而接收者大量的应用(例如无线电广播)
  • 最小成本路径树计算： Dijkstra
    • 这些路径的集合可形成一棵最小成本路径树。

组播路由技术

• 泛洪与修剪
  • 开始时以flooding的方式把组播数据报发送到全网
  • 修剪(prune)掉没有接收者(组成员)的分支
  • 协议实例: DVMRP, PIM-DM
• 基于链路状态组播协议
  • 路由器向全网广播拟接收的组
  • 根据自身需要各自计算组播树
  • 实例: MOSPF
• 基于核心树的组播协议
  • 标示一个会面地点 ——“核心”
  • 源端向“核心”发送组播报
  • 接收者加入以“核心”为根的树
  • 实例: CBT, PIM-SM
• 逆向路径转发(RPF)
  • 逆向路径转发(Reverse Path Forwarding):如果从R到s的数据报将通过a转发，则转发由a转发来的组播数据报。
  • 此处配合图理解
  • RPF在构造组播树中的作用
    • 用于构造组播树
    • 路由器接收到一个数据包，对它执行RPF检查
    • 路由器可以确保自己在 组播树中“入境”的路径只有一条，并且是到发送者最优的那一条
• 修剪和嫁接
  • 修剪过程
    • 一个接收到组播包的组播路由器，若其附接的主机没有属于该组播组，则给其上行流路由器发送一个 “prune”消息;
    • 如果一个路由器从其每个下行流路由器收到了一个修剪消息，则转发 “prune”消息到上行流;
  • 嫁接(grafting)
    • 一个组播路由器收到若其附接的主机发出的加入某个组请求IGMP消息，则给其上行流路由器发送一个“graft”消息;
    • 一个已在组播树中的路由器回复一个确认消息;不在组播树中的路由器则转发“graft”消息到上行流;

组播协议实例

• 组播协议
  • 域内组播(intra-domain)协议:自治系统内部用来转发组播报的树;
    • DVMRP • MOSPF • PIM-DM • PIM-SM
  • 域间组播 (inter-domain)协议:自治系统之间用来传输组播数据报的树。
    • MSDP • BGMP
• 协议一览： 见图

• DVMPR： 距离矢量 + 源树 + 泛洪&修剪

  • 组播采用推送push方式 -> (发送到每个网络)
  • 适用于组成员分布比较密集的“密集模式”
  • 实现了具有逆向路径转发、嫁接和修剪的“基于源的组播树”
  • 功能：
    • 计算下一跳
    • 计算下行数据流的路由器列表
  • 注意:基于距离矢量的路由机制没有全局拓扑信息
  • 工作过程(数据驱动)
    • 发送者的第一跳路由器开始向所有下行端口发送组播数据报
    • 中间的路由器对接收到的数据报进行RPF检查
    • 最后一跳路由器根据IGMP信息返回修剪/嫁接 一个分支
  • 基本操作： 邻居发现，路由交换，源树构造，组播转发，修剪， 嫁接
  • 控制报文
    • 修剪(prune)报文:包含一个修剪生存期指出被修剪掉的分枝将自动恢复的期限;
    • 嫁接(graft)报文:通知上行邻接路由器，强制先前修剪掉的分枝重新加到组播树中;
  • 部署： 只有一部分路由器具备组播功能，如何转发组播数据报?
    • 利用隧道技术可在混合单播路由器和组播路由器的物理网络上构造一个虚拟的组播路由器网络。

• 稀疏模式的协议独立组播(PIM-SM)

  • 组播报文采用pull方式(接收方驱动)
  • 组播树共享，每个路由器只能加入一个组的一棵树 (*，G)
  • 初始化时共享树就是汇聚点 (RP)
  • 离接收者(组成员)最近的边缘路由器向RP发送“注册”控制消息
  • 发送者(组播源)向RP注册，通过共享树发送组播包
  • 如果距离组播源的距离小于距离RP的距离，边缘路由器可通过发送(S,G)控制消息给组播源强制转换成一棵基于源的树

第十六讲 传输层和 UDP 协议

传输层概述

• 传输层协议能提供应用的多路复用/分用服务、可靠数据传送、带宽保证及延迟保证等
  • 传输层提供了应用进程之间的端-端连接
  • 网络层提供了主机之间的逻辑通道
• 为什么要传输层：根本原因在于网络不可靠
  • 网络层提供的无连接服务不可靠(丢包、重复)
  • 路由器可能崩溃
  • 传输线路中断
• 网络层协议处理主机之间通信的事务， 传输层协议处理应用进程之间通信的事务
• 传输协议面临的问题
  • 基于可靠有序的网络服务
    • 寻址(定位应用程序)
    • 多路复用(为多个应用服务)
    • 流量控制(发送接收匹配)
    • 连接建立/释放
  • 基于不可靠的网络服务：除了上述还有
    • 有序传送
    • 重传策略
    • 重复检测
    • 系统崩溃恢复
• 传输层的服务
  • 面向连接： 大多数面向连接的服务提供了可靠的通信
    连接与可靠性是两个不同的概念。
  • 无连接： 大多数通信是不可靠的
    • 适用于： 内部数据收集， 外部数据发布， 请求 - 响应， 实时流媒体应用
• 传输层的多路复用与分用
  • 分用:当传输层从网络层接收数据后，必须将数据正确递交给某个应用程序。
  • 复用:当传输层从应用程序接收报文后要封装在传输层的段中再交给网络层发送。
• 应用程序使用 socket 收发数据
  • 使用socket的通信过程
    • 应用程序将数据送入socket
    • 应用程序从socket提取数据
  • 传输层必须将网络层传来 的数据正确分发
• 传输层的端口(port)
  • 端口(port):用来标识某个特定的应用进程。
  • Socket具有唯一标识， 每个发出去的报文必须有字段描述递交数据的socket
  • 端口作用：
    • 应用层通过端口将数据交给传输层发送
    • 传输层通过端口将收到的数据交给应用层
    • 端口号仅本地有效
• 无连接的多路复用和分用
  • UDP socket 由二元组标识 <Dest. IPaddr， Dest. Port#>
• 重复型客户 - 服务器模型
  • 服务器在任何时刻只能为一个客户服务
    • 等待一个客户请求的到来
    • 处理客户请求
    • 发送响应给客户
    • 在此期间服务器不能为其他客户提供服务
  • 所有客户的请求在一个队列中排队
  • 服务器只需要一个 port
• 面向连接的多路复用和分用
  • 服务器可以同时支持多个socket
  • 每个socket与一个进程关联， 每个socket由四元组描述
  • TCP socket由四元组标识
    
    < Source IPaddr, Source Port#, Dest. IPaddr， Dest. Port# >
• 并发型客户 - 服务器模型
  • 服务器可以为多个客户提供服务
    • 服务器等待客户请求的到来
    • 启动一个新的服务器处理该客户请求
      • 新服务器对客户的全部请求进行处理
      • 处理结束后终止该服务器
  • 服务器有一个迎宾port负责“引导”
  • 每个客户都有自己对应的服务器

用户数据报协议

• 通信的最终目的地不是进程号而是协议端口
  • 进程的生成/消失都是动态的
  • 接收进程的变化对发送端透明
  • 由接收端功能来识别目的地
• UDP和TCP的最主要功能是将IP提供的主机-主机传递服务扩展到端-端的进程级
  • UDP 基本功能： 进程-进程数据传递 + 差错检测
  • TCP 基本功能： 进程-进程数据传递 + 差错检测 + 可靠数据传递（差错检测后对应处理） + 面向连接 + 拥塞控制
• UDP(User Datagram Protocol)提供了不可靠的无连接传输服务。它使用IP传输报文，但增加了对给定主机上多个目标进行区别的能力
  • 特点：
    • 没有确认机制
    • 不对报文排序
    • 没有超时机制
    • 没有反馈机制控制流量
  • 导致报文丢弃、重复和乱序
  • 使用 UDP 的应用程序要承担可靠性方面的全部工作
• UDP 报文格式： 源端口(可选(0)) + 目的端口 + 长度 + 校验和
  • UDP的校验和覆盖了UDP头和UDP数据
  • 当校验和为0时表示发送端没有计算校验和
  • 当计算出的校验和为0则用全“1”表示
  • 如果接收端计算出校验和有错则丢弃数据报
  • UDP的校验和提供了唯一对数据是否正确传送到目机的地的监督手段
• UDP的伪头
  • 伪头： 源IP + 目的IP + 0 + 协议（17） + 长度 （这部分在IP头中实际存在）
  • 伪头不实际传递， 只用于两次校验报文没有传错
  • 伪头对层次划分的破坏
    • 传输层如何获得网络层的IP地址?
• 最大UDP数据报长度
  • IP数据报的最大长度(65535字节)
    • 20个字节的IP头， 8个字节的UDP头， 理论最大 65507
  • 制约UDP数据报长度的因素
    • 大部分系统省缺提供读写8192个字节的UDP数据报
• UDP的复用分用和端口
  • 范围： 0~65535， 知名端口 0～1023
  • 混合式的端口管理模式
    • 端口号的集中式管理
      • 一个集中管理机构负责对端口的分配和发布
      • 所有软件在设计时都要遵守这些分配的规定
    • 动态绑定： 应用程序需要时网络软件便指派一个端口

• UDP 协议特性

  • 无需建立连接： DNS采用UDP;HTTP采用TCP
  • 无需维护连接状态(收发buffer、拥塞控制参数、序号和确认号等）：相比使用TCP来说可支持更多的client
  • 报头开销小： TCP 头20字节， UDP 头8字节
  • 应用程序可控制何时发送数据
    • TCP的拥塞控制机制阻止TCP的立即发送， 只能收到确认后才能发送后面的数据
    • 对于流媒体传输需要满足最小发送速率的需求

• UDP的适用场合

  • 流媒体应用(网络电话、视频会议等)可容忍少量的报文丢失，而在有拥塞控制的TCP上工作很糟糕
  • RIP定期更新路由表(5分钟)偶尔丢失可被更新的替换
  • SNMP要定期采集运行在不同的网络上的数据

域名系统（DNS）

• 域名系统(domain name system):将主机名、电子邮件地址、Web服务器名映射成IP地址的分布式数据库系统（工作在应用层）
• DNS特点：层次的， 分布式的， 基于域的(AS)的
• 主机名字的层次管理
  • edu com gov mil org net fr cn （顶级域名）
  • 每个区域对应一个负责该层次主机的管理授权中心
• DNS 功能
  • 提供名字呵地址的映射关系
  • 主机别名(aliasing)
  • 邮件服务器别名
    • 别名一般比规范名更易于记忆
    • DNS可返回对应的规范名和IP地址
  • 负载均衡
    • 例如:www.sina.com.cn 对应多个具有不同IP地址的服务器
    • DNS数据库包括所有的IP地址
    • 每次DNS查询将获得该组IP地址但次序是循环的
• 递归查询
  • 递归查询:当主机/名字服务器A向B查询，B将代表A执行查询请求并结果返回
  • 名字解析负担加到所有关联的域名服务器上，上层服务器负担越重
• 迭代查询
  • 迭代查询： 当主机/名字服务器A向B查询， B将返回下一个 DNS 名字服务器的 IP
  • 服务器返回有关服务器的名字:“我不知道这个名字， 你可以问这个服务器”
• DNS 的资源记录（RR）： 见图
  • 一台机器可以有多个功能
• DNS缓存与更新
  • 一旦服务器了解到一个名字地址便将这种映射关系缓存
    • 一定时间(TTL)后缓存的表项超时
    • 通常本地域名服务器缓存顶级域名服务器
      • 减轻顶级域名服务器的负担
  • 被缓存的映射关系可能过时
    • 提供的是best effort“名字-地址”解析服务
    • 如果某个主机修改了其IP地址，直到TTL后才能扩散到Internet

第十七讲 可靠数据传输与TCP协议

可靠数据传输机制

• 基于可靠通道： 传输层几乎不需要控制
• 基于不可靠网络
  • 不会丢失/可能出错，新增三种功能：
    • 差错检测
    • 接收端的反馈: ACK/NAK
    • 重传机制
  • 报文可能出错/ACK、NAK 可能出错（但不会丢失）
  • 报文可能出错和丢失、 ACK 可能出错和丢失（只用 ACK 可以完成可靠通信）
• 采用回退N协议的可靠数据传输
  • 增加三类事件：
    • 上层调用过程:是否成功取决于当前窗口大小
    • 收到ACK的处理:采用累计确认技术
    • 超时事件:重传所有的报文

连接管理

• 传输层连接模式
  • 面向连接
  • 无连接
• 与网络层虚电路的区别
  • 网络层的虚电路由每个路由器上的VC表项维护
  • 传输层的连接仅由两个主机上的传输实体维护
• 特点：
  • 每一端确保另一端的存在
  • 允许两端协商传输参数
  • 触发传输实体资源的分配
• 面向连接的网络通信模型
  • 无论网络层的虚电路/路由有无变化，传输层的连接不变。

连接建立

• 基于可靠网络服务的连接建立
  • “二次握手”方式
    • 发起连接请求的传输实体向另一方发送一个同步(SYN)请求
    • 对方传输实体将该请求排入队列直到传输层用户发出Open
      • 传输实体中断/向传输层用户发信号通知到达一个请求
• 基于不可靠网络服务的连接建立
  • 可能发生的错误情况
    • 连接发起方的SYN丢失
    • 连接接受方的应答SYN丢失
    • 出现重复SYN的情况
      • 发起方发起的SYN被延迟
      • 接受方的响应丢失
      • 接受方的响应被延迟
    • 解决途径:维护状态信息
  • 序号固定从0开始对连接的影响（PPT）
• “三次握手”的连接建立
  • A通知B发送的第 一段序号为i
  • B通知A发送的第一段序号位j， 并且明确表示知道A的初始需好
  • 一旦连接建好两个传输实体便可用任何滑动窗口协议实施流量控制。
  • 通信两端要保持有关连接的所有状态信息。
• 连接建立时初始序号的选择
  • 主机崩溃时
    • 所有保持的有关连接状态信息全部失去
    • 重新建立的连接必须采用不受之前报文影响的序号
  • 解决方法
    • 确保两个序号相同的报文永远不会同时有效
    • 主机恢复后等待T秒
    • 限制对序号的使用
    • T是报文生存期的倍数，用来确保报文发出去T时间后不再存在。
  • 基于时钟方法
    • 每台机器的时钟采用二进制计数器的形式
    • 连接建立时用时钟的低k位作为初始序号

连接释放

• 可靠网络服务之上连接释放
  • 非对称方式
    • 连接的任何一方均可向对方请求释放连接
    • 一旦该请求到达对方连接即告终止
  • 对称方式
    • 释放连接后不能发送数据但仍能接收数据
    • 只有在双方均释放连接后连接才算彻底终止
  • 释放连接只是关闭发送通道，仍然能接收数据。
• 不可靠网络服务上释放连接问题
• “三次握手”方式释放连接
  • 需要加入计时器
    • 发送方： 尝试 N 次超时后： 断开
    • 接收方： 超时后断开
  • 双方设立连接关闭超时计时器可，用来防止出现网络的物理故障

传输控制协议 TCP

• TCP( Transmission Control Protocol):可靠的面向连接的端-端字节流传输协议。
• 特性：
  • 面向连接
    • 只在两个端系统上保持连接状态
    • 不同于TDM/FDM
    • 不同于虚电路
  • 连接是全双工： 可同时双向传送数据
  • 连接是点-点： 只能一对一通信(不支持一对多通信)
  • 有缓冲的发送
  • 无结构的数据流
• TCP的字节流传输
  • 端-端之间不保留报文边界
  • 应用通过socket发出的数据被缓存在缓冲区
  • 何时从本地发出取决于具体TCP实现

报文格式

• 源端口 + 目的端口 + 序列号 + 确认号 + （各种其他信息)共2byte + 接受窗口 + 校验和 + 紧急数据指针
• TCP的最大段（Segment）长
  • 最大段长(MSS)： MSS太小降低网络利用率， MSS太大降低网络性能
  • TCP的Segment独立确认，IP的Fragment不能独立确认/独立重传
• TCP段编号以及确认号
  • TCP的接收数据特性
    • 为每个字节编号
    • 确认号为接收端等待接收的下一个字节序号
    • 采用累计确认技术
    • 缓存到达的乱序数据
• urgent发送和push接收
  • urgent数据的发送
    • URG强迫TCP发送当前数据流中的字节
    • URG指针指出urgent数据所在
    • TCP将PSH位置1使接收端执行urgent操作
  • 带外数据(out of band)（控制数据）
    • 允许发送方将数据标为urgent
    • 接收方收到urgent数据后通知相应应用程序进入“urgent”
  • 当应用程序希望不必等待另一端把数据流接收完毕 后就能发送带外(out of band)数据。
• TCP的窗口扩大因子
  • 当网络具备高带宽、高延迟特点时，一次发送64KB字节可能带来 发送的低效率。TCP用窗口扩大选项来加大每次发送的数据量

传输特性

• TCP的连接建立
  • TCP的连接建立采用“三次握手”方法
  • TCP采用基于时钟的序号产生方案(每4us)
  • 双方协商本次连接的初始序号
  • TCP协议用改进的“三次握手”来关闭连接
    • 每个方向连接单独释放, 超时值设定为2倍的MSL
• TCP的可靠性保证
  • TCP采用累计确认
    • 后续确认包含了之前传输正确的隐信息
    • 确认丢失不一定导致发送端重传
    • 累计确认的缺点：
      • 发送端不能收到所有成功传送的段的确认信息
      • 只知道已收到的数据流中的某一位置信息
      • 缺乏全部成功传送的信息 -> 累计确认的效率降低
  • TCP快速重传机制
    • 基于超时的重发机制不足:发送端等待一定时间才能重发可能丢失的段, 加剧了端-端的延迟
    • 快速重传:发送端检测到三个重复ACK立即重传该ACK所指的段，而不是等待该段超时后再重传。

第十八讲 TCP协议与拥塞控制

拥塞控制概述

• 非正式定义: 太多的发送源端给网络发送太快太多的数据
• 如果发生拥塞：
  • 队列延迟加大
  • 路由器的缓冲区溢出(丢失包)
• 局部拥塞会蔓延
• 拥塞-> 重发 -> 更拥塞
• 最大-最小公平:如果分配给一个流的带宽在不减少分配给另一个流带宽的前提下得不到进一步增长，就不给这个流分配更多带宽。
• 理想拥塞条件：
  • 要求所有的站点都能知道提交给网络的包的时间和速率
  • 当不同节点的队列长度增加时实际吞吐量呈下降趋势。
  • 限制每个节点的队列长度以避免吞吐量崩溃。
  • 拥塞控制技术无法达到理论上的理想值。

TCP 流量控制

• 流量控制： 流控只与发送者和接收者之间的端-端通信有关
• TCP 采用大小可变的滑动窗口协议， 由接受端通过 window size 字段反馈当前可接受的字节数
• TCP的流量控制——发送端
  • 维护一个变量“RcvWin”记录接收端能接收的字节数
  • LastByteSent:发送端发出的最后一个字节序号
  • LastByteAckd:发送端从网络接收的最后一个确认序号
• TCP的流量控制——接收端
  • 通过报文头的“window size”字段反馈给发送端接收窗口的大小值
  • LastByteRead:上层应用程序接收的最后一个字节序号
  • LastByteRcvd:接收端从网络接收的最后一个字节序号
• TCP传输性能问题
  • Nagle
    • 如果已传数据未确认之前发送端应用程序又生成了额外的数 据，则照常将数据放入输出缓冲区，但并不发送;
    • 直到缓冲区中的数据足够填满一个MSS;
    • 如确认到达后发送端仍处于等待状态，则发送缓冲区中累积 的所有数据。
    • 只有第一段是小报文，从而提高了发送端的数据传输效率。
  • “低能”窗口综合症： 当接收端的应用程序每次仅读一个字节时，接收端通告一个小的可用窗口值将导致发送端产生短段，发送端的段仅含少量数据
    • Clark 方法： CP对收到的段进行确认，但要等到接收窗口可用空间达到启发式策略所指定的限度之后才发出“窗口增大”通告。
  • TCP规范说明:
    • 发送端使用启发技术(Nagle)避免传输少量数据
    • 接收端使用启发技术(Clark)防止反馈微小增量 值的窗口通告

TCP 拥塞控制

• TCP采用端-端拥塞控制：限制发送端通过连接注入网络的流量
• 路由器的拥塞检测方法
  • 路由器通过监测出境线路和其他资源的使用情况
    • 路由器周期性地对出境线路的瞬间利用率进行取样f ，可得到u的近似值
    • 假设线路的利用率用实型变量u表示u的 取值范围在0.0~1.0之间。
    • u_new = a u_old + (1-a) f
    • a为常数。确定路由器忘记历史的最快速度。 7/8是经验值
    • 当路由器检测出线路利用率接近饱和时，通过某种隐式或者显式方式通知发送端降低发送速率。

• TCP如何知晓路径上发生拥塞?

  • “丢包事件”的定义
    • 段的计时器超时
    • 收到三个重复ACK(快速重传机制)
  • 当发生拥塞时，发送端和接收端之间路径上一个或者多个路由器的缓冲区溢出，导致数据报被丢弃
  • 数据报被丢弃可反映在发送端超时或者收到3个重复ACK
    • 被丢弃的包后面没有后续包/后续包被丢
    • 被丢弃的包的后续包到达目的地

• 确认时钟：确认返回到发送端的速率恰好是数据包通过路径上最慢链路的速率

  • 根据确认时钟，TCP可以平滑输出流量并避免路由器队列增长。
• TCP如何限制发送速率
  • CongWin:控制TCP发送速率的拥塞窗口
  • RTT:TCP段开始发送到ACK返回的时间
  • LastByteSent–LastByteAcked ≤ min{ CongWin, RcvWin }
  • 假设接收端缓冲区足够大忽略接收窗口因素， 在RTT开始发送CongWin字节， 在RTT结束时收到相应的确认
    • 发送端的发送速率近似为CongWin/RTT bps
    • TCP发送端通过调整CongWin来限制发送速率

TCP基于拥塞的速率调整算法

慢速启动(slow start)算法

• TCP连接建立时，壅塞窗口CongWin初始为一个MSS （后来改进为 4 个MSS）
  • 初始发送速率 = CongWin/RTT
• 在初始阶段按指数增长速度加大发送速率直到发生“丢包事件”
  • 每个 RTT 后 CongWin 大小加倍
• 发生“丢包事件”后将CongWin窗口 减半并重新开始慢速启动过程
• 确认时钟在发送端起到平滑发送速率的作用。
  • 多个包发送时的发送间隔（不是一下子全部发出去）
• 慢速启动 vs 线性增长
  • 线性： 在RTT时间内全 部ACK都返回拥塞窗口才增大1
  • 指数： 在RTT时间内每 返回一个ACK拥塞窗口就增大1 （全部返回就加倍）

AIMD 算法

• 拥塞避免(congestion avoidance):TCP拥塞控制协议的线性增加阶段。
• 逐步递增(Additive-Increase)
  • 每当经过一个RTT就将CongWin窗口增大一个MSS(maximumsegment size)
• 加倍递减(Multiplicative Decrease)
  • 一旦发现丢失段立即将CongWin窗口减半(最后减到1)
  • 对于保留在发送窗口中的段将重传计时器的值加倍

响应“丢包事件”

• 某个段超时
  • 发送端进入“慢速启动”阶段，拥塞发送窗口置为1个MSS
  • 按指数增长直到CongWin = 发生超时时的一半
  • 按线性增长(进入拥塞避免阶段)
• 三个重复ACK
  • 拥塞窗口减半
  • 按线性增长
• 慢速启动阈值（到达阈值之后就先行增长）
  • 用来统一管理拥塞窗口
  • 标志慢速启动的结束和线性增长的开始
  • 阈值(Threshold)的初始值较大

网络层拥塞控制

• 显式拥塞通知(ECN)
  • 当检测到发生拥塞时路由器在包头设置一个特殊的比特
  • 该特殊比特被接收端拷贝并“捎带”在ACK中发给发送端
  • 发送端监测带有警告比特的ACK的数量并据此调整传输速率
• 拥塞控制之抑制包
  • 抑制包方法
    • 由拥塞节点产生并发给源端
    • 发送端收到抑制包后以一定比例降低 发送速率
    • 实例:ICMP的Source Quench
  • HOP-HOP 抑制包
    • 每一跳都降低传输速率(即使抑制包未到达源端之前)
• 每一跳都降低传输速率(即使抑制包未到达源端之前)
  • 卸载方法
    • 当路由器被包所淹没时只能将包丢弃
    • 丢弃哪个包取决于应用以及数据链路层的差错控制策略
    • 应用程序打上丢包优先级标记，在发生拥塞的节点作为是否被丢弃的依据
  • 拥塞控制之随机早期丢弃(RED)
    • 路由器在缓冲区溢出之前就丢弃一个或者多个包

第十九讲 流媒体应用与传输协议

数字音频

• 如何将声频转换成数字形式： 模数转换器(Analog Digital Converter)
• 如何将数字值转换成声频： 数模转换器(Digital Analog Converter)
• 音频压缩技术
  • 语音： 8000次采样，量化为256(8b) -> 64Kbps （通常做不到）
  • CD:
    • 每秒44100次采样，获得22050Hz的频率
    • 量化为65536(16b)，单声道为705.6kbps，多声道为1.411Mbps
  • 未压缩的音频传输需要更多的带宽需求和传输时间
  • 数字化和压缩是多媒体网络应用得以展开的基本条件
• 压缩算法特性
  • 有损系统:解码输出信号不完全等同于原始输入信号
    无损系统:解码输出信号和原始输入信号完全相同
  • 压缩算法组成：
    • 编码:作用在源端，对数据进行压缩处理
    • 解码:作用在目标端，解压数据还原出原始信息
  • 压缩算法的非对称性
    • 压缩算法可非常复杂，解压算法要简单
      • 适应目前因特网的服务模式
      • 强大的服务器群vs.弱小的用户终端
    • 编解码过程可以不可逆
      • 压缩数据文件，解压出来的必须与原始数据完全一致
      • 压缩流媒体文件，解压出来的不一定与原始数据完全一致
• 音频压缩的两类方式
  • 波形编码
    • 通过傅里叶变换将信号转换成频率分量
    • 对每个分量的强度进行编码
    • 目的:在接收端以尽可能少的比特重现该波形
  • 感知编码
    • 利用人类听觉系统的缺陷对信号进行编码
    • 人耳听不出接收信号与原始信号之间的差异
  • 频率屏蔽:一段频率中较大的声音屏蔽了较弱的声音。
• 音频压缩过程
  • 音频压缩过程
    • 以8kHz~96kHz的采样率对声波进行采样
    • 采样可以对一个信道(单声道)或两个信道(立体声)进行
    • 确定输出比特率的分配
      • 给最大频谱功率的无屏蔽频段分配最多的比特
      • 给最小频谱功率的无屏蔽频段分配较少的比特
      • 不给任何被屏蔽的频段分配任何比特

数字视频

• 不压缩视频对带宽的需求
  • 针对640*480，像素用24位表示，播放速率30帧/秒
  • 所需带宽200Mbps
• 数字化图像的冗余
  • 空间冗余体现在图像中的许多空白部分可压缩掉
  • 时间冗余体现在连续两幅图像的重复部分
• 视频压缩技术
  • JPEG标准(联合图像专家组) —— 空间冗余压缩
  • MPEG标准(运动图像专家组) —— 在JPEG的基础上进行时间冗余压缩
• JPEG
  • 压缩比： 通常10:1， 可达到20:1
  • 4种模式
• MPEG的输出帧
  • I-帧(Intracoded frames)
    • 压缩的静止图片
    • 周期性地出现(1~2帧/秒)
    • 解码I帧类似于解码JPEG
  • P-帧(Predictive frames)
    • 与前一帧的逐块差值，解码要求缓冲前面的帧
    • 基于宏块(亮度空间的1616，色度空间的88)
  • B-帧(Bidirectional frames)
    • 与前一帧和后一帧的逐块差值

三种流媒体应用

• 三大类
  • 存储的流式音频/视频： 点播
    • 客户机按需请求存储在服务器上的被压缩音频文件或者视频文件
    • 三个关键特征：
      • 存储好的媒体： 用户可以暂停、反转、快进或根据内容跳进
      • 流式： 从客户机发出请求到实际播放等待1~10秒是可接受的
      • 连续播放： 播放开始后数据传输延迟必须与媒体原始录制匹配
  • 实况的流式音频/视频： 直播流媒体
    • 通常存在多个用户正在收看相同的音频/视频节目
    • 用户播放器不能快进媒体流
    • 实况音频和视频流分发的最有效方式是IP组播技术
    • 从用户发出播放请求到真正播放延迟10秒是可忍受的
  • 实时交互式音频/视频： 实时会议
    • 用户通过网络进行视频/音频交流
    • 语音延迟应小于几百毫秒
    • 要控制抖动
    • 延迟非常重要
    • 与端系统的距离长短有关(8公里的光纤延迟需要40ms)
    • 与报文长度有关(例如:将报文长度从1KB减小到160B， 单向延迟从181毫秒减少到62毫秒)

流媒体播放与RTSP协议

• 通过web服务器访问音频/视频
  • 浏览器作为媒体播放器与服务器连接的中间桥梁
• 播放器直接与web服务器联系：
  • Meta文件:提供了有关已流化的音频/视频文件的信息(URL或者编码方式)。
  • HTTP并不支持媒体流(暂停/恢复、快进以及跳转等)
• 流媒体服务器的引入
  • 播放器直接向streaming服务器请求文件
  • 播放器与媒体流服务器通过专用协议通信
• RTSP
  • 对播放操作加以控制， 而不定义数据格式
  • 媒体播放器和媒体流服务器用来 交换playback控制信息的协议。
  • 消息是带外发送的， 端口544， 可以通过 UDP 或者 TCP 发送
• 媒体播放器的功能
  • 解压： 播放时解压音频/视频流
  • 错误处理
    • 主要用来克服大量丢包造成的图像不连续
    • 两种主要技术:前向纠错(FEC)、交替发送
  • 抖动消除
    • 接收端通过缓冲包来消除延迟的变化
    • 抖动(jitter): 前后两个包的延迟差。
• 差错处理
  • 前向纠错： 定期构造奇偶包(P):由数据包生成
  • 交错编码： 发送前将媒体流混合或者交叉编码， 接收端做相反操作还原原始媒体流
• 实时性保证
  • 以播放所需的速率通过UDP发送音频/视频，媒体播放器一旦收到媒体流立即解压播放
    • 媒体播放器延迟5~10秒再播放，通过Client缓冲区消除网络引入的抖动
  • 通过TCP(尽可能快地)发送媒体流，把到达的媒体缓存在播放缓冲区中，并延迟5~10秒播放
• 抖动的危害以及如何消除抖动， 如何应对网络延迟变化： 设立高低水印标记

流媒体传输与RTP/RTCP协议

实时传输协议 RTP

• RTP(real-time protocol)协议
  • 用来传输流媒体数据的协议
  • 可支持PCM、GSM、MP3等公共语音标准
  • 可支持MPEG、H.263等公共视频标准
• RTP不具备以下功能
  • 不提供确保数据传输时间的任何机制
  • 不提供任何QoS保障
  • 不保证数据报的传输
  • 不保证数据报不乱序
• 特性：
  • 每个发送端可指定自己的独立RTP流(音频流、视频流)
  • 大多数编码技术(如:MPEG1/MPEG2)可将音频和视频数据编码在一个流中
  • 可用于“一对多”或者“多对多”通信
• 格式： 编码方式+媒体包序号+时间戳+所属媒体流ID

实时传输控制协议(RTCP)

• RTP的姊妹协议， 不携带任何音频/视频数据， 用来向同一个RTP会话的所有成员报告发送/接
  收的统计信息(通过IP组播)， RTCP端口号 = RTP端口号 + 1。
• 接收端： 在一个RTCP包中报告每个流的状况
  • 每个端都要报告
• 发送端： 针对每个流的报告
• 扩展性问题： 如果用户增多报告太多
  • RTCP消息的定期发送
    • RTCP根据当前RTP会话中的参与者个数动态调整发送RTCP消息的间隔
    • 将当前RTP会话带宽的5%用于RTCP消息
    • 其中全部发送端占用25%;全部接收端占用75%

流媒体应用示例

第二十讲 流媒体应用与服务质量

网络应用对网络服务QoS需求

• 影响多媒体应用的主要因素
  • 时间受限： 发送端到接收端高达几百毫秒的延迟包已无用
  • 丢失容忍度： 偶尔的丢失仅造成音频/视频播放的小停顿
  • 包的抖动： 相同媒体流中包延迟的变化
• Internet流量分类
  • 弹性流量:指那些延迟和吞吐量变化很大仍然能满足应用需要需求 的流量。
    • 通常关心延迟、吞吐量和可靠性
    • Best effort方式工作就很好
  • 非弹性流量:不能适应延迟和吞吐量发生变化的流量。
• 数据流对网络服务质量的需求
  • 流(flow):从一个源端到一个目的端的包流。
    • 流需求特征： 可靠性， 延迟， 抖动， 带宽
• QoS保证的提出
  • 过度配置:准备足够的资源以应付可能的需求, 例如电话系统。
  • QoS机制:用较低的成本来满足应用的需求, 例如因特网。

• 非弹性流量对网络体系新需求

  • 需要某种手段给予需求更多的优先待遇
    • 应用程序必须能在服务开始之前或之中通过IP包头陈述自己的需求
    • 在需求的表述上有更大的灵活性
    • 网络预先订下应用所需的资源并在所需资源不满足时拒绝新请求
  • 必须仍然支持弹性流量
    • 在拥塞期间，非弹性流量将继续供给高负载，而弹性流量将被挤出互联网络

• 流的隔离——链路级的包调度

  • 链路级的包调度机制:为每个应用流分配固定的链路带宽.
• 流的隔离——监管机制
  • 监管机制:在端系统或边缘路由器，将不遵守某种要求的应用数据包打上标记， 为将来的处理提供依据。
• 呼叫许可:获得网络许可或者阻塞的过程
  • 必须有一个呼叫准入过程。流说明自己的服务质量需求，获得许可进入网络或者阻塞进入网络。

调度机制

FIFO

• 包的链路发送次序与到达队列的次序相同
• 如果没有足够的空间存放新近到达的包，则丢包策略决定是否丢弃刚到达的包，还是删除已排入队列等待传送的包(牛奶?葡萄酒?)。
• 针对不同延迟到达的包,以固定速率输出

优先级队列

• 到达输出链路的包被分类排入不同优先级队列
• 优先级的确定可考虑多种因素
  • 包头的标记(ToS)、包的源/目的IP地址
  • 包的目的端口号等

公平队列

• 加权公平队列
  • 循环调度各队列i
  • 给每个队列赋予不同的权值Wi
  • WFQ保证给予类i一定比例服务 R * Wi / (∑Wj) 其中∑Wj是所有类的队列包总和

监管机制——漏桶

• 平均速率(average rate)： 限制了流的包注入网络的长期平均间隔
• 峰值速率(peak rate)
  • 限制了流的包注入网络的短期最大速率
  • 例如:平均速率6000/分钟，峰值为1500/秒
• 突发大小(burst size)： 限制在极短时间内注入网络的最大值
• 漏桶现象
  • 漏桶特征
    • 从桶底小孔向外漏的速率恒定
    • 一旦桶空外漏速率为0
    • 桶一满水从上面溢出
• 漏桶算法
  • 原理
    • 将主机用户进程输出的不规则包流转换为输入网络的均速包流
    • 主机与网络的接口为一个漏桶
    • 漏桶就是一个有限的内部队列
  • 字节计数漏桶算法（一个变种）
    • 每节拍初始时，计数器为n;
    • 如队列第一个包的字节数<当前计数器的值，则将其发送并修改计数器的值
    • 如果队列第一个包的字节数>当前计数器的值，则停止传输，等待下一节拍的开始。
  • 漏桶算法的缺点： 不管突发通信量的大小，输出速率保持不变。
• 令牌桶算法
  • 思想
    • 只有在令牌桶不为空时才能发送包
    • 每发送一个包漏桶内的令牌数减1
    • 漏桶满时新产生的令牌将被丢弃
  • 令牌生成速率为r， 令牌可以积攒， 可以应对一定程度突发
  • 可以以包计数也可以以k字节计数
  • 设:突发时间为s;令牌到达速率r;网络最大传输率M;
    突发数据最大输出为b+r ·s
    b+r ·s= M ·s

• 两种算法区别

  • 令牌桶可积累发送数
  • 令牌桶满时会丢失令牌而不 会丢失包

• 监管机制与调度机制的配合

  • 令牌速率:R， 令牌桶容量:B， 路由器容量：C
  • R< W2*C/(W1+W2+W3)
  • 流的最大排队延迟:令牌通突发大小的函数
• 如何保证应用所需要的QoS
  • 源端有规律地发送包(监管策略，流量整形)
  • 同一个流走相同路径且在该路径上预留相应资源(带宽、缓冲、CPU周期)
  • 路由器必须有能力决定接受或者拒绝一个流(准入控制)
  • 保证流在每次转发时不被拖延(调度策略)

综合（IntServ）服务

• IntServ(Integrated Services):由IETF开发的一种服务框架，用来为个别应用会话提供个别的服务质量保证。
• 多个类型
  • 尽力而为
  • 可控负载
  • 确保型
• 设计目标： 在拥塞期间如何共享可用的网络容量
• IntServ模型 （PPT）
• 基本思想：
  • 准入(许可)控制： 如果路由器确定不能为请求的QoS提供足够的资源则不允许该流进入网络
  • 路由算法
  • 排队策略
  • 丢弃策略
• 关键特性：
  • 资源预留： 路由器必须知道为出境流预留了多少资源
    • 资源预留请求由接收端发起，向着服务器端逐跳预留
  • 呼叫建立：
    • 需要服务质量保证的流必须在沿途的每个路由器预留足够的资源才能保证端-端QoS需求
    • 每个路由器必须确定该会话所需的本地资源，考虑已经许诺给其他出境流的资源，然后再确定是否具有足够的资源满足本会话的需求
  • 支持QoS路由器必须具备
    • 先进的快速包分类/处理
    • 许可控制、包调度、缓冲区管理
    • 先进的资源控制信令
    • 政策性控制
• 呼叫建立过程
  • 第一步:网络应用提交流量特征说明以及所需QoS说明
  • 第二步:将Tsepc和Rsec传递给路径上所有路由器
  • 第三步:路由器确定能否许可本次呼叫
  • Rspec:预留说明定义了请求的QoS
  • Tspec:流量特性指明发送到网络的流量特性
• 资源预留协议 RSVP
  • 应用程序为数据流预留带宽， 主机请求一定的带宽， 路由器转发带宽预留请求
  • 基本性质
    • 为组播树预留带宽
    • 面向接收端
      • 由数据流的接收端发起并维护预留的资源
  • RSVP没有说明网络如何为数据流预留带宽
  • RSVP不是路由协议不负责确定预留哪条链路
  • RSVP可用于异构接收端
  • 一旦预留成功，路由器包调度机制必须实际提供数据流对应的预留带宽
  • RSVP消息 —— 路径 PATH
    • 沿着路由协议提供的单播/组播路由下行发送的消息
    • 在沿途每个节点存储 “path state”，包括上一跳的单播地址。该地址将被用在“逆向路由”预留消息。
    • 路由器要聚合请求， 比如同一个消息流， 如果流1请求2Mbps，流 2请求预留5Mbps，那么 路由器将预留5Mbps。
• IntServ 的不足

区分服务 DiffServ

• 特点
  • 机制可扩展性
    • 将成千上万的端-端流归纳为有限的几个类别
    • 网络核心简单化、网络边缘承担复杂控制操作
  • 服务方式灵活性
    • 并不定义特殊的服务或者服务类别
    • 提供了构建任何服务的功能组件
• 区分服务模型
  • 最简单的基于每个类别的模型
    • 将用户流数据报标志成类
    • 由标准化的单跳行为(PHBs)执行针对每一类的控制： 单个管理实体负责控制
    • 相比针对每个流的IntServ途径复杂性大大减少
  • 关键特性
    • 使用IPv4 ToS字段或者IPv6 Traffic Class字段作为DS字段
    • 预先建立服务级别协定(SLA)
    • 基于流量分类的内置聚合机制
    • 路由器基于包携带的DS字段进行排队和转发
• 边缘路由器——分类与整形
  • 边缘(edge):具有DifferServ能力并产生流量的主机或者流量经过的第一个具有DifferServ能力的路由器。
  • 网络边缘器
    • 如果用户包遵守双方协商，则包将获得优先标记
    • 如果违反了双方约定，则超出部分包可另行标记(被整形、被丢弃)

第二十一讲 计算机网络安全概述

• 被动攻击
  • 难于检测
  • 重在预防（加密）
• 主动攻击
  • 中断
  • 篡改 - 伪造
  • 重放
  • DoS
  • 恶意程序

网络安全目标

• 网络安全的目标是为一个分布式系统中的双方建立安全的通信信道。
• 保密性： 用来确保只有真正的发送者和接收者才能理解被传输的内容
  • 保密途径
    • 加密消息
    • 不能被窃取者解密
    • 机密通信常常依赖于一把或多把密钥来加密或者保密通信内容。
• 认证性： 发送者和接收者都必须确认对方就是自己想通信的对象。
• 完整性： 发送者和接收者相互认证对方身份后，还必须确信他们的通信内容在过程中没有被恶意或者偶然修改。
• 不可否认性： 发送者不可否认自己发送的信息内容
• 可用性和访问控制： 确保合法用户能使用网络基础设施进行通信。

密码学

• Kerckhoff原则:所有的算法必须是公开的，而密钥是保密的
• 置换密码： 对每个字符进行变化

• 替代密码： 不改变字符， 只打乱顺序

  • 将明文排成矩阵形式，按密钥顺序按列发送
  • 密钥在字母表中的出现顺序就是明文的发送顺序

• 基本密码学两大原则

  • 密码学原则一:消息必须包含一定的冗余度。
  • 密码学原则二:需要采取某种方法来对抗重放攻击。

• 数据加密标准(DES)

• 非对称密钥

数字签名

网络安全

IP安全

• IPSec (IP Security)是一个多服务、多算法和多粒度的框架，提供的服务有保密性、完整性和预防重放攻击的保护
• 多服务:给用户提供多种选择
• 多算法:与算法无关的设计理念，以便未来替换成更加有效的算法
• 多粒度:包括单条TCP连接、一对主机时间的所有流量、一对路由器间的全部流量

• 工作基础是对称密钥密码学

• 增加了一个安全层次， 路由器没有这个层次

• 安全关联：
  • 两个端点之间的单纯连接， 由一个安全标识符表示
  • 单向性
• 安全标识符
  • 用来查询密钥和其他有关安全信息
  • 数据包必须携带安全标识符才能通过安全连接
• 协议扩充
  • 新增两个头的描述： 被加到IP包中，携带安全标识符、完整性控制和其他信息
  • 因特网安全关联及密钥管理协议(ISAKMP)
    • 处理如何建立密钥
    • 是一个框架
• 使用方式一
  • 传输模式(transport mode)
    • 在IP包头和有效载荷之间增加一个IPSec新头
    • IPSec新头称为认证头(Authentication Header)
      • 包括安全关联ID、序号、有效载荷数据的完整性检查
  • 支持加密功能的传输模式
    • 在IP包头和有效载荷之间增加一个IPSec新头
    • IPSec新头称为封装的安全有效载荷头(Encapsulating Security Payload Header)
• 使用方式二
  • 隧道模式(Tunnel mode)
    • 整个IP包被封装到一个新的IP包的有效载荷部分

安全的socket

• SSL( Secure Socket Layer)
  • 在两个socket之间建立一个安全的连接
    • 客户机与服务器之间的参数协商
    • 客户及和服务器的双向认证
    • 通信的保密性
    • 数据完整性
  • 主要任务是压缩和加密
  • 支持多种算法和选项
    • 是否使用压缩功能
    • 使用哪些密码学算法
    • 有哪些密码产品限制
  • 针对拟传输数据的安全处理： 被分割成最多16KB的块，每块单独进行安全处理

防火墙

• 一个防火墙由一台或多台机器组成，它用一组形成防火墙“砖头”的软件将外部网络(如Internet)与内部网络隔开。
• 特性
  • 双向通信必须经过防火墙
  • 只允许本地安全策略授权的信息通过
  • 防火墙本身不会影响信息的流动
• 包过滤(packet filtering)
  • 工作原理
    • 基于检查TCP或UDP包的信息做出决策
    • 只能区分好包和坏包
    • 无法区分好用户和坏用户
  • 适合黑白安全策略
  • 不能安全地用于特定的通信
  • 无法察觉网络上的攻击
  • 粗粒度
• 电路网关(circuit gateway)
  • 工作原理： 电路网关可被看作是一条经过防火墙的通道，它将防火墙一边的系统与另一边的系统链接
  • 通常结合了某些信息的带外认证模式。
  • 适合于网络应用传送的实际信息并不重要而正在使用该应用的用户更重要时。
• 应用代理(application proxy)
  • 工作原理： 可对应用包含的实际内容或数据流加以控制。
  • 应用代理特定于某个应用，一般还包括应用数据流中的认证信息。
• 应用网关(application gateway)
  • 基本功能： 提供最终的“细粒度”安全控制
  • 管理员对每一个使用Internet服务的用户提出认证要求
  • 根据认证信息和其他因素(例如时间等)允许或拒绝用户访问
• 防火墙的一般使用： 防范措施:没有入境连接通过防火墙
• 防火墙的综合使用：
  • 内部LAN上包过滤器检查出境分组
  • 外部LAN上包过滤器检查入境分组
  • 所有分组必须经过应用网关的再次检查