计网复习日记

复习《计算机通信网络》。

[TOC]

计算机通信网

计算机通信网三要素

两台以上自治计算机互联
通道（通信子系统）连接
通信协议

计算机通信网的组成

计算机的通信子系统是核心的要素
数据通信系统为计算机之间的信息交互提供了传输媒介，并提供可靠的数据传送能力

通信子网和资源子网

计算机通信网就是一个由通信子网承载的、传输和共享资源子网的各类信息的系统。

通信子网负责数据的无差错和有序传递，其处理功能包括差错控制、流量控制、路由选择、网络互连等。
资源子网是计算机通信的本地系统环境，包括主机、终端和应用程序等，主要功能是：用户资源配置、数据的处理和管理、软件和硬件共享以及负载均衡等。

主要网络类型

局域网（LAN）：单位内部使用的高速宽带网络，分为共享型和交换型。
城域网（MAN）：与LAN类似
广域网（WAN）：使用分组交换和路由技术
互联网（internet）：通过WAN连接起来的LAN集合，中间通过网关使不同网络兼容。

网络软件及协议体系结构

通信协议

定义：相互通信的双方（或多方）对如何进行信息交换所必须遵守的一整套规则。

作用：完成计算机之间有序的信息交换。

建立连接要遵守的规则：

要保证在源-宿点之间存在物理的传输资源。
多路接入技术必须与所使用的设备配合，执行某种协议
差错处理功能的实现需要由两个端设备之间运行的协议来处理（ARQ）
必须保证信息到达正确的目的地，需要寻址和路由
端节点或交换节点上存储所收到的信息，直至等待这些信息得到服务或再转发出去。这需要协议来协调设备之间的动作
流量控制，防止缓冲器溢出，防止拥挤
保证接入通路能与用户的特性协调一致。如：消息格式、字符编码等。

协议分类

面向应用的协议：TCP/IP：FTP、TELNET、SMTP
系统到系统的协议：端系统特定应用进程之间
端到端协议：TCP、UDP
其他网内协议：流量控制、寻址和路由协议
点到点协议：直接相连的节点之间。HDLC和PPP
网络接入协议：MAC
网间互联协议：不同网络用户的寻址、异构网络协议转换

协议三要素

语法
语义
时序

分层的协议体系结构

将庞大复杂的协议分层不同的层次。各层完成不同的功能。

分层的基本思想：把整套的协议体系分成一些小块（层），下一层对它的上一层提供服务。
分层的基本原则：定义每一层向上一层提供的服务，以保证每层功能的相互独立，但不规定如何完成这些服务。

OSI/RM

物理层：bit
数据链路层：帧
网络层：分组
（通信子网边界）
传输层：报文(TPDU) 高三层与低三层的接口，第一个端到端的层次。
（资源子网边界）
会话层：SPDU
表示层：PPDU
应用层：APDU

各层功能

物理层
- 提供建立、维护和释放物理链路所需的机械、电气功能和规程等特性；
- 通过传输介质进行数据流(比特流)的物理传输、故障监测和物理层管理；
- 从数据链路层接收帧，将比特流转换成底层物理介质上的信号。
数据链路层
- 在物理链路的两端之间传输数据；
- 在网络层实体间提供数据传输功能和控制；
- 提供数据的流量控制；
- 检测和纠正物理链路产生的差错
- 格式化的消息称为帧
网络层
- 负责端到端的数据的路由或交换，为透明地传输数据建立连接
- 寻址并解决与数据在异构网络间传输相关的所有问题
- 使用上面的传输层和下面的数据链路层的功能；
- 格式化的消息称为分组
传输层
- 提供无差错的数据传输；
- 接收来自会话层的数据，如果需要，将数据分割成更小的分组，向网络层传送分组并确保分组完整和正确到达它们的目的地；
- 在系统之间提供可靠的透明的数据传输,提供端到端的错误恢复和流量控制
会话层
- 提供节点之间通信过程的协调
- 负责执行会话规则（如：连接是否允许半双工或全双工通信？）、同步数据流以及当故障发生时重新建立连接
- 使用上面的表示层和下面的传输层的功能。
表示层
- 提供数据格式、变换和编码转换；
- 涉及正在传输数据的语法和语义；
- 将消息以合适电子传输的格式编码；
- 执行该层的数据压缩和加密；
- 从应用层接收消息，转换格式，并传送到会话层，该层常合并在应用层中
应用层
- 包括各种协议，它们定义了具体的面向拥护的应用：如电子邮件、文件传输和虚拟终端等；

TCP/IP

应用层（application）：TELNET FTP SMTP DNS NNTP HTTP
传输层（transport）： TCP UDP NVP
网际层（internet）： IP ICMP ARP RARP
网络接口（network interface）

协议分层的基本原理

分层原理

分层是一种构造技术
- 将网络看成一些逻辑上相连的层次组成
- 每层在下层提供的服务上增加一定的功能，然后再为上层提供服务
- 分层能将一个完整的问题，分成许多较小的问题
保证层次间独立
- 只规定提供的服务，而与如何完成无关
- 用户只需知道功能，不必知道内部细节

服务分类

面向连接服务

需要连接建立、数据传送、连接释放三个阶段
数据交换前必须建立连接，结束后必须释放连接
传送数据时，顺序传送

无连接服务

不需要事先建立连接
不需要两个实体同时活跃
不能防止报文丢失、失序，是不可靠服务

N层

N层的SAP（服务访问点）是N+1层访问N层服务的地方
一个(N)SAP只能被一个N实体使用，并且只能被一个N+1实体使用
一个N/N+1实体可以使用多个(N)SAP
(N)SAP的标识符称为(N)地址，可以唯一地标识与某个(N+1)实体相连的一个特定(N)SAP。

N服务与N协议

服务是上下关系，是各层向上层提供的原语
协议是水平关系，同层对等实体间通信
服务和协议是完全分离的

连接及其操作

(N)连接

两个或多个对等N+1实体之间交换数据时，必须在N层内使用N协议在N+1实体之间建立联系。
在同一对SAP之间也可以存在若干条连接。这些连接彼此之间的区分是通过连接端点来标识的。
在一个(N)SAP上的一条连接的端点称为(N)连接端点，(N)CEP。

