计算机网络期末复习
on Courses
计算机期末复习总结
主体来自于Maxwell：https://maxwell-lyu.github.io/，在其基础上简单修改
- List
- 计网复习
- 具体构成描述
- 服务描述
- 什么是协议
- 接入网
- 物理媒体
- 分组交换
- 电路交换
- 网络的网络
- 时延概述
- 排队时延和丢包
- 端到端时延
- 吞吐量
- 分层的协议结构
- 封装
- 无连接的多路复用与多路分解
- 面向连接的多路复用与多路分解
- 报文段结构
- UDP检验和
- TCP连接
- TCP报文段结构
- 往返时间的估计与超时
- 可靠数据传输
- 流量控制
- TCP连接管理
- 公平性
- 网络辅助拥塞控制
- 输入端口处理和基于目的地转发
- 交换
- 输出端口处理
- 何处出现排队
- 分组调度
- IPv4数据报格式
- IPv4数据报分片
- IPv4编址
- 网络地址转换NAT
- IPv6
- 链路状态路由选择算法
- 距离向量路由选择算法
- 开放最短路优先OSPF
- BGP的作用
- 通告BGP路由信息
- 确定最好的路由
- IP任播
- 路由选择策略
- 拼装在一起: 在因特网中呈现
- 信道划分协议
- 随机接入协议
- 轮流协议
- 链路层寻址和ARP
- 以太网
- 链路层交换机
- 网桥
- 虚拟局域网
- 流式存储视频
List
计网复习
[重点] 1.x
[概念] 3.2 3.3
[重点] 3.5 3.6 3.7
[重点] 4.2 4.3
[重点] 5.2 5.3
[概念]
[重点] CSMA/CD
[概念]
[概念] 9.x QoS相关内容
距离向量算法，可能出现的问题
LS算法
TCP reno协议 三次握手，四次挥手
默写ALOHA
流媒体
CSMA/CA CSMA/CD
了解：SDN，ICMP，网桥
第一章
=================
什么是因特网
具体构成描述
主机 / 端系统: 与因特网相连的设备
通信链路: 同轴电缆, 铜缆, 光纤, 无线电频谱
分组交换机
路由器: 通常在网络核心
链路层交换机: 通常在接入网
传输速率: 比特/秒 bps
分组: 数据分段并加上首部字节(发送系统)
路径: 分组经历的通信链路和分组交换机
因特网服务提供商(ISP): 因特网接入服务
协议: 控制因特网中信息的接收和发送
TCP: 传输控制协议
IP: 网际协议
因特网标准: 由IETF研发
RFC: 请求评论, 因特网标准文档
服务描述
分布式应用程序: 涉及到多个相互交换数据的端系统
套接字接口: 规定了端系统上的程序, 请求因特网基础设施, 向另一个端系统上程序, 交付数据的方式
什么是协议
协议定义了:
在两个或多个通信实体之间, 交换报文的格式和顺序
报文发送和/或接收报文, 或其他事件, 所采取的动作
网络边缘
端系统: 运行应用程序
P2S模型
客户端: 发送请求, 接受服务
服务器: 响应请求, 提供服务, 始终在线, 性能更强
P2P模型
无专用服务器, 每设备既是客户端也是服务器
接入网
接入网: 端系统物理连接到边缘路由器的网络
边缘路由器: 端系统接入到远程端系统的第一台路由器
接入链路与接入环境
家庭接入
拨号
介质: 电话线, 有调制解调器, 执行的操作相当于给接入号(服务台)打个电话, 独占一个线路
速率: 56kbps
卫星: 1Mbps
DSL: 数字用户线
介质: 电话线
拓扑
DSLAM: 数字用户线接入复用器, 位于中心局, 许多端系统共享
频段分布
* 高速下行: 50kHz - 1MHz 12Mbps 55Mbps
* 中速上行: 4kHz - 50kHz 1.8Mbps 15Mbps
* 双向话音: 0 - 4kHz
HFC: 混合光纤同轴/电缆因特网接入
介质: 同轴电缆 + 光纤
拓扑
CMTS: 电缆调制解调器端接系统, 位于电缆头端
速率: 42.8Mbps下行, 30.7Mbps上行
有碰撞
FTTH: 光纤到户(PON: 被动光纤网络)
介质: 光纤
拓扑
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, 可以来自不同级
分组交换网中的时延丢包和吞吐量
时延概述
处理时延: 节点检查首部, 决定转发, 进行校验的时间, 微秒-$d_{proc}$
排队时延: 在链路前的队列等待传输, 微秒~毫秒,$d_{queue}$
传输时延: $L/R$, 将所有比特推向链路的时间, 微秒~毫秒，$d_{tran}$.
传播时延: $d/s$, 速度s略小于光速, 毫秒,$d_{prop}$.
排队时延和丢包
排队时延对不同的分组不相通, 以统计量衡量
流量强度: $La/R$, $a$为分组到达的速率, 流量强度不能大于1。($a$是分组到达的速率，$L$是分组的长度,比特到达队列的平均速率是$La$ $bps$)
流量强度增加, 平均排队时延迅速增加($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
仅提供复用分解, 差错检测
无连接: 发送报文段之前, 没有握手
优点: 首部短, 时间灵活, 无连接建立, 无连接状态
无拥塞控制, 可以由应用层构建可靠传输
报文段结构
| 源端口号 | 目的端口号 | 长度（首部+数据） | 检验和 | 应用数据（报文） |
| ——– | ———- | —————– | —— | —————- |
| 16 bit | 16 bit | 16 bit | 16 bit | - |
UDP变长数据段
检验和计算: UDP报文段 + IP首部的部分字段()
UDP检验和
计算方法
报文段分为16bit字, 相加求和
最高位进位回卷, 加到最低位
取反码
检验方法: 接收方做前两步, 得到全1, 则没问题
能检测, 不能纠错, 端到端差错控制
面向连接的运输TCP
提供差错检测, 重传, 累积确认, 定时器, 序号和确认号的首部字段
全双工
TCP连接
三次握手
客户发送
服务端发送
客户发送
MSS最大报文段长度(其实是应用层数据的最大长度): 根据 MTU(链路层)最大传输单元确定, 典型值1460字节（1500-40TCP/IP首部）
TCP报文段结构
| 源端口号 | 目的端口号 | 序号 | 确认号 | （第一堆） | 接收窗口 | 因特网校验和 -紧急数据指针 | 选项 | 数据 |
| ——– | ———- | —– | —— | ———- | ——– | ————————– | —– | —- |
| 16bit | 16bit | 32bit | 16bit | 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, 之后根据下式更新
指数移动加权平均
- DevRTT: RTT的偏差, 是Sample和Estimated的差的绝对值, 也用指数移动加权平均
设置和管理重传超时间隔
重传间隔
默认初始值为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
收到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洪泛攻击
第二步的server_isn使用散列函数, 用源地址, 目的地址和端口号, 和一个只有服务器知道的散列函数
第二步不分配资源
第三步根据ACK里面的seq, 可以验证这个ACK是由先前的某个SYN生成的, 于是分配资源建立连接
拒绝通信
发送RST(RST标志位1)
拥塞控制原理
- 一堆废话, 我只关心TCP
TCP拥塞控制
拥塞窗口cwnd
对发送进行限制: 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（当对丢失报文段的一个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数据报格式
- 数据报格式
| 版本 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
- 数据报格式
| 版本 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次发送
- 效率: 近似为
- 最小帧长: 检测冲突的时长不超过端到端传播时延的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与站点的点对点
第八章 网络安全
=================
安全通信要求
机密性：加密报文
报文完整性：不会被篡改，或识别出篡改
端点鉴别：确认两方身份
运行安全性
密钥
对称密钥
攻击方式
唯密文攻击：入侵者只能截获密文
已知明文攻击：入侵者知道明文和密文的匹配
选择明文攻击：能够选择某一明文报文并得到改明文报文对应的密文形式
单码代替密码：凯撒密码
多码代替密码：不同位置出现的相同字母可能以不同的方式加密
块密码
要加密的报文被处理为k比特的块，kbit块明文被映射为k比特块的密文
如：DES，3DES，AES
流密码
公开密钥加密
RSA
$n=pq,z=\phi(n)=(p-1)(q-1)$
选择$e<n,gcd(e,z)=1$,$ed\mod{z}=1$
公钥$K_B^+(n,e)$，私钥$K_B^-(n,d)$
$K_B^+(m)=m^e\mod{n},K_B^-(m)=m^d\mod{n}$.
会话密钥
用RSA传输用于加密大量传输信息的密钥
报文完整性和数字签名
密码散列函数：MD5、SHA-1等
报文鉴别码：报文附加H(m+s),s仅二者已知
数字签名：私钥签名
公钥认证：CA
端点鉴别
ap4.0：
A->B: “我是A”
B->A: 选一个不重数R，给A
A->B: $K_{A-B}(R)$.
B验证
TCP：SSL
握手
客户发送它支持的密码算法的列表，连同一个客户的不重数
从该列表中，服务器选择一种对称算法（例如AES）、一种公钥算法（例如具有 特定密钥长度的RSA）和一种MAC算法。它把它的选择以及证书和一个服务器不重数返 回给客户
客户验证该证书，提取服务器的公钥，生成一个前主密钥（Pe Master Secret, PMS）,用服务器的公钥加密该PMS,并将加密的PMS发送给服务器。
使用相同的密钥导岀函数（就像SSL标准定义的那样），客户和服务器独立地从 PMS和不重数中计算出主密钥（Master Secret, MS）O然后该MS被切片以生成两个密码和 两个MAC密钥。此外，当选择的对称密码应用于CBC （例如3DES或AES）,则两个初始 化向量（Initialization Vector, IV）也从该MS获得，这两个IV分别用于该连接的两端。自 此以后，客户和服务器之间发送的所有报文均被加密和鉴别（使用MAC）
客户发送所有握手报文的一个MAC
服务器发送所有握手报文的一个MAC
第九章
=================
流式存储视频
UDP流、HTTP流、适应性HTTP流
与客户缓存有关
提供多种类型的服务
监管: 漏桶
监管准则
* 平均速率: 长时间速率存在最大值 - 漏桶的令牌产生速率
* 峰值速率: 短时间速率存在最大值 - (将桶容量定为1, 此时能够限制峰值速率)
* 突发长度: 极短时间(趋近0)发送的分组数量存在最大值 - 漏桶的高度
- 漏桶描述
* 分组首先进入令牌等待队列
* 在漏桶处取得令牌的分组将被发送
* 桶高度不超过b
* 每秒生成r个令牌加入桶
- 效果
* 平均速率: r + b/t, 时间足够长, 该值为r
* 突发长度: b
* 峰值速率: 在已有的一个漏桶后, 串联一个高度为1的桶, 其速率r’可限制峰值速率