[ Japanese version ] [ English version ] [ Edit this subsite ]

2034-02-02

What's New

TowardProgrammingLinguistics.jpg

キーワード:

2014-07-12

Method of Designing, Partitioning, and Printing 3D Objects with Specified Printing Direction

Kanada, Y., 2014 International Symposium on Flexible Automation (ISFA 2014), 2014-7.
[ English page ]
[ 論文 PDF ファイル ]
[ スライド PDF ファイル (w/o video) ]
[ スライド (Keynote (Macintosh) 用ファイル.ビデオつき) ]

Abstract: Although 3D objects to be printed may have “natural direction” or intended direction for printing, most 3D printing methods slice and print them horizontally. This causes staircase effect on the surface and prevents expression of the natural or intended direction; that is, the natural direction and the printing direction contradict. This paper proposes a methodology for direction-specified 3D printing and methods for designing, partitioning, and printing 3D objects with specified printing direction using a fused deposition modeling (FDM) printer. By using these methods, printed objects do not only have unnatural steps but also enables to express the direction explicitly. By developing and evaluating a set of methods based on this methodology, chained rings of an Olympic symbol are designed, partitioned, and printed by a delta-type 3D printer, which is cheaper but can move quick vertically. The rings were well designed and printed rings look well. Although there are still several unsolved problems including difficulty in deciding part partition points and weakness in the partition points, this methodology will probably enable new applications of 3D printing, such as 3D calligraphy.

研究テーマ紹介: 3D 造形技術

キーワード:

2014-07-07

Self-organized 3D-printing Patterns Simulated by Cellular Automata

Kanada, Y., 20th International Workshop on Cellular Automata and Discrete Complex Systems (Automata 2014), July 2014.
[ English page ]
[ 論文 PDF ファイル ]
[ 論文 PDF ファイル (拡張版, IWNC8 用原稿) ]
[ スライド (減量版) ]
[ スライド (動画つき, Keynote) ]


Abstract: 3D printers are usually used for printing objects designed
by 3D CAD exactly, i.e., deterministically. However, 3D printing process
contains stochastic self-organization process that generate emergent
patterns. A method for generating fully self-organized patterns using a
fused deposition modeling (FDM) 3D printer has been developed. Melted
plastic filament is extruded constantly in this method; however, by using
this method, various patterns, such as stripes, splitting and/or merging
patterns, and meshes can be generated. A cellular-automata-based
computational model that can simulate such patterns have also been
developed.



研究テーマ紹介:
3D 造形技術

キーワード:

2014-07-05

Providing Infrastructure Functions for Virtual Networks by Applying Node Plug-in Architecture

Kanada, Y., International Workshop on Software Defined Networks for a New Generation of Applications and Services (SDN-NGAS 2014), August 2014.
[ English page ]
[ 論文 PDF ファイル 未出版 ]
[ スライド PDF ファイル 未出版 ]

Abstract – Although nodes in a network-virtualization infrastructure, which is called a virtualization node, usually contain a switch or a router with sophisticated and high-performance functions such as Ethernet switching, VLAN, and IP routing, most of such infrastructure functions cannot be reused as program components by slices. Accordingly, a method for providing such functions to slices on a virtualization node (VNode) infrastructure, by applying the previously proposed plug-in architecture, is proposed. This architecture defines two types of plug-ins, i.e., control plug-ins and data plug-ins, and interfaces for them. As for the proposed method, the switch or router in the VNode is regarded as a data plug-in, and a control plug-in that allocates and isolates the switch/router resources was developed. The data plug-in interface was customized to handle a data plug-in, i.e., a layer-3 switch in a VNode, and a control plug-in and the interfaces for providing layer-3/VLAN switch functions to slices were designed, implemented, and evaluated. The evaluation result shows that instead of specifying a routing/switching program or method, specifying only an additional 8 to 25 lines in a slice definition enables slice developers to use routing and switching functions.

研究テーマ紹介: ネットワーク仮想化

キーワード:

2014-06-28

Developing Revolutionary 3D Design and Printing Methods

Kanada, Y., BIT’s 1st Annual International Congress of 3D Printing, Dalian, China, June 27-29, 2014.
[ English page ]
[ 動画なしのスライド (PDF), (旧版) ]
[ 動画つきのスライド (Keynote 用, 65 MB) (旧版) ]


Abstract – Conventional 3D design methods design only the surface of 3D objects and conventional 3D
printing methods only slice and print 3D objects horizontally. We in Dasyn.com develop new 3D
design methods that enable designing real 3D objects including the internal structures and
textures, and develop new 3D printing methods that enable printing patterns with nonhorizontal
directions. The “real 3D design method” makes transparent objects and objects with
holes much more realistic, and the non-horizontal 3D printing method enables naturallydirected
objects such as 3D calligraphies. We also develops a naturally randomized or fluctuated
3D printing method. We seek partners who will develop applications of these methods.



研究テーマ紹介:
ネットワーク仮想化

キーワード:

2014-06-16

High-level Portable Programming Language for Optimized Memory Use of Network Processors

Yasusi Kanada, ACM SIGPLAN Workshop on Memory Systems Performance and Correctness (MSPC 2014), poster, June 2014.
[ English page ]

[ Poster ]

研究テーマ紹介: Network virtualization

キーワード:

2014-05-17

Controlling Network Processors by using Packet-processing Cores

Kanada, Y., 2nd International Workshop on Network Management and Monitoring (NetMM 2014), May 2014.
[ English page ]
[ 論文 PDF ファイル ]
[ スライド PDF ファイル ]

Abstract – A network processor (NP) usually contains multiple packet processing cores (PPCs) and a control processing core (CPC), and the synchronization and communication between CPC and PPCs, which is required for controlling an NP, is very complex. To reduce the complexity, a method for controlling packet processing in NPs by using PPCs is proposed. By means of this method, complex control messages are partially processed and divided into simplified control packets by a CPU outside the NP chip, and these packets are sent to a control-processing PPC. The control-processing PPC controls data-processing PPCs by using data-exchange mechanisms, such as a shared memory or an on-chip network, which are more uniform and simpler than those between a CPC and PPCs. This control method is applied to a virtual-link controlprocessing task and packet-processing tasks in a network node with a virtualization function. Both tasks are described by a hardware-independent high-level language called “Phonpl,” and communication between the PPCs is programmed following normal and uniform shared-memory semantics. As a result, programming the control-processing task and porting the program become much easier.

研究テーマ紹介: ネットワーク仮想化

キーワード: Network processors, Multi core, Control processing, Packet processing, Network virtualization

2014-05-13

A Method for Evolving Networks by Introducing New Virtual Node/link Types using Node Plug-ins

Kanada, Y., 1st IEEE/IFIP International Workshop on SDN Management and Orchestration (SDNMO 2014), May 2014.
[ English page ]
[ 論文 PDF ファイル ]
[ スライド ]

Abstract – Network virtualization introduces two concepts: slice (i.e., virtual network), which consists of virtual nodes and links, and slice developer, which is the third role in networks. Slice developers can introduce new network services by using slices. A method for introducing new types of virtual nodes and links for new services into the slicedefinition language and the virtualization infrastructure by evolving physical nodes (i.e., “virtualization nodes” or VNodes) is proposed. This evolution consists of two stages: the experimental stage and the operational stage. In the experimental stage, data and control plug-ins are developed and tested by the operator or vendor by using experimental sliver definitions. In the operational stage, which is focused on in this study, the plug-ins are integrated into original components in the infrastructure and are available for slice development by using normal sliver definitions. By mapping type names to plug-in identifiers and parameters, the proposed method enables abstract and simple definitions of slices by slice developers and authorization of plug-ins by the operator, but it remains the loose integration of the new function, i.e., the plug-in architecture used in the experimental stage. Prototyping and evaluation demonstrates that this method greatly simplifies both slice developers’ tasks and operators’ tasks.

研究テーマ紹介: ネットワーク仮想化

キーワード: Slice developer, Network-node evolution, Node plug-in architecture, Data plug-in, Control plug-in, Network virtualization, Virtualization node, VNode infrastructure, Virtual-link type creation, Deep programmability.

2014-02-21

FDM 3D-printing as Asynchronous Cellular Automata

Kanada, Y., 8th International Workshop on Natural Computing (IWNC8), 2014-3.
[ English page ]
[ スライド ]

Abstract: Fused deposition modeling (FDM) is a 3D-printing method that shapes 3D objects by layering melted plastic filament. The process of this type of 3D printing can be regarded as asynchronous cellular-automata because it generates 1D on-off pattern per a head motion. Especially, by a constant head-motion at reduced constant extrusion-velocity, a 3D printer can generate self-organized grids or similar structures, which is much finer than artificial (i.e., program-controlled) patterns. Depending on the parameter values, i.e., layer depth, extrusion velocity, and so on, the generated pattern varies among regular stripes, stripes with crossing waves, and splitting and merging patterns. Some of the patterns can be simulated by a computational model, i.e., asynchronous cellular automata.

研究テーマ紹介: 3D 造形技術

キーワード:

2014-01-22

3D Printing and Simulation of Naturally-Randomized Cellular-Automata

Kanada, Y., 19th International Symposium on Artificial Life and Robotics (AROB 2014), 2014-1.
[ English page ]
[ 論文 (発表後改訂) ]
[ スライド ]

RIMG2281.jpg要旨: 3D printing technology usually aims reproducing objects deterministically designed by 3D CAD tools. However, 3D printing can generate patterns similar to randomized (non-deterministic) 1D or 2D cellular automata (CA). Cheap fused deposition modeling (FDM) 3D printers can be used for this purpose. By using an FDM 3D printer, melted plastic filament is extruded by a hot nozzle to shape a 3D object. They can generate CA-like patterns with constant head motion and constant filament extrusion and with unintended fluctuation but no explicit randomness. Because of fluctuation, every time the printer generates a different emergent pattern. This paper proposes a method for printing seaweed-like patterns of 1D and 2D CA using FDM, and computational CA models. This method will open a new horizon of 3D printing applications.

研究テーマ紹介: 3D 造形技術

キーワード: 3D 印刷, 3 次元印刷, 非同期セル・オートマトン, ランダム, ゆらぎ, Solid Free-form Fabrication, SFF, Fused deposition modeling, FDM

2013-11-13

A Node Plug-in Architecture for Evolving Network Virtualization Nodes

Kanada, Y., 2013 Workshop on
Software Defined Networks for Future Networks and Services (SDN4FNS 2013)
, 2013-11.
[ English page ]
[ 論文 PDF file ]
[ スライド ]

要約: Virtualization nodes, i.e., physical nodes with network virtualization functions, contain computational and networking components. Virtualization nodes called “VNodes” enabled mutually independent evolution of computational component called programmer and networking component called redirector. However, no methodology for this evolution has been available. Accordingly, a method for evolving programmer and redirector and developing new types of virtualized networking and/or computational functions in two steps is proposed. The first step is to develop a new function without updating the original VNode, which continues services to existing slices, using a proposed plug-in architecture. This architecture defines predefined interfaces called open VNode plug-in interfaces (OVPIs), which connect a data and a control plug-ins to a VNode. The second step is to merge the completed plug-ins into the original programmer or redirector. A prototype implementation of the above plug-in architecture was developed, tested, and evaluated. The prototype extends the redirector by adding new types of virtual links and new types of network accommodation. Estimated throughputs of a VLAN-based network accommodation and a VLAN-based virtual link using network processors are close to a wire rate of 10 Gbps.

研究テーマ紹介: ネットワーク仮想化

キーワード: Network-node plug-in architecture, Data plugin, Control plug-in, Network virtualization, Virtualization node, VNode, Virtual link, Network processors

2013-11-06

Maker Faire Tokyo 2013 のフライヤー等

Dasyn.com, Maker Faire Tokyo 2013, 2013/11/3-4.
[ 主フライヤー ]
[ 自然な方向によるオリンピック・マーク ]
[ ゆらぎ印刷 ]
[ ペンローズの 3 角形 ]
[ 中空ピラミッド ]
[ 中空多面体 ]
[ ポスター ]

Maker Faire Tokyo 2013 に Dasyn.com の名のもとに実演した 2 つの 3D 印刷について書いたフライヤーと,「自然な方向の印刷」,「ゆらぎ印刷」 など,個々のテーマに関するかんたんな説明を収録した.

キーワード:

2013-09-09

A VNode Plug-in Architecture to Evolve VNode

Kanada, Y., and Tarui, T., Network Virtualization Symposium 2013, September 2013.
[ English page ]

Summary: VNode enabled mutually independent evolution of programmers and redirectors. In this presentation, a method for evolving VNodes and developing new species of virtual links by using both control and data plug-ins and a publicly available testbed is proposed.

Introduction to this research theme: 3D shape formation technologies

キーワード:

2013-08-06

A Method of 3D Printing which is Consistent with Natural Direction in Shape

Kanada, Y., International SFF Symposium 2013, 2013-8.
[ English page ]
[ ポスターの内容 + 説明 (英語) ]
[ 改訂したポスターの PDF ファイル ]
[ ポスターの写真 ]

IMG_3034_edited-1.jpgAbstract: Usually, objects are horizontally sliced when printed by 3D printers. Therefore, if an object to be printed, such as a collection of fibers, originally have natural direction in shape, the printed direction contradicts with the natural direction. By using proper tools, such as field-oriented 3D paint software, field-oriented solid modelers, field-based slicing algorithms, and non-horizontal FDM 3D printers, the natural direction can be modeled and objects can be printed in a direction that is consistent with the natural direction. This consistence results in embodiment of momentum or force in expressions of the printed object. To achieve this goal, several manufacturing problems, but not all, have been solved. An application of this method is (Japanese) 3D calligraphy.

研究テーマ紹介: 3D 造形技術

キーワード: 3D 印刷, 3 次元印刷, Solid Free-form Fabrication, SFF, Fused deposition modeling, FDM, Additive Manufacturing, 付加加工

2013-07-19

ネットワーク・プロセッサのためのオープンで高級で移植可能なプログラミング環境

金田 泰, 電子情報通信学会 第 7 回 ネットワーク仮想化時限研究会, 2013-7.
[ English page ]
[ Paper PDF file ]
[ Slides ]

Abstract: ネットワーク・プロセッサは高性能でプログラマブルなネットワークのためにひろく使用されている. しかし,ネットワーク・プロセッサのプログラムは移植性と開発者数がかぎられ,開発コストが高い. この問題を解決するためにオープンで高級かつ移植性のあるプログラミング言語 CSP とそのための開発環境 +Net を開発した. この環境においては,パケットの高速処理に必要な SRAM と DRAM のつかいわけをプログラマにできるだけ意識させずに高 いスループットがえられるようにした. ネットワーク・プロセッサ Cavium Octeon のためのプロトタイプを実装し,ネット ワーク仮想化基盤の一部を使用して評価した結果,かんたんなプログラムでワイヤレートにちかい 7.5 Gbps 以上の 性能をえた.

