计算机网络笔记Ⅲ

计算机网络笔记Ⅲ

数据链路层

数据链路层服务

​ 数据链路层。术语:主机和路由器称为结点,连接相邻结点的通信信道称为链路,链路分为物理链路数据链路,物理链路是物理层,数据链路是数据层面(物理链路之上),物理链路如有线链路,无线链路,局域网,链路层(第2层)数据分组称为数据帧,用来封装网络层数据报。

​ 数据链路层负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传送数据报。

​ 数据链路层提供的服务:1.组帧,封装数据报构成数据帧,加首部和尾部,帧同步(在首部和尾部加入特殊比特串),2.链路接入,如果是共享介质,需要解决信道接入,链路层寻址使用MAC地址,用于标识帧的源和目的,不同于IP地址,3.相邻结点间可靠交付,根据不同的链路采用的交付方式不同,如在低误码率的有线链路上很少采用(如光纤,某些双绞线等),在误码率高的无线链路上采用可靠交付,4.流量控制,协调相邻的发送结点和接收,5.差错检测,接收端检测到差错时可能通知发送端重传或者直接丢弃帧,6.差错纠正,接收端直接纠正比特差错,7.全双工和半双工通信控制,全双工是链路两端结点同时双向传输,半双工是链路两端结点交替双向传输。上述服务不一定所有链路层都提供。

​ 链路层的具体实现。每个主机或路由器都会实现,链路层在“适配器”(即网络接口卡-NIC)中实现,或者在一个芯片上实现。结构如下图。

image-20191203114929448

​ 链路层多是网卡之间的通信。发送端将数据报封装成帧,增加差错检测比特,实现可靠数据传输和流量控制等,接收方检测差错,实现可靠数据传输和流量控制等,提取数据报,交付上层协议实体。

image-20191203115151006

差错编码

​ 差错编码的基本原理:在数据基础上增加一些冗余信息,建立起了数据位与位之间原本不存在的关联关系,作为编码的结果一起发送给接收端,接收端收到之后判断关联关系是否存在。形式化描述如下所示,其中有$D\rightarrow DR$,其中$R$为差错检测与纠正比特(冗余比特)。

image-20191203115540406

​ 差错编码可以分为分组码和卷积码,计算机中多使用分组码。分组码又可分为线性分组码和非线性分组码,线性码表示R建立的比特位之间的关系是线性关系,计算机网络中更多用的是线性分组码。R称为冗余比特,在通信领域中R称为监督位。差错编码不能保证100%可靠。差错码可分为检错码与纠错码,对于检错码,如果编码集的汉明距离$d_s=r+1$,则该差错编码可以检测r位的差错,汉明距离是两个码字之间对应比特位不同的位数,编码集的汉明距离是编码集中任意两个码字的汉明距离的最小值。对于纠错码,如果编码集的汉明距离$d_s=2r+1$,则该差错编码可以纠正r位的差错,纠错码基本的原则是将一个无效的码字纠错为距离其最近的有效码字(基于概率最大化原则)。

​ 奇偶校验码。1比特奇偶校验在原数据的基础上增加一个校验位,如果是奇校验,则加上校验位之后的1的个数应该为奇数个,偶校验则是偶数个。奇校验可以实现检测所有错了奇数个位的差错所有偶数位的检测不出来,即50%,但是编码效率高。二维奇偶校验,对多个二进制数摆成矩阵,对每行每列都进行奇偶校验,可以检测奇数位差错和部分偶数位差错(偶数个差错在不同的行,列),也可以纠正同一行/列的奇数位错(翻转交叉位)。

​ Internet校验和。即checksum(UDP,TCP,IP中使用的,IP只校验头部)。接收方按照同样的算法计算出来如果是全0则表示完好。

循环冗余校验码码(CRC)。检错能力更强大的差错编码。将数据比特,D,视为一个二进制数。选择一个$r+1$位的比特模式(生成比特模式),G。目标:选择r位的CRC比特,R,满足$<D,R>$刚好可以被G整除(模2),其中$<D,R>$表示把D和R连成一个数,接收端检错只需要利用G除$<D,R>$,余式如果全0则无措,否则有错。可以检测所有突发长度小于$r+1$位的差错。广泛应用于实际网络(以太网,802.11,WiFi,ATM)。R的推导如下,注意二进制的除法中原来的减法现在是异或。

