分散ハッシュテーブルを用いた ONS の設計と実装

卒業制作

2003

(

15

)

分散ハッシュテーブルを用いた ONS の設計と実装

指導教員 徳田 英幸

村井 純 楠本 博之

中村 修 南 政樹

慶應義塾大学 環境情報学部 廣瀬 峻

[email protected]

平成

16

1

15

概 要

RFID

EPC Global

Auto-ID Lab

Auto-ID

Auto-ID

EPC

ID

RFID

この

ID

製品の情報をネットワーク上に展開し、管理するためには、情報を保持したサーバを特定す る名前解決機構が必要である。現在の

Auto-ID

EPC

DNS

ONS

DNS

本研究では、

Auto-ID

ONS

DNS

本研究により、

Auto-ID

EPC

ID

キーワード

1,

2,

3, Object Name Service 4, Auto-ID

慶應義塾大学 環境情報学部

廣瀬 峻

abstract

With the popularization of RFIDs, various researches using the automatic individual recog- nition technology are being accelerated for its infinite possibility. One of these is the Auto-ID system lead by EPC Global and Auto-ID Laboratory. The Auto-ID system propose a use case model where products are maintained by attaching RFID tags which have an ID called EPC, and detecting the tags over radio transmission allowing identification of individual products.

The meta information of each product, such as the shipping status and their location, are maintained over a network for use with various applications.

When maintaining product information over a network, it is necessary to have a name resolution feature which resolves the specific server holding the product’s information. The proposed method for this in the current Auto-ID system uses the same resolution method used in the Internet called Domain Name Server (DNS). EPC allocated in each product is used as keys when searching for the destination server.

The EPC used in the Auto-ID retain its uniqueness by structuring the ID from the vendor ID, the product number, and the serial number. This structure involves a concern for privacy, since anyone capable of reading the ID can easily guess the product itself. Thus, a mechanism to encrypt the ID is needed and is currently being proposed to insure privacy. However, the proposed method uses plain text when handling the ID by decrypting the encrypted ID. In a case with package delivery service using Auto-ID, the sender may use the encrypted ID for the product before handing the package to the postman. If plain text is used when handling the product, any third party can obtain the original ID. Therefore, it is necessary to utilize the encrypted ID without any decryption. When applying this in the Auto-ID system, name resolution system which can handle ID that are not in a structured format, same as those encrypted ID, is necessary.

In this research, we design and implement a name resolution system capable of handling the mapping of unstructured ID with its server holding the meta information, as an extension to the proposed Auto-ID system. This name resolution independent ID format was realized by using Distributed Hash Table (DHT), mapping search keys with the hash space.

From this research, name resolution system capable of handling any sophisticated ID format is realized. By covering the meta information which were visible in the original system to provide privacy, and still retaining the uniqueness of the ID, the effectiveness of the system was shown.

Keywords

1, Name Resolve 2, Distributed Hash Table 3, Object Name Service 4, Auto-ID Faculty of Environmental Information, Keio University

Shun Hirose

目 次

第

1

1

1.1

. . . . 1

1.2

. . . . 2

1.3

. . . . 2

第

2

Auto-ID

3 2.1 Auto-ID

. . . . 3

2.2

ONS

. . . . 6

2.3

. . . . 7

第

3

8 3.1

. . . . 8

3.2 DHT

ONS

. . . . 8

3.2.1

. . . . 8

3.2.2

. . . . 9

3.2.3

. . . . 10

3.3 DHT

. . . . 10

第

4

DHT

ONS

12 4.1

. . . . 12

4.2

. . . . 12

4.2.1

. . . . 12

4.2.2 ONS

. . . . 14

4.3 DHT

. . . . 15

4.3.1

. . . . 15

4.3.2

. . . . 15

4.3.3

. . . . 16

4.3.4

. . . . 16

4.3.5

. . . . 16

4.3.6

. . . . 16

第

5

DHT

ONS

18 5.1

. . . . 18

5.2

. . . . 18

5.2.1

ID

. . . . 18

5.2.2

. . . . 19

5.2.3

. . . . 19

5.2.4

. . . . 20

5.2.5

. . . . 21

5.2.6

