t=0
A
t
L
B
碰撞
B 发送数据
A 检测到发生碰撞
B 检测到发生碰撞
t= t=
t = 2
单程端到端 传播时延记为
CSMA/CD的性能 (4.3.5 以太网的性能)
平均NR个竞争周期
竞争周期 竞争周期 … 竞争周期
传输周期 成功发送 T0
2
2
2
t
发送一帧所需平均时间TAV

假设所有帧等长，称传输一个帧所需要的时间为帧时； 假设每个帧时中帧的到达服从泊松分布，平均到达率为G。 吞吐量S=GP0，P0是一帧没有冲突的概率 在t个帧时内产生k帧的概率服从泊松分布
(Gt ) k eGt Pr[ N (t ) k ] k!

在两个帧时内生成零帧的概率（无冲突）为 P0=e-2GS=Ge-2G

4.2.1 ALOHA－纯ALOHA
一个帧时 N1 N2 N3 M3j M11 M1i 随机时间 M1i 随机时间 M2k M3j
Ni
Mi1
信道
M11
Mi1
M1i
M2k
M3j

想说就说：每当用户有数据要发送，立刻发送 发送方通过广播的反馈特性侦听信道，可以知道是否发生 了冲突；若发生冲突，则发送方等待一段随机的时间，再 次发送该帧，直到发送成功为止
实现通信实体间良好的连通性，获得尽可能高
的吞吐量。 良好的报文时延特性。

分类：
静态信道分配方案 动态信道分配方案
4.1.1 静态信道分配方案

静态的信道分配方案
FDM频分复用 TDM时分复用 将信道均分为若干个子信道，每个子信道为一
个用户所独占。
FDM系统的性能分析： N个子信道时，每个子信道的带宽为C bps，帧到 达率为每秒帧 平均帧长为1/µ bit 子信道平均服务率为每秒µC帧 若到达率和服务速率均服从泊松分布，数据帧的 平均时延TFDM
通过逻辑连接，差错控制，流量控制等办法
当不需要可靠性时，LLC可以是很薄的一层，甚至省
略。
底层信道对 LLC 子层是透明的
LLC 子层看不见 下面到底是广播式信道还是点到点信道
网络层 网络层
逻辑链路控制
媒体接入控制
LLC
MAC 广播式信道
LLC
MAC
数据 链路层
物理层
站点 1
物理层
站点 2
max

T0 1 T0 (2e 1) 1 4.44a
其中a表示以帧时为单位的归一化传播时延，设F为帧长， B为网络带宽，L为电缆长度，c是信号传播的速度，则 有：
BL a T0 cF


2 =51.2us, B=10Mbps时的网络性能
1 BL ,a , A kp(1- p) k 1 1 a(2 A1 1) cF

S=Ge-2G，当G=0.5时，Smax=1/2e≈0.184
时隙ALOHA（Slotted ALOHA）

将时间分成离散间隔（slot），所有用户遵守统一 的时隙边界，用户只能在时隙开始时发送数据
一个帧时 N1 N2 N3 M31 M11 M1i M2k 随机时间 随机时间 M2k M1i
Ni

4.1.2 动态信道分配方案

通常采用的信道访问方法有两类
随机访问：各节点根据自已的意愿发送数据，
Hale Waihona Puke 可能会产生冲突。分布式，节点间协作化解冲 突。 受控访问：通过某种控制机制使得任何时刻只 有一个接点接入信道，需要一个仲裁机制，可 以是集中式的，也可以是分布式的。
4.2 多路访问协议
随机接入类（亡羊补牢） 无冲突类（防患于未然）

自适应树搜索协议：把站点看作是二叉树的叶子
自适应树搜索协议原理

在一次成功传送之后的第一个时隙，slot 0，所有的 站都允许尝试获取信道，如果发生了冲突，则在slot 1中，只有树中2号节点之下的那些站才可以竞争。如 果其中之一获得了信道，则这一帧之后的那个时隙被 保留给节点3下面的那些站。另外，如果节点2下面的 两个或者多个站希望发送数据，在slot 1中会发生冲 突，则slot 2就由节点4下面的站来竞争。
坚持对信道的检测，以利于及时知道信道的忙闲情况，
避免浪费。 即便发现信道空闲，也不一定非要坚持发送，若某个 结点能主动退避一下的话，可以减少冲突的可能性。
Q：0.01坚持的CSMA在G=9时整体性能如何？

D表示以帧时为单位的归一化平均报文发送 时延
CSMA/CD

带冲突检测Collision detection的CSMA
p-坚持CSMA（时隙信道）

