隨筆 - 7  文章 - 5  trackbacks - 0
          <2006年11月>
          2930311234
          567891011
          12131415161718
          19202122232425
          262728293012
          3456789

          目前在研究生階段,主要是做基于J2EE的web services

          常用鏈接

          留言簿(2)

          隨筆分類

          文章分類

          最新隨筆

          最新評論

          ????? 今天修改了jsf的驗證器部分...看到了對于email的驗證.....看起來還是有點頭大呀.....于是乎翻javadoc....找到了java.util.regex.Pattern類....挺有意思的...一起分享一下......?

          java.util.regex
          類 Pattern

          java.lang.Objectjava.util.regex.Pattern
          所有已實現的接口:
          Serializable

          public final class Pattern
          extends Object
          implements Serializable

          正則表達式的編譯表示形式。

          指定為字符串的正則表達式必須首先被編譯為此類的實例。然后,可將得到的模式用于創建 Matcher 對象,依照正則表達式,該對象可以與任意字符序列匹配。執行匹配所涉及的所有狀態都駐留在匹配器中,所以多個匹配器可以共享同一模式。

          因此,典型的調用順序是

           Pattern p = Pattern.compile("a*b");
           Matcher m = p.matcher("aaaaab");
           boolean b = m.matches();

          在僅使用一次正則表達式時,可以方便地通過此類定義 matches 方法。此方法編譯表達式并在單個調用中將輸入序列與其匹配。語句

           boolean b = Pattern.matches("a*b", "aaaaab");
          等效于上面的三個語句,盡管對于重復的匹配而言它效率不高,因為它不允許重用已編譯的模式。

          此類的實例是不可變的,可供多個并發線程安全使用。Matcher 類的實例用于此目的則不安全。

          正則表達式的構造摘要

          構造匹配
          ?
          字符
          x字符 x
          \\反斜線字符
          \0n帶有八進制值 0 的字符 n (0?<=?n?<=?7)
          \0nn帶有八進制值 0 的字符 nn (0?<=?n?<=?7)
          \0mnn帶有八進制值 0 的字符 mnn(0?<=?m?<=?3、0?<=?n?<=?7)
          \xhh帶有十六進制值?0x 的字符 hh
          \uhhhh帶有十六進制值?0x 的字符 hhhh
          \t制表符 ('\u0009')
          \n新行(換行)符 ('\u000A')
          \r回車符 ('\u000D')
          \f換頁符 ('\u000C')
          \a報警 (bell) 符 ('\u0007')
          \e轉義符 ('\u001B')
          \cx對應于 x 的控制符
          ?
          字符類
          [abc]abc(簡單類)
          [^abc]任何字符,除了 abc(否定)
          [a-zA-Z]azAZ,兩頭的字母包括在內(范圍)
          [a-d[m-p]]admp[a-dm-p](并集)
          [a-z&&[def]]def(交集)
          [a-z&&[^bc]]az,除了 bc[ad-z](減去)
          [a-z&&[^m-p]]az,而非 mp[a-lq-z](減去)
          ?
          預定義字符類
          .任何字符(與行結束符可能匹配也可能不匹配)
          \d數字:[0-9]
          \D非數字: [^0-9]
          \s空白字符:[ \t\n\x0B\f\r]
          \S非空白字符:[^\s]
          \w單詞字符:[a-zA-Z_0-9]
          \W非單詞字符:[^\w]
          ?
          POSIX 字符類(僅 US-ASCII)
          \p{Lower}小寫字母字符:[a-z]
          \p{Upper}大寫字母字符:[A-Z]
          \p{ASCII}所有 ASCII:[\x00-\x7F]
          \p{Alpha}字母字符:[\p{Lower}\p{Upper}]
          \p{Digit}十進制數字:[0-9]
          \p{Alnum}字母數字字符:[\p{Alpha}\p{Digit}]
          \p{Punct}標點符號:!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~
          \p{Graph}可見字符:[\p{Alnum}\p{Punct}]
          \p{Print}可打印字符:[\p{Graph}\x20]
          \p{Blank}空格或制表符:[ \t]
          \p{Cntrl}控制字符:[\x00-\x1F\x7F]
          \p{XDigit}十六進制數字:[0-9a-fA-F]
          \p{Space}空白字符:[ \t\n\x0B\f\r]
          ?
          java.lang.Character 類(簡單的 java 字符類型
          \p{javaLowerCase}等效于 java.lang.Character.isLowerCase()
          \p{javaUpperCase}等效于 java.lang.Character.isUpperCase()
          \p{javaWhitespace}等效于 java.lang.Character.isWhitespace()
          \p{javaMirrored}等效于 java.lang.Character.isMirrored()
          ?
          Unicode 塊和類別的類
          \p{InGreek}Greek?塊(簡單)中的字符
          \p{Lu}大寫字母(簡單類別
          \p{Sc}貨幣符號
          \P{InGreek}所有字符,Greek 塊中的除外(否定)
          [\p{L}&&[^\p{Lu}]]?所有字母,大寫字母除外(減去)
          ?
          邊界匹配器
          ^行的開頭
          $行的結尾
          \b單詞邊界
          \B非單詞邊界
          \A輸入的開頭
          \G上一個匹配的結尾
          \Z輸入的結尾,僅用于最后的結束符(如果有的話)
          \z輸入的結尾
          ?
          Greedy 數量詞
          X?X,一次或一次也沒有
          X*X,零次或多次
          X+X,一次或多次
          X{n}X,恰好 n
          X{n,}X,至少 n
          X{n,m}X,至少 n 次,但是不超過 m
          ?
          Reluctant 數量詞
          X??X,一次或一次也沒有
          X*?X,零次或多次
          X+?X,一次或多次
          X{n}?X,恰好 n
          X{n,}?X,至少 n
          X{n,m}?X,至少 n 次,但是不超過 m
          ?
          Possessive 數量詞
          X?+X,一次或一次也沒有
          X*+X,零次或多次
          X++X,一次或多次
          X{n}+X,恰好 n
          X{n,}+X,至少 n
          X{n,m}+X,至少 n 次,但是不超過 m
          ?
          Logical 運算符
          XYX 后跟 Y
          X|YXY
          (X)X,作為捕獲組
          ?
          Back 引用
          \n任何匹配的 nth捕獲組
          ?
          引用
          \Nothing,但是引用以下字符
          \QNothing,但是引用所有字符,直到 \E
          \ENothing,但是結束從 \Q 開始的引用
          ?
          特殊構造(非捕獲)
          (?:X)X,作為非捕獲組
          (?idmsux-idmsux)?Nothing,但是將匹配標志由 on 轉為 off
          (?idmsux-idmsux:X)??X,作為帶有給定標志 on - off 的非捕獲組
          (?=X)X,通過零寬度的正 lookahead
          (?!X)X,通過零寬度的負 lookahead
          (?<=X)X,通過零寬度的正 lookbehind
          (?<!X)X,通過零寬度的負 lookbehind
          (?>X)X,作為獨立的非捕獲組

          反斜線、轉義和引用

          反斜線字符 ('\') 用于引用轉義構造,如上表所定義的,同時還用于引用其他將被解釋為非轉義構造的字符。因此,表達式 \\ 與單個反斜線匹配,而 \{ 與左括號匹配。

          在不表示轉義構造的任何字母字符前使用反斜線都是錯誤的;它們是為將來擴展正則表達式語言保留的。可以在非字母字符前使用反斜線,不管該字符是否非轉義構造的一部分。

          根據 Java Language Specification 的要求,Java 源代碼的字符串中的反斜線被解釋為 Unicode 轉義或其他字符轉義。因此必須在字符串字面值中使用兩個反斜線,表示正則表達式受到保護,不被 Java 字節碼編譯器解釋。例如,當解釋為正則表達式時,字符串字面值 "\b" 與單個退格字符匹配,而 "\\b" 與單詞邊界匹配。字符串字面值 "\(hello\)" 是非法的,將導致編譯時錯誤;要與字符串 (hello) 匹配,必須使用字符串字面值 "\\(hello\\)"

          字符類

          字符類可以出現在其他字符類中,并且可以包含并集運算符(隱式)和交集運算符 (&&)。并集運算符表示至少包含其某個操作數類中所有字符的類。交集運算符表示包含同時位于其兩個操作數類中所有字符的類。

          字符類運算符的優先級如下所示,按從最高到最低的順序排列:

          1????字面值轉義????\x
          2????分組[...]
          3????范圍a-z
          4????并集[a-e][i-u]
          5????交集[a-z&&[aeiou]]

          注意,元字符的不同集合實際上位于字符類的內部,而非字符類的外部。例如,正則表達式 . 在字符類內部就失去了其特殊意義,而表達式 - 變成了形成元字符的范圍。

          行結束符

          行結束符 是一個或兩個字符的序列,標記輸入字符序列的行結尾。以下代碼被識別為行結束符:

          如果激活 UNIX_LINES 模式,則新行符是惟一識別的行結束符。

          如果未指定 DOTALL 標志,則正則表達式 . 可以與任何字符(行結束符除外)匹配。

          默認情況下,正則表達式 ^$ 忽略行結束符,僅分別與整個輸入序列的開頭和結尾匹配。如果激活 MULTILINE 模式,則 ^ 在輸入的開頭和行結束符之后(輸入的結尾)才發生匹配。處于 MULTILINE 模式中時,$ 僅在行結束符之前或輸入序列的結尾處匹配。

          組和捕獲

          捕獲組可以通過從左到右計算其開括號來編號。例如,在表達式 ((A)(B(C))) 中,存在四個這樣的組:

          1????((A)(B(C)))
          2????\A
          3????(B(C))
          4????(C)

          組零始終代表整個表達式。

          之所以這樣命名捕獲組是因為在匹配中,保存了與這些組匹配的輸入序列的每個子序列。捕獲的子序列稍后可以通過 Back 引用在表達式中使用,也可以在匹配操作完成后從匹配器檢索。

          與組關聯的捕獲輸入始終是與組最近匹配的子序列。如果由于量化的緣故再次計算了組,則在第二次計算失敗時將保留其以前捕獲的值(如果有的話)例如,將字符串 "aba" 與表達式 (a(b)?)+ 相匹配,會將第二組設置為 "b"。在每個匹配的開頭,所有捕獲的輸入都會被丟棄。

          (?) 開頭的組是純的非捕獲 組,它不捕獲文本,也不針對組合計進行計數。

          Unicode 支持

          此類符合 Unicode Technical Standard #18:Unicode Regular Expression Guidelines 第 1 級和 RL2.1 Canonical Equivalents。

          Java 源代碼中的 Unicode 轉義序列(如 \u2014)是按照 Java Language Specification 的 第 3.3 節中的描述處理的。這樣的轉義序列還可以由正則表達式分析器直接實現,以便在從文件或鍵盤擊鍵讀取的表達式中使用 Unicode 轉義。因此,可以將不相等的字符串 "\u2014""\\u2014" 編譯為相同的模式,從而與帶有十六進制值 0x2014 的字符匹配。

          與 Perl 中一樣,Unicode 塊和類別是使用 \p\P 構造編寫的。如果輸入具有屬性 prop,則與 \p{prop} 匹配,而輸入具有該屬性時與 \P{prop} 不匹配。塊使用前綴 In 指定,與在 InMongolian 中一樣。可以使用可選前綴 Is 指定類別:\p{L}\p{IsL} 都表示 Unicode 字母的類別。塊和類別在字符類的內部和外部都可以使用。

          受支持的類別是由 Character 類指定版本中的 The Unicode Standard 的類別。類別名稱是在 Standard 中定義的,即標準又豐富。Pattern 所支持的塊名稱是 UnicodeBlock.forName 所接受和定義的有效塊名稱。

          行為類似 java.lang.Character boolean 是 methodname 方法(廢棄的類別除外)的類別,可以通過相同的 \p{prop} 語法來提供,其中指定的屬性具有名稱 javamethodname

          與 Perl 5 相比較

          Pattern 引擎用有序替換項執行傳統上基于 NFA 的匹配,與 Perl 5 中進行的相同。

          此類不支持 Perl 構造:

          此類支持但 Perl 不支持的構造:

          與 Perl 的顯著不同點是:

          • 在 Perl 中,\1\9 始終被解釋為 Back 引用;如果至少存在多個子表達式,則大于 9 的反斜線轉義數按 Back 引用對待,否則在可能的情況下,它將被解釋為八進制轉義。在此類中,八進制轉義必須始終以零開頭。在此類中,\1\9 始終被解釋為 Back 引用,較大的數被接受為 Back 引用,如果在正則表達式中至少存在多個子表達式的話;否則,分析器將刪除數字,直到該數小于或等于組的現有數或者其為一個數字。

          • Perl 使用 g 標志請求恢復最后匹配丟失的匹配。此功能是由 Matcher 類顯式提供的:重復執行 find 方法調用可以恢復丟失的最后匹配,除非匹配器被重置。

          • 在 Perl 中,位于表達式頂級的嵌入式標記對整個表達式都有影響。在此類中,嵌入式標志始終在它們出現的時候才起作用,不管它們位于頂級還是組中;在后一種情況下,與在 Perl 中類似,標志在組的結尾處還原。

          • Perl 允許錯誤匹配構造,如在表達式 *a 中,以及不匹配的括號,如在在表達式 abc] 中,并將其作為字面值對待。此類還接受不匹配的括號,但對 +、? 和 * 不匹配元字符有嚴格限制;如果遇到它們,則拋出 PatternSyntaxException

          有關正則表達式構造行為更準確的描述,請參見《Mastering Regular Expressions, 2nd Edition》,該書由 Jeffrey E. F. Friedl、O'Reilly 和 Associates 合著,于 2002 年出版。

          從以下版本開始:
          1.4
          另請參見:
          String.split(String, int), String.split(String), 序列化表格

          字段摘要
          static?intCANON_EQ
          ??????????啟用規范等價。
          static?intCASE_INSENSITIVE
          ??????????啟用不區分大小寫的匹配。
          static?intCOMMENTS
          ??????????模式中允許空白和注釋。
          static?intDOTALL
          ??????????啟用 dotall 模式。
          static?intLITERAL
          ??????????啟用模式的字面值分析。
          static?intMULTILINE
          ??????????啟用多行模式。
          static?intUNICODE_CASE
          ??????????啟用 Unicode 感知的大小寫折疊。
          static?intUNIX_LINES
          ??????????啟用 Unix 行模式。
          ?
          方法摘要
          static?Patterncompile(String?regex)
          ??????????將給定的正則表達式編譯到模式中。
          static?Patterncompile(String?regex, int?flags)
          ??????????將給定的正則表達式編譯到具有給定標志的模式中。
          ?intflags()
          ??????????返回此模式的匹配標志。
          ?Matchermatcher(CharSequence?input)
          ??????????創建匹配給定輸入與此模式的匹配器。
          static?booleanmatches(String?regex, CharSequence?input)
          ??????????編譯給定正則表達式并嘗試將給定輸入與其匹配。
          ?Stringpattern()
          ??????????返回在其中編譯過此模式的正則表達式。
          static?Stringquote(String?s)
          ??????????返回指定 String 的字面值模式 String
          ?String[]split(CharSequence?input)
          ??????????圍繞此模式的匹配拆分給定輸入序列。
          ?String[]split(CharSequence?input, int?limit)
          ??????????圍繞此模式的匹配拆分給定輸入序列。
          ?StringtoString()
          ??????????返回此模式的字符串表示形式。
          ?
          從類 java.lang.Object 繼承的方法
          clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait


          這樣下來檢驗email的代碼也是相當簡單呀....
          ???? boolean b = Pattern.matches("^\\w+@\\w+(\\.\\w+)+", email);

          posted @ 2006-11-18 22:38 Stefanie 閱讀(5926) | 評論 (1)編輯 收藏

          P2P網絡的拓撲結構

          拓撲結構是指分布式系統中各個計算單元之間的物理或邏輯的互聯關系,結點之間的拓撲結構一直是確定系統類型的重要依據。目前互聯網絡中廣泛使用集中式、層次式等拓撲結構。Internet本身是世界上最大的非集中式的互聯網絡,但是九十年代所建立的一些網絡應用系統卻是完全的集中式的系統,許多Web應用都是運行在集中式的服務器系統上。集中式拓撲結構系統目前面臨著過量存儲負載、DOS(Denial of Service,拒絕服務)攻擊,網絡帶寬限制等一些難以解決的問題。Peer-to-Peer (簡稱P2P) 系統主要采用非集中式的拓撲結構,一般來說不存在上述這些難題。根據結構關系可以將P2P系統細分為四種拓撲形式:

          • 中心化拓撲(Centralized Topology);
          • 全分布式非結構化拓撲(Decentralized Unstructured Topology);
          • 全分布式結構化拓撲(Decentralized Structured Topology,也稱作DHT網絡);
          • 半分布式拓撲(Partially Decentralized Topology)。

          其中,中心化拓撲最大的優點是維護簡單,資源發現效率高。由于資源的發現依賴中心化的目錄系統,發現算法靈活高效并能夠實現復雜查詢。最大的問題與傳統客戶機/服務器結構類似,容易造成單點故障,訪問的“熱點”現象和版權糾紛等相關問題,這是第一代P2P網絡采用的結構模式,經典案例就是著名的MP3共享軟件Napster[1].

          Napster是最早出現的P2P系統之一,并在短期內迅速成長起來。它實質上并非是純粹的P2P系統,而是通過一個中央索引服務器保存所有Napster用戶上傳的音樂文件索引和存放位置的信息。它的工作原理如圖1所示。當某個用戶需要某個音樂文件時,首先連接到Napster中央索引服務器,在服務器上進行檢索,服務器返回存有該文件的用戶信息,再由請求者直接連到文件的所有者傳輸文件。Napster首先實現了文件查詢與文件傳輸的分離,有效地節省了中央服務器的帶寬消耗,減少了系統的文件傳輸延時。

          圖1 Napster的拓撲結構

          然而,這種對等網絡模型存在以下這些問題:

          • 中央索引服務器的癱瘓容易導致整個網絡的崩潰,因此可靠性和安全性較低。
          • 隨著網絡規模的擴大,對中央索引服務器進行維護和更新的費用將急劇增加,所需成本較高。
          • 中央索引服務器的存在常引起版權問題上的糾紛,服務提供商容易被追究法律責任。

          綜合上述優缺點,對小型網絡而言,中心化拓撲模型在管理和控制方面占一定優勢。但鑒于其存在的上述缺陷,該模型并不適合大型網絡應用。

          全分布式非結構化拓撲的P2P網絡是在重疊網絡(Overlay Network)(見標注1)采用了隨機圖的組織方式,結點度數服從Power-law規律(冪次法則)[2],從而能夠較快發現目的結點,面對網絡的動態變化體現了較好的容錯能力,因此具有較好的可用性。同時可以支持復雜查詢,如帶有規則表達式的多關鍵詞查詢,模糊查詢等,采用這種拓撲結構最典型的案例便是Gnutella(音譯:紐特拉)。準確地說,Gnutella不是特指某一款軟件,而是指遵守Gnutella協議[3]的網絡以及客戶端軟件的統稱。目前基于Gnutella網絡的客戶端軟件非常多,著名的有ShareazaLimeWire和BearShare等。

          圖2Gnutella的拓撲結構和文件檢索方法

          Gnutella和Napster最大的區別在于Gnutella是更加純粹的P2P系統,因為它沒有中央索引服務器,每臺機器在Gnutella網絡中是真正的對等關系,既是客戶機同時又是服務器,所以被稱為對等機(Servent,Server+Client的組合)。在文件檢索方面,它與Napster也不相同。在Gnutella網絡的發展初期,它主要采用基于完全隨機圖的Flooding搜索算法。圖2 顯示了Flooding的工作流程:當一臺計算機要下載一個文件,它首先以文件名或者關鍵字生成一個查詢,并把這個查詢發送給與它相連的所有計算機,這些計算機如果存在這個文件,則與查詢的機器建立連接,如果不存在這個文件,則繼續在自己相鄰的計算機之間轉發這個查詢,直到找到文件為止。為了控制搜索消息不至于永遠這樣傳遞下去,一般通過TTL (Time To Live)的減值來控制查詢的深度。

          但是,隨著聯網節點的不斷增多,網絡規模不斷擴大,通過這種Flooding方式定位對等點的方法將造成網絡流量急劇增加,從而導致網絡中部分低帶寬節點因網絡資源過載而失效。所以在初期的Gnutella網絡中,存在比較嚴重的分區,斷鏈現象。也就是說,一個查詢訪問只能在網絡的很小一部分進行,因此網絡的可擴展性不好。所以,后來許多研究人員在Flooding的基礎上作了許多改進,例如采用Random work [4]、Dynamic Query[5]等方法。

          由于非結構化網絡將重疊網絡認為是一個完全隨機圖,結點之間的鏈路沒有遵循某些預先定義的拓撲來構建。這些系統一般不提供性能保證,但容錯性好,支持復雜的查詢,并受結點頻繁加入和退出系統的影響小。但是查詢的結果可能不完全,查詢速度較慢,采用Flooding查詢的系統對網絡帶寬的消耗非常大,并由此帶來可擴展性差等問題。

          全分布式結構化拓撲的P2P網絡主要是采用分布式散列表(Distributed Hash Table, 簡寫成DHT)技術來組織網絡中的結點。DHT是一個由廣域范圍大量結點共同維護的巨大散列表。散列表被分割成不連續的塊,每個結點被分配給一個屬于自己的散列塊,并成為這個散列塊的管理者。通過加密散列函數,一個對象的名字或關鍵詞被映射為128位或160位的散列值。分布式散列表起源于SDDS(Scalable Distribute Data Structures)[6]研究,Gribble等實現了一個高度可擴展,容錯的SDDS集群。DHT類結構能夠自適應結點的動態加入/退出,有著良好的可擴展性、魯棒性、結點ID分配的均勻性和自組織能力。由于重疊網絡采用了確定性拓撲結構,DHT可以提供精確的發現。只要目的結點存在于網絡中DHT總能發現它,發現的準確性得到了保證,最經典的案例是Tapestry,Pastry,Chord和CAN。

          Tapestry [7]提供了一個分布式容錯查找和路由基礎平臺,在此平臺基礎之上,可以開發各種P2P應用(OceanStore[8]即是此平臺上的一個應用)。Tapestry的思想來源于Plaxton。在Plaxton中,結點使用自己所知道的鄰近結點表,按照目的ID來逐步傳遞消息。Tapestry基于Plaxton的思想,加入了容錯機制,從而可適應P2P的動態變化的特點。OceanStore是以Tapestry為路由和查找基礎設施的P2P平臺。它是一個適合于全球數據存儲的P2P應用系統。任何用戶均可以加入OceanStore系統,或者共享自己的存儲空間,或者使用該系統中的資源。通過使用復制和緩存技術,OceanStore可提高查找的效率。最近,Tapestry為適應P2P網絡的動態特性,作了很多改進,增加了額外的機制實現了網絡的軟狀態(soft state),并提供了自組織、魯棒性、可擴展性和動態適應性,當網絡高負載且有失效結點時候性能有限降低,消除了對全局信息的依賴、根結點易失效和彈性差的問題。

          Pastry 是微軟研究院提出的可擴展的分布式對象定位和路由協議,可用于構建大規模的P2P系統。如圖3 所示,在Pastry中,每個結點分配一個128位的結點標識符號(nodeID) ,所有的結點標識符形成了一個環形的nodeID空間,范圍從0到2128 - 1 ,結點加入系統時通過散列結點IP地址在128位nodeID空間中隨機分配。網絡結點的加入與退出,資源查詢的過程可以參考文獻[9]。

          圖3Pastry的消息路由

          Chord [10]項目誕生于美國的麻省理工學院。它的目標是提供一個適合于P2P環境的分布式資源發現服務,它通過使用DHT技術使得發現指定對象只需要維護O(logN)長度的路由表。在DHT技術中,網絡結點按照一定的方式分配一個唯一結點標識符(Node ID) ,資源對象通過散列運算產生一個唯一的資源標識符(Object ID) ,且該資源將存儲在結點ID與之相等或者相近的結點上。需要查找該資源時,采用同樣的方法可定位到存儲該資源的結點。因此,Chord的主要貢獻是提出了一個分布式查找協議,該協議可將指定的關鍵字(Key) 映射到對應的結點(Node) 。從算法來看,Chord是相容散列算法的變體。

          圖4 Chord的拓撲形狀

          CAN(Content Addressable Networks)[11] 項目采用多維的標識符空間來實現分布式散列算法。CAN將所有結點映射到一個n維的笛卡爾空間中,并為每個結點盡可能均勻的分配一塊區域。CAN采用的散列函數通過對(key, value) 對中的key進行散列運算,得到笛卡爾空間中的一個點,并將(key, value) 對存儲在擁有該點所在區域的結點內。CAN采用的路由算法相當直接和簡單,知道目標點的坐標后,就將請求傳給當前結點四鄰中坐標最接近目標點的結點。CAN是一個具有良好可擴展性的系統,給定N個結點,系統維數為d,則路由路徑長度為O(n1/d) ,每結點維護的路由表信息和網絡規模無關為O(d) 。

          上述四種基于DHT的P2P系統的性能比較可以參照[12]。DHT這類結構最大的問題是DHT的維護機制較為復雜,尤其是結點頻繁加入退出造成的網絡波動(Churn)會極大增加DHT的維護代價。DHT所面臨的另外一個問題是DHT僅支持精確關鍵詞匹配查詢,無法支持內容/語義等復雜查詢。

          半分布式拓撲結構(有的文獻亦稱作混雜模式,英文表達為Hybrid Structure)吸取了中心化結構和全分布式非結構化拓撲的優點,選擇性能較高(處理、存儲、帶寬等方面性能)的結點作為超級結點(英文表達為SuperNodes或者Hubs),在各個超級結點上存儲了系統中其他部分結點的信息,發現算法僅在超級結點之間轉發,超級結點再將查詢請求轉發給適當的葉子結點。半分布式結構也是一個層次式結構,超級結點之間構成一個高速轉發層,超級結點和所負責的普通結點構成若干層次。采用這種結構的最典型的案例就是KaZaa

          圖5 半分布式拓撲結構(網絡中包含Super Node)

          KaZaa是當前世界最流行的幾款P2P文件共享軟件之一。根據CA公司統計,全球KaZaa的下載量超過2.5億次。使用KaZaa軟件進行文件傳輸消耗了互聯網40%的帶寬。之所以它如此的成功,是因為它結合了Napster和Gnutella共同的優點。從結構上來說,它使用了Gnutella的全分布式的結構,這樣可以是系統更好的擴展,因為它無需中央索引服務器存儲文件名,它是自動的把性能好的機器成為SuperNode,它存儲著離它最近的葉子節點的文件信息,這些SuperNode,再連通起來形成一個Overlay Network. 由于SuperNode的索引功能,使搜索效率大大提高。

          圖6 KaZaa的軟件界面

          半分布式結構的優點是性能、可擴展性較好,較容易管理,但對超級點依賴性大,易于受到攻擊,容錯性也受到影響。

          在實際應用中,每種拓撲結構的P2P網絡都有其優缺點,下表從可擴展性、可靠性、可維護性、發現算法的效率、復雜查詢等方面比較了這四種拓撲結構的綜合性能。

          比較標準/拓撲結構

          中心化拓撲

          全分布式非結構化拓撲

          全分布式結構化拓撲

          半分布式拓撲

          可擴展性

          可靠性

          可維護性

          最好

          最好

          發現算法效率

          最高

          復雜查詢

          支持

          支持

          不支持

          支持



          我還是比較看好chord...雖然目前還有不少問題沒有解決....
          順便附上一篇經典的chord論文: Chord: A Scalable Peertopeer Lookup Service for Internet Applications
          http://www.aygfsteel.com/Files/heiyuchuanxia/chord_sigcomm.rar
          posted @ 2006-11-15 15:28 Stefanie 閱讀(3469) | 評論 (0)編輯 收藏
               摘要: The Summery of OWL-S 1.2 OWL-S is an ontology, within the OWL-based framework of the Semantic Web, for describing Web services. This documen...  閱讀全文
          posted @ 2006-11-12 14:00 Stefanie 閱讀(687) | 評論 (1)編輯 收藏
          主站蜘蛛池模板: 沈阳市| 阳信县| 松滋市| 东宁县| 丹巴县| 招远市| 凉城县| 万山特区| 金寨县| 中西区| 南京市| 松潘县| 科尔| 葵青区| 大宁县| 二连浩特市| 平罗县| 饶河县| 博兴县| 博爱县| 绥江县| 涿鹿县| 镇原县| 安阳市| 宝丰县| 余姚市| 克什克腾旗| 山东| 大姚县| 泰宁县| 韩城市| 上高县| 宣化县| 翁源县| 镇原县| 乡宁县| 双辽市| 汝州市| 射洪县| 彭山县| 基隆市|