计算机网络之期末复习

Posted on

第1章 计算机网络和因特网

1.1 什么是因特网

1.1.1 具体构成描述

组成

组成: 端系统, 通信链路, 分组交换机

  • 连入因特网的设备: 主机(host) 或 端系统
  • 端系统通过通信链路 和 分组交换机连接到一起
  • 通信链路: 由不同类型的物理媒体构成:
    • 同轴电缆, 铜线, 光纤, 无线电频谱
    • 传输速度: bits/s或bps
  • 端系统向别的端系统发送数据时, 发送端将数据分段, 为每段加上首部字节, 称为分组; 这些分组通过网络发送到目的端系统, 在那里被装备成初始数据.

  • 分组交换机 从它的一条入通信链路接受到达的分组, 并从它的一条出通信链路转发该分组. 主要一下两种:

    • 路由器: 网络核心中
    • 链路层交换机: 接入网中

  • 从发送端到接收端, 一个分组所经历的一系列通信链路和分组交换机称为通过该网络的路径

ISP

  • 端系统通过因特网服务提供商(ISP)接入因特网

  • 各ISP为端系统提供各种不同类型的网络接入

    • 住宅宽带接入, 高速局域网接入, 移动无限接入
  • ISP也为内容提供者提供因特网接入服务
    • 将Web站点和视频服务器直接连入因特网
  • 粗略分等级:
    • 中心(1级): 国际ISPs(网络服务提供者)
    • 2级ISPs: 较小的(一般地区性的)ISPs
    • 3级ISPs和局部/端ISPs, 连接接入网

协议

  • 端系统, 分组交换机和其他因特网部件都要运行一系列的协议, 这些协议控制着因特网中信息的接收和发送

  • 因特网的主要协议: TCP/IP

    • 高效但不可靠的数据传输 — IP
    • 从源到目的地的可靠数据传输 — TCP

网络标准

  • IETF, RFC

1.1.2 服务描述

  • 涉及到多个相互交换数据的端系统的应用程序: 分布式应用程序
  • 与因特网相连的端系统提供了一个套接字接口
    • 该接口规定了运行在一个端系统上的程序 请求因特网基础设施向 运行在另一个端系统上的特定目的地程序 交互数据的方式

1.1.3 什么是协议

  • 协议 定义了在两个或多个通信实体之间交换的报文的格式和顺序, 以及报文发送和/或接受一条报文或者其他事情所采取的动作.

2.2 网络边缘

  • 主机(端系统)运行应用程序

  • 主机分为客户和服务器

1.2.1 接入网

  • 接入网 指将端系统物理连接到其边缘路由器的网络

家庭接入: DSL, 电缆, FTTH, 拨号和卫星

  • 数字用户线DSL
    • 从本地电话接入的本地电话公司处获得DSL因特网接入
    • ISP: 用户的本地电话公司
    • 每个用户的DSL调制解调器使用现有的电话线(即双绞铜线)与位于电话公司的本地中心局(CO)中的数字用户线复用器(DSLAM)交换数据
    • 家庭电话线同时承载了数据和传统的电话信号, 用不同的频率编码
  • 电缆因特网接入:
    • 使用有线电视公司现有的有线电视基础设施
    • 需要电缆调制解调器
    • 不对称: 下载快, 上传慢
    • 共享广播媒体(人多就卡)

  • 光纤入户FTTH

    • 本地中心局直接到家庭提供一条光纤路径
    • 分成主动光纤网络和被动光纤网络
  • 拨号上网

企业(和家庭)接入

  • 使用局域网(LAN)将端系统连接到边缘路由器
  • 以太网Ethernet是最流行的接入技术
  • 无线LAN(WLAN): WiFi
  • 现代家庭网络:
    • 设备
    • 一个与无线PC和其他设备通信的基站(无线接入点)/以太网交换器
    • 一个提供与因特网宽带接入的DSL/电缆调制解调器
    • 一台互联了基站和带有电缆调制解调器的固定PC的路由器(router)/防火墙

现代家庭网络

广域无线接入: 3G和LTE

1.2.2 物理媒体

  • 分类:
    • 导引型媒体
      • 电波沿固体媒体前行
    • 非导引型媒体
      • 电波在空气或外层空间中传播
  • 双绞铜线
  • 同轴电缆
  • 光纤
  • 陆地无线电信道
  • 卫星无线电信道

1.3 网络核心

  • 分组交换机和链路构成的网状网络
  • 核心问题:
    • 数据如何通过网络传播
  • 分类
    • 电路交换(面向连接, 固定的)
    • 分组交换(面向无连接, 到了每个路口自己决定怎么走)

1.3.1 分组交换

  • 类似于公路网, 或者打的

  • 源将报文(message)划分为较小的数据块, 称为分组(packet)

  • 在源和目的地之间, 每个分组都通过通信链路和分组交换机传送

  • 无固定路线
  • 应用A, B的分组共享网络资源
  • 不分配资源
  • 分组每次前进一步: 后在交换机处存储(排队)
  • 每个包用满的带宽
  • 有拥塞问题, 排队

存储转发传输

  • 多数分组交换机在链路的输入端使用存储转发传输
  • 存储转发传输 指在交换机能够开始向输出链路传输该分组的第一个比特之前, 必须接收到整个分组

  • 1路由器1分组: 总时延$2L/R$: $L/R$ 时刻路由器接收整个分组, $2L/R$ 时刻路由器传输了整个分组

  • 1路由器3分组: 时延$4L/R$

  • $N-1$路由器($N$链路)1分组: 时延$N\frac{L}{R}$

排队时延和分组丢失

  • 每台分组交换机连多条链路, 对于每条链路, 有一个输出缓存
  • 如果某条链路正在传输别的分组, 需要在输出缓存中等待, 因此有排队时延
  • 如果缓存满了, 会出现分组丢失(丢包)

转发表和路由选择协议

问题: 路由器如何决定向哪条链路转发:

  • 因特网中每个端系统有IP地址
  • 目的地的IP地址包含于分组的首部
  • 每台路由器有一个转发表, 用于将目的地址(或一部分)映射成输出链路
  • 因特网具有路由选择协议来自动设置转发表

1.3.2 电路交换

  • 类似于铁路网
  • 在端系统间通信期间, 预留了端系统间沿路径通信所需要的资源(缓存和传输速率)
  • 两台主机要通信时, 该网络在两台主机之间创建一条专用的端到端连接
  • 专用资源, 无共享
  • 面向连接, 固定路线
  • 路由器分配资源: 带宽固定
  • 线路分配资源: 频分复用/时分复用/码分复用
  • 性能有保障
  • 有Call setup和teardown, 不灵活

1.3.2.1 电路交换网络中的复用

  • 频分复用FDM和时分复用TDM

  • FDM:

    • 每条连接专用一个频段
    • 频段宽度称为带宽

  • TDM:

    • 时间被划分为固定期间的帧, 每个帧被划分为固定数量的时隙

    • 在循环的TDM帧中, 每条电路被分配相同的专用时隙

    • 传输速率: 帧速率$\times$一个时隙中的比特数量

1.3.2.2 分组交换和电路交换的对比

  • 电路交换存在静默期, 例如打电话的一个人停止说话, 空闲的网络资源不能被其他进行中的连接利用, 因此性能不如分组交换
  • 因此有了虚电路: 分组交换 + 电路交换, 分组交换和电路交换的中间形式(类似于公交车)
    • 路由器或者主要通路固定
    • 资源共享, 需要拥塞控制
    • 资源可被保留, 导致不同的性能
    • 需要连接setup/teardown

1.3.3 网络的网络

  • 多层ISP
  • 存在点PoP(入网点): 存在于除了接入ISP的所有层次, 为提供商的一台或者多台路由器群组, 其中客户ISP能够与供应商ISP连接

  • 多宿: 一个ISP可以和多个提供商ISP连接

  • 对等: 位于相同结构等级层次的邻近的一对ISP可以直接将网络连在一起, 流量不经过上游ISP传输

  • 因特网交换点IXP: 多个ISP在这里一起对等的汇合点
  • 内容提供商网络: 独立于公共因特网, 与多层ISP相连

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

1.4.1 分组交换中的时延概述

时延的类型:

  • 处理时延
    • 包括检查分组首部, 决定该分组导向何处; 检错
  • 排队时延
    • 分组在链路上等待传输的时间
  • 传输时延
    • 将整个分组中所有比特都推向链路所需要的时间
    • 分组长度L, 链路传输速率R, 则传输时延$L/R$
  • 传播时延
    • 一个比特从链路起点到下一个路由器的时间
    • 传播速度接近光速
  • 总时延就是这四种时延之和

1.4.2 排队时延和丢包

  • 分组长度L比特, 分组到达队列的速率$\alpha$, 分组传输速率R
  • 定义流量强度$L\alpha /R$
  • $L\alpha /R>1$, 队列无限增加

  • $L\alpha /R\le 1$, 若到达队列的过程是随机的, 随着流量强度接近于1, 平均排队时延迅速增加

  • 丢包: 队列已满, 没有地方存储, 则丢弃该分组

