(57)【要約】【課題】属性ベースなどの柔軟な名前空間に対しても或いは規模の拡大に対しても、良好に動作する名前解決機構を提供する。【解決手段】本発明による名前解決システムは、ネットワーク上に配置した複数の名前解決装置を具えると共に、これらの名前解決装置が担当する複数の部分空間（２ａ〜２ｃ）により構成される名前空間（１）を有する。各名前解決装置は、自己が担当する部分空間であって、軸上の距離情報として規定される複数のレベルにより規定される部分空間を具えると共に、自己が担当する部分空間内に属するリソースの名前とそのアドレスとの対応関係を規定した情報と、各レベルについて自己が担当する範囲を規定したデータと、ユーザから提示された名前について、各レベルの軸上の距離を各レベル毎に算出する手段と、算出された各レベルの距離が自担当の部分空間内に存在するか否かを判定する手段と、判定の結果として自担当の部分空間内に存在しない場合算出された距離に位置する部分空間を担当する名前解決装置に当該名前解決の問い合わせを転送する手段とを有する。【選択図】        図２
2005004587.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク上に分散管理されているリソースについて、ユーザからのアクセスに応じて目的とするリソースのアドレスをユーザに提供する名前解決システムにおいて、
当該名前解決システムは、ネットワーク上に配置した複数の名前解決装置を具えると共に、これらの名前解決装置が担当する複数の部分空間により構成される名前空間を有し、
各名前解決装置は、自己が担当する部分空間であって、軸上の距離情報として規定される複数のレベルにより規定される部分空間を具えると共に、自己が担当する部分空間内に属するリソースの名前とそのアドレスとの対応関係を規定した情報と、各レベルについて自己が担当する範囲を規定したデータと、ユーザから提示された名前について、各レベルの軸上の距離を各レベル毎に算出する手段と、算出された各レベルの距離が自担当の部分空間内に存在するか否かを判定する手段と、判定の結果として自担当の部分空間内に存在しない場合算出された距離に位置する部分空間を担当する名前解決装置に当該名前解決の問い合わせを転送する手段とをそれぞれ有し、
各名前解決装置は、ユーザから提示されたリソースの名前に基づいて名前解決処理を実行するに当たり、
ユーザから提示されたリソースの名前について、各レベルについて距離を算出する工程及び算出された距離が自己が担当する部分空間内に存在するか否かを判定する工程とを１つ又は複数のレベルについて繰り返し実行し、
自担当の名前空間の範囲内に存在する名前を見出した際、当該名前に対応するアドレスをユーザに提供することを特徴とする名前解決システム。
【請求項２】
請求項１に記載の名前解決システムにおいて、各名前解決装置は、ユーザから提示された名前について算出された距離が自担当の部分空間内に存在しない場合、算出された距離に位置する部分空間を担当する名前解決装置に当該問い合わせを転送し、転送を受けた名前解決装置において、各レベルについて距離を算出する工程及び算出された距離が自己が担当する部分空間内に存在するか否かを判定する工程を実行し、自担当の名前空間の範囲内に存在する名前を見出した際、当該名前に対応するアドレスをユーザに提供することを特徴とする名前解決システム。
【請求項３】
請求項１又は２に記載の名前解決システムにおいて、前記名前の記述は、ツリー構造を有し、ツリー構造のリーフに対応する要素とその値との対により特定されることを特徴とする名前解決システム。
【請求項４】
請求項３に記載の名前解決システムにおいて、前記レベルとして、名前のリーフ数、名前の構造及び名前の要素を含むことを特徴とする名前解決システム。
【請求項５】
請求項１から４までのいずれか１項に記載の名前解決システムにおいて、前記名前の記述は、ＸＭＬの様式に従うことを特徴とする名前解決システム。
【請求項６】
ネットワーク上に分散蓄積されているリソースについて、ユーザからのアクセスに応じて、目的とするリソースのアドレスをユーザに提供する名前解決システムに用いられる名前解決装置において、
当該名前解決装置は、自己が担当する部分空間であって、軸上の距離情報として規定される複数のレベルにより規定される部分空間を具えると共に、自己が担当する部分空間内に属するリソースの名前とそのアドレスとの対応関係を規定した情報と、各レベルについて自己が担当する範囲を規定したデータと、ユーザから提示された名前について、各レベルの軸上の距離を各レベル毎に算出する手段と、算出された各レベルの距離が自担当の部分空間内に存在するか否かを判定する手段と、判定の結果として自担当の部分空間内に存在しない場合算出された距離に位置する部分空間を担当する名前解決装置に当該名前解決の問い合わせを転送する手段とを有し、
ユーザから提示されたリソースの名前に基づいて名前解決処理を実行するに当たり、
ユーザから提示されたリソースの名前について、各レベルについて距離を算出する工程及び算出された距離が自己が担当する部分空間内に存在するか否かを判定する工程とを１つ又は複数のレベルについて繰り返し実行し、
自担当の名前空間の範囲内に存在する名前を見出した際、当該名前に対応するアドレスをユーザに提供することを特徴とする名前解決装置。
【発明の詳細な説明】
【０００１】
本発明は、ネットワーク上に分散蓄積されている複数のリソースについて、ユーザからのアクセスに応じて目的とするリソースのアドレスをユーザに提供する名前解決システム及び当該名前解決システムに用いられる名前解決装置（リゾルバ）に関するものである。
【０００２】
【従来の技術】
ファイルなどのリソースをネットワーク上で分散蓄積するシステムにおいて、ファイル名などの「名前」を与えて、「名前」に対して、対応するファイルなどのリソースのある場所のアドレスを回答する名前解決技術は、今後の情報流通ネットワークで、非常に重要な位置を占めると考えられる。名前解決技術のうち、現在、最もよく知られているのは、インターネットのＤＮＳ（Ｄｏｍａｉｎ  Ｎａｍｅ  Ｓｙｓｔｅｍ）である。このシステム、メールアドレスなどの「名前」を与えると、対応するＩＰアドレスを回答するものである。ＤＮＳは、メールアドレスに使用されるドメイン名が階層化されていることを利用し、ＤＮＳも階層構成をとっている。このため、規模が増大しても、比較的効率的に、名前解決できるが、あらかじめ定められた階層構成でない場合、適用に問題が生ずる。
【０００３】
一般的な名前解決を分散管理の下で行うことで、大規模化しても効率的に動作させる機構として、ＣＡＮと称されている研究結果（例えば、非特許文献１参照）及びＣｈｏｒｄと称せられている研究結果（例えば、非特許文献２参照）が発表された。
【０００４】
これらの機構は、ファイル名などの名前をハッシュ関数によりハッシュキーに変換することで名前空間の分割および名前解決の分散処理を効率的に行う技術である。
図１に示すように、リゾルバは、ハッシュキーとリソースのアドレスとの対応を管理する。名前解決で対応表を参照する際も、名前をハッシュキーに変換し、これを探索キーとしてアドレスを見出す。
【０００５】
ハッシュキーはｎ次元のユークリッド空間にマッピングされる。このハッシュキーの空間は、複数あるリゾルバによりゾーンと呼ばれる部分に分割される。どのリゾルバがどのゾーンを担当するかは任意であるが、全リゾルバのゾーンの集合がハッシュキーの空間の全体を網羅するように決められる。各リゾルバは、リソースの名前をハッシュキーに変換する全リゾルバ共通のハッシュ関数および自身が担当するゾーン内にハッシュキーがマッピングされたリソースの名前とアドレスとの対応表、及び隣接するゾーンを担当するリゾルバのアドレスを保持する。
【０００６】
名前解決の処理においては、名前解決要求者（以下、ユーザ。通常、インターネットに接続したパーソナルコンピュータ）は、まず、最寄の適当なリゾルバ（図１では、リゾルバ３）にアクセスする。リゾルバは、入力された名前をハッシュ関数でハッシュキーに変換する。目的のリソースのハッシュキーが自身が担当するゾーンにない場合、そのハッシュキーヘより近い、隣接するゾーン担当のリゾルバヘ問合せを転送する（図１では、リゾルバ２と４のうち、リゾルバ２の方が近いので、リゾルバ２に転送する）。ハッシュキーヘの近さは、ＣＡＮでは隣接ゾーンの代表のハッシュ値とリソースのハッシュキーの座標のユークリッド距離で比較される。この転送を繰り返すことにより、最終的にハッシュキーとルーティングアドレスとの対応を管理するリゾルバに問合せが到達し、名前解決が達成されることになる。
【０００７】
【非特許文献１】
Ｓ．Ｒａｔｎａｓａｍｙ，  Ｐ．Ｆｒａｎｃｉｓ，Ｍ．Ｈａｎｄｌｅｙ，  Ｒ．Ｋａｒｐ，  ａｎｄ  Ｓ．Ｓｈｅｎｋｅｒ，  “Ａ  ｓｃａｌａｂｌｅ  ｃｏｎｔｅｎｔ−ａｄｄｒｅｓｓａｂｌｅ  ｎｅｔｗｏｒｋ”，  Ｉｎ  Ｐｒｏｃ．ｏｆ  ＡＣＭ  ＳＩＧＣＯＭＭ  ０１，  Ａｕｇ．２００１．
【非特許文献２】
Ｉ．  Ｓｔｏｉｃａ，  Ｒ．  Ｍｏｒｒｉｓ，  Ｄ．  Ｘａｒｇｅｒ，  Ｍ．  Ｆ．  Ｋａａｓｈｏｅｋ，  ａｎｄ  Ｈ．  Ｂａｌａｋｒｉｓｈｎａｎ，  “Ｃｈｏｒｄ：Ａ  ｓｃａｌａｂｌｅ  ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  ｌｏｏｋｕｐ  ｓｅｒｖｉｃｅ  ｆｏｒ  ｉｎｔｅｒｍｅｔ  ａｐｐｌｉｃａｔｉｏｎｓ”，  Ｉｎ  Ｐｒｏｃ．  ｏｆ  ｔｈｅ  ＡＣＭ  ＳＩＧＣＯＭＭ  ２００１，  Ａｕｇ．  ２００１．
【０００８】
【発明が解決しようとする課題】
これらの機構は、効率的に名前解決の負荷やメモリを分散し、目的の名前解決情報への到達方法もシンプルであるという利点がある。特に、固定長の名前など、名前空間の構造がシンプルであるものについて、うまく動作する。しかしながら、属性ベースの名前など、柔軟な名前空間の場合は、ハッシュ関数による名前空間の分割などがうまく、動作せず、適さない。
【０００９】
属性ベースの名前に対する名前解決の類似技術としては、ＸＭＬで名前を規定するＷｅｂサービスのＵＤＤＩ機能がある。しかしながら、ＵＤＤＩは膨大な数の名前を処理するというよりは、各企業名程度の大きさの名前空間を想定したものであり、実際、ＵＤＤＩの公衆サービスは世界的に見て数社により提供されるに過ぎない。
【００１０】
従って、本発明の目的は、属性ベースなどの柔軟な名前空間に対しても或いは規模の拡大に対しても、良好に動作する名前解決機構を提供することにある。
【００１１】
【課題を解決する手段】
本発明による名前解決システムは、  ネットワーク上に分散蓄積されているリソースについて、ユーザからのアクセスに応じて目的とするリソースのアドレスをユーザに提供する名前解決システムにおいて、
当該名前解決システムは、ネットワーク上に配置した複数の名前解決装置を具えると共に、これらの名前解決装置が担当する複数の部分空間により構成される名前空間を有し、
各名前解決装置は、自己が担当する部分空間であって、軸上の距離情報として規定される複数のレベルにより規定される部分空間を具えると共に、自己が担当する部分空間内に属するリソースの名前とそのアドレスとの対応関係を規定した情報と、各レベルについて自己が担当する範囲を規定したデータと、ユーザから提示された名前について、各レベルの軸上の距離を各レベル毎に算出する手段と、算出された各レベルの距離が自担当の部分空間内に存在するか否かを判定する手段と、判定の結果として自担当の部分空間内に存在しない場合算出された距離に位置する部分空間を担当する名前解決装置に当該名前解決の問い合わせを転送する手段とをそれぞれ有し、
各名前解決装置は、ユーザから提示されたリソースの名前に基づいて名前解決処理を実行するに当たり、
ユーザから提示されたリソースの名前について、各レベルについて距離を算出する工程及び算出された距離が自己が担当する部分空間内に存在するか否かを判定する工程とを１つ又は複数のレベルについて繰り返し実行し、
自担当の名前空間の範囲内に存在する名前を見出した際、当該名前に対応するアドレスをユーザに提供することを特徴とする。
【００１２】
【発明の実施の形態】
本発明では、下記のような形態を例示するが、本質的には、図２に示すように、次のような名前空間の分割が可能であればよい。図２において、符号１は名前解決システムの全体空間を示し、符号２ａ，２ｂ，２ｃはリゾルバが担当する部分空間を示す。尚、図面を明瞭にするため３個の部分空間を示したが、勿論３個以上の部分空間を有することが可能である。さらに、符号３ａ及び３ｂは部分空間間の各レベル（後述するように、例えば名前のリーフ数、構造、要素が対応する）に関する軸上の距離を示す。部分空間は、次レベルでの全体空間になる、という手順を繰り返すイメージで、名前空間の部分空間に対して、対応するリゾルバを１つ又は複数割り当て、その中のいずれかのリゾルバ（名前解決装置）にまずアクセスする。そこで目的の名前と部分空間との関係をある軸（下記実施例では、リーフ数、構造、要素名、など）の距離で測る。近い部分空間を選択することにより、部分空間を選択する。次のレベルでは、最初の分割とは別の軸を必要に応じて採用し、前ステップと同様に繰り返すことで、最終的に目的部分空間（目的リゾルバ）に至る。▲１▼部分空間に対応するリゾルバを複数割り当てることができるので、名前空間上の名前の出現密度の濃淡に柔軟に対応でき、▲２▼部分空間の入れ子構造と異なる軸による名前空間分割を行うことで柔軟な名前空間に対応しやすい。
【００１３】
ＸＭＬによる属性ベースの名前記述による名前空間を前提として実施例を述べる。図３に、ＸＭＬによる名前例を示す。映画の例であるが、タイトルだけでは、邦訳版か否かなどが不明なため、それ以外の情報も付与されている。実際には、映画のタイトルが決まれば、俳優なども決まるため、冗長な情報を含む名前の例となっている。逆に、特定の実体を一意に特定できるだけの情報を含まない名前も想定される。図４に、この名前から抽出される構造を示す。本例では、ＸＭＬの名前記述を前提とするが、ＸＭＬのｆｏｒｍａｔ等は、本質的に本発明と重要な関連性を有していない。名前が、ツリー構造となること、ツリー構造のリーフに対応する要素（女優、製作年、など）と値（キム・ハンター、１９６８年、など）との対で構成されることが下記実施例の前提である。
【００１４】
名前のツリー構造を表記する方法として、以下の規則を用いる。名前ツリー上の各ノードを「点」と呼ぶことにする。図５に示すように、ルートを第０階層、ルートに直接ぶら下がる点を第１階層、第１階層の点に直接ぶら下がる点を第２階層、第ｋ階層の点に直接ぶら下がる点を第ｋ＋１階層と呼ぶ。
【００１５】
名前空間がＬ階層からなるとする。第１階層がｎｌ個の点、第２階層がｎ２個の点、第Ｌ階層がｎＬ個の点からなる名前空間を（ｎｌ，ｎ２，…，ｎＬ）と表記し、階層数のリストと呼ぶことにする。こうして表現される（情報が縮退した）名前空間を図示したものを名前構造空間図と呼ぶことにする。図６にｋ＝２の場合の名前構造空間図を図示する。図５の例は、図６において（３，１）として表される名前空間に属する。名前空間を名前構造空間図上で、分割する。図６において、点線が分割の境界線を示し、５つのリゾルバの担当空間に分割される。
【００１６】
名前構造空間上の１つの点に対応する名前を以下のように要素名で分割する。各リーフに対応する各要素の名前を例えば５０音順（アルファベット順でもよい）に並べ、その最も若い方から順に、要素名空間（図７）上での軸にとって、分割を行う。図４の例で言えば、要素の名前で最も５０音で若いものは「監督」であるので、第１の要素名として「監督」を取り出す。同様に、第２、第３の要素名を取り出して、要素空間を分割することにより、名前空間を分割することにより、名前空間を分割する。なお、リーフの全要素を取り出す必要はない。各リゾルバの担当範囲が、要素空間上で分離できるようになる次元数まで、取り出せばよい。
【００１７】
本実施例の概要を述べる。各リゾルバの担当する名前空間の範囲を、▲１▼まず、名前の中のリーフ数（値の数に相当する。例えば、図４の例では、１１）に対応して、分割し、最初の部分空間Ａを得る。▲２▼次に、名前の構造に注目して、同一のリーフ数を有する名前からなる名前（部分）空間Ａを分割し、第２の部分空間Ｂを得る。▲３▼最後に、部分空間Ｂを要素の名前でさらに分割し、最終的な目的の部分空間〈以下、目的部分空間〉を得るものである。目的の部分空間は、各リゾルバ対応に定義され、目的部分空間に属する名前に対しては、リゾルバは、名前とアドレスの対応表をもつ。
【００１８】
実際には、リーフ数での分割後、先に要素の名前で名前空間を分割し、次に、構造に着目してさらに名前空間を分割する方法（すなわち、▲１▼、▲３▼、▲２▼の順に行う方法）でも実施可能であるが、本実施例より容易に類推可能であるので、詳述しない。また、名前解決を行う対象システムが小規模であれば、▲１▼リーフ数による分割、▲２▼構造による名前空間の分割、あるいは、▲３▼要素の名前による名前空間の分割、のいずれか１つだけ或いはいずれか２つだけで、名前解決を行うことができる場合がある。これについても、本実施例より容易に類推可能であるので、詳述しない。また、ＸＭＬであることを前提とすると、業界ごとに、名前空間が定義されているケースもあり、この場合は、名前空間を定義組織などを軸に名前空間を分割すること可能である。この分割は自明であるので詳述しない。
【００１９】
次に、ネットワーク上に接続されたリゾルバが有する手段、機能ないし処理プログラムについて説明する。本例では、各リゾルバは、
・目的部分空間に属する名前とアドレスの対応表
・目的部分空間に対する、リーフ数の範囲（ｉｌ以下でｉ２以上）（部分空間Ａに相当）、名前構造空間上の部分空間（部分空間Ｂに相当）、要素名を軸とする空間上での部分空間（目的部分空間に相当）
・分割した名前空間に属する名前のリーフ数が「ｉｌ＋１」であるリゾルバのうちのどれか１つのアドレス（以下ａｌ）、
・分割した名前空間に属する名前のリーフ数が「ｉ２−１」であるリゾルバのうちのどれか１つのアドレス（以下ａ２〉、
・ｉ２以上ｉｌ以下の各整数値ｉをリーフ数とする名前に対する名前構造空間上で、自分が担当する部分空間に隣接した各分割名前空間を担当するリゾルバのうちのどれか１つのアドレス（各ｉについて、少なくとも２つの部分空間に対応するアドレス）、
・自分が担当する名前構造空間内の各点に関する要素空間で、第ｉ要素を軸として隣接する各部分空間（若番側、老番側）を担当する少なくとも１つのリゾルバのアドレス〈各ｉについて〉
・名前を入力された場合、当該名前のリーフ数を計数、比較する手段（プログラム）、名前の構造を抽出する手段（プログラム）、名前構造空間上でのユークリッド距離を計算、比較する手段（プログラム）、及び要素名を順に抽出して比較する手段（プログラム）、
・ユーザから提示された名前が自己が担当する部分空間内に存在しない場合、算出された距離に位置する部分空間を担当するリゾルバに当該問い合わせを転送する手段を保持する。
【００２０】
次に、名前の解決処理の一例について説明する。名前解決の処理においては、名前解決要求者（ユーザ）は、まず、ネットワークを介して目的とするリソースの名前を提示して最寄の適当なリゾルバにアクセスする。各リゾルバでは、
▲１▼＜リーフ数による名前空間分割＞
名前解決をして対応するアドレスを見出す必要がある名前（以下、目的の名前）のリーフ数を数える。その数Ｉが、自分の担当するリーフ数の範囲にあれば、処理▲２▼へ移行する。計算されたリーフ数Ｉが自担当のリーフ数の範囲より大きい場合は、ａｌのアドレスのリゾルバヘ行き、再び▲１▼から開始する。Ｉが自担当のリーフ数の範囲より小さい場合は、当該ユーザからの問い合わせをａ２のアドレスのリゾルバヘ転送し、再び▲１▼から開始する。
【００２１】
▲２▼＜構造による名前空間分割＞
解決要求している名前の構造をリゾルバのプログラムが解釈し、階層数のリスト（構造）を抽出する。この構造が、自身が担当する部分空間にある場合は、▲３▼へ移行する。目的の名前の構造が自身が担当する部分空間にない場合、名前構造空間図上、各隣接ゾーンの代表（中央）の座標と名前解決要求リソースの名前の座標のユークリッド距離を計算する。名前構造空間において当該名前が近い（上記、計算した距離の短い）ほうの隣接する部分空間担当のリゾルバ（の１つ）へ問合せを転送する。（図６で、目的の名前の構造が（５，１）で、自分がリゾルバｘであるとすると、リゾルバｙに転送する。）転送されたリゾルバでは、再び▲１▼から処理を開始する。
【００２２】
▲３▼＜要素による名前空間分割＞
自分が担当する部分空間が、第何要素までを軸として分割されているか、チェックする（例えば、第１要素が「監督」であり、第２要素以降は何でもよい、など）。第ｊ要素までの軸だとする。解決要求している名前をリゾルバのプログラムが解釈し、各リーフに対応する各要素の名前を５０音順（アルファベット順でもよい）に並べ、その最も若い方から順に、第ｊ要素まで抽出する。第１からｊ要素に対して、まず、自担当の名前部分空間（目的部分空間）に属するか判定する。目的部分空間に属していれば、▲４▼へ。そうでなければ、第１からｊ要素までを使った要素空間で隣接する部分空間を担当するリゾルバのうち、目的の名前が属する部分空間に近い部分空間を担当するリゾルバに問い合わせを転送する。ここでいう近さは、以下のように定義する．目的の名前の第１からｋ要素までは、目的部分空間に属するが、第ｋ＋１要素が目的部分空間に属さないとする。目的の名前の第ｋ＋１要素が、目的部分空間の第ｋ＋１要素より、５０昔順で若番なら若番側、老番なら老番側を近いものとする。転送されたリゾルバでは、再び（▲１▼から開始する。
【００２３】
▲４▼＜名前解決＞
目的の名前が名前とアドレスの対応表に記載されているので、目的の名前に対応するアドレスを読み出し、名前解決要求者に回答する。
【００２４】
【発明の効果】
柔軟な名前空間に対しても、並びに大規模化しても対応できる名前解決機構が構築できる。
【図面の簡単な説明】
【図１】従来の名前解決システムの処理例を示す線図である。
【図２】本発明による名前解決方法の概念を示す線図である。
【図３】名前をＸＭＬで記述した例を示す線図である。
【図４】図３に示す名前から抽出される構造を示す線図である。
【図５】名前の階層構造を示す線図である。
【図６】名前の構造空間を示す線図である。
【図７】名前の要素空間を示す線図である。
【符号の説明】
１    全体空間
２ａ〜２ｃ    部分空間
３ａ，３ｂ    軸上の距離
【図１】
2005004587.tif 000003
【図２】
2005004587.tif 000004
【図３】
2005004587.tif 000005
【図４】
2005004587.tif 000006
【図５】
2005004587.tif 000007
【図６】
2005004587.tif 000008
【図７】
2005004587.tif 000009