研究テーマ紹介: Network virtualization

キーワード: ネットワーク・プロセッサ,プログラマビリティ,移植性,SRAM,DRAM,Octeon,ネットワーク仮想化

2013-06-02

Federation-less-federation of Network-virtualization Platforms

Kanada, Y., Tarui, T., and Shiraishi, K., IFIP/IEEE International Symposium on
Integrated Network Management (IM 2013)
, 2013-5.
[ English page ]
[ 論文 PDF file ]
[ スライド ]

要約: A method for federating multiple network-virtualization platforms by creating and managing slices (virtual networks) is proposed. A cross-domain slice can be created, deleted, or modified by sending a slice specification to the domain controller (network manager) of one domain. The specification is then propagated to other domains. Two chal­lenges were addressed while this method was developed. The first challenge is to enable federation among multiple domains that do not support federation functions by only adding a few components without modification of the existing network-virtualization-platform architecture. A domain-dependent specification of a slice, containing a pseudo virtual node that encloses a part of the slice specification in the other domains, is used, and this part is handled by a proxy node that represents another domain and a control component that implements a federation API to create a cross-domain slice. The second challenge is to enable manageable non-IP (arbitrary-format) data communication on a cross-domain slice. For an inter-domain communication, underlay VLAN parameters including MAC addresses are negotiated in advance and data packets on a slice are tunneled between gateways in these domains. The proposed federation method was implemented on two network-virtualization platforms, federation between two homogeneous domains was successfully demonstrated, federation perfor­mance was measured, and several issues on functional restrictions and implementation difficulty were found.

研究テーマ紹介: ネットワーク仮想化

キーワード:

2013-01-01

Network-resource Isolation for Virtualization Nodes

Kanada, Y., Shiraishi, K., and Nakao, A., IEICE Trans. Commun., Vol. E96-B, No. 1, pp. 20-30, 2013.
[ English page ]
[ 論文 PDF file ]

要約: One key requirement for achieving network virtualization is resource isolation among slices (virtual networks), that is, to avoid interferences between slices of resources. This paper proposes two methods, per-slice shaping and per-link policing for network-resource isolation (NRI) in terms of bandwidth and delay. These methods use traffic shaping and traffic policing, which are widely-used traffic control methods for guaranteeing QoS. Per-slice shaping utilizes weighted fair queuing (WFQ) usually applied to a fine-grained flow such as a flow from a specific server application to a user. Since the WFQ for fine-grained flows requires many queues, it may not scale to a large number of slices with a large number of virtual nodes. Considering that the purpose of NRI is not thoroughly guaranteeing QoS but avoiding interferences between slices, we believe per-slice (not per virtual link) shaping satisfies our objective. In contrast, per-link policing uses traffic policing per virtual link. It requires less resource and achieves less-strict but more-scalable isolation between hundreds of slices (500 to 700 slices in estimation). Our results show that both methods perform NRI well but the performance of the former is better in terms of delay. Accordingly, per-slice shaping (with/without policing) is effective for delay-sensitive services while per-link policing may be sufficiently used for the other types of services.

研究テーマ紹介: ネットワーク仮想化

キーワード: Resource isolation, Network virtualization, Virtual network, Per-slice shaping, Per-link policing, Weighted fair queuing, WFQ.

2012-11-27

Network-virtualization Nodes that Support Mutually Independent Development and Evolution of Node Components

Kanada, Y., Shiraishi, K., and Nakao, A., 13th IEEE International Conference on Communication Systems (ICCS 2012), 2012-11-23.
[ English page ]
[ 論文 PDF file ]
[ スライド PDF file ]

要約: “Virtualization nodes” (VNodes) for programma­ble network-virtualization platforms are being developed. Criteria for “clean” network-virtualization are devised and applied to this platform and slices (virtual networks). These criteria meet one of the challenges targeted by the Virtualization Node Project, that is, to enable mutually independent development and evolution of compo­nents (namely, computational compo­nents called programmers and networking compo­nents called redirectors) in VNodes. To meet this challenge, the redirector plays the central role in implementing the following two functions of VNodes. The first function is creation of mapping between virtual links to external physical paths and mapping between virtual links to internal physical paths, which makes it possible to hide various alterna­tive computa­tional components in the VNode from the external network and to hide these external-network representa­tions from the internal compo­nents. The second function is imple­mentation of high-performance data conversion, which connects the exter­nal and internal data formats or mappings, by using an add-on card with a network processor. Two results are obtained from the performance evaluation of these functions. First, the overhead caused by mapping creation can be hidden by other tasks under normal conditions, but the overhead caused by mapping deletion must be reduced. Second, the data-conversion rate is half the wire rate, which should be increased in future work.

研究テーマ紹介: ネットワーク仮想化

キーワード: Clean network virtualization, Virtualization node, VNode, Modularity, Model-mapping separation, Packet data conversion

2012-10-17

High-performance Network Accommodation and Intra-slice Switching Using a Type of Virtualization Node

Kanada, Y., Shiraishi, K., and Nakao, N., IARIA Infocomp 2012, 2012-10-24.
[ English page ]
[ 論文 PDF file ]
[ ThinkMind 論文ページ ]
[ スライド PDF file ]

要約: The architecture for programmable networkvirtualization platforms, i.e., the VNode architecture, has been developed in a project called the Virtualization Node Project. This paper introduces a type of physical node called Network ACcommodation Equipment (NACE) to the VNode architecture. NACE has dual roles in this architecture. The first role is as a network-slice gateway between an external network (Ethernet/VLAN) and a slice (virtual network). NACE can accommodate a data center or another testbed in a slice with high-performance (up to 10 Gbps) data-format conversion. The second role is as a special type of virtualization node that implements intra-slice virtual switch by using Ethernet hardware, which can replace software-based switching using a VM or a network processor. These roles are modeled as a node sliver (virtual node) with a gateway function and a node sliver with a switching function (i.e., a switch node-sliver), and these node slivers are specified by using XML. These functions were evaluated by using two testbeds, and the evaluation results confirm that both functions work correctly and perform well in terms of delay and packet loss.

研究テーマ紹介: ネットワーク仮想化

キーワード: network virtualization; virtual network; network accommodation; network-slice gateway; virtual switch; intraslice switching

ネットワーク仮想化基盤における仮想ノード間とスライス-外部ネットワーク間の接続機能

金田 泰,白石 圭,中尾 彰宏,電子情報通信学会 ネットワーク仮想化時限研究会, 2012-10-11.
[ English page ]
[ 論文 PDF file ]

要約: 複数の仮想化ノード(VNode) によって構成されるネットワーク仮想化基盤においては,多数のスライス (仮想ネットワーク) を同時に,他のスライスから隔離された状態で動作させることができる. スライスがふくむ仮想ノード (ノードスリバー) どうしは仮想リンク (リンクスリバー) によって自由に最高 10 Gbps で接続でき,そのなかでは Ethernet や IP にしばられない任意のプロトコルが使用できる. VNode においては,GRE トンネルを使用して仮想リンクを IP ネットワーク上に実装している. また,ネットワーク収容装置 (NACE, NC) を使用してパケット・データ・フォーマットを外部ネットワーク用に変換することにより, スライスを外部の VLAN ネットワークに最高 10 Gbps で接続できる. この論文では,スライス開発者からこれらの接続がどのように参照・定義され, またそれがどのように変換され物理的な通信が実現されるかをを記述する.

研究テーマ紹介: ネットワーク仮想化

キーワード: ネットワーク仮想化基盤,仮想化ノード,VNode,スライス,仮想ネットワーク,ノードスリバー,リンクスリバー,ネットワーク収容

2012-07-06

Network-resource Isolation for Virtualization Nodes

Kanada, Y., Shiraishi, K., and Nakao, A., 17th IEEE Symposium on Computers and Communication (ISCC 2012), 2012-7-4.
[ English page ]
[ 論文 PDF file ]
[ スライド PDF file ]
[ IEEExplore 論文ページ ]

要約: One key requirement for achieving network virtualization is resource isolation among slices (virtual networks), that is, to avoid interferences between slices of resources. This paper proposes two methods, per-slice shaping and per-link policing for network-resource isolation (NRI) in terms of bandwidth and delay. These methods use traffic shaping and traffic policing, which are widely-used traffic control methods for guaranteeing QoS. Per-slice shaping utilizes weighted fair queuing (WFQ) usually applied to a finegrained flow such as a flow from a specific server application to a user. Since the WFQ for fine-grained flows requires many queues, it may not scale to a large number of slices with a large number of virtual nodes. Considering that the purpose of NRI is not thoroughly guaranteeing QoS but avoiding interferences between slices, we believe per-slice shaping suffices our objective. In contrast, per-link policing uses traffic policing per virtual link. It requires less resource and achieves less strict isolation between hundreds of slices. Our results show that both methods perform NRI well but the performance of the former is better in terms of delay. Accordingly, per-slice shaping is effective for delay-sensitive services while per-link policing may be sufficiently used for the other types of services.

研究テーマ紹介: ネットワーク仮想化

キーワード:

2012-03-06

Development of A Scalable Non-IP/Non-Ethernet Protocol With Learning-based Forwarding Method

Kanada, Y. and Nakao, A., World Telecommunication Congress 2012 (WTC 2012), 2012-3-5.

[ English page ]
[ 論文 PDF ファイル ]
[ IEEExplore 論文ページ ]

要約: We have developed an experimental non-IP/non-Ethernet protocol called IPEC (IP Ether Chimera). IPEC switches learn IPEC addresses that are structured hierarchically, similar to IP addresses, using an algorithm that extends the learning algorithm of Ethernet switches. IPEC is a simple non-IP network-layer protocol that has features of both Ethernet and IP. Unlike IP, IPEC introduces an address group to manage multiple terminals as a group to make learning of mobile terminals more scalable and more efficient than Ethernet. Because an address group is the unit of learning in IPEC, it is more scalable than Ethernet, and mobile groups can be learned more efficiently. In addition, IPEC tolerates loops in a network as long as a limited number of duplicate packets are allowed, and thus, enable an alternative route against link failures. We have implemented IPEC both on an IPEC-capable switches using LAN cards and on a virtual network using virtualization nodes (VNodes), which have been developed to experiment with non-IP protocols such as IPEC. We show evaluations that the group learning function of IPEC is viable especially for multiple terminals moving together concurrently.

研究テーマ紹介: ネットワーク仮想化

キーワード: ネットワーク仮想化

2012-03-02

「クリーンな仮想化」 と要素独立進化型の 仮想化ノード・アーキテクチャ

金田 泰, 中尾 彰宏, 電子情報通信学会 ネットワーク仮想化時限研究会 第 3 回, 2012-3-2.

[ English page ]
[ スライド PDF ファイル]

(論文はありません)

要約: 共同研究プロジェクトにおいて仮想化ノード (VNode) およびそれによって構成されるネットワーク仮想化基盤を開発し,発展させている. VNode の特徴として 「要素独立進化型アーキテクチャ」 がある. すなわち,VNode においては,その構成要素 (プログラマ,リダイレクタ) が独立に進化できるアーキテクチャを実現している. この発表においては 「クリーンな仮想化」 という概念を提案し,VNode が この概念をほぼ実現していること,要素独立進化型アーキテクチャを実現するうえでこの概念が重要であることをしめす. また,VNode とくにその一部であるリダイレクタにおける要素独立進化型アーキテクチャと 「クリーンな仮想化」実現のしくみをしめす.

研究テーマ紹介: ネットワーク仮想化

キーワード: ネットワーク仮想化

2012-01-21

Network-resource Isolation for Virtualization Nodes

Kanada, Y., Shiraishi, K., and Nakao, A., COMSNETS 2012, 2012-1-6.
[ English page ]
[ 論文 PDF file ]
[ ポスター PDF file ]

[ IEEExplore論文ページ ]

要約: In network virtualization [Nak 10a], it is important to avoid resource interference, e.g., concerning communication bandwidth and delay, so that a single slice (virtual network) may not disrupt the whole infrastructure. To avoid this type of interference, a method for network-resource isolation (NRI) must be developed. Two types of traffic-control mechanisms, i.e., traffic shaping and traffic policing, can be used for NRI. To more effectively implement NRI using these mechanisms, two methods are proposed in this study: the “per-slice shaping” using weighted fair queuing (WFQ) and the “per-link policing” (per-virtual-link policing).

研究テーマ紹介: ネットワーク仮想化


キーワード: ネットワーク仮想化

2011-11-11

フェデレーション機能をもたない仮想化基盤のフェデレーション

金田 泰, 垂井 俊明 電子情報通信学会 ネットワーク仮想化時限研究会 第 2 回, 2011-11-10.

[ English page ]
[ スライド PDF ファイル]

(論文はありません)

要約: NICT の仮想化ノード・プロジェクトにおいて開発してきた仮想化基盤と G-lambda, ProtoGENI などとのフェデレーションすなわち仮想化基盤間に またがるスライスの生成・管理の機構を NICT 委託研において共同開発している. フェデレーション機能をもっていないこの仮想化基盤を改造する ことなく,付加的な機構をつかってフェデレーションを実現する方法について発表する.

研究テーマ紹介: ネットワーク仮想化

キーワード: ネットワーク仮想化

2011-02-11

仮想ネットワーク・モデルにもとづく VM 広域ライブマイグレーションの設定法の開発

金田 泰, 垂井俊明, 情報処理学会論文誌, Vol. 52, No. 3, pp. 1-17, 2011.

[ English page ]
[ PDF 版論文へのいりぐち (IPSJ) ]

要旨: ネットワーク仮想化は,ひとつの物理的なネットワーク上で多様なサービスを相互に干渉せず実現し,かつ単純にプログラムしカスタマイズすることを可能にする. ネットワーク仮想化は,IP,VLAN,あるいは NAT を使用するなど,多様な機構によって実現できる. 我々はこれらの実現手段に依存しない統一的な仮想ネットワークのモデルをつくり,そのモデルによって記述した仮想ネットワークを基本的に変更せずに多様な実現手段のネットワーク上に展開可能にすることをめざしている. この論文では仮想ネットワークのモデルとその主要な部品を定義し,それによって広域ライブ・マイグレーションのための仮想ネットワークを記述し,さらにそれをネットワーク・パーティション (VLAN による VRF) とアドレス・マッピング (NAT) という 2 つの実現方法による仮想ネットワークに展開できることを示す. この方法を仮想ネットワーク設定プロトタイプを新規開発して評価した. その結果,アドレス範囲指定やルーティング・パラメタの指定は実現手段ごとに変更する必要があったが,モデル記述の主要部分は共通化できた.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: ネットワーク仮想化, 仮想ネットワーク

2011-01-28

A “Network-Paging” Based Method for Wide-Area Live-Migration of VMs

Kanada, Y., and Tarui, T., 25th International Conference on Information Networking (ICOIN 2011), 2011-1-28.

