[發明專利]基于de Bruijn圖的大規模網絡資源搜索方法

無效

• 申請號: 201010158376.7
• 申請日: 2010-04-28
• 公開（公告）號: CN101854383A
• 公開（公告）日: 2010-10-06
• 發明（設計）人: 盧錫城;張一鳴;李東升
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: H04L29/08
• 分類號: H04L29/08;H04L12/24;G06F17/30
• 代理公司: 國防科技大學專利服務中心 43202
• 代理人: 郭敏

技術領域

本發明涉及計算機網絡中的資源搜索方法，尤其是一種基于de?Bruijn圖的資源搜索方法。

背景技術

P2P(peer-to-peer)網絡是近年來興起的一種網絡。在P2P網絡中，各節點在邏輯上是對等的，沒有客戶端和服務器之分，各個節點之間可以直接進行通信和交互。目前，P2P網絡在科學研究、電子商務、電子政務和軍事應用等重要領域都有著廣闊的應用。為了實現資源的有效共享和綜合利用，P2P網絡用戶需要對符合要求的資源進行搜索，資源搜索是P2P網絡的關鍵技術之一。

根據資源組織模式，P2P網絡通常可分為兩種：結構化(Structured)P2P網絡和非結構化(Unstructured)P2P網絡。結構化P2P網絡由于具有更加可靠的性能，目前在Internet上得到了大量應用。

結構化P2P網絡中的資源搜索問題可以抽象為：如何在大規模網絡上實現資源對象的高效搜索，并且適應結點的動態變化。

目前，結構化P2P網絡中的資源搜索方法主要包括Chord、CAN、Pastry、Tapestry等。在上述方法中，每個結點都有唯一的標識，并根據一定算法在結點間構建網絡拓撲。每個結點都維護一個“轉發表”，保存相關鄰居結點的信息。每個資源對象根據其關鍵字，通過哈希函數得到資源對象標識。資源對象的標識和結點標識通常屬于相同或相似的名字空間，各結點都負責資源對象標識空間的一部分。當結點加入或退出時，各相關結點需要修改轉發表，并動態調整其負責的標識空間范圍，以維護分布哈希表的一致性。在資源搜索時，每個結點根據其“轉發表”將資源搜索消息轉發到相應的鄰居結點上，直到最終到達目標結點完成搜索。評價大規模網絡資源搜索性能的重要參數包括結點度數和搜索延遲等。結點度數是指各結點上維護的“路由表”的大小；搜索延遲是指一次資源搜索請求在系統中轉發的邏輯跳步數。評價網絡搜索方法的標準主要包括結點度數和搜索延遲，高效的搜索方法一方面應具有較小的節點度數，另一方面應具有較低的搜索延遲。但是，現有搜索方法均沒有實現結點度數和搜索延遲的較好的折中。

發明內容

本發明所要解決的技術問題：針對大規模網絡搜索對結點度數小和搜索延遲低的需求，提出一種基于de?Bruijn圖的大規模網絡資源搜索方法，該方法既能夠具有較小的節點度數(即較小的路由表)，又具有較低的搜索延遲。

為了解決上述問題，本發明提出的技術方案為：

第一步，為資源對象命名：對每個結點和資源對象，采用文獻“RFC?1321：The?MD5Message-Digest?Algorithm”(http://www.ietf.org/rfc/rfc1321.txt，April?1992)所述的MD5(消息摘要5)算法進行命名。

第二步，采用de?Bruijn圖實現網絡拓撲：de?Bruijn圖B(d，D)是一種有向圖，其中d為各結點標識的基(即結點標識中每個字符的取值范圍為0到d-1)、D為各結點標識的長度。每個點u＝u₁u₂...u_D有d條出邊：對任意α∈{0，1，2，L，d-1}，點u有一條到點v＝u₂u₃...u_Dα的出邊。文獻“A?Combinatorial?Problem”(Proc.of?Koninklijke?NederlundseAcademic?van?Watenschappen，vol.A49，pp.758-764，1946)證明，de?Bruijn圖的最大延遲為log_dN，結點度數為2d。

傳統的de?Bruijn圖的結點數為d^D，不能容納任意數目的結點。例如，取d＝2，則結點數只能為2¹＝2、2²＝4、2³＝8、……。因此，我們采用文獻“Factoring?and?Scaling?KautzDigraphs”(Research?Report?94-15，LIP?ENSL，69364?Lyon，France，Apr.1994)提出的一股化的de?Bruijn圖定義：令GB(d，n)代表基為d和結點個數為n的一股化de?Bruijn圖，那么其點集V(GB(d，n))和邊集E(GB(d，n))分別為

V(GB(d，n))＝{0，1，L，n-1}，???(1)

E(GB(d，n))＝{[i，(d×i+α)modn]|0≤α≤d-1}，??(2)