. . . . 21

第

6

25 6.1

. . . . 25

6.2

. . . . 25

6.3

. . . . 26

第

7

30 7.1

. . . . 30

7.2

. . . . 30

付 録

A The Chord Protocol 34 A.1

. . . . 34

付 録

B Naming Authority Pointer 37

B.1 NAPTR RR . . . . 37

図 目 次

1.1

RFID . . . . 1

2.1 Auto-ID

(

Auto-ID Center

) . . . . 3

2.2 Auto-ID

. . . . 4

2.3 EPC

. . . . 5

2.4 ONS

. . . . 6

2.5

. . . . 7

4.1

. . . . 13

4.2 ONS

. . . . 14

4.3

. . . . 15

4.4

. . . . 16

5.1 SHA1

ID . . . . 18

5.2

. . . . 19

5.3

. . . . 19

5.4

. . . . 20

5.5

. . . . 21

5.6

. . . . 22

5.7

. . . . 23

5.8

. . . . 23

5.9

. . . . 24

6.1

. . . . 25

6.2

. . . . 26

6.3

. . . . 27

6.4

. . . . 27

6.5

. . . . 28

6.6 Server

. . . . 29

A.1 Chord

. . . . 34

A.2

Chord

. . . . 36

表 目 次

3.1 DHT

ONS

. . . . 8

3.2

. . . . 10

5.1 DHT ONS

. . . . 18

5.2

. . . . 19

5.3 message

. . . . 20

A.1

. . . . 35

B.1 NAPTR

. . . . 38

第 1 _{章 序論}

本章では、本研究の背景および研究の目的について述べる。また本論文の構成を示す。

1.1 背景

Radio Frequency IDentification(RFID)

現在

RFID

RFID

IC

RFID

IC

Sony

Felica[1]

Felica

JR

Suica[2]

IC

IC

[3]

FeliCa

Edy

[4]

RFID

1.1

Omron

[5]

図

1.1:

RFID

RFID

Supply Chain Management(SCM)

では薬品や患者を

RFID

RFID

このように、

RFID

これらの要求にともない、製品に一意な

ID

Auto-ID

EPC Global[6]

Auto-ID Laboratory(

Auto-ID Center)[7]

Auto-ID

別技術の開発を主目的として始まった。製品の製造段階で、一意性が保証されている

Electronic Product Code(EPC)[8]

RFID

(Source Tagging)

EPC Information Service(EPCIS)[9]

EPCIS

EPCIS

EPCIS

EPC

EPCIS

Auto-ID

Object Name Service(ONS)[10]

として定義している。

現在の

ONS

Domain Name System(DNS)[11]

DNS

ID

Auto-ID

DNS

Root

1.2 目的

本研究では、現在インターネットの名前解決機構である

DNS

Auto-ID

ONS

ONS

とは異なる名前解決機構を実現することを目的とする。

1.3 本論文の構成

本論文は

7

第

2

Auto-ID

3

4

5

6

7

第 2 _{章 現在の} Auto-ID _{システムにおける名前} 解決の問題点

本章では、

Auto-ID

2.1 Auto-ID のシステム概要

Auto-ID

EPC

ID

RFID

EPC

EPC

製品データを蓄積したサーバに対して、様々なアプリケーションがアクセスし、製品情報を 取得・利用することが想定されている。つまり、

EPC

Auto-ID

図

2.1

Auto-ID

図

2.1: Auto-ID

(

Auto-ID Center

)

次に、現在

Auto-ID Center

2.2

Auto ID

EPC

EPC

Savant[12]

ONS

EPCIS

!#"$%

&'()

*+,+.-

/ .01!2"3$%4 506!

$

)87

!91:5;<=06>

7)=?

5;

