计算机网络期末复习资料, 是结合给出的考点重新整理的资料

考点

第一章

什么是因特网

具体构成描述

  • 主机 / 端系统: 与因特网相连的设备
  • 通信链路: 同轴电缆, 铜缆, 光纤, 无线电频谱
  • 分组交换机
    • 路由器: 通常在网络核心
    • 链路层交换机: 通常在接入网
  • 传输速率: 比特/秒 bps
  • 分组: 数据分段并加上首部字节(发送系统)
  • 路径: 分组经历的通信链路和分组交换机
  • 因特网服务提供商(ISP): 因特网接入服务
  • 协议: 控制因特网中信息的接收和发送
    • TCP: 传输控制协议
    • IP: 网际协议
  • 因特网标准: 由IETF研发
  • RFC: 请求评论, 因特网标准文档

服务描述

  • 分布式应用程序: 涉及到多个相互交换数据的端系统
  • 套接字接口: 规定了端系统上的程序, 请求因特网基础设施, 向另一个端系统上程序, 交付数据的方式

什么是协议

  • 协议定义了:
    • 在两个或多个通信实体之间, 交换报文的格式和顺序
    • 报文发送和/或接收报文, 或其他事件, 所采取的动作

网络边缘

  • 端系统: 运行应用程序
  • P2S模型
    • 客户端: 发送请求, 接受服务
    • 服务器: 响应请求, 提供服务, 始终在线, 性能更强
  • P2P模型
    • 无专用服务器, 每设备既是客户端也是服务器

接入网

  • 接入网: 端系统物理连接到边缘路由器的网络
  • 边缘路由器: 端系统接入到远程端系统的第一台路由器

  • 接入链路与接入环境

    • 家庭接入

      • 拨号
        • 介质: 电话线, 有调制解调器, 执行的操作相当于给接入号(服务台)打个电话, 独占一个线路
        • 速率: 56kbps
      • 卫星: 1Mbps

      • DSL: 数字用户线

        • 介质: 电话线

        • 拓扑

          1
          2
          3
          家庭电话-----------(电话线)----分配器----(现有电话线)----DSLAM----电话网
                                         |                             |
          PC--(双绞线)--Modem--(电话线)--+                             +----因特网

        • DSLAM: 数字用户线接入复用器, 位于中心局, 许多端系统共享

        • 频段分布
          • 高速下行: 50kHz - 1MHz 12Mbps 55Mbps
          • 中速上行: 4kHz - 50kHz 1.8Mbps 15Mbps
          • 双向话音: 0 - 4kHz

      • HFC: 混合光纤同轴/电缆因特网接入

        • 介质: 同轴电缆 + 光纤

        • 拓扑

          1
          2
          3
          家庭----(同轴电缆)----光纤节点----(光纤)----CMTS----因特网
          家庭----(同轴电缆)----|                        |
          家庭----(同轴电缆)----+                        +----有线电视服务

        • CMTS: 电缆调制解调器端接系统, 位于电缆头端

        • 速率: 42.8Mbps下行, 30.7Mbps上行
        • 有碰撞

      • FTTH: 光纤到户(PON: 被动光纤网络)

        • 介质: 光纤

        • 拓扑

          1
          2
          3
          ONT----(光纤)----光纤分配器----(光纤)----OLT----因特网
          ONT----(光纤)----|                       
          ONT----(光纤)----+

        • ONT: 光纤网络端接器; OLT: 光纤线路端接器

    • 企业(家庭)接入
      • LAN
        • 介质: 双绞线
        • 拓扑: 设备接入以太网交换机, 通过路由器接入因特网
        • 速率: 10Mbps 100Mbps, 1Gbps, 10Gbps
      • WiFi(802.11b/g/ac)
        • 11Mbps, 54Mbps, 100Mbps+
    • 广域无线接入: 通信运营商
      • 3G: 1Mbps
      • 4G LTE / WiMAX(淘汰): 10Mbps+
      • 5G: 20Gbps?

物理媒体

  • 导向型
    • 双绞铜线
    • 同轴电缆(可用作共享媒体)
    • 光纤
  • 非导向型
    • 陆地无线电
    • 卫星无线电

网络核心

分组交换

  • 数据切分成分组, 加首部
  • 每个分组发送时独占带宽
  • 交换机: 链路层交换机, 路由器
  • 存储转发传输
    • 交换机先接收并存储整个分组, 之后再发出
    • 端到端时延(N个交换机, 分组长度L, 速率R): $d_{e2e}=N\frac{L}{R}$
  • 排队时延和分组丢失
    • 输出缓存/输出队列: 位于输出链路前
    • 拥塞: 分组排队等待链路
    • 排队时延: 入队到出队的时延
    • 分组丢失: 队列近满, 概率丢失; 队列满, 直接丢失
  • 转发表和路由选择协议
    • 转发表: 目的地址映射到输出链路
    • 路由选择协议: 自动设置转发表

电路交换

  • 预留资源, 需要建立连接/断开连接
  • 端到端连接: 专用电路, 恒定时延/速率, 稳定的性能
  • 电路交换中的复用
    • 频分复用
      • 分频段, 每个电路独占一个频率范围
    • 时分复用
      • 划分时隙, 每个电路轮流得到时隙
      • 统计时分复用: 划分时隙, 高数据率的源得到更多时隙
    • 对比
      • 电路: 时延固定
      • 分组: 时延不可预测, 共享带宽更高, 更简单有效成本低
      • 电路预先分配, 分组按需分配
    • 虚电路
      • 电路交换 + 分组交换
      • 虚电路建立时, 固定路由, 无需路由选择
      • 共享资源, 需要拥塞控制
      • 保证分组按序到达
      • 可预留资源, 可区别服务(有快有慢, 优先级等)
      • 需要连接建立和拆除

网络的网络

  • 粗略的层次结构
    • Tier-1 ISP与内容提供商
    • 区域ISP(与多个Tier-1相连)
    • 接入ISP: 接入网, 连接端系统和Tier-2 ISP
    • IXP: 连接ISP, 可以来自不同级

分组交换网中的时延丢包和吞吐量

