计算机网络复习（3）

数据链路层

数据链路层的功能

在物理层的基础上向网络层提供服务，对网络层表现为一条无差错的逻辑链路。

提供的服务

数据链路层可能提供以下的服务：

成帧：链路层封装IP数据报，帧的结构由链路层协议规定。
链路接入：媒体访问控制协议（Medium Access Control，MAC）规定了帧在链路上传输的规则.
可靠交付：如果链路层实现可靠交付，通常是通过确认和重传取得的。对于高比特差错的链路来说，链路层通常要实现可靠交付，比如无线传输链路而不是通过运输层或应用层协议迫使进行端到端的数据重传。对于低比特差错的链路来说，可靠交付将是不必要的开销，出于此，许多链路层协议不提供可靠交付服务。数据链路层可能提供无连接无确认的服务，有确认无连接的服务，或者是有连接有确认的服务。
检错和纠错：实际链路传输的时候，需要考虑是由信号衰减和电磁噪声导致的。上层也提供了有限的差错检测，也就是因特网检验和，IP校验了它的首部字段，TCP，UDP校验了全部字段。

数据链路

基本概念：

链路（link）：是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。
数据链路（data link）：除了物理线路外，还必须有通信协议来控制这些数据的传输。把协议加到物理线路上，就形成了数据链路，现在的适配器都实现了物理层和数据链路层的协议。早期的通信协议（protocol）叫通信规程（procedure），因此在数据链路层，这两个概念相同。

三个基本问题

封装成帧

将数据前后分别添加首部和尾部，构成了帧，首部和尾部的作用是用于进行帧界定。比如如果数据限定在 ASCII 字符集，那么我们可以使用非ASCII字符集作为帧的首部和尾部。我们把首部的控制字符称为 SOH（Start Of Header），结束的控制字符称为 EOT（End Of Transmission）。

但是我们如果传输二进制文件的话，我们传输的字节很可能是任意（00-FF）的，这种能传输任意字节数据的行为我们称为透明传输。

透明传输

当数据出现了控制字符代表的字节时，节点很可能认为传输已经结束而丢弃后面正常的数据，比如下面的图中

如果数据出现了 EOT，就会把后面的数据全部丢弃，直到下一个 SOH 被接收为止。

为了解决这个问题，我们可以使用字节填充的方式解决，若在数据中出现特殊控制字符，在前面填充一个 ESC（0x1B）字节，表示这个是一个正常数据不是控制字符，如果我要表示 ESC 这个字符，那么我双写即可。

这样就可以完美解决透明传输的问题

差错控制

在传输过程中可能会产生比特差错：1 可能会变成 0 而 0 也可能变成 1。

在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率 BER (Bit Error Rate)。

误码率与信噪比有很大的关系。

为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施，循环冗余校验就是其中一种。

循环冗余校验

首先确定一个 r+1 的比特位，作为生成多项式G，且要求最高位必为1，然后把 d 位的数据位左移 r 位得到一个值，如下图所示：

然后用这个值去除之前给定的比特模式。

在除法过程中，加法不进位，减法不借位，因此加减都变成异或运算了

最后会得到 r 位的余数，那么这个余数替换掉最后末尾的 r 位 0 就是最后的数据位了，CRC 在检验的时候会计算整个比特位是否可以被 r+1 位的模式除且不留余数，如果可以那就说明数据是正确的，如果不是就说明数据传输发生了偏差。

以下是关于 CRC 的一个计算过程：

帧检验序列

帧检验序列（Frame Check Sequence，FCS）是 CRC 的一种应用场景，两个并不等同。

仅用循环冗余检验 CRC 差错检测技术只能做到无差错接受（accept）。无差错接受是指凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错。也就是说凡是接收端数据链路层接受的帧都没有传输差错（有差错的帧就丢弃而不接受）。

要做到可靠传输（即发送什么就收到什么）就必须再加上确认和重传机制。

汉明码

汉明码的编码需要满足以下的条件：

假设数据位个数为 n，检验位的个数为 k，那么 $n+k=2^k-1$，最常见的就是$n=4,k=3$。