[ English page ]
[ 論文 PDF ファイル ]
[ IEEExplore 論文ページ ]

要約: In cloud-computing environments, migration of virtual machines (VMs) between data centers can solve many problems such as load balancing and power saving. One of the difficulties in wide-area migration, however, is the “address-warping” problem, in which the address of the VM warps from the source server to the destination server. This confuses or complicates the status of the WAN, and the LANs connected to the WAN. We propose two solutions to this problem. One is to switch an address-translation rule, and the other is to switch multiple virtual networks. The former is analogous to paging in memory virtualization, and the latter is analogous to segmentation. The “network-paging” based method is described and our evaluation results are shown. It took less than 100 ms in average to switch from the source to the destination server using this method.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: Network Virtualization, Virtual Network, ネットワーク仮想化, 仮想ネットワーク

2011-01-24

Address-Translation-Based Network Virtualization

Kanada, Y., and Tarui, T., 10th International Conference on Networks (ICN 2011), 2011-1-24.

[ English page ]
[ 論文 PDF ファイル (C) IARIA ]
[ ThinkMind Paper page ]

要約: Two network-virtualization architectures, namely, network segmentation and network paging, were investigated. They are analogical to two memory-virtualization architectures: segmentation and paging. Network paging, which is relatively new and is based on a type of network-address translation (NAT), is focused on. This architecture requires smaller packet size and has several more advantages over the conventional architecture (i.e., network segmentation). Intranet- and extranet- type communication methods based on this architecture are described. An address translators is placed at each edge router in the WAN and used to evaluate client-server communication under wide-area virtual-machine (VM) live migration as a case of extranet-type communication.

研究テーマ紹介: ネットワーク仮想化

キーワード: Network Virtualization, Segmentation, Paging, Network Address Translation, NAT, Extranet, Virtual Network, ネットワーク仮想化, 仮想ネットワーク

2010-12-17

仮想化ノードを使用した非 IP プロトコル開発法と経験

金田 泰, 中尾 彰宏, 電子情報通信学会インターネットアーキテクチャ (IA) 研究会, 2010-12-17.

[ English page ]
[ 論文 PDF ファイル (C) IEICE]

要約: 情報通信研究機構 (NICT) の仮想化ノード・プロジェクトは,ネットワーク仮想化技術を使用して自由なフレーム形式をもつ非 IP プロトコルを実装可能にした 10 Gbps 級の仮想化ノード (VNode) を開発している. VNode は研究開発用ネットワーク JGN2plus に導入され,開発者 (JGN2plus 使用者) のためのユーザビリティ向上が課題になっている. そこで我々は,課題解決のための第一歩として VNode を使用した実験用ネットワーク上で IPEC (IP-Ether-Chimera) という非 IP プロトコルを開発・実験してその手順や経験を記述し,そこからユーザビリティに関する問題やノウハウを抽出した. 課題として開発者によるケアレスミスの防止策の必要性,ノウハウとして Linux PC による小規模な実験を VNode を使用した広域網の実験にスケールアップすることによって開発を容易化できることがあげられる. 今回の実験には広帯域は必要でなかったが,今後 10 Gbps の帯域を活用した実験へのスケールアップも比較的容易に実現できるとかんがえられる.

研究テーマ紹介: ネットワーク仮想化

関連論文: 仮想化ノードを使用した実験用非 IP プロトコルの開発

関連するブログのページ:

キーワード: ネットワーク仮想化ノード, 非 IP プロトコル, アドレス学習

2010-09-04

仮想化ノードを使用した実験用非 IP プロトコルの開発

金田 泰, 中尾 彰宏, 電子情報通信学会情報ネットワーク (IN) 研究会, 2010-9-2.

[ English page ]
[ 論文 PDF ファイル (C) IEICE]

要約: 情報通信研究機構 (NICT) においてはネットワーク仮想化技術を使用して任意のフレーム形式をもつ非 IP プロトコルを実装可能にした 10 Gbps 級の仮想化ノード (VNode) を開発している. 我々はそれを利用して実験的な非 IP プロトコル IPEC (IP Ether Chimera) を開発した. IPEC においては IP アドレスのような階層化可能なアドレスを Ethernet スイッチの学習アルゴリズムを拡張したアルゴリズムによって学習する. IPEC はつぎのような特徴をもつ. 第 1 に Ethernet,IP それぞれの特徴的な機能の一部を 1 層の単純な非 IP プロトコルによって実現している. 第 2 に学習をグループ単位でおこなうため,Ethernet よりスケールするうえ,グループ単位の移動が効率的に学習できる. 第 3 にこのアルゴリズムはループをふくむネットワークでも使用でき,障害時にも代替経路で通信できる. グループ ID はロケータとしても使用できるため,ID/Locator 分離を拡張したアーキテクチャを実現しているとかんがえることができる. IPEC を VNode 上に実装して,グループ単位の学習や端末の移動に実際に対応できることを実験により確認した.

研究テーマ紹介: ネットワーク仮想化

関連論文: 仮想化ノードを使用した非 IP プロトコル開発法と経験

関連するブログのページ:

キーワード: ネットワーク仮想化ノード, 非 IP プロトコル, アドレス学習, ID/Locator 分離, モビリティ, VNode

2009-05-21

ユーザ・レベルの通信品質要求を満足させるネットワーク制御機構の開発

金田 泰, 電子情報通信学会情報ネットワーク (IN) 研究会, 2009-5-21.

[ English page ]
[ 論文 PDF ファイル (C) IEICE]

要約: ユーザが経験する通信の体感品質すなわち QoE に関する要求をユーザが入力し,その要求をネットワークにおいて満足させるための機構を提案する. QoE 要求は QoS にマップされ,アドミッション制御やネットワーク・ノードへの設定を通じて満足される. 要求のためにソフト・ステートのプロトコルを使用することによって,サービスの開始,延長,中止などを統一的にあつかうことができる. この機構の一部をプロトタイプにくみこみ, 階層化シェイパーつきのネットワーク・ノードを使用して動画ストリーミングに関する実験をおこなった結果,QoE 要求が満足されることを確認した.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: QoE 最適化, 体感品質, QoS 保証, 最低帯域保証, ソフト・ステート・プロトコル, 階層化シェイパー, 階層化シェーパー

2009-05-20

A Method of Admission Control Based on Both Resource Requests and Traffic Measurement and Its Dynamics Under On/Off Model Traffic

Kanada, Y., 5th Advanced International Conference on Telecommunications (AICT 2009), 2009-5-25. [新型インフルエンザのために発表はキャンセルされた.]

[ English page ]
[ 論文 PDF ファイル ]
[ IEEExplore 論文ページ ]

要約: A method of admission control based on both resource requests by applications and class-based traffic mea-surement results was developed. In this method, a wide range of admission-control policy can be realized by adjusting three parameters, , , and . A policy-server prototype using this method and simulated voice traffic was used in traffic measurements. The measurements results show that the proposed method improves bandwidth usage and decreases call-blocking ratio while incurring low measurement load. Interesting but possibly harmful dynamics (i.e., system behavior) were observed by the simulations using traffic generated by an on/off model. That is, this admission-control method may cause oscillation or long-term evolution that lasts for 100 to 150 minutes, and it may also cause bandwidth “overshooting”. The range of parameters with which such effects can be properly suppressed and the admission control correctly works was experimentally obtained.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: QoS, アドミッション制御, CAC, トラフィック計測, QoS 保証, DiffServ, Differentiated Services, ネットワーク・ダイナミクス

2009-04-20

資源要求とトラフィック計測結果の両方にもとづくアドミッション制御法と その On/Off モデルのもとでのダイナミクス

金田 泰, 電子情報通信学会ネットワークシステム (NS) 研究会, 2009-4-16.

[ English page ]
[ 論文 PDF ファイル (C) IEICE ]

要約: アプリケーションによる資源要求と NetFlow によってえられる DiffServ クラスごとのトラフィック計測結果の両方にもとづくアドミッション制御法を開発した. この方法を使用したポリシーサーバのプロトタイプを開発し,シミュレートされた音声トラフィックを使用して実験した. その結果,この方法を使用すればひくい計測負荷で帯域使用率をたかめることができ,呼損を減少させられることがわかった. On/off モデルを使用したシミュレーションの結果,興味ぶかいが害をなしうるダイナミクスが観察された. すなわち,このアドミッション制御法においてはパラメタの値によって発振や 100~150 分間にわたる変化,帯域のオーバーシュートなどの現象がおこることがわかった. これらの現象をおさえてアドミッション制御を適切に動作させられるおよそのパラメタ値の範囲をもとめることができた.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: CAC, アドミッション制御, トラフィック計測, QoS 保証, DiffServ, Differentiated Services, ネットワーク・ダイナミクス

2008-01-03

Policy-based End-to-End QoS Guarantee Using On-Path Signaling for Both QoS Request and Feedback

Kanada, Y., The International Conference on Information Networking 2008 (ICOIN 2008), I-1, January 2008.

[ English page ]
[ 論文 PDF ファイル ]
[ IEEExplore 論文ページ ]

要約: Real-time and multimedia applications require an end-to-end QoS guarantee, and various types of applications require various QoS conditions. A DiffServ network should guarantee different QoS conditions for different types of communications. In this paper, the effect of traffic control in a DiffServ core network is experimentally evaluated using bursty traffic generated by an MMPP (Markov-Modulated Poisson Process) model. The situation to be simulated is that there are hundreds of conversational video streams that are delay-sensitive and hundreds of streaming videos that are loss-sensitive. If there are bandwidth-sharing queues such as those follow WFQ (Weighted Fair Queuing) in the core no-des and the two types of video traffic are assigned to two of the queues, the requirements of both types of traffic can be satisfied in a better way (a more efficient way) by assigning a larger weight to the queue for the conversational video. In our experiment, the optimum ratio of the weights was ap-proximately 1.3 when the traffic rates were the same. The optimum weight shares depend on the nature of the traffic, especially the burstiness.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: QoS measurement,QoS guarantee,DiffServ,On-path signaling,QoS feedback

2007-11-30

Method of DiffServ-Based Bandwidth-Sharing among Delay-Sensitive Traffic and Loss-Sensitive Traffic in Backbones

Kanada, Y., 未出版 (2008-4).

[ English page ]
[ 論文 PDF ファイル ]

要約: Real-time and multimedia applications require an end-to-end QoS guarantee, and various types of applications require various QoS conditions. A DiffServ network should guarantee different QoS conditions for different types of communications. In this paper, the effect of traffic control in a DiffServ core network is experimentally evaluated using bursty traffic generated by an MMPP (Markov-Modulated Poisson Process) model. The situation to be simulated is that there are hundreds of conversational video streams that are delay-sensitive and hundreds of streaming videos that are loss-sensitive. If there are bandwidth-sharing queues such as those follow WFQ (Weighted Fair Queuing) in the core no-des and the two types of video traffic are assigned to two of the queues, the requirements of both types of traffic can be satisfied in a better way (a more efficient way) by assigning a larger weight to the queue for the conversational video. In our experiment, the optimum ratio of the weights was ap-proximately 1.3 when the traffic rates were the same. The optimum weight shares depend on the nature of the traffic, especially the burstiness.

キーワード: NGN, Next-generation backbone, QoS measurement, QoS guarantee, DiffServ, Bandwidth sharing, WFQ.

2007-09-11

パスにそったシグナリングにもとづく QoS 保証法の設計と試作

金田 泰, 電子情報通信学会 通信ソサイエティ大会, 2007-7.

[ English page ]
[ 論文 PDF ファイル ]

要約: NGN の目標とされている端点間 (end-to-end) QoS 保証を実現するコア網のためのスケーラブルな QoS 技術の開発をめざしている. 2006 年度は次世代バックボーンにおいて有効なポリシーベースのトラフィック制御法の発見を目標として,QoS 保証方式の開発,プロトタイプの開発と評価実験とをおこなった.

開発した方式においては,RSVP や NSLP にちかいプロトコルによって端末からつたえられる QoS 要求をコア網で集約してスケーラブルな端点間 QoS 保証を実現する. 上記のプロトタイプにおいてこの要求はポリシールーティングとアウトソース型のプロトコルによってポリシーサーバにつたえられ,ポリシーサーバが要求をもとにエッジノードにポリシングとマーキングの設定をおこなうとともに,トラフィック量を予測してコアノードのキューを制御する.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: NGN, 次世代バックボーン,QoS 保証, Diffserv, 帯域配分

2007-08-09

仮想の “音の部屋” によるコミュニケーション・メディア voiscape の主観評価

金田 泰, 電子情報通信学会 応用音響 (EA) 研究会, EA2007-42, 2007-8.

[ English page ]
[ 論文 PDF ファイル (投稿後改訂版) ]
[ 論文 PDF ファイル (草稿) ]

要約: voiscape は仮想音響空間内を自由に移動しながら会話できるコミュニケーション・メディアである. そのプロトタイプ VPIIQ (Voiscape Prototype 2 Q) を使用して,ネットワーク・ポリシーのちがいによる QoS のちがいがあたえる効果に関する主観評価を実施したところ,音源方向等をあてる位置判定実験において,予想とちがって QoS がひくいときのほうがやや正答率がたかかった. また,位置判定実験においては被験者が移動・回転の操作をしないときよりそれをしたときのほうが正答率がたかかったが,話者判定実験においては逆の結果がえられた.

研究テーマ紹介: voiscape

キーワード: IP 電話, 音声コミュニケーション, voiscape, 3次元オーディオ, 3D音響, 仮想音響空間, 体感品質評価, QoE 評価

2007-07-13

パスにそったシグナリングにもとづく端点間 QoS 保証法の開発と評価

金田 泰, 電子情報通信学会 コミュニケーションクオリティ (CQ) 研究会, 2007-7.

[ English page ]
[ 論文 PDF ファイル ]

要約: RSVP や NSLP にちかいプロトコルによって端末からつたえられる QoS 要求をコア網で集約してスケーラブルな QoS 保証を実現する方式を設計・ 試作した. 要求はポリシールーティングとアウトソース型のプロトコル によってポリシーサーバにつたえられる. ポリシーサーバが要求をもと にトラフィック量を予測してコアノードのキュー (WFQ) の帯域分割を 制御する. このコアノードの制御の効果を L3 スイッチ GS4000 に MMPP モデルにもとづくバースト性トラフィックをとおして評価した. その結果,大量の会話ビデオ・トラフィックとストリーミング・トラ フィックとがあるときに,WFQ における前者のウェイトを後者より たかめれば,しかるべき条件のもとでは両者ともに満足させられること がわかった.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: NGN, 次世代バックボーン,QoS 計測,QoS 保証, Diffserv, 帯域配分, WFQ

2005-11-06

Simulated Virtual Market Place By Using voiscape Communication Medium

Kanada, Y., 13th ACM International Conference on Multimedia, pp. 794-795, November 2005.

