Archive

Posts Tagged ‘PeerSim’

PeerSim 源代码分析之一:程序入口

March 17th, 2011 leeing No comments

PeerSim 的文档资料很少,有很多地方看上去概念很模糊,去年曾经翻译过官方的几篇文档,按顺序汇总如下:

当时翻译的时候,并没有深入地去学习,最近由于仿真的需要,又静下心来研究了几天,有些东西发现在文档中是无法得到一个很清晰的解释,看了一下PeerSim的源代码规模也并不是很大,所以决定 RTFSC (Read the F *** ing Source Code : –) ,源代码本身就是最好的学习资料,当然,这需要足够的耐心。

不过不得不说的是 PeerSim 的源代码的缩进真是有点混乱。

首先,是程序的入口 peersim.Simulator.java:

package peersim;

import java.io.*;

import peersim.cdsim.*;
import peersim.config.*;
import peersim.core.*;
import peersim.edsim.*;

/**
 * peersim.Simulator.java
 *
 * 程序的入口,主要作用就是读取配置文件,并根据仿真类型来调用仿真引擎。
 */
public class Simulator {

    // 某些静态变量,一看就懂。

    public static final int CDSIM = 0;

    public static final int EDSIM = 1;

    public static final int UNKNOWN = -1;

    protected static final String[] simName = {
        "peersim.cdsim.CDSimulator",
        "peersim.edsim.EDSimulator",};

    // 配置文件中的 simulation.experiments 参数,如果没有标明,则默认为
    // 进行1次实验
    public static final String PAR_EXPS = "simulation.experiments";

    // 设置程序的输出,默认为 stdout
    public static final String PAR_REDIRECT = "simulation.stdout";

    // 仿真类型,有3种,即 CDSIM,EDSIM 和 UNKNOWN
    private static int simID = UNKNOWN;

    // 根据配置文件返回当前的仿真类型
    public static int getSimID() {

        if (simID == UNKNOWN) {
            // 怎么判断类型?很简单,看配置文件里有没有
	    // 定义 simulation.cycles 的参数
            if (CDSimulator.isConfigurationCycleDriven()) {
                simID = CDSIM;
            } else if (EDSimulator.isConfigurationEventDriven()) {
                // 类似的,如果配置文件里有 simulation.endtime 的定义,
                // 就是 Event-driven 模式
                simID = EDSIM;
            }
        }
        return simID;
    }

    // 程序的入口,运行时要将配置文件的位置作为参数提供给 Simulator
    public static void main(String[] args) {
        long time = System.currentTimeMillis();

        System.err.println("Simulator: loading configuration");

        // 读入配置文件
        Configuration.setConfig(new ParsedProperties(args));

        // 设置输出到某一个 PrintStream,默认为 System.out
        PrintStream newout =(PrintStream)
		Configuration.getInstance(PAR_REDIRECT, System.out);

        if (newout != System.out) {
            System.setOut(newout);
        }

        // 设置实验的次数,默认为1次,可以通过设置 simulation.experiments
		// 来改变默认值。
        // 在这里说一下,PeerSim 的配置文件学习是第一步,想要编写仿真
        // 首先就要明白 PeerSim 是如何解析配置文件的,具体的解析可以看
        // peersim.config 包里边的类。
        int exps = Configuration.getInt(PAR_EXPS, 1);

        // 读取实验的类型,如果不能确定仿真类型,就退出。
        final int SIMID = getSimID();
        if (SIMID == UNKNOWN) {
            System.err.println(
    	"Simulator: unable to determine simulation engine type");
            return;
        }

        try {

            for (int k = 0; k < exps; ++k) { // 一次循环进行一次实验
                if (k > 0) {
                    // 仿真过程中的种子,可以通过在配置文件中的
		    	// random.seed 来设置。
                    // 如果不设置的话,就将当前的时间作为种子
                    long seed = CommonState.r.nextLong();
                    CommonState.initializeRandom(seed);
                }
                System.err.print(
			"Simulator: starting experiment " + k);
                System.err.println(" invoking " + simName[SIMID]);
                System.err.println("Random seed: "
			+ CommonState.r.getLastSeed());
                System.out.println("\n\n");

                // 作者说可以用反射机制的,不过这样写容易理解。
  			// 我个人觉得没必要用反射。
                // 根据仿真的类型,调用相应的仿真引擎。
                switch (SIMID) {
                    case CDSIM:
                        CDSimulator.nextExperiment();
				// 具体怎么运行且听下文分解
                        break;
                    case EDSIM:
                        EDSimulator.nextExperiment();
				// 同上
                        break;
                }
            }

        } catch (MissingParameterException e) {
            System.err.println(e + "");
            System.exit(1);
        } catch (IllegalParameterException e) {
            System.err.println(e + "");
            System.exit(1);
        }

        // undocumented testing capabilities
        // 这一部份源码没有任何说明,看样子作者是用来做测试的
        if (Configuration.contains("__t")) {
            System.out.println(System.currentTimeMillis() - time);
        }
        if (Configuration.contains("__x")) {
            Network.test();
        }

    }
}

