计算机网络原理实验八、Link States Algorithm的实现

计算机网络中的路由算法路由算法在计算机网络中起着关键的作用，它用于确定数据包在网络中的传输路径。

根据不同的网络拓扑和需求，有多种不同的路由算法被应用。

本文将介绍几种常见的路由算法。

1. 距离矢量算法（Distance Vector Algorithm）距离矢量算法是一种分布式的路由算法，每个节点在路由表中记录到达目的节点的距离向量。

节点之间通过交换距离向量信息来更新路由表，并且通过Bellman-Ford算法来计算最短路径。

该算法简单易实现，但是在大型网络中容易产生计数到无穷大的问题，即由于链路故障等原因产生的无限循环。

2. 链路状态算法（Link State Algorithm）链路状态算法是一种集中式的路由算法，每个节点都会收集与自身相连的链路状态信息，并通过最短路径算法（如Dijkstra算法）计算出到达其他节点的最短路径。

然后，每个节点都将自己的链路状态信息广播给所有其他节点，使得每个节点都有完整的网络拓扑和链路状态信息。

该算法需要节点之间频繁的广播和计算，但是能够保证收敛，即要么找到最短路径，要么不进行路由。

3. 路径向量算法（Path Vector Algorithm）路径向量算法可以看作是距离矢量算法和链路状态算法的结合，它通过回退进行路径检测和避免计数到无穷大的问题。

每个节点在路由表中记录到达目的节点的路径和向量信息，通过交换路径向量信息来更新路由表。

在计算最短路径时，路径向量算法使用类似链路状态算法的Dijkstra算法，但是在寻找路径时，会检查前面的节点是否已经在路径中出现，以避免产生环路。

4. 队列距离矢量算法（Queue Distance Vector Algorithm）队列距离矢量算法是距离矢量算法的一种改进算法，主要解决计数到无穷大问题。

该算法引入了队列和计数器，通过计数器和链路状态信息来确定数据包是否进入队列。

每个节点在路由表中记录到达目的节点的距离向量和队列的长度。

计算机⽹络实验⼋计算机⽹络实验指导书昆明理⼯⼤学信⾃学院实验⼋：计算机⽹络协议分析实验⼀、实验⽬的：了解各种协议的格式与⼯作机制，学习使⽤Wireshaek协议分析⼯具。

通过eNSP抓包⼯具，分析所获取报⽂的内容。

⼆、实验原理：1.TCP协议通讯的双⽅由IP地址和端⼝号标识。

32位序号、32位确认序号、窗⼝⼤⼩。

4位⾸部长度和IP协议头类似，表⽰TCP协议头的长度，以4字节为单位，因此TCP协议头最长可以是4x15=60字节，如果没有选项字段，TCP协议头最短20字节。

URG、ACK、PSH、RST、SYN、FIN是六个控制位。

16位检验和将TCP协议头和数据都计算在内。

2.UDP协议3.IP协议IP数据报的⾸部长度和数据长度都是可变长的，但总是4字节的整数倍。

对于IPv4，4位版本字段是4。

4位⾸部长度的数值是以4字节为单位的，最⼩值为5，也就是说⾸部长度最⼩是4x5=20字节，也就是不带任何选项的IP⾸部，4位能表⽰的最⼤值是15，就是说⾸部长度最⼤是60字节。

8位TOS字段有3个位⽤来指定IP数据报的优先级（⽬前已经废弃不⽤），还有4个位表⽰可选的服务类型（最⼩延迟、最⼤呑吐量、最⼤可靠性、最⼩成本），还有⼀个位总是0。

总长度是整个数据报的字节数。

每传⼀个IP数据报，16位的标识加1，可⽤于分⽚和重新组装数据报。

3位标志和13位⽚偏移⽤于分⽚。

TTL（Time to live)是这样⽤的：源主机为数据包设定⼀个⽣存时间，⽐如64，每过⼀个路由器就把该值减1，如果减到0就表⽰路由已经太长了仍然找不到⽬的主机的⽹络，就丢弃该包，因此这个⽣存时间的单位不是秒，⽽是跳（hop）。

协议字段指⽰上层协议是TCP、UDP、ICMP还是IGMP。

然后是校验和，只校验IP⾸部，数据的校验由更⾼层协议负责。

IPv4的IP地址长度为32位。

4.ICMP报⽂类型ICMP全称Internet Control Message Protocol（⽹际控制信息协议）。