它的编码过程如下：

定义数列 ${P_n}$ 来存放所有的数据，并为其编号：$P_1P_2\cdots P_{2^k-1}$。
每个 2 的整数次幂的位置上放置校验码，其它位置放置数据位。
对于校验位的计算，将由若干个数据位异或得到结果，异或的所有做运算的数据位的下标$(i)$与校验位的下标$(j)$满足 $i&j==j$。举个例子就是，j=1的时候，将所有奇数位置（$x&1==1$即为奇数位置）上的数据位进行异或运算。
最终对每一个校验位重新对它异或的数据再次进行异或，得到的结果如果全 0 则表示没有发生差错。如果发生差错，则得到的结果的二进制的值就是出错的位置。
对于原理可以这么思考：对于一个位置下标的二进制值为 $00101001$ 的数据，如果发生了差错，对于异或运算来说，它会影响所有与它作了异或运算的位，而它会与所有自己二进制值为 1 的位置上的校验位进行异或运算，如果只有这一位发生差错，则它们都会变成 1，也指示出了出错的位置。

为了更好的理解汉明码，这里我也是写了一个测试程序，想要掌握建议自己也写一个玩玩，也挺简单的。

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;

char s[10000];
char ham[20000];
int k[10000];
int menu(){
    int n;
    printf("Hamming Code Test\n");
    printf("1.generate\n");
    printf("2.Test\n");
    printf("3.exit\n");
    printf("Your choice:");
    scanf("%d",&n);
    return n;
}

void gen(){
    int n,k;
    printf("input n for length of data:");
    scanf("%d",&n); 
    printf("input k for length of Test:");
    scanf("%d",&k);
    int N=(1<<k)-1;
    if(n>10000||n+k!=N){
        printf("error value for n k\n");
        return ;
    }
    printf("input your string(only contain 0,1):");
    scanf("%s",s+1);
    int len=strlen(s+1);
    if(len!=n){
        printf("error length\n");
        return ; 
    }
    int i=1,j=0;
    while(i<=n){
        j++;
        if((j&(~j+1))==j){
            ham[j]=0;
            continue;
        }
        ham[j]=s[i]-'0';
        i++;
    }
    for(i=0;i<k;i++){
        int pos=1<<i;
        for(int l=1;l<=j;l++){
            if(l!=pos&&(l&pos)==pos){
                ham[pos]^=ham[l];
            }
        }
    }
    for(int i=1;i<=j;i++){
        putchar('0'+ham[i]);
    }putchar(10);
    printf("done\n");
}

void Test(){
    printf("input the hamming code data(only contain 0,1):");
    scanf("%s",ham+1);
    int len=strlen(ham+1);
    int x=len+1;
    if((x&(~x+1))!=x){
        printf("error length for hamming code\n");
        return ;
    }
    int res=0;
    for(int i=1;i<=len;i<<=1){
        int k=ham[i]-'0';
        for(int l=1;l<=len;l++){
            if(l!=i&&(l&i)==i){
                k^=ham[l]-'0';
            }
        }
        res+=i*k;
    }
    if(res){
        printf("error bit in %d\n",res);
    }
    else{
        printf("correct\n");
    }
}

signed main(){
    int k=1;
    while(k){
        
        switch(menu()){
            case 1:
                gen();
                break;
            case 2:
                Test();
                break;
            case 3:
                exit(0);
                break;
            default:
                printf("Unknown Choice!\n");
                break;
        }
    }        
    return 0;
}

流量控制与可靠传输协议

基本上有三种可靠传输协议：停等协议，后退N帧（Go Back N，GBN）协议，选择重传（SR），后两种是通过滑动窗口实现的。

停等协议

实现非常简单，但是信道利用率非常低。发送方一次只发送一个帧，等到接收方确认之后，再发送下一个帧。

后退N帧协议

允许发送方一次发送多个帧，并且采用累积确认的方法，累计确认就是说，我如果发送了 ACK 为 5 的确认帧，说明 5 号之前的帧都被完整无误地接收到。只能按序接收，一旦出现了不属于当前期望的帧的序号，会立刻丢弃。