好吧,程序的入口就分析到这里。下次就分析 Cycle-based 仿真核心 CDSimulator 的代码。

Categories: PeerSim Tags:

PeerSim 中文教程:Event-driven 模型

July 4th, 2010 leeing No comments

1. 介绍

本教程使用Event-driven模型来演示一个简单的例子,仍然使用的是gossip-based平均数协议,对消息的发送将进行更细节的建模;通过与cycle-based模型的对比,可以发现本协议存在的问题。

在Event-based模型中,除了时间管理和control传递给protocols的方式以外,其它与cycle-based模型相同。不可执行的Protocols(只用于存储数据,比如只存储邻居节点的linkable协议,或存储数值的vectors)可以以同样的方式应用和初始化,在peersim.cdsim包之外的controls也都可以使用。在默认情况下,在cycle-based模型中,controls会的每个周期中调用 ,但在event-based模型中,它们需要进行明确的调度,因为事件驱动模型并不存在周期的概念。

显然,我们可以编写专用于event-based模型的controls,即可以给协议发送事件(消息)。在很多情况下,这是必要的,因为系统经常完全或部分地由外部事件如用户的查询来驱动 ,这能很好地用由生成这些事件,并且驱动仿真执行的controls进行建模。

有些组件是不可用的。例如依赖于静态类peersim.cdsim.CDState(它提供了读取cycle相关的全局状态的接口)的所有组件。我们的经验是,很多依赖于这个状态的 cycle-based 组件可以经过简单的修改并删除这个依赖。

然而,可能有些令人吃惊的是,实现了cycle-based接口的peersim.cdsim.CDProtocol也可以使用于event-based模型,但是必须指出,在大部份的情况下这样做没有什么意义。然而,这个特性的有用之处在于:它让周期性地调用protocols变得很简单,这是一个几乎对所有与housekeeping,失效检测和sending heartbeat message有关的P2P协议来说典型的特性。

2. Protocol

下面以event-based模型来实现平均数协议:

package example.edaggregation;

import peersim.vector.SingleValueHolder;
import peersim.config.*;
import peersim.core.*;
import peersim.transport.Transport;
import peersim.cdsim.CDProtocol;
import peersim.edsim.EDProtocol;