[ English page ]
[ 論文 PDF ファイル ] [ ポスター PDF ファイル ]

要約: We are developing a new voice communication medium called voiscape. Voiscape enables natural and seamless bi-directional voice communication by using sound to create a virtual sound room. In a sound room, people can feel others' direction and distance expressed by spatial sounds with reverberations, and they can move freely by using a map of the room. Voiscape enables multi-voice-conversations. In a virtual market place that will be realized by voiscape, people can not only buy goods or information but also enjoy talking with merchants and people there. In this demo, a voiscape prototype called VPII is used for realizing such an environment. Unfortunately, because prerecorded voices are used in this demo, the participants cannot talk with merchants. However, the participants can talk each other with small end-to-end latency (less than 200 ms) and will feel the atmosphere of the virtual market place. Prerecorded people and merchants talk each other in English, Japanese and Chinese in parallel and with crossovers, and participants can virtually walk among them and can selectively listen one voice or hear multiple voices at once.

研究テーマ紹介: voiscape

キーワード: voiscape, デモンストレーション, 仮想コミュニケーション空間, 仮想コミュニケーション場, 仮想マーケットプレース, 仮想マーケット・プレース, 仮想マーケットプレイス, 仮想マーケット・プレイス, 仮想空間, 仮想の場所, 仮想場, バーチャル空間, ヴァーチャル空間, バーチャル・スペース, ヴァーチャル・スペース, バーチャル・プレース, バーチャル・プレイス, バーチャルスペース, ヴァーチャルスペース, バーチャルプレース, バーチャルプレイス, 多声会話, 音声会話

2005-09-27

SIP/SIMPLE-based Conference Room Management Method for the Voice Communication Medium "voiscape"

Kanada, Y., Asia-Pacific Network Operations and Management Symposium 2005 (APNOMS 2005), September 2005.

[ English page ]
[ short paper PDF ファイル ] [ ポスター PDF ファイル ] [ 未出版 full paper PDF ファイル ]

要約: A method for conference-room management for an auditory-virtual-space-based voice-communication medium called voiscape and a voice-communication system prototype called VPII, which used this method, were developed. With this method, conference rooms (called sound rooms) are managed through SIP and SIMPLE (a presence-related event-notification mechanism). A user can not only obtain a room list and enter (select) or exit from a room, but can also create, modify, or delete rooms by SIMPLE messaging. Rooms, users, and objects are managed by their "soft state"; i.e., they are deleted when a time out occurs. Users are informed of room membership, presence of a user, e.g., location and direction in the room, and presence of an object in the room by SIMPLE messaging, i.e., by SUBSCRIBE, NOIFY, and PUBLISH requests. To reduce the messaging overhead, the partial notification mechanism of SIMPLE is used in VPII.

研究テーマ紹介: voiscape

キーワード: SIMPLE, SIP, Session Initiation Protocol, voiscape, 会議室管理, 音室管理

2005-06-24

仮想の "音の部屋" によるコミュニケーション・メディア voiscape のための音声 3D 化と残響の計算

金田 泰, 電子情報通信学会 応用音響 (EA) 研究会, 2005-6.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: 3D 音響技術によってつくられた仮想的な "音室" 内を移動して相手を選択しつつ 会話ができるコミュニケーション・メディア voiscape を開発している. Voiscape の第 2 のプロトタイプ VPII においては,FIR 法によって低遅延な HRTF フィルタ計算をおこなうとともに,移動可能な範囲としての音室を 音響計算上の部屋とみなし,その壁による初期反射をシミュレートした. この初期反射によって音の頭外定位と距離感の表現を可能にした. また,ユーザの移動を追跡し必要な補間処理をおこなった. これによって,話者識別が容易で,複数の会話コンテクストが共存することができ, また音室内の移動が自然でノイズがすくない音声コミュニケーション環境を実現した.

研究テーマ紹介: voiscape

キーワード: HRTF, 頭部伝達関数, voiscape, 初期反射, 残響, 仮想移動追跡, 距離感, 頭外定位, 仮想コミュニケーション空間, 仮想コミュニケーション場, 仮想空間, 仮想の場所, 仮想場, 音声会話, 立体音響, 3次元オーディオ, 三次元オーディオ, 3Dオーディオ, 3次元サウンド, 三次元サウンド, 3Dサウンド, 3D音響, 3次元音響, 三次元音響

2005-06-13

Multi-Context Voice Communication In A SIP/SIMPLE-Based Shared Virtual Sound Room With Early Reflections

Kanada, Y., 15th ACM International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV 2005), pp. 45-50, June 2005.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: An improved prototype of the "voiscape" voice communication medium has been developed and subjectively evaluated. Voiscape enables natural and seamless voice communication by using sound to create a virtual "sound room" in which people, who are repre-sented by different sounds, can move freely. It features low-delay motion-tracking spatial audio with simulated early reflections that produce out-of-head sound localization and sound distance expression. It also features virtual-location-based selective communication: a user can walk freely in the sound room using a map- and cursor-key-based user-interface and can select whom to talk to or which sound sources to listen to. A third feature is SIP-presence-event-notification (SIMPLE)-based sound room management: when users move, their locations and directions are distributed using SIP SUBSCRIBE/NOTIFY messages. The combination of these features creates a natural voice-communication space in which two or more parallel conversation contexts can coexist. Limited, subjective testing by around 200 people showed that this medium can be used for cocktail-party-like conversation; i.e., users could distinguish parallel conversations by paying attention to or by moving toward one of them.

研究テーマ紹介: voiscape

キーワード: SIMPLE, SIP, Session Initiation Protocol, voiscape, 会議室管理, 初期反射, 残響, 仮想移動追跡, 音室管理, 仮想コミュニケーション空間, 仮想コミュニケーション場, 音声会話, 多声会話, 立体音響, 3次元オーディオ, 三次元オーディオ, 3Dオーディオ, 3次元サウンド, 三次元サウンド, 3Dサウンド, 3D音響, 3次元音響, 三次元音響, 仮想空間, 仮想の場所, 仮想場, バーチャル空間, ヴァーチャル空間, バーチャル・スペース, ヴァーチャル・スペース, バーチャル・プレース, バーチャル・プレイス, バーチャルスペース, ヴァーチャルスペース, バーチャルプレース, バーチャルプレイス

2004-11-08

Multi-Context Voice Communication Controlled By Using An Auditory Virtual Space

Kanada, Y., 2nd IASTED International Conference on Communication and Computer Networks (CCN 2004), 2004-11.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: A new voice communication medium, which the author calls "voiscape", will probably appear in near future. Voiscape shall have much improved user interface than the conventional voice communication systems, i.e., telephone and conference systems, and be based on the IP-based conferencing and spatial audio technologies. The author has developed a prototype toward voiscape, which has made a step toward solving two problems of the conventional systems i.e., complicated and restricted conference control and lack of crossed-over multi-context support, by introducing two features. The first function is the virtual-location based communication; i.e., the users can talk with other users and move, in a way similar to face-to-face conversation, in a virtual auditory space created by spatial audio technology without explicit session and floor control. The second function is personalized policy-based communication control; i.e., the users can specify communication policies that protects their privacy and reduce required resources. This function is enabled by a distributed policy-arbitration mechanism. Experiments showed that the basic mechanisms and the policy-based control with a simple policy worked well.

研究テーマ紹介: voiscape

キーワード: voiscape, 会議室管理, 音室管理, 仮想コミュニケーション空間, 仮想コミュニケーション場, 仮想空間, 仮想の場所, 仮想場, バーチャル空間, ヴァーチャル空間, バーチャル・スペース, ヴァーチャル・スペース, バーチャル・プレース, バーチャル・プレイス, バーチャルスペース, ヴァーチャルスペース, バーチャルプレース, バーチャルプレイス, コミュニケーション・メディア, 音声コミュニケーション, 多声会話, 音声会話, 立体音響, 3次元オーディオ, 三次元オーディオ, 3Dオーディオ, 3次元サウンド, 三次元サウンド, 3Dサウンド, 3D音響, 3次元音響, 三次元音響, JMF, Java, Java 3D, Java Media Framework, Javaメディア・フレームワーク, Javaメディアフレームワーク

2004-03-05

仮想の "音の部屋" によるコミュニケーション・メディア voiscape の JMF と Java 3D を使用した実装

金田 泰, 情報処理学会 マルチメディア通信と分散処理研究会, 2004-3.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: 電話にかわるべき音声コミュニケーション・メディア voiscape の確立をめざし て研究をおこなっている. Voiscape においては 3 次元オーディオ技術によっ てつくられた仮想的な "音の部屋" を使用するが,音声通信と 3 次元音声にく わえて 3 次元グラフィクスを使用するプロトタイプを PC 上に開発した. この プロトタイプにおいては音声のキャプチャと通信のために JMF (Java Media Framework),3 次元音声 / グラフィクスのために Java 3D を使用した. 開発 前はこれらの API をつなげば必要な基本機能がほぼ実現できるとかんがえてい たが,実際にはこれらを直接つなぐことはできず,3 次元音声のためには Java 3D のインタフェースをとおして OpenAL を使用した. また,プロトタイプにお いては音質劣化や遅延などの問題を容易に解決することができなかったが,試行 をかさねてこれらの問題をほぼ解決した.

研究テーマ紹介: voiscape

キーワード: JMF, Java, Java 3D, Java Media Framework, Javaメディア・フレームワーク, Javaメディアフレームワーク, OpenAL, Open AL, voiscape, 公開論文, 音室, 3次元オーディオ, 3Dオーディオ, 3次元音響, 3D音響, 3次元サウンド, 3Dサウンド, 立体音響, 音声会話, 多声会話

2003-10-08

仮想の "音の部屋" によるコミュニケーション・メディア voiscape

金田 泰, 電子情報通信学会 マルチメディアと仮想環境研究会, 2003-10.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: 電話にかわるべきコミュニケーション・メディア voiscape の概念を提案する. Voiscape は,3 次元オーディオ技術による仮想的な "音の部屋" をユーザ間で共有し,そのなかを自由に移動してさまざまなひとと会ったり わかれたりしながら多者間のコミュニケーションがおこなえるウェアラブルな メディアである. プレゼンスや周縁的情報の伝達を可能にし,電話におけるような 1 対 1 の会話から従来のメディアではできなかったさまざまなかたちの コミュニケーションまでをカバーすることによって,つながり感・安心感の 共有や暗黙知の共有も実現されるだろう. この論文では voiscape の使用場面や 手順についてのべ,PC 上に開発した voiscape のプロトタイプについてものべる. プロトタイプ上ではユーザは前方の様子を 3 次元グラフィクスによって 確認しながらマウスをつかって部屋内を移動することができる.

研究テーマ紹介: voiscape

キーワード: voiscape, 立体音響, 3次元オーディオ, 三次元オーディオ, 3Dオーディオ, 3次元サウンド, 三次元サウンド, 3Dサウンド, 3D音響, 3次元音響, 三次元音響, コミュニケーション・メディア, 音声コミュニケーション, 多声会話, 音声会話, 仮想コミュニケーション空間, 仮想コミュニケーション場, 仮想空間, 仮想の場所, 仮想場, バーチャル空間, ヴァーチャル空間, バーチャル・スペース, ヴァーチャル・スペース, バーチャル・プレース, バーチャルスペース, ヴァーチャルスペース, バーチャルプレース

2003-10-06

仮想の "音の部屋" によるコミュニケーション・メディア voiscape におけるポリシーベース・セッション制御

金田 泰, 電子情報通信学会 インターネットアーキテクチャ (IA) 研究会, 2003-10.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: 電話にかわるべき音声コミュニケーション・メディアの確立をめざした研究の 一部として,多者間通信が可能な常時接続型コミュニケーショ ン・メディア voiscape のアーキテクチャとプロトタイプを開発した. Voiscape においては 3 次元オーディオ技術によってつくられた仮想的な "音の部屋" を使用する. ユーザがマウスをつかって音の部屋内を移動すると,プレゼンスサーバを介して 部屋内の位置などのプレゼンス情報が部屋内の他のユーザにつたえられる. 相手にちかづいたり相手からとおざかったりすると,あらかじめ端末において 定義されたポリシーにしたがって,SIP を使用して自動的に通信セッションの 開始・終了などの動作がとられる. このポリシーベース・セッション制御に よってプライバシー保護や通信量削減が可能になる. 接続開始を要求する際に 相手からも同時に接続開始を要求されることが頻繁におこりうるので,2 重に接続したり "話し中" になったりせずに接続が確立する方法を くふうしている.

研究テーマ紹介: voiscape

キーワード: voiscape, 音声会話, 音声コミュニケーション, 多声会話, 仮想プレゼンス情報, SIP, Session Initiation Protocol, ポリシーベース・セッション制御, プライバシー保護, 仮想コミュニケーション空間, 仮想コミュニケーション場, 仮想空間, 仮想の場所, 仮想場

2003-09-01

Rule-Based Building-Block Architecture for Policy-based Networking

Kanada, Y. and O'Keefe, B. J., Journal of Network and Systems Management, Vol. 11, No. 3, pp. 253-275, 2003.

[ English page ]
[ JNSM 掲載号 Web ページ ] [ 論文 PDF ファイル (草稿) ]

要約: We developed two rule-based building-block architectures, i.e., pipe-connection and label-connection architectures, for describing complex and structured policies, especially network QoS policies. The latter is focused on in this study. The relationships or connec-tions between building blocks are specified by the da-taflow and control flow between them. The dataflow is specified by tags, including virtual flow labels (VFLs), which are data attached to "outside packets". The con-trol flow can be classified and specified by four control structures: concatenation, parallel application, selection, and repetition. We have designed fine-grained and coarse-grained building blocks and methods for specify-ing dataflow and control flow in differentiated services (Diffserv), and implemented the coarse-grained ones in a policy server. Two cases of building-block use are de-scribed, and we concluded that there are five advantages of building-block-based policies, i.e., expressibility, uni-form semantics, simplicity, flexibility, and management-task-oriented design. We also developed techniques for transforming building-block policies into executable ones, which are called policy division and fusion.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: QoSポリシー, ポリシーベース・ネットワーキング, ポリシーベース・ネットワーク, ポリシーベース管理, 部品化ポリシー, ポリシー部品化, ポリシー結合, ポリシー分割, ポリシー融合, Diffservポリシー

2003-02-01

20 世紀の名著名論 Robert W. Floyd: Nondeterministic Algorithms

金田 泰, 情報処理, vol. 44, No. 2, 2003.

[ English page ]

キーワード: 非決定性アルゴリズム, 非決定的アルゴリズム

2002-06-05

Dynamically Extensible Policy Server and Agent

Kanada, Y., 3rd International Workshop on Policies for Distributed Systems and Networks (Policy 2002), pp. 236-239, June 2002.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]
[ IEEExplore 論文ページ ]

