数据链路层
Mar 19th, 2020
Last updated
Mar 19th, 2020
Last updated
链路(link)是一条点到点的物理线路段,中间没有任何其他的交换结点。
一条链路只是一条通路的一个组成部分
数据链路(data link) 除了物理线路外,还必须有通信协议来控制这些数据的传输。把实现这些协议的硬件和软件加到链路上,就构成了数据链路。目的是让通信过程变得更加可靠。
现在最常用的方法是使用适配器(即网卡)来实现这些协议的硬件和软件。
一般的适配器都包括了数据链路层和物理层这两层的功能。
数据链路层采用了帧结构传输,当传输中有位发生错误时,只需要重新传输有错误的帧,提高了传输的效率。
链路管理
封装成帧 (帧定界)
有起始帧和终止帧表示传输的开始和结束
流量控制
当传输的速率过快或者稍慢可以调节传输速率
差错控制
如带有海明校验码进行传输帧的检验和纠错
透明传输
下一层不需要关心帧的传输,就像数据链路层不需要关心物理层的bit传输
在面向比特的传输协议中,通过在连续5个1后面插入0来转义起止符
在面向字节的传输协议中,通过插入转义字节来转义起止符
寻址
确定接受信息的对象地址
无确认的无连接服务
e.g. 以太网
不需要对方在线,不需要建立连接,不需要对方应答
有确认的无连接服务
不需要对方在线,不需要建立连接,需要对方应答
面向连接的服务
有建立连接、相互应答、结束连接等过程
涉及的问题
将上层(网络层)交下来的数据包按照所采用协议决定的格式,封装成一定形式的帧;
考虑接收双方的同步问题(即定界);
计算帧的校验和并放入帧中一起传送给接收方;
协议数据单元 PDU(Protocol Data Unit)
帧:在数据链路上交换数据的单位。
物理层编码违例法
发出非0非1表示传输开始
不正常,不常用
字符填充的首尾定界法
以字节为单位进行传输
以 10101011
为起止符
传输的数据是8bit的倍数
e.g. 以太网中使用最多
位填充的首尾定界法
以比特为单位进行传输
以 0111111
为起止符
传输的数据不受限制,不需要是8bit的倍数
e.g. 广域网中使用最多
数据链路层要控制从同等实体接收PDU的速率。
流量控制定义:限制发送方发送速度的一种机制。使发送速率不能超过接收方能处理的速率。
流量控制的特点
流量控制必须是动态的
流量速度不仅与发方速度相关而且与网络的当前拥挤程度有关
必须有某种反馈机制
使发送方了解接受方的当前处理能力
顺序到达
指保证所有的帧最终都按正确的发送次序到达目的。
确认方式
ACK肯定确认
NAK否定确认
计时器法
计时器值的设定要保证一帧到达对方并作处理后,相应的确认帧返回。
如果超时则主动重发
检错和纠错
检出传输中出现的差错;可能的话确定出错位置从而纠正错误。
步骤: 1. Source transmits frame 2. Destination receives frame and replies with acknowledgement 3. Source waits for ACK before sending next frame 4. Destination can stop flow by not send ACK 5. Works well for a few large frames
源实体发送一个PDU,并启动一个计时器。目标实体收到后发回一个对该PDU的确认,表示同意接受下一个PDU
计时器作用:防止死锁,两个相互等待
计时器时间设置:略大于单程传输时间
源实体必须等待直到收到确认后才能发送下一个PDU;如果源实体的计时器超时后还没有收到确认,就重新发送一次。
目标实体能简单地用停止发送确认的方式来阻止数据流。
由接受方控制发送方的数据流乃是计算机网络中流量控制的一个基本方法。
详细步骤
在发送结点: (1) 从主机取一个数据帧。 (2) 将数据帧送到数据链路层的发送缓存。 (3) 将发送缓存中的数据帧发送出去(启动Timer)。 (4) 等待。 (5) 若收到由接收结点发过来的信息(此信息的格式与内容可由双方事先商定好),则从主机取一个新的数据帧,然后转到(2)。
在接收结点: (1) 等待。 (2) 若收到由发送结点发过来的数据帧,则将其放入数据链路层的接收缓存。 (3) 将接收缓存中的数据帧上交主机。 (4) 向发送结点发一信息,表示数据帧已经上交给主机。 (5) 转到(1)。
举个例子:
设 P 是传输帧出错的概率,则传输一帧的期望为:
线路最大利用率为:
实用的停等ARQ协议
特点:简单,效率低
超时重发技术
A发送完一个数据帧时,就启动一个超时计时器
重复帧问题
如果是接收方的应答帧丢失(差错),会导致发送方重复发送,出现重复帧。每个数据帧带上不同的发送序号。每发送一个新的数据帧就把它的发送序号加1,(mod 2),1 bit序号。
帧的编号问题
序号所占用的比特数是有限的,因此,经过一段时间后,发送序号就会重复。
序号占用的比特数越少,数据传输的额外开销就越小。习惯表示,ACKn 表示“第n * 1号帧已经收到,现在期望接收第n号帧。
Stop-and-Wait ARQ结论
stop-wait协议ARQ的优点比较简单,但缺点是通信信道的利用率不高,尤其是传播延时很大时,可采用连续ARQ和选择重传ARQ。
Window size W
The sender transmits packets 0,1,2, …,W-1 and waits for up to T seconds for each of their ACKs. As soon as the receiver gets an ACK for packet 0 it transmits packet W.
If time-out go back n and retransmit.
接受端只按序接收数据帧
每发送一个数据帧都要设置超时timer
因连续发送数据帧而提高了效率,但信道传输质量很差时,效率不一定优于stop-wait 协议。
发送端在重发表中保存所发送的每个数据帧的备份。重发表按FIFO队列操作。
每个数据帧包含一个唯一的序号,该序号在相应的ACK帧中返回,返回该序号时,发送端从重发表中删除该数据帧。
对每个出错的数据帧,接收端都产生相应的NAK帧;发送端一收到NAK,从重发表中尚未确认的第一个帧开始重新发送。
注意:上图中的累计确认方式,即 发送ACK4的时候表示前面的0-3都已经收成功收到了,所以此时只需要从第4个开始重发。
前提:在连续ARQ协议中,必须对可以连续发出的最多帧数(已发出但未确认的帧)作限制,每一帧设置timer。
原则:循环重复使用有限的帧序号,以形成固定值(标准)
流量控制:
发送窗口:其大小WT表示在收到对方确认的信息之前,可以连续发出的最多帧数(只有序号在窗口内的帧才可发送)
接收窗口:其大小WR可以连续接收的最多数据帧数(只有序号在窗口内的帧才可以接收,否则丢弃)
接收窗口驱动发送窗口的转动
回退N协议的最大发送窗口大小
W_T=m : 当确认全部丢失时易造成混肴
W_T=m-1 : 发送序号为 0~m-2;重新发送的第一个序号是0,下一轮的第一个序号是 m-1,不会混淆——最大滑动窗口
W_T< m-1 : 更加不会混淆
注意:这里 GBN 的编号是一开始就预留的,滑动窗口的大小收到其限制
在连续ARQ中,如果某个数据帧发生差错,后续的数据帧即使被正确地接收到,也要被丢弃,造成网络资源浪费
为进一步提高信道的利用率,可设法只重传出错的数据帧或计时器超时的数据帧
可加大接收窗口,先收下发送序号不连续但仍处在接收窗口中的那些数据帧。等到所缺序号的数据帧收到后再一并送交主机。
选择重传 ARQ 协议可避免重复传送那些本来已经正确到达接收端的数据帧。
我们付出的代价是在接收端要设置具有相当容量的缓存空间(保存窗口中正确的帧),实现相对复杂。
选择重传ARQ协议
原则:只重传出错或定时器超时的数据帧
方法:WR > 1,暂存接受窗口中序号在出错帧之后的数据帧
优点:避免重传已正确传送的帧,提高信道利用率
缺点: 在接收端需要占用一定容量的缓存,算法相对复杂
接收窗口尺寸过大发生重叠举例
注:确认信号完全丢失的情况下,发送方重新发送0-3,而接收方希望得到4-7和下一个0,此时由于发送和接受的0序号相等导致接收端接收到了错误的序号0
与GBN协议对比
出错全部重发协议中,发送窗口的尺寸是大于1(加大接受窗口),而接收窗口的尺寸则等于1。
由于接收窗口的尺寸为1,接收端只能按顺序地接受数据帧,一旦某个帧出错或丢失,只能简单地丢弃该帧及其所有的后续帧(因为发送窗口的尺寸是大于1的),不作任何确认。发送端超时后需重发出错或丢失的帧及其后续所有的帧。
发送端需要为每个待确认的帧各自设置一个定时器。
发送窗口的尺寸不能超过2^(n-1) (这里的n为序号的编码位数),否则会造成接收端无法分辨新、旧数据帧。
只要求发送端保持一定数量的缓存来保存没有确认的数据帧,对接收端没有缓存的要求。但在误码率高的情况下,会大大降低信道的利用率。
所谓差错,就是在通信接收端收到的数据和发送端发送的数据不一致的情况。
在发送的数据码元序列中加入监督位,并进行某种变换,使它们和原来相互独立的数据码元之间具有某种约束关系。如果这种约束关系被破坏,则接收端就可以发现传输中的错误,甚至纠正错误。
变换的方法不同,就构成了不同的编码,因而产生不同的差错控制方法。
检错码可以发现传输错误,但不能自动纠正。
主要代表:CRC循环冗余校验
纠错码可以自动纠正传输错误。
由于实现复杂+需要更多冗余位导致传输效率降低,大部分纠错码限于1-3位纠错
主要代表:Hamming Code(汉明码),主要用来纠正1位差错
由于监督位需要占用传输资源,所以差错控制是以降低效率为代价的。
解决方案:
自动请求重发 (ARQ , Automatic Repeat Request)
正向纠错 (FEC , Forward Error Correction)
实际应用中主要用ARQ,只有单向(工)通信用FEC (如电视)
待传送数据M,约定好的供差错检测用位n位和约定好的除数P(P的首位和末位一定为1)
在M的后面直接添加n位的0,与P进行模2除法
模2除法中不采用借位而是直接求 异或
将上面模2除法的余数拼接在M的后面进行传输
接收端接收到的数据与约定好的除数P进行模2除法,结果为0则正确,不为0则错误
举个例子:
M = 1010001101,设 n = 5, P = 110101
加上n位0的M为 101000110100000,模 2 运算的余数 R = 01110
将余数 R 作为冗余码添加在数据 M 的后面为 101000110101110
接收方将 101000110101110 与 110101 模2运算结果为 0
CRC循环冗余计算特点:检错能力极强,开销小,易于用编码器及检测电路实现(异或位运算对硬件友好)
差错控制的重要措施:采用抗干扰编码(即纠错编码)。
定义
码组:由n个码元(0,1)构成的每一组合
信息码:代表报文的0和1
监督码:插入的 "0" 和 "1"
(按照某种规律在信息序列中插入一定数量的新码元)
举个例子:
需要传输 0 或 1
若直接传输 0 或 1,完全不知道是否有错误发生
若用00代替0,11代替1,则{00,11}是准用码组,{01,10}是禁用码组,则具备1位检错能力,不具备纠错能力
若用000代替0,111代替1,则只有{000,111}是准用码组,具有检出两位及两位以下错码的能力,具有纠正一位错码的能力,纠正是按照最短汉明距离计算的
码距:指两个码组对应码位码元不同的个数
e.g. (000)与(010) 的码距为1,(000)与(110) 的码距为2,(000)与(111) 的码距为3
由此可见,码组的最小距离越大,其抗干扰能力越强
汉明距离(d0) :一个有效编码集中,任意两个码字的码间距离的最小值。即一组编码中的最小码距
编码关系式
接收方收到数据单元和CRC后,将整个码字除以给定除数(同生成CRC用的除数)。
如果到达的数据没有差错,接收方CRC校验器产生的余数应是0,数据被接收,如果余数非0则被拒收。
注:上图中是在左端补齐,左端是末端,应该是小端存储。
理论上,自动纠正每一个二进制代码的传输差错是可以做到的。但纠错码比检错码复杂得多,而且需要更多的冗余位,导致传输效率降低。为此,大部分纠错码只限于处理1位、2位或3位差错。
在数据通信中,最常用的纠错码是所谓“汉明码”(Hamming Code),是贝尔实验室的科学家R.W.Hamming 于1950年提出的,主要用来纠正1位差错。
自动请求重发 (ARQ , Automatic Repeat Request)
自动发现差错并要求对方重发
正向纠错 (FEC , Forward Error Correction)
自动发现并纠正错误
实际应用中主要用ARQ,只有单向(工)通信用FEC
1974年,IBM的SNA采用了面向比特的 SDLC(Synchronous Data Link Control)
国际标准化组织把SDLC修改为高级数据链路控制 HDLC (High-Level Data Link Control)
CCITT则把HDLC再修改后称为链路接入规程LAP(Link Access Procedure),后改为LAPB。B即表示平衡型。
HDLC中只有一个地址域,即从站的地址,在命令帧中,它是目的地址,在响应帧中,它是源地址。
HDLC是面向比特的数据链路控制协议的典型代表,该协议不依赖于任何一种字符编码集;
数据报文可透明传输,用于实现透明传输的 “0比特插入法” 易于硬件实现;
全双工通信,有较高的数据链路传输效率;
所有帧采用CRC检验,对信息帧进行顺序编号,可防止漏收或重发,传输可靠性高;
HDLC支持的规程种类包括异步响应方式下的不平衡操作、正常响应方式下的不平衡操作、异步响应方式下的平衡操作。
One primary and one or more secondary stations,采用主从结构(有一个结点Primary管理其他结点Secondary),链路上一个主站控制多个从站,主站向从站发命令,从站向主站返回响应。
Supports full duplex(全双工) and half duplex(半双工)
平衡 Balanced
Two combined stations(既是Primary又是Secondary)
Supports full duplex and half duplex
Controls operation of link
Frames issued are called commands
Maintains separate logical link to each secondary station
Under control of primary station
Frames issued called responses
May issue commands and responses
帧同步机制 首位标志Flag:01111110
All transmissions in frames
Single frame format for all data and control exchanges
Delimit frame at both ends:01111110
May close one frame and open another(01111110可以同时作为一个帧的结尾和开始)
Receiver hunts for flag sequence to synchronize
Bit stuffing used to avoid confusion with data containing 01111110
0 inserted after every sequence of five 1s
If receiver detects five 1s it checks next bit
If 0, it is deleted
If 1 and seventh bit is 0, accept as flag
If sixth and seventh bits 1, sender is indicating abort
Identifies secondary station that sent or will receive frame
Usually 8 bits long
May be extended to multiples of 7 bits
LSB (Least Significant Bit)of each octet indicates that it is the last octet (1) or not (0)
每8位的最小位是0或1,0代表后面还有扩充地址,1代表扩充地址结束
All ones (11111111) is broadcast
全1的情况是发送广播,任何人都能接收
Different for different frame type
Information - data to be transmitted to user (next layer up)
Flow and error control(流控制和差错控制) piggybacked(捎带) on information frames
开头第一位是 0
Supervisory - ARQ when piggyback not used
监控帧用于差错控制和流量控制
开头两位是 10
Unnumbered - supplementary link control
开头两位是 11
First one or two bits of control filed identify frame type
8位控制码
16位控制码
注意里面构成:
N(S) = Send Sequence Number
N(R) = Receive Sequence Number
S = Supervisory Function Bits
M = Unnumbered Function Bits
P/F = Poll/Final Bit
Use depends on context(基于传输的内容)
Command frame
P bit
1 to solicit (poll) response from peer(发出请求)
Response frame
F bit
1 indicates response to soliciting command(发出应答)
Only in information and some unnumbered frames
Variable length
信息帧用于传送有效信息或数据,通常简称I帧。
I帧以控制字第一位为“0”来标志。
信息帧的控制字段中的N(S)用于存放发送帧序号,以使发送方不必等待确认而连续发送多帧。
N(R)用于存放接收方下一个预期要接收的帧的序号,N(R)=5,即表示接收方下一帧要接收5号帧,换言之,5号帧前的各帧接收到。
N(S)和N(R)均为3位二进制编码,可取值0~7。
FCS
Error detection
16 bit CRC
Optional 32 bit CRC
Exchange of information(负责传输数据), supervisory(负责进行检查) and unnumbered frames(负责建立连接)
Three phases(面向连接三步曲)
*Initialization
Data transfer
Disconnect
Connection Establishment
SABME ---->
<----- UA
Data Transfer
I-frames and
S-frames for flow and error control.
Disconnect
Either entity can issue a DISC
IP数据报用字符END(0XC0)定界。(11000000)
如果在IP数据中出现END字符(0XC0),就用2字节字符 0Xdb,0Xdc 代替。
如果IP数据报中有字节为0Xdb,就用 0Xdb,0Xdd 代替。
存在的问题: 1. 没有类型域,只能支持IP数据报。 2. 没有校验位。
特点:
IP地址的动态分配和管理;(因为是点对点传输所以甚至可以开始时没有地址)
同步(面向位的同步传输)或异步(起始位+数据位+奇偶校验位+停止位)传输;
网络层协议的复用;
链路的配置、质量检测和纠错;
多种配置参数选项的协商。
FLAG: 7Eh = b'01111110
ADDR: FFh = b'11111111 直接硬编码,因为点对点不需要地址
CONTROL: 03h = b'00000011
PROTOCOL: PPP支持不同的协议
CRC: 校验码
PPP协议通过LCP协议完成数据链路的配置和测试
PPP协议通过NCP协议完成点对点通信设备之间网络层通信所需参数的配置
一次交互
PPP不存在主从之分,两者都可以发起请求和应答
假设点对点通信的一端发送了一个Config-Request报文,该报文将携带多种配置选项,具体携带哪些配置选项视应用而定。
当对端正确接收到该报文后,如果接受该报文携带的所有配置选项,则回应一个Config-Ack报文。
点对点通信的一方设置了IP地址,而另一方则通过协商从对端获取IP地址。
one sender, one receiver, one link: easier than broadcast link:
no Media Access Control
no need for explicit MAC addressing
e.g., dialup link, ISDN line
popular point-to-point DLC protocols:
PPP (point-to-point protocol)
HDLC: High level data link control
F:首尾标志7Eh,透明传输采用字符填充
A:地址字段,永远为FFh,表示所有站点都可以接收
C:控制字段,默认为03h,表示无编号帧
协议:指明净荷字段的包类型,支持LCP、NCP、IP、IPX、AppleTalk...
LCP(链路控制协议),用于建立/拆除数据链路连接、测试连接质量、协商参数...
NCP(网络控制协议),用于协商网络层选项,如动态分配IP地址
物理层:支持MODEM拨号、HDLC位串行线、SONET...
no error correction/recovery(不负责纠错)
在TCP/IP协议族中,可靠传输由运输层的TCP协议负责,而数据链路层的PPP协议只进行检错。
这就是说,PPP协议是不可靠传输协议。
no flow control(没有流量控制)
在TCP/IP协议族中,端到端的流量控制由TCP负责,因而链路层的PPP协议就不需要再重复进行流量控制了。
out of order delivery OK(没有应答序号传输)
PPP不是可靠传输协议,因此不需要使用帧的序号(许多过去曾经很流行的停止等待协议或连续ARQ协议都是用序号。)
在噪声比较大的环境下,如无线网络,则可以使用有序号的工作方式,这样就可以提供可靠传输服务。
no need to support multi-point links (e.g. polling)
PPP协议不支持多点线路(即一个主站轮流和链路上的多个从站进行通信),而只支持点对点的链路通信。
差错、序号等问题放在高层解决,因为网络层的传输中出错的概率很小,所以不花费时间去检查检查。
对于广播信道,需要解决信道分配问题,信道的分配方案有:
静态分配:如传统的FDM或TDM,如果有N个用户,把带宽或时间分成N份,每个用户静态地占用一个。
缺点是不能有效地处理突发数据,有的用户无通信量时白白浪费资源。
动态分配:异步时分多路复用。分为两种:
随机访问(争用,contention):只要有数据,就可直接发送,发生冲突后再采取措施解决冲突。适用于负载轻的网络,负载重时效率低。
控制访问:发送站点必须先获得发送的权利,再发送数据,不会发生冲突。在负载重的网络中可获得很高的信道利用率。主要有轮转(round-robin)和预约(reservation)两种方式。
Two types of “links”
point-to-point (single wire, e.g. PPP, SLIP)
broadcast (shared wire or medium; e.g. Ethernet, Wavelan, etc.)
When node has packet to send
transmit at full channel data rate R.
no a priori coordination(预先的配置) among nodes
two or more transmitting nodes -> “collision”
random access MAC protocol specifies:
how to detect collisions
how to recover from collisions (e.g., via delayed retransmissions)
Examples of random access MAC protocols:
slotted ALOHA
(pure) ALOHA
CSMA and CSMA/CD
20世纪70年代,美国夏威夷大学的ALOHA网通过无线广播信道将分散在各个岛屿上的远程终端连接到本部的主机上,是最早采用争用协议的网络。(Aramson)
Too short -> large number of collision
Too long -> under-utilization
两个版本:
纯ALOHA协议(Pure ALOHA):每个站点只要有数据就可发送;通过监听信道来发现是否发生冲突;若冲突,则等待一段随机时间,再重新发送。
时隙ALOHA协议(Slotted ALOHA):将信道时间分为离散的时间片,每个时间片可以用来发送一个帧。一个站点有数据发送时,必须等到下个时间片的开始才能发送。
工作原理:每个站只要有数据发送,就可自由发送一个数据帧,但必须收到接收节点的确认信号ACK之后,才能发送下一个数据帧。
冲突的发生:两个以上的站同时发送报文分组,由于在时间上重叠从而造成冲突,导致发送失败。
冲突的解决方案:发送节点在一个timeout interval内未收到确认信号ACK,自动重发。
特点:简单、不需要同步
任意时刻直接发送不需要等待
发生 collision 的概率增多 (以一帧传输的时间为单位时间)
pkt sent at t0 collide with other pkts sent in [t0-1, t0+1]
可以看出需要在发送帧的时间前后1个单位都没有其他数据发送
推导传输成功率
time is divided into equal size slots (= pkt trans. time)
node with new arriving pkt: transmit at beginning of next slot
if collision: retransmit pkt in future slots with probability p, until successful.
Slotted Aloha efficiency
Suppose N stations have packets to send
each transmits in slot with probability p
prob. successful transmission S is:
At best: channel use for useful transmissions 37% of time!
Aloha protocol is very simple, and fairly robust against failure of a host.
The protocol is distributed among the hosts.
Under low-load, we can expect the delay to be small.
Under high-load, a lot of time is “wasted” sending packets that collide.
Improving performance: 1. Listen for activity before sending a packet.(发送前监听) 2. Detect collisions quickly and stop transmitting.(快速检测碰撞) 3. After a collision, pick the random waiting time so as to maximize throughput.(加大吞吐量)
目的:载波监听多点访问 CSMA是从ALOHA演变出的一种改进协议。采用了附加的硬件装置,每个站都能在发送数据前监听信道上其他站是否在发送数据。如在发送,则此站就暂不发送数据,从而减少了发送冲突的可能。这样就提高了整个系统的吞吐量。
根据监测时刻不同,及监测后采用策略的差异,可分为四种:
非坚持CSMA(non-persistent CSMA)
1-坚持CSMA
P-坚持CSMA
CSMA/CD:边听边发
非坚持CSMA的工作原理
(a) 监听到数据"闲",则发送;
(b) 监听到数据“忙”,则放弃监听,按一定退避算法(random delay)延迟一段时间(这就是“非坚持”的含义),返回(a)。
优点:采用随机重传时间减少碰撞概率。
缺点:延迟时间内可能会出现通道闲的情况,利用率不高。
坚持CSMA的工作原理
坚持CSMA的特点是在监听到信道忙,仍坚持听下去,一直坚持听到信道空闲为止。
有两种不同的策略:
p-坚持CSMA
(a) 若信道“闲”,以0<p<1
的概率发送,以概率(1-p)延迟一个随机时间段再发送。
(b) 信道"忙",则继续侦听到信道闲,返回(a)。
优点:P可以设置以提高效率,但很难选择。
1-坚持CSMA
1-坚持是p-坚持的特例:p=1的情况,一旦监听信道为闲立刻发送。
优点:提高信道利用率。
缺点:若有两个或更多的站同时在监听信道,则一但信道空闲就必然使这些同时发送的帧互相冲突。
带冲突检测的 CSMA
引入原因
当两个帧发生冲突时,两个被损坏帧继续传送毫无意义,而且信道无法被其他站点使用,对于有限的信道来讲,这是很大的浪费。如果站点边发送边监听,在监听到冲突之后立即停止发送,可以提高信道的利用率,因此产生了CSMA/CD。
工作原理
站点使用CSMA协议进行数据发送 (1-坚持) ;
在发送期间如果检测到冲突,立即终止发送,并发出一个瞬间干扰信号,使所有的站点都知道发生了冲突;
在发出干扰信号后,等待一段随机时间,再重复上述过程。
collision detection(CD)
easy in wired LANs: measure signal strengths, compare transmitted, received signals -> 以太网使用 CSMA/CD
difficult in wireless LANs: receiver shut off while transmitting -> 无线网使用 CSMA/CA
CSMA/CS 伪代码
Jam Signal: make sure all other transmitters are aware of collision
Exponential Backoff: (截断二进制指数退避)
Goal: adapt retransmission attempts to estimated current load
heavy load: random wait will be longer
first collision: choose K from {0,1}; delay is K * 512
bit transmission times
K=0 --- send instantly
K=1 --- wait K*512 bit transmission times
after second collision: choose K from {0,1,2,3}
after N collision: choose K from {0,1,2,3,...,2^N-1}
after ten or more collisions, choose K from {0,1,2,3,4,…,1023}
The efficiency (the percentage of useful time) is:
Question: you want to increase the bandwidth of the network, but still want to maintain the same efficiency, what do you do?
Answer: Increase T_prop as well
Token:特殊的比特模型
拓扑结构:点到点链路连接,构成闭合环
传输媒体:STP,光纤,速率4/16Mbps;
令牌沿着环旋转
当某站要发送时必须等到经过该站的令牌
当一个站发送数据时环上不再有令牌
帧将在环上运行一周后由发送站清除
发送站完成发送后释放令牌
该站所发送的帧的前沿已回到本站(已绕环一圈)
该站已完成其帧的发送
下游的第一个站就能抓住令牌并进行发送
逻辑上和物理上均为环型
起始、结束定界符(违例差分Manchester码)
访问控制字节:
PPP,RRR:优先级位,和优先级预约位
T:令牌位,帧类型标识
0 表示 令牌为空,可以发送数据,发送数据则将T位改成1然后挂载数据传递下去非令牌帧
1 表示 信息/控制帧,查看目的地址是否为自己,是自己则接收数据
M:监督位,防止无效帧在环路中无限循环
优点
在重负载条件下有效而公平
可对媒体访问进行灵活控制
提供优先级和保证带宽的服务
内置应答
发送节点在取回帧时能肯定是否被正确接收
缺点
在轻负载下效率较低
站必须等待token的到来才能发送
需要对token进行维护
既不能丢失,也不能重复
CSMA/CD是一种随机争用的媒体控制方式,具有不可知的最长等待时间。
在工厂自动化生产中,需要一种具有可知的最长等待时间的媒体访问控制方法。
802.4采用总线型的物理媒体,媒体访问控制方式则采用令牌环的方式.。
前导码(Preamble):用于接收方时钟同步,但最短可以只有1个字节。
帧首定界符和帧尾定界符(SD and ED):用作帧定界标志,用模拟编码符号。
帧控制段(FC):表示帧是数据帧还是控制帧,在控制帧中,该段则说明帧的类型;在数据帧中,则带上该帧的优先级。
目的/源地址:接收方/发送方地址,有16位和48位两种,但在同一局域网中所有的地址长度应相同。
帧检验序列(FCS):32位循环冗余码,检验除前导码、SD和ED外的字段。
局域网(LAN)是在一个小区域范围内对各种数据通信设备实现互连的信息网。特点如下:
地理范围有限,一般局限于单个建筑物内,也可覆盖几个建筑物。如一个企业网,范围在几公里~几十公里。
传输速率比较高,延迟小,传输速率一般在10Mbps~1000Mbps,~10Gbps。
传输介质通常为光缆、双绞线;无线局域网流行
往往为一个单位/组织来统一管理
局域网产生的原因
70~80年代,微型机发展迅速,彼此需要相互
通信(近距离),共享资源
决定局域网特性的主要技术
用以传输数据的传输媒体
用以连接各种设备的拓扑结构
用以共享资源的媒体访问控制方法
局域网的典型特性
高数据传输速率(10M-1000Mbps,10G)
短距离(0.1-10km)
低误码率(10^-8-10^-11)
星型(Star)
环型(Ring)
总线型(Bus)
树型(Tree)
同轴电缆
双绞线
光纤
无线
逻辑链路控制子层(LLC)
通过提供统一格式,向网络层提供一个接口
支持链路的多路访问特性,建立/释放逻辑连接,差错控制,帧序号处理
屏蔽各种802网络的底层差异,如拓扑结构、介质、介质访问控制访问
介质访问控制子层(MAC)
根据网络的拓扑结构和传输介质,不同的局域网采用不同的介质访问控制方法
成帧(各种不同的帧结构),拆帧,寻址等
CRC校验
提供三种服务
无连接的服务
面向连接的服务
复用
差错控制与流量控制
类似HDLC协议,定义了三种格式
信息帧