基于分层感知的拓扑感知流体系

基于分层感知的拓扑感知流体系

随着个人计算机性能的提高和宽带接入网络技术的广泛普及，p2p网络技术及其应用的研究得到了全面实施。在结构化的P2P系统中,通常采用分布式哈希表(DHT)来建立结点之间的拓扑关系。该技术能够提供精确的站点定位、自适应站点的动态加入和退出、不会因为网络规模的增大而导致不相称的维护开销。最近的几年,很多研究都致力于高效、结构化的P2P应用层网络的开发。目前,有许多独创性的基于DHT的结构化P2P系统。例如:Chord,CAN,Kademlia,Tapestry,Pastry,和Viceroy。它们都提供了可扩展、高效的应用层路由去定位资源服务信息。资源定位的复杂度一般为O(logN),N为系统中的节点数目,而且每个节点都维护一个小的路由表去保持和系统中其他节点的联系。但是DHT技术没有考虑到节点的异构性、维护机制也较为复杂,尤其是结点频繁加入、退出造成的网络波动会极大增加维护代价;此外,使用DHT技术会破坏结点的物理位置信息。同一个子网中的节点经过hash后可能在网络拓扑上相距甚远,还可能存在节点间的三角路由问题,极大地浪费了宝贵的网络资源、增加了链路压力。对于要求高传输效率的流媒体来说,是个不可忽视的问题。基于此,拟对传统DHT算法进行改进,提出基于chordPNS的新体系TA-chord2,其采用分层DHT技术和使用Vivaldi去预测节点之间的延迟,它是一种拓扑感知、维护开销较小、扩展性较好、负载平衡的结构化P2P流媒体系统。1节点的dht体系构建分层DHT体系的目的是让不同的节点尽其所能地改善应用层的路由性能;通过减少节点频繁加入和退出对系统的影响,降低系统的维护开销。根据服务能力的大小,节点被分成超级节点和普通节点。一个节点的服务能力包括它的处理器的能力、接口带宽、存储能力及其在系统中的稳定性等等。节点的服务能力可以用符号C表示:C=∑PiWi,i=1,2,3,4,P1为处理器能力,P2为接口带宽,P3为节点的存储能力,P4为节点在系统中的稳定性,Wi为对应的权值,其中P4的权值最大,由于DHT体系中网络波动大会导致高维护开销,而一个节点越稳定,它引起网络波动的可能性就越小。C的值代表的是节点n的能力大小,给C设置一个初始阈值,当一个节点的当前C值大于等于初始阈值,它才能变成超级节点。超级节点能够根据自己的能力动态调整自身C值的大小,以适应自身能力的变化。如在一段时间内,节点的负载比较重,它处理新任务的能力就将减少。反之,它的能力就会提升,节点根据自身的服务能力决定是否成为超级节点。开始的时候,每个节点都是作为普通节点加入系统。在一段时间后,如果节点有能力成为超级节点,它将加入由超级节点组成的管理环中并保留普通节点的所有属性和操作,超级节点形成一个管理环负责底层环的维护和查询请求。超级节点可以自由加入和离开管理环,为了减少源到目的端的延迟,可基于PNS(ProximityNeighborSelection)原则去建立超级节点的finger表。此外,为了减少管理环中的通讯开销,超级节点的标志符将使用其在普通环中的标志符。Chord提供了一种基于DHT的有效的分布式查询服务。因chord的简单性、精确的定位性、负载平衡性和良好的可扩展性,故采用chord作为分层DHT体系的基础。它把每个节点的IP地址使用hash算法映射到逻辑空间中的一个节点ID。关键字key也被hash到同一逻辑空间中的一个节点ID。节点和关键字key的标志符在环中用0到2m表示。这个环被称作ID环。Chord提供了一个查询操作,把信息的关键字进行hash得到一个键值,然后把它存放到对应键值的节点。因为在chord环中有些节点并不对应于实际的网络节点即虚节点,这时,相关信息就需被存放到对应键值节点的后继节点。在对等网络中节点的后继节点定义为:如果节点是实节点,那么后继节点就是其本身。否则,是其后面第一个真正存在的实节点。每个节点维护它的后继、前趋、和一个有m项的finger表(m是节点ID的长度)在finger表中节点n的第i项指向在ID环中距离节点n至少为2i的节点。在节点k上查找键值key的过程:如果key值介于k和successor(k)之间,那么包含key信息的节点是successor(k),查找结束。否则查找finger表,找出start值最接近于key的前趋,直接发一请求给相应的节点,请求它继续查找,直到这个key的后继被找到。在一个有N个节点的系统中,查询请求能够在O(logN)步内完成。当节点加入到系统,它需要初始化它的finger表,这个开销为O(log2N)。文献提出了利用节点的异构性去构造分层的chord体系以减少结构化对等网络的维护开销;文献则把强能力的节点组织成路由环去帮助节点进行定位操作和消息路由。在此基础上结合PNS原则和Vivaldi坐标,提出一种采用分层DHT技术的拓扑感知chord结构—TA-chord2,并将之应用于流媒体体系中。该体系中节点被分成超级节点和普通节点。所有的节点共同组成下面的底层环,而其中的超级节点再组成一个上层的管理环。所有的查询请求和消息路由都在管理环上进行,而且超级节点要负责普通节点的finger表的维护和更新。普通节点根据自己的能力和意愿决定是否成为超级节点。每个超级节点都指向它的超级前趋和超级后继。超级节点的超级后继、超级前趋指的是这个超级节点在管理环上的直接后继、直接前趋。而且每个超级节点保存一个finger表和一个额外的普通节点表。finger表中有m个表项,索引值从0～m-1,每个表项指向一个超级节点。每个表项有三个域:start域、interval域、snode域,为了减少查询延迟,每层chord中都利用了PNS原则去选择邻近的节点作为finger表项。如节点n的finger表的第i项能够选择start值所在区间[n+2i,n+2i+1)中延迟最小的那个节点,表项中的snode域则是该节点的超级后继。在具体的实现操作中,使用Vivaldi从区间选择节点作为finger表项。Vivaldi是一个网络坐标系统,这个坐标系统能根据节点的位置坐标去预测节点之间的延迟;普通节点表注册了其超级前趋和它之间的普通节点。此外,普通节点除了维护相应的finger表项外还直接指向它的前趋、后继,它的超级前趋和它的超级后继。图1显示的是TA-chord2体系。超级节点8的每一项指向一个超级节点。其普通节点表包含了从节点1到节点8的普通节点2,3,4,6。其中,节点1是超级节点8的超级前趋。(a)分布在环上的是32个节点标志符,超级节点8的fingertable的表项为5;(b)超级节点8的普通节点表中维护的是普通节点2,3,4,6。1.3超级后果的管理在TA-chord2中,查询请求只在管理环上进行,最后一跳到达目的端。普通节点的查询请求首先被递交到它的超级后继,然后开始在管理环上进行查询。一个超级节点的查询直接在超级环上解决。超级节点把键值信息key路由到管理环上键值key的超级后继s。因为s中的普通节点表注册了位于节点s和其超级前趋之间的普通节点,所以s能够在最后一跳直接把请求传到目的地。如图1,假设节点2要查询successor(17),首先这个信息被路由到键值17的超级后继节点20,然后通过节点20就可以找到successor(17)。从图中也可以看出,节点2在普通环上查询需要4跳,而通过管理环,它只需要2跳。TA-chord2还支持另外一个功能:superSuccLookup(key,x),它用来查找键值key的x个超级后继。superSuccLookup(key,x)被用来建立超级节点的finger表。除了最后一跳不是到达普通节点外,节点路由superSuccLookup(key,x)的请求和路由一个查询请求是类似的。1.4基于数据的普通节点更新节点n首先是作为一个普通节点加入到系统。经历一段时间,节点n根据自身的服务能力决定是否变成一个超级节点。下面详细阐述节点的加入、离开、环的维护和变成超级节点的过程。当一个新节点n加入到系统中时,n首先通过管理环找出它的后继。n后继的超级前趋也是n的超级前趋.通过这个超级前趋,n能够找到它的超级后继和它的前趋。然后n把它自己和它的链信息link-info(n)=<n,n.successor,n.predecessor>注册到它的超级后继,link-info的拥有者n是其关键字。节点n也把它的finger表信息插入到管理环。对于每个finger表,fingerinfo的形式如下:finger-info(target)=<y,i,n>,它表示节点n的第i个指数项指向的是y,y是这个finger-info的关键字。它们通过n的超级后继插入到负责这些关键字的超级节点上。当节点x离开了这个普通环,超级节点能够知道哪些节点的finger表指向了x,然后能够指引它们把finger表中的x用x.successor代替。这样超级节点就能通过finger-info去维护普通环,动态更新普通节点的fingertable;利用存储的link-info去维护普通节点之间的关系。假设图1中节点16发现节点17失效,节点16就会通知负责它的超级节点20去更新它的link-info。超级节点20同时也是负责节点17的超级节点,它知道节点18是节点17的后继,这样它就可以把存储在它上面的指向节点17的finger-info更新为指向节点18,而且通知相应的节点去更新它们的finger表。如果新节点没有能力成为超级节点,那么它什么都不做。否则,它将初始化它的finger表。对超级节点n而言,初始化的进程如下:(1)向超级前趋和超级后继请求它们的finger表和它们各自的超级后继和超级前趋。它们构成一个最近的邻居finger表。(2)对于n的每一项,假如在最近的邻居finger表中的一些指数项位于区间[n+2i,n+2i+1),根据PNS原则和vivaldi坐标选出该项的指数项。(3)对于n的每一项i假如在最近的邻居finger表中的所有指数项都不位于区间[n+2i,n+2i+1),n会调用superSuccLookup(key,x)去找节点n超级前趋的第i个指数项开始的x个超级后继,然后n就能得到该项的指数项。在初始化finger表后,n就建立普通节点表。通过n的超级后继,可以构造这个普通节点表。因为n的超级后继注册了位于n的超级前趋和n的超级后继之间的普通节点。在chord中,节点初始化进程后和离开的时候,节点需要通知和它相关的节点关于它到达和离开的信息。在TA-chord2中这个操作被取消。取而代之的是超级节点持续的获取相关信息。通过获取到的超级节点更新它们的finger表。这些超级节点也周期性地检测它们finger表中的节点。假如某个表项失效,这个超级节点会调用superSuccLookup(key,x)去重新设置该项。一个节点的生命周期越长,它越可能继续留在系统,检测的周期就可以设置得更长。为了保证节点的超级后继和后继的正确性,确定机制是必要的。确定机制被分成普通节点的确定和超级节点的确定。普通节点的确定和chord中的确定进程是一样的。普通节点周期性地调用确定机制去保证它的后继是在线的。当发现一个普通节点失效,这个普通节点就会通知它的超级后继有这个变化。超级节点的确定机制和chord中的确定机制进程是类似的,但是确定机制进程的间隔周期更长,超级节点周期性地调用确定机制去保证它的超级后继的正确性。当一个超级节点找到一个新的超级节点或者当它的超级后继离开,它需要相应地改变超级节点表并通知相关的普通节点去改变它们的超级前趋和超级后继。虽然超级节点相对稳定,但是失效的可能性不能被排除。为了增加管理环的容错能力,将备份超级节点的信息到它的超级后继,一旦超级节点失效,它的超级后继将负责它的所有工作。为了减少额外的开销,节点将在确定进程执行的时候捎带需要备份的信息。2节点的dct提取对于需要高效的数据传输的流媒体来说,节点之间的网络位置是非常重要的,因为路由开销是衡量应用层网络组织结构性能的一个很重要机制,而在传统的chord算法中,节点被随机组织,应用层网中相距很近的节点,在实际的物理网络中可能就相距非常远,而同一个子网中的节点经过hash后可能在网络拓扑上相距甚远,这就会浪费很多网络资源并增加链路的压力,而且数据的传输服务质量会显著下降。文献采用vivaldi确定一个节点的网络位置来解决拓扑失配问题。该算法是分布式的,而且,它只需要通过在信息交流中捎带自己的信息去计算节点之间的坐标位置:只要节点之间进行直接的交流,它们就交换vivaldi坐标,因此它能以较低的资源开销达到高性能的目标,适合在P2P系统中使用。该算法收集节点和边界间的ping测量(结果),并返回在一个欧拉空间中的多维坐标。为了搜索附近网络位置的父节点,文献将信息存放的节点地址及其坐标一起返回给查询节点,查询节点根据坐标确定邻近的符合要求的节点。文献将坐标信息放入节点注册分段的DHT关键字中,根据它查找临近的父节点。本文采用文献的思想结合索引列表,在TA-chord2的底层环上进行流媒体的分布式存储、分发、维护。该文献中节点的网络位置使用Vivaldi得到。这个坐标系统把节点的位置信息映射到一个欧拉空间中的多维坐标。为了搜索附近的父节点,节点的位置坐标被放入其注册分段的DHT关键字中。因为多数DHT使用关键字的一维空间,而坐标是多维的,所以,应用空间填充曲线(SFC)把多维坐标空间映射到一维DHT关键字空间。使用这样的映射是因为SFC是保持邻近关系的(即,如果多维空间中的两个点是邻近的,映射后也是邻近的)。DHT搜索关键字由三部分组成:散列的媒体信息、视频分段ID和节点的空间填充曲线映射的网络坐标。文中采用文献的DHT关键字构建思想为每个节点构建32bitDHT关键字,也包括散列的媒体信息、分段ID和SFC映射的坐标。DHT关键字的长度能够扩展以适应更大系统。11bit散列的媒体信息已经能够在系统中容纳大约2048媒体对象。如图2所示,DHT关键字以重要性程度的顺序组合字段(域)。最重要的域是媒体信息,后跟视频分段ID,之后是SFC映射的坐标。为了节点间负载的均衡,对媒体信息进行散列。每个节点所存储的视频分段在DHT中注册其自身的关键字。同时,它使用由分段ID和其自身映射的坐标构成的DHT搜索关键字,搜索其父节点。在一台流媒体服务器存储用户访问的流媒体集合。流媒体对象等分为k个数据段:Segment0,Segment1,Segment2,…Segmentk。假设300s每段。如果视频比特速率是1Mb/s,则每段为36M字节,对于大多数节点的本地存储是可以接受的。一个节点可以随机地在其本地存储中存储视频分段。并在DHT中注册其所存储的视频分段、网络坐标。分段就这样分布于节点间。媒体信息的索引(DHT关键字,片段拥有者IP,流端口)根据散列的媒体信息值存放到相应的节点。这样同一个媒体的所有片段的索引将存放在同一个节点的索引列表中。索引列表中的信息按顺序进行存放,相同的片段在一块。当一个节点请求媒体片段时,它使用由分段ID和其自身映射的坐标构成的DHT搜索关键字,在索引列表中搜索多个关键字在数值上最接近于搜索关键字的父节点。在搜索关键字中使用的是节点自身映射的坐标,因此返回的应答节点和请求节点是临近的。请求节点把它们作为父节点并向其请求流。图3勾勒出一新节点如何在TA-chord2中查找、接收视频流。首先,搜索视频流的第一个分段。接着,基于设计的DHT搜索关键字,在索引列表中离请求的客户最近、可提供服务的节点应答并开始供应流服务。请求节点一旦得到请求流,它就会和存有其索引信息的节点保持直接联系。如果客户快消耗完当前分段,它会直接在索引列表中找到下一片段的索引信息,并根据自身的映射坐标选择最接近于自身的节点为自己提供持续的流化服务。新节点一旦进入系统,就可能开始观看其视频。同时,它利用其剩余带宽也下载一些随机分段。视频分段完全地下载之后,节点将其分段注册到DHT中。由于DHT网络中的用户可能在任意时间离开甚至突然失效,尤其在网络抖动厉害的情况下,索引列表中的相关索引信息会频繁失效。如果想保持列表中所有的指针最新则需要频繁的更新,这对系统来说是一笔非常大的开销,而且在实际应用中也是非常困难的。基于此,采用一种基于反馈和直接通知的机制维护索引列表中的信息,从而减少系统开销。请求的节点负责检查索引列表中信息的有效性。如果无效或故障指针的百分比大于某个阈值t,请求节点将这种情况报告给媒体信息所在的节点,一旦接收到这样的故障报告,该节点将失效的索引信息删除,并更新索引列表。这种被动更新机制的优势有两点:(1)存储索引列表的节点不需要时刻跟踪更新索引信息;(2)一些失效的信息可能再次成为有效的,因为故障可能是临时的。另外,如果节点DHT关键字中的信息发生变化,该节点直接通知媒体信息所在的节点更新索引列表信息。3实验结果和分析论文在公开的open-chord上构建了分层的chord流媒体体系。在仿真中,使用GT-ITM产生transit-stub底层物理网络拓扑结构。它以文件形式输入模拟器。GT-ITM可以生成一个两类的拓扑结构,第1类由若干transit域组成,类似Internet中的骨干网络;第2类由stub域组成,类似于Internet的边缘网络节点,此拓扑能较好地仿真现实世界中的Internet。在它的基础上使用TA-chord2形成逻辑上的网络链路,初始化应用节点的数据结构,在应用节点上初始化视频文件存储的数据结构。将文件通过hash(文件名)得到一个标志符,然后把媒体索引信息放到相应的节点上。这样,节点在加入系统的时候就可提供视频文件共享,同时初始化数据采集接口。在仿真中,媒体流的长度和比特率分别是7200s和1Mb/s。每个分段长度为300s,大小约为36MB。每个节点在其本地存储中存储一个视频分段。根据泊松分布确定节点的插入、视频文件的查询和插入、节点的离开等事件。测量中节点的总数,从1000到6000间变化,每次测量选择其中的20%做为超级节点。实验评估带有各种参数设置的分层流媒体体系的性能,并将之与基于传统chord体系的流化系统作比较。图4示出TA-chord2体系和chord体系就跳数而言的路由时延。从图中看出,两体系路由时延以对数规模随测量尺寸增加而增加。在chord中路由时延为O(logN),而TA-chord2中由于查询在管理环上进行,通过它的路由时延显示为O(logS)(S=N*20%),其中N是系统中节点的数量,S是超级节点的数量,实验结果和从理论上分析的结果一致。虽然实验中测量时延的单位为hop,但是由于超级节点的超能力,通过管理环进行信息路由不仅可以减少hop数,而且每一个hop需要的时间更少,TA-chord2中时延因此会明显地降低。图5比较了两个系统中的跳转(前跳或后跳)时延。如图所示,提出的按索引列表的跳转时延远远低于在chord中的跳转时延。在基于chord的流化系统中,跳转请求和加入请求几乎是相同的。因为节点都