实验五最小生成树
一、需求分析
1、本程序的目的是要建设一个最经济的网，，输出相应的最小生成树。在这里都用整型数来代替。
2、测试数据
见下程序。
二、概要设计
主程序：
int main()
{
初始化；
while (条件)
{
接受命令;
处理命令;
}
return 0;
}
三、详细设计
#include
using namespace std;
#define MAX_VERTEX_NUM 20//最大结点数
#define MAX 200
typedef struct Close//结构体
{
char adjvex;
int lowcost;
}Close,close[MAX_VERTEX_NUM];
typedef struct ArcNode
{
int adjvex;
ArcNode *nextarc;
int info;
}ArcNode;
typedef struct VNode
{
char data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList verties;
int vexnum,arcnum;
}ALGraph;
ALGraph G;//对象G
int LocateVek(ALGraph ,char );//返回结点位置
int minimum(close);//返回最小数
void MinSpanTree_PRIM(ALGraph,char);//最小生成树
void Create(ALGraph &);//创建邻接表
int main()
{
char a;int i=1;
Create(G);
/*for(int i=1;i<=G.vexnum;i++)
{
for(s=G.verties[i].firstarc;s!=NULL;s=s->nextarc)
cout< while(i) { cout<<"输入起点 : "; cin>>a; MinSpanTree_PRIM(G,a); cout<<"如果结束输入'0',否则输入'1':"; cin>>i; } return 0; } int LocateVek(ALGraph G,char u) { int i; for(i=1;i<=G.vexnum;i++) if(u==G.verties[i].data) return i; return -1; } int minimum(close m)//返回最小数 { int i=0,j,n=200; for(i=1;i<=G.vexnum;i++) if(m[i].lowcost { n=m[i].lowcost; j=i; } return j; } void MinSpanTree_PRIM(ALGraph G,char u) { int j,k,a; close closedge;ArcNode *s,*p,*q; for(j=1;j<=MAX_VERTEX_NUM;j++) closedge[j].lowcost=MAX;//把所有值都赋为最大 k=LocateVek(G,u); for(j=1;j<=G.vexnum;j++) if(j!=k) { closedge[j].adjvex=u; for(s=G.verties[k].firstarc;s!=NULL;s=s->nextarc) if(j==s->adjvex) {closedge[j].lowcost=s->info; break; } } closedge[k].lowcost=0; cout<<"最小生成树 : "<<"{";//查找并输出最小生成树 for(j=1;j { k=minimum(closedge); cout<<"("< < closedge[k].lowcost=0; for(int i=1;i<=G.vexnum;i++) { for(p=G.verties[k].firstarc;p!=NULL;p=p->nextarc) if(p->info { closedge[i].adjvex=G.verties[k].data; closedge[i].lowcost=p->info; } } }cout<<"}"< cout<<"边及对应权值: "< for(j=G.vexnum;j>=1;j--) { if(closedge[j].lowcost==0&&G.verties[j].data!=u) { cout<<"("< <<","< <<") =="; a=closedge[j].adjvex; for(q=G.verties[j].firstarc;q!=NULL;q=q->nextarc) if(a-64==q->adjvex) cout< } } } void Create(ALGraph &G) { int i,j,k,x; char a,b;ArcNode *s; cout<<"输入顶点数(1-20):"; cin>>G.vexnum; cout<<"输入边数:"; cin>>G.arcnum; cout<<"输入顶点信息:"< for(i=1;i<=G.vexnum;i++) { cin>>G.verties[i].data; G.verties[i].firstarc=NULL; } for(i=1;i<=G.arcnum;i++) { cout<<"输入相邻两结点和权值 "; cin>>a>>b;cin>>x; j=a-64;k=b-64;//将字符型转化成整数型 s=new ArcNode; s->info=x; s->adjvex=k; s->nextarc=G.verties[j].firstarc; G.verties[j].firstarc=s; s=new ArcNode; s->info=x; s->adjvex=j; s->nextarc=G.verties[k].firstarc; G.verties[k].firstarc=s; } } 四、调试分析 1、在写程序时遇到很多有关专业名词的C语言编译，没有完全套用书上的固有解释，而是按照自己有限的英语词汇的理解去编译的。 2、通过求最小生成树，进一步掌握了图的含义。 五、运行结果 六、实验环境 （1）Windows XP系统下 （2）编程环境：VC6.0++ ，TC2.0 七、实验体会 通过此实验，通过求最小生成树，进一步掌握了图的含义。知道了普里姆算法。通过本次课程设计，锻炼了我们的实际操作能力，培养了我们严密的思维和严谨的态度。 STP生成树协议原理及配置—从入门到精通 生成树协议（Spanning-Tree Protocol，以下简称STP）是一个用于在局域网中消除环路的协议。运行该协议的交换机通过彼此交互信息而发现网络中的环路，并适当对某些端口进行阻塞以消除环路。由于局域网规模的不断增长，STP已经成为了当前最重要的局域网协议之一。 STP的算法 STP将一个环形网络生成无环拓朴的步骤： 选择根网桥（Root Bridge） 选择根端口（Root Ports） 选择指定端口（Designated Ports） 选择根网桥的依据 网桥ID（BID） 网桥ID是唯一的，交换机之间选择BID值最小的交换机作为网络中的根网桥 STP选择根网桥举例 根据网桥ID选择根网桥 选择根端口的依据 在非根网桥上选择一个到根网桥最近的端口作为根端口 选择根端口的依据是： 根路径成本最低 直连（上游）的网桥ID最小 端口（上游）ID最小 根路径成本 根路径成本（开销）－是网桥到根网桥的路径上所有链路的成本之和，默认10M/100M自适应的路径开销为200000 STP选择根端口举例 在非根桥上，选择一个根端口（RP） 选择指定端口的依据 在每个网段上，选择1个指定端口 根桥上的端口全是指定端口 非根桥上的指定端口： 根路径成本最低 端口所在的网桥的ID值较小 端口ID值较小 STP选择指定端口举例 在每个网段选择1个指定端口（DP） STP计算结果 经过STP计算，最终的逻辑结构为无环拓朴 STP举例 经过STP计算后的逻辑拓朴 BPDU（桥协议数据单元） 交换机之间使用BPDU来交换STP信息 BPDU Bridge Protocol Data Unit －桥协议数据单元 使用组播发送BPDU，组播地址为： 01-80-c2-00-00-00 BPDU分为2种类型： 配置BPDU －用于生成树计算 拓朴变更通告（TCN）BPDU －用于通告网络拓朴的变化 BPDU包含的关键字段 STP使用BPDU选择根网桥2-1 交换机启动时，假定自己是根网桥，在向外发送的BPDU中，根网桥ID 字段填写自己的网桥ID STP使用BPDU选择根网桥2-2 当接收到其他交换机发出的BPDU后，比较网桥ID，选择较小的添加到根网桥ID中 STP使用BPDU计算根路径成本2-1 根网桥发送根路径成本为0的BPDU STP使用BPDU计算根路径成本2-2 其他交换机接收到根网桥的BPDU后，在根路径成本上添加接收接口的路径成本，然后转发 生成树端口的状态 生成树计时器 STP状态机 在STP选举过程中，端口是不能转发用户数据的。端口一开始处于阻塞状态，这个状态只能接收BPDU； STP/RSTP 协议理解 拟制 Prepared by 沈岭 Date 日期 2004-11-03 评审人 Reviewed by Date 日期 yyyy-mm-dd 批准 Approved by Date 日期 yyyy-mm-dd 华为三康技术有限公司 Huawei-3Com Technologies Co., Ltd. 版权所有 侵权必究 All rights reserved 修订记录Revision Record 目录 1 S TP 生成树协议 (7) 1.1STP的主要作用 (7) 1.2STP的基本原理： (7) 1.3STP端口的角色和状态 (8) 1.4端口状态： (9) 1.5STP算法 (9) 1.5.1问题1 (12) 1.5.2问题2 (13) 1.6STP的计时器： (13) 1.7STP拓扑结构改变 (14) 1.8问题讨论 (16) 1.8.1问题3的答案： (16) 1.8.2附加题： (16) 2 RSTP 快速生成树协议 (19) 2.1RSTP的改进 (19) 2.2P/A协商 (22) 2.3拓扑结构变化 (23) 2.3.1问题1： (24) 2.3.2问题2： (25) 2.3.3问题3 (25) 2.3.4问题4： (25) 2.3.5附加题 (26) 2.4RSTP新增特性 (26) 2.4.1BPDU Guard (26) 2.4.2Root Guard (27) 2.4.3Root Primary/Secondary (27) 2.4.4Loop Guard (27) 2.4.5STP Mcheck (28) 2.4.6STP TC-protection (28) 推荐资料： (29) 参考资料： (29) 数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 指导教师: 2011—2012年度第 2 学期 一、需求分析 1.问题描述： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 2.基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 3.输入输出 以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。 二、概要设计 1.设计思路： 因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。 2.数据结构设计： 图状结构： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR} VR={ 实验四、生成树协议 STP的应用实验 【相关知识】 1．生成树协议 STP简介 在局域网中，为了提高网络连接可靠性，经常提供冗余链路。所谓冗余链路就像公路、铁路一 样，条条道路通北京，这条不通走那条。例如在大型企业网中，多半在核心层配置备份交换机（网 桥），则与汇聚层交换机形成环路，这样做使得企业网具备了冗余链路的安全优势。但原先的交换机 并不知道如何处理环路，而是将转发的数据帧在环路里循环转发，使得网络中出现广播风暴，最终 导致网络瘫痪。 为了解决冗余链路引起的问题， IEEE802 通过了 IEEE 802.1d协议， 即生成树协议 （Spanning Tree Protocol，STP）。IEEE 802.1d协议通过在交换机上运行一套复杂的算法，使冗余端口置于“阻塞状 ，从而使网络中的计算机通信时只有一条链路生效，而当这个链路出现故障时，STP 将会重新计 态” 算出网络的最优链路，将“阻塞状态”的端口重新打开，从而确保网络连接的稳定可靠。 生成树协议和其它协议一样，是随着网络的不断发展而不断更新换代的。在生成树协议发展的 过程中，老的缺陷不断被克服，新的特性不断被开发出来。按照功能特点的改进情况，习惯上生成 树协议的发展过程被分为三代： 第一代生成树协议：STP/RSTP 第二代生成树协议：PVST/PVST+ 第三代生成树协议：MISTP/MSTP 2．IEEE 801.1D生成树协议简介 生成树协议（Spanning Tree Protocol，STP）最初是由美国数字设备公司（DEC）开发的，后经 IEEE 修改并最终制定了 IEEE 802.1d标准。 STP 协议的主要思想是当网络中存在备份链路时，只允许主链路激活，如果主链路失效，备份 链路才会被打开。大家知道，自然界中生长的树是不会出现环路的，如果网络也能够像树一样生长 就不会出现环路。STP 协议的本质就是利用图论中的生成树算法，对网络的物理结构不加改变，而 在逻辑上切断环路，封闭某个网桥，提取连通图，形成一个生成树，以解决环路所造成的严重后果。 为了理解生成树协议，必先了解以下概念： （1）桥协议数据单元（Bridge Protocol Data Unit，BPDU）：交换机通过交换 BPDU来获得建立 最佳树型拓扑结构所需的信息。生成树协议运行时， 交换机使用共同的组播地址 “01-80-C2-00-00-00”来发送 BPDU； （2）每个交换机有唯一的桥标识符（Brideg ID），由桥优先级和 MAC 地址组成； （3）每个交换机的端口有唯一的端口标识符（Port ID），由端口优先级和端口号组成； （4）对生成树的配置时，对每个交换机配置一个相对的优先级，对每个交换机的每个端口也配 置一个相对的优先级，该值越小优先级越高； （5）具有最高优先级的交换机被称为根桥（Root Bridge），如果所有设备都具有相同的优先级， 则具有最低 MAC 地址的设备将成为根桥； （6）网络中每个交换机端口都有一个根路径开销（Root Path Cost），根路径开销是某交换机到 根桥所经过的路径开销（与链路带宽有关）的总和； （7）根端口是各个交换机通往根桥的根路径开销最低的端口，若有多个端口具有相同的根路径 开销，则端口标识符小的端口为根端口； （8）在每个 LAN 中都有一个交换机被称为指定交换机（Designated Bridge），它是该 LAN 中与 根桥连接而且根路径开销最低的交换机； （9）指定交换机和 LAN 连接的端口被称为指定端口（Designated Port）。如果指定桥中有两个 以上的端口连在这个 LAN 上，则具有最高优先级的端口被选为指定端口。根桥上的端口都可以成为 黄冈师范学院 提高型实验报告 实验课题最小生成树的Prim算法 （实验类型：□综合性■设计性□应用性） 实验课程算法程序设计 实验时间 2010年12月24日 学生姓名周媛鑫 专业班级计科 0801 学号 200826140110 一．实验目的和要求 （1）根据算法设计需要, 掌握连通网的灵活表示方法; （2）掌握最小生成树的Prim算法; （3）熟练掌握贪心算法的设计方法; 二．实验条件 （1）硬件环境：实验室电脑一台 （2）软件环境：winTC 三．实验原理分析 （1）最小生成树的定义： 假设一个单位要在n个办公地点之间建立通信网，则连通n个地点只需要n-1条线路。可以用连通的无向网来表示n个地点以及它们之间可能设置的通信线路，其中网的顶点表示城市，边表示两地间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以表示一个通信网。其中一棵使总的耗费最少，即边的权值之和最小的生成树，称为最小生成树。 （2）构造最小生成树可以用多种算法。其中多数算法利用了最小生成树的下面一种简称为MST的性质：假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必存在一棵包含边 (u.v)的最小生成树。 （3）普里姆（Prim）算法即是利用MST性质构造最小生成树的算法。算法思想如下： 假设N=(V,{E})和是连通网，TE是N上最小生成树中边的集合。算法从U={u0}( u0∈V)，TE={}开始，重复执行下述操作：在所有u∈U，v∈V-U的边(u, v) ∈E 中找一条代价最小的边(u0, v0)并入集合TE，同时v0并入U，直到U=V为止。此时TE中必有n-1条边，则T=(V,{TE})为N的最小生成树。 四．实验步骤 （1）数据结构的设计： 采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作： 邻接矩阵的抽象数据结构定义： #define INFINITY INT_MAX //最大值 #define MAX_ERTEX_NUM 20 //最大顶点数 typedef enum {DG,DN,UDG,UDN}GraphKind;//{有向图,有向网，无向网，无向图} typedef struct Arc Cell{ VRType adj ; // VRType 是顶点关系的类型。对无权图用1和0表示相邻否；InfoType * info; //该弧相关信息的指针 }ArcCell ，AdjMatrix [ MAX_VERTEX_NUM][MAX_VERTEX_NUM]； Typedef struct { VertexType vexs [ MAX_VERTEX_NUM] ; //顶点向量 实验五最小生成树 一、需求分析 1、本程序の目の是要建设一个最经济の网，，输出相应の最小生成树。在这里都用整型数来代替。 2、测试数据 见下程序。 二、概要设计 主程序： int main() { 初始化； while (条件) { 接受命令; 处理命令; } return 0; } 三、详细设计 #include { char adjvex; int lowcost; }Close,close[MAX_VERTEX_NUM]; typedef struct ArcNode { int adjvex; ArcNode *nextarc; int info; }ArcNode; typedef struct VNode { char data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList verties; int vexnum,arcnum; }ALGraph; ALGraph G;//对象G int LocateVek(ALGraph ,char );//返回结点位置 int minimum(close);//返回最小数 void MinSpanTree_PRIM(ALGraph,char);//最小生成树 void Create(ALGraph &);//创建邻接表 int main() { char a;int i=1; Create(G); /*for(int i=1;i<=G.vexnum;i++) { for(s=G.verties[i].firstarc;s!=NULL;s=s->nextarc) cout< 附件2： 北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 班级学号姓名指导教师成绩实验题目生成树协议故障排除实验时间 拓扑图 地址表 端口分配－ S2 学习目标 ?观察所有中继的初始状态 ?更正存在的错误 ?记录交换机配置 场景 拓扑图所示的冗余交换 LAN 由您负责维护。您和您的用户发现在网络高峰期延时会变长，经过分析，您怀疑是中继拥塞所致。您发现在所配置的六条中继中，只有两条在当前运行的默认 STP 配置中转发数据包。要解决此问题，就需要提高对可用中继的使用率。 任务1：观察所有中继的初始状态 在每台交换机上，使用show spanning-tree命令列出其上的生成树表。注意观察每台交换机上的转发端口，找出在默认配置中哪些中继没有被使用。您可以使用网络拓扑图来记录所有中继端口的初始状态。 任务2：更正存在的错误 修改生成树配置，使所有三条中继都能用上。假设三个用户LAN（10、20 和30）承载等量的流量。尝试找出一个解决方案，使三个用户VLAN 中的每一个都使用不同的一组端口进行转发。 要使本次练习得到正确评分，您必须满足以下条件： ?S1 成为VLAN 10 的根桥（优先级4096）、VLAN 20 的备用根桥（优先级16384）?S2 成为VLAN 20 的根桥（优先级4096）、VLAN 30 的备用根桥（优先级16384）?S3 成为VLAN 30 的根桥（优先级4096）、VLAN 10 的备用根桥（优先级16384） 任务3：记录交换机配置 实施完毕您的解决方案后，在每台交换机上捕获show run命令的输出并保存在文本文件中。 石河子大学 信息科学与技术学院 <网络技术>课程设计成果报告 目 快速生成树协议（802.1w） 注：本文译自思科的白皮书Understanding Rapid Spanning Tree Protocol（802.1w）. ---------------------------------------------------------------------------------------------------------------------- 介绍 Catalyst 交换机对RSTP的支持 新的端口状态和端口角色 端口状态（Port State） 端口角色（Port Roles） 新的BPDU格式 新的BPDU处理机制 BPDU在每个Hello-time发送 信息的快速老化 接收次优BPDU 快速转变为Forwarding状态 边缘端口 链路类型 802.1D的收敛 802.1w的收敛 Proposal/Agreement 过程 UplinkFast 新的拓扑改变机制 拓扑改变的探测 拓扑改变的传播 与802.1D兼容 结论 ---------------------------------------------------------------------------------------------------------------------- 介绍 在802.1d 生成树（STP）标准设计时，认为网络失效后能够在1分钟左右恢复，这样的性能是足够的。随着三层交换引入局域网环境，桥接开始与路由解决方案竞争，后者的开放最短路由协议（OSPF）和增强的内部网关路由协议（EIGRP）能在更短的时间提供备选的路径。 思科引入了Uplink Fast、Backbone Fast和Port Fast等功能来增强原始的802.1D标准以缩短桥接网络的收敛时间，但这些机制的不足之处在于它们是私有的，并且需要额外的配置。快速生成树协议（RSTP；IEEE802.1w）可以看作是802.1D标准的发展而不是革命。802.1D 的术语基本上保持相同，大部分参数也没有改变，这样熟悉802.1D的用户就能够快速的配置新协议。在大多数情况下，不经任何配置RSTP的性能优于思科的私有扩展。802.1w能够基于端口退回802.1D以便与早期的桥设备互通，但这会失去它所引入的好处。 算法分析与设计之Prim 学院：软件学院学号：201421031059 ：吕吕 一、问题描述 1.Prim的定义 Prim算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。 2.实验目的 选择一门编程语言，根据Prim算法实现最小生成树，并打印最小生成树权值。 二、算法分析与设计 1.Prim算法的实现过程 基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U ＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作： 在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。 此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。 Prim算法的核心:始终保持TE中的边集构成一棵生成树。 2.时间复杂度 Prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，N 为顶点数，而看ruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。 三、数据结构的设计 图采用类存储，定义如下： class Graph { private: int *VerticesList; int **Edge; int numVertices; int numEdges; int maxVertices; public: Graph(); ~Graph(); bool insertVertex(const int vertex); bool insertEdge(int v1,int v2,int cost); int getVertexPos(int vertex); int getValue(int i); int getWeight(int v1,int v2); int NumberOfVertices(); STP 为什么会有stp 为了保证可靠，设计了一种环网拓扑，又因为交换机的工作原理，会出现环路问题，为了解决环路，才有了stp生成树 1 mac地址表震荡 2 广播风暴 作用：在保证可靠的基础上，解决环路问题 原理：阻塞端口（预备端口）通过选举阻塞端口，来防止环路 1 根桥（根交换机）： 1 比较每台交换机上的网桥id （优先级+mac地址）越小越优先 默认优先级 32768 修改优先级修改的时候要改成4096的倍数 交换机上有默认的stp版本为mstp （多实例生成树）stp （生成树）rstp (快速生成树) [系统]stp mode stp 修改stp的模式 Stp priority 4096 修改优先级 2 根端口：非根交换机到达根交换机的最优端口 比较规则 1 路径开销值 2 对端网桥id 3 对端对口id 4 本端端口id （hub） 3 指定端口：每条链路上到达根交换机最优端口根交换机上所有端口都是指定端口 比较规则 1 路径开销 2 本端网桥id 3 本端端口id （端口优先级和端口编号）端口优先级默认是128 4 剩下的端口就叫做阻塞端口 Stp中的报文交互 BPDU 桥协议数据单元 两种bpdu 1 配置bpdu 作用：用于角色（端口）选举 维护网络拓扑 2秒1次最多20秒20 秒没有根的回应，则认为根down掉 2 tcn bpdu 拓扑变化bpdu 作用：当拓扑发生变化时，会发tcn bpdu Bpdu 字段 1 bpdu flsges标识字段 Tca 位拓扑变化确认位 Tc 位拓扑变化位 发生变化时置1 2 root identifier 根网桥id 3 root path cost 到达根的开销值 4 bridge id 本交换机的网桥id 5 port id 端口id 0x8001 前面的80 代表优先级128 ， 01代表端口号 6 message age 消息寿命每经过一台交换机message age +1 7 max age 最大寿命 20 秒 8 hello time 2秒 9 forward delay 转发延迟 15秒 端口的状态变化 1 disable 开启stp时特点：不进行stp计算 2 blocking 阻塞端口直接进入blocking 状态 3 listening 非阻塞端口才进入侦听状态特点：加速mac地址表老化 中间有15秒的间隔时间，目的是为了加速mac地址表老化，mac地址表老化时间300秒 4 learning 学习状态 中间有相隔15秒的时间，加速mac地址表的学习 5 forwarding 转发状态 算法与数据结构 实验报告 系（院）：计算机科学学院 专业班级：软工11102 姓名：潘香杰 学号： 201104449 班级序号： 18 指导教师：詹泽梅老师 实验时间：2013.6.17 - 2013.6.29 实验地点：4号楼5楼机房 目录 1、课程设计目的．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 2、设计任务．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 3、设计方案．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 4、实现过程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 5、测试．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 6、使用说明．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 7、难点与收获．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8、实现代码．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 9、可改进的地方．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 算法与数据结构课程设计是在学完数据结构课程之后的实践教学环节。本实践教学是培养学生数据抽象能力，进行复杂程序设计的训练过程。要求学生能对所涉及问题选择合适的数据结构、存储结构及算法，并编写出结构清楚且正确易读的程序，提高程序设计基本技能和技巧。 一．设计目的 1．提高数据抽象能力。根据实际问题，能利用数据结构理论课中所学到的知识选择合适的逻辑结构以及存储结构，并设计出有效解决问题的算法。 2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3．初步了解开发过程中问题分析、整体设计、程序编码、测试等基本方法和技能。二．设计任务 设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下： ①创建无向图的邻接表 ②无向图的深度优先遍历 ③无向创建无向图的邻接矩阵 ④无向图的基本操作及应用 ⑤图的广度优先遍历 1．有向图的基本操作及应用 ①创建有向图的邻接矩阵 ②创建有向图的邻接表 ③拓扑排序 2．无向网的基本操作及应用 ①创建无向网的邻接矩阵 ②创建无向网的邻接表 ③求最小生成树 3．有向网的基本操作及应用 ①创建有向网的邻接矩阵 ②创建有向网的邻接表 ③关键路径 ④单源最短路径 三．设计方案 第一步：根据设计任务，设计DOS菜单，菜单运行成果如图所示： 0分计。 4. 实验报告文件以PDF 格式提交。 【实验题目】生成树协议 【实验目的】理解快速生成树协议的配置及原理。使网络在有冗余链路的情况下避免环路的产生，避免广播风暴等。 【实验内容】 (1)完成实验教程实例3-8的实验，回答实验提出的问题及实验思考。（P117） (2)抓取生成树协议数据包，分析桥协议数据单元（BPDU ）。 (3)在实验设备上查看VLAN 生成树，并学会查看其它相关重要信息。 【实验要求】 一些重要信息需给出截图。 注意实验步骤的前后对比！ 【实验记录】(如有实验拓扑请自行画出, 要求自行画出拓扑图) (1) 实例3-8 实验拓扑图如下： 步骤0： 将PC1和PC2配置好IP地址和掩码后按照拓扑图连接实验设备。 在PC1上启动Wireshark 软件观察包的数量变化如下： 此时已经产生了广播风暴。 两台交换机此时的生成树配置信息如下： 无生成树配置信息。 用PC1pingPC2时包增长情况如下： 可见此时包增长的更快，已经产生广播风暴，但是PC并未发生死锁。步骤1： 配置交换机A： 步骤2： 配置交换机B： 步骤3: 配置两交换机的快速生成树协议： 再按照拓扑图连接实验设备，此时包增长情况如下： 此时两PC间可以相互ping通，且无广播风暴。由此可见生成树协议的作用为避免网络中存在交换环路的时候产生广播风暴，确保在网络中有环路时自动切断环路。 步骤4：验证测试 SwitchA的生成树信息： SwitchB的生成树信息： 步骤5：设置交换机的优先级 将SwitchA的优先级设置为4096 步骤6: 验证SwitchA的优先级 当两个端口都连在一个共享介质上，交换机会选择一个高优先级的端口进入 惠州学院《计算机网络》实验报告 实验三生成树的协议配置 一．实验目的 在掌握环路产生的原因及危害性的基础上，学习STP的功能、原理及配置方法，从而了解利用冗余链路来提高网络安全性和可靠性的相关技术。 二．实验环境 1.交换机2台，二层三层均可，本实验使用的是二层交换机 2.实验用PC机2台 3.Console电缆2根 4.直连双绞线2根 5.交叉双绞线2根 三．实验内容和要求 （1）掌握链路冗余的重要性。 （2）了解广播风暴对网络性能造成的影响。 （3）掌握STP、RSTP和MSTP的概念以及相互之间的区别。 （4）学习生成树协议的配置方法。 四．网络拓扑图 五、实验步骤 生成树协议在部分交换机（如思科）上是自动打开的，管理员不需要进行配置。但在一些交换机（如锐捷）上默认是关闭的，如果网络中存在环路，则必须手动开启。根据如上的拓扑图，具体配置如下： 1.在交换机A上创建一个VLAN，然后将与PC1连接的端口添加到VLAN 10中。同时，将用于交换机之间连接的两个端口设置为tag模式。 Switch-A#configure terminal Switch-A(config)#vlan 10 Switch-A(config-vlan)#name test Switch-A(config-vlan)#exit Switch-A(config)#interface FastEthernet 0/6 Switch-A(config-if)#switchport access vlan 10 Switch-A(config-if)#end Switch-A(config)#interface FastEthernet 0/3 Switch-A(config-if)#Switchport mode trunk Switch-A(config-if)#exit Switch-A(config)#interface FastEthernet 0/4 Switch-A(config-if)#Switchport mode trunk Switch-A(config-if)#end 2.在交换机B上创建一个VLAN，然后将与PC2连接的端口添加到VLAN 10中。同时，将用于交换机之间连接的两个端口设置为tag模式。 Switch-B#configure terminal Switch-B(config)#vlan 10 Switch-B(config-vlan)#name test Switch-B(config-vlan)#exit Switch-B(config)#interface FastEthernet 0/6 Switch-B(config-if)#switchport access vlan 10 Switch-B(config-if)#end Switch-B(config)#interface FastEthernet 0/3 Switch-B(config-if)#Switchport mode trunk Switch-B(config-if)#exit Switch-B(config)#interface FastEthernet 0/4 Switch-B(config-if)#Switchport mode trunk Switch-B(config-if)#end 3.如果该交换机没有启用生成树协议，则分别在A和B交换机上启用相应的协议，以免产生环路。Cisco交换机开启生成树协议的命令为：spanning-tree vlan 1 Switch-A(config)#spanning-tree vlan 1 Switch-B(config)#spanning-tree vlan 1 锐捷交换机开启生成树协议的命令为：spanning-tree mode rstp 六、实验截图 实验十三快速生成树协议RSTP 实验名称 快速生成树协议RSTP。 实验目的 理解生成树协议的配置及原理。 实现功能 使网络在有冗余链路的情况下避免环路的产生，避免广播风暴等。 实验设备 锐捷S2126（或S3550）交换机2台，网线4根。 实验步骤 1.用2根网线从交换机（除了1和2号端口）分别连到2台计算机，这两台计算机的IP 地址设为同一个网段地址。 2.连到交换机1，对交换机1进行配置。 3.对交换机1开启生成树协议。 configure terminal(进入交换机全局配置模式) spanning-tree(开启生成树协议) spanning-tree mode rstp(设置生成树模式为802.1W) spanning-tree priority 8192(设置此交换机的生成树优先级为8192) end show spanning-tree(显示交换机生成树的状态) StpVersion : RSTP SysStpStatus : Enabled BaseNumPorts : 24 MaxAge : 20 HelloTime : 2 ForwardDelay : 15 BridgeMaxAge : 20 BridgeHelloTime : 2 BridgeForwardDelay : 15 MaxHops : 20 TxHoldCount : 3 PathCostMethod : Long BPDUGuard : Disabled BPDUFilter : Disabled BridgeAddr : 00d0.f8b8.1c5b Priority : 8192 TimeSinceTopologyChange : 0d:0h:7m:24s TopologyChanges : 0 DesignatedRoot : 200000D0F8B81C5B RootCost : 0 RootPort : 0 freezing1# 4.连到交换机2，对交换机2进行配置。 5.对交换机2开启生成树协议。 configure terminal(进入交换机全局配置模式) spanning-tree(开启生成树协议) spanning-tree mode rstp(设置生成树模式为802.1W) spanning-tree priority 16384(设置此交换机的生成树优先级为16384) end Cisco快速生成树协议RSTP协议原理及配置 实验8 Cisco 快速生成树协议RSTP 协议原理及配置 一、相关知识介绍 1、生成树协议的主要功能有两个：一是在利用生成树算法、在以太网络中，创建一个以某台交换机的某个 端口为根的生成树，避免环路。二是在以太网络拓扑发生变化时，通过生成树协议达到收敛保护的目的。 2、根网桥的选择流程： （1）第一次启动交换机时，自己假定是根网桥，发出BPDU报文宣告。 （2）每个交换机分析报文，根据网桥ID选择根网桥，网桥ID小的将成为根网桥（先比较网桥优先级，如果相等，再比较MAC地址）。 （3）经过一段时间，生成树收敛，所有交换机都同意某网桥是根网桥。 （4）若有网桥ID值更小的交换机加入，它首先通告自己为根网桥。其它交换机比较后，将它当作新的根网桥而记录下来。 3、RSTP 协议原理 STP并不是已经淘汰不用，实际上不少厂家目前还仅支持STP。STP的最大缺点就是他的收敛时间太长，对于现在网络要求靠可靠性来说，这是不允许的，快速生成树的目的就是加快以太网环路故障收敛 的速度。 （1）RSTP 5种端口类型 STP定义了4种不同的端口状态，监听（Listening），学习（Learning），阻断（Blocking）和转发（Forwarding），其端口状态表现为在网络拓扑中端口状态混合（阻断或转发），在拓扑中的角色（根 端口、指定端口等等）。在操作上看，阻断状态和监听状态没有区别，都是丢弃数据帧而且不学习MAC 地址，在转发状态下，无法知道该端口是根端口还是指定端口。RSTP有五种端口类型。根端口和指定端口这两个角色在RSTP中被保留，阻断端口分成备份和替换端口角色。生成树算法（STA）使用BPDU来决定端口的角色，端口类型也是通过比较端口中保存的BPDUB来确定哪个比其他的更优先。 1）根端口：非根桥收到最优的BPDU配置信息的端口为根端口，即到根桥开销最小的端口，这点和STP 一样。请注意图8-16上方的交换机，根桥没有根端口。按照STP的选择根端口的原则，SW-1和SW-2和根连接的端口为根端口。 2）指定端口：与STP一样，每个以太网网段段内必须有一个指定端口。假设SW-1的BID比SW-2 优先，而且SW-1的P1口端口ID比P2优先级高，那么P1为指定端口，如图8-17所示。STP生成树协议原理及配置--从入门到精通
STP.RSTP协议理解
最小生成树实验报告
生成树协议STP的应用实验1
最小生成树的Prim算法提高型实验报告
最小生成树-实验报告
生成树协议故障排除
RSTP快速生成树协议的配置课程设计
2014—2015 学年第一学期
题目名称：
利用快速生成树协议（RSTP） 实现现交换机之间的冗余链路备份
专 班 学
业： 级： 号：
计算机科学与技术 计科 2012（一）班 2012508013 蒋 曹 能 传 凯 东
学生姓名： 指导教师：
完成日期：二○一五
年
一 月 七
日
录
一 课题介绍 ......................................................................................................................................................... - 3 1.1 课题名称 ............................................................................................................................................... - 3 1.2 课题简介 ............................................................................................................................................... - 3 1.3 课题拓展 ............................................................................................................................................... - 3 二 RSTP 简介....................................................................................................................................................... - 3 三 实验环境介绍 ................................................................................................................................................. - 5 3.1 实验软硬件环境 ................................................................................................................................... - 5 3.2 实验参数 ............................................................................................................................................... - 5 3.3 实验拓扑图 ........................................................................................................................................... - 8 四 实验内容 ......................................................................................................................................................... - 8 五 实验详细步骤 ................................................................................................................................................. - 9 5.1 绘制实验拓扑 ....................................................................................................................................... - 9 5.2 交换机及 PC 的基本配置 .................................................................................................................... - 9 5.3 Spanning-tree 的配置 .......................................................................................................................... - 13 5.3 链路测试 ............................................................................................................................................. - 14 六 课题总结 ....................................................................................................................................................... - 17 附录 A 参考文献................................................................................................................................................ - 18 -理解快速生成树协议(RSTP)
Prim最小生成树算法实验报告材料
华为stp生成树协议笔记
实验报告
07_生成树实验
计算机网络实验三 生成树的协议配置
实验13 快速生成树协议RSTP
Cisco快速生成树协议RSTP协议原理及配置
相关主题
文本预览