如果发送的某个帧出现了丢失，那么会等到这个帧的计时器超时之后，才才再次从出错的帧开始重传，而此时发送端可能已经发送了很多个帧，并且准确到达了目标节点，但是因为后退 N 帧协议只能按序接受的缘故，在信道质量差的时候，后退N帧协议效率也会比停等协议差。

选择重传

选择重传（SR）协议通过让发送方仅重传那些它怀疑在接收方出错（即丢失或受损）的分组而避免了不必要的重传。它会缓存失序的分组，等到能排成有序时候交付上层，移动窗口，同时发送确认报文，使得接收方同步移动。此时不采用累积确认，而是逐个确认，只有超时（丢失）和否定帧（受损）会引发重传，其它情况一律不会发生重传，接收方对于收到的冗余分组，需要再次发送ACK确认，因为冗余分组可能是发生了 ACK 丢失或者是高延迟引发的重传，对于后者的情况，我们不必重新发送 ACK，但是前者的情况我们必须重新确认，否则会导致发送方一直处于超时而无限重传这个分组。

（以下摘抄自我对自顶向下第三章的解读）

这里探讨一下接收窗口大小的问题，如果窗口大小和序号大小一致，很容易出现接收方不知道这个序号是一个新分组还是重传，因为都有可能。

这里其实只要窗口大小<=序号大小的一半即可。因为考虑最极端情况，滑动窗口一次滑动最多不超过自身的长度，因此我接收的分组一定是最新分组。这里举一个极端的例子：

1	0 1 2 3 4 5 6 7 8 0 1 2 3 4

假设窗口大小为 5，那么此时 0 1 2 3 4 是待发送的。我假设 1 2 3 4 都已经被确认完毕，此时 0 到达，但是在 ACK 抵达发送端之前产生了超时，而接收端因为接受了 0 1 2 3 4 滑动窗口已经移动到 5 6 7 8 0，那么此时我再接收到一个 0 我就不知道是重传还是新分组了。

所以我需要保证我一次滑动的距离不能有和我之前在窗口中相同序号的分组。

证明一下：假设序号大小为 n，窗口大小为 p。

假设当前所在分组为 i，此时的最后一个分组是 i+p-1，那么我一次最多滑动 p 的距离，此时第一个分组是 i+p，最后一个分组是 i+2p-1。那么观察上面的序列号，如果两个序号逻辑位置相差为 n+1，那么这两个序号是相同的。

不难发现，我需要让我的最右端点，落不到这个 n+1 那个点的距离。

也就是 i+n+1>i+2p-1 稍微移一下得到了 $p<\frac{n+2}{2}$，等价于 $p\le\frac{n}{2}$，也就是 p 要小于等于 n 的一半。

证毕！

总结就是，发送窗口和接收窗口不能超过序号大小的一半。

介质访问控制

这个存在的意义就是使得通信的多节点避免发生碰撞，使用合理的手段控制达到通信互不干扰的目的。

常见的介质访问控制方法有：信道划分（静态），随机访问介质控制，轮询访问介质访问控制。

信道划分介质访问控制

有这几种方式（考纲内）：

