Introduction

The evolution of computers and the Internet now brings us the ability to access huge number of computing and networking resources distributed widely on the Internet and on devices in the area surrounding users. Effective utilization of these resources will allow us to use various kinds of attractive services such as web services, context-aware network services, Grid computing systems, etc. Since number of resources is huge and their accessibility may change due to user's environment, the realization of flexible and seamless access to computing and networking resources is a big challenge.

Personal Mesh

In the first half of this dissertation, we focus our attention on the utilization of networking resources such as wireless LAN, 3G, 4G, etc appearing in a personal area network（PAN）. The motivation of our work comes from the consideration that personal devices' Internet connection quality can be improved by sharing access link resources in a PAN. First, the Internet connection area of mobile devices can be expanded. For example, a mobile device which has only a short-range wireless link can access the Internet via a wide-area access link of other devices in the PAN. Second, since one bottleneck link on the end-to-end communication path of personal devices is on the wireless access link, Internet connection quality can be improved through the utilization of appropriate access links for each communication session, which meets the application's performance requirements and the user's preferences.

We have developed a framework, called Personal Mesh, which enables devices in a PAN to use appropriate access links for their communication sessions without interruption even when access link resources in PAN change dynamically. Our framework is realized by a software module installed on devices that have at least one Internet access link （Fig. 1）. We call such a device a Personal Gateway （PGW）. Our design does not require local devices （i.e. devices that have only short-range wireless link） to be aware of the change in access link resources.

First, PGWs select appropriate access links for each communication session of each PAN device passing through it. The selection is based on access link information, application requirements and user preferences. PGWs cooperate with each others to gather required information. They also observe access link resource changes. Whenever an access link resource change occurs, they reselect access link and trigger a handoff if necessary.

Second, PGWs maintain addresses of devices in PAN unchanged through the use of an address/port translation function. This function is an extended version of the address/port translation function of a NAPT's box, modified for the use with a PAN mobility support scheme to be mentioned later. Every PAN device is assigned a private address when joining the PAN. They use the private address to communicate with hosts in the global network. The address/port translation function of PGWs makes proper packet routing between the PAN and the global network possible.

Third, the change of network location of PAN devices when a handoff occurs is concealed through the use of the address/port translation and the session information binding update in PGWs and corresponding hosts. PGWs in a PAN share session information between each other. When a handoff occurs, PGWs will notify the corresponding hosts about the new session information. The PGW and the corresponding host will use the session information to perform address/port translation for the session such that the change of network location due to the handoff will be transparent to local devices and application layer of the corresponding hosts. Through the use of session information in the binding update and packet forwarding, our scheme allows devices in PAN to independently switch each of their communication sessions to the appropriate access link without communication interruption.

We have implemented a prototype of Personal Mesh and have proved the effectiveness of our system by experiment.

SENS: A Scalable and Expressive Naming System

In the second half of the dissertation, we design a scalable and expressive naming system called SENS to provide information systems a resource information　retrieval service based on resource names. The motivation of our work comes from the fact that because number of computing and information resources distributed on the Internet is huge and increasing rapidly, information of resources must be stored in a large number of servers. Our system will route query messages to servers responsible for queried information.

Our system utilizes a descriptive naming scheme which names each resource by a tuple of attribute/value pairs. Resource information is distributed at name servers （NSs） based on resource names. Our system retrieves resource information by exact queries （i.e. query information of a resource whose resource name is the same as the query name） and multiple-attribute range queries （i.e. querying information of resources whose names have attribute values satisfying a query range） over resource names.

SENS distributes resource information to the overlay network of NSs based on resource IDs. The resource ID space is a virtual d-dimensional Cartesian coordinate space built on the overlay network of NSs. Each resource name is mapped to one or several resource IDs. Resource information including a resource name and meta-data is stored at NSs whose are responsible for resource IDs. A NS performs a query by mapping a queried resource name or a range of queried names to a queried resource ID or a range of resource IDs and then sending a query message to NSs that are responsible for the queried resource ID or the queried range of resource IDs.

To limit number of NSs responsible for a range query, we propose a locality-preserving mapping scheme between a multi-attribute resource name space and a multi-dimensional resource ID space. A resource name is mapped to a resource ID by mapping each attribute value in attribute/value pairs of the resource name to a coordinate value of the resource ID in a deterministic dimension assigned by the attribute （Fig. 2）. As the result, our matching scheme allows all resource names that match a range query to be mapped within a limited segment of the resource ID space. We call it the range query segment. To resolve a range query, a range query message will be sent to NSs responsible for the range query segment. We propose a multi-attribute range query algorithm which is a combination of the CAN routing algorithm and a broadcast routing algorithm based on a spanning binomial tree （Fig. 3）.

Consequently, our SENS system is designed by the following elements:

A locality preserving mapping scheme between multi-attribute resource name space and a resource ID space. All resource names that match a range query will be mapped within a limited range query segment of the resource ID space.

The construction of resource ID space on the overlay network of NSs based on the CAN routing algorithm.

A resource information delivery algorithm which is a combination of the CAN routing algorithm and a multicast routing algorithm based on a spanning binomial tree. It delivers resource information to corresponding NSs with a minimum number of messages.

A multi-attribute range query algorithm which is a combination of the CAN routing algorithm and a broadcast routing algorithm based on a spanning binomial tree. It routes multi-attribute range query messages to NSs in a range query segment with a minimum number of messages.

