通信网复习整理终极版

1、1、 RED(random early detect)，提前随机丢弃：拥塞控制是一种主动队列管理算法。通过监控路由器输出端口队列的平均长度来探测拥塞，一旦平均队列长度超过一个阈值，就以一定的概率丢包或者在分组上作标记来通知相应的连接来减小发送速率，从而缓解网络拥塞，也就是说在缓冲区满之前就按照一定的比例（即丢弃概率）随机地将缓冲区的数据丢弃或标记。TCP拥塞控制与网络层有密切的关系。网络层对拥塞控制的策略之一就是Drop tail尾部丢弃，缓冲区溢出时丢弃。路由器的尾部丢弃往往会导致一连串分组的丢失，这就使得发送方出现超时重传，使TCP进入慢状态开始，即发生全局同步现象。为了避免网络中全局同步

2、现象，路由器采用RED措施。即使路由器的队列维持两个参数，即队列长度最小门限THmin和最大门限THmax。每当一个分组到达时RED组都先计算平均队列长度Lav。RED的算法是：（1）若Lav<THmin，则把新到达的分组放入队列进行排队。（2）若Lav>THmax，则把新到达的分组丢弃。（3）若THmin<Lav<THmax，则按照某一概率p将新到达的分组丢弃。RED中的随机就体现在（3）中，也就是说RED不是等到已经发生网络拥塞后才把所有在队列尾部的分组全部丢弃，而是在检测到网络拥塞的早期征兆时，就先以概率p随机丢弃个别的分组，让拥塞只在个别的TCP连接上进行，因而

3、避免发生全局性的拥塞控制。2、GBN ARQ，返回N自动请求重发：差错控制差错控制：自动请求重发；前向纠错控制；混合纠错控制；有四种不同形式的ARQ：停止等待（SW） ARQ、GBN ARQ、选择重发（SR） ARQ、并行等待（ARPANET）ARQ。GBN ARQ：运用最广泛。发信侧不用等待收信侧的应答，持续的发送多个帧，假如发现已发送的帧中有错误发生，那么从那个发生错误的帧开始及其之后所有的帧全部再重新发送，窗口越大重传帧数越多。最大窗口值：-1（i通常去3或7）。缺点：一个分组的差错可能引起大量分组的重传，这些分组可能已经被接收方正确接收了，但由于未按序到达而被丢弃。SR ARQ：是对G

4、BN ARQ的改进，与GBN ARQ的思路相同，但只重发出错的帧。这就要求加大接收窗口，以便先收下失序到达但仍然处在接收窗口中的哪些分组，等到所缺分组收齐后再一并送交上层。同时要求接收方有对分组排序的能力，且应答应包括出错帧N以及那些大于N的已被正确接收的帧的信息。3、 BEB，二进制指数退避：流量控制二进制退避技术（binary exponential backoff）. 指在遇到重复的冲突时，站点将重复传输，但在每一次冲突之后，随着时延的平均值将加倍。二进制指数退避可以依据通信环境的变化自适应的调整冲突窗口值，提供了一个处理重负荷的方法。尝试传输的重复失败导致更长的退避时间，这将有助于负荷

5、的平滑。二进制退避技术（binary exponential backoff）. 一旦检测到冲突，为降低再冲突的概率，需要等待一个随机时间，然后再使用CSMA方法试图传输。为了保证这种退避维持稳定，采用了二进制指数退避算法的技术。冲突的窗口以2的指数次方增长，让站点随机延迟一个时间点来发送，从而减小发生冲突的概率，这是一种自适应算法.其算法过程如下：1. 将冲突发生后的时间划分为长度为2t的时隙2. 发生第一次冲突后，各个站点等待0或1个时隙再开始重传3. 发生第二次冲突后，各个站点随机地选择等待0，1，2或3个时隙再开始重传4. 第i次冲突后，在0至2的i次方减一间随机地选择一个等待的时隙数

6、，再开始重传5. 10次冲突后，选择等待的时隙数固定在0至1023（2的10次方减一）间6. 16次冲突后，发送失败，报告上层。例：若第二次发生碰撞：n = 2，k = MIN(2,10) = 2，R = 0, 1, 2, 3)，延迟时间 = 0, 51.2 , 102.4 , 153.6 us 其中任取一4、LPM(Longest-prefix Matching)最长前缀匹配（可变长网络号）：路由表查找（最长前缀匹配是指在IP协议中被路由器用于在路由表中进行选择的一个算法。因为路由表中的每个表项都指定了一个网络，所以一个目的地址可能与多个表项匹配。最明确的一个表项，即子网掩码最长的一个，就叫

7、做最长前缀匹配。）IP路由器查找转发表或路由表：IP前缀与出口之间的映射关系。适用于单播路由：分组只有一个目标地址；路由器查表，得到匹配项最长前缀ib的表项及出口；关键问题: 快速查找。5、CSMA载波侦听多址接入；多用户接入（先听后说）/CD（边听边说）/CA（先听后说） 随机多址接入协议：ALOHA协议和CSMA协议。CSMA：以太网中，总线上只要有一台计算机在发送数据，总线的传输资源就会被占用。所以在同一时间只允许一台计算机发送信息，否则会发生冲突。载波侦听：每一站在发送数据之前要先检测总线上是否有其他站在发送数据，若有则暂不发送，要等信道变为空闲时再发送。CSMA/CD：“边说边听”。