(7 0

% 7 0;@ :5; '(; AB"3$%< / DCCE@FHG

F@I

DCCEFHG

FHI

2J

2J

KBLM

N K#LM

N

I 1O

G

J

QP

I

,RM

FHI

I 1O

G

J

QP

I

,RM

FHI

S :5; +"UT1.0V; ? .01 W )

X5Y[Z

X5\[]^

_` Zab6^c

dHef

^.gh eh f hji

X5Y[Z

X5\[]^

_` Zab6^c

dHef

^.gh eh f hji

\1kUX^.g h eh f h,i

^.gh eh f hji

\1kUX^.g h eh f h,i

^.gh eh f hji

l

? )

+ 7 *T1

m

^c

X d gnpo

f8d Zh

f8qHe ohsr

m ^c

t

^.gh,usv

f@e5w r5xhNgy

qHe ohsr

dHef z hNg

dH{5q y|5i

dj}

X d r.~hsgVu

qHeq



qHed h,x5y

q

rjv5x

q8fHe v,g

d

dHef

図

2.2: Auto-ID

以下に図中の用語について概要を示す。

• EPC

EPC

Auto-ID Center

(Source Tagging)

EPC

2.3

EPC

8

ID

28

ID

24

ID

36

ID

96

ID

64

256

EPC

• EPC

!"

#%$'&()*,+-

./1023

!54"

687:9 ;-<=&?>,@-@

A.CBD

E

F HG>JIKL 7 J

MONQPSRDT1UC VCWYXZVSV[V[V]\_^[`1XZV[VSVCWba1cdXZVSV[VCWeaf`gihjV

図

2.3: EPC

EPC

EPC

タグ自身が電波を発生する比較的高価なアクティブタグと、電源を内部に持たず、リーダ からの電波を受けることで電波を発生する比較的安価なパッシブタグの２種類がある。ま

た、

Auto-ID

ID

• EPC

EPC

EPC

EPC

EPC

• Savant

Savant

ウェアである。

Savant

EPC

EPC

EPCIS

• EPCIS

EPCIS

EPC

Sim-

ple Object Access Protocol(SOAP)[13]

XML Remote Procedure Call(XML-RPC)[14]

SQL

• ONS

ONS

EPC

EPC

EPCIS

ONS

EPC

ONS

ONS

ONS

DNS

EPC

EPCIS

ONS

EPC

DNS

ONS

ONS

EPCIS

として、

NAPTR

(RR)[15]

ONS

なお、

DNS

2.4

現在の

ONS

1. ID

URI

2.

!"#%$!

!& ('*)"+

,

)-,

.!& 0/$12,034$25

15

" !!&

5

4!& 6,.1$$ 7048$25/

9

5;:

/

! 7<

/

! 7

図

2.4: ONS

3.

”onsroot.org”

次に

Auto-ID

EPC

EPC

タグから

EPC

EPC

Savant

EPC

Savant

Savant

EPC

EPCIS

EPC

アプリケーションは、

EPC

ONS

EPCIS

そして、

EPCIS

EPC

2.2 既存 ONS の問題点

本節では、既存

ONS

既存の

Auto-ID

ONS

機構である

DNS

図

2.5

2.1

図中の

ONS Resolver

EPC

ONS

Root

Root

ID

Root

また、

DNS

!#"%$'&(

)+* ,- ./..

021'3

4'5768:9;5%<

021'3

4'5768:9;=5:<

> ?@?A9BCD=EB8AF

G%3'D;@DAFE

> ?@?A9BCD=EB8AF

G%3'D;@DAFE

)*,- ./..

図

2.5:

2.3 新しい名前解決機構への要件

•

システムとして、

Single Point of Failure

•

Auto-ID

DNS

成され、検索されることが予想される。これを一つのサーバで集中管理するのは非現実 的であり、分散システムの形式をとることが必要である。

•

現在の

ONS

EPC

2.1

しかし、今後

EPC

ID

ID

以上のことを考慮しながら新たな名前解決機構を設計する必要がある。

第 3 章 問題解決へのアプローチ

本章では、第

2

3.1 分散ハッシュテーブル

分散ハッシュテーブル

(Distributed Hash Table

DHT)

ID

DHT

peer to peer

(scalable)

(robust)

3.2 DHT を用いた ONS に対する考察

本節では、

DHT

ONS

DNS

ONS

3.1

3.2.1

表

3.1: DHT

ONS

DNS DHT

運用 管理権限 データ登録 △ ○

データ保持 ○ △

耐故障性 △ アルゴリズムに依存

その他 規模性 負荷分散 ○ ○

局所性 ○ アルゴリズムに依存 その他 非構造的名前空間 × ○

3.2.1

現在、

DNS

(

RR)

SCM

ID

これに対し、

DHT

どのノードにデータの登録要求を行っても同じ結果となる。これにより、消費者が自分が購入 した製品をローカルなデータベースで管理したい、といったニーズにも対応できる。ただし、

誰にでもデータの登録ができるということは、悪意あるユーザが偽りのデータを登録すること も可能となる。この問題は、

Public Key Infrastructure(PKI)[16]

このように、データの登録制限という点で

DHT

他方で、データ保持の問題が考えられる。

DNS

DHT

(

)

3.2.2

システムとしての規模性を比較するにあたり、耐故障性、負荷分散、局所性の三点について 検討を行う。

耐故障性

DNS

(

)

Root

Single Point of Failure

Single Point of Failure

DNS

Root

NS RR

TTL

Cache

一方、

DHT

DHT

3.1

負荷分散

DNS

管理空間を委譲していくことで、一人の管理者が管理する空間を小さくし、負荷を軽減して いる。

DHT

局所性

DNS

一方で、

DHT

localize

ID

3.2.3

DNS

ID

一方、

DHT

DNS

DHT

ONS

システム参加へのインセンティブ

DNS

DHT

P2P

3.3 DHT におけるアルゴリズム比較

分散ハッシュの検索アルゴリズムとして、

Chord[17]

Tapestry[18]

CAN[19]

3.2

表

3.2:

Chord Tapestry CAN

データ構造

Skiplist Plaxton

d

1

1

d

O(log

N ) O(log

N) O(d ∗ N

)

O(log

N ) bLog

N O(d)

insert

O(log

N ) O(log

N ) O(d ∗ N

)

負荷分散 ○ ○ ○

アルゴリズムの簡易性 ○ ○ △

局所性 × ○ ×

耐故障性 ○ × △

注

. N : ID space, b : IDs of base b, d :

• Chord

データをハッシュした値を基に、論理ネットワーク上にあるノードに、データを割り当 てる。各ノードは

N

ID

N

• Tapestry

データをハッシュした値を基に、ハッシュ値の部分一致をにより検索を行う。

Tapestry

Plaxton

(Plaxton

Rajaman

Richa

)

• CAN

データから

d

d

d

ID

各ノードは自身の管理領域

(

)

ID

CAN

Tapestry

Chord

fail

Chord

logN

ゆえに、本研究では、検索アルゴリズムに

Chord

第 4 _章 DHT _を用いた ONS _の設計

本章では、

DHT

ONS

4.1 設計概要

本研究では、

Auto-ID

UID

EPCIS

UID

EPCIS

ID

Auto-ID

ONS

EPC

信するインターフェースと、検索するための機能が必要である。すなわち、既存のシステムに おいて、

ONS

ONS

3

DHT

次節では、

ONS

4.2 システムの設計

本節では本研究で構築する名前解決機構のシステム構成について述べる。

4.2.1

本研究では、特に

DNS

DHT

DHT

DHT ONS

4.1

このシステムモデルでは

ONS

API

ID

ONS

取った

ID

DNS

DHT ONS

信したネーミングシステムは、

DNS

NAPTR RR

DHT ONS

IP

なお、本節で述べるデータを、検索キーとなる

ID

IP

3.1

US Secure Hash Algorithm 1(SHA1)[20]

160

ID

SHA-1

EPC

96

ID

ID

"!#%$'&(

)*,+-./10324*

