工程硕士班《通信网理论基础》.ppt

通信网理论基础 第三部分 图论基础 与 应用; 基本概念;图的一个例子;图的邻接矩阵;邻接矩阵一例;Terminology;简单路径 (1);简单图 (2);有向图;加权图;加权图与邻接矩阵;V1 至 V6 的路径距离 和 路径长度;树;树中顶点的等级关系; 树的例; 子图;生成树;;生成树的“先广搜索”算法; 例; 上例的图示;Avoiding Loops;Avoiding Loops;Spanning Tree Algorithm;LAN1;LAN1;LAN1;最短距离路径的距离;最短长度路径; 路由决策; 一跳的代价; Dijkstra 算法 (1) ?? 定义;Dijkstra 算法(2) – 步骤;Dijkstra 算法原理图示; Dijkstra’s 算法 (3) – 说明; Dijkstra 算法 用于例图;Bellman-Ford 算法 (1) – 定义;Bellman-Ford 算法 (2) – 步骤;Bellman-Ford Algorithm (3) –说明;Bellmin-Ford 算法原理图示;Bellman-Ford 算法用于例图; Dijkstra 和 Bellman-Ford  算法 的运算结果;比较所需要的信息 – Bellman-Ford 算法;比较两种算法所需要的信息 -------------Dijkstra 算法; 其他事项;;Autonomous Systems;AS Number;Inter and Intra Domain Routing;Outline;RFC 1058 RIP based on routed, “route d”, distributed in BSD UNIX Uses the distance-vector algorithm Runs on top of UDP, port number 520 Metric: number of hops Max limited to 15 suitable for small networks (local area environments) value of 16 is reserved to represent infinity small number limits the count-to-infinity problem ;RIP Operation;RIP Protocol;;Command: request or response Version: v1 or v2 One or more of: Address Family: 2 for IP IP Address: network or host destination Metric: number of hops to destination Does not have access to subnet mask information Cannot work with variable-length subnet masks RIP v2 (RFC 2453): Subnet mask, next hop, routing domain can work with CIDR still uses max cost of 16;Outline;Used in OSPF to distribute link state (LS) information Forward incoming packet to all ports except where packet came in Packet eventually reaches destination as long as there is a path between the source and destination Generates exponential number of packet transmissions Approaches to limit # of transmissions: Use a TTL at each packet; won’t flood if TTL is reached Each router adds its identifier to header of packet before it floods