时延概述

  • 处理时延: 节点 检查首部, 决定转发, 进行校验 的时间, 微秒-
  • 排队时延: 在链路前的队列等待传输, 微秒~毫秒
  • 传输时延: $L/R$, 将所有比特推向链路的时间, 微秒~毫秒
  • 传播时延: $d/s$, 速度s略小于光速, 毫秒

排队时延和丢包

  • 排队时延对不同的分组不相通, 以统计量衡量
  • 流量强度: $La/R$, a为分组到达的速率, 流量强度不能大于1
  • 流量强度增加, 平均排队时延迅速增加($x^2$)
  • 丢包
    • (上课提到)队列近满, 部分设备采取按照概率丢弃分组, 队列越长概率越大
    • 队列满, 再来就丢, 用丢包率衡量

端到端时延

  • $N-1$个路由器, 则端到端时延$d_{e2e}=N(d_{proc}+d_{trans}+d_{prop})$
  • traceroute: ttl递增的一系列分组, 分别测试到第i跳的时延
  • 端系统, 应用程序和其他时延
    • 向共享媒体传输的端系统, 有意延迟传输
    • 媒体分组化(AD-DA转换, 填充分组)延迟

吞吐量

  • 瞬时吞吐量: 主机B接收的速率
  • 平均吞吐量: $F/T$, 文件大小除以传输时间
  • 瓶颈链路: 吞吐量是各个子链路吞吐量的最小值
    • 因特网中, 吞吐量瓶颈在接入网
  • 共享链路: 多个链路共享某一段链路, 则需要共享这个链路的吞吐量

协议层级及其服务模型

分层的协议结构

  • 协议分层
    • 每层向上提供服务， 各层所有协议称为协议栈
    • PDU: protocol data units, 也就是分组(控制信息 + 数据)
  • 因特网(TCP/IP)协议栈
    • 应用层
      • 支持网络应用程序: FTP(端系统文件传输), SMTP(电子邮件报文传输), HTTP(Web文档请求和传送)
      • 信息分组: 报文
    • 运输层
      • 进程间数据传输: TCP, UDP
      • 信息分组: 报文段
    • 网络层
      • 路由数据报: IP
      • 信息分组: 数据报
    • 链路层
      • 在邻接的主机或路由器间传输: Ethernet, PPP
      • 信息分组: 帧
    • 物理层
      • 线路上的比特
  • OSI模型
    • 应用层: 应用访问OSI模型的环境
    • 表示层, 会话层: 并入应用层
    • 运输层
      • 端系统间通信
      • 可靠传输 或 单块传输
      • 连接建立, 维持, 释放
    • 网络层
      • 分组在多个网络或链路上传输
      • 编址, 路由, 转发, 拥塞控制
      • 连接建立, 维持, 拆除
    • 数据链路层
      • 链路层帧
      • 媒体访问控制, 差错检测和重传, 流量控制
      • 连接激活, 维持和失活
    • 物理层
      • 链路上的比特流

封装

  • 封装: 分组 = 首部字段 + 有效载荷字段
    • 应用层报文
    • 运输层报文段: 运输层首部(应用交付信息, 差错检测信息) + (分段的)应用层报文
    • 网络层数据报: 网络层首部(源目的地址等) + 运输层报文段
    • 链路层帧: 链路层首部 + 网络层数据报

面对攻击的网络

  • 攻击个人电脑
    • 恶意软件
      • 大多数都是自我复制的
      • 病毒: 需要某种形式的用户交互来感染用户设备
      • 蠕虫: 无需任何明显用户交互就能进入设备
      • 木马: 伪装成无害程序, 吸引用户点击
      • 后门: 绕过授权验证
      • 广告软件: 访问弹出广告
      • 间谍软件: 收集用户的输入, 记录用户活动
  • 攻击服务器和网络基础设施
    • 拒绝服务攻击DoS
      • 使得服务不能由合法用户使用
      • 弱点攻击: 针对易受攻击的程序或操作系统, 引发停止运行或崩溃
      • 带宽洪泛: 大量发送分组到目标, 使链路拥塞
      • 连接洪泛: 创建大量半开或全开的TCP连接, 耗尽资源
    • 分布式DoS(DDoS)
      • 攻击者控制多个源
      • 僵尸网路: 攻击者用恶意软件控制大量计算机, 作为DDoS的源头等
  • 嗅探分组
    • 分组嗅探器: 记录每个流经的分组副本的被动接收机
    • 防范: 加密
  • 伪装
    • IP欺骗: 将具有虚假源地址的分组注入因特网
    • 重放攻击
    • 中间人攻击
    • 连接劫持
    • 解决方案: 加密, 数字签名, MAC

第三章

多路复用与多路分解

  • 多路分解: 将运输层报文段中的数据, 交付到正确的套接字的工作
  • 多路复用: 从套接字中收集数据, 加首部生成报文段, 将报文段传递到网络层
  • 套接字
    • 具有唯一标识符
    • 报文段具有特殊字段(源端口号16bit, 目的端口号16bit), 指示需要交付到的套接字
    • 周知端口号: 0~1023

无连接的多路复用与多路分解

  • UDP套接字由二元组进行标识: 目的IP : 目的端口号
  • 源端口号: 回复时使用

面向连接的多路复用与多路分解

  • TCP套接字由四元组进行标识: 源IP : 源端口号 : 目的IP : 目的端口号
  • 不同来源的报文到达同一端口可区分, HTTP服务器

无连接运输UDP

  • 仅提供复用分解, 差错检测
  • 无连接: 发送报文段之前, 没有握手
  • 优点: 首部短, 时间灵活, 无连接建立, 无连接状态
  • 无拥塞控制, 可以由应用层构建可靠传输

报文段结构

源端口号 目的端口号 长度(首部+数据) 检验和 应用数据(报文)
16bit 16bit 16bit 16bit …
  • UDP变长数据段
  • 检验和计算: UDP报文段 + IP首部的部分字段()

UDP检验和

  • 计算方法
    • 报文段分为16bit字, 相加求和
    • 最高位进位回卷, 加到最低位
    • 取反码
  • 检验方法: 接收方做前两步, 得到全1, 则没问题
  • 能检测, 不能纠错, 端到端差错控制

面向连接的运输TCP

  • 提供差错检测, 重传, 累积确认, 定时器, 序号和确认号的首部字段
  • 全双工

