《计算机网络与通信》复习

《计算机网络与通信》复习《计算机网络与通信》复习一、三大定理1取样定理2奈奎斯特定理3香农定理《计算机网络与通信》复习1取样定理取样定理：只要取样频率fs等于或大于模拟传输信号频率fm的二倍，则样值信号序列就足够代表原先的模拟信号。如：话音系统最高频率为3.4kHz，话音带宽为4kHz，取样频率为8kHz，取样周期fs取8kHz，取样周期T为125µs，在取样后形成了幅度连续、时间离散的脉冲信号，即脉幅调制（PAM）信号。《计算机网络与通信》复习量化是将PAM信号的幅度进行分级、取整的幅度离散的过程，且将每一个取样瞬时幅度纳入邻近的整数级。编码则是把量化后脉冲取样值按幅度大小变换成相应的二进制码元，形成PCM信号。《计算机网络与通信》复习2奈奎斯特定理带宽为WHz的无噪声低通信道，它的最高的码元传输速率为：CMAX=2Wlog2N《计算机网络与通信》复习3香农定理信噪比(Signal-to-Noiseratio)为S/N的高斯白噪声干扰信道，在其对应的介质上传输可达到的数据传输速率：C=Wlog2(1+S/N)其中，式中的S/N通常用10log10P1/P2即分贝(dB)来表示，如S/N=1000，相当于30dB。《计算机网络与通信》复习由香农定理可知：在信道容量不变时，增加带宽，可以降低信噪比。利用此原理可进行带宽的扩展。《计算机网络与通信》复习二、通信质量参数1传输损耗2信道容量3误码率和误组率《计算机网络与通信》复习1传输损耗任何传输中都存在着损耗。模拟信号传输中，传输损耗将降低信号的质量；在数字信号传输中，传输损耗会引起位串错误。影响传输损耗的主要参数有：衰减、衰减失真、延迟变形和噪声。《计算机网络与通信》复习2信道容量

信道容量是指在给定条件下，给定通信路径（或信道上）的数据传输速率。信道的带宽：信道所能传输的信号的频率围，赫兹(Hz)。带宽小的信道会限制信号的部分频率成分的传输，使之衰减和失真。适用带宽的定理是：香农定理扩展带宽的方法是：多路复用技术多路复用技术包括：频分、时分、波分复用技术等。《计算机网络与通信》复习3误码率和误组率在数据传输中，通常用误码率和误组率来作为数据传输信道的质量指标。1）误码率误码率Pe是在一定时间内接收到的出错比特数e1与总传输比特数e2之比。Pe=（e1/e2）X100%《计算机网络与通信》复习误码状况一般分为三种类型：1）正常通信范围：Pe≤10-62）通信质量欠佳范围：Pe=10-3~10-63）不能通信的范围：Pe≥10-3误码时间率Pt通常是用不能通信的时间t2与可通信的时间t1和不能通信时间t2之和（整个通信时间）的比。Pt=t2/(t1+t2)X100%通常要求误码时间率达到99%以上。《计算机网络与通信》复习2误组率误组率是用块或帧检验以及在纠错的应用中能反映的重发概率。PB=b1/b2X100%PB为误组率，b1为接收出错组数，b2为总的传输组数。《计算机网络与通信》复习三、编码1纠错码2检错码《计算机网络与通信》复习（一）纠错码

1奇偶校验码奇偶校验码可分为奇校验码和偶校验码，其原理相同。校验码为1比特，其校验规则为：加入校验码的码字所包含的总的“1”的个数据为偶数，即D1+D2+D3+D4+D5+D6+D7+D8=0，式中从右到左依次为：D1、D2、D3到D7。同理，奇校验码的规则为：加入校验码的码字所包含的总的“1”的个数据为奇数，即D1+D2+D3+D4+D5+D6+D7+D8=1奇偶校验码简单实用，但纠错能力有限。《计算机网络与通信》复习2海明码海明码是一种特殊的线性分组码，它可以纠正一个出错的比特，海明码的规则为：码长为n，信息为k，附加冗余信息为r位（也称为校验位或监督位），其中每一个校验位与某几个特定的信息位构成偶校验关系。接收端对这r个奇偶关系进行校验，即将每个校验位和与它关联的信息位进行相加（异或），相加的结果称为校正因子。校正因子全为0时，为无错，不全为0时，有错；由校正因子的不同取值，知道错误发生在哪个位置上。附加位数条件为：2n≧n+1即为2n≧k+r+1，其结构为：（n,k）《计算机网络与通信》复习其校正因子在7个码元中的对应关系如下表：