要約: This paper proposes a method, called the policy-extension-by-policy method, for quickly and dynamically adding policy classes with new functionality to policy servers and agents. In this method, users can add a new policy class to the policy server by using policy-definition (PD) policies, and they can define a method to translate a policy of the new class and to send to network nodes of different vendors through various types of device interfaces, such as CLI, MIBs, PIBs, APIs or hardware tables, by using policy-embedding (PE) policies. A PE policy also enables translating a policy of an existing class and sending the result to a new type of network node. PE policies contain command templates and methods for filling the templates. A program interpreter is embedded in policy agents to make flexible policy-to-configuration translation possible. A prototype system and example policies, i.e., access control, Diffserv, and VPN policies, were developed.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: ポリシーベース・ネットワーキング, ポリシーベース・ネットワーク, ポリシーベース管理, 拡張可能ポリシーシステム, 可拡張ポリシーシステム, 汎用ポリシーサーバ, PxP, DEPS

2002-05-14

A Method of Software-Hardware Integration for QoS Policy Combination in Gigabit Routers

Kanada, Y., and Yazaki, T., Communications Quality and Reliability 2002 (CQR 2002), pp. 12-16 2002.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: In policy-based networks, two or more policies often have to cooperate because combined and customized network functions must be controlled using policies. Two types of policy trans-formation, policy fusion and policy division, are sometimes required to implement cooperating policy systems on high-performance hardware routers. Policy fusion transforms two or more policies into one, and policy division transforms a policy into two or more policies. These transformations causes a problem that the original policies must usually be strongly constrained to allow these transformations. This paper shows a method for resolving restrictions on the division of QoS policies by a software-hardware integration, i.e., by implementing virtual flow labels (flow IDs) in hardware and by dividing a policy and deploying the policies onto two filter blocks. We have developed a policy agent (PEP) and a gigabit router integrated by using this method. Both high-performance and flexibility are achieved by this integration.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: QoSポリシー, QoS保証, サービス品質保証, ポリシーベース・ネットワーキング, ポリシーベース・ネットワーク, ポリシーベース管理, 部品化ポリシー, ポリシー部品化, ポリシー結合, ポリシー分割, ポリシー融合, ポリシー部品化, 仮想フローラベル

2002-03-27

IETF 標準化を中心としたポリシー管理技術の動向

金田 泰, 電子情報通信学会 2002 年総合大会,2002-3.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: (なし)

キーワード: IETF, チュートリアル, ポリシーベース管理

2002-03-01

ポリシーサーバ PolicyXpert における Diffserv ポリシーとそのくみあわせ

金田 泰, ブライアン・オキーフ, 電子情報通信学会 情報ネットワーク・ネットワークシステム (IN / NS) 合同研究会,2002-3.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: ネットワークのポリシー制御において,Diffserv のようなプログラムし カスタマイズすることが可能なネットワーク機能を表現するために, 複数のポリシーをくみあわせる必要が生じることがある. PolicyXpert というポリシーサーバにおいて,3 種類のポリシーと,ポリシーを接続するための 3 種類の仮想フローラベル (VFL) とを設計・実装した.ポリシーのくみあわせに よって複雑な Diffserv ポリシーが表現可能になる. また,ポリシーをくみあわせる ことにより,DSCP にもとづくサービスクラスのサブクラスの定義が可能になり, サービスポリシーと加入者ポリシーとの分離が可能になっている. しかも, Diffserv ポリシーを慎重に設計したため,単純な Diffserv ポリシーは単純な かたちであらわせるようになった.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: Diffservポリシー, QoSポリシー, ポリシーベース管理, ポリシーベース・ネットワーキング, ポリシーベース・ネットワーク, 部品化ポリシー, ポリシー部品化, ポリシー結合, 仮想フローラベル, 汎用ポリシーサーバ, ネットワーク・ポリシー

2001-09-26

Diffserv Policies and Their Combinations in OpenView/JP1 PolicyXpert

Kanada, Y. and O'Keefe, B. J., Asia-Pacific Network Operations and Management Symposium 2001 (APNOMS 2001), September 2001, (poster paper, presentation cancelled).

[ English page ]
[ 論文 PDF ファイル ] [ 未出版フルぺーパ PDF file ]

要約: Policies sometimes have to be combined and applied in cooperation to represent such programmable and customizable network functions as Diffserv. In the OpenView PolicyXpert and JP1/PolicyXpert policy servers, three types of policies and three types of virtual flow labels, to connect the policy rules, are defined for Diffserv. The combination of these policies allows the representation of complex Diffserv policies and the separation of service and subscriber policies. Diffserv policies and virtual flow labels make this possible. However, the careful design of Diffserv policies has enabled simple Diffserv policies to be represented in a simple form.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: Diffservポリシー, QoSポリシー, ポリシーベース管理, 部品化ポリシー, ポリシー部品化, ポリシー結合, 仮想フローラベル, 汎用ポリシーサーバ, ネットワーク・ポリシー

2001-05-14

Policy Division and Fusion: Examples and a Method - or, Multiple Classifiers Considered Harmful

Kanada, Y., 7th IFIP/IEEE International Symposium on Integrated Network Management (IM 2001), pp. 545-560, May 2001.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]
[ IEEExplore 論文ページ ]

要約: Because higher- and lower-level policies do not necessarily correspond one to one, a higher-level network policy may have to be translated into two or more lower-level policies, and two or more cooperating higher-level policies may have to be translated into one lower-level policy. The former transformation is called a policy division, and the latter transformation is called a policy fusion. These transformations can be performed mechanically under restricted conditions as described in this paper. However, in general, they are very complicated and the restrictions cannot be eliminated completely mainly because of existence of multiple packet classifiers in a set of policies. Thus, this paper concludes that they should not be introduced if it is possible. The policy division and fusion can be avoided in certain cases, but they will not probably be able to be avoided in general. If so, the problem should be solved or relaxed by removing harmful classifiers by introducing virtual flow labels and by further studies. In addition, we may have to find a better method to control network devices than policies in the current sense.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: ポリシーベース管理, ポリシー分割, ポリシー融合, ポリシー部品化, 部品化ポリシー, ポリシー結合, フロー・クラシファイア

2001-01-29

Taxonomy and Description of Policy Combination Methods

Kanada, Y., Workshop on Policies for Distributed Systems and Networks (Policy 2001), Lecture Notes in Computer Science, No. 1995, Springer, pp. 171-184, January 2001.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: To control complicated and decomposable networking functions, such as Diffserv, two or more policies must cooperate. Combining two or more mutually dependent policies for a specific purpose is called policy combination. Methods of passing information between combined policies can be classified into real tags and virtual tags, or labels and attributes. Policy combinations can be classified into concatenation, parallel application, selection, and repetition. Explicitly specifying policy combinations makes policy systems semantically clearer and better suited to general use, extends the range of functionality, and improves the possibility of optimization. If policy combinations can be specified in a policy system, two types of policy organizations can be distinguished: homogeneous and heterogeneous. Heterogeneous organization is more service-oriented and seems to meet service-management requirements, but homogeneous organization is more device-oriented and may provide better performance.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: ポリシーベース管理, ポリシー部品化, 部品化ポリシー, ポリシー結合

2000-10-20

ネットワークのポリシー制御のための 2 つの部品化アーキテクチャの比較

金田 泰, 電子情報通信学会 情報ネットワーク (IN) 研究会, 信学技法, 100-378, IN 2000-102, pp. 47-54, 2000-10.

[ English page ]
[ 論文 PDF ファイル ]

要約: ポリシーベース・ネットワークにおいては,高水準の機能あるいはポリシーを 実現するためにしばしば 2 個以上の低水準のポリシーをくみあわせる必要がある. このような部品化されたポリシーをサポートするために,複数のポリシーを モデル化するための 2 つのアーキテクチャを開発した. それらはパイプ結合 アーキテクチャとラベル結合アーキテクチャである. 規則ベースの部品が ポリシーベース・ネットワーク制御にとってすぐれていること,そして ラベル結合アーキテクチャが現在のところはよりよいことがわかった. しかし, また,ネットワーク環境においては非常に重要な並列性という点においては パイプ結合アーキテクチャのほうがすぐれていることがわかった.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: パイプ結合アーキテクチャ, ポリシー部品化, 部品化ポリシー, ポリシー結合, ラベル結合アーキテクチャ, ポリシーベース管理

2000-10-16

Two Rule-based Building-block Architectures for Policy-based Network Control

Kanada, Y., 2nd International Working Conference on Active Networks (IWAN 2000), Lecture Notes in Computer Science, No. 1942, pp. 195-210, Springer, October 2000.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: Policy-based networks can be customized by users by injecting programs called policies into the network nodes. So if general-purpose functions can be specified in a policy-based network, the network can be regarded as an active network in the wider sense. In a policy-based network, two or more policies must often cooperate to provide a high-level function or policy. To support such building-block policies, two architectures for modeling a set of policies have been developed: pipe-connection architecture and label-connection architecture. It is shown that rule-based building blocks are better for policy-based network control and that the label-connection architecture is currently better. However, the pipe-connection architecture is better in regards to parallelism, which is very important in network environments.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: パイプ結合アーキテクチャ, ポリシー部品化, 部品化ポリシー, ポリシー結合, ラベル結合アーキテクチャ, ポリシーベース管理

2000-06-05

A Representation of Network Node QoS Control Policies Using Rule-based Building Blocks

Kanada, Y., International Workshop on Quality of Service 2000 (IWQoS 2000), pp. 161-163, June 2000.

[ English page ]
[ 論文 PDF ファイル ] [ OHP PDF ファイル ]

要約: Network node functions, such as QoS or the security functions of routers, are becoming increasingly complex, so programs, not only configuration parameters, are required to control network nodes. In a policy-based network, a policy is defined at a policy server as a set of rules that deployed at network nodes where it must be translated into an executable program or parameters. Thus, a policy must be represented by a form in which the syntax and semantics are clearly defined, and which can be mechanically translated into an executable program. This is possible if the policy is written in an appropriate rule-based programming language. This paper describes such a language in which functions required for DiffServ can be specified for the interface between a policy server and network nodes. In this language, a policy rule can be composed using predefined primitive building blocks and control structures.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: ポリシーベース管理, ポリシー部品化, 部品化ポリシー, ポリシー結合, QoSポリシー, ネットワーク・ポリシー

2000-02-01

Rule-based Modular Representation of QoS Policies

金田 泰, 電子情報通信学会 ネットワーキング・アーキテクチャ・ワークショップ 10 周年記念大会, pp. 106-113, IEICE, 2000.

[ English page ]
[ 論文 PDF ファイル ] [ 日本語版 OHP PDF ファイル ] [ 英語版 OHP PDF ファイル ]

要約: To realize internet-protocol-based QoS-assured networks, using differentiated services under policy-based networking is a promising approach. A QoS policy server must work in multi-vendor environment. To use standard protocol, such as COPS or SNMP, between the policy server and routers is not sufficient, but also to define and to standardize high-level syntax and semantics, i.e., a language, is required for interoperability. This paper describes the outline of a rule-based language for this purpose. Policy rules can be defined in the policy server and can be deployed to routers or router proxies using this language through an appropriate protocol such as COPS, SNMP, or IIOP. The language consists of several types of rules, i.e., matching, policing (or metering), marking, discarding, and scheduling types, and linkage labels that connects rules. A MIB and/or PIB that simulates the language is also explained in this paper. The language will be implemented in near future.

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: ポリシーベース管理, ポリシーベース・ネットワーク管理, QoSポリシー, COPS, Common Open Policy System

1999-11-07

SNMP-based QoS Programming Interface MIB for Routers

Kanada, Y., Ikezawa, M., Miyake, S., and Atarashi, Y., draft-kanada-diffserv-qospifmib-00.txt, Internet Draft, November 1999.

[ English page ]
[ Local textual version ]
[ Slides used in 46th IETF: Configuration Management BOF, Diffserv WG, and RAP WG (not recommended) ]

要約: This document describes a QoS PIF MIB (Quality-of-Service Programming-Interface Management-Information-Base) to be used as an SNMP-based programming interface for routers. This MIB is intended to be a programming interface for router QoS functions, especially DiffServ-related [RFC2475] functions including packet scheduling (queuing), dropping, and metering that must be modular and concisely described. Traffic-conditioning rules and metering rules for DiffServ-related functions are defined modularly by using "virtual flow labels" and exclusive conditions in rules, and new classifications for packet-scheduling and packet-dropping functions are introduced. This document focuses on satisfying the requirements on programming interfaces or programming languages for router control. Thus, the focus is different from that of DiffServ MIB [DSMIB] or QoS PIB [QoSPIB].

研究テーマ紹介: ポリシーにもとづくネットワーキング

キーワード: IETF, Management Information Base, QoS MIB, インターネット・ドラフト, 仮想フローラベル, SNMP, Simple Network Management Protocol

1999-11-02

A Method of Geographical Name Extraction from Japanese Text for Thematic Geographical Search

Kanada, Y., 18th International Conference on Information and Knowledge Management (CIKM'99), pp. 46-54, November 1999.

[ English page ]
[ 論文 PDF ファイル (ACM DL)] [ 論文 PDF ファイル ]

要約: A text retrieval method called the thematic geographical search method has been developed and applied to a Japanese encyclopedia called the World Encyclopedia. In this method, the user specifies a search theme using free words, then obtains a sorted list of excerpts and references to encyclopedia sentences that contain geographical names. Using this list, the user can open maps that indicate the location of the names. To generate an index of names for this searching, a method of geographical name extraction has been developed. In this method, geographical names are extracted, matched to names in a geographical name database, and identified. Geographical names, however, often have several types of ambiguities. Ambiguities are resolved using context analysis and several other techniques. As a result, the precision of extracted names is more than 96% on average. This method depends on features of the Japanese language, but the strategy and most of the techniques can be applied to texts in English or other languages.

研究テーマ紹介: 軸づけ検索 (テーマ検索)

キーワード: テキスト検索, 軸づけ検索, 軸付け検索, テーマ地図検索, テーマ地名検索, 地域軸検索, 百科事典検索, 地名情報抽出, 情報組織化, 検索結果組織化, 組織化検索, 整列, 検索結果構造化, 構造化検索

1999-09-28

Methods of Extracting Year References for Chronological-table-generating Text Searching

Kanada, Y., International Symposium on Digital Library 1999, pp. 135-142, 1999.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 PostScript ファイル ]

要約: A method of extracting year references for a textual information retrieval method called the thematic chronological-table search method is explained in this paper. This search method generates an index by extracting and collecting year references from a text collection. The resulting index and a full-text index are used for searching statements that contain year references and search words. The results are displayed in the form of a chronological table with hyperlinks to the original text. Seven forms of year or century references are extracted and normalized using string matching patterns. The extraction error rate is reduced by using both local and nonlocal contexts. If the lower two digits of a Gregorian year, which matches a form, occurs, it is normalized by supplementing the upper digits using the non-local context. This method has been applied to a Japanese encyclopedia. An evaluation shows the precision of extraction to be higher than 99% in most cases.