TCP连接

  • 三次握手
    • 客户发送
    • 服务端发送
    • 客户发送
  • MSS最大报文段长度(其实是应用层数据的最大长度): 根据 MTU(链路层)最大传输单元 确定, 典型值1460字节

TCP报文段结构

源端口号 目的端口号 序号 确认号 (第一堆) 接收窗口 因特网校验和-紧急数据指针 选项 数据
16bit 16bit 32bit 32bit 16bit 16bit 16bit+16bit 0bit+ …
  • 第一堆里面有: 首部长度4bit(以字为单位, 1=4字节) + 保留未用6bit + (URG ACK PSH RST SYN FIN)标志字段6bit
  • SYN FIN RST 用于连接建立和拆除, PSH代表必须立即将数据交给上层, URG与紧急数据指表示指向位置是紧急数据的最后一个字节, 需要通知上层
  • 序号和确认号
    • 序号: 是该报文段的首字节的字节流编号

      单纯的ACK不包含数据字节, 因此不引发编号增加

    • 确认号: 表示这一序号之前的字节均被正确接收, 它和其后的未接收

      一个报文可以同时有确认号和序号, 是捎带ACK

往返时间的估计与超时

  • 估计往返时间
    • SampleRTT: 某一报文被发出(交给IP)到其确认被接收的时间量(一个来回)

      重传的报文不进行测量

    • EstimatedRTT: 初始为第一个测得的SampleRTT, 之后根据下式更新
      $$\textrm{EstimatedRTT} = (1-\alpha)\cdot\textrm{EstimatedRTT} + \alpha \cdot \textrm{SampleRTT}$$

      指数移动加权平均

    • DevRTT: RTT的偏差, 是Sample和Estimated的差的绝对值, 也用指数移动加权平均
      $$\textrm{DevRTT} = (1-\beta)\cdot\textrm{DevRTT} + \beta \cdot |\textrm{SampleRTT}-\textrm{EstimatedRTT}|$$
  • 设置和管理重传超时间隔
    • 重传间隔
      • 默认初始值为1s
      • 超时后, 设为先前值的2倍
      • 若有新的EstimatedRTT, 立刻据下式更新
        $$\textrm{TimeInterval} = \textrm{EstimatedRTT} + 4\cdot \textrm{DevRTT}$$

可靠数据传输

  • 累积ACK
    • ACK中的数字, 表示其之前的字节均被接收
  • 重传
    • 规则: 一个报文到达重传间隔, 仍未收到ACK(ACK>SEQ+LEN), 则重传
    • 超时间隔加倍: 重传过后, 下一次的定时将会加倍;
    • 推算超时间隔: 若收到ACK或得到上层应用数据, 则又改为使用$\textrm{TimeInterval}$计算
  • 快速重传
    • ACK生成策略
      • 延迟ACK: 某一报文到达, 等待500ms, 若下一个按序报文没到, 发这一报文ACK
      • 立刻发送累积ACK: 一个按序报文到了, 前一个在等待发ACK, 发累积ACK, ACK后一个报文
      • 冗余ACK: 到达一个报文, 其序号大于期望的序号, 立刻发送冗余ACK, 其序号为期望序号
      • 收到的报文填补空缺, 且起始于空缺的低端, 则立刻发ACK
    • 收到3个冗余ACK, 则进行快速重传, 假定被ACK的报文后的报文全部丢失
  • 回退N步还是选择重传
    • 第n个报文重传, 若之后的报文被缓存, 且其ACK及时到达, 那么后续可以不用重传

      这意味着TCP不是单纯的GBN, 而含有一部分SN

流量控制

  • 接收窗口
    • 接收方跟踪
      • 应用读取的最后一个字节的编号: LastByteRead
      • 接收到的最后一个字节的编号: LastByteRcvd
      • 接收缓存大小: RcvBuffer
      • 接收窗口大小: rwnd = RcvBuffer-(LastByteRcvd-LastByteRead)

        也就是缓存余量

      • 接收方将rwnd放入发给发送方的报文中
    • 发送方跟踪
      • 发送的最后一个字节的编号: LastByteSent
      • 被确认的最后一个字节的编号: LastByteAcked
      • 从接收到的报文中得到的rwnd
      • 需要始终保证 LastByteSent - LastByteAcked <= rwnd
      • 若出现rwnd=0, 则需要继续发送含有一字节数据的报文

        为了防止接收方无数据要发, 引发发送端阻塞. 这个一字节的报文总会被ACK, 有机会获得一个非0的rwnd值

TCP连接管理

  • 建立: 三次握手
通信 SYN ACK ACK SEQ 数据 操作
客户->服务 + client_isn 客户端随机选择起始序号
服务->客户 + + client_isn+1 server_isn 服务器分配资源, 随机选择起始序号
客户->服务 + server_isn+1 client_isn+1 可携带 客户端分配资源
  • 终止(以客户终止为例)
通信 FIN SEQ ACK ACK 操作
客户->服务 + client_isn (server_isn) 客户发送FIN
服务->客户 server_isn + client_isn + 1 服务器ACK这个FIN, 之后还可以发数据(len)
服务->客户 + server_isn + len (client_isn + 1) 服务器发送FIN, 收到客户端的ACK后关闭, 释放资源
客户->服务 client_isn + 1 + server_isn + len + 1 客户端ACK这个FIN, 定时等待之后关闭, 释放资源
  • 防范SYN洪泛攻击
    • 第一步的isn使用散列函数, 用源地址, 目的地址和端口号, 和一个只有服务器知道的散列函数
    • 第二步不分配资源
    • 第三步根据ACK里面的seq, 可以验证这个ACK是由先前的某个SYN生成的, 于是分配资源建立连接
  • 拒绝通信
    • 发送RST(RST标志位1)

拥塞控制原理

  • 一堆废话, 我只关心TCP