《计算机网络与通信》复习由此表可得：S1=c6+c5+c4+c2S2=c6+c5+c3+c1S3=c6+c4+c3+c0若接收到的码元正确无误，S1、S2、S3全为0即有：c2=c6+c5+c4c1=c6+c5+c3c0=c6+c4+c3

《计算机网络与通信》复习（二）检错码

检错码最有代表性的就是循环冗余码。1循环冗余码的特性循环冗余码是一种分组码，其结构为（n,k），即是在一个长度为n的码组中有k个信息位和r个校验位，校验位的产生只与组内的k个信息有关。它具有以下两个特性：《计算机网络与通信》复习1）一种码中任何两个码字按模2相加后，形成的新序列仍为一个码字；若两个码字相加得到一个全为0序列，具有这种特性的循环冗余码称为线性码；2）码字的每次循环移一位一定也是集合码中的另一个码字，这种特性称为循环特性。《计算机网络与通信》复习由以上原理可将循环冗余校验码（CRC）的码多项式C(x)，表示为：C(x)=Cn-1xn-1

+Cn-2xn-2

+…+C1x+

C0信息码(k位)多项式：码多项式K(x)；校验码(r位)余数多项式：余码多项式R(x)；可得：CRC码(n=k+r位)，码字多项式C(x)：C(x)=xrK(x)+R(x)只要求得R(x)即可得CRC码多项式。《计算机网络与通信》复习循环冗余码的编码步骤为：（1）求K(x)对应的码字多项式，乘以xr；（2）然后除以生成多项式G(x)得余式R(x)；（3）相加得码字多项式：C(x)=xrK(x)+R(x)。《计算机网络与通信》复习2纠/检错能力分析1）发方由已知的K(x)求R(x):R(x)=xrK(x)÷G(x)的r位余数；除法用无借位减；G(x):给定的生成多项式；由K(x)求R(x)示例信息位串：生成多项式：11001得到余数：1010《计算机网络与通信》复习2）收方校验设xrK(x)除以G(x)的商为Q(x)，则xrK(x)=G(x)Q(x)+R(x)C(x)=xrK(x)+R(x)=G(x)Q(x)+R(x)+R(x)=G(x)Q(x)----整除差错可分为两种：一种为单个错；一种为突发错。两个码字对应位数取值不同的个数称为海明距离。《计算机网络与通信》复习四、差错控制确认消息：正确认ACK(positiveacknowledgement)和超时重发。负确认NACK或REJ(链路层)和重发。确认消息可以夹带在发送数据包的包头，称为捎带确认(piggybacking)。停-等(确认)：每发一个包就等待确认。后退N

：连发数包等确认。顺序接收累计确认,第k个包错,从第k个包开始全重发。选择重发：连发数包等确认，只重发出错的包。接收方需暂存已到达错序包…。《计算机网络与通信》复习五、多路访问技术1信道分配问题

1）静态分配在多用户竞争单信道的传统方法是频分复用FDM，这只适用户较少、数目固定、数据量较大通信，而大多数时候，用户数量不固定，通信量多少也不能保证，将每个用户分配一个信道（不管它是否需要）是不现实的。《计算机网络与通信》复习2）动态分配信道的动态分配主要是解决以下几个问题：（1）站模型。N个独立的站，每个站都可以生成帧，一旦生成帧，就阻塞，直到它发送回去。（2）单通信道假设。（3）冲突假设。若两帧同时发送，它们会互相重叠，结果产生的信号难以确认，这就是冲突。（4）连续时间。帧能在任何时间开始发送。《计算机网络与通信》复习（5）分槽时间(时隙)。时间被分为离散的区间。（6）载波检测(侦听)。所有站在使用信道之前，检查信道是否空闲，只有空闲时，才能使用。（7）无载波检测(侦听)。各站使用信道之前，不检查信道就发送出去。《计算机网络与通信》复习2多路访问协议1）ALOHA协议争用技术又称随机访问技术，即两个或多个用户站点竞争使用同一线路或信道。（1）纯ALOHA吞吐量S与网络负载G的关系为：S=Ge-2G（2）分隙ALOHA为了提高信道的利用率，将各站点都同步工作，且将时间分为等长的时隙T0，分组只能在每个时隙开始才能发送出去。S=Ge-G《计算机网络与通信》复习2）载波侦听多路访问协议CSMA技术