image-20191203151933758

多路访问(MAC)协议

​ 有两类链路:1.点对点链路,如拨号接入的PPP,以太网交换机与主机间的点对点链路,2.广播链路(共享介质),如早期的总线以太网,HFC的上行链路,802.11无线局域网。

​ MAC协议解决的场景是单一共享广播信道,即两个或两个以上结点同时传输时会产生干扰,也称为冲突,会导致结点同时接收到两个或者多个信号,导致接收失败。MAC协议:1.采用分布式算法决定结点如何共享信道,2.基于信道本身,通信信道共享协调信息,即无带外信道用于协调。

​ 一个理想的MAC协议。给定速率为R bps的广播信道。期望:1.当只有一个结希望传输数据时,它可以以速度R发送,2.当有M个结点期望发送数据时,每个结点平均发送数据的平均速率是R/M,3.完全分散控制,无需特定结点协调,无需时间,时隙同步,4.简单。

​ MAC协议分类:1.信道划分MAC协议,使用多路复用技术,TDMA,FDMA,CDMA,WDMA,多址技术,2.随机访问MAC协议,信道不划分,允许冲突,采用了冲突“恢复”机制,3.轮转MAC协议,结点轮流使用信道。

​ 信道划分MAC协议TDMA,​”周期性“接入信道,每个站点在每个周期,占用固定长度的时隙,所有结点都发一个帧称为复用帧。

image-20191203220018531

​ 信道划分MAC协议FDMA,信道频谱划分为若干频带,每个站点分配一个固定的频带,无传输频带空闲。信道划分MAC协议,如果网络负载比较重则信道利用率高,且公平,但是如果比较轻则信道利用率较低。不会产生冲突

​ 随机访问MAC协议。当结点要发送分组时,利用信道全部数据速率R发送分组,没有事先的结点间协调,有可能产生冲突(两个或多个结点同时传输)。因此随机访问MAC协议需要定义:1.如何检测冲突,2.如何从冲突中恢复,比如通过延迟重传。典型的随机访问MAC协议:1.时隙(sloted)ALOHA协议,2.ALOHA,3.CSMA,CSMA/CD,CSMA/CA(结合802.11)。

​ 时隙ALOHA协议。协议假设:所有帧大小相同,时间被划分为等长的时隙(每个时隙可以传输1个帧),结点只能在时隙开始时刻发送帧,结点间时钟同步,如果2个或2个以上结点在同一时隙发送帧,结点即检测到冲突。具体运行:1.当结点有新的帧时,在下一个时隙(slot)发送,如果无冲突该结点可以在下一个时隙继续发送新的帧,2.如果发生冲突,该结点在下一个时隙以概率p重传该帧,直至成功。优点是单个结点活动时,可以连续以信道全部速率传输数据,并且高度分散化,只需同步时隙,简单。缺点:冲突,浪费时隙,空闲时隙,结点也许能以远小于分组传输时间检测到冲突(即传输数据帧的时候有机制发现已经有冲突则同一时隙后面的时间不必要再发送了),时钟同步。最大的问题是效率。分析如下图所示。

image-20191203222022789

​ 非时隙(纯)Aloha协议:更加简单,无需同步。每当有新的帧生成时立即发送,冲突的可能性增大,因此纯ALOHA协议效率比时隙ALOHA协议效率低。具体推导如下。

image-20191203222409840

载波监听多路访问协议CSMA协议。发送数据帧之前,监听信道(载波),如果空闲则发送完整帧,如果信道忙则推迟发送,根据推迟策略可以分为:1. 1-坚持CSMA,一直监听信道有空闲马上发送,2.非坚持CSMA,随机等待一段时间再监听,3.P-坚持CSMA,以概率p坚持监听信道,以概率1-p随机等待一段时间再监听。CSMA冲突可能仍然发生,因为一般的CSMA协议只要发送数据帧了就一定会发完,由于物理距离有可能其他结点还没有收到信道已被占用的消息而产生冲突,而继续发送冲突帧浪费信道资源。

