导图社区 计算机网络与通讯
- 53
- 2
- 2
- 举报
计算机网络与通讯
这是一篇关于计算机网络与通讯的思维导图,计算机网络与通讯是密切相关的领域，它们相互促进、相互发展。
编辑于2023-12-26 23:38:34- 网络与通讯
- 相似推荐
- 大纲
计算机网络与通讯
chap 01 绪论
计算机网络？
计算机网络是通信技术与计算机技术紧密结合的产物
定义：计算机网络就是互连的、自治的计算机集合。
互联指的是相互连接
自治指的是无主从关系
通过交换网络互连主机
构成
主机设备
通信链路
交换设备
通信基础设施
编程API
网络协议？
协议：计算机网络中的数据交换必须遵守事 先约定好的规则
计算机网络的所有通信过程都 必须遵守某种/些规则—协议
网络协议(network protocol)，简称为协议，是为进行网络中的数据 交换而建立的规则、标准或约定 协议规定了通信实体之间所交换的消息的格式、意义、顺序以及针 对收到信息或发生的事件所采取的“动作”（actions）
三要素
语法
数据与控制信息的结构或格式
信号电平
语义
需要发出何种控制信息
完成何种动作以及做出何种响应
差错控制
时序
事件顺序
速度匹配
协议是计算机网络的重要内容
计算机网络的结构
边缘网络
接入网络
核心网路
Internet结构
网络之网络（许多网络组成的网络）
端系统通过接入ISP（access ISPs ）连接到Internet，接入ISP必须进一步互连，构成复杂的相互连接的网络
网络核心-数据交换
如何实现数据通过网络核 心从源主机到达目的主机？数据交换
类型
电路交换
电路交换网络如何共享中继线？ —多路复用（Multiplexing）
多路复用(multiplexing)，简称复用，是通信技术中的基本概念
典型方法
频分多路复用( frequency division multiplexing-FDM )
将信道频段进行划分，给不同用户
时分多路复用( time division multiplexing-TDM )
将传输过程划分为不同时隙
波分多路复用(Wavelength division multiplexing-WDM)
本质上还是频分复用，需要调制
码分多路复用( Code division multiplexing-CDM )
每个用户有唯一的码片序列，且各个用户码片序列彼此正交
“0”用“-1”表示、 “1”用“+1”表示
编码信号 = (原始数据) × (码片序列)
如发送比特 1（+1），则发送自己的 m bit 码片序列
如发送比特 0（-1），则发送该码片序列的m bit 码片序列的反码
传输时将各个用户编码后的码片序列求和
解码时将对应的用户码片与序列和作点乘即可解出对应用户位
报文交换
报文：源（应用）发送信息整体
分组交换
分组：报文分拆出来的一系列相对较小的数据包
分组交换需要报文的拆分与重组
产生额外开销,但是提高效率
报文交换与分组交换均采用存储-转发交换方式
区别
报文交换以完整报文进行“存储-转发”
分组交换以较小的分组进行“存储-转发”
效率比较：传输延迟建模
报文长度为M bits 链路带宽为R bps 每次传输报文需要M/R秒 且路由器至少需要M bits缓存
如果有n个路由器则
分组的话，假设分组大小为L，经过n个路由器
注意：跳步数h和路由器数量n的关系是：n+1=h
计算机网络性能
速率即数据率(data rate)或称数据传输速率或比特率(bit rate)
“带宽”(bandwidth)原本指信号具有的频带宽度，即最高频率与最 低频率之差，单位是赫兹（Hz）
网络的“带宽”通常是数字信道所能传送的“最高数据率”，单位 ：b/s (bps)
其实和速率是一个意思
延迟/时延(delay或latency)
处理时延dproc
排队时延dqueue
堵塞
传输时延dtrans
传播时延dprop
时延带宽积
时延带宽积 = 传播时延×带宽
链路的时延带宽积又称为以比特为单位的链路长度
丢包
队列缓存容量有限
分组到达已满队列将被丢弃 (即丢包)
丢弃分组可能由前序结点或源重发（也可能不重发）
吞吐量
吞吐量:表示在发送端与接收端之间传送数据速率 (b/s)
一般来说是链路上带宽最小的一部分
吞吐量=min(Rs,Rc,R/10)(10个链接共享R)
计算机网络体系结构
是否存在一种系统结构有效 描述网络？
分层结构
计算机网络体系结构简称网络体系结构(network architecture) 是分层结构，每层遵循某个/些网络协议完成本层功能
计算机网络体系结构是计算机网络的各层及其协议的集合
为什么分层
结构清晰，有利于识别复杂系统的部件及其关系
模块化的分层易于系统更新、维护
有利于标准化
分层网络体系结构基本概念
实体(entity) 表示任何可发送或接收信息的硬件或软件进程。
协议是控制两个对等实体进行通信的规则的集合，协议是“水平的”
任一层实体需要使用下层服务，遵循本层协议，实现本层功能，向上层提供服务， 服务是“垂直的”。
下层协议的实现对上层的服务用户是透明的。
同系统的相邻层实体间通过接口进行交互，通过服务访问点 SAP (Service Access Point)，交换原语，指定请求的特定服务。
发送时下层需要对上层数据进行封装，接收后进行解封
增加控制信息
OSI参考模型
应用层
支持网络应用
表示层
数据格式转化
会话层
会话控制
传输层
负责源-目的（端-端） （进程间） 完整报文传输
网络层
负责源主机到目的主机数据分组（packet）传输
可跨越多个网络
逻辑寻址（Logical addressing）
链路层
负责结点-结点（node-to-node）数据传输
组帧（Framing）
物理寻址
物理层
通过物理介质进行比特传输
五层参考模型
综合 OSI 和 TCP/IP 的优点，便于学习与实现
应用层: 支持各种网络应用
▪ FTP, SMTP, HTTP
传输层: 进程-进程的数据传输
▪ TCP, UDP
网络层: 源主机到目的主机的数据分组路由与转发
▪ IP协议、路由协议等
链路层: 相邻网络元素（主机、交换机、路由器等）数据传输
▪ 以太网（Ethernet）、802.11 (WiFi)、PPP
物理层:比特传输
计算机网络发展历史
chap 02应用层
网络应用体系结构
客户机/服务器结构(Client-Server, C/S)
服务器
7*24小时提供服务
永久性访问地址/域名（ip地址可能不是一个，但域名通常是一个）
利用大量服务器实现可扩展性
客户机
与服务器通信，使用服务器提供的服务
间歇性接入网络
可能使用动态IP地址
不会与其他客户机直接通信
例子：Web
纯P2P结构
没有永远在线的服务器
任意端系统/节点之间可以直接通讯
节点间歇性接入网络
节点可能改变IP地址
有高度可伸缩性，但是难于管理
混合结构
例子：Napster
文件的传输使用P2P结构
文件的搜索使用C/S结构
每个节点向中央服务器登记自己的内容
每个节点向中央服务器提交查询请求
网络应用的基础：进程间通信（由传输层负责）
进程是主机上运行的程序
同一主机上的进程间通信由操作系统提供
不同主机上进程之间的通信通过消息交换
进程间通信利用socket发送/接收消息
每个进程之间有标识符：IP地址（主机）+端口号（进程）为网络上进程的标识符
网络应用需要遵循应用层协议
HTTP，SMPT等
应用层协议的内容
消息的类型：请求/响应
消息的语法格式：字段/描述
字段的语义
规则：如何/何时发送请求/响应消息
网络应用的服务需求
可靠性/数据丢失
某些应用可以容忍一定的数据丢失，如视频、直播等；而有些应用不允许数据传输错误，如邮箱等
时延
有些应用只有在延迟足够低时才有效：实时应用，如直播，网络电话
带宽
某些应用只有在带宽达到最低要求时才有效：网络视频；而有些应用是弹性的：邮箱
Internet传输层服务模型
TCP
面向连接
可靠的传输
流量控制
拥塞控制
不提供时延保证
不提供带宽保证
UDP
无连接
不可靠的传输
不提供
可靠性保障
流量控制
拥塞控制
延迟保障
带宽保障
二者相比较，UDP无限制，不可靠但是性能较强，一般适用于直播或流媒体；TCP提供可靠的数据传输，一般适用于文件传输
特定网络应用及协议
HTTP
超文本传输协议，用于传输网页（包含html，css，js等多个对象）
对象的寻址使用url：统一资源定位符
格式为：scheme://host/path
HTTP使用TCP作为传输层的服务
服务器在80端口等待客户的请求
浏览器发起到服务器的TCP连接(创建套接字Socket)
服务器接受来自浏览器的TCP连接
浏览器(HTTP客户端)与Web服务器(HTTP服务器)交换HTTP消息
关闭TCP连接
HTTP是无状态的，服务器不维护任何有关客户端过去所发请求的信息
使用Cookie技术来获取客户端信息
HTTP连接的两种类型
非持久性连接
每次TCP连接只允许发送一个对象
Connection为close
持久性连接
每次TCP连接允许发送多个对象
Connection为keep-alive
响应时间分析建模
RTT：从客户端发送一个很小的数据包到服务器并返回响应的时间
网络时延包括处理时延、排队时延、传输时延和传播时延，而RTT由于数据包较小，可以不忽略传输时延，在网络较好的条件下也可以忽略排队时延，所以RTT近似于两倍的传播时延加上处理时延
响应时间：
发起、建立TCP连接所需1个RTT
发送HTTP请求消息到HTTP响应消息的前几个字节到达所需1个RTT
相应消息所含文件/对象的传输时间
Total per tcp=2*RTT+传输时间（dtrans）
持久性与非持久性的时间建模
非持久性的问题
每个对象都需要两个RTT
操作系统需要为TCP的建立开销资源（每个对象一个TCP）
浏览器会打开多个并行的TCP，增加服务器负担
持久性连接
发送响应后服务器持久保持TCP的连接
后续的HTTP消息可以通过这个TCP来进行传输
无流水的持久连接
客户端只有在收到前一个请求的响应才会发送新的请求
每个被引用的对象消耗一个RTT
流水机制的持久连接
客户端一次性发送多个对象的请求
理想情况下，所有引用对象只耗费一个RTT
HTTP消息类型
request请求
请求消息是由ASCII码组成，人可以直接读出信息
HTTP请求消息的通用格式
请求方式：POST方法：在请求的消息体中传入参数；GEt方法，通过request的url字段传入
response响应
响应消息同样使用ASCII码
第一行为响应状态码
200 OK
301 Moved Permanently
400 Bad Request
404 Not Found
505 HTTP Version Not Supported
cookie技术
HTTP无状态，需要使用cookie技术来获取客户端状态
cookie是存储在客户端本地的一组加密文件
cookie的组件
HTTP响应消息的cookie头部行
HTTP请求消息的cookie头部行
保存在客户端主机上的cookie文件，由浏览器管理
Web服务器端的后台数据库
request携带设置cookie的头部行发往服务器
服务器数据库设置cookie，并将响应数据返回；本地端cookie也会更新
在后续请求中request直接携带相应cookie字段，发往服务器数据库查询
web缓存
在不访问服务器的情况下满足客户端的HTTP请求
Web缓存/代理服务器
用户设置通过缓存进行访问
当缓存中有所需数据时直接返回；否则缓存服务器向原始服务器发送请求，将获取到的对象返回
缓存既充当客户端又充当服务器
性能分析
示例：假定对象的平均大小100000bit，每秒15个请求到服务器，RTT=2s，对于接入链路的利用率为100%（拥塞）
此时总延迟为：RTT+传输时延+排队时延+处理时延=2s+some minutes+some ms
解决方案1：将接入链路的带宽上调
此时总延迟：2s+some ms+some ms
虽然减少延迟，但是降低了接入链路的利用率，而且成本也太高
解决方案2：使用缓存服务器
假设缓存命中率为0.4
此时仅有60%的请求访问原始服务器，对于接入链路的利用率变为60%，拥塞得到解决
现在的总延迟：0.6*2.01s+0.4*some ms<1.4s
使用条件性get方法获取Web对象：如果缓存中有最新的版本则不需要向原始服务器发送请求
SMTP， POP，IMAP
这些协议是用来构建Email应用的
HTTP其实也可以用作收发邮件（客户端与服务器之间），SMTP只能发邮件，POP只能收邮件
Email应用的组成部分
邮件客户端，或者称为agent
邮件服务器
SMTP
是邮件服务器之间传递消息所使用的协议
也可以用作邮件客户端向邮件服务器发送消息
SMTP的客户端相当于发送消息的邮件服务器，服务器相当于接收消息的邮件服务器
使用的传输层协议为TCP，端口号为25
传输过程为
握手
消息传输
关闭连接
命令/响应交互模式
命令为ASCII码语句
响应为状态代码和语句
使用持久性连接，消息必须由7位ASCII构成（纯文本），使用CRLF.CRLF确定消息的结束
SMTP消息格式
分为头部行与消息体
From To Subject
body以ASCII码的形式传达消息本身
SMTP与HTTP的比较
SMTP是推式的，而HTTP为拉式的
HTTP每个对象封装在独立的响应消息中，SMTP多个对象在由多个部分构成的消息体重发送
MINE多媒体扩展
原始的SMTP仅支持纯文本，为了扩展其性能加入MINE
通过在头部添加额外的MINE行以声明MINE的类型
示例
从服务器获取邮件可以使用POP协议/HTTP
POP3
一些邮件访问协议：POP3、IMAP、HTTP
两种模式
下载并删除模式
文件被下载到客户端并且删除在服务器的备份，如果删除客户端则无法再次查看
下载并保持模式
文件被下载到客户端并在服务器中留有备份，不同客户端可以同步消息
POP3是无状态的
IMAP
所有消息统一保存在一个地方：服务器
允许用户利用文件夹组织消息
IMAP支持跨会话(Session)的用户状态:
▪ 文件夹的名字
▪ 文件夹与消息ID之间的映射等
DNS
Internet上主机/路由器的识别问题
IP地址与域名之间的映射
使用域名解析系统DNS来解决
多层服务器构成的分布式数据库
是一个应用层协议，完成域名解析
DNS服务
域名向IP地址的翻译
主机别名
邮件服务器别名
负载均衡：Web服务器
是分布式的数据库
为什么不使用集中式的服务器
单点失败
流量问题
距离问题
维护性问题
层次数据库
结构
从上到下依次为：根域名服务器、顶级域名服务器、权威域名服务器
本地域名解析服务器无法解析域名时，访问根域名服务器
根域名服务器
如果不知道映射，访问权威域名服务器
获得映射
向本地域名服务器返回映射
TLD和权威域名解析服务器
顶级域名服务器(TLD, top-level domain): 负责com, org, net,edu等 顶级域名和国家顶级域名，例如cn, uk, fr等
权威(Authoritative)域名服务器：组织的域名解析服务器，提供组 织内部服务器的解析服务
本地域名解析服务器
不严格属于层级体系
每个ISP有一个本地域名服务器，为默认域名解析服务器
当主机进行DNS查询时，查询被发送到本地 域名服务器
作为代理(proxy)，将查询转发给（层级式）域 名解析服务器系统
逐级查询
迭代查询
被查询服务器返回域名解析服务器的名字
递归查询
将域名解析的任务交给所联系的服务器
二者之间的区别
对于迭代查询：本地域名服务器需要进行多次查询
对于递归查询：本地域名服务器只需要进行一次查询
DNS记录缓存和更新
只要域名解析服务器获得域名—IP映射，即缓存这一映射
一段时间后失效
本地域名服务器一般会缓存顶级域名服务器的映射，因此根域名服务器一般不经常被访问
如何注册域名
向域名管理机构提供你的权威域名解析服务器的名字和IP地址
域名管理机构向com顶级域名解析服务器中插入两条记录： (networkutopia.com, dns1.networkutopia.com, NS) (dns1.networkutopia.com, 212.212.212.1, A)
在权威域名解析服务器中为www.networkuptopia.com加入Type A记录 ，为networkutopia.com加入Type MX记录
P2P应用
纯P2P架构
特点
没有服务器
任意端之间直接通信
节点阶段性接入Internet
节点IP地址可能改变
文件分发的速度
示例：假设服务器上传带宽为us、节点i的上传带宽为ui、节点i的下载带宽为di
对于CS架构来说的理论最短下载时间
因为服务器要并行地上传N个文件，所有客户端下载的最小时间为最慢的那个客户端下载完的时间
对于P2P架构的理论最短下载时间
最少上传一个文件，客户端最慢下载时间，还有总的需要下载的数量除以可能最大的速度
可以看出；当客户端越多时，P2P的速度优势越明显
文件分发：BitTorrent
torrent: 交换同一个文件的文件块的节点组
tracker：跟踪参与torrent的节点
chunk：交换文件块
流程
文件划分为256KB的chunk
节点加入torrent
没有chunk，但是会逐渐积累
向tracker注册，与邻居节点建立连接
下载的同时，需要向其他节点上传chunk
节点可能加入或离开
一旦节点获得完整的文件，它可能（自私 地）离开或（无私地）留下
获取与发送chunk
获取chunk
给定任一时刻，不同的节点持有文件的不同chunk集合
节点(Alice)定期查询每个邻居所持有的chunk列表
节点发送请求，请求获取缺失的chunk
发送chunk
Alice向4个邻居发送chunk：正在向其发送Chunk，速率最快的4个；每十秒钟重新评估
上传速率高，则能够找到更好 的交易伙伴，从而更快地获取 文件
每30秒随机选择一个其他节点，向其发送chunk
P2P的信息搜索
索引：信息到节点位置（IP+端口号）的映射
集中式索引
内容是分布式的，但索引是集中式的
会导致一些问题
单点失效
性能瓶颈
版权问题
洪泛式查询
查询消息通过已有的TCP连接发送
节点转发查询消息
如果消息命中，则利用反向路发回查询节点
示意
层次式覆盖网络
介于集中式索引和洪泛查询之间的方法
每个节点是或被分配一个超级节点
节点与超级节点之间有tcp连接
部分超级节点之间维持TCP连接
超级节点负责跟踪子节点的内容，索引分布在超级节点上
示意
chap 03 传输层
传输层服务概述
传输层协议为运行在不同Host上的进程提供了一种逻辑通信机制
端系统（主机）运行传输层协议
发送方：将应用递交的消息分成一个或多个的Segment（段），并向下传给网络层。
接收方：将接收到的segment组装成消息，并向上交给应用层。
传输层和网络层的关系
网络层：提供主机之间的逻辑通信机制
传输层：提供应用进程之间的逻辑通信机制
传输层位于网络层之上，使用网络层提供的服务，可能对网络层服务进行增强
将主机和进程类比家庭和孩子，家庭之间使用的邮政服务为网络层，孩子之间的通信为进程间的
传输层协议
TCP：可靠的传输
拥塞控制
流量控制
连接建立
UDP：不可靠的数据传输
两种服务均不保证：延迟、带宽
多路复用与多路分用
发送端进行多路复用:从多个Socket接收数据，为每块数据封装上头部信息，生成Segment，交给网络层
接收端进行多路分用:传输层依据头部信息将收到的Segment交给正确的Socket，即不同的进程
分用如何工作
主机接收到IP数据报(datagram)
每个数据报携带源IP地址，目的IP地址
每个数据报携带一个传输层的段
每个数据报携带源端口号和目的端口号
主机收到Segment之后，传输层协议提取IP地址和端口号信息，将Segment导向相应的Socket
分用的两种类型
无连接的分用：UDP
UDP的socket使用二元组进行创建：目的端口号，源端口号
主机收到UDP段后
检查段中的目的端口号
将UDP段导向绑定在该端口号所在的socket上
来自不同源IP地址和/或源端口号的IP数据包被导向同一个Socket
面向连接的分用：TCP
TCP的socket使用四元组进行标识：源IP，目的IP，源端口号，目的端口号
接收端利用所有的四个值将segment导向合适的socket
服务器可能同时支持多个TCP Socket，每个socket有着独立的四元组标识
Web服务器为每个客户端开不同的Socket
无连接传输：UDP
基于IP协议的无连接传输层协议，拥有复用/分用的基本功能和简单的差错校验
是一种“Best Effort”协议，不保证防丢失与按序到达
是一种无连接协议，接收方与发送方无需握手，段之间可以独立处理
为什么使用UDP？
无需建立连接 (减少延迟)
实现简单，无需维护状态
头部开销少
没有拥塞控制：可以使用尽可能多的资源传输
常用于流媒体应用/DNS/SNMP
简单的差错检测：校验和checksum
发送方
将段的内容视为16-bit整数
计算校验和：计算所有整数的和，进位加在和的后面，将得到的值按位求反，得到校验和
发送方将结果放入校验和字段
接收方
计算所收到的校验和
与发送方的校验和字段进行对比
相等：不一定没错
不相等：一定有错
实例
计算时需要进位
取反
可靠数据传输原理
可靠数据传输协议
可靠数据传输原理
不错、不丢、不乱
渐进地设计可靠数据传输协议的发送方和接收方
利用状态机(Finite State Machine, FSM)刻画传输协议
Rdt 1.0：可靠信道上的可靠数据传输
在信道上不会发生任何丢失与错误
发送方与接收方的状态机独立
发送方：等待接受到应用层传递过来的数据，接收到后打包为segment发送
接受方：等待传递过来的segment，将packet解包后递交给应用层
Rdt 2.0：信道中产生位错误
底层信道可能反转分组中的位/bit
解决方法：使用校验和进行差错检验
如何恢复？
使用ACK进行确认（接收方显式告知发送方已经正确接收），如果发现错误就发送NAK，发送方收到NAK后会重传分组
FSM
发送方：在收到应用层传递的数据后会将其打包发送，然后等待来自接受方的ACK或NAK，收到ACK就会继续等待下一个数据包，收到NAK会重传刚发送的数据包
接收方：等待收到来自发送方的数据，对其进行checksum校验，根据结果返回ACK或NAK
等——停协议
Rdt2.0的缺陷
如果ACK/NAK发生错误会怎样？
可以为ACK与NAK建立纠错机制，但是当ACK/NAK坏掉时重传分组很可能造成分组重复
为了解决重复分组，可以引入序号机制
Rdt 2.1：应对ACK/NAK破坏
FSM
需要等待对应序号的ACK或NAK，当序号错误或受到NAK时都会重传
需要额外考虑对应的序号，当收到指定序号的数据包（无错误）时会返回对应序号的ACK，如果收到重复的分组（序号与期望不一样）则直接丢弃（状态不变），是否重传则由发送方来进行处理
2.1 verse 2.0
发送方
2.1为每个分组新添了序列号
为什么需要除01之外的其他序列号？为流水线机制做铺垫；仅有两个序号等待时间太长
需要校验ACK序号是否正确
状态数量翻倍
接收方
判断分组是否重复：当前所处状态提供了期望收到的分组的序列号
接收方无法知道ACK/NAK是否被正确收到
Rdt 2.2：无NAK协议
与2.1功能相同，但是只用ACK
如何实现？
接收方通过ACK告知最后一个被正确接收的分组
在ACK消息中显式地加入被确认分组的序列号
发送方收到重复ACK之后，采取与收到NAK消息相同的动作：重传当前分组
FSM
减少了一个状态的改变，接收方在收到错误与序号不匹配时都会返回最后一个已经正确接收的分组序号的ACK；发送方会根据返回的ACK的序号进行处理：继续发送 or 重传当前分组
Rdt 3.0：信道不仅可能错误，而且可能丢失
解决方法：发送方等待合理时间（timeout）
如果没收到ACK，重传
如果只是延迟
重传过去的分组重复会丢弃
接收方需要在ACK中显式告知确认的分组
需要定时器
FSM
发送方新添加了超时后重传的机制
实例
重复的分组会被接收方丢弃
性能分析
能正常工作但性能很差
停等机制增加其发送时间
流水线机制与滑动窗口协议
流水线机制可以增加发送效率
每次同时发送多个分组，以不同的序号标识
允许发送方在收到ACK之前连续发送多个分组
更大的序列号范围
发送方和/或接收方需要更大的存储空间以缓存分组
滑动窗口协议
窗口：允许使用的序列号范围
窗口尺寸为N：最多有N个等待确认的消息
有两个协议：GBN、SR
GO-BACK-N和SR协议
GBN协议
使用累计确认的机制，接收方每次收到数据包时会返回已经确认的最大序号的ACK
当序号为send_base的数据包丢失时，接受方即使成功接受到后面序号的数据包仍会丢弃（无缓存），返回的还是已经确认的最大序号（顺序序列的最后一个）/n
当发送方收到的ACK序号大于等于send_base时，会将窗口向前移动到收到的序号处，重置计时器并发送新的数据包；当超时时会重传大于接收到的最大顺序序号/n的所有分组
SR协议
不使用累计确认，每个分组独立确认
对于大于send_base的分组会缓存，缓存乱序到达的分组
每个分组独立设置计时器，timeout时只会重发当前分组
发送方
上面的数据： 如果窗口中有下一个可用的 seq #，则发送 pkt 超时（n）： 重新发送 pkt n，重新启动计时器 [sendbase,sendbase+N] 中的 ACK(n)： 将 pkt n 标记为已接收 如果 n 最小未确认的 pkt，将窗口基数推进到下一个未确认的 seq #
接受方
pkt n in [rcvbase, rcvbase+N-1] 发送 ACK(n) 无序：缓冲区 有序：交付（也交付缓冲的、按顺序的 pkt），将窗口推进到下一个尚未的窗口-收到的包裹 [rcvbase-N,rcvbase-1] 中的 pkt n ACK(n)，否则为重复分组，忽略
序列号空间大小与窗口大小需要满足一定条件：NS+NR<=2^k
面向连接传输：TCP
TCP是全双工通信
TCP段结构
每行四个字节32位
源端口，目标端口
序列号指的是segment中第一个字节的编号，而不是segment的编号
ACKs：希望收到的下一个字节的序列号 累计确认：该序列号之前的所有字节均已被正确接收到
二者以字节为单位
启用ACK字段的为返回分组，否则为发送分组
RST：重置；SYN：同步；FIN：结束；可能会在握手与挥手时用到
TCP可靠数据传输
TCP RTT与超时
如何设置定时器的timeoutInterval？
过大：等待时间长
过小：可能是延迟，重复发送分组
使用经验总结的公式/移动加权平均
alpha一般取0.125
beta一般取0.25
TCP发送方事件
从应用层收到数据
创建Segment
序列号是Segment第一个字节 的编号
开启计时器
设置timeoutInterval
超时
重传引起超时的segment，重启定时器
收到ACK
如果确认此前未确认的segment：更新send_base，如果窗口中还有未被确认的分组，更新定时器
ACK的序号是下一次期望收到的序号，不是已经确认的（可以看成是已经确认+1）
TCP接收方事件
具有预期序列号的有序段到达。达到预期 seq # 的所有数据均已确认
延迟的 ACK。等待下一段最多 500 毫秒。如果没有下一个报文段，则发送ACK
具有预期序列号的有序段到达。另一个段有 ACK 待处理
立即发送单个累积 ACK，对两个按顺序段进行确认
无序段的到达高于预期序列。 #.检测到间隙
立即发送重复的 ACK，指示 seq。下一个预期字节的#
部分或完全填补空白的航段的到达
立即发送 ACK，前提是该段从间隙的下端开始
快速重传机制
TCP的实现中，如果发生超时，超时时间间隔将重新设 置，即将超时时间间隔加倍，导致其很大
可以通过重复的ACK检测其丢失
当接收方收到乱序的数据时，会发送重复的ACK（下一个期望的序号）
当收到三个重复ACK，认为数据包丢失，触发快速重传，在定时器超时之前重传
TCP流量控制
为了防止处理速度小于接收速度导致排队，甚至缓存溢出导致丢包，需要对流量进行控制
发送方不会传输的太多、太快以至于淹没接收方（buffer溢出）
使用速度匹配机制
Buffer中的可用空间为RcvWin
接收方在TCP段的头部将RcvWin告诉发送方，Sender限制自己已经发 送的但还未收到ACK的数据不超过接收方的空闲RcvWindow尺寸
TCP连接管理
建立连接：三次握手
发送方：向接收方发送含有SYN的请求，不含有数据
接收方：收到后返回含有SYN的ACK
发送方：收到后返回ACK
关闭连接：四次挥手
发送方：向接收方发送含有FIN的段
接收方：收到FIN，回复ACK，关闭连接（不再传输数据）并发送FIN
发送方：收到后回复ACK
接受方：收到ACK，连接关闭
拥塞控制原理
拥塞的成因和代价
拥塞：非正式定义：“太多发送主机发送了太多数据或者发送速度太快，以至于网络无法处理”
实际上就是数据占满了信道，像堵车一样难以前进
表现
分组丢失
传输延迟
与流量控制的区别
流量控制是端到端的控制，而拥塞控制是在链路全局上的控制
场景分析
stage 1：无限缓存，一个路由器
stage 2：一个路由器，有限缓存，有重传分组
stage 3：多个路由器
当一个分组被drop时，任何用于该分组上游的路由器传输能力全部被浪费掉
拥塞控制的方法
端到端的控制
TCP采取这种方法
网络辅助的控制：ABR
TCP拥塞控制
TCP性能分析
如何感知网络拥塞：使用丢包（三个重复的ACK）或者超时来进行感知
如何调整发送速率？
加增减乘：AIMD
原理：逐渐增加发送速率，谨慎探测可用带宽，直到发生loss
线性增加发送速率，当发生loss事件时，将CongWin降低到一半
图示
慢启动：SS
原理：当连接建立时，速率指数型增长
每个RTT将CongWin翻倍
收到每个ACK进行操作
当达到CongWin达到loss事件前值的1/2时，将指数型增长切换为线性增长
将其存在threshold变量中
对不同事件的处理
三个重复ACK
CongWin切到一半，然后线性增长
timeout
将CongWin直接设为一个MSS（最大报文段，单次报文段传输最大长度），然后指数增长，达到threshold后再线性增长
图示
TCP的公平性
如果K个TCP Session共享相同的瓶颈带宽R，那么每个Session的平均速率 为R/K
TCP具有公平性，会通过速率的调整来使得各个session的速率趋近相同
UDP则没有公平性
但是TCP的公平性是针对连接（进程）而言的，不是针对主机
chap 04 网络层
网络层服务
从发送主机向接收主机传送数据段（segment）
发送主机：将数据封装到数据报（datagram）中
接收主机：向传输层递交数据段（segment）
每个主机和路由器都运行网络层协议
路由器检验所有穿越它的IP数据报的头部域
网络层的核心功能
转发：将分组从路由器的输入端口转移到合适的输出端口
路由：确定分组从源到目的经过的路径
首先通过路由算法确定通过网络的端到端路径，再通过转发表确定路由器如何转发分组
数据分组传输之前需要网络设备建立逻辑连接
与传输层连接不同的是，传输层建立的是端到端连接，而网络层连接中路由器也会参与
网络层服务模型
无连接模型
不事先为系列分组的传输确定传输路径
每个分组独立确定传输路径
不同分组可能传输路径不同
数据报网络(datagram network )
有连接模型
首先为系列分组的传输确定从源到目的经过的路径(建立连接)
然后沿该路径（连接）传输系列分组
系列分组传输路径相同
传输结束后拆除连接
虚电路网络(virtual-circuit network )
虚电路网络与数据报网络
数据报(datagram)网络与虚电路(virtual-circuit)网络是典型两类分组交换网络
数据报网络提供网络层无连接服务
虚电路网络提供网络层连接服务
虚电路（VC）：一条从源主机到目的主机，类似于电路的路径(逻辑连接)
通信过程
呼叫建立(call setup)→数据传输→拆除呼叫
每个分组携带虚电路标识(VC ID)，而不是目的主机地址
虚电路经过的每个网络设备 （如路由器），维护每条经过它的虚电路连接状态
链路、网络设备资源(如带宽、缓存等)可以面向VC进行预分配
VC的具体实现
每条虚电路包括
从源主机到目的主机的一条路径
虚电路号（VCID）， 沿路每段链路一个编号
沿路每个网络层设备（如路由器），利用转发表记录经过的每条虚电路
沿某条虚电路传输的分组，携带对应虚电路的VCID，而不是目的地址
同一条VC ，在每段链路上的VCID通常不同
路由器转发分组时依据转发表改写/替换虚电路号
VC信令协议
用于建虚电路网络的建立，维护和拆除
不用于Internet
数据报网络
网络层无连接
每个分组携带目的地址
路由器根据分组的目的地址转发分组
基于路由协议/算法构建转发表
检索转发表
因为地址太多，转发表记录的是地址范围而不是确定的地址（聚合转发表入口）
每个分组独立选路
转发时使用最长前缀匹配：在检索转发表时，优先选择与分组目的地址匹配前缀最长的入口（entry）
数据报网络与虚电路网络的区别
数据报网络是简化网络，复杂边缘
虚电路网络是复杂网络，简化边缘
路由器体系结构
路由器的主要作用
运行路由算法/协议（RIP、OSPF、BGP）
将数据报从传入链路转发到传出链路
输入端口示意图
最左边的是物理层，传输数据比特
然后是链路层
网络层，进行分组转发
给定数据报目的地，使用输入端口内存中的转发表查找输出端口（“匹配加操作”）
理想情况下，会以宽带速度完成转发
但有时会有排队：当转发速度小于数据报进入交换结构的速度会产生
当排队较多，缓存区溢出时会发生丢包
队头阻塞(head -of- line):队列前面的排队数据报阻止队列中的其他数据报向前移动
输出端口争用:只能传输一个红色数据报。下方红包被阻塞
一个包后:绿色包经历HOL阻塞
是因为原先绿色包前面的红色包通路被占用，所以队头阻塞
需要将数据包从输入缓存区转发到合适的输出缓存区中
转发速率（switch rate）：数据包从输入到输出的传输速率
通常以输入/输出线路速率的倍数来测量
N个输入:转发速率N倍于理想的线路速率
转发的结构：三种
memory
传统的在计算机CPU控制下进行的转发
数据包复制到系统内存
速度受内存带宽限制（每个数据报2个总线交叉点）
bus（总线）
经由共享总线从输入端口存储器到输出端口存储器的数据报
独立的处理器来进行转发
总线争用：交换速度受总线带宽限制
crossbar
克服总线带宽限制
拥有多个处理器，性能强大
先进的设计：将数据报分段成固定长度的信元，通过结构交换信元。
输出端口
总体看与输入端口结构类似，数据方向相反：网络层->链路层->物理层
当数据报从转发结构到达的速度快于传输速率时需要缓冲
调度规则在排队的数据报中选择传输
由于输出端口缓冲区溢出导致的延迟和丢失
IP协议
网络层的协议主要分为
路由协议：路径选择
IP协议：寻址规约、数据报（分组）格式、分组处理规约
ICMP协议：差错报告、路由器“信令”
IP数据报
IP数据报格式
每行为4字节，也就是32位
版本号字段占4位
首部长度字段占4位，以4字节为单位
首部长度最大达到64字节，也就是16行
服务类型字段占8位
一般情况下不使用
总长度字段占16位
为IP分组的总字节数=首部+数据
最大IP分组的总长度：65535B
最小的IP分组首部：20B
IP分组可以封装的最大数据：65535-20=65515B
生存时间（TTL）字段占8位
为IP分组在网络中可以通过的路由器个数（跳数）
每通过一个路由器，TTL-1；当TTL为0时，路由器丢弃该分组
协议字段占8位
指示IP协议是封装的哪个协议的数据包（TCP、UDP等）
实现了复用分解
首部检验和（checksum）字段占16位
实现对IP首部的差错检测
需要逐跳计算、逐跳校验（路由器也在网络层中）
源IP地址占32位
目的IP地址占32位
可选项：为1到40个字节的字段，需要填充至四字节的倍数
IP数据报分组分片
MTU：链路层的最大传输单元
如果IP层传输的数据大于MTU且DF=0的话会进行分片
IP数据报首部的总长度、标识、标志位和片偏移字段被用来标识分片与确定顺序
标识字段占16位
被用来标识一个IP分组
使用计数器，每产生一个分组就加一
标志位字段占3位
分别是保留位、DF位与MF位
DF位用于表示是否禁止分片：当DF=1时禁止分片；DF=0时允许分片
MF位用于表示是否为最后一个分片：MF=1时不是最后一片；MF=0时表示最后一片（未分片）
片偏移字段占13位
表示一个IP分组的分片相对原数据的偏移量
以8字节为单位
所以要求分片大小为8字节的整数倍
分片规则
每个分片总大小（包含首部）必须是8的倍数
分片数据长度（单位：字节）：
MTU减去首部字节大小，除以8向下取整（需要满足d+20不大于MTU）乘8（8的整数倍）
分片个数：
L是原分组总长度（包括首部）
每个分片的总长度(包括首部)
片偏移大小：
标志位MF字段：当该分片为最后一片时MF为0，否则为1
IP地址与子网划分
IP分组中有着源地址与目的地址的字段
接口：主机/路由器与链路的连接
路由器有多个接口
主机通常有一到两个接口（有线/无线）
IP地址（IPv4）是32位对于网络中的主机/路由器接口的标识
IP地址与每个接口关联
使用IP子网（Subnet）为接口分配地址
IP地址由两部分组成：网络号（NetID）为高位比特、主机号（HostID）为低位比特
IP子网指的是具有相同网络号，不跨越路由器可以相互物理联通的接口
六个，因为有六个不同的NetID
IP编址
有类编址
将IP地址划分为A/B/C/D/E类
A类：0.0.0.0——127.255.255.255
B类：128.0.0.0——191.255.255.255
C类：192.0.0.0——223.255.255.255
D类：224.0.0.0——239.255.255.255
E类：240.0.0.0——255.255.255.255
实际上就是从IP地址的前四位作为分类依据
特殊IP地址
私有IP地址
如何区分一个IP子网（更小范围网络）？子网划分
将HostID中的一部分较高位作为子网ID（SubID），以此对子网进行划分
例如：对202.118.1.0/24的网络进行子网划分为两个等大小的网络
分别为202.118.1.0-127，子网掩码：255.255.255.128；202.118.1.128-255，子网掩码：255.255.255.128
划分为两个等长子网需要后借一位，划分为四个等长子网需要后借两位
如何确定是否划分了子网？使用子网掩码
子网掩码+子网地址=准确确定子网大小及范围
子网掩码是形如IP地址的32位点分十进制形式
取值规则
NetID与SubID全取1
HostID全取0
例如
A类默认子网掩码：255.0.0.0
B类默认子网掩码：255.255.0.0
C类默认子网掩码：255.255.255.0
B类的默认子网掩码借用三位划分子网为：255.255.224.0
将子网掩码与子网地址作and操作即可获取子网的NetID+SubID
子主题
有类编址容易造成IP空间的浪费
CIDR与路由聚合
无类域间路由
将NetID+SubID的位数作为任意长度的网络前缀
融合了NetID与SubID便于子网划分
格式为：a.b.c.d/x，x为前缀长度
例如：子网：201.2.3.64，子网掩码：255.255.255.192，则使用CIDR表示为：2.0.2.3.64/26
优点
提高了IPv4地址分配效率
将多个子网进行聚合，构造超网
聚合路由，层级编址使得通告更加高效
使用最长前缀优先匹配
DHCP协议
一台新的主机如何获取IP地址？
硬编码
进行静态手动配置
动态主机配置协议DHCP（Dynamic Host Configuration Protocol）
从DHCP服务器动态获取IP地址、子网掩码、默认网关和DNS服务器名称与地址
步骤
主机广播“DHCP discover”(发现报文)
DHCP服务器利用“DHCP offer” (提供报文) 进行响应
主机请求IP地址: “DHCP request” (请求报文)
DHCP服务器分配IP地址: “DHCP ack” (确认报文)
四次通信均为广播，完成后主机获得IP地址
示例
第一次通信yiaddr为0.0.0.0，后面三次都是DHCP服务器先要分配给该主机的IP地址
DHCP协议在应用层实现
请求封装在UDP数据报中
NAT
所有离开本地网络去往Internet的数据报的源IP地址需替换为相同的NATIP地址: 138.76.29.7以及不同的端口号
动机
只需从ISP申请一个IP地址
延缓地址短缺
本地设备iP地址的变更无需通告外界
更换ISP时本地网络设备IP地址无需变更
内部网络对外部不可见，安全
实现
替换：利用(NAT IP地址,新端口号)替换每个外出IP数据报的(源IP地址,源 端口号)
记录：将每对(NAT IP地址, 新端口号) 与(源IP地址, 源端口号)的替换信 息存储到NAT转换表中
替换：根据NAT转换表，利用(源IP地址, 源端口号)替换每个进入内网IP 数据报的(目的IP地址,目的端口号)，即(NAT IP地址, 新端口号)
在传出网络时将源IP与端口替换为NATIP和新端口
接受来自外界的请求时将收到的NATIP与端口号按照转换表转为源IP和源端口
NAT具有16位的端口号，可以支持数万的并行连接
NAT的问题
路由器不应该负责进程（端口）相关的任务
违背了端到端通信的原则
应用开发者需要考虑NAT的存在，例如P2P
地址短缺问题应该由IPv6来解决
NAT穿透
期望访问内网地址为10.0.0.1的服务器，但是不能直接访问（不可知），对外只有唯一的一个NAT IP地址
解决方法
静态配置
将指定NAT IP和端口号的请求转发给指定内网IP地址的主机
UPnP：互联网网关设备协议
中继：双方与中继服务器建立连接，中继服务器桥接两个连接的分组
ICMP协议
互联网控制报文协议 ICMP (Internet Control Message Protocol)支持主机或路由器：差错报告；网络探询
两类ICMP报文
差错报文：5种
目的不可达
源抑制
超时
参数问题
重定向
网络探询报文：2种
回声（ping）请求与响应报文
时间戳请求与响应报文
几种不发送ICMP报文的特殊情况
对ICMP差错报告报文不再发送 ICMP差错报告报文
除第1个IP数据报分片外，对所有后续分片均不发送ICMP差错报告报文
对所有多播IP数据报均不发送 ICMP差错报告报文
对具有特殊地址（如127.0.0.0 或 0.0.0.0）的IP数据报不发送 ICMP 差错报告报文
ICMP报文的格式
ICMP首部
前四个字节（32位）分别为：类型占8位，代码占8位，checksum占16位
后四个字节由ICMP的类型决定
ICMP数据部分由类型决定
ICMP报文的封装
需要封装在IP数据报中
在ICMP中插入IP数据报的首部作为ICMP报文，插入IP数据报的首部与数据部分之间
ICMP应用举例：tranceroute
每次向目的主机发送一个IP数据报，且随着每次发送TTL++
当第n组经过第n个路由器时会被丢弃
结束条件：1.到达目的主机；2.目的主机返回目的不可达ICMP报文；3.源主机停止运行
IPv6简介
动机
地址短缺：主要原因
快速处理转发数据报
IPv6数据报格式
固定长度的四十字节首部
不允许分片
版本占4位
优先级占8位
流标签占24位，标识同一流中的分组
载荷长度占16位
下一个首部占8位，标识下一个选项首部或上层协议首部（如TCP）
实现分路复用
跳步限制占8位，类似TTL
源地址与目的地址都为128位，分别占4行
以上为40字节首部，扩展首部与数据在下面——载荷
与IPv4的区别
移除校验和，无需逐跳检验，提高转发效率
选项从基本首部移除到扩展首部，通过下一个首部字段指示
取消了广播，使用多播来近似实现
IPv6表示形式
为八段：分式，每段4位16进制数组成
每位16进制数可以换算为4位二进制，所以相当于16位二进制
如果不满4位16进制请在数字前面填充0直到满足四位，再将其转为二进制
IPv4嵌入形式
最后两段改为IPv4的显示形式
每一段表示16位，那么两段就是32位——IPv4
例如：::FFFF:13.1.68.3
只使用地址前缀，而不是用子网掩码
例如：2002:43c:476b::/48,只使用前三段48位作为网络前缀
IPv6基本地址类型
单播：一对一通信
多播：一对多通信
任意播：一堆一组之一（最近）
IPv4向IPv6过渡
穿越IPv4网络
目前IPv6还不完全普及，需要穿越IPv4的网络
隧道
将IPv6数据报作为载荷封装在IPv4数据报中，穿越IPv4网络
路由算法
网络抽象——图
将网络视为由点集（路由器）和边集（链路）组成的图
费用
经由某链路转发的代价
目标是找到转发的最小费用路径
链路状态路由算法
静态路由/动态路由
静态路由需要手动配置，无法及时根据状态进行更新，有较高的优先级
动态路由定期更新，及时响应变化
全局信息/分散信息
全局信息：所有路由器信息一样——完整的网络拓扑结构和链路费用信息
分散信息：路由器只掌握邻居的信息，邻居之间交换信息
LS（链路状态路由算法）
需要全局信息
使用Dijkstra算法进行最小费用路径的求解
Dijkstra算法的核心是找到距离已达集的最小费用路径（费用需要累加）并将对应未进入已达集的点加入已达集
最终会生成一颗最短路径树，根据最短路径树构建转发表
每个节点（路由器）的转发表不一样，但是其获取到的信息是一样的
复杂度
Dijkstra算法要求寻找最小费用的邻接边
遍历：O(n^2)
优化：O(nlogn)
LS的震荡
假设费用为链路承载的通信量
最小费用路径计算完毕，进行转发
通信量实时变化
重新计算最小费用路径，有可能出现来回震荡的情况，因为通信量变化而使得数据报来回往返
通信量作为费用不合适
距离向量路由算法
Bellman-ford方程
设dx(y)为从x到y的最小费用，则有
dx(y)=min{c(x,v)+dv(y)}
v是x的邻居
此过程相当于动态规划
距离向量路由算法DV
设Dx(y)为x到y的最小费用的估计
存在距离向量[Dx(y):y∈N]
每个节点
已知其到每个邻居的费用c(x,v)
维护其所有邻居的DV [Dv(y):y∈N]
会不定时地将自身的DV发送给邻居
当收到邻居的DV更新时，会更新自身DV
Dx(y)->min{c(x,v)+Dv(y)} for y in N
是一种异步迭代更新
只有节点DV改变时才会进行通告
经过迭代后逐渐逼近LS的效果
对于DV来说，好消息（费用更小）传播较快
如果变小的话会进行更新从而改变DV，会进行通告
坏消息（费用变大）会传播得很慢
原先的DV表
经过一次通告
子主题
子主题
子主题
也即是Dy(x)和Dz(x)会更新得很慢，在逐渐传播中增加
这也是无穷计数问题
解决无穷计数问题的方案
毒性逆转
如果一个结点(e.g. Z)到达某目的(e.g.X)的最小费用路径是通过某个邻居(e.g.Y)，则：通告给该邻居结点到达该目的的距离为无穷大
定义最大度量：最大的费用有效值
层次路由
在大规模网络中几乎不能标识所有路由器
将整体网络划分为不同的AS，AS内部管理自治
同一AS中的路由器运行相同的路由协议（算法）
网关路由器
位于AS的边缘
与其他AS的网关路由器相连接
转发表由AS内部路由算法与AS间路由算法共同配置
AS内部路由算法设置AS内部目的网络路由入口(entries)
AS内部路由算法与AS间路由算法共同设置AS外部目的网络路由入口
网关路由器的任务
确定到达目的网络需要经过的外部AS，也即是外部AS的可达性信息
将可达性信息传达给内部路由器
若多个外部AS均可到达目标网络。则需要进行决策
热土豆路由
将分组转发给最近（最小费用）的网关路由器
路由协议
Internet采用层次路由
RIP协议
使用DV算法
以跳步数作为费用，每条链路一个跳步
每个30秒邻居交换一次DV
当然DV改变时也会进行通告
每次通告最多25个子网
示例
A向D通告
D的路由表更新
如果180没有收到通告，则认为邻居/链路失效
如果链路失效可能发生无穷计数问题
使用毒性逆转，认为16跳为最大距离度量
RIP路由表是利用一个称作route-d (daemon)的应用层进程进行管理
通告报文周期性通过UDP进行发送
OSPF协议
采用LS算法
LS分组扩散
每个路由器掌握完整的网络拓扑结构
利用Dijkstra算法计算路由
OSPF通告在AS范围内洪泛
OSPF报文直接封装在IP数据报中
OSPF相对RIP的优点
安全：OSPF报文可以被认证
允许使用多条费用相同的路径（RIP只能选一条）
对于每条链路，可以针对不同的TOS设置多个不同的费用度量
集成单播与多播路由
支持对大规模AS进行分层
将AS分为多个局部区与主干
区边界路由器：连接区与主干
网关路由器在主干处
BGP协议
BGP协议是事实上的标准区间路由协议
为每个AS提供了一种手段
eBGP：从邻居AS获取子网可达性信息
iBGP：将可达性信息传达给内部路由器
基于可达性信息与“策略”确定路由
BGP会话：两个BGP路由器 (“Peers”)交换BGP报文
通告去往不同目的前缀的路径
报文交换基于半永久的TCP
报文种类
OPEN: 与peer建立TCP连接，并认证发送方
UPDATE: 通告新路径 (或撤销原路径)
KEEPALIVE: 在无UPDATE时，保活连接；也用于对OPEN请求的确认
NOTIFICATION: 报告先前报文的差错；也被用于关闭连接
BGP过程
当AS3通告给AS1某个前缀时
AS3承诺可以将数据报转发给该子网
AS3在通告中会聚合网络前缀
当路由器获得新的前缀可达性时，会在其转发表中加入该前缀的入口
通告的前缀信息包括BGP属性
前缀+属性= “路由”
两个重要属性
AS-PATH(AS路径): 包含前缀通告所经过的AS序列
NEXT-HOP(下一跳): 开始一个AS-PATH的路由器接口，指向下一跳AS.
网关路由器收到通告时，利用其输入策略接受/拒绝该路由
以下是一些策略
1. 本地偏好(preference)值属性: 策略决策(policy decision)
2. 最短AS-PATH
3. 最近NEXT-HOP路由器: 热土豆路由(hot potato routing)
4. 附加准则
AS内部网络路由侧重性能，而AS之间路由侧重策略
chap 05 链路层
数据链路层服务
数据链路层负责通过一条链路从一个节点向另一个物理链路直接相连的相邻结点传送数据报。（帧）
服务
组帧(framing)
封装数据报构成数据帧，加首部和尾部
帧同步
链路接入(link access)
如果是共享介质，需要解决信道接入(channel access)
帧首部中的“MAC”地址，用于标识帧的源和目的
相邻结点间可靠交付
在低误码率的有线链路上很少采用 (如光纤，某些双绞线等)
无线链路：误码率高，需要可靠交付
流量控制(flow control)
协调(pacing)相邻的发送结点和接收
差错检测(error detection)
信号衰减和噪声会引起差错.
接收端检测到差错:通知发送端重传或者直接丢弃帧
差错纠正(error correction)
接收端直接纠正比特差错
全双工和半双工通信控制
全双工：链路两端结点同时双向传输
半双工：链路两端结点交替双向传输
链路层的具体实现
链路层在“适配器”(即网络接口卡-NIC)中实现 或者在一个芯片上实现
以太网网卡，802.11网卡；以太网芯片组
实现链路层（部分）与物理层
网卡结构
网卡通信
发送端：
将数据报封装成帧
增加差错检测比特，实现可靠数据传输和流量控制等.
接收端：
检测差错，实现可靠数据传输和流量控制等
提取数据报，交付上层协议实体
差错编码
类型
差错编码基本原理：D→DR，其中R为差错检测与纠正比特（冗余比特）
检错码
对于检错码，如果编码集的汉明距离ds=r+1，则该差错编码可以检测r位的差错
纠错码
对于纠错码，如果编码集的汉明距离ds=2r+1，则该差错编码可以纠正r位的差错
方式
奇偶校验
校验和
与之前的checksum相同：发送端计算16进制数据进位和取反，接收端校验
循环冗余校验CRC
将数据比特，D，视为一个二进制数
选择一个r+1位的比特模式 (生成比特模式)，G
目标：选择r位的CRC比特，R，满足
<D,R>刚好可以被G整除(模2)
接收端检错：利用G除<D,R>，余式全0，无错；否则，有错！
可以检测所有突发长度小于r+1位差错。
应用于实际网络（如以太网）
实例
公式：
R为CRC比特，D为数据比特，G为选择的生成模式
多路访问控制(MAC)协议
链路层为单一共享广播渠道，当信道中有两个或以上节点同时传输，会产生干扰
冲突(collision) 结点同时接收到两个或者多个信号→接收失败！
所以我们采用多路访问控制协议来决定节点如何共享信道
信道划分MAC协议
多路复用技术
FDMA：频分复用，将信道的不同频段划分给不同的节点
TDMA：时分复用，将传输过程划分为不同时隙，不同节点只在不同时隙进行数据交换
CDMA：码分复用
随机访问MAC协议
信道不划分，允许冲突；采用冲突“恢复”机制
需要定义如何检测冲突，如何从冲突中恢复
时隙ALOHA
假定
所有帧大小相同
时间被划分为等长的时隙(每个时隙可以传输1个帧)
结点只能在时隙开始时刻发送帧
结点间时钟同步
如果2个或2个以上结点在同一时隙发送帧，结点即检测到冲突
运行
当结点有新的帧时，在下一个时隙(slot)发送
如果无冲突：该结点可以在下一个时隙继续发送新的帧
如果冲突：该结点在下一个时隙以概率p重传该帧，直至成功
优点
单个结点活动时，可以连续以信道全部速率传输数据
高度分散化：只需同步时隙
简单
缺点
冲突，浪费时隙
空闲时隙
结点也许能以远小于分组传输时间检测到冲突
时钟同步
效率分析
假设: N个结点有很多帧待传输，每个结点在每个时隙均以概率p发送数据
对于给定的一个结点，在一个时隙将帧发送成功的概率= p(1-p)N-1
对于任意结点成功发送帧的概率= Np(1-p)N-1
最大效率: 求得使Np(1-p)N-1最大的p*
对于很多结点，求Np*(1-p*)N-1当N趋近无穷时的极限，可得:最大效率为1/e，约等于0.37
ALOHA
无时隙，当有新的帧生成时，立即发送；更加简单
冲突可能性增大：在t0时刻发送帧，会与在[t0-1, t0+1]期间其他结点发送的帧冲突
效率分析
P(给定结点成功发送帧) = P(该结点发送) . P(无其他结点在[t0-1, t0]期间发送帧) . P(无其他结点在[t0, t0+1]期间发送帧) = p . (1-p)N-1 . (1-p)N-1 = p . (1-p)2(N-1) … 选取最优的p，并令n趋于无穷 = 1/(2e) = 0.18
比时隙ALOHA效率更差
CSMA/CD
载波监听多路访问协议CSMA
需要在发送帧之前监听信道
信道空闲：发送完整帧
信道忙：推迟发送
1-坚持CSMA
非坚持CSMA
P-坚持CSMA
推荐
冲突仍然可能发生，因为有信号传播的延迟（物理）
CSMA/CD（Collision Detection）
短时间内可以检测到冲突
冲突后传输中止，减少信道浪费
冲突检测
有线信道易于实现：测量信号强度，比较发射信号与接受信号
无线信道不易实现：接收信号可能会淹没在接收方的发射信号中
对于距离的要求
网络带宽：R bps
数据帧最小长度：Lmin (bits)
信号传播速度：V (m/s)
因为Lmin/R要大于RTT（2倍的传播距离加一点可以忽略的处理时间），所以有Lmin/R≥2dmax/v
dmax=Lmin*v/2R
CSMA/CD效率
Tprop = LAN中2个结点间的最大传播延迟
ttrans = 最长帧传输延迟
要想提高效率
减少传播延迟，减少距离
增大传输延迟，增大最小帧长度
轮转访问MAC协议
前两种方法
信道划分MAC协议：
网络负载重时，共享信道效率高，且公平
网络负载轻时，共享信道效率低！
随机访问MAC协议：
网络负载轻时，共享信道效率高，单个结点可以利用信道的全部带宽
网络负载重时，产生冲突开销
轮转MAC协议综合了二者的优点
轮询：主结点轮流“邀请”从属结点发送数据
令牌传递(token passing): 控制令牌依次从一个结点传递到下一个结点.
令牌实际上是一个特殊帧
有令牌的节点可以激活并发送数据，没有令牌的节点需要等待
ARP协议
MAC地址介绍
是一种48位地址，由六祖两位十六进制数组合而成
作用：标识网络内的一个帧从哪个接口发出，到达哪个物理相连的其他接口（物理位置）
48位MAC地址(用于大部分LANs)，固化在网卡的 ROM中，有时也可以软件设置
MAC地址在局域网内是唯一的，而IP地址在全球唯一；但是MAC地址是不可变的（身份证），IP地址可以变动（邮政编码）
局域网中的每块网卡都有一个唯一的MAC地址
MAC地址是“平面”地址： 可“携带” 可以从一个LAN移到另一个LAN
IP地址是层次地址，不可携带，取决于连接到哪个子网
ARP协议：MAC解析协议
（在同一个LAN内）如何在已知目的接口的IP地址前提下确定其MAC地址？
使用ARP表维护IP与MAC的映射关系
ARP表: LAN中的每个IP结点(主机、路由器)维护一个表
存储某些LAN结点的IP/MAC地址映射关系:
< IP地址; MAC地址; TTL>
TTL：经过这个时间以后该映射关系会被遗弃(典型值为20min)
好像IP数据报也有个字段是TTL，可经过路由器的跳数
在同一局域网内的ARP协议过程
A想要给同一局域网内的B发送数据报，但B的MAC地址不在 A的ARP 表中.
A广播ARP查询分组，其中包含B的IP地址
目的MAC地址 = FF-FF-FF-FF-FF-FF
LAN中所有结点都会接收 ARP查询
B接收ARP查询分组，IP地址匹配成功，向A应答B的MAC 地址
利用单播帧向A发送应答
A在其ARP表中，缓存B的IP-MAC地址对，直至超时
超时后刷新
ARP是“即插即用”协议:无需干预
寻址：从一个LAN到另一个LAN
通信过程: A通过路由器R向B发送数据报
关注寻址：IP地址(数据报中)和MAC地址(帧中)
假设A知道B的IP地址(怎么知道的?)
域名解析DNS？
假设A知道第一跳路由器R (左)接口IP地址 (怎么知道的?)
路由算法？
假设A知道第一跳路由器R (左)接口MAC地址 (怎么知道的?)
LAN内ARP？
A构造IP数据报，其中源IP地址是A的IP地址，目的IP地址是B的IP地址
A构造链路层帧，其中源MAC地址是A的MAC地址，目的MAC地址是R(左)接口的MAC地址，封装A到B的IP数据报。
帧从A发送至R，R接收帧，提取IP数据报，传递给上层IP协议
R转发IP数据报（源和目的IP地址不变！）
R创建链路层帧，其中源MAC地址是R(右)接口的MAC地址，目的MAC地址是B的MAC地址，封装A到B的IP数据报。
路由器通过路由算法将数据转发到B所在的LAN，再重复之前过程即可
以太网
以太网简介
是一个统治地位的有线LAN技术
是不可靠的无连接服务
以太网的MAC协议: 采用二进制指数退避算法的CSMA/CD
1. NIC从网络层接收数据报，创建数据帧。
2. 监听信道：
如果NIC监听到信道空闲，则开始发送帧；
如果NIC监听到信道忙，则一直等待到信道空闲，然后发送帧。
3. NIC发送完整个帧，而没有检测到其他结点的数据发送，则NIC确认帧发送成功！
4. 如果NIC检测到其他结点传输数据，则中止发送，并发送堵塞信号(jam signal)
5. 中止发送后，NIC进入二进制指数退避： 第m次连续冲突后： 取n = Min(m, 10) NIC 从{0,1,2, …, 2n-1}中随机选择一个数K NIC等待K·512比特的传输延迟时间，再返回第2步 连续冲突次数越多，平均等待时间越长。
选择512的原因是最小帧长度为2^8bit
以太网帧结构
前导码(Preamble)(8B):
7个字节的10101010，第8字节为10101011
用于发送端与接收端的时钟同步
目的MAC地址、源MAC地址(各6B):
如果网卡的MAC地址与收到的帧的目的MAC地址匹配，或者帧的目的MAC地址为广播地址(FF-FF-FF-FF-FF-FF)，则网卡接收该帧，并将其封装的网络层分组交给相应的网络层协议。
否则，网卡丢弃(不接收)该帧
类型(Type)(2B): 指示帧中封装的是哪种高层协议的分组(如，IP数据报、Novell IPX数据报、AppleTalk数据报等)
数据(Data)(46-1500B): 指上层协议载荷。
R=10Mbps，RTTmax=512μs，Lmin / R = RTTmax
Lmin=512bits=64B，Datamin=Lmin-18=46B
CRC(4B): 循环冗余校验码
丢弃差错帧
交换机
是一种链路层设备
存储-转发以太网帧
检验到达帧的目的MAC地址，选择性(selectively) 向一个或多个输出链路转发帧
利用CSMA/CD访问链路，发送帧
特点
透明：主机感知不到交换机的存在
自学习：无需配置
即插即用
需要交换表来对MAC地址和接口进行映射（类似路由器转发表）
通过自学习算法
当收到帧时，交换机“学习”到发送帧的主机（通过帧的源MAC地址），位于收到该帧的接口所连接的LAN网段
将发送主机MAC地址/接口信息记录到交换表中
当目的MAC已知时，选择性转发；否则泛洪
交换机 vs 路由器
均为存储转发设备
路由器: 网络层设备 (检测网络层分组首部)
交换机: 链路层设备 (检测链路层帧的首部)
均使用转发表
路由器: 利用路由算法(路由协议)计算(设置), 依据IP地址
交换机: 利用自学习、泛洪构建转发表, 依据MAC地址
虚拟局域网（VLAN）：这里就不介绍了
PPP协议
点对点的数据链路控制
一个发送端，一个接收端，一条链路：比广播链路容易；不需要寻址
功能
组帧：将网络层数据报封装到数据链路层帧中
可以同时承载任何网络层协议分组(不仅IP数据报)
可以向上层实现分用（多路分解）
比特透明传输：数据域必须支持承载任何比特模式
差错检测：(无纠正)
连接活性(connection liveness)检测：检测、并向网络层通知链路失效
网络层地址协商：端结点可以学习/配置彼此网络地址
PPP数据帧结构
标志(Flag): 定界符(delimiter)
地址(Address): 无效(仅仅是一个选项)
控制(Control): 无效；未来可能的多种控制域
协议(Protocol): 上层协议 (eg, PPP-LCP, IP, IPCP, etc)
信息(info): 上层协议分组数据
校验(check): CRC校验，用于差错检测
“数据透明传输”需求: 数据域必须允许包含标志模式<01111110>，如何判断此为数据还是flag？
使用字节填充
发送端: 在数据中的<01111110>和<01111101>字节前添加额外的字节<01111101> (“填充(stuffs)”)
接收端:
单个字节<01111101>表示一个填充字节；
连续两个字节<01111101>：丢弃第1个，第2个作为数据接收
单个字节<01111110>: 标志字节
在交换网络层数据之前，PPP数据链路两端必须：
配置PPP链路
学习/配置网络层信息
chap 07 无线网络
802.11无线局域网
802.11局域网组成
基站（访问点）AP
通常连接到有线网络
中继——负责在有线网络和其“区域”内的无线主机之间发送数据包
无线主机
可以是静止的(非移动的)或移动的
BSC基本服务集/单元
无线链路
通常用于连接移动设备到基站
与有线链路的区别
信号强度下降: 无线信号在通过物质(穿过空气/墙体)传播时发生衰减(路径损耗)
来自其他信号源的干扰: 由其他设备(如手机/蓝牙等)共享的标准化无线网络频率(如2.4 GHz)；机械设备(如发动机等)也会产生干扰
多路径传播: 无线信号的一部分受物体和地面反射，在发送方和接收方之间走了不同长度的路径，这使得接收方收到的信号变得模糊
无线链路的特性
信噪比与误码率
SNR: 信噪比(signal-to-noise ratio) 更大的信噪比-更容易从噪声中提取信号(“好事”)
信噪比与误码率的权衡
对于给定的物理层(调制方案)：增加功率->增加信噪比->减少误码率
对于给定的信噪比：具有较高的比特传输率（吞吐量）的调制技术将具有较高的误码率BER
BER是接收方收到的有差错传输比特的概率
无线链路传输的问题
隐藏终端
信号衰减
信道与AP关联
无线主机必须与某个AP关联
主动扫描
主机(H1)主动广播探测请求帧(Probe Request Frame)
AP发送探测响应帧(Probe Response Frame)
主机(H1)向选择的AP发送关联请求帧
AP向主机(H1)发送关联响应帧
被动扫描
各AP发送信标帧
主机(H1)向选择的AP发送关联请求帧
AP向主机(H1)发送关联响应帧
二者可以同时进行
802.11 MAC层
基本结构
DCF是必须实现的部分，PCF有更高的优先级，不必实现
DCF 子层在每一个结点使用 CSMA 机制的分布式接入算法，让各个站通过争用信道来获取发送权。因此 DCF 向上提供争用服务。
PCF 子层使用集中控制的接入算法把发送数据权轮流交给各个站从而避免了碰撞的产生
帧间间隔
所有的站在完成发送后，必须再等待一段很短的时间（继续监听）才能发送下一帧。这段时间的通称是帧间间隔 IFS (InterFrame Space)。
帧间间隔长度取决于该站欲发送的帧的类型。高优先级帧需要等待的时间较短，因此可优先获得发送权。
若低优先级帧还没来得及发送而其他站的高优先级帧已发送到媒体，则媒体变为忙态因而低优先级帧就只能再推迟发送了。这样就减少了发生碰撞的机会。
类型
SIFS，即短(Short)帧间间隔，是最短的帧间间隔，用来分隔开属于一次对话的各帧。一个站应当能够在这段时间内从发送方式切换到接收方式。
PIFS，即点协调功能帧间间隔，它比 SIFS 长，是为了在开始使用 PCF 方式时（在 PCF 方式下使用，没有争用）优先获得接入到媒体中。PIFS 的长度是 SIFS 加一个时隙(slot)长度。
DIFS，即分布协调功能帧间间隔（最长的 IFS），在 DCF 方式中用来发送数据帧和管理帧。DIFS 的长度比 PIFS 再增加一个时隙长度。
时隙的长度是这样确定的：在一个基本服务集 BSS 内当某个站在一个时隙开始时接入到媒体时，那么在下一个时隙开始时，其他站就都能检测出信道已转变为忙态。
当一个站检测到正在信道中传送的 MAC 帧首部的“持续时间”字段时，就调整自己的网络分配向量 NAV 。NAV 指出了必须经过多少时间才能完成数据帧的这次传输，才能使信道转入到空闲状态。
在源与目的通信的时间内信道处于忙状态，需要等待NAV时间后才能发送数据
802.11 的多路控制协议：CSMA/CA（Collision Avoid）
无线信道很难实现监听所有的冲突
所以CSMA/CA的目标是避免冲突
解决方法
允许发送端“预约”(reserve)信道，而不是随机发送数据帧，从而避免长数据帧的冲突
发送端首先利用CSMA向BS发送一个很短的RTS (request-to-send)帧
RTS帧可能冲突，但是很短
BS广播一个CTS(clear-to-send)帧作为对RTS的响应
CTS帧可以被所有结点接收
消除隐藏站影响
发送端可以发送数据帧
其他结点推迟发送
利用很小的预约帧彻底避免了数据帧冲突
802.11 帧结构
有四个地址，第四个地址只有桥接时才用到
地址1-地址3
地址2都是发送帧的的地址，地址3都是帧最终到达的地址
移动自组网和无线传感网
移动自组网络又称自组网络(ad hoc network)
自组网络是没有固定基础设施（即没有 AP）的无线局域网。这种网络由一些处于平等状态的移动站之间相互通信组成的临时网络
移动自组网络和移动 IP 并不相同
移动 IP 技术使漫游的主机可以用多种方式连接到因特网。
移动 IP 的核心网络功能仍然是基于在固定互联网中一直在使用的各种路由选择协议。
移动自组网络是将移动性扩展到无线领域中的自治系统，它具有自己特定的路由选择协议，并且可以不和因特网相连
几种不同的接入
固定接入(fixed access)——在作为网络用户期间，用户设置的地理位置保持不变。
移动接入(mobility access)——用户设置能够以车辆速度移动时进行网络通信。当发生切换时，通信仍然是连续的。
便携接入(portable access)——在受限的网络覆盖面积中，用户设备能够在以步行速度移动时进行网络通信，提供有限的切换能力。
游牧接入(nomadic access)——用户设备的地理位置至少在进行网络通信时保持不变。如用户设备移动了位置，则再次进行通信时可能还要寻找最佳的基站
无线个人区域网
WPAN：在个人工作地方把属于个人使用的电子设备用无线技术连接起来自组网络，不需要使用接入点 AP。
1. 蓝牙系统(Bluetooth)
2. 低速 WPAN
3. 高速 WPAN
无线城域网
WiMAX 常用来表示无线城域网 WMAN，这与Wi-Fi 常用来表示无线局域网 WLAN 相似
蜂窝移动通信网GSM
现在已经到达5G
基本组件
移动 IP
这种技术允许计算机移动到外地时，仍然保留其原来的 IP 地址。
移动 IP 要解决的问题，就是要使用户的移动性对上层的网络应用是透明的。
GSM的切换
移动用户在和一个基站相关联期间，会周期性地测量来自其当前基站及其邻近基站的信标信号强度，并将测量结果以每秒 1 ~ 2 次频率报告给当前基站。根据这些测量数据以及邻近蜂窝的当前负载情况，当前基站决定是否发起切换。 移动站的切换可能仍处在同一个 MSC 的控制下，而只是相关联的基站发生了变化。但在许多情况下，移动站的切换是相关联的 MSC 都改变了。在这种情况下，向移动站的呼叫路由会有很大的变化。