频分复用（Frequency division multiplexing，FDM）：将多路的基带信号调制到不同频率的载波上，叠加形成符合信号的多路复用技术，每条子信道的带宽可以不相同但是不能超出信道总带宽，为了防止码间串扰，相邻信道需要添加保护频带。
时分复用（Time division multiplexing，TDM）：将物理信道按时间划分为时间片，在某一个时间片内，仅允许特定的信号发送。但是当只有一个信号活跃的时候，它的信道利用率仅有 $\frac{1}{n}$，因此出现统计时分复用（Statistical Time Division Multiplexing，STDM），它可以根据信号活跃度，按需分配时隙。
波分复用（Wavelength Division Multiplexing，WDM）：特指光信号的频分复用，在光纤中，传输多种不同波长（频率）的光信号可以使得信号互不干扰，最后用波长分解器分解出来，光处于高频段，具有很高的带宽。
码分复用（Code Division Multiplexing，CDM）：又叫码分多址（Code Division Multiple Access，CDMA）。给定一个码片向量 $(a_1,a_2,_\cdots a_n),a_i\in {-1,1}$，这代表这个信号的 1 的码片，全部取负得到 0 的码片。同时会有不同的另一组向量表示其它信号的 1 的码片，这些码片会两两正交，也就是内积为 0，或者直白点说就是点积为0。当接收方接收到信号的时候，会对所有码片进行内积运算，之后会除向量维度数目，如果得到的结果为 1，说明这个码片所属的发送方发送了 1，如果为 -1 说明它发送了 0，如果为 0，说明它什么也没发送。
- 1.共有 4 个站进行码分多址CDMA通信。4 个站的码片序列为：A.（-1,-1,-1,+1,+1,-1,+1,+1）B.（-1,-1,+1,-1,+1,+1,+1,-1）C.（-1,+1,-1,+1,+1,+1,-1,-1）D.（-1,+1,-1,-1,-1,-1,+1,-1）。现收到这样的码片序列：（-1,+1,-3,+1,-1,-3,+1,+1）。问哪个站发送数据了？发送数据的站发送的 1 还是 0？
- 解析：S·A=（+1-1+3+1-1+3+1+1）/8=1，A 发送 1，S·B=（+1-1-3-1-1-3+1-1）/8=-1，B发送0，S·C=（+1+1+3+1-1-3-1-1）/8=0，C无发送，S·D=（+1+1+3-1+1+3+1-1）/8=1，D 发送 1。

随机访问介质控制

第二大类多访问协议是随机接入协议。一个传输节点总是以信道的全部速率（即 R bps）进行发送。当遇到碰撞的时候，涉及碰撞的每个节点反复地重发它的分组，到该帧无碰撞地通过为止，它又叫争用型协议。

它肯定不会立刻发送，因为如果双方都立刻发送肯定又会发生碰撞，它在重发该帧之前等待一个随机时延，这个时延会独立地随机选择。因为如果双方延迟一样的时间，那么再次发送一样也会发生碰撞。于是让它们分别随机等待就会有这样的结果出现：这些节点之一所选择的时延充分小于其他碰撞节点的时延，并因此能够无碰撞地将它的帧在信道中发出。

随机接入协议最常用的有两种：ALOHA协议和载波监听多路访问（CSMA）协议，以太网就是一种流行并广泛部署的 CSMA 协议。

时隙ALOHA

这是比较简单的随机接入协议，做如下假设：

所有帧由L比特组成。
时间上被划分为 L/R 秒的时隙，也就是刚好传输一帧的时间。
节点只会在时隙起点开始传播。
节点之间是同步的，它们都清楚的知道当前是否是时隙起点。（这个同步往往是比较难的）
如果发生碰撞，那么发生碰撞的这个时隙的结束所有节点都知道发生了碰撞。
对于发送的事件，只需要考虑三点：
- 当有个帧要发送时，等待下一次最近的时隙发送。
- 如果没有碰撞，则该时隙发送成功。
- 如果有碰撞，那么该节点以 p 的概率在后续的时隙重传该帧（1-p的概率在此时隙不重传，而在下个时隙继续以p的概率重传）。

时隙ALOHA有以下优点：

唯一活跃的节点能占用整个信道的带宽，以全速率发送。
时隙ALOHA也是高度分散的，因为每个节点检测碰撞并独立地决定什么时候重传。
时隙ALOHA也是一个极为简单的协议。

这里进行了多个活跃节点效率的计算，具体计算过程不需要掌握，需要记住它最后的效率是 1/e≈0.37。

ALOHA

它不需要同步时隙，但是效率相比时隙ALOHA下降了一半。

载波侦听多路访问（CSMA）

对于人类来说，为了获得更多的数据量，有礼貌的人类交谈有两个重要的规则：

说话之前先听。在网络领域中，这叫载波侦听（carrier sensing）
如果与他人同时开始说话，停止说话。在网络领域中，这叫碰撞检测（collision detection）

