通信网理论基础整理

基本概念1、RED：提前随机丢弃(Random Early Detection)；拥塞控制是一种主动队列管理算法。Random:指按照一定的概率丢弃；Early:发生在队列已满之前；detection:只是为分组标记，更倾向于被丢弃。通过监控路由器输出端口队列的平均长度来探测拥塞，一旦发现拥塞逼近，即平均队列长度超过一个阈值，就以一定的概率丢包或者在分组上作标记来通知相应的连接来减小发送速率，使他们在队列溢出导致丢包之前减小拥塞窗口，降低发送数据速度，从而缓解网络拥塞，也就是说在缓冲区满之前就按照一定的比例（即丢弃概率）随机地将缓冲区的数据丢弃或标记。随机早期检测（RED，Random Early Detection）算法将队列的平均队长作为决定拥塞避免机制是否应被处罚的随机函数的参数，增加了在队列长度变得太大之前平滑瞬时拥塞的可能性，可以过滤掉短期队长的变化，减少了同时使多个流受分组丢弃影响的可能性，使得因特网数据突发本质或短暂拥塞不会平均使队长有明显变化。概率与长度问题计算：（1）若平均队列长度小于最小门限，则把新到达的分组放入队列进行排队（p=0）；（2）若平均队列长度超过最大门限，则把新到达的分组丢弃（分组丢弃概率p=1）；（3）若平均队列长度在最小门限和最大门限之间，则按照某一概率p（0-1）将新到达的分组丢弃。RED不是等到已经发生网络拥塞后才把所有在队列尾部的分组全部丢弃，而是在检测到网络拥塞的早期征兆时（即路由器的平均队列长度超过一定的门限值时），就以概率p随机丢弃个别的分组，让拥塞控制只在个别的TCP连接上进行，因而避免发生全局性的拥塞控制。平均队列长度（）（count代表新到达的分组有多少个已经进入队列）。AQM:主动队列管理（Active queue management）,主动而非相应性的分组丢弃，提早通知发送方降低速率。包含有RED,SRED,FRED等。另一种拥塞控制：Drop tail：尾部丢弃（被动），队列达到最大长度，通过丢包来指示拥塞，告知发送方调整发送速率。2、GBN ARQ:返回N自动请求重发（Go back N automatic repeat reQuest）；差错控制发送方在没有收到对方应答的情况下，可以持续的发送多个帧（窗口大小），假如发现已发送的第N帧中有错误发生，那么回退到第N帧及其之后所有的帧全部再重新发送，窗口越大重传帧数越多，而上述过程可以自动完成，不需要上层干预。最大窗口值：2i-1（i为比特数）ARQ其他类型：停等式(stop-and-wait）ARQ（在开始下一帧传送之前，必须确保当前帧已被正确接收），选择性重传（selective repeat）ARQ（发送端不用等待接收端的应答，持续发送多帧，假如发现已发送的帧中有错误，只重新发送那个发生错误的帧）。3、 BEB：二进制指数退避（binary exponential backoff）：流量控制依据通信环境的变化，自适应调整冲突窗口时间值，提供了一个处理重负荷的方法。具体是指：一旦检测到冲突，为降低再冲突的概率，需要等待一个随机时间，然后再使用CSMA方法试图传输。为了保证这种退避维持稳定，采用了二进制指数退避算法的技术。遇到重复的冲突时，站点将重复传输，但在每一次冲突之后，通信窗口的时间t随n翻倍，从而减小发生冲突的概率，这是一种自适应算法。尝试传输的重复失败导致更长的退避时间，这将有助于负荷的平滑。具体实现：具体的退避算法如下:（1）确定基本退避时间，它就是争用期（以太网的端到端往返时间，以太网把争用期定为51.2）；（2）从离散的整数集合(k为重传次数) 中随机取出一个数，记为r。重传应推后的时间就是r倍的争用期。;(3)当重传16次仍不能成功时（这表明同时打算发送数据的站太多，以致连续发生冲突），则丢弃该帧，并向高层报告。 PPT：（1）准备就绪时，在（0，w-1）一致性随机选择延后发送；（2）起始时，,最大不超过；（3）冲突发生后，w倍增；（4）如遇信道忙，w冻结。所谓截断就是有一个上限，不能无限制的加倍。4、LPM：最长前缀匹配（longest prefix match）；路由表查找最长前缀匹配是指在IP协议中路由器用于在路由表中进行选择的一个算法。Prefix:前缀，即IP地址中的前缀部分，对用于网络号。在使用CIDR时，由于采用了网络前缀这种记法，IP地址由网络前缀和主机号这两个部分组成，这时，路由表中的每个项目由“网络前缀”和“下一跳地址”组成。但是在查找路由表时可能会得到不止一个匹配结果。应当从匹配结果中选择具有最长网络前缀的路由。这是因为网络前缀越长，其地址块就越小，因而路由就越具体。在CIDR中，路由表中的每个表项都指定了一个网络，可能存在多行路由表记录能匹配同一个IP地址，找出前缀长度最长的匹配项，即子网掩码最长的一个作为匹配依据。IP路由器查找转发表或路由表：IP前缀与出口之间的映射关系。适用于单播路由：分组只有一个目标地址；路由器查表，得到匹配项最长前缀的表项及出口；关键问题: 快速查找。5、CSMA:载波侦听多址接入（carrier sense multiple access）；多用户接入所谓载波侦听，意思是网络上各个工作站在发送数据前都要侦听总线上有没有数据传输。若有数据传输，则不发送数据；若无数据传输，立即发送准备好的数据。CSMA是从ALOHA协议演变出的一种改进型协议，它采用了附加的硬件装置，每个节点都能够检测（侦听）到信道上有无分组在传输。如果一个节点有分组要传输，它首先检测信道是否空闲，如果信道有其他分组在传输，则该节点可以等到信道空闲后再传输，这样可以减少要发送的分组与正在传输的分组之间的碰撞，提高系统的利用率。“多点接入”就是说明这是总线型网络，许多计算机以多点接入的方式连接在一根总线上，且发送数据是广播式的。6、 BHCA：忙时呼叫量（busy hour call attempt）；业务度量是通信业务工程中用于测量、评估和规划电话网络呼叫处理能力的一个关键性指标。BHCA是指在一天中一个通信系统最繁忙的一个小时（高峰时期,一般为早上9点到10点）电话呼叫的请求总次数。单位：次/小时.单位时间系统用于呼叫的开销：t=a+b*n(a固有开销；b处理一次呼叫的平均开销，N即BHCA)。7、 ESR：误码秒率或误码秒百分数（Errored Second Ratio）：服务质量指标(以秒为单位)误码秒是指这一秒内出现了错误。ESR是是误码秒（ES）和可用时间的比值，即有误码产生的秒数占总秒数的比率。是信号传输中的重要服务质量指标。相关概念：严重误码秒，是指含有30%误码秒或含有至少1个缺陷的1秒周期；SESR(Severely Errored Second Ratio)严重误码秒比率（在规定的测量时间间隔内出现的SES数与总可用时间之比），可反映设备的抗干扰能力（1s中BERE-3）。背景误码块：BBE（在扣除不可用时间后，发生在SES以外的误码块）；BBER（Background Block Error Ratio），背景块误码秒率，是指在一个确定的测试期间，在可用时间内的背景误码秒，与总秒数中扣除严重误码秒中的所有秒数后剩余秒数之比。8、HDLC:高级数据链路控制(High-Level Data Link Control)；数据链路层的传输控制是一个在同步网上传输数据、面向比特的数据链路层协议，它是由国际标准化组织（ISO）根据IBM公司的SDLC（Synchronous Data Link Control）协议扩展开发而成的。HDLC特点：HDLC是面向比特的数据链路控制协议的典型代表，该协议不依赖于任何一种字符编码集；数据报文可透明传输，用于实现透明传输的“0比特插入法”易于硬件实现； 全双工通信，有较高的数据链路传输效率；所有帧采用CRC检验，对信息帧进行顺序编号，可防止漏收或重发，传输可靠性高；传输控制功能与处理功能分离，具有较大灵活性。HDLC的完整的帧由标志字段（F）、地址字段（A）、控制字段（C）、信息字段（I）、帧校验序列字段（FCS）等组成。标志字段(F):标志字段为01111110的比特模式，用以标志帧的起始和前一帧的终止。地址字段(A)：的内容取决于所采用的操作方式。命令帧中的地址字段携带的是对方站的地址，而响应帧中的地址字段所携带的地址是本站的地址。控制字段(C)：控制字段用于构成各种命令和响应，以便对链路进行监视和控制。控制字段中的第一位或第一、第二位表示传送帧的类型，HDLC中有信息帧（I帧）、监控帧（S帧）和无编号帧（U帧）三种不同类型的帧。控制字段的第五位是P/F位，即轮询/终止（Poll/Final）位。控制字段中第1或第1、2位表示传送帧的类型，第1位为“0”表示是信息帧，第1、2位为“10”是监控帧，“11”是无编号帧。信息字段(I)：信息字段可以是任意的二进制比特串。帧校字段(FCS)：帧校验序列字段可以使用16位CRC，对两个标志字段之间的整个帧的内容进行校验。9、sliding window ：窗口控制：传输控制（可部分补充后面的基本方法内容）滑动窗口协议是用来改善吞吐量的一种技术，即容许发送方在接收任何应答之前传送附加的包。接收方告诉发送方在某一时刻能送多少包（称窗口尺寸）。TCP中采用滑动窗口来进行传输控制，滑动窗口的大小意味着接收方还有多大的缓冲区可以用于接收数据。发送方可以通过滑动窗口的大小来确定应该发送多少字节的数据。10、Architecture：体系结构/网架；网络结构在描述计算机的格式、指令类型、硬件参数和速率增强，统称为“system architecture”。与其他体系结构一样，是一门技艺。需要明确用户关于结构方面的需求，并通过设计手段，在经济和技术约束条件下，尽可能有效地完成需求指标。模型有：ITU-T HRX/HRP, 传输误码的分配；IBM SNA, 链路的可靠传输；E2E论断, 通信子网与资源子网分割ISO OSI-RM, 分层协议结构；ITU-T B-ISDN PRM, 三平面立体结构。最核心的是OSI参考模型（协议架构）:1 物理层；2 数据链路层；3 网络层；4 运输层；5 会话层；6.表示层；7.应用层。TCP/IP是一个四层的体系结构，它包括1.网络接口层；2.网际层IP（用网际层这个名字是强调这一层是为了解决不同网络的互连问题）；3.运输层（TCP或UDP）;4.应用层（各种应用层协议如TELNET,FTP,SMTP等）。五层协议的体系结构：1.物理层；2.数据链路层；3.网络层；4.运输层；5.应用层。11、E2E Arguments：端到端论断（End To End）；协议工程关于如何在功能之间进行合适的划分，如何将功能安置到合适的层中。其中包括路由选择，差错控制，安全控制等。区别于网络层的点到点控制，E2E是在传输层的。端到端是网络连接。网络要通信，必须建立连接，不管有多远，中间有多少机器，都必须在两头（源和目的）间建立连接，一旦连接建立起来，就说已经是端到端连接了，即端到端是逻辑链路，这条路可能经过了很复杂的物理路线，但两端主机不管，只认为是有两端的连接，而且一旦通信完成，这个连接就释放了，物理线路可能又被别的应用用来建立连接了。TCP就是用来建立这种端到端连接的一个具体协议，SPX也是。端到端的服务对象处在网络末端。从一末端到另一个末端会经过点到点链路，链路上会采取一些措施（如HDLC的差错控制、流量控制、拥塞控制），这些控制可以放在每一个网络上做，在Eed-to-End论断中，只要能在网络边缘做的，就不放在网络中间做。网络边缘的功能集中在网络层之上，形成TCP/IP协议的上层（传输层，应用层），网络中间要做的就是路由要做的（IP层），IP层之下就是网络结构。最后形成的协议称为协议工程。具体指：路由选择：离不开中间节点；差错控制：可以放在中间节点；安全控制：不宜放在中间节；总结为：只要在边缘做就不放在网络中间做。12、CIDR：无分类域间路由（Classless Inter-Domain Routing）；路由与寻址CIDR最主要的特点有两个：（1）CIDR消除了传统的A类、B类、C类地址以及划分子网的概念，因而可以更加有效地分配IPv4的地址空间。CIDR把32位的IP地址划分为两个部分。前面的部分是”网络前缀”（networe-prefix），用来指明网络，后面的部分则用来指明主机。因此CIDR使IP地址从三级编址（使用子网掩码）又回到了两级编址，但这已是无分类的两级编址。（记法：IP地址：=，），CIDR还使用“斜线记法”，或称为CIDR记法，即在IP地址后面加上“/”，然后写上网络前缀所占的位数。（2）CIDR把网络前缀都相同的连续的IP地址组成一个“CIDR地址块”。我们只要知道CIDR地址块中的任何一个地址，就可以知道这个地址块的起始地址（即最小地址）和最大地址，以及地址块中的地址数。13、STDM：统计时分复用（statistical time division multiplexing）；网络资源共享（1）时分复用是将时间划分为一段段等长的时分复用帧（TDM帧）。每一个时分复用的用户在每一个TDM帧中占用固定序号的时隙。每一个用户所占用的时隙是周期性地出现（其周期就是TDM帧的长度），时分复用的所有用户是在不同的时间占用同样的频带宽度。（2）STDM是一种改进的时分复用，它能明显地提高信道的利用率。STDM使用STDM帧来传送复用的数据。但每一个STDM帧中的时隙数小于连接在集中器上的用户数。各用户有了数据就随时发往集中器的输入缓存，然后集中器按顺序依次扫描输入缓存，把缓存中的输入数据放入STDM帧中。对没有数据的缓存就跳过去。当一个帧的数据放满了，就发送出去。因此，STDM帧不是固定分配时隙，而是按需动态地分配时隙。因此统计时分复用可以提高线路的利用率。使用统计时分复用的集中器也叫做智能复用器，它能提供对整个报文的存储转发能力，通过排队方式使各用户更合理地共享信道。所有用户在统计上是时分复用的。与TDM几乎无关，TDM是分配给该用户的时隙，永远被占用（独享），只是STDM从统计上来说是时分复用的。14、TCP：传输控制协议（Transmission Control Protocol）：端到端传输复用TCP是一种面向连接的、可靠的、基于字节流的传输层通信协议，由IETF的RFC 793定义。在简化的计算机网络OSI模型中，它完成第四层传输层所指定的功能。在因特网协议族（Internet protocol suite）中，TCP层是位于IP层之上，应用层之下的中间层。不同主机的应用层之间经常需要可靠的、像管道一样的连接，但是IP层不提供这样的流机制，而是提供不可靠的包交换。应用层向TCP层发送用于网间传输的、用8位字节表示的数据流，然后TCP把数据流分区成适当长度的报文段。之后TCP把结果包传给IP层，由它来通过网络将包传送给接收端实体的TCP层。TCP为了保证不发生丢包，就给每个包一个序号，同时序号也保证了传送到接收端实体的包的按序接收。然后接收端实体对已成功收到的包发回一个相应的确认（ACK）；如果发送端实体在合理的往返时延（RTT）内未收到确认，那么对应的数据包就被假设为已丢失将会被进行重传。TCP用一个校验和函数来检验数据是否有错误；在发送和接收时都要计算校验和。TCP三次握手的过程如下：客户端发送SYN（SEQ=x）报文给服务器端，进入SYN_SEND状态；服务器端收到SYN报文，回应一个SYN （SEQ=y）ACK(ACK=x+1）报文，进入SYN_RECV状态；客户端收到服务器端的SYN报文，回应一个ACK(ACK=y+1）报文，进入Established状态。三次握手完成，TCP客户端和服务器端成功地建立连接，可以开始传输数据了。TCP最主要的特点：（1）TCP是面向连接的运输层协议。这就是说，应用程序在使用TCP协议之前，必须先建立TCP连接。在传送数据完毕后，必须释放已经建立的TCP连接；（2）每一条TCP连接只能有两个端点，每一条TCP连接只能是点对点的（一对一）；（3）TCP提供可靠交付的服务。也就是说，通过TCP连接传送的数据，无差错、不丢失、不重复、并且按序到达。（4）TCP提供全双工通信。TCP允许通信双方的应用进程在任何时候都能发送数据。（5）面向字节流。15、CAC：呼叫接纳控制（Call Admission Control）；流量工程CAC：是通过限制进入网络的呼叫连接数量来降低网络拥塞概率和呼叫中断概率的方法。其目的是维护网络的稳定性、保证无线链路质量和合理利用系统容量。其一般性原理如下：即系统必须有足够的资源支持呼叫用户的请求，并且新用户的加入不能影响己经存在的用户的QoS。相关文献提出的呼叫接纳控制的标准为：系统预先估计新呼叫接纳后的用户QoS，而当所有用户的QoS都达到要求时，呼叫才能被接纳。若不能容纳新的呼叫则拒绝。呼叫接纳控制已广泛应用于许多通信网中，如ATM通信网和移动蜂窝系统。仅对VoIP的业务流，不影响普通数据业务的技术；对实时性或时延敏感的业务，依据网络负载情况，决定呼叫接续与否，是保证服务质量的一项技术。CAC方法：本地决策（依据历史经验，设置固定的允许呼叫的上限）；基于测量的决策（发启方通过测量到达目标节点的丢失率和延时，决定呼叫的接续与否）；基于资源的决策（计算所需与可用的资源，或者执行资源预留操作，再决定呼叫的接续）。16、DFS：深度优化查找（Depth-first-search）；单播路由算法它是搜索算法的一种，目的是要达到被搜索结构的叶节点。对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。步骤如下：（1）当节点V的所有关联边都已被探寻过时，搜索将回溯到发现节点V的父节点，这一过程一直进行到已发现从源节点可达的所有节点为止；（2）否则选择V的关联边e，到下一点y：如果y已查过，则e为回退边；如果y未查过，e为树边，以y替代x重复第1步。每次深度优先搜索的结果必然是图的一个连通分量。深度优先搜索可以从多点发起。如果将每个节点在深度优先搜索过程中的“结束时间”排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下，将该节点加入list结尾，然后逆转整个链表),则我们可以得到所谓的“拓扑排序”，即topological sort.(搜索原理：在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续汉下去。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。深度优先搜索所遵循的搜索策略是尽可能深地搜索图。)（2）BFS（Breadth First Search）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。17、MST：最小生成树（Minimum Spanning Tree）；多播路由算法对于一个无向连通图G=(V,E)，其中V是顶点集合，E是边的集合，对于E中每一条边（u,v），都有一个权值w(u,v)表示连接u和v的代价。我们希望找出一个无回路且连接所有的顶点，且其权值之和 为最小。因为T无回路且连接所有的顶点，所以它必然是一棵树，称为生成树，因为它“生成”了图G。最小生成树其实是最小权重生成树的简称。把确定树T的问题称为最小生成树问题。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。（1）kruskal算法：将一条权最小的边加入子图T中，并保证不形成圈。如果当前弧加入后不形成圈，则加入这条弧，如果当前弧加入后会形成圈，则不加入这条弧，并考虑下一条弧。（？）（2）prim算法：不断扩展一颗子树T=(S,F),F为E子集，知道S包括全部顶点，得到最小生成树T。每次增加一条边，使得这条边是由当前子树结点集S及其补集S所形成的边割集的最小边。（二进制堆 ：,斐波那契堆(Fibonacci heap):）18、RIP：路由信息协议（Routing Information Protocol）：距离矢量路由是基于距离矢量算法的路由协议，利用跳数来作为计量标准。在带宽、配置和管理方面要求较低，主要适合于规模较小的网络中。路由器发送一个列表，其中包含他到每一个目标路由器的延时估计值；同时，他也从每一个邻居路由器收到一个类似的列表。通过在邻居之间相互交换信息，获得邻居到目的网络的最佳路由信息，应用距离矢量路由算法得到自己到目的网络的下一跳，一个路由器针对每个邻居都执行这样的计算，就可以发现最佳的估计值，然后在新的路由表中使用这个最佳的估计值以及对应的输出线路。RIP协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录（因此，这是一组距离，即“距离向量”）。RIP协议将“距离”定义如下：从一路由器到直接连接的网络的距离定义为1.从一路由器到非直接连接的网络的距离定义为所经过的路由器加1。“加1”是因为到达目的网络后就进行直接交付，而到直接连接的网络的距离已经定义为1。RIP协议的“距离”也称为“跳数”，因为每经过一个路由器，跳数就加1。RIP认为好的路由就是它通过的路由器的数目少，即“距离短”。RIP允许一条路径最多只能包含15个路由器。因此，“距离”等于16即相当于不可达。可见RIP只适用于小型互联网。RIP不能在两个网络之间同时使用多条路由。RIP选择一条具有最少路由器的路由（即最短路由），哪怕还存在另一条高速（低时延）但路由器较多的路由。RIP协议的特点是：（1）仅和相邻路由器交换信息；（2）路由器交换的信息是当前本路由器所知道的全部信息，即自己的路由表；（3）按固定的时间间隔交换路由信息。路由表中最主要的信息就是：到某个网络的距离（即最短距离），以及应经过的下一跳地址。路由表更新的原则是找出到每个目的网络的最短距离。这种更新算法又称为距离向量算法。RIP网络有可能产生路由环路。可以通过水平分割、毒性反转、触发更新、抑制时间等技术来避免环路的产生。距离相等路径的解决方法（1） 先到先用；（2） 组播更新周期一半之前的优先。19、OSPF：开放最短路径优先（Open Shortest Path First）；链路状态路由。“开放”表明OSPF协议不是受某一家厂商控制，而是公开发表的。不是开放给所有人，而是不同企业之间可以互相开放。“最短路径优先”是因为使用了Dijkstra提出的最短路径算法SPF。OSPF只是一个协议的名字，它并不表示其他的路由选择协议不是“最短路径优先”。实际上，所有的在自治系统内部使用的路由选择协议（包括RIP协议）都是要寻找一条最短的路径。OSPF最主要的特征就是使用分布式的链路状态协议（link state protocol）,而不是像RIP那样的距离向量协议。和RIP协议相比，OSPF的三个要点和RIP的都不一样：（1）向本自治系统中所有路由器发送信息。这里使用的方法是洪泛法（flooding），这就是路由器通过所有输出端口向所有相邻的路由器发送信息。而每一个相邻路由器又再将此信息发往其所有的相邻路由器（但不再发送给刚刚发来信息的那个路由器）。这样，最终整个区域中所有的路由器都得到了这个信息的一个副本；（2）发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。所谓“链路状态”就是说明本路由器都和哪些路由器相邻，以及该链路的“度量”（metric）。OSPF将这个“度量”用来表示费用、距离、时延、带宽，等等;（3）只有当链路状态发生变化时，路由器才向所有路由器用洪泛法发送此信息。而不像RIP那样，不管网络拓扑有无发生变化，路由器之间都要定期交换路由表的信息。/OSPF的更新过程收敛得快是其重要优点。OSPF的简化原理：发Hello报文建立邻接关系形成链路状态数据库SPF算法形成路由表。20、STP：生成树协议（Spanning Tree Protocol）：（局域网、以太网的网桥中使用的生成树协议。与MST协议的一些算法接近，MST讲的是一般性问题，STP是一个具体的协议，具体在设备中使用的协议。STP是为了抑制“广播风暴”。（由于网络中有环路存在，造成每一帧都在网络中重复广播，获得了更多的响应，以至于像滚雪球一样，导致网络瘫痪，引起了广播风暴。要消除这种网络循环连接带来的网络广播风暴可以使用STP协议（生成树协议），以网络中一台交换机为节点生成一棵转发树，而树是没有环路的，这样所有的数据都只在这棵树所指示的路径上传输，就不会产生广播风暴。）广播风暴（broadcast storm）简单的讲是指当广播数据充斥网络无法处理，并占用大量网络带宽，导致正常业务不能运行，甚至彻底瘫痪，这就发生了“广播风暴”。一个数据帧或包被传输到本地网段（由广播域定义）上的每个节点就是广播；由于网络拓扑的设计和连接问题，或其他原因导致广播在网段内大量复制，传播数据帧，导致网络性能下降，甚至网络瘫痪，这就是广播风暴。）过程：（1）选择根网桥：在全网中选择一个根网桥：BID最小的被选举为根网桥。（2）选择根端口：在每个非根交换机上选择根端口：路径成本最低的端口为根端口；路径成本相同，BID较小的优先极高，称为根端口。（3）选择指定端口：在每条链路上选择一个指定端口，根网桥上所有端口都是指定端口。（1）STP的基本原理是，通过在交换机之间传递一种特殊的协议报文，网桥协议数据单元（Bridge Protocol Data Unit，简称BPDU），来确定网络的拓扑结构。BPDU有两种，配置BPDU（Configuration BPDU）和TCNBPDU。前者是用于计算无环的生成树的，后者则是用于在二层网络拓扑发生变化时产生用来缩短MAC表项的刷新时间的（由默认的300s缩短为15s）。该协议的原理是按照树的结构来构造网络拓扑，消除网络中的环路，避免由于环路的存在而造成广播风暴问题。（2）STP的基本思想就是按照树的结构构造网络的拓扑结构，树的根是一个称为根桥的桥设备，根桥的确立是由交换机或网桥的BID（Bridge ID）确定的，BID最小的设备成为二层网络中的根桥。由根桥开始，逐级形成一棵树，根桥定时发送配置BPDU，非根桥接收配置BPDU，刷新最佳BPDU并转发。这里的最佳BPDU指的是当前根桥所发送的BPDU。如果接收到了下级BPDU（新接入的设备会发送BPDU，但该设备的BID比当前根桥大），接收到该下级BPDU的设备将会向新接入的设备发送自己存储的最佳BPDU，以告知其当前网络中根桥；如果接收到的BPDU更优，将会重新计算生成树拓扑。当非根桥在离上一次接收到最佳BPDU最长寿命（Max Age，默认20s）后还没有接收到最佳BPDU的时候，该端口将进入监听状态，该设备将产生TCN BPDU，并从根端口转发出去，从指定端口接收到TCN BPDU的上级设备将发送确认，然后再向上级设备发送TCN BPDU，此过程持续到根桥为止，然后根桥在其后发送的配置BPDU中将携带标记表明拓扑已发生变化，网络中的所有设备接收到后将CAM表项的刷新时间从300s缩短为15s。整个收敛的时间为50s左右。（3）生成树协议最主要的应用是为了避免局域网中的单点故障、网络回环，解决成环以太网网络的“广播风暴”问题，从某种意义上说是一种网络保护技术，可以消除由于失误或者意外带来的循环连接。21、CSPF：约束最短路径优先（ConstrainedShortest Path First）CSPF是一种改进的最短路径优先算法，在计算通过网络的最短路径时，将特定的约束（链路，代价，下一跳，可用带宽）也考虑进去。CSPF基于资源的可用性和所选部分是否违反用户策略约束，在当前拓扑结构中删除不满足条件的节点和链路，然后再通过SPF算法计算出一条满足约束条件的最短路径，包括一组LSR（Link State Request）地址。路径计算的具体过程为：（1）对比TEDB中的每一个链路，裁减不满足带宽和颜色等要求的链路；（2）在剪切以后的拓扑中采用最短路径算法（SPF算法），得到一条满足LSP的约束条件的最短路径；（3）如果仍有多条路径，选择跳数最少的路径；（4）如果仍有多条路径，根据配置的负载分担策略进行选择。流量工程：绕过网络中已知的瓶颈和阻塞点，将业务映射到现有拓扑上的业务，将成为ISP（Internet service provider）一个非常重要的工具；ISP必须配置一个能够使他们的客户连接到他们网络上的物理拓扑结构。在网络部署完毕后，ISP必须将客户的业务流映射到网络的物理拓扑上。LSR通过对TED中的信息使用CSPF算法决定每条LSP的物理路径。22、MMPP：马氏调制泊松过程（Markov modulated Poisson process）是一个泊松过程，其瞬间泊松到达率是一个平稳的随机过程，且受到另一个泊松过程的调制，另一个泊松过程的发生与否取决于一个不可观测的隐马尔科夫过程所处的状态。一般有n个状态，任意i个状态是一个状态依赖速率参数为的泊松过程，状态之间的转移为一个基本的连续时间的马尔科夫链所控制。排队论(Queuing Theory)：是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法，又称随机服务系统理论，为运筹学的一个分支。23、语义透明：ATM的语义透明性是指信息经过ATM网络后没有误码也没有信元的丢失。语义透明性要求：从源到目的地传送信息时只能有很少的误码。误码通常有两种，一是由于信元的丢失而造成一个信元内的所有比特丢失，另一种是由于系统本身的原因和环境原因造成的单个比特的错误和突发错误。语义透明是业务传送的需求，要求来自用户的信息在通信过程中，信息内容不被改变，信息交互双方或多方之间，不因交互手段改变各自的意思。在实际通信中，为了实现语义透明，需要采用很多措施，对于误码、丢失、误插，需要采用流量控制及差错控制解决，对于编码问题，采用转义控制来解决，在语义透明中，信息量是核心问题。时间透明：也是业务传送的需求，定义为没有时延及时延抖动。要求交互双方，在可接受的时间范围内，收到对方的信息与本地或面对面交流一样，即可以被无延迟地送到，强调通信的实时性。对通信过程的控制，产生技术性约束，纠错和嵌入式技术，是核心问题。24、单纯形法：求解线性规划问题的通用方法。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在，必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。（2）根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个或多个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。（3）单纯形法的一般解题步骤可归纳如下：把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基可行解。若基本可行解不存在，即约束条件有矛盾，则问题无解。若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。若迭代过程中发现问题的目标函数值无界，则终止迭代。网络单纯形法：（后面）找最小生成树构成环的边，从环里面增加一条新边，减掉一条旧边，就构成了树的变化，对应于单纯形法中凸点之间的转换。找到一条合适的新边加入原有生成树，以便于这条生成树的成本降低。同时从原来的环里去除一条旧边，才能构造一棵新的生成树，因为树是不允许有环的。思路：（1）以一个初始生成树为起点（该生成树包含网络的所有节点）；（2）可行树解x与生成树T相关联，且 if ij不是生成树T的边；（3）通过查找所有可行树解，得最优解。因为，加入树外的边，必然增大成本。25、易损期：易损期是吞吐性能求解的一个参数，如果在一段时间区间有一个用户占用资源，则此用户可有效利用资源；若有两个或以上用户占用资源则发生冲突。会发生冲突的时间区间称为易损期。如果易损期能够求得，那么就能求出冲突概率，可以求得冲突时间和不冲突时间。这样网络的吞吐性能就能求解出来。所以易损期是在网络分析过程中至关重要的一个概念。如果在t-T到t时间内，其他用户产生了数据分组，则该分组就会和t时刻发送的分组的头部发生碰撞；同样，在t和t+T之间产生的任何分组都将和t时刻发送的分组的尾部发生碰撞。时间区间t-T,t+T称为易损期。（这里，t:分组开始发送时间，T：分组发送时长）。26.剩余服务时间：剩余服务时间是在M/G/1求解问题中常用到的一个参数，正在接受的服务还有多少时间服务结束。关心的是随时间变化的统计平均值。（剩余服务时间在M/G/1求解问题中常用到的一个参数，在M/G/1模型中，用户到达人数服从泊松分布，服务时间相同且为任意分布，只有一个服务员，在这种情况下，第i个顾客等待服务的时间可以表示为，这里的表示在第i个顾客之前等待的顾客数目，S表示平均的服务时间，R表示服务员的剩余服务时间。如果服务员处于空闲状态，那么R=0，否则表示某一个顾客接受服务的剩余服务时间。）“M/M/m”是排队系统的通用表示法。第一个字母表示到达过程的特征，M表示是无记忆的Poisson过程。第二个字母表示服务时间的概率分布，M表示指数分布，G表示一般分布，D表示确定性分布。第三个字母表示服务员的个数。有时还有第四个字母，表示系统容量的大小。如果没有第四个字母，则表示系统的容量是无限大的。基本方法1、面向连接服务：所谓连接，就是两个对等实体为进行数据通信而进行的一种结合。面向连接服务具有连接建立、数据传输和连接释放这三个阶段。面向连接服务是在数据交换之前，必须先建立连接。当数据交换结束后，则必须终止这个连接。在传送数据时是按时序传送的。面向连接服务比较适合于在一定期间内要向同一目的地发送许多报文的情况。对于发送很短的零星报文，面向连接服务的开销就显得过大了。无连接服务：在无连接服务的情况下，两个实体之间的通信不需要先建立好一个连接，因此其下层的有关资源不需要事先进行预定保留。这些资源将在数据传输时动态地进行分配。无连接服务的另一特征就是它不需要通信的两个实体同时是活跃的，当发送端的实体正在进行发送时，它才必须是活跃的。这时接收端的实体并不一定必须是活跃的。只有当接收端的实体正在进行接收时，它才必须是活跃的。无连接服务的优点是灵活方便和比较迅速。但无连接服务不能防止报文的丢失、重复或失序。无连接服务的特点不需要接收端做任何响应，因而是一种不可靠的服务。这种服务常被描述为“尽最大努力交付”或“尽力而为”。（与所涉及到的时间透明性有关，如果时间透明性要求比较高的话，不能采用面向连接的服务，无连接的时间透明性好，面向连接的时间透明性差，通信服务包括两大类一个是对时间敏感一个是对时间不敏感，通常对时间敏感采用无连接服务。）1.5、前向纠错的计算方法：为了提高时间透明性，用户应尽可能降低传输错误。所以在通信里面通常采用前向纠错做法，以便减少接收出错的情况。前向纠错也叫前向纠错码(Forward Error Correction简称FEC)，是增加数据通讯可信度的方法。在单向通讯信道中，一旦错误被发现，其接收器将无权再请求传输。FEC 是利用数据进行传输冗长信息的方法，当传输中出现错误，将允许接收器再建数据。常用的检错方法有两类：一类是奇偶校验，另一类是循环冗余校验码（Cyclic Redundancy Check）。其基本思路是发端按照给定的规则在K个信息比特后面增加L个按照某种规则计算的校验比特，在接收端对收到的信息比特重新计算L个校验比特。比较接收到的校验比特和本地重新计算的校验比特，如果相同则认为传输无误，否则认为传输有错。奇偶校验码是一种增加二进制传输系统最小距离的简单和广泛采用的方法。是一种通过增加冗余位使得码字中1的个数恒为奇数或偶数的编码方法，它是一种检错码。在实际使用时又可分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验等几种。奇偶校验可描述为：给每一个码字加一个校验位，用它来构成奇性或偶性校验。可以看出，附加码元d2，是简单地用来使每个字成为偶性的。因此，若有一个码元是错的，就可以分辨得出，因为奇偶校验将成为奇性。奇偶校验编码通过增加一位校验位来使编码中1个个数为奇数（奇校验）或者为偶数（偶校验），从而使码距变为2。因为其利用的是编码中1的个数的奇偶性作为依据，所以不能发现偶数位错误。CRC的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码也叫（N，K）码。对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。 校验码的具体生成过程为：假设要发送的信息用多项式C(X)表示，将C(x)左移R位（可表示成C(x)*xR），这样C(x)的右边就会空出R位，这就是校验码的位置。用 C(x)*xR除以生成多项式G(x)得到的余数就是校验码。2、后向反馈的滑窗控制：发送方和接收发都维持一个窗口，窗口内部包含哪些可以接收的序列号。发送方的窗口大小从0 开始，可以增大到某一个预设的最大值，由于发送方可能在未来的某个时刻重传未被确认的帧，所以它会把已发送的帧保留一段时间，知道它确认接收方已接收这些帧。接收方窗口大小固定，任何时刻一帧到达，接收方通过between检查其序列号，确认是否落在窗口内，若在窗口内，且以前未接受该帧，则接收并保存。发送窗口的上界表示要发送的下一帧序号，下界表示未得到确认的帧最小编号。每发送一帧，上界+1；每收到一个正确响应帧，下界+1；接收窗口上界表示允许接收的序号最大帧，下界表示希望接收的帧。喜好等于下界的帧被正确接收，并产生一个响应帧，下界+1。在回退n帧的ARQ中，当发送方接收到接收方的状态报告指示报文出错后，发送方将回退到第N帧及其之后所有的帧全部再重新发送。在回退N ARQ中，发送窗口大于1，接收窗口等于1，也就是说发送方在发送完一个数据帧后，不停下来等待应答帧，而是连续发送若干个数据帧，即使在连续发送过程中收到了接收方发来的应答帧，也可以继续发送，但是，一旦某帧发生错误，必须重新发送该帧及其后的帧。最大窗口大小为2n-1。TCP中采用滑动窗口来进行传输控制，滑动窗口的大小意味着接收方还有多大的缓冲区可以用于接收数据。发送方可以通过滑动窗口的大小来确定应该发送多少字节的数据。滑动窗口协议的基本原理就是在任意时刻，发送方都维持了一个连续的允许发送的帧的序号，称为发送窗口；同时，接收方也维持了一个连续的允许接收的帧的序号，称为接收窗口。发送窗口和接收窗口的序号的上下界不一定要一样，甚至大小也可以不同。不同的滑动窗口协议窗口大小一般不同。发送方窗口内的序列号代表了那些已经被发送，但是还没有被确认的帧，或者是那些可以被发送的帧。下面举一个例子（假设发送窗口尺寸为2，接收窗口尺寸为1）：分析：初始态，发送方没有帧发出，发送窗口前后沿相重合。接收方0号窗口打开，等待接收0号帧；发送方打开0号窗口，表示已发出0帧但尚确认返回信息。此时接收窗口状态不变；发送方打开0、1号窗口，表示0、1号帧均在等待确认之列。至此，发送方打开的窗口数已达规定限度，在未收到新的确认返回帧之前，发送方将暂停发送新的数据帧。接收窗口此时状态仍未变；接收方已收到0号帧，0号窗口关闭，1号窗口打开，表示准备接收1号帧。此时发送窗口状态不变；发送方收到接收方发来的0号帧确认返回信息，关闭0号窗口，表示从重发表中删除0号帧。此时接收窗口状态仍不变；发送方继续发送2号帧，2号窗口打开，表示2号帧也纳入待确认之列。至此，发送方打开的窗口又已达规定限度，在未收到新的确认返回帧之前，发送方将暂停发送新的数据帧，此时接收窗口状态仍不变；接收方已收到1号帧，1号窗口关闭，2号窗口打开，表示准备接收2号帧。此时发送窗口状态不变；发送方收到接收方发来的1号帧收毕的确认信息，关闭1号窗口，表示从重发表中删除1号帧。此时接收窗口状态仍不变。若从滑动窗口的观点来统一看待1比特滑动窗口、后退n及选择重传三种协议，它们的差别仅在于各自窗口尺寸的大小不同而已。1比特滑动窗口协议：发送窗口=1，接收窗口=1；后退n协议：发窗口1，接收窗口=1；选择重传协议：发送窗口1,接收窗口1。N:无接受应答时发送数据的最大量。3、比特填充：在HDLC的帧结构中，常以标志字段F（01111110）模式在帧两端起定界作用，若在两个标志字段之间的比特串中，碰巧出现了和标志字段F（01111110）一样的比特组合，那么就会误认为是帧的边界，会破坏同步，为了避免出现这种情况，HDLC采用零比特填充法，使一帧中两个F字段之间不会出现6个连续1。零比特填充法的具体做法是：在发送端，当一串比特流尚未加上标志字段时，先扫描整个帧。只要发现5个连续1，则立即填入一个0。因此经过这种零比特填充后的数据，就可以保证不会出现6个连续1。在接收一个帧时，先找到F字段以确定帧的边界。接着再对其中的比特流进行扫描。每当发现5个连续1时，就将这5个连续1后的一个0删除，以还原成原来的比特流。这样就保证了在所传送的比特流中，不管出现什么样的比特组合，也不至于引起帧边界的判断错误。4、Aloha随机多址接入控制：ALOHA它采用的是随机争用技术，又分为纯ALOHA方式和时隙ALOHA方式二种。其易受破坏区间为两个单