精华内容
下载资源
问答
  • 流量控制(基于速率/基于反馈)-在数据链路通常采取基于反馈的模式,即由接收方向发送方提供处理能力大小,发送方根据处理能力提供对应流量 帧 (数据链路处理的协议数据单元PDU) 帧的组成:帧头+载荷+帧尾 ...

    原文链接

    数据链路层概述

    保证数据传输的有效,可靠性

    • 差错的检测和控制
    • 流量控制(基于速率/基于反馈)-在数据链路层通常采取基于反馈的模式,即由接收方向发送方提供处理能力大小,发送方根据处理能力提供对应流量

    (数据链路层处理的协议数据单元PDU)

    帧的组成:帧头+载荷+帧尾

    • 帧头:包含定位所需要的地址,物理地址信息
    • 载荷:上层网络层传递下来的包
    • 帧尾:校验和,做帧的校验

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-r640jeyc-1586083911078)(http://47.97.124.78:8000/wp-content/uploads/2020/03/帧的组成.png)]

    数据链路层使用物理层提供的服务,所以要将物理层处理的位流(bits)转换成数据链路层能够处理的帧,这个过程就叫做“成帧”。

    成帧

    将原始的位流分散到离散的帧中

    常见的四种成帧方法

    1. 字符计数法
    2. 字节填充的标志字节法
    3. 比特填充的比特标记法
    4. 物理层编码违例法

    字符计数法

    发送方:

    在每个帧头部中的第一个字段,标识该帧的长度共有多少字符

    接收方:

    通过第一个字段,就知道这个帧有几个字符,在哪里结束该帧

    优点: 实现简单

    缺点: 没有考虑重新同步问题,一旦出错,无法恢复,工程中极少使用

    字节填充的标志字节法

    考虑了重新同步问题,每一帧采用一个特殊字节做帧界,即当前帧的开始与上一个帧的结束

    标记数据标记数据

    将这个特殊字节称为标志字节(flag byte)

    存在问题:当传输数据中也存在标志字节时,会和真正的帧界混淆

    解决方案:当数据中存在标记字节时,在标记前添加转义字符(这种方式解决了一部分问题,但同时也带来了一些特殊情况,当数据中包含转义字符时,又必须在转义字符前添加转义字符避免混淆)

    特殊情况下传输数据内容:

    ESCFLAGESCFLAGESCFLAG

    在成帧过程中就变成了

    ESCESCESCFLAGESCESCESCFLAGESCESCESCFLAG

    缺点: 1.数据中存在帧界或转义符时容易混淆,大量的标志字节或转义字符会造成低效率的成帧(最坏情况50%)。2. 不适用于任意比特数的帧,必须是8位整数倍

    比特填充的比特标记法

    这是一种面向二进制位的帧格式,把所有需传输的数据以比
    特位一字排开,并以特殊的位模式01111110作为帧标志,即
    一个帧的开始(同时标志前一个帧的结束)

    当帧内容出现与帧标志相同位串01111110时:

    在5个1后插入一个0,即变成01111101,接收方将自动删除第5 个1后的0。这称为位填充法(零比特填充法),也称为透明传输。

    当扫描过程中出现错误导致部分帧没有被正确接收:

    接收方会继续扫描直到读取到下一个帧标志,开始重写转换同步数据

    优点: 可以传输任意比特数的帧,同时传输效率更高

    物理层编码违例法

    将冗余信号用作帧界

    例如:在4B/5B编码模式中,将4比特映射到5比特上,能够承载32位却只利用了16位,剩下的位就可以用作帧界

    例如:在曼彻斯特编码中,只利用了高到低表示1,低到高表示0,却没有利用高到高,低到低两种情况

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Ya43z6Cd-1586083911080)(http://47.97.124.78:8000/wp-content/uploads/2020/03/曼彻斯特编码.png)]

    优点: 由于利用的是冗余信号,不会混淆,传输效率较高


    差错处理的概述

    处理错误的常见手段

    1. 纠错:恢复出正确的数据
    2. 检错:仅仅检出错误,不恢复,通常伴随重传

    常见错误类型

    1. 单个错误:分散在各个数据块中
    2. 突发错误:集中于一个数据块,整个数据块都是错误

    纠错码(前向纠错技术)

    发现错误,从错误中恢复出正确的来。

    由于纠错码需要纠错,这个过程中需要太多的冗余位,所以开销较大。在有线网络中极少使用,主要应用于无线网络中

    检错码

    只能发现错误,不能从错误中恢复,但可采用重传恢复

    主要应用于局域网


    码字:包含数据位和校验位的n位单元(模式)

    海明距离:两个码字的海明距离指,两个码字间不同位的数目

    例如:“11010101”与“10000101”的海明距离就是2

    海明距离可以利用异或运算,其中1的个数表示海明距离

    全部码字的海明距离:

    指在全部码字中任意两个码字间海明距离的最小值

    海明距离的意义:

    如果海明距离为d,则一个码字要变成另一个码字,需要跳变d位(发生d个一位错误)才能实现。

    海明距离与“检错”的关系:

    海明距离为d+1的编码能检测出d位的差错

    奇偶校验码:

    海明距离为2,能检验出1位错误

    奇偶校验码就是将一个校验位追加到传输数据中,分为奇校验和偶校验,校验位的值是“0”还是“1”取决于数据中“1”的个数。

    例如:

    DATA:100011

    偶校验:100011 1

    奇校验:100011 0

    因为Data中含义3个1,偶校验就是加入校验码后1为偶数个,所以添加1。对应的奇校验则加入0

    奇偶校验检错举例:

    有一组传输数据只有四种格式“00”,“11”,“01”,“10” 。
    经过偶校验,编码后变为“000”,“110”,“011”,“101”

    此时发送方向接收方传输数据“101”.产生一个跳变成为“111”.

    显而易见“111”这个数据不在四种基本数据内,所以接收方可以成功检错

    如果这个过程中发生两次跳变,可能变为“011”.

    这个数据虽然变化了,但也出现在基本数据内,所以接收方无法成功检错,说明接收方无法通过奇偶校验处理两次及以上跳变

    海明距离与“纠错”关系

    海明距离为2d+1的编码,能够纠正d位及以内的差错

    纠错的原理在于,此时即使码字发生d次跳变,这个错误码字与原码字之间的距离仍然是最近的。所以接收方只需要找到与这个错误码字海明距离最接近的码字就能将错误纠正

    例如:一个系统有4个合法码字(0000000000, 0000011111, 1111100000 , 1111111111)

    海明距离是 5=2*2+1,所以可纠正2位错误.

    发送方:0000011111

    发生两次跳变后:0000000111

    接收方发现差错并且找到海明距离最近的码字进行替换。

    收方纠正后: 0000011111

    假如发生3次跳变(超出纠错范围):0000000011

    收方找到的海明距离最近码字是:0000000000

    可以看到无法再进行纠错

    显而易见,随着海明距离增大,纠错能力就不断增强

    但是,海明距离越大意味着合法码字越少,传输效率也就越低

    二者只能找到一种平衡,而不能同时保持高纠察率以及高传输效率吧


    纠1位错的海明码

    假设一个系统,经过编码后的码字位数是n位,则n位的组成应该为n=m+r 。其中m表示传输的数据位,r表示冗余位。

    在海明码中,将这些冗余位用作纠错位

    如何确定冗余位个数r:

    在数据传输过程中有m位数据位,所以合法码字有2^m个,而总位数为n,所以一共 有2^n个码字。任取一个合法码字,要保证其跳变一位后能够被纠错,或者说其跳变一位就变成错误码字,就需要至少n+1个码字来表示它。

    例如:总位数为5的 “10010” 是一个合法码字,为了保证其跳变一位后会变成错误码字,就要求 “10011”,“10000”,“10110”,“11010”,“00010”这五个与其海明距离为1的码字全部为错,也就是“10010”需要5+1个码字来表示。

    综上,则有以下条件成立:

    ( n + 1 ) 2 m < = 2 n (n+1)2^m <= 2^n (n+1)2m<=2n

    n = m + r n=m+r n=m+r

    推导出:

    ( m + r + 1 ) < = 2 r (m+r+1)<=2^r (m+r+1)<=2r

    利用上式容易得出,纠正单个错误需要的校验位的下界满足:

    mrn
    123
    2~435~7
    5~1149~15
    12~26517~31
    27~57633~63

    海明纠错码

    1. 将每一个码字从左到右编号,最左边为第一位
    2. 规定凡编号为2的次幂的位是校验位,如1位,2位,4位,8位,16位…
    3. 其余各位均是数据位,如3,5,6,7,9…
    4. 每一个校验位的设置规则:包括自己在内的一些位的集合的奇偶值(奇偶校验)

    如何决定每个数据位的校验位:

    将某一位数据位的编号展开成2的次幂的和(例如11可以写作:1+2+8),那么每一项所对应的位即为该数据位的校验位(供接收方使用)

    如:一个系统中,码字的数据位是7位,根据上文公式求得冗余位是4位,所以码字位数一共11位,其中1,2,4,8位属于校验位(下图P表示校验位,D表示数据位)

    1234567891011
    P1P2D1P3D2D3D4P4D5D6D7
    1=2^0YYYYYY
    2=2^1YYYYYY
    4=2^2YYYY
    8=2^3YYYY

    上述图表中描述了我们在第四条中所说的每一个校验位所在的集合,例如第三行表示了1这个校验位的值由1,3,5,7,9,11这些位的值结合奇偶校验决定

    1234567891011
    P1P2D1P3D2D3D4P4D5D6D7
    信息码--1-001-000
    检验位00-1---0---
    海明码00110010000

    (上图采用了偶校验)


    海明码纠错过程

    1. 首先将差错计数器置0
    2. 当海明码数据到达接收端后,接收端逐个检查各个校验位的奇偶性。
    3. 如发现某一校验位和它所检测的集合的奇偶性不正确,就将该检验位的编号加到差错计数器中。
    4. Counter=0,无差错。Counter ≠0,出错,该值指明出错的位

    比如:

    接收到码字为00111000100,校验各校验位:(采用偶校验)

    第一位:00111000100,校验集合有3个1,错。counter+1

    第二位:00111000100,校验集合有1个1,错。counter+2

    第四位:00111000100,校验集合有2个1,对

    第八位:00111000100,校验集合有1个1,错。counter+8

    累加出错位编号:1+2+8=11

    可计算得其第11位出错,将该位由0改为1,即纠正得到正确结果: 00111000101


    利用海明码纠正突发错误

    突发错误虽然是整个数据块的错误,但可以利用海明码巧妙的逐个纠正

    1. 将连续的k个码字按行排列成矩阵
    2. 发送数据时,按列发送,每列k位
    3. 如果一个突发性错误长度是k位,则在k个码字中,至多只有一位受到影响,正好可用海明码纠错改位后恢复

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-n800U5UW-1586083911081)(http://47.97.124.78:8000/wp-content/uploads/2020/03/海明码纠错.jpg)]


    检错码

    采用检错码的原因:

    纠错码占用太多冗余位,信道利用率不高

    在局域网中,主要使用的是检错码

    常见的检错码:

    • 奇偶校验码(海明距离为2,检一位错)
    • 互联网校验和
    • 循环冗余校验码

    奇偶校验码:

    奇偶位取值等同于对数据位进行模2和运算

    例如,采用偶校验: 1110000 -> 11100001

    接收方能够检查出是否存在单个比特的错误(或者奇数个)

    出错误的概率在50%(奇数跳变成功检验,偶数则不能)

    校验和

    校验和通常是按照N位码字来进行模2加/和运算,发送方将运算结果附加在数据报文尾部 ,作为校验位。

    例如:16位的互联网补码校验和

    特点:

    • 比奇偶检验更好的检错性能
    • 能检出高至N位的突发错误
    • 检错随机错误率1-2^N
    • 易受系统错误干扰,比如,增加的“0”

    互联网校验和计算文档:RFC1071(computing the internet checksum)

    (1)待校验的相邻字节成对组成16比特的整数一行,按列
    从低位开始计算其模2和;并将结果按位取反码,作为校验
    和取值。

    (2)检查校验和时,将所有字节,包括校验和,进行相加
    并求二进制反码。接收方:如果结果为全1 ,无错误

    注意:如果某列的模2和有溢出,向高位进位,如果高位产
    生进位,循环向低位进位。

    循环冗余检错码CRC

    任何一个k位的帧都可以看成一个k-1次的多项式

    例如:1011001 可以看成-> x 6 + x 4 + x 3 + x 0 x^6+x^4+x^3+x^0 x6+x4+x3+x0(k项k-1阶多项式)

    CRC系统里一定具有生成多项式:G(x),G(x)为r(冗余码个数)阶

    还具有m位帧的多项式:M(x),且一般 m>r , M(x)>G(x)

    接下来:

    x r M ( x ) G ( x ) = Q ( x ) + R ( x ) \frac{x^rM(x)}{G(x)}=Q(x)+R(x) G(x)xrM(x)=Q(x)+R(x)

    Q(x)表示商,R(x)表示余数

    易知:

    x r M ( x ) − R ( x ) G ( x ) = Q ( x ) \frac{x^rM(x)-R(x)}{G(x)}=Q(x) G(x)xrM(x)R(x)=Q(x)

    说明 x r M ( x ) − R ( x ) x^rM(x)-R(x) xrM(x)R(x)一定能被G(x)整除,所以将它作为转码后的数据传送给接收方

    接收方在收到后,将其与约定好的生成多项式G(x)相除:

    • 若为0,说明传输过程中没有发生错误
    • 若不为0,说明传输过程发生错误

    在二进制运算中,减法和加法都做异或运算,即相同得0,相异得1

    例如:11010+10100=01110,11001-10010=01011

    模2运算:模2加以及模2减等同于异或运算,即相同得0,相异得1

    0⊕0=0; 0⊕1=1;
    1⊕0=1; 1⊕1=0.


    CRC码计算:

    发送方

    传输的一帧:1101011011(m=10)

    易知: M ( x ) = x 9 + x 8 + x 6 + x 4 + z 3 + x + 1 M(x)=x^9+x^8+x^6+x^4+z^3+x+1 M(x)=x9+x8+x6+x4+z3+x+1

    规定:收发双方采用统一的 G ( x ) = x 4 + x + 1 G(x)=x^4+x+1 G(x)=x4+x+1

    计算得: T ( x ) = x 4 M ( x ) = x 4 ( x 9 + x 8 + x 6 + x 4 + z 3 + x + 1 ) = x 13 + x 12 + x 10 + x 8 + z 7 + x 5 + x 4 T(x)=x^4M(x)=x^4(x^9+x^8+x^6+x^4+z^3+x+1)=x^{13}+x^{12}+x^{10}+x^8+z^7+x^5+x^4 T(x)=x4M(x)=x4(x9+x8+x6+x4+z3+x+1)=x13+x12+x10+x8+z7+x5+x4 。(相当于在原码字后边加r个0)

    开始计算:(采用模2除法,用G(x)去除 X r M ( x ) X^rM(x) XrM(x),得余数)

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pebCa1Qt-1586083911081)(http://47.97.124.78:8000/wp-content/uploads/2020/03/运算.png)]

    计算11010110110000/10011 得余数1110 ,采用模2减法,用XrM(x)减去余数,得到带CRC校验和的帧,11010110110000-1110=11010110111110,所以:

    最终得到发送给接收方的数据= 1101011011(帧数据)1110(余数)

    接收方

    接收方在得到传输过来的码字后,会利用规定的G(x)与之相除,能够整除则认为传输正确

    如果不能被整除,则检测为传输出错


    生成多项式国际标准

    CRC-12 :$x^{12} +x^{11} + x^3 + x^2 + x^1 + 1 $。用于字符长度为6位

    CRC-16 :$x^{16} + x^{15}+ x^2+ 1 $用于字符长度为8位

    CRC-CCITT : x 16 + x 12 + x 5 + 1 x^{16} + x^{12}+ x^5+ 1 x16+x12+x5+1。 用于字符长度为8

    CRC32 : G ( x ) = x 32 + x 26 + x 23 + x 22 + x 16 + x 12 + x 11 + x 10 + x 8 + x 7 + x 5 + x 4 + x 3 + x + 1 G(x)=x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^3+x+1 G(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x3+x+1

    CRC32广泛应用于以太网计算循环冗余校验时用

    例题:如果生成多项式是 G(x)= x^3 + x^2 + 1,待传送的原始码字分别是1111 和 1100,请计算采用CRC编码后的码字分别是多少?

    解题:生成多项式是3阶的,所以r=3,生成多项式对应的位(除数)是:1101

    待传输的1111,移位后变为:1111000(被除数),得到余数111

    用1111000-111,得到编码后的码字为:1111111


    三个单工协议-基本数据链路层协议

    单工:数据的传输在某时是单向的

    • 无限制的单工协议
    • 单工停-等协议
    • 有噪声信道的弹弓协议

    理想条件下假设:

    • 物理层,数据链路层和网络层是各自独立运行的进程(在工程中可能有各自不同的存在形式)
    • 机器A希望向B发送的是一个可靠的面向连接的长数据流
    • 假设机器不会崩溃,即使崩溃,我们不会处理因崩溃产生的错误
    • 从网络层拿到的数据是纯数据

    几个协议共用的数据类型,调用函数

    protocol.h文件

    #define MAX_PKT 1024                    /* packet size in bytes */
    
    typedef enum { false, true } boolean;   /* boolean type */
    typedef unsigned int seq_nr;            /* sequence or ACK numbers  序列号或确认号*/
    
    typedef struct {
        unsigned char data[MAX_PKT];
    } packet;                               /* 从网络层传输来的包/分组 */
    typedef enum { data, ack, nak } frame_kind; /* frame kind definition ack表示确认字符,nak表示否定应答或者非应答 */
    
    
    typedef struct {
        frame_kind kind;                    /* what kind of frame? 帧的类型 */
        seq_nr seq;                         /* sequence number 序列号*/
        seq_nr ack;                         /* ACK number 确认号/确认字符*/
        packet info;                        /* the Network layer packet 包/分组(来自网络层)直接作为帧的载荷定义在帧的结构中*/
    } frame;   //定义帧结构
    
    typedef enum {
    	frame_arrival,  //帧到达
    	cksum_err,   //检错码错误
    	timeout,   //时间超出
    	network_layer_ready,   //网络层完成准备(可以发送下一条数据)
    	ack_timeout  //延时确认计时器时间超出
    } event_type;  //定义事件类型
    
    
    /* wait for an event to happen; return its type of event */
    /*等待事件发生,并返回事件类型:即上文事件类型类中的内容*/
    void wait_for_event(event_type* event);
    
    /* fetch a packet from the network layer for transmission 从网络层获取数据*/
    void from_network_layer(packet* p);
    
    /* deliver information from an inbound frame to the network layer 向网络层发送数据*/
    void to_network_layer(packet* p);
    
    /* get an inbound frame from the physical layer 从物理层获取数据*/
    void from_physical_layer(frame* r);
    
    /* pass the frame to the physical layer 向物理层发送数据*/
    void to_physical_layer(frame* s);
    
    /* start the clock and enable the timeout event 重传定时器启动*/
    void start_timer(seq_nr k);
    
    /* stop the clock and disable the timeout event 重传定时器关闭*/
    void stop_timer(seq_nr k);
    
    /* start an auxiliary timer and enable the ack_timeout event 捎带确认定时器启动*/
    void start_ack_timer(seq_nr k);
    
    /* stop an auxiliary timer and disable the ack_timeout event 稍待确认定时器关闭*/
    void stop_ack_timer(seq_nr k);
    
    /* allow the network to cause a network_layer_ready event */
    void enable_network_layer(void);
    
    /* forbid the network to cause a network_layer_ready event */
    void disable_network_layer(void);
    
    /* macro inc */
    #define inc(k) if (k < MAX_SEQ) k = k + 1; else k = 0
    

    其中定义了很重要的帧结构,以及事件类型,基本操作等等…


    无限制的单工协议-协议1

    这种协议设定了很多理想条件,在现实中很难满足,所以被称为“乌托邦协议”

    理想条件:

    • 收发双方的网络层都处于就绪状态(随时待命)
    • 处理时间忽略不计(瞬间完成)
    • 可用的缓存空间无穷大(无限空间)
    • 假设DLL之间的信道永远不会损坏或者丢失帧(完美通道)

    代码实现:

    typedef enum { frame_arrival } event_type;
    #include "protocol.h"
    
    //封装发送过程
    void sender1(void)
    {
    	frame s; /*buffer for an outbound frame 为帧准备内存空间*/
    	packet buffer; /*buffer for an outbound packet*/
    	while (true) {
    		from_network_layer(&buffer); /*go get something to send 从网络层获取数据存入缓存 */
    		s.info = buffer; /*copy it into s for transmission 将数据写入帧的载荷*/
    		to_physical_layer(&s); /*send it on its way 将帧传递给物理层处理*/
    	}
    }
    
    //解封装发送过程
    void receiver1(void)
    {
    	frame r;
    	event_type event; /*filled in by wait, but not used here*/
    	while (true) {
    		wait_for_event(&event); /*only possibility is frame arrival 等待数据到达事件*/
    		from_physical_layer(&r); /*go get the inbound frame 接收来自物理层的数据并进行成帧*/
    		to_network_layer(&r.info); /*pass the data to the network layer 将数据中的包向上传递到网络层*/
    	}
    }
    

    单工停-等协议 协议2

    无限制的单工协议条件过于完美,现实中要想实现就需要不断解除这些完美条件。

    单工停-等协议首先取消了可用缓存空间无限大这一理想条件

    也因此,需要解决接收方有可能被发送方传输的大量数据淹没这一问题

    解决方法:

    接收方在每次接收到数据后,会向发送方返回一个哑帧,表示自己已经正常接收到数据,并且可以继续接收数据。发送方在收到返回的哑帧后,才会继续传输下一个数据。
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6isDOE9a-1586083911082)(http://47.97.124.78:8000/wp-content/uploads/2020/03/停等协议.png)]

    代码实现:

    
    
    typedef enum { frame_arrival } event_type;
    #include "protocol.h"
    void sender2(void)
    {
    	frame s; /*buffer for an outbound frame*/
    	packet buffer; /*buffer for an outbound packet*/
    	event_type event; /*frame arrival is the only possibility */
    	while (true) {
    		from_network_layer(&buffer); /*go get something to send */
    		s.info = buffer; /*copy it into s for transmission*/
    		to_physical_layer(&s); /*bye - bye little frame */
    
    		/*
    		 *这里体现了与第一种协议的区别,
    		 *在发送一条数据后不会立即循环发送下一条
    		 *而是等待返回的哑帧再进一步操作
    		 */
    		wait_for_event(&event); /*do not proceed until given the go ahead*/
    	}
    }
    void receiver2(void)
    {
    	frame r, s; /*buffers for frames*/
    	event_type event; /*frame arrival is the only possibility */
    	while (true) {
    		wait_for_event(&event); /*only possibility is frame arrival */
    		from_physical_layer(&r); /*go get the inbound frame */
    		to_network_layer(&r.info); /*pass the data to the network layer */
    		/*
    		 *与第一种协议不同之处
    		 *收到信息并传到网络层后,没有立即进入接收状态
    		 *而是返回一段哑帧
    		 */
    		to_physical_layer(&s); /*send a dummy frame to awaken sender */
    	}
    }
    

    有噪声信道的单工协议-协议3

    有噪声的单工信道协议在前文基础上,取消了帧不会损坏或丢失这一理想条件

    认为信道中含有噪声,有噪声就会引发错误

    进而考虑如何处理以下衍生问题并解决

    发现错误后如何通知发送方,如何修正错误,恢复正确帧:(PAR肯定确认重传协议/ARQ自动重传请求)

    在接收方对数据进行检验并且检验正确后,会向发送方返回一个确认帧,发送方在收到确认帧后继续传输数据。

    发送方在数据发送的同时启动重传定时器(防止锁死),超过定时器规定时间还未收到确认帧(发送过程失败或者返回确认帧过程失败,或者检验错误),发送方就会重置计时器,并且重传原数据。

    在传输过程中,每个帧都具有自己独一无二的编码,防止数据帧成功到达接收方并且检验合格但返回确认帧失败的问题,同时方便重排

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HPq3IYbX-1586083911083)(http://47.97.124.78:8000/wp-content/uploads/2020/03/ARQ.png)]

    代码实现:

    typedef enum { frame_arrival } event_type;
    #include "protocol.h"
    void sender3(void)
    {
    	seq_nr next_frame_to_send; /*seq number of next outgoing frame 出站序列号-用于区别各个帧 */
    	frame s; /*scratch variable */
    	packet buffer; /*buffer for an outbound packet*/
    	event_type event;
    	next_frame_to_send = 0; /*initialize outbound sequence numbers 初始化出站序列号 */
    	from_network_layer(&buffer); /*fetch first packet 获取第一个数据包*/
    	while (true) {
    		s.info = buffer; /*construct a frame for transmission 将包放入帧的载荷*/
    		s.seq = next_frame_to_send; /*insert sequence number in frame */
    		to_physical_layer(&s); /*send it on its way 向物理层传输 */
    		start_timer(s.seq);  /*if answer takes too long, time out 开启重传计时器*/
    		wait_for_event(&event); /*frame arrival, cksum err, timeout 等待确认帧返回*/
    		if (event == frame_arrival) {  //判断是否返回确认帧
    			from_physical_layer(&s); /*get the acknowledgement 获取物理层回传的数据*/
    			if (s.ack == next_frame_to_send) {   //获得收方确认则执行以下操作
    				stop_timer(s.ack); /*turn the timer off 重置重传计时器*/
    				from_network_layer(&buffer); /*get the next one to send 从网络层获取下一个传输数据*/
    				inc(next_frame_to_send); /*invert next frame to send 转化序列号*/
    			}
    		}
    	}
    	//如果这个过程中没有收到返回的确认帧,或确认帧表明传输错误
    	//则通过while循环进行重传
    }
    void receiver3(void)
    {
    	seq_nr frame_expected;
    	frame r, s;
    	event_type event;
    	frame_expected = 0;
    	while (true) {
    		wait_for_event(&event); /*possibilities: frame arrival, cksum err*/
    		if (event == frame_arrival) {
    			/*a valid frame has arrived */
    			from_physical_layer(&r); /*go get the newly arrived frame */
    			if (r.seq == frame_expected) {  //获得正确传输的数据
    				/*this is what we have been waiting for*/
    				to_network_layer(&r.info); /*pass the data to the network layer 将数据向网络层传输*/
    				inc(frame_expected); /*next time expect the other sequence nr 下一阶段期待的序列号*/
    			}
    			s.ack = 1 - frame_expected; /*tell which frame is being acked 告知发送方需要传输的数据*/
    			to_physical_layer(&s); /*send acknowledgement 返回确认帧*/
    		}
    	}
    }
    

    提高传输效率的协议实现方式:

    全双工:

    在信道传输的过程中,不再是单向的数据流动,而是除去了常见的收发双方概念,两方同时进行接受与发送数据的工作,提高数据传输的效率

    捎带确认:

    接收方在发送确认帧时,不再新建一个帧,而实挂靠到一个将要前往发送方的数据帧末尾。提高了信道利用率,但要注意,有时收发双方数量是不对等的,也就是我们不一定能等到可以挂靠的数据帧,所以我们要建立一个稍待确认计时器,超时之后直接发送确认帧

    批发数据(管道化技术):

    在等待第一帧的确认帧返回时,不停止数据发送,而是持续发送数据,等第一帧的确认帧返回,再确定是否继续进行发送过程


    滑动窗口协议-协议4

    上文所提到的三种协议都是单工或半双工协议,在等待确认帧返回的空闲时间里不进行任何操作,所以信道的利用率非常低。协议4-6区别于前文三种协议,采用以下几种手段提高信道利用率

    全双工模式

    即在通讯过程中允许双方同时相互传输数据,整个过程模糊了收发双方的概念,因为双方都在同时进行收和发的操作

    管道化技术(批量发送)

    在等待上一帧的确认帧返回时,不是单纯等待,而是继续发送帧。它可以一次性发送多条数据,我们将这些数据的组合称为一个窗口,管道化技术就是在逐个发送窗口。所以我们也称其为滑窗技术

    滑动窗口

    整个过程中双方都对应拥有两个窗口:

    1. 发送窗口:对应着已经发送,未被确认的数据帧的序列号
    2. 期望接收的数据帧的序列号

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1RsM0F3m-1586083911084)(http://47.97.124.78:8000/wp-content/uploads/2020/03/滑动窗口.jpg)]

    可以看到整个滑动窗口的流程是首先从接收一方开始,接收方首先将窗口设置在0位置,表示期望接收到0序列号的帧,接下来发送方开始滑动窗口到0,并向接收方发送0数据帧,在接收方收到第一帧后,接收方返回确认帧并且滑动窗口到1位置表示期望收到1数据帧,发送方在接到确认帧后继续滑动窗口并发送对应帧

    协议代码实现

    #define MAX_SEQ 1			
    #include"protocol.h"
    
    void protocol4(void)
    {
    	seq_nr next_frame_to_send;  //将要发送的帧的序列号
    	seq_nr frame_expected;   //期望收到的帧的序列号
    	frame r, s;  
    	packet buffer;
    	event_type event;
    	next_frame_to_send = 0;  //初始化将要发送的帧的序列号,从0号帧开始发送
    	frame_expected = 0;   //表明期望接受到的帧是0号帧
    	from_network_layer(&buffer);   //从网络曾获取包
    	s.info = buffer;  //放入要发送的帧中
    	s.seq = next_frame_to_send;
    	s.ack = 1 - frame_expected;
    	/*
    	 *由于是双工协议,所以采用了稍待确认
    	 *也就是将确认帧放到数据帧中,提高了信道利用率
    	 */
    	to_physical_layer(&s);  //像物理层开始传输
    	start_timer(s.seq);  //启动计时器
    	while (true) {
    			wait_for_event(&event);  //接收对应事件
    			if (event == frame_arrival) {
    				from_physical_layer(&r);  //从物理层获取返回的确认帧+数据帧 
    				//通过帧的seq号判断是否是期望接受的帧
    				if (r.seq == frame_expected) {  
    					to_network_layer(&r.info); //如果是就将数据继续向网络层传输
    					inc(frame_expected);  
    					//这里调用了一个宏用来移动窗口
    					//这个宏的作用就是将期望的数据帧序列号+1,将期望窗口调整到下一位置
    				}
    				//通过帧的ack号与发送出的帧序列号比较,判断数据是否成功到达接收方
    				//以及是否继续发送下一帧或者重传
    				if (r.ack == next_frame_to_send) {
    					stop_timer(r.ack);
    					from_network_layer(&buffer);
    					inc(next_frame_to_send);
    				}
    			}
    			s.info = buffer;
    			s.seq = next_frame_to_send;
    			s.ack = 1 - frame_expected;
    			to_physical_layer(&s);
    			start_timer(s.seq);
    		}
    }
    

    窗口滑动条件

    接收方收到帧后,首先核对帧是否与期望相同,如果相同,则返回确认帧并且滑动接收窗口(frame_expected+1)然后将数据像网络层传输

    发送方在收到确认帧后,核对响应帧号next_frame_to_send,全部完成后,从网络层获取新的数据,并将响应帧号next_frame_to_send+1即移动发送窗口,然后像物理层传输信息,否则,不移动窗口

    滑动窗口基本概念

    每个待发送帧被赋予一个序列号seq,seq的取值范围是 0 ~ 2^n-1(n位字段)

    发送窗口

    • 顺序接收来自网络层的分组->成帧->赋予序列号
    • 最多保存W个已经发送、等待确认的帧
    • 窗口达到最大值W时强制关闭网络层

    接收窗口

    • 对进入窗口的帧顺序提交网络层,产生确认
    • 落在窗口外的帧被丢弃

    SEQ码和ACK码

    因为滑动窗口协议只涉及1个窗口,所以在传输过程中,SEQ码和ACK码的取值只有0和1两种,当SEQ码=1时,表示当前发送的数据为1序列号的帧,当ACK码为1时,表示已经成功接收序列号为1的帧,期望接收序列号为0的帧(这里与直观感受并不一致)

    通信双方初始值:seq =0, ack=1(期待接收seq=0)

    窗口滑动机制

    • A首先发送数据帧(seq=0, ack=1, A0)–发送0帧,期望收到0帧
    • B收到A0,发送捎带确认帧(seq=0, ack=0, B0)–发送0帧,成功收到0帧,期望收到1帧
    • A收到对A0的确认,滑动窗口,发送帧(seq=1, ack=0, A1)–发送1帧,收到0帧,期望收到1帧

    协议帧的差错控制

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2eyjMJu7-1586083911084)(http://47.97.124.78:8000/wp-content/uploads/2020/03/传输过程.png)]

    可以看到在发生错误后,由于计时器时间设置不合理,接收方收到重复帧,这种情况下接收方会发送同样的确认帧返回发送方,但不会接收当前传过来的重复帧,这就使得整个流程可以正常运行,不会因为错误帧而中断。但整个流程效率极低


    效率问题

    假设窗口每次只发送一帧,那么可以通过运算获得整个过程的信道利用率:

    信道传输速率是: b (bps)
    
    每帧的大小是: k (bits)
    
    来回时间是: R (sec)
    
    信道利用率=\frac{k}{k+bR}
    

    带入数据:信道容量 b = 50 kbps,传输延迟 R = 500 ms(双程),数据帧的长度 k = 1000 bit。(设接收方收到数据帧后马上回送确认短帧,没有延时)

    可以算的信道利用率为3.85%,不足4%,利用率极低。这是因为我们一个窗口只发送了一帧,这一帧到达之前,窗口始终处于空闲状态,所以需要设定窗口合理的帧数,使利用率提高(增加滑动窗口长度)

    设窗口长度为W(一个窗口发送字节的数量)

    在源端发送数据帧过程需要的时间=T_f =\frac{k}{b}
    
    从发送完毕到确认帧返回需要的时间(双程延迟)R
    
    从开始发送到确认返回总共需要的时间(T_f +R)
    
    线路的利用率=\frac{W*T_f}{T_f +R}
    

    上文实例中若假设信道利用率为100%,可以解得W=26,也就是一个窗口发送26帧时,信道利用率最高。当然,这只是理想状态下的假设,正常情况下一般无法达到信道100%的利用

    如何确定合适的W值

    信道上的容量:一帧从发送方传输到接收期间可容纳的帧数量

    带宽-延迟积:BD(B表示带宽,D表示时间)

    窗口值:w=2*BD+1

    实际上:w≤2*BD+1


    例题:

    主机甲和主机乙之间使用后退N帧协议(GBN)传输数据,甲的发送窗口尺寸为1000,数据帧长为1000字节,信道为100Mbps,乙每收到一个数据帧立即利用一个短帧(忽略其传输延迟)进行确认。若甲乙之间的单向传播延迟是50ms,则甲可以达到的最大平均传输速率约为?

    解题:

    假设平均传输效率为x(Mbps)

    根据w=2*BD+1

    易知: 1000 = 2 ∗ x ( M b p s ) ∗ 50 ( m s ) ∗ 1 0 − 3 + 1 1000=2*x(Mbps)*50(ms)*10^{-3}+1 1000=2x(Mbps)50(ms)103+1

    解得:x=80Mbps


    管道化技术面临的出错情况

    • 连续发送W个数据帧,其中有一帧出错,但其后续帧被成功
      发送

    接收方的接收策略选择

    • 丢弃错帧及后续帧,其后续帧因不是期望接收帧也被丢弃,对应协议5
    • 丢弃错帧,缓存后续正确接收帧,对应协议6

    回退n帧-协议5

    上文提到了使用管道化技术带来的新问题与两种解决方式

    1. 回退n帧
    2. 选择性重传

    这两种协议对应着不同的接收发送策略

    回退n帧

    接收方的接收策略与选择:

    直接将错误帧与后续帧丢弃,后续的正确帧到来后因不是期望帧也被舍弃

    发送方的发送策略:

    发送前将所有帧缓存,在收到确认帧后,未为成功发送的帧以及后续所有帧进行重传

    选择性重传

    接收方的接收策略与选择:

    丢弃错误帧,将剩余正确帧保留并缓存

    发送方的发送策略:

    在收到确认帧后只重传错误帧


    回退n帧

    基本概念

    • 定义了序列号seq,以及滑动窗口长度W
    • 发送方持续发送数据,直到达到最大窗口长度
    • 接收窗口为1,在接到错误帧后不确认(引发超时,进而重传)
    • 发送方超时后进行重传,从未收到的确认帧处开始

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0oRW9PRW-1586083911085)(http://47.97.124.78:8000/wp-content/uploads/2020/03/回退n帧.jpg)]

    可以看到在发送过程中,从2号帧开始出错,则后续帧都被丢弃。之后接收方会返回1号帧的确认帧(注意!不是返回2号帧,而是返回错误帧的上一位帧的确认帧,因为1号帧成功被接收,发送方借此可以判断是从2号帧开始需要重传的)

    在这里插入图片描述

    累计确认

    在滑动窗口中采用了累计确认的方式来对帧进行确认

    也就是说在收到对于5号帧确认时,暗含的意思就是已经完成了对0,1,2,3,4,5这几个帧的确认,而不必要每一个都发送确认帧

    对于发送方,这样在接收到第n帧确认后,就可以删除n帧及以前所有的缓存

    但这同样也引发了新的问题(规定):

    滑动窗口最大长度W不能超过最大序列号
    比如:序列号用三位表示,则最大序列号=111。表示7,所以窗口长度不能等于8或超过8,超过8很好理解,因为如果窗口长度大于8,则,没有足够的序列号为每一个帧标记。

    当序列号等于8时,有足够标记(0,1,2,3,4,5,6,7)但这也是不允许的,因为这会引发新的问题。

    我们在返回确认帧时采取了累计确认,当第一个窗口的8个帧全部被顺利接收后,接收方会返回一个确认帧ACK=7,表示已经正常收到7号帧及之前元素,可以继续发送下一窗口了。

    这时如果发送方在发送第二个窗口时发生错误,接收方根本没收到期望帧,就会重新发送确认帧ACK=7表示自己期望接受第二个窗口,可这时就会发生混淆,发送方不能分别这个确认帧,是希望对窗口二进行重传还是表示已经正常接收到窗口二。 无法正确执行程序

    如果滑动窗口不超过8就不会有这种问题,比如滑动窗口为7,这样第一窗口的确认帧是ACK=6,第二窗口的确认帧是ACK=5(因为第二窗口帧的序列号是从7开始的:7,0,1,2,3,4,5)

    这样就避免了过程中可能产生的歧义,很好的解决了问题

    回退n帧需要发送方付出更大的缓存代价,缓存整个窗口的数据帧

    适合出错较少的高速信道


    选择性重传-协议6

    基本概念

    • 接收窗口接收错误帧后的所有正确帧,并将它们缓存起来
    • 发送方只重传错误帧
    • 接收方在接收到重传帧后,将其与其他帧按正确顺序排序,再提交至网络层

    选择重传协议的工作原理分析

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CbxpKp2C-1586083911086)(http://47.97.124.78:8000/wp-content/uploads/2020/03/接收方发送方2.png)]

    否定确认NAK

    • 在接收方收到错误帧时会发送否定确认NAK到发送方
    • 这样可以加快出错帧的重传
    • 对出错帧回送否定确认,使发方不再等到超时再重传

    滑动窗口长度选择

    接收窗口:W= (MAX_SEQ + 1) / 2

    发送窗口一般小于接收窗口

    原因:

    当发送窗口和接收窗口都比较大时,就会导致新老窗口序列号重叠,比如说序列号为3位(XXX),收发窗口大小都是7,则接收窗口第一次为(0,1,2,3,4,5,6),第二次为(7,0,1,2,3,4,5)。这其中(0,1,2,3,4,5)都为重叠部分。

    当接收方正确接收第一窗口并滑动窗口后,确认帧被发送出去,但在确认帧发送过程中,全部丢失。所以发送方超时进行重发(0,1,2,3,4,5,6)这个窗口,当0号帧到达时

    接收方不能判定他是重传帧,反而在第二个窗口发现了对应帧的序列号,这个重传帧就被错误的放在了第二个窗口,而实际上,它只是第一个窗口的重传帧而已


    当W遵守W= (MAX_SEQ + 1) / 2 的规定时,就可以保证新老窗口之间没有重叠部分。,可以正常通过帧的序列号判定帧的类型

    协议4:滑动窗口协议5:回退n帧协议6:选择性重传
    发送窗口(SWnd)0<SWnd<=10 <=SWnd<=MAX_SEQ0 <= SWnd<= RWnd
    接收窗口(RWnd)11(MAX_SEQ+1)/2

    两种策略比较

    回退n帧

    • 发送方需要较大的缓冲区,以便重传
    • 重传帧数多,适于信道出错率较少的情况

    选择重传

    • 接收方需要较大的缓冲区,以便按正确顺序将分组提交网络层
    • 重传帧数少,适于信道质量不好的情况
    展开全文
  • LLC逻辑链路控制子层

    千次阅读 2017-10-17 21:20:09
    LLC逻辑链路控制子层
    数据链路层的LLC子层用于设备间单个连接的错误控制,流量控制。
    
            与MAC层不同,LLC和物理媒介全无关系。媒介是CSMA/CD的802.3还是802.5的令牌环都没关系。它在LAN中是独立的802.2。在LLC之上的网络层可以是无连接、响应的无连接或面向连接的不同业务。
            LLC用业务接入点SAP访问上层协议,有了SAP,站点就能在LLC层只用一个接口同时与几个高层协议玩。一个SAP是简单的地址或协议ID,内容则为空的LLC帧。LLC协议数据单元(LLCPDU)即LPDU。它包括:DSAP(目的SAP)/SSAP(源SAP);一个定义吞吐量优先级的控制域(Controlfield);和含带数据的信息域。在接收方,DSAP例如协议ID就是消息要被递送的,通常DSAP和SSAP是一样的,因为两端只有在同种协议间才能通信。例如当SAP为AA,代表SNAP(子层接入协议)。SNAP是个非标准化的,或厂商特定的协议,用于接入协议的业务。例如当SAP为06,则代表IP协议;当SAP为FO,代表NetBIOS(网络基本输入/输出协议)。SAP为FF表示广播的Global协议。

      SNAP机制

            规范种DSAP都只有一个字节,那不足够区分所有协议了。SNAP就来了,而且它支持在LLC帧上传厂商的协议。这样传递的协议就被放入所谓SNAP帧中了。SNAP”ㄍ酚形遄纸冢前三字节为厂商号,后两字节指示协议。
            以太网有两种版本:IEEE(802.2、802.3); DIX(Digital、Intel、Xerox)又称V2以太网。
            DIX帧在源地址之后是两字节的Type,例如IP。
            IEEE以太网帧,在源地址后是帧长度指示,在随后的数据域中才是标准的LPDU封装,包括DSAP/SSAP/控制域/Data。在这个Data中会有协议ID、以太类型指示,例如以太类型806表示地址解析协议ARP。以太网卡通过跳针或软件可以设置需要的以太网版本,DIX通常都设的,因为大约90%的网络都用此版本。请注意网络所有要通信的站点应设成相同版本。
    展开全文
  • 1、逻辑链路控制子层 2、以太网(Ethernet) 3、世界上最早的无线电计算机通信网:ALOHA 4、CSMA(Carrier Sense Multiple Access)协议:载波监听多路访问协议 三、以太网的MAC层协议 1、...

    目录

     

    一、概述

    1、多路访问链路

    2、介质访问控制子层的由来

    二、介质访问控制子层(Media Access Control, MAC层)

    1、逻辑链路控制子层

    2、以太网(Ethernet)

    3、世界上最早的无线电计算机通信网:ALOHA

    4、CSMA(Carrier Sense Multiple Access)协议:载波监听多路访问协议

    三、以太网的MAC层协议

    1、发送帧的方法:CSMA/CD(Carrier Sense Multiple Access With Collision Detection)协议,即1-persistent CSMA

    2、二进制指数退避算法(binary exponential backoff)

    3、802.3的MAC帧格式(802.3标准是以太网的一个协议)

    4、地址类型

    5、以太网接收帧的方法

    6、其他知识点

    四、以太网的物理层

    1、冲突域和广播域

    2、集线器(hub)和交换机(switch)

    3、交换机的转发方法:

    4、交换机的自动翻转:

    五、透明网桥

    1、相关概述

    2、三种操作:

    3、MAC地址表

    4、透明网桥算法

    5、自学习

    6、自学习的合理性:

    六、生成树协议(Spanning Tree Protocol)

    七、虚拟局域网VLAN

    八、令牌环网


    一、概述

    1、多路访问链路

    多路访问链路(广播链路)采用共享介质连接所有站点。发送站点通过广播方式发送数据并占用整个共享介质的带宽。每个站点只需要一条线接入网络就可以访问该链路上的所有站点。【局域网LAN使用的就是多路访问链路】

    2、介质访问控制子层的由来

    在多路访问链路中多个站点同时发送数据会造成冲突,因此OSI(开放式系统互联通信参考模型)为解决冲突问题,专门在数据链路层划分出一个子层:介质访问控制子层,以控制和协调所有站点对共享介质的访问,避免或减少冲突。即MAC层定义了主机何时以及如何访问共享介质

    二、介质访问控制子层(Media Access Control, MAC层)

    1、逻辑链路控制子层

    MAC子层不提供可靠的数据传输,在这一层之上又定义了一个子层:逻辑链路控制子层(logic link control, LLC)用来为上层协议提供服务。如滑动窗口就是在LLC层中实现的,其中LLC2提供了有确认的面向连接的服务(TCP)。【LLC:提供可靠的数据传输】

    2、以太网(Ethernet)

    以太网属于OSI参考模型的数据链路层,是为了实现局域网通信而设计的一种技术,它规定了包括物理层的连线、电子信号和介质访问层协议,是目前应用最普遍的局域网技术。

    3、世界上最早的无线电计算机通信网:ALOHA

    • 纯ALOHA协议(随机访问/竞争发送协议):想发送就发送,超时未收到确认则认为发送了冲突。
    • 分槽ALOHA协议:把时间分为长度相同的时槽(slot),每个站点只在时槽开始时发送,信道空则立即以概率P发送,以概率1-P延迟一个时槽;若信道忙则延迟一个时槽。

    4、CSMA(Carrier Sense Multiple Access)协议:载波监听多路访问协议

    CSMA协议属于随机访问协议(Random Access Protocol)的一种,它遵循发送前先监听信道的规则:

    • 1-persistent CSMA(以太网使用):信道空则立即发送,信道忙则持续监听(所以如果信道为空时有两个站点同时发送数据则它们一定会产生冲突);
    • non-persistent CSMA:信道空则发送,信道忙则延迟一段随机长度的时间(这种方式在信道较忙时最省电)。
    • p-persistent CSMA(分槽ALOHA):信道空则立即以概率P发送,以概率1-P延迟一个时槽,信道忙则延迟一个时槽。

    三、以太网的MAC层协议

    1、发送帧的方法:CSMA/CD(Carrier Sense Multiple Access With Collision Detection)协议,即1-persistent CSMA

    • 发送数据帧之前先监听信道,如果信道空闲则立即发送,如果信道忙则持续监听,直到信道空闲,立即发送。(发送前持续监听时,如果监听到96bits的空闲则说明当前信道空闲,立即发送信号。96bits的空闲可以用于区分帧,即以太网采用了inter-frame space的成帧方法
    • 边发送边检测冲突,如果发送完毕都没有检测到冲突则发送成功。
    • 如果检测到冲突,则停止发送,并发送32位干扰位(jamming signal)以加强冲突信号。采用二进制指数退避算法随机延迟一段时间后执行第一条操作。(因此第一个冲突的概率无法计算)

    注意两个概念:

    • 监听信道:指的是在未发送信号时监听,监听的是主机接入到多路访问链路上的共享链路的位置是否有数据在传输;
    • 边发送边检测冲突:指的是在帧的发送延迟这段时间内检测是否有冲突;

    2、二进制指数退避算法(binary exponential backoff)

    这里引入最短帧的问题:

    以太网(10Mbps)相距最远的两个站点之间的信号往返时间为51.2微秒。如果A发送的数据在快到B时与其发送的数据冲突(因为B检测到其上方的共享链路为空则发送,此时可能A还没传到B,但B一发送A就到了),因为发送站点只有在发送的时候才检测冲突,为了检测到返回的冲突信号,要求此时站点A仍在发送数据帧,故一个数据帧至少为512bit(64B,由51.2微秒乘上10Mbps所得),即一个往返时间的字节长度。这也就是最短帧的长度,这个长度同时也被称为争用窗口长度(contention window)。

    为什么二进制指数退避算法选择最短帧的发送时间作为其时间槽/片的长度?

    因为,最短帧的发送时间保证了首先发送的信号可以到达最远的站点,如果先发送的只有一个站点,那么其他站点要不就是检测到发送站点的信号而不能发送自己的信号,要不就是因为发送站点发送完毕而检测到信道空闲,总之不会与之冲突。即时间槽的长度为最短帧发送时间或者大于最短帧发送时间,则可以保证两个发送数据的站点不会发生冲突。

    分析下面问题:

    最长帧1520B,一个64B(最短帧)的帧的传送需要一个时间片,所以一个最长帧需要23个时间片。故最少情况下第一次冲突时,只有一个站点发送成功,其他四个站点继续监听信道,直到信道空闲时立即发送,产生第二次冲突,...,以此类推,由于前四次冲突后各站点最多可以延迟15个时间片再发送,15<23,故每一次延迟后信道上仍有帧在发送,故每一次冲突只能成功发送一个信号,所以总共需要四次冲突。

    3、802.3的MAC帧格式(802.3标准是以太网的一个协议)

    • 前导字符(preamble):包含同步字符和起始定界字符;
    • 有效载荷(payload):是用户数据,不足46字节时加入填充字节至46字节;
    • 类型/长度:若值大于1500,则用于指明上层协议;若值<=1500,则用于指明有效载荷长度;

    4、地址类型

    • 单播地址:全球唯一,每个网卡(或接口)有一个单播地址,最高字节的最低有效位是0,也称为网卡地址,烧录地址BIA,MAC地址、硬件地址、物理地址;共48位

      厂商号(3B)

           序号(3B)

    • 多播地址:0号字节的第0位为1;
    • 广播地址:48位地址全为1;

    5、以太网接收帧的方法

    • 以太网站点会缓存所有的帧
    • 如果缓存的帧有错则丢弃;
    • 如果缓存的帧的目的地址为单播地址且与接收该帧的网卡的MAC地址一致,则接收它;如果目的地址为多播地址且为网卡预设的多播地址之一,或者目的地址为广播地址,也接收该帧。其他情况则丢弃该帧。
    • 如果把网卡设置为混杂模式则会接收所有无错的帧。

    6、其他知识点

    • 以太网的物理层采用的是异步传输,采用曼彻斯特编码。命名规则为10BaseT,表示10Mbps,base=基带传输,T表示双绞线
    • 以太网中的一个站点有可能一直不能成功发送信号
    • 规定最短帧是为了使得发送站点可以检测到所有冲突
    • 属于同一个以太网的所有站点可以收到广播帧;
    • 以太网、快速以太网和千兆以太网主要在OSI的物理层不同(传输介质);
    • 以太网传输速率的提高会使得可传输距离缩短,因为速率越高,对信号干扰的规定越严格,而线路越长抗干扰能力越弱,想要在长距离上进行高速传输只有靠光纤,无法使用双绞线。

    四、以太网的物理层

    1、冲突域和广播域

    • 如果通过两个接口同时发送数据会产生冲突,则这两个接口属于同一个冲突域(collision domain),属于同一个冲突域的以太网部分称为网段;
    • 一个广播帧可以到达的所有接口属于同一个广播域;

    2、集线器(hub)和交换机(switch)

    • 集线器收到一个bit就立刻转发给所有其他接口,其所有接口都属于同一个冲突域。而交换机的每个接口属于一个冲突域,但所有接口属于同一个广播域。
    • 集线器是将信号收集放大后传输给所有其他端口,即集线器的传输线路是共享的;而交换机能够选择目标端口,在很大程度上减少了冲突的发生,能够为通信双方提供一条独占的线路。(即交换机增加了冲突域的数量,但减小了冲突的范围);
    • 集线器上的数据传输属于半双工传输,交换机上的数据传输属于全双工传输
    • 集线器只属于物理层
    • 交换机跟踪与它直接相连的设备的MAC地址;

    3、交换机的转发方法:

    • 存储转发:交换机接收整个数据帧后转发它;
    • 直通(cut through):交换机收到帧的硬件地址后立即转发它,如果输出忙则会转为存储转发;
    • 无碎片(fragment free):交换机收到帧的前64个字节(最短帧长度)后立即转发它
    • 适应性交换:自动在上面三种方式进行选择;

    4、交换机的自动翻转:

    指的是网线接口的切换。网线分为直通线和交叉线。当同种设备连接时需要用到交叉线(如电脑之间的直连),当不同设备连接时需要用到直通线(如电脑和交换机相连),自动反转指的是交换机的端口会自动根据接入的线对信号进行调整。

    五、透明网桥

    1、相关概述

    • 用网桥连接若干个局域网可以建造一个更大的局域网,称为桥接的局域网或扩展局域网,原来的局域网称为扩展局域网的一部分,称为一个网段(一个网段是一个冲突域);
    • 透明网桥采用的是广播模式;
    • 网桥由交换机实现,因为对于终端来说它们不知道网桥的存在,不需要通过修改自己的配置来适应网桥,所以称为透明网桥;

    2、三种操作:

    • 扩散(flood):网桥把收到的帧转发到除了该帧的接收端口之外的所有其他端口;
    • 转发(forward):把收到的帧转发到查到的端口;
    • 过滤(filter):当根据帧查到的端口(即网桥要转发该帧的端口)与收到该帧的端口一致则丢弃该帧,防止重复传输帧;

    3、MAC地址表

    查询收到的帧的MAC地址需要从哪个端口转发,查不到则扩散。

    4、透明网桥算法

    当网桥收到一个单播帧时,则用该帧的目的地址查询MAC地址表,如果没查到则扩散该帧;如果查到了则看查看到的端口是否为收到该帧的端口,如果是则丢弃该帧,否则把该帧从查到的端口发送出去;

    5、自学习

    • MAC地址表初始为空;
    • 网桥从端口接收所有的帧,并把接收到的帧的源地址和接收端口记录到MAC地址表中。如果该源地址在MAC地址表中不存在,则增加一个新记录并启动超时定时器;如果存在则更新接口并重置超时定时器;
    • 网桥会自动删除超时的记录;

    6、自学习的合理性:

    • 网桥从一个接口收到一个帧,则该帧中源地址的主机一定与该接口连通;
    • 如果整个扩展局域网没有回路,则该接口处于从该网桥到达该主机唯一的路径上,该网桥只有把目的地址为该源地址的帧转发到该接口才能使该帧可能到达目的地;

    六、生成树协议(Spanning Tree Protocol)

    • 网桥ID:BID,优先权+网桥的MAC地址;
    • 端口ID:PID,优先权+序号;
    • 根端口:网桥上离根网桥最近的端口;
    • 指定网桥:网段上离根网桥最近的网桥;(这是从网段的角度去看的)
    • 指定端口:指定网桥与对应网段之间相连的端口(网桥只在根端口和指定端口之间传输数据
    • 可以这样理解,网桥上的端口只有三种:根端口、指定端口和阻塞端口,阻塞端口就是无法转发帧的端口;
    • 根网桥的确定:一开始生成树中所有网桥都以广播形式传帧,各个网桥只要接收到了比其BID还小的网桥发送的帧,就停止发送。

    只要两个网桥之间有通路,在构造生成树的时候它们就会连接在同一棵树中

    七、虚拟局域网VLAN

    据上图,如果网桥只在具有相同颜色的端口之间转发帧,就会把原来的局域网分割成多个相互隔离的局域网,称为虚拟局域网。

    所谓的颜色其实就是VLAN ID,是由管理员为每个端口配置的一个标识。具有相同的VLAN ID的端口处于同一个VLAN,端口的默认VLAN为VLAN1;

    要点:

    • 一个VLAN的帧只能转发到属于同一个VLAN的端口或者干道端口;
    • 干道(trunk)可以接收所有颜色的帧,但每一帧需要加上自己的VLAN ID;
    • 只有发往干道端口的帧才需要加上VLAN ID;
    • 从干道收到的帧中如果没有VLAN ID,则认为是本征VLAN(Native VLAN),默认为VLAN 1;
    • 发往干道的Native VLAN不需要加VLAN ID;

    上图中VLAN可以从E发信息给A也可以从A发信息给E。

    如果从A发给E,因为S2转发到S3的端口是VLAN10的端口,所以可以转发,而S3与S2连接的端口是VLAN20,所以S3会认为接收到的帧都是VLAN20的帧,然后转发给E。(因为只有发往干道端口的帧才需要加上VLAN ID)

    八、令牌环网

    • 令牌环网采用了Take Turns Protocol,是一个通过在站点之间传递令牌防止冲突并且具有优先权的VLAN,其标准为IEEE 802.5。(令牌指的是帧)
    • 令牌环网需要设置监控站点(以竞选的方式决定),用于检测令牌是否丢失。
    • 同时监控站点也用于监控数据帧,每次收到一个数据帧就对其标记,当再次接收到被标记的数据帧时说明数据帧的传输出现问题(该数据帧没有被任何站点接收),把该帧删除。
    • 监控站点也需要定时发送帧给其他站点让其他站点检测监控站点是否失效。
    • 光纤分布式数据接口是一种采用了令牌环的局域网。

    数据传送过程:

    • 令牌绕环而行;
    • 只有截获令牌的站点才可以发送数据帧;
    • 发送的数据帧通过所有的活动站点;
    • 目的站点拷贝数据帧;
    • 当没有数据帧要发送或者持有时间到,当前的发送站点要释放令牌。

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 介质访问控制子层(MAC子层)概述 MAC子层要解决的问题 1. 介质的多路访问控制/介质访问控制MAC 2. 数据通信方式(单播/广播/组播) 单播(unicast):一对一的通信,是客户端与服务器之间的点到点连接 广播...

    原文链接

    介质访问控制子层(MAC子层)概述

    MAC子层要解决的问题

    1. 介质的多路访问控制/介质访问控制MAC

    2. 数据通信方式(单播/广播/组播)

    • 单播(unicast):一对一的通信,是客户端与服务器之间的点到点连接
    • 广播(broadcast):一对所有的通信,发出的信息,要送达到所有对象
    • 组播(multicast):一对一个组的通信,发出的信息送达到特定组的用户

    局域网中采用了共享传输介质的方式来降低成本,共享传输介质上通常采用的就是广播的通信方式


    广播网络面临问题

    一条信道上有多个站点,所以会出现在共享信道(多路访问信道,广播信道)上同时有两个甚至更多的站点同时请求占用网络

    解决方法:

    介质的多路访问控制:在多路访问信道上确定下一个使用者(分配信道)

    分配信道方式:

    • 静态分配:预先分配信道给用户,对于不同用户也采用相同的信道分配方式
    • 动态分配:信道开放,没有预分配,按照需求临时分配给用户

    静态分配

    已经学习过的静态分配方式:

    • 频分多路复用 FDM(Frequency Division Multiplexing)
    • 时分多路复用 TDM(Time Division Multiplexing)

    缺陷:

    • 信道分配不合理,资源没有按需分配
    • 有资源浪费,效率低
    • 由于信道可能是按时间分配的,所以延迟时间增大N倍

    静态信道分配的排队模型(符合M/M/1排队系统模型)

    M:

    帧到达时间间隔服从指数分布(顾客到达时间间隔分布)

    平均到达率(输入率):λ 帧/秒

    M:

    帧长度服从指数分布,平均长度 1 μ \frac{1}{μ} μ1 (位/帧) (顾客到达时间间隔分布)

    信道容量为C 位/秒,则信道服务率为μC (帧/秒)

    1:

    并列服务台个数为1

    根据排队理论,可证明:单信道平均延迟时间(顾客在服务系统中的逗留时间)为:

    T = 1 μ C − λ T=\frac{1}{μC-λ} T=μCλ1

    信道N等分后每个子信道的平均延迟时间

    M — 平 均 输 入 率 : λ N M —平均输入率: \frac{λ}{N} MNλ

    M — 平 均 服 务 率 : μ C N M —平均服务率: \frac{μC}{N} MNμC

    T F D M = 1 μ ( C / N ) − ( λ / N ) = N μ C − λ = N T T_{FDM}=\frac{1}{μ(C/N)-(λ/N)}=\frac{N}{μC-λ}=NT TFDM=μ(C/N)(λ/N)1=μCλN=NT

    得证:信道N等分后每个子信道的平均延迟时间增大N倍

    适用范围:

    • 用户量少,用户数目固定
    • 通信量大且流量稳定
    • 不适用于突发性业务的情况

    动态分配

    通过多路访问协议,动态分配信道资源,可以提高信道利用率

    多路访问协议分为两大类

    • 随机访问协议
    • 受控访问协议

    随机访问协议

    站点/用户争用信道,可能会出现站点之间的冲突

    典型的随机访问协议

    • ALOHA协议
    • CSMA协议
    • CSMA/CD协议(以太网采用此协议)

    受控访问协议(Controlled Access)

    特点:站点明确被分配占用信道,不会产生冲突


    ALOHA协议

    上世纪七十年代诞生于夏威夷大学的随机访问协议,为了解决夏威夷群岛与檀香山之间的无线网络通信问题。无线信道是典型的广播/共享信道

    ALOHA协议有两个版本:

    • 纯ALOHA协议
    • 分隙ALOHA协议(隙是时隙,时槽的意思)

    纯ALOHA协议

    工作原理

    • 任何一个信道都可以在帧生成后立刻发送帧(可能发生冲突,且不关心信道是否已经被占用),通过信号的反馈,检测信道,确定是否发送成功
    • 两个以上站点都在发送数据时就会发生冲突
    • 对于发送失败的帧,在随机延时后,继续重新发送

    在这里插入图片描述

    重要概念

    吞吐率(Throughout) S

    在发送时间T(一个帧时)内,发送成功的平均帧数

    显然:0<S<1

    S = 1时分组一个接一个地发送出去,帧之间没有空隙。一
    般用S接近于1的程度来衡量信道的利用率

    运载负载(Carried load) G 又称网络负载

    时间T内所有通信站总共发送的帧平均值(包括原发和重发的分组)。

    显然G>=S,当G=S时表示无冲突发生,G>S时,表示存在冲突,当G>1时,表示冲突频繁

    p0

    一帧发送成功(即未发生冲突)的概率。即发送成功的分
    组在已发送分组的总数中所占的比例。

    三者之间存在关系:

    S = G ∗ P 0 S=G*P_0 S=GP0

    冲突危险期

    发送的帧容易根其他帧发生冲突的时间

    在纯ALOHA协议中冲突危险期是2T

    在2T内生成帧的均值是2G

    生成k帧的概率服从泊松分布

    P r [ k ] = G k e − G k ! P_r[k]=\frac{G^ke^{-G}}{k!} Pr[k]=k!GkeG

    所以生成0帧的概率就是

    P r [ 0 ] = G 0 e − G 0 ! = e − G P_r[0]=\frac{G^0e^{-G}}{0!}=e^{-G} Pr[0]=0!G0eG=eG

    在冲突危险期内发送成功的概率就是在2T内都不产生新帧的概率,所以

    P 0 = P r [ 0 ] ∗ P r [ 0 ] = e − 2 G P_0=P_r[0]*P_r[0]=e^{-2G} P0=Pr[0]Pr[0]=e2G

    带入纯ALOHA协议中

    S = G ∗ P 0 = G ∗ e − 2 G S=G*P_0=G*e^{-2G} S=GP0=Ge2G

    两边求导,求极值

    S ′ = e − 2 G − 2 G ∗ e − 2 G = 0 S^{'}=e^{-2G}-2G*e^{-2G}=0 S=e2G2Ge2G=0

    当G=0.5时,S取得极大值≈0.184,即纯ALOHA协议信道利用率最大可达到18.4%

    分隙(分槽)ALOHA协议

    协议原理

    把时间分成时间片(时隙),时隙长度=1帧时T

    新帧的产生仍然是随机的,但不再允许随机发送

    每一个发送帧想要发送必须等待时槽的起点,等到时槽起点到来才可以发送,所以冲突只可能发生在时槽的起点冲突危险期缩短为T

    一旦某个站占用时隙并且发送成功,则在这个时隙内就不会发生冲突(因为其他帧在这段时间内不能发送)

    在这里插入图片描述

    显而易见,由于冲突时间减小,所以P0发生变化,性能随之提高

    P 0 = P r [ 0 ] = e − G P_0=P_r[0]=e^{-G} P0=Pr[0]=eG
    S = G ∗ P 0 = G ∗ e − G S=G*P_0=G*e^{-G} S=GP0=GeG
    S ′ = e − G − G ∗ e − G = 0 S^{'}=e^{-G}-G*e^{-G}=0 S=eGGeG=0

    解得极值位于1处,此时S约等于0.368,也就是说信道利用率最大为36.8%。较纯ALOHA协议提升了一倍

    在这里插入图片描述


    载波侦听多路访问协议(CSMA)

    属于改进的ALOHA协议,特点是“先听后发

    CSMA分为两大类

    • 非持续式
    • 持续式(又分为1-持续CSMAP-持续式CSMA

    非持续式-载波侦听多路访问协议

    特点:

    1. 经侦听,如果介质空闲,就开始发送
    2. 如果介质忙,则等待一段随机事件
    3. 随机事件结束后,继续重复步骤1

    等待一个随机时间,可以减少站点之间发生冲突的可能性,但在等待这段时间,可能整条信道是空闲的,这就会导致信道浪费

    持续式-载波侦听多路访问协议

    1-持续式CSMA

    1. 经侦听,如果介质空闲,就开始发送
    2. 如果介质忙,就开始持续侦听,直到介质空闲
    3. 如果发生冲突,就等待一个随机时间,然后重复步骤1

    显然,持续式的随机时间要少于非持续式的随机时间

    存在问题:

    一旦一条信道上有两个及以上站点在持续侦听,那么一旦介质空闲下来,多个站点同时争用信道,必然发生冲突

    P-持续式CSMA

    1. 经侦听,如果介质空闲,以P概率发送,以1-P概率延迟一个时间单元
    2. 如介质忙,持续侦听,介质一旦空闲,重复步骤1
    3. 如果已经延迟一个时间单元,就再次重复步骤1

    1-持续式是P-持续式的特例,当概率P为1时,二者相同

    CSMA工作方式如果侦听到介质上没有报文发送,则帧发送后,仍然会发生冲突

    冲突原因

    • 同时传送:两个都在持续侦听的站点在空闲时同时发送帧导致冲突
    • 传播延迟时间

    传播延迟时间

    信号在介质上的传播速度只有在自由空间的65%左右,一般近似为:200m/μs。由于传播延迟时间的存在,某个站发出报文后仍会遇到冲突

    在这里插入图片描述

    冲突窗口

    发生冲突时间的上限,即发送站发出帧后能检测到碰撞的最长时间,数值上等于最远两站传播时间的两倍,即2t

    信号在物理信道上的传播速度v 一般近似为:

    (v=200m/μs,网卡延时= t P H Y t_{PHY} tPHY,最远距离S,t=S/v)

    S l o w t i m e = 2 t + 2 t P H Y Slow time=2t+2t_{PHY} Slowtime=2t+2tPHY
    如果考虑网段上有N个中继器,每个中继器延迟时间为 t 中 继 器 t_{中继器} t,则可得下式:

    S l o w t i m e = 2 ∗ ( t + t P H Y + N ∗ t 中 继 器 ) Slow time=2*(t+t_{PHY}+N*t_{中继器}) Slowtime=2(t+tPHY+Nt)

    CSMA/CD(采用1-持续)

    (带冲突检测的载波侦听多路访问协议)

    工作原理:“先听后发,边听边发”

    特点:

    • 经侦听,如果介质空闲,则发送当前帧
    • 如介质忙,持续侦听,一旦空闲立即发送。
    • 如果发生冲突,等待一个随机分布的时间再重复步骤1
    • 不同于其他CSMA协议,该协议在帧发出后,仍持续监视该帧情况,一旦收到的信号与发出的不一致,就说明发生了冲突
    • 发送站感知冲突后立即停止帧的发送,并且发一个简短的堵塞信号 (称强化冲突信号,Jammingsignal),通知网上各站已经发生冲突,本站及网上所有站都等待一段随机分布的时间,然后再按CSMA/CD方式重发该帧。

    随着P变化P-持续式CSMA吞吐量变化

    在这里插入图片描述

    不难发现P越小,吞吐量越大,传输效率越高。这是由于发送出的帧发生冲突的可能性降低了,但同样的,P变小牺牲了等待时间,一个帧发送所经历的等待时间变长

    冲突检测方法

    比较发送信号(A→B)与回复信号(A⬅B)的能量或脉冲
    宽度变化

    最大冲突检测时间(冲突窗口):两个最远距离站点间的传输时间为t,则网络的最大冲突检测时间为2t

    冲突检测的要求

    1. 时隙宽度 = 最大冲突检测时间(保证在一个时隙内能够检测到最远距离发生的冲突)

    2. 发送有效帧的时间 >= 最大冲突检测时间(防止因在发生冲突时已完成短帧发送而造成的异常情况)


    以太网概述

    以太网发展史

    • 1973 Robert Metcalfe及其同事设计了以太网雏形(施乐公司)
    • 1980 DIX发布最早的以太网标准,开放标准
    • 1985 IEEE802.3对以太网作了小的修改,基本一致,兼容
    • 1995 IEEE宣布了100Mbps以太网标准
    • 1998 吉比特以太网标准(1000M) 1999
    • 2002 IEEE通过了10Gbps以太网标准

    以太网分为

    • 经典以太网(3M~10Mbps,不再使用)
    • 交换式以太网(10M,100M,1G,广泛使用)

    IEEE以太网命名规则

    10Base2:(IEEE 802.3a)

    10:表示10Mbps

    Base:表示以太网采用线路编码这种基带传输的方式

    2:表示传输距离,单位是百米(四舍五入)

    10Base-TX(IEEE 802.3X)

    -T:表示铜制非屏蔽双绞线

    -F:表示光缆

    名称电缆最大区间/长度节点数/段优点接口
    10Base5粗缆(采用总线拓扑)500m100用于主干AUI
    10Base2细缆(采用总线拓扑)200m(185)30廉价BNC
    10Base-T双绞线(采用星型拓扑)100m1024易于维护RJ-45
    10Base-F光纤2km1024用于楼间ST

    10Base-T拓扑结构

    在这里插入图片描述

    • 物理连接是星型/扩展星型结构
    • 逻辑上是总线结构(站点争用总线)

    10Base-T相较于10Base2和10Base5的优点

    1. 安装成本大大降低
    2. 即插即用,组网灵活,增删方便(采用了RJ-45)
    3. 采用星型结构,故障便于隔离
    4. 适合大批量制造
    5. 具有开放式标准的互操作能力

    问题:

    多个用户共享一条10M速率的信道

    10Base-T以太网采用曼彻斯特编码

    • 1:高电压到低电压
    • 0:低电压到高电压
    • 电压值:

      +0.85 volt: high signal

      -0.85 volt: low signal

      0 volt: DC value

    所以要求比特率达到b = 10 Mbps

    就需要波特率B = 20 MHz(信号的变化频率)

    IEEE802.3协议描述了运行在各种介质上1 Mb/s~10 Mb/s的1-持续CSMA/CD协议的局域网标准。

    很多人对以太网和IEEE802.3不加区分,但二者确有差别(如帧格式)。

    在这里插入图片描述

    以太网采用介质访问控制技术(CSMA/CD)

    CSMA/CD协议遵守先听后发,边发边听的原则,并且在发生冲突后返回等待一段随机时间,这段随机时间的确定,利用到了“二进制指数回退算法

    二进制指数回退算法

    1. 冲突检测到后,时间被分散成离散的时隙
    2. 时隙长度等于信号在介质上来回传输的时间,在以太网中一般是51.2μs
    3. 一般地,第i次冲突后,随机时间可从以下事件中选择

    ( 0   2 i − 1 ) ∗ 51.2 μ s (0~2^i-1)*51.2μs (0 2i1)51.2μs
    当冲突超过16次,一般直接放弃发送

    提高负载方法

    10Base以太网逐渐不能满足人的需求,所以需要考虑如何提升负载

    • 提速到100M
    • 采用全双工代替半双工,提速1倍
    • 采用交换式网络,用交换机取代集线器

    快速以太网(100M以太网)

    标准:IEEE802.3u

    属于改进的10M以太网

    要求:与10M以太网兼容

    基本思想:

    保留原有帧格式,接口和过程规则,将比特时间(发送1比特所需时间)由100ns降至10ns,电缆长度也由2500m降低至250m

    编码方式也发生了改变,由曼彻斯特编码变为4B/5B编码方式

    4B/5B编码表

    在这里插入图片描述

    优点:

    • 效率高
    • 易于实现
    • 容易电压平衡

    千兆位以太网(吉比特以太网,GE)

    标准:IEEE802.3z

    与现有的10M/100M以太网完美兼容

    主要工作在全双工模式,工作在半双工模式下时,需要使用CSMA/CD技术,可能带来传输距离过短的问题(适用帧串/帧扩充方法来解决)

    FDDI,ATM等技术失败原因

    • 太复杂,很难到桌面
    • 部署复杂,成本高昂,交换机端口少
    • 受快速以太网的冲击

    以太网优点

    1. 简易性和灵活性
    2. 易于维护
    3. 支持TCP/IP协议,容易互联
    4. 善于借鉴(4B/5B…)

    以太网帧格式

    在这里插入图片描述

    以太网和IEEE802.3之间并不是完全相同的,以太网对应OSI模型中的下两层(物理层数据链路层),而IEEE 802.3只对应于OSI模型中的下1.5层(物理层,逻辑链路控制子层)

    二者的区别主要存在于帧格式上

    帧格式

    帧类型前导码(先导码)帧起始字节目的地址源地址长度/类型数据校验和
    IEEE 802.3帧格式62bit(1010…)2bit(11)6byte6byte2byte(长度)46~1500byte4byte-循环冗余校验
    DIX以太网帧格式62bit(1010…)2bit(10)6byte6byte2byte(类型)46~1500byte4byte-循环冗余校验

    第一个字段—前导码+帧起始字段

    大小为8byte(前导码62bit,帧起始字段2bit)。帧起始字段用来表明一个帧的开始,在IEEE 802.3中这个字段是用11表示的,但在以太网中才用10表示

    第二,三个字段—目的地址,源地址

    每个字段6byte,48bit。表示的地址都是物理地址(MAC地址)

    在这里插入图片描述

    总共存在约 7 ∗ 1 0 13 7*10^{13} 71013(七万亿个),暂时不存在枯竭的风险

    MAC地址表示形式=组织/机构ID(Manufacture ID 24bit)+NIC ID(自定义 24bit)

    前后各24bit,由于都是用十六进制表示的,所以一个典型的物理地址表示如下:(三种格式均正确)

    00 − 60 − 8 C − 01 − 28 − 12 00-60-8C-01-28-12 00608C012812
    00 : 60 : 8 C : 01 : 28 : 12 00:60:8C:01:28:12 00:60:8C:01:28:12
    00.60.8 C . 01.28.12 00.60.8C.01.28.12 00.60.8C.01.28.12

    其中前6位由IEEE分配表示的是一个企业或组织,例如:

    • 3Com 00-20-AF
    • IBM 08-00-5A
    • Cisco 00-00-0c

    后六位是由企业自行分配的

    物理地址具有全球唯一性的特点,也就是说没有两台电脑可能具有相同的MAC地址,MAC地址烧录在ROM中,当计算机启动时,会从ROM拷贝到RAM中

    目的MAC地址定位目的机

    在这里插入图片描述

    为了维护MAC地址的全球唯一性IEEE 要求厂商遵守两条简单的规定:

    • 必须使用该供应商分配的OUI作为前3个字节
    • OUI相同的所有MAC地址的最后3个字节必须分配唯一的值

    第四个字段—长度/类型字段

    大小为2byte。

    在IEEE 802.3中表示帧的长度字段(不包括前导码),长度最短不能小于64字节,最长不能超过1518各字节(由于以前内存十分昂贵,而帧中的数据要占用内存,如果过大对数据的要求会越高)

    在DIX以太网协议中表示类型字段,由于以太网对应整个下两层直接与上层的网络层交流,所以第四字段用于存放网络层类型

    如何区分第四字段是类型还是长度?

    (如何区分当前帧是以太帧还是IEEE 802.3帧?)

    检查数值大小:

    • 小于等于1536(十六进制下<=0x600):表示长度字段(802.3帧)
    • 大于1536(十六进制下>0x600):表示类型字段(以太帧)

    第五个字段—数据字段

    长度最小为46字节(因为帧头,帧尾长度14字节,为保证帧的长度大于64字节,多以数据字段长度最少46字节)小于46字节就进行填充。

    内含LLC层(逻辑链路子层)的数据

    第六个字段—校验字段

    大小4byte,32bit。

    以太帧采用CRC循环冗余校验,校验的范围是目的/源地址,长度字段,LLC数据字段等

    为什么最小帧的长度是64byte

    以太网(802.3)采用CSMA/CD协议

    协议要求为保证正确检查是否发生冲突

    最 短 帧 的 发 送 时 间 ≥ 争 用 时 隙 2 t 最短帧的发送时间\ge争用时隙2t 2t

    以太网规定,在10Mbps局域网中,时隙2t=51.2μs

    所以最短帧的长度:

    最 短 帧 长 度 = 10 M b p s ∗ 51.2 μ s 8 = 64 b y t e 最短帧长度=\frac{10Mbps*51.2μs}{8}=64byte =810Mbps51.2μs=64byte

    二层交换的基本原理

    在不同的区域,地点,都存在着很多的LAN(局域网),我们将这些LAN连接起来就利用到了重要的“网桥”

    网桥工作在DLL层(数据链路层),通过检查MAC地址做出转发帧的决策,因为工作在DLL层,所以不会检查网络层情况所以,IPv4, IPv6, AppleTalk, ATM, IPX, 和OSI 分组均可穿越网桥。

    交换机是网桥的现代名称,二者之间不做区别

    二层交换

    通过网桥实现

    在这里插入图片描述

    网桥可以将两种不同格式的局域网相连接,例如802.11和802.3虽然是两个不同类型的LAN,仍然可以通过网桥连接起来,网桥会在内部处理两个LAN的区别,使之可以正常通信

    • 帧格式不同—进行重新封装
    • 不同的数据传输速率—从快的LAN向慢的传递时进行缓存
    • 不同的最大帧长度—进行切割 (例如, 802.3 1526 字节,802.11 2346 字节)
    • 不同的安全策略,不同的服务质量信息—在传递过程中,如果以访不支持对应的安全策略或服务质量信息的话就会消去对应信息

    透明的网桥(transparent bridges)

    • 通过透明的网桥可以将多个LAN连接起来,同时硬件和软件不需要做任何形式的变化,所以称其为“透明”
    • 透明网桥工作在混杂模式,接收所有与之相连的LAN的帧
    • 当一个帧到达网桥,它必须要做出决策,丢弃还是转发,如果转发还要知道向哪个LAN转发
    • 决策通过网桥内部的一张地址表实现,通过地址表确定丢弃还是转发

    如何维护网桥内部的地址转发表

    • 初始时,这张转发表是空表
    • 利用扩散算法(泛洪算法,flooding algorithm),当网桥不知道目的地址在何处时,将会把这个帧向传入LAN以外的所有LAN转发(广播
    • 逆向学习,网桥从到达帧的源地址认识到源地址对应的那台机是在帧来的那条LAN上,所以,把它写入MAC地址表(例如PC1发送一个帧从LAN1向PC6传递,到达网桥处时,网桥并不认识PC6,但它直到这个帧是从LAN1来的,并且这个帧的源地址是XX-XX-XX-XX-XX-XX,就会将这两个数据写入网桥的转发表中,再遇到要转发给XX-XX-XX-XX-XX-XX的帧,就只向LAN1转发)

    网络的拓扑结构在不断变化,网桥如何适应这种变化

    1. 任何时候,在向网桥的转发表中写入数据的时候,都要同时打下时戳(表明数据在何时写入)
    2. 当一个到达的帧它的到达地址在表中已经有记录时,它会再次更新这个时戳
    3. 网桥周期性的扫描整张表,删去那些时戳已经过期的记录

    这样保证了网桥的转发表中的数据一直都是最新且活跃的那些工作站的信息(如果一个工作站十分活跃的接收帧却从来不发送,那网桥中同样不会有它的信息)

    网桥工作原理

    当一个帧到达网桥时,网桥启动如下算法:

    1. 如果源LAN和目的LAN相同,则丢弃该帧(filtering,过滤或丢弃)
    2. 如果源LAN和目的LAN不同,则转发该帧(forwarding)
    3. 如果目的LAN不存在于转发表中,则广播该帧(flooding,泛洪广播)

    每当帧到达,上述算法都将被执行一遍

    有些专用的 VLSI芯片可以在几微秒内完成查找和更新表项的动作

    网桥工作示例:

    初始时,整个结构状态:

    在这里插入图片描述

    此时两个网桥的转发表都是初始状态为空:

    网桥1

    MACPort

    网桥2

    MACPort

    现在,要从图上的源地址(AA-AA-AA-AA-AA-AA)向目的地址(BB-BB-BB-BB-BB-BB)发送数据帧,帧从源地址出发到达LAN1,然后到达网桥1,网桥1发现源地址与目的地址不同,并且目的地址信息未知,所以进行广播,然后网桥1进行逆向学习,它发现这个帧的源地址是(AA-AA-AA-AA-AA-AA),没有在转发表中,并且它是从LAN1所在的端口(这里记作A1端口)来的,所以将这个地址和端口写入到转发表中。

    网桥1

    MACPort
    AA-AA-AA-AA-AA-AAA1

    非目的地址收到帧后都选择忽略,当帧到达网桥2时,进行同样算法继续广播,同时进行逆向学习(将网桥1所在端口记作B1)将数据写入转发表中

    网桥2

    MACPort
    AA-AA-AA-AA-AA-AAB1

    最终数据帧成功从LAN4找到目的地址(BB-BB-BB-BB-BB-BB)

    在这里插入图片描述

    这时,假设目的地址返回一个确认帧,数据从图上目的地址出发,通过LAN4到达网桥2,到达网桥2时,运行算法查找目的地址,发现此时目的地址就是原来的源地址(AA-AA-AA-AA-AA-AA),所以此时网桥2就会进行转发,而不再广播,只将这个帧转发给网桥1所在的B1端口。同时会进行逆向学习.

    网桥2

    MACPort
    AA-AA-AA-AA-AA-AAB1
    BB-BB-BB-BB-BB-BBB2

    到达网桥1后同样的运行算法并且发现了AA-AA-AA-AA-AA-AA在准发表中对应的端口是LAN1所在的A1端口,所以它只对LAN1进行转发,并且进行逆向学习

    网桥1

    MACPort
    AA-AA-AA-AA-AA-AAA1
    BB-BB-BB-BB-BB-BBA2

    最终成功在LAN1上找到了AA-AA-AA-AA-AA-AA

    在这里插入图片描述

    有了网桥/交换机,各个LAN之间的通信可以互不影响,同时进行,这个过程也就分割了冲突域,提高了性能

    网桥与中继器比较

    header 1header 2
    row 1 col 1row 1 col 2
    row 2 col 1row 2 col 2
    功能网桥中继器
    再生信号YesYes
    连接采用不同MAC协议的网段YesNo
    隔离冲突域YesNo
    根据帧头的物理地址转发帧YesNo
    丢弃损坏帧YesNo

    生成树协议(STP)

    (Spanning Tree Protocol)

    为了数据传输的可靠性,我们经常采用冗余结构来搭建网桥,即一个LAN可能连着多个网桥,如下图所示,但这样同样带来了一些问题

    在这里插入图片描述

    冗余结构导致了环结构的产生

    问题1:多帧传送

    例如PC1向PC3传输数据,从LAN1上可以直接到达,从LAN1到网桥1再到LAN2再到网桥2最后到PC3也可以到达,这就导致了会有多个相同的帧(或帧的副本)传送到PC3,造成多帧传送问题

    问题2:广播风暴

    在局域网中经常会发送广播,例如PC1向PC2发送帧,帧到达网桥1进行广播到达网桥2,到达网桥2后,进行广播又可以回到网桥1,如此循环往复就会形成广播风暴。严重情况下可使网络彻底瘫痪

    MAC地址库不稳定

    PC1发出帧(MAC地址为A),A从LAN1通过端口port1到达网桥1,将这组信息(A,port1)写入转发表中。

    同样的,A还能通过port2端口到达网桥2。在经过循环从LAN2到达网桥1的port3,所以更新这组数据为(A,port3).导致交换机的逆向学习不断发生改变

    导致帧的转发方向具有不确定性


    解决方案:生成树协议

    Radia perlman提出了生成树算法,利用生成树的定义产生一棵无环的树

    IEEE将这个协议标准化为IEEE 802.1D,即STP

    STP运作方式:

    • 每个网络一个根网桥
    • 每个网桥一个根端口
    • 每网段一个指定端口
    • 非指定端口不被使用

    在这里插入图片描述

    生成树算法生成一棵逻辑上无回路的树,即生成树,但不能保证这棵生成树是最优的

    非指定端口虽然不参与数据帧的传送,但它会继续监听树的工作报文,一旦树中某些工作端口失效后,非工作端口会被重新启用,形成新的生成树


    虚拟局域网VLAN

    经典LAN:物理LAN,地理位置靠近的工作站组成LAN

    VLAN:虚拟局域网,一组逻辑上的设备或用户,不需要考虑地理位置

    同一个VLAN用户中的通信和在LAN中是一样的,在一个VLAN中的广播只有VLAN的成员能够听到,而不会传到其他VLAN中去,从而避免了不必要的广播风暴产生。若没有路由,不同的VLAN之间不能够相互通信,进一步提高了不同工作组之间信息的安全性。网络管理员可以通过配置VLAN之间的路由来全面管理网络内部不同工作组之间的信息互访。

    VLAN的实现方式

    1. 基于端口
    2. 基于MAC地址
    3. 基于三层协议

    基于端口的VLAN在交换机内部有一张VLAN成员配置表,由此了解某个端口属于哪个VLAN

    当一个帧在LAN中定位目标机(MAC寻址)时,帧在整个VLAN中穿行,类似下图,从源地址出发,发送给所有相同类型的目标机

    在这里插入图片描述

    如上图情况所示,当一个VLAN的成员跨越了交换机时,帧在传输到交换机1时会进行一些处理,向帧中写入数据VLAN ID,表明这是该条VLAN上传送的帧,这样这个帧就会顺利到达交换机2,并在交换机2处重新进行格式转换,消去VLAN ID等信息,最终到达目标机的帧就与发出帧完全一致了

    上述描述的就是IEEE802.1Q(一种帧标记法)

    • 帧在经过干线trunk(图中两个交换机之间的连线)时,会打上标签
    • 标签中有10bit用来表示VLAN ID
    • 到达干线终点时会拆除标签

    一个VLAN就是一个广播域(广播域就是指网络中所有能接收到同样广播消息的设备的集合。)

    有了VLAN,可以使用二层交换机实现广播域的分割


    二层设备

    二层(数据链路层设备)主要有

    • 网卡
    • 网桥
    • 交换机

    NIC网卡(Network Interface Card)

    主要功能:

    网卡的主要功能包括命名、成帧、介质访问控制,再生信号等。

    为主机提供介质访问

    MAC地址就烧在网卡的ROM中

    • Logical link control (LLC): 和上层通信
    • Naming: 提供一个独特的 MAC 地址标识符
    • Framing: 封装过程的一部分,为传输比特流打包
    • Media Access Control (MAC): 为访问共享介质提供访问策略
    • Signaling:创建信号和与介质的接口

    网卡同时运作在第一层和第二层

    主要是第二层的设备

    • 在计算机中与上层通信
    • Logical Link Control (LLC)
    • 烧入芯片的MAC 地址
    • 封装数据城帧
    • 提供介质访问

    也是第一层设备

    • 创建信号和与介质的接口
    • 内建转发器( transceiver)

    网卡分类:

    • 按照计算机类型分类:笔记本,台式机
    • 按照网络类型分类:Ethernet, Token Ring, FDDI
    • 按照传输介质分类:Twisted pair, coax, fiber
    • 按照系统总线类型分类:PCI, ISA

    网桥

    连接不同的LAN网段

    通过过滤部分交通流量(以网段分流交通,基于 MAC 地址过滤流量),减少冲突的机会,改善网络性能。

    交换机

    LAN 交换机是多端口网桥

    连接 LAN 网段(比网桥更高的交换速度)

    使用一张 MAC 表,来决定一帧转发的端口

    交换机常被用来替换集线器(hub),用作以太网星型拓扑中心,以改善现有网络性能

    增加带宽

    支持新的功能,如VLAN

    基本的工作原理与网桥一模一样

    微分段

    交换机利用微分段(LAN被交换机分割开的网段在冲突域中产生无冲突域,就是微分段)的技术(交换机的每个端口只接一个工作站)创建无冲突域

    交换机的交换模式

    存储转发:

    交换机将整个帧接收下来,计算其校验和,确保没有发生错误,再按照MAC地址转发表的指示进行转发

    延迟大,出错率小

    直通交换(贯穿交换),虫孔交换:

    交换机读取到帧的目的地址后,就直接将其进行转发,不再在接收整个帧后再处理。

    延迟小,出错率高

    无碎片交换(无分片交换):

    交换机再读取帧的字节数达到64字节后才开始转发,类似于前两种交换方式的折中,避免了碎片帧的转发(冲突的碎片帧,短帧,残帧往往小于64字节)

    延迟和出错率达到了相当的平衡

    展开全文
  • 概述:多路访问链路(广播链路)采用共享介质连接所有站点。发送站点通过广播方式发送数据并占用整个共享介质的带宽。...这种问题是点到点链路没有的,因此,需要重新考虑数据链路层的功能设计。OS...
  • IEEE 802.2逻辑链路控制协议

    千次阅读 2012-12-24 17:24:15
    逻辑链路控制(Logic Link Control,LLC)是一种IEEE 802.2 LAN协议,规定了局域网参考模型中数据链路层中LLC子层的实现。IEEE 802.2 LLC应用于IEEE802.3(以太网)和 IEEE802.5(令牌环)LAN,以实现如下功能: ...
  • MAC子层的主要功能包括数据帧的封装/卸装,帧的寻址和识别,帧的接收与发送,链路的管理,帧的差 错控制等。MAC子层的存在屏蔽了不同物理链路种类的差异性; 在MAC子层的诸多功能中,非常重要的一项功能是仲裁介质...
  • 3、介质访问控制方法 IEEE802.3标准提供了介质访问控制子层的功能说明,有两个主要的功能:数据封装(发送和接收),完成成帧(帧定界、帧同步)、编址(源和目的地址处理)、差错检测(物理介质传输差错的检测);...
  • 数据链路层的MAC子层和LLC子层

    千次阅读 2020-07-17 10:15:32
    MAC子层的主要功能包括数据帧的封装/卸装,帧的寻址和识别,帧的接收与发送,链路的管理,帧的差错控制等。MAC子层的存在屏蔽了不同物理链路种类的差异性; 在MAC子层的诸多功能中,非常重要的一项功能是仲裁介质的...
  • 一、 局域网、 二、 局域网 拓扑结构、 三、 局域网 传输介质、 四、 局域网 介质访问控制方法、 五、 局域网 分类、 六、 IEEE 802 标准、 六、 数据链路层 LLC、MAC 子层
  • 逻辑链路控制与适配协议通常简称为L2CAP(Logical Link Control and Adaptation Protocol),它向上连接应用,向下连接控制器,发挥主机与控制器之间的适配器的作用,使上层应用操作无需关心控制器的数据处理...
  • LLC 逻辑链路控制

    千次阅读 2016-09-26 13:04:00
    LLC 协 议 4.2.1 LLC帧格式  LLC协议定义了LLC之间通信的帧格式,参见图4.3。   图4.3 LLC帧格式 ...LLC帧格式中各个字段的含义如下: ... ① 服务访问点(SAP)地址:SAP...为此,LLC协议定义了一种逻辑地址SA...
  • Wi-Fi 链路 - LLC(逻辑链路层

    千次阅读 2019-10-11 15:45:26
    IEEE 802.11 LLC LLC(Logic Link Control Sub Layer...IEEE 802.11是以 IEEE 802.2的逻辑链路控制来封装上层协议 当有线网络 Ethernet帧需要在Wi-Fi中传输时,首先转换为LLC帧,增加4个字段(网络访问协议 ...
  • LLC逻辑链路控制

    千次阅读 2013-08-29 19:00:08
    转载:...LLC是Logical Link Control的缩写,意为:逻辑链路控制。  解封示意图 数据要通过网络进行传输,要从高层一的向下传送,如果
  • 物理一个基本的任务就是将mac帧送达目的地,这在传统的有线以太网中,由于交换机有端口缓存,交换机与主机之间是双工模式,以及不同虚拟链路相互没有影响,基本情况下很少存在冲突,但是换到wifi的无
  • 以太网将数据链路层的功能划分到了两个不同的子层逻辑链路控制 (LLC) 子层和介质访问控制 (MAC) 子层。OSI 模型中所述的数据链路层功能被分配到了 LLC 和 MAC 子层。这些子层的使用极大地促进了不同终端设备之间的...
  • 目录   一、概述 1、多路访问链路 2、介质访问控制子层的由来 二、介质访问控制子层...1、逻辑链路控制子层 2、以太网(Ethernet) 3、世界上最早的无线电计算机通信网:ALOHA 4、CSMA(Carrier Sense Multip...
  • 计算机网络知识点总结

    千次阅读 2017-08-24 22:52:34
    网络体系结构 SAP ...(访问访问点),OSI参考模型中上协议实体与下层协议实体之间的逻辑接口叫作服务...SAP位于N和N+1逻辑交界面上,是N实体向N+1实体提供服务的地方,或者N+1实体请求N服务的地
  • 数据链路(2-6分) 1.功能: 2.组帧: 3.差错控制:检错编码;纠错编码 4.流量控制和可控传输机制(滑动窗口): 5.介质访问控制:信道划分 随机访问(CSMA CSMA/CD(宽带)CSMA /CA(WiFi)协议) 轮询访问...
  • 第4章 介质访问控制子层 4.1 局域网技术的发展与演变 介质控制访问(MAC)是所有“共享介质”类型的局域网必须解决的共性问题 共享介质:作为总线连接多台计算机的同轴电缆 多路访问/多路存取:多个主机通过一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,836
精华内容 9,934
关键字:

逻辑链路控制子层