Jul 4 2010

PeerSim 中文教程:Event-driven 模型

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 模型上。

Continue reading


Jul 2 2010

PeerSim 中文教程:拓扑生成器

本教程描述了如何构建一个新的 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以模块化的方式为用户提供了一个能处理任何拓扑结构的抽象。

Continue reading


Jul 2 2010

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

本文的目的是在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,因为这些组件实现了相同接口。

Continue reading


Jan 20 2010

常用的 P2P 仿真平台

由于网络的研究和设计的复杂度很大,不能给出抽象的模型,且实验成本很高。研究人员对真实或接近真实的大规模网络实验环境的需求越来越强烈。大规模网络试验环境是当前计算机网络研究迫切需要解决的问题。

首先看一下目前使用较多的一些开源的P2P网络仿真器情况,其它的一些仿真器由于使用的人较少或者多年没有更新,所以没有在这里提及。

  • PeerSim 

PeerSim 是一个模拟P2P overlay网络的软件,支持结构化和非结构化P2P网络模拟。PeerSim有两种模拟方式,cycle-based和event-driven。event-driven模式相对精确,cycle-based模式缺少传输层的模拟而且不能起到并发控制的作用,但占用资源少以适合于大规模的模拟,根据官方所发表的一篇最新论文,在拥有4GB内存的情况下,event-driven模式目前最多支持十万节点级别,而cycle-based模式则支持千万个节点级别。 

PeerSim本身不带任何具体的协议实现,但是提供了很好的扩展性,目前已经有研究人员在其基础上实现了Bandwidth management protocol,a fault-tolerant FSM,Pastry,Chord,Skipnet,BitTorrent,Aggregation,SG-1,Peer sampling service,T-Man,PdProtocol,Slacer等协议,可以在项目主页上下载,但官方并不提供直接支持。

PeerSim采用Java语言,截止到2009年12月,PeerSim 下载次数已经超过12000次,已经有150多篇重要的P2P方面论文中使用PeerSim 模拟器,当中很少一部分是由 PeerSim 的作者编写的,但是PeerSim不支持分布式模拟。

更新情况:最新的主要版本1.0.0发布于2005年11月11日,后续的版本的更新修改事实上都极小,目前最高版本是2009年9月29日发布的1.0.5版本。

文档情况:官方只发布三篇文档,无论是cycle-based还是event-driven模式的文档都很少,源代码虽然不是很多,但是缺少必要的注释。

项目主页http://peersim.sourceforge.net/

  • Oversim

OverSim运行在类UNIX系统,采取OMNeT++ 实现其网络层,支持无结构和结构化P2P协议,已经实现了Chord, Pastry, Bamboo, Koorde, Broose, Kademlia, GIA, Vast和Publish-Subscribe for MMOGs协议。

OverSim 拥有图形化的交互界面,方便验证和调试。有INETUnderlying 网络和 Simple Underlying网络用于模拟网络层。能够模拟10万节点以上的规模,模拟代码易转化成为仿真代码,现在 OverSim 已经成功将一个基于P2P的DNS系统部署在PlanetLab 当中,实现了P2PNS系统,部署于450个节点上。

OverSim的实现语言为C++,综合来看,Oversim也是一个优秀的仿真工具。

更新情况:最近更新时间为2009年9月28日,近年来更新最频繁的模拟软件。

文档情况:很少。

项目主页http://www.oversim.org/

 

  • P2Psim

P2Psim 是一个免费的,多线程的,不关联的事件模拟器,用来评估,审查,和探索peer-to-peer协议,运行在UNIX-Like系统上,采用C++语言。P2Psim支持搅动、支持迭代和递归路由查询、可以通过继承来实现新协议、支持多种底层网络拓扑格式、支持一种网络时延模型;但是不支持分布式模拟和带宽变动,节点规模小(3000节点)。已经实现的协议有:Chord, Koorde, Kelips, Tapestry, Kademlia。

更新情况:最新版本发布于 2005年4月18日,四年半没有任何更新。