连接释放

有序释放
常规释放
异常释放

连接复用和分用

连接的映射关系
- 一对一映射：每条N连接建立在对应得一条N-1连接上
- 多对一映射（复用）：若干条N连接建立在同一条N-1连接上
- 一对多映射（分用）：一条N连接建立在若干条N-1连接上, N连接的通信量可以分解到若干条N-1连接上.
复用的目的
提高使用效率,节省费用;在只有一条N-1连接时,提供多条N连接.
分用的目的
在有多条N-1连接可用时,提高可靠性;提高吞吐量和其他服务质量;利用廉价的多条N-1连接提高经济效益

PDU IDU SDU

(N)与(N)对等实体间
(N)PCI + (N)SDU = (N)PDU
(N)与(N-1)相邻层间
(N-1)ICI + (N-1)ID = (N-1)IDU

数据传送方式

张昌数据传送
加速数据传送
特权数据传送

数据单元分合

分段和合段 (N)PCI (N)SDU1 + (N)PCI (N)SDU2 -> (N)PCI (N)SDU
拼块和分块 (N)PCI (N)SDU (N)PCI (N)SDU
拼接和分割 (N)PDU + (N)PDU -> (N-1)SDU

服务原语

request
indication
response
confirm
无确认服务
request -> indication ->
确认服务
request -> indication ->
<- confirm <- response

数据传输相关概念

波特率比特率

波特率：每秒信号变化次数，码元速率
比特率：每秒传输的位数

信号分为V级，比特率=log2V*波特率

奈奎斯特定理

在假定的理想条件（无噪声）下，为了避免码间串扰，码元的传输速率的上限值。
在无噪声信道中，当带宽为W Hz时，
码元传输速率的上限值 = 2W Baud

香农定理

带宽受限且有高斯白噪声干扰的信道的极限、无差错的信息传输速率。
在噪声信道中，当带宽为W Hz，信噪比为S/N，则：
最大数据传输速率(b/s) = Wlog2(1+S/N)

基带传输宽带传输

基带传输：信号源产生的原始电信号称为基带信号，即将数字数据0、1直接用两种不同的电压表示，然后送到线路上去传输。
宽带传输：将基带信号进行调制后形成模拟信号，然后采用频分复用技术实现宽带传输。

信号编码技术

数模调制

调幅ASK(Amplitude Shift Keying)
调频FSK(Frequency Shift Keying)
调相PSK(Phase Shift Keying)
正交调相QPSK(Quadrature Phase Shift Keying)

数数编码

不归零编码：不能携带时钟信号，无法表示无数据传输。一个时钟周期表示1bit，一次采样得到1bit，效率最高
曼切斯特编码：低-高跳变为1。能携带时钟信号，且可表示没有数据传输。一个时钟周期表示1bit，2次采样得到1bit
差分曼切斯特编码：位中间跳变，位间也跳变，表示下一个bit为0。抗干扰性更强。
4B/5B编码：用5bit来表示4bit。至少有两个1，即保证在传输中信号码元至少发生两次跳变，以便接收端提取出时钟信号。

模数编码

脉冲编码调制PCM技术

模模调制

调幅AM (Amplitude Modulation)：载波的振幅随模拟数据的数值变化。
调频FM (Frequency Modulation)：载波的频率随模拟数据的数值变化。
调相PM (Phase Modulation)：载波的初始相位随模拟数据的数值变化。

信道复用

频分复用FDM(Frequency Division Multiplexing)
时分复用TDM(Time Division Multiplexing)
统计时分复用STDM(Statistic TDM)
波分复用 WDM(Wavelength Division Multiplexing)
码分复用 CDM(Code Division Multiplexing)
正交频分复用OFDM(Orthogonal Frequency Division Multiplexing)

数据交换技术

电路交换

指交换系统为通信的双方寻找并建立一条全程物理通路，以供双方传输信息，直到信息交换结束。

空分交换多级矩阵
时分交换

优点

数据传输时延小
对用户透明
吞吐量高
缺点：
必须有一个呼叫建立的过程（时延较大）
专供通信的双方使用，占用固定的带宽，信道带宽利用率低
存在呼叫损失现象
难以实施差错控制措施
难以适应计算机和各种终端传输速率不一致等情况
——不适合具有突发性的计算机数据传输

报文交换

数据的传输不需建立连接，数据的传输是一站一站往下送，所以数据中必须包含目的地址，并采用存储-转发（store-forward）机制

在数据传输前，不必建立端到端的连接
只要下一个节点空闲，即可传输
线路的利用率较高
数据中必须包含地址域
在数据传输过程中，除了信号传播的延时之外，还有存储和转发的延时，而且延时不可估计
每个中间站点都必须有足够大的缓存，但由于报文大小不定，所以缓存通常设置在硬盘中
报文交换的端到端时延
- 传输时延
- 传播时延
- 存储-转发时延
- 排队等待时间
- 存入中间节点的处理时间
- 从存储器送到输出链路的处理时间

分组交换

与报文交换相似，只是将报文分为若干个定长的分组，每个分组为一个子报文。
管道化 pipelining

每个分组中必须包含目的地址，并采用存储-转发机制。
收发顺序可能不同，需要重组

数据报（无连接方式）

每个分组独立处理，独自选择在网络中传输的路由。

虚电路方式（面向连接方式）

首先要建立传输路径，所有分组均在这个连接上进行传送，帧顺序和路径都是确定的。

分组中没有目的地址，只有虚电路号

快速分组交换

尽量简化底层对数据单元的操作，由端到端的高层协议保证——光纤
大大缩短分组长度——异步传输模式ATM

分组最佳长度

设报文的总长度为M(bit)，令nh(bit)为附加到每个分组的开销，用Kmax表示包括附加开销在内的最大分组长度。

以分组方式发送一个报文所必须传送的总比特数为
N = M + [M/(Kmax-nh)]nh
传送一个报文所需要的总时间T为第一个分组通过前面（j－1）条链路的时间加上整个报文通过最后一条链路的时间
T = ((j-1)Kmax + N)/R
运用求极值的常规方法，将上式对Kmax求导，并令导数等于零，于是得到分组最佳长度为
K = nh + 根号(E[M]*nh/(j-1))