这两个规则包含在载波侦听多路访问（Carrier Sense Multiple Access，CSMA）和具有碰撞检测的 CSMA（CSMA with Collision Detection）。

来看下面这张图：

在途中的时刻，B在t0的时候开始传输，而 D 在t1的时候并没有听到 B 正在传输，因此它也开始发，于是产生了碰撞。

显然广播信道的端到端信道传播时延（channel propagation delay）越长，载波侦听节点不能侦听到网络中另一个节点已经开始传输的机会就越大，效率就会变低。

对于碰撞的处理方式，CSMA 协议分为三种：

1-坚持：发生冲突后马上监听信道，如果空闲立刻重传，如果忙则持续监听。
非坚持：发生冲突后如果空闲，立刻重传，如果忙则随机等待一个时间后再次监听。
p-坚持：发生冲突后，如果信道空闲，那么以 p 的概率发送数据，1-p 的概率推迟到下一个时隙，如果忙则持续监听。

具有碰撞检测的载波侦听多路访问（CSMA/CD）

从网络适配器的视角来讲解 CSMA/CD：

适配器从网络层一条获得数据报，准备链路层帧，并将其放入帧适配器缓存中。
如果适配器侦听到信道空闲，它开始传输帧。如果正在忙，那么重复步骤2。
在传输过程中，适配器监视来自其他使用该广播信道的适配器的信号能量的存在。（边发送边检测）
如果适配器传输整个帧而未检测到来自其他适配器的信号能量，该适配器就完成了该帧。在另一方面，如果适配器在传输时检测到来自其他适配器的信号能量，它中止传输。
中止传输后，适配器等待一个随机时间量，然后返回步骤2。

用于以太网以及 DOCSIS 电缆网络多路访问协议中的二进制指数后退（binary exponential backoff）算法，简练地解决了这个问题。在连续经历过 n 次碰撞后，节点随机地从 ${0,1,2,…,2^n-1}$ 中选择一个 K 值作为等待的时间。因此，一个帧经历的碰撞越多，K选择的间隔越大。对于以太网，一个节点等待的实际时间量是 Kx512比特时间（即发送512比特进入以太网所需时间量的K倍），n 能够取的最大值在10以内。

因为每次碰撞，选择等待的集合呈指数增长，因此该算法被叫做二进制指数后退。

CSMA/CD 效率

显然，当只有一个节点有一个帧发送时，该节点能够以信道全速率进行传输。然而，如果很多节点都有帧要发送，信道的有效传输速率可能会小得多。令 $d_{prop}$ 表示信号能量在任意两个适配器之间传播所需的最大时间。令 $d_{trans}$ 表示传输一个最大长度的以太网帧的时间。

最后我们得到效率为 $\frac{1}{1+5\times\frac{d_{prop}}{d_{trans}}}$。当 $d_{prop}$ 趋于0的时候，效率趋于 1，因为如果没有传播时延，则根本不会发生碰撞，因为监听总能实时判断出当前信道是否空闲。当 $d_{trans}$ 趋于无穷的时候，传输效率也趋于 1，因为一个帧取得信道之后，它将占用很长的时间，因此大的部分时间都在有效工作。

CSMA/CA

CA 的意思是碰撞避免。这个协议在无线局域网中应用广泛，因为无线信道的质量比较低，因此链路层采用确认重传的方案，可以理解为停等协议。

802.11协议规定，所有站发送完帧之后需要等待一段事件才能发送下一帧，这个等待的时间称为帧间间隔（InterFrame Space，IFS）。802.11 是用了三种 IFS：

SIFS（短IFS）：分隔一次对话的帧，常见的帧类型有 ACK帧，CTS（Clear To Send，允许发送）帧，分片后的数据帧，回答AP探寻的帧。
PIFS（点协调IFS）：PCF操作中使用。
DIFS（分布式协调IFS）：用于异步帧竞争访问的时延。

上面的帧长度，依次下来变长。

CSMA/CA 的算法大致如下：