研究テーマ紹介: 軸づけ検索 (テーマ検索)

キーワード: テキスト検索, 軸づけ検索, 軸付け検索, テーマ年表検索, 年代軸検索, 時間軸検索, 百科事典検索, 年代情報抽出, 情報組織化, 検索結果組織化, 組織化検索, 整列, 検索結果構造化, 構造化検索

1999-09-01

「ネットで百科」 における 「テーマ地図検索」 の機能と実装法

金田 泰,山崎 幹夫,澤田 瑞穂,平野 義明,藤井 泰文, 情報処理学会第 59 回全国大会,3P-9, 1999, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 PostScript ファイル ]

要約: 会員制ネットワーク 「ネットで百科」 においては,地域を軸として百科事典 テキストの検索結果を整理して表示する 「テーマ地図検索」 のサービスを 実施している. この検索においては,テキストを文単位に検索し,その結果を 文中に出現する地名によってソートして表示する. また,その地名に関する 地図をひらくこともできる. ここではその機能と実現法の概要を説明する.

研究テーマ紹介: 軸づけ検索 (テーマ検索)

キーワード: テキスト検索, 軸づけ検索, 軸付け検索, 地域軸検索, テーマ地名検索, 百科事典検索, ネットで百科, テーマ地図検索

検索結果を地域で整理する百科事典テキスト検索のための地名情報抽出法

金田 泰, 情報処理学会 自然言語処理研究会報告 99-NL-132-2, 1999, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 PostScript ファイル ]

要約: 「テーマ地図検索」 というテキスト情報検索法を開発した. この検索法において は,ユーザは検索のテーマを自由語入力し,地名をふくむ文の抜粋とその文へのハ イパーリンクのソートされたリストをえることができる. このリストを使用して ユーザはその地名の位置をしめす地図をひらくこともできる. この検索のための 地名インデクスを生成するため,地名抽出法を開発した. この方法においては, 地名を抽出してデータベース中の地名とマッチングし同定する. 地名には数種類 のあいまいさがある. あいまいさは一種の文脈解析や他のいくつかの技法によっ て解決する. その結果,世界大百科事典においては 96% 以上の抽出精度を実現し た. 情報抽出のための規則は日本語の特徴に依存しているが,その戦略は他の言 語にも適用することができる.

研究テーマ紹介: 軸づけ検索 (テーマ検索)

キーワード: テキスト検索, 軸づけ検索, 軸付け検索, 地域軸検索, テーマ地図検索, テーマ地名検索, 地名情報抽出, 地名抽出, 百科事典検索, 情報組織化, 検索結果組織化, 組織化検索, 検索結果構造化, 構造化検索

1999-08-16

"Active Edge" 基本アーキテクチャの提案

生澤 満, 吉澤 聡, 三村 到, 金田 泰, 大槻 兼市, 電子情報通信学会 1999 年 通信ソサイエティ大会,SB-6-4, 1999, IEICE により出版.

キーワード:

1999-06-01

百科事典から動的に年表を生成するテキスト検索法のための年代情報の抽出法と表現法

金田 泰, 情報処理学会 情報学基礎研究会報告 99-FI-?, 1999, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 PostScript ファイル ]

要約: 「テーマ年表検索」 というテキスト情報検索法を開発した. この検索法において は,あらかじめ文書集合から年代参照を抽出して年代インデクスを生成し,ユーザ 入力があると年代インデクスと文単位の全文インデクスとから年代参照と入力され た語の出現場所をもとめて結果を年代順に組織化 (ソート) して表示する. 検索結 果は年代参照とそれをふくむ文,もとのテキストへのハイパーリンクをふくんでい る. この報告ではテーマ年表検索における年代情報抽出法について説明する. こ の方法を世界大百科事典に適用して評価した結果,大半のばあいに 99% 以上の抽出 精度がえられた. また,年月日や世紀など,いくつかの単位がまざった年代表記を 効率よくかつすくない誤差でデータ表現する方法について説明する.

研究テーマ紹介: 軸づけ検索 (テーマ検索)

キーワード: テキスト検索, 軸づけ検索, 軸付け検索, テーマ年表検索, 年代軸検索, 時間軸検索, 年代情報抽出, 時間情報抽出, 年代抽出, 情報組織化, 百科事典検索, 検索結果組織化, 組織化検索, 検索結果構造化, 構造化検索

1999-03-09

会員ネットワーク「ネットで百科」の概要と実現法

澤田 瑞穂,山崎 幹夫,藤井 泰文,西岡 真吾,高野 明彦,金田 泰, 情報処理学会第 58 回全国大会,1J-1, 1999, IPSJ により出版.

[ 論文 PDF ファイル (NII) ]


キーワード: テキスト検索, 軸づけ検索, 軸付け検索, 地域軸検索, テーマ地名検索, 百科事典検索, ネットで百科, テーマ地図検索, 共著論文

1999-03-01

「ネットで百科」 における 「テーマ年表検索」 の機能と実装法

金田 泰,山崎 幹夫,澤田 瑞穂,平野 義明,藤井 泰文, 情報処理学会第 58 回全国大会,1J-3, 1999, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 PostScript ファイル ]

要約: (なし)

研究テーマ紹介: 軸づけ検索 (テーマ検索)

キーワード: テキスト検索, 軸づけ検索, 軸付け検索, テーマ年表検索, 年代軸検索, 時間軸検索, 百科事典検索

1999-02-15

Vector Compiler and Its Algorithms

Yasumura Michiaki, Tanaka Yoshikazu, Kanada Yasusi, 数理解析研究所講究録, 1999, 京都大学により出版.

[ 論文 PDF ファイル ]

キーワード:

1998-12-01

細粒度全文検索法の開発

金田 泰, 未出版, 1998.

[ 論文 PDF ファイル ]
[ 論文ポストスクリプト・ファイル ]

要旨: 従来のテキスト検索は,通常,文書を単位としていた. しかし,ユーザがもとめるのは文書そのものではなく,膨大な文書集合から短時間で必要な 《情報》 を検索することである. そこで,文書中での検索情報の存在場所へのハイパーリンクやその周辺からの抜粋が表示でき,文書中の複数の話題をくべつして全文検索できる 「細粒度検索法」 を開発した. この報告では,テキストを原子というこまかい単位で検索する細粒度検索のモデルを記述し,従来の全文検索エンジンをそのまま,または一部だけ改造して実現できる 2 方法を説明・比較し,試作評価によって従来法よりユーザの負荷を低減できることをしめした.

研究テーマ紹介: 軸づけ検索 (テーマ検索)

キーワード: テキスト検索, 細粒度検索, パッセージ検索

1998-11-01

軸づけ検索法 -- 文書からの抜粋を抽出・整理して出力する全文検索法

金田 泰, 情報処理学会 情報学基礎研究会報告 98-FI-50-4, pp. 25-32, 1998, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 PostScript ファイル ]

要約: 軸づけ検索法という,文書集合からの抜粋情報を抽出し整理する機能をもつ 全文検索法を開発した. この方法では,ユーザが検索語を入力すると同時に 年代,地域,数量などの軸をメニューから選択する.すると,軸と検索語に 関連する部分の抜粋とその原文へのハイパーリンクがその軸にそって 整列出力される. この方法をつかえば,検索結果が膨大でもユーザ要求に あわせて整理されているので,ユーザはそれをサーベイすることができる. この方法を百科事典と新聞記事に応用した結果,分散された関連情報がうまく 収集でき,検索結果のあいだの関係を発見することができることがわかった. たとえば,検索文字列として 「流域」,軸として 「面積」 をあたえると, 百科事典から世界の川の記述を収集し流域面積でソートした結果がえられる.

研究テーマ紹介: 軸づけ検索 (テーマ検索)

キーワード: テキスト検索, 軸づけ検索, 軸付け検索, 年代軸検索, 時間軸検索, 地域軸検索, 数量軸検索, 百科事典検索, 新聞記事検索, 新聞検索, 情報抽出, 情報組織化, 検索結果組織化, 組織化検索, 整列, 検索結果構造化, 構造化検索

1998-06-27

Axis-specified Search: A Fine-grained Full-text Search Method for Gathering and Structuring Excerpts

Kanada, Y., 3rd ACM Conference on Digital Libraries, pp. 108-117, 1998, (C) Copyright 1998 by ACM.

[ English page ]
[ 論文 PDF ファイル (ACM DL)] [ 論文 PDF ファイル ] [ 論文 PostScript ファイル ]

要約: A text search method, which is called an axis-specified search method, is proposed. This method is suitable for full-text searches of a large-scale text collection. In this method, in addition to specifying search strings, the user selects an axis from a predefined set. The system outputs excerpts and hyper-links that are ordered along the axis. The search strings express the specific subject of the search, and the axis specifies a general-purpose method of ordering results. Short sub-topics, which cannot be easily caught by statistical methods, are effectively gathered from the text collection. The user can get satisfactory results using a simple search string. Even if the number of results is very large, the user can easily survey them, because they are well structured. This method has been applied to an electronic encyclopedia and a newspaper database. In these applications, distributed descriptions that were related to each other could be gathered, and the user could discover their relationships from the results. For example, by specifying "semiconductor" for a search string and "year" for an axis, a table listing seven decades of semiconductor-related topics sorted by year was generated from newspaper issues published over a single year. By specifying "basin" for a search string and "area" (m2) for an axis, descriptions of the world's largest rivers were extracted from the encyclopedia and sorted according to their basin areas.

研究テーマ紹介: 軸づけ検索 (テーマ検索)

キーワード: テキスト検索, 軸づけ検索, 軸付け検索, 年代軸検索, 時間軸検索, 地域軸検索, 数量検索, 百科事典検索, 新聞記事検索, 新聞検索, 情報抽出, 情報組織化, 検索結果組織化, 組織化検索, 整列, 検索結果構造化, 構造化検索

1998-01-01

記憶装置・入出力装置

「記憶装置」,「入出力装置」 の項目,世界大百科事典,平凡社.

[ English page ]

キーワード:

1997-11-01

Web Pages That Reproduce Themselves by JavaScript

Kanada, Y., ACM SIGPLAN Notices, Vol. 32, No. 11, pp. 49-56, November, 1997.

[ English page ]
[ 論文 PDF ファイル改訂版 ]
[ 論文 PDF ファイル (オリジナル) ]

要約: A JavaScript program in a Web page can clear the page content including the program itself and generate new content. The program can generate exactly the same content including the program itself. This means that a Web page can reproduce itself by JavaScript program that is included in the page. Although exact reproduction is useless, inexact reproduction, which transform part of the content, is usable for more practical purpose. For example, Web pages that change its view from outline mode to detail mode by clicking a button in the page can be implemented using this method. This method can also applicable to other types of documents, such as SGML or XML, if the document may contain self-reproductive program. Another method for reproducing Web pages without reproducing programs is also mentioned. Reproductive Web pages partially but really work on Netscape Navigator.

研究テーマ紹介: Web ページの自己再生産

キーワード: 自己再生産, 自己増殖, プログラミング言語, JavaScript

1997-07-01

Web ページを自己再生産する JavaScript プログラム

金田 泰, 情報処理学会 「夏のプログラミング・シンポジウム」, 別冊 (105-112), 1997-7.

[ English page ]
[ 論文 PDF ファイル ]

要約: Web ページ中の JavaScript プログラムは,そのプログラムじたいをふくむ ページ内容を消去して,あらたにページ内容を生成することができる. JavaScript プログラムはそのプログラムをふくむ正確に同一のページ内容を 生成できる. したがって,Web ページはそこにふくまれる JavaScript プログラムによって自己再生産できる. 正確な再生産はやくにはたたないが, 内容の一部を変化させる "不正確な再生産" は実用的な目的でつかえる. この方法によって,たとえばページ中のボタンをおすことでアウトライン・モード から詳細表示モードに,またその逆に変化させることができる. この方法は, 自己再生産するプログラムを文書がふくむことができるなら,SGML や XML など,HTML 以外の文書にも適用できる. またここではプログラムを再生産せずに Web ページを再生産する方法についてものべる. 自己再生産する Web ページは 部分的にだが Netscape Navigator において実際に動作する.

研究テーマ紹介: Web ページの自己再生産

キーワード: 自己再生産, 自己増殖, プログラミング言語, JavaScript

1996-02-01

Methods of Parallel Processing of Constraint Satisfaction Using CCM -- A Model for Emergent Computation

Kanada, Y., SIG PPAI, Japan Society for Artificial Intelligence, Feb, 1996, Published by JSAI.

[ English page ]
[ 論文 PDF ファイル ] [ 論文ポストスクリプト・ファイル]
[ 論文 DVI ファイル (図をのぞく)] [ EPSF 形式の図 : 1, 2, 3, 4, 5, 6, 7, 8 ]

要旨 (英語のみ) : Two methods for solving large-scale constraint satisfaction problems using parallel processing are surveyed in the present paper. These methods are based on CCM, which is a model for emergent computation. The number of constraint violations is minimized in these methods. The minimization is performed by optimization of local functions. The computation is stochastic and no global information is used. An annealing method called FAM has been introduced to avoid ``local maxima.'' FAM also works only with local information. Two types of parallel processing of CCM-based constraint satisfaction using FAM has been tested. One is a parallel search and the other is a cooperative search. Our experiments has shown that both methods improve performance almost linearly in large-scale graph coloring problems when the number of processors is ten or so.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, 創発的計算, 制約充足問題, 並列処理, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決

1996-01-01

Constraint Satisfaction by Parallel Optimization of Local Evaluation Functions with Annealing

Kanada, Y., 未出版, 1996.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト ファイル ]

[ Java による各種の制約充足問題のデモ (それぞれ触媒,規則,フラストレーションをかえてためせます) ]

要旨 (英語のみ): A method for solving large-scale constraint satisfaction problems is proposed in the present paper. This method is stochastic (or randomized) and uses local information only, i.e., no global plan is expressed in the program and the computation refer to no global information. This method uses CCM (Chemical Casting Model) as a basis, which is a model for emergent computation proposed by the author. The original CCM-based method minimizes the number of constraint violations not directly but throught optimization of local functions, which are called LODs (local order degrees). This method sometimes falls into a "local maximum." This difficulty is solved by a type of annealing, which we call the frustration accumulation method (FAM). FAM also works only with local information. No global functions is used in FAM, No global parameters such as temperature are used, and global control is thus unnecessary. Experiments show that the performance of this method is not very sensitive to parameter values. This means that parameter tuning is easy. In several problems, the performance is comparable to conventional simulated annealing or GSAT, which are based on global evaluation functions. Because of the nonexistence of global information reference, CCM with FAM can be parallelized very easily. Thus, the performance is improved and is almost linear in certain cases.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, 制約充足問題, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, アニーリング, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, 関数最適化, 局所情報, 局所的計算, 局所評価関数, FAM, フラストレーション蓄積法