数据链路层

需要数据链路层的理由

传输数据的信道是不可靠的（即不能保证所传的数据不产生差错），并且还需要对数据的发送端进行流量控制

要解决的问题

如何在有差错的线路上，进行无差错传输。

数据链路层协议定义了一条链路的两个结点间交换的数据单元格式，以及结点发送和接收数据单元的动作。

主要功能

对网络层提供服务接口，对网络层实体提供数据链路连接的建立、维持和释放
将bit流组装成帧frame
控制帧在物理链路上的传输帧的同步、传输差错、速率匹配

向网络层提供：

无应答无连接服务
应答式无连接服务
面向连接的服务

frame的构成

字符计数法
带字符填充的起始字符和终结字符法
- DLE STX
- DLE ETX
- DLE DLE
带位填充的起始/终结标志法

差错控制

反馈确认
超时机制
顺序编号

流量控制

协调发送速度与接受速度匹配
连续性ARQ中，必须对已发送出去但未被确认的数据帧的数目加以限制（浪费资源、附加的帧序号开销大）

滑动窗口式流量控制

发送窗口：任何时刻发送端都保持着一组序号，对应于在还没有收到对方确认的条件下最多允许发送的帧。
发送窗口的上界表示要还能发送的帧的最大序号，下界表示等待确认的帧的最小编号。发送窗口大小 = 上界 - 下界，大小可变；
发送端每发送一个帧，序号取下界值加1；每接收到一个正确响应帧，上界加1；
接收窗口：对应于一组允许（或期望）接收的帧。
接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的序号最小帧；
接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个响应帧，上界、下界都加1。接收窗口大小不变

差错检测和纠正

前向纠错FEC

接收端检测到接收信息有错后，通过一定的运算，确定差错的具体位置，并自动加以纠正。

汉明定理

用d表示码组的最小汉明距离

当码组用于检测错误时，设可检测e个位的错误，则
d >= e + 1
若码组用于纠错，设可纠错t个位的错误，则
d >= 2t+1
如果码组用于纠正t个错，同时检测e个错，则
d >= 2t+e+1

循环冗余码CRC

校验和（checksum）加在帧尾，使带校验和的帧的多项式能被G(x)除尽；收方接收时，用G(x)去除它，若有余数，则传输出错。
生成多项式

反馈重发ARQ

接收端检测到接收信息有错后，通过反馈信号要求发送端重发原信息，直到接收端肯定确认为止，从而达到纠正差错的目的。

肯定确认ACK
否定确认NAK
超时重发规定时间内未收到ACK/NAK

等待式ARQ

等待式ARQ方法为了获得通信的可靠性而牺牲了传输效率，过于浪费信道的有效带宽。

Ws = Wr = 1

回退N帧ARQ

发送端连续发送一系列信息帧，不等前帧确认便发下一帧。因此，连续重发请求方案把等待时间利用起来，传输效率大大提高。然而在实现上相应地需要更大的缓冲存储空间。

回退N帧ARQ会回退到错误帧开始重发

1 < Ws <= 2**n - 1 , Wr = 1

选择性重发ARQ

选择性重发ARQ只重发错误帧

Ws <= 2**n - 1 , Ws + Wr <= 2**n
Ws >= Wr

纠检混合的差错控制方式

接收端对少量的接收差错自动纠正，而超过纠正能力的差错则通过反馈重发的方法加以纠正。

点对点协议 PPP

面向字符的协议

a)初始状态
b)建立连接：建立成功到c)，否则到a)
c)选项协商：协商成功到d)，否则到g)
d)身份认证：认证成功到e)，否则到g)
e)配置网络：网络配置完后到f)
f)数据传输：数据传输完后到g)
g)释放链路：回到a)

PPP协议不提供纠错、流量控制、序号、多点线路

高级数据链路控制 HDLC

面向bit的同步通信协议

初始化
数据传输
断开连接

介质接入控制

广播信道分配问题

信道使用产生竞争时，分配信道使用权。
用来决定广播信道中信道分配的功能及协议属于数据链路层的子层，称作介质接入控制MAC(Medium Access Control)子层。

静态分配

频分多路复用（FDM）
时分多路复用（TDM）
波分多路复用（WDM）

动态分配

若干假设：

数据站模型
单信道假设
冲突重传
连续时间与时间分槽何时发送
载波侦听和无载波侦听能否发送

动态分配技术

查询技术

查询技术是常见的一种信道访问技术，该技术都需要一个中心控制站，中央控制站周期性地向各终端或工作站发送查询帧，各用户只有当被控制站查询时，才能发送信息。

传统查询：

roll-call
hub
在轻负载的情况下，效率较低
在重负载的情况下，将引入较长的时延

探查法：探查二叉树
（1）同时探查一组（两个或多个）站点。如果其中某个站点需发送数据，则它反馈以某种形式的信号；否则，系统就认为整个该组站点都是空闲的，直至下一次探查。
（2）将具有反馈信号的站点组（即其中有站点申请使用信道）分成两个子组，重复过程（1）。
（3）对于最终的探查（即组内只有一个站点），由控制站发送给该站点一个查询帧，使其可以发送数据。

自适应查询：探查+查询

随机接入：ALOHA

目的：解决信道的动态分配，基本思想可用于任何无协调关系的用户争用单一共享信道使用权的系统；

纯ALOHA

基本思想：当用户想要发送数据帧时，它就可以在任何时候发送。但是，不同用户发出的数据帧就有可能发生冲突。冲突的帧将被破坏，传输不成功，使吞吐量下降。

易受冲突时间2T
平均每个帧时产生S个新帧
帧发送的均值为G

S = G e-2G
Smax = 1/2e = 0.184

时隙ALOHA

在一个时隙内产生的新帧，将在下一个时隙开始处发送，冲突危险区为T
新帧的产生是随机的，但是不允许随机发送
在一个时隙的起点没有其它帧发送的概率为：P0 = e-G
S = G e-G
Smax = 1/e = 0.368
（0.37时隙为空，0.37时隙成功，0.26时隙冲突）
时隙ALOHA需要全网的同步机制，增加了复杂性

随机接入：CSMA