文档情况:不完善,基本没有文档。

项目主页http://pdos.csail.mit.edu/P2Psim/

综合各方面考虑,觉得 Oversim 和 PeerSim 都是比较好的选择。


Jan 20 2010

CDN 仿真器现状和 CDNsim

开发新的网络服务需要大量的投资,因此有必要在一个可控的仿真环境下建立原型,监控和预测服务的行为。很多技术已经被提出以提高CDN的性能,但是大部分却没有被CDN提供商采用,这是因为这些技术并没有广泛地在一个仿真测试床上进行评估,而一些学术性的CDN网络,如CoralCDN和Codeen则是运行上PlanetLab上,但PlanetLab是一个黑箱且需要大量学术界的人员参与,在这样的环境下开发新技术显得很困难甚至不可能。

因此有必要开发一种在真实仿真环境下的CDN模拟器,而且必须是可靠和节省内存的,要求对大规模的CDN网络能进行较细节的仿真。大部分的CDN仿真系统没有考虑几个关键的因素,如网络中可能出现的瓶颈,每个网络元素(router,surrogate server等)可以处理的的session数目等等。这样,仿真结果可能产生误导。因为它们只是通过遍历每个节点来测量而没有考虑TCP/IP的网络架构;另一方面,现存的很多网络模拟器不能有效地仿真Internet的架构,例如NS-2是一个离散事件仿真框架,通常用来仿真TCP/IP协议,流量控制等,然而它需要大量的内存来仿真大规模的网络。同样的,一些测试床不能由非研究机构自由进行仿真,且PlanetLab的一个显著缺点是仿真不可以重复进行。

Testbed TCP/IP 内存占用 可重复性 规模 可用性 运行环境
CDNsimulator

(ns2&logsim)

本地
CDN simulator

[Bent et al 2004]

本地
CDN simulator

[Kulkarni et al. 2003]

本地
Codeen 限制 实时
CoralCDN 限制 实时
Globule 开源 实时
CDNsim 开源 本地

从上面的讨论可以看出,目前缺少可靠而且可伸缩的CDN仿真器,且CDN仿真器只能以有限的细节来模拟真实的网络(例如对网络的传输时间进行静态估计),总的来说,开发一个完整的CDN仿真器,包括相关的应用程序和网络工具,是一个极消耗时间的任务,因为典型的网络或缓存仿真器不能用在CDN仿真中使用。

专门用于CDN仿真的CDNsim是基于OMNet++仿真环境和INET框架开发的,其中:

  1. 基于离散事件的OMNeT++,是一个免费的、开源的多协议网络仿真软件,在网络仿真领域中占有十分重要的地位。OMNeT++英文全称是Objective Modular Network Testbed in C++,是近年来在科学和工业领域里逐渐流行的一种基于组件的模块化的开放的网络仿真平台。OMNeT++作为离散事件仿真器,具备强大完善的图形界面接口。
  2. INET框架则是在OMNet++环境中的开源通信网络仿真包,它包括几个Internet协议,如UDP,TCP,SCTP,IP,IPV6,Ethernet,PPP,IEEE 802.11,MPLS,OSPF等等。

CDNsim只是使用OMNet++中的基本的网络操作,如TCP/IP传送和离散事件的调度。请求路由,内容分发和管理以及所有CDN的特性则是由CDNsim本身完成的。


Dec 31 2009

PlanetLab

         估计明年主要工作都集中在P2P-CDN的仿真器上,之前做过一些调研,是关于PlanetLab的,而国内关注的人极少,只有少数一些大学的实验室有过相关的应用,而且由于Cernet作为一个整体被除名,中国的使用人数应当大减了。就实验室的项目来说,原本我以为是要设计一个P2P-CDN的混合系统,现在已经变更为设计一个P2P-CDN的模拟器,所以PlanetLab是不可能得到应用,不过这里的一些信息可能对需要它的人有用。