工作原理：
如果信道忙，则发送站持续侦听信道；
如果信道空闲，以概率p发送数据，以概率1-p将
数据的发送延迟到下一时隙并重复这一过程。当 发生冲突时，等待一段随机时间后再重新开始
Mik在结点内等待
Mik到达 Ni τ …… 信道 M1i M2j M3l 持续监测信道直至空闲
4.2.3 无冲突的协议

不再使用随机接入的思路，而是通过某种 机制提前避免冲突。
位图协议（比特映射协议） 二进制倒计数协议。
位图协议（Basic Bitmap Method）



由竞争周期和帧传输周期组成。 每个竞争周期包含N个时隙，如果站点n需要占用 信道，则在第n个时隙中写入1，构成位图。 当所有的N个时隙都通过后，每一个站点都知道 了哪些站点希望发送数据，然后按照数字顺序开 始传送数据

S=Ge-G，当G=1时，Smax=1/e≈0.369
D表示以帧时为单位的归一化平均报文发送时延
4.2.2 载波检测多路访问协议

ALOHA的信道利用率很低，根本原因在于想说就 说，导致了频繁的冲突。 载波检测（载波侦听）（carrier sense）：可以 检测到信道上当前是否有数据在传输 载波侦听多路访问（Carrier Sense Multiple Access,CSMA）--先听再说
边说边听：正在发送数据的站点一旦检测到冲
突，立刻停止发送。 半双工系统

工作流程
先听再说 边说边听 冲突停止 延时再试
CSMA/CD性能分析模型

CSMA/CD由三种状态交替组成
竞争
传输
空闲
竞争周期
竞争周期为2, 是信道上间隔最远的两台 机器间的传播时延 每个节点发出一帧后，在2时间内无冲突， 则可以肯定该帧必将成功发送。
TFDM

若合并这N个子信道为一个信道为N个用户同时提 供服务，对应的平均时延
TFDM 1 1 T NC N N (C ) N
1 C
静态的信道分配方案适用于
适用于用户数较少且每个用户都有平滑的 流量负担（电话局间通信） 不适用于数据流量突发性很大的网络，很 多网络（如LAN）的流量具有突发性和间歇 性特征，业务量和发送速率上都具有很高 的峰值/平均比率，如1000:1
信道
M11
M31
M2k
M1i
时隙ALOHA的性能

危险周期减少一半，系统吞吐率S=Ge-G G=1时，Smax=1/e≈0.368，是纯ALOHA的两倍 每帧平均重传次数随着G的增大而呈指数增长
Pk e (1 e )
k 1 k 1
G
G k 1
E kpk ke G (1 e G ) k 1 eG
第四章 介质访问控制子层

网络的分类
点到点连接的网络 使用广播信道的网络(多用于局域网)

广播信道由多个用户共享，由此产生冲突，关键的 问题是解决信道的争用，即MAC(Media Access Control )。
远端服务器 计算机 路由器 Internet 电缆
数据链路层的两个子层

将数据链路层拆为两个子层：
二进制倒计数法


地址采用二进制编码，开销减少。设d为数据 帧长，N为站点数，则信道利用率为d/(d+log2N) 如果帧格式选择恰当，帧中第一字段为发送方 地址，则效率为100%。
特点
各站需严格同步
公平性差可能的改进？？

4.2.4 有限竞争协议

结合随机访问法和无冲突法的优点：
在轻负载时采用随机访问法来尽快接入信道。 在重负载时采用无冲突法来保证信道利用率。
非坚持CSMA



工作原理：发送站侦听信道，发现信道空闲，则开 始传送数据；如果信道不空闲，则等待一段随机的 时间后再次侦听信道 优点：减少了冲突概率 缺点：增加了信道空闲时间，增大了数据发送延迟
Mik在结点内等待
Mik到达 随机时间 Ni τ 信道忙 信道 M1i τ 信道忙 M2j 随机时间 Mik τ 信道闲 Mik
每帧的平均发送时间TAV N R 2 T0 T0 信道利用率 TAV
CSMA/CD的性能 (4.3.5 以太网的性能)

假设总线上有k个站要传送数据，每个站要发送 帧的概率为p，则在一个竞争周期中总线上只有 一个站发送帧的概率A=kp(1-p)k-1
当p=1/k时，A最大，k→∞时，A→1/e
CSMA/CD的性能分析
max
1 1 4.44

T0

1 BL 1 4.44 cF

电缆越长，竞争周期越长 帧越短，传送帧所需要的时间越短 带宽越大，传送帧所需要的时间越短
信道利用率 就越低。
CSMA/CD不适用于长距离（卫星），高带 宽（光纤）或短帧的网络环境，应寻求其他 解决思路。