/**
* Event driven version of epidemic averaging.
*/
public class AverageED extends SingleValueHolder
			implements CDProtocol, EDProtocol {

首先,这里同时实现了EDProtocol和CDProtocol接口,前者能让这个类能处理输入的消息,后者则可能令人困惑,因为它属于cycle-based模型的接口。但注意 event-based 的协议不是必须实现CDProtocol接口的,然而想要实现一个可以周期性取得control的协议时,可以通过实现CDProtocol接口,并在配置文件中设置一个CDScheduler 来实现。这样,代码就显得更清晰:以一个单独的组件来管理周期性的执行,而且能单独地进行配置。最后,我们还能简单地将 cycle-based 的协议移植到 event-based 模型上。

Read more…

Categories: P2P, PeerSim Tags:

PeerSim 中文教程:拓扑生成器

July 2nd, 2010 leeing No comments

本教程描述了如何构建一个新的 PeerSim 拓扑生成器。

1. 什么是拓扑?为什么它很重要?

在一个大型的动态P2P系统中,节点没有关于整个网络的信息,而所有的节点都可能拥有一些邻居节点,即节点能”感知”的peers,这种”感知”的关系就定义了一个覆盖网络,这是P2P系统中的一个基本概念。

很多P2P协议都需要在多个不同的网络拓扑上进行实验。PeerSim中的peersim.dynamic.Wire*类已经包含了很多拓扑结构,可以直接用来对linkable协议进行初始化,本教程将展示如何构建一个自定义的拓扑生成器。

2. 一个用来模拟Internet的简单模型

下面我们将编写一个拓扑生成器来构建类似于Internet的树状拓扑,整个构建过程基于一个特定的,与位置相关的preferential attachment方法,编写规则很简单,并且会考虑几何和网络的限制以更好地模拟真实的网络。Preferential attachment由参数a来调整,这个参数能扩大或减少几何位置所带来的影响。

这个规则的策略如下:给定一个单位正方形,将x0置于中心,即x0 = (0.5,0.5),这个节点被称为root,令W()为与root相隔的跳数(hops),对于i=1 … n-1,随机在单位正方形中选择一个xi,然后选择使下面的表达式值最小的节点xj来连接它:

在这里dist()是欧几里德距离而a (alpha)是权重参数,显然,

通过这个方案我们得到了一个x0以为根的树。这个拓扑中每个节点(除了root外)的出度都为1,如果想更深入地理解这个模型,可以参考下面的文章:

  • Heuristically Optimized Trade-offs: A New Paradigm for Power Laws in the Internet
  • Degree distributions of the FKP network model
  • On Power-Law Relationships of the Internet Topology

3. 如何编码

我们的目标是编写一个可以根据 a (alpha)参数生成所需拓扑的PeerSim组件,并且能对生成的拓扑进行分析。这个拓扑可以在仿真过程中逐步生成,也可以用一个步骤生成拓扑,在这里我们倾向后者。为了构建需要的拓扑结构,我们需要下面的组件(注意这只是其中一种方案)。

  • 一个protocol 类,可以存储坐标,它不具备行为元素,只是一个普通的容器。
  • 一个initializer 类,可以为每个节点设置坐标值。
  • 一个control 类, 可在一个任意的linkable协议中根据坐标连接拓扑(在节点间添加link)
  • 一个observer 类,将拓扑结构打印到一个文件中(例如用GnuPlot对图进行可视化)。
  • 一个observer 类,用来收集节点入度的分布的统计数据
  • 一个observer 类,用来测试对随机节点失效的健壮性

在下节我们将看到,一些我们列出来的类是PeerSim中的基本组件,它们都实现了Linkable接口,Linkable以模块化的方式为用户提供了一个能处理任何拓扑结构的抽象。

Read more…

Categories: P2P, PeerSim Tags:

PeerSim 中文教程:编写一个新协议

July 2nd, 2010 leeing No comments

本文的目的是在PeerSim中用Cycle-based模型实现一个简单的负载均衡算法。节点的状态有两种值:本地负载(local load)和配额(quota),其中配额是指节点在每个周期中允许传输的“负载”的大小。配额是必要的,是一个时间单元中能传输的负载上限。每个节点与和它距离最远的邻居节点交换配额值,这里“距离最远”是指与当前节点的负载差异最大。经过对比距离,协议将在负载均衡时选用push或pull的方式。

在每个周期之后,配额值将会被存储。协议并不关心拓扑管理,它依赖于其它组件来访问邻居节点(例如,Newscast,或者由IdleProtocol实现的静态拓扑)。

一. 必要的组件

一般来说只编写一个协议类是不足够的,还需要一些附加的组件。例如,为了在每个周期结束时为每个节点存储配额值,需要一个特定的Control对象。基本上来说,PeerSim是一个可替换的组件集合,所以在开发时需要注意模块化以让代码尽可能重用,出于这样的目的,我们这样设计下面的类:

  • protocol 它基于peersim.vector.SimpleValueHolder,这是一个简单的基类,用于访问一个浮点变量。Aggreation协议也使用了同样的基类。
  • ResetQuota 用于在每个周期结束时存储每个节点配额的control。
  • QuotaObserver 一个control,用于监视quota参数,即覆盖网中交换的流量大小。
  • initialization 这是在aggregation示例中的初始化器,这里也可以直接使用,因为它们实现了同样的接口SingleValueHolder。注意在example包中提供的初始化器是轻量级的,开发者应当更多地使用peersim.vector.*包中的初始化器。
  • observers 可以使用aggreagation.AverageObserver,因为这些组件实现了相同接口。

Read more…

Categories: P2P, PeerSim Tags:

PeerSim 中文教程:解析 Cycle-based 模式仿真

June 30th, 2010 leeing 6 comments

本文介绍了PeerSim的基本概念,并解析了两个示例以更清晰地说明PeeSim的仿真流程。

Peersim支持两种仿真模式,即Cycle-based的模型和传统的event-based的模型,本文专注于前者,

Cycle-based模型是一个简化的模型,拥有更好的伸缩性及性能,在拥有4GB内存的情况下,event-driven模式目前最多支持十万节点级别,而cycle-based模式则支持千万个节点级别。 但是Cycle-based模型缺少对传输层的仿真和并行处理,节点之间是直接通信的,仿真核心以一定的顺序周期性地给以节点控制。在运行时,可以进行任意的操作,如调用其它对象的方法并执行一些计算。

Cycle-based模型损失了一些真实性,虽然一些简单的协议可以忽略这些差别,但是在选择使用这个模型时,需要注意这些区别。我们可以相对简单地将Cycle-based的仿真移植到Event-driven引擎上,但在本文中不讨论这个话题。

一.基本介绍

PeerSim鼓励基于接口的模块化编程,每一个组件都能被其它实现了相同接口的组件代替,一般的仿真过程如下:

  1. 选择网络大小(即节点数量)。
  2. 选择要实验的一个或多个协议并进行初始化。
  3. 选择一个或多个Control对象来监视感兴趣的属性,并在仿真时修改一些参数(比如,网络大小,协议的内部状态,等等)。
  4. 根据配置文件,调用Simulator类运行仿真。

在仿真时创建的对象都是实现了一个或多个接口的类的实例,主要的接口如下所示:

Node P2P网络是由节点组成的,节点是协议的容器。Node接口提供了对节点所包含的协议的访问方法,并为节点提供了固定的ID。
CDProtocol 这是一个特定的协议,被设计用来在Cycle-based模型中运行,它只定义了在每一个周期中要运行的操作。
Linkable 一般都由协议来实现,这个接口为其它协议提供了访问邻居节点集合的服务,节点间相同的linkable协议类的实例定义了一个覆盖网络。
Control 实现了这个接口的类可以在仿真期间的某个时间点调度执行,这些类一般用于观察或修改仿真过程。

Cycle-based仿真的生命周期是这样的:

  1. 读取配置文件(通过命令行参数传递进来),然后仿真器初始化网络中的节点和节点中的协议,每个节点都拥有相同的协议栈。节点和协议的实例是通过克隆来创建的,只有一个原型是通过构造方法创建,其它的节点和协议都是从这个原型中克隆而来。基于这个原因,协议类中clone方法的实现是很重要的。
  2. 初始化操作,设置每个协议的初始状态。初始化阶段是由Control对象控制运行的,仅在实验开始时运行一次。在配置文件中,初始化的组件可以由init前缀识别,在下面讨论的initializer对象也是controls,但为了标记其功能以区别于一般的Control对象,它被配置用来在初始阶段运行。
  3. 在初始化完成后,Cycle-based引擎在每一个周期中调用所有组件(protocols和controls)一次,直到完成了指定的周期数,或者某个组件决定终止仿真为止。在PeerSim中每一个对象(controls和protocols)都被赋以一个Scheduler对象,它定义了什么时候本组件将会被执行。在默认情况下,所有对象都会在每个周期中运行。但我们也可以配置一个protocol或control只在某些特定的周期中运行,也可以在每一个周期中指定组件的执行顺序。

Read more…

Categories: PeerSim Tags: ,