chapter4: 介质访问控制子层
4.1 信道分配问题
4.1.1 静态信道分配
主要考虑FDM(频分多路复用)和TDM(时分多路复用)。
4.1.2 动态信道分配的假设
流量独立、单信道、冲突可观察、时间连续或分槽、载波侦听或不听
4.2 多路访问协议
4.2.1 ALOHA
纯ALOHA
当发送站有数据时就发送，如果该帧成功传输，中央计算机会把该帧重新广播给所有站，那个发送站以此来确认是否成功发送帧。
如果帧传输失败了，发送站在超时之后就随机等待一段时间再次发送帧。
分槽ALOHA
把纯ALOHA的连续时间改为时间槽。每个时间槽对应一帧，帧的传输必须是在时间槽开始时刻。
4.2.2 载波侦听多路访问协议CSMA
1-坚持 CSMA(Carrier Sense Multiple Access)
发送帧前先一直侦听信道，等到信道空闲就发送，发生冲突就随机等待一段时间再开始上述过程。
非坚持 CSMA
发送帧前先侦听一下信道，如果空闲就发送，如果信道忙，就随机等待一段时间再侦听。
p-坚持 CSMA
发送帧前先侦听一下信道，如果空闲就以概率p发送数据，以概率1-p延迟到下一个时间槽，如果下一个时间槽信道也空闲，就以概率p发送数据……，这个过程一直重复，直到帧被发送出去或者遇到信道忙随机等待一段时间再开始。
如果信道忙，就随机等待一段时间再重新开始。
CSMA/CD
带冲突检测的CSMA，在0时刻，一个站完成了帧的传送，其他需要发送帧的站试图发送。假设有AB两个站同时要发送数据，A站、B站都侦听到信道空闲，都发送数据，产生了冲突。检测到这种冲突之后，它们立即停止发送，并随机等待一段时间之后，再重新开始。假设A等待的时间比B短，则A就会先发送出这一帧。
4.3 以太网
4.3.1 经典以太网物理层
经典以太网用一个长电缆连接所有计算机。
4.3.2 经典以太网MAC子层协议
帧结构
最小帧长需要64字节(目标地址开始到校验和，数据字段最少46字节)。理由如下：以10Mbps的速率，发送一位需要100ns，而最差的情况下，最大传播时间$\tau=25us$，所以一帧最少有$2\tau/t=500$位，该值被增加到512位，即64字节。
二进制指数后退的CSMA/CD
CSMA/CD：发送帧前先侦听信道，如果信道空闲则立即发送，同时检测是否有冲突，有冲突就立即终止传输，并发出一个短冲突加强信号，随机等待一段时间后重发。
对于以太网，第i次冲突发生后的随机等待时间为$0\to2^i-1$，最大为1023，且16次冲突之后放弃发送。这个算法称为二进制指数后退。
如果没有发生碰撞，发送方就认为帧成功传递。不提供确认服务。适用于出错率很低的有线电缆和光纤通信。
4.3.3 以太网性能
针对每个帧e(数学常数)个竞争时间槽的最佳情况，设以太网中帧的长度F、网络带宽B、电缆长度L、信号传播速度c。则：
$$
信道效率=\frac{1}{1+2BLe/cF}
$$
4.3.4 交换式以太网
交换机：发送发把帧发送给交换机，交换机把帧输出到该帧想要去的端口。当交换机端口接收到来个某个站的以太网帧，它就检查该帧的以太网地址，确定该帧前往的目的地端口。
4.3.5 快速以太网(Fast Ethernet)
将原以太网的比特时间从100ns降低到10ns。同时为了确保CSMA/CD算法工作，必须保持最小帧长和最大电缆长度（两个站之间最大传播时间）的关系。最简单的选择是把任意两个站的最大距离降低十倍，采用交换机的方式解决。
4.3.6 千兆以太网(Gigabit Ethernet)
全双工模式
这种模式允许一台交换机将周围的计算机连接起来，在这种配置下，所有的线路都具有缓存能力，所以每台计算机或者交换机在任何时候都可以自由地发送帧。
半双工模式
计算机被连接到一个集线器而非交换机，要求使用标准的CMSA/CD协议，与此同时因为现在的传输速率是经典以太网的100倍，所以线缆的长度下降了一百倍，只有25m。考虑到25m的长度限制实在太痛苦，因此标准中增加了两个特性来使得最大线缆长度增加到200m。
载波扩充：在普通的帧后面增加一些填充位，将帧的长度扩充到512字节。
帧突发：允许发送方将多个帧级联在一起，一次传输出去。如果级联起来的帧仍小于512字节，则硬件会对它进行再次填充。
扩展帧
加入了暂停帧和巨型帧。
4.3.7 万兆以太网
只支持交换机的全双工模式。
4.4 无线局域网
4.4.1 802.11体系结构和协议栈
分布式系统(distributed system)
每个客户端都与一个接入点(AP,Access Point)相关联，该接入点有与其他网络连接。客户端发送和接收数据包都要通过AP进行。几个接入点可通过可以通过一个称为分布式系统的有线网络连接起来。
自组织网络(ad hoc network)
网络由一组互相关联的计算机组成，它们相互之间可以直接给对方发送帧。
介质访问子层(MAC,Medium Access Control)
决定如何分配信道，也就是说下一个谁可以发送。
逻辑链路控制(LLC,Logic Link Control)
它的工作是隐藏802系列协议之间的差异，使它们在网络层看来并无差别。
4.4.2 802.11物理层
速率自适应(rate adaption)
如果无线信号较弱，采用较低的速率；如果信号很清晰，可使用最高速率。
4.4.3 802.11 MAC子层协议
分布式协调功能(DCF，Distributed Coordination Function)
必有的操作模式。每个站都独立行事，没有任何一种中央控制机制。在这种模式下，MAC子层采用带冲突避免的CSMA协议。
点协调功能(PCF, Point Coordination Function)
可选的操作模式，这种模式下，AP控制自己覆盖范围内的一切活动，就像蜂窝中的基站一样。
带冲突避免的CSMA(CSMA/CA)
需要发送帧的站需要通过侦听确定在一个很短的时间内没有信号，然后倒计数空闲时间槽（时间槽数范围在0-15之间），当有帧在发送时暂停该计数器；当计数器递减到0，该站就发送自己的帧。
如果帧发送成功，目标站立即发送一个短确认。
如果收到确认，则结束此次通信。
如果没有收到确认，则可推断出传输发生了错误，这种情况下发送方要加倍后退选择的时间槽数，再重新试图发送。如此反复，连续像以太网那样以指数后退，直到成功发送帧或者达到重传的最大次数。
RTS/CTS机制
隐藏终端问题
A希望给B发送数据，而此时C已经在给B发送数据，而A无法侦听到C，因此A认为现在它可以给B发送数据了。显然，这样会导致冲突发生。
暴露终端问题
A正在传输数据，而B希望给发送C发送数据，B在侦听信道时发现有帧在传输，便认为此时无法给C发送数据，但可能A在给D传输，而B给C传输不会影响这一过程(D不在B在传播范围内)，浪费了一次传输机会。
网络分配向量(NAV,Network Allocation Vector)
每个帧携带一个NAV字段，说明这个帧所属的一系列数据将传输多长时间。无意中听到这个帧的站就知道由NAV所指出的时间段信道一定是繁忙的。
在可选的RTS/CTS协议中，当A决定向B发送数据时，A首先给B发送一个RTS帧，请求对方的允许。如果B接收到这个请求，它就以CTS帧作为应答，表明信道被清除可以发送。一旦收CTS，A就发送数据帧，并启动一个ACK计时器。当正确的数据帧到达后，B用一个ACK帧回复A，完成此次交流。如果A的ACK计时器超时前，ACK帧没有返回，则可视为发生了一个冲突，经过一次后退（CSMA/AD规定），整个协议重新开始运行。
假设C在A的范围内，因此它可能会收到RTS帧，如果收到了，他就根据RTS帧的信息，估算出需要传多长时间，包括最后的ACK。它通过更新自己的NAV记录表明信道正忙，停止传输。
假设D在B的范围内，如果它没有收到RTS但收到了CTS，它也会更新自己的NAV，提醒自己在一段时间内保持安静。
但这种机制已被证明在实践中几乎没有任何价值，首先，它对短帧（替代RTS发送）或AP（大家都能彼此听到）一点好处都没有。对于其他情况该机制只会降低操作速度。它只对有助于解决隐藏终端的问题，而无助于暴露终端的问题。大多数情况下隐藏终端不多，而且CSMA/CA通过后退发送失败的站可以缓解隐藏终端的问题，使得传输更可能获得成功。
可靠性问题
对于无线网络，可靠性很差，帧成功传输的概率很小，再确认和重传帮助不大。
解决方案一：降低传输速率
在一个给定的信噪比环境下，速度放慢可以使用更健壮的Modem技术，增加传输的成功率。如果太多帧丢失，站可以降低传输速率，如果帧传输时损失很少，则站可以测试是否可以采用较高的速率来传输帧。
解决方案二：发送短帧
802.11允许把帧拆分为更小的单元——称为段。每个段有自己的校验和，段的大小由AP调整。这些段独立编号，使用停-等式协议对其进行确认。一旦获得信道，可以突发多个段，这些段一个接着一个发送，两个段之间是从收到上一个段的确认开始（或者从计时器超时重传开始）直到整个帧被成功发送（或者计时器超时）。NAV机制保证了其他站在该帧传输期间保持沉默，直到下一个确认。
省电
信道帧
信道帧由AP定期广播，该帧向客户通告AP存在，同时传递一些系统参数，比如AP的标识、时间（下一帧多久到来）和安全设置。
省电模式(power-save mode)
客户端可以在它发送到AP的帧中设置一个电源管理位(power-management)，告诉AP自己进入省电模式。在这种模式下，客户端可以打个盹，AP将缓冲发给客户的流量。为了检查入境流量，客户端在每次信标帧来时苏醒过来，并且检查作为信标帧一部分的流量图，查看AP中是否有为自己缓冲的流量。如果有，客户给AP发送一个poll消息，告诉AP将缓冲的流量发送过来。在接收了缓冲的流量之后，客户可以再回去打盹，直到下一个信标帧被发送出来时苏醒。
自动省电交付(APSD,Automatic Power Save Delivery)
AP依然为休眠的客户端缓冲帧，但只在客户端发送帧到AP后才将其缓存的帧发送到客户端。这样依赖，客户端可以安心进入睡眠状态，直到它有更多流量需要发送(和接收)时才醒来。
服务质量
802.11e
802.11扩展了CSMA/CA，并且仔细定义了帧之间的各种时间间隔。
4.4.4 802.11帧结构
帧控制(Frame Control)字段
协议版本(Protocol Version)
用于在同一个蜂窝内同时运行协议的不同版本。
类型(Type)
数据帧、控制帧或管理帧。
子类型(Subtype)
比如RTS和CST。
去往来自DS
表明该帧时发送到或者来自与AP连接的网络，该网络称为分布式系统DS。
受保护的
表明该帧被加密。
持续时间(Duration)字段
通知本帧和确认帧将会占用信道多长时间。
地址(Address)字段
第一个地址是接收方地址，第二个地址是发送方地址，第三个地址是中继点地址。
4.8 数据链路层交换
4.8.2 学习网桥
如果一个端口连接了多个站，就有可能发生冲突，需要使用CSMA/CD协议。
考虑a的拓扑结构，如果站A发送一个帧给B，网桥B1将在端口1上接收该帧，然后立即舍弃，因为它已经在正确的端口上。
考虑b的拓扑结构，如果站A发送一个帧给B，网桥B1在端口1上接收该帧，并从端口4发出，网桥B2在端口4接收该帧，并从端口1发出。
泛洪算法(flooding algorithm)
网桥第一次被接入网络时，所有的哈希表都是空的，对于每个发向未知目的地址的入境帧，网桥将它输出到所有端口，除了它来的那个端口。随着时间的推移，网桥将学习到每个目的地址在哪，发给该地址的帧只会放到正确的端口。
向后学习法(backward learning)
由于网桥工作在混杂模式下，可以看到每个端口上发送的所有帧，通过检查这些帧的源地址，网桥就可获知通过那个端口可以访问到哪些机器。
当打开、关闭或者移动机器和网桥时，网络的拓扑结构会发生变化。为了处理这种动态的拓扑结构，一旦构造出一个哈希表后，帧的到达时间也会记录下来。当一帧到达，如果它的源地址已经在表中，那么对应表项中的时间被更新为当前值。
网桥中有一个进程定期扫描哈希表，并且把那些时间值在几分钟以前的表项全部清除掉。
直通式交换(cut-through switching)或虫孔路由(wormhole routing)
每到达一个帧，都要使用泛洪算法，所以通过一个芯片来查找和更新哈希表。因为网桥在看到MAC地址就可决定如何转发帧，或者有可能一旦从入境线路输入帧的目的地址字段(之前提到过一帧有三个地址，源地址，目的地址和中继地址)就可转发，此时帧的其他部分还在输入，即在完整接收一帧前就开始了转发。这种方式就是直通式交换。
4.8.3 生成树网桥
冗余链路带来的循环问题
考虑A给以前没观察到的某个站发生帧，这个帧到达B1，网桥把这一帧泛洪，B2收到F1，泛洪发送了F4，收到F2，泛洪发送F3，F3，F4到达B1之后，因为是没观察的到站，又进行泛洪，一直循环。
这个问题的解决途径就是让网桥互相之间通信，然后用一棵可以达到每个网桥的生成树覆盖实际的拓扑结构。
生成树算法
为了建立生成树，每个网桥周期性地从他的所有端口广播一个配置消息给邻居，同时处理来自其他网桥的消息。
1.确定根桥：选择具有最低标识符的网桥作为根。经过足够的消息交换和扩散，最终所有网桥同意这个根。
2.构造每个网桥的最短路径树。B1可以直达B2、B3，最短路径都是一跳，从根通过B2或B3到达B4，最短路径都是两跳。选择一条经过具有最低标识符的网桥路径。因此到达B4的路径经过B2。经过B3两调可以到达B5。
为了找到这些最短路径，网桥在配置消息中还包括与根的距离。每个网桥记住它找到根的最短路径。然后，顽固掐关闭那些不属于最短路径的端口。
4.8.4 中继器/集线器/路由/交换机/路由器和网关
中继器
工作在物理层，中继器是模拟设备，主要处理自己所连线缆上的信号。在一个线缆上出现的信号被清理、放大，然后放到另一个线缆上。
集线器
集线器有多条输入通道，它将这些输入线路连接在一起。从任何一条线路上到达的帧都被发送到其他的线路上，如果两帧同时到达就会发生冲突。
网桥
网桥连接多个局域网，具有多个输入线。与集线器不同的是网桥的每个端口被隔离成它自己的一个冲突域。全双工，不需要CSMA/CD算法，半双工需要。采用泛洪算法发送帧。
网桥比集线器有更好的性能，且输入线路可以以不同速度运行。
交换机
现代网桥的另一个称呼。
路由器
当一个数据包进入路由器后，帧头和帧尾被去除，路由软件利用数据包的头信息来选择输出线路。包头中含有ipv4/6的地址，而不是48位的802地址。路由软件看不到帧地址，不知道数据包来自哪个LAN或者点到点线路。
网关
传输网关
假设两台使用了不同传输协议的计算机需要通信，传输网关将数据包从一个连接复制到另一个连接上，并且根据需要对数据包重新进行格式化。
应用网关
理解数据的格式和内容，并且可以将消息从一种格式转换为另一种格式。