路由算法之链路状态路由算法LS 把我与谁连接告诉所有的路由器，那么所有的路由器就都具有了⼀幅⽹络图由这副图计算每条具体的路径所以实现的关键在于链路状态信息的可靠分发根据链路状态信息计算路由步骤1. 发现邻接点, 获得邻居的⽹络地址.每⼀个点对点链路发送 HELLO 分组邻居返回响应多个路由器通过LAN连接,路有器的⼀个端⼝有多个邻居,如何抽象?把 LAN 当做⼀个节点 LAN上指定的⼀个路由器来运⾏路由协议2. 测量到每⼀个邻居的代价发送⼀个 ECHO 分组，邻居迅速返回响应测量往返时间, / 2即是到邻居的延迟多测⼏次取平均值3. 构造链路状态分组（邻居信息）LSP (Link-State Packet，链路状态分组)和路由计算相关的项产⽣ LSP节点的ID直接相连的邻居列表到每个邻居的代价和可靠性相关的项序号（ sequence number），区分新旧消息年龄（ age）更新计时器超时通常⼏⼗分钟⽹络变化时直接连接的链路断开可以⽤链路层协议检测直接连接的邻居下线通过定期发送 “hello” 检测4. 分发链路状态包（发送给所有其它路由器）.⽬的：保证所有参加路由的节点得到其它所有节点的链路状态信息的⼀个拷贝⽅法：可靠泛洪（Reliable Flooding）将 LSP发送到所有直接相连的链路收到 LSP 的节点将它转发到所有其它链路存储每个节点的最新 LSP向所有相邻节点转发每个LSP，但不发送给发来该LSP的节点相邻路由器之间有确认和重传的机制控制泛洪规模Packet: 包含⼀个序号保证拥有最新 copy序号存在的问题问题1：序号回转解决：使⽤⼤的序号空间，如32bit问题2：⼀个路由器崩溃了, 将丢失所有序号记录，恢复后从0开始，将会拒绝正常分组问题3：序号本⾝被破坏解决增加 age域 (TTL) 每经过⼀个路由器，age递减 Age=0，抛弃Router: 记录见过的分组 ( router, sequence number )如果 LSP 是 duplicate , 就丢弃Duplicate: LSP序号 is lower当⼀个 LSP 到来时, it wait a short while, ⽽不是⽴即转发当⼀个 LSP 到来, 先放到⼀个保留区等⼀会有新 LSP 到来, ⽐较序号相等，是重复分组，不再转发不同，⽐较年龄，丢弃旧的分组5. 计算到每个节点的最短路径优缺点优点没有慢收敛问题，对坏消息响应迅速代价存储空间开销存储所有的链路状态分组CPU 开销任何拓扑变化都要重新计算最⼩代价树⽐较和 DV对⽐，都要交流信息DV（距离向量）Who: 邻居What：距离向量，可能有不确定（道听途说）的消息使⽤最短路径优先算法，算法复杂度为O(n^2) n个结点（不包括源结点），需要n*(n+1)/2 次⽐较使⽤更有效的实现⽅法，算法复杂度可以达到O(nlogn) 可能存在路由振荡（oscillations）结点会⼴播错误的链路开销每个结点只计算⾃⼰的路由表LS（链路状态）Who: 所有路由器What ：LSP，仅通告确定的消息收敛时间不定可能会出现路由循环结点会⼴播错误的路径开销每个结点的路由表被别的结点使⽤，错误会传播到全⽹。

计算机组成原理实验八简单模型计算机实验关键信息项：1、实验目的2、实验设备3、实验原理4、实验步骤5、数据记录与分析6、注意事项7、故障处理8、实验结果评估标准11 实验目的本实验旨在通过构建和操作简单模型计算机，深入理解计算机组成原理中的核心概念，包括数据存储、运算处理、指令执行等，培养学生的实际动手能力和对计算机系统的综合理解能力。

111 具体目标1111 掌握简单模型计算机的基本结构和工作原理。

1112 熟悉各种指令的编码和执行过程。

1113 能够运用所学知识设计和实现简单的计算任务。

12 实验设备121 硬件设备计算机主机、实验箱、连接线等。

122 软件工具特定的模拟软件、编程环境等。

13 实验原理131 模型计算机结构包括运算器、控制器、存储器、输入设备和输出设备等主要部件，以及它们之间的连接和协同工作方式。

132 指令系统定义了各种操作指令的格式、功能和编码方式。

133 数据存储与传输说明数据在存储器中的存储方式和在各部件之间的传输机制。

14 实验步骤141 连接实验设备按照正确的方式将计算机主机与实验箱等设备进行连接，并确保连接稳定可靠。

142 启动软件工具打开相应的模拟软件和编程环境，进行初始化设置。

143 设计指令序列根据实验要求，设计一系列的指令来完成特定的计算任务。

