洪泛路由模拟

发表于 | 分类于

本文主要是以洪泛路由的一个简单模拟，一切都源于一个朋友的请求，所以花了大概两个小时的时间完成了这么一个简单的实现。

不知道大家对洪泛算法有没有过一些了解，总之我在这之前是完全没有听说有这么一个算法存在。如果没有了解过的话，可以参考如下描述（源自百度百科的拷贝）：

洪泛不要求维护网络的拓扑结构和相关的路由计算，仅要求接收到信息的节点以广播方式转发数据包。例如，源节点希望发送一段数据给目标节点。源节点首先通过网络将数据副本传送给它的每个邻居节点，每个邻居节点再将数据传送给各自的除发送数据来的节点之外的其他。如此继续下去，直到数据传送至目标节点或者数据设定的生存期限(TTL,Time To Live)为0为止。

通过这么简短的一句话，大家也对于这个算法有了一个大致地了解，下面我们来谈谈对它的实现，

首先，我选用Java作为实现语言而不是C或者C++的原因主要有如下两点：

  1. Java作为一种面向对象的语句使我们可以更好地对数据进行抽象，如路由中的节点、报文甚至通道。
  2. 我对C与C++等不熟悉，也就没有必要为了这么简单一个实现去了解它们的语法了。

其次，既然是模拟通信，那么我们就必须先要有一份网络拓朴图，下图即为此次我所使用的拓朴图。

对于实现来说，我们需要对这个图进行抽象化。此次我主要将图抽象为两个对象，一个是节点对象，用于描述图中各主机的关联关系，第二个是报文对象，用于描述传输的数据。

洪泛路由模拟

对于一个模拟程序来说，我们需要指定一个报文的发出主机与目的主机，而在洪泛算法里，报文每到一个主机后会对与之相邻且未接收过该份报文的主机进行广播，在这里我们需要给一个最大的跳跃次数，即尝试多少次广播后，若还没有到达目标主机，我们会将该份报文丢弃。

这里，我选用初始节点为：节点1、目标节点为：节点7、最大跳跃次数为3。下面给出相关的代码实现：

首先，对节点对象的进行封装：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class Node {
 
    // 结点名称
    private String name;
    // 是否结束节点
    private boolean isEnd = false;
    private Set<Node> relativeNodes = new HashSet<Node>();
    
    public Node(String name) {
        this.name = name;
    }
    
    public void link(Node... nodes) {
        for (Node node : nodes) {
            this.relativeNodes.add(node);
            node.getRelativeNodes().add(this);
        }
    }
 
    public Set<Node> getRelativeNodes() {
        return relativeNodes;
    }
 
    public void accept(Packet packet) {
        // 记录当前节点
        packet.getRoute().add(this.name);
        
        // 如果计数器仍然等于零 或 当前节点已经是最终节点，则打印路由信息
        // 否则继续传输，否则输出报文传输路径
        if (this.isEnd) {
            System.out.println("传输成功: " + packet);
            
        } else if (packet.getCounter() == 0) {
            System.out.println("传输失败，已超出生命周期: " + packet);
            
        } else {
            packet.decrement();
            boolean isAvailableNodeExist = false;
            for (Node nextNode : relativeNodes) {
                if (!packet.getRoute().contains(nextNode.getName())) {
                    isAvailableNodeExist = true;
                    nextNode.accept(packet.clone());
                }
            }
            if (!isAvailableNodeExist) {
                System.out.println("传输失败，无法找到下一结点: " + packet);
            }
        }
    }
    
    public void setEnd(boolean isEnd) {
        this.isEnd = isEnd;
    }
 
    public String getName() {
        return this.name;
    }
    
}

其次，封装报文的实现，这里继承并实现了 Cloneable 接口，让报文可以在分叉路口进行复制传递：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Packet implements Cloneable {
 
    // 计数器
    private int counter;
    // 传输路径
    private ArrayList<String> route = new ArrayList<String>();
    
    public Packet(int counter) {
        this.counter = counter;
    }
 
    public int getCounter() {
        return counter;
    }
 
    public List<String> getRoute() {
        return route;
    }
 
    public void decrement() {
        this.counter = this.counter - 1;
    }
    
    @Override
    public Packet clone() {
        Packet result = null;
        try {
            result = (Packet) super.clone();
            result.route = (ArrayList<String>) this.route.clone();
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return result;
    }
    
    @Override
    public String toString() {
        return String.format("报文的传输路径为: %s", route);
    }
    
}

最终是整个拓朴图的组织及模拟报文传递：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Runner {
 
    public static void main(String[] args) {
        
        Node node1 = new Node("1");
        Node node2 = new Node("2");
        Node node3 = new Node("3");
        Node node4 = new Node("4");
        Node node5 = new Node("5");
        Node node6 = new Node("6");
        Node node7 = new Node("7");
        Node node8 = new Node("8");
        Node node9 = new Node("9");
        Node node10 = new Node("10");
        
        node1.link(node2, node3, node6);
        node2.link(node3, node10);
        node4.link(node6);
        node5.link(node6);
        node6.link(node8);
        node7.link(node8);
        node8.link(node9, node10);
        
        // 设置节点7为终止结点
        node7.setEnd(true);
        // 从节点1出发，尝试跳跃次数为3
        node1.accept(new Packet(3));
    }    
}

运行 Runner.java 可以得到如下结果：

传输失败，已超出生命周期: 报文的传输路径为: [1, 3, 2, 10]
传输失败，无法找到下一结点: 报文的传输路径为: [1, 2, 3]
传输失败，已超出生命周期: 报文的传输路径为: [1, 2, 10, 8]
传输失败，无法找到下一结点: 报文的传输路径为: [1, 6, 4]
传输失败，无法找到下一结点: 报文的传输路径为: [1, 6, 5]
传输失败，已超出生命周期: 报文的传输路径为: [1, 6, 8, 10]
传输失败，已超出生命周期: 报文的传输路径为: [1, 6, 8, 9]
传输成功: 报文的传输路径为: [1, 6, 8, 7]

当然我们也可以自定义拓朴图，只需修改 Runner.java 的拓朴图组织及跳跃次数即可。

附： Python实现, 提取码: i8dx

qchery wechat
欢迎您扫一扫上面的微信公众号，订阅我的博客！