精华内容
下载资源
问答
  • 距离向量路由算法的Java模拟
    千次阅读
    2016-09-01 00:49:45

    实验内容与实现原理;
    实验内容:模拟距离向量路由算法的路由表交换过程,演示每轮交换后路由表的变化。基本要求(动态生成网络拓扑图,节点间的距离随机生成。从初始路由表开始,进行交换路由表,演示每轮交换后的路由表的变化。观察和讨论多少轮交换后路由表稳定)。
    实现原理:初始时设定站点个数,每一个站点附带一个表格来记录其余的站点以及距离,并用随机数产生站点之间距离记入表格(产生距离是要考虑到是否相邻的情况)。在所有的距离都产生之后,就用循环对每一个站点的每一个距离与相邻结点到目标结点距离加上当前结点到相邻结点距离之和来进行比较,如果当前记录的值是较大的一个,则更新记录。并设置一个标志位,标志位初始值设为0,若发生了更新行为,则将标志位改为1,。若当前这一轮循环之后的标志位仍为0,则说明已经达到了稳定状态。输出最终结果,完成算法。


    窗体类:
    import java.awt.GridLayout;
    import java.awt.Image;
    import javax.swing.*;
    public class Myframe extends JFrame{
    private GridLayout gd=new GridLayout(4,1,10,10);
    private JTable t1=new JTable(8,8);//八行八列
    private JTextField j1=new JTextField(“初始时距离记录如下”);
    private JTable t2=new JTable(8,8);//八行八列
    private JTextField j2=new JTextField(“稳定后距离记录如下”);
    public Myframe(Routing array[],Routing b[]){
    this.setLayout(gd);
    this.setTitle(“距离向量路由算法”);
    this.setSize(800, 800);
    t1.setSize(200, 200);
    t2.setSize(200,200);
    try{
    for(int i=0;i<7;i++){
    t1.setValueAt((char)(i+’a’), 0, i+1);
    t1.setValueAt((char)(i+’a’), i+1, 0);
    t2.setValueAt((char)(i+’a’), 0, i+1);
    t2.setValueAt((char)(i+’a’), i+1, 0);
    }
    for(int i=1;i<8;i++)
    for(int j=1;j<8;j++){
    t1.setValueAt(b[i-1].dis[j-1], i, j);
    t2.setValueAt(array[i-1].dis[j-1], i, j);
    }
    }catch(Exception e){
    e.printStackTrace();
    }
    this.add(j1);
    this.add(t1);
    this.add(j2);
    this.add(t2);

    }
    }


    路由节点类
    public class Routing {
    protected char m;
    protected char[] name=new char[100];
    protected int[] dis=new int[100];
    protected char[] next=new char[100];
    public Routing(char a){
    m=a;
    for(int i=0;i<100;i++){
    dis[i]=0;
    }
    }
    }
    路由算法类:
    public class suanfa {
    Routing[] arr=new Routing[7];
    public static Routing[] create(Routing array[]){//随机生成距离
    for(int i=0;i<7;i++)
    for(int j=0;j<7;j++){
    if(i==j)
    array[i].dis[j]=0;
    else{
    if(array[i].dis[j]==0){
    array[i].dis[j]=(int)(Math.random()*50);
    if(array[i].dis[j]>40||array[i].dis[j]==0){//这种情况视为不相邻把距离设为一个很大的值
    array[i].dis[j]=1000;
    array[j].dis[i]=1000;
    } }
    }
    array[i].name[j]=array[j].m;
    array[i].next[j]=array[j].m;
    }
    for(int n=0;n<7;n++){
    System.out.println(“这是初始值”);
    System.out.println(“这是结点”+array[n].m+”的当前路由表”);
    for(int e=0;e<7;e++){
    System.out.println(array[n].name[e]+” “+array[n].dis[e]+”下一跳地址是”+array[n].next[e]);
    }
    }
    return array;
    }
    public static Routing[] exchange(Routing array[]){//检查是否有更小距离进行修正
    int ex=0,count=0;
    while(true){
    for(int i=0;i<7;i++)
    for(int j=0;j<7;j++){
    for(int m=0;m<7;m++){
    if(array[i].dis[m]==1000)
    continue;//不相邻的结点不能交换路由表
    if(array[i].dis[j]>array[i].dis[m]+array[m].dis[j]){
    array[i].dis[j]=array[i].dis[m]+array[m].dis[j];
    array[i].next[j]=array[m].m;
    ex=1;
    }}}
    count++;
    for(int n=0;n<7;n++){
    System.out.println(“这是第”+count+”轮的结果”);
    System.out.println(“这是结点”+array[n].m+”的当前路由表”);
    for(int e=0;e<7;e++){
    System.out.println(array[n].name[e]+” “+array[n].dis[e]+”下一跳地址是”+array[n].next[e]);
    }
    }
    if(ex==0){
    System.out.println(“已经达到稳定状态,一共运行了”+count+”轮”);
    return array;
    }
    ex=0;
    }
    }
    public static void main(String[] args){
    try{
    Routing[] arr=new Routing[7];
    Routing[] b=new Routing[7];
    arr[0]=new Routing(‘a’);
    arr[1]=new Routing(‘b’);
    arr[2]=new Routing(‘c’);
    arr[3]=new Routing(‘d’);
    arr[4]=new Routing(‘e’);
    arr[5]=new Routing(‘f’);
    arr[6]=new Routing(‘g’);
    b[0]=new Routing(‘a’);
    b[1]=new Routing(‘b’);
    b[2]=new Routing(‘c’);
    b[3]=new Routing(‘d’);
    b[4]=new Routing(‘e’);
    b[5]=new Routing(‘f’);
    b[6]=new Routing(‘g’);
    arr=create(arr);
    for(int i=0;i<7;i++){
    b[i].m=arr[i].m;
    for(int j=0;j<7;j++){
    b[i].dis[j]=arr[i].dis[j];
    b[i].name[j]=arr[i].name[j];

        }}
        arr=exchange(arr);
        Myframe mf=new Myframe(arr,b);
        mf.setVisible(true);
       }catch(Exception e){
           e.printStackTrace();
       }
    

    }
    }
    在本次模拟实验中,初始状态是随机生成的,然后由算法进行路径距离优化,将最终优化的结果在窗体上显示出来。实际上,在每一次的交换优化中,我都将结果在控制台输出了,比较繁琐,不过这也不是我们所关心的。

    更多相关内容
  • 首先它询问节点的数量,然后它生成一个节点分布在空间中并且... 然后它根据维基百科链接中给出的理论解释使用距离矢量路由算法计算最短路径: “ http://en.wikipedia.org/wiki/Distance-vector_routing_protocol ”。
  • 距离向量路由算法

    千次阅读 2021-08-03 14:41:30
    一、距离向量路由算法特点 距离向量路由算法是一种迭代的、异步的和分布式的算法。 (1)分布式:每个节点都从其直接相连邻居接受信息,进行计算,再将计算结果分发给邻居。 (2)迭代:计算过程一直持续到邻居之间...

    一、距离向量路由算法特点

    距离向量路由算法是一种迭代的、异步的和分布式的算法。
    (1)分布式:每个节点都从其直接相连邻居接受信息,进行计算,再将计算结果分发给邻居。
    (2)迭代:计算过程一直持续到邻居之间无更多信息交换为止。
    (3)异步:不要求所有节点相同之间步伐一致地操作。
    (4)自我终结:算法能自行停止。
    最低费用表示:
    d x _x x(y)=min v _v v{c(x,v)+d v _v v(y)}。
    d x _x x(y):节点x到节点y地最低费用路径的费用;
    v:节点x的邻居节点;
    c(x,v)+d v _v v(y):x与某个邻居v之间的直接链路费用c(x,v)加上邻居v到y的最小费用,即x经v到节点y的最小路径费用。
    在这里插入图片描述
    我们来计算一下源节点u到目的节点z的最低费用路径。
    源节点u有3个邻居:
    邻居v:d v _v v(z)=5,c(u,v)=2;
    邻居w:d w _w w(z)=3,c(u,w)=5;
    邻居x:d x _x x(z)=3,c(u,x)=1;
    则从u节点到z节点的最低费用路径的费用为:
    B-F公式:
    d u _u u(z)=min{d v _v v(z)+c(u,v),d w _w w(z)+c(u,w),d x _x x(z)+c(u,x)}=min{5+2,5+3,3+1}=4
    即源节点u经相邻节点x到目的节点z的路径费用最低为4。

    二、算法过程

    对每个节点x
    (1)在每个节点建立自己的距离向量表并初始化。
    (2)在每个节点将自己维护的距离向量表向其邻居节点转发。
    (3)每个节点收到邻居节点发送的距离向量表以后基于新的信息采用方程来更新自己的距离向量表。
    (4)当自己的距离向量表发生变化时,将新的距离向量表发送给自己的邻居节点,如果与以前的向量表相同则不向其邻居节点转发,直到每个节点的距离向量表达到稳定为止。
    在这里插入图片描述
    假设图中只有3个节点,3个节点两两相连,因此可在每个节点建立自己的距离向量表。
    在这里插入图片描述
    上图为x节点的选路表。
    节点x选路表中:
    行:该节点的距离向量Dx和其邻居的距离向量Dv;
    列:所有目的节点。
    在初始化时由于每个节点只知道本路由器相连的链路费用,因此只有到相邻节点的最低路径费用有值,为对应的链路费用值。如下图
    在这里插入图片描述
    当每个节点完成自己的距离向量表后,会不断的向自己的邻居节点发送这个距离向量表。
    每个节点收到邻居新的距离向量表后,会使用B-F公式更新自己的距离向量。若距离向量发生变化将新的距离向量通知给邻居。
    当距离向量不在变化,则算法终止。
    在这里插入图片描述
    x、y、z三个节点向其邻居发送了自己的向量表之后,x节点收到了来自y节点和z节点的距离向量分别是201和710。分别将这两个向量放在第二行和第三行的第一列中。然后利用收到的新的信息来更新自己的距离向量。首先更新x节点到y节点的最低路径费用。根据B-F方程可是x节点到y节点最低路径费用为2,因此保持不变二x节点到z节点的最低路径费用可进一步减小为3即x节点先到y节点再到z节点。经过上述修改后x的向量表如第一行第二列所示。x节点新的距离向量与以前的发生了变化,因此x节点会将新的距离向量向其邻居节点y和z发送。依次类推,每个节点都不断更新自己的距离向量,直到不在发送变化为止。例如第二行第二列这里的y节点重新计算距离向量后发现这里的距离向量没有发生变化仍然是201,因此不再向其邻居节点发送。
    我们观察到多次从邻居接受更新距离向量、重新计算选路表项、并向邻居发送更新通知的过程,一直持续到没有更新报文发出为止;算法进入静止状态,直到某个链路费用发生改变为止。

    三、链路改变与链路故障

    当一个节点检测到从它到邻居的链路费用发生变化时,就更新其距离变量,如果最低费用路径的费用发生变化,通知其邻居。
    (1)某条链路费用减少时
    在这里插入图片描述
    如图所示,当y到x的链路费用从4变为1的情况。
    t0时刻:y检测到x的链路费用从4变为1,更新其距离变量,并通知其邻居z。
    t1时刻:在t1时刻,z收到来自y的更新报文,并更新自己的距离表,此时到节点x的最低费用减为2,并通知其邻居y。
    t2时刻:在t2时刻y收到来自z的更新报文,并更新自己的距离表,此时到节点x的最低费用不变仍为1,不发送更新报文,算法静止。
    因此当x与y之间费用减少,算法只需两次迭代到达静止状态。
    (2)某链路费用增加时
    在这里插入图片描述

    如图所示,假设x与y之间的链路费用从4增加到60。
    链路费用变化前:
    Dy(x)=4,Dy(z)=1,Dz(y)=1,Dz(x)=5
    t0时刻:在t0时刻,y检测到链路费用从4变为60。更新到x的最低路径费用
    d y _y y(x)=min{d x _x x(x)+c(y,x),d z _z z(x)+c(y,z)}=min{0+60,1+5}=6
    经节点z到x费用最低,此新费用错误,发给节点z。
    t1时刻;t1时刻z收到新费用,更新其到x的最低路径费用
    d z _z z(x)=min{d x _x x(x)+c(y,z),d y _y y(x)+c(z,y)}=min{0+50,1+6}=7
    经节点y到x费用最低,发给节点y。
    t2时刻:y收到新费用,更新到x的最低路径费用
    d y _y y(x)=min{d x _x x(x)+c(y,x),d z _z z(x)+c(y,z)}=min{0+60,1+7}=8
    经节点z到x费用最低,发给节点z。
    以此节点y或节点z的最低费用不断更新。
    这里就产生了选路循环:为到达x,y通过z选路,z又通过y选路。即目的地为x的分组到达y或z后,将在这两个节点之间不停地来回反复,直到转发表发送改变为止。
    上述循环将持续44次迭代,直到z最终算出它经由y地路径费用大于50为止。并确定z到x地最低费用路径是zx,y到x地最低费用路径是yzx。
    通过上述两个变化我们可知链路费用减少地好消息传播的快,而链路费用增加的坏消息传播很慢。甚至当链路费用增加很大时会出现“计数到无穷”问题。

    四、链路状态路由算法和向量路由算法对比

    (1)消息复杂度
    链路状态路由算法(LS):需要知道每条链路的费用,需发送O(nE)个报文;当一条链路的费用发生变化时,必须通知所有节点。
    距离向量路由算法(DV):迭代时,仅在两个直接相连邻居之间交换报文;当链路费用改变时,只有该链路相连的节点的最低费用路径发生改变时,才传播已经、改变的链路费用。
    (2)收敛速度
    LS:需要O(nE)个报文和O(n 2 ^2 2)的搜寻。
    DV:收敛较慢。可能会遇到选路回环,或计数到无穷的问题。
    (3)健壮性:当一台路由器发生故障、操作错误或受到破坏时
    LS:路由器向其连接的一条链路广播不正确费用,路由计算基本独立(仅计算自己的转发表),有一定健壮性。
    DV:一个节点可向任意或所有目的节点发布其不正确的最低费用路径,一个节点的计算值会传递给它的邻居,并间接地传递给邻居的邻居。

    展开全文
  • 用弗洛伊德最短路径,实现的距离向量路由算法
  • 距离向量路由算法系列文章目录三、距离向量路由算法距离向量(Distance Vector)路由算法Bellman-Ford举例距离向量路由算法距离向量路由算法举例(来自邻居的DV更新)距离向量DV:链路费用变化(以yz为例)距离向量...

    系列文章目录

    第九章计算机网络之网络层之路由算法3距离向量路由算法


    三、距离向量路由算法

    距离向量(Distance Vector)路由算法

    在这里插入图片描述

    Bellman-Ford举例

    在这里插入图片描述

    距离向量路由算法

    在这里插入图片描述
    异步迭代:作为每一个路由器不是同步迭代同步结束。
    邻居再计算,邻居再选择是否通告邻居(邻居的邻居)。

    在这里插入图片描述

    距离向量路由算法举例(来自邻居的DV更新)

    其它的邻居节点还未将自己的距离向量交换过来,所以是无穷大。
    x在计算的时候,将7更新为3,根据距离向量路由算法,当x向量发生变化时候,它便会把新的向量告知给邻居。同时向量y与z也在计算,如果发生改变也会告知其邻居
    在这里插入图片描述在这里插入图片描述
    最终就趋向实际dx,y,z了,将该值更新到转发表中。

    距离向量DV:链路费用变化(以yz为例)

    y检测到距离的改变,同理x也能检测到距离的改变
    同时也会告知x,以z为例。

    在这里插入图片描述

    距离向量DV:无穷计数问题(以yz为例)

    当y由4变成60时,还没告诉z,z之前告诉,z到x是5,现在y到x是60,根据距离向量路由算法得现在最短路径为5(z到x)+1(y到z)= 6

    在这里插入图片描述

    一直重复下去,直到,z发现经过y到x(51)比直接到x距离长(50),这样重复很多次,如果50或者60变成很大时候,就会出现无穷计数问题。

    无穷计数的解决办法(毒性逆转)

    在这里插入图片描述

    无穷计数的解决办法(定义最大度量)

    虽然可能出现无穷计数问题,但是通过定义最大度量值的方法,会在有限的交换过程中到达最终达到收敛,最终反应网络实际状态。
    16跳步认为不可抵达即无穷大
    在实际的网络中,交换的距离向量不是面向路由器而是网络。
    前面讲算法原理用路由器结点便于理解
    R2收到16时候就知道该子网不可到达了,由于,由于原先认为可达14,现在不可达,距离向量发生变化,依然会把16跳交换给R1
    R1,无穷大+1=无穷大,所以还是16跳(R1由于一开始不可以到达该子网(认为大于16跳)通过R2来到子网+1转发)
    到t15 R1 和 R2 知道网络不可抵达

    在这里插入图片描述

    展开全文
  • 计算机网络网络层之距离向量路由算法(2) 距离向量路由算法:举例 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-M09lKkrU-1637152980472)(C:\Users\13559\AppData\Roaming\Typora\typora-...

    计算机网络网络层之距离向量路由算法(2)

    TIPS:知识出自哈尔滨工业大学李全龙老师的课程讲解。

    距离向量路由算法:举例

    效果图

    效果图

    距离向量DV(路由算法):链路费用发生变化

    链路费用变化

    • 结点检测本地链路费用变化
    • 更新路由信息,重新计算距离向量
    • 如果DV改变,通告所有邻居

    效果图

    距离向量DV(路由算法):无穷计数问题

    效果图

    效果图

    效果图

    展开全文
  • 距离向量路由算法(例题) 如图子网中采用距离向量算法,C节点路由器收到B节点的距离向量为(5,0,8,12,6,2),收到D的向量为(16,12,6,0,9,10),收到E向量为(7,6,3,9,0,4),经过测量,C节点到B、...
  • 基本概念 距离向量路由算法 链路状态路由选择算法 其他路由选择算法
  • 距离向量路由算法模拟

    热门讨论 2010-02-08 09:13:22
    模拟路由算法,自己初始化网络拓扑,显示各路由器路由表变化。
  • 距离向量路由算法及举例

    千次阅读 2013-10-19 22:06:45
    距离向量路由算法(Bellman-Ford Routing Algorithm),也叫做最大流量演算法(Ford-Fulkerson Algorithm),其被距离向量协议作为一个算法,如RIP, BGP, ISO IDRP, NOVELL IPX。使用这个算法的路由器必须掌握这个距离表...
  • java多线程实现距离向量路由算法

    热门讨论 2011-04-07 15:49:54
    作为一个实验课题,本项目实现了应用java多线程来实现距离向量算法,可以对此算法深入的理解
  • 计算机网络,基于距离矢量路由算法
  • 计算机网络网络层之距离向量路由算法(1) TIPS:知识出自哈尔滨工业大学李全龙老师的课程讲解。 Bellman-Ford方程(动态规划) 令: dx(y):=从x到y最短路径的费用(距离) d_x(y):=从x到y最短路径的费用(距离) ...
  • 距离向量路由相关原理及实现

    千次阅读 2018-11-19 23:48:29
    一、距离矢量路由协议的特点 ...每台路由器都必须在将从邻居学到的路由转发给其它路由器之前,运行路由算法,所以网络的规模越大,其收敛速度越慢 3、更新的是“路由条目”,一条重要的链路如果发生变化,意味...
  • 距离向量路由选择

    千次阅读 2019-11-06 21:50:43
    距离向量路由选择是通过对Bellman-Ford算法进行适当修改,找到任意两结点之间的最短路径。 ​ 先介绍一下Bellman-Ford算法: 1 Bellman-Ford算法 ​ 这个算法基于这样一个事实,如果结点 i 的所有邻站都知道到...
  • 距离向量算法

    万次阅读 多人点赞 2019-06-08 20:12:10
    算法执行步骤 从相邻的 X 路由器接收发送过来的 RIP 报文 将该 RIP 报文中的下一跳地址修改为 X,且跳数增加 1 对每个项目执行如下步骤 a.若原路由表没有 RIP 中的目的网络 N,直接添加到原路由表中 b.若原路由表中...
  • 【2016】408联考真题(距离-向量路由算法

    万次阅读 多人点赞 2018-04-02 13:32:16
    该子网采用距离向量路由算法,下面的向量刚刚到达路由器C,来自B的向量为(5,0,8,12,6,2);来自D的向量为(16,12,6,0,9,10);来自E的向量为(7,6,3,9,0,4)。经过测量,C到B,D,E的延迟分别是6,3,5.那么C到达所有结点的...
  • RIP是指路由信息协议,基于距离向量算法;OSPF是指开放最短路径优先协议,基于链路状态算法。 D-V 算法中,每个节点只需要维护自身的距离向量,且只需要与自己相连的链路的状态,需要的存储空间小;而L- S 算法中...
  • 该程序是使用的python编写的关于学习型交换机和距离向量路由的路由器算法
  • 演示“距离矢量路由算法”工作原理现代计算机网络通常使用动态路由算法,因为这类算法能够适应网络的拓扑和流量变化,其中最流行的两种动态路由算法是“距离矢量路由算法”和“链路状态路由算法”。距离矢量路由算法...
  • 文章目录 0.思维导图 1.... 2.... 3.动态路由的两种算法:链路状态路由算法和距离向量路由算法 4....路由器转发分组是通过...3.动态路由的两种算法:链路状态路由算法和距离向量路由算法 链路状态路由算法和距.
  • 基于状态稳定性更新的距离向量路由算法.pdf 基于状态稳定性更新的距离向量路由算法.pdf 基于状态稳定性更新的距离向量路由算法.pdf
  • 第二步 看看C依次到达ABCDEF的距离 ;C到A 可以有三条路c-b-a=【c到b是5+原路由需要2+4】=11 c-d-a=3+16=19 c-e-a=5+7=12 则C到A的期望=(11+19+12)/3=14 依次算C到B期望=(6+15+12)/3 C到C的期望=0 CD =(18+3+14...
  • } } //距离矢量路由算法 void Distance_vector_routing(G* g) { int count = 0 ; //更新计数 bool is_change; //路由表是否有变化的布尔值 //还没稳定,就进行一轮更新 do { count++; is_change = false; //先把...
  • RIP协议和距离向量算法① RIP协议定义② RIP协议:交换对象、交换周期、交换内容③ 距离向量算法例题1例题2④ RIP协议的报文格式⑤ RIP协议:好消息传得快,坏消息传得慢三. OSPF协议与链路状态算法① OSPF协议定义...
  • 分析链路状态路由算法与距离向量路由算法的区别。 IP路由选择协议一般有三种。1。距离矢量协议。2。链路状态协议。3.两者混合。距离向量协议是基于距离矢量算法的,通过判断路径查找到最佳路由。代表协议有RIP,IGRP...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,829
精华内容 4,331
关键字:

距离向量路由算法

友情链接: monitoring.rar