计算机网络概论
计算机网络的应用
- 商业应用:
Client-Server服务模式 构建计算机网络的三个主要目标:
- 数据共享
- 个人信息共享
- 电子商务
- 家庭应用:
B:Business, C:Consumer, G:Goverment, P:Peer 不采用点到点的通信的原因:
- 通信设备相距太远
- 通信链路数为终端数的平方,不实用
- 电路交换:
每次呼叫建立一个专用电路
是专用资源,不是共享的,可以保证性能
需要考虑链路带宽和交换容量
需要呼叫建立过程 - 分组交换:
数据以离散的数据块形式在网络上发送
统计复用——分组内部序列无固定模式
多个用户处于同一分组,共享网络资源
每个分组使用全部的链路带宽,资源按需使用
会出现资源竞争,拥塞——分组排队等待
节点接受整个分组后才转发 分组交换细节:
- 内容: 消息或者报文
- 分组: 网络上交换数据的基本单位
分组头: 源地址、目标地址 - 帧: 在链路上传输数据的基本单位
帧头、帧尾: 地址、序号、校验位 发送过程:
- 发送端: 先将长报文划分为较短的、固定长度的数据段,每个数据段前添加首部构成分组
- 分组交换网以“分组”作为数据传输单元,以此把各分组发送到接受端
- 接收端收到分组后剥去首部还原为报文,最后再组合起来
分组交换的特点:
优点:- 高效: 动态分配带宽,逐段占用通信链路
- 灵活: 以分组为单位传输、存储和转发,各链路速率可以不同
- 迅速: 不必先建立连接,直接想其他主机发送分组,充分利用带宽
- 可靠: 网络协议与路由选择协议提高网络的生存性
缺点:
- 存储转发时需排队,增加时延
- 分组增加首部,加大了开销
- 分组交换与电路交换对比:
分组交换更适用于突发数据,且资源共享,无需事先建立连接,但存在拥塞问题,增大延时和丢包率 - 分组交换的时延: 处理时延、排队时延、发送时延、传播时延
Entity实体——表示发送或接收信息的硬件或软件Protocol协议——通信实体之间的规则和约定Peers对等体——不同机器上构成相同层的实体——对等体使用协议相互通信Interface接口:定义下层向上层提供哪些原语操作和服务- 数据并非在两台机器的第n层之间直接传输,而是每一层将数据和控制信息直接传递给下层,一直至最底层
- 设计问题: 可靠性、检错、纠错、路由、协议分层、寻址、互联、可扩展、资源分配、流量控制、拥塞控制、服务质量、网络安全
每层向其上层提供两种服务:
- 面向连接的服务: 电话模式、呼叫虚电路——信令
- 无连接的服务: 因特网模式——无呼叫建立过程、不维护端对端的连接状态
- 服务原语——一个服务由一组原语说明,用户进程通过原语访问该服务.原语告诉服务要执行某个动作.
- 服务是一层向其上层提供的一组原语(操作),服务定义了该层准备代表用户执行哪些操作,但并不包括如何实现
协议是一组规则,规定了对等实体之间所交换的报文格式和含义
服务和协议是完全独立的 - 网络体系结构模型:
应用层——提供网络应用、传输层——进程之间的数据传输、网络层——源到目的之间的数据报路由、链路层——临近网络部件间的数据传送、物理层——在线路上传输的位 OSI(Open Systems Interconnection)模型的概念- 服务: 每一层向上层提供某些服务
- 接口: 告诉上层如何访问本层,规定了参数以及结果,没有说明本层是如何工作的
- 协议: 协议是内部的事情,可以使用或改变任意协议,只要能完成既定的任务,不影响上面的各层
网络标准化:
- 电信领域: 国际电信联盟
ITU有三个部门-T电话电报数据接口-R无线电通信分配无线频率-D发展部门 - 著名的国际标准化组织: 国际标准化组织
ISO(International Organization for Standardization),电器和电子工程师协议IEEE - 因特网标准:
IEEE,RFC(Request For Coments)
- 电信领域: 国际电信联盟
- 互联网标准:
802.3——以太网、802.11——无线局域网、802.15——蓝牙&Zigbee、802.16宽带无线
物理层
- 物理层: 定义了为建立、维护和拆除物理链路所需的机械、电气、功能和规程等特性,其作业是使比特流能在物理介质上传输.
提供以下服务:
- 提供传送和接收比特流的能力,物理连接的建立、维持和释放
- 在两个相邻系统之间唯一地标识数据电路
数据传输理论: 信道传输等限制
- 通信系统的一般模型
数据(data)——携带信息(即比特)的实体; 信号(signal)——信号是表示消息的物理量,随时间变化 通信系统的主要参数
- 信号功率
S,单位为瓦特(焦耳每秒W) - 信号带宽
B,单位为赫兹(Hz): 与收发设备及传输介质的特性有关 - 噪声功率
N: 通信线路上的平均噪声功率 SNR:S/N是信噪比,单位为分贝(dB), $SNR_{dB}=10\log_{10}(S/N)$- 数据率,单位为
bps: 数据传输速率 - 误码率: 数据传输错误的概率,衡量数据传输的质量,单位为 $1\times10^{-n}$
- 信号功率
- 信号分析方法——傅立叶变换: 任一个周期为T的函数
g(t),可以用傅立叶级数来表示
$g(t)=\frac{c}{2}+\sum_{n=1}^\infty a_n\sin(2\pi nft)+\sum_{n=1}^\infty b_n\cos(2\pi nft)$,
$\int_0^T\sin(2\pi kft)\cos(2\pi nft)=\delta_{k,n}\frac{T}{2}$
$a_n=\frac{2}{T}\int_0^Tg(t)\sin(2\pi nft)dt, b_n=\frac{2}{T}\int_0^Tg(t)\cos(2\pi nft)dt,c=\frac{2}{T}\int_0^Tg(t)dt$ - 信号带宽受限: 各频率分量的幅度$\sqrt{a_n^2+b_n^2}$表示信号传输的能量
- 传输带宽会影响数据率,正相关, 传输带宽与通信设备、传输介质有关
- 传输带宽: 传输中幅度衰减不明显的频率范围;定义为接收功率由最大将为1/2(3dB)的频率范围
- 奈奎斯特定理: 在理想无噪声的信道条件下最大数据率$=2B\log_2V$,其中B为信道带宽,V为信号中的状态数
- 香农容量公式: 信道极限信息传输速率或无误码容量C遵从公式: $C=B\log_2(1+S/N)\ b/s$
传输介质: 常用传输介质的特性
双绞线:(STP)屏蔽双绞线, (UTP)无屏蔽双绞线, 传输距离为100米, 可传数字信号和模拟信号
Type(Category) 1 2 3 4 5 5e 6 7 Use Voice Only Data to 4Mbps 10Mbps 20Mbps 100Mbps 100Mbps 250MHz 600MHz Where Telephone Wire Local Talk Ethernet 16Mbps Token Ring Fast Ethernet Fast Ethernet Gigabit Ethernet 同轴电缆:
系带同轴电缆:阻抗匹配$50\Omega$,用于数字信号传输
- 粗缆10Base-5,单段最长500米,最长5段2.5公里
- 细缆10Base-2,单段最长185米,最长5段925米
- 宽带同轴电缆:阻抗匹配$75\Omega$,用于电视信号传播
- 光缆: 由传导光波的高纯石英玻璃纤维和保护层构成,全反射原理,多根光纤封装在坚固的外壳中构成多芯光纤
光发射系统:
- 光源: LED(发光二极管),ILD(注入型激光二极管),光信号的有无表示1和0
- 检测器: 接收端由光电二极管构成的光检测器将光信号转换成电信号
- 光纤的连接: 机械式0.1dB快速无需特殊设备, 熔结,极低损耗0.05dB,昂贵的特殊设备,长距离链路唯一方法
- 无线传输: 中频0.3-3M、高频3-30M、甚高频30-300M、超高频0.3-3G 用于移动通信, 特高频3-30GHz用于数字通信
- 微波,利用抛物面天线聚集能量可沿直线实现视距传输(LOS),具有很高的信噪比
可以利用地面传播,地波传播——2MHz以下平行地表传播,天波传播——2-30MHz在地面与大气层之间来回反射
数字调制技术: 比特与信号间的转换技术及常见通信系统
基带传输
带宽效率——与一个符号承载的比特数有关:
- 符号电平数多,则承载比特也多, 如8电平的符号可以表示3比特
- 符号率: 信号改变的频率,单位为波特率,若带宽为B,则符号率为2B
非归零码NRZ(Non-Return-Zero): 0为高电平,1为低电平
- 时钟恢复: 根据跳变来恢复时钟,可能因长时间发送0或1导致信号电平无跳变,导致收发之间难以同步
- 信号平衡(基线漂移):用接受信号的平均值确定信号电平的高低,连1或连0会改变信号均值
- 对于NRZ,若带宽为B,则数据率为2B
非归零反转码NRZI(NRZ Inverted):是一种差分编码
- 信号跳变表示1, 无跳变表示0
- 解决了连1问题,未解决连0
- 弱带宽为B,则数据率为2B
曼彻斯特编码(Manchester Encoding)
- 发送0时,电平从高到低跳变, 发送1时,电平从低到高跳变
- 每比特时间必有一次电平跳变,接受方通过检测该跳变实现与发送方的位同步
- 带宽为B,则数据率为2B
差分曼彻斯特编码
- 在每位信号起始处,没有跳变表示1,有跳变表示0,
- 每比特时间仍有一个跳变用来同步
- 需要更复杂的设备,有更好的抗干扰性
4B5B编码
- 4比特数据用5比特编码,保证码组前部最多1个0,尾部最多2个0,即码流中连0不超过3个
- 对码组再用NRZI编码,每5比特至少有2个1,即有两次跳变
- 4B5B的编码效率为80%, 用于100Mb/s以太网和光纤分布式数据接口FDDI
通带传输
- 由于基带信号在信道上长距离传输会受到衰减、畸变和噪声影响,低频信号不适合远距离传输, 各个传输介质有其适于的信号频率范围, 需要将数字信号转换成一种适合于在信道上传输的信号,称转换过程为调制(modulation);相应的,从信号中提取数字信号的过程称为解调(demodulation)
- 调制解调器(MODEM)就是调制器(MOdulator)和解调器(DEModulator)的组合
数字调制技术:
- 用$A\sin(2nft+\Phi)$表示正弦信号,使A,f或$\Phi$随基带信号而变化,称为对载波进行调制
- 基本调制方法: 调幅(AM), 调频(FM), 调相(PM)
- 调幅: 在幅度调制中,两个不同载波信号的幅值分别代表0和1,有时也用恒定幅度的载波的有和无代表1和0
- 调频: 频率调制是用两个不同频率的载波分别代表0和1, 抗干扰能力优于调幅,但频带利用率不高,常用于传输低速数字信号
- 调相: 相位调制是用不同相位的载波分别表示0和1, BPSK
调制: QPSK正交相移键控:用信号的45度135度225度315度表示2比特
- 联合信号的幅度和相位,使一个符号表示更多比特,黑点表示合法的幅度和相位
- QAM正交振幅调制 QAM-16,振幅相位16种组合,可表示4比特
- 调制星座图: 数字通信中,将数字信号表示在复平面上,给出信号及信号之间的关系的图示就是星座图
信道复用: 在一条传输介质上提供多个数据传输信道的方法
频分复用 FDM(frequency division multiplexing)
- 信号在同样时间占用不同频段
当信道带宽B为基带调制信号带宽的N倍时,将信道分割为N个子信道,在每个子信道上传输一路基带信号
- 子信道之间有保护间隔
- 基带滤波器
- 用各路基带信号调制不同频率的载波,将各路信号搬移到各个子信道上
- 举例: 广播系统、电话系统、电视系统
时分复用 TDM(time division multiplexing)
- 信号在不同时间占用同样的频段
- 所有用户占用同样频段的不同时隙,组成信道传输的帧
- 用户按照“轮”来访问信道,每一轮,每个用户得到固定长度的时隙
- 用户之间需要同步, 需要在时隙之间设置保护间隔,应对同步偏差和远近效应
- 举例: 电话系统骨干网中数据传输,第二代蜂窝无线通信系统,以太网中的数据传输
码分复用 CDM(code division multiplexing)
- 从代码集$C_k$中选取特有的“码序列”分配给每个用户,码序列特点是
$$ \frac{1}{m}\sum_{i=1}^mC_{ki}C_{ji}=\delta_{k,j} $$
- 所有用户共享相同频率,但每个用户用其特定码序列对数据进行编码或调制,允许多个用户“共存”并同时传输,具有最小的干扰,因为“码”是正交的
- 编码信号=原始数据x码序列, 解码信号=编码信号x码序列
- CDMA(Code Division Multiple Access) 码分多址,是无线广播信道的标准,扩展了频谱,通常码片速率为信息速率的m倍, 编码信号=原始数据x码片序列
- 原始数据经CDMA编码后,信号频谱被展宽,称为扩频,例如原始10Kbps,100倍扩频后码速率为1Mbps
- 展宽的信号频谱不易被检测,已知码序列才能解调数据,因此扩频通信具有保密性
各子载波正交 OFDM(Orthogonal frequency division Modulation)
- M是调制不是复用, 其方法时:在某一子载波的中心采样,则其他正交子载波的干扰为0
- 用基带数据调制一个正交频率子载波, 子载波之间没有保护间隔,更有效地利用带宽(最大的频谱效率), 要求子载波间严格正交,接收频率严格对准
对比
- FDMA:抑制带外信号,需设置保护频段
- TDMA:各信号严格同步,需设置保护时间间隔
- CDMA:需要功率控制
- OFDM:需要各子载波频率正交,接发频率对齐
单双工
- 单工: 信道只能在一个方向上传输数据
双工(duplex): 信号可以在两个方向上同时传输数据
- TDD(Time Division Duplex)——时分双工
- FDD(Frequency Division Duplex)——频分双工
- CDD(Code Division Duplex)——码分双工
脉冲编码调制 PCM(Pulse Code Modulation)
- 脉冲编码调制PCM是将模拟信号变换为数字信号的方法,包括采样、量化和解码三个步骤
- 编解码器codec
- 采样: 奈奎斯特定理,若模拟信号带宽为WHz,则采样频率为2W时,足以捕获模拟信号的信息
- 量化: 对取样点信号幅值分级取整
- 编码: 将量化后的整数值用二进制表示
TDM复用——T1标准
- 长距离链路TDM传输语音和数据混合信号,24个信道总数据率为1.544Mbps, 每个信道8位数据(7语言1信令),数据率位56(7x8)Kbps
- T1总速率 [(7+1)x24+1]x8k=193bx8k=1.544Mbps E1:2.048Mbps=8x32x8K(32个子信道,30个语音,2个控制信号及帧同步)
- PDH(Plesiochronous Digital Hierarchy)准同步数字系列,各路时钟频率有一定偏差,复接时需插入一定脉冲实现同步
- SDH(Synchronous Digitial Hierarchy)同步数字系列, SONET(Synchronous Optical NETwork同步光网络), 系统由一个精度$10^{-9}$的时钟控制,精准同步,易于复接和分接
SONET/SDH 速率和复用
- SONET基本信道, $125\mu s$传输810字节(90列x9行),数据率=8bit x 810Byte x 8KHz=51.84Mbps 称为STS-1同步传输信号
- 多路STS-1复用:3路STS-1合成为STS-3.155.52Mbps,STS-n的光纤线路称为OC-n,从 OC-3开始 称作同步传输模块STM-1,
GSM
- 25MHz, FDM将25MHz分为124个信道,每个信道200KHz,再在每个子信道用TDM
- 手机发送频率比接收频率高45MHz
数据链路层
组帧及检错
数据链路层
- 结点(node):主机及路由器
- 链路(link):连接相邻结点之间的通信信道,可分为有线链路、无线链路
- 帧(frame):在数据链路上传输数据的基本单位,用于承载数据
- 数据链路层: 负责在一个结点与其相邻结点之间经过一条链路传递数据
- 在每个主机中,链路实现是在适配器,即网卡(NIC)——网卡实现链路层及物理层,与主机的系统总线连接,是软件硬件及固件的结合,可分为以太网卡、PCMCI网卡、802.11网卡
- 适配器之间通信: 发端——将数据封装成帧,增加校验位,接收地址,实施流量控制等; 发端——检查错误,检查接收地址,实施流量控制等,提取数据,交由高层处理
成帧——同步、透明传送
同步: 计算机之间的通信需要收发双方协调发送和接收之间的动作
异步传输: 以字符为传输单位,字符之间的时间间隔是可变的,而字符中的位则以固定速率传送.
- 起停位、数据为、校验位
- 传输字符之间无固定时间间隔
- 接收时钟与发送时钟存在偏差
- 特点: 简单、廉价、每帧一个字符
同步传输: 发送和接收之间的每位都是同步的,接收端从接受的信号中提取时钟,以保持与发送信号的时钟同步
- 以数据块位传输单位
- 要求时钟同步——提供时钟线给接收端或从接收信号中提取时钟
- 适用于长距离的数据传输,效率高
- 举例: 以太帧——同步码:8个字节,前7 用于帧的位同步,最后1个是帧开始定界符,表示后面的信息是MAC帧
- 帧是链路层的基本单位,用于承载链路层的数据、实施差错控制
- 异步传输中的起始停止位、同步传输中的同步位之后需要确定帧开始.
成帧方法:
字节计数法: 利用头部的一个字段来标识该帧的字节数
- 问题:若头部字节出错,则会失去同步
- 解决:若能将一个特殊的字节作为帧的首尾标志,则帧失步后可以重新同步
封装成帧: 在一段数据的前后分别加首部“SOH”(0x01)和尾部“EOT”(0x04),构成一个帧
- 首部和尾部的作用就是帧定界
- 问题: 若帧数据部分含有帧头或帧尾,则会导致同步出错,遗失信息
解决:
字符填充实现透明传输:
- 发送端若在数据中出现“SOH”或“EOT”,则在其前面插入一个转义符“ESC”(0x1B).
- 接收端将数据送往高层之前删除插入的转义符.
- 若转义符也在数据中出现,则在转义符前插入一个转义符,当接收段收到连续两个转义符时就删除一个
用比特填充实现透明传输:
- HDLC,帧标志位F为01111110,采用零比特填充,
- 数据中某一段比特组合恰好和F一样时,
- 发送端在连续发送5个连1后,填入一个0比特再发送出去,
- 接收端将5个连1之后的0比特删除,恢复原帧
差错控制技术:检错及纠错
- 差错: 数字通信系统中接收位与发送位不一致
- 信道误码率: $P_b=$误码位数/发送总位数
- 若误码率为$P_b$,帧长为L位,则无差错帧的概率为$P_1=(1-P_b)^L$
差错检测: 在信息位中加入冗余位——编码
- 信息位:要发送的数据
- 冗余位:按某种关系对信息位运算所得到的数据
- 发送过程:信息位+冗余位,构成码字,发送码字
- 接受过程: 检查信息位和冗余位之间的关系(校验过程),以发现传输过程是否初心啊差错
奇偶校验
- 增加冗余位,使码字中的1的个数为奇数或偶数个,称为奇(或偶)校验
- 一维奇偶校验: 检测单比特错,无法纠错
- 二维奇偶校验: 检测并纠正单比特错
- 检错码: 能自动发现差错的编码,如奇偶校验码、循环冗余码CRC(Cyclic Redundancy Code)
- 纠错码: 不仅能发现差错而且能定位差错的位置:,如汉明码、卷积码等
- 汉明距离(码距)为两个码字中不相同位的个数
- 编码就是增大码距,解码就是找出距离码字最近的码字
- m位信息+r位校验,在$2^{m+r}$中仅传输$2^m$种码字,码距大于1,码字空间稀疏
码距与检错、纠错能力的关系（当d≤4）
- 若码距d为奇数,则能发现d-1位错,或能纠正(d-1)/2位错.
- 若码距d为偶数,则能发现d/2位错,并能纠正(d/2-1)位错.
- 若要检测d位错,则需要码距为d+1,若要纠正d位错,则需要码距为2d+1
- 码率: 衡量编码效率——若码长为n的码字中含有信息位m位,则码率=m/n
- 理论上, m位信息位,r位校验位,则$m+r+1\leq2^r$,给出了纠1位错r的下界
纠错码——汉明码:
- 校验位:(p1,p2,p4,p8,p16,...)r位,位于$2^n$,n=0,1,...,r-1
- 信息位:(m3,m5,m6,m7,m9,...)m位
- 第K位信息的校验位来自2的幂次只和,如5=1+4
例如(7,4)汉明码,码长7,信息位4,校验位3
- 信息位m3=p1+p2,m5=p1+p4,m6=p2+p4,m7=p1+p2+p4
- 根据校验位的计算结果,可以定位差错的位置——纠1位错
检错码——交织与校验和
- 码字的检错能力有限,如奇偶校验码,汉明码只能纠检1位错
- 突发长度:在码字中第1位错与最后1位错之间的间隔
交织:将信息位组成n列k行,按列计算校验位,按行顺序发送,只要突发长度$\leq$n,则可以检错,
- 实现最多只有1位错
- 校验和:对发送数据位计算校验和,接收端实施同样运算以检错,例如IP头、UDP报文
检错码——循环冗余校验CRC
- d位数据,组成一个二进制数D, 选择r+1位生成式G,计算r位的CRC位R
- 发送端使<D,R>能被G整除(模2),计算端已知G,用<D,R>除以G,若余数为0则保留,否则出错
- 可以检测所有突发长度小于等于r位的错误
- 用于Ethernet,802.11WiFi,ATM
编码效率高
- G(X)能检出所有1比特错,因为G(X)不含$X^i$因子即含1
- G(X)能检出所有2比特错,因为G(X)不含$X^i$因子且对任何$0< e \leq n-1$的e除不尽$x^{e+1}$
- G(X)能检出所有奇数位错,因为G(X)含因式(X+1)
- 能检出所有长度小于等于CRC长度的突发错
- 易于硬件实现——移位、异或
- 举例: CRC-12 $X^12+X^11+X^3+X^2+X+1$
差错控制方法:
前向纠错FEC(Forward Error Correction):采用纠错码,接收端发现差错并纠正
- 纠错编码模型——发送端纠错编码送信道传输,接收端接收信号译码,检测到错误自动纠正
- 优点: 无需反向信道、单工即可,也可用于一对多的通信
- 缺点: 译码设备复杂,为纠错需附加冗余码
- 纠错编码模型——发送端纠错编码送信道传输,接收端接收信号译码,检测到错误自动纠正
自动请求重传ARQ(Automatic Repeat reQuest): 接收端检测到错误时,通知发送端重传,直到收到正确的数据
- 模型——发送端将数据发向信道,同时缓存数据.如果接到重发请求,则将放入缓存器的数据重新编码发送,接收端判决,如果接收正确则发送ACK,若检测到错误则发送NACK,要求重发.
- 三种ARQ方式:停发等候重发、返回重发、选择重发
- 模型——发送端将数据发向信道,同时缓存数据.如果接到重发请求,则将放入缓存器的数据重新编码发送,接收端判决,如果接收正确则发送ACK,若检测到错误则发送NACK,要求重发.
混合纠错HARQ(Hybrid ARQ)检错码+纠错码
- 若发现差错但在纠错范围内,则直接纠错; 当超出纠错能力时,则要求发端重传
- 对比
FEC不需要重传,实时性好,常用于无线链路
ARQ常用于计算机网络
ARQ
基本的数据链路层协议
- 检错及纠错:在帧头增加控制信息,帧尾增加帧校验
- 定义一系列函数,例如:
wait_for_event(&event); event表示发生的事件 - 发送方:发送帧给另一主机
接收方:收到数据后计算帧校验,设置event
- 若有错,则event=chksum_err;否则event=frame_arrival
停等协议:
- 发送端发送数据时同时缓存;当收到确认帧后,才清除
- 只有收到确认帧ACK后,才发送新的数据帧
- 接收端受到数据帧后,发送确认; 若时新数据帧,则保存;若为重复帧,则丢弃
- 发送端自动对错帧重传,因此称为自动请求重传ARQ
信道利用率:
- 设数据帧长 $l_f$(bit) ,数据发送速率$R$(bit/s), 则一个数据帧的发送时间$t_f=l_f/R$
数据帧发送后若经过重传时间还没有收到确认帧,则重传数据帧,设重传时间为
$$ _{out}=t_p+t_{pr}+t_a+t_p+t_{pr} $$
- 一般处理时间$t_{pr}$和确认帧发送时间$t_a$远小于传播时延$t_p$,故忽略他们,得到$t_{out}=2t_p$
定义$\alpha=t_p/t_f$,表示传播时间(即延迟)与帧发送时间(为带宽倒数)之比,则信道利用率
$$ =t_f/(t_f+2t_p)=1/(1+2\alpha) $$
- 设数据帧长 $l_f$(bit) ,数据发送速率$R$(bit/s), 则一个数据帧的发送时间$t_f=l_f/R$
- 优点: 简单
缺点: 信道利用率不高,尤其不适于再长时延的信道上采用
连续ARQ:
- 发送发连续发送多个分组,不必每发完一个分组就停下来等待确认,提高了信道利用率
- 若延迟为$t_p$,带宽为帧率$1/t_f$(单位时间发送的帧数), 则延迟带宽积为$\alpha=t_p/t_f$
- 若可连续发送的帧数为w,则利用率$\leq w/(1+2\alpha)$
- 接收确认帧ACKi表示期望收到的下一个帧的序号是i
- 接收端: 按序接收数据帧
- 发送端: 收到ACKn时取消n-1的计时器, n计时器超时时,重传第n个数据帧
- 又被称为Go-back-N ARQ
滑动窗口:
- 发送端和接收端分别设置发送窗口和接收窗口
- 发送窗口WT用来对发送端进行流量控制,表示发送端最多可发送的数据帧数量
- 接收端只接收发送序号落入接收窗口的数据帧
- 连续ARQ中,接收窗口WR=1,收发两端窗口不断向前滑动,协议又称滑动窗口协议
- 若WT=1,则为停止等待协议
- 当帧序号用n个比特编号时,若接收窗口为1,则发送窗口$W_T\leq 2^n-1$
选择重传ARQ:
- 增大接受窗口WR, 接受序号不连续但仍在接收窗口的数据帧,等收到缺失序号的数据帧后再送交主机
- 避免重传正确到达接收端的数据帧,但需要接收端有缓存
- 若用n比特编号,则接受窗口最大为$W_R\leq2^{n-1}$
捎带确认与累计确认:
- 累计确认:接收端不是每收到一个数据帧就发送一个确认帧,若确认序号为i,则表示 (i-1)及之前的所有数据帧均被确认,且期望收到的下一个帧的序号为i.
- 捎带确认:当接收端向发送端发送确认信息时,如 果同时存在需要发送的数据,那么可以将确认信息和数据合并在一个帧中发送
MAC
信道分配与多路访问协议
一个共享信道, 两个或更多结点同时发送:干扰,碰撞:如果同时接收到两个或两个以上的结点的发射信号
介质访问控制MAC(Medium Access Control):
- 决定结点如何共享信道,确定下一个使用信道的结点
- 信道共享的控制必须使用自身的信道
- 与信道复用的区别:
MAC:关注多个用户如何使用共享的信道 ,分配算法
信道复用:关注信道如何划分为多个信道,TDM、FDM、CDM、OFDM
划分信道
- 将总的信道资源分割为更小的信道(时隙,频率,码字)
- 为需要使用信道的结点分配信道资源
- 通常需要一个信道分配中心,信道资源集中控制
随机接入
- 不分割信道,允许碰撞
- 接收端避免碰撞
划分信道
时分多址TDMA(time division multiple access)
- 按照“轮”来访问信道, 在每一轮,每个站得到固定长度的时隙(长度=分组发送时间)
- 未使用的时隙成为空闲的
- 实现问题:需要时隙同步;设置保护间隔
频分多址FDMA(frequency division multiple access)
- 将信道划分为频段, 为每个站分配固定的频段
- 不传输信号,则频段为空闲的
- 实现问题:需要带通滤波器,设置频率保护带
静态信道分配
- 传统的复用技术(FDM,TDM等),N个用户N个信道,信道数与用户数相同
- 面临的问题:用户数量很多且动态变化,例如当每个用户的数据为突发时
- 将信道划分为N个独立的信道,降低了信道效率
- 信道容量为C ,帧的平均长度为$1/\mu$ b,平均到达率为$\lambda$帧/s,
平均延迟时间为$T=\frac{1}{\lambda-\mu C}$
动态信道分配
- 划分信道,增大了平均延迟,降低了信道利用率
- 对于数据突发业务,N的数量动态变化,需要一种动态信道分配技术
随机访问控制: 当结点有分组要发送时,以全信道速率R发送分组,结点之间没有优先级协同
- 两个或两个以上的发送结点——碰撞
ALOHA:
- 假设:
帧长度相同,发送时间为1;
各个站不需要同步;
一个帧到达时,就立即发送 - 那么在$t_0$时刻发送的帧将与发送时刻位于[$t_0$-1,$t_0$+1] 的帧碰撞
- 效率:
当 N -> 无限,最大利用率 = 1/(2e) = 0.18
- 假设:
时隙ALOHA
- 假设:
帧长度相同、信道时间划分为相同的时隙(每个时隙发送一个帧)、
结点只有在时隙开始时刻才能发送,以降低碰撞的概率、
结点之间是同步的、
若在一个时隙中有2个以上的结点同时发送,所有结点都可以检测碰撞 当结点得到一个新的帧,则在下一个时隙发送
- 若没有碰撞:结点可以在后续时隙发送新的帧
- 若碰撞:结点在后续时隙中以概率p重传该帧,直到成功发送
- 效率(成功发送的时隙比率):
当N趋于无穷时,最大效率 = 1/e = 0.37 优点:
- 一个活动的结点可以 以全信道速率连续发 送数据
- 非集中式:只是结点 的时隙需要同步
- 简单
缺点:
- 碰撞,浪费时隙
- 空闲时隙
- 结点在发送数据之前 不能够检测碰撞
- 时钟需要同步
- 假设:
载波侦听CSMA(Carrier Sense Multiple Access)
结点在发射信号前测试信道状态,如果信道空闲(即没有检测到载波),则按照以下算法来发送.
- 1-坚持CSMA(1-persistent CSMA)
当信道空闲时，以概率1发送 - 非坚持CSMA(non-persistent CSMA)
若信道忙，则等待一随机时间，之后再进行载波侦听 - p坚持CSMA(p-persistent CSMA)
若信道空闲，则以概率P在当前时隙发送，而以概率1-p推迟到下一时隙发送
- 1-坚持CSMA(1-persistent CSMA)
- 在低负载时，采用1坚持CSMA，吞吐率高于ALOHA的;在高负载时，非坚持更好;非坚持CSMA峰值吞吐率约比1-坚持CSMA高2倍
- 仍然可能发送碰撞:传播延迟致使两个结点无法听到对方发送的信号
CSMA/CD (碰撞检测)
- 在短时间内做碰撞检测
- 终止有碰撞的发送, 降低信道的浪费
- 易于在LAN中实现:测量信号强度，比较发送、接收信号
- 难于在WLAN中实现:接收信号很小，而发送信号很大
无冲突协议
碰撞降低了带宽、增加了帧的发送时延
通过竞争方式预约信道，而在预约的信道上用无冲突的方式传输数据位图协议(预约协议reservation protocols)
- N个站，每个站的地址为0~(N-1)，忽略传播延迟
- 每个竞争周期有N个时隙
- 第j号站有帧要发送时，则在时隙 j 发送比特1预约 时隙，不允许其它站在该时隙发送
要求各站在预约时隙的尺度上是同步的 - 经过预约时隙后，每个站都知道哪些站要发送，每个站按顺序发送帧
- 低负载时的信道利用率: 平均等待时间为N个时隙
- 高负载时的信道利用率: 平均延迟:排队时间+N+(N-1)d
轮询
- 主结点邀请从结点按序发送,典型地用于主从式通信环境
- 问题:轮询的开销、延迟、主结点故障
令牌环:控制令牌依次经过各个结点、携载信息
- WLAN中的PCF方式
有限竞争协议
降低竞争的站数，则增加了获得信道的概率
有限竞争协议是适当调整竞争站点数- 将结点划分为组
- 第0组的成员只允许在第0时隙竞争
- 若某个站竞争成功，则其占用信道并发送帧;若发生碰撞，则第1组的成员继续在第1时隙竞争
以太网与WLAN
IEEE802.3 以太网:CSMA/CD
- 总线型:用同轴电缆连接，或用双绞线通过集线器连接
所有的节点在同一碰撞域，节点之间相互碰撞 - 星型拓扑
交换机:位于中心
每个链路执行以太网协议，节点之间不再相互碰撞 
- 8个字节前导码:前7字节是同步码，实现帧的位同步，最后1个字节是帧开始定界符，表示后面的信息是MAC帧
- 地址字段:目的地址首位为0的为普通地址，为1的为组播地址;全1的为广播地址;源地址前3字节为组织标识符，分配给网络制造商
- 类型字段:通知接收方帧内包含的协议类型
- 数据字段:最小长度 (64-18) 字节，不足时，插入填充字段
- 以太网以多点接入方式共享总线资源, CSMA/CD:Carrier Sense Multiple Access with Collision Detection，载波监听多点接入/碰撞检测
$\tau$为端到端传播时延，发送数据帧后最多经过$2\tau$后,可判决是否发生碰撞;$2\tau$称为争用期
- 发生碰撞后，推迟一个随机时间再发送;退避时间由二进制指数退避算法决定
- 基本退避时间取$2\tau$
- 重传次数为k，每次退避后，K累加k = Min[k+1,10]
- 随机选取一个数r， r$\in$[0,1,...,($2^k-1$)]
- 重传时延为 r×2$\tau$
- 当重传10次仍不成功，则丢弃该帧并通知上层
- 以太网的争用期为51.2$\mu$s(5120m=2*10^8 *51.2*10^-6/2),10Mb/s可发送512b，即64B
- 最短有效帧长为64B，长度小于64B的帧为无效帧。因检测到冲突就中止发送，此时的数据长度小于64字节
- 强化碰撞:当发送数据结点一旦检测到碰撞，立即停止发送数据，并要发送若干比特的干扰信号，让所有站都检测到碰撞
CSMA/CD的信道利用率
- $t_{prop}$ = LAN上两节点的最长传播延迟
- $t_{trans}$ = 最长帧的发送时间
- $efficiency=1/(1+5t_{prop}/t_{trans})$
以太网信道利用率
- $T_0$为帧发送时间, 帧长为L(b)，数据速率为R(b/s)，则帧的发送时间 $T_0$ = L/R (s), 争用期为$2\tau$
- 当N无穷大时, $S\approx\frac{1}{1+4.44a}$,$a=\tau/T_0$
- 10 Mbps，512b争用期时，节点数与利用率的关系——增加帧长，则利用率更高
IEEE802.11 WLAN:CSMA/CA
- 无线主机与基站之间的通信(基站 = AP)
有固定基础设施下的基本业务集(BSS:Basic Service Set)
- 无线主机
- AP(access point):基站
ad hoc模式:仅有主机
- 没有基站、节点只能在其信号覆盖范围内将传输数据、节点构成网络——节点实现路由
与有线链路的区别:
- 信号强度的衰减:无线信号强度与其传播路径有关 (路径损耗)
- 各种信号间的干扰:标准的无线网络频段 (如 2.4GHz) 为其它设备共享;设备之间也存在干扰
- 多径传播:无线信号经地面及物体发射，使到达 目的节点的信号有不同的延迟
- 信噪比SNR:更高的SNR–易于从噪声中提取信号
SNR与BER(Bit Error Rate)的折中
- 对给定的物理层 增加功率=增加SNR=降低BER
对给定的SNR:为得到更高的吞吐量，选择不同的物理层技术,使之满足BER要求
SNR可以随移动而改变:动态 地调整物理层(调制技术，速率等)- 随着节点与BS距离的增加 ，SNR降低, BER增大
- 当BER太高时, 切换到更低的传输速率，BER随之降低
- 注册:
AP周期性地(如每100ms)发送信标(Beacons)广播帧，建立同步，维持连通性或关联: 信标中含有BSS-ID用于指示AP及网络;业务指示(用于sleep mode);功率管理，用于站点的节能
节点: 基于信标测量RSS,与AP建立关联:节点向AP注册，节点发送请求，AP予以响应;只有注册后，节点才能发送接收数据DATA 802.11b: 信道, 关联
- 信道管理与分配:AP管理所选择的信道;可能的干扰:工作信道可能被其他AP占用!
- 主机:必须与AP关联
信道分配及注册: 节点周期性地扫描所有信道，对信道的接收信号强度进行估计(CCA Channel)
- 关联: 由信道强度决定，选择一个 AP 并注册
- 重关联:与新的AP关联，出现在下述情况下: 节点离开当前AP覆盖区;当信号条件改变时;当有多个用户与当前的AP关联时
- 802.11b: 2.4GHz-2.485GHz,定义了11(13/14) 信道，信 道带宽22MHz，信道间隔5MHz,完全正交的信道是3个，如 1,6,11
802.11: 被动扫描与主动扫描
- 被动扫描: AP发送信标帧
- 主动扫描: 客户端以广播方式发送信标帧, AP发送探测响应帧
- 隐蔽终端问题
多点访问:碰撞避免: 2个以上的节点同时发送
- 802.11: CSMA – 在发送之前侦听,不与正在发送的节点发生碰撞
802.11: 没有碰撞检测
- 因信号衰落的原因，接收信号很弱，难以在发送的同时进行接收以检测碰撞
- 因存在信号衰落以及隐蔽节点，不能检测到碰撞
- 目的:避免碰撞CSMA/CA
- 暴露节点
802.11 MAC: CSMA/CA
- 发端: 若信道空闲DIFS，则发送一个帧(无CD); 若信道占用，则:启动随机退避定时器、若信道空闲，则计时、若定时时间到，则发送、若没有收到ACK，则增加随机退避时间间隔, 返回
- 收端: 若收到一个帧，则:等待SIFS时间之后，响应ACK(因隐蔽节点问题，需要ACK)
MACA: 为解决WLAN中存在的隐蔽节点问题，采用MACA(MultipleAccess with Collosion Avoidance)
- 发送端采用CSMA先发送短RTS帧(RTS之间也可能发送碰撞，但它很短)
- 收端收到RTS后，发送CTS
CTS可被附近节点检测到，从而避免隐蔽节点问题
- 发端发送更长的数据帧
- 其他节点延迟发送
- 完全避免数据帧的碰撞，采用更短的预约分组!
载波侦听有两类，物理的和虚拟的
- 物理的载波侦听:通过PLCP在空闲信道评估(CCA:Clear Channel Assessment)阶段，侦听相关比特或检查 RSS(received signal strength)是否高于门限
- 虚拟的载波侦听:基于网络分配矢量(NAV， Network allocation vector)，从RTS/CTS帧中提取NAV
优先级:定义不同的帧间隔
- SIFS (Short Inter Frame Spacing):高优先级,用于ACK,CTS,轮询响应
- PIFS (PCF IFS):中等优先级, 用于PCF方式的有时限限制的业务
- DIFS (DCF IFS):低优先级, 用于异步数据业务
PCF: 基于DCF之上，支持无竞争、有时限要求的传输方式
- 为可选的MAC功能 – 有些产品不支持
主要过程:
- AP周期性地轮询所有设备，建立CFP;
- 在PCF期间，设置设备的NAV为ON
- PCF周期的长度可变，并占用CFP的固定位置;其他时段用于竞争并传送DCF帧
高速局域网及链路层交换机
100BASE-T以太网
- MAC帧格式仍采用802.3 标准
- R增大10倍，$\tau$减小到1/10
- 保持最短帧长不变，但将一个网段的最大电缆长度减小到100m
- 帧间时间间隔从原来的9.6$\mu$s改为0.96$\mu$s——网络设备在接收一个帧之后，需要一段 时间恢复并为接收下一帧做准备。固定的为96b的时间
千兆以太网——允许在1Gb/s下采用全双工和半双工(与集线器 连接)两种方式工作，使用802.3的帧格式
- 全双工方式:发送接收同时进行，无碰撞，不需要CSMA/CD
- 在半双工方式下使用CSMA/CD协议，与10BASE-T和100BASE-T技术后向兼容
为使参数a较小并保持网段最大长度为200m，采用“载波延伸”(carrier extension)使最短帧长仍为64字节，将争用时间增大为512字节 (4.096$\mu$s, 409.6m)
- 载波延伸: 若发送的MAC帧长不足512字节时(例如46字节数据)就在帧后填充一些特殊字符，使帧的发送长 度增大到512字节(此时链路利用率约为9%);接收端在收到MAC帧后，删除填充的特殊字节后 才交付给高层
- 帧突发: 允许发送方将多个帧级联在一起，一次传输、帧长最长为1500字节、若不足512字节，则采用载波延伸;
集线器Hubs:物理层的转发器(repeaters)
- 来自一个端口的数据以相同速率在所有端口上发送
- 连接到集线器的所有节点可以相互侦听到
- 没有帧的缓存
- 集线器不做CSMA/CD:主机NIC检测碰撞
交换式以太网:
- 需要决定一个帧去往哪个端口
- 在不同端口上传输的帧不发生碰撞
- 更安全:因为以太网卡支持混杂模式，例如协议分析软件Wireshark可以捕获全部的帧
交换机Switch:链路层设备
比集线器更智能，其主要作用
- 存储，转发以太帧
- 检测输入帧的MAC地址，有选择地向一个或多个端口转发帧，在转发接口对应的网段上实施 CSMA/CD
- 透明:主机不感知交换机是否存在
分类:
- 学习网桥:即插即用，自学习;无需配置即可工作
- 生成树网桥:
- 虚拟局域网:VLAN
- 网桥或以太网交换机:将多个局域网连接在一起，工作在链路层，检测MAC地址并转发帧
交换: 允许多点同时传输
- 主机通过专线与交换机相连
- 交换机缓存分组
- 在每条输入链路上采用以太协议，各个链路间没有碰撞;
- 每条链路有各自的碰撞
- 全双工
交换表: 表项组成(主机的MAC地址，达到主机 的接口，时间标记)类似于路由表
自学习: 当收到帧，交换机知道其发送的位置:输入LAN网段;将发送“主机/位置”记入交换表
- 不知帧的目的地址的位置: flood(在除帧接收的端口以外的其它所有端口上转发)
- 目的地址 A 的位置已知: 选择发送
- 交换机从某一端口上接收到来自H1的帧，则记录:由此端口可以发送数据给H1,不需要知道哪个AP与H1关联
- 生成树网桥:(环路问题) 网桥之间通信，构造一个连接各网桥的生成树——网桥周期地发送配置消息给邻居，并处理接收的消息;配置消息中含标识(基于MAC地址)及与其他节点的跳 数;选择最小标识作为生成树的根;构造由根到每个网桥的最短路径树
- VLAN:按照用户的组织结构而非物理结构，构建局域网
- 优点:1.安全;2.负载均衡 3.减少广播流量
- 方法:必须建立配置表，设置其端口属于G或W或GW