载波侦听多址接入，发送之前侦听信道，减少盲目性

非持续型
- 信道空闲则发送，忙则延迟一随机时长再侦听
- 限制信道利用率的进一步提高
p-持续型
- 信道空闲则以p概率发送，以1-p概率延迟一个时隙再侦听
- 随即延迟使吞吐特性变坏，但尽快发送和主动退避使其性能优于非持续型CSMA
1-持续型
- 空闲则发送
- 轻载性能好，重载时比持续型CSMA差，最大吞吐量只能达到0.53

0.01-持续>0.1持续>0.5持续>1持续>slotted-ALOHA>pure-ALOHA

CSMA/CD

发送前进行载波侦听，发送过程中侦听是否冲突，检测到冲突后及时中断发送。

冲突检测：

信号电平
过零点检测法（过零点将偏移）
自发自收

操作规程

竞争发送
- 发送前侦听总线，空则发送，否则等待
- 发送后侦听冲突检测，若有冲突则干预总线——继续发送异常帧，延迟等待
无冲突接收
- 检测到冲突后发送不完全帧（冲突加强）
- 接受站点收到后，处理错误信息

退避算法

就是让发生碰撞的站在停止发送数据后，不是立即再发送数据，而是推迟（这叫做退避）一个随机时间。具体做法是：
（1）确定基本退避时间，一般是取为争用期2 τ 。
（2）定义参数k，它等于重传次数，但k不超过10，即k=Min(重传次数，10)。
（3）从离散整数集合[0,1,2,…,(2k-1)]中随机地取出一个数，记为r。重传输所需的时间就是r倍的基本退避时间。
（4）当重传达16次仍不能成功时，则丢弃该帧，并向高层报告。

最短帧长

如果帧的第一个比特到达电缆的远端前帧已经发完，那么即使发生冲突也无法检测，因此帧发送时间应该大于 2τ；

10Mbps LAN，最大冲突检测时间为51.2微秒，最短帧长为64字节；
网络速度提高，最短帧长应增大或者站点间的距离要减小。

IEEE802标准

局域网的低三层

IEEE 802.1标准规定局域网的低三层。
（1）物理层：与OSI/RM的物理层相对应，但所采用的具体协议标准直接与传输介质有关。
（2）介质接入控制（MAC）层：具体管理通信实体接入信道而建立数据链路的控制过程。尽力而为的数据报服务
（3）逻辑链路控制（LLC）层：提供一个或多个服务访问点，以复用的形式建立多点—多点之间的数据通信连接，并包括寻址、差错控制、顺序控制和流量控制等功能。

LLC层向网络层提供多个服务访问点L-SAP。对同一个LLC可以提供多个MAC选择
MAC层向LLC层提供一个服务访问点M-SAP
物理层向MAC层也只需单一的服务访问点P-SAP
两个站点建立逻辑链路连接，需要两种地址：
- MAC物理地址，即某站在网络中的物理地址（48位网卡地址），由MAC帧负责传送；
- L-SAP地址，即进程在站中的地址，由LLC帧负责传送。
LLC层与局域网形态和传输介质无关
MAC层与局域网形态和传输介质直接相关

IEEE802协议

802.1 基本介绍和接口原语定义
802.2 逻辑链路控制（LLC）子层
802.3 采用CSMA/CD技术的局域网
802.4 采用令牌总线（Token Bus）技术的局域网
802.5 采用令牌环（Token Ring）技术的局域网

公用信道的分配方法

方法/系统	说明
纯ALOHA	在任何时候均非同步传输
时隙ALOHA	在定义恰当的时隙内随机传输
1－持续CSMA	标准的载波侦听多路访问
非持续CSMA	当侦听到信道忙时随机延迟
p－持续CSMA	CSMA，但持续概率为p
CSMA/CD	CSMA，但发生冲突时终止
以太网	采用CSMA/CD的局域网
令牌总线	在一条物理总线上的逻辑环
令牌环	在发送数据前必须获得令牌

无线局域网使用的CSMA/CA

带冲突避让的载波多路侦听CSMA/CA

无线局域网很难检测信道
任何站在完成发送后必须等待一段很短的时间才能发送下一帧，这段时间称为帧间间隔IFS(InterFrame Space)。
争用：当信道从忙转为空闲时，任何站在发送数据前，都要采用二进制后退算法减少发生冲突的概率。与以太网不一样的是第i次后退是从22+i个时隙中选取一个

网络层

网络层为一个网络连接的两个传输层实体间交换网络服务数据单元提供功能和规程的方法，它使传输层实体看不到下面资源的使用情况。

网络层是处理端到端传输的最低层，通信子网的最高层。

网络层解决的问题

路由选择
拥塞控制

向传输层提供的服务

面向连接的服务:将复杂的功能放在网络层(通信子网)
无连接服务:将复杂的功能放在传输层
通信子网提供的服务（面向连接或无连接）与通信子网结构（虚电路或数据报）没有必然联系。

网络层的两种实现方式 —— 数据报和虚电路

都属于分组交换，采用存储转发机制。

路由选择算法

路由选择与流量控制的关系

路由选择的时延反馈给流量控制，改变吞吐量

路由表

某节点路由表包括目的节点和下一节点
虚电路中的路由表使用虚电路号
从所有的源节点到一个给定的目的节点的最优路由的集合形成了一个以目的节点为根的树，称为汇集树；

路由选择算法

随机路由选择

随机选择出口转发，可能造成分组在通信子网中长期中转

洪泛路由选择

基本思想:把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。
优点：可靠性高，路径最短
主要问题:洪泛要产生大量重复包，浪费带宽。
解决措施:每个包头包含站点计数器，每经过一站计数器减1，为0时则丢弃该包；在每个节点上建立登记表，则数据包再次经过时丢弃

固定式路由选择（静态）

固定式单路由算法(绝对固定式路由选择)
- 每个节点都有一张人工计算得到的固定路由表。
- 优点是简单、实现方便，可选择正常情况下的最佳路由。
- 缺点是路由表不能联机修改，不能适应网络的业务量及拓扑变化。
固定式多路由算法（迂回式路由选择）
- 固定式多路由算法是任何一对节点之间有多条可选路由。
- 缺点是路由表不能联机修改。