TCP拥塞控制

  • 拥塞窗口cwnd6;
    • 对发送进行限制: LastByteSent - LastByteAcked <= min(rwnd, cwnd)
  • 窗口与速率的关系: B = S(发出的包数量)/RTT(往返时间)
  • TCP拥塞控制算法
    • 总结
      • ssthresh变化: 丢包事件: ssthresh = cwnd / 2
      • cwnd变化: 状态初始值
        • 进入慢启动: cwnd = 1
        • 进入拥塞避免: cwnd = ssthresh
        • 进入快速恢复: cwnd = ssthresh + 3
      • cwnd变化: 增长方式
        • 慢启动: 每个ACK, +1, 相当于每轮乘二
        • 拥塞避免: 每轮 +1
        • 快速恢复: 每个冗余ACK +1
    • 慢启动
      • 初始: cwnd = 1 (MSS)
      • 加倍: 每一轮, cwnd加倍
      • 结束
        • 超时, 取cwnd = 1, ssthresh = cwnd/2
        • 到达ssthresh, 进入拥塞避免模式
        • 3个冗余ACK, ssthresh = cwnd/2, cwnd = cwnd/2+3, 进入快速恢复
    • 拥塞避免
      • 线性增加: 每一轮, cwnd+1
      • 结束
        • 超时, 取cwnd = 1, ssthresh = cwnd/2, 相当于慢启动
        • 3个冗余ACK, ssthresh = cwnd/2, cwnd = cwnd/2+3, 进入快速恢复
    • 快速恢复
      • 接下来收到的冗余ACK, cwnd都加1(之前的3个冗余ACK已经加过3, 至少加3)
      • 结束
        • 收到期待的ACK, 将cwnd = ssthresh, 进入拥塞避免
        • 超时, ssthresh = cwnd/2, cwnd = 1
    • TCP拥塞控制: 回顾
      • TCP Tahoe: 没有快速恢复, 3个ACK也进入慢启动
      • TCP Reno: 上文的方案

        加3根据协议不同, 看具体情况做
        慢启动: 其实是收到的每个ACK都加1, 因为ACK数等于发送数, 相当于翻倍

  • 需要拥塞控制的原因: 浪费带宽
    • 速率接近容量 -> 队列满 + 大排队时延
    • 大时延 -> 不必要的超时重传
    • 队列满 -> 丢包 -> 浪费上游流量
    • 丢包 -> 重传代价

公平性

  • TCP AIMD
    • 相同的RTT: 公平, 最终会达到平均分配带宽
    • RTT不同: RTT小的更快扩大窗口, 将得到更多带宽, 最终似乎与RTT成反比
  • UDP参与
    • UDP没有公平可言, 抢占资源
    • UDP将挤压TCP资源
  • 并行TCP
    • 一个应用使用多个TCP连接, 就获得了多倍其应得的带宽

网络辅助拥塞控制

  • IP首部设置ECN(2比特, 4状态), 送到接收主机
  • 接受主机在TCP ACK中设置ECE, 发到发送主机
  • 发送主机减半cwnd, 并在下一个报文头中设置CWD, 发到接收主机

第四章

路由器工作原理

  • 输入端口
    • 线路端接: 物理线路接入
    • 数据链路处理: 协议, 拆封
    • 查找转发排队: 查找转发表, 存帧排队
  • 交换结构
    • 经内存交换
    • 经总线交换
    • 经互连网络交换(纵横式)
  • 输出端口: 排队, 数据链路处理, 线路端接
  • 路由选择处理器: 执行控制平面功能, 维护路由选择表和链路状态, 计算转发表
    • 基于目的地转发: 仅考虑目的地
    • 通用转发: 考虑更多因素

输入端口处理和基于目的地转发

  • 转发表在输入端口有副本, 在输入端口本地做出转发决策
  • 前缀匹配
    • 转发表不存储所有目的地址, 而是根据最长前缀匹配确定转发
    • 使用DRAM, SRAM, TCAM(三态内容可寻址存储器), 纳秒级
  • 其他动作
    • 出现物理层和链路层处理
    • 检查版本号, 检验和, 寿命, 重写后两个
    • 更新网络管理信息(如 计数器)

交换

  • 经内存交换: 输入卡处理地址查找和分组存储, 所有输入共享内存
  • 经总线交换
    • 输入端口为分组计划一个交换机内部标签(首部)
    • 与首部匹配的输出端口存分组, 并去除标签
  • 经互连网络交换
    • 优点: 可以并行
    • 纵横式, N纵N横N*N交叉点
    • 非阻塞: 到不同输出端的分组不会互相阻塞
  • 更复杂(去数据通信笔记看)
    • 三级非阻塞网络

输出端口处理

  • 输出缓存, 数据链路处理(协议, 封装), 线路端接

何处出现排队

  • 丢包: 没有缓存可以用来存储到达的分组
  • 输入排队
    • 交换结构不足以使所有到达分组无时延地通过它传送
    • HOL阻塞(线路前部阻塞): 被线路前部的一个分组阻塞, 例如两个分组发往一个目的地
  • 输出排队
    • 没有足够的内存存储到达的分组
    • 主动队列管理AQM
      • 弃尾: 丢弃到达的分组
      • 也可以删除正在排队的部分分组
      • 向发送方提供阻塞信号
    • 随机早期检测RED
    • 缓存大小: $B=\textrm{RTT}\cdot C/\sqrt{N}$, $C$为链路容量, $N$链路上的TCP流数量, $\textrm{RTT}$平均往返时延

分组调度

  • 先进先出FIFO 先来先服务FCFS
    • 维护一个队列, 来了进入队尾, 队首挨个处理
  • 优先权排队
    • 每个优先权类有自己的队列, 各自FIFO
    • 不同优先级, 高的队列空了才处理低的
    • 非抢占: 已经开始的传输不会被打断
  • 循环排队规则
    • 多个队列, 不分优先级, 轮流提供服务
    • 保持工作排队规则: 有任何类的分组在等待, 则不允许链路保持空闲
  • 加权公平排队
    • 在循环排队的基础上加上优先级
    • 每一循环, 每个类得到多次服务, 次数与权重成正比

网际协议