"!4&5687%9;:=< >7@?

ACB=D@EF G"H

JIKLK'K

&

HNM%M EDPO8O

Q=: O8D

M

"!

Q=: O8D

M

$&(

SRR +T")N2U+-

図

4.1:

4.2.2 ONS

ONS

(

)

”Service Location”

SAG(Software Action Group)[21]

ONS

4.2

!" #%$'&)( *+" ,.- *

/0123" *'- *54'*+6 7

*34'#%68/9 /:!

/01&;- #%$=<3#%"<

>?@&BA ?DCB1@EF

7

*34'#%68/9

G$8- H+" ( #54'H IKJ

IKJ

IKJ

図

4.2: ONS

図

4.2

EPC

EPCIS

DNS

DHT

EPCIS

特定のネーミングシステムに依存していないので、検索のニーズ、オプションに応じて問い合 わせるネーミングシステムを変え、柔軟な検索を行えることが大きな特徴である。

本研究で構築する名前解決機構において、検索の柔軟性は重要である。なぜなら

DNS

UID

Protocol dispatcher

リゾルバで、各ネームシステム毎のクエリを生成するためには、

API

ID

ネームサービスを指定するフラグを付加することや、リゾルバに送信するデータフォーマット を統一すること、リゾルバ側にコンフィグファイルを置く方法などが具体的にあげられる。

本研究で想定するモデルでは、

96

EPC

EPC

UID

ID

API

ID

ID

ID

2.3

8

れている、すなわち構造化されている場合は

DNS

ID

ID

96

DNS

4.3 DHT による名前解決

本節では、

DHT

4.3.1

本システムでは、システムに参加するノードは自身の

IP

SHA-1

ID

ID

4.3.2

ハッシュテーブルの構築の際に問題となるのが、悪意あるノードの参加である。悪意のある ノードが参加すると、データを保持しつつ故意に接続性をなくしたり、嘘のデータを投げたり することが可能となる。

よって、ノードがシステムに参加する時点で、ノードを認証する枠組が必要となる。

!

"#$

"%$

"#$

"%$ &&

&&

&&' &&'

& (&) (&) (&

& (&) (&) (&

(&) &) & &)

(& (&)

(&)

(&

(&

(&) *+(,-.#/

0123452678926:5

;4<=4<

>(?)@A'B - @,C

>'@B ./

D

++(E

?F .GIHJI/

KBL ,M @BK

.GNHJI/

O B D

B@B .GNHJI/

PQRS#TVUWYXZV[

PQRS#TVUWYXZ\[

図

4.3:

図

4.3

4.3.3

データの登録には

ID

ID

SHA-1

HID

4.3.4

本システムで行うデータ検索は、

”ID

”

ID

96

ID

4.3.5

データの保持の仕方には、リスト構造、ローカルデータベース、などいくつか考えられる。

Auto-ID

ると予想される。よって、データの登録、削除、検索をはやく、かつ効率的に行えるデータ構 造が望ましい。

図

4.4

図

4.4:

4.3.6

本システムでは、各ノードがデータをおおよそ均一に保持している。しかし、データを保持 したノードが何らかの理由により到達性を失う可能性は十分に考えられ、それに伴ってデータ

への到達性が失われる。

Chord

本研究では、今回この機能はサポートしないが、

ID

Savant

第 5 _章 DHT _を用いた ONS _の実装

本章では、本研究で行った実装について述べる。

5.1 実装環境

DHT

ONS(

DHT ONS)

5.1

表

5.1: DHT ONS

OS FreeBSD 5.1-RELEASE CPU Pentium4 2.5GHz

1024Kbyte

言語

C

5.2 実装

本節では、本研究における実装について述べる。

5.2.1

ID

本研究における実装では

SHA-1

160

ID

IP

ID

C

160

unsigned char

ID(

HID)

¶ ³

typedef unsigned char uint8_t; //uint8_t

unsigned char

uint8_t Message_Digest[20]; //

ID

µ ´

図

5.1: SHA1

ID

図

5.1

HID

HID

unsigned char

uint8 t

として定義し、

HID

Message Digest[20]

8bit × 20 = 160bit

ID

4

40

5.2.2

ルーティングテーブルのメンバ構成を表

5.2

index

ID(

)

ID

IP

表

5.2:

index

ID

IP

本実装では、図

5.2

index

index

¶ ³

struct routeTable{

uint8_t hid[20]; //

uint8_t nodeid[20]; //

ID

char *ipaddr; //IP

};

µ ´

図

5.2:

5.2.3

システムに参加するノードは、自身のノード情報を図

5.3

ID

IP

ID

IP

¶ ³

struct mynode_info{

uint8_t hid[20];

char *ipaddr;

struct routeTable successor;

struct routeTable predecessor;

};

µ ´

図

5.3: