第二章 直连的网络提问
1.P39T5 a
2.P39T5 d
3.P39T6
4.P41T19
5.P40T15 b
6.P40T15 c
2.1 全章逻辑关系
1,所需硬件 (介质和结点 )
2,信号编码 (层次性 )
1) 如何编码一个比特
2) 在比特的基础上构建帧
3) 差错控制
4) 通信协议 (可靠传输 )
5) 介质访问控制问题
3,直连的网络常用的拓扑结构
1) 以太网
2) 令牌环网
3) 无线网注：核心问题是如何保证数据的正确性。
2.2 拓扑结构
a
b c
2.3 网络构件
1,结点
1) 主机,CPU,内存
2) 网络适配器编码、成帧、
错误检测、可靠传输、访问控制，一般这五个功能实现在一个 网络适配器 （网卡）
上。
附,网络适配器位置
CPU
cache
内存网络适配器
I/O总线
2.3 网络构件 (完 )
2,介质 (链路 )
1) 电缆,适用于各种场合。
2) 租用线,适用于个人安装成本过大的场合。
3) 最后一公里线路,适合连入已经存在的网络。
2.3.1 常用缆线类型电缆 典型带宽 距离五类双绞线细同轴电缆粗同轴电缆多模光纤单模光纤
10—100 Mbps
10—100 Mbps
10—100 Mbps
100 Mbps
100—2400 Mbps
100 M
200 M
500 M
2km
40 km
注,缆线的选择决定于建网的需求,它反过来又在很大程度上决定了网络所能覆盖的地理范围和带宽极限 ;
其中距离可以通过中继站延伸,但带宽一般是最大的限制,难以提高,
2.3.2 常用的网络服务服务 带宽
POTS
ISDN
xDSL
CATV
28.8—56 Kbps
64—128 Kbps
16 Kbps—55.2 Mbps
20—40 Mbps
注,上行速度与下行速度往往是不同的,目前的宽带一般是 ADSL
项 目 轨道 (km) 卫星数目 上行频率 下行频率
ICO
Globalstar
Iridium
Teledesic
10 355 10 2170—2200 1980--2010
1 410
780
1350
48 L-band S-band
66 L-band L-band
288 Ka-band Ka-band
附,ADSL
数字用户线 xDSL,使用最广的是 非对称 的数字用户线 ADSL.
ASDL为从用户到电话公司中心局（ 上行 ）
和从中心局到用户（ 下行 ）所提供的 带宽不同 。并在已存在的铜线上运行，其下行带宽的范围从 1.544Mbps到 8.448Mbps，而上行带宽的范围从 16Kbps到 640Kbps。
附,ADSL
1.554--8.448Mbps
中心局 住户
16---640kbps
本地回路附,ADSL
1.用户要求,接收大容量的文件，发送小的文件
2.划分,ASDL将双绞线电缆的带宽（ 1MHz） 划分成三个频带。
1)第一频带,通常在 0-25KHz之间，用于常规的电话业务（称为简单的老电话业务或 POTS）,这种业务仅用 4KHz的带宽。余下的用作警戒频带宽来分隔数据信道与语音信道。
2)第二频带,是在 25-200KHz之间，用于上行信道。
3)第三频带,是在 250K-1MHz之间，用于下行信道。
附,ADSL连接示意图附,ADSL工作方式
1.在电话线两端分别放置 ADSL Modem后,这段电话线上便产生了三个信息通道：
1) 一个速率为 1.5Mbps-9Mbps的高速下行通道，用于用户下载信息；
2) 一个速率为 16Kbps-1Mbps的中速双工通道，用于用户上传输出信息；
3) 一个普通的老式电话服务通道,用于普通电话服务 。
附,ADSL工作方式
2,这三个通道可以同时工作 。 在铜线两端安装 ADSL Modem的作用是接收基带数据,然后通过调制技术形成高速模拟信号进行传输 。
3.其特点是可以充分利用现有的铜缆网络，
在线路两端加装 ADSL设备即可为用户提供宽带服务，如访问因特网、视频传输、
网上购物、远程教学等。
2.4 编码
1,概念将比特信息 (1/0)转换为电磁信号的过程,
2,编码待解决的问题
1) 如何确定两个信息的分界点 (时钟同步 ).
2) 是否能够一定程度上检测差错,
2.4 编码 (续 )
3,常用的编码方案,
1) NRZ,1?高信号,0?低信号最为自然的编码方案
2) NRZI:第 1个信号同 NRZ,此后遇变为 1,
不变为 0,其它同 NRZ
3) Manchester:与时钟异或
4) 4B/5B:一种成组编码方案,有检错能力,
注,4B/5B方案一般与 NRZI配合使用,因为成组所以有检错能力,
附,编码简单分析
Bits
NRZ
Clock
Manchester
NRZI
0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0
附,编码简单分析 (完 )
111011111F0111101117
111001110E0111001106
110111101D0101101015
110101100C0101001004
101111011B1010100113
101101010A1010000102
10011100190100100011
10010100081111000000
5B4B数据5B4B数据
2.4 编码 (完 )
3,编码解决的问题
1) 时钟同步：解决正确同步，从而能正确区分两个信号的分界。这是正确通信的第一步。
2) 简单差错检测：在特定的编码方式下，某些比特序列的出现标志着发生了错误。如 4B/5B中出现大于等于三个连续 0
3) 编码效率：不同的编码方案有不同的效率，
如曼彻斯特编码的效率为 50%，而 4B/5B编码方案的效率为 80%
2.5 成帧
1,概念以特定的格式传送若干比特。
2,待解决的问题
1) 如何确定帧的开始与结束。
2) 如何能有更强的检错能力。
3,目的 (优点 )
有利于错误检测。
只需重发错帧，而不必重发全部数据。
2.5 成帧 (续 )
4,成帧的方法
1) 字符填充,以字符为单位传输与填充。
2) 字节计数,有特定的计数字段。
3) 比特填充,以比特为单位传输与填充。
4) 违例编码,以正常编码中不允许的编码标志帧的开始与结束。
5) 基于时钟,一种复杂的基于统计的方法。
注：填充的含义是当特定模式出现时，在该特定模式之前填充另一特定模式。
2.5 成帧 (完 )
5.帧的基本格式帧开始标志 帧结束标志传送的数据什么是填充?
由于需要特殊的“帧结束标志”来识别帧的结束,而在“传送的数据”部分很可能存在与
“帧结束标志”相同的内容,从而导致误判结束,
填充就是在发生上述情况时在前面“填充”
额外的特殊内容以区别于有效的结束标志,
附：成帧方法比较
1,字符填充与比特填充使用特定的字符或比特位填充,一般情况是提前结束一个帧,不破坏下一个帧,
字符填充与字符集关系密切，不利通用。
2,字节计数使用特定字段以计数的方式说明帧的结束,一旦计数字段出错,往往会破坏很多帧,
附：成帧方法比较 (完 )
3,违例编码只适用于某些特定的编码方式,适用面窄,
4.基于时钟相当复杂。
思考,
能否事先约定每帧的长度从而进行传输?
2.6 差错检测思想
1,要思考的问题
1) 是否能将错误分析限定在一帧内进行?
2) 可能出现的错误看起来为数众多，难以分析，如果让你来分析，你如何思考？
2.6 差错检测思想 (续 )
2,再看帧的识别帧开始标志 帧结束标志传送的数据
1) 开始标志错,无法识别一帧的正确开始，此时如果在数据中有与开始标志一样的数据，则产生一个错误的开始，但不影响下一帧。
2) 传送的数据错,如果某个填充数据出错，则导致帧错误结束，但不影响下一帧。
3) 结束标志错,导致帧不能正确结束，影响下一帧。
思考,为了限制错误不影响下一帧,该怎么设计方案?
返回
2.6 差错检测思想 (完 )
3,检错的基本思想在传输的数据中加入一部分附加的数据，将附加的数据作为“校验”，用于判断传输过程中是否发生错误。
问题,附加的数据同样可能出错，无论算法如何，
都存在数据按“校验”算法进行计算时表现为
“正确”，似乎判断错误是件没有希望的事情？
回答,校验失败一定错，成功未必对。
2.7 差错检测算法
1,二维奇偶校验
1011110 1
1101001 0
0101001 1
1011111 0
0110100 1
0001110 1
1111011 0
奇偶校验位校验字节数据功能,可以检测到所有 1,2,3比特错和大部分 4比特错。
冗余量,每 42比特中加入 14比特校验数据 (42/56)
缺点：所有信息到达后才能进行校验，需要存储器。
2.7 差错检测算法 (续 )
2,循环冗余校验 (Cyclic Redundancy Code)
思想,设想通信双方在交换一个多项式,利用模
2运算及相应的多项式性质,通过约定的“生成多项式”在发送端产生校验码,而在接收端计算校验和,
从而判定是否在传输中发生错误,
2.7 差错检测算法 (续 )
2,循环冗余校验 (续 )
方案,
设想一帧的长度为 k比特,它对应一个多项式 P(x),
该多项式以一帧的数据为各项系数,现在帧的尾部
(结束标志之前 )追加 r比特数据从而形成一个 k+r长度的帧,即相当于发送一个新的多项式
T(x)=P(x)× xr+R(x)
附加数据通过模 2的多项式除法产生,充当除数的多项式
C(x)称为 生成多项式,收到的数据也被视为一个多项式,
A(x)=T(x)+E(x)
如果不能被生成多项式整除,则表示数据出错,
附,模 2运算加减,
乘除,建立在模 2加减之上的乘法和除法,
0 1
0
1
0
01
1
附,多项式性质
1,C(x)=A(x)B(x),则 C(i)=A(i)B(i),这种多项式性质在全部使用模 2运算的前提下同样成立,
2,如果 B(x)的幂次大于等于 C(x),则 B(x)
能被 C(x)除,
3,如果 B(x)的幂次小于 C(x),则 B(x)不可能被 C(x)整除,
2.7 差错检测算法 (续 )
2,循环冗余校验 (续 )
生成多项式 G(x)的性质,
1) 如果 G(x)含有 (x+1)的因子,则能检测出所有奇数位错,即 G(x)=(x+1)g(x).
2) 如果 G(x)中不含有 x的因子 (即含有常数项 1),
则能检测出所有长度小于等于 r的突发错误 (突发错误指因某种原因导致的连续若干位出错 )。
3)如果 G(x)中不含有 x的因子 (即含有常数项 1),
且对任何 0<e≤n-1的 e,除不尽 xe+1,则能检测出所有的双错。 (n=k+r)
2.7 差错检测算法 (完 )
2,循环冗余校验 (续 )
4) 如果 G(x)中不含有 x的因子 (即含有常数项 1),
则对突发长度为 r+1的突发错误的漏检率为 2-(r-1)
5) 如果 G(x)中不含有 x的因子 (即含有常数项 1),
则对突发长度大于 r+1的突发错误的漏检率为 2-r
注：检错还是纠错同样取决于成本，想象一下美国火星探测时，
很多指令是由地面发送的，而一条指令传到火星需要 4—10分钟，
所以可以明白如果使用“停止等待协议”这样的检错重传方案，
那将是非常糟糕的。
附,常用 CRC生成多项式
CRC-8 x8+x2+x1+1
CRC-10 x10+x9+x5+x4+x1+1
CRC-12 x12+x11+x3+x2+1
CRC-16 x16+x15+x2+1
CRC-CCITT x16+x12+x5+1
CRC-32
x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1
小结
1,这是数据链路层的差错控制功能。
2,既有能力检错也有能力纠错。
3,只能证明错误却不能证明正确。正确是由概率保证的。
4,纠错未必比检错更有益。
5,假定至此已经能够检出所有的错误帧。
2.8 可靠传输
1,目的：
在能够检出所有错误的前提下更进一步，
即保证收到全部正确的数据。
2,重要协议
1) 停止等待协议
2) 滑动窗口协议
3.并发逻辑信道
2.8 可靠传输
4.相关概念,
1)确认 （ ACK） 是协议发给它的对等实体的一个小的控制帧,告知它已收到刚才的帧 。
2)控制帧 是一个无任何数据的头部,但是一个协议也可以将一个 ACK捎带在一个恰好要发向对方的数据帧上,
3)如果发送方在合理的一段时间后未收到确认,
那么它重发 （ retransmit） 原始帧 。 等待一段合理的时间的这个动作称为 超时 （ timeout）,
4)使用确认和超时实现可靠传输的策略有时称为自动请求重发（ ARQ） 。
2.8.1 停止等待协议
1.停止等待 (stop-and-wait)的思想：
发送方传输一帧之后，在传输下一帧之前等待一个确认。如果在某段时间之后确认没有到达，则发送方超时，
重发原始帧。
注,显然超时时间要大于等于 RTT.
2.8.1 停止等待协议 (续 )
时间超时发送方 接收方帧
ACK
（ a） 确认在超时前到达超时发送方 接收方帧帧
ACK
超时
(b) 原始帧丢失目标,确定对方收到帧,默认未收到,
2.停止等待协议分析
2.8.1 停止等待协议 (续 )
超时发送方 接收方帧
ACK
帧
ACK
超时
（ c） 确认丢失收方问题,是重发的帧还是确认后的新帧?
要求,区分重复帧,
超时发送方 接收方帧
ACK
帧
ACK
超时
（ d） 超时过快
2.8.1 停止等待协议 (续 )
发送方 接收方帧 0
ACK0
帧 1
ACK1
帧 0
ACK0
加入了序号的停止等待协议时间线思考,序号需要多少位才够用?
2.8.1 停止等待协议 (续 )
3.停止等待协议算法发送方：
1）初始化,N?0
2)从主机取一个数据帧（来自上层）
3)以帧序号为 N,发送它，设置超时定时器，
超时前收到 ACK,则 N=1-N,转 2）
可选的功能 [发方收到 NAK,转 3） ]
5）超时，转 3）
2.8.1 停止等待协议 (续 )
接收方：
1）初始化,N?0,期待的帧号
2) 等待，收到一个数据帧（来自下层）
3) 错误,(发 NAK),转 2）
4) 如果收到的帧号 =N,则接收，发 ACK，
N=1-N,转 2）
5）如果收到的帧号 ≠ N,则丢弃，发 ACK，
转 2）（此处收到重复帧）
2.8.1 停止等待协议 (续 )
4.停止等待协议的不足允许发送方每次在链路上只有一个未确认的帧，这可能远远低于链路的容量,
2.8.1 停止等待协议 (完 )
例,RTT=45ms的 1.5Mbps链路 。 这条链路的延迟与带宽的乘积为 67.5Kb,或大约 8KB。 由于发送方每个 RTT仅能发送一帧,假设一帧为 1KB,则最大发送速率为,
BitsPerFrame? TimePerFrame
(有效带宽的近似,忽略了发送延时 )
= 1024? 8? 0.045
= 182 Kbps
大约是链路容量的 八分之一 。
为完全利用链路,希望发送方在必须等待一个确认之前最多能够发送 8帧 。
2.8.2 滑动窗口协议
1.目标实现最大限度的利用带宽，连续发送数据,直至链路上充满数据。
时间发送方 接收方
2.8.2 滑动窗口协议 (续 )
2.滑动窗口协议算法收方与发方各维持一个窗口，发方的窗口根据收方发回的确认移动。
1)发送方
(a)维护一个序号,记作 SeqNum.假设 SeqNum能无限增大,
(b)发送窗口大小,记作 SWS,给出发送方能够发送但未确认的帧数的上界；
(c)LAR表示最近收到的确认帧的序号
(d)LFS表示最近发送的帧的序号
LFS-LAR<=SWS
2.8.2 滑动窗口协议 (续 )
(e)发方的工作：
当一个确认到达时，发送方向右移动 LAR,允许发送方发送另一帧。同时，发送方为所发的每个帧设置一个定时器，如果定时器在 ACK到达之前超时，
则重发此帧。
注意：发送方必须可以存储 SWS个帧，因为在它们得到确认之前可能重发。
<=SWS
LAR LFS
发送方的滑动窗口
2.8.2 滑动窗口协议 (续 )
2) 接收方
(a)维护三个变量：
接收窗口大小 (RWS):给出接收方所能接收的无序帧数目的上界；
最大的可接收帧（ LAF）,用于标识帧的最大序号；
收到的最后一个帧 (LFR):指序号,最大的,(在假设序号足够用的情况下 )
2.8.2 滑动窗口协议 (续 )
(b)维护一个等式
LAF-LFR<=RWS
<=RWS
LFR LAF
收方的滑动窗口
2.8.2 滑动窗口协议 (续 )
(c)接收方的算法,
当一个具有序号 SeqNum的帧到达时，接收方采取如下行动：
如果 SeqNum? LFR 或 SeqNum > LAF，
那么 帧不在接收窗口内，丢弃它；
如果 LFR? seqNum? LAF,
那么 帧在接收窗口内，于是被接收。
2.8.2 滑动窗口协议 (续 )
设 SeqNumToACK表示未确认的帧的最大序号，则,
如果 序号小于等于 SeqNumToACK的帧都已收到,
那么 确认该帧,并设 LFR = SeqNumToACK，
LAF=LFR+RWS
或者进行有选择确认：
如果 接收方能够准确地确认那些已收到的帧,
那么 可以更好地保持管道满载,但更复杂,
可选择,否认帧：为某个未到的帧发此帧
2.8.2 滑动窗口协议 (续 )
3.有限序号产生的问题,
如何区分同一序号的不同次发送?
或者说,
至少要有多少可用序号,才能满足协议要求,
答案,
如果 RWS=1,则 MaxSeqNum≥ SWS+1
如果 RWS=SWS,则 SWS<(MaxSeqNum+1)/2
提示,只有在临界点会出错,即最大帧收到,但 ACK丢失,
2.8.2 滑动窗口协议 (完 )
(?)滑动窗口协议有 3个不同的功能，
(a) 在不可靠链路上可靠地传输帧 ---算法的核心功能
(b) 用于保持帧的传输顺序 (缓存错序到达的帧 )
(c) 支持流量控制，它是一种接收方能够控制发送方使其降低速度的反馈机制。
2.8.3 并发逻辑信道基本思想是：
在一个点到点链路上多路复用多个逻辑信道，并且在每个逻辑信道上运行停止等待算法。
在任意逻辑信道上传输的帧之间没有任何关系，因为在每个逻辑信道上可以有一个不同的待确认帧，发送方可保持链路满载。
2.8.3 并发逻辑信道 (完 )
发送方为每一信道状态留有 3个比特：
（ 1）一个布尔量,说明信道当前是否忙
（ 2） 1比特序号,用于说明下次在这个逻辑信道上发送的帧；
（ 3）以及下一帧的序号,用于说明期望到达这一信道的一个帧。（即期望接收的序号）
当结点有一个帧要发送时，它使用序号最小的空闲信道，其它行为就象停止等待一样 。
小结前面所有的知识是如何配合工作的？
设,1）采用 4B/5B编码。 2） NRZI编码 3）比特填充法 。
4） CRC帧校验。 5）停止等待协议。
问,实际的工作流程如何？
分析：以数据,Hello World” 从 A?B的过程为例
1） 拆成两个数据,Hello”,,World” 。 2） 转换成
ASCII编码。 3） 视数据为比特，加上帧结构信息，进行比特填充。 4） 附加上 CRC校验码。 5） 将 4）中得到的比特集进行 4B/5B编码转换。 6） 以 NRZI再次编码，
并最终发送至线路。 7) 经停止等待协议的控制在接收方得到两个,正确的,数据包。 8） 在接收方此过程逆向进行。
数据链路层协议原始数据上层协议原始数据帧头 帧尾数据链路层协议帧头 封装上层数据 帧尾 CRC
4B/5B编码
NRZI编码物理链路
4B/5B解码
NRZI解码收集帧 过程分析完整的帧原始数据上层协议原始数据帧头 帧尾帧头 封装上层数据帧尾 CRC
通过校验比特恢复
CRC计算
CRC计算比特填充停止等待协议小结至此已经可以在收发双方正确的传送以帧为单位的数据，当然分析中可知正确性是由概率来保证的,为了进一步保证数据的正确性，
可以在更高层的协议进一步使用检错机制。
如在文件传输中，可以整个文件为单位再附加一个 CRC码，当每个帧的数据最终组成文件后再校验一次，也有使用 MD5算法作为校验方式的，归根结底,正确性 是一切远距离通信中最需要，也是最难保证的事情。
下一步的工作解决共享介质的公平访问问题。
局域网 (LAN)概述
覆盖范围小,房间、建筑物、园区范围距离 ≤25 km
高传输速率 10Mbps～ 1000Mbps
低误码率 10-8 ～ 10-10
采用总线、星形、环形拓扑
双绞线、同轴电缆、光纤
为一个单位所拥有，自行建设，不对外提供服务
1,LAN的特点
hub
hub
hub
Switch
Server
farm
station
stations
stations
2,IEEE802 标准主要有 12种。
1.IEEE802.1,
概述，局域网体系结构以及网络互连
2.IEEE802.2,
定义了逻辑链路控制子层的功能与服务
3.IEEE802.3：
描述 CSMA/CD总线式介质访问控制协议及相应物理层规范
2,IEEE802 标准 (续 )
4,IEEE802.4：
描述令牌总线（ token bus） 式介质访问控制协议及相应物理层规范
5,IEEE802.5：
描述令牌环（ token ring） 式介质访问控制协议及相应物理层规范
6,IEEE802.6：
描述市域网（ MAN） 的介质访问控制协议及相应物理层规范
7,IEEE802.7：
描述宽带技术进展
2,IEEE802 标准 (续 )
8,IEEE802.8：
描述光纤技术进展
9,IEEE802.9：
描述语音和数据综合局域网技术
10.IEEE802.10：
描述局域网的安全与解密问题
11.IEEE802.11：
描述了无线局域网技术；
12.IEEE802.12：
描述用于高速局域网的介质访问方法及相应的物理层规范。
2,IEEE802 标准 (续 )
13.IEEE 802.13：
保留
14.IEEE 802.14,
描述了交互式电视网（包括 Cable Modem）
以及相应的技术参数规范
15.IEEE 802.15,
描述了无线个人区域网络
16.IEEE 802.16,
描述了宽带无线接入技术
3.MAC地址
IEEE802标准为每个厂商生产的网卡规定了一个 48位的全局地址 (MAC),它是 全球唯一的,MAC地址的 高 24位 由 IEEE统一分配给厂商，
低 24位 由厂商分配给每一块网卡。
网卡的 MAC地址可以认为就是该网卡所在站点的 MAC地址。
计算机间的通信不是基于 IP,而是基于 MAC.
IP只是用于路由过程,
2.9 以太网 （ 802.3）
2.9.1 物理特性收发器适配器主机以太网收发器和适配器以太网电缆
2.9.1 物理特性
1,带宽有多种选择,10M 100M 1000M
2,长度限制,2500米
3,任意 两台主机间的中继器 不超过 4个,
4,分接头 至少相隔 2.5米
2.9.2 802.3布线介质标准
10Base2 细同轴
10Base5 粗同轴
10BaseT 双绞线
10BaseF MMF
100BaseT 双绞线
100BaseF MMF/SMF
1000BaseX 屏蔽短双绞线 /MMF/SMF
1000BaseT 双绞线附,IEEE 802.3 规范传统以太网
802.3 —— 同 轴电缆 Ethernet
802.3a —— 细缆 Ethernet
802.3i —— 双绞线
802.3j —— 光纤快速以太网 FE
802.3u —— 双绞线，光纤千兆以太网 GE
IEEE802.3z —— 屏 蔽短双绞线、光纤
IEEE802.3ab —— 双绞线
2.9.3 帧结构
CRC数据区类型 /长度源地址目标地址前缀
64 48 48 16 32
每帧最多包含 1500B,最少包含 46B,以太网是一个面向比特的成帧协议,
1500B的上界意味着适配器只能以一段有限时间占用线路。
2.9.4 适配器工作方式
1,发送到网络上的数据可被所有主机,侦听,
到,
2,每个适配器只接收,
1) 目标地址是自己地址的帧,
2) 目标地址是广播地址的帧,
3) 目标地址是本机监听的多点广播的地址的帧
4) 适配器是可编程的,处于混杂模式时可接收所有帧,
2.9.5 传输过程
1,接收方侦听每一个帧,并将符合条件的帧发给主机,
2,发送方必须以某种方式避免冲突,并在特定条件满足的情况下发送数据,
3,这些过程是网络适配器负责完成的,
以太网的问题：
以太网上的任意一个主机传输的数据都能够到达 所有其它主机 。所有主机竞争访问 同一条链路,处在同一个冲突域中。
总线
A B C
C
D E F
附,冲突
1.要发送的站首先监听信道，判断是否有其他站正在发送（载波监听）
如果 信道正在被使用，
那么 站点等待；
如果 信道空闲，
那么 站点发送数据；
发送后 等待确认，收到确认，成功 ;否则，
重发。
2.9.6 CSMA技术
2.9.6 CSMA技术（续）
2,1-坚持算法
1） 如果 信道空闲，发送；
否则,转 2）
2） 如果 信道忙，
那么 继续监听直到信道空闲，
然后立即发送。
2.9.6 CSMA技术（续）
3,P-坚持算法同 1-坚持算法，但在发送时计算一个概率，以计算结果确定自已是否发送。
4,发送方必须知道自己发送的帧是否与其它主机发生冲突。
要求,确保帧能够无冲突的到达最远主机。
解决方案,发送方的发送时间必须足够长，
足以检测到冲突，因为只有在发送时发生的冲突才是自己的数据发生的冲突。
5,如果在发送过程中检测到冲突，发送一个简单的干扰信号保证所有站点都知道发生冲突并停止发送。 (谁先测到谁先发,)
发完干扰信号后，随机等待一段时间，重传（从 1)开始重复）
2.9.6 CSMA技术（续）
检测冲突所需的时间不超过端到端传播时延的两倍
(a)
(b)
(c)
(d)
BA
BA
BA
BA
例,最小传输量设在 10Mbps的以太网,RTT=51.2us,为了能够了解到冲突,传输方至少应发送多少数据?
解,
m=51.2× 10-6× 10× 106
=512 (b)
802.3标准与以太网区别
1.区别,帧的长度 /类型字段。 (P77)
2.解决方法是,该字段中的值大于帧的最大长度 (1518)，则表示为类型,否则表示是长度，即 802.3 标准。
3.具体做法是,以 1536(十六进制 0600)为界，
大于或等于 0600H 认为是以太网，按类型处理，如 IP为 0800H,XNS为 0600H,IPX为
8137H 等，类型字段指明上层所用的协议。
2.9.7 以太网的经验以太网在轻载情况下工作很好，很实用
1） 大部分以太网以比标准允许的方式更保守的方式使用。
2） 即使以太网适配器没有实现链路层流量控制，主机通常会提供端到端流量控制机制 ---很少出现任意一个主机连续把帧送到网上的情况。
1）以太网极易管理和维护，不存在出故障的交换机，也没有需要不断更新的路由选择或配置表，
2）易于向网络增加一个新的主机。
3）便宜，唯一的其它开销仅是每个主机上的网络适配器。而任何基于交换的方法除了每个适配器增加的开销外，将包括一个昂贵的基础构件（交换机）。
2.9.8 以太网的优点小结以太网通过 载波监听 了解其他主机的行为,初步避免冲突,如果还是发生了冲突,
则通过 指数退避 技术避免进一步的冲突 ;
如果冲突还是不断发生,主机 停止发送,减轻网络负载,希望能恢复网络性能 ;如果还是无效,称 以太网崩溃,
公平共享介质 通过最长数据长度实现,
2.10 令牌环网
2.10.1 令牌环思想一个令牌在环上循环，
每个结点收到令牌后转发它。当一个有帧要传输的结点看到令牌时，它把令牌从环上取下，而将自己的帧插入环中。沿路的每个结点简单地转发帧，目的结点存一个该帧拷贝，
然后继续转发该帧。
2.10.1 令牌环特性
1.隐患及解决方案隐患,某个结点故障可能导致整个网络失效。
解决方案,使用继电器来自于前一个主机 到下一个主机主机继电器来自于前一个主机 到下一个主机主机继电器
2.10.1 令牌环特性
MSAU
来自前一个 MSAU
到下一个 MSAU
主机主机主机主机多站访问单元
2.10.1 令牌环特性
2,优点
1) 每个下游的结点将有机会发送一个帧。介质访问算法是公平的。
2) 可以引入监控站对整个网络进行故障管理。
2.10.2 令牌环方案
1.信号单向传递,在令牌环网中信号只单向传递,
2.环路容量,即环路的容量要大于等于令牌长度,
3.令牌持有时间,即为了公平共享介质而要求任一主机一次持有令牌的时间不得大于,令牌持有时间,
4.可靠传控制,在帧尾部附加 2比特标志数据是否成功传递到目标主机,1) A=0,C=0,目的站不存在或未加电。 2) A=1,C=0,目的站存在但帧未被复制。 3)A=1,C=1,目的站存在并且帧被复制,。
2.10.2 令牌环方案
5.优先级支持,
令牌及帧是有 优先级 的,只有 大于等于 令牌优先级的帧才能被发送,
1) 要发送高优先级帧的主机修改经过自身的当前帧的优先级位,
2) 该帧回到发送者 (即令牌持有者 )时,令牌持有者调高令牌优先级并释放出去,
3) 只有不低于新的优先级的帧才允许被发送,
由发送者负责将优先级调回原值,
6.令牌释放,
1) 早期释放,发完帧后立即释放令牌,
2) 延期释放,待发送的帧环绕一周后释放令牌,
2.10.2 令牌环方案
7.错误恢复
1) 监控站,由预定义的方案产生,
2) 监控站 负责保证“环路容量”足够存放令牌,
3) 监控站 负责在令牌毁损或丢失的情况下 恢复令牌 及 清除坏帧,
小结令牌环通过 令牌的持有与释放 实现对共享介质的公平访问,由于一次只可能有一个令牌持有者且信号单向传递,在令牌环中不存在冲突 ;
令牌环能够实现更多的控制功能,能够进行集中式管理,能够定义优先级,
说明以太网和令牌环网的介绍中着重的是它们如何解决共享介质的公平访问问题,在任何网络中同样存在着检错和传输控制的任务。要理解三者是叠加的关系而不是平行的。
比如在以太网中，一个主机如果成功发送了数据，
接收方为了发送 ACK,必须参与下一轮对共享介质的竞争；同样，主机要重发数据也必须参与新一轮对共享介质的竞争在令牌环网中也会存在突发错误等情况，因此也会使用 CRC等检错方法，及使用等待重传等传输控制协议。
2.11 FDDI
2.11.1 拓扑结构双环结构：其中一条环是作为备用环
2.11.1 拓扑结构降低成本的实用方案
2.11.2 FDDI参数
1,最多 500个站点
2,光纤总长限制为 200KM
3,使用 4B/5B编码
4,时控令牌算法
5,令牌维护
6,帧格式状态帧结束CRC数据源地址目标地址控制帧开始
2.12 无线网
2.12.1 扩频技术
1.跃频扩频：它在一个随机的频率序列上传输信号； (伪随机 )
1)发方,首先以一个频率传输，然后是第二个，
然后第三个，依次类推。
2)接收方,使用与发送方相同的算法（且用相同的初值来初始化），因此能够与发送方同步跃频以正确接收帧。
2.12.1 扩频技术
2.直接序列它通过用被传输信号中的多个比特表示帧中的一个比特来获得相同的效果。
1
0
1
0
1
0
数据流,1010
随机序列：
0100101101011001
两者的异或：
1011101110101001
2.12.2 无线网特点
1.特点：
并非所有的结点可达（与以太网不同）。
2.存在隐藏结点,
假设 A和 C都想与 B进行通信，都向 B发送一帧。
这两个帧在 B互相冲突,A和 C都不知道这一冲突。
称 A和 C是关于对方的隐藏结点,
BA C D
2.12.2 无线网特点
3.存在暴露结点
B正向 A发送数据。结点 C发现到这一通信，如果 C只是因为听到 B的传输就认为它不能向任何结点（如 D结点）传输，这将是错误的。
BA C D
2.12.3 MACA
所有可达站在传输数据前都要交换控制帧
1) 过程：
发送方,给接收方发一个请求发送 （ RTS） 帧； RTS
帧包括一个表明发送方希望占有介质多久的字段 （ 即,
它指定要传输的数据帧的长度 ） 。 接收方,用一个清除发送 （ CTS） 帧应答；该帧向发送方回应这一长度字段 。
2) 处理方案,
看到 CTS帧的任意结点 知道它离接收方很近,因此在发送指定长度的帧的这段时间内不能传输 。
2.12.3 MACA
看到 RTS帧而不是 CTS帧的任意结点 离接收方不太近,不会干扰接收方,因此可以自由传输 。
（ 但要保证发方正确的收到 CTS）
BA C D
2.12.3 MACA
说明：
（ 1） 接收方在成功接收了一帧后向发送方发送一个 ACK。 所有结点在试图传输之前必须等待该 ACK
（ 2） 如果两个或多个结点同时检测到一个空闲链路并试图传输一个 RTS帧，那么它们的 RTS帧将彼此冲突。 802.11不支持冲突检测，但发送方在一段时间之后没有收到 CTS帧时，它就意识到发生了冲突。在这种情况下，它们都等待一个随机时间量后再试,(类似以太网的二进制退避算法 )
本章总结第二章综合解决了网络的基本问题,利用这些知识能够构建起最基本的网络形式,从层次上看,
它属于数据链路层的问题,
归纳来说,本章主要讨论并解决了以下问题,
1） 将数据以帧为单位划分
2） 通过校验、确认、反馈重发确保数据链路的无差错。
3） 进行流量控制，使得在高速的收发双方能协调配合。
下一步要考虑的是网络规模扩展带来的问题。
1.P39T5 a
2.P39T5 d
3.P39T6
4.P41T19
5.P40T15 b
6.P40T15 c
2.1 全章逻辑关系
1,所需硬件 (介质和结点 )
2,信号编码 (层次性 )
1) 如何编码一个比特
2) 在比特的基础上构建帧
3) 差错控制
4) 通信协议 (可靠传输 )
5) 介质访问控制问题
3,直连的网络常用的拓扑结构
1) 以太网
2) 令牌环网
3) 无线网注：核心问题是如何保证数据的正确性。
2.2 拓扑结构
a
b c
2.3 网络构件
1,结点
1) 主机,CPU,内存
2) 网络适配器编码、成帧、
错误检测、可靠传输、访问控制，一般这五个功能实现在一个 网络适配器 （网卡）
上。
附,网络适配器位置
CPU
cache
内存网络适配器
I/O总线
2.3 网络构件 (完 )
2,介质 (链路 )
1) 电缆,适用于各种场合。
2) 租用线,适用于个人安装成本过大的场合。
3) 最后一公里线路,适合连入已经存在的网络。
2.3.1 常用缆线类型电缆 典型带宽 距离五类双绞线细同轴电缆粗同轴电缆多模光纤单模光纤
10—100 Mbps
10—100 Mbps
10—100 Mbps
100 Mbps
100—2400 Mbps
100 M
200 M
500 M
2km
40 km
注,缆线的选择决定于建网的需求,它反过来又在很大程度上决定了网络所能覆盖的地理范围和带宽极限 ;
其中距离可以通过中继站延伸,但带宽一般是最大的限制,难以提高,
2.3.2 常用的网络服务服务 带宽
POTS
ISDN
xDSL
CATV
28.8—56 Kbps
64—128 Kbps
16 Kbps—55.2 Mbps
20—40 Mbps
注,上行速度与下行速度往往是不同的,目前的宽带一般是 ADSL
项 目 轨道 (km) 卫星数目 上行频率 下行频率
ICO
Globalstar
Iridium
Teledesic
10 355 10 2170—2200 1980--2010
1 410
780
1350
48 L-band S-band
66 L-band L-band
288 Ka-band Ka-band
附,ADSL
数字用户线 xDSL,使用最广的是 非对称 的数字用户线 ADSL.
ASDL为从用户到电话公司中心局（ 上行 ）
和从中心局到用户（ 下行 ）所提供的 带宽不同 。并在已存在的铜线上运行，其下行带宽的范围从 1.544Mbps到 8.448Mbps，而上行带宽的范围从 16Kbps到 640Kbps。
附,ADSL
1.554--8.448Mbps
中心局 住户
16---640kbps
本地回路附,ADSL
1.用户要求,接收大容量的文件，发送小的文件
2.划分,ASDL将双绞线电缆的带宽（ 1MHz） 划分成三个频带。
1)第一频带,通常在 0-25KHz之间，用于常规的电话业务（称为简单的老电话业务或 POTS）,这种业务仅用 4KHz的带宽。余下的用作警戒频带宽来分隔数据信道与语音信道。
2)第二频带,是在 25-200KHz之间，用于上行信道。
3)第三频带,是在 250K-1MHz之间，用于下行信道。
附,ADSL连接示意图附,ADSL工作方式
1.在电话线两端分别放置 ADSL Modem后,这段电话线上便产生了三个信息通道：
1) 一个速率为 1.5Mbps-9Mbps的高速下行通道，用于用户下载信息；
2) 一个速率为 16Kbps-1Mbps的中速双工通道，用于用户上传输出信息；
3) 一个普通的老式电话服务通道,用于普通电话服务 。
附,ADSL工作方式
2,这三个通道可以同时工作 。 在铜线两端安装 ADSL Modem的作用是接收基带数据,然后通过调制技术形成高速模拟信号进行传输 。
3.其特点是可以充分利用现有的铜缆网络，
在线路两端加装 ADSL设备即可为用户提供宽带服务，如访问因特网、视频传输、
网上购物、远程教学等。
2.4 编码
1,概念将比特信息 (1/0)转换为电磁信号的过程,
2,编码待解决的问题
1) 如何确定两个信息的分界点 (时钟同步 ).
2) 是否能够一定程度上检测差错,
2.4 编码 (续 )
3,常用的编码方案,
1) NRZ,1?高信号,0?低信号最为自然的编码方案
2) NRZI:第 1个信号同 NRZ,此后遇变为 1,
不变为 0,其它同 NRZ
3) Manchester:与时钟异或
4) 4B/5B:一种成组编码方案,有检错能力,
注,4B/5B方案一般与 NRZI配合使用,因为成组所以有检错能力,
附,编码简单分析
Bits
NRZ
Clock
Manchester
NRZI
0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0
附,编码简单分析 (完 )
111011111F0111101117
111001110E0111001106
110111101D0101101015
110101100C0101001004
101111011B1010100113
101101010A1010000102
10011100190100100011
10010100081111000000
5B4B数据5B4B数据
2.4 编码 (完 )
3,编码解决的问题
1) 时钟同步：解决正确同步，从而能正确区分两个信号的分界。这是正确通信的第一步。
2) 简单差错检测：在特定的编码方式下，某些比特序列的出现标志着发生了错误。如 4B/5B中出现大于等于三个连续 0
3) 编码效率：不同的编码方案有不同的效率，
如曼彻斯特编码的效率为 50%，而 4B/5B编码方案的效率为 80%
2.5 成帧
1,概念以特定的格式传送若干比特。
2,待解决的问题
1) 如何确定帧的开始与结束。
2) 如何能有更强的检错能力。
3,目的 (优点 )
有利于错误检测。
只需重发错帧，而不必重发全部数据。
2.5 成帧 (续 )
4,成帧的方法
1) 字符填充,以字符为单位传输与填充。
2) 字节计数,有特定的计数字段。
3) 比特填充,以比特为单位传输与填充。
4) 违例编码,以正常编码中不允许的编码标志帧的开始与结束。
5) 基于时钟,一种复杂的基于统计的方法。
注：填充的含义是当特定模式出现时，在该特定模式之前填充另一特定模式。
2.5 成帧 (完 )
5.帧的基本格式帧开始标志 帧结束标志传送的数据什么是填充?
由于需要特殊的“帧结束标志”来识别帧的结束,而在“传送的数据”部分很可能存在与
“帧结束标志”相同的内容,从而导致误判结束,
填充就是在发生上述情况时在前面“填充”
额外的特殊内容以区别于有效的结束标志,
附：成帧方法比较
1,字符填充与比特填充使用特定的字符或比特位填充,一般情况是提前结束一个帧,不破坏下一个帧,
字符填充与字符集关系密切，不利通用。
2,字节计数使用特定字段以计数的方式说明帧的结束,一旦计数字段出错,往往会破坏很多帧,
附：成帧方法比较 (完 )
3,违例编码只适用于某些特定的编码方式,适用面窄,
4.基于时钟相当复杂。
思考,
能否事先约定每帧的长度从而进行传输?
2.6 差错检测思想
1,要思考的问题
1) 是否能将错误分析限定在一帧内进行?
2) 可能出现的错误看起来为数众多，难以分析，如果让你来分析，你如何思考？
2.6 差错检测思想 (续 )
2,再看帧的识别帧开始标志 帧结束标志传送的数据
1) 开始标志错,无法识别一帧的正确开始，此时如果在数据中有与开始标志一样的数据，则产生一个错误的开始，但不影响下一帧。
2) 传送的数据错,如果某个填充数据出错，则导致帧错误结束，但不影响下一帧。
3) 结束标志错,导致帧不能正确结束，影响下一帧。
思考,为了限制错误不影响下一帧,该怎么设计方案?
返回
2.6 差错检测思想 (完 )
3,检错的基本思想在传输的数据中加入一部分附加的数据，将附加的数据作为“校验”，用于判断传输过程中是否发生错误。
问题,附加的数据同样可能出错，无论算法如何，
都存在数据按“校验”算法进行计算时表现为
“正确”，似乎判断错误是件没有希望的事情？
回答,校验失败一定错，成功未必对。
2.7 差错检测算法
1,二维奇偶校验
1011110 1
1101001 0
0101001 1
1011111 0
0110100 1
0001110 1
1111011 0
奇偶校验位校验字节数据功能,可以检测到所有 1,2,3比特错和大部分 4比特错。
冗余量,每 42比特中加入 14比特校验数据 (42/56)
缺点：所有信息到达后才能进行校验，需要存储器。
2.7 差错检测算法 (续 )
2,循环冗余校验 (Cyclic Redundancy Code)
思想,设想通信双方在交换一个多项式,利用模
2运算及相应的多项式性质,通过约定的“生成多项式”在发送端产生校验码,而在接收端计算校验和,
从而判定是否在传输中发生错误,
2.7 差错检测算法 (续 )
2,循环冗余校验 (续 )
方案,
设想一帧的长度为 k比特,它对应一个多项式 P(x),
该多项式以一帧的数据为各项系数,现在帧的尾部
(结束标志之前 )追加 r比特数据从而形成一个 k+r长度的帧,即相当于发送一个新的多项式
T(x)=P(x)× xr+R(x)
附加数据通过模 2的多项式除法产生,充当除数的多项式
C(x)称为 生成多项式,收到的数据也被视为一个多项式,
A(x)=T(x)+E(x)
如果不能被生成多项式整除,则表示数据出错,
附,模 2运算加减,
乘除,建立在模 2加减之上的乘法和除法,
0 1
0
1
0
01
1
附,多项式性质
1,C(x)=A(x)B(x),则 C(i)=A(i)B(i),这种多项式性质在全部使用模 2运算的前提下同样成立,
2,如果 B(x)的幂次大于等于 C(x),则 B(x)
能被 C(x)除,
3,如果 B(x)的幂次小于 C(x),则 B(x)不可能被 C(x)整除,
2.7 差错检测算法 (续 )
2,循环冗余校验 (续 )
生成多项式 G(x)的性质,
1) 如果 G(x)含有 (x+1)的因子,则能检测出所有奇数位错,即 G(x)=(x+1)g(x).
2) 如果 G(x)中不含有 x的因子 (即含有常数项 1),
则能检测出所有长度小于等于 r的突发错误 (突发错误指因某种原因导致的连续若干位出错 )。
3)如果 G(x)中不含有 x的因子 (即含有常数项 1),
且对任何 0<e≤n-1的 e,除不尽 xe+1,则能检测出所有的双错。 (n=k+r)
2.7 差错检测算法 (完 )
2,循环冗余校验 (续 )
4) 如果 G(x)中不含有 x的因子 (即含有常数项 1),
则对突发长度为 r+1的突发错误的漏检率为 2-(r-1)
5) 如果 G(x)中不含有 x的因子 (即含有常数项 1),
则对突发长度大于 r+1的突发错误的漏检率为 2-r
注：检错还是纠错同样取决于成本，想象一下美国火星探测时，
很多指令是由地面发送的，而一条指令传到火星需要 4—10分钟，
所以可以明白如果使用“停止等待协议”这样的检错重传方案，
那将是非常糟糕的。
附,常用 CRC生成多项式
CRC-8 x8+x2+x1+1
CRC-10 x10+x9+x5+x4+x1+1
CRC-12 x12+x11+x3+x2+1
CRC-16 x16+x15+x2+1
CRC-CCITT x16+x12+x5+1
CRC-32
x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1
小结
1,这是数据链路层的差错控制功能。
2,既有能力检错也有能力纠错。
3,只能证明错误却不能证明正确。正确是由概率保证的。
4,纠错未必比检错更有益。
5,假定至此已经能够检出所有的错误帧。
2.8 可靠传输
1,目的：
在能够检出所有错误的前提下更进一步，
即保证收到全部正确的数据。
2,重要协议
1) 停止等待协议
2) 滑动窗口协议
3.并发逻辑信道
2.8 可靠传输
4.相关概念,
1)确认 （ ACK） 是协议发给它的对等实体的一个小的控制帧,告知它已收到刚才的帧 。
2)控制帧 是一个无任何数据的头部,但是一个协议也可以将一个 ACK捎带在一个恰好要发向对方的数据帧上,
3)如果发送方在合理的一段时间后未收到确认,
那么它重发 （ retransmit） 原始帧 。 等待一段合理的时间的这个动作称为 超时 （ timeout）,
4)使用确认和超时实现可靠传输的策略有时称为自动请求重发（ ARQ） 。
2.8.1 停止等待协议
1.停止等待 (stop-and-wait)的思想：
发送方传输一帧之后，在传输下一帧之前等待一个确认。如果在某段时间之后确认没有到达，则发送方超时，
重发原始帧。
注,显然超时时间要大于等于 RTT.
2.8.1 停止等待协议 (续 )
时间超时发送方 接收方帧
ACK
（ a） 确认在超时前到达超时发送方 接收方帧帧
ACK
超时
(b) 原始帧丢失目标,确定对方收到帧,默认未收到,
2.停止等待协议分析
2.8.1 停止等待协议 (续 )
超时发送方 接收方帧
ACK
帧
ACK
超时
（ c） 确认丢失收方问题,是重发的帧还是确认后的新帧?
要求,区分重复帧,
超时发送方 接收方帧
ACK
帧
ACK
超时
（ d） 超时过快
2.8.1 停止等待协议 (续 )
发送方 接收方帧 0
ACK0
帧 1
ACK1
帧 0
ACK0
加入了序号的停止等待协议时间线思考,序号需要多少位才够用?
2.8.1 停止等待协议 (续 )
3.停止等待协议算法发送方：
1）初始化,N?0
2)从主机取一个数据帧（来自上层）
3)以帧序号为 N,发送它，设置超时定时器，
超时前收到 ACK,则 N=1-N,转 2）
可选的功能 [发方收到 NAK,转 3） ]
5）超时，转 3）
2.8.1 停止等待协议 (续 )
接收方：
1）初始化,N?0,期待的帧号
2) 等待，收到一个数据帧（来自下层）
3) 错误,(发 NAK),转 2）
4) 如果收到的帧号 =N,则接收，发 ACK，
N=1-N,转 2）
5）如果收到的帧号 ≠ N,则丢弃，发 ACK，
转 2）（此处收到重复帧）
2.8.1 停止等待协议 (续 )
4.停止等待协议的不足允许发送方每次在链路上只有一个未确认的帧，这可能远远低于链路的容量,
2.8.1 停止等待协议 (完 )
例,RTT=45ms的 1.5Mbps链路 。 这条链路的延迟与带宽的乘积为 67.5Kb,或大约 8KB。 由于发送方每个 RTT仅能发送一帧,假设一帧为 1KB,则最大发送速率为,
BitsPerFrame? TimePerFrame
(有效带宽的近似,忽略了发送延时 )
= 1024? 8? 0.045
= 182 Kbps
大约是链路容量的 八分之一 。
为完全利用链路,希望发送方在必须等待一个确认之前最多能够发送 8帧 。
2.8.2 滑动窗口协议
1.目标实现最大限度的利用带宽，连续发送数据,直至链路上充满数据。
时间发送方 接收方
2.8.2 滑动窗口协议 (续 )
2.滑动窗口协议算法收方与发方各维持一个窗口，发方的窗口根据收方发回的确认移动。
1)发送方
(a)维护一个序号,记作 SeqNum.假设 SeqNum能无限增大,
(b)发送窗口大小,记作 SWS,给出发送方能够发送但未确认的帧数的上界；
(c)LAR表示最近收到的确认帧的序号
(d)LFS表示最近发送的帧的序号
LFS-LAR<=SWS
2.8.2 滑动窗口协议 (续 )
(e)发方的工作：
当一个确认到达时，发送方向右移动 LAR,允许发送方发送另一帧。同时，发送方为所发的每个帧设置一个定时器，如果定时器在 ACK到达之前超时，
则重发此帧。
注意：发送方必须可以存储 SWS个帧，因为在它们得到确认之前可能重发。
<=SWS
LAR LFS
发送方的滑动窗口
2.8.2 滑动窗口协议 (续 )
2) 接收方
(a)维护三个变量：
接收窗口大小 (RWS):给出接收方所能接收的无序帧数目的上界；
最大的可接收帧（ LAF）,用于标识帧的最大序号；
收到的最后一个帧 (LFR):指序号,最大的,(在假设序号足够用的情况下 )
2.8.2 滑动窗口协议 (续 )
(b)维护一个等式
LAF-LFR<=RWS
<=RWS
LFR LAF
收方的滑动窗口
2.8.2 滑动窗口协议 (续 )
(c)接收方的算法,
当一个具有序号 SeqNum的帧到达时，接收方采取如下行动：
如果 SeqNum? LFR 或 SeqNum > LAF，
那么 帧不在接收窗口内，丢弃它；
如果 LFR? seqNum? LAF,
那么 帧在接收窗口内，于是被接收。
2.8.2 滑动窗口协议 (续 )
设 SeqNumToACK表示未确认的帧的最大序号，则,
如果 序号小于等于 SeqNumToACK的帧都已收到,
那么 确认该帧,并设 LFR = SeqNumToACK，
LAF=LFR+RWS
或者进行有选择确认：
如果 接收方能够准确地确认那些已收到的帧,
那么 可以更好地保持管道满载,但更复杂,
可选择,否认帧：为某个未到的帧发此帧
2.8.2 滑动窗口协议 (续 )
3.有限序号产生的问题,
如何区分同一序号的不同次发送?
或者说,
至少要有多少可用序号,才能满足协议要求,
答案,
如果 RWS=1,则 MaxSeqNum≥ SWS+1
如果 RWS=SWS,则 SWS<(MaxSeqNum+1)/2
提示,只有在临界点会出错,即最大帧收到,但 ACK丢失,
2.8.2 滑动窗口协议 (完 )
(?)滑动窗口协议有 3个不同的功能，
(a) 在不可靠链路上可靠地传输帧 ---算法的核心功能
(b) 用于保持帧的传输顺序 (缓存错序到达的帧 )
(c) 支持流量控制，它是一种接收方能够控制发送方使其降低速度的反馈机制。
2.8.3 并发逻辑信道基本思想是：
在一个点到点链路上多路复用多个逻辑信道，并且在每个逻辑信道上运行停止等待算法。
在任意逻辑信道上传输的帧之间没有任何关系，因为在每个逻辑信道上可以有一个不同的待确认帧，发送方可保持链路满载。
2.8.3 并发逻辑信道 (完 )
发送方为每一信道状态留有 3个比特：
（ 1）一个布尔量,说明信道当前是否忙
（ 2） 1比特序号,用于说明下次在这个逻辑信道上发送的帧；
（ 3）以及下一帧的序号,用于说明期望到达这一信道的一个帧。（即期望接收的序号）
当结点有一个帧要发送时，它使用序号最小的空闲信道，其它行为就象停止等待一样 。
小结前面所有的知识是如何配合工作的？
设,1）采用 4B/5B编码。 2） NRZI编码 3）比特填充法 。
4） CRC帧校验。 5）停止等待协议。
问,实际的工作流程如何？
分析：以数据,Hello World” 从 A?B的过程为例
1） 拆成两个数据,Hello”,,World” 。 2） 转换成
ASCII编码。 3） 视数据为比特，加上帧结构信息，进行比特填充。 4） 附加上 CRC校验码。 5） 将 4）中得到的比特集进行 4B/5B编码转换。 6） 以 NRZI再次编码，
并最终发送至线路。 7) 经停止等待协议的控制在接收方得到两个,正确的,数据包。 8） 在接收方此过程逆向进行。
数据链路层协议原始数据上层协议原始数据帧头 帧尾数据链路层协议帧头 封装上层数据 帧尾 CRC
4B/5B编码
NRZI编码物理链路
4B/5B解码
NRZI解码收集帧 过程分析完整的帧原始数据上层协议原始数据帧头 帧尾帧头 封装上层数据帧尾 CRC
通过校验比特恢复
CRC计算
CRC计算比特填充停止等待协议小结至此已经可以在收发双方正确的传送以帧为单位的数据，当然分析中可知正确性是由概率来保证的,为了进一步保证数据的正确性，
可以在更高层的协议进一步使用检错机制。
如在文件传输中，可以整个文件为单位再附加一个 CRC码，当每个帧的数据最终组成文件后再校验一次，也有使用 MD5算法作为校验方式的，归根结底,正确性 是一切远距离通信中最需要，也是最难保证的事情。
下一步的工作解决共享介质的公平访问问题。
局域网 (LAN)概述
覆盖范围小,房间、建筑物、园区范围距离 ≤25 km
高传输速率 10Mbps～ 1000Mbps
低误码率 10-8 ～ 10-10
采用总线、星形、环形拓扑
双绞线、同轴电缆、光纤
为一个单位所拥有，自行建设，不对外提供服务
1,LAN的特点
hub
hub
hub
Switch
Server
farm
station
stations
stations
2,IEEE802 标准主要有 12种。
1.IEEE802.1,
概述，局域网体系结构以及网络互连
2.IEEE802.2,
定义了逻辑链路控制子层的功能与服务
3.IEEE802.3：
描述 CSMA/CD总线式介质访问控制协议及相应物理层规范
2,IEEE802 标准 (续 )
4,IEEE802.4：
描述令牌总线（ token bus） 式介质访问控制协议及相应物理层规范
5,IEEE802.5：
描述令牌环（ token ring） 式介质访问控制协议及相应物理层规范
6,IEEE802.6：
描述市域网（ MAN） 的介质访问控制协议及相应物理层规范
7,IEEE802.7：
描述宽带技术进展
2,IEEE802 标准 (续 )
8,IEEE802.8：
描述光纤技术进展
9,IEEE802.9：
描述语音和数据综合局域网技术
10.IEEE802.10：
描述局域网的安全与解密问题
11.IEEE802.11：
描述了无线局域网技术；
12.IEEE802.12：
描述用于高速局域网的介质访问方法及相应的物理层规范。
2,IEEE802 标准 (续 )
13.IEEE 802.13：
保留
14.IEEE 802.14,
描述了交互式电视网（包括 Cable Modem）
以及相应的技术参数规范
15.IEEE 802.15,
描述了无线个人区域网络
16.IEEE 802.16,
描述了宽带无线接入技术
3.MAC地址
IEEE802标准为每个厂商生产的网卡规定了一个 48位的全局地址 (MAC),它是 全球唯一的,MAC地址的 高 24位 由 IEEE统一分配给厂商，
低 24位 由厂商分配给每一块网卡。
网卡的 MAC地址可以认为就是该网卡所在站点的 MAC地址。
计算机间的通信不是基于 IP,而是基于 MAC.
IP只是用于路由过程,
2.9 以太网 （ 802.3）
2.9.1 物理特性收发器适配器主机以太网收发器和适配器以太网电缆
2.9.1 物理特性
1,带宽有多种选择,10M 100M 1000M
2,长度限制,2500米
3,任意 两台主机间的中继器 不超过 4个,
4,分接头 至少相隔 2.5米
2.9.2 802.3布线介质标准
10Base2 细同轴
10Base5 粗同轴
10BaseT 双绞线
10BaseF MMF
100BaseT 双绞线
100BaseF MMF/SMF
1000BaseX 屏蔽短双绞线 /MMF/SMF
1000BaseT 双绞线附,IEEE 802.3 规范传统以太网
802.3 —— 同 轴电缆 Ethernet
802.3a —— 细缆 Ethernet
802.3i —— 双绞线
802.3j —— 光纤快速以太网 FE
802.3u —— 双绞线，光纤千兆以太网 GE
IEEE802.3z —— 屏 蔽短双绞线、光纤
IEEE802.3ab —— 双绞线
2.9.3 帧结构
CRC数据区类型 /长度源地址目标地址前缀
64 48 48 16 32
每帧最多包含 1500B,最少包含 46B,以太网是一个面向比特的成帧协议,
1500B的上界意味着适配器只能以一段有限时间占用线路。
2.9.4 适配器工作方式
1,发送到网络上的数据可被所有主机,侦听,
到,
2,每个适配器只接收,
1) 目标地址是自己地址的帧,
2) 目标地址是广播地址的帧,
3) 目标地址是本机监听的多点广播的地址的帧
4) 适配器是可编程的,处于混杂模式时可接收所有帧,
2.9.5 传输过程
1,接收方侦听每一个帧,并将符合条件的帧发给主机,
2,发送方必须以某种方式避免冲突,并在特定条件满足的情况下发送数据,
3,这些过程是网络适配器负责完成的,
以太网的问题：
以太网上的任意一个主机传输的数据都能够到达 所有其它主机 。所有主机竞争访问 同一条链路,处在同一个冲突域中。
总线
A B C
C
D E F
附,冲突
1.要发送的站首先监听信道，判断是否有其他站正在发送（载波监听）
如果 信道正在被使用，
那么 站点等待；
如果 信道空闲，
那么 站点发送数据；
发送后 等待确认，收到确认，成功 ;否则，
重发。
2.9.6 CSMA技术
2.9.6 CSMA技术（续）
2,1-坚持算法
1） 如果 信道空闲，发送；
否则,转 2）
2） 如果 信道忙，
那么 继续监听直到信道空闲，
然后立即发送。
2.9.6 CSMA技术（续）
3,P-坚持算法同 1-坚持算法，但在发送时计算一个概率，以计算结果确定自已是否发送。
4,发送方必须知道自己发送的帧是否与其它主机发生冲突。
要求,确保帧能够无冲突的到达最远主机。
解决方案,发送方的发送时间必须足够长，
足以检测到冲突，因为只有在发送时发生的冲突才是自己的数据发生的冲突。
5,如果在发送过程中检测到冲突，发送一个简单的干扰信号保证所有站点都知道发生冲突并停止发送。 (谁先测到谁先发,)
发完干扰信号后，随机等待一段时间，重传（从 1)开始重复）
2.9.6 CSMA技术（续）
检测冲突所需的时间不超过端到端传播时延的两倍
(a)
(b)
(c)
(d)
BA
BA
BA
BA
例,最小传输量设在 10Mbps的以太网,RTT=51.2us,为了能够了解到冲突,传输方至少应发送多少数据?
解,
m=51.2× 10-6× 10× 106
=512 (b)
802.3标准与以太网区别
1.区别,帧的长度 /类型字段。 (P77)
2.解决方法是,该字段中的值大于帧的最大长度 (1518)，则表示为类型,否则表示是长度，即 802.3 标准。
3.具体做法是,以 1536(十六进制 0600)为界，
大于或等于 0600H 认为是以太网，按类型处理，如 IP为 0800H,XNS为 0600H,IPX为
8137H 等，类型字段指明上层所用的协议。
2.9.7 以太网的经验以太网在轻载情况下工作很好，很实用
1） 大部分以太网以比标准允许的方式更保守的方式使用。
2） 即使以太网适配器没有实现链路层流量控制，主机通常会提供端到端流量控制机制 ---很少出现任意一个主机连续把帧送到网上的情况。
1）以太网极易管理和维护，不存在出故障的交换机，也没有需要不断更新的路由选择或配置表，
2）易于向网络增加一个新的主机。
3）便宜，唯一的其它开销仅是每个主机上的网络适配器。而任何基于交换的方法除了每个适配器增加的开销外，将包括一个昂贵的基础构件（交换机）。
2.9.8 以太网的优点小结以太网通过 载波监听 了解其他主机的行为,初步避免冲突,如果还是发生了冲突,
则通过 指数退避 技术避免进一步的冲突 ;
如果冲突还是不断发生,主机 停止发送,减轻网络负载,希望能恢复网络性能 ;如果还是无效,称 以太网崩溃,
公平共享介质 通过最长数据长度实现,
2.10 令牌环网
2.10.1 令牌环思想一个令牌在环上循环，
每个结点收到令牌后转发它。当一个有帧要传输的结点看到令牌时，它把令牌从环上取下，而将自己的帧插入环中。沿路的每个结点简单地转发帧，目的结点存一个该帧拷贝，
然后继续转发该帧。
2.10.1 令牌环特性
1.隐患及解决方案隐患,某个结点故障可能导致整个网络失效。
解决方案,使用继电器来自于前一个主机 到下一个主机主机继电器来自于前一个主机 到下一个主机主机继电器
2.10.1 令牌环特性
MSAU
来自前一个 MSAU
到下一个 MSAU
主机主机主机主机多站访问单元
2.10.1 令牌环特性
2,优点
1) 每个下游的结点将有机会发送一个帧。介质访问算法是公平的。
2) 可以引入监控站对整个网络进行故障管理。
2.10.2 令牌环方案
1.信号单向传递,在令牌环网中信号只单向传递,
2.环路容量,即环路的容量要大于等于令牌长度,
3.令牌持有时间,即为了公平共享介质而要求任一主机一次持有令牌的时间不得大于,令牌持有时间,
4.可靠传控制,在帧尾部附加 2比特标志数据是否成功传递到目标主机,1) A=0,C=0,目的站不存在或未加电。 2) A=1,C=0,目的站存在但帧未被复制。 3)A=1,C=1,目的站存在并且帧被复制,。
2.10.2 令牌环方案
5.优先级支持,
令牌及帧是有 优先级 的,只有 大于等于 令牌优先级的帧才能被发送,
1) 要发送高优先级帧的主机修改经过自身的当前帧的优先级位,
2) 该帧回到发送者 (即令牌持有者 )时,令牌持有者调高令牌优先级并释放出去,
3) 只有不低于新的优先级的帧才允许被发送,
由发送者负责将优先级调回原值,
6.令牌释放,
1) 早期释放,发完帧后立即释放令牌,
2) 延期释放,待发送的帧环绕一周后释放令牌,
2.10.2 令牌环方案
7.错误恢复
1) 监控站,由预定义的方案产生,
2) 监控站 负责保证“环路容量”足够存放令牌,
3) 监控站 负责在令牌毁损或丢失的情况下 恢复令牌 及 清除坏帧,
小结令牌环通过 令牌的持有与释放 实现对共享介质的公平访问,由于一次只可能有一个令牌持有者且信号单向传递,在令牌环中不存在冲突 ;
令牌环能够实现更多的控制功能,能够进行集中式管理,能够定义优先级,
说明以太网和令牌环网的介绍中着重的是它们如何解决共享介质的公平访问问题,在任何网络中同样存在着检错和传输控制的任务。要理解三者是叠加的关系而不是平行的。
比如在以太网中，一个主机如果成功发送了数据，
接收方为了发送 ACK,必须参与下一轮对共享介质的竞争；同样，主机要重发数据也必须参与新一轮对共享介质的竞争在令牌环网中也会存在突发错误等情况，因此也会使用 CRC等检错方法，及使用等待重传等传输控制协议。
2.11 FDDI
2.11.1 拓扑结构双环结构：其中一条环是作为备用环
2.11.1 拓扑结构降低成本的实用方案
2.11.2 FDDI参数
1,最多 500个站点
2,光纤总长限制为 200KM
3,使用 4B/5B编码
4,时控令牌算法
5,令牌维护
6,帧格式状态帧结束CRC数据源地址目标地址控制帧开始
2.12 无线网
2.12.1 扩频技术
1.跃频扩频：它在一个随机的频率序列上传输信号； (伪随机 )
1)发方,首先以一个频率传输，然后是第二个，
然后第三个，依次类推。
2)接收方,使用与发送方相同的算法（且用相同的初值来初始化），因此能够与发送方同步跃频以正确接收帧。
2.12.1 扩频技术
2.直接序列它通过用被传输信号中的多个比特表示帧中的一个比特来获得相同的效果。
1
0
1
0
1
0
数据流,1010
随机序列：
0100101101011001
两者的异或：
1011101110101001
2.12.2 无线网特点
1.特点：
并非所有的结点可达（与以太网不同）。
2.存在隐藏结点,
假设 A和 C都想与 B进行通信，都向 B发送一帧。
这两个帧在 B互相冲突,A和 C都不知道这一冲突。
称 A和 C是关于对方的隐藏结点,
BA C D
2.12.2 无线网特点
3.存在暴露结点
B正向 A发送数据。结点 C发现到这一通信，如果 C只是因为听到 B的传输就认为它不能向任何结点（如 D结点）传输，这将是错误的。
BA C D
2.12.3 MACA
所有可达站在传输数据前都要交换控制帧
1) 过程：
发送方,给接收方发一个请求发送 （ RTS） 帧； RTS
帧包括一个表明发送方希望占有介质多久的字段 （ 即,
它指定要传输的数据帧的长度 ） 。 接收方,用一个清除发送 （ CTS） 帧应答；该帧向发送方回应这一长度字段 。
2) 处理方案,
看到 CTS帧的任意结点 知道它离接收方很近,因此在发送指定长度的帧的这段时间内不能传输 。
2.12.3 MACA
看到 RTS帧而不是 CTS帧的任意结点 离接收方不太近,不会干扰接收方,因此可以自由传输 。
（ 但要保证发方正确的收到 CTS）
BA C D
2.12.3 MACA
说明：
（ 1） 接收方在成功接收了一帧后向发送方发送一个 ACK。 所有结点在试图传输之前必须等待该 ACK
（ 2） 如果两个或多个结点同时检测到一个空闲链路并试图传输一个 RTS帧，那么它们的 RTS帧将彼此冲突。 802.11不支持冲突检测，但发送方在一段时间之后没有收到 CTS帧时，它就意识到发生了冲突。在这种情况下，它们都等待一个随机时间量后再试,(类似以太网的二进制退避算法 )
本章总结第二章综合解决了网络的基本问题,利用这些知识能够构建起最基本的网络形式,从层次上看,
它属于数据链路层的问题,
归纳来说,本章主要讨论并解决了以下问题,
1） 将数据以帧为单位划分
2） 通过校验、确认、反馈重发确保数据链路的无差错。
3） 进行流量控制，使得在高速的收发双方能协调配合。
下一步要考虑的是网络规模扩展带来的问题。