We also conduct simulations to evaluate the performance of the SENS system. The simulation result shows that the SENS system can realize exact queries and range queries with a reasonable cost. Furthermore, our system can achieve a good degree of load balancing even the distribution of attribute/value pairs in resource names is skewed.

Structure of thesis

This dissertation is organized as follows.

In Chapter 1, we introduce the background and the contributions of our research.

In Chapter 2, we present the background of our design in Section 2.1; discuss related works in Session 2.2. We describe our implementation including Personal Mesh's system structure and its operations in Section 2.3. Section 2.4 describes our testbed network and our experimental results. We conclude the chapter in Section 2.6.

In Chapter 3, we present the background of our system in Section 3.1. Section 3.2 discusses the related works and their problems. We describe our system's design in Section 3.3 and our simulation and the results in Section 3.4. We conclude the chapter in Section 3.5.

In Chapter 4, we summarize our contributions and conclude this dissertation.

Fig. 1 Structure map of Personal Gateway

Fig. 2 The mapping between a resource name and a resource ID

Fig. 3 A broadcast routing protocol for sending a query message to a range query segment based on a spanning binomial tree

本論文は「Flexible and Seamless Access Architecture for Ubiquitous Computing and Networking Resources （ユビキタスコンピューティング環境におけるリソースアクセスアーキテクチャに関する研究）」と題し，全4章からなる．今後ユビキタスコンピューティングリソースは，その数，種類と共に増加の一途をたどると考えられ．リソースの多様化. 遍在化が進むユビキタスコンピューティング環境においてユーザはこれらのリソースを効率的に利用できることが望ましい．そこで本論文ではユビキタスコンピューティングリソースへ柔軟なアクセスを実現するためのネットワークアーキテクチャについて論じている．

第1章は序論であり、ユビキタスコンピューティング環境におけるリソースの多様化. 遍在化について述べ、ユビキタスコンピューティングリソースを柔軟かつ有効に利用したいという需要などについて考察し、本研究の背景と研究の目的及び論文の構成について述べている．

第2章「パーソナルメッシュ」はユーザを取り巻くパーソナルエリアネットワークに遍在するインターネットアクセスリンクのリソースに着目している．ユーザが移動する際、アクセスリンクのリソースは動的に変動するため、通信環境に応じて適切なアクセスリンクを切り替えながら通信できる機構が必要となる．この機構をパーソナルメッシュと命名し．まずパーソナルメッシュの内部アドレス空間をプライベートアドレスとすることで，グローバルネットワークから分離させる。これはパーソナルメッシュの内部デバイスに対して移動を隠蔽するためである．次に、アクセスリンクを持つパーソナルゲートウェイ（PGW）はアドレス/ポート変換によりパーソナルメッシュの内部からグローバルネットワークへの通信を可能にする．さらに、各PGWは自律的にアクセスリンク選択とモビリティサポートを行い、お互いにアクセスリンクリソースの情報を交換することによって、各通信セッションに対してユーザの嗜好，アプリケーションの特徴及びアクセスリンクリソースに基づいて適切なアクセスリンクを選択することを可能にする．また、アクセスリンクリソースの変化が起こると、それを検知し、必要に応じてアクセスリンクの切り替えを行う．アクセスリンクの切り替えの際、PGWは通信相手ホストに対してエンドツーエンドでセッション情報を送信し、アドレス変換を適切に行うことによって、外部アドレスの変化を隠蔽する．ここでは，パーソナルメッシュの構成とPGW 間における通信プロトコルを示す．また，実際にテストベッドネットワークを構築してハンドオフ時間を測定し，基本動作の確認を行う性能評価について述べている．

第3章「SENS」ではユビキタスコンピューティングリソースの情報検索を可能にするネーミングシステムの設計を考察する．インターネット上に分散している膨大な数のコンピューティングリソースやコンテンツリソースを有効に利用するために，リソースに付けられた名前の完全一致検索だけでなく，リソースの属性値の範囲を絞って検索を行うスケーラブルなネーミングシステムが必要となる．本章では，このようなネーミングシステムを実現するために，リソースの属性値を反映するネーミング体系を構成し，オーバレイネットワーク上においてスケーラブルなルーティングを行うCANルーティングアルゴリズムを適用し、多次元リソースID座標空間を構築する手法について示している．また、属性値のハッシュ値をリソースIDに適切に反映させるようなマッピング手法を提案している．それによって、リソース名の局所性をリソースID座標空間上に維持し，一つの範囲検索または部分検索に該当するリソース名をある部分空間にマッピングすることを可能にしている．これによって本システムではリソースIDのまま資源の名前と検索キーの照合を行い，効率の良い範囲検索や部分検索を達成することができる．さらに大規模なネーミングシステムに欠かせない負荷分散という性質も達成することができる．このような手法を構成するシステムを設計し、様々なパラメータを変数とするシミュレーションを行い、設計したシステムの有効性を評価している．

第4章は「結論」であり，本論文の成果をまとめるとともに今後の研究の方向性について述べている．

以上，これを要するに，本論文は，ユビキタスコンピューティング環境において，柔軟なリソースアクセスを実現するために動的なパーソナルアリアネットワークに遍在するネットワーキングリソースを環境に応じて柔軟に利用できる環境適応型移動透過機構、リソース名前の一致検索、範囲検索と部分検索が実現できるスケーラブルなネーミングシステムの設計を提案し，実装評価およびシミュレーションによりその有効性を示しており電子情報学上寄与するところが少なくない。よって本論文は博士（情報理工学）の学位請求論文として合格と認められる．