动态路由选择

自适应路由选择方法是从路径和时延两方面考虑的：

孤立的自适应路由算法
- 选择路由时，仅仅孤立地依据本节点自身的当前运行状态（流量和排队）信息来决定路由，而与网络其他各节点的状态无关。
分布式自适应路由选择
- 在网络相邻节点之间，每经过一定时间相互交换一次状态信息，各节点根据相邻节点送来的状态信息来修改自己的路由表。
- 距离矢量路由算法
  - 每个路由器维护一张矢量表，表中列出了该节点到每个目的地已知的最佳距离和路径。
  - 相邻路由器交换信息
- 链路状态（link state）算法
  - 与距离矢量算法不同，它是一种全局的路由选择算法
  - 每个节点将链路状态包向网络中所有其他的节点广播。链路状态包包括节点的身份和它到相邻节点的代价信息。最后的结果是所有的节点都具有同样的网络拓扑图。

网络流量控制

网络拥塞的因素

缓冲器容量不够
- 缓冲器容量不足时，分组丢失；但缓冲器太大时，会发生超时
处理器速度太低
链路带宽不够

拥塞控制和流量控制的关系

拥塞控制必须使得通信子网能够传送所有待传送的数据，它是一个全局性的问题，涉及到所有主机、路由器、路由器中的存储转发处理的行为。
流量控制是与某发送者和某接收者之间的点到点的业务量有关。它的任务是确保一个快速的发送者不能以比接收者能承受的速率更高的速度传输数据。
简单的说，流量控制是防止网络拥塞的一种机制。

流量控制的功能

防止过载产生吞吐量降低、响应时间增长
避免死锁
资源合理分配
速率匹配

缓冲策略与流量控制

为了使没有得到确认的PDU可以超时重发，需要在缓冲区中暂存

数据链路层点对点通信缓冲区大小根据滑窗协议而定
传输层端到端通信多个缓冲区动态分配和管理非常复杂

流量整形技术

流量整形需要在网络的边沿实现以便控制进入网络的流量速率。
与之相比，TCP滑动窗口协议只是限制一次传送数据的数量，而不是传送的速率。

漏桶算法

这种策略相当于将非平稳的分组流变成了一个平稳的分组流，从而平滑了数据分组的突发性。
但是没有考虑突发业务流的大小，输出不具有突发性。

令牌漏桶算法

在令牌漏桶算法中，漏桶中保留的不是数据分组，而是令牌。系统每隔ΔT个时间单位产生一个令牌，送入漏桶中。当漏桶满时，产生的新令牌将被丢弃。对于数据分组来说，只有获得了令牌才可以发送。当有多个分组要发送，可以根据获取的令牌数决定一次可发送的分组数，从而使漏桶的输出具有一定的突发性。

网络拥塞控制

网络性能和网络负载的关系

当网络的负载较小时，吞吐量和负载呈线性关系；
当负载达到膝点（knee point)之后，随着负载的继续增加，吞吐量的增量变化很小；
当负载超过了崖点（cliff point)之后，吞吐量却急剧下降。
通常将膝点附近称为拥塞避免区，膝点和崖点间的区域成为拥塞恢复区，而崖点之后的区域称为拥塞崩溃区。

处理拥塞的控制方法

分组删除
流量控制
- 只限制两点流量，多源造成的拥塞仍会出现
缓冲分配能用于需电力技术中
抑制分组

网络中的拥塞控制机制

开环拥塞控制
- 预防式
- 优点：控制算法性能不受传输影响
- 缺点：资源利用率低
闭环拥塞控制
- 反馈式
- 源算法：在主机和网络边缘设备中执行。根据反馈信息调整发送速率。
- 链路算法：在网络内部（如路由器和交换机）中执行，它的主要作用是检测网络拥塞的发生，生成拥塞反馈信息。

TCP的流量控制和拥塞控制

利用滑动窗口机制可以很方便地在 TCP 连接上实现流量控制。

可以用不同的机制来控制 TCP 报文段的发送时机:

第一种机制是 TCP 维持一个变量，它等于最大报文段长度 MSS。只要缓存中存放的数据达到 MSS 字节时，就组装成一个 TCP 报文段发送出去。
第二种机制是由发送方的应用进程指明要求发送报文段，即 TCP 支持的推送(push)操作。
第三种机制是发送方的一个计时器期限到了，这时就把当前已有的缓存数据装入报文段（但长度不能超过 MSS）发送出去。

持续计时器

TCP 为每一个连接设有一个持续计时器。
只要 TCP 连接的一方收到对方的零窗口通知，就启动持续计时器。
定时发送零窗口探测报文段。

慢启动和拥塞避免

数据接收窗口（R-window）和拥塞控制窗口（C-window）。接收窗口的大小由接收端的缓存容量决定，拥塞窗口的大小由网络的带宽决定。发送端所能发送的数据段的数量是接收窗口和拥塞窗口二者的最小值。

TCP拥塞控制机制分为“慢启动”和“拥塞避免”两个阶段。数据段发送端用一个门限变量（或阈值）来区分两个阶段。当发送端开始发送数据时，首先处于“慢启动”阶段。

“慢启动”用于探测网络的带宽,使用指数增长的方式;“拥塞避免”试图避免拥塞的发生。

在慢开始门限ssthresh前为慢开始阶段，拥塞窗口指数增长：每经过一个传输轮次，拥塞窗口 cwnd 就加倍。
在门限后进入拥塞避免阶段，拥塞窗口线性增加（加法增大）
发生超时则慢开始门限改为拥塞窗口的一半（乘法减小），拥塞窗口设置为1

快重传和快恢复

快重传算法首先要求接收方每收到一个失序的报文段后就立即发出重复确认。这样做可以让发送方及早知道有报文段没有到达接收方。发送方只要一连收到三个重复确认就应当立即重传对方尚未收到的报文段。
当发送端收到连续三个重复的确认时，就执行“乘法减小”算法，把慢开始门限 ssthresh 减半。但接下去不执行慢开始算法。而是将拥塞窗口设置为慢开始门限 ssthresh 减半后的数值，然后开始执行拥塞避免算法（“加法增大”），使拥塞窗口缓慢地线性增大。