—————–华丽丽的分割线———————

         PlanetLab是一个全球性的研究网络,用于新型网络服务的开发。自从2003年起,超过1,000个来自顶级学术机构和业界实验室在PlanetLab上开发了新技术包括:分布式存储、网络印射、P2P系统、DHT(分布式哈希表)和查询处理。并且值得关注的是在这个平台上,P2P分布式计算的项目很多,甚至是基于P2P的CDN实现和部署。

 http://www.planet-lab.org/

         截止至2009年12月,PlanetLab目前拥有1063个节点和491个站点,很多世界一流大学和行业研究实验室成为PlanetLab计划的联盟成员,其中包括AT&T实验室、剑桥大学、法国电信、HP、Google、NEC实验室、哈佛大学、普林斯顿大学和加州大学伯克利分校连同中国华为集团、以及Internet2机构。2009年5月,PlanetLab中心升级至4.3版本,可以支持新的节点类型(如无线节点),同时加入一些新的GUI特性。

          PlanetLab的主要目标之一是用作重叠网络的一个测试床。研究组能够请求一个PlanetLab分片,其中他们能够试验各种全球规模的服务,包括文件共享和网络内置存储、内容分发网络、路由和组播重叠网、QoS重叠网、可扩展的对象定位、可扩展的事件传播、异常检测机制和网络测量工具。目前有数百个活跃的研究项目运行于PlanetLab之上。

         对研究人员而言使用PlanetLab的好处是:可以在真实世界条件下大规模试验新服务,因为节点广泛分布于Internet,是一个由遍布世界各地的服务器组成的网络,能够观察并对网络行为做出反应;从位于许多数据源和数据终点的邻近范围而受益;从分布于多个管理的边界而受益。

         PlanetLab是一个大规模互联网服务的测试床,在其上更多的狭窄定义的虚拟测试床能够被部署)。网络研究人员能够使用这项基础设施来试验对于Internet协议簇的修改和扩展。除了支持短期试验外,PlanetLab也设计用来支持长期运行的服务,这些服务支持一个用户基础(用户群)。即PlanetLab不但是一个测试床,也是一个部署平台,支持一个应用的无缝迁移,从早期原型,通过多次设计迭代,最后转变为一项持续演进的成熟服务。

          2004 年12月27日中国教育和科研计算机网(CERNET)宣布,CERNET已加入PlanetLab,首先在中国20个城市的25所大学( 包括清华,北大,北航,北邮 )中设立50个 PlanetLab节点,这使得CERNET成为亚洲第一个地区性PlanetLab研究中心,但是在2009年6月1日,PlanetLab重新考虑了CERNET地位,指出PlanetLab接受的成员是研究机构/大学,而不是“国家组织”如CERNET,因此要求所有CERNET地址的中国大学重新申请为独立成员。个人不能直接参与到PlanetLab中,必须是PlanetLab的成员。截止到写这篇文章为止,国内也仅有少数的大学通过审批,更多的则是处于pending状态,更多被除名的大学则没有重新提交过申请。

          建立在PlanetLab之上的一些成功案例,在这里主要是针对P2P-CDN系统来说明的:

CoralCDN

基于P2P的CDN网络:www.coralcdn.org/

CoralCDN是一个免费的P2P内容分发网络,由世界范围内的web代理和域名服务器组成,它允许用户在之上建立一个高性能大需求的web网站。它于2004年的3月,在PlanetLab上进行测试。可以免费地下载CoralCDN的源代码,源代码是由C++完成的,超过一万行。

CoDeeNA Content Distribution Network for PlanetLab

主页:http://codeen.cs.princeton.edu/

CoDeeN是由普林斯顿大学开发的学术性的CDN网络实验平台,且这个CDN网络由众多的PlanetLab节点组成,当前很多缓存服务器部署在PlanetLab的节点之上,这些缓存服务器同时作为request redirectors和server surrogates,它们相互合作提供了一个快速而健壮的web内容分发服务。

同时,它还包括以下的子项目:

最后,特别推荐一篇文章:http://ww2.cs.mu.oz.au/~apathan/CDNs.html,具体描述了CDN技术的前沿方向。