计网笔记_6

第6章 链路层和局域网LAN

6.1 引论和服务

链路层的功能基本通过网卡/网络适配器NIC (Network Interface Controller)实现。

存在一些寻址问题和网络控制问题。

链路层导论：包括优先链路、无线链路，也可以分为点对点的链路和多点链路。

主要功能：把分组封装成这个网卡所对应的帧，再通过链路传输给目标节点。

链路层服务：

成帧，链路接入：

将数据封装在帧中，加上帧头帧尾；

如果采用的是共享介质，信道接入获得信道访问权；

在帧头使用MAC media access control 即网卡物理地址来标识源和目的。

在相邻两个节点完成可靠数据传递：

在低出错率的链路上很少使用（光纤、同轴电缆等介质）；

在无线链路上经常使用（出错率高）。

流量控制：使相邻的发送和接收方的速度相匹配；

检错、纠错；

半双工、全双工通信。

适配器通信：

发送方：在帧中封装数据报；加上差错控制编码，实现RDT和流量控制功能等。

接收方：检错，执行RDT和流量控制功能等；解封装数据报，将之交给上层。

RDT: Reliable Data Transfer 可靠数据传输协议。

网卡NIC是半自治的，实现了链路层和部分物理层功能

6.2 差错检测和纠错

EDC：差错检测和纠正位

D：数据由差错检测保护，可以包含头部字段。

差错检测不是100%可靠，协议会漏检，EDC和D也会出错，但是比较少。越长的EDC检错效果会越好。

奇偶校验：

单bit奇偶校验：检测单个bit级错误；

双bit奇偶校验：可以检错也可以纠错，如果是对偶错误，则检测不出来。

CRC：Cyclic Redundancy Check 循环冗余校验：

模2运算：加不进位，减不借位，等价于异或运算（按位，不同为1，相同为0）；

位（比特）串的两种表示：比如：1011 或1*x^3+0*x^2+1*x^1+1*x^0=x^3+x+1；

生成多项式，r次方的比特序列：如G=x^3+1，r次方多项式共r+1位，表示1001；

约定：D | EDC：D位后附上r位冗余位，使数据可以被生成多项式整除，若接收方不能被生成多项式整除，则说明传输过程出错。

R的计算方法：D | R 可以被生成多项式整除：

D * 2^r ⊕ R = n * G （⊕表示模2运算）

等价于：D * 2^r ⊕ R ⊕ R = n * G ⊕ R

等价于：D * 2^r = n * G ⊕ R

两边同除生成多项式G：

R = remainder[D * 2^r / G] （remainder[ ]：表示取余数）

CRC性能：

能检测所有1bit和2bits的错误；

能检查所有长度=r或者<r的错误；

出现长度为r+1的突发错误，检查不出的概率使1/2^(r-1)；

出现长度大于r+1的突发错误，检查不出的概率是1/2^r。

6.3 多点访问协议

多点网络：传统以太网同轴电缆，无线局域网，等。

多点同时发送报文会冲突，比如电磁波信号会相互干扰。

多路访问协议：MAC multiple access control protocol

理想的多路访问协议：

在速率为Rbps的广播信道中，当一个节点要发送时，可以R速率发送，但当有M个节点需要发送时，我们希望每个节点都可以R/M的速率发送，即公平性。而且对于一个理想的协议，它应该不需要特殊节点来辅助协调发送，也不需要时钟和时隙来做同步，当然作为一个好协议最重要的一点，是要尽量简单。

MAC multiple access control 媒体访问控制协议，分类：（三大类）

信道划分：把信道划分成小片（时间、频率、编码等）；

随机访问：信道不划分，允许传输时发生冲突，冲突发生后恢复；

依次轮流：节点依次轮流，但是数据较多的节点可以获得较多的信道使用权。

1. 信道划分：TDMA分时、FDMA分频、CDMA分码，编码方式不一样来划分

2. 随机访问：允许冲突，问题是如何检测冲突，冲突后如何恢复

常见协议：时隙ALOHA、ALOHA、CSMA、CSMA/CD、CSMA/CA

时隙ALOHA：

检测冲突：根据频率和幅度判断冲突的发生；

恢复发送：以时钟同步，都以概率p发送，完全分布，时间越长，冲突概率越小。

效率efficient：最好的频率37%

ALOHA：

不按时隙的时隙ALOHA，按帧时传，帧时小于数据传输时间，效果更差，p=17.5%

CSMA Carrier Sense Multiple Access：载波侦听多路访问：

发之前先听一下信道有没有人在发，有人在发就不发了，在ALOHA基础上减少冲突的可能性，冲突仍然可能发生：听的时候一方已经发了但是因为传播延迟没检测到（局部探知全局），信道延时越大，节点之间距离越远，发生冲突的概率就越大。

CSMA/CD： Carrier Sense Multiple Access with Collision Detection（冲突检测）

侦听到冲突之后发出表示冲突的信号，足够长足够大，让其他节点都知道此时信道冲突。冲突记次数，连续冲突K次之后，节点在长度为2^K的空间中选一个位时传输数据，这就是二进制指数退避，这样连续冲突次数越多，发生冲突的概率就越小，但是导致平均等待时间增加。