网络互连

网际层IP协议

地址解析协议 ARP(Address Resolution Protocol)
逆地址解析协议 RARP(Reverse Address Resolution Protocol)
网际控制报文协议 ICMP(Internet Control Message Protocol)
网际组管理协议 IGMP(Internet Group Management Protocol)

互连设备的类型

当中继系统是转发器或网桥时，一般并不称之为网络互连，因为这仅仅是把一个网络扩大了，而这仍然是一个网络。

物理层中继系统

转发器集线器

物理层设备，在电缆段之间拷贝比特；
对弱信号进行放大或再生，以便延长传输距离。

数据链路层中继系统

网桥、交换机

数据链路层设备，在局域网之间存储转发帧；
网桥可以改变帧格式。

路由层中继系统

路由器

网络层设备，在网络之间存储转发包；
必要时，做网络层协议转换。

高层中继系统

网关

互连方式

级联虚电路
- 建立连接
- 传输数据
- 拆除连接
无连接互连
- 每个包单独路由
- 根据不同子网的需要做协议转换
级联虚电路的优点
- 路由器预留缓冲区等资源，保证服务质量；
- 包按序号传输；
- 短包头。
级联虚电路的缺点
- 路由器需要大量内存，存储虚电路信息；
- 一旦发生拥塞，没有其它路由；
- 健壮性差；
- 如果网络中有一个不可靠的数据报子网，级连虚电路很难实现。
无连接网络互连的优点
- 能够容忍拥塞，并能适应拥塞；
- 健壮性好；
- 可用于多种网络互连。
无连接网络互连的缺点
- 长包头；
- 包不能保证按序号到达；
- 不能保证服务质量。

LAN的互连

HUB

使用hub连接的计算机共享一个“碰撞域”

从某一端口A将收到的帧发送到所有端口
非广播帧时，地址与帧目的MAC地址相同的站响应用户A
广播帧时，所有用户都响应用户A

网桥

一种存储转发装置

读取网络N1上的所有帧并接收那些指向N2的帧；
将接收的帧送到数据链路层，在该层上计算校验和并计算到达N2的路由；
将接受的帧用N2的MAC协议转发到N2上；

不足：

存储转发导致时延增加
无流量控制功能，负载重时会丢失帧
不能防止广播风暴（广播消息仍会泛滥到网桥所连接的各个网段）

交换机

交换机利用“地址学习”的方法来动态建立和维护端口号/MAC地址映射表的。

直接交换方式(只要接收并检测到目的地址字段就立即将该帧转发出去，而不管这一帧数据是否出错。)
存储转发方式(交换机先完整接收数据帧进行差错检测再转发 FCS检测)
改进的直接交换方式(接收数据帧的前64字节判断字头段正确再转发)

虚拟局域网VLAN

建立在网络交换机基础上

优点：

建立虚拟工作组，便于进行网络的管理
增强了网络安全性
抑制广播数据的泛滥
减少了处理用户站点移动所带来的开销

一个VLAN就好像是一个孤立的网段，VLAN间不能直接通信，实现VLAN间互联必须借助于路由器。

MAC帧中有VLAN标记

IP地址

IP = net id + host id

IP分类

A类 8+24 0……
B类 16+16 10……
C类 24+8 110……
D类多播 1110……
E类保留 1111……

后缀全1表示广播

IP地址的重要特点

IP分net和host的好处：
- IP地址管理机构只分发网络号
- 路由器只根据网络号进行路由
一个路由器至少应有两个IP

IP地址与硬件地址

TCP报文 = 首部 + 应用层数据
IP数据报 = 首部(含IP) + TCP报文
MAC帧 = 首部(含MAC地址) + IP数据报

ARP和RARP

IP地址 -ARP-> 物理地址

物理地址 -RARP-> IP地址

每个主机中都设有一个ARP高速缓存，包含所在局域网上各主机和路由器的IP-MAC地址映射，对不同局域网应该找到路由器的硬件地址转发给下一网络。

IP数据报

标志
DF = 0 表示本分组允许分段
= 1 表示本分组必须完整到达，途中不允许分段
MF = 0 表示本段为本分组的最后一个段
= 1 表示本段后面还有更多的分段
段偏移（fragmentation offset）：13位
实际偏移量 = 段偏移值 x 8 Byte

数据报分段与重组

每个分段头部copy原来的头部，与分段相关的重新生成
必须在各分段都到达目的地之后才进行重组：（可以不同路由、不按序）
要么重组成功，要么全部丢弃的原则

IP层转发分组流程

主机号路由
特定主机路由
默认路由

(1) 从数据报的首部提取目的主机的 IP 地址 D（划分子网情况下需要先相与）, 得出目的网络地址为 N。
(2) 若网络 N 与此路由器直接相连，则把数据报直接交付目的主机 D；否则是间接交付，执行(3)。
(3) 若路由表中有目的地址为 D 的特定主机路由，则把数据报传送给路由表中所指明的下一跳路由器；否则，执行(4)。
(4) 若路由表中有到达网络 N 的路由，则把数据报传送给路由表指明的下一跳路由器；否则，执行(5)。
(5) 若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器；否则，执行(6)。
(6) 报告转发分组出错。

划分子网

两级IP到三级IP

IP = net id + subnet id + host id

子网划分后对外仍是一个网络

子网掩码是一个网络或子网的重要属性，表示网络号+子网号的位数

IP地址和子网掩码与运算得到网络地址

无分类编址CIDR

一个 CIDR 地址块可以表示很多地址—路由聚合/构成超网

IP = 网络前缀 + host id

提高IP地址的利用率
缩短路由表

使用CIDR时，路由表最长前缀匹配

网际控制报文协议ICMP

为了提高 IP 数据报交付成功的机会，在网际层使用了网际控制报文协议 ICMP (Internet Control Message Protocol)。

ICMP 允许主机或路由器报告差错情况和提供有关异常情况的报告。
ICMP 不是高层协议，而是 IP 层的协议。
ICMP 报文作为 IP 层数据报的数据，加上数据报的首部，组成 IP 数据报发送出去。

ICMP报文种类

差错报告报文
- 终点不可达
- 源抑制
- 超时
- 重定向
- 参数问题
询问报文
- 回送请求和回答
- 时间戳请求和回答

