《通信网理论教学课件》2

《《通信网理论教学课件》2》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、DFS：深度优先查找，单播路由算法。DFS在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点wl；再从wl出发，访问与Ml邻接但还没有访问过的顶点w2；然后再从W2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。MST:是指边的重暈Z和最小的生成

2、树。最小生成树是指对于图G二(V,E)包含了图G屮所有顶点的树。用Kruskal算法构造MST：选择所有的顶点作为单顶点的fragment(树枝，MST的任意子树),在所有的链路中选择具有最小重量且不会形成回路的链路添加到当前的fragment中，每次迭代仅添加一条链路。最终即生成MST。用prime算法：不断扩展一棵子树T=(S,F),F为E子集，直到S包括•全部顶点，得到最小生成树T;每次增加一条边，使得这条边是由当前子树结点集S及其补集S所形成的边割集的最小边。RIP：路由信息协议，每个RIP路由器都保

3、存了一张路由表，每一项对应着一个目的地，英屮每项包括了目的地的IP地址，到FI的地的路径距离的度量、到FI的地的路径的下一个路rh的IP地址，路由改变标志以及和这条路由有关的一些计时器。RIP是一个简单的距离矢量路由协议。距离矢量路由算法中，每个路由维护一张矢量表，表中列出了当前已知的到每个目标的最佳距离以及所使用的线路。通过在邻居之间相互交换信息，路由不断更新它们内部的表。收到相邻路由器(其地址为X)的每一个RIP报文：⑴先修改此RIP报文中的所有项目：将“下一跳”字段中的地址都改为X,并将所有的“距离”字

4、段的值加(2)对修改后的RIP报文中的每一个项目，重复以下步骤：若项目中的目的网络刁；在路由表中，则将该项目添加到路由表中。否则，若下一跳字段给出的路由器地址是同样的，则将收到的项目替换原路rti表甲的项目。否则，若收到的项目中的距离小于路由衷中的距离，则进行更新。否则什么也不做。⑶若3分钟还没有收到相邻路rh器的更新路rh表，则将此相邻路rh器记为不可达的路由器，即将距离置为16。(4)返回。OSPF:使用分布式链路状态协议，链路状态算法发送路由信息到互联网上所有的节点，然后对每个路由器，仅发送它的路由表中

5、描述了其自身链路状态的那一•部分。链路状态路由算法的思想(1)发现邻节点，并获取它们的地址；(2)测量到达每一个邻节点的时延或成本;(3)构造一个分组来通知它所知道的所有路由信息；(4)发送该分组到所有其他节点；(5)计算到所有其他节点的最短路径。STP生成树协议，其基本原理是，通过在交换机之间传递一种特殊的协议报文，网桥协议数据单元(BridgeProtocolDataUnit,简称BPDU),来确定网络的拓扑结构。该协议的原理是按照树的结构来构造网络拓扑，消除网络中的坏路，避免rh丁-环路的存在而造成广播

6、风:暴问题。生成树协议最主要的应用是为了避免局域网中的单点故障、网络回环，解决成环以太网网络的“广播风暴”问题，从某种意义上说是一种网络保护技术，可以消除由于失误或者意外带来的循环连接约束最短路径优先(CSPF)算法来决定每条LSP(layerserverprovder)的物理路径。CSPF是一种改进的最短路径优先算法，它是一种在计算通过网络的最短路径吋，将特定的约束也考虑进去的算法，用于对流量的控制。MMPP:马氏过程：设一个随机过程X(t)•如果对于任意的时间序列tl=3,在给定随机

7、变量X(tl)=xl,X(t2)=x2,•••,X(tn_l)=xn_l语义透明、时间透明；业务传送需求语义透明性：是指来自用户的信息在通信过程屮不被改动，信息交互双方或多方Z间，不因交互手段改变各白的真实的意思。1•要求信息通信，不改变信息的内容2.误码，丢失，误插,采用流量控制及差错控制解决3.编码，采用转义控制解决4•信息量是核心问题解决方案：信道中噪声的干扰会增大误码率，可以通过增加信号功率增大信噪比；资源有限造成阻塞和拥挤，使得一些信息丢失，可以根据系统的性能合理进行流量控制。举例：电子转账要求实际

8、无差错的信息传递来保证金融信息传送的止确性，这种端到端的质量的提高可以用二种技术来实现，一种是前向差错纠错，(3选2)择多判决，发送方发送多次相同的信息则认为发送正确，称为自动重发。另一种是后向纠错，利用所谓自动重发请求协议在检测到错误后，接受方要求发送方重传。时间透明性：可以定义为没有时延及时延抖动，信息交互双方，在对接受的时间范围内，收到对方的信息与木地或面对面交流一样。1.要求信息通信，无延误