第一章 概述
1.1 Uses of Computer Networks（使用计算机网络 ）
计算机网络的定义
Computer network（计算机网络）: a collection of autonomous computers interconnected by a single technology. （一些互相连接的、自治的计算机的集合）
把分布在不同地点且具有独立功能的多个计算机系统通过通信设备和线路连接起来，在功能完善的网络软件和协议的管理下，以实现网络中资源共享为目标的系统。
一般不会让默写整个定义，需要重点关注加粗的内容
网络概念的三重含义
① 必须有两台或两台以上的具有独立功能的计算机系统相互连接起来，以达到共享资源为目的。
② 两台或两台以上的计算机连接，互相通信交换信息，必须有一条通道。这条通道的连接是物理的，由物理介质来实现。
③ 计算机系统之间的信息交换，必须有某种约定和规则，这就是协议。这些协议可以由硬件或软件来完成。
计算机网络和分布式系统的区别
给出例子要学会区分
主要是看在使用的时候关不关心底层的网络的架构，如果不关心是分布式系统，登陆的是某个节点，那就是计算机网络
business applications 远程服务器上如何调用服务器上的资源
分布式系统
只是一个模型或范型
通常在操作系统之上有一层软件负责实现这个模型，这个软件成为中间件（middleware）
分布式系统是建立在网络之上的软件系统，有高度的内聚性和透明性。
内聚性：每一个数据库分布节点高度自治，有本地数据库管理系统透明性：每个数据库分布节点对用户应用来说是透明的，用户感觉不到数据是分布的 Internet 是最著名的计算机网络，万维网是最著名的分布式系统，万维网（软件）运行于 Internet（硬件）上
P2P
P2P（Peer to Peer network）对等网络：对等网络又称工作组，网上各台计算机有相同的功能，无主从之分，一台计算机都是既可作为服务器，设定共享资源供网络中其他计算机所使用，又可以作为工作站，没有专用的服务器，也没有专用的工作站。对等网络是小型局域网常用的组网方式。
它的作用在于，减低以往网路传输中的节点，以降低资料遗失的风险。
- 每台设备既可以是服务器，也可以是客户机，关系对等（平等）
- 用户之间是Connected，主要用软件支持，如资源的定位，数据传递路径的确定等。每个节点需要有路由功能。
1.2 Network Hardware （网络硬件）
传输链路 广播式链路 点到点链路
常见的传输技术(链路)有两种，广播式链路（Broardcast Links）和点到点链路（Point-to-Point Links）
广播式链路（Broardcast Links）中，通信信道被网络上所有机器所共享。
一台机器发送的信息，会沿着通信信道传播，到达网络上其它机器（无线信号可能不能到达所有机器，带来了新的复杂性）。
总线网络使用硬件实现，环网络使用硬件+软件（桥功能）实现。
点到点链路（Point-to-Point Links）将一对单独的机器连接起来。可能中间经过一个或多个中间机器。直接相连的两个机器是点到点链路的最简单的形式。点到点链路的确定过程称为路由。
broadcasting、multicasting、unicasting
网络中常见的数据递交方式
- 单播(Unicast)：将数据发送给某个特定接收方的方式。
- 广播(Broadcast)：将数据发送给所有接收方的方式。
- 组播/多播(Multicast)：将数据发送给某些接收方的方式。
这些概念属于网络功能性的概念，与具体的网络拓扑有区别，是对网络抽象后封装的功能。
无论网络采用什么样的物理拓扑（广播网络或点到点网络），都可以支持以上的三种数据递交方式。
注意传输链路分类和数据递交方式分类的区别
LAN、MAN、WAN、Internet
Network Scale，网络尺度或网络规模，根据距离和接入网络的机器的数量等作为分类依据。
每年都考网络规模 需要记忆：几种规模的名字，根据例子判断属于哪种网络（一般不问Internet），记住例子
不同规模的网络采用的传输技术，最终的网络设计方案也会不同。
Scale | Type |
Vicinity | PAN (Personal Area Network) 个域网 |
Building | LAN (Local Area Network) 局域网 |
City | MAN (Metropolitan Area Network) 城域网 |
Country | WAN (Wide Area Network) 广域网 |
Planet | The Internet (network of all networks) |
1.2.1 PAN（个域网）
PAN是一个私有网络，通常是指连接用户的主设备和它的周边设备的网络。
例子1：连接电脑和无线鼠标、键盘、打印机等的无线网络；
例子2：手机和穿戴式设备（手表、手环、无线耳机）通过蓝牙组成的PAN
常用的PAN连接技术包括Bluetooth，RFID，红外，etc。
1.2.2 LAN（局域网）
局域网是一个私有网络，是由一个组织投资、设计、维护、使用的网络。Cisco公司给出的定义是没有使用通信部门的公共网络的网络。
规模一般覆盖一个办公室、一个楼层、一栋楼、几栋楼或一个校园 。校园网和企业网一般属于局域网。详细内容参见本书第4章。
常见的类型根据使用的传输技术的不同，分为共享式局域网和交换式局域网；或根据连接介质的不同，分为有线局域网和无线局域网。另外，通过添加标签和相应的处理软件，组织虚拟局域网等。
共享式局域网一般采用广播链路。
注意：链路是一个逻辑上的概念，可能包含一条或多条物理线路。指的是一个广播域，信号能够传递到网络上所有节点。分析环网的特点。
交换式局域网一般采用点到点链路。
是由交换设备连接的多条点到点链路。注意：交换式网络的重点在交换设备。
概念区分：
- 局域网主要是一种根据网络规模分类的类别。
- 共享式或交换式局域网主要依据网络设备区分。详见第四章网络设备部分。
许多有线局域网的拓扑结构是以点到点链路为基础的，俗称以太网的IEEE 802.3是迄今为止最常见的一种有线局域网。每台计算机按照以太网协议规定的方式运行，通过一条点到点链路链接到一个盒子，这个盒子称交换机（Switch），一台交换机有多个端口，每个端口连接一台计算机。交换机的工作是中继与之连接的计算机之间的数据包，根据数据包中的地址来确定这个数据包要发送给哪台计算机。
1.2.3 MAN（城域网）
MAN（Metropolitan Area Network）的范围覆盖一个城市。典型的例子为有线电视网。
初期的有线电视网只支持单向内容传播。现在的有线电视网可以支持双向数据传播（单人点播）。
1.2.4 WAN（广域网）
广域网包含互联网 广域网是一个复杂的概念，一个广域网可能包含多个广域网
WAN（Wide Area Network）的范围覆盖一个国家、地区或大陆（例：欧盟）。
Subnet（子网）是由ISP运营管理的骨干网络，用于连接不同城市或地区的网络。层次化特征。
通信子网由传输线路与交换节点组成。
- 传输线路（transmission line）负责在机器之间移动比特
- 交换元素（switching element）或简称为交换机（switch）是专用的计算机，负责连接两条或两条以上的传输线路。当数据到达一条入境（Incoming）线路时，交换元素必须选择一条出境（Outgoing）线路把数据转发出去。
这些负责交换的计算机现在成为路由器（router）
主要功能集中在交换节点。使用点到点链路传输技术。
此处与局域网是一个区别，广域网不会使用广播链路传输技术。
Internet服务提供商：Internet Service Provider (ISP)，面向公众提供Internet接入服务
子网经营者称为网络服务提供商：Network service provider(NSP) 是一家拥有、运营和销售互联网骨干基础设施和服务访问的公司。NSP 的主要客户是其他服务提供商，包括 ISP，而 ISP 又向企业和消费者销售 Internet 访问。
国内没有NSP
虚拟专用网络 VPN (Virtual Private Network)
1.2.5 互联网络
一组相互连接的网络称为互联网络（internetwork）或互联网（internet）
而全球范围内使用的因特网首字母要大写Internet
在互联网中，一个自治系统（autonomous system，AS)是一个有权自主地决定在本系统中应采用何种路由协议的小型单位。这个网络单位可以是一个简单的网络也可以是一个由一个或多个普通的网络管理员来控制的网络群体，它是一个单独的可管理的网络单元(例如一所大学，一个企业或者一个公司个体)。一个自治系统有时也被称为是一个路由选择域（routing domain）。一个自治系统将会分配一个全局的唯一的号码，有时我们把这个号码叫做自治系统号（ASN）。
1.3 Network Software （网络软件）
protocol、layer、interface、service
1.3.1 协议层次结构
为了降低网络设计的复杂性，绝大多数网络都组织成一个层次栈（a stack of layer）或分级栈（a stack of level），每一层都建立在其下一层的基础之上。层的个数、每一层的名字、每一层的内容以及每一层的功能各个网络不尽相同。每一层的目的是向上一层提供特定的服务，而把如何实现这些服务的细节对上一层加以屏蔽。从某种意义上讲，每一层都是一种虚拟机，它向上一层提供特定的服务。
其基本思想是一个特定的软件（或硬件）向其用户提供某种服务，但是将内部状态和算法的细节隐藏起来。
一台机器上的第n层与另一台机器上的第n层进行对话，该对话中使用的规则和约定统称为第n层协议。基本上，所谓协议（protocol）是指通信双方就如何进行通信的一种约定。
从计算机编程角度，为了完成某种功能，最基本的方式是“数据结构+算法”。数据结构是双方交互的内容，称为协议字段；运行在各个对等体上针对协议格式的处理操作集合称为协议算法。
不同机器上构成相应层次的实体称为对等体（peer）。
正是这些对等体为了实现彼此沟通才使用协议来进行通信。
实际上，数据并不是从一台机器的第n层直接传递到另一台机器的第n层。相反，每一层都将数据和控制信息传递给它的下一层，这样一直传递到最低层。第1层下面是物理介质（physical medium），通过它进行实际的通信。
在每一对相邻层次之间的是接口（interface）。
接口定义了下层向上层提供哪些原语操作和服务。（告诉上面的进程如何访问本层，规定了有哪些参数以及结果是什么，但并未说明过程和服务方式）
服务：是指下层为紧相邻的上层提供的功能调用，由一组原语（primitive）构成的正式说明，用户可以通过这些原语来访问该服务
层和协议的集合称为网络体系结构（network architecture）
1.3.2 层次设计问题
错误控制、流量控制
差错控制（Error Control）：是在数字通信中利用编码方法对传输中产生的差错进行控制，以提高数字消息传输的准确性。
流量控制（Flow Control）：是指在发送端和接收端之间的点对点通信量的控制。流量控制所要做的就是抑制发送端发送数据的速率，以便使接收端来的及接收。
拥塞控制（Congestion Control）：必须确保通信子网能够传送待传送的数据，是一个全局性的问题，涉及网络中所有的主机、路由器以及导致网络传输能力下降的所有因素。
1.3.3 面向连接服务与无连接服务
面向连接与无连接的服务
在计算机网络中，面向连接和无连接是两种不同的通信服务模式。
- 面向连接的服务（connection-oriented service）是按照电话系统建模的，服务用户首先必须建立一个连接，然后使用连接传输数据，最后释放连接，本质上像一个管道
- 无连接的服务（connectionless service）是按照邮政系统建模的，每一个报文都携带者完整的目的地址，每个报文都由系统中的中间节点路由，并且独立于后续的报文。
二者的区别在于：
- 面向连接的要求建立连接，因而没有传输的数据没有必要再标明传输的目的地址；而无连接的则对每个报文都由独立的目标地址。
- 一般来说，面向连接的可靠性较高，协议相对复杂，传输的数据按照发送顺序到达；而无连接的可靠性较差，协议相对简单，常出现乱序，重复和丢失现象。
可靠和不可靠的服务
可靠服务：从来不丢失数据的一种服务。一般情况下，可靠服务都要求接收方向发送方确认收到的每个报文
不可靠的服务：不会给发送方反馈任何确认消息，不保证数据不丢失
为什么要同时存在可靠服务与不可靠服务？
- 在给定的层次可靠通信并不总是可以使用的
- 为了提高可靠服务而导致的固有延迟可能是不可接受的
面向连接的服务是可靠的吗？
面向连接的服务只是在发送方和接收方之间建立连接，它并不能保证发送的数据流能准确无误的到达接收方。面向连接的服务同样可以分为可靠的面向连接服务和不可靠的面向连接服务。前者主要包括报文序列、字节流，后者如数字化语音。
1.3.4 服务原语 primitive
一个服务由一组原语正是说明，用户进程通过这些原语来访问该服务。
可用的原语取决于底层所提供的服务。
1.3.5 服务与协议的关系
服务与协议的关系
服务是指某一层向他上一层提供的一组原语。服务定义了该层准备代表其用户执行哪些操作，但是它并不涉及如何实现这些操作。服务与两层之间的接口有关，低层是服务提供者，而上层是服务用户。
与此不同的是，协议是一组规则，规定了同一层上对等实体之间所交换的数据包或者报文的格式和含义。对等实体利用协议来实现它们的服务定义，它们可以自由地改变协议，只要不改变呈现给它们用户的服务即可。
按照这种方式，服务和协议是完全相分离的，这是任何一个网络设计者应该很好理解的关键概念。
强调：
服务涉及层与层之间的接口
协议涉及不同机器上两个对等实体之间发送的数据包。
1.4 Reference Models （参考模型）
1.4.1 OSI参考模型
OSI参考模型
OSI参考模型本身不是一个网络体系结构，只是指明了网络分为几层和每层应该做些什么，没有定义详细的服务和实现服务所用的协议。
OSI模型分为七层，由低到高分别为：物理层，数据链路层，网络层，传输层，会话层，表示层，应用层。
名称 | 数据格式 | 功能 | 设备 |
物理层 | 二进制比特流 | 1) 相邻两节点之间，实现点到点的传输过程，2) 建立、维护和取消物理连接。 | 光纤、集线器、双绞线 |
数据链路层 | 数据帧 Frame | 保证相邻两节点之间的可靠传输，讲一个原始的传输设施转变成一条逻辑的传输线路。 | 交换机、网卡 |
网络层 | 数据包 Packet | 控制子网运行过程，确定传输路径。 | 路由器 |
传输层 | 数据段 Segment | 为网络层找到的路径提供可靠的传输。 | ㅤ |
会话层 | 数据 Data | 允许不同机器上的用户之间建立会话。 | ㅤ |
表示层 | 数据 Data | 关注所传递的信息的语法和语义，取消格式差异。 | ㅤ |
应用层 | 数据 Data | 包含各种各样的协议。 | ㅤ |
第n层的问题若无法完全解决，则需要依靠上一层。如物理层实现了点到点传输，而链路层使此传输变得可靠；网络层确定了传输路径，而传输层使此传输变得可靠。
1.4.2 TCP/IP参考模型
TCP/IP参考模型
TCP协议用在传输层，IP协议用在网络层。
TCP/IP协议划分了四层网络，自下而上分别为：
- 链路层：对应OSI参考模型中的物理层和数据链路层，负责监视数据在主机和网络之间的交换。该层主要有地址解析协议（ARP）工作。
事实上，TCP/IP本身并未定义该层的协议，而由参与互连的各网络使用自己的物理层和数据链路层协议，然后与TCP/IP的网络接入层进行连接。
- 互联网层：对应OSI参考模型中的网络层，解决主机到主机的通信问题。该层通过重新赋予主机一个IP地址来完成对主机的寻址，负责数据包在多种网络中的路由。该层主要有网际协议（IP）、互联网组管理协议（IGMP）和互联网控制报文协议（ICMP）在工作。
IGMP 是允许多个设备共享一个 IP 地址以便它们可以接收相同数据的协议，具体参见https://www.cloudflare.com/zh-cn/learning/network-layer/what-is-igmp/。ICMP 的主要目的是报告错误。当两个设备通过互联网连接时，ICMP 会生成错误以与发送设备共享，以防任何数据未到达其预期目的地。详见https://www.cloudflare.com/zh-cn/learning/ddos/glossary/internet-control-message-protocol-icmp/
- 传输层：对应 OSI 参考模型的传输层，为应用层实体提供端到端的通信功能，保证了数据包的顺序传送及数据的完整性。运行了 TCP 和 UDP。
- 应用层：对应OSI参考模型的高层。
数据链路层与传输层的区别：
①数据链路层是两个相邻节点之间的通信
②传输层是两个主机上的进程之间相互通信，叫做两个端点
1.6 网络标准化
802协议、网络标准化
802.11协议限定在OSI七层网络模型的最低两层——数据链路层和物理层。
IEEE 802协议簇是指IEEE标准中关于局域网（LAN）和城域网（MAN）的一系列标准。IEEE 802中定义的服务和协议限定在OSI七层网络模型的最低两层，即数据链路层和物理层。实际上，IEEE802又将OSI的数据链路层分成了两个子层，分别是逻辑链路控制（LLC，Logical Link Control）和介质访问控制（MAC，Media Access Control）。几种重要的802协议：
- 802.3：以太网介质访问控制协议（CSMA/CD）及物理层技术规范。
- 802.11：无线局域网的介质访问控制协议及物理层技术规范。
- 802.15：个域网协议（蓝牙、ZigBee）。
- 802.16：宽带无线网。
IEEE802协议簇由IEEE802标准委员会维护。其中最广泛应用的协议有以太网（802.3）和WLAN（802.11）。每一个工作组专注一个方向，每个工作组由数字编号，比如目前从802.1编到了802.24。
因此，802.11协议是IEEE802标准委员会下属的无线局域网工作组制定的无线局域网标准。
第二章 物理层
铜线、光纤、无线等的物理属性限制了网络的适用范围
使用模拟信号发送数字信号的过程叫做调制（modulation）
模拟信号是指用连续变化的物理表示的信息，其信号的幅度、频率、相位随时间连续变化。在变化范围内可以有任意的取值。
网络中常见的调制方式有调频、调相与调幅
数字信号由模拟信号经过离散化获得，时间离散，幅值离散，频率、相位离散。
所有自然中存在的都是模拟信号，数字信号需要以模拟信号为载体进行传输
物理层是参考模型的第1层，工作环境是相邻的两台设备。讲述比特作为信号在信道上递交时的协议，包括信号转换、信道使用等内容。
2.1 数据通信理论基础
信道的传输能力
bandwidth 带宽
信道的传输能力可以使用带宽和信道描述：
- 信道：用于传输信号的一个物理通道。可以是一个传输导线，也可以是一个频率范围，或几个传输导线的传输能力的复合。
信号在任何物理通道传输的过程中会有能量的损失，尤其是不同频率的信号损失程度不同。频率越高的信号损失能量越多。
给定一个传输介质，频率高的一些信号成分无法传输到接收方。（消耗完了）
- 带宽（Bandwidth）：在传输中不会明显减弱的频率的宽度，通常引用的带宽是指从0到使得接收能量保留一半的那个频率位置，是传输介质的一种物理属性。通常取决于介质的构成、厚度、电线或者光纤的长度。
滤波器（filter）可用来进一步限制信号的带宽
802.11无线信道允许使用的带宽约20MHz；
滤波技术（filtering）使得多个信号共享一段给定范围的频谱（某些信号的起始频率不等于0）；电视一个频道占6MHz
基带（baseband）信号：占用从0到某个最大频率的信号（信号范围0-）
通带（passband）信号：被搬移并占用更大频率范围的信号（信号范围-）；无线传输是通带信号。
电气工程：（模拟）带宽是可以通过信号的最大频率，以Hz度量；
计算机：（数字）带宽是一个信道传输最大速度数据速率（data rate），用bps（bits/s）来计量。
Hz是模拟带宽；bps是数字带宽
信号的频率
信号包含一种或多种频率成分（方波含有很多种频率成分）。
当信号在信道中传输时，高于信道截止频率的频率成分将由于能量衰减过多而不能通过信道。通过信道的只能是低于截止频率的成分。（低频部分描述信号概貌，高频部分描述信号细节。）
信号会发生变形，能否准确识别，依赖于通信双方的约定（信号发送设备和信号接收设备的）。通信双方需要根据能够传输过去的频率成分考虑合适的调制（编码）和解调制（解码），即什么样的信号对应什么样的比特（组合）。
Relation between data rate and harmonics.（约定：每一个周期信号表示8位，信道截止频率3000Hz）
基频：First harmonic=bps/8=1/T;
可以发送谐波数量：Harmonics sent = [3000/First harmonic]向下取整
波特率（Baud per second, Bps)：信道上每秒钟信号变化的次数；或信道上每秒钟传递的周期信号个数。
结论一：波特率的最大取值不大于信道带宽。因为波特率的取值等于所传周期信号一次谐波的频率值。
比特率（bit per second, bps）：信道上每秒钟发送或接收的比特位数（bit）。
结论二：bps=Bps*W，其中，W表示一个周期信号能够表达的信息位数。
在例子中，W=8。
推论一： 给定一个信道和一个周期信号能够表达的位数（给定了发送和接收设备，给定了识别算法），即给定了最大数据传输速率。
在例子中，最大数据传输速率为应该为24kbps
结论三：当波特率提高时，周期信号能够通过的谐波数减少，信号形状越来越难以识别，需要更好的识别算法。
Nyquist（奈奎斯特）采样定理
尼奎斯特定理 Nyquist（奈奎斯特）采样定理
用来表示一个有限带宽的无噪声信道的最大数据传输率。尼奎斯特定理用于计算理想情况下的最大数据传输速率，即在没有噪声干扰的情况下。根据尼奎斯特定理，信道的最大数据传输速率可以通过以下公式计算：
其中，Rmax 表示最大数据传输速率（单位为比特/秒），B 表示信道的带宽（单位为赫兹），V 表示信号的离散级数（即离散的幅度或相位级数）。
尼奎斯特定理告诉我们，通过增加信号的离散级数或者扩大信道的带宽，可以提高信道的最大数据传输速率。
例如，如果一个无噪音话音信道（3400 Hz），采用二进制信号传输，V=2，最大速率不能超过2×3400Hz=6800bps。若V = 16，最大速率则可提高到 27200=2*3400*4 bps。
信号的量化（quantization）和离散等级
不同的量化等级可以通过不同的电压电平来实现
假设滤波器带宽是B，理想状态下传输速率是？
香农定理
香农定理
用来表示有噪声信道的最大数据传输率或容量。香农定理用于计算在存在噪声干扰的情况下的最大数据传输速率。根据香农定理，最大数据传输速率可以通过以下公式计算：
其中，C 表示最大数据传输速率（单位为比特/秒），B 表示信道的带宽（单位为赫兹），S/N表示信号与噪声的比值（信噪比）。
带宽B实际上为一个信道支持的最大频率与最小频率的差值，即，信噪比的单位为dB
香农定理告诉我们，通过增加信道的带宽或提高信号与噪声的比值，可以提高信道的最大数据传输速率。
例如，模拟电话系统中，话音信道信噪比的典型值为 30dB（或者说因为1dB=10lgS/N，所以S/N=1000），那么最大数据传输速率为：C=3400×log2(1+1000)≈33888bps。
2.2 引导性传输介质
有导向的传输介质
2.2.1 磁介质 magnetic media
磁带、磁盘（移动硬盘），带宽大，传输成本低，但延迟大；几分钟到几小时；
例：光盘属于光介质
2.2.2 双绞线 twisted pair
双绞线是最常用的有线传输介质： 局域网内的网线（家用网线）, 电话线
- 双绞线是两根相互绝缘的铜线以螺旋形式绞在一起
- 绞在一起的电线产生的干扰信号相互抵消，降低辐射、减少干扰
- 信号通过两铜线之间的电压差传播，对外部噪声有更好的免疫力
- 外部噪声对两根平行的电线的影响是相同的，不会改变电压差
- CAT5 五类网线（基本淘汰）；CAT5E 超五类网线（家用常见），CAT6六类网线（家用常见），CAT6E超六类网线（公司内常见）
Full-duplex link （全双工链路，双向同时）
Half-duplex link（半双工链路，双向不同时）
Simplex link（单工链路，只有一个传输方向）
2.2.3 同轴电缆 coax cable
和双绞线相比，同轴电缆具有更好的屏蔽性和更大的带宽；因此有更长的传输距离和更高的传输速度。
同轴电缆的组成（从外到内）：铜芯，绝缘材料，编织外层导体，保护性塑料外壳
现在主要用于有线电视网络和计算机城域网
2.2.4 电力线 power line
优点：家庭内部电力线网络具有极大的便利性，
缺点：但数据传输性能差
- 高频信号在电线上有巨大的衰减
- 电气设备的开关产生很宽频率范围的电噪声
解决方法：采用抗频率损耗和突发错误的通信方案可以在家居电力线上达到不小于100Mbps的数据发送。
2.2.5 光纤 fiber coble
光纤通常用于长距离、高速的数据传输
- 骨干网使用光纤作为传输介质实现
- 高速局域网（FttH，光纤到户，大部分新住宅已经实现）
- 光纤传输系统由光源、传输介质（超薄玻璃纤维）和光探测器组成
- 电信号->发射光脉冲->传播->接收光脉冲->电信号
- 入射角度大于临界值的光在光纤内部反射可以长距离传输
- 多模光纤可以传输多个角度（多模）光束；单模光纤中的光线沿着一条直线传播（单模，类似波导guided wave）
- 光纤内折射>空气折射率（入射角<折射角）,通过全反射传播
光纤具有超高带宽（25000-30000GHz），低信号传输损失，因此可以长距离高速传输数据。
光纤通信中常用的三个波段：0.85微米，1.30微米和1.55微米
光缆的组成
高折射率玻璃芯（Core），低折射率硅玻璃包层，加强树脂涂层->光纤（光导纤维）
多根光纤捆扎成束，最外加塑料保护套
单模光纤
核心8-10um，光线沿直线传播
和激光结合进行远距离传输，例如超过100km，成本高
多模光纤
常见的光纤的主要形式
核心50um，光线沿折线传播
使用LED灯作为光源，成本低，适合短距离传输
2.5 数字调制与多路复用
一些基本概念（数据和信号）
数据(Data)：传递（携带）信息的实体，信息(Information)则是数据的内容或解释。
- 模拟(Analog)数据：指的是在某个区间产生的取值范围连续的变量或数值
- 数字(Digital)数据：指的是取值范围是离散的变量或者数值
信号(Signal)：数据的物理量编码（通常为电编码），数据以信号的形式传播。
- 模拟信号与数字信号
- 基带( Base band )信号 ：信源发出的没有经过调制（频谱搬移和变换）的原始电信号
- 宽带( Broadband )信号：将基带信号进行调制（频谱搬移和变换）后形成的模拟信号
数字调制：为了发送数字信息，必须用模拟信号来表示比特。比特与代表他们的信号的转换过程叫做数字调制。
多路复用：用单根线缆传送几个信号的信道共享形式叫做多路复用技术。
数据→信号→在介质上传输→信号→数据
通信系统的任务
把携带信息的数据用物理信号形式通过介质传送到目的地。
信息和数据（0、1比特）不能直接在介质上传输，需要经过数字调制转换成相应的模拟信号进行传输
信道（数字信道和模拟信道）
- 数字信道：以数字脉冲形式（离散信号）传输数据的信道。
数字信道只有高电平(1)和低电平(0)两种状态（在光纤中有光线代表1，无光纤代表0）
抗干扰能力强、无噪声积累；便于加密处理；便于存储、处理和交换；设备便于集成化、微型化；便于构成综合数字网和综合业务数字网；占用信道频带较宽
- 模拟信道：以连续模拟信号形式传输数据的信道。
模拟信道中的电平随时间连续变化，时具有周期性的正弦波，如固定电话。
趋势：通信网的初期，所有信道都是模拟信道，随着数字技术的发展，模拟信道正在被数字信道所代替。现在的骨干网基本是数字信道（光缆）。
信号（模拟信号和数字信号）
- 模拟信号：时间上连续，包含无穷多个值
- 数字信号：时间上离散，仅包含有限数目的预定值
编码
用一个编码符号代表一条信息或一串数据，叫做数据编码不同类型的信号在不同类型的信道上传输有4种组合，每一种相应地需要进行不同的编码处理。
信号的两种（调制）传输方式
- 基带传输（Baseband communication）：
把数据比特直接转换成信号，信号的传输占有传输介质上从零到最大值之间的全部频率，最大取决于信令速度（信号变化的速度），这是有线介质普遍使用的一种调制方式。
- 通带传输（Passband communication）：
信号占据了以载波信号频率为中心的一段频带，信号只能在给定的频带中传输；这是无线信道和光纤信道最常用的调制方式。
2.5.1 基带传输
考！！！
- 不归零制(NRZ，Non-Return to Zero)
二进制数字0、1分别用两种电平来表示。
常用－5V表示1，＋5V表示0。
缺点: 不具备自同步机制，必须使用外同步。
- 曼彻斯特编码(Manchester code)
用电压的变化表示0和1。
- 差分曼彻斯特编码(Differential Manchester code)
与曼彻斯特编码类似，区别在于码元开始时的跳变
曼彻斯特编码
规定在每个码元的中间发生跳变：
高 →低的跳变——1，低→高的跳变——0
∵ 每个码元中间都要发生跳变，接收端可将此变化提取出来作为同步信号，使接收端的时钟与发送设备的时钟保持一致。
∴ 曼彻斯特编码也称为自同步码（Self-Synchronizing Code）。它具有自同步机制，无需外同步信号。
缺点：需要双倍的传输带宽（即信号速率是数据速率的2倍）。
差分曼彻斯特编码(Differential Manchester code)
与曼彻斯特编码相同，在每个码元的中间，信号都会发生跳变；不同之处在于：
用在码元开始处有无跳变来表示0和1 ：
- 每个码元开始处有跳变——0
- 每个码元开始处无跳变——1
- 每个码元中间都有跳变（与曼彻斯特编码相同）
- 整个信号开头的第一个比特的编码按照曼彻斯特编码规则。
线路编码/Line codes
线路编码又称信道编码，其作用是消除或减少数字电信号中的直流和低频分量，以便在光纤中传输接收及监测
NRZ是最简单最直接的线路编码方式，但是实际上很少被使用（不可靠）
更加复杂的线路编码可以帮助通信系统提高带宽效率、时钟恢复和直流信号平衡
带宽效率
如何使用有限的带宽传递更多的数据：使用多个信号级别（离散等级）
时钟恢复
通信双方需要同样速率的时钟才能正确解析信号
当通信双方约定好编码方式时，如使用高电平表示1，低电平表示0。还需要约定信号的传输速率，如每秒钟传递1000个信号，则每位的时间长度为0.001秒。只有双方时钟完全一致，接收方才能正确识别解析为1000位。
但是，两台设备的时钟不可能完全一致，总存在误差。当数据传输速率较低且传输数据量较少时，这种误差可以忽略。否则，就会引起识别的错误。这种现象称为时钟漂移。曼彻斯特编码每位携带时钟信息，有利于时钟恢复。
要准确的解码，信号需要提供足够的状态变化（0变1，1变0）一长串的0或者1会存在时钟的恢复问题（时钟漂移），解决策略：
- 曼彻斯特编码
让时钟以2倍的比特率的速度运行
时钟信号和数据信号进行异或操作，在每个比特时间内发生一次跳变
需要两倍于NRZ码的带宽，带宽效率不高。
- 不归零逆转编码（NRZI，Non-Return-to-Zero Inverted）
用信号跳变表示1，信号不跳变表示0
解决了连续1的问题（每个1都会在NRZI中引入一个跳变）
连续0的问题仍然没有解决
- 4B/5B编码
每4个比特的数据（data）分成一组，根据转换表映射成5位比特的编码（code）
被选择的5位比特编码保证映射结果不会出现连续3个0
增加了25%的带宽开销（曼彻斯特编码增加了100%）
未使用的5位比特编码可用于物理层控制信号（11111线路空闲，11000开始）
- 扰频
在发送数据前使用扰频器（scrambler）产生伪随机序列，与数据进行异或操作
经过异或操作后数据接近伪随机序列。
接收端使用相同的伪随机序列进行异或操作恢复出原始数据。
优点：不增加带宽或时间开销；缺点：无法保证不出现长期状态不变的情况
平衡信号
平衡信号：在一段时间内，正电压与负电压一样多的信号。均值为0，能够避免直流信号。
平衡信号（无直流分量）的优点
- 直流分量在信道上有剧烈的衰减
- 电容耦合只允许交流部分通过，传输直流信号浪费能量
双极编码（一种平衡码）
- 用+1V和-1V表示逻辑1，0V表示逻辑0，
- 发送1时，发射器在+1V和-1V两个电平之间选择，达到信号平衡。
- 在电话里网络中被称为交替标记逆转（AMI，Alternative Mark Inversion）
2.5.2 通带传输
基本原理：用数字信号对载波的不同参量进行调制
载波 S(t) = A cos (wt+j)
S(t)的参量包括： 幅度A、频率w 、相位j 调制就是要使这三个参量随数字基带信号的变化而变化
幅移键控ASK(Amplitude Shift Keying)
不同的振幅来表示0或1
两个或更多的幅值等级可以表示更多的符号
频移键控FSK(Frequency Shift Keying)，调频
相移键控PSK(Phase Shift Keying) ，调相
BPSK（二进制相移键控）在每个符号周期内把载波波形改变0或180度
BPSK的Binary指的是两个符号，而不是每个符号代表2比特（1个符号1比特）
QPSK（正交相移键控）包括4中相位偏移（45，135，225，315度）
数据率 = 信号速率 x
M：调制级数
Question: QPSK一个符号应该代表几个比特？ Answer: 2bits
混合调制模式
调制模式可以综合使用，使得每个符号传输更多比特
振幅和相位可以结合起来一起调制
- QAM-16，QAM-64 （正交振幅调制）
QAM-16每个符号传输4个比特
QAM-64每个符号传输6个比特
- 正交振幅调制和相移键控可以用星座图表示
频率和相位不能同时调制
- 频率是相位随时间的变化率，相位调制会影响频率的计算
星座图 Constellation diagrams
格雷码
任意两个相邻的代码只有一位二进制数不同
- 使用自然二进制编码，两个相邻转态的错误判断会产生多位错误（0111-1000）
- 使用格雷码，相邻状态的错误只会产生一位错误，数据的错误率
复用（FDM；WDM；TDM）
2.5.3 频分复用 FDM
频分复用
原理：整个传输频带被划分为若干个频率通道，每个用户占用一个频率通道。频率通道之间留有防护频带。
多路复用中每个信道所分配的带宽大于通信实际需要的带宽，多出的频带叫做保护带（guard band），使信道之间完全隔离
NB 即使有保护带，因为滤波器是非理想的，相邻信道间仍然可能存在重叠
正交频分复用
OFDM是实现复杂度最低，应用最广的多载波传输方案。
不存在保护带，将信道分成若干正交的子信道，提高利用率
每个子载波在相邻子载波的中心频率上的响应为0，因此可以在子载波的中心频率上采样而不受到邻居的干扰
2.5.4 波分复用 WDM
原理：整个波长频带被划分为若干个波长范围，每个用户占用一个波长范围来进行传输。
2.5.5 时分复用 TDM
原理：把时间分割成小的时间片，每个时间片分为若干个通道（时隙） ，每个用户按照固定的安排，轮流占用一个通道传输数据。
时分复用要求输入流时间上必须同步，为了适应时钟的微小变化，增加保护时间（guard time）间隔。
常用在语音电话网络和蜂窝网络
Statistics TDM：STDM（统计时分复用）
- TDM的缺点：某用户无数据发送，其他用户也不能占用该通道，将会造成带宽浪费。
- 改进：统计时分多路复用（STDM），用户不固定占用某个通道，有空槽就将数据放入。
2.5.6 码分复用 CDMA
码分多址（Code Division Multiple Access): CDMA中的用户根据自己分配到的特有的码片序列发送信息
- 1是发送分配到的码片序列，0是发送码片序列的反码
- 不同用户之间的码片序列两两正交（内积为0）
- 接收到混合信号后，用户使用自己的码片进行内积操作
- 发送1时，解码得到m（码片长度），发送-1，解码得到-m
2.6 公共电话交换网络 PSTN
Modem的调制方式（调幅；调频）
PSTN（Public Switched Telephone Network）作为早期用户接入互联网的主要方式，包含了现代网络中的一些主要思想和概念。三网（电信网，计算机网络，电视网）融合促进了电信部门同时支持电话业务和数据业务。
2.6.1 电话系统结构
电话系统的三个主要部分：
- 本地回路（家庭和公司的模拟双绞线）
- 中继线（连接交换局的数字光纤）
- 交换局（电话呼叫从这里从一条中继线接入到另一条中继线）
通过设置不同层次的交换局，避免全连接
特点：线路减少；按需连接；分布式保存、逐级呼叫，检索效率高；多条可选路径，灵活度高。
2.6.3 本地回路 Local loop（调制解调器、ADSL和光纤）
传统双线电话线路上传递模拟信号。
本地回路关注如何使用模拟信号尽可能快速的传递数据，主要设备是调制解调器（modem）。
调制是将数据转换为模拟信号，解调是将模拟信号转换为数据。
最初使用设备是电话调制解调器
之后调制解调器先是被ADSL取代，
此后在一些地方被光调制解调器取代（光猫）。
调制解调器可以内置到电脑中（电话调制解调器）或使用单独的盒子（DSL调制解调器和有线电视调制解调器）
电话调制解调器
电话调制解调器使用电话的4k带宽，所以电话和数据传输不能同时进行。
第一代使用2400个符号（采样信号），通过调整每个符号能够表达的数据位数不断提高数据传输速率。
第二代使用8k个符号（采样信号）。理论上可以达到很高的数据传输速率，但是由于香农定理的限制，极限值为35k或70kbps。
电话调制解调器将数字信号转化为模拟信号在模拟线路上传输
- 两端都存在本地回路的速度33.6kbps（调制解调器发送速率2400Hz，每个符号传递14个数据比特）
- 如果只有一端存在本地回路，理论上最大传输速率70kbps(信噪比提高)
- 实际使用的modem是56kbps
由尼奎斯特定理决定的： 电话系统内的电话信道运载的是数字样本值。每个电话信道 4000 Hz 宽，包括保护带在内。因此重构信号所需要的采样应该亥是每秒 8000次。在美国每个样本值为8比特，其中一比特用于控制目的，所以每个用户数据能获得 56 000 bps的数据速率。在欧洲，全部的8比特样本值都供用户使用，因此他们能使用 64 000 bps 的调制解调器，但国际协议标准选择了56 000。
数字用户线 Digital Subscriber Line
xDSL或DSL是所有基于数字用户线服务的统称；
ADSL（Asymmetric DSL）非对称数字用户线
ADSL
电话线带宽限制是由于引入了300-3400Hz的滤波器（通常引用为4000)
使用本地回路的所有1.1MHz频谱
频谱被分成256条独立信道：信道0用于简单老式电话服务（POTS, Plain Old Telephone Service），1-5空闲防止语音和数据干扰，1条用于上行控制，1条用于下行控制，其余用于传输用户数据。
一般80-90%带宽用于下行（用户下载数据量远大于上传）
ADSL：8M/1M；ADSL2：12M/1M；ADSL2+：24M（距离端局较近的良好线路上的最快速度，实际无法达到, 为什么？）
实际情况：1M/256K; 4M/1M; 8M/2M
非对称用户数字线路，采用FDM将线路带宽划分为多个信道，其中大部分用于下行数据（下载数据），小部分用于上行数据（上传数据），保留单独的语音信道，并使用几个信道隔离数据信道和语音信道，避免相互之间的干扰。
ADSL连接通常由两个设备组成：ADSL调制解调器和路由器。ADSL调制解调器连接到电话线路，将数据转换成适合在电话线上传输的信号，并且从电话线路接收数据，并将其转换回原始数据格式。路由器连接到ADSL调制解调器，并将数据分发给网络中的其他设备。
DSL宽带（Broadband）通过本地回路向电话公司的端局发送数据
电话和计算机通过分离器（splitter,是一个模拟滤波器）连到同一条电话线
根据不同的服务（adsl，adsl2，adsl2+）、与端局的距离，网速不同
住户处需要一个网络接口设备（NID，Network Interface Device）接口外是公共网络
NID和splitter只能由专业技术人员安装，产生高昂的上门费用
FttH光纤到户
光纤到户将本地回路升级为光纤，使用光信号传递数据。每大约100个用户的光纤通过分离器/组合器复合到一根到端局的光纤上，用户之间通过时分多路复用使用到端局的光纤。
- 一个波长的 被所有住户共享用于下行数据传输，另一个波长被所有住户共享用于上行数据传
- 多个用户使用时分复用的方式共享光纤带宽
- 光纤是是无源的（PON，Passive Optical Network），例如没有信号放大器
2.6.4 中继线和多路复用
干线（中继线）
中继线是电话系统中的骨干线路，用于连接不同层次的交换局，使用数字信号传输。现在的中继线一般为光纤，能够同时支持多路电话呼叫，采用的主要技术是多路复用技术。
时分多路复用 TDM
语音呼叫以电信号的形式在公共电话交换网的中继线上传播
基于PCM的TDM每125us为每路电话发送一个样本值（64kbps=88k）
T1载波包含24个语音信道，每125us每个信道发送8比特
每帧包含192比特（248）外加一个控制比特，总数据传输率1.544Mbps
第193比特使用扩展超帧的方法发送同步信号（中文版120最后一段）
波分多路复用 WDM
波分多路复用（ Wavelength Division Multiplexing ，WDM）是一种频分复用的形式，用于光纤上多个信号的传播，例如
- 每条光纤传输信号的能量位于不同的波长处
- 在combiner出汇合到一条共享光纤上
- 接收端splitter再分成多条光纤
- 每条光纤的filter为每个光纤过滤掉不需要的波长
- WDM是极高频率上的复用，是对光纤信道的描述，与电子FDM的区别是光纤复用系统是无源的（衍射光线），可靠性高
2.6.5 交换
电路交换、分组交换、报文交换三种交换方式的比较
电话系统分为局外部分（本地回路和中继线，因为位于交换局外部）和局内部分（交换机）。
交换局内主要设备是交换机（交换节点），交换机连接多条线路，主要功能是把一条入境线路上来的呼叫交换到一条出境线路上。从而支持呼叫一直到接收方。
电路（虚电路）交换 circuit switching
电路交换是一种面向连接的工作方式。分为三步：使用前建立一条从发送方到接收方的路径；使用这条路径传输；传输完毕释放路径。
交换设备在通信双方找出一条实际的物理线路的过程。(最早的电路交换连接是由电话接线员通过插塞建立的，现在则由计算机化的程控交换机实现。原始的电路交换要占用整条线路，现代的虚电路通过复用技术只使用一个子信道)
特点：数据传输前需要建立一条端到端的通路。
呼叫——建立连接——传输——挂断
缺点：
- 建立连接的时间长
- 一旦建立连接就独占线路，线路利用率低
- 无纠错机制
优点：
- 建立连接后，传输延迟小
数据包交换（分组交换） packet switching
包（分组）交换是一种非连接的工作方式。数据被分为多个包（分组），每个包包含完整的目的地址。每个包经过交换节点时，交换节点按照当前网络状况（交换表）为其选择一条输出线路。此过程一直持续直到包被传送到目的地。
将报文划分为若干个大小相等的分组(Packet)进行存储转发。
优点：
1）存储量要求较小，可以用内存来缓冲分组——速度快；
2）转发延时小——适用于交互式通信；
3）某个分组出错仅重发该分组——效率高；
4）各分组可通过不同路径传输，可靠性高。
特点：
1）数据传输前不需要建立一条端到端的通路。
2）有强大的纠错机制、流量控制和路由选择功能。
两种交换技术的主要区别
电路交换有固定的线路，包交换没有固定路径。
包交换对于数据包的大小规定了严格的上限，没有用户长时间霸占线路；
延迟和拥塞产生位置不同：
- 包交换在交换局等待转发产生排队延时，拥塞来自转发数据包不及时；
- 电路交换拥塞发生在建立电路阶段（例如打电话时遇到占线忙音无法使用线路）
数据包交换不会浪费带宽，电路交换有可能浪费带宽
数据包交换比电路交换容错性更好：某个交换机出现故障，所有使用它的电路都被终止；数据包交换则可以绕过故障交换机。
二者收费方式不同：电路交换按照距离和时间收费（例如长途电话）；数据包交换流量是主要因素：ISP对用户包月收费，骨干网运营商则按照流量大小收取区域网络费用
报文交换（message switching）
报文交换中交换结点也采用存储转发方式。但报文交换对报文的大小没有限制，因此要求交换结点需要有较大的缓存空间。
三种数据交换方式的时延计算
（13年考研35题）
主机甲通过1个路由器（存储转发方式）与主机乙互联，两段链路的数据传输速率均为10Mbps，主机甲分别采用报文交换和分组大小为10kb的分组交换向主机乙发送1个大小为8Mb（1M=10^6）的报文。若忽略链路传播延迟、分组头开销和分组拆装时间，则两种交换方式完成该报文传输所需的总时间分别为
A. 800ms、1600ms B.801ms、1600ms
C. 1600ms、800ms D.1600ms、801ms
【解答】选D。
不进行分组时，发送一个报文的时延是8Mb/10Mbps=800ms，在接收端接收此报文件的时延也是800ms，共计1600ms。进行分组后，发送一个报文的时延是10kb/10Mbps=1ms，接收一个报文的时延也是1ms，但是在发送第二个报文时，第一个报文已经开始接收。共计有800个分组，总时间为801ms。
【考查知识点】本题考查报文交换和分组交换技术发送时延的计算。
第三层 数据链路层
3.1.2 成帧
成帧（位填充、字节填充）
成帧的主要工作是将每一段来自上层的数据封装起来，使得数据链路层的接收方实体能够正确识别一个帧的开始和结束（能够确定帧的边界），并能依据帧中携带的各种控制字段（额外添加的协议字段）判断所接收帧的正确性（是否在传输过程中出错、是否是想要的那一帧）。
确定帧的边界有一些基本的要求：容易识别一个帧的开始和结束（出错时容易同步）；开销尽可能少。
字节计数法 Byte count
利用头部中的一个字段来标识该帧中的字符数。当目的节点的数据链路层收到字节计数值时就知道后面跟随的字节数，从而可以确定帧结束的位置。
- 这种方法比较简单，知道字符数就知道该帧在何时结束
- 但是计数值出错之后，接收方就找不到下一帧正确的起始位置，很难重新同步
- 错误之后无法要求重传（接收方不知道从哪里开始错误）
- 这种方法很少被使用
问题：如果计数字段出错，即失去了帧边界划分的依据，接收方就无法判断所传输帧的结束位和下一帧的开始位，收发双方将失去同步，从而造成灾难性的后果。
字节填充的标志字节法 Byte stuffing
使用一些特定的字符来界定一帧的开始与结束。发送方的数据链路层在数据中“偶尔”出现的每个标识字节的前面插入一个特殊的转义字节（ESC）
接收方的数据链路层在将数据传递给网络层之前必须删除转义字节，这种技术成为字节填充。
这种方法更长，但更容易在错误后重新同步
比特填充的标志比特法 Bit stuffing
使用一个特定的比特模式，即
01111110来标志一帧的开始和结束。为了不使信息位中出现比特流
01111110被误判为帧的首尾标志，发送方的数据链路层在信息位中遇到5个连续的1时，将自动在其后插入一个0；而接收方做该过程的逆操作，即收到5个连续的1时，则自动删除后面紧跟的0，以恢复原信息。问题：采用比特填充和字节填充两种方法时，一帧的长度要取决于它所携带的数据内容。
物理层编码违例法（曼彻斯特编码）
物理层编码中有一些编码形式（Code）不会出现在常规数据中（编码违禁）
使用编码违禁来区分帧的边界
例如：4B/5B编码中有25-24=16个编码在数据编码中不会被使用
这些分界符是保留不用的，可以用来区分帧的边界，不需要填充
3.2 差错检测和纠正
错误检测和纠正（CRC）
校验和checksum：通信双方为了对传输的数据进行检错和纠错而根据一定的规则添加的额外的位（组合）
在数据链路层，接收方实体需要判断接收的帧是否在传输过程中出现了错误。如果没有传输错误，则将帧中包含的分组提交给网络层。否则，需要发送方重传这一帧。
帧的数据取值可能没有任何特征，这时需要添加额外的位来凑出某种或某几种特征，通过检验特征是否存在来判断数据传输是否正确。
最简单的检验和是奇偶检验。
在数据之外增加一位，这一位的目的就是将原有数据加上增加的这一位具有某种明显的特征。如“数据+校验位”中“1”的个数是奇数个（偶数个）。
发送方发送帧时，根据原来数据中1的个数决定校验位的取值。
以1位偶校验为例。“数据+校验和”中“1”的个数为偶数个。这就是约定的特征。
接收方收到帧后，检查“数据+校验和”中“1”的个数是否为偶数个。是，则认为帧传递正确。不是，则认为传输过程出现了错误，需要重传。
校验和的开销体现在额外增加的位的多少、位的位置和校验位生成和检查的算法的复杂性。校验位的多少影响线路使用的效率，校验算法的复杂性影响数据发送和接收的处理速率。总的来说，会影响真正数据传输的速率（或传输线路的利用率）。
校验和的复杂性需要平衡“校验通过则数据传输正确”的支持和开销两个方面的因素。
如果让“校验通过则数据传输正确”这个结论100%正确，需要的开销可能很大。一般支持这个结论到一个可以接受的置信度就可。
几个相关概念和工作机制：
重传：当某一帧在传输过程中出现错误时，网络中常用的处理方法是发送方重传这一帧，而不是接收方使用纠错算法纠正错误。
重传对发送方有资源要求，即保存自己所发送过的帧，需要时重新发送一次。只有当一帧被接收方正确接收并将帧中分组提交给网络层后，才认为这一帧的传递任务结束，才能清空保存这一帧的缓冲区。
一个分布式协议观点：通信双方组成一个分布式系统，只有当双方都认为一帧传递正确后，协议才认为这一帧的传递结束。校验和只是让接收方判断是否接收正确。
确认：接收方对自己所接收正确的帧回复一个确认，使得接收方也能知道这一帧已经被正确传输。
有了确认机制后，发送方如果收到一帧的确认，则认为这一帧已经被正确传递，并且接收方也这样认为（否则不会发回确认），这一帧的传递结束。清空这一帧所使用的资源。
如果发送方没有收到一帧的确认，则需要重传这一帧。
重传定时器：为了避免发送方长时间地等待确认，根据线路延迟等要素估计一个确认能够返回的时间，设置为重传定时器。当等待时间超过这个时间时，则认为确认无法回来，重发这一帧。
在定时器超时时一帧的确认没有回来，发送方只能认为接收方没有发回确认，也只能推断接收方没有收到正确的这一帧。所以选择重传这一帧。
但是，情况并不完全是这样。确认没有回来有可能是确认在传输过程中出错丢失了。重传会造成接收方收到重复的帧。（这是由于分布式系统中每个实体只能使用局部的部分的信息做出判断和操作）。
编号：为每个传递的帧确定一个编号，从而区别不同的帧。
当接收方收到一个已经接收过的编号的帧时，则认为是重复帧，直接丢弃这一帧，但要回复一个这一帧的确认（因为接收方在等待这一帧的确认）。
3.2.1 纠错码（海明码/汉明码）
（n，m）码，一个长为n的帧，包含m个数据位，r个校验位
r=n-m; 线性码中校验位是数据位的线性函数计算得到（常用异或=模2加法）
n位码字（codeword），码率=m/n
海明距离（Hamming distance)
两个codeword中不同的位的个数称为海明距离
一个编码方式的海明距离是两个合法编码之间最小的海明距离
检测d个错误需要d+1的海明距离，纠正d个错误需要2d+1的海明距离
海明码设计
海明码可以纠正1位的错误
每个合法的消息对应n个单个错误的码字，（n+1）2m<=2n
海明码需要的校验位r的计算（m+r+1）<=2r，例：如果m=7，r=4
校验位在2^k(k=0,1,2,..,r-1)
将数据的位置转化成二进制码。例如，1->1, 2->10, 3->11, 4->100,…,
校验位1（20）覆盖所有数据位置序号的二进制码最后一位是1的数据，例如，1（1），11（3），101（5），111（7），1001(9)，1011(11)
校验位2（21）覆盖所有数据位置需要的二进制码倒数第二位是1的数据，例如，10(2), 11(3), 110(6), 111(7), 1010(10), 1011(11)
以此类推（4=22，8=23，16=24。。。），若采用偶校验，则校验位所控制的数据位的和是偶数，校验位为0，奇数为1（等同于异或和模2加法）
海明码
配奇原则
1的个数为偶数：1，奇数：0
3.2.2 检错码
奇偶检错码
奇偶（parity）检验是在数据末尾添加表示奇（1）偶（0）的检验位
偶校验：所有数据位相加模2，相当于异或
例如： 1110000->11100001
当数据位的和与奇偶校验位不相符，表明出现了错误
可以检测奇数个错误
Ex: 1 error, 11100101; detected, sum is wrong
Ex: 3 errors, 11011001; detected sum is wrong
Ex: 2 errors, 11101101; not detected, sum is right!
Error can also be in the parity bit itself
Random errors are detected with probability ½
交错（interleaving）校验可以检测突发连续错误（burst）
循环冗余码 CRC
基本思想：把要传输的数据信息当作一个报文码多项式f(x)的系数，发送时用一个标准的生成多项式G(x)来除f(x) ，将所除得余式R(x)的系数附加在报文码之后发出；接收时用同一生成多项式G(x)来除收到的码字多项式，能除尽说明传输正确，否则说明有错。
实现：用简单的移位寄存器电路即可。
每年都考，必会，简单！
G(x)为r次的生成多项式，k个信息码元的码多项式为f(x)，n=k+r
3.3 基本数据链路层协议 Elementary Data Link Protocols
基本数据链路协议（停等协议）
3.3.1 Link layer environment (数据链路层环境)
数据链路层一般在网络接口卡和操作系统驱动部分实现；网络层（IP）的实现一般是操作系统软件
网络层、数据链路层和物理层都是独立的进程
硬件实现：
物理层的功能实现驻留在网络接口卡中，主要功能包括按照一定速率将数据转换为信号发送出去和将接收到的信号转换为数据。
数据链路层的功能实现部分分布在网卡中，部分分布在操作系统中。网卡中的数据链路层功能主要包括对发送的数据生成校验和，对接收的数据检查校验和。
网卡上发送和接收的数据都存放在一个缓冲区中，由网卡上的物理层和数据链路层进程使用。
软件实现：
数据链路层的部分功能（本章关心的协议内容）在操作系统中实现，主要包括可靠性和高效性所涉及的各种功能。如重传、确认、编号、流量控制、流水等。
网络层的功能也在操作系统中实现。
操作系统中发送和接收的数据都存放在操作系统管理的缓冲区中，由位于操作系统中的数据链路层和网络层进程使用。
应用层有单独的缓冲区。数据需要在应用层缓冲区和操作系统缓冲区交换数据。
将网卡上实现的功能并列在一起，统称为物理层。
将位于操作系统中的这一部分数据链路层功能称为数据链路层。这是我们学习的重点，我们关心这一部分功能的协议实现。
所以，数据链路层协议不再关心校验和的生成和检查的具体实现。而是使用一种事件方式提供网卡操作的结果。当发送数据时，我们简单的发给物理层即可。接收数据时，可能有两个可能的结果，即收到一个通过校验的帧（from_physical_layer），或收到一个没有通过校验的帧（cksum_err）。
Group | Library Function | Description |
Network layer | from_network_layer(&packet)
to_network_layer(&packet)
enable_network_layer()
disable_network_layer() | 从网络层获得一个将要发送的数据包
把一个刚接收到的数据包传给网络层
允许网络层工作（产生“ready”事件）
阻止网络层产生“ready”事件 |
Physical layer | from_physical_layer(&frame)
to_physical_layer(&frame) | 从物理层接收一帧数据
把一帧发送数据传递给物理层 |
Events & timers | wait_for_event(&event)
start_timer(seq_nr)
stop_timer(seq_nr)
start_ack_timer()
stop_ack_timer() | 等待一个事件（数据包/帧到达、计时事件）
对帧（seq_nr）开始(重置)一个倒计时timer
停止帧（seq_nr）的倒计时timer
开始（或重置）ACK 的倒计时 timer
停止ACK的 倒计时 timer |
3.3.2 Utopian Simplex Protocol （乌托邦单工协议）
假设没有错误，接收方和发送方一样快，考虑单向数据传输
无约束单工协议
工作在理想情况，几个前提：
- 单工传输
- 发送方无休止工作（要发送的信息无限多）
- 接收方无休止工作（缓冲区无限大）
- 通信线路（信道）不损坏或丢失信息帧
工作过程
- 发送程序:取数据，构成帧，发送帧；
- 接收程序：等待，接收帧，送数据给高层
3.3.3 Stop-and-Wait Protocol for Error-free channel （无错误信道的停-等单工协议）
确保发送方不能超过接收方：
接收器在准备就绪时返回一个dummy frame（哑帧ack）
所谓的dummy帧就像EVA中的Dummy Plug一样，只是用来告诉sender可以发送下一个帧了，不需要做任何事情。
一次只输出一帧，称为stop and wait
我们添加了流控制
单工停等协议（A Simplex Stop-and-Wait Protocol）
- 增加约束条件：接收方不能无休止接收。
- 解决办法：接收方每收到一个帧后，给发送方回送一个响应。
工作过程
- 发送程序：取数据，成帧，发送帧，等待响应帧；
- 接收程序：等待，接收帧，送数据给高层，回送响应帧。
3.3.4 Stop-and-Wait Protocol for Noisy channel （有噪声信道的单工停-等协议）
增加约束条件：信道（线路）有差错，信息帧可能损坏或丢失。
解决办法：出错重传。
- 带来的问题：
- 什么时候重传 —— 定时
- 响应帧损坏怎么办（重复帧）—— 发送帧头中放入序号
- 为了使帧头精简，序号取多少位 —— 1位
- 发方在发下一个帧之前等待一个肯定确认的协议叫做PAR（Positive Acknowledgement with Retransmission）或ARQ（Automatic Repeat reQuest）
- 该协议增加了一个计时器，发送方发出一帧，接收方只有在正确接收到数据之后才返回一个确认帧。如果到达接收方的是一个已经损坏的帧则将它丢弃，经过一段时间后发送方将超时，于是它再次发送该帧。这个过程将不断重复，直至该帧完好无损地到达接收方。
- 发送方在它所发送的每个帧的头部放上一个序号，然后，接收方可以检查它所接收到的序号，由此判断这个帧是新帧还是应该被丢弃的重复帧。
- 如果到达了一个有效确认帧，则发送方从它的网络层获取下一个数据包，并把它放入缓冲区覆盖掉原来的包，同时他还会递增帧的序号。如果到达了一个受损的确认帧，或者计时器超时，则缓冲区和序号都不作任何改变，以便重传原来的帧。
- 当一个有效帧到达接收方时，接收方首先检查它的序号，确定是否为重复数据包。如果不是，则接收该数据包并将它传递至网络层，然后生成一个确认帧。重复帧和受损帧都不会被传递给网络层，但它们的到来会导致最后一个正确接收到的数据帧的确认被重复发送，返回给发送方，以便发送方做出前进到下一帧或重发那个受损帧的决策。
这个协议能够实现重传，是因为：
- 如果拿到正确帧，相安无事
- 如果拿到校验和错误，啥也干不了，等超时
- 如果拿到超时（或者说上一种情况的超时），最终会自动超时重传
停-等协议的问题在于：只能有一个没有被ACK的帧在发送中，这样会导致发送方的带宽利用率很低。
为什么buffer不是越大越好？答案是，大buffer会带来更高的延迟。
3.4 滑动窗口协议
滑动窗口协议工作原理：
发送窗口、接收窗口
发送端
滑动窗口中的窗口指的是协议关心的内容，滑动指的是关心的内容在不断变化。
发送的信息帧都有一个序号，从0到某个最大值，0 ~ - 1，一般用n个二进制位表示0；
发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小 = 上界 - 下界，大小可变；
发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1；
接收端
接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示能够接收的序号最大的帧，下界表示希望接收的帧。
接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应（确认）帧，上界、下界都加1。接收窗口大小不变。
一个基本要求：数据链路层协议必须按照发送的顺序递交所有的帧给网络层。
滑动窗口协议具体实现说明：
滑动窗口协议的实现本质上是一组针对缓冲区管理的协议。发送方和接收方都有一个（组）用于发送的和接收的缓冲区。发送缓冲区里面存放的是已经发送但没有收到确认的帧；接收缓冲区用于存放能够接收的帧。
发送窗口尺寸大小对应着发送缓冲区的使用情况，接收窗口尺寸大小对应着能够用于接收的缓冲区的个数。
发送窗口尺寸大小可以为0—MAX（MAX为能够使用的发送缓冲区的最大个数）；接收窗口尺寸大小固定。
发送缓冲区和接收缓冲区都组织成循环队列。
缓冲区的大小和帧所使用的编号（位数）没有直接关系。（一般缓冲区<最大编号）
捎带确认
捎带确认带来的复杂性：
捎带/载答（piggybacking）：暂时延迟待发确认，以便附加在下一个待发数据帧的技术。 也就是说将下一个数据帧的 ack 设置为上一帧的 ack，有效利用 ack 的位置。 优点：充分利用信道带宽，减少帧的数目意味着减少“帧到达”中断； 带来的问题：复杂。
如果是双工通信，则每台机器都维护一个发送窗口和接收窗口反应当前的发送情况和接收情况。一台机器的发送窗口和对方机器的接收窗口逻辑上是一个方向的通信。
当一台机器有数据要发送时，帧中除了携带本次发送数据的编号、数据以外（与发送窗口有关），还需要携带本机作为接收方接收对方数据的情况（确认已接收的帧，捎带确认，与接收窗口有关）
当接收方没有及时的返回数据，对已经接收的数据帧的确认不能及时返回，可能会造成数据帧的超时重传。解决方案是设定一个确认定时器（ack_timer），当收到第一帧时启动确认定时器，如果在确认定时器超时时依然没有返回的数据帧，则产生返回一个单独的确认帧。
确认定时器的设定规则是保证最早接收的帧的确认能够在其重传定时器超时之前返回。
多个缓冲区（窗口尺寸大于1）协议机制
当有多个发送缓冲区时（发送窗口尺寸大于1）支持流水发送，即可以在没有收到确认的情况下连续发送多帧，这些帧保存在缓冲区中，每帧对应一个重传定时器。
捎带确认可能一次确认多个帧，此时发送窗口下沿连续滑动，直到第一个没有收到确认的帧；发送缓冲区将收到确认的帧所在的缓冲区清空（具体实现时可以被新的数据覆盖）。
当有多个接收缓冲区时（接收窗口尺寸大于1）支持乱序接收，即当前期望的帧没有到来（由于噪声出错）时，可以接收后面到来的传输正确的帧，放到相应的接收缓冲区内。但是，此时不能向网络层递交（按序要求）。当期望接收的帧到达后一起递交。
如果当前期望的帧没有到来，则启动否定确认机制，及时索要此帧，避免后面正确接收的帧触发超时重传。
滑动窗口协议概念
发送端维护的窗口内是它发送出但还未被确认的帧
- Needs to buffer them for possible retransmission
- Window advances with next acknowledgements
接收端维护的窗口内是它（预期）将要接收的帧
- Needs to keep buffer space for arrivals
- Window advances with in-order arrivals
更大的窗口可以实现管道化 （pipelining）的数据传输从而提高链接的效率
- Stop-and-wait (w=1) is inefficient for long links
- Best window (w) depends on bandwidth-delay (BD)
- Want w ≥ 2BD+1 to ensure high link utilization
BD（单向信道可以同时容纳帧的数量：带宽*传输时间/一帧的比特数），“1”要完整接收一个帧之后才会发送确认帧）
管道化的数据传输需要不同的错误/缓存机制的选择
- We will consider Go-Back-N（回退N） and Selective Repeat（选择性重传）
3.4.1 一位滑动窗口协议
一位滑动窗口协议
发送窗口大小为1，1个发送缓冲区接收窗口大小为1，1个接收缓冲区
Transfers data in both directions with stop-and-wait （窗口大小为1）
- Piggybacks 把确认信息捎带在acks on reverse data frames for efficiency
（捎带确认）
- 需要解决传输错误，流量控制 early timers
一位滑动窗口协议的两种情况:
Simultaneous start [right] causes correct but slow operation compared to normal [left] due to duplicate transmissions.
- 左侧过程：
A 发送（0,1，A0），0 是 seq 的初始值，1 是对前一帧的 ack（或者初始值），A0 为数据，B 接收到后发送（0,0，B0），0 是 B 的 seq 的初始值，第二个 0 表示对 A0 的 seq=0 的 ack，B0 是数据，如此往复。
- 右侧过程：
A 和 B 都试图发送，A 先发送（0,1，A0），B 发送（0,1，B0）二者 seq 以及 ack 都应该是初始值，B 接收到后发现 A 的 ack=1，与自己发的（0,1，B0）的 seq 不一样，重传（0,0，B0），表示收到了 seq=0 的 A0，同样 A 也会重传（0,0，A0）表示收到了 seq=0 的 B0，也就是说，最终的结果相当于消息体 A0、B0 与 ack 消息被分开传输了。
3.4.2 回退N协议 Go-Back-N, GBN
回退N
接收端必须按照顺序接收（窗口是1）
- 发现错误或者丢失帧，将所有后续帧都丢弃
- 发送端对应的帧超时，重传所有超时帧（发生错误及其之后的帧）
- 接收窗口长度是1
发送窗口大小大于1，多个发送缓冲区接收窗口大小为1，1个接收缓冲区
Tradeoff made for Go-Back-N（回传方式设计的优缺点）:
- Simple strategy for receiver; needs only 1 frame
- Wastes link bandwidth for errors with large windows; entire window is retransmitted
逻辑上每一个未被确认的帧都单独需要一个计时器
使用链表的形式模拟多个计时器（滴答计数器）
例如，我如果扔了个
A B C D出去，过段时间回了带有正确ACK的，那什么都好说；如果我拿到的ACK，A，B与D正确，但C有问题，那我要从C开始重发，D就算白发了，也要重新来。本质上，这意味着接收窗口的window size是1。
3.4.3 选择性重传协议
选择性重发协议
发送窗口大小大于1，多个发送缓冲区接收窗口大小大于1，多个接收缓冲区
接收端可以接受在接收窗口中任意序号的帧（窗口大）
任意顺序接收：只要在接收窗口范围内的帧都可以接收
累计确认：当发送端收到第n帧的确认，（若n-1，n-2，。。确认未收到），它之前的帧也会被自动确认
NAK：接收方检测到某一帧错误，发送NAK要求发送方重传这一帧
N.B.: 帧的接收和确认是两个概念：在选择重传中帧的接收可以无顺序，但帧的确认必须有顺序（否则累计确认无法使用？）
Tradeoff made for Selective Repeat: （优缺点）
- More complex than Go-Back-N due to buffering at receiver and multiple timers at sender
- More efficient use of link bandwidth as only lost frames are resent (with low error rates)
为了保证传输的正确性（避免相邻的window里有相同的序号）可能的序号数量（MAX_Seq+1）最少是window尺寸的2倍
显然，Go Back N协议的缺点在于，如果有一个帧出错，那么后面的帧即使正确也要重发。
因此一个改进的措施就是只重发出错的帧，这就是选择性重传协议。为了实现这一点，改进的本质是增大了接收窗口的大小，使得接收方可以缓存多个帧。比如，让发送窗口的大小和接收窗口大小一致。一般来说，这个尺寸是。
一切如常的情况和上面一样，就不说了；如果出错，后面的帧该ACK还是ACK，直到出错帧timeout，sender重传这单个帧。
关键在于，只要窗口在，怎么接收都可以。但是出错帧会导致窗口不能向后滑动，窗口后面正确发的帧会被缓存。
例题：数据链路层采用了后退 N 帧（GBN）协议，发送方已经发送了编号为 0～7 的帧。当计时器超时时，若发送方只收到 0、2、3 号帧的确认，则发送方需要重发的帧数是（ ）。
A. 2 B. 3 C. 4 D. 5
【答案】C
【解析】确认机制是累计确认的 ，如果发送方收到了 3 号帧的确认，则说明 0、1、2、3 号帧都已经发送成功， 所以只需要重发 4、5、6、7 号帧即可。
第四章 介质访问子层
Media Access Control Sublayer (介质访问控制子层)：
负责决定谁在多路访问链路上发送下一个消息
链路层的重要组成部分，特别是对于局域网
局域网特别是无线局域网中MAC非常重要，因为无线信道是广播信道
广播信道也称为多路访问信道（multiaccess channel）或者随机访问信道（random access channel）
介质访问控制（MAC）：用于在多路访问信道问题上确定下一个使用者的问题。
4.1 信道分配问题
静态和动态信道分配
4.1.1 静态信道分配
在有N个用户的静态信道：
使用FDM，TDM，CDMA等多路复用的方式将带宽分配成N等分
静态的信道分配使每个用户获得固定的信道
静态信道分配是低效的：
- 分配给一些用户的信道有时候没有被使用
- 在静态信道分配中，如果有的用户不再使用信道，信道也不能被其他用户使用
静态信道分配（FDM,TDM）方式不适用于突发流量，需要动态分配信道的协议实现
4.1.2 动态信道分配模型的假设
- 流量独立 Independent traffic：N 个独立的站（计算机、电话）组成，每个站独立产生流量；帧的到达是独立的
- 单信道假设 Single channel：所有站共享同一信道，可发送可接收
- 冲突可观察假设 Observable collisions：如果两帧 “同时传输”（传输时间有重叠），会产生信号重叠造成信号混乱、不可识别，称为 “冲突”。冲突使所有传输失败，除了冲突产生错误，不会再有其他错误。所有站都可以检测到冲突的发生。而且发生冲突需要重新传输。
- 时间连续或分槽（离散）Continuous or slotted time：如果时间连续，则在任何时刻可以开始传输数据；如果时间离散，则只能在某个时间槽的起始点开始传输。
- 载波侦听或不侦听 Carrier sense：侦听判断当前信道是否空闲，一个站在试图使用信道之前知道该信道是否被使用。
动态信道分配模型根据用户的需求分配信道
4.2 多路访问协议
4.2.1 ALOHA
ALOHA
pure ALOHA（纯 ALOHA）
先说后听
基本思想：在纯ALOHA（纯ALOHA）中，用户只要有数据就发送帧；用户在随机冲突时间后重试
在低负载下高效低延迟
当其他用户在两倍于帧时间的易受攻击时段进行传输时，就会发生冲突
将发送器同步到插槽可以减少冲突
分槽 ALOHA
将时间分成离散的间隔（时间槽），每个时间槽对应一帧。
用户要遵守统一的时间槽边界。
系统中有一个特殊的站在每个间隔起始时刻发出一个脉冲信号。
用户需要等待下一个时间槽开始时刻发送数据。
易受冲突期减少了一半。
分槽ALOHA的效率是纯ALOHA的两倍
- 低负载会浪费插槽，高负载会导致碰撞
- 随机流量模型的效率高达1/e（37%）
4.2.2 CSMA（载波侦听多路访问协议）
先听后说
检测其他站点，调整自己的动作
CSMA
1-Persistence CSMA
① 当一个站有数据要发送时先侦听信道
② 若信道空闲，立即发送数据
③ 若信道忙，持续监听等待直至信道变为空闲
④ 若发生冲突，等待随机时间，返回步骤 1
1-persistence 代表出现信道空闲，传输数据的概率为 1
如果 2 个以上的站在某个站传输数据过程中准备好了数据，在空闲到来时会产生冲突
若传输延迟大，第一个站的信号没有到达第二个站时，后者认为信道是空闲的，发送数据导致冲突（带宽延迟积越大，越严重）
Non-Persistence CSMA
① 当一个站有数据要发送时先侦听信道
② 若信道空闲，立即发送数据
③ 若信道忙，不持续监听，等待一个随机时间返回步骤 1
④ 若发生冲突，等待随机时间，返回步骤 1
与 1-Persisitence CSMA 相比，Non-persistence CSMA 的信道利用率更好（冲突发生概率低），但延迟更大（更多的随机等待）
P-Persistence CSMA
p-Persistence 适用于分时间槽的信道
① 当一个站有数据要发送时先侦听信道
② 若发现信道空闲，在下一个时间槽到达时，以 p 的概率发送数据，有 q=1-p 的概率，将发送推迟到下一个时间槽
③ 在新的时间槽如果还是空闲，依然以 p 的概率发送数据，q 的概率推迟。
④ 以上过程一直重复直到发出，或有其他站发送数据，随即等待一段时间，重复以上步骤
p-Persistence 的 p 越小，信道利用率越高，但带来的延迟也越大
p=1 时与 1-Persistence CSMA 等价，但是 p=0 时不与 Non-Persistence CSMA 等价
CSMA/CD （Carrier Sense Multiple Access with Collision Detection，带冲突检测的载波侦听多路访问）
边听边说
两个站都侦听到信道为空，并且开始传输。信号会产生冲突
每个站检测到发生冲突后立即停止传输帧，并发送一个拥塞信号，通过二进制指数后退算法确定等待时间后重新开始监听信道。
站的硬件在传输时监听信道，读回的信号不同于发送的信号说明发生了冲突。
当一个站传输了 2𝝉 的时间后可以确定不会发生冲突了（ 𝝉 是网络中两个最远站点之间数据传输需要的时间）
也就是说所有站点都发现信道被占用
考虑到信号传输的延迟，最开始发的时候会有还没接收到信号的站点认为信道空闲
2𝝉 的时间是传输与回传的时间
所以我们可以让发送的帧足够大，传到以太网最远端时仍在发送。（我们可以计算出最小帧长）
CSMA/CD的发送流程可以概括为：
- 先听后发
- 边听边发
- 冲突停止
- 延迟重发
CSMA/CD 控制方式的优点是：
原理比较简单，技术上易实现，网络中各工作站处于平等地位 ，不需集中控制，不提供优先级控制。但在网络负载增大时，发送时间增长，发送效率急剧下降
CSMA/CD 跟非坚持的 CSMA 区别在于听与说的关系，非坚持的 CSMA 发送时也会有传输延迟的问题，但并不会管是否发生了冲突，若一定时间内没有收到确认，则尝试重发即可。CSMA/CD 监听到冲突后会立即停止重发。
4.2.3 无冲突协议
无冲突的解决方案各站点遵守事先确定的竞争规则，合理安排各个站发送数据的顺序，不会产生冲突。包括以下几个协议：
基本位图法 Bitmap
在一个竞争周期内，如果某个站有数据发送，则当其对应的时槽到来时置 1，错过则等待下一个竞争周期。竞争周期结束后，时槽置 1 的站轮流发送数据。 需要事先安排各个站的编号及对应的竞争时槽。
基本位图协议：
如果发送方有数据，则在争用时隙中设置一个位
发件人依次发送；每个人都知道谁有数据
高位的站预期的等待时间低于低位的站
令牌传递
所有站组成一个逻辑环，令牌按照某种方向在逻辑环上传递。获得令牌的站拥有发送数据的权力。发送完毕后，将令牌向后传递到下一个站。需要事先安排逻辑环上各个站的顺序。
带有令牌的站点可以在通过前发送一帧
Idea也可以在没有响铃的情况下使用，例如token bus
为了阻止帧进入无限的循环，接收站或者发送站要把数据从循环中取下
所有站的预期等待时间相同
二进制倒计数：
每个站拥有一个逻辑地址，发送时各个站按位从高到低广播自己的逻辑地址。信道将所有地址位布尔或（只要有一个/多个1，结果就是1）在一起。每个站将自己的地址位与布尔或后的位比较，自己地址位小的竞争失败并放弃发送后续的地址位。最终剩余的站竞争成功并随后发送数据。需要事先安排站的逻辑地址。
站在竞争时隙中发送其地址（log N位而不是N位）
Medium ORs bits; 当电台发送“0”但看到“1”时，就会放弃
看到其完整地址的站将在旁边发送
基于冲突的解决方案没有实现约定的竞争顺序，各个站公平地竞争信道。此时，冲突不可避免。协议基于冲突解决各个站的发送顺序。这是本书的重点，经典以太网采用了这种解决思路。
有限竞争协议综合以上两种协议特点，将所有站分成若干个组，组内公平竞争（基于冲突），组间按照一定顺序竞争（无冲突）。常见的有限竞争协议为自适应树遍历协议。
无线局域网拥有不同于有线局域网的特点，冲突检测困难，信道侦听复杂，采用了类似于经典以太网但冲突避免的协议。
4.2.4 有限竞争协议
如何在一个广播网络中获取信道，我们已经考虑了两种基本策略：一种是竞争的方法，如同CSMA 的做法那样；另一种是无竞争协议。
每一种都可以用两个重要性能指标来衡量：低负载下的延迟，以及高负载下的信道利用率。
在负载较轻的情况下，竞争方法（即纯ALOHA 或者分槽ALOHA）更为理想，因为它的延迟较短（冲突很少发生）。随着负载的增加，竞争方法变得越来越缺乏吸引力，因为信道仲裁所需要的开销变得越来越大。
而对于无冲突协议，则结论刚好相反。在低负载情况下，它们有相对高的延迟，但是随着负载的增加，信道的效率反而得到提高（因为开销是固定的）。
显然，如果我们能够把竞争协议和无冲突协议的优势结合起来，那就太好了。这样得到的新协议在低负载下来用竞争的做法而提供较短的延迟，但在高负载下来用无冲突技术，从而获得良好的信道效率。我们把这样的协议称为有限竞争协议（limited-contention protocol）
由上图可以看出，只要减少参与竞争的站数量，则站获得信道的概率就会增加。有限竞争协议正是这样做的。
把站进行分组，保证每个分组里每次只有少部分的站想要发送数据（降低站内冲突）
避免闲置周期和冲突造成的信道浪费
4.2.5 无线局域网协议
MACA 冲突避免多路访问（Multiple Access with Collision Avoidance)
与有线相比，无线电传输范围有限，导致它具有复杂性。
节点可能具有不同的覆盖区域，导致隐藏和暴露终端问题
节点无法检测到冲突，即在发送时进行感应，使碰撞变得昂贵且需要避免
下图中无线电的覆盖范围是这样的：A和B都在对方的范围内，可能潜在地相互之间有干扰： C也可能潜在地干扰到B和D，但不会干扰A。
隐藏站和暴露站问题
隐藏终端是无法相互感知但仍在预期接收器处发生碰撞的发送器
暴露终端是可以相互感知但仍然安全传输（到不同的接收器）的发送器
无线局域网在传输数据时会产生隐藏终端问题和暴露终端问题
【隐藏终端】站A正在给站B发送数据，C监听信道，它什么也监听不到，从而得出错误的结论：现在可以给B发送数据了。
【暴露终端】站B给站A传输数据，此时站C想给站D传输数据，站C侦听介质，则它会听到一个传输正在进行，从而得出错误的结论：C不能给D传输数据。
MACA 的基本思想是发送方剌激接收方输出一个短帧，以便其附近的站能检测到该次传输，从而避免在接下去进行的（较大）数据帧传输中也发送数据。这项技术被用来替代载波侦听。
具体例子：A如何向B发送一帧？
A首先发送给B一个RTS（request to send），这个短帧包含了随后将要发送的数据帧的长度；然后，B用一个CTS（clear to send）作为应答，此CTS 帧也包含了数据长度（从RTS帧中复制过来）。A在收到了 CTS帧之后便开始传输。
C落在A 的范围内，但不在B 的范围内。因此，它听到了A发出的RTS，但是没有听到B发出的CTS，只要它没有干扰CTS，那么在数据帧传送过程中，它可以自由地发送任何信息。
相反， D落在B的范围内，但不在A 的范围内。它听不到RTS帧，但是听到了 CTS 帧。只要听到了 CTS 帧，这意味着它与一个将要接收数据帧的站离得很近；所以，它就延缓发送任何信息直到那个帧如期传送完毕。
E听到了这两条控制消息，与D一样在数据帧完成之前它必须保持安静。
4.3 以太网
4.3.1 经典以太网
经典以太网是最重要的一种局域网模式，通常工作在10Mbps。所有站点共享同一个传输介质（信道），采用基带(什么是基带？)传输信号，采用广播传输技术，即每个站将自己发送的数据通过收发器发送到传输介质上，信号占用信道所有带宽，信号沿传输介质传递到每个站点。当两个或多个站同时传输信号，则会发生信号叠加，造成接收方接收失败。所有传输都会失败。
经典以太网每个时刻只允许一个站点发送数据。没有事先规定的竞争顺序，允许竞争时产生冲突，并基于冲突解决介质访问控制问题。
经典以太网出现过程
a)Ethernet的核心技术是CSMA/CD介质访问控制方法；
b)随机争用技术起源于夏威夷大学校园网ALOHA；
c)1972年，Xerox[zieroks]公司开始Ethernet实验网的研究；
d)1979年，Xerox公司宣布了Ethernet产品；
e)1980年，Xerox、DEC与Intel联合宣布Ethernet V2.0规范 ；
f)20世纪90年代，10Base-T标准使得Ethernet性能价格比大大提高；
g)目前，交换式Ethernet与最高速率为10Gb/s的高速Ethernet的出现，更确立了它在局域网中的主流地位。
经典以太网– 物理层
一根 shared coaxial（共享的同轴电缆），所有主机都连接到该电缆上
- 传输速率最高10Mpbs，使用曼彻斯特编码
- 所有主机运行经典以太网协议来接入网络
- 19世纪物理学家认为ether是一种假想的电磁波传输媒介
- 最初科学家认为信息可以以电磁波的形式沿同轴电缆传播
曼彻斯特编码
曼彻斯特编码、差分曼彻斯特编码
4.3.2 经典以太网MAC子层协议
经典以太网的MAC子层协议最早使用1-persistent CSMA/CD
- 当发生冲突后，使用二进制指数后退（BEB）算法决定随机等待的时间
- 经典以太网的帧结构被仍然在现代以太网中使用
- Preamble：8个字节的先导码，每个字节的比特模式10101010，最后一个字节10101011，作为帧的定界符（SOF）
- 目标地址第一位为0对应普通地址，第一位是1代表组地址（组播），全1的特殊地址广播
- 源地址具有全球唯一性：前三个字节是组织唯一标识符（制造商），每个制造商224个地址
- 数据字段最多包含1500个字节，最小帧长64字节（区分有效帧和垃圾数据）
- Pad用来填充小于46字节的数据字段，校验和使用32位CRC
a)前导码与帧前定界符字段
前导码：7个字节，10101010…101010比特序列。
帧前定界符：1字节，10101011。
b)目的地址和源地址字段
地址字段长度：2个字节或6个字节 。
目的地址类型：
单一结点地址（unicast address）第一位0；
多点地址（multicast address）第一位1；
广播地址（broadcast address）全1。
以太网（本书中）最大帧长和最小帧长（不包括前导码）
4.3.3 以太网中MAC层协议对竞争和冲突的处理思路
想说就说
按照对时间管理的不同，分为连续时间和离散时间，对应的协议分别为：纯ALOHA，分槽ALOHA
纯ALOHA协议：当站点有数据要发送时就发送。如果多个用户同时发送则会发生冲突造成发送失败。发送失败后（发送站会依靠某种方法得知），等待一段随机时间再次发送。等待一段随机时间为了有效解决冲突。
分槽ALOHA协议：是纯ALOHA协议的改进。将时间离散化，分为时间槽（一段事先规定的时间）。只有在时间槽的起始点可以发送。通过推迟发送时间（未准备好的被推迟到下一个时间槽），避免连续时间发送带来的某些冲突。
先听后说
为了不打扰已有的通信，站点在发送数据之前首先侦听信道。如果信道空闲，则发送；如果信道忙，代表有其它站点在发送数据，则不能发送，等待一段随机时间发送。
这种发送数据之前先侦听信道是否空闲的协议称为载波侦听多路访问协议（CSMA，Carrier Sense Multiple Access）。根据贪婪程度和处理策略不同，分为：
- 1-坚持CSMA
- 1-坚持CSMA只是将连续时间上的冲突压缩到前一个数据传递完毕（一个时刻）。
1-坚持CSMA：站点在发送数据之前首先侦听信道。如果信道空闲，则发送；如果信道忙，则继续侦听，直到信道空闲，立即发送。
1-坚持CSMA协议避免打扰已有的通信，但是不能完全避免冲突。
假如现在站点A正在发送数据，站点B想要发送数据，先侦听信道，信道忙，则站点B持续侦听信道。接着（或“同时”）站点C也有数据要发送，执行同样的协议。当站点A发送完毕后，站点B和C都侦听到信道空闲，都会选择立即发送。结果，站点B和C发送数据冲突，都会发送失败。
- 非坚持CSMA
非坚持CSMA：站点在发送数据之前首先侦听信道。如果信道空闲，则发送；如果信道忙，则等待一段随机时间再来侦听。
非坚持CSMA协议不再在信道忙时坚持侦听信道，而是等待一段随机时间再来侦听。能够有效避免1-坚持CSMA协议不能真正分解冲突的问题。
非坚持CSMA协议在提高整个系统吞吐量（系统在单位时间内能够真正完成的数据传输次数）的同时，可能会带来较大的延迟（对每一次数据传输而言）
- p-坚持CSMA
p-坚持CSMA：适用于时间分槽系统。站点在发送数据之前首先侦听信道。如果信道空闲，则以概率p发送数据；以概率1-p推迟到下一个时槽；重复以上过程，直到发送出去或听到信道忙。如果信道忙，则等待一段随机时间再来重复以上协议。
p-坚持CSMA协议可以有效分解潜在的可能的冲突。由于每个站点都运行这个协议，选择了不同的发送时间槽，两个或多个站同时选择一个时间槽的概率随着p的变小而降低。
可以提高吞吐量，但可能带来更大的延迟。
边说边听
先听后说（CSMA）协议要求所有有数据发送的站点侦听到信道空闲时才能发送数据，从而不会打扰已有的通信过程，但是不能完全避免冲突（不能保证站点发送一定成功，或成功获得信道的使用权），尤其是当多个站点同时侦听到信道空闲。
当两个帧发生冲突时，两个被损坏帧继续传送毫无意义，而且信道无法被其他站点使用，对于有限的信道来讲，这是很大的浪费。如果站点边发送边监听，并在监听到冲突之后立即停止发送，可以提高信道的利用率，因此产生了CSMA/CD。
边说边听的实现机制：发送方一边向信道发送（说）数据，一边从信道上读取（听）数据，通过判断双方是否一致来判断是否发生了冲突。
边说边听：所有站点还要同时运行冲突检测（CD, Collision Detection）协议，边发送数据（竞争信号）边检测信道上是否发生了冲突。如果听到冲突，则表明还有其它站点“同时”发送数据，代表本次发送失败（所有发送站点都会意识到这一点）。听到冲突的站点立即停止发送（提高效率），等待一段随机时间后再次运行CSMA/CD。
如果站点在发送过程中没有听到冲突，则认为本次发送成功（或取得总线的控制权）。
二进制指数后退
二进制指数后退算法
站点运行CSMA/CD协议，听到冲突后进入竞争周期，时间离散为多个时间槽。如果第一次冲突，则参与竞争的站点在随后的两个时间槽内随机选择一个发送，发送前依然要侦听信道空闲。排在最前面的只有一个竞争者的时间槽对应的竞争者竞争成功，随后抓住信道发送数据，其它竞争者等到选择的竞争时间槽时侦听信道为忙，只能等待已有通信完成再次参与竞争。
当一个时间槽有两个竞争者都会听到冲突，全部竞争失败。竞争失败的站点将随机等待的时间槽数加倍，然后从中随机选择一个参与竞争，直到竞争成功或达到最大竞争次数。
二进制指数后退指的是每次冲突后随即后退的时间槽翻倍，直到1024（0~1023）个时间槽，此时运行了16次依然解决不了冲突，则认为网络坏了。
竞争周期时间槽的时间应该远远小于普通帧长。这样能够减少冲突带来的消耗，提高信道使用效率。
对每一个站点，选择任何一个时间槽都是公平的。因为一个时间槽的好坏不只是取决于是否靠前，更重要的是是否其它竞争者也选择了这个时间槽（博弈论）。
竞争周期的最后结果是某一个站点获得信道使用权。
最小帧长
最小帧长
一个站点执行CSMA/CD协议，当发送（竞争）过程中没有听到冲突，则认为发送（竞争）成功。
考虑到信道传输延迟时，这个结论需要前提条件保证才是正确的。
发送方必须发送足够长时间的数据，才能够检测到发生在“远方”的冲突，从而做出正确的判断。
本质是一个分布式系统，每个站点只能依据自己周围的是否有信号叠加（ “局部信息” ）来推断整个信道上是否有冲突（ “全局结论” ）。或依据自己周围是否空闲来推断整个信道是否空闲。
由图可知，站 A 在发送帧后至多经过时间 2𝝉 （端到端传播时延的 2 倍）就能知道所发送的帧有没有发生碰撞（当 时）。因此把以太网端到端往返时间 2T 称为争用期（又称冲突窗口或碰撞窗口）。每个站在自己发送数据之后的一小段时间内，存在发生碰撞的可能性，只有经过争用期这段时间还未检测到碰撞时，才能确定这次发送不会发生碰撞。
为了确保发送站在发送数据的同时能检测到可能存在的碰撞，需要在发送完帧之前就能收到自发送出去的数据，即帧的传输时延至少要两倍于信号在总线中的传播时延，所以 CSMA / CD 总线网中的所有数据帧都必须要大于一个最小帧长。任何站点收到帧长小于最小帧长的帧时，就把它当作无效帧立即丢弃。最小帧长的计算公式为
最小帧长＝总线传播时延 × 数据传输速率 ×2
例如，以太网规定取 为争用期的长度。对于 10Mb/s 的以太网，在争用期内可发送 512bit，即 64B。在以太网发送数据时，如果前 64B 未发生冲突，那么后续数据也就不会发生冲突（表示已成功抢占信道）。换句话说，如果发生冲突，那么就一定在前 64B。由于一旦检测到冲突就立即停止发送，因此这时发送出去的数据一定小于 64B。因此，以太网规定最短帧长为 64B，凡长度小于 64B 的帧都是由于冲突而异常中止的无效帧，收到这种无效帧时应立即丢弃。
如果只发送小于 64B 的帧，如 40B 的帧，那么需要在 MAC 子层中于数据字段的后面加入一个整数字节的填充字段，以保证以太网的 MAC 帧的长度不小于 64B。
例如：
4.3.4 经典以太网的传输效率
4.4 无线局域网
无线局域网对应的标准为IEEE 802.11，也称为WiFi。
无线局域网工作在无需授权许可的ISM（Industrial Scientific and Medical）频段上，易受其它电气设备干扰。
网络分为两种模式：带有接入点AP（Access Point）或基站（base station）的网络（有架构模式），和没有接入点的网络（ad hoc）（自组织模式）两种工作模式。
4.4.1 802.11 体系结构和协议栈
带有接入点的网络模式（有架构模式）中任意两个站点通信通过AP(Access Point 接入点)。隐含的假设为：所有站点都应该在AP的信号覆盖范围内，所有站点的信号范围能够覆盖AP。发送方首先将数据发送给AP，AP将数据再转发给接收方。AP之间通过有线连接。
ad hoc network（自组织网络）模式中任意两个站点可以直接通信。属于自组织网络。当AP不再作为网络内部任意两个站点通信的转发站点，只作为外部站点的代理时，AP和网内其它站点也组织为ad hoc网络模式。
无线局域网只使用一个信道，支持广播传输模式。
形式上类似于经典以太网，那么经典以太网的介质访问控制协议CSMA/CD是否能够直接应用于无线局域网？
无线和有线局域网的区别：无线局域网的站点的信号可能无法覆盖所有的其它站点；而有线局域网任意站点发送的信号都能够到达其它所有站点。
冲突的本质是接收方接收到两路或多路信号时就会发生冲突。CSMA/CD的本质是发送方判断是否发生了冲突。
但是由于无线信号的物理性质，无线局域网中发送方很难侦测到冲突的发生
4.4.2 802.11 物理层
802.11物理层使用2.4G和5GHz两个频段，都属于ISM，发射功率不能超过1w（实际上50mW已经很高）
2.4G拥挤（其他无线通信，微波炉，车库门），5GHz传输范围小
802.11b支持1、2、5.5、11Mpbs速率（一般为11），802.11a在5Ghz速率54Mpbs
使用OFDM（正交频分复用）增强频谱使用效率，抵抗多径衰减
常见的无线局域网产品在单一网卡上同时支持802.11a/b/g
802.11n使用4跟天线，结合多入多出（MIMO）技术提高网络吞吐量（100Mbps）
4.4.3 802.11 MAC 子层协议
802.11 MAC子层协议
存在的主要问题
无线信道的MAC子层协议与有线信道相比更加复杂
冲突检测非常困难
- 无线信道是半双工的，节点不能在同一个频率上传输的同时侦听到该频率上的突发噪声
- 接收信号比发送信号的强度低很多，无法在发送同时识别到微弱的信号（接收信号强度过低类似噪声）
无线节点具有不同的覆盖区域
Leads to hidden and exposed terminals（隐藏和暴露终端问题）
见4.2.5
无线局域网需要解决以下几个挑战：
冲突判断：不能直接使用“边说边听”方式来判断是否发生了冲突，因为可能根本听不到冲突（半双工）。事后确认来判断，如果发送后能够收到确认，则认为没有发生冲突；否则认为发生了冲突（无论是真的发生了由于站点竞争引起的冲突还是其它电气设备带来的噪声干扰，都可以认为发生了冲突）。由于整帧发送完成才能知道是否发生冲突，需要尽量避免可能的冲突发生。
冲突避免1：需要事先判断接收方是否空闲，并在接收期间避免其它站点贸然发送带来的干扰。（类似于CSMA，但更加复杂）
冲突避免2：当可能有多个站点同时竞争信道时，需要事先避免冲突的策略。（类似于p-坚持CSMA的随机后退策略）。每个站点随机选择发送的时间，减少多个站点同时发送引发冲突的概率。
支持并发：无线信号范围受限带来问题复杂性的同时也带来了可能的好处：可以支持多个通信同时“并发”进行，提高信道的利用率。（类似于网桥将一个冲突域分段为多个冲突域）
一个早期的但有影响力的方案是MACA（冲突避免多路访问）。通过短帧声明自己可能的接收时间段，其它站点根据声明安排自己的发送时间。
MACA冲突避免多路访问
CSMA/CA
CSMA/CA：带有冲突避免的CSMA
MACA存在的问题：依然会有冲突。
如果两个站点同时发送给一个站点RTS帧，会发生冲突，两个发送站点都接收不到CTS帧。这时需要分解冲突。
无线局域网采用了随机后退策略，类似于p-坚持的CSMA协议+二进制指数后退协议。P-坚持用于事先尽量避免冲突，二进制指数后退用于发生冲突后的随机时间选择。
带有冲突避免的CSMA（CSMA/CA）：在发送前侦听信道（物理侦听+虚拟侦听），如果信道忙则继续侦听，如果信道空闲，则按照随机选择后退的时间槽发送，冲突后指数后退。
- 通过侦听确定在一个很短的时间内（DIFS）没有信号，则认为信道空闲；
- 倒计数空闲时间槽（时间槽数事先随机选定），当有帧发送时暂停该计数器；
- 当计数器为0，发送自己的帧；
- 如果发送成功，则目标站立即发送一个短确认；
- 在规定时间内没有收到确认，加倍后退时间槽，再试；
- 直到发送成功或达到最大发送次数。
CSMA/CA机制下发送时序：
- CSMA/CA 在发送数据前使用随机指数后退（时间槽）来避免冲突
- MAC层使用ACK/重传机制来解决无线传输错误
侦听
CSMA/CA侦听机制：为了克服隐藏/暴露站点问题，采用物理侦听+虚拟侦听机制。
- 物理侦听只是简单地检查信道，看是否存在有效信号。
- 虚拟侦听根据听到的RTS/CTS帧（或其它类型帧）中包含的相关字段（Duration字段 ：用于说明该帧需要的传输时间）设置自己的网络分配向量（NAV，Network Allocation Vector），维护自己的一个关于信道使用的逻辑记录。代表无论能否真正听到信号，在NAV声明的时间信道一定是忙的。
- NAV也可以优化为声明自己接收确认的时间段，从而有效地支持并发。
- 无论物理侦听或虚拟侦听，只要有一个是忙的，则代表信道忙。
CSMA/CA协议使用可选的RTS/CTS虚拟侦听机制，用来解决隐藏站点问题：
虚拟侦听中每个站保留一个信道何时要用的逻辑记录，通过网络分配向量NAV获得
每一帧所携带的NAV说明这个帧所属的一系列数据将传输多长时间
RTS/CTS是可选的，但一般不用。只对隐藏终端有好处，并且影响效率。802.11中该机制会降低操作速度，所有终端都会听到RTS和CTS。
帧间隔
通过定义不同的帧间隔给予不同帧流量以不同的优先级
短帧有更高的优先级
为了节省移动设备电量，MAC具有节能机制
- 省电模式：AP缓冲数据，客户端信标帧苏醒，检查是否有为其缓冲的流量
- 自动省电交付：AP缓冲数据，客户端发送帧到AP后，AP将缓存帧发送到客户端
4.4.4 802.11 帧结构
- 帧控制：包括11个子字段：协议版本，类型字段（数据/控制/管理），子类型（RTS/CTS），去往/来自DS（发送还是来自AP），更多段，重传，电源管理，更多数据（更多帧），受保护的（加密），顺序（严格按照顺序处理）
- 持续时间：占用信道的时间（其他站用该字段管理NAV）
- 地址1，地址2，地址3：接收、发送、远端地址
- 序号：该帧的编号
- 数据：有效载荷，最长2312字节
- 校验序列：32位CRC
4.4.5 服务
Association：关联服务被移动站用来把自己连接到AP上，AP可能会接收也可能会拒绝。
Disassociation：解除关联服务一个移动站在离开本地或关闭之前，需要解除关联，AP在停止运行进行维护之前也会解除关联
Reassociation：重新关联服务允许站改变它的首选AP。用于从一个AP移动到另一个AP。
Distribution：分发服务决定了如何对帧进行路由；如果帧目的地是本地，则AP直接发送，否则需要通过有线网络转发。
Integration：集成服务处理协议转换（一帧发往或者来自局域网外）。
Authentication：AP发送帧之前必须认证，认证模式：开放；WiFi Protected Access 2（WPA2）；
Deauthentication：解除认证
Data Delivery：数据传送服务；802.11传输不能保证可靠性
Privacy：通过无线局域网发送的信息要求保密时，需要使用隐私服务，该服务管理加密解密的细节。
Privacy和Authentication的区别？
- Authentication是对用户是否有权使用AP进行认证和授权
- Privacy是指用户数据的隐私保护，用户通过802.11传输数据时要进行 数据加密，避免他人窃听
4.8 数据链路层交换
4.8.1 网桥的使用
网桥（散列表；flooding算法；逆向学习；动态拓扑结构变化）
网桥（路由器）把多个局域网连接起来组成更大的局域网
- 以太网交换机是网桥的现代称呼
- 网桥工作在数据链路层，通过检查数据链路层地址来转发帧
- 网桥把多个物理局域网连接成一个逻辑局域网
- 虚拟局域网（VLAN）是把一个物理局域网看成多个逻辑局域网
网桥使用的三种情况
- 学校和公司不同部门使用不同的 LAN，需要网桥把这些不同的 LAN 连接起来
- 一个组织分布在不同的楼宇，每个楼内有独立的 LAN，通过网桥把分布在不同空间的 LAN 连接起来
- 把逻辑上的单个 LAN 分成多个独立的 LAN。例如在大学中需要几千台工作站，系统规模很大，不适合把所有的工作站都放在一个 LAN 上：要上网的计算机数目远大于任何以太网集线器的端口数。
使用网桥的好处
- 使用网桥可以增加局域网的容量
- 使用网桥可以隔离出错的节点（通过转发规则）
- 网桥是全透明的，只需要将 LAN 线缆插入网桥就可以使用
网桥（交换机）的交换功能主要由三个模块组成：转发模块、自学习模块和MAC-端口映射表（也称MAC地址表）。
转发模块依据映射表决定入境的帧应该从哪个端口转出。转发规则为：
- 目标LAN和源LAN相同，丢弃
- 目标LAN和源LAN已知，转发
- 目标LAN未知（网桥新接入），使用泛洪算法（flooding）
- 使用哈希表列出目的地和他所属的输出端口（例：B给D发送数据）
4.8.2 学习网桥
A bridge operates as a switched LAN (not a hub)
带有交换功能的LAN，而不像集线器（将线缆的一端物理的连接在一起）
网桥的端口可以连接计算机、集线器和其他网桥
不同种类的线缆也可以附接到同一个网桥上
自学习模块
负责“实时”（可能几分钟）地将网络拓扑（主要指站点和端口的连接关系）的情况和MAC-端口映射表同步。
让映射表能够动态反应网络拓扑的变化。
向后学习，Backward learning
网桥使用向后学习(backward learning)来构建端口和目的地对应关系哈希表
- 网桥可以看到每个端口发送的所有帧
- 当收到一个入境帧时，将其内部携带的“源地址”与进入端口的关联关系写入映射表中。
- 建立哈希表后，就可以通过检查帧的目的地地址来发往对应的端口
- 如果发现还未学习到的目的地地址，通过Flooding发往所有的其他端口
自学习模块是一种动态学习机制。映射表是动态建立的，能够动态反应网络拓扑。开始时为空，随着流量的增多，映射表不断完善。
- 为了适应拓扑结构变化，会记录每个地址最新帧的时间
- 映射表中每个表项关联一个计时器，在规定时间内没有刷新的表项删除。
- 一台机器改变物理位置后，旧的对应关系将被遗忘，学习新的关系
- 一台计算机沉默几分钟之后也会被遗忘，需要重新学习
直通式交换（cut-through switching）或虫孔路由（wormhole switching）
- 算法实现采用专用的大规模集成电路芯片查找和更新哈希表
- 看到MAC地址就可以决定如何转发
- 速度快，可能帧还没传完就开始转发
- 降低了网桥的延迟和需要缓冲的帧数
MAC-端口映射表（也称MAC地址表）记录了站点和端口的映射关系。（考虑多个网桥连接时映射表的情况，如B1的4号端口与站点D\E\F\G的映射，B2的4号端口与站点A/B/C的映射）
请给出上图最终（收敛）的两个映射表。
网桥（交换机）实现机制
网桥（交换机）的交换功能主要位于交换机概念模型中的中继（Relay）功能中。三个模块的相互关系为：
- 转发模块使用MAC-端口映射表（也称MAC地址表）进行转发，使用入境帧中携带的目的地址查找映射表，将帧转发到相应表项对应的端口。
- 自学习模块执行逆学习算法，建立入境帧的源地址与入境端口的映射关系。
- 映射表将转发模块和自学习模块的实现解耦合。其它网络设备的工作机制大体如此（表驱动）。
4.8.3 生成树网桥
生成树网桥
网桥的拓扑结构存在环形，只使用向后学习可能会造成帧的传输陷入永远的循环
- 为了提高可靠性，网桥之间有冗余链路，造成了拓扑环路（两个网桥之间有两条甚至更多的路径）
- 提出基于生成树（Spanning tree）拓扑结构的网桥来解决拓扑环路问题
生成树拓扑结构
- 生成树要能够到达每个网桥
- 每个站到另外一个站只有一条路径
- 无环的生成树拓扑结构是实际拓扑结构的一个子集
生成树的过程
- 网桥运行一个分布式的算法
- 每个网桥周期性从所有端口广播一个配置信息给邻居
- 同时处理其他网桥的配置信息
- 这些消息不被转发，只用作构建树用于随后帧的转发
生成树算法
- 每个桥广播自己的桥编号，号最小的桥称为生成树的根；
- 每个网桥计算自己到根的最短路径，构造出生成树，使得每个LAN和桥到根的路径最短；
- 如果路径长度相同，选择经过最低标识符的路径；
- 当某个LAN或网桥发生故障时，要重新计算生成树；
- 生成树构造完后，算法继续执行以便自动发现拓扑结构变化，更新生成树。
4.8.4 中继器／集线器／网桥／交换机／路由器和网关
中继器、集线器、交换机、路由器、网关
应用层 | 应用网关 | |
传输层 | 传输网关 | 设在传输层的叫传输层网关。 |
网络层 | 路由器 | 用于连接多个逻辑上分开的网络。当一个分组进入到路由器中时，帧头和帧尾被剥掉，将IP分组传递给路由软件，路由软件根据分组的头信息来选择一条输出线路。 |
数据链路层 | 网桥
交换机 | 工作在数据链路层，将多个LAN连接起来，通过检查数据链路层地址来转发帧 |
物理层 | 中继器
集线器 |
第五章 网络层
网络层根据网络拓扑和流量特征为任意两个节点确定一条（多条）传输路径，并完成任意两个节点之间的数据递交。
网络层的功能通过网络层设备—路由器—实现。
5.1 网络层的设计问题
5.1.1 存储转发数据包交换
路由器是网络层设备，除了具有网络层的功能以外，还具有物理层和数据链路层的功能。
在直接相邻的两个路由器端口之间运行物理层协议（编码、速率等）和数据链路层协议（第三章学习的滑动窗口协议，提供一条线路上可靠的数据传输、第四章交换机的转发封装功能等）。
在所有路由器上运行的路由有关的协议属于网络层协议。
路由器处理数据过程：当一个数据（帧）到达路由器的一个入境端口后，首先进行帧的校验和验证（数据链路层功能），通过校验的帧中的负载字段（数据包或分组）提交给网络层，进入网络层的存储队列（网络层存储功能），路由器根据一定的调度规则处理队列中的数据包（网络层调度功能），被调度到的数据包根据路由表确定出境端口（网络层路由功能），并将数据包转发到所确定的端口（网络层转发功能），出境端口按照端口类型封装数据包为帧并发送出去（数据链路层功能）。
存储转发：将入境数据缓存（存储），根据一定的规则调度到出境端口并发送（转发）的过程。
5.1.2 提供给传输层的服务
网络层向传输层提供的服务包括无连接的服务和面向连接的服务。
无连接的服务由数据网络（互联网）阵营支持。初始由ARPANET选择，为了防止由于部分网络节点或线路瘫痪而严重影响路由，做到只要两个节点之间存在路径（两个节点是连通的），数据就可以被自动路由递交。
面向连接的服务由电话公司阵营支持。支持顺序递交的基础上，提供实时流量、可靠性等各种服务质量。
三网融合（电话网、有线电视网、数据网）要求一个网络支持以上两种服务并支持多种服务类型。
5.1.3 无连接服务的实现
所有的数据包被独立地注入到网络中，每个数据包携带完整的目的地址，在网络中被独立路由（在每个路过的路由器根据本身的路由表，和数据包中的目的地址，确定下一步的转发线路）。数据包之间由于网络状态的变化（反映到某些路由器路由表的变化，从而导致从当前路由器以后路径的变化）可能经过不同的路径。所谓“独立”，指的是任意两个数据包的路径没有相关性。
检查A的路由表中的错误：转发只能是邻居节点
5.1.4 面向连接服务的实现
事先为一次传输确定一条路径（虚电路，虚的含义是使用一条线路的部分资源而非全部），本次传输中的所有数据包使用同样的路径递交。
可以分为按需虚电路和永久虚电路。按需虚电路为每次传输计算一条路径，传输完毕后拆除虚电路；永久虚电路一直保存在网络中，每次传输选择一条虚电路。
虚电路使用一个标识符标识本虚电路。虚电路标识符具有“局部（本地）”特征，即每台路由器可能选择不同的标识符。标识符在整条路径上不断变化，不影响数据转发。
每个数据包携带一个虚电路标识符用于中间路由器的转发，每经过一个路由器，虚电路标识符的取值可能变化。
5.1.5 虚电路与数据报网络的比较
5.1 网络层设计要点（虚电路子网、数据报子网）
问题 | 数据包网络 | 虚电路网络 |
电路建立 | 不需要 | 需要 |
寻址 | 每个包包含全部的源和目的地址。 | 每个包包含简短的VC号。 |
状态信息 | 路由器不保留连接状态。 | 针对每个连接，每条VC都需要路由器保留其状态。 |
路由方式 | 每个数据包被单独路由。 | 建立VC时选择路由，所有包都遵循该路由。 |
路由器失效的影响 | 没影响，除了那些路由器崩溃期间丢失的包。 | 穿过故障路由器的所有VC都将崩溃。 |
服务质量 | 困难 | 容易，如果在预先建立每条VC时有足够的资源可以分配。 |
拥塞控制 | 困难 | 容易，如果在预先建立每条VC时有足够的资源可以分配。 |
实现上的一些共同考虑
都需要路由算法的支持：无论是数据报服务还是虚电路服务，都需要根据网络状况（网络拓扑和应用需求）计算从一个源节点到目标节点的路由（一条或多条路径）。
都需要将计算所得的路由分布式保存在路径经过的路由器中。每个路由器只保存路径的一部分（下一跳），所有路由器协同完成数据递交。
数据进入网络后逐跳转发。
数据进入路由器后都需要存储转发（缓存和查表）。
后续内容基于上述共同假设，不再具体区分。所以，本书大部分情况以数据报服务为例，但同样适用于虚电路。
5.2 路由算法
路由算法和路由协议
路由算法和路由协议的最主要的目标是为数据传输寻找一条（或多条，本书主要讨论一条）从源节点到目的节点的路径。这条路径应该能够满足给定的优化目标要求，应该能够反应当前的网络状态（包括网络拓扑—网络的连接情况，和网络的流量负载状况等）。
路由算法和路由协议是路由器中的一个重要功能，目标是建立和维护存放在路由器中的路由表。路由器还有另外一个重要功能，即使用路由表对数据进行的转发功能（被路由功能，如IPv4）。
路由算法是一个优化问题的求解，更为精确的说，是一个受限的优化问题的求解。可以很复杂，有些情况下是NP-hard问题。常用的路由算法使用较为简单的启发式算法求解。本书主要讨论相对简单的启发式算法。
路由算法可以分为集中式路由算法和分布式路由算法。也可以分为静态路由算法和动态（自适应）路由算法。还可以有其它分类形式。
- 集中式路由算法一般要求有一个负责计算路由的中心节点，这个中心节点拥有全局网络信息，求解后的路由结果发送到其它节点。分布式路由算法中每个节点使用局部信息分别计算自己的路由。
- 静态路由算法是实现确定路由，路由确定后不再随着网络状态的变化而改变。动态（自适应）路由算法根据网络当前的情况“实时”确定路由。
路由算法根据网络状态计算路由时，需要了解网络的当前状态，这个状态也是路由算法使用的数据结构。这个结构的获得需要通过网络中路由节点之间交换信息获得，这些信息交换需要遵循一定的规则，属于路由协议。
在本书中，路由算法和路由协议可以交换使用。
路由算法（协议）属于网络层协议的一部分，一般驻留在节点的操作系统中。
虚电路路由只有在建立路径时才计算路径，在使用过程中不再改变，即使网络状态发生剧烈改变。
数据报路由“实时”的根据网络状态修改部分相关节点的路由，不同的数据包可能使用不同的路径。（在数据包传递过程中，路由算法根据当前网络状态修改了路由表）
“实时”一般采用周期性或重大改变触发式的计算路由表。或采用两者结合的方式。
路由算法的特征
路由表既要反应当前的网络状态，又要保持一定的稳定性。需要优化和稳定的折中。不稳定的路由表会造成许多不可知的错误。
路由表的计算既需要达到（近似达到）优化目标，又需要计算简单、用时少。一般路由表需要在相对短的时间内收敛到稳定状态，这个路由表会使用相对较长的时间。
常见的特征有：
- 正确性
- 简单性
- 鲁棒性：在长时间连续运行过程中对于故障的抵抗力
- 稳定性：一个稳定的算法可以迅速收敛，达到平衡，并且保持平衡状态
- 公平性：单个连接的公平
- 有效性：全局的效率（与公平性矛盾）
路由是发现网络路径的过程
- 将网络建模为节点和链接的图形
- 决定优化什么（例如，公平与效率）
- 更新拓扑变化的路由（例如故障）
转发是沿路径发送数据包
5.2.1 Optimality principle 优化原则
最优化原则、sink tree
作为最优化原则的一个直接结果，从所有的源到一个指定目标的最优路径的集合构成了一棵以目标节点为根的树。这样的树称为汇集树（sinktree），如图 5-6 (0）所示，图中的距离度量是跳数。所有路由算法的目标是为所有路由器找到这样的汇集树，并根据汇集树来转发数据包。
最优化原则：如果路由器J在从路由器I到路由器K的最优路径上，那么从J到K的的这一段子路径必定是从J到K的最优路径。
最优化原则可以通过反证法证明。
最优路径通常称为最短路径，可以使用不同的度量值或它们的组合来定义（依据优化目标）：
- 跳数
- 距离
- 带宽
- 平均流量
- 通信成本
- 平均延迟
最优化原则可以避免环路。即遵循最优化原则计算的路径没有环路，但是当网络拓扑收集不准确时，可能造成环路。
5.2.2 Shortest path algorithm 最短路径
最短路径路由
Dijkstra的算法计算图上的汇树：
每个链接都分配了一个非负权重/距离
最短路径是总重量最低的路径
使用权重1给出跳数最少的路径（按1的作用为权重）
算法：
从sink开始，将其他节点的距离设置为无穷大
放松与其他节点的距离
选取距离最小的节点，将其添加到汇点树中
重复此操作，直到所有节点都在汇点树中
最短路径算法用于计算任意两个节点之间的最短路径，网络中经常使用的是迪杰斯特拉算法，当然还有其它的算法。
迪杰斯特拉算法工作在加权无向图或有向图上，先决条件是加权图已知。
迪杰斯特拉算法有几个特点：
- 是一种贪心算法
- 权值为标量
- 权值非负
迪杰斯特拉算法不适用于权值为矢量或权值为负值的情景。
- 矢量加法具有方向性
- 权值为负使得贪心算法不成立
5.2.3 Flooding 泛洪
flooding算法
泛洪（扩散）算法：每个路由节点把从一个端口收到的数据从其它所有端口转发出去。
泛洪算法不需要事先知道网络的拓扑结构图（从现在起，网络拓扑指的是网络连接+权值），所以适用于协议开始时传递拓扑信息（见本章链路状态协议）。
基本的泛洪算法经过所有可能的路径，具备以下特性：
- 最可靠：只要有一条路径连接就能传递到
- 最快：肯定使用了最短路径
- 代价最大：所有路径至少走一遍，通常一条路径就可可以有效支持广播
泛洪算法的优化：
- 每个路由器只转发最新的数据，已经转发过的不再转发
- 限制每个数据被转发的次数（设置一个计数器，每经过一跳计数器减一，计数器为0就丢弃该数据包）
5.2.4 动态路由算法
动态路由算法：每个路由器能够根据当前的网络状态（网络拓扑）计算从自己到所有其它路由器的最短路径。
动态路由算法也称为自适应路由算法，包含两个方面的内容：获得当前的网络状态，根据网络状态计算路由。
根据获得当前网络状态和计算最短路由的不同，常见的路由算法有：
- 距离矢量路由算法
- 链路状态路由算法
- 二者的混合
1. Distance vector routing 距离矢量
距离矢量路由及无穷计算问题
距离矢量路由算法：每个路由器（路由节点）定期地与自己的邻居相互交换距离矢量，根据距离矢量计算路由表。
- 距离矢量是一组矢量<目的节点，距离>
- 是一种分布式的计算方法：根据邻居传来的距离矢量，从自己的邻居中选择距离最短的作为下一跳。每个节点只知道路径的下一跳。
- 是较早的一类路由算法
距离向量是一种分布式路由算法，最短路径计算在节点之间进行分割，算法如下：
- 每个节点都知道与其邻居的链接距离
- 每个节点向所有邻居通告最低已知距离的向量
- 每个节点使用接收到的向量来更新自己的向量
- 定期重复
若遇到距离相同，则选择标号较小的那一个
J到达A、I、H、K的距离：8、10、12、6
故障可能导致DV在寻找无法到达的节点的路径时“计数到无穷大”
距离矢量路由算法只是根据邻居的距离矢量计算自己的路由表，当计算一条路径时，无法判断邻居所说的最短路径是否通过自己（这是分布式算法本身固有的缺陷），所以可能带来环路问题。
环路带来的缺陷是数据在网络中无休止地循环（IP协议中规定了数据分组在网络中的最大存活时间，用以克服环路）
环路带来的第二个缺陷是算法收敛慢，尤其是线路出现问题时很难达到收敛。
常见的克服无穷计算（计数）的方法有：
- 逆向有毒（带有染毒逆向的水平分裂法）：防止路由器向邻居返回一个从该邻居得到的最佳路径
- 抑制定时器：在一段时间内，不接受从邻居传来的不好的路径
- 都存在缺陷
距离矢量路由算法虽然具有一个根本性的缺陷（一个路由节点无法知道自己是否在邻居宣称的最短路径上），从而无法从根本上克服环路问题（即使在理论上，网络实际比理论探讨复杂得多），环路问题可能带来不可预知的网络错误（有时使得网络无法正常运行），但是在很多时候非常有用，尤其是在不同的自治域间计算路由（见Internet框架结构）。
自治域（AS，Autonomous System）指的是由一个组织统一建立、维护、使用的网络（类似于局域网，但现在指的是用于给用户传递数据的广域网ISP）。这个网络的拓扑结构对外保密，能够使用的路径由组织统一发布。域间路由只能根据这些信息计算路由。
最终解决方案是保持完整的路径信息（BGP协议，一种改进的用于域间路由的距离矢量协议）。
2. Link state routing 链路状态
链路状态路由
链路状态路由算法：每个路由器通过定期或触发式扩散自己的邻接信息给所有节点，从而得到完整的网络拓扑图，依据完整拓扑图计算自己的路由表。
- 每个路由节点都需要一张完整而一致的网络拓扑图
- 使用最短路径算法计算从自己到其它所有节点的最短路径，每个节点知道全部的路径信息
- 是改进后的路由算法
链路状态是距离矢量的替代方案，计算量更大，动力学更简单；广泛应用于互联网（OSPF、ISIS）；算法如下：
- 每个节点（可靠地）在LSP（链路状态包）中洪泛其邻居的信息；所有节点都学习完整的网络图
- 每个节点都运行Dijkstra算法来计算每个目的地的路径
Seq.number和age用于可靠的泛洪
新的LSP在所有其他线路上接收和发送的线路上得到确认
示例显示了路由器B上的LSP数据库
source E：通过EAB和EFB发送
如果第四项被转发前，C的链路状态包的一个副本由F到达，则状态位变为100011
链路状态路由算法能够正确运行的基本保证是每个路由节点的邻接信息能够可靠地传递到所有其它路由节点。所以，可靠的扩散算法至关重要。扩散的任意一步（即邻接信息在两个路由器之间的传递）都必须是可靠的，可靠算法参见第3章内容（任意两个相邻的节点之间可靠的数据传输），所以每个节点保留的数据结构中都有转发和确认两个字段。
为了减少可能的错误带来的影响（校验和从理论上无法保证数据100%正确），每个邻接信息只能存活一定的时间（年龄字段）。
为了减少扩散代价，邻接信息使用编号，使用优化后的扩散算法。
即使这样，也可能有环路，主要是邻接信息不能完全正确的在规定时间到达所有路由器，从而带来路由器中的网络拓扑图不一致。
可能碰到的一个部署问题
无论是距离矢量还是链路状态路由算法，都是以所有其它路由器为目标。当网络中的路由器数量增多时，路由表项会随着路由器的增长而线性增长。路由表项过多会带来两个主要的问题：较大的存储空间和较长的查表时间。路由器的存储空间（尤其是快速存储空间NVRAM）有限且价格昂贵；路由器需要尽快地转发分组。这就是由路由器数目增多而带来的扩展性问题（Scalability problem）。这个问题不解决会使得整个网络性能剧烈下降甚至不可用。
解决这个问题的一个思路是层次路由：将大的网络划分为多个区域，区域内部详细路由，区域之间域间路由。
层次路由用于减少路由表项。
距离矢量路由和链路状态路由的比较
3. Hierarchical routing 层次路由
分级路由
分层路由减少了路由计算的工作量，但可能会导致比平面路由稍长的路径.
路由算法计算从一个路由器到其它路由器的最短路径，支持一对一的路径计算和数据传递。
在有些应用中，需要支持广播、组播、选播、移动节点等。这需要根据基本路由算法进行扩展，从而产生了新的路由算法：
- 广播路由
- 组播路由
- 选播路由
- 移动路由
基本解决方式是根据最短路径算法计算一棵树，在路由表中添加相应的表项和相应的转发算法，从而支持数据通过计算得到的树进行传递。在计算构建树时，由于两种路由协议中每个节点所知信息不同而有所不同。
4. Broadcast routing 广播路由
广播路由
广播路由：找到支持数据广播的转发路径。
使用分别为每个节点发送一次的方式非常低效，常用方式是使用类似树结构来进行转发，可以避免在一条线路上转发同样的数据多次。
如果网络运行链路状态路由协议，那么每个节点包含完整的网络拓扑信息，则很自然能够计算从其它所有节点到广播节点的汇聚树。然后依据汇聚树转发给最短路径经过自己的节点。
如果网络运行距离矢量路由协议，每个节点不能计算汇聚树，使用逆向路径转发：当一个节点收到广播分组，判断这个分组是否从自己到广播源节点的最短路径的端口上收到。如果是，则认为是第一份收到的数据，转发给所有其他邻居节点；否则，则认为是重复分组，不再转发。
广播向所有节点发送数据包
RPF（反向路径转发）：将链路上接收到的广播发送到所有剩余链路的源。或者，可以在所有节点上构建和使用汇聚树。
5. Multicast routing 组播路由
组播路由：找到支持数据组播的转发路径
当组成员节点较为稠密时，可以使用基于广播树的方式：直接使用广播树近似，或对广播树剪枝。
如果网络运行链路状态路由协议，则树的生成和剪枝非常自然。
如果网络运行距离矢量路由协议，使用逆向路径转发，通知上游节点剪枝：如果一个路由器连接的主机没有组成员，并且没有收到其它路由器的关于组的连接请求，则认为本节点与组无关，通知上游路由器剪枝掉自己；如果一个路由器原来位于组的转发树（结构）上，现在所有下游节点都提交了剪枝请求，并且自己直接连接的主机再没有组成员，则也向上游路由器发送剪枝掉自己的请求。
dense case
多播发送到称为组的节点子集，为每个组和源使用不同的树
上述组播路由需要为每个组的每个成员建立一棵树，路由节点需要保存的组路由信息较多。
可以使用基于核心（汇聚点）的方式，即为每个组寻找一个核心，组的所有成员都使用最短路径连接到核心。发送时，信息首先传递到核心，然后经核心传递到所有其它节点。
基于核心的方式每个组只需要一棵树。
但是，核心的选择非常困难，在有些目标要求下（如代价最小），问题可能是NP-hard。
最短路径树不一定是最小代价树（Steiner Tree Problem）
sparse case
CBT（基于核心的树）使用单个树进行多播，树是从核心节点到组成员的汇树，多播将进入核心，直到到达CBT
6. Anycast routing 选播路由
选播路由：当节点向一个组传递数据时，只需要向距离最近的一个组节点发送即可；反之，当从一个组接收数据时，也是选择距离自己最近的节点。
实质：所谓组，即为一个分布式系统的多个站点；选播路由就是为当前路由器从这些站点中选择距离自己最近的一个。最近，可以是物理距离，也可以是多个度量值的组合，与已学习的路由算法一致。
当网络使用距离矢量路由算法时，非常简单，所有组成员使用一个统一的标识，直接选择到这个标识的最短路径即可。
当网络使用链路状态路由算法时，可以使用修改的迪杰斯特拉算法从这些站点中选择一个距离自己最近的站点（执行贪心算法，直到第一个组成员标记）
Anycast向一个（最近的）组成员发送数据包，在许多地方与节点脱离常规路由
可以看做某个节点出现在多个位置上（同一个组的不同节点）
使用普通路由的算法找到最近节点位置即可
7. Routing for mobile hosts 移动主机路由
移动路由
移动主机路由：支持主机的移动：能够找到它并将数据传送给它。
移动支持：家乡代理，每台主机到达其它地方后，需要与家乡（登记注册地）服务器通信，告知自己现在的位置。
其它节点向移动主机发送数据时，首先发送到其注册地址（这是主机唯一对外宣称的官方地址），家乡代理将数据转发给移动主机。
移动主机使用当前地址与发送主机联系。
发送主机直接发送到移动主机当前位置。
中间需要隧道技术支持：隧道技术即为封装技术，详细见网络互联。
初始时，每个地点的管理服务器分为三个部分：本地主机在本地，本地主机在外地，外地主机在本地。各个地点的服务器定期交换部分内容，完成路由。
可以通过本地代理联系移动主机
固定归属代理通过隧道将数据包传输到移动主机；回复可以优化后续数据包的路径
不更改路由器或固定主机
5.3 拥塞控制算法
处理拥塞是网络和传输层协同工作的责任
目的：减少拥塞，提高网络整体性能
当过多的流量出现时可能会导致拥塞，拥塞产生后由于过多的数据丢失和重传，致使网络性能下降
Goodput (=useful packets，有效吞吐量)
5.3.1 拥塞控制
拥塞产生的原因
- 传输层注入太多的、超过网络处理能力（网络容量）的数据
- 网络层路由协议不能充分使用网络资源、不能适应流量的分布变化
- 网络资源不足以支持流量
拥塞控制的基本思路
- 网络层的路由节点感知、检测拥塞状况，并在需要时将拥塞状况返回给网络层或传输层相关实体
- 网络层和传输层依据一定的标准处理拥塞
- 拥塞控制可以分为拥塞避免和拥塞处理：提前做好各种准备，避免拥塞的发生，如加大网络资源提供、控制流量准入、调节流量分布特性、设计更好的路由协议等方式避免拥塞的发生；将要或已经发生拥塞时，可以减少流量的注入、流量调节、负载脱落等解决拥塞。
拥塞控制的基本原则
发现拥塞，传递信息，调整系统
- 监控系统，检测何时何地发生拥塞
- 将信息传递给可以采取行动的地方
- 调整系统操作以纠正问题
哪些指标可用于衡量拥堵程度？
Loss of packets 数据包丢失
Queue length 队列长度
Queueing delay 排队延迟
Retransmitted packets due to time out 由于超时而重新传输的数据包
Other variation of the above 上述其他的变体
拥塞避免政策
5.3.2 拥塞控制的途径
网络必须尽最大努力提供负载
- 不同时间尺度下的不同方法
- 节点还应减少提供的负载（传输）
提高网络供给：根据较长时间段的检测，判定网络资源不能支持现有流量，则需要增加网络资源。
- 找到瓶颈资源并提高供给
- 时间较长（几个月甚至更长）
5.3.3 流量感知路由
流量感知路由：将链路负载作为权值计算的一个因素，通过改变链路权值重新计算路由，使新的流量绕开负载较重的热点区域
- 实时改变路由会引发路由震荡
- 要处理陈旧信息对路由计算的影响
- 流量工程：一般将一天的流量归纳为几个特征模板，并为每个模板计算相应的路由，每个模板的路由工作较长时间（几个小时）
- 最新进展：流量工程（微软SWAN），几分钟计算一次
- 问题是对一个实时流量选择哪一个模板，并处理切换时的一系列问题
根据流量选择路由，而不仅仅是拓扑
例如，如果CF已加载，则使用EI进行西向东交通
但要注意避免振荡
5.3.4 准入控制
准入控制：除非网络能够携带额外的流量，否则不再建立新的连接。
- 适用于虚电路
- 可以和流量感知路由算法结合，即为新的连接寻找一条负载较轻的路径
准入控制仅在网络具有足够容量（例如，具有虚拟电路）时才允许新的流量负载
可以与寻找一条不拥挤的路线相结合
5.3.5 流量调节
流量调节：当将要发生拥塞时，感知拥塞的路由节点必须告诉发送节点降低发送速率
- 确定拥塞：一般通过检测路由节点的排队队列长度
- 发送方降低发送速率
- 抑制包：路由节点直接给发送方返回一个抑制包，发送方接收到抑制包后降低发送速率
- 显示拥塞通知（ECN）：设置分组头部的位表明拥塞，接收方返回数据时将此通知返回给发送方，发送方收到通知后降低发送速率
- 逐跳后压：抑制包在返回途中逐跳降低所经过路由节点的发送速率
抑制包（choke packet）
通知拥塞发送方的最直接方式是直接告诉发送方。在这种方法中，路由器选择一个被拥塞的数据包，给该数据包的源主机返回一个抑制包（choke packet）。抑制包中的目标地址取自该拥塞数据包。同时，在原来的拥塞数据包上添加一个标记（设置头部中的一位〉，因而它在前行的路径上不会产生更多的抑制包。除此以外，数据包的转发过程如同平常一样。
当源主机收到了抑制包，按照要求它必须减少发送给指定目标的流量，
显式拥塞通知 (ECN, Explicit Congestion Notification)
拥挤的路由器向主机发送信号以降低流量
ECN（显式拥塞通知）标记数据包，接收器向发送器返回信号
逐跳后压
5.3.5 负载脱落
负载脱落：当上述方法不能完全消除拥塞时，随机丢弃部分分组。
- 可以根据应用不同，设置不同的分组选择策略：对文件传输而言，旧的分组更好，选择丢弃新的分组；对语音通信而言，新的分组更好，选择丢弃旧的分组。
- 但是设定由用户完成，如何刺激大家选择合适的优先级不容易
拥塞控制（RED）
- 在Internet中，使用随机早期检测协议（RED，Random Early Detection）：每个路由器实时检测队列长度，如果超过一定的阈值，代表将要发生拥塞，尽早地随机选择一些分组丢弃。RED协议尤其适用于不支持ECN的网络中。现在新的拥塞控制主要集中在基于ECN的拥塞控制（新的路由器支持）
5.4 服务质量 QoS
服务质量机制是根据网络实际状态和用户的需求，确定用户数据的传输方案，使之与要求尽量匹配的一些方法的统称。本部分内容主要要求一些基本的方法，更加精细的算法很多很复杂。
- 流量整形：将随机的用户流量进行规则化处理，以便网络路由。包括漏桶和令牌桶算法。
- 包调度算法：使用多个队列对不同用户需求进行调度，以便“公平”地使用网络资源。
- 准入控制：根据用户服务质量需求描述，确定用户传输数据所使用路径的允许与否。
- 综合服务：一种广泛应用于组播的资源预留方式。
- 区分服务：对用户数据进行类型（优先级）设置，并根据不同类型提供不同资源使用的方式。
服务质量取决于可靠性、延迟、抖动、带宽
5.4.1 Application requirements 应用需求
不同的应用程序关心不同的属性
我们希望所有应用程序都能得到他们需要的东西
Jitter Control 抖动控制
抖动、缓冲
延迟的变化（标准差）或者数据包到达时间的变化称为抖动
网络提供具有不同QoS（服务质量）的服务以满足应用需求
Network Service | Application |
Constant bit rate | Telephony |
Real-time variable bit rate | Videoconferencing |
Non-real-time variable bit rate | Streaming a movie |
Available bit rate | File transfer |
5.4.2 Traffic shaping 流量整形
流量整形调节进入网络的数据的平均速率和突发性
流量整形（也称为“数据包整形”）是一种计算机网络流量管理技术，它延迟部分或全部数据报，使其符合所需的流量配置文件。流量整形是一种限速形式。
流量整形通常与以下内容结合使用：
- 差异化服务、集成服务——包括流量分类和优先级。
- 加权循环赛（WRR）
- 随机早期检测（RED）、加权红色（WRED）和红色输入/输出（RIO）——降低了端口队列缓冲区尾部丢失的可能性，从而降低了TCP全局同步的可能性。
- 多个端口队列缓冲区。
漏桶和令牌捅
漏桶算法、令牌桶算法
令牌/泄漏桶限制了流量的平均速率（R）和短期突发（B）
对于token，桶大小为B，水以R的速度进入并被移除发送；与leaky相反。
漏桶和令牌桶是网络中用于流量整形的主要方法。根据所学知识，回答下面问题：
1）漏桶的工作原理是什么？
① 在每个主机连接到网络的接口处都包含一个漏桶，即一个有限长度的内部队列。
② 如果当队列满的时候，又有一个分组到来，则该分组被抛弃。
③ 每经过一个常数时间才允许把一个分组放到网络上。
④ 这种机制可以将主机内用户进程发送出来的一个不均匀分组流变成网络上的一个均匀分组流，他把突发的分组流变得很平滑，从而降低了拥塞的几率。
⑤ 无论负载突发性如何，漏桶算法都强迫输出按平均速率进行。
2）令牌桶的工作原理是什么？
① 漏桶中保存的是令牌，这些令牌由时钟产生，每隔T产生一个。
② 要使一个分组被传送出去它就必须要抓住并销毁一个令牌。
③ 令牌桶允许将令牌（即许可权）保存起来，直至达到桶的最大尺寸n
④ 当令牌桶满后，令牌桶丢弃令牌，不丢弃分组。
⑤ 从本质上讲，令牌桶所做的事情是：允许突发流量但是不得超过一个预定的最大值
3）区别
① 流量整形策略不同：漏桶法不允许将空闲的主机许可权保存起来以便将来发送更大的突发数据，而令牌法则允许将许可权保存起来，直至达到桶的最大尺寸。
② 丢弃对象不同：当令牌桶满了之后，丢弃令牌，但是不丢弃分组；相反的，在漏桶算法中丢弃分组。
计算题例题：在一个5Mbps网络上有一台主机，其流量通过一个令牌桶整型，令牌桶的填充速率为2Mbps。初始时令牌桶被填满到容量8Mb。试问该计算机能以5Mbps的全速率传输多长时间。
设时间为t
∴ t = 8/3 s
5.4.3 Packet scheduling 包调度
在同一个流的数据包之间以及在竞争流之间分配路由器资源的算法称为（数据）包调度算法（packetscheduling algorithms）
例：
5.4.4 Admission control 准入控制
准入控制通过是否允许一个流进入网络来避免多个流对网络资源的过度使用，从而影响服务质量。
准入控制采用流量规范，并决定网络是否可以承载它
有一个对应于带宽和延迟性能保证的流规格说明方法。该方法在流量源端采用 CR, B）令牌桶整形，而在路由器采用 WFQ。每个流都有一个WFQ权重W，该权重值足够大到能排空速率为R的令牌桶，如图5-33所示。例如，如果流的速率为 lMbps，路由器和输出链路的容量为 l Gbps，那么在路由器的输出链路上该流的权重必须大于所有流的全部权重的千分之一。这保证了该流具有最低带宽。如果流得不到足够大的速度，那么该流就不允许进入网络。
5.4.5 Integrated services 综合服务
综合服务主要用于针对单播和组播应用
资源预留
为每个流设计QoS；处理多播流量。资源预留协议（RSVP, Resource reSerVation Protocol）：
- 接收方将请求发送回发送方
- 沿途的每个路由器都保留了资源
- 路由器合并同一流的多个请求
- 整个路径已设置，或未进行预订
组播路由算法（树的计算、建立和维护）、使用树结构进行组播数据传递等都不属于RSVP协议的内容。RSVP协议只关心资源的预留，当然这些功能需要相互配合。
综合服务带来的可扩展性问题
综合服务协议会带来路由器的可扩展问题（相对于路由器节点太多引发的可扩展性问题，层次路由），这个问题的核心是每个流（无论是组播还是单播）都需要途经的路由器保存一个路由表项。
当网络中存在越来越多的流时，路由表项会随着流的数目线性增长，对这些表项的计算和维护需要的计算、存储资源和信息交换也会不断增长，最终导致网络性能下降甚至崩溃。
Internet中一般不支持基于 流的路由算法或协议，只是与目的地址有关，称为无状态路由算法。
常用于服务质量的协议为基于类别的区分服务。
5.5 网络互联
一个互联网络的集合：
5.5.1 How networks differ 网络的区别
5.5.2 How networks can be connected 网络怎样连接
基于公共网络层（IP）的互联网
不同类型网络互联
互联不同协议的网络非常复杂，协议转换通常不是首选项。
不同类型网络关注的重点、采用的技术方案可能区别很大，体现在实现上则是协议采纳的数据结构（头部）和处理数据结构的算法可能具有很大的差异。
从一种协议到另外一种协议的转换可能会丢失一些信息，也可能需要一些新的信息。
最终的协议转换过程可以类比常见的一种游戏：每个人带着耳机看上一个人表演然后表演给下一个人。
5.5.3 Tunneling 隧道技术
网络互连（隧道技术）
隧道技术是解决不同种类网络互联一个特例的方法。
隧道技术用于解决发送和接收网络属于同一类型网络，但是中间经过不同类型网络的情况。
隧道技术是一种封装技术，在中间网络传输时将整个数据包使用中间网络的协议类型封装。
网络种类不同，则封装数据包的头部和对头部的处理方法不同，而数据包的头部和对头部处理的方法驱动数据在网络中被路由，不同的头部及其处理方法对应于汽车的引擎。
5.6 Internet网络层
Internet的网络层主要包括Internet完成网络层主要功能的协议栈，包括：。
- Internet路由协议：用于计算任意两个节点之间的数据传输路径，并将路径分布保存在途径的路由器中；包括域内路由（OSPF）和域间路由（BGP）。主要原理在5.2节已经学习，这里只是两个实例。
- Internet数据转发（被路由）协议：规定数据在Internet中传输时应该遵循的协议，只有遵循这个协议，数据才能够被网络沿着路由协议计算所得的路径（路由表）从发送方逐跳交换到接收方。包括协议格式（IPv4协议头、IPv6协议头）以及处理算法。协议除了需要支持正常的转发功能、服务质量以外，还需要处理不同网络互联带来的一些问题，主要是数据包分段等。
- Internet控制协议：用于在网络中传递控制信息（ICMP协议）、支持转发数据时需要的链路层地址（ARP协议）、动态主机配置协议等。
- IP地址：用于标识网络上的设备，并基于此进行路由转发。为了克服由于节点数目太多带来的路由器中路由表项可扩展性问题，采用了层次地址，并具有明显的地理指向性。为了支持层次路由，分类IP地址和不分类IP地址的相关机制。
- IP组播：支持网络层的组播功能。原理5.2节已介绍。
- 移动IP：支持节点的移动性。原理与第4章、5.2节相似
5.6.1 IPv4 协议
IPv4协议
IPv4协议是过去几十年最主要的网络层协议之一，提供尽力而为（best effort）或尽最大努力的数据传输服务。
IPv4协议驻留（运行）在Internet主机的操作系统内，驻留在路由器的网络层中。
IPv4支持最基本的数据传输服务，如数据包逐跳转发、数据包分段等。
IPv4协议很少提供服务质量等功能的支持，在支持越来越多的种类不同的数据传输服务要求时，出现了所谓“瘦腰现象”。
网络控制信息等使用IPv4协议格式封装，支持控制信息在网络内的传递。
IPv4协议对应的协议数据单元是数据包（分组），包括头和数据两个部分。数据来自于上层协议（传输层协议）或IPv4服务的网络层协议（网络控制信息协议）等。
IPv4协议分为协议头和处理算法，头格式规定了数据传递时必须携带的信息，处理算法根据这些信息完成数据的递交。
IPv4协议头由20字节定长部分和可选的变长部分组成。
- 版本（4位）：协议属于的版本，常见的取值为4（0100）和6（0110）。发送方机器设定，中间经过的路由器和最终的接收方读取数值，确定使用什么格式解析头部。
- 头长（IHL，4位）：规定了头部的长度，取值范围为5~15，单位为4字节（或格式中的一行）。最小头长为20字节（固定头部），最大头长为60字节（可选头部最长40字节）。
- 区分服务（DS，8位）：前6位标记数据包的服务类型，路由器根据不同的服务类型采取不同的调度方式（见5.4节区分服务）；后2位用于携带显示拥塞通知（ECN），用于标识数据包在传递过程中是否经历了拥塞，路由器或发送主机依次调整速率。（见5.3节拥塞控制）
- 总长度（16位）：整个数据包的长度，以字节为单位，包括头和数据的总长度。最大取值为65535。
运行在以太网中的主机发送或接收的数据包长度受到以太网帧最大长度的限制：以太网帧最大负载为1500字节，所以一个数据包在以太网中传输时其总长度取值不大于1500.
- 标识（ID，16位）：标识一个数据包。如果数据包需要分段，则需要将数据包的数据字段分成多份，每份数据再封装为一个数据包（添加数据包头部，为了能够路由转发），分段的数据包（子数据包）中的标识字段与被分段数据包（父数据包）的标识一致（继承）。重新组装时，将标识一样的数据包组装。
- 不分段（DF，1位）：标识数据包不能分段。如果携带此标识的数据包进入一个小分组网络（MTU不支持携带的数据量），则被拒绝转发，并发送相应消息。
- 更多段（MF，1位）：标识后面是否还有分段，置位标识还有，否则没有，自己就是最后一段。MF=1，DF=0表示后面还有分段
- 分段偏移量（fragment offset，13位）：标识本分段数据在原来数据包数据中的位置（偏移量），8字节为单位。
- 生存期（TTL，8位）：用于规定数据包在网络中存在的时间。可以取值为时间单位（秒），也可以取值为跳数。每经过一个时间单位或一跳减一，为0时丢弃该数据包。一个重要应用是避免数据包在网络上由于路由环路（5.2节提到路由环路不可避免）在网络上无休止地循环。也可用于探测网络路径。
- 协议（protocol，8位）：用于标识数据包中所携带数据的类型。将数据提交给指定的处理进程。
- 头校验和（16位）：用于确定头部在传输过程中是否发生了错误。由于IP协议不提供可靠的传输，所以不对整个分组（数据）校验；由于头部携带的信息对于路由数据非常重要，所以校验头部。经常使用的是反码加法。头校验和每跳都会变化（至少TTL发生变化）。
- 源地址（Source Address，32位）：发送方的IP地址。用于中间路由器向发送方发送某种控制信息（如抑制分组），或接收方回复。
- 目标地址（Destination Address，32位）：接收方的IP地址。用于查表，确定转发路径。
- 选项（Options，0~40字节）：4字节的倍数，用于可选择的功能，如源路由、时间戳等。
分段举例：一个大的IP分组经过小分组网络时，被分成了多个小的分组。
- 分段过程：将大的分组的数据分成若干部分，为每部分封装一个IP头。子分组的头部字段取值与父分组头部字段的关系：如版本号、头长度、区分服务、标识、生存期、协议、源地址、目标地址等字段直接继承；跟分段相关的字段如总长度、MF、分段偏移量等需要根据分段情况填写。
- 组装过程：根据与分段相关的字段将各分段携带的数据组装在一起，为其封装一个IP头。组装时，标识号一致的分段需要组装为一个分组；判断所有数据是否都已经收到，根据总长度、分段偏移量、MF、IHL计算判断。
5.6.2 IP 地址
IP地址、子网、子网掩码、子网划分
IPv4地址长度为32位，用于标识一台主机或路由器的一个端口。
IP地址是一种逻辑地址，为了减少为每个IP地址单独路由引发的路由器表项过多（路由器表项可扩展性问题），通常采用层次地址。即IP地址的一部分用于标识所在的网络，另一部分标识在网络中的编号，分别称为网络地址和主机地址。
路由器表项只保存到一个网络的路由表项，负责将分组递交到所在的网络。
与网卡地址（MAC地址）不同：位于同一个网络的网卡地址原则上没有任何关系，是相互独立的。真正通信时，需要IP地址与网卡地址的转换（ARP协议）。
IP地址的网络号也称为（网络）前缀。原则上，位于同一个网络的主机之间具有相同的网络号。
路由器的一个端口与其所连接的设备属于同一个网络。如果路由器的端口与一个子网相连，则此端口和网络中所有主机属于同一个网络，分配的IP地址具有相同的网络号；如果路由器的端口与另外一台路由器的某个端口相连，则这两个不同路由器的端口也属于同一个网络。
IP地址中的网络号需要某种声明：一种是子网掩码，一种是分类的IP地址（稍后介绍）。
子网掩码：用于声明IP地址中网络前缀的长度（前多少位为网络号）。
子网掩码的定义方式：与IP地址位数相同，如果一个IP地址中某一位属于网络号，则子网掩码对应的位置1，否则置0。
IP地址和子网掩码都可以使用点分十进制表示。
由于IP地址定义为“网络号+主机号”，所以，子网掩码的形式为“111……1000……0”。可以使用两种方式声明：“255.255.0.0”或“IP/16”
IP地址与子网掩码“按位与”，就得到IP地址所在的网络。通常一个网络使用主机全0表示。
地址以称为prefixes前缀的块分配
- 前缀由网络部分决定
- 有地址在边界上对齐
- 书面地址/长度，例如18.0.31.0/24
IP地址举例：与主机（202.194.196.80，子网掩码：255.255.240.0） 在同一个网络内的其它主机的IP地址范围是什么？
思路：这个网络内的主机的IP地址具有相同的网络号，主机号任意配置。
第一步：首先计算主机所在网络的网络号。使用已知主机的IP地址和子网掩码按位与即可。
第二步：主机号从全0到全1。最后可以去掉有特殊意义的主机位全0和全1。
子网掩码：255.255.11110000.00000000【有连续8+8+4=20位1】
主机：202.194.11000100.80
可以得到最小的网络号：202.194.192.0（202.194.11000000.0）
最大的网络号：202.194.207.255（202.194.11001111.255）
得到IP地址范围为（因为是IP地址范围，所以不包含全0和全1）：202.194.192.1~202.194.207.254
子网、子网划分
当一个网络规模较大时（网络号较短、主机号较长，能够容纳很多的主机），根据需要，可以进一步将这个网络划分为多个子网。
在内部将一个网络块分成几个部分供多个内部网络使用，但对外部世界仍然像单个网络一样。这就是所谓的子网划分（subnetting），分割一个大型网络得到的一系列结果网络（比如以太网〉称为子网（subnet）。
子网划分方法：从主机位的最高位置根据需要拿出一位或几位作为子网的编号。划分的原则是每个划分后的子网必须具有相同的网络号，并且主机空间满足子网要求。（与后面的CIDR相似）
一个网络划分为多个子网时，需要路由器的支持，路由器的一个接口作为对外接口与外界相连，作为整个网络的代表；其它接口作为对内接口，分别对应不同的子网。
从外部看起来，还是一个网络。从内部，区分不同的网络。
实现上，其它路由器只保留最初的网络表项；只有内部路由器，保留多个子网的表项。这样的方式，使得每个网络（组织）内部的划分不影响外面的其它节点。
子网划分举例：见下图
第一步：根据每个子网规模需求，为其确定子网；
第二部：在内部路由器上填上相应的表项。
子网划分后的路由分析。
子网划分IP前缀以帮助管理，看起来像是网络外的单个前缀
IP地址：
- 子网部分（高位比特）
- 主机部分（低位）
什么是子网？
- 具有相同IP地址子网部分的设备接口
- 可以在没有路由器干预的情况下物理地相互连接
当一个IP数据包到达主路由器，路由器如何知道应该将它转发到哪个子网？
当数据包到达时，路由器会查看该数据包的目标地址，井检查它属于哪个子网。具体做法是：路由器把数据包的目标地址与每个子网的掩码进行 AND 操作，看结果是否对应于某个前缀。
CIDR(无类域间路由)
CIDR、地址聚合技术
CIDR: Classless InterDomain Routing 无类域间路由
为了进一步减少路由表项，可以将地理位置相同的网络聚合成一个更大的网络。使得其它位置的路由器能够使用一个（或几个）路由表项为这些网络进行数据转发。
聚合的原理与子网划分类似。
从伦敦几个大学申请IP地址开始。
聚合后的路由表项和路由过程。
最长前缀匹配。如果有一个分组与多个路由表项匹配，则按最长匹配转发。
聚合将多个IP前缀连接到一个更大的前缀中，以减少路由表的大小
最长匹配前缀（longest matching prefix ）
CIDR的工作原理：当一个数据包到达时，路由器扫描路由表以确定目的地是否在前缀的地址块内。有可能多个具有不同前缀的表项得到匹配，在这种情况下，使用具有最长前缀的表项，具体方法
- 计算每个prefix对应的子网掩码
- 每个子网掩码和数据包ip地址进行与操作对比prefix
- 多个match选择子prefix长的选项
分类和特殊寻址
A：128个网络，每个网络1600万台机器；
B：16384个网络，每个网络65536台机器；
C：200万个网络，256台机器
NAT－网络地址转换
NAT
网络地址转换协议，在网络内部使用私有地址，在网络外部使用公有地址。当一个节点需要向外网发送数据时，将内网的私有IP地址转换为公有IP地址，并将端口号映射为新的端口号。当接受一个数据时，通过映射关系查找对应的私有IP地址及传输层端口号，重新封装传递。
5.6.3 IPv6协议
它的主要目标是：
( 1 ）即使地址空间的分配效率不高，也能支持几十亿台主机。
(2）降低路由表的大小。
(3 ）简化协议，使路由器更快速地处理数据包。
(4）提供更好的安全（认证和隐私）。
(5 ）更加关注服务类型，特别是针对实时数据。
(6）辅助指定范围内的组播。
(7）主机漫游时无须改变地址。
(8 ）允许协议向未来演进。
(9 ）允许新老协议共存多年。
主要的IPv6头
- 区分服务（Differentiated services，最初称为流量类别〉字段的用途主要是区分数据包的服务类别，这些数据包具有不同的实时传递需求。它主要被用在服务质量的区分服务体系中， 使用方式与IPv4数据包的同名字段一样。此外，最低2位用来发送显式拥塞指示，也与IPv4 的方式相同。
- 流标签（Flowlabel) 字段为源端和接收方提供了一种建立伪连接的方式，即源端和接收方把一组具有同样需求并希望得到网络同等对待的数据包打上标记。
- Next header: identify upper layer protocol for data
Next hearder指的当前头之后还有哪种扩展头；若是IP最后一个头，则定义了upper layer的协议（TCP/UDP）
- 校验和（Checksum）字段被去掉了，因为计算校验和会极大地降低性能。
- Options：被允许，但在header之外，由“Next Header”字段指示
- ICMPv6：ICMP的新版本
- 隧道：IPv4路由器之间的IPv4数据报中携带IPv6作为有效载荷
扩展头
巨型数据报Header格式
- Next header：接下来是哪个头
- 第二个字段（0），不包含起始的8个强制的字节以外当前逐跳扩展头有几个字节
- 第三个字段表明该选项定义的是数据报的长度（代码194），以4个字节为单
- Jumbo payload length：数据报payload的长度
路由扩展头：
- Next header和header extension length与定义上一个扩展头相同
- 路由类型给出了剩余部分的格式
- 剩余段数：记录地址列表中还有多少地址尚未被访问到
5.6.4 Internet控制协议
ICMP——Internet 控制消息协议
ICMP
是返回错误信息的IP的companion
ARP——地址解析协议
ARP工作过程
查找本地IP地址的以太网地址
ARP（地址解析协议）让节点从其IP地址中找到目标以太网地址
某一层的地址只在本层有效，网络层负责寻找路径，而真正实现消息传递的是链路层，所以要实现两层地址之间的映射。
即关键在于已知源IP、源MAC和目的IP的情况下怎样获取目的MAC
具体例子如上图所示，有两个/24的网络（左侧为CS网络，右侧为EE网络），这两个局域网通过一个IP路由器相连。以太网的每台机器和路由器上的每个接口都有一个唯一的以太网地址，E1~E6。
1. （同一子网的消息传递）主机1用户给主机2用户发送数据包
① 根据已知域名找到主机2的IP（由DNS系统返回IP地址）
② 主机 1 发送一个广播包到以太网络上请求拥有 IP 地址192.32.6.5.5 的主机。该广播包将会到达 cs 网络上的每一台主机，并且每台主机都会检查自己的IP地址。只有主机2会用自己的以太网地址 (E2)作为应答。通过这种方式，主机1 得知IP 地址 192.32.65.5 是一台拥有以太网地址为E2的主机。
请求和获得应答两个过程所使用的协议称为地址解析协议 (ARP, Address Resolution Protocol）
2. （不同子网消息的传递）主机 1 给 EE 网络上的主机 4发送数据包
（1）主机 1 发现目标 IP 地址不在 cs 网络。同时它知道应该把所有这些网络外的流量发给路由器，该路由器称为默认网关（Defaultgateway）
按照惯例，默认网关具有网络上的最低地址（198.31.65.1 ）。
为了给路由器发送帧，主机 1 必须知道该路由器在cs 网络上的接口地址。因此，主机1 发送一个ARP广播报文，请求198.31.65.1 对应的以太网地址，从该广播报文的应答报文它获知所需的以太网地址为E3：然后用该地址给路由器发送帧。
如果路由器不知道主机4的以太网地址，它可以再次使用ARP。
（2）主机1不知道主机4在另一个子网上，仍然可以从主机1 发送一个数据包给主机4。解决办法是让cs 网络上的路由器回答针对主机4的ARP请求，并且以E3 作为响应。然后，路由器将收到发给192.32.63.8 的帧，并将该帧转发到 EE 网络。这个解决方案称为ARP代理（proxyARP）
在以太网上广播时，以太网帧的目的地址全为1，即FF-FF-FF-FF-FF-FF-FF
DHCP——动态主机配置协议
DHCP
动态主机配置协议（DHCP）是用于互联网协议（IP）网络上的主机的网络配置协议。
连接到IP网络的计算机必须先进行配置，然后才能与其他主机通信。
所需的最基本信息是IP地址、默认路由和路由前缀。
DHCP消除了网络管理员的手动任务。
它还提供了一个连接到网络的设备的中央数据库，并消除了重复的资源分配。
5.6.5 标签交换和MPLS
MPLS（多协议标签交换）沿着已建立的路径发送数据包；ISP可以用于QoS
在IP前添加一个MPLS header用于存储标签
MPLS header字段
- 共四个字节，四个字段。
- 标签存放索引用于标签交换
- QoS字段指明服务类型
- S字段涉及层次网络中叠加多个标签
- TTL字段表明还可以被转发几次
当数据包进入MPLS网络时根据IP地址添加标签，离开时去除标签
- 在MPLS网络中进行转发只使用标签信息
- MPLS可以转发IP数据包和非IP数据包（多协议）
- MPLS可以在一个数据包前添加多个标签，从而同时在多个标签层次上运行
5.6.6 OSPF一一内部网关路由协议
OSPF
OSPF 在一个自治系统内部计算路由
- 一个自治系统根据实际的链接情况可以抽象为一个带权值的有向图
- 路由器之间有双向链路，权值可能不同；广播网络到路由器双向，但网络到路由器权值为0（广播网络会把数据传递到每个出境口），路由器到局域网是单向的（局域网只有主机，无路由功能路径只能到达不能穿越）
“open”: publicly available（不属于任何一家公司私有）
Uses Link State algorithm （使用链路状态算法进行路由）
- LS packet dissemination（链路状态包扩散）
- Topology map at each node（在每个节点建立网络拓扑图）
- Route computation using Dijkstra’s algorithm（在网络拓扑图上运行最短路径算法）
OSPF广播包会为每一个和它临接的路由器携带一条信息
广播信息会通过泛洪算法扩散到整个自治系统
- OSPF的广播信息是通过IP数据包（而不是TCP或UDP）进行传递
OSPF是一个基于连接状态的路由方法
OSPF把一个大的网络（自治系统）分割为多个带编号的区域，这些区域都连接到骨干区域（或0号区域）
- AS内任何一个区域出发，通过骨干区域，都可以到达AS内部的任意另一个区域
- 两个在不同区域内的主机通信一定要通过骨干区域
- 连接到两个或以上区域的路由器叫做区域边界路由器（它必须是骨干区域的一部分？）
- 只有一个边界路由器通往区域外，叫做存根区域（stub area），存根区域不需要外部路由信息，因为只有一个路由选择。
- 通往其他AS的路由器是AS边界路由器
5.6.7 BGP一一外部网关路由协议
BGP
BGP计算相互连接的自治系统之间的路由
- BGP和OSPF最重要的区别是BGP还需要考虑各种网络背后组织的政策限制（比如，有的AS系统不希望转发跟它没有关系的数据包，美国发出的数据不能通过伊拉克）
通常的传输AS间的路由政策包括中转传输和对等传输
- 中转服务需要付费购买，对等传输的对等体双方都将获益（降低中转服务账单）
- 图中AS1可以为AS2和AS4之间的数据传递提供中转服务，AS3只会分别和AS2和AS4进行对等传输
BPG沿着政策允许的路由传递信息
- BGP是距离矢量协议的一种形式，但与域内距离矢量协议有很大区别
- BGP告知路由的方向（建立传输路由）的方向与数据的路径方向相反
- BGP告知路由信息包括前缀（目的地址，AS路径，下一跳路由器）
互联网AS间路由：BGP
a)BGP (Border Gateway Protocol): the de facto standard（实际使用的标准）
b)BGP给每个AS提供了方法去：
1.从相邻的AS获得子网的可到达信息
2.把可到达信息传递给AS内部所有路由器
3.根据可到达信息和政策决定一个好的路由
c)BGP还可以允许一个子网向互联网其他区域广播它的存在
为什么AS内和AS间路由不同？
Policy:
- Inter-AS: 网络管理者要控制自己的流量怎样路由，并且决定谁的路由可以通过自己的网络
- Intra-AS: 单一管理者完全控制一个AS，不需要考虑其他政策
- Scale: 使用层次路由来节省路由表的尺寸，减少路由表更新带来的流量
第六章 传输层
传输层提供应用进程之间的逻辑通信（即端到端的通信）。与网络层的区别是，网络层提供的是主机之间的逻辑通信。
6.2 传输协议的要素
传输协议与数据链路协议的关系
相似之处：差错控制、流量控制、顺序性
不同之处：
- 传输协议需要明确的地址
- 连接过程更加复杂（由于网络缓存带来的重复数据）
- 缓冲区使用方式(传输层同时存在多个连接，带宽变化大，不适用给每个连接固定数量缓冲区的方法)
6.2.1 寻址 Addressing
寻址
Transport layer adds TSAPs（传输服务访问点，或端口）
网络层类似的端点叫做网络服务端口（NSAP），如IP地址
一个应用使用一个TSAP，多个TSAP可以共享一个NSAP，每台主机只有一个IP address
TSAPs 是TCP/UDP的端口ports
端口号：动态分配；某些端口号为一些常用的应用固定使用，例如port 80一般用于web服务器
端口映射器：将服务名字解析为端口
- 找到一个给定服务名字（e.g. Bittorrent）相对应的TSAP地址
- 用户与端口映射器发送消息指定想要的服务名字
- 端口映射器返回相应的TSAP地址
- 一个新服务建立时，必须向端口映射器注册
初始连接协议（进程服务器）：代理不常使用的进程
- 服务器上存在很多不常使用的服务进程，保持活跃状态是一种浪费
- 每台希望提供服务的机器由进程服务器充当不频繁使用的服务器的代理
- 在同一个时间监听一组端口，等待连接请求的到来
- 一个用户发出连接请求，并制定TSAP地址
- 如果TSAP对应的服务不在活跃状态，则与进程服务器连接。
- 进程服务器收到请求，派生出被请求的服务器进程，允许该服务器进程继承与用户的现有连接。
6.2.2 连接建立
建立连接三次握手
需要解决的关键问题是怎样在数据包可能发生丢失损坏延迟或重复情况下依然保障传输的可靠性
- 不要把旧的或重复的packet当作新的
- 对于丢失los/损坏corruption使用ARQ（自动重传请求）和校验和
重点是避免重复的连接建立，连接中的重复数据可以通过滑动窗口避免。
- 不能在【2T（T为数据包最大生存期） = 240secs】内使用sequence number两次
- 三次握手机制（three-way handshake）
(a) 主机1发起连接请求时的正常建立过程：
①主机 1选择一个序号x，并且发送一个包含x的CONNECTIONREQUEST段给主机2。
②主机2 回应一个ACK段作为对x 的确认，并且宣告它自己的初始序号y。
③最后，主机 1 在它发送的第一个数据段中，对主机2选择的初始序号进行确认。
(b) 出现延迟的重复控制段时三次握手协议
(c) 延迟的CONNECTION阻QUEST和ACK 同时出现在网络中
如何选取序号？
考试概率不大，但要搞明白
当建立一个连接时，时钟的低k位【选择低位：变化快，可以很快产生新的序号】被用于同样是k位的初始序号。因此每个连接都从一个完全不同的初始序号开始对它的段进行编号。序号空间应该足够大，以便当序号绕回时，原先那些具有老序号的段都已经消失。时间和初始序号之间的线性关系如图(a)，禁止区域显示了段序号非法使用的对应时间。
程序发出去的段，如果其序号恰好落在禁止区域，那么它可能被延迟，因为他会假冒将在之后发出的具有相同序号的段。例如，如果主机在70秒时崩溃并重新启动，它将初始序号，基于它崩溃后的时钟，因此主机不可能启用一个位于禁止区域的较低序号。一旦双方的传输实体已经统一了初始序号，则可用任何一个滑动窗口协议来控制数据流的传输。滑动窗口协议将发现并丢弃早已接收到到重复数据包。事实上，初始序号曲线（图中的粗线）并不是线性的，而是一条梯状线（想象一下相似的分段函数），因为时钟是离散前进的。
为了防止序号进入禁止区域，我们必须兼顾两个方面。协议可能以两种不同方式遇到麻烦。①如果一台主机在一个新打开的连接上发送得太快，则实际序号与时间的曲线可能比初始序号与时间的曲线还要陡，导致序号进入禁止（即数据包被延迟）。为了防止这种情况出现，每个连接上的最大数据速率是每个时钟滴答一次(单位时间)发送一段。这同时也意味着在机器崩溃并重启之后，传输实体必须等待时钟滴答，才能打开一个新的连接，以免同样的序号被使用两次。这两点都倾向于使用短的时钟滴答（1微秒甚至更短）。但是相对序号来说时钟不能滴答得太快。假设时钟速度为C（每滴答一次一段），序号空间大小为S（一个序号一段），则有S/C>T（S/C即滴答完一个S所用的时间，表达式也即一个T时间不能使用完S个序号），才能使得序号不至于回绕得太快（即导致序号进入禁止区域）。
由于发送速度太快而造成由下方往上进入禁止区域并不是带来麻烦的唯一情形，从图b可以看出，如果任何以低于时钟频率的数据率发送（图中的阴影区域向下倾斜，可以想象极端情形，比如阴影部分贴近x轴，那么就会与之后的阴影发生重叠），实际使用的序号与时间之间的曲线最终会从左边进入到禁止区域中。实际序号曲线的斜度越大，则这种事件发生的越晚，应该限制连接序号递增的速度不能太慢。
6.2.3 连接释放
释放连接三次握手
非对称
非对称释放连接是电话系统的工作方式：当一方挂机后，连接就被中断了。
不对称释放（当一侧断开连接时）是突然的，可能会丢失数据。
对称
对称释放连接是把连接看成两个独立的单向连接，要求单独释放每一个单向连接。
难点在于两个分布式实体需要达成一个共识（确定两方都要断开连接）
类似三次握手：断开请求发送方收到确认后即可断开连接，并返回确认。请求接收方收到请求后回确认，在规定时间内收不到确认也会断开连接
两军对垒问题（two－army problem）可以证明不存在安全的通过 N 次握手实现对称式连接释放的方法
这个协议不总能正确地工作
正常情况下，一个用户发送一个DR (DISCONNECTION QUEST）段来启动释放连接过程。
当该段到达对方，接收端也发回一个DR段，并启动一个计时器，设置计时器的目的是为了防止它的DR丢失。
当这个DR到达时，最初的发送端发回一个ACK段，并且释放连接。最后，当ACK返回后，接收端也释放连接。
三次握手法释放连接的错误情况：
(a) 最后一个ACK丢失：可以使用计时器来补救。当计时器超时，无论如何连接都被释放
(b) 响应丢失（第二个DR被丢失的情形。发起释放连接的用户接收不到期望的响应，所以它将超时，于是再次尝试释放连接）
(c) 响应和随后的DR都丢失（发送端所有重传DR的尝试都失败，经过N次尝试，发送端放弃了，并且释放连接。同时，接收端超时，退出连接）
6.2.4 差错控制和流量控制
流控制和缓冲
与第三章学的类似
差错控制确保数据传输具备所需的可靠性，通常指所有的数据均被无差错地传送到目的地。流量控制是防止快速发送端淹没慢速接收端。流量控制不考虑子网，仅考虑端到端，拥塞控制要考虑整个收发子网的情况。
发送端窗口大小>（网络每秒钟能够处理c个段，往返时间是r）
对于buffer的使用与数据链路层不同：
(a) 如果段长度的差异范围很大，如果将缓冲区设置成最大可能的段长，那么当短数据包到来时就会浪费空间：如果将缓冲区设置成比最大的段要小，则长的段就需要多个缓冲区，从而带来额外的复杂性。
(b) 大小可变的缓冲区，优点是能获得更好的内存利用率，付出的代价是缓冲区的管理更加复杂。
(c) 为每个连接使用一个大的循环缓冲区：
6.2.5 多路复用
6.2.6 崩溃恢复
传输层恢复失败是因为 A(ck) / W(rite) 不是同时发生
6.3 拥塞控制 Congestion Control
拥塞控制算法的目标：一个好的拥塞控制算法应该能够提供理想的带宽分配
- 有效：能够充分利用网络的可用带宽
- 公平：公平对待整个竞争的传输实体
- 收敛：能够快速收敛到公平有效的带宽分配上
拥塞控制算法的实现：通过调整发送速率，获得一个理想的带宽分配
- 流量控制：能够反映接收方缓存能力（已讲）
- 拥塞控制：能够反映网络传输能力
- 依赖于网络返回的反馈形式（显示、隐式，精确、不精确）
6.4 Internet传输协议：UDP
UDP
6.4.1 UDP 用户数据协议
User Datagram Protocol
UDP 为应用程序提供了一种无需建立连接就可发送封装的 IP 数据报的方法。UDP传输的段（Segment）由8字节的头和有效载荷字段构成
- Source port：源端口号；Destination port：目标端口号；即传输层端口地址TSAP，共16位
- UDP length规定UDP数据包长度，最大65515（为什么？ 65535-20）
- UDP checksum（可选）：校验头，数据和一个概念性的IP伪头
IP伪头用于UDP协议里的校验和的计算，有助于发现错误的数据包，但是这种做法违反了协议的分层原则（IP是网络层）
UDP协议不做的事情：
- UDP没有流量控制、拥塞控制、没有重传机制
- 所有以上的功能交给应用层解决
UDP做的事情：
- 提供一个与IP协议的接口
- 通过多个端口号提供复用多个进程的功能
- 端到端的错误检测
6.5 TCP
6.5.1 TCP
传输控制协议（TCP，Transmission Control Protocol）是为了在不可靠的互联网上提供可靠的端到端字节流而专门设计的一个传输协议。
TCP协议的设计目标是能够动态的适应互联网异构特性
每台支持TCP的机器都有一个TCP传输实体，TCP实体可以是一个库过程、一个用户进程或者内核的一部分。
TCP实体管理TCP流以及与IP层之间的接口
TCP传输实体接收用户数据流，分割成64KB的分段
TCP负责足够快的发送数据报，充分使用网络容量，又不能引起网络拥塞。
TCP要进行重传并且保证递交的数据报在正确的顺序。
6.5.2 TCP服务模型
TCP服务模型
TCP提供可靠的端到端字节流服务。发送端和接收端创建套接字（Socket），套接字编号包括32位IP地址和16位端口号
1024以下的端口号保留，用作某些知名的服务，知名端口
一个TCP连接就是一个字节流，而不是消息流。端到端之间不保留消息的边界。
6.5.3 TCP协议
TCP协议
TCP的一个关键特征是：TCP连接上的每个字节都有它独有的32位序号（按照字节流传输）。
发送端和接收端的TCP实体以段的形式交换数据。
- TCP段由1个固定的20字节的头以及随后0个或多个数据字节构成。TCP软件决定了段的大小。
- TCP软件可以把多个写操作的数据积累起来，放到一个段中发送，也可以把一次写操作中的数据分割成多段发送
- 有两个因素限制了段的长度： ① 包括在TCP头在内的每个段，必须适合IP的65515个字节的有效载荷的要求 ② 要考虑每个网络的最大传输单元（MTU, maximum transfer unit），如以太网的1500字节
- TCP 实体使用的基本协议是具有动态窗口大小的滑动窗口协议。当发送端传送一段时，它启动一个计时器。当该段到达接收方时，接收端的TCP实体返回一个携带了确认号和剩余窗口大小的段（如果有数据要发送的话，则包含数据，否则就不包含数据〉，并且确认号的值等于接收端期望接收的下一个序号。如果发送端的计时器在确认段到达之前超时，则发送端再次发送原来的段。
6.5.4 TCP段的头
每个段的起始部分是一个固定格式的20宇节头。固定的头部之后可能有头的选项。如果该数据段有数据部分的话，那么在选项之后是最多可达
65 535-20-20=65 495 个字节的数据，这里的第一个 20 是指IP 头，第二个20指TCP 头。
source port，destination port（源端口，目标端口）
序列号（Sequence number），表示此次发送数据的第一个字节的编号
确认号（Acknowledge number），表示下次想要接收数据的第一个字节的编号。
TCP header length：TCP头长度；
CWR，ECE：与显式拥塞通知（ECN）相关
URG：紧急指针；Urgent pointer指向从当前序号开始找到紧急数据的字节偏移量（置 1 表示使用了紧急指针）
ACK：1表示确认号字段有效；
PSH：1表示这是被推送PUSH的数据；
RST：被用于重置一个已经混乱的连接(一般而言，如果得到的数据段被设置了 RST 位，那说明你这一端有了问题)
SYN 被用于建立连接过程。在连接请求中， SYN=1 和ACK=0表示该段没有使用捎带确认字段。但是，连接应答捎带了一个确认，因此SYN=1和ACK=1。
FIN用于释放连接；
win size：滑动窗口大小，表示这个 TCP 数据段发送方当前可用的缓冲区大小，表示的是这一方的接收能力。
校验和（Checksum），它校验的范围包括TCP数据段的头部、数据以及伪 TCP 头
options必须是32位的倍数
【综合题中的注意事项】
1. 确认号-初始数据号=已经确认收到的字节数
2. 分组的标识字段用来分辨2个不同的IP分组在分片之前是否是同一个IP分组
6.5.5 TCP连接建立
TCP连接建立
TCP 使用了三次握手法来建立连接（见6.2.2节）
三次握手的过程如下：
1）客户端向服务端发送SYN包，其中SYN标志位被置为1，表示客户端请求建立连接。序列号Seq=x
2）服务端接收到SYN包后，向客户端发送一个SYN/ACK包，其中SYN和ACK标志位都被置为1，表示服务端已经接收到客户端的连接请求，并准备好建立连接。序列号Seq=y, 确认号Ack=x+1（表示收到客户端的序号
Seq并将其值加1作为自己确认号Ack的值）3）客户端接收到服务端的SYN/ACK包后，向服务端发送一个ACK包，其中ACK标志位被置为1，表示客户端确认服务端的SYN/ACK包已收到。序列号Seq=x+1（表示收到服务器端的确认号
Ack，并将其值作为自己的序号值）, 确认号Ack=y+1（表示收到服务器端序号seq，并将其值加1作为自己的确认号Ack的值）通过三次握手协议，客户端和服务端都确认了彼此的身份，并同意建立连接，从而可以开始传输数据。
6.5.6 TCP连接释放
TCP连接释放
释放连接的三次握手（四次挥手）过程：
1）客户端（主动关闭连接的一方）向服务端（被动方）发送一个FIN包，其中FIN标志位被置为1，表示客户端不再发送数据。序列号Seq=u
2）服务端接收到FIN包后，向客户端发送一个ACK包，其中ACK标志位被置为1，表示服务端已经接收到客户端的FIN包。序列号Seq=v，确认号Ack=u+1
3）当服务端不再发送数据时，服务端向客户端发送一个FIN包，其中FIN标志位被置为1，表示服务端不再发送数据。序列号Seq=w，确认号Ack=u+1
4）客户端接收到FIN包后，向服务端发送一个ACK包，其中ACK标志位被置为1，表示客户端已经接收到服务端的FIN包。序列号Seq=u+1，确认号Ack=w+1
通过四次挥手协议，客户端和服务端都确认了彼此的关闭请求，并释放了TCP连接。
6.5.8 TCP滑动窗口
TCP滑动窗口协议
在TCP中，发送方维护一个发送窗口，接收方则会维护一个接收窗口，它们是一个连续的字节序列，表示发送方可以发送的数据范围大小。窗口由两个参数定义：窗口的起始字节和窗口的大小。
工作原理：
发送方和接收方分别维护着发送窗口和接收窗口，发送窗口表示发送方可以发送的数据的范围，接收窗口表示接收方可以缓冲的字节数。
① 在建立TCP连接时，确定初始的拥塞窗口大小。
② 当发送方发送数据包后并接收到接收方传来的ACK确认应答后，将发送窗口向前滑动，这样，发送方可以继续发送新的数据。
③ 接收方更新、通告接收窗口大小：接收方在根据已经成功接收的字节数和初始窗口大小计算可用的接收窗口大小，并将新的接收窗口的大小通过TCP 报文段中的窗口大小字段通告给发送方。这个值告诉发送方接收方的当前可用缓冲区空间。
④ 动态调整窗口大小：接收方通过ACK确认号通知发送方已成功接收的数据。发送方可以根据接收方通告的窗口大小进行数据发送控制——如果接收方的窗口变大，发送方可以发送更多的数据；如果接收方的窗口变小，发送方需要适应减少的窗口大小。
⑥ 流量控制：通过滑动窗口机制，接收方可以动态调整窗口大小以限制发送方的数据发送速率。接收方通过通告窗口大小，告知发送方自己的可用缓冲区空间。发送方根据接收方的窗口大小调整发送速率，确保不会超出接收方的处理能力。
Nagle算法
尽管通过延迟确认减少了接收端给予网络的负载，但是发送端发送多个小数据包的工作方式仍然非常低效（比如， 41 字节的数据包只包含 1 个字节的数据）。避免这种用法的一种办法是采用Nagle算法：
当数据每次以很少量方式进入到发送端时，发送端只是发送第一次到达的数据字节，然后将其余后面到达的字节缓冲起来，直到发送出去的那个数据包被确认；然后将所有缓冲的字节放在一个TCP段中发送出去，并且继续开始缓冲字节，直到下一个段被确认。
这就是说，任何时候只有第一个发送的数据包是小数据包。如果在一个来回时间内应用程序发送了许多数据，那么Nagle 算法可以将这些数据放置在一个段中发送，由此大大地减少所需的带宽。另外，如果应用传递来的数据足够多，多到可以填满一个最大数据段，则该算法也允许发送一个新的段。
愚笨窗口综合症（sillywindow syndrome)
降低TCP性能的另一个问题是低能窗口综合症（sillywindow syndrome) 。当数据以大块形式被传递给发送端TCP实体，但是接收端的交互式应用每次仅读取一个字节数据的时候，这个问题就会发生。
初始时，接收端的TCP 缓冲区为满，发送端知道这一点（即它有一个大小为0的窗口〉。然后，交互式应用从TCP 流中读取一个字符，这个动作使得接收端的TCP欣喜若狂，它立刻发送一个窗口更新段给发送端，告诉它现在可以发送 1个字节过来。发送端很感激，立即发送1个字节。现在缓冲区又满了，所以，接收端对这 1 字节的数据段进行确认，同时设置窗口大小为 0。这种行为可能会永久地持续下去。
解决方法为：禁止接收端发送只有 1 个字节的窗口更新段。它强制接收端必须等待一段时间，直到有了一定数量的可用空间之后再通告给对方。特别是，只有当接收端能够处理它在建立连接时宣告的最大数据段，或者它的缓冲区一半为空时（相当于两者之中取较小的值〉，它才发送窗口更新段。
6.5.10 TCP拥塞控制
TCP拥塞控制
当提供给任何网络的负载超过它的处理能力时，拥塞便会产生。
TCP 维持一个拥塞窗口，窗口大小是任何时候发送端可以往网络发送的字节数。相应的速率则是窗口大小除以连接的往返时间。
流量控制窗口，该窗口指出了接收端可以缓冲的字节数。（流量控制窗口就是接收端窗口）
slow start
一开始将拥塞窗口大小设为1，然后成倍增加(指数级)拥塞窗口的大小，直到到达所设定的阈值或发生网络拥塞。当达到阈值时，慢启动结束，TCP进入拥塞避免阶段，此时拥塞窗口大小变为线性增长；当网络出现拥塞时，TCP慢启动会减缓发送速度，从而避免网络过载和拥塞的发生。
第七章 应用层
7.1 DNS——域名系统
DNS
简要地说， DNS 的使用方法如下所述。为了将一个域名映射成IP地址，应用程序调用一个名为解析器（resolver）的库程序，并将名字作为参数传递给此程序。
① 解析器向本地DNS服务器发送一个包含该名字的请求报文；
② 本地DNS服务器查询该名字，并且返回一个包含该名字对应IP地址的响应报文给解析器，然后解析器再将IP地址返回给调用方。
查询报文和响应报文都作为UDP 数据包发送。有了IP地址以后，应用程序就可以与目标主机建立一个TCP连接，或者给它发送UDP数据包。
7.1.1 DNS 名字空间
DNS namespace是一个分层的结构
7.1.2 域名资源记录
无论是只有一台主机的域还是顶级域，每个域都有一组与它相关联的资源记录(resource record）。这些记录组成了 DNS 数据库。
7.1.3 域名服务器
DNS名字空间被划分为一些不重叠的区域(zones)
区域边界应该放置在区域中的什么位置由该区域的管理员来决定。这个决定在很大程度上取决于需要在哪里使用多少个名字服务器。
查询一个名字和找出其对应地址的过程称为域名解析（name resolution），是通过DNS协议完成的。
域名解析：
- 计算机请求本地域名服务器
- 本地域名服务器请求根域名服务器
- 根域名服务器返回较低层次的域名服务器
- 继续下面的区域直到域名服务器可以应答
根域名服务器：最高层次，知道所有顶级域名服务器的IP地址，管辖顶级域，当本地域名服务器无法自己解析时，就会求助根域名服务器，根域名服务器不直接告诉它IP地址，而是告诉本地域名服务器下一步应该去找哪个顶级域名服务器
没有根域名服务器，就无法进行域外的名字解析。建立根域名服务器是战略高点。
顶级域名服务器：负责管理在该顶级域名服务器下注册的所有二级域名，包含一个行业或一个国家所有子域的有关信息，给出子域的域名服务器的权威记录。包含通用和国家、地区两类。
本地域名服务器：每个ISP都拥有一个本地域名服务器，当一台主机发出DNS请求时，这个查询请求报文就发送给本地DNS。
域名服务器包含域内所有子域的有关信息。
DNS协议：
在UDP端口53上运行，重新传输丢失的消息
缓存名称服务器答案以获得更好的性能
7.3 万维网 World Wide Web
7.3.4 HTTP 超文本传输协议
HTTP (应用层常见的协议)
HTTP 是一个简单的请求．响应协议，它通常运行在TCP之上。它指定了客户端可能发送给服务器什么样的消息以及得到什么样的响应。请求和响应消息的头以ASCII码形式给出，就像SMTP一样：而消息内容则具有一个类似MIME的格式，也像SMTP一样。
HTTP协议支持流水线请求，支持缓存。
HTTP使用持续连接（persistent connection）来提升性能。
GET: 请求服务器发送页面
HEAD：只请求页面的头部
PUT：存储一个页面
POST：也携带一个URL，上载数据到服务器；
Trace：用于调试，指示服务器发回收到的请求；
Connect：通过一个中间设备（比如Web缓存）与Web服务器建立一个连接。
Options: 客户向服务器查询一个页面并且获得可用于该页面的方法和头
每个请求都会得到一个响应，每个响应由一个状态行及可能的附加消息（例如全部或者部分Web页面）组成；状态行包括一个3位数字的状态码，指明请求是否被满足，如果没被满足，原因是什么。
用户发送请求，检查缓存中内容是否过期，如果过期了则向服务器发送Conditional GET，如果内容改变了，服务器会给出相应；如果未改变，则可以继续从缓存cache中获取响应内容。