8、首先检查线路上是否有其他主机信号在发送:如果有，说明其他主机在发送，自己利用退避算法等一会再试图发送。如果没有其他主机信号，自己则将数据发出去，同时不断监听线路，如果检测到有其他信号，则自己发送一个阻塞信号，通知其他节点停止发送数据，自己也要停止发送数据，此时，再利用退避算法等一会再试图发送。CSMA/CA：“先听后说”。首先检测介质是否空闲，若是介质为空闲时，送出RTS信号，接收端收到RTS信号后，将会送响应信号CTS，当发射端收到CTS包后，随即开始发送数据包。接收端收到数据包后，将以包内的CRC校验码来检验包数据是否正确，若是检验结果正确时，接收端将响应ACK包，告知发射端数据己经被成功

9、地接收。当发射端没有收到接收端的ACK包时，将认为包在传输过程中丢失，将重新发送数据。CTS帧有两个作用：一是表明接收节点B可以接收发送节点A的帧，二是禁止B的临节点发送，从而避免了B的临界点的发送对A到B的数据传输造成的影响。 6、 BHCA，忙时呼叫量：业务度量BHCA（Busy Hour Call Attempt，忙时每小时起呼次数）是通信业务工程中用于测量、评估和规划电话网络呼叫处理能力的一个关键性指标。BHCA是指在一天中一个通信系统最繁忙的一个小时（高峰时期）电话呼叫的请求总次数。7、 ESR，误码秒（百分数|率）：服务质量指标(以秒为单位)是指在一个确定的测试期间，在可用时间内的