站点有数据发送，检测到信道空闲（不空闲则跳下一步），等待 DIFS 的时间后，发送整个数据帧，到第四步。
站点执行 CSMA/CA 算法，选取一个随机值回退，信道忙时计数器保持不变，空闲时进行倒计时。
计时器到0，发送整个数据帧等待确认。
发送站收到确认，如果要发送第二帧，需要从步骤2开始。

如果重传计时器控制的时间内没有收到确认帧，需要重传，则继续2的算法发送帧。

处理隐蔽站

通过使用 RTS（requests to send）控制帧和 CTS（clear to send）控制帧。

考虑一种情况，有三个站点，A和B可以通信，B和C可以通信，但是A和C不能感知对方的存在，于是它们可能同时向B发送数据，此时必然导致碰撞的发生，这就是隐蔽站的问题。

为了解决这个问题，我们允许发送站预约信道，发送站会发送 RTS 帧请求预约信道，接收方收到之后，会广播一个 CTS 帧，包括这次通信所需要的时间，这样的话，A发送请求给B，B就能广播给其它人，这样其他人就会被抑制发送，而发送方也可以根据这个广播帧作为对我 RTS 的一个回应，A就知道B已经给它预约好信道了。

广播 CTS 的目的有两个：

让源站知道我已经接受了你的许可。
让其它站不要在指定时间内发送数据。

轮询访问

最典型的是令牌传递协议，节点在逻辑上形成一个环，拥有令牌的节点具有发送数据帧的权限。因此不会发生冲突，因为同一时间只能有一个节点具有令牌。当所有节点都不发送数据帧的时候，只有令牌在网络中传输。

最小帧长度

这是一个比较重要的概念。一般来说，链路层采用 CSMA/CD 算法来避免和检测冲突，我们考虑这个图：

假设t0时刻，B 发送数据，到了 D，在一个恰好的时间节点，D想发送数据，而此时恰好D监听是空闲的，但是它只要发数据马上就会产生碰撞，此时D马上停止，但是远在 B 的节点确不知道发生了碰撞，依然还在不停地发。此时发生了碰撞之后链路上的数据应该都是不正确了，都不能用了，但是B需要在它知道发生了碰撞的时候才会停止。最坏应当是一倍的最长端到端延时。

但是仅仅是冲突发生到 B 节点知道最长花一段的端到端延时，可是发生碰撞的时候，B已经发送了若干数据，第一个比特发生的碰撞，此时应当已经发了相当于一倍最长端到端延时的数据。最坏的打算，B会发送两倍端到端时延的数据。我们认为这种数据是十分难以处理的（无法判断是正常帧还是错误帧），因此规定一个最小帧长，使得小于多少字节的帧无效。这个长度一般是两倍端到端延时（传播延时）与带宽乘积。

错题

同轴电缆在没有中继的情况下传输距离不超过500m。
同一局域网中，MAC地址的冲突会导致两个设备都不能正确通信。
链路聚合不是VLAN的优点。
快速以太网采用保持最短帧长不变，减小最大传输距离来提高传输速率。

点对点协议

目前使用得最广泛的数据链路层协议是点对点协议 PPP (Point-to-Point Protocol)。

用户使用拨号电话线接入互联网时，用户计算机和 ISP 进行通信时所使用的数据链路层协议就是 PPP 协议。

协议组成

一个将 IP 数据报封装到串行链路的方法。
链路控制协议 LCP (Link Control Protocol)。
网络控制协议 NCP (Network Control Protocol)。

帧格式

透明传输问题

在同步传输的时候，PPP采用比特填充方式。

在异步传输的时候，PPP采用字符填充法。

链路层设备

网桥

它可以连接两个局域网，形成更大的局域网，它的工作原理仅仅是，连接两个网络中，如果收到的帧的目的地址是发送方的目的网络，直接丢弃，否则转发给另一个网络。

理解起来很简单：就是这个帧不需要经过网桥那就丢弃，否则转发。

交换机

本质是一个多端口网桥。

可以隔离冲突域，VLAN功能还可以隔离广播域。

使用交换机能提升用户的使用带宽，拥有自学习的功能，根据源MAC地址学习，根据目的MAC地址转发。