144 输入指令到模型计算机通过编程环境将指令输入到模型计算机的存储器中。

145 启动模型计算机运行设置相关参数，启动模型计算机执行指令序列。

146 观察运行过程和结果密切观察模型计算机在执行指令过程中的各种状态变化，以及最终的输出结果。

15 数据记录与分析151 记录实验过程中的关键数据包括指令的执行时间、存储器的状态变化、运算结果等。

152 对数据进行分析对比预期结果，分析实验数据的准确性和合理性，找出可能存在的偏差和错误原因。

16 注意事项161 设备操作规范严格按照设备的操作说明进行连接和使用，避免因不当操作造成设备损坏。

链梯法和b-f法链梯法（Link State Algorithm）和B-F法（Bellman-Ford Algorithm）是两种常用的网络路由算法，用于在计算机网络中寻找最短路径或最佳路径。

虽然两者在算法基本原理上有所不同，但都是为了解决相同的问题，即在网络中找到最佳的路径。

链梯法是一种逐步迭代的算法，其基本思想是将整个网络划分为多个子网，并通过交换路由信息来构建网络图。

每个路由器根据收集到的链路状态信息，计算出到达目标节点的最佳路径，并将该路径信息广播到整个网络中。

最后，每个节点记录下到达目标节点的最佳路径，并根据该路径来进行数据包转发。

链梯法的优点是收敛速度快、计算复杂度低，但同时也存在着一些问题，如计算延迟大、存储开销大等。

B-F法是一种迭代更新的算法，其基本思想是通过多次迭代更新网络中每个节点的最短路径信息，直到收敛为止。

B-F法通过比较每个节点的当前最短路径和新发现的路径，选择其中较短的路径作为节点的最短路径，并逐渐将最短路径信息从源节点向目标节点进行传播。

B-F法的优点是适用于不同类型的网络，计算复杂度相对较低，但也存在着一些问题，如慢收敛、计算开销大等。

在实际应用中，选择使用链梯法还是B-F法需要根据具体的网络场景和需求来确定。

一般来说，链梯法适用于网络规模较大、带宽充足且稳定的网络，它能够快速进行路径计算，并具有较好的收敛性能。

而B-F法适用于网络规模较小、带宽较为有限或不稳定的网络，它能够适应网络拓扑结构的动态变化，但收敛速度相对较慢。

总结来说，链梯法和B-F法是两种常用的网络路由算法，它们都能够找到最短路径或最佳路径。

在选择具体算法时，需要考虑网络规模、带宽情况、网络拓扑结构的动态变化等因素，根据具体需求和场景来确定最合适的算法。

通过深入理解和研究这两种算法，可以更好地理解和应用网络路由技术，提高计算机网络性能和效率。

简述链路状态协议的工作原理。

链路状态协议（Link State Protocol）是一种网络路由协议，用于在计算机网络中的路由器之间交换路由信息，从而建立网络拓扑图并计算最佳路径。

它的工作原理是通过每个路由器收集并广播网络中的链路状态信息，然后根据这些信息计算出最短路径。

链路状态协议的工作原理可以分为以下几个步骤：1. 链路状态信息收集：每个路由器都会周期性地发送链路状态请求消息，以收集相邻路由器的链路状态信息。

这些信息包括链路的状态、带宽、延迟等。

2. 链路状态信息传播：收集到链路状态信息后，路由器会将其打包成链路状态更新消息，并通过广播或单播的方式发送给所有相邻路由器。

这样，每个路由器都能得到整个网络中的链路状态信息。

3. 构建网络拓扑图：每个路由器收集到链路状态更新消息后，会根据这些信息构建网络的拓扑图。

拓扑图记录了网络中所有的路由器和链路，并标注了它们之间的连通关系和代价。

4. 最短路径计算：在网络拓扑图构建完成后，每个路由器都可以利用该图计算出到达目的地的最短路径。

这通常使用Dijkstra算法来实现，该算法会根据链路的代价和距离来计算最短路径。

5. 路由表更新：最后，每个路由器根据最短路径计算结果更新自己的路由表，以便将数据包发送到正确的下一跳路由器。

链路状态协议的工作原理具有以下特点：1. 分布式计算：每个路由器都独立地计算最短路径，而不需要一个中心节点来协调。

这种分布式计算的方式能够提高网络的可扩展性和鲁棒性。

2. 实时更新：链路状态协议中的路由器会周期性地收集和传播链路状态信息，以保持网络的实时性。

这样，当网络中的链路发生变化时，路由器能够及时更新最短路径，以适应变化后的网络拓扑。

3. 基于全局信息：链路状态协议中的每个路由器都拥有整个网络的链路状态信息，这使得它能够全局优化路由路径。