Constraint Satisfaction Using Neural Networks with a Local and Autonomous Annealing Technique

Kanada, Y., 未出版, 1996.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト ファイル ]

要旨 (英語のみ): A method for solving large-scale constraint satisfaction problems using an annealed symmetrically-connected neural network, which is called DSN-FAM, is proposed in the present paper. Some conventional methods, such as Hopfield networks, often fail to find a solution. Some others, such as Boltzmann Machines, take too much time. These difficulties are solved by a type of annealing technique, which we call the frustration accumulation method (FAM). DSN-FAM works only with local information, and no global functions or global parameters such as a temperature are used. DSN-FAM thus works autonomously. That is, no external control is necessary while operating. Experiments show that this method does not fail to find a solution and the execution time is less than one tenth of Boltzmann Machines. The performance can be easily and almost linearly improved by parallel processing using tens of processors.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, ニューラル・ネットワーク, ニューラルネットワーク, 制約充足問題, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, アニーリング, FAM, フラストレーション蓄積法

1995-11-01

Combinatorial Problem Solving Using Randomized Dynamic Composition of Production Rules

Kanada, Y., 1995 Int'l Conference on Evolutionary Computation (ICEC '95), pp. 467-472, (C) Copyright 1995 by IEEE.

[ English page ]
[ 論文 PDF ファイル] [ 論文ポストスクリプト・ファイル]
[ IEEExplore 論文ページ ]

要旨 (英語のみ) : The present paper proposes a method of solving combinatorial problems using randomized dynamic rule composition. This method is called CCM* and is based on a computational model called Chemical Casting Model (CCM), which is a rule-based computational model for emergent computation. CCM was proposed by the author toward solving dynamic, open and incompletely specified problems using a few simple rules and evaluation functions. By composing a rule from a given production rule dynamically and randomly, CCM* makes it possible to escape from local maxima, which cannot be escaped from by applying the original rule. This method is compared with the original CCM and another extended version of CCM, i.e., CCM with simulated annealing. 0-1 integer programming problems are solved using these methods. Our experiments show that CCM* performs much better than both the original and annealed CCM. In addi-tion, suboptimal solutions can be found in less time than a branch-and-bound method.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, くみあわせ最適化, 組合せ最適化, 組み合わせ最適化, 整数計画, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, アニーリング

1995-10-01

Combinatorial Problem Solving Using Randomized Dynamic Tunneling on A Production System

Kanada, Y., IEEE Systems, Man and Cybernetics '95, (C) Copyright 1995 by IEEE.

[ English page ]
[ 論文 PDF ファイル] [ 論文 ポストスクリプト・ファイル]
[ IEEExplore 論文ページ ]

要旨 (英語のみ) : Levy and Montalvo, Yao, and Shima individually pro-posed tunneling algorithms. The tunneling algorithms employ analogy to tunnel effect in physics, and are used to optimize continuous systems. The present paper proposes a method of solving combinatorial problems using a type of randomized dynamic tunneling technique. This method is based on a computational model called CCM*. CCM* is an extended version of the Chemical Casting Model (CCM). CCM was proposed by the author toward developing a method of solving open and incompletely-specified problems that may change while being solved, using self-organizing computation.

The 0-1 integer programming problem is solved using CCM* with a very simple rule and an evaluation function. CCM* allows us to escape from local maxima by composing the rule dynamically and randomly. This cannot be done by using the original production rule as is. Our experiments show that approximate solutions can be found more rapidly by CCM* than by using a branch-and-bound method in the case of 0-1 integer programming.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, くみあわせ最適化, 組合せ最適化, 組み合わせ最適化, 整数計画, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, トンネル効果, トンネリング

1995-08-01

局所情報によるアニーリングをつかった大規模制約充足とその並列処理 -- 創発的計算のためのモデル CCM の応用 --

金田 泰, SWoPP '95 (情報処理学会人工知能研究会), AI95-16, 17-24, 1995, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル: なし (変換失敗 !) ] [ 論文 ポストスクリプト・ファイル]

要旨 (英語のみ) : この報告では,創発的計算のためのモデル CCM (化学的キャスティング・モデル) にもとづいて大規模な制約充足問題をとくための方法を提案する. また,その並 列処理の方法をしめす. CCM にもとづく方法ではこれまで大規模な問題をとくこ とができなかったが,FAM (フラストレーション蓄積法) という一種のアニーリン グを導入し,さらにパラメタをうまく調整することによって,大規模なグラフ彩 色問題を GSAT シミュレーテッド・アニーリングと同程度の計算時間で逐次処理で とくことができるようになった. さらに,かぎられた量の相互排斥だけをつ かって,比較的容易に並列処理できることがわかった. ある条件のもとではほぼ プロセッサ数に比例する性能がえられた.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, 制約充足問題, 並列処理, 創発的計算, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, アニーリング, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, 局所情報, 局所的計算, 局所評価関数

1995-06-01

Fuzzy Constraint Satisfaction Using CCM -- A Local Information Based Computation Model

Kanada, K., Fuzz-IEEE/IFES '95, pp. 2319-2326, 1995.

[ English version ]
[ 論文 PDF ファイル. (C) Copyright 1995 by IEEE]
[ 論文 ポストスクリプト・ファイル. (C) Copyright 1995 by IEEE]
[ IEEExplore 論文ページ ]

要旨 (英語のみ) : A method of solving fuzzy constraint satisfaction problems defined by Ruttkay is shown in the present paper. This method is based on CCM, which is a computation model for emergent computation or for locality-based problem solving. CCM is a type of production system. It works stochastically, or randomly, and works with evaluation functions that are computed only with local information. CCM has been applied to constraint satisfaction problems (CSPs). Binary-valued evaluation functions, each of which indicates whether a constraint is satisfied, are used. If the values of evaluation functions are extended to real values, fuzzy CSPs can be expressed in CCM, and solved using a technique similar to GSAT or annealing. This method is applied to a fuzzy graph coloring problem, and the performance is evaluated. This method can also be applied to an open and dynamical fuzzy/non-fuzzy CSPs, in which data and constraints are changing dynamically or coming from or going to the outside of the system.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, ファジー制約充足, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, 局所情報, 局所的計算, 局所評価関数

1995-01-01

Parallel Processing Method of Local-Information-Based Combinatorial Problem Solving Based on Implicit Stochastic Divide-and-Conquer

Kanada, Y., 未出版, 1995.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト ファイル ]

要旨 (英語のみ): A method of solving combinatorial problems, such as the N queens problem or graph coloring problems using independent parallel processes, is proposed in the present paper. This method is stochastic (or randomized). Problems are decomposed for parallel processing implicitly and stochastically by this method. This method is based on CCM, which is a computational model proposed by the author. A program consists of production rules and local evaluation functions in CCM. Each process uses the same set of rules and functions, and it may use the same set of initial data in this method. However, the performance is approximately in proportion to the number of processors in average in certain cases. The theoretical reason of this linear acceleration is explained, and several results of experiments, some of which was successful but others were not, are also shown.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, 並列処理, 制約充足問題, くみあわせ最適化, 組合せ最適化, 組み合わせ最適化, トラベリング・セールスマン問題, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決

1994-12-01

化学反応系とのアナロジーにもとづく開放的で複雑な計算のためのモデル CCM -- その連動式ニューラルネットとの関係について --

金田 泰, 日本神経回路学会第 5 回全国大会, pp. 36-39, 1994, JNNS により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP PDF ファイル: スライド, ハンドアウト ] [ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]

要旨 (英語のみ) : The basics of CCM (chemical casting model), which is a computation model for emergent computation, is explained, and an extension of CCM, i.e., dynamical composition of rules, is described. The relation between the extended CCM and neural networks, especially the neural networks with linked state transition, is mentioned, and the importance of designing good concrete dynamics is also mentioned.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, 化学反応系, 開放系

1994-10-01

創発的計算のためのモデル CCM による制約充足問題などの独立並列処理法

金田 泰, 情報処理学会 第 49 回全国大会, pp. 4-321 - 322, 1994, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ] [ OHP PDF ファイル: スライド, ハンドアウト ]

要旨: CCM (Chemical Casting Model) は,創発的計算にもとづく問題解決法の確立を めざして開発した,非決定的 (ランダム) な計算のモデルである. この研究で は,局所的・部分的な情報だけをつかった,たえず変化する環境のもとでのひ らかれた計算をめざしている. この報告では, CCM にもとづく制約充足問題な どのひとつの並列処理法についてのべる. CCM にもとづく計算においては計算 時間がほぼ指数分布にしたがうばあいがあり,そのときは独立な並列処理に よってプロセッサ台数にほぼ比例する性能向上が期待できることがわかった.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, SOOC, 計算言語, 制約充足問題, くみあわせ最適化, 組合せ最適化, 組み合わせ最適化, 並列処理, 創発的計算, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決

1994-09-01

創発的計算のための言語 SOOC: その特徴と実装 -- 魔方陣を例題として --

金田 泰, 情報処理学会記号処理研究会, 94-SYM-75-5, pp. 31-38, 1994, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

[ Java による魔方陣のデモ (SOOC とは無関係です) ]

要旨: たえず変化する環境に対してひらかれた創発的計算にもとづく問題解決法の確立をめざして, 著者は CCM という計算モデルを提案している. CCM は局所的な情報だけで計算される評価 関数をともなう,ランダムに動作する一種のプロダクション・システムである. その実験を おこなうために計算言語 SOOC-94 とその処理系を開発し使用している. ここでは SOOC-94 の特徴と逐次計算機の Lisp 上の実装について,魔方陣の問題を例として説明する. この言語 の特徴としては,規則適用時に評価関数の自動計算や局所的な自動バックトラックをするこ と,規則の両辺におけるパタンの構文がほぼ統一されていること,規則の適用順序に関する 2 種類のスケジューリング戦略とくにランダム戦略の存在,データ (構造体) の要素と して複数の同名の要素の存在をゆるしていることなどがある.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, SOOC, 計算言語, 創発的計算, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, プロダクション・システム, プロダクションシステム, プロダクション規則, 局所情報, 局所的計算, 局所評価関数, 魔方陣

SOOC-94: An Experimental Language toward Building Real-World Computing Systems

Kanada, Y., 未出版, 1994.

[ English page ]
[ 論文 PDF ファイル] [ 論文 ポストスクリプト・ファイル]

要旨 (英語のみ): Today's computer applications often require on-line input and output and sometimes requires change of computation methods while processing complex tasks. In future, they will probably be required to change even the objectives of computation. Such a new style of information processing is called real-world computing in the present paper. Real-world computing requires computation languages to work without fixed sequence of control nor fixed data flow, to work without a whole plan of computation, to be always open to environment at any time, to have possibility of distributed and parallel processing, to have possibility to respond to nondeterministic actions, and so on. Because today's programming languages are considered not to satisfy these requirements, a new computation model called CCM (chemical casting model) and a language called SOOC-94, which partially satisfies the requirements, are developed as the first step. Computation is regarded as biased random walk in CCM. The random walk is realized by a randomly acting forward-chaining production system, and the bias is realized by locally computed evaluation functions in SOOC-94. I have developed a preliminary version of compiler and interpreter, and analyzed the computation processes and results of graph coloring problems for example.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, SOOC, 計算言語, 創発的計算, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決

1994-08-01

創発的計算のためのモデル CCM による問題解決法における局所性の制御法

金田 泰, SWoPP '94 (情報処理学会人工知能研究会), 94-AI-95-4, pp. 29-38, 1994, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル] [ 論文 ポストスクリプト・ファイル (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ] [ OHP PDF ファイル: スライド, ハンドアウト ]

[ Java による各種の制約充足問題のデモ (それぞれ触媒,規則,フラストレーションをかえてためせます) ]

要旨 : CCM (Chemical Casting Model) は,たえず変化する環境に対してひらかれた創発的計算にもと づく問題解決法の確立をめざして開発した,非決定的 (ランダム) に動作する計算のモデルで ある. CCM においては局所的な情報をつかって計算がおこなうが,局所的な極限においては 解をもとめることはできない. したがって,計算,とくに評価関数の計算の局所性を制御し て,局所最適点におちいらないように探索空間内での局所性を制御する必要がある. この報 告では 4 つの局所性の制御法をしめす. それらは,触媒の加減,反応規則の合成またはトン ネリング,シミュレーテッド・アニーリング (SA),フラストレーション蓄積法 (FAM) であ る. これらを比較した結果,制約充足のばあいは触媒の加減と FAM が有効だが,これらだ けでは従来法に計算時間のうえでおとるばあいがあることがわかった. また最適化のばあい はトンネリングすなわち反応規則の動的な合成が有効だとわかった.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, 創発的計算, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, 局所情報, 局所的計算, 局所評価関数, トンネル効果, トンネリング

1994-07-01

The Effects of Randomness in Asynchronous 1D Cellular Automata

Kanada, Y., Artificial Life IV, Poster, 1994.

[ English page ]
[ 論文 PDF ファイル ] [ ポスター ハイパーテキスト版 ]
[ 未出版 拡大版論文 PDF ファイル]

要旨 (英語のみ): Cellular automata are used as models of emergent computation and artificial life. They are usually simulated under synchronous and deterministic conditions. Thus, they are evolved without existence of noise, i.e., fluctuation or randomness. However, noise is unavoidable in real world. The objective of the present paper is to show the following two effects and several other effects caused by asynchronism or synchronism and by existence or nonexistence of randomness in the computation order in one-dimensional asynchronous cellular automata (1D-ACA) experimentally. One major effect is that certain properties of two-neighbor 1D-ACA are fully expressed in their patterns if certain level of randomness exists, though they are only partially expressed if no randomness exists. The patterns generated by 1D-ACA may have characteristics, such as mortality of domains of 1's or splitting domains of 0Us into two. These characteristics, which are coded in the RchromosomeS of the automata, i.e., the look-up table, are fully expressed only when the computation order is random. The other major effect is that phantom phenomena, which almost never occurs in real world, sometimes occur when there is no noise. The characteristics of patterns generated by several 1D-ACA are drastically changed from uniform patterns to patterns with multiple or chaotic phases when only low level of noise is added.

研究テーマ紹介: RACA: ランダムな非同期セル・オートマトン

キーワード: ランダム・セルオートマタ, ランダム・セルオートマトン, ランダム・セル・オートマタ, ランダム・セル・オートマトン, ランダム化セルオートマタ, ランダム化セルオートマトン, ランダム化セル・オートマタ, ランダム化セル・オートマトン, 非同期セルオートマタ, 非同期セルオートマトン, 非同期セル・オートマタ, 非同期セル・オートマトン, 創発的計算, 複雑系, ノイズ, エマージェント・コンピュテーション, セルラオートマタ, セルラオートマトン, セルラーオートマタ, セルラーオートマトン, セルラ・オートマタ, セルラ・オートマトン, セルラー・オートマタ, セルラー・オートマトン, ランダマイズド計算, 規則ベース計算