1.4.3 端到端时延

  • 假设源到目的地之间有N-1台路由器, 网络无阻塞, 则端到端时延为

    $d_{end-end}=N(d_{proc}+d_{trans}+d_{prop})$

  • 可以用traceroute程序查看端到端时延

  • 其他时延:

    • 希望向共享媒体传输分组的端系统可能会有意延迟传输
    • 媒体分组化时延, 出现于IP语音VoIP中

1.4.4 计算机中的吞吐量

  • 瞬时吞吐量, 平均吞吐量: bps
  • 瓶颈链路:
    • 无干扰流量时为链路中最小的那个传输速率
    • 有干扰流量, 高传输速率的链路也可能为平静链路

1.5 协议层次及其服务模型

1.5.1 分层的体系结构

  • 各层的所有协议称为协议栈, 协议栈分成五层: 物理层, 链路层, 网络层, 运输层, 应用层

  • OSI参考模型: 物理层, 链路层, 网络层, 运输层, 会话层, 表示层, 应用层(后三层可以统称为应用层)

(1) 应用层

  • 应用层是网络应用程序及它们的应用层协议存留的地方. 应用层协议分布在多个端系统上, 一个端系统上的应用程序使用协议和另一个端系统上的应用程序交换信息分组
  • 应用层的信息分组称为报文(message)
  • FTP, SMTP, HTTP

(2) 运输层

  • 因特网的运输层在应用程序端点之间传送应用层报文
  • TCP, UDP
    • TCP面向连接, 包括确保传递和流量控制, 将长报文划分成短报文, 有拥塞, 可靠
    • UDP提供无连接服务, 不可靠, 无流量控制, 无拥塞机制
  • 运输层的分组称为报文段(segment)

(3) 网络层

  • 网络层负责将称为数据报(datagram)的网络层分组从一台主机移动到另一台主机
  • 运输层协议向网络层提交运输层报文段和目的地址
  • IP协议

(4) 链路层

  • 为了将分组从一个节点(主机或路由器)移动到路径上的下一个节点, 网络层需要依靠链路层的服务
  • 一个数据报可以被沿途不同链路上的不同链路层协议处理
  • 网卡实现
  • 差错检测, 流量控制
  • PPP, 以太网
  • 链路层分组: 帧(frame)

(5) 物理层

  • 链路层任务是将整个帧从一个网络元素移动到邻近的网络元素, 而物理层的任务是将该帧中的一个个比特从一个节点移动到下一个节点
  • 物理层协议依然链路相关, 并且和实际传输媒体(例如双绞铜线, 单模光纤)有关

1.5.2 封装

  • 封装: 应用层报文传送给传输层, 传输层收到报文并附上附加信息(传输层首部信息); 其他层之间也类似
  • 在每一层, 一个分组具有两种类型的字段: 首部字段和有效载荷字段. 有效载荷字段来自上一层的分组
  • 链路层交换机实现了协议栈中的第一层和第二层
    路由器实现了协议栈中的第一层到第三层
    主机实现了所有5个层次

1.6 面对攻击的网络

1.6.1 坏家伙能够经因特网将有害程序放入你的计算机中

  • 恶意的东西统称为恶意软件
  • 恶意软件感染我们设备后, 可以做各种不正当的事情, 包括删除文件, 安装间谍软件收集隐私信息并发给坏家伙

  • 受害主机可以称为众多受害设备网络中的一员, 它们统称为僵尸网络

  • 坏家伙可以通过僵尸网络控制并对目标主机展开垃圾邮件分发或者分布式拒绝服务攻击

  • 多数恶意软件是自我复制的: 感染一台主机后从那台主机寻求进入因特网上的其他主机
  • 病毒是一种需要某种形式的用户交互来干扰用户设备的恶意软件
    • 例如包含恶意可执行代码的电子邮件附件
  • 蠕虫是一种无须任何明显用户交互就能进入设备的恶意软件
    • 例如用户运行了一个攻击者能够发送恶意软件的脆弱网络应用程序

1.6.2 坏家伙能够攻击服务器和网络基础设施

  • 拒绝服务攻击DoS: DoS攻击使得网络, 主机或其他基础设施部分不能由合法用户使用
  • 主要三种:
    • 弱点攻击: 发送制作精细的报文
    • 带宽洪泛: 发送大量分组
    • 连接洪泛: 创建大量半开或者全开TCP连接
  • 分布式DoS(DDoS): 攻击者控制多个源并让每个源向目标猛烈发送流量

1.6.3 坏家伙能够顾嗅探分组

  • 在无线传输设备的附近放置一台被动的接收机, 接收机就能得到传输的每个分组的副本
  • 记录每个流经的分组副本的被动接受器称为分组嗅探器

1.6.4 坏家伙能够伪成你认识的人

  • 将具有虚假源地址的分组注入因特网的能力称为IP哄骗

第3章 运输层

3.1 概述和运输层服务

  • 运输层协议为运行在不同主机上的应用进程之间提供了逻辑通信.
  • 运输层协议在端系统中实现.
  • 运输层分组称为报文段. 运输层将从发送应用程序进程接收到的报文转换成报文段, 然后在发送端系统中, 运输层将这些报文段传递给网络层, 网络层将其封装成数据报并向目的地发送; 在接收端, 网络层从数据报中提取运输层报文段, 并上交给运输层, 运输层处理接收到的报文段, 使报文段中的数据为接受应用进程所使用.
  • 因特网有两种运输层协议: TCP和UDP.
    • UDP: 不可靠, 无连接
    • TCP: 可靠, 面向连接
  • IP的服务模型是尽力而为交付, 所以称为不可靠服务. TCP和UDP的最基本的责任是, 将两个端系统间IP的交付服务扩展为运行在端系统上的两个进程之间的交付服务, 即运输层的多路复用和多路分解.
  • TCP和UDP都会进行差错检查.
  • TCP通过流量控制, 序号, 确认和定时器提供可靠数据传输, 还提供拥塞控制.

3.2 多路复用和多路分解

  • 一个进程有一个或多个套接字, 相当于从网络向进程传递数据和从进程向网络传递数据的门户.
  • 将运输层报文段中的数据交付到正确的套接字的工作称为多路分解
  • 源主机从不同套接字中收集数据块, 并为每个数据块封装上首部信息从而生成报文段, 将报文段传递到网络层, 所有这些工作称为多路复用
  • 套接字有唯一标识符, 每个报文段有特殊字段指示该报文段所要交付到的套接字, 即源端口号字段和目的端口号字段
  • 端口号是一个16比特的字段, 0-1023范围的端口号称为周知端口号, 是保留给周知应用层协议使用的.
  • UDP套接字是由一个二元组(目的IP地址, 目的端口号)全面标识的, 不同源IP/端口号但相同目的IP和端口号的UDP报文段会通过相同的目的套接字被定向到相同目的进程
  • TCP套接字是由一个四元组(源IP地址, 源端口号, 目的IP地址, 目的端口号)标识的, 不同源IP/端口号的TCP报文段会定向到不同的套接字, 除非是包含初始创建连接请求的报文段(目的端口号12000)
  • 对于web服务器, 一个进程对应多个套接字

3.3 无连接运输: UDP

  • UDP只是做了运输协议能够做的最少工作, 即复用/分解和少量的差错检测
  • DNS使用UDP协议
  • UDP相比TCP的优点:
    • 关于发送什么数据以及何时发送的应用层控制更为精细
    • 无须连接建立
    • 无连接状态
    • 分组首部开销小

3.3.1 UDP报文段结构

  • 首部4个字段:
    • 源端口号
    • 目的端口号
    • 长度
    • 检验和

3.3.2 UDP检验和

  • 对报文段中的所有16比特字求和(有溢出的加法需要回卷, 即最高位的记为加到最低位), 再取反码(01对换).

  • 需要检验和的原因: 不保证所有链路提供差错检验, 所以必须在端到端基础上在运输层提供差错检验.

  • UDP提供差错检测但不提供差错恢复

3.4 可靠数据传输原理

3.4.1 构造可靠数据传输协议

  1. rdt 2.0
  • 因为信道可能有比特差错, 所以需要使用肯定确认ACK和否定确认NAK
  • 自动重传请求(ARQ)协议: 差错检测, 接收方反馈, 重传
  • 发送放在确认接收方正确接受之前需要等待, 因此称为停等协议
  1. rdt 2.1
  • 考虑到ACK和NAK分组受损的可能, 在分组中加入了序号. 一旦发送方接收到对同一个分组的2次ACK(冗余ACK), 就知道接收方没有正确接受到该分组后的分组.
  1. rdt3.0
  • 假设可能丢包, 发送方选择一个时间值, 以判定可能发生了丢包
  • 如果在这个时间内没有收到ACK, 则重传
  • 因此需要一个倒计时计数器

3.4.2 流水线可靠数据传输协议

  • 停等太慢, 所以改为流水线
  • 流水线需要:
    • 增加序号范围
    • 协议的发送方和接收方两端缓存多个分组
    • 所需序号范围和对缓冲的要求取决于数据传输协议如何处理丢失, 损坏以及延时过大的分组. 解决流水线的差错恢复有两种基本方法: 回退N步和选择重传