CSMA技术是ALOHA的一种改进协议。CSMA可分为：（1）非持续CSMA。（2）时隙非持续CSMA。（3）持续CSMA。（4）p持续CSMA。《计算机网络与通信》复习3）有冲突检测的CSMA（CSMA/CD）（1）载波监听。（2）冲突检测。（3）多路访问。《计算机网络与通信》复习二进制指数退避算法决定发送的随机时间，可采用二进制指数退避算法，其过程如下：（1）对每个帧，当第一次发生冲突时，设置参数为L=2。（2）退避间隔随机取1到L个时间间隔中的一个，一个时间间隔等于任意两个占之间最大传播时两倍。（3）当帧重复发生一次冲突时，将参数L加倍。（4）设置一个最大重传次数，超过这个限值，则停止重传并报告出错。《计算机网络与通信》复习4）无冲突协议无冲突协议主要是解决多个用户进行资源竞争时，怎样避免冲突，假定有N个站点，每个站点均与一个唯一的地址对应。（1）位图协议基本位图协议也称为预定协议，它是通过资源竞争来发送数据的，若N个站点恰好有N个时隙，如果站点I要发送数据，它就在第I个时隙中填入1个比特，当N个时隙过后，每个站点都知道哪些站点要发送数据，然后照此顺序依次发送，《计算机网络与通信》复习（2）二进制倒计数法二进制倒计数法协议是位图协议的一种改进形式，它是采用高地址具有高优先权的形式来解决资源问题的。《计算机网络与通信》复习5）有限资源竞争协议竞争者越多，性能越差，而无冲突协议的情况正好相反，竞争者越多，信道利用率越高，若把两个优点集中起来成为一个更优的协议——有限资源竞争协议，让它无论竞争者的多少，性能都较优。《计算机网络与通信》复习6）波分多路访问协议波分复用是在光纤成缆的基础上实现的大容量传输技术。它是在一根光纤上传输多个不同波长的光信号，发送端将多个光信号复合，接收端分离。《计算机网络与通信》复习六、信息变换1曼彻斯特编码规则为：每个比特的中间有跳变（极性转换）。1）二进制数“0”，在第1个间隔为低电压，在第2个间隔为高电压；2）二进制数“1”，在第1个间隔为高电压，在第2个间隔为低电压。2它常在以太网使用，它的优点是：1）自带时钟码（self-clocking-code）;2）相位的跳变容易判断0/1；3）无直流分量。《计算机网络与通信》复习2差分曼彻斯特编码编码规则为：每个比特的中间有跳变（极性转换）。1）二进制数“0”表示每个比特的开始有跳变；2）二进制数“1”表示每个比特的开始无跳变。它常在令牌环使用，用每位开始有无跳变（正或负）表示数字0∕1（有∕无）《计算机网络与通信》复习曼彻斯特编码及差分曼彻斯特编码的变换如下图：《计算机网络与通信》复习3二元指数后退算法采用二进制指数后退算法：一般地，第n次冲突后的等待时间从0到2n-1中选取；达到10次后，随机等待的最大时隙固定在1023；16次冲突后，控制器不再动作，报告发送失败。《计算机网络与通信》复习七、路由算法路由选择算法是网络层软件的一部分，负责确定所收到分组应传送的外出路线。路由选择是网络层的主要功能，理想的路由选择算法的特征有：算法正确、简单、最佳的，并具有公平性、健壮性和稳定性。路由选择算法可分为两大类：非适应式路由选择算法和自适应式路由选择算法。《计算机网络与通信》复习1最短路由最短路由选择是一种静路由选择算法，它是可以用站点数量、距离和弧段（测试分组在一段时间内的平均队列长与传输时延）来量度的。《计算机网络与通信》复习2扩散法扩散法也是一种静态路由选择算法。扩散式路由选择方法，分组从源节点送到它的各相邻节点，相邻节点再将第一次收到的分组转发到它的相邻节点，这样依次转发，总有一个最小时延的到达终点。扩散式具有可靠性高、健壮性好的特点。其不足是：网络无效传输量大，网络资源占用大，不适宜于大量的数据传输。《计算机网络与通信》复习3距离矢量路由选择算法（V-D）距离矢量路由选择算法（V-D）原理由路由器周期性地向外广播路径刷新报文，即用网关可达的网络或主机的距离信息按最短路径原则刷新路由表。若度量的标准为站点，距离是按照路径上的站点数来计算的；若度量的标准是队列，距离是由队列的长度来计算的；若度量的标准是延迟，路由器可以直接发送一个特别“响应”分组来测出延迟，接收者只对它加上时间标记后就尽快送回。距离矢量路由选择算法（V-D）的特点易于实现；收敛过程慢；交换信息量大。《计算机网络与通信》复习4链路状态路由链路状态路由选择算法（L-S）原理链路状态路由选择算法（L-S）又称为最短路径优先算法。各网关主动测试所有与其相邻网关之间的状态，即周期性地向相邻网关发出查询报文，根据相邻网关的响应判断链接状态，随后各网关周期性地广播L-S信息，网关收到L-S报文后，可刷新网络互联拓朴，若L-S发生变更，则立即采用最短路径算法刷新本地路由。L-S算法每次创建三个单列的表，一个跟踪直连相邻路由器，一个确定整个互联网拓朴，一个用于路由表中。《计算机网络与通信》复习5移动主机的路由用户的定位1）用户有一个永久性的主地址来确定它的主方位，用主地址来作为用户在系统中的路选择目标，将分组发送给动态用户，再使分组有效地到达用户所在的任何地方。2）外地代理：用来管理所有来到当地的移动用户。3）主代理：用来管理原来属于本区域，但当时正在外地的用户。《计算机网络与通信》复习移动用户登录过程1）外地代理定期广播一个分组，宣布自己的存在及其地址；2）移动主机登录到外地代理，并给出其原来所在地的地址，当前数据链路层地址，以及一些安全性信息；3）外地代理与主代理联系，并通知主代理有一个或多个移动用户在此；4）主代理进行安全性检查，以证实它确实在通知的外地；5）外地代理得到确认后，给出一个表项，并通知移动用户，它就可以登录上网了。《计算机网络与通信》复习八、拥塞控制算法当通信子网中的某一部分有太多的数据分组时，会导致网络性能的下降。这种现象称为网络中的拥塞。拥塞会引起网络分组的丢失，在严重的情况下，会导致网络运行的瘫痪。《计算机网络与通信》复习拥塞控制与流量控制的区别拥塞控制用于确保通信子网能运送所有待传送的数据，是一个全局性的问题。涉及所有主机、路由器，并与路由器的存储转发能力和其他影响通信子网负荷的因素有关。流量控制只涉及发送者和接收者之间的点到点通信流量。其任务是确保一个快速的发送者不要以高于接收者所能承受的速率发送数据。《计算机网络与通信》复习拥塞控制的出现是由于网络载荷（暂时）超过了（系统中的一部分）资源的承受能力，解决的方法是增加资源或降低载荷。一般来说，增加资源可能性不大，主要是通过降低载荷来进行拥塞控制的。解决的方法有两种：一个是开环，一个是闭环。《计算机网络与通信》复习1拥塞预防策略拥塞的预防策略，可以通过数据链路、网络和传输层来加以控制《计算机网络与通信》复习2虚电路子网中的拥塞控制虚电路子网中的拥塞控制是动态控制拥塞的一种闭环措施,常用方法有：1）许可控制许可控制是一旦出现拥塞信号，就不再创建任何虚电路，直到拥塞解除为止。2）重建出现拥塞，允许建立新的虚电路，仔细选择路由，以便新的虚电路绕过有问题的区域。《计算机网络与通信》复习3）资源保留建立虚电路时，主机和子网协商出说明了通信量、形式、服务质量和其它参数的一致意见，通过保留许多资源的方式来保障它的通讯，就不太可能出现拥塞，但这种可能浪费许多资源。《计算机网络与通信》复习3数据报子网中的拥塞控制1）抑制分组通过监视路由器和子网最近资源的利用率，当超过某个临界值时，就发出警告（抑制分组）到源端主机，并指明原分组的目的地。这种实现方法有：多个临界值法队列长度法。2）站到站抑制分组当高速或远距离的情况下，抑制分组作用太慢，效用不大，如下图(a)。我们可以通过每个站点的抑制分组都起作用，达到快速反应，迅速解脱的目的《计算机网络与通信》复习4载荷丢弃当路由器被它所不能控制的分组所掩没时,将这些分组扔掉，称为载荷脱落。为了被免这种情况的出现，在其上将多余的分组标上优先级来决定先丢弃哪些内容，超过某个极限的分组标为更低级别的优先级，并将它存于分组的一个或多个头部。《计算机网络与通信》复习5抖动控制网络多数时，都希望传输的时间延迟是一个稳定的值，延时差可以通过沿途站点计算期望传输时间来加以控制，当分组比预期先到或晚到时，可以通过沿途站点来控制它，使它按预定的时间到达目的地。《计算机网络与通信》复习九IP地址1IP地址的格式1）IP地址由4个字节组成，它分为两部分：网络号和主机号。2）IP地址采用“点分十进制”的方法来表示。每个十进制都用8位，因此都在0~255内。3）IP地址可根据网络的规模，分为五类：A类、B类、C类、D类和E类。《计算机网络与通信》复习4）因特网中的专用地址（1）主机地址全为0：表示指向本网。（2）主机地址全为1：表示广播地址，向特定网络上的所有主机发送数据报。（3）32位全为1：表示仅在本网络内进行广播发送。（4）网络号127：在TCP/IP中为回送地址，它将信息通过自身的接口发送后返回，可用来测试端口。《计算机网络与通信》复习2子网划分在C类网络地址中，只用8位定义主机。从左到右，连续不跳位且至少有两个同