IPv4数据报格式

  • 数据报格式

    1
    2
    3
    4
    5
    6
    7
    |    $版本 4   |  首部长度 4  |  服务类型 8  | 数据报长度16 |
    |          $标识16             | 标志 3 |       片偏移13    |
    |    寿命 8    |  $上层协议 8  |         首部检验和16       |
    |                  (NoNAT)$源地址32                         |
    |                 (NoNAT)$目的地址32                        |
    |                      选项(可选)                           |
    |                         数据                              |
    • 服务类型: 优先级(3bit), 可靠性(1bit, 一般/高), 时延(1bit, 一般/低), 吞吐量(1bit, 一般/高)
    • 标识, 标志, 片偏移: 与IPv4分片有关
    • 选项: 长度不定, 默认首部长度为20字节, 可变
    • 数据报长度: 首部加数据的长度, 字节为单位
    • 寿命: 经过一个路由器, 减1, 为0丢弃
    • 协议: 到达目的地才有用, 6-TCP, 17-UDP, 类似端口号

IPv4数据报分片

  • 原因: 链路层最大传输单元MTU, 限制IP数据报的长度
  • 对数据报分片, 并设置标识等
    • 标识: 每个数据报+1, 一个数据报的各个分片相同
    • 标志: 最后一个为0, 其他是1
    • 片偏移: 以64bit为单位

IPv4编址

  • 接口: 主机与物理线路的边界
  • 点分十进制记法: 192.168.0.255, 就这样的, 每个8位当作十进制数, 点分开
  • 地址分类:
    • A: 0开头/8
    • B: 10开头/16
    • C: 110开头/24
  • 子网(IP网络): CIDR无类别域间路由选择
    • 子网掩码: xxx.xxx.xxx.xxx/yy, yy为子网掩码,
    • 网络前缀: 地址的前yy位
    • 子网内的地址: 剩下的位数
    • 另一种表示: 前yy位为1, 剩下为0, 用点分十进制写出来
    • 路由聚合/路由摘要: 一个组织共享相同前缀
  • 主机得到地址的过程
    • 获取一块地址
      • 来自ISP, ISP来自ICANN
      • 管理员划分这些地址给子网
    • 获取主机地址: DHCP
      • 所有的目的地址都是 255.255.255.255
      • DHCP服务器发现: 新到达的主机发送DHCP发现报文
        • UDP端口67的报文
        • 目的: 255.255.255.255
        • 内容: 事务ID
      • DHCP服务器提供: 服务器的相应
        • UDP端口68的报文
        • 源: DHCP服务器地址
        • 内容
          • 事务ID, 推荐IP地址, 掩码, 地址租期
      • DHCP请求: 主机选择一个服务器, 相应
        • UDP端口67的报文
        • 源: 0.0.0.0
        • 内容: 回显配置信息, 事务ID+1
      • DHCP ACK: 确认配置
        • UDP端口68的报文
        • 源: DHCP服务器地址
        • 内容: 证实参数, 事务ID+1

网络地址转换NAT

  • NAT路由器: 它和它背后的网路对外界是一台单一的设备
  • 允许内部外部通信, 使用不同的地址
  • NAT路由器将重写IP地址和端口号字段
  • NAT转换表
    • 内部地址:端口 - 外部地址:端口
  • NAT穿越: 解决内网服务器周知端口问题
  • UPnP: 通用即插即用协议, 解决NAT自动配置
  • 跨越网络层和传输层

IPv6

  • 数据报格式

    1
    2
    3
    4
    5
    |    版本 4    |  流量类型 8  |         流量标签 20         |
    |       有效载荷长度 16      | 下一个首部 8 |    寿命 8     |
    |                       源地址 128                          |
    |                      目的地址 128                         |
    |                         数据                              |
    • 首部定长40字节
    • 版本: 6
    • 流量类型: 与IP的服务类型字段类似
    • 流标签: 识别数据报的流, 用于优先权等
    • 有效载荷长度: 给出数据段的长度, 不含头部
    • 下一个首部 = 上层协议类型, 与IPv4的协议类型同值
  • 与IPv4的不同
    • IPv6不允许由路由器进行分片, 因此没有分片3字段
    • 首部检验和: 运输层和数据链路层进行过检验, 因此丢掉
    • 选项: 不是标准IP的一部分了, 可能出现在”下一个首部”指定的地方
  • 从IPv4到IPv6
    • 隧道: IPv6数据报放入IPv4的有效载荷字段中, 上层协议41

第五章

路由选择算法

  • 路由选择算法: 从发送方到接收方, 确定一条通过路由器网络的好的路径
  • 图, 节点, 路径, 最低开销路径, 最短路径
  • 分类1
    • 集中式路由选择算法(链路状态算法): 完整, 全局的网络知识, 计算源到目的的最低开销路径
    • 分散式路由选择算法(距离向量算法): 迭代, 分布式地计算出最低开销路径
  • 分类2
    • 静态路由选择算法: 变化很慢, 人工配置
    • 动态路由选择算法: 随着网络流量负载变化或拓扑发生变化而改变路由选择路径
  • 分类3
    • 负载敏感: 链路开销反映拥塞水平
    • 负载迟钝: 反之

链路状态路由选择算法

  • 算法流程
    • $u$源, $D(v)$从源到$v$的距离, $p(v)$到$v$的最短路上的下一个节点
    • 首先$D(v)$正无穷, 若有边设为边的开销
    • 每一轮, 找出$D(v)$中最小的一个$v$, 进行如下操作
      • 用这个$D(v)$更新$v$的所有邻点的开销, 值为$D(v)$加边开销
    • 直到不再变化
  • 复杂性: $O(n^2)$
  • 出现的问题
    • 同时运行LS算法的路由器
    • 链路选择的震荡, 由于一侧拥塞, 都选择另一侧, 而恰好使得这一侧也拥塞, 不断往返
    • 解决: 随机化发送链路通告的时间

距离向量路由选择算法

  • 算法流程: 对于每个节点
    • 更新距离向量估计值, 当直接相连的链路开销发生变化, 或从邻居接收到距离向量的更新
    • 更新规则: 取最小值, 对所有$D_v(y)+c(x,v)$以及原有的距离, $v$是$x$的邻居
  • 路由选择环路
    • 无穷计数: 有环路的情况下, 链路代价的增加, 将会反复震荡, 长时间后才能达到稳定
    • 毒性逆转: 如果z通过y路由选择到x, 则z将通告y, z到x的距离是无穷大
    • 涉及到3个或更多节点的环路还是不能解决无穷计数

算法比较

  • 报文复杂性
    • LS: $O(|N||E|)$
    • DV: 仅在新的链路开销导致与该链路相连节点的最低开销路径发生改变, 才传播开销
  • 收敛速度
    • LS: 收敛块
    • DV: 较慢, 还有无穷计数
  • 健壮性
    • LS: 节点分别计算自己的最短路径, 一定程度健壮性
    • DV: 一个节点的错误计算值, 扩散到整个网络

因特网中自治系统内部的路由选择OSPF

  • 自治系统AS
    • 由处在相同管理控制下的路由器组成
    • 具有 自治系统内部路由选择协议
    • 具有 独有的AS编号 ASN

开放最短路优先OSPF

  • 是一种链路状态协议: 洪泛状态信息 + Dijkstra算法
  • 各个链路的开销: 管理员进行配置
  • 路由选择信息: 向全部路由器广播
  • 广播条件: 有链路状态发生变化 / 至少每30min一次
  • 报文: 直接由IP承担, 上层协议的值为89, 自己实现可靠传输和链路状态广播
  • 其他功能: 检查链路运行(发送OSPF HELLO), 获得相邻路由的链路状态数据库
  • 优点
    • 安全: 鉴别报文防止伪造(使用口令或MD5), 序号防范重放攻击
    • 多条相同开销的路径: 允许使用多条路径
    • 单播与多播: MOSPF使用现有的链路数据库, 链路状态广播机制增加新型链路状态通告
    • AS内层次结构: OSPF自治系统内部也可以配置多个区域, 运行自己的OSPF算法

ISP之间的路由选择BGP

  • 自治系统间路由选择协议
  • 边界网关协议: BGP

BGP的作用

  • BGP中, 分组不是路由到特定的地址, 而是路由到CIDR化的前缀
  • 协议提供的手段
    • 从邻居AS获得前缀的可达性信息: 允许子网广播自己的存在
    • 确定到该前缀的”最好的”路由: 本地运行BGP路由选择过程, 基于策略和可达性信息

通告BGP路由信息

  • 网关路由器: AS边缘的路由器, 直接连接到其他AS中的路由器
  • 内部路由器: 只连接了同一AS内的路由器
  • BGP连接
    • 在端口179的半永久TCP连接
    • eBGP: 跨越AS的BGP连接
    • iBGP: 相同的AS内的两台路由器的连接
  • 传递可达信息: 不断重复 AS内广播, 网关传递到其他AS 的过程

确定最好的路由

  • BGP属性: 路由器通告前缀时, 会在前缀中包括BGP属性
    • AS-PATH属性
      • 每当前缀通过(离开)一个AS, (网关路由器)就在AS-PATH属性末尾, 加上自己的ASN
      • 若其中已有自己的ASN, 则拒绝该通告, 以防止环路
      • 于是, 接到这个通告的路由器, AS-PATH从头到尾恰为到达目标需要经过的AS的顺序
    • NEXT-HOP属性
      • 是该AS-PATH起始路由器接口的IP地址, 也就是连接AS1, AS2的子网中, AS2网关路由器的地址
    • 目的前缀属性
    • 更多
  • 热土豆(烫手山芋)路由选择
    • 不考虑AS-PATH, 只关注NEXT-HOP
    • 用内部路由协议确定, 所有的NEXT-HOP中, 开销最小的一个
    • 目的是尽快将分组送出AS, 如同烫手山芋
  • 路由器选择算法
    • 依次使用规则, 直到只剩一个
      • 选择本地偏好最高的
        • 路由被指派本地偏好(是BGP属性之一), 可由该路由器设置或学习到, 取决于网络管理员
      • 选择最短AS-PATH的路由, 使用DV确定路径, 距离测度使用AS跳的跳数
      • 使用热土豆路由选择
      • 使用BGP标识选择

IP任播

  • 访问某任播地址的请求, 到达一系列主机中的一个
  • CDN
    • 多台服务器, 相同IP地址, 都用BGP通告各自的IP地址
    • 路由器将认为收到的多个通告, 是到达同一服务器的不同路径(其实是不同的服务器, 只是配置为相同的服务)
    • 客户请求时, 路由器将路由到”较近”的CDN服务器
  • DNS
    • 根服务器13个地址, 每个地址有许多镜像
    • 类似CDN, 可以让DNS请求到达”最近的”镜像

路由选择策略

  • 选择的路由通告策略
    • ISP协商等, 确定BGP通告规则, 拒绝某些通告, 尽管这些通告能够提供有效的路径
    • 例如BC直连, 另有BXC路线, X可以选择拒绝通告B和C自己能到达C或B, 以达到不转发BC流量的目的

拼装在一起: 在因特网中呈现

  • [木大警告] 这节不知道在讲什么玩意, 全是例子

因特网控制报文协议ICMP

  • ICMP在IP之上, 位于IP分组的有效载荷字段, 上层协议字段为1
  • 字段
    • 类型
    • 编码
    • 引发该ICMP报文生成的IP数据报的首部, 及其前8字节
  • 详细
    • 0-0: PING回显
    • 3-[0~3]: 目的[网络/主机/协议/端口]不可达
    • 3-[6-7]: 目的[网络/主机]未知
    • 4-0: 源抑制
    • 8-0: PING请求
    • 9-0: 路由器通告
    • 10-0: 路由器发现
    • 11-0: TTL过期
    • 12-0: IP首部损坏
  • 例子
    • PING: 类型8编码0, 回显: 类型0编码0
    • ICMP源抑制: 网络层拥塞控制, 然而TCP有了, 废物一件
    • TRACEROUTE
      • 利用报文过期的ICMP的TTL过期报文(内含路由器的地址和名字)
      • 每个包的目的端口号都不可达, 使用ICMP的目的端口不可达报文, 确定探索结束
  • IPv6新的ICMPv6
    • 分组太大
    • 未被承认的IPv6选项

第六章

多路访问链路和协议

  • 广播链路: 多点, 一个信道
  • 碰撞: 多个结点同时发送

信道划分协议

  • 时分复用TDM
    • 时隙slot, 每轮每结点一个时隙
    • 速率: R/N, 负载不均衡时浪费, 统计时分复用解决, 有额外开销
  • 频分复用FDM
    • 分频率, 一人一频
    • 速率: R/N, 负载不均衡时浪费
  • 码分多址CDMA
    • 每结点一个编码, 1电平为此编码, 0为编码取反
    • 速率: R, 可同时发送(每个结点的编码必须线性不相关), 抗干扰

