TWI279110B - Network topology generation method and node - Google Patents

Description

1279110 (1) 九、發明說明 【發明所屬之技術領域】 本發明係有關於，在藉由複數節點所構成之網路中 加入新節點之網路拓樸生成方法。又，本發明係有關於 ，在藉由複數節點所構成之網路中新增參加的節點。 【先前技術】 參照圖1至圖5，說明先前之網路拓樸生成方法 馨 (Gnutella所使用的方法）。具體而言，是針對節點1〇5欲 新增至含有節點101〜1〇4之網路中的動作。 第1，如圖1所示，節點1 0 5係從構成網路的複數節 點101〜104之中，和已知IP位址或URL的節點101之 間建立連線。 第2，如圖2所示，節點1 0 5係對節點1 〇 1，發送含 有節點105之IP位址的Ping訊息。 第3，如圖3所示，節點1 0 1係除了將含有節點1 〇 1 # 之IP位址的Pong訊息回應給節點105，同時還將含有節 點1 0 5之IP位址的P i n g訊息，傳送給節點1 〇 2〜1 〇 4。 第4，如圖4所示’各節點1 〇 2〜1 〇 4，係將含有其 各自之IP位址的Pong訊息，回應給節點105。 藉由重複以上的程序，節點105便可取得在Ping訊 息的T T L (T i m e T 〇 L i v e ’存活時間）欄位內所指定之範圍 內的節點之IP位址。 第5，如圖5所示，節點105會參照所收到之P〇ng -4- (2) (2)1279110 訊息內所含之IP位址，而和構成網路的各節點1 〇 1〜1 04 分別建立連線。 如此一來，節點1 0 5就可新增參加至由節點1 0 1〜 104所構成的網路。 如上述，在先前的網路拓樸生成方法當中，新節點 1 0 5係利用P i n g訊息及Ρ ο n g訊息，而可隨機地參加網路 之構成。 可是在此同時，先前的網路拓樸生成方法中，在生 φ 成新的網路拓樸之際，由於並未考慮實體層的網路狀況 ，因此即使在邏輯層上是相鄰的節點，網路延遲可能會 相當地大，導致新生成的網路中資料的傳送效率降低， 是爲其問題點。 (專利文獻1)日本特開2003 -304277號公報 於是，本發明係有鑑於以上問題點，其目的在於提 供一種網路拓樸生成方法及節點，藉由考慮實體層的網 鲁 路狀況，可在新生成網路拓樸之際，將網路延遲抑制成 平均且最小限度。 【發明內容】 本發明之第1特徵，係一種節點，係屬於欲參加至 由複數節點所構成之網路的節點，其特徵爲，具備：虛 擬連線建立部，在前記複數節點間建立虛擬連線；和平 均公制値算出部，算出透過各虛擬連線之到達前記複數 -5- (3) (3)1279110 節點爲止的路徑的平均公制値（metric);連線建立部，藉 由對前記路徑之平均公制値爲最小之已建立虛擬連線之 節點來建立連線，而參加至前記網路。 若藉由所論之發明，則因爲連線件路部，是考慮實 體層之網路狀況而使得所算出之平均公制値爲最小，來 對已建立虛擬連線的節點進行連線建立，因此當新網路 拓樸生成之際，可使網路延遲抑制成平均且最小限度。 本發明之第1特徵中，亦可具備：取得部，從前記 網路內的任意節點，取得該任意節點之相鄰節點所相關 之節點間連接資訊；前記平均公制値算出部，係使用前 記節點間連接資訊來算出前記平均公制値。 本發明之第1特徵中，前記節點間連接資訊，係亦 可含有：用來識別前記相鄰節點之節點ID、前記任意節 點和前記相鄰節點之間路徑的公制値、前記相鄰於前記 相鄰節點之節點數。 本發明之第1特徵中，前記公制値，係亦可構成爲 含有：躍點（hop)數、網路頻寬、通訊成本、延遲、負荷 、MTU、信賴性之至少一者。 本發明之第1特徵中，前記取得部，係亦可對前記 任意之節點，通知前記節點間連接資訊中所應含有之公 制値或公制値之組合種類。 本發明之第2特徵，係一種網路拓樸生成方法，係 拓點 路節 網新 的記 路前 網由 之 ·· 成程 構工 所下 點 以 節有 數具 複， 由爲 至徵 加特 參其 點， 節法 新方 讓成 於生 屬樸 -6- (4) (4)1279110 來和前記複數節點之間建立虛擬連線之工程；和由前記 新節點來算出透過各虛擬連線之到達前記複數節點爲止 的路徑的平均公制値之工程；和前記新節點，藉由對前 記路徑之平均公制値爲最小之已建立虛擬連線之節點進 行連線建立，而參加至前記網路之工程。。 【實施方式】 (實現本發明之第1實施形態所論之網路拓樸生成方法的 構成） 以下將參照圖6A及圖6B，說明實現本發明之實施 形態、所論之網路拓樸生成方法的節點之構成。本實施形 態中，節點X係構成爲能夠新增參加至含有複數節點A 〜D的網路中。 如圖6A所示，本實施形態所論之節點X，係具備： 節點間連接資訊取得部1 1、虛擬連線建立部1 2、平均公 制値算出部1 3、連線建立部1 4、公制値指定部1 5。 節點間連接資訊取得部1 1，係從網路內的任意節點（ 例如節點A)，取得該當任意節點之相鄰節點（例如節點b 〜D)所相關之節點間連接資訊。此外，節點間連接資訊 內，係含有··用來識別節點的「節點名（節點z D)」、相 鄰節點之「節點位址（例如· IP位址）」、任意節點和相鄰 節點之間之路徑的「公制値（metric)」、相鄰於相鄰節點 的「節點數」。又，「公制値」係含有：躍點（h〇p)數、 網路頻寬、通訊成本、延遲、負荷、MTU、信賴性之至 (5) (5)1279110 少一者。 此處’躍點數係代表實體層中的躍點數，亦即代表 和該當節點之間所建立之連結當中的路由器等之躍點數 。網路頻寬係代表和該當節點之間所建立之連結中可使 用的通訊頻寬（例如6 4 k b p s等）。通訊成本係代表和該當 節點間所建立之連結的通訊費。延遲係代表和該當節點 間所建立之連結上的傳播延遲時間。負荷係代表和該當 節點間所建立之連結的使用狀況（例如50% )。MTU係代 表和該當節點間所建立之連結上所使用的最小傳送區塊 大小（Minimum Transfer Unit)。信賴性係代表和該當節點 間所建立之連結上的障礙發生率。 節點間連接資訊取得部1 1亦可構成爲，在從網路內 任意節點取得節點間資訊之際，將公制値指定部1 5所指 定的公制値（或公制値的組合）之種類予以通知。 虛擬連線建立部1 2，係參照節點間連接資訊取得部 1 1所取得之節點間連接資訊內的節點位址，而在複數的 節點A〜D之間建立虛擬連線。 平均公制値算出部1 3，係利用節點間連接資訊取得 部1 1所取得之節點間連接資訊，算出透過了各虛擬連線 的至複數節點爲止之路徑的平均公制値。此外，關於該 當平均公制値的具體算出方法將於後述。 連線建立部1 4，係對路徑之平均公制値爲最小的虛 擬連線已建立節點，進行連線建立。 公制値指定部1 5，係當節點X新增參加入網路之際 -8 - (6) (6)1279110 ’指定要從任意節點取得之節點間連接資訊內所必須含 有之公制値（或公制値之組合）的種類。此外，當未藉由公 制値指定部1 5指定公制値的時候，在任意節點所提供之 15間連接資訊內，則是含有預設設定的公制値（或公制 値之組合）。 如圖6B所示，本實施形態所論之節點a，係具備： 節點間連接資訊取得部3 i、節點間連接資訊記憶部3 2、 虛擬連線建立部3 3、節點間連接資訊提供部3 4、連線建 參 立部3 5。 節點間連接資訊取得部3 1，係於網路內，從相鄰於 該當節點A的相鄰節點（例如節點B〜D)，取得相關於該 當相鄰節點之節點間連接資訊。此外，各節點間的連結 上的公制値會被適宜地更新。 例如，節點間連接資訊取得部3 1，亦可將更新通知 封包，對網路內的所有節點進行廣播，藉此時定期地取 得節點間連接資訊的更新結果。 φ 又，節點間連接資訊取得部3 1亦可構成爲’藉由在 TTL(Time To Live，存活時間）設定範圍內發送更新通知 封包’而定期地取得節點間連接資訊的更新結果。 節點間連接資訊記億部3 2，係將節點間連接資訊取 得部3 1所取得之節點間連接資訊予以記憶。 虛擬連線建立部3 3 ’係響應於來自節點X的虛擬連 線建立要求，而和節點X之間建立虛擬連線。 節點間連接資訊提供部34 ’係從節點間連接資訊記 -9- (7) (7)1279110 憶部3 2取得相鄰於節點A之相鄰節點的節點間連接資訊 ’透過虛擬連線建立部3 3所建立之和節點X間的虛擬連 線’而將該當節點間連接資訊提供給節點χ。 節點間連接資訊提供部34亦可構成爲，當有藉由節 點X而通知公制値（或公制値之組合）之種類的情況下， 提供出含有所論之公制値（或公制値之組合）的節點間連接 資訊。 又’節點間連接資訊提供部3 4亦可構成爲，當未藉 由節點X而通知公制値（或公制値之組合）之種類的情況 下，提供出含有預設設定之公制値（或公制値之組合）的節 點間連接資訊。 連線建立部3 5，係響應於來自節點X的連線建立要 求，而和節點X之間建立虛擬連線。 (本實施形態所論之網路拓樸生成方法的動作） 參照圖7〜圖1 7，說明本實施形態所論之網路拓樸 生成方法的動作。具體而言，是針對節點X要新增參加 入含有節點Α〜D之網路之際的動作來加以說明。 如圖7及圖8所示，步驟S 1中，節點X的節點間連 接資訊取得部1 1，會從節點A取得節點A所管理的節點 間連接資訊。此處，節點X的節點間連接資訊取得部1 1 亦可構成爲，會通知所欲取得之節點間連接資訊內所應 該含有的公制値（或公制値之組合）之種類。 圖9係圖示本實施形態中，節點A所管理之節點間 -10- (8) (8)1279110 連接資訊。 如圖9所示，節點a的相鄰節點，係爲節點b〜〇。 此外’節點B的節點位址爲「BIP」，節點C的節點位址 爲「CIP」，節點D的節點位址爲「DI p」。又，節點A 與節點B之間的公制値爲「2」，節點A與節點c之間 的公制値爲「3」’節點A與節點D之間的公制値爲r 2 」。又’相鄰於節點B的節點數爲「2」，相鄰於節點 C的節點數爲「2」，相鄰於節點D的節點數爲「3」 〇 如圖7及圖1 〇所示，步驟s 2中，節點X的虛擬連 線建立部1 2，會根據已取得之節點間連接資訊內所含之 「節點位址」，而和節點A〜D之間建立虛擬連線。 步驟S 3中，節點X的平均公制値算出部丨3，會根 據已取得之節點間連接資訊內所含之「公制値」及「節 點數」’算出一經由各虛擬連線而從節點X到達各節點 A〜D之路徑的平均公制値。 具體而言，是如以下般地算出平均公制値。此外， 假設節點X和節點D之間所建立之虛擬連線# 1的公制値 爲「1」，節點X和節點A之間所建立之虛擬連線#2的 公制値爲「5」，節點X和節點B之間所建立之虛擬連線 # 3的公制値爲「3」，節點X和節點C之間所建立之虛 擬連線#4的公制値爲「1」。 圖Π係圖示了，將經由經由虛擬連線# 1而從節點X 到達各節點A〜D之路徑# A 1〜#D 1中的「公制値」及相 (9) (9)1279110 鄰於各I卩點A〜D之「節點數」，賦予關連而成的路徑 資訊。 又’圖1 2係圖示了，將經由經由虛擬連線# 2而從節 點X到達各節點A〜D之路徑# A 2〜# D 2中的「公制値」 及相鄰於各節點A〜D之「節點數」，賦予關連而成的 路徑資訊。 又’圖1 3係圖示了，將經由經由虛擬連線#3而從節 點X到達各節點A〜D之路徑# a 3〜# D 3中的「公制値」 及相鄰於各節點A〜D之「節點數」，賦予關連而成的 路徑資訊。 胃II 1 4係圖示了，將經由經由虛擬連線#4而從 節點X到達各節點A〜D之路徑# A4〜#D4中的「公制値 」及相鄰於各節點A〜D之「節點數」，賦予關連而成 的路徑資訊。 節點X的平均公制値算出部1 3，係使用圖1 1〜圖 1 4的路徑資訊’藉由圖1 5所示的計算式，算出經由各虛 擬連線# 1〜#4而從節點X到達節點i之路徑的平均公制 値Vi。圖丨5所示的算式中，^係代表網路所屬總節點數 ’ VMi係代表從節點X到達節點vi之路徑的公制値，Ni 係代表節點i之相鄰節點數加1後的値。此處，節點A 係該當於節點1，節點B係該當於節點2，節點C係該當 於節點3，節點D係該當於節點4。 圖1 6係本實施形態中，由節點X的平均公制値算出 部1 3來參照圖丨丨〜圖1 4所示的路徑資訊，而算出經由 -12- (10) (10)1279110 各虛擬連線# 1〜# 4而從節點X到達各節點A〜D之路徑 的平均公制値的樣子之一例。 如圖1 6所示，節點X經由和節點a之間所建立之 虛擬連線#2而從節點X到達各節點a〜D之路徑的平均 公制値爲「7 8 /1 1」，節點X經由和節點b之間所建立之 虛擬連線# 3而從節點X到達各節點a〜D之路徑的平均 公制値爲「5 9/1 1」，節點X經由和節點c之間所建立之 虛擬連線#4而從節點X到達各節點a〜D之路徑的平均 φ 公制値爲「5 0 /1 1」，節點X經由和節點d之間所建立之 虛擬連線# 1而從節點X到達各節點A〜D之路徑的平均 公制値爲「4 0 /1 1」。 根據該結果，步驟S 4中，如圖1 7所示，節點X的 連線建立部1 4，係對上述之路徑的平均公制値爲最小者（ 「4 0/1 1」）亦即已建立虛擬連線#ι的節點〇，來進行連 線建立，藉此而新增參加入至網路。其結果爲，網路拓 樸被變更了。亦即，節點X係經由虛擬連線# 1，而可以 φ 和含有節點A〜D之網路內的所有節點之間進行通訊。 (本實施形態所論之網路拓樸生成方法的作用、效果） 若根據本實施形態所論之網路拓樸生成方法，則由 於節點X的連線建立部1 4，是會考慮實體層之網路狀況 而使得所算出之平均公制値爲最小，來對已建立虛擬連 線# 1的節點D進行連線建立，因此在新生成網路拓樸之 際’可將網路延遲抑制在平均且最小限度。 -13- (11) (11)1279110 以上，雖然藉由實施例詳述本發明，但對當業者而 言，本發明並非侷限於本說明書中所說明之實施例，此， 乃自明事項。本發明之裝置，係在不脫離申請專利範圍 之記載的本發明之精神及範圍內，可以作各種修正及變 更樣態而實施。因此，本說明書的記載，其目的僅爲例 示說明，並非具有對本發明作任何限制之意思。 【產業上利用之可能性】 Φ 如以上說明，若根據本發明，則可提供一種網路拓 樸生成方法及節點，藉由考慮實體層之網路狀況，在新 生成網路拓樸之際，可將網路延遲抑制在平均且最小限 度。 【圖式簡單說明】 【圖1】先前技術中，由節點i 〇 5來和節點1 〇丨之間 建立連線的動作圖。 Φ 【圖2】先前技術中，由節點1〇5對節點ι〇1發送 Ping訊息的動作圖。 【圖3】先前技術中，由節點ι〇1對節點1〇4發送 Pong訊息，同時，對節點1〇2〜1〇4發送ping訊息的動 作圖。 【圖4】先刖技術中，由節點1〇2〜1〇4來對節點 1 0 1發送Ρ ο n g訊息的動作圖。 【圖5】先則技術中，由節點i 〇丨來和節點1 〇 2〜 -14- (12) (12)1279110 1 〇 4之間建立連線的動作圖。 【圖6A】本發明之一實施形態所論之節點χ的機能 方塊圖。 【圖6B】本發明之一實施形態所論之節點A的機能 方塊圖。 【圖7】本發明之一實施形態所論之節點χ，要新增 參加至網路的動作流程圖。 【圖8】本發明之一實施形態所論之節點χ ,從節點 Α取得節點間連接資訊的動作流程圖。 【圖9】本發明之一實施形態所論之節點χ所取得 之節點間連接資訊之一例的圖示。 【圖1 〇】本發明之一實施形態所論之節點χ，在節 點Α〜D之間建立虛擬連線之動作圖。 【圖1 1】本發明之一實施形態所論之節點χ，透過 已和節點D間建立之虛擬連線的從節點χ至節點a〜D 爲止之路徑資訊的圖示。 【圖1 2】本發明之一實施形態所論之節點X ,透過 已和節點A間建立之虛擬連線的從節點χ至節點A〜〇 爲止之路徑資訊的圖示。 【圖1 3】本發明之一實施形態所論之節點χ，透過 已和節點Β間建立之虛擬連線的從節點χ至節點Α〜D 爲止之路徑資訊的圖示。

【圖1 4】本發明之一實施形態所論之節點χ，透過 已和節點C間建立之虛擬連線的從節點χ至節點A〜D -15- (13) (13)1279110 爲止之路徑資訊的圖示。 【圖1 5】本發明之一實施形態所論之節點X，算出 透過虛擬連線之至節點 A〜D爲止之路徑的平均公制値 的計算式的圖示。 【圖1 6】本發明之一實施形態所論之節點X，算出 透過虛擬連線之至節點A〜D爲止之路徑的平均公制値 的一例的圖示。 【圖1 7】本發明之一實施形態所論之節點X ’和節 點 D間建 連 線 之 動 作 圖 〇 [ 主要元· 件 符 號 說 明 ] 10 1-105 節 點 A ^ ^ D，X 節丨 點 11 節 點 間 連 接 資 訊 取 得 部 12 虛 擬 連 線 建 部 13 平 均 公 制 値 算 出 部 14 連 線 建 部 15 公 制 値 指 定 部 3 1 節 點 間 連 接 資 訊 取 得 部 32 節 點 間 連 接 資 訊 記 億 部 3 3 虛 擬 連 線 建 部 34 節 點 間 連 接 資 訊 提 供 部 3 5 連 線 建 部 -16-

Claims (1)

1. —------- 十、申請專利範圍 第93 1 406Z4號專利申請案 中文申請專利範圍修正本 民國95年12月22日修正 1 · 一種網路節點，係屬於欲參加至由複數網路節點 所構成之網路的網路節點，其特徵爲，具備： 虛擬連線建立部，在前記複數網路節點間建立虛擬 連線；和 平均公制値算出部，算出透過各虛擬連線之到達前 記複數網路節點爲止的路徑的平均公制値（metric); 連線建立部，藉由對前記路徑之平均公制値爲最小 之已建立虛擬連線之網路節點來建立連線，而參加至前 記網路。 2·如申請專利範圍第1項所記載之網路節點，其中 具備：取得部，從前記網路內的任意網路節點，取 得該任意網路節點之相鄰網路節點所相關之網路節點間 連接資訊； 前記平均公制値算出部，係使用前記網路節點間連 接資訊來算出前記平均公制値。 3 .如申請專利範圍第2項所記載之網路節點，其中 前記網路節點間連接資訊，係含有：用來識別前記 修(更)正替換頁 相鄰網路節點之網路節點ID、前記任意網路節點和前記 相鄰網路節點之間路徑的公制値' 前記相鄰於前記相鄰 網路節點之網路節點數。 4·如申請專利範圍第3項所記載之網路節點，其中 前記公制値，係含有：躍點（hop)數、網路頻寬、通 訊成本、延遲、負荷、Μ T U、信賴性之至少一者。 5 ·如申請專利範圍第3項所記載之網路節點，其中 前記取得部，係對前記任意之網路節點，通知前記 網路節點間連接資訊中所應含有之公制値或公制値之組 合種類。 6 · —種網路拓樸生成方法，係屬於讓新網路節點參 加至由複數網路節點所構成之網路的網路拓樸生成方法 ，其特徵爲，具有以下工程： 由前記新網路節點來和前記複數網路節點之間建立 虛擬連線之工程；和 由前記新網路節點來算出透過各虛擬連線之到達前 記複數網路節點爲止的路徑的平均公制値之工程；和 前記新網路節點，藉由對前記路徑之平均公制値爲 最小之已建立虛擬連線之網路節點進行連線建立’而參 加至前記網路之工程。