10、误码秒（ES）与总秒数之比。(SESR(Severely Errored Section Ratio)，严重误码秒率，是指在一个确定的测试期间，在可用时间内的严重误码秒（SES）与总秒数之比。严重误码秒，是指含有30%误码秒或含有至少1个缺陷的1秒周期(BBER（Background Block Error Ratio），背景块误码秒率，是指在一个确定的测试期间，在可用时间内的背景误码秒，与总秒数中扣除严重误码秒中的所有秒数后剩余秒数之比。背景误码秒是指扣除在严重误码期间出现的严重误码秒之后所剩下的误码秒。8、 HDLC，高级数据链路控制：数据链路层的传输控制.完成功能：传输控制。做法：滑窗控

11、制高级数据链路控制（High-Level Data Link Control或简称HDLC），是一个在同步网上传输数据、面向比特的数据链路层协议，它是由国际标准化组织（ISO）根据IBM公司的SDLC（Synchronous Data Link Control）协议扩展开发而成的。HDLC的完整的帧由标志字段（F）、地址字段（A）、控制字段（C）、信息字段（I）、帧校验序列字段（FCS）等组成。HDLC特点：HDLC是面向比特的数据链路控制协议的典型代表，该协议不依赖于任何一种字符编码集；数据报文可透明传输，用于实现透明传输的“0比特插入法”易于硬件实现； 全双工通信，有较高的数据链路传输效率

12、；所有帧采用CRC检验，对信息帧进行顺序编号，可防止漏收或重发，传输可靠性高；传输控制功能与处理功能分离，具有较大灵活性。标志字段(F):标志字段为01111110的比特模式，用以标志帧的起始和前一帧的终止。地址字段(A)：的内容取决于所采用的操作方式。命令帧中的地址字段携带的是对方站的地址，而响应帧中的地址字段所携带的地址是本站的地址。控制字段(C)：控制字段用于构成各种命令和响应，以便对链路进行监视和控制。控制字段中的第一位或第一、第二位表示传送帧的类型，HDLC中有信息帧（I帧）、监控帧（S帧）和无编号帧（U帧）三种不同类型的帧。控制字段的第五位是P/F位，即轮询/终止（Poll/Fin

13、al）位。控制字段中第1或第1、2位表示传送帧的类型，第1位为“0”表示是信息帧，第1、2位为“10”是监控帧，“11”是无编号帧。信息字段(I)：信息字段可以是任意的二进制比特串。帧校字段(FCS)：帧校验序列字段可以使用16位CRC，对两个标志字段之间的整个帧的内容进行校验。9、sliding window ，窗口控制：传输控制滑动窗口协议是用来改善吞吐量的一种技术，即容许发送方在接收任何应答之前传送附加的包。接收方告诉发送方在某一时刻能送多少包（称窗口尺寸）。发送方可以通过滑动窗口的大小来确定应该发送多少字节的数据。发送窗口用来对发送端进行流量控制。发送窗口的大小Wt代表在还没有收到对方

14、确认信息的情况下发送端最多可以发送多少个数据帧。在接收端只有当收到的数据帧的发送序号落入接收窗口内才允许将该数据帧收下。若接收到的数据帧落在接收窗口之外，则一律将其丢弃。在连续 ARQ 协议中，接收窗口的大小 Wr = 1。（只有当收到的帧的序号与接收窗口一致时才能接收该帧。否则，就丢弃它。每收到一个序号正确的帧，接收窗口就向前（即向右方）滑动一个帧的位置。同时发送对该帧的确认。）TCP中采用滑动窗口来进行传输控制，滑动窗口的大小意味着接收方还有多大的缓冲区可以用于接收数据。发送方可以通过滑动窗口的大小来确定应该发送多少字节的数据。10、Architecture,体系结构/网架：网络结构ITU

15、-T HRX/HRP, 传输误码的分配；IBM SNA, 链路的可靠传输；E2E论断, 通信子网与资源子网分割ISO OSI-RM, 分层协议结构；ITU-T B-ISDN PRM, 三平面立体结构11、E2E Arguments，端到端论断：协议工程（端到端传送功能的分布）：路由选择：离不开中间节点；差错控制：可以放在中间节点；安全控制：不宜放在中间节；只要在边缘做就不放在网络中间做点到点是物理拓扑，是网络层的。E2E：端到端是网络连接，是运输层的。网络要通信，必须建立连接，不管有多远，中间有多少机器，都必须在两头（源和目的）间建立连接，一旦连接建立起来，就说已经是端到端连接了，即端到端是逻

16、辑链路，这条路可能经过了很复杂的物理路线，但两端主机不管，并不知道中间节点的存在，只认为是有两端的连接，而且一旦通信完成，这个连接就释放了，物理线路可能又被别的应用用来建立连接了。TCP就是用来建立这种端到端连接的一个具体协议。总之，一句话概括就是端到端是由无数的点到点实现和组成的。只要能放在网络边缘做的就不要放在网络中间做。E2E优点：降低网络核心复杂度，简化复杂功能；尽可能好的数据传输服务；“End-To-End”地址透明性和全球唯一地址。12、CIDR，无分类域间路由：路由与寻址CIDR（无类别域间路由，Classless Inter-Domain Routing）是一个在Interne

17、t上创建附加地址的方法，这些地址提供给服务提供商（ISP），再由ISP分配给客户。CIDR将路由集中起来，使一个IP地址代表主要骨干提供商服务的几千个IP地址，从而减轻Internet路由器的负担。将32位的IP地址划分为“网络前缀”和“主机号”两个部分。采用“斜线记法”，即在IP地址后面加上“/”，然后写上网络前缀的位数，即地址掩码中1的位数。13、STDM，统计时分复用：网络资源共享STDM，统计时分复用，网络资源共享，从统计上来说是时分复用的。为了提高TDM系统的利用率,可以使用按需分配的技术,即根据用户需求动态分配时隙,以避免每帧中出现空闲的时隙. STDM：是一种改进的TDM，能明显

18、的提高信道的利用率。各用户有了数据就随时发往集中器的输入缓存，然后集中器按顺序依次扫描输入缓存，把缓存中的数据放入STDM帧中，对没有数据的缓存就跳过，当一个STDM帧的数据放满了就发送出去。STDM帧不是固定分配时隙，而是按需动态的分配时隙。在每个时隙中还必须有用户的地址信息，这是STDM不可避免的开销。14、TCP，传输控制协议：端到端传输复用：传输层TCP（Transmission Control Protocol 传输控制协议）是一种面向连接的、可靠的、基于字节流的传输层通信协议，由IETF的RFC 793定义。在简化的计算机网络OSI模型中，它完成第四层传输层所指定的功能。在因特网协

19、议族（Internet protocol suite）中，TCP层是位于IP层之上，应用层之下的中间层。应用层向TCP层发送用于网间传输的、用8位字节表示的数据流，然后TCP把数据流分区成适当长度的报文段。之后TCP把结果包传给IP层，由它来通过网络将包传送给接收端实体的TCP层。TCP为了保证不发生丢包，就给每个包一个序号，同时序号也保证了传送到接收端实体的包的按序接收。然后接收端实体对已成功收到的包发回一个相应的确认（ACK）；如果发送端实体在合理的往返时延（RTT）内未收到确认，那么对应的数据包就被假设为已丢失将会被进行重传。TCP用一个校验和函数来检验数据是否有错误；在发送和接收时都要

20、计算校验和。TCP三次握手的过程如下：客户端发送SYN（SEQ=x）报文给服务器端，进入SYN_SEND状态；服务器端收到SYN报文，回应一个SYN （SEQ=y）ACK(ACK=x+1）报文，进入SYN_RECV状态；客户端收到服务器端的SYN报文，回应一个ACK(ACK=y+1）报文，进入Established状态。三次握手完成，TCP客户端和服务器端成功地建立连接，可以开始传输数据了。15、CAC,呼叫接纳控制：流量工程（CAC (Connection Admission Control)：连接接纳控制是异步转移模式（ATM）技术的一种流量控制标准。是网络保护自身免受免受负荷威胁的第一道

21、防线。CAC通过限制进入网络的业务量来防止网络中出现拥塞。CAC的功能可以概括为：确定接受或拒绝连接请求；选路及分配网络资源；导出业务量合约中用于UPC/NPC的业务量参数。）仅对VoIP的业务流，不影响普通数据业务；对实时性或时延敏感的业务，依据网络负载情况接收到阻止呼叫CAC方法：本地决策：依据历史经验，设置固定的允许呼叫的上限；基于测量的决策：发启方通过测量到达目标节点的丢失率和延时，决定呼叫的接续与否；基于资源的决策：计算所需与可用的资源，或者执行资源预留操作，再决定呼叫的接续与否。16、DFS（Depth First Search，深度优化搜索）：单播路由算法。对每一个可能的分支路径

22、深入到不能再深入为止，而且每个节点只能访问一次。步骤如下：（1）. 所有点 x 关联边查找完成时，返回父节点；（2）. 否则选择x的关联边e，到下一点y：如果y已查过，则e为回退边；如果y未查过，e为树边，以y替代x重复第1步。17、MST（Minimum Spanning Tree，最小生成树）：多播路由算法。一个有n个节点的连通图的生成树是原图的极小连通子图，且包含原图中所有n个结点，并且有保持图连通的最少的边，最小生成树可以用Kruskal算法或Prim算法求解。Kruskal步骤：1. 将一条权最小的边加入子图 T 中，并保证不形成圈。2. 如果当前弧加入后不形成圈，则加入这条弧，如果

23、当前弧加入后会形成圈，则不加入这条弧，并考虑下一条弧。Prim步骤：1. 不断扩展一棵子树 T = (S , F), F 为E子集，直到S包括全部顶点，得到最小生成树T。2. 每次增加一条边，使得这条边是由当前子树结点集S 及其补集S 所形成的边割集的最小边。途径Walk：图中存在关联关系的点边，交替出现的序列；迹Trail：无重复边的walk；路Path：除始末点外无重复点的walk/trail。对图G=(V,E)来说，若G的两个顶点u,v之间存在一条路径，则称u和v是连通的；若图G的任意两个顶点都是连通的，则称图G是连通的。不包括回路的连通图称为树。对于图G=(V,E)，包含了图G中所有顶

24、点的树称为生成树。树的等价定义：G=(V, E)是树；G是连通的，且|E| = |V| - 1；G无圈，且|E| = |V| - 1；G的任意两点之间，存在唯一条路；G是连通的，删除任意一边后为非连通；G无圈，增加任意一边后，正好有一个圈。设图G=(V, E)是连通图，SE，若从图G中消去属于S的所有边，则G变为一个非连通的图；而若去掉属于S的任何真子集中的边，图G仍保持连通，则称S是图的G的一个割集。即割集S是使连通图G失去连通性的最小的边的集合。18距离矢量路由控制：计算机网络通常使用动态路由算法，这些算法能找到当前网络拓扑结构中的最短路径，其中最流行的动态路由算法是距离矢量路由算法和链路

25、状态路由算法。距离矢量路由算法中，每个路由器维护一张表（一个矢量），表中列出了当前已知的到每个目标的最佳距离，以及所使用的链路。这些表通过邻居之间的相互交换信息二不断被更新，最终每个路由器都了解到达目的地的最佳链路。路由器从自己的邻居路由器得到路由信息，并将这些路由信息连同自己的本地路由信息发送给其他邻居，这样一级级的传递下去以达到全网同步。每个路由器都不了解整个网络拓扑，它们只知道与自己直接相连的网络情况，并根据从邻居得到的路由信息更新自己的路由。RIP（Routing Information Protocol，路由信息协议）、参考方法8： 工作原理：(1)路由建立:路由器运行RIP后，会首

26、先发送路由更新请求，收到请求的路由器会发送自己的RIP路由进行响应(2)距离矢量的计算:RIP度量的单位是跳数，其单位是1，也就是规定每一条链路的成本为1，而不考虑链路的实际带宽、时延等因素，RIP最多允许15跳。(3)定时器:周期更新定时器；超时定时器；清除定时器； 延迟定时器。(4)环路:当网络发生故障时，RIP网络有可能产生路由环路。可以通过水平分割、毒性反转、触发更新、抑制时间等技术来避免环路的产生。距离相等路径的解决方法（1） 先到先用；（2） 组播更新周期一半之前的优先。19、OSPF（Open Shortest Path First,开放最短路径优先）：链路状态路由。工作原理：每

27、台路由器通过使用Hello报文与它的邻居之间建立邻接关系 ；每台路由器向每个邻居发送链路状态通告(LSA),有时叫链路状态报文(LSP). 每个邻居在收到LSP之后要依次向它的邻居转发这些LSP(泛洪) ；每台路由器要在数据库中保存一份它所收到的LSA的备份，所有路由器的数据库应该相同 ；依照拓扑数据库每台路由器使用Dijkstra算法（SPF算法）计算出到每个网络的最短路径，并将结果输出到路由选择表中。OSPF的简化原理：发Hello报文建立邻接关系形成链路状态数据库SPF算法形成路由表。相同点：都是动态路由协议；都是内部路由协议（即在AS内运行）；都支持VLSM（变长子网掩码）；都是组播更

28、新，支持认证。不同点：RIP是按跳数来算路由的，OSPF是状态路由协议；两个路由协议支持跳数大小不一样。RIPOSPF默认开启自动汇总，汇总路由基于接口区域默认没有汇总，汇总路由基于区域支持接口明文或MD5认证支持区域和接口明文或MD5认证周期更新，汇聚时间长，更新不及时会有环路触发更新，快速汇聚，无环路开销以跳数为单位，不识别带宽运行SPF算法计算开销，识别带宽周期更新整张路由表，开销大区域内交换LSA构建LSDB，开销小20、LAN广播风暴：由于网络中有环路存在，造成每一帧都在网络中重复广播，获得了更多的响应，以至于像滚雪球一样，导致网络瘫痪，引起了广播风暴。要消除这种网络循环连接带来的网

29、络广播风暴可以使用STP协议（生成树协议），以网络中一台交换机为节点生成一棵转发树，而树是没有环路的，这样所有的数据都只在这棵树所指示的路径上传输，就不会产生广播风暴。STP（Spanning Tree Protocol.生成树协议）：STP：树是不包括回路（环）的连通图，对于图,包含了图G中所有顶点的树成为生成树。生成树协议拓扑结构的思路是: 不论网桥(交换机)之间采用怎样物理联接,网桥(交换机)能够自动发现一个没有环路的拓扑结构的网路，这个逻辑拓扑结构的网路必须是树型的。生成树协议还能够确定有足够的连接通向整个网络的每一个部分。所有网络节点要么进入转发状态，要么进入阻塞状态,这样就建立了整

30、个局域网的生成树。当首次连接网桥或者网络结构发生变化时，网桥都将进行生成树拓扑的重新计算。为稳定的生成树拓扑结构选择一个根桥, 从一点传输数据到另一点, 出现两条以上条路径时只能选择一条距离根桥最短的活动路径。生成树协议这样的控制机制可以协调多个网桥(交换机)共同工作, 使计算机网络可以避免因为一个接点的失败导致整个网络联接功能的丢失, 而且冗余设计的网络环路不会出现广播风暴。（1）选择根网桥：再全网中选择一个根网桥：BID最小的被选举为根网桥。（2）选择根端口：在每个非根交换机上选择根端口：路径成本最低的端口为根端口；路径成本相同，BID较小的优先极高，称为根端口。（3）选择指定端口：在每条

31、链路上选择一个指定端口，根网桥上所有端口都是指定端口。21、约束路由计算方法约束路由是一种命令驱动并具有资源预留能力的路由算法，能够和现有的 Internet 中的拓扑驱动的、逐跳的内部网关协议共存。它可以根据多个约束条件（可以是QOS 约束条件也可以是其他策略性的约束条件）计算出所有的可能路径并根据一定的优选策略选出一条最优的路径，实现网络性能的优化。（延时、带宽、跳数约束等）在一个源点到其他网络节点间首先找到一条最小跳数的路由，且该路由受约束。QoS多约束包括带宽、缓冲、延时、抖动和丢包等约束条件，为了找到一条满足多约束条件的路径，先搜索相同跳数时是否存在满足多约束条件的路径，如果没找到，

32、增加一跳继续搜索满足多约束条件的路径，不断迭代，直到找到一个折中点，使这条路径能够同时满足约束条件。流量工程：绕过网络中已知的瓶颈和阻塞点，将业务映射到现有拓扑上的业务，将成为ISP（Internet service provider）们一个非常重要的工具；ISP必须配置一个能够使他们的客户连接到他们网络上的物理拓扑结构。在网络部署完毕后，ISP必须将客户的业务流映射到网络的物理拓扑上。LSR通过对TED中的信息使用CSPF算法决定每条LSP的物理路径。CSPF（ConstrainedShortest Path First约束最短路径优先）：CSPF是一种改进的最短路径优先算法，它是一种在计算

33、通过网络的最短路径时，将特定的约束也考虑进去的算法，用于对流量的控制。属性格式(链路，代价，下一跳，可用带宽)（1）,选择拥有最大的预留带宽的路径。（2），如果二者仍然相同，选择具有最小跳数的路径。(路径中三层设备的个数)（3）, 如果仍然相同，随机选择一条（那么选择PATH列表置顶的路径）22、MMPP（Markov modulated Poisson process，马氏调制泊松过程）：是一种双随机过程，这种调制过程强度是有一个马尔科夫链来调制，当链的状态是i的时候，我们称相位为i，强度取,i=1，2N,这里N是调制链的状态数。因此MMPP是由用以调制的马尔科夫链的无穷小生成矩阵和一个泊松

34、过程的强度向量所唯一确定的。排队论(Queuing Theory)：是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法，又称随机服务系统理论，为运筹学的一个分支。23、语义透明：语义透明是业务传送的需求，要求信息在通信过程中，信息内容不被改变，在实际通信中，为了实现语义透明，需要采用很多措施，对于误码、丢失、误插，需要采用流量控制及差错控制解决，对于编码问题，采用转义控制来解决，在语义透明中，信息量是核心问题。解决方案：信道中噪声的干扰会增大误码率，可以通过增加信号功率增大信噪比；资源有限造成阻塞和拥挤，使得一些信息丢失，可以根据系统的性能合理进行流量控制。举例：电子转账要求实际无差

35、错的信息传递来保证金融信息传送的正确性，这种端到端的质量的提高可以用二种技术来实现，一种是前向差错纠错，（3选2）择多判决，发送方发送多次相同的信息则认为发送正确，称为自动重发。另一种是后向纠错，利用所谓自动重发请求协议在检测到错误后，接受方要求发送方重传。时间透明：时间透明也是业务传送的需求，要求信息在通信过程中，可以被无延迟地送到，强调通信的实时性，对通信过程的控制，产生技术性约束，在实现时间透明中，纠错和嵌入式技术，是核心问题。24、单纯形法：求解线性规划问题的通用方法。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所

36、对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。网络单纯形法：最小生成树求解。找最小生成树构成环的边，从环里面增加一条新边，减掉一条旧边，就构成了树的变化，对应于单纯形法中凸点之间的转换。找到一条合适的新边加入原有生成树，以便于这条生成树的成本降低。同时从原来的环里去除一条旧边，才能构造一棵新的生成树，因为树是不允许有环的。思路：（1）以一个初始生成树为起点（

37、该生成树包含网络的所有节点）；（2）可行树解x与生成树T相关联，且xij=0, if ij不是生成树T的边；（3）通过查找所有可行树解，得最优解。因为，加入树外的边，必然增大成本。25、易损期：易损期是吞吐性能求解的一个参数，表示在两个分组发送期间会发生冲突的时间。在下图中，第一个分组开始发送的时刻是t,分组发送时长是T，在t+T时刻，第二个分组开始发送，那么易损期就是t-T到t+T之间的2T时间间隔。26.剩余服务时间：剩余服务时间在M/G/1求解问题中常用到的一个参数，在M/G/1模型中，用户到达人数服从泊松分布，服务时间相同且为任意分布，只有一个服务员，在这种情况下，第i个顾客等待服务的

38、时间可以表示为，这里的表示在第i个顾客之前等待的顾客数目，S表示平均的服务时间，R表示服务员的剩余服务时间。如果服务员处于空闲状态，那么R=0，否则表示某一个顾客接受服务的剩余服务时间。1、面向连接服务：面向连接的服务（connection-oriented service）就是通信双方在通信时,要事先建立一条通信线路,其过程有建立连接、使用连接和释放连接三个过程。TCP协议就是一种面向连接服务的协议,电话系统是一个面向连接的模式。无连接服务：无连接服务就是通信双方不需要事先建立一条通信线路，而是把每个带有目的地址的包（报文分组）送到线路上，由系统选定路线进行传输。IP、UDP协议就是一种无连

39、接协议，邮政系统是一个无连接的模式。A.TCP是面向连接的运输层协议，在传送数据之前必须先建立连接，数据传送之后要释放连接；每一条TCP只能有两端点，即每一条TCP连接只能是点对点的；提供可靠交付的服务；提供双工通信；面向字节流。由于 TCP 要提供可靠的、面向连接的运输服务，因此不可避免地增加了许多的开销，如确认、流量控制、计时器及连接管理等f。这不仅使协议数据单元的首部增大很多，还要占用许多的处理机资源。B.UDP 是无连接的，无连接服务就是通信双方不需要事先建立一条通信线路，而是把每个带有目的地址的包（报文分组）送到线路上，由系统选定路线进行传输。发送数据之前不需要建立连接，减少了开销和

40、发送数据之前的时延；使用尽最大努力交付，即不保证可靠交付，同时不使用流量控制和拥塞控制，因此主机不需要维持具有许多参数的、复杂的链路状态表；由于UDP没有拥塞控制，因此网络出现的拥塞不会使源主机的发送速率降低；是面向报文的；支持一对一、一对多、多对一和多对多的交互通信；用户数据报只有8个字节的首部开销，比TCP的20个字节的首部要短的多。2.前向纠错的计算方法。为了提高时间透明性，用户应尽可能降低传输错误。所以在通信里面通常采用前向纠错做法，以便减少接收出错的情况。前向纠错也叫前向纠错码(Forward Error Correction简称FEC)，是增加数据通讯可信度的方法。在单向通讯信道中

41、，一旦错误被发现，其接收器将无权再请求传输。FEC 是利用数据进行传输冗长信息的方法，当传输中出现错误，将允许接收器再建数据。常用的检错方法有两类：一类是奇偶校验，另一类是循环冗余校验码（Cyclic Redundancy Check）。其基本思路是发端按照给定的规则在K个信息比特后面增加L个按照某种规则计算的校验比特，在接收端对收到的信息比特重新计算L个校验比特。比较接收到的校验比特和本地重新计算的校验比特，如果相同则认为传输无误，否则认为传输有错。(奇偶校验码是一种增加二进制传输系统最小距离的简单和广泛采用的方法。是一种通过增加冗余位使得码字中"1"的个数恒为奇数或偶数

42、的编码方法，它是一种检错码。在实际使用时又可分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验等几种。奇偶校验可描述为：给每一个码字加一个校验位，用它来构成奇性或偶性校验。可以看出，附加码元d2，是简单地用来使每个字成为偶性的。因此，若有一个码元是错的，就可以分辨得出，因为奇偶校验将成为奇性。奇偶校验编码通过增加一位校验位来使编码中1个个数为奇数（奇校验）或者为偶数（偶校验），从而使码距变为2。因为其利用的是编码中1的个数的奇偶性作为依据，所以不能发现偶数位错误。(CRC的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码也叫（N，K）码。对于一个给定的（N，K）码

43、，可以证明存在一个最高次幂为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、后向反馈的滑窗控制：在回退n帧的ARQ中，当发送方接收到接收方的状态报告指示报文出错后，发送方将重传过去的n个报文。在回退N ARQ中，发送窗口大于1，接收窗口等于1，也就是说发送方在发送完一个数据帧后，不停下来等待应答帧，而是

44、连续发送若干个数据帧，即使在连续发送过程中收到了接收方发来的应答帧，也可以继续发送，但是，一旦某帧发生错误，必须重新发送该帧及其后的n帧。最大窗口大小为2n-1。3、比特填充：在HDLC的帧结构中，若在两个标志字段之间的比特串中，碰巧出现了和标志字段F（01111110）一样的比特组合，那么就会误认为是帧的边界。为了避免出现这种情况，HDLC采用零比特填充法使一帧中两个F字段之间不会出现6个连续1。零比特填充法的具体做法是：在发送端，当一串比特流尚未加上标志字段时，先用扫描整个帧。只要发现5个连续1，则立即填入一个0。因此经过这种零比特填充后的数据，就可以保证不会出现6个连续1。在接收一个帧时

45、，先找到F字段以确定帧的边界。接着再对其中的比特流进行扫描。每当发现5个连续1时，就将这5个连续1后的一个0删除，以还原成原来的比特流。这样就保证了在所传送的比特流中，不管出现什么样的比特组合，也不至于引起帧边界的判断错误。4、Aloha随机多址接入控制： 若一个空闲的节点有一个分组到达，就立即发送该分组，并期望不会和其他节点发生碰撞。分为纯ALOHA和时隙ALOHA。纯ALOHA：“想说就说”。网络中多个用户共用一个信道，采用竞争方式，各自随机的访问系统。站点只要产生帧，就立即发送到信道上；规定时间内若收到应答，表示发送成功，否则等待一段随机时间，然后重发；若再次冲突，则再等待一段随机时间，

46、直到发送成功为止。由于产生冲突现象，使传输效率或吞吐率降低。只有在易受破坏区间（易损期）内没有其他分组传输，该分组才能成功传输。时隙ALOHA：将时间轴划分为若干个时隙（宽度等于一个分组的传输时间），各节点只能在时隙的开始时刻才能发送分组。（假设系统有无穷多个节点，重传的时延足够随机，重传分组和新到达分组合成的分组流是到达率为G的Poisson过程，则，G=t，在t时长内，t是时间段，指平均的发生事件的数量。在易损期内没有其他分组传输的概率，即k=0时的概率，对于纯ALOHA来说易损期为2T，P(0)=e-2G，吞吐量S=Ge-2G，求导后可得最大通过率约为0.184，G=0.5时；对于时隙A

47、LOHA最大通过率约为0.368，G=1时。）。5、CSMA/(CD/CA)随机多址接入控制：（1）CD: (边听边说)首先检查线路上是否有其他主机信号在发送:如果有，说明其他主机在发送，自己利用退避算法等一会再试图发送。如果没有其他主机信号，自己则将数据发出去，同时不断监听线路，如果检测到有其他信号，则自己发送一个阻塞信号，通知其他节点停止发送数据，自己也要停止发送数据，此时，再利用退避算法等一会再试图发送。（2）CA: (先听再说)首先检测介质是否空闲，若是介质为空闲时，送出RTS信号，接收端收到RTS信号后，将会送响应信号CTS，当发射端收到CTS包后，随即开始发送数据包。接收端收到数据

48、包后，将以包内的CRC校验码来检验包数据是否正确，若是检验结果正确时，接收端将响应ACK包，告知发射端数据己经被成功地接收。当发射端没有收到接收端的ACK包时，将认为包在传输过程中丢失，将重新发送数据。6、电话呼叫的固定等级制路由选择： 1.星型汇接：构成基干路由。由同一交换区内相邻等级交换中心的低呼损电路群所组成，在该路由上的话务量不允许溢出到其他路由。2.相邻直连：提供高效直达路由。它是由任意两个等级交换中心之间高效电路群所组成的路由，可以全部或部分地旁路基干路由，在该路由上的话务量可以溢出到其他路由。 1）路由选择的基本原则：首先，路由选择应确保传输质量和信令信号的可靠传输。最长的串接段

49、不应超过7段。其次，路由选择方法应有明确的规律性，不出现死循环。第三，不应使网络设计或对交换设备的要求过于复杂，首选串接段数少的路由。最后，能在低等级网络中疏通的话务量，尽量不在高等级交换中心疏通。2）等级制路由选择规则：在我国最早实行的路由选择规则规定：一个交换中心呼叫某一目标局的路由，其中路径数最大为3个；有高效直达路由时，路由选择顺序依次为高效直达路由、迂回路由、基干路由；无高效直达路由时，路由选择顺序为跨级或跨区的路由、基干路由；一般在受话区自下(下级局)而上(上级层)，发话区自上而下；在跨区路由中，连接该路由的两个交换中心的等级差不应超过一级，但在选择跨级路由时，允许连接该路由上的两

50、个交换中心的等级差不超过二级；路由选择过程中，遇到低呼损路由时，不再溢出，路由选择终止。7、距离矢量路由控制： 路由器从自己的邻居路由器得到路由信息，并将这些路由信息连同自己的本地路由信息发送给其他邻居，这样一级级的传递下去以达到全网同步。每个路由器都不了解整个网络拓扑，它们只知道与自己直接相连的网络情况，并根据从邻居得到的路由信息更新自己的路由。由于每一个路由器都要维护从它自己到其他每一个目的网络的距离记录，即距离向量，相邻的路由器间交换的也是各自的距离向量，最后各自根据路由器的距离向量来更新自己的距离向量，因此这类路由选择算法被称为距离向量路由选择算法。RIP协议的距离向量算法：收到相邻路

51、由器（其地址为 X）的一个路由更新报文：(1) 先修改此报文中的所有项目：把“下一跳”字段中的地址都改为X，并把所有的“距离”字段的值加1。每一个项目都有三个关键数据，即：到目的网络N，距离是d，下一跳路由器是X。(2) 若原路由表中没有目的网络N，则把该项目添加到路由表中。否则，查看路由表中目的网络为N的表项，若其下一跳是X，则把收到的项目替换原项目。否则，若收到的项目中的距离d小于路由表中的距离，则进行更新，否则什么也不做。(3) 若180秒（默认）没有收到某条路由项目的更新报文，则把该路由项目记为无效，即把距离置为16（距离为16表示不可达），若再过一段时间，如120秒，还没有收到该路由

52、项目的更新报文，则将该路由项目从路由表中删除。(4) 若路由表发生变化，向所有相邻路由器发送路由更新报文。(5) 返回。RIP协议让互联网中的所有路由器都和自己的相邻路由器不断交换路由信息，并不断更新其路由表，使得从每一个路由器到每一个目的网络的路由都是最短的（即跳数最少）。虽然所有的路由器最终都拥有了整个自治系统的全局路由信息，但由于每一个路由器的位置不同，它们的路由表当然也应当是不同的。RIP 协议采用的是距离向量路由选择算法，三个要点（1）仅和相邻路由器交换信息。 （2）交换的信息是当前本路由器所知道的全部信息，即自己的路由表。 （3）按固定的时间间隔交换路由信息（即周期性更新），例如，

53、每隔 30 秒。然后路由器根据收到的路由信息更新路由表。为加快协议的收敛速度，当网络拓扑发生变化时，路由器也及时向相邻路由器通告拓扑变化后的路由信息（即触发更新）。路由器收到相邻路由器发送给他的路由信息（即距离向量）后，判断从哪个相邻路由器或直接到某个网络的距离最近，从而找出每个目的网络的最短距离和下一跳路由器，最后更新路由表。RIP 协议的优缺点 RIP 协议最大的优点就是实现简单，开销较小。缺点：RIP 限制了网络的规模，它能使用的最大距离为 15（16 表示不可达）。路由器之间交换的路由信息是路由器中的完整路由表，因而随着网络规模的扩大，开销也就增加。“坏消息传播的慢”，使更新过程的收敛

54、时间过长。当网络出现故障时，要经过比较长的时间才能将此信息传送到所有的路由器。8、链路状态路由控制OSPF 协议即开放最短路径优先。OSPF最主要的特征就是使用分步式的链路状态路由选择算法，三个要点：（1）向本自治系统中所有路由器发送信息，这就是路由器通过所有输出端口向它所有相邻的路由器发送信息。而每一个相邻路由器又再将此信息发往其所有的相邻路由器(但不再发送给刚刚发来信息的那个路由器)。这样，最终整个区域中所有的路由器都得到这个信息的一个副本。（2）发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。所谓“链路状态”就是说明本路由器都和哪些路由器相邻，以及该链

55、路的“度量”。（3）只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息。OSPF的其他特点：OSPF对不同的链路可根据 IP 分组的不同服务类型 TOS 而设置成不同的代价。因此，OSPF 对于不同类型的业务可计算出不同的路由。如果到同一个目的网络有多条相同代价的路径，那么可以将通信量分配给这几条路径。这叫作多路径间的负载平衡。所有在 OSPF 路由器之间交换的分组都具有鉴别的功能。支持可变长度的子网划分和无分类编址 CIDR。每一个链路状态都带上一个32位的序号，序号越大状态就越新。OSPF 还规定每隔一段时间，如30分钟，要刷新一次数据库中的链路状态。 由于一个路由器的链路状

56、态只涉及到与相邻路由器的连通状态，因而与整个互联网的规模并无直接关系。因此当互联网规模很大时，OSPF协议要比距离向量协议 RIP 好得多。 OSPF 没有“坏消息传播得慢”的问题，其响应网络变化的时间小于100 ms。 链路状态路由：链路状态路由算法中，每个节点将它所知的路由信息传达给其邻近节点。首先，一个节点收集与邻节点相连的每条链路的状态信息。例如，链路的比特率、通过链路发送报文的延迟时间、缓冲区中报文的数目以及链路的可靠性等等，诸如此类的信息。这些都是决定链路费用的因素。其次，节点为每个连接建立一个链路状态报文。这类报文指出通过那条链路相连的两个节点和它收集的链路信息。然后节点将报文发

57、送给每个邻节点。再者，收到链路状态报文的节点将它转发给所有的其它邻近节点。最后，由于链路状态报文在节点间交换，最终，每个节点都可以知道网络拓扑结构，以及网络节点间的链路状态和费用。只要每个节点定期地建立并发送包含当前信息的链路状态报文，这种方法就能对网络费用的增长和下降作出响应。它还能对链路失效作出反应。此外，如果一条链路失效，所有的节点能通过链路状态报文最终了解这一情况。因此，它们可以确定新路径来避开无效链路。9、Patricia路由表查找Patricia前缀树(Patricia Trie)PATRICIA算法被广泛应用在信息检索系统中，检索信息时是逐比特(或字符)进行的，树的所有数据信息都

58、存放在叶子PATRICIAtrie消除了所有的单分支节点,所有非叶子节点的分支都为2,PATRICIAtrie是深度最浅的trie。PATRICIAtrie通过消除单分支中间节点大大压缩了trie的深度,压缩搜索路径能够减少搜索时间1PATRICIA算法在许多领域都得到了广泛的应用。PATRICIA算法非常适合状态表操作,主要因为PATRICIAtrie是深度最浅的trie;支持定长匹配;算法的时间性能与数据宽度无关,非常适合数据宽度很大的情况;。10、DTMF信号的带内和带外传送方法双音多频信号（DTMF）双音多频，由高频群和低频群组成，高低频群各包含4个频率。一个高频信号和一个低频信号叠加组成一个组合信号，代表一个数字。DTMF信号有16个编码。利用DTMF信令可选择呼叫相应的对讲机。即拨号音。，电话系统中电话机与交换机之间的一种用户信令