3.4.3 回退N步

  • 定义基序号为最早未确认分组的序号, 下一个序号为最小的未使用序号, 则将序号范围分割为4段:

    • $[0, base-1]$: 已经发送并确认
    • $[base, nextseqnum-1]$: 已经发送但是未确认
    • $[nextseqnum, base+N-1]$: 要被立即发送的分组
    • $\ge base+N$: 不能使用, 直到前面的未确认分组被确认

  • $N$: 窗口长度(为了流量限制)

  • 回退N步(GBN)协议也被称为滑动窗口协议
  • 设接受方上次交付给上层 数据是序号为$n-1$的分组,
    • 如果正确接收到序号为$n$的分组, 为其发送一个ACK, 并交付给上层
    • 其他所有情况, 丢失(失序)分组, 为$n-1$分组重新发送ACK

3.4.4 选择重传

  • 选择重传(SR)协议通过让发送方只重传那些它怀疑在接收方出错(丢失或受损)的分组而避免了不必要的重传.
  • SR确认方接受一个正确接收的分组而不管其是否按序

  • 发送方:

    • 从上层收到数据, 检查下一个可用于该分组的序号. 如果在窗口内就发送, 否则缓存.
    • 超时: 每个分组有一个自己的逻辑计时器
    • 收到ACK: 如果序号在窗口内, 标记为已接受; 否则, 窗口基序号前移到具有最小序号的未确认分组处. 如果移动后窗口内有未发送分组, 则发送这些分组.

  • 接收方:

    • 序号在$[rcv_base, rcv_base + N - 1]$(窗口内)被正确接收, 则返回ACK
    • 序号在$[rcv_base-N,rcv_base-1]$, 则是接收方已经确认过的分组, 一定要发送ACK.
      • 这种情况是因为之前接收方发的ACK没有到达发送放, 如果此时不发ACK, 会使发送方的窗口一直无法前进
    • 其他情况忽略

  • 如果序号范围有限, 发送发和接收方的窗口不一致会产生严重后果, 无法区分新分组和重发的分组

3.5 面向连接的运输: TCP

  • TCP连接是逻辑连接
  • TCP连接提供的全双工服务: 一台主机的进程A和另一台主机的进程B存在一条TCP连接, 那么应用层数据可以
    A到B也可以B到A. TCP连接也是点对点的.
  • TCP连接建立: 三次握手
  • 最大报文段长度MSS: 指在报文段里应用层数据的最大长度, 不含TCP首部. 根据最大传输单元MTU设置.
  • TCP连接的组成: 一个台主机上的缓存, 变量和进程连接的套接字和另一个台主机上的缓存, 变量和进程连接的套接字.

3.5.1 TCP报文段结构

TCP报文结构

  • TCP首部一般20字节, 比UDP多12字节

  • 源端口号和目的端口号

  • 序号
    • 是该报文段首字节的字节流编号
  • 确认号
    • 主机A填充进报文段的确认号是主机A从主机B收到的下一报文段的首字节的序号
    • TCP只确认该流中至第一个丢失字节为止的字节, 称为累计确认
  • 校验号
  • 接收窗口字段(rwnd)
    • 用于流量控制, 指示接收方愿意接受的字节数量
  • 首部长度字段
    • 以32比特的字为单位
  • 选项字段
  • 标志字段
    • ACK: 指示确认字段中的值是有效的
    • RST, SYN, FIN用于连接的建立和拆除
    • CWR, ECE: 明确拥塞通告
    • PSH: 指示接收方应立即将数据交给上层
    • URG:报文段里存在着被发送端的上层实体设为 “紧急” 的数据

3.5.3 往返时间的估计

  • 往返时间RTT: 一个报文段发出到它被确认的时间

  • $\text{EstimatedRTT}=(1-\alpha)\cdot \text{EstimatedRTT}+\alpha\cdot \text{SampleRTT}$

    • 如果RTT序号越小越新, 则

    • 一般$\alpha=0.125$,

    • 称为指数加权移动平均EWMA

  • 估计偏离程度: $\text{DevRTT}=(1-\beta)\cdot\text{DevRTT}+\beta\cdot|\text{SampleRTT}-\text{EstimatedRTT}|$

  • 一般$\beta=0.25$

  • TCP超时间隔: $\text{TimeoutInterval}=\text{EstimateRTT}+4\cdot\text{DevRTT}$

    • 推荐初始值为$1 s$, 超时则翻倍
    • 只要收到(非重传)报文段并更新了$\text{EstimatedRTT}$, 就用上述公式重新计算$\text{TimeoutInterval}$

3.5.4 可靠数据传输

  • 快速重传:

    • 冗余ACK: 再次确认某个报文段的ACK
    • TCP发送方收到对相同数据的3个冗余ACK, 说明跟在后面的数据报已经丢失, 就进行快速重传

  • 使用回退N步和选择重传的混合体: 选择确认, 即有选择地确认收到地报文，而非采用累计确认.

  • 发送端事件处理大致如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    /*假设发送方不受TCP流量控制和拥塞控制，每一个数据小于MSS.*/
    NextSeqNum = InitialSeqNum
    SendBase = InitialSeqNum

    loop(永远){
      switch(event):
      
        case 从上层应用接收数据：
          生成序号为NextSeqNum的报文;
          if(定时器没有启动){
            启动定时器;
          }
          向IP传递报文;
          NextSeqNum += 数据字节数;
          break;

        case 超时：
          重传SendBase对应的TCP报文; /*和GBN不同之处*/
          TimeoutInterval *= 2;
          重启定时器; /*每次重传一个报文后都会重新启动定时器*/
          break;

        case 接收ACK, AN = y:
          if(y > SendBase){
            SendBase = y; /*采取累计确认*/
            重新计算TimeoutInterval;
            if(仍有发送且未确认报文){
              重启定时器;
            }
          }
          else{/*实际上此时y == SendBase*/
              y的冗余数量 += 1;
              if(y的冗余数量 == 3){
                /*快速重传*/
                立即重传序号为y对应的报文;
              }
          }
          break;
    }

  • 接收端产生ACK的情况在RFC 5681中建议：

    | 事件 | 动作 |
    | :—————————————————————————————- | :—————————————————————————————- |
    | 具有所期望序号的按序报文段到达 且在此之前的报文段都已经被确认 即本报文段是当前状态下第一个接收但未被确认的报文 | Delayed ACK，延迟ACK发送 (根据本地的计时器设定, 如果在短时间内还有可以接收的报文段，那么可以减少ACK的数量) |
    | 具有所期望序号的按需报文段到达 且当前有一个报文段等待ACK传输， 即此时处于事件一的状态 | 立马发送ACK，确认这两个报文 |
    | 比所期望序号大的失序报文段到达， 即接收产生了空隙 | 立马发送一个冗余ACK |
    | 收到能够填补间隙的报文段 | 如果该报文段序号是间隙的低端， 则马上发送ACK |

3.5.5 流量控制

  • TCP为它的应用程序提供了流量控制服务以消除发送方使接收方缓存溢出的可能

  • TCP也有可能因为IP网络的拥塞而被遏制, 这种形式的发送方的控制称为拥塞控制

  • TCP通过让发送方维护一个称为接收窗口(rwnd)的变量来提供流量控制, 确保

    $\text{LastByteRecd}-\text{LastByteRead}\le \text{RcvBuffer}$, 因此

    $\text{rwnd}=\text{RcvBuffer}-[\text{LastByteRecd}-\text{LastByteRead}]$

  • 主机B把当前的$\text{rwnd}$值放入它给主机A的报文段接收窗口字段中, 主机A保证

    $\text{LastByteSent}-\text{LastByteAcked}\le \text{rwnd}$

    • 如果主机B的$\text{rwnd}=0$, 主机A依然发送1字节数据的报文段, 被确认后就知道主机B的缓存清空后的新$\text{rwnd}$值

3.5.6 TCP连接管理(必考)

连接建立

三次握手:

三次握手

  1. 客户端发送不含应用层数据的特殊TCP报文段, 其中SYN比特置1. 同时客户端随机选择一个初始序号($\text{client_isn}$)
  2. 服务器收到SYN报文段后, 服务器为该TCP连接分配YCP缓存和变量, 并向客户端发送允许连接的SYNACK报文段(也不含应用层数据). SYN比特置为1, 确认号ACK为$\text{client_isn}+1$, 服务器选择自己的初始序号$\text{server_isn}$.
  3. 收到SYNACK报文段后, 客户也要为该连接分配缓存和变量. 客户主机向服务器发送另一个报文段, 对服务器的允许连接的报文段进行确认, 确认号ACK为$\text{server_isn}+1$, SYN比特置为0, 序列号为$\text{client_isn}+1$.
  • 快速连接: 发送SYN的时候就带数据, 第三次握手不光是ACK还是FIN.
  • 客户端time wait: 保证ACK已经被收到; 防止影响后续连接
  • 服务端没有time wait

例子:

  • 客户端: SYN 1056
  • 服务端: SYN 2078, ACK 1057
  • 客户端: SN 1057, ACK 2079
  • 连接已经建立
  • 客户端: SN 1057(并没有+1)

连接关闭

四次挥手

  • 客户端向服务器发送FIN
  • 服务器收到后发ACK确认
  • 服务器发自己的终止报文段FIN
  • 客户对终止报文段发ACK确认
  • 同样的, 客户端需要time wait. 原因: 可能最后A的ACK丢失，导致B重发FIN/ACK，这个2MSL能够保证A能够获得重发的数据报并回应。