​ CSMA/CD协议(CSMA with Collision Detection)。即CSMA协议中如果检测到冲突则停止发送当前的冲突帧。CSMA/CD短时间内可以检测到冲突,冲突后传输终止,减少信道浪费。冲突检测的实现:有线局域网易于实现,测量信道强度,比较发射信号与接收信号,无线局域网很难实现,接收信号强度淹没在本地发射信号强度下,因此在无线网络中很少使用CSMA/CD。CSMA/CD,”边发边听,不发不听“。CSMA/CD协议必须有如下(不)等式才会保证效率。其中$R$ bps是网络带宽,$L_{min}$ bits是数据帧最小长度,$V$(m/s)是信号传播速度。
$$
L_{min}/R=2d_{max}/V\
L_{min}/R=RTT_{max}
$$
​ CSMA/CD效率。CSMA/CD协议的效率比ALOHA好很多。令$T_{prop}$表示LAN中2个结点间的最大传播延迟,$t_{trans}$为最长帧传输延迟。则效率如下所示。当$t_{prop}$趋近0或者$t_{trans}$趋近于$\infty$时,效率趋近于1。远优于ALOHA,并且简单,分散。
$$
效率=\frac{1}{1+5t_{prop}/t_{trans}}
$$
​ 总结信道划分MAC协议,随机访问MAC协议和轮转访问MAC协议。

image-20191203225846844

​ 轮转访问MAC协议,轮询(polling)协议。主节点轮流“邀请”从属结点发送数据,典型应用:“哑”从属设备。问题是轮询开销,等待延迟,单点故障。

​ 轮转访问MAC协议,令牌传递(token passing)协议。控制令牌一次从一个结点传递到下一个结点,令牌就是特殊帧。网络中有且只有一个令牌,很多令牌网络都是环形网络。问题是:令牌开销,等待延迟,单点故障。

​ MAC协议总结。如下图所示。

image-20191203230930309

ARP协议

​ MAC地址。32位IP地址用于标识接口的网络层地址,用于标识网络层(第3层)分组,支持分组转发。MAC地址(或称LAN地址,物理地址,以太网地址),用于局域网内标识一个帧从哪个接口发出,到达哪个物理相连的其他接口,48位MAC地址(用于大部分LANs),固化在网卡的ROM中,有时也可以软件设置。常见的形式是1A-2F-BB-76-09-AD(16进制)。局域网中的每块网卡都有一个唯一的MAC地址。MAC地址由IEEE统一管理与分配,网卡生产商购买MAC地址空间(前24比特)。类比MAC地址:身份证号,IP地址:邮政地址。MAC地址是“平面”地址,可“携带”,可以从一个LAN移到另一个LAN。IP地址是层次地址,不可“携带”,IP地址依赖于结点连接到哪个子网。

​ ARP地址解析协议。LAN中的每个IP结点(主机,路由器)维护ARP表,存储某些LAN结点的IP/MAC地址映射关系<IP地址;MAC地址;TTL>,TTL是指经过这个时间以后该映射关系会被遗弃(典型值为20min)。ARP协议的过程:A想要给同一局域网内的B发送数据,如果B的MAC地址不在A的ARP表中,A广播ARP查询分组,其中包含B的IP地址(广播中的MAC地址为FF-FF-FF-FF-FF-FF),LAN中所有结点都会接收ARP查询,B接收ARP查询分组,IP地址匹配成功,向A应答B的MAC地址,利用单播帧向A发送应答,A在其ARP表中,缓存B的IP-MAC地址对,直至超时,超时后,再次刷新。ARP是“即插即用”协议。结点自主创建ARP表,无需干预。

​ 如果从寻址是从一个LAN路由至另一个LAN,如下图所示,关注寻址:IP地址(数据报中)和MAC地址(帧中)。假设A知道B的IP地址,假设A知道第一跳路由器R(左)接口的IP地址和MAC地址,A构造IP数据报,帧从A发送至R,R创建链路层帧,其中源MAC地址是R(右)接口的MAC地址,目的MAC地址是B的MAC地址,封装A到B的IP数据报。整个过程是A先判断B不是在同一子网内,因此发送给默认网关,然后路由至B所在的子网并发送给B。

image-20191204103003918

以太网

​ 具有“统治地位“的有线LAN技术。优势有造价低廉,应用最广泛的LAN技术,比令牌局域网和ATM等,简单,便宜,满足网络速率需要(10Mbps~10Gbps)。