不发送ICMP差错报文的情况

ICMP报文出错
对分片的数据报值只发送一个
多播地址和特殊地址不发送

ICMP应用

ping

使用了回送请求与回答报文
测试两个主机连通性

tarcert

使用超时报文
不断增大hop直至到达

得到路径中最小的MTU

使用参数错误报文
置DF=1不允许分段，不断减小报文长度

自治系统AS

一个AS对其他AS表现出单一和一致的路由选择策略

内部网关协议IGP 域内路由选择

路由信息协议RIP

分布式的基于距离向量的路由选择协议
要求每一个路由器维护从他自己到每一个目的网络的距离记录，定时和相邻路由器交换路由信息
各路由器中信息不同
RIP 认为一个好的路由就是它通过的路由器的数目少，即“距离短”。
RIP 不能在两个网络之间同时使用多条路由。
RIP 允许一条路径最多只能包含 15 个路由器。
“距离”的最大值为16 时即相当于不可达。可见 RIP 只适用于小型互联网。

RIP用UDP数据报传送

优点：

实现简单开销较小
缺点：
网络出现故障时，时延较长(好消息传播得快，坏消息传播得慢)
距离最大为16，网络规模受限
路由表开销随网络规模增大

OSPF

是分布式的链路状态协议

向本自治系统中所有路由器发送信息，这里使用的方法是洪泛法。
发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。
- “链路状态”就是说明本路由器都和哪些路由器相邻，以及该链路的“度量”(metric)。
只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息。

各路由器中信息一致

OSPF可以将AS再划分成多个区域，减少洪泛法的通信量

OSPF直接用IP数据报传送，数据报很短

特点：

支持CIDR和变长子网划分
多路径负载均衡
对不同服务计算不同路由

五种分组：

类型1，问候(Hello)分组。
类型2，数据库描述(Database Description)分组。
类型3，链路状态请求(Link State Request)分组。
类型4，链路状态更新(Link State Update)分组，
用洪泛法对全网更新链路状态。
类型5，链路状态确认(Link State Acknowledgment)
分组。

外部网关协议EGP 域间路由选择

BGP

在AS间交换“可达性”信息
边界网关协议 BGP 只能是力求寻找一条能够到达目的网络且比较好的路由（不能兜圈子），而并非要寻找一条最佳路由。

BGP发言人通常为边界路由器，两个BGP发言人通过一个共享网络连接

BGP建立TCP连接以建立BGP会话

特点：

支持CIDR
BGP邻站只更新变化部分

网际组管理协议 IGMP 和多播路由选择协议

用于IP多播：

IGMP：使路由器知道多播组成员的信息
多播路由选择协议：把多播数据报用最小代价传送给所有的组成员。这就需要使用。

IGMP在本地使用，并不知道多播组的成员数，知识让多播路由器知道主机加入或退出
IGMP 使用 IP 数据报，但它也向 IP 提供服务

多播路由选择协议必须动态适应成员变化

转发多播数据报使用的方法：

洪泛与剪除
路由器转发多播数据报使用洪泛法。为了避免兜圈子，采用了叫做反向路径广播 RPB (Reverse Path Broadcasting)的策略。
隧道技术(tunneling)
使用隧道技术在单播网络中传递多播数据报
基于核心的发现技术

VPN

本地地址——仅在机构内部使用的 IP 地址，可以由本机构自行分配，而不需要向因特网的管理机构申请。
全球地址——全球唯一的IP地址，必须向因特网的管理机构申请。

隧道技术实现VPN

内联网和外联网

都是基于TCP/IP协议

由部门 A 和 B 的内部网络所构成的虚拟专用网 VPN 又称为内联网(intranet)，表示部门 A和 B 都是在同一个机构的内部。
一个机构和某些外部机构共同建立的虚拟专用网 VPN 又称为外联网(extranet)。

远程接入VPN

VPN软件在PC和主机间建立隧道

网络地址转换NAT

把私有IP地址转换成公开IP地址

Router（Firewall）将对请求IP包和返回的应答IP包作NAT

返回的包到达源端：
利用传输层的源端口号字段，查询NAT中的映射表进行转换

NAT存在的问题

NAT违反了IP的体系结构
IP规定一个IP地址对应一个网络接口，而在NAT中，某个地址可能会对应成千上万个地址
NAT将Internet的无连接服务变成了有连接服务
因为NAT必须包含所有经过它的连接信息
NAT违反了网络分层原则
在第三层用了第四层协议格式中的字段
如果IP包的载荷不是TCP或UDP，则NAT无法工作
因为在其他协议的信息中不包含源端口号
在有些应用中NAT可能会出错
在有些应用中，发送方会将源IP地址嵌在它的消息中，接收方必须从信息中取用源IP地址，但NAT不作此类处理，因而将导致错误

IPv6

更大的地址空间
首部简化
支持选项
安全性
服务质量多媒体应用

传输层

面向通信部分的最高层，用户功能中的最低层，在通信子网中没有传输层。介于通信子网和资源子网之间。

传输层的任务

提供从源端到目的端（应用进程间）可靠而有效的数据传输，屏蔽低层网络的差异

两个主要协议

用户数据报协议 UDP (User Datagram Protocol)：无连接，不可靠
传输控制协议 TCP (Transmission Control Protocol)：面向连接，可靠，不提供广播或多播服务

两个对等运输实体在通信时传送的数据单位叫作运输协议数据单元 TPDU (Transport Protocol Data Unit)。

TCP 传送的数据单位协议是 TCP 报文段(segment)
UDP 传送的数据单位协议是 UDP 报文或用户数据报。

TCP

特点：

面向连接
只能一对一
可靠交付
全双工
面向字节流

三次握手建立连接

—-SYN=1,seq=x—->
<—-SYN=1,ACK=1,seq=y,ack=x+1—-
—-ACK=1,seq=x+1,ack=y+1—->

正常流程：

避免的异常流程：

重复的CR出现，主机2接受连接，但是主机1随即拒绝
同时有作废的CR和ACC出现，主机1的数据应该捎带确认该ACC，但是主机1并不会这样做

四次挥手释放连接