1994-04-01

創発的計算のためのモデル CCM による動的なグラフ彩色

金田 泰, 人工知能学会並列人工知能研究会, SIG-PPAI-9401, pp. 7-12, 1994, JSAI により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ ポスター ポストスクリプト・ファイル: Part 1, Part 2 ]
[ ポスター PDF ファイル : Part 1, Part 2 ]

[ Java による彩色のデモ (静的な彩色) ]

要旨 : 実世界の計算システムは刻々と変化する環境に対してひらかれた複雑なシステムであり,従来 のソフトウェア開発法では根本的に対処できないとかんがえられる. CCM (Chemical Casting Model) は,創発的計算にもとづくソフトウェア開発法の確立をめざして開発した,局所情報に もとづく非決定的 (ランダム) な計算のモデルである. CCM は局所的に計算される評価関数を ともなうプロダクション・システムである. この報告では,CCM にもとづく計算言語 SOOC による動的に変化するグラフ頂点の彩色 (移動放送局への電波のわりあて) の方法と実験結果と をしめす. SOOC によれば,静的なグラフ彩色とおなじプロダクション規則と評価関数とをつ かうだけで,動的な彩色をおこなうことができ,基本的におなじ方法と道具とをつかって結果 を評価できる.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, 動的制約充足問題, 創発的計算, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, プロダクション・システム, プロダクションシステム, プロダクション規則, 局所情報, 局所的計算, 局所評価関数, グラフ彩色, グラフぬりわけ, グラフ塗り分け

プロダクション規則の合成による記号的ランダム・トンネリング -- 計算モデル CCM* による制約充足と最適化 --

金田 泰, 計測自動制御学会第 14 回システム工学分科会研究会 "組合せ問題とスケジューリング問題の新解法," 45-52, 1994, SICE により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル : なし (変換失敗!)]

要旨 : トンネリング・アルゴリズムという連続系のための最適化法を Levy and Montalvo,Yao,島ら が提案しているが,この報告では,くみあわせ問題をとくための,一種のトンネリングをとり いれた方法をしめす. この方法は,問題解決の途中で問題じたいが変化するような動的な問題 の自己組織的な解決をめざして著者が提案している CCM* (拡張された 化学的キャスティング・モデル) という計算モデルにもとづいている. ここではグラフ彩色問題と 0-1 整数計画問題と を例題として,この方法を説明する. CCM* はプロダクション・システムの一種であるが,こ の方法をつかえば,あたえられたプロダクション規則をそのまま適用してもぬけだせない局所 最大点を,そのプロダクション規則を動的かつランダムに合成することによって,ぬけだすこ とができる.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, 制約充足問題, くみあわせ最適化, 組合せ最適化, 組み合わせ最適化, 創発的計算, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, トンネル効果, トンネリング, プロダクション・システム, プロダクションシステム, プロダクション規則, 局所情報, 局所的計算, 局所評価関数, グラフ彩色問題, グラフぬりわけ問題, グラフ塗り分け問題, 整数計画問題

1994-01-01

Stochastic Problem Solving by Local Computation based on Self-organization Paradigm

Kanada, Y., and Hirokawa, M., 27th Hawaii International Conference on System Sciences (HICSS-27), pp. 82-91, 1994.

[ English page ]
[ 論文 PDF ファイル, (C) Copyright by IEEE ]
[ 論文 ハイパーテキスト版 (図は現在利用できません) ]
[ 論文 ポストスクリプト・ファイル, (C) Copyright by IEEE ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ] [ OHP PDF ファイル: スライド, ハンドアウト ]
[ IEEExplore 論文ページ ]

[ Java による N クイーン問題とソートのデモ ]

要旨: We are developing a new problem-solving methodology based on a self-organization paradigm. To realize our future goal of self-organizing computational systems, we have to study computation based on local information and its emergent behavior, which are considered essential in self-organizing systems. This paper presents a stochastic (or nondeterministic) problem solving method using local operations and local evaluation functions. Several constraint satisfaction problems are solved and approximate solutions of several optimization problem are found by this method in polynomial order time in average.

Major features of this method are as follows. Problems can be solved using one or a few simple production rules and evaluation functions, both of which work locally, i.e., on a small number of objects. Local maxima of the sum of evaluation function values can sometimes be avoided. Limit cycles of execution can also be avoided. There are two methods for changing the locality of rules. The efficiency of searches and the possibility of falling into local maxima can be controlled by changing the locality.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, 制約充足問題, 創発的計算, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, 局所情報, 局所的計算, 確率過程, 局所評価関数

1993-11-01

プロダクション規則と局所評価関数にもとづく計算モデル CCM による各種のソート法

金田 泰, 情報処理学会記号処理研究会, 93-SYM-71-5, pp. 33-40, 1993, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

[ Java によるソートと N クイーン問題のデモ (ソートは 1 種類だけ)]

要旨: 著者は,局所情報だけで計算されるプロダクション規則と評価関数とを要素とする確 率的な計算モデル 「化学的キャスティング・モデル (CCM)」 とそれにもとづく計算言語 SOOC を提案している. このモデルは仕様も明確にかきくだせない開放系の問題に 適用するために開発したものだが,古典的な問題への適用実験も重要だとかんがえて いる. そこでこの報告では CCM をソートに適用し,あたらしいソート法をしめすと ともに,従来の挿入ソート,交換ソートなどにもとづくソート法をしめす. また,あ わせてそれらの実験結果をしめす. この方法では,唯一のプロダクション規則と唯一 の評価関数をあたえるだけで,局所情報の参照だけにもとづいてソートをおこなうこ とができる. また,局所情報だけをつかうことによって生じる興味ぶかい現象につい ても言及する.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, ソート, ソーティング, 創発的計算, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, プロダクション規則, 局所評価関数, プロダクション・システム, プロダクションシステム

1993-10-01

プロダクション規則と局所評価関数にもとづく計算モデル CCM -- その拡張と 0-1 整数計画問題への適用 --

金田 泰, 情報処理学会第 47 回全国大会, pp. 1-99-100, 1993.10, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

要旨: 報告者は局所的部分的な情報にもとづく自己組織的な計算をめざして, 化学的キャスティング・モデル (CCM) という計算モデルを提案している. CCM は化学反応系 とのアナロジーをつかい,プロダクション・システムにもとづく計算モデルであ る.CCM の特徴は,適用対象データに関する局所的な評価関数によってプロダク ション規則の適用が制御される,非決定的あるいは確率的に動作する,手続き的な 解法よりはるかに単純なプログラムで問題がとけるなどである. これまでに N ク ウィーン問題,彩色問題,巡回セールスマン問題などへの CCM の適用を試行した が,ここではそれを拡張して 0-1 整数計画問題に適用した結果を報告する.

P.S. より具体的にいうと,ここでおこなった CCM の拡張とは,シミュレーテッ ド・アニーリングとプロダクション規則の合成 (いずれも局所最大点におちいるの をふせぐための方法) である.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, くみあわせ最適化, 組合せ最適化, 組み合わせ最適化, 整数計画法, 創発的計算, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決

1993-08-01

化学反応系とのアナロジーにもとづく自己組織的情報処理のためのモデル CCM

金田 泰, 長期研究会 「複雑系 2」 発表報告 (A4, 1 枚), 物性研究, 1994.2.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル (印刷低速 !) ]
[ ポスター ポストスクリプト・ファイル : ポスター, ハンドアウト ]
[ ポスター PDF ファイル: ポスター, ハンドアウト ]

要旨: この研究はコンピュータ上で自己組織的計算,すなわち局所的・部分的 (不完全) な 情報だけをあたえて,のぞみの大域的な構造をつくりあげる,創発的 (emergent) な 情報処理法の実現をめざしている. CCM にもとづいて,局所的な情報から彩色問題な どの問題解決ができる. CCM にもとづく制約充足問題をとくシステムは,大域秩序度 の時間変化,触媒の作用などにおいて興味ぶかい動特性をしめすことがわかった.

発表は 1993 年 8 月.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, 創発的計算, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, 化学反応系, 自己組織化

プロダクション規則と局所評価関数にもとづく計算モデル CCM による問題解決法の特徴

金田 泰, SWoPP '93 (情報処理学会人工知能研究会), 93-AI-89-2, pp. 11-20, 1993, IPSJ により出版.

[ English page ]
[ 論文 3 訂版 PDF ファイル ] [ 論文 3 訂版 ポストスクリプト・ファイル (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

[ Java による彩色のデモ ]

要旨: 制約充足や最適化などの問題解決は解の探索としてとらえられる. 人工知能やオペ レーションズ・リサーチなどにおける従来の解探索法においては,バックトラックを つかって木構造の探索空間を網羅的・系統的に探索することが基本となっている. 著 者は分散・並列的に作用するプロダクション規則と局所評価関数にもとづく計算モデル CCM (化学的キャスティング・モデル) を提案しているが,CCM による解探索は, 評価関数によってバイアスをかけながら探索空間上を酔歩 (random walk) すること だとみなせる. この方法の特徴は,木ではなく強連結なグラフ上を探索すること,可 逆で対称性がある規則を使用すること,規則がふくむ触媒なるものを加減したり規則 を合成したりすることによってバイアスのつよさや規則の局所度がかえられることな どである.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, 制約充足問題, 創発的計算, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, 局所情報, 局所的計算, 局所評価関数

1993-03-01

プロダクション規則と局所評価関数による制約充足問題の解法

金田 泰, 廣川 真男, 情報処理学会記号処理研究会, 93-SYM-68-2, pp. 9-16, 1993, IPSJ により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

[ Java による N クイーン問題のデモ ]

要旨: この報告では,CCM にもとづいてある種の制約充足問題をとく方法をしめす. この方 法では決定的かつ手続き的な制約伝搬にはよらずに確率的な手法によって,また非常 に単純な"プログラム" によって N クウィーン問題や地図の彩色問題などの制約充足 問題を平均すると多項式時間でとくことができる. この報告ではまた,この方法によ る計算の特性すなわち実行時間やその分布などを実測値にもとづいて論じる.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, 制約充足問題, 創発的計算, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, 局所情報, 局所的計算, 局所評価関数, プロダクション規則, 局所評価関数, プロダクション・システム, プロダクションシステム, Nクイーン問題, 彩色問題, ぬりわけ問題, 塗り分け問題

確率過程としての計算 -- 計算過程のマクロ・モデルの必要性とその例 --

金田 泰, 電子情報通信学会コンピューテーション研究会 / ソフトウェアサイエンス研究会, COMP92-93, SS92-40, pp. 1-10, 1993, IEICE により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

要旨: 複雑な記号処理をおこなう計算システムは,プログラムを静的に理解することによっ て,あるいはミクロな動作を追っていくことによってそのふるまいを理解することは できない. したがって,それを理解するには計算過程をマクロにみるモデルが必要で ある. 計算過程のマクロ・モデルはまた,計算の自動制御や自己組織的計算の実現の ためにも必要だとかんがえられる. この報告では計算過程のマクロな理論に関する基 礎検討をおこない,確率過程論にもとづくモデル化を提案する. そして,そのひとつ の例として,ミクロ・モデルとしての 化学的キャスティング・モデル (CCM) に対応するマクロ・モデルとしてマルコフ連鎖モデルをしめし,それにもとづいて CCM にもとづくエイト・クウィーン問題の計算過程を分析する. この理論はミクロ・モデル における記号計算とマクロ・モデルにおけるパタン計算との一種の融合をはかってい るということができる.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, 創発的計算, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, 局所情報, 局所的計算, 確率過程, 自己組織化, ミクロ・モデル, ミクロモデル, 記号計算, マクロ・モデル, パタン計算, マクロモデル, 自己組織化

1993-02-01

プロダクション規則と局所評価関数による最適化の方法とその計算過程におけるマクロなふるまい

金田 泰, 第 11 回計測自動制御学会システム工学部会研究会, pp. 27-34, 1993, SICE により出版.

[ English page ]
[ 論文 PDF ファイル ] [ 論文 ポストスクリプト・ファイル: Part 1, Part 2 (印刷低速 !) ]
[ OHP ポストスクリプト・ファイル: スライド, ハンドアウト ]
[ OHP PDF ファイル: スライド, ハンドアウト ]

要旨: 著者は自己組織的計算のための 「化学的キャスティング・モデル (CCM)」とそれにも とづく計算言語 SOOC を提案している. このモデルは仕様も明確にかきくだせない開 放系の問題への適用を本来の目的として開発した. しかしこれを仕様が明確な最適化 問題に適用しても,巡回セールスマン問題などの単純な最適化問題のばあい,唯一の プロダクション規則と唯一の評価関数 (局所秩序度という) をあたえるだけで,局所 的な情報の参照だけにもとづいて問題がとけるという利点がある. この報告では CCM にもとづく最適化の例として巡回セールスマン問題をとりあげ,解法と実験結果とを しめす. また,この方法による計算過程におけるマクロなふるまいを理解するため, マルコフ連鎖にもとづくモデルにあてはめた結果をしめす.

研究テーマ紹介: CCM: 化学的計算のモデル

キーワード: CCM, くみあわせ最適化, トラベリング・セールスマン問題, 創発的計算, ランダム化計算, ランダム化問題解決, ランダマイズド計算, ランダマイズド問題解決, 規則ベース計算, 規則ベース問題解決, ルールベース計算, ルールベース問題解決, プロダクション規則, プロダクションシステム, プロダクション・システム, 局所評価関数

1993-01-01

A Method of Vector Processing for Shared Symbolic Data

Kanada, Y., Parallel Computing, Vol. 19, 1993, pp. 1155-1175.

[ English page ]
[ 論文 PDF ファイル (一部フォント不正)]
[ 論文ポストスクリプト・ファイル ]

要旨 (英語のみ): Conventional processing techniques for pipelined vector processors such as the Cray-XMP, or data-parallel computers, such as the Connection Machines, are generally applied only to independent multiple data prcessing. This paper describes a vector processing method for multiple processings including parallel rewriting of dynamic data strutures with shared elements, and for mutiple procesings that may rewrite the same data item multiple times. This method enables vector processing when entering mutiple data items into a hash table, address calculation sorting, and many other algorithms that handle lists, trees, graphs and other types of symbolic data structures. This method is aplied to several algorithms; consequently, the peformance is improved by a fator of ten on a Hitachi S-810.

研究テーマ紹介: 論理 / 記号 ベクトル処理

キーワード: 記号処理ベクトル化, ベクトル記号処理, 並列記号処理, スーパーコンピューティング, スーパー記号処理, 並列処理, ベクトル処理
(C) 2007 by Yasusi Kanada
Powered by
Movable Type 3.36