比ALOHA更好，简单，廉价，分布式。

CSMA/CA Carrier Sense Multiple Access with Collision Avoid（冲突避免）

无线局域网中，电磁波传输，无法检测冲突，自己的发送信号比接收别人的发送信号强多了，所以不能用CD，而且无线网络中冲突不一定意味着传输失败（覆盖范围大了，能量和频率问题），没冲突也不意味着成功（可能检测不到冲突，冲突信号被挡住了），只能期望CA。

CA的实现：先听信道，信道忙的时候就直接在时序空间里随机选时间，每过一周期-1，为0的时候直接发送，因为CD不了。但是仍然有冲突可能，完全避免冲突，可以先发送预约报文，很小占用信道资源少，冲突了也没事，预约保温发送出去之后可以被信道上的所有节点听到，之后预约过的节点全速发送，其他节点一直发送。

线缆接入网络：

下行：端上只有一个用户CMTS，单向传输，节点上每个节点都检测报文，比较地址，是自己的就拿走，不是自己的就放掉。

上行：所有节点向CMTS预约，预约之后CMTS将预约结果下发给所有节点，然后按预约结果使用信道，如果预约报文本身冲突预约失败，则二进制指数退避。

3. 依次轮流协议taking turns

信道划分MAC在高负载的时候有效且公平，低负载时效率低下，只能用1/N信道。

随机访问MAC低负载时效率高，冲突概率低，单个传输用全部信道，高负载时冲突开销大，二进制指数退避增加平均等待时间。

依次轮流协议taking turns有有两者的优点：

有两种：轮询、令牌token传递

轮询：主节点要求其他所有节点依次轮流，问题是万一主节点挂了，系统就不工作了，存在单点故障问题single point of failure (SPOF)，可靠性较差。

令牌token传递：令牌在节点中轮转（有专门的令牌总线），令牌是特殊帧，有数据需要传输时，拿下令牌放到自己数据帧里（令牌在前数据在后），开始传输，接收端接收到之后，把令牌拿下来再丢到网络中去轮转，有令牌的才能发，没令牌不准发。

Token方法高低负载利用率都很高，但都高不过前面两种“极端情况”信道划分和随机访问。此外，这种也存在风险，token可能会丢，但有办法弥补。

6.4 LANs

MAC地址由IEEE分发，固定不变。

IP地址和MAC地址分开，正常情况下对应不变，换IP网卡不用动，换网卡IP也不用动。

以太网：目前最主流的LAN技术

传统以太网使用的是通过同轴电缆连接的总线型网络。

但是同轴电缆过长的话，一旦电缆有一处受损，整个网络都会瘫痪。

HUB集线器：物理上好像是星形网络，其实逻辑上还是总线型，HUB上的所有设备处在同一个碰撞域内，但是高负载情况下，由于其使用的时CSMA/CD的方式，导致信道利用率很低，所以需要升级。（HUB中每条线路都要匹配，带宽要一致）

SWITCH交换机：HUB的升级版，相当于暂时缓存一个节点发出的数据，再将其发给目标节点，所以可以看作是点对点的连接，是一种点点共享的星型网络，效率提高很多。交换机即插即用，自学习性，无需配置，自动学哪些MAC地址可以通过哪些端口到达，主机无需关心交换机的存在（透明）。

以太帧结构：发送方适配器在以太网帧中封装IP数据报，或其他网络层协议的数据单元。

Preamble + 目的地址 + 源地址 + type + 数据data (payload) + CRC

Preamble前导码：7B 10101010 + 1B 10101011，用来同步接收方和发送方的时钟速率，类似节拍，全1的时候也收。

（CRC在最后，一边发数据一边生成，提高效率）

以太网提供的是无连接、不可靠的服务：

无连接：传输前不握手。

不可靠：接收方适配器不返回ACK或NAK之类的报文。

以太网的MAC协议采用二进制退避的CSMA/CD介质访问控制形式。

低负载时因为CSMA/CD的特性，效率很高，高负载时因为引入了交换机switch，效率也很高。

以太网的标准：标准不一样，帧结构一样但物理层介质不一样。

交换机和路由器对比：

都是存储转发设备，但层次不同：

交换机：链路层设备，检查链路层头部；

路由器：网络层设备，检查网络层头部。

都有转发表：

交换机：维护交换表，按照MAC地址转发（执行过滤、自学习和生成树算法；即插即用，二层设备，速率高；执行生成树算法，限制广播帧的转发）

路由器：维护路由表，执行路由算法（路由算法能避免环路，无需再生成树也可以限制广播分组，还可以按各种拓扑构建网络；不能即插即用，需要先配置子网前缀；三层设备，效率低）

6.5 链路虚拟化MPLS

路由设备太多，会导致数据在链路中传输时需要检索的路由很多，必然带来延迟，所以在原有的分组前再加上一个特有的标签进行传输，除了最后一个路由是弹出pop标签之外，每一个路由都给到来的分组加上一个新的标签，只是其实路由是在分组前面加标签，中间的路由则是交换标签swap，即用一个新的标签替换此前旧的标签。

随着设备发展的进步，检索路由已经不再是一种困难，所以MPLS在传统链路中用得就比较少了，目前MPLS主要是用在VPN相关技术中。