与之相比，距离矢量协议则只知道与自己相邻的路由器的信息，无法进行全局优化。

4. 成本自适应：链路状态协议中的每个链路都可以具有不同的代价，代表了该链路的带宽、延迟等性能指标。

云南大学软件学院实验报告实验八、Link States Algorithm的实现1．实验目的：通过编程模拟实现LSA.2．实验环境：软件开发平台，可以使用任何编程语言。

3．实验要求（1）求网络中任何两个结点之间的最短路径（网络中至少有4个节点）。

（2）得到任何一个节点上的转发表。

4．实验分析，回答下列问题（1）给出LSA算法的主要思想。

答：首先引进一个辅助向量D，其每个分量D[]表示当前阶段从起点start到顶点i所计算出的最短路径。

初始化之为：D[start]为0，其余D[]为“无穷大”。

在每个阶段，该算法选择所有顶点中D[]最小的未知顶点，将其标记为已知，然后对其所有的邻接顶点的D[]进行更新(若新的D[]更小的话)，然后进入下一阶段，直至所有顶点均已知.（2）通过图表算出任何两个节点之间的最短路径，并给出每个节点上的转发表。

5.算法程序以及运行结果代码如下：#include<stdio.h>#include <stdlib.h>void Dijkstra(int n,int v,int *RoutWeight,int *Rout,int *MGraph[]){int i;int j;int maxint =00000;//定义一个最大的数值，作为不相连的两个节点的代价权值 int *s ; //定义具有最短路径的节点子集ss = (int *)malloc(sizeof(int) * n);//初始化最小路径代价和前一跳节点值for (i = 1; i <= n; i++){RoutWeight[i] = MGraph[v][i]; //初始化V对应的的其余点的权重s[i] = 0; // 现在该点不属于节点子集if (RoutWeight[i] == maxint) //初始化会回溯路径{Rout[i] = 0;}elseRout[i] = v;}}RoutWeight[v] = 0;s[v] = 1; //源节点作为最初的s子集for (i = 1; i < n; i++){int temp = maxint;int u = v;//加入具有最小代价的邻居节点到s子集for (j = 1; j <= n; j++){if ((!s[j]) && (RoutWeight[j] < temp)){u = j;temp = RoutWeight[j];}}s[u] = 1;//计算加入新的节点后，更新路径使得其产生代价最短 for (j = 1; j <= n; j++){if ((!s[j]) && (MGraph[u][j] < maxint)){int newRoutWeight = RoutWeight[u] + MGraph[u][j]; if (newRoutWeight < RoutWeight[j]){RoutWeight[j] = newRoutWeight;Rout[j] = u; //J点的回溯路径}}}}}void ShowPath(int n,int v,int u,int *RoutWeight,int *Rout){int j = 0;int count = 0;int *way ;way=(int *)malloc(sizeof(int)*(n+1));//回溯路径while (w != v){count++;way[count] = Rout[w];w = Rout[w];}//输出路径printf("最优路径:\n");for (j = count; j >= 1; j--){printf("%d -> ",way[j]);}printf("%d\n",u);}void Dijkstra(int ,int ,int *,int *,int * []);void ShowPath(int ,int ,int ,int *,int *);int main(){int i,j,t;int n,v,u;int **MGraph; //矩阵int *RoutWeight; //最短路径代价int *Rout; //回溯节点printf("结点的个数为: ");scanf("%d",&n);printf("结点之间的链接代价（不相连的节点用代价表示）为:\n");MGraph=(int **)malloc(sizeof(int)*(n+1));//构建动态存储矩阵for (i = 1; i <= n; i++){MGraph[i]=(int *)malloc(sizeof(int)*(n+1));}for (j = 1; j <= n; j++) //输入代价矩阵{for (t = 1; t <= n; t++){scanf("%d",&MGraph[j][t]);}}RoutWeight = (int *)malloc(sizeof(int)*n);Rout = (int *)malloc(sizeof(int)*n);printf("确定源结点：");scanf("%d",&v);Dijkstra(n, v, RoutWeight, Rout, MGraph); //调用dijkstra算法for(i = 1; i <= n ; i++){if(i!=v){printf("从%d 到%d 的路径距离是%d\n",v,i,RoutWeight[i]);//printf("结点%d 的前一个结点是%d \n",i,Rout[i]);ShowPath(n,v,i, RoutWeight, Rout);}}return 0;}运行结果截图如下：6.实验小结：答：因为老师给出了一段c语言的代码，并且网上关于Dijkstra算法的资料很多，因此比较容易搞清楚算法的思路以及算法是如何用程序语言实现的。