例子:

  • 客户端: FIN 7080, ACK 6079

  • 服务器: SN 6079, ACK 7081

  • …

  • 服务器:FIN 10679, ACK 7081
  • 客户端: SN 7081, ACK 10680

TCP状态

TCP状态图

  • 如果一台主机接收了具有目的端口80的TCP SYN分组, 但是该主机在端口80不接受连接(即它不在端口80上运行Web服务器), 则该主机向源发送一个特殊重置报文段, 该报文段的RST标记位置为1.
  • 因此探索一台主机上的一个特定端口, nmap将对该端口发送一个TCP SYN报文段
    • 如果收到TCP SYNACK, 则目标主机上一个应用程序使用该TCP端口
    • 如果收到TCP RST, 说明SYN到达了目标主机但是目标主机并没有使用该端口号的应用程序
    • 如果什么都没有收到, 那么可能该SYN报文段被中间的防火墙锁阻挡

补充: 崩溃检测

  • 如果一边崩溃重启, 状态丢失, 连接半开
  • 当任意报文段i到达, 重启的那端发送RST i, 从而另一端关闭连接
  • 或者多次重试后关闭

3.6 拥塞控制原理

3.6.2 拥塞控制方法

  • 端到端拥塞控制: TCP报文段的丢失(通过超时或者三次冗余确认而得知)被认为是网络拥塞的迹象, TCP会相应的地减少其窗口长度, 且可以增加往返时延值.
  • 网络辅助的拥塞控制, 例如拥塞分组, 或者路由器标记或更新从发送方通知该网络拥塞指示

3.7 TCP拥塞控制

  • TCP采用的拥塞控制方法是让每一个发送方根据所感知到的网络拥塞程度来限制其能向连接发送流量的速率.

TCP发送方限制其向连接发送流量速率的方法

  • 发送方跟踪一个额外的变量: 拥塞窗口(cwnd)
  • 在一个发送方中, 未被确认的数据量不会超过$\min\{\text{cwnd}, \text{rwnd}\}$. rwnd为接收窗口(由接受缓存决定)

TCP发送方如何感知在它和目的地之间的路径上出现了拥塞

  • 定义丢包事件: 超时或者三次冗余ACK
  • 当出现过度的拥塞时, 在这条路径上的一个或多个路由器的缓存会溢出, 引起丢包.
  • 因为TCP使用确认来触发增大它的拥塞窗口长度, 所以TCP被称为是自计时的.

TCP拥塞控制算法

  1. 慢启动

  • cwnd初始值为1MSS, 较小.

  • 每当传输的报文段被首次确认, cwnd就翻倍, 指数增长.

  • 停止慢启动的时机:
    • 如果存在一个超时指示的丢包事件, TCP发送方将cwnd设置为1MSS, 且将第二个状态变量ssthresh(慢启动阈值)设为cwnd/2, 即拥塞窗口值的一半.
    • 检测到cwnd的值到达或超过ssthresh后, 结束满启动, 并且TCP转移到拥塞避免状态, 更加谨慎地增加cwnd.
    • 检测到3个冗余ACK, 则执行快速重传并进入快速恢复状态
  1. 拥塞避免
  • 一旦进入拥塞避免状态, cwnd大约为上次拥塞时的值的一半, 每次cwnd的值增加一个MSS.
  • 超时则cwnd设为1MSS, 更新ssthresh为cwnd/2
  • 碰到三个冗余ACK, 将cwnd减半(再根据冗余ACK的数量增加相应个数的MSS), ssthresh记为cwnd/2, 并进入快速恢复状态
  1. 快速恢复
  • 在快速恢复中, 对于引起TCP进入快速恢复状态的缺失报文段, 对收到的每个冗余的ACK, cwnd的值增加1个MSS.
  • 当缺失报文段的最后一个ACK到达时, TCP将降低cwnd后进入拥塞避免状态
  • 超时处理方法同1中
  • TCP Reno: 三次冗余ACK后窗口减半; TCP Tahoe: 三次冗余和超时一样, 窗口置1
  1. TCP拥塞控制: 回顾
  • 加性增, 乘性减(AIMD)模式: 每个RTT内cwnd线性增加1, 出现3个冗余ACK后减半

第4章 网络层: 数据平面

4.2 路由器工作原理

  • 路由器的两个主要功能:
    • 运行路由算法
    • 从输入端口到输出端口转发分组
  • 路由器的4个组件
    • 输入端口
    • 交换结构
    • 输出端口
    • 路由选择处理器

路由器结构

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

  • 输入端口处理:
    • 线路端接->数据链路处理(协议, 拆分)->查找, 转发, 排队->交换结构
  • 目的地转发:
    • 路由器转发表采用前缀匹配的方式生成表项，对于每一个链路接口，其目的地址范围的前缀为表项中的前缀匹配
    • 当存在多个成功匹配时，采用 最长前缀匹配规则，转发到匹配长度最长的那个链路接口
  • 转发见下面对比中

4.2.2 交换

  • 经内存交换
    • 第一代交换机
    • 速度由内存带宽限制
  • 经总线交换
    • 速度由带宽限制
  • 经互联网络交换
    • 数据报分为固定大小的单元, 在网络中交换单元

4.2.3 输出端口处理

  • 交换结构—>排队(缓存管理)—>数据链路处理(协议, 封装)—>线路端接

  • 包括选择和取出排队的分组进行传输, 执行所需的链路层和物理层传输功能

  • 缓冲满的时候选择扔掉的分组

4.2.4 何处出现排队

  • 缓存空间无内存可用: 丢包

  • 输入排队:

    • 两个输入队列前端的分组发往同一个输出队列
    • 线路前部阻塞: 被位于线路前部的另一个分组阻塞

  • 输出排队

4.2.5 分组调度

排队的分组如何经输出链路传输:

  • 先进先出
  • 优先权排队
    • 将到达输出链路的分组按照优先级分成多个类，优先级高的类先传输，类内采用FIFO的方式
    • 非抢占式优先权排队：一旦分组开始被传输，即使此时有更高优先级的分组到达，该分组的传输也不会被打断
  • 循环排队
    • 将分组分成多个类，循环调度器在类之间轮流传输
  • 加权公平排队
    • 循环排队基础上每个类加权

4.3 网际协议: IPv4, 寻址, IPv6和其他

  • IP操作
    • 路由
    • 数据报生命周期
    • 分片和重装
    • 错误控制
    • 流控制
  • 路由:
    • 主机和路由器维护路由表
  • 数据报生命周期:
    • 数据报可能会不确定地循环
    • 在IP中用TTL(time to live)标记lifetime, 一旦用完, 数据报就会被丢弃
    • lifetime的类型: 跳数, 每次在路由器间传递, 减少TTL

4.3.1 IPv4数据报格式

IPv4首部

IP首部字段(不用背):

  • 版本: 4 or 6(见后面)
  • 首部长度(4 bits)
  • 服务类型(8 bits)
    • 说明该IP数据报是什么类型, 包括优先级 Precedence, 可靠性, 延迟, 吞吐量
  • 数据报长度(16 bits): 首部+数据的长度
  • 标识(16 bits)
    • 序列号
    • 和地址以及协议唯一标识数据报
  • 标志flags(3bits)
    • More flags
    • Don’t fragment
  • 片偏移(13bits)
  • 寿命TTL(8bits)
  • 协议(8bits)
    • tcp, udp, ospf, (不可能是rip, 因为rip直接装在udp里面, udp装在ip里面)
  • 首部校验和:
    • 计算首部中所有16bits words的校验和
    • 在每个路由器中重新计算
  • 源地址(必考)
  • 目的地址
  • 选项及padding(凑整的): 可有可无

4.3.2 分片和重装

  • 最大传送单元MTU: 一个链路层帧能够承载的最大数据量。

  • 分片和重装: 分组长度超过了网络的MTU

  • 位置:

    • IPv4的分片在路由器实现(IPv6在主机)
      • 一个数据报变为多个小数据报
    • IP的重装只在目的地实现

  • 实现:

    • 分片. IPv4数据报分片利用标识，标志，片偏移三个字段:

      • 发送主机通常将它发送的每一个数据报的标识号(ID)依次加1
      • 分片后每个片(一个小的数据报)的源地址，目的地址，标识号一致，接收方可以通过标识号判断两个片是否属于同一个大的IP数据报
      • 片偏移(在原始数据包中的位置(不含头), 以8个字节为单位, 因此计算片偏移需要除以8.)
      • more flag: 判断是不是最后一个分片. 只有最后一个分片的more flag标志为1.

      多次分片容易导致碎片化.

    IPv4分片

    • 重装:

      • 预留足够的缓冲区(开始不知道要多少)

      • 分片到达, 则放在缓冲区的对应位置

      • 知道所有的数据域都重装

  • 失败:

    • 当分片丢失

    • 重装超时, 扔掉所有的部分数据

    • 使用分组lifetime(TTL in IP)

      • 随着分组下降, 超时则杀死所有数据
    • IPv6使用源分片

错误控制和流量控制

  • 错误控制:

    • 不保证到达
    • 如果分组丢失, 路由器试图告诉信息源

  • ICMP用于发送错误信息

    • 源可能用更高层的协议

  • 流量控制

    • 运行路由器限制到达数据速率
    • 当缓冲区满了, 路由器丢弃输入分组
      • 可能告知源
      • 使用ICMP

4.3.3 IPv4编址 (非常重要, 必考)

  • 接口: 主机与物理链路之间的边界
    • 一般一个主机有一条链路和一个接口, 路由器有多个链路和多个接口
  • IP要求每台主机和路由器接口拥有自己的IP地址(全球唯一, NAT除外)
  • 每个IP地址32位(4字节), 按照点分十进制记方书写, 即每个字节用十进制, 各字节之间用点隔开.
  • 包含2部分: 网段地址和主机地址, Net+Host
  • IP只关心网段之间的通讯
  • 0和255慎用, 0表示网段地址, 255广播地址
  • 在CIDR被采用之前使用分类编址:具有8, 16, 24比特的子网分别被称为A, B, C类网络.
  • A类网, B类网, C类网(略)
  • 子网和子网掩码
    • 子网: 分开主机和路由器的每个接口, 产生几个隔离的网络岛, 使用接口端接这些隔离的网络的端点. 这些隔离的网络中的每一个都叫做一个子网.
    • 解决网络地址使用不充分问题
    • 地址通过子网掩码分为子网数和主机数
    • CIDR(无类别域间路由选择)
    • 网段地址A.B.C.D/n, n为IP前缀, 表示掩码的1的数量, 前n位为IP地址的网络部分, 后32-n位用于分配组织内部设备使用
  • 地址汇聚:
    • 多个网段看做一个更大的网 段

获取主机IP地址: DHCP协议

DHCP(动态主机配置协议): 主机刚入网如何获取IP地址DHCP

分为以下四步骤:

  • DHCP服务器发现(discover)
    • 一台新到达的主机的首要任务是发现一个要与其交互的DHCP服务器
    • 因为不知道服务器的IP地址, 所以客户生成包含DHCP dicover的IP数据报, 广播目的地址255.255.255.255(广播), 本主机地址0.0.0.0, 传给链路层, 广播到该子网的所有节点.
  • DHCP服务器提供(offer)
    • DHCP服务器收到一个DHCP discover报文时, 用DHCP offer报文向客户做出响应, 向子网的所有节点广播, 使用地址255.255.255.255
    • 可能有多台DHCP服务器, 他们向客户提供的报文包含:
      • 收到的发现报文的事务ID
      • 向客户推荐的IP地址
      • 网络掩码
      • IP地址租用期
  • DHCP请求(request)
    • 新到达的客户从一个或多个DHCP offer中选择一个, 并向选取的DHCP offer用 DHCP request报文进行响应(含DHCP服务器ID, 即选择的那个服务器的offer包的IP头里面的IP地址), 回显配置的参数.

  • DHCP ACK

    • 服务器用DHCP ACK报文对DHCP request进行响应

  • 全部使用IP广播

4.3.4 网络地址转换(NAT)

  • 内部(虚拟地址)和外部地址分开
  • 和外网通信时转换IP地址
  • NAT使能路由器对于外部来说可以就是一个具有单一IP地址的单一设备，而其实际上对外部隐藏了内部网络的细节。
  • 内部网络使用的IP地址是RFC 1918中保留的IP地址空间之一，用于家庭网络等专用网络或者具有专用地址的地域(即其地址只对该网络中设备有意义)

NAT

  • 实现:
    • 用NAT表的方式进行地址转换, 记录对应的WAN端和LAN端的IP地址和端口号
    • 通过分配不同的源端口号来区分内部的主机
    • 内部主机向外通信，发送源地址为主机IP地址，端口号随机生成的报文
    • NAT使能路由器接收到内部主机发送的报文后，改变源地址为自身IP地址，生成一个不在NAT表中的端口号，发送报文，随后添加NAT表项
    • 外部主机收到后，发送 目的地址为路由器IP地址，端口号为路由器生成端口号的 响应报文
    • NAT使能路由器接收到外部主机的响应报文后，通过查NAT表，来转发给内部主机

4.3.5 IPv6

IPv6数据报格式

IPv6首部

  • IPv6引入的主要变化

    • 扩大的地址容量: 32bits变为128bits, 冒分(冒号分隔); 还引入的任播地址(传播给任意一个)

    • 简化高效的40字节首部, 许多IPv4字段被舍弃或者作为选项. 舍弃的字段:

      • 分片/重装: 不允许在路由器上分片
      • 首部校验和: 因为运输层协议(TCP与UDP)和链路层(以太网协议)都有差错检测，所以在网络层不需要再进行检测
      • 选项: 不在标准IP首部内, 但是可能在IPv6首部的”下一个首部”指出的位置上. 这样IP首部就是定长的了
    • 流标签: 给属于特殊流的分组加上标签, 这些特殊流是发送方要求进行特殊处理的流, 如一种非默认服务质量或需要实时服务的流. 例如音频和视频传输

  • IPv6首部字段:

    • 版本: 4或6
    • 流量类型: 同IPv4的服务类型
    • 流标签: 标识一条数据报的流, 能够对一条流中的某些数据报给出优先权
    • 有效载荷长度: 在定长的40字节首部后面的字节数量, 不含首部(IPv4的数据报长度包含首部)
    • 下一个首部: 标识数据报内的内容(数据字段)需要交付给哪个协议, 同IPv4的协议字段
    • 跳限制: 每一跳-1, 到0则丢弃. 和IPv4中寿命(TTL)用处一致
    • 源地址和目的地址: 从原来的32比特改为了128比特

题目:

IPv4首部图, 哪些字段在经过中间路由器的时候肯定不会被修改(分为不考虑和考虑NAT)

IPv4和IPv6的互通

隧道模式:

tunnel

  • 两台IPv6路由器之间的连续的IPv4路由器合成为一个隧道。
  • 隧道入口处的IPv6路由器，会将IPv6报文当作数据, 封装在IPv4报文的数据部分，将IPv4数据报的目的地址设为隧道出口处的IPv6路由器，并将IPv4数据报的上层协议设为41(表明数据部分是一个IPv6数据报)
  • 隧道中的IPv4路由器就像处理正常的IPv4数据报一样转发。
  • 出口处的IPv6路由器根据IPv4数据报中上层协议为41从而取出中间的IPv6数据报，然后进行相关操作。

第5章 网络层: 控制平面

5.1 概述

  • 计算维护和安装转发表和流表
  • 两种可能方法:
    • 每路由器控制: 每台路由器运行一种路由选择算法
    • 逻辑集中式控制: 需要控制代理CA和控制器通信并且按控制器命令行事, CA不能直接相互交互, 也不主动参与计算转发表

5.2 路由选择算法

  • 路由选择算法的目的是从发送方到接收方的过程中确定一条通过路由器网络的好的路径.

  • 不同的路由策略:

    • 集中式路由选择算法:
      • 用完整的全局性的网络制式计算出源到目的地之间的最低开销路径
      • 具有全局状态信息的算法称为链路状态(LS)算法
    • 分散式路由选择算法:
      • 路由器以迭代, 分布式的方式计算出最低开销路径
      • 没有结点拥有关于所有网络链路开销的完整信息
      • 例如距离向量(DV)算法

  • 洪泛:

    • 不需要网络信息
    • 分组转发到路由器的每个邻居
    • 很多副本到达目的地
    • 缺点: 多副本, 环路问题
    • 优点:
      • 尝试所有路径, 鲁棒
      • 至少一个分组采用最小消耗道路
      • 访问所有路由器
  • 随机路由: 随机选取一个输出路径
  • 最小消耗算法:
    • Dijkstra算法
    • Bellman-Ford算法

5.2.1 链路状态(LS)路由选择算法

  • 在该算法中，网络拓扑和所有链路开销都是已知的。实践中是通过让每个节点向网络中广播链路状态分组来完成的。其中链路状态分组包含和自己相连的链路的开销信息，这常常由 链路状态广播算法完成(洪泛)
  • 使用协议：OSPF，使用的算法：Dijkstra算法，复杂度$O(|V|^2)$.

Dijkstra算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1   Initialization: 
2    N’ = {u} 
3    for all nodes v 
4      if v is a neighbor of u 
5        then D(v) = c(u, v) 
6      else D(v) = ∞ 
7  
8   Loop
9    find w not in N’ such that D(w) is a minimum 
10   add w to N’ 
11   update D(v) for each neighbor v of w and not in N’: 
12         D(v) = min(D(v), D(w)+ c(w, v) ) 
13    /* new cost to v is either old cost to v or known 
14     least path cost to w plus cost from w to v */ 
15  until N’= N
  • 找给定源到其他所有节点之间的最短路
  • k次迭代后得到k个目的节点的最低开销路径
  • 例子见书P246
  • 存在的问题：拥塞敏感的选择振荡
    • 在拥塞敏感且将路径负载当作开销的情况下，所有路由器同时运行LS算法，会使得由于选择了某一条目前最短开销路径而导致网络中路径开销改变，LS算法得出的最短开销路径会不断摇摆振荡。
    • 解决办法是 使每台路由器广播链路状态分组的时间随机化。

5.2.2 距离向量(DV)路由选择算法

  • 该算法是一种 迭代的，异步的，分布式的算法，使用的协议有BGP，RIP.
  • 使用的算法：Bellman-ford算法，复杂度$O(|V||E|)$，算法关键为$d_x(y)=\min_v\{c(x,v)+d_v(y)\}$

Bellman-Ford算法

在每个节点x:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1  Initialization: 
2    for all destinations y in N: 
3       Dx(y)= c(x, y)/* if y is not a neighbor then c(x, y)= ∞ */ 
4    for each neighbor w 
5       Dw(y) = ? for all destinations y in N 
6    for each neighbor w 
7       send distance vector  Dx = [Dx(y): y in N] to w 
8 
9  loop 
10    wait  (until I see a link cost change to some neighbor w or 
11            until I receive a distance vector from some neighbor w) 
12 
13    for each y in N: 
14        Dx(y) = min_v {c(x, v) + Dv(y)} 
15 
16 if Dx(y) changed for any destination y 
17       send distance vector Dx = [Dx(y): y in N] to all neighbors 
18 
19 forever
  • 每个节点维护一张路由选择表, 包含 该点和它的所有邻居 到 所有节点 的开销
  • 初始计算自己的距离向量$D_x=[D_x(y):y\in N]$,发送自己的距离向量给相邻节点
  • 保存相邻节点距离向量，并依据其更新自己的距离向量，再循环
  • 例子:

DVtable

存在的问题：无穷计数

  • 当DV算法稳定后，网络中某条链路开销突然改变后，可能会出现路由选择环路，节点间的最短路径互相依赖，结果会在节点间不断来回变换，直到最后稳定，变换的次数和链路开销改变后的值相关，值足够大时会导致变换很多次，因此被称为无穷计数问题.
  • 解决方法：毒性逆转，即某一结点z到达x的最小开销路径的下一跳是y的话，z发送给y的信息中，z到x的最小开销为正无穷，使得此时y不可能通过依赖z来选择到达x的最小开销链路，从而避免无穷计数. 毒性逆转并不能完全解决无穷计数问题.

两者对比

LS:

  • 链路状态通过洪泛告知其他节点
  • 每个节点有复杂的拓扑, 构造自己的路由表
  • 鲁棒性好
  • 收敛快

DV:

  • 每个节点维护距离向量
  • 向量和邻居节点交换
  • 分布式构建路由表
  • 报文简单
  • 鲁棒性差
  • 收敛慢

5.3 因特网中自治系统内部路由协议

  • 自治系统AS: 一个ISP中的路由器以及互联他们的链路构成一个AS
  • 同一个AS中使用同一个路由协议

  • 网关:

    • AS之间的路由
    • 同AS内与其他路由器之间的路由

  • IGP—自治系统内部协议

    • RIP: 使用距离向量
    • OSPF: Open Shortest Path First, 使用链路状态
  • EGP—自治系统之间
    • BGP

RIP

  • 使用DV算法，应用于应用层
  • 在路由表或报文中Distance Matric表明当前节点(路由器)到达目的子网的跳数，取值为[0,15]，到达和路由器直接相连的子网跳数为0，取值为16则表示正无穷。后来不仅使用跳数，还增加了队列长度作为链路开销
  • 各个路由器每30s中向相邻节点发送一次路由表信息
  • 超过180s没有接收到相邻节点的路由表信息则认为已经失去和相邻节点的连接

OSPF

  • 使用LS算法和洪泛链路状态信息，周期性广播链路状态ICMP

  • 每一个路由器上都储存了一个含有着整个自治系统网络信息的有向图，其中路由器，主机，子网都是节点，他们之间的关联作为图的边

  • 通过在本地运行LS算法，生成一个以自己为根的最短路径树(SPF Tree)

  • OSPF的优点：
    • 安全：所有OSPF消息都经过身份验证，以防止恶意入侵。
    • 多条相同开销的路径：当存在多条相同开销的路径时，OSPF允许使用多条路径
    • 对单播和多播路由选择综合支持
    • 支持在单个AS中的层次结构：在AS内部可以划分区域，每个区域运行自己的OSPF,然后由一个主区域为其他区域之间流量提供路由选择

5.4 ISP之间的路由选择: BGP

  • 分组跨越多个AS进行路由的时候, 需要一个自治系统间路由选择协议

  • 因特网中所有的AS运行相同的AS间路由选择协议, 称为边界网关协议BGP

  • 在BGP中，分组并不是路由到一个具体的目的地，而是一个CIDR化的前缀，即路由到一个子网或一个子网的集合，所以运行BGP协议的路由器的转发表项格式大致为(前缀，接口)

  • 路由器分为:

    • 网关路由器: 位于AS边缘的路由器, 直接连接到在其他AS中的一台或多台路由器
    • 内部路由器: 仅仅连接在它自己AS内的主机和路由器

  • BGP连接分为:

    • 外部BGP(eBGP)连接: 跨越2个AS的BGP连接
    • 内部BGP(iBGP)连接: 在相同AS中的两台路由器之间的BGP连接

  • 例子见书P258

  • BGP给每个AS提供了如下工具：

    • 通告路由信息：
      • 通过eBGP(external BGP)来确保AS内部某个子网被整个因特网中其他AS所知。
      • 通过iBGP(internal BGP)来确保这个信息在其他AS内部传播到所有BGP路由器上。
    • 确定到目的前缀”最好的”路由：
      • 当BGP通告前缀的时候，前缀中会带有一些BGP属性比如AS-PATH和NEXT-HOP.
        • 当一个前缀通过某个AS时，该AS会在该前缀的AS-PATH上加上自己的AS number. 该属性用来检测和防止环路，当路由器在AS-PATH中看到了自己所在的AS的number,则说明有环路，拒绝该通告。
        • NEXT-HOP是AS-PATH中起始的路由器接口的IP地址。
      • 热土豆路由选择：选择的路由是到 开始该路由的NEXT-HOP路由器的最小开销，即自己AS内部开销最小，而不管其他AS。
      • 路由选择算法:(1)本地偏好优先。(2)最短AS-PATH优先。(3)热土豆选择。(4)BGP标识符选择

IP任播

  • 常用于DNS中，使得每个用户能够从最靠近自己的服务器上获得想要的内容。
  • 比如DNS根IP只有13个，但是每一个IP被分配在不同地方多个DNS根服务器上，通过BGP通告后，这些不同地方会被当作到达同一地址的不同路径，然后在用户申请访问的时候，根据上面说的路由选择算法，选择最靠近自己的服务器。

5.6 ICMP: 因特网控制报文协议

  • 数据承载于IP分组中, 协议类型1, 不可靠
  • 被主机和路由器用来彼此沟通网络层的信息, 传递控制信息和差错信息

ICMP

  • 使用ICMP: Ping
    • 测试目的地可达性
    • 源发送回显请求echo request(ICMP类型8编码0的报文)
    • 远程系统收到ICMP包, 则发送回一个echo reply包给源
    • 从而还可以计算来回的时间和跳数(用TTL)
  • 使用ICMP: Traceroute
    • 得到到达目的地需要的跳数
    • 源主机向目的地主机发送一系列普通的IP数据报, 每个携带一个具有不可达UDP端口号的UDP报文
    • 第一个数据报TTL为1, 第二个为2, 以此类推
    • 第n个数据报到达第n台路由器时, 路由器观察到数据报的TTL正好过期, 丢弃该数据报并发送一个ICMP告警报文给源主机(类型11编码0)
    • 数据报之一会到达目的主机, 因为UDP端口不可达, 目的主机发送一个端口不可达的ICMP报文(类型3编码3). 源主机收到后, 就知道不用再发送另外的探测分组.
  • 使用ICMP: path MTU
    • 决定路径中的最小MTU
    • 发送带有don’t fragment的IP包, 如果超过路径MTU, 则会返回错误信息parameter unintelligible. 减少IP包大小直到不报错.
    • 路径必须固定, 结果方法: 使用源路由

第6章 链路层和局域网

  • 链路层提供的服务

    • 成帧: 把数据报封装成帧
    • 链路接入: 媒体访问控制MAC协议规定了帧在链路上传播的规则
    • 可靠交付
    • 差错检测: f(D)=E, 检测码E放在尾部, f(D’) = E’和收到的E对比
      • 奇偶校验
      • 校验和checksum
      • 循环冗余校验CRC
        • 协定一个$r+1$比特模式, 称为生成多项式G, G最高有效位(最左)是1
        • 选择$r$位附加比特(CRC位, 记为R), 附加在D上, 满足被G整除, 即$D \cdot 2^r \oplus R=nG$
        • $R=\text{remainder}\frac{D\cdot 2^r}{G}$
    • 流量控制
      • 滑动窗口

  • 链路层的主体在网络适配器(也称网络接口卡, 网卡)中实现