—-FIN=1,seq=u—->
<—-ACK=1,seq=v,ack=u+1—-
…数据传送…
<—-FIN=1,ACK=1,seq=w,ack=u+1—-
—-ACK=1,seq=u+1,ack=w+1—->
左边需等待2MSL才释放：

为了保证 A 发送的最后一个 ACK 报文段能够到达 B。
防止 “已失效的连接请求报文段”出现在本连接中。A 在发送完最后一个 ACK 报文段后，再经过时间 2MSL，就可以使本连接持续的时间内所产生的所有报文段，都从网络中消失。
非对称释放
对称释放
- 正常情况
- 最后的确认TPDU丢失，因超时释放
- 数据的应答丢失，因超时重发重新进行三次握手，传输完释放
- 应答和重发都丢失，因多次重发超时而释放

UDP

UDP 只在 IP 的数据报服务之上增加了很少一点的功能，即端口的功能和差错检测的功能。

特点：

无连接
尽最大努力交付，不可靠，无拥塞控制
面向报文
支持一/多对一/多
首部开销小

端口号

端口号 16bit 只具有本地意义
TCP和UDP都使用了端口号

传输层地址，也称为传输服务访问点（TSAP）在TCP协议中传输层地址即TCP的端口号
网络层地址称为网络服务访问点NSAP（Network Service Access Point），NSAP在IP协议中即IP地址

套接字 = IP + port

DNS

根域名服务器
顶级域名服务器
权限域名服务器
本地域名服务器

域名解析过程

主机向本地域名服务器的查询一般都是采用递归查询。如果主机所询问的本地域名服务器不知道被查询域名的 IP 地址，那么本地域名服务器就以 DNS 客户的身份，向其他根域名服务器继续发出查询请求报文。
本地域名服务器向根域名服务器的查询通常是采用迭代查询。当根域名服务器收到本地域名服务器的迭代查询请求报文时，要么给出所要查询的 IP 地址，要么告诉本地域名服务器：“你下一步应当向哪一个域名服务器进行查询”。然后让本地域名服务器进行后续的查询。

FTP

FTP 只提供文件传送的一些基本的服务，它使用TCP 可靠的运输服务。

FTP 的主要功能是减少或消除在不同操作系统下处理文件的不兼容性。
FTP 使用客户服务器方式。一个 FTP 服务器进程可同时为多个客户进程提供服务。FTP 的服务器进程由两大部分组成：
- 一个主进程，负责接受新的请求；
- 若干个从属进程，负责处理单个请求。

两个TCP连接：

控制连接客户端连接服务器21
数据连接服务器20连接客户端

TELNET 远程终端协议

TELNET 是一个简单的远程终端协议，也是因特网的正式标准。
用户用 TELNET 就可在其所在地通过TCP连接注册（即登录）到远地的另一个主机上（使用主机名或 IP 地址）。
和 FTP 的情况相似，服务器中的主进程等待新的请求，并产生从属进程来处理每一个连接。

TELNET 使用网络虚拟终端 NVT 格式

WWW

统一资源定位符 URL

统一资源定位符 URL 是对可以从因特网上得到的资源的位置和访问方法的一种简洁的表示。
协议://主机:端口/路径

HTTP 超文本传送协议

是一个应用层协议，它使用 TCP 连接进行可靠的传送。

分析超链指向页面的URL
浏览器向DNS请求解析域名的IP
DNS解析出IP
浏览器与服务器建立TCP连接
浏览器发出取index.htm文件命令
服务器响应，把index.htm文件发给浏览器
TCP连接释放
浏览器显示index.htm文件的文本

HTTP协议本身是无连接的
HTTP/1.1后使用持续连接

代理服务器又称Web Cache

代表浏览器发出 HTTP 请求。
万维网高速缓存把最近的一些请求和响应暂存在代理服务器的本地磁盘中。

电子邮件

一个邮件服务器既可以作为客户，也可以作为服务器

发件人调用 PC 机中的用户代理撰写和编辑要发送的邮件。
发件人的用户代理把邮件用 SMTP 协议发给发送方邮件服务器，
SMTP 服务器把邮件临时存放在邮件缓存队列中，等待发送。
发送方邮件服务器的 SMTP 客户与接收方邮件服务器的 SMTP 服务器建立 TCP 连接，然后就把邮件缓存队列中的邮件依次发送出去。
运行在接收方邮件服务器中的SMTP服务器进程收到邮件后，把邮件放入收件人的用户邮箱中，等待收件人进行读取。
收件人在打算收信时，就运行 PC 机中的用户代理，使用 POP3（或 IMAP）协议读取发送给自己的邮件。

发送邮件 SMTP

建立TCP连接传送邮件
端口号25

存在冒名发送邮件的漏洞

接收邮件 POP3 IMAP

POP3:
POP 也使用客户服务器的工作方式。
在接收邮件的用户 PC 机中必须运行 POP 客户程序，而在用户所连接的 ISP 的邮件服务器中则运行 POP 服务器程序。

IMAP:
用户在自己的 PC 机上就可以操纵 ISP 的邮件服务器的邮箱，就像在本地操纵一样。
因此 IMAP 是一个联机协议。当用户 PC 机上的 IMAP 客户程序打开 IMAP 服务器的邮箱时，用户就可看到邮件的首部。若用户需要打开某个邮件，则该邮件才传到用户的计算机上。

通用因特网邮件扩充 MIME

SMTP缺点：

不能传送可执行文件
限于传送ASCII
长度限制
MIME 并没有改动 SMTP 或取代它。
MIME 的意图是继续使用目前的[RFC 822]格式，但增加了邮件主体的结构，并定义了传送非 ASCII 码的编码规则。

动态主机配置协议DHCP

使用UDP端口（需要广播）

协议配置需要配置的项目
(1) IP 地址
(2) 子网掩码
(3) 默认路由器的 IP 地址
(4) 域名服务器的 IP 地址

DHCP提供了即插即用的机制，不需要手动配置

步骤：

需要IP的主句启动时向DHCP服务器广播发送发现报文，成为DHCP客户
只有DHCP服务器回答此广播报文（DNCP中继代理）
DHCP服务器在数据库中查找，若无则分配一个，发送提供报文

租用期