随机接入协议

  • 时隙ALOHA
    • 有ACK
    • 前提: 每帧长L, 每时隙L/R, 结点同步, 且在时隙开始时才传输, 碰撞检测够快
    • 流程
      • 发送: 结点在一个时隙开始发送帧
        • 成功: 若没检测到碰撞, 则认为成功传输
      • 失败: 检测到碰撞, 在之后的时隙中以概率p不断尝试重传, 直到没有碰撞
    • 效率: 取p=1/N时最大化, 当N趋于无穷时, 效率为1/e
  • ALOHA
    • 有ACK

      除了不同步, 跟时隙ALOHA一样

    • 流程
      • 发送: 结点发送帧
        • 成功: 若没检测到碰撞, 则认为成功传输
      • 失败: 检测到碰撞, 立刻以概率p不断尝试重传, 直到没有碰撞
    • 效率: 取p=1/N时最大化, 当N趋于无穷时, 效率为1/2e(前后都可能有重叠)
  • CSMA/CD
    • 无ACK
    • 不做同步
    • 流程
      • 监听: 监听信道是否空闲, 空闲时才开始传输, 传输前得等96比特时间(最小帧间隔)
      • 传输: 传输时也不断监听是否有其他结点的信号能量
        • 成功: 未发现其他能量, 认为发送成功
      • 失败: 发现其他能量, 立刻停止; 发送48bit干扰信号
      • 等待(非持续): 等待一个随机时间, 回到”监听”重传
      • 回退(p持续): 之后的时间当中以概率p重传
      • 回退(1持续, 以太网): 使用二进制指数后退
        • 经历过了k次碰撞, 就从[0,…,2^k-1]中选一个K值, 等待512K个比特时间
        • k最大为10
        • 最多尝试16次发送
    • 效率: 近似为
      $$\frac{1}{1+5d_{prop}/d_{trans}}$$
    • 最小帧长: 检测冲突的时长不超过端到端传播时延的2倍, 取这一值为最小帧长

轮流协议

  • 轮询协议
    • 流程: 每个从结点n
      • 主节点发帧, 告诉从节点n能够发送的最大包数
      • 从节点发送不超过n帧
      • 主节点发现没有信号了, 继续轮询下一个从节点
    • 缺点: 轮询时延(第一步耗时); 主节点损坏则信道无用
  • 令牌传递协议
    • 流程
      • 收到令牌
      • 如果有帧要发, 则发送不超过最大数目的帧数
      • 传递令牌
    • 缺点: 令牌传播时延, 令牌丢失, 单点故障则信道崩溃

交换局域网

链路层寻址和ARP

  • 媒体访问控制 MAC地址
    • 长度: 6字节
    • 与适配器(NIC等)绑定
    • 广播地址: 全1, 即12个F
    • 每个主机都检查MAC是否与自己相同, 相同则接收
  • 地址解析协议 ARP协议
    • 子网内解析
    • 每台主机或路由器存有ARP表, 保存了其知晓的MAC-IP对应关系, 每个条目有过期时间
    • 流程
      • 若有表项, 直接构造包并发送
      • 若无, 向适配器发送ARP分组(内容: 发送和接收的IP地址, 目的MAC: 广播地址)
      • 每个主机都收到, 若IP相同, 则响应ARP分组, 用标准链路层帧回复
  • 发送数据报到子网以外
    • 路由器每个端口均有MAC和IP
    • 路由器将相应ARP, 主机获得的此IP的MAC地址是路由器这一端口的MAC

以太网

  • 以太网帧结构
    • 帧字段
      • 前同步码: 8字节: 前7个字节都是10101010, 同步时钟并唤醒适配器; 最后一个是10101011, “11”警告适配器数据到来
      • 目的MAC地址: 6字节: 与自己的MAC相同才会接收
      • 源MAC地址: 6字节
      • 类型字段: 2字节: 允许以太网复用多种网络层协议
      • 数据: 46-1500: 承载IP数据报, 超长将分片
      • CRC: 4字节: 适配器丢弃校验出错的帧
    • 无连接服务: 不事先握手
    • 不可靠服务: 成功无ACK, 失败无REJ
  • 以太网技术
    • 命名: [速率]BASE[距离 或 介质], T指铜双绞线, FX/SX/BX指光纤
    • 10Mbps: 10BASE[%d], 距离, 使用同轴电缆
    • 100Mbps: 100BASE-TX/T4/T2双绞线, -FX/SX/BX光纤
    • 1000Mbps: 1000BASE-T等, 又名802.3z, 双绞线, 兼容旧标准, 点对点(交换机)信道全双工, 另有广播(集线器)
    • 10Gbps: 10GBASE-T

链路层交换机

  • 交换机转发和过滤
    • 过滤: 决定帧应该发到某个接口还是将其丢弃
    • 转发: 决定帧去往哪个接口
      • 流程: 借助交换机表(MAC - 接口 - 时间)
        • 没找到目的MAC, 向源以外的所有端口广播
        • 找到MAC, 与源端口匹配, 则丢弃
        • 找到MAC, 与另一端口匹配, 转发到这一端口(进入端口的缓存)
  • 自学习
    • 流程
      • 初始: 交换表为空
      • 学习: 收到帧, 则将[源MAC地址 - 到达的接口 - 当前时间]存入交换表
      • 老化: 一段时间后未收到这一地址作为源的帧, 则此表项移除
    • 即插即用设备: 无需进行配置
    • 双工: 每个接口可同时发送和接收
  • 链路层交换机的性质
    • 消除碰撞: 星型拓扑, 没有因碰撞而浪费的带宽
    • 异质链路: 链路彼此隔离, 允许不同速率, 新旧混用
    • 管理: 检测异常适配器并断开之, 等
  • 交换机与路由器
    • 交换机
      • 优: 即插即用, 分组过滤, 高速率
      • 缺: 拓扑限制为树形, 不提供广播风暴的保护
    • 路由器
      • 优: 拓扑灵活, 提供防火墙保护
      • 缺: 需要配置, 处理延迟大