6.3 多路访问链路和协议

  • 两种截然不同的链路层信道
    • 点对点通信链路
      • PPP协议
      • HDLC协议
    • 广播链路:
      • 多个发送和接收节点都连接到相同的, 单一的, 共享的广播信道上
      • 多路访问问题: 如何协调多个发送和接收节点对一个共享广播信道的访问
      • 多个节点同时传输帧, 所有节点同时收到多个帧, 则发生碰撞, 也称冲突
      • 多路访问协议
        • 信道划分协议
        • 随机接入协议
        • 轮流协议
  • 对于速率为R bps的广播信道，多路访问协议应该具有以下所希望的特性：
    • 当仅有一个节点发送数据时，该节点具有R bps的吞吐量。
    • 当有M个节点发送数据时，每个节点吞吐量为R/M bps，不要求每个节点总是有R/M bps的瞬时速率，而是在适当的时间间隔内平均速率达到。
    • 协议是分散的，不会因为某主节点故障而使得整个系统崩溃。
    • 协议是简单的，实现昂贵。

6.3.1 信道划分协议

  • 三种: 时分复用,频分复用, 码分复用
  • 时分复用:
    • 将时间划分为时间帧, 每个时间帧划分为N个时隙, 每个时隙分配给N个节点中的一个
    • 优点
      • 避免了碰撞而且公平
      • 每个节点中在属于自己的时隙中可以占用信号全部的带宽。
    • 缺点
      • 在每一个时间帧中，每个节点的传输速率只有R/N bps.
      • 节点必须等待一个轮次才能进行下一次传输
  • 频分复用:
    • 在$R$ bps信道中创立$N$个较小的$R/N$ bps信道
    • 优点
      • 避免了碰撞而且公平。
      • 每个节点可以任意时刻都传输数据。
    • 缺点
      • 每个节点只有R/N的带宽。
  • 码分复用(CDMA): 对每个节点分配一个码片, 码片是正交的(码片相乘为0)
    • 编码信号 = 原信号$\times$码片序列
    • 解码:编码信号和码片序列的内积
    • 码片频率高, 信号频率低
    • 码片中的0用-1代替, 为1, -1编码

6.3.2 随机接入协议

  • 一个传输节点总是以信道的全部速率进行发送
  • 有碰撞时, 涉及碰撞的每个节点反复重发它的帧知道帧无碰撞地通过为止
  • 重发之前会等待随机一个时延
  • 主要种类: ALOHA和CSMA

ALOHA

  • 无线型, 传输时间远大于传播时间
  • 过程:
    • 节点首次获取某一个数据帧后，立即将该帧完整地传输到信道中。
    • 如果收到ACK则成功，反之则以概率p重传，或1-p等待一个帧时间
    • 等待一个帧时间之后, 再次以概率p重传，或1-p再等待一个帧时间. 以此类推
  • 最大效率为$1/(2e)$, 恰好为时隙ALOHA的一半

时隙ALOHA

  • 假设:
    • 所有帧大小相同为$L$
    • 时间被划分成长度为$L/R$(即传输一帧的时间)的时隙
    • 基站发送脉冲, 主机收到脉冲才能发送帧
    • 如果一个时隙中发生碰撞，则所有节点在该时隙结束前能够检测到该碰撞
  • 过程
    • 节点有新帧需要发送，其需要等到下一个时隙开始时才可以发送。
    • 没有碰撞则传输成功，反之该节点以概率p在后面每个时隙开始重传该帧直到传输成功
  • 帧只会完全冲突或者不冲突, 性能提升明显
  • 有效传输速率$1/e=0.37$

载波侦听多路访问(CSMA)

  • 有线型, 传输时间远大于传播时间, 都是理论协议
  • 载波侦听：一个节点在传输前先侦听信道，等待知道检测到一段时间信道空闲，然后开始传输
  • 过程:
    • 发送之前先载波侦听, 如果信道空闲才发送帧
    • 发送后等待ACK, 没等到就重传
  • 帧越长, 传播时间越短, 性能越好
  • 根据信道非空闲时的处理方式分成以下三种
    • 非坚持CSMA
      • 检测到空闲立即传输
      • 信道忙就回去休息(idle), 过一段时间再次检测
      • 休息时间一定是随机的
    • 1坚持CSMA
      • 检测到空闲立即传输
      • 信道忙就一直侦听, 一旦空闲立即发送
      • 如果多个在等, 肯定冲突, 效果不好
    • p坚持CSMA(概率坚持)
      • 空闲时以概率p重传，1-p延后一个时间单位再决定, 忙时一直监听

具有碰撞检测的CSMA: CSMA/CD

  • 以太网的协议, 现在已经无效
  • 碰撞检测: 当一个传输节点在传输时一直侦听此信道, 如果检测到另一个节点正在传输干扰帧, 就停止传输(从而减少了冲突时间)
  • 过程如下
    • 适配器从网络层获得一条数据报, 准备链路层帧, 放入缓存
    • 若侦听到信道空闲: 发送; 若侦听到信道忙, 1坚持, 直到侦听到空闲就发送
    • 发送的同时监听, 如果发现冲突则发送一个高频信号(表示冲突)立即停止; 如果全程无冲突则成功.
    • 侦听到冲突则等待随机时间后回到第二步重试
  • 无ACK(CSMA和ALOHA都有), 但是在CSMA/CD中, 只要全程没冲突即发送成功
  • 最坏要2个传播时间$2\mu$才能检测出来冲突, 因此要发送的最小帧长大于等于$2\mu$ ($\mu$的时间到目的地, 即将到目的地的时候冲突, 冲突再经过$\mu$传到发送方)
  • 重试:
    • 等待时间是$[0, 2^k)$之间的随机整数$\times$ 发送512比特的时间
    • 前10次重试失败后$k$会加1, 第一次重试$k=1$
    • 第11-16次$k=10$不再增加
    • 16次都不成功则放弃

CSMACD

9.6$\mu s$: 硬件重置: 不管

周期之前会等待512比特时间

jam信号: 4-6字节

轮流协议

  • 轮询协议
    • 一个主节点轮询其他节点，告诉其他节点可以传输的帧的最大数量
    • 优点：避免碰撞和随机接入协议里面会出现的空时隙
    • 缺点：1.主节点故障，整个系统崩溃。2.引入了轮询时延
    • 例如蓝牙
  • 令牌传递协议
    • 一个被称为 令牌 的特殊帧在节点间按照固定次序交换
    • 拿到令牌的节点才能发送帧, 没有帧要发送则马上传递
    • 拿到令牌后如果有帧要发送, 则发送最大数目的帧, 然后把令牌给下一个节点
    • 缺点：1.一个节点故障会导致最原始模式的令牌环协议崩溃。 2.令牌环额外的开销和延迟

6.4 交换局域网

6.4.1 链路层寻址和ARP

MAC地址

  • 并不是主机或者路由器具有链路层地址，而是它们的适配器(网络接口)具有链路层地址。因此具有多个网络接口的主机或者路由器具有多个链路层地址。
  • 因为主机和路由器不必明确地将帧寻址到其间的交换机, 所以链路层交换机无链路层地址
  • 链路层地址称为LAN地址，物理地址或MAC地址。
  • MAC地址长度为6字节，所以共有$2^{48}$个可能的MAC地址(常用16进制表示为XX-XX-XX-XX-XX-XX)
  • 适配器的MAC地址一般是固定的
  • 没有个两块适配器具有相同的地址
  • 适配器的MAC地址具有扁平化结构, 且不论适配器到哪里用都不会变化，带有以太网接口的便携机总是具有同样的MAC地址(IP地址不是这样的)
  • 当适配器要向某些目的适配器发送一个帧时
    • 发送适配器将目的适配器的MAC地址插入到链路层帧中，再发送到局域网上。
    • 接收适配器接收到帧后，检查其中MAC地址是否与自己MAC地址相匹配，如果匹配则取出其中数据，向上层传递，如果不是，则丢弃该帧。
  • 广播：发送适配器需要让局域网上所有适配器都接受并处理某帧，则在该帧的目的地址中插入一个特殊的MAC地址(FF-FF-FF-FF-FF-FF)

地址解析协议 ARP

  • ARP协议: IP地址转换为对应的MAC地址

  • 每台主机或路由器在其内存中有一个ARP表.

ARP过程

  • Sender

    • 查找自己的cache, 如果没有就
    • 构建ARP请求, 插入
    • 用MAC帧广播
    • 缓存目的地的对, 以及时间戳

  • Receiver:

    • 查目的地IP, 如果OK

    • 建立ARP应答, 插入

    • 用MAC帧发送sender MAC

    • 缓存发送方的以及时间戳

6.4.2 以太网

以太网帧结构

前同步码 目的地址 源地址 类型 数据 CRC(循环冗余校验码)
8 bytes 6 6 2 46-1500 4
  • 前同步码: 前7字节10101010唤醒接受适配器并同步时钟, 后1字节10101011
  • 目的地址: 目的适配器的MAC地址
  • 源地址: 传输该帧到局域网上的适配器的MAC地址
  • 类型字段: 允许以太网复用多种网络层协议, 例如可以使用除了IP以外的其他网络层协议
  • 数据字段承载IP数据报，以太网最长传输单元(MTU)为1500字节，超过之后得分片
  • CRC: 循环冗余校验