​ 以太网物理拓扑:1.总线,在上世界90年代中期前流行,所有的结点在同一冲突域(可能彼此冲突,CSMA/CD可以检测到的范围也是冲突域),2.星型拓扑,目前主流网络拓扑,有中心交换机,每个结点一个单独冲突域(结点间彼此不冲突)

image-20191204104502833

​ 以太网提供不可靠,无连接服务。无连接即发送帧的网卡与接口帧的网卡间没有”握手“过程。不可靠即接收网卡不向发送网卡进行确认。对差错帧直接丢弃,丢弃帧中的数据恢复依靠高层协议,否则,发生数据丢失。

​ 以太网使用二进制指数退避算法的CSMA/CD。算法如下图所示。堵塞信号用于加强网络信道中的冲突,让其他结点也都尽快发现冲突。注意下图应该为$n=Min(m,10)$。注意如果连续发生了16次冲突,则NIC不再尝试并向上层报告。

image-20191204105326567

​ 以太网帧结构。如下图所示,发送端网卡将IP数据报(或其他网络层协议分组)封装到以太网帧中。前导码的前7个字节都是10101010,第8个字节是10101011,用于发送端和接收端的时钟同步。一般计算帧的大小的时候是不包含前导码的。

image-20191204110405472

​ 有许多不同的以太网标准,标准的格式都是相同的,不同在速率上(2Mbps,10Mbps,100Mbps,1Gbps,10Gbps),可以使用不同物理介质(光纤,线缆)。

​ 以太网交换机。以太网交换机是链路层设备。存储-转发以太网帧。检验到达帧的目的MAC地址,选择性向一个或多个数据链路转发帧,利用CSMA/CD访问链路,发送帧。通常的交换机是透明的,即插即用的,能够自学习的(无需配置)。交换机缓存帧,在每段链路上利用CSMA/CD收发帧,但无冲突(每段链路一个独立的冲突域),且可以全双工。如下图$A$和$A’$与$B$和$B’$的传输不会产生冲突。

image-20191204111120811

​ 每个交换机都有交换表,记录每个入口(主机的MAC地址,到达主机的接口,时间戳),入口也称交换表项。交换机是通过自学习获知到达主机的接口信息。具体来说是当收到帧时,交换机”学习“到发送帧的主机(通过帧的源MAC地址),位于该收该帧的接口所连接的LAN网段,将发送主机MAC地址/接口信息记录到交换表中。交换机收到帧的时候的行为如下图所示。注意对同一接口的处理

image-20191204115153944

​ 交换机可以互联。也通过自学习(例如泛洪)。IP子网也称为广播域。

​ 交换机对比路由器,如下图所示。

image-20191204120714363

​ 同时对比网络设备如下图所示。现在网络中很少使用集线器。交换机就是多端口网桥。直通传输,就是在一个接口上接收数据帧的同时直接转发到另一个接口上(边收边发,需要设置)。

image-20191204120801379

​ VLAN。VLAN的动机是用户迁移,划分广播域,安全/隐私,效率问题。支持VLAN划分的交换机,可以在一个物理LAN架构上配置,定义多个VLAN。基于端口的VLAN:分组交换机端口(通过交换机管理软件),于是,单一的物理交换机就像多个虚拟交换机一样运行。可以实现流量隔离,也可以基于MAC地址定义VLAN,而不是交换端口。动态成员,端口可以动态分配给不同的VLAN。在VLAN间转发:通过路由(就像在独立的交换机之间),在实践中,厂家会将交换机与路由器集成在一起(三层交换机)。

image-20191204121936352

​ 中继端口比多线缆连接更好,中继端口需要在跨越多个物理交换机定义的VLAN承载帧,为多VLAN转发802.1帧容易产生歧义(必须携带VLAN ID信息),因此IEEE定义了802.1q协议为经过中继端口转发的帧增加/去除额外的首部域。具体格式如下图所示。

image-20191204122420565

PPP协议

​ 点对点数据链路控制。PPP协议是点对点链路的协议(与MAC协议不同)。一个发送端,一个接收端,一条链路:比广播链路容易。无需介质访问控制,无需明确MAC地址,如拨号链路,ISDN链路。常见的点对点数据链路控制协议有:HDLC,PPP。