网桥

  • 功能: 读取A网(总线)的所有帧, 在B(总线)上重发每个帧; B->A同理
  • 特点: 不更改帧, 原样转发; 带缓存; 路由寻址能力(基于MAC, 只转发需要转发的帧)
  • 协议体系
    • 层次: 数据链路层 - MAC层
    • 链接模式
      1. 局域网 - 网桥 - 局域网, 原样转发
      2. 局域网 - 网桥 - [网络或链路] - 网桥 - 局域网, 需要适当封装, 但原始MAC帧不修改
  • 固定路由选择
    • 每对点均有一条选定的路由, 跳数最少, 仅在拓扑变化时改变(生成树算法)
  • 生成树方法
    • 帧转发
      • x收到帧
      • 检查目的地址: 若在某一端口的列表中, 且非阻塞, 发送; 不在任何列表, 则x除以外的端口全部转发
    • 地址探索: 同交换机
      • 收到帧, 则帧源地址MAC与此端口关联, 加入此端口数据库
      • 数据库项带计时器, 超时删除
    • 最小生成树算法: Prim
      • Prim算法流程
        • 选取起始点(根网桥), 加入集合S
        • 对于S中所有点(网桥), 在他们所有邻居里面找离S中点最短的距离, 把这个邻居加入S, 这条边(网桥间的最短距离)加入生成树
        • 直到所有点都加入S, 边集合构成生成树
      • 网桥阻塞规则
        • 选择根网桥: ID最小的网桥
        • 为每个网桥选择root port: 到根网桥最低开销的端口
        • 为每个LAN指定网桥: 拥有到根网桥最低开销路径的, 与这个LAN相连的网桥
        • Designated port: 这个指定网桥与这个LAN相连的端口
        • Designated port 和 root port 不阻塞, 别的都阻塞

虚拟局域网

  • 树形交换局域网的缺陷
    • 缺乏流量隔离: 单播能够隔离, 但广播不行; 缺乏安全隐私的隔离
    • 交换机无效使用: 为了分组造成交换机端口的浪费
    • 管理用户: 用户在分组间移动, 则需要改变物理布线, 连接到不同交换机
  • VLAN: 单一的物理交换机定义多个虚拟局域网, 广播流量仅到达同一分组的端口
    • 跨VLAN需要路由器
    • VLAN划分: 端口 或 MAC
    • VLAN干线连接
      • 干线接口: VLAN交换机之间交换帧
      • 帧格式802.1Q: 以太网帧的源地址和类型之间, 加入VLAN标志

第七章

802.11 体系结构

  • 接入点AP： 中央基站
  • 基本服务集BSS: 1AP + 若干站点(其NIC有唯一MAC)
  • 基础设施无线LAN: AP和将AP连接到路由器的有线以太网
  • 信道与关联
    • 服务集标识符SSID: 热点名(单字/双字)
    • 信道: 一共11个, 1 6 11是三个不重叠信道
    • 关联: 站点选择一个AP, 仅通过它接入因特网
      • 信标帧: AP周期性广播发送, 包含SSID和MAC
      • 被动扫描: 站点等待信标帧
      • 主动扫描: 站点广播探测帧, AP回复探测响应帧
      • 关联流程: 类似DHCP
        • 关联请求帧 -> 关联响应帧 -> (第二次握手, 与想关联的AP)

CSMA/CA: 802.11 MAC协议

  • 带碰撞避免的CSMA: CSMA/CA
    • 载波侦听
    • 碰撞避免
    • 使用链路层ARQ: 确认/重传, 有ACK
  • 不适用碰撞检测的原因
    • 接收信号的强度远小于发送信号的强度, 检测碰撞代价大
    • 由于隐藏终端, 衰减问题, 无法检测所有的碰撞
  • 链路层确认方案
    • 目的接到帧, 且通过了CRC检验, 则等待”短帧间间隔SIFS”, 发回确认帧
    • 发送站点在给定时间内未收到确认, 将会假定发生错误, 并重传该帧
    • 多次重传失败, 将放弃发送并丢弃该帧
  • CSMA/CA流程
    • 监听到信道空闲, 则在”分布式帧间间隔DIFS”的短时间后发送
    • 否则, 选取一个随机回退值, 并在侦听信道空闲时递减该值, 若信道忙, 则不变
    • 当值为0时, 发送整个帧
    • 如果收到确认, 则该帧已被正确接收
      • 如果此时需要发下一帧, 直接从第二步开始
      • 如果没有确认, 则进入第二步的回退, 并从更大的范围选取随机值
  • 处理隐藏终端
    • 隐藏终端: AP与节点A B均相互可见, 但由于信号衰减, AB之间互相接收不到对方的信号, 无从进行载波侦听
    • 请求发送(RTS)帧, 短: 站点广播, 指示传输DATA帧和ACK需要的总时间
    • 允许发送(CTS)帧, 短: AP广播, 给发送方明确地许可, 并让其他站点知道不要发送
      • 收到CTS且不是自己发送RTS的站点, 将在其中的时间段内, 抑制发送
    • 效果
      • 解决隐藏终端, 长DATA只会在预约后才被传输
      • 发生RTS和CTS的碰撞, 因为他们很短, 仅持续很短时间
    • 实际
      • RTS门限值, 大于此的数据才会预约
      • 许多站点的RTS门限大于帧长, 默认不使用RTS/CTS
  • 点对点网络
    • 定向天线, 没其他站点, 相当于是AP与站点的点对点

第九章

提供多种类型的服务

  • 监管: 漏桶
    • 监管准则
      • 平均速率: 长时间速率存在最大值 - 漏桶的令牌产生速率
      • 峰值速率: 短时间速率存在最大值 - (将桶容量定为1, 此时能够限制峰值速率)
      • 突发长度: 极短时间(趋近0)发送的分组数量存在最大值 - 漏桶的高度
    • 漏桶描述
      • 分组首先进入令牌等待队列
      • 在漏桶处取得令牌的分组将被发送
      • 桶高度不超过b
      • 每秒生成r个令牌加入桶
    • 效果
      • 平均速率: r + b/t, 时间足够长, 该值为r
      • 突发长度: b
      • 峰值速率: 在已有的一个漏桶后, 串联一个高度为1的桶, 其速率r’可限制峰值速率