网站建设考试重点,dw软件是做什么用的,展览制作设计公司,WordPress协会学院主题模板系列文章目录
什么是计算机网络#xff1f; 什么是网络协议#xff1f; 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能#xff08;1#xff09;——速率、带宽、延迟 计算机网络性能#xff08;2#xff09;…系列文章目录
什么是计算机网络 什么是网络协议 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能1——速率、带宽、延迟 计算机网络性能2——时延带宽积、丢包率、吞吐量/率 计算机网络体系结构概念 OSI参考模型基本概念 OSI参考模型中非端-端层物理层、数据链路层、网络层功能介绍 OSI参考模型中端-端层传输层、会话层、表示层、应用层功能介绍 TCP/IP参考模型基本概念包括五层参考模型 网络应用的体系结构 网络应用进程通信 网络应用对传输服务的需求 Web应用之HTTP协议涉及HTTP连接类型和HTTP消息格式 Cookie技术 Web缓存/代理服务器技术 传输层服务概述、传输层 vs. 网络层 传输层——多路复用和多路分用 传输层——UDP简介 传输层——可靠数据传输原理之Rdt协议 传输层——可靠数据传输之流水线机制与滑动窗口协议 传输层——TCP特点与段结构 传输层——TCP的可靠数据传输 TCP连接管理图解三次握手和四次挥手 传输层——拥塞控制原理与解决方法 TCP的拥塞控制机制 网络层服务与核心功能 网络层服务模型——虚电路网络 网络层服务模型——数据报网络 Internet网络的网络层——IP协议之IP数据报的结构 IP分片 IP编址与有类IP地址 IP子网划分与子网掩码 CIDR与路由聚合 DHCP协议 网络地址转换(NAT) ICMP互联网控制报文协议 IPv6简介 系列文章目录网络抽象路由算法分类链路状态路由算法说明示例 网络抽象
我们可以将网络抽象为一个图。图是由一些结点和边构成的拓扑结构。图的抽象在网络领域应用很广泛。 图: G (N, E) 网络中的路由器会被抽象为图中的结点。N 路由器集合 { u, v, w, x, y, z } 路由器之间的链路抽象为图中的边。E 链路集合 { (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) } 权值代表网络中链路的费用或者说距离、代价。描述了这个链路的成本大小。比如图中的c(w, z) 5
我们在描述一个路径的费用的时候就是从源到目的经过的每段链路的费用之和。一般原则是费用越小路径越好。所以在路由的过程中关键问题就是源到目的如u到z的最小费用路径是什么。为了解决这样的问题需要网络中每个路由器运行路由算法即寻找最小费用路径的算法。
路由算法分类
对于不同的分类标准分类是不一样的。
静态路由 vs 动态路由 静态路由即手工配置的路由。这种路由更新慢但是优先级高动态路由基于某些路由算法动态地计算而来。这种路由更新快可以实现定期更新。优点在于能够及时响应链路费用或网络拓扑变化 全局信息 vs 分散信息 全局信息路由算法或路由协议进行计算的时候需要掌握完整的网络拓扑和链路费用信息。换句话说掌握那张抽象的图。最具代表性也是被广泛使用的是链路状态(LS)路由算法分散(decentralized)信息路由器只掌握物理相连的邻居以及链路费用在这个基础上通过邻居间信息交换和多次的迭代计算以后就可以找到到达目的网络最佳的路由信息。比如距离向量(DV)路由算法
链路状态路由算法
说明
链路状态路由算法基于Dijkstra迪杰斯特拉 算法来设计。
首先需要考虑的问题就是结点如何掌握整张图和链路费用。那就要求每个路由器构造一个链路状态分组然后广播出去这个分组包括这个路由器与之相连的所有邻居路由器的ID以及与这些路由器直接相连的链路的费用。这样任何一个路由器最后都会集齐网络中所有结点广播的链路状态分组然后路由器就可以基于这些信息构造网络完整的拓扑和费用信息。这样每一个路由器就可以基于它所构造的网络这张图去求最短路径了。
通过Dijkstra 算法k次迭代后就能得到到达k个目的结点的最短路径
这里给出Dijkstra 算法需要用到的一些符号及其含义
c(x,y) : 结点x到结点y链路费用如果x和y不直接相 连则为∞D(v) : 从源即计算结点到目的v的当前路径费用值。注意不一定是最短的p(v) : 沿从源到v的当前路径v的前序结点N’ : 已经找到最小费用路径的结点集合
下面来看一下这个算法的伪代码 示例
通过一个例子看一下这个过程 初始化从u结点开始。v、w、x都与u相邻所以它们的D值和p都能够准确确定。而y、z与u不相邻记为∞ 进入循环。目前除了u以外的结点都不在N‘ 中并且D(w)是最小的所以将w加入N‘ 中。然后更新w的所有邻居。可以看到到达v的路径费用原先是7如果通过w到达v就是6以此类推更新与w相邻的结点路径的费用 以此类推经过5次迭代就找到了从u到其他结点的最短路径。这里u到v的最短路径大小是6到w是3到x是5……
下面再看一个例子 大家可以自行计算一下。最终u就可以获得一个最短路径树 然后将这个树反映在转发表中。比如这个例子中如果要把数据送到v就从(u,v)这条链路发送而发向x、y、w、z的数据都要从(u,x)这条链路发送。 但是使用链路状态路由算法可能会产生震荡(oscillations)现象。因此使用这种算法的路由协议往往会采用一些机制去避免这种现象的发生。