以太网技术

  • 以太网技术向网络层提供无连接服务，也就是源适配器要发送数据报时需要先将IP数据报封装在以太网帧中然后发到局域网上，而非像TCP协议那样三次握手建立连接。
  • 以太网技术向网络层提供不可靠服务，当适配器收到一个以太网帧后执行CRC检验，检验通过不会发送ACK帧，检验不通过也不会发送否定帧，而是直接丢弃该帧

  • IEEE 802.3是一个定义了有线以太网物理层和链路层的媒体访问控制(MAC)的标准

  • 以太网有很多标准, 缩写为10base5, 10base2,10baseT, 10baseFX等.

    • 由IEEE 802.3 CSMA/CD(Ethernet)工作组标准化
    • 其中缩写的第一部分表示该标准的速率:10, 100, 1000, 10G(单位为Mbps)
    • “BASE”指基带以太网, 表示该物理媒体仅承载以太网流量
    • 最后一部分表示物理媒体本身, 以太网是链路层也是物理层的规范. 例如’T’表示双绞铜线.

6.4.3 网桥/switch/二层交换机(同一个意思)(重要)

  • 主要作用: 互连局域网的网段, 网桥互联的必须是同类型的局域网

  • 不修改帧的内容(路由器会修改)

  • 有交换功能(基于MAC地址, 以主机为单位)(==必考路由器和网桥的区别==)
    • MAC地址看不出网段, 而IP地址看得出
    • 网桥是以主机为单位, 路由是以网段为单位
    • 网桥不涉及封装解封, 路由器涉及
  • 存储转发(store and forward)不涉及协议转换
  • 对于子网中的主机和路由器是透明的(不被知道)

  • 自学习的, 即插即用(plug-and-play)

  • 隧道模式:

    • 完整的帧, 加头和尾传播, 接收去掉头尾, 得到完整的帧

  • 交换:

    • 选择最短路—支撑树算法

支撑树算法

  • 网桥自动生成交换表, 自动更新
  • 主要分为:
    • 帧转发
    • 地址学习
    • 环路识别
1. 帧转发
  • 交换表结构: <目的MAC地址, 转发端口号, 时间戳>
  • 对于一个到达端口X的帧:
    • 搜索转发表, 看有没有这个MAC地址
      • 如果没找到MAC地址, 在所有端口(除X)都转发
      • 如果有MAC地址, 检查端口号
        • 若端口是X, 直接丢掉
        • 若端口是Y(非X), 如果Y是可以转发状态就转发
          (forwarding状态可收可发, blocking状态只能发)
2. 地址学习

  • 转发表是自学习的

  • 帧X到达端口后:

    • 如果没有这个MAC源地址, 则补上
    • 如果有MAC源地址, 则检查端口号
      • 如果端口是X则更新时间戳
      • 如果端口是Y(非X), 则端口更新为X且更新时间戳
    • 每个表项有计时器, 时间到则删除表项(即一个表项如果一段时间没有对应的帧到来则删除)

  • 交换机和路由器的比较

    • 路由器是使用网络层地址转发分组的存储转发分组交换机
    • 交换机也是一个存储转发分组交换机,但它和路由器是根本不同的, 因为它用MAC地址转发分组。
    • 交换机是第二层的分组交换机, 而路由器是第三层的分组交换机,
    • 交换机是即插即用的,具有相对高的分组过滤和转发速率

第7章 无线网络和移动网络

7.3 WiFi: 802.11无线LAN

  • 频段: 2.4GHz, 5GHz
  • 媒体访问协议: CSMA/CA

7.3.1 802.11体系结构

  • 基本构建模块: 基本服务集 BSS, 包含一个或多个无线站点和一个称为接入点(AP)的中央基站

    • 控制模块/基站/无线hub/接入点都是同一个东西
    • 用户模块: 无线网卡
  • 每个802.11无线站点都有一个6字节的MAC地址, 存在该站适配器(网卡)中
  • 每个接入点(AP)的无线接口也有一个MAC地址
  • 配置AP的无线LAN称为基础设施无线LAN
  • 每个接入点有一个服务集标识符SSID
  • ESS: 多个BSS通过分布式系统(DS)互联, DS为交换机, 有线网或者无线网
  • WiFi丛林: 任意一个物理位置, 在这里无线站点可以从2个或者多个AP中收到很强的信号
  • 关联:
    • 进入WiFi丛林时, 主机需要加入其中一个子网并与其中一个AP相关联, 即在这一无线站点在自身和该AP之间创建一个虚拟线路.
    • 仅有关联的AP才向你的无线站点发送数据帧, 你的无线站点也仅仅通过该关联AP向因特网发送数据帧
  • 被动扫描：
    • 每个AP每个一定时间在自身所在信道中发送一个信标帧(含AP的SSID(服务集标识)和MAC地址)。
    • 设备扫描所有信道获取信标帧，选择一个AP发送关联请求帧
    • AP向设备发送关联响应帧.
  • 主动扫描：
    • 设备发送广播探测帧。
    • AP发送探测响应。
    • 设备选择AP发送关联请求帧。
    • AP向设备发送关联响应帧。

7.3.2 802.11 MAC协议

  • 802.11无线网无法使用碰撞检测
  • 有链路层确认ACK, 因为无线LAN中节点发送帧有可能不能无损到达目的站点
  • IFS帧间间隔(实现了优先级)

  • 过程:

    • 如果最初监听到信道空闲, 它将在一个 分布式帧间间隔DIFS后发送该帧

    • 否则该站点选取一个随机返回值, 并且在侦听信道空闲时递减该值. 侦听到信道忙时不变

    • 计数值为0时, 该站点发送整个数据帧并等待确认
    • 收到确认则知道帧已经正确接收. 如果想要再发送一个帧, 从第二步开始.
    • 如果没有收到确认, 发送站点重新进入第二步中的回退阶段, 并从更大的范围中选取随机值

  • 倒计时(backoff)时即使监听到信道空闲也抑制传输的原因: 尽量避免碰撞.

  • IEEE 802.11 Medium Access Control Logic

  • 3个级别的IFS:

    • SIFS: 短IFS—高优先级
    • PIFS: AP使用, 用于抢占信道，AP发送信息的优先级高于一般节点
    • DIFS

处理隐藏终端: RTS和CTS(4帧交换)

  • 问题描述: A节点可以和B节点相互传输，B可以和C相互传输，但A不能直接和C相互传输，那么可能A,C同时向B发送帧, 因为AC之间互相听不到对方的传输而导致冲突
  • 解决方法: 使用RTS(请求发送控制帧)和CTS(允许发送控制帧)
  • 发送方要发数据帧时:
    • (延迟DIFS后)先向AP发一个RTS帧, 指示传输数据和确认帧的总时间
    • AP收到RTS帧后, (延迟SIFS后)广播一个CTS帧作为回应, 目的为
      • 给发送方发送许可
      • 指示其他站点在预约期内不要发送
    • 发送方收到RTS(延迟SIFS)后发送data帧
    • 目的地收到data(延迟SIFS)后发送ACK

CSMACA传输过程

补充: 拥塞和Qos

拥塞原因

  • 大量分组在网络上传输，数量超出路由器的处理能力。

拥塞代价

  • 造成丢包，时延；重传使得浪费之前发送的资源。

拥塞控制方法

  • 抑制分组(choke packet): 产生拥塞的路由器通过特定协议(如ICMP)向源端系统发送抑制分组来抑制源端系统的分组发送。

  • 反向施压(Backpressure): 当传播时间大于传输时间时，choke packet往往没有作用，则通过产生拥塞路由器向前面一个路由器反向施压抑制前面路由器的发送，这样传递下去，最终影响到源端系统。

  • 标志位(Warning bit): 通过在分组上设置一个标志位来告诉端系统可能发生拥塞。

    • 前向标记(FECN): 发生拥塞相同的方向
    • 后向标记(BECN): 发生拥塞相反的方向

  • 拥塞窗口：使用在端系统上(如TCP)

  • 早期随机丢弃(RED): 作用在路由器上，该方式设置一个下限Lmin，一个上限Lmax。

    • 当队列的长度小于小于下限时，保证不会丢掉分组
    • 当队列的长度介于上下限之间时，对于每一个接收到的分组，路由器以概率 p丢弃
    • 当队列长度完全大于上限时，丢弃接收到的分组。

  • 流量整形（Traffic shaping): 在建立连接之后，端系统和路由器之间协商流量整形的方式。

    • 约定数据速率(CIR): RED方式。
    • 漏桶(令牌桶):漏桶由一个能够容纳$b$个令牌的桶组成。令牌加进该桶的过程如下:
      • 可能潜在地加入桶中的新令牌总是以每秒$r$个令牌的速率产生
      • 当产生一个令牌时,如果桶填充得少于 个令牌,新产生的令牌加入该桶中;否则忽略该新产生的令牌,令牌桶保持具有$b$个令牌的满状态。
    • 漏桶规则:
      • 在一个分组向网络传输之前,必须首先从令牌桶中去除一个令牌
      • 如果令牌桶是空的,分组必须等待一个令牌
    • 效果:
      • 平均速率: $r+b/t$, 令牌产生速率$r$用于限制分组能够进入网络的长期平均速率
      • 突发长度: $b$
      • 峰值速率:在已有的一个漏桶后, 串联一个高度为1的桶,其速率为$r’$可限制峰值速率。

Qos的两种服务

ISA(Integrated Services Architecture)

  • 由于太复杂，现在还没用。

DS(Differentiated Services)差异化服务

  • 使用IPv4和IPv6里面的服务类型和流量类型来区分不同的分组的重要性。