​ PPP设计需求:组帧,将网络层数据报封装到数据链路层帧中,可以承载任何网络层协议分组(不仅IP数据报),可以向上层实现分用(多路分解),需要有比特透明传输,差错检测(无纠正),连接活性检测,网络层地址协商(端结点可以学习/配置彼此网络地址)。PPP不支持的功能:差错纠正/恢复,无需流量控制不存在乱序交付,无需支持多点链路。PPP数据帧的结构如下图所示。结构中的可变长度都是经过协商决定。

image-20191204123217944

​ 字节填充。为满足数据透明传输需求,数据域必须允许包含标志模式01111110,发送端在数据中的01111110和01111101字节前添加额外的字节01111101(填充,stuffs),接收端扫描数据,发现字节01111101,则丢弃这个字节保留下一个字节。

​ 在交换网络层数据之前,PPP数据链路两端必须:1.配置PPP链路,最大帧长,身份认证等,2.学习/配置网络层信息,对于IP协议:通过交换IPCP协议报文(IP分组首部的”上层协议“字段取值8021),完成IP地址等相关信息配置。

802.11无线局域网

​ 802.11有很多版本。早期是802.11b,2.4-2.5GHz免费频段,最高速率是11Mbps,物理层采用直接序列扩频(DSSS)技术(如CDMA),所有主机使用的码片序列相同。802.11a,5-6GHz,最高速率54Mbps,802.11g(使用比较多),2.4-2.5GHz频段,最高速率54Mbps,802.11n,多天线(MIMO),2.4-2.5GHz频段,最高速率:600Mbps。均采用CSMA/CA多路访问控制协议,均有基础设施(基站)网络模式和特定网(自组网)网络模式。具体数据如下图所示。

image-20191204152255743

​ 802.11体系结构。无线主机与基站(base station,也成为访问点 AP)通信,AP的覆盖范围称为基本服务集BSS,也称为单元。在基础设施网络模式中有无线主机和AP(基站),在自组网模式中只有主机。

​ 802.11b:2.4GHz-2.48GHz频谱划分为11个不同频率的信道(相邻频率有干扰),每个AP选择一个频率(信道),存在干扰可能:相邻的AP可能选择相同的信道。主机必须与某个AP关联。主机扫描信道,监听包含AP名称(服务集标识符SSID)和MAC地址的信标(beacon)帧,选择一个AP进行关联,可能需要身份认证。典型情形:运行DHCP获取IP地址等信息。

​ 802.11AP关联。有被动扫描和主动扫描。被动扫描:各AP发送信标帧,主机向选择的AP发送关联请求帧,AP向主机发送关联响应帧(通过了身份认证,连接成功,然后进行DHCP等)。主动扫描:主机主动广播探测请求帧,AP发送探测响应帧,主机向选择的AP发送关联请求帧,AP向主机发送关联响应帧

​ 802.11的多路访问控制。802.11的多路访问控制基于CSMA——发送数据前监听信道(避免与正在进行传输的其他结点冲突)。802.11不能像CSMA/CD那样边发送边检测冲突,无线信道很难实现,无法侦听到所有可能的冲突如隐藏站信号衰落CSMA/CA不能避免所有冲突,只是避免了数据帧的冲突。

image-20191204153739397

​ 802.11的MAC协议CSMA/CA协议过程如下图所示。DIFS,分布式帧间间隔时间。由于SIFS比DIFS短,因此ACK的优先级比data高。

image-20191204161159156

​ CSMA/CA基本思想:允许发送端”预约“信道,而不是随机发送数据帧,从而避免长数据帧的冲突。发送端首先利用CSMA向BS(基站)发送一个很短的RTS(request-to-send)帧,RTS帧仍然可能彼此冲突(但RTS帧很短)。BS广播一个CTS(clear-to-send)帧作为对RTS的响应,CTS帧可以被所有结点接收(消除隐藏站影响),发送端可以发送数据帧,其他结点推迟发送,推迟的时间在CTS帧的字段中有说明。利用很小的预约彻底避免了数据帧冲突。

image-20191204162237727

​ 802.11MAC帧。帧结构如下所示。有四个地址字段,第四个地址字段很少使用。duration包括了确认帧的发送时间,以微秒为单位。数据传输过程中可能将大的数据帧分片进行传输,有More frag位。

image-20191204162752511

​ 802.11数据帧有4个地址字段,地址4用于自组网络。所有地址都是MAC地址。

image-20191204162940556

​ 地址的使用场景。

image-20191204163304185