[ Japanese Version ] [ English Version ] [ Edit this subsite ]

December 31, 2023

What's New

TowardProgrammingLinguistics.jpg

Keywords:

July 12, 2014

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

Kanada, Y., 2014 International Symposium on Flexible Automation (ISFA 2014), 2014-7.
[ 日本語のページ ]
[ Paper PDF file ]
[ Slides PDF file (w/o video) ]
[ Slides (Keynote file with video, for 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.

Introduction to this research theme: 3D shape formation technologies

Keywords:

July 7, 2014

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.
[ 日本語のページ ]
[ Paper PDF file ]
[ Paper PDF file (extended ver. for IWNC8 book) ]
[ Slides (reduced size) ]
[ Slides (with a movie, 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.

Introduction to this research theme: 3D shape formation technologies

Keywords:

July 5, 2014

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.
[ 日本語のページ ]
[ Paper PDF file not yet available ]
[ Slides PDF file not yet available ]

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.

Introduction to this research theme: Network virtualization

Keywords:

June 28, 2014

Developing Revolutionary 3D Design and Printing Methods

Kanada, Y., BIT’s 1st Annual International Congress of 3D Printing, Dalian, China, June 27-29, 2014.
[ 日本語のページ ]
[ Slides w/o movies (PDF) (old ver) ]
[ Full-set slides (for Keynote, 65 MB) (old ver) ]


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.



Introduction to this research theme:
Network virtualization

Keywords:

June 16, 2014

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.
[ 日本語のページ ]

[ Poster ]

Introduction to this research theme: Network virtualization

Poster:

Voting:

Session:

Keywords:

May 17, 2014

Controlling Network Processors by using Packet-processing Cores

Kanada, Y., 2nd International Workshop on Network Management and Monitoring (NetMM 2014), May 2014.
[ 日本語のページ ]
[ Paper PDF file ]
[ Slides PDF file ]

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.

Introduction to this research theme: Network virtualization

Keywords: Network processors, Multi core, Control processing, Packet processing, Network virtualization

May 13, 2014

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.
[ 日本語のページ ]
[ Paper PDF file ]
[ Slides ]

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.

Introduction to this research theme: Network virtualization

Keywords: 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.

February 21, 2014

FDM 3D-printing as Asynchronous Cellular Automata

Kanada, Y., 8th International Workshop on Natural Computing (IWNC 2014), 2014-3.
[ 日本語のページ ]
[ Slides ]

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.

Introduction to this research theme: 3D shape formation technologies

Keywords:

January 22, 2014

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

Kanada, Y., 19th International Symposium on Artificial Life and Robotics (AROB 2014), 2014-1.
[ 日本語のページ ]
[ Paper (updated after the symposium) ]
[ Slides ]

RIMG2281.jpgAbstract: 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.

Introduction to this research theme: 3D shape formation technologies

Keywords: 3D printing, Three-dimensional printing, Asynchronous cellular automata (CA), Randomness, Fluctuation, Solid Free-form Fabrication, SFF, Fused deposition modeling, FDM, Additive Manufacturing

November 13, 2013

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.
[ 日本語のページ ]
[ Paper PDF file ]
[ Slides ]

Abstract: 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.

Introduction to this research theme: Network virtualization

Keywords: Network-node plug-in architecture, Data plugin, Control plug-in, Network virtualization, Virtualization node, VNode, Virtual link, Network processors

September 9, 2013

A VNode Plug-in Architecture to Evolve VNode

Kanada, Y., and Tarui, T., Network Virtualization Symposium 2013, September 2013.
[ 日本語のページ ]

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: Network virtualization

IMG_3299.jpg

Keywords:

August 6, 2013

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

Kanada, Y., International SFF Symposium 2013, August 2013.
[ 日本語のページ ]
[ Poster content + explanation ]
[ Updated poster PDF file ]
[ Poster photo ]

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.

Introduction to this research theme: 3D shape formation technologies

Keywords: 3D printing, Three-dimensional printing, Solid Free-form Fabrication, SFF, Fused deposition modeling, FDM, Additive Manufacturing

July 19, 2013

Open, High-level, and Portable Programming Environment for Network Processors

Kanada, Y., IEICE 7th Network Virtualization SIG, July 2013.
[ 日本語ページ ]
[ Paper PDF file ]
[ Slides ]

Abstract: Network processors are used for high-performance programmable networks. However, programs for net- work processors are limited in portability and number of developers, so the development cost is high. To solve this problem, open, high-level, and portable programming language called “CSP” and a development environment called “+Net” have been developed. In this environment, high throughput can be obtained without programmers’ signifi- cant awareness of SRAM/DRAM distinction. A prototype using Cavium Octeon, a network processor, has been de- veloped, and it performs 7.5 Gbps or more in simple programs in an evaluation using part of the network virtualization platform.

Introduction to this research theme: Network virtualization

Keywords: Network processor, Programmability, Portability, SRAM, DRAM, Octeon, Network virtualization

June 2, 2013

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.
[ 日本語のページ ]
[ Paper PDF file ]
[ Slides ]

Abstract: 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.

Introduction to this research theme: Network virtualization

Keywords:

January 1, 2013

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.
[ 日本語のページ ]
[ Paper PDF file ]

Abstract: 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.

Introduction to this research theme: Network virtualization

Keywords: Resource isolation, Network virtualization, Virtual network, Per-slice shaping, Per-link policing, Weighted fair queuing, WFQ.

November 27, 2012

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.
[ 日本語のページ ]
[ Paper PDF file ]
[ Slides PDF file (1 slide per page) ]

Abstract: “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.

Introduction to this research theme: Network virtualization

Keywords: Clean network virtualization, Virtualization node, VNode, Modularity, Model-mapping separation, Packet data conversion

October 17, 2012

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

Kanada, Y., Shiraishi, K., and Nakao, A., IARIA Infocomp 2012, 2012-10-24.
[ 日本語のページ ]
[ Paper PDF file ]
[ ThinkMind Paper page ]
[ Slides PDF file ]

Abstract: 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.

Introduction to this research theme: Network virtualization

Keywords: network virtualization; virtual network; network accommodation; network-slice gateway; virtual switch; intraslice switching

Inter-Virtual-Node and Slice-to-External-Network Connection Function in the Network Virtualization Platform

Kanada, Y., Shiraishi, K., and Nakao, A., IEICE SIG on Information Networks, 2012-3-5.
[ 日本語のページ ]
[ Paper PDF file (in Japanese) ]
[ Slides PDF file (in Japanese) ]

Abstract: On the network virtualization platform that consists of multiple virtualization nodes (VNodes), multiple slices (virtual networks) can be operated simultaneously while isolated from other slices. Virtual nodes (node slivers) can be connected freely by using virtual links (link slivers) at up to 10-Gbps, and arbitrary protocol, which is not constrained by Ethernet or IP, can be used on the slice. VNodes implement virtual links on IP networks by using GRE tunnels. In addition, by using a network accommodation equipment (NACE, NC) that translates the packet data format to an external format, slices can be connected to external VLAN networks at up to 10-Gbps. This paper describes how such connections are referenced and defined by slice developers and how they are translated and physical communication is realized.

Introduction to this research theme: Network virtualization

Keywords: Network virtualization platform, Virtualization node, VNode, Slice, Virtual network, Node sliver, Link sliver, Network accommodation

July 6, 2012

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.
[ 日本語のページ ]
[ Paper PDF file ]
[ Slides PDF file ]

[ IEEExplore Paper page ]

Abstract: 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.

Introduction to this research theme: Network virtualization

Keywords:

March 6, 2012

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.
[ 日本語のページ ]
[ Paper PDF file ]
[ IEEExplore Paper page ]

Abstract: 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.

Introduction to this research theme: Network virtualization

Keywords: Network Virtualization

“Clean Virtualization” and Virtualization Node Architecture that Supports Independent Component-Evolution

Kanada, Y., and Nakao, A., 3nd IEICE SIG on Network Virtualization, 2012-3-2.
[ 日本語のページ ]
[ Slide PDF file (in Japanese) ]

(No paper is available.)

Abstract: In a collaboration project, the virtualization node (VNode) and the virtualization platform are developed. A feature of VNode is architecture that supports independent component-evolution. In this presentation, we propose clean-virtualization concept, and show that VNode realizes this concept, and that this concept is important to implement architecture that supports independent component evolution. In addition, we show the method of implementing the architecture and realizing the condept in VNode, especially the implementation of the architecture in the redirector, a part of VNode.

Introduction to this research theme: Network virtualization

Keywords: Network Virtualization

January 21, 2012

Network-resource Isolation for Virtualization Nodes

Yasusi Kanada, Kei Shiraishi, and Akihiro Nakao, COMSNETS 2012, 2012-1-6.
[ 日本語のページ ]
[ Paper PDF file ]
[ Poster PDF file ]
[ IEEExplore Paper page ]

Abstract: 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).

Introduction to this research theme: Network virtualization

Keywords:

November 11, 2011

Federation Method for Virtualization Platform without Federation Function

Yasusi Kanada and Toshiaki Tarui, 2nd IEICE SIG on Network Virtualization, 2011-11-10.
[ 日本語のページ ]
[ Slide PDF file (in Japanese) ]

(No paper is available.)

Abstract: In collaboration projects funded by NICT, we develop a mechanism of federation among the virtualization platform developed by the Virtualization Node Project and G-lambda, ProtoGENI, and other platforms. This mechanism enables generation and management of slices extending through the virtualization platforms. We presents a method for enabling federation without recreating the virtualization platform without federation function, but only by adding additional functions.

Introduction to this research theme: Network virtualization


Keywords: Network Virtualization

January 28, 2011

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.
[ 日本語のページ ]
[ Paper PDF file ]
[ IEEExplore Paper page ]

Abstract: 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.

Introduction to this research theme: Policy-based Networking

Keywords: Network Virtualization, Paging, Segmentation, Live migration

January 24, 2011

Address-Translation-Based Network Virtualization

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

[ 日本語のページ ]
[ Paper PDF file (C) IARIA ]
[ ThinkMind Paper page ]

Abstract: 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.

Introduction to this research theme: Policy-based Networking

Keywords: Network Virtualization, Segmentation, Paging, Network Address Translation, NAT, Extranet

December 17, 2010

Development Method and Experience of A Non-IP Proocol Using the Virtualization Nodes

Kanada, Y., and Nakao, A., IEICE Technical Committee on Internet Architecture (IA), 2010-12-17.

[ 日本語のページ ]
[ Paper PDF file (C) IEICE (in Japanese) ]

Abstract: The virtualization-node project at the National Institute of Information and Communications Technology (NICT) is developing 10-Gbps-class virtualization nodes (VNodes) that enables implementing non-IP protocols with any frame format using network-virtualization technology. In this project, because the VNodes have been introduced into the R & D test-bed network called JGN2plus, an important challenge is to improve usability for developers (JGN2plus users). There-fore, we developed and tested a non-IP protocol called IPEC (IP-Ether-Chimera) on the experimental network using the VNodes, described the procedure and experiments, and extracted the problems and knowhow concerning usability. A problem to solve is to develop methods for avoiding careless mistakes by developers, and an obtained knowledge is that a combination of a small-scale experiment using connected several Linux PCs and a scaled-up experiment on wide-area network reduced the complexity of the development. This experiment did not need wide bandwidth, but this method will enable scaling up the experiment utilizing 10-Gbps bandwidth relatively easier.

Introduction to this research theme: Policy-based Networking

Keywords: Network virtualization, Non-IP protocol, Virtualization node, Address learning

September 4, 2010

Development of An Experimental Non-IP Protocol Using the Virtualization Nodes

Kanada, Y., and Nakao, A., IEICE Technical Committee on Information Networks (IN), 2010-9-2.

[ 日本語のページ ]
[ Paper PDF file (C) IEICE (in Japanese) ]

Abstract: In the National Institute of Information and Communications Technology (NICT), 10-Gbps-class virtualization nodes (VNodes) that enables implementing non-IP protocols with any frame format are developed using network-virtualization technology. We have developed an experimental non-IP protocol called IPEC (IP Ether Chimera) on a virtual network us-ing the VNodes. In IPEC, the nodes learn addresses that can be hierarchical such as IP addresses using an algorithm that extends Ethernet switch learning algorithm. IPEC has the following features. First, IPEC realizes a simple single-layer non-IP protocol that has features of both Ethernet and IP. Second, because a group is the unit of learning in IPEC, it is more scalable than Ethernet, and mobile groups can be more efficiently learned. Third, this forwarding algorithm can be used in networks with loops and it can forward packets during failure using an alternative route. Group IDs can be used as locators, so IPEC can be regarded to realize an architecture that extends ID/Locator separation architecture. We implemented IPEC on VNodes, and confirmed that it enabled group learning and group mobility by experiments.

Introduction to this research theme: Policy-based Networking

Keywords: Network virtualization, Non-IP protocol, Virtualization node, Address learning, ID/Locator separation, Mobility

July 18, 2009

Fine-grained Full-text Search

Yasusi Kanada, Not yet published, 1998.

[ Paper PDF file ]
[ Paper PostScript file ]

Abstract: Most conventional text retrieval methods are designed to search for documents. However, users often do not require documents themselves, but are searching for spe-cific information that may come from a large collection of texts quickly. To satisfy this need, we have developed a model and two methods for fine-grained searching. The unit of search in this model is called an atom, and it can be a sentence or smaller syntactic unit. A score, i.e., a relevance value, is defined for each atom and for each query, and the score is propagated between atoms. By using the two methods, excerpts from texts surrounding the search-result items and/or hyperlinks to the document parts that include the items are displayed. Multiple topics in a document can be separately listed in a search result. Evaluation of two prototypes, using a conventional full-text search engine as is or with only a small modification, has demonstrated that these methods are feasible and can decrease the search cost in terms of time and effort for users.

Introduction to the research theme: Axis-Specified Search (Thematic Search)

Keywords: Text search, Fine-grained search, Passage retrieval

May 21, 2009

Prototype Development of A Network Control Mechanism That Satisfies Requests on User-level Communication Quality

Kanada, Y., IEICE Technical Committee on Information Networks (IN), 2009-5-21.

[ 日本語のページ ]
[ Paper PDF file (C) IEICE ]

Abstract: A mechanism for users to input a request on quality of experience (QoE) and for the network to satisfy the request. A QoE request is mapped to QoS, and it is satisfied by using admission control and network node configurations. By using a soft-state protocol for the request, service initiation, extension, and termination are handled in a unified method. Part of this mechanism has been built into a prototype, and tested using a network node with so-called hierarchical shaper and using video streaming, the mechanism has been confirmed to work in a designed way.

Introduction to this research theme: Policy-based Networking

Keywords: QoE Optimization, Quality of Experience, QoS Guarantee, Minimum Bandwidth Guarantee, Soft-state Protocol, Hierarchical Shaper

May 20, 2009

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. [The presentation was canceled because of the new type of influenza.]

[ 日本語のページ ]
[ Paper PDF file ]
[ IEEExplore Paper page ]

Abstract: 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.

Introduction to this research theme: Policy-based Networking

Keywords: CAC, Admission Control, Traffic Measurement, QoS Guarantee, DiffServ, Differentiated Services, Network Dynamics

April 20, 2009

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

Kanada, Y., IEICE Technical Committee on Network Systems (NS), 2009-4-16.

[ 日本語のページ ]
[ Paper PDF file ]

Abstract: A method of admission control based on both resource requests by applications and traffic measurement results per DiffServ class using NetFlow was developed. Several experiments using a newly-developed policy-server prototype using this method and simulated voice traffic showed that bandwidth usage can be improved and call blocking ratio was decreased with low measurement load by using this method. Interesting but possibly harmful dynamics were observed by simulations using simulated traffic that follows an on/off model; i.e., this admission control method may cause oscillation or long-term development that lasts for 100 to 150 minutes, and it may also cause bandwidth overshooting. The range of parameters, with which such phenomena can be properly suppressed and the admission control correctly works, was experimentally obtained.

Introduction to this research theme: Policy-based Networking

Keywords: CAC, Admission Control, Traffic Measurement, QoS Guarantee, DiffServ, Differentiated Services, Network Dynamics

January 3, 2008

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.
[ 日本語のページ ]
[ Paper PDF file ]
[ IEEExplore Paper page ]

Abstract: 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.

Introduction to this research theme: Policy-based Networking

Keywords: QoS measurement,QoS guarantee,DiffServ,On-path signaling,QoS feedback

November 30, 2007

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

Kanada, Y., not yet published (April 2008).

[ 日本語のページ ]
[ 論文 PDF ファイル ]

Abstract: 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.

Keywords: NGN, Next-generation backbone, QoS measurement, QoS guarantee, DiffServ, Bandwidth sharing, WFQ.

September 11, 2007

Design and Prototyping of a QoS Guarantee Method Based on Path-Coupled Signaling

Kanada, Y., IEICE Communication Society Convention, 2007.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ]

Currently no abstract is available.

Introduction to this research theme: Policy-based Networking

Keywords:

August 9, 2007

Subjective Evaluation of voiscape – A Virtual “Sound Room” Based Communication-Medium

Kanada, Y., Technical Committee on Electrical Acoustics (EA), Information and Communication Engineers (IEICE), EA2007-42, August 2007.

[ 日本語のページ ]
[ Paper PDF file (updated after the SIG) (in Japanese) ]
[ Paper PDF file (draft) (in Japanese) ]

Abstract: Voiscape is a communication medium by which people can talk each other while moving within virtual sound space freely. By using a prototype of voiscape called VPIIQ (Voiscape Prototype II Q), the effect of difference of QoS caused by network policies was evaluated subjectively. The result showed unexpectedly that the percentage of correct answers was higher in the case in which QoS is lower in the localization test. In the sound localization tests, the percentage of correct answers was higher when subjects performed operations to move or to turn than not to do so. However, in the speaker recognition tests, opposite results were observed.

Introduction to this research theme: voiscape

Keywords: IP telephony, Voice communication, voiscape, Spatial audio, 3D sound, Virtual sound space, Quality of Experience, QoE evaluation

July 13, 2007

Development and Evaluation of an End-to-End QoS Guarantee Method Based on Path-Coupled Signaling

Kanada, Y., IEICE Technical Committee on Communication Quality (CQ), Technical Reports, July 2007.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ]

Abstract: A method for scalable QoS guarantee, in which QoS requirements are signaled by using a protocol similar to RSVP or NSLP and are aggregated in backbones, has been developed and prototyped. The requirements are propagated to the policy server by using policy-based routing and a policy outsourcing protocol. The policy server estimates the amount of traffic and controls the bandwidth sharing among the queues (WFQs) of the backbone routers. The effect of core traffic control has been evaluated by using an L3-switch GS4000 and bursty traffic generated by the MMPP model. The results showed that, if there are many conversational video and streaming traffics, the QoS requirements of both types of traffic can be satisfied by relatively increasing the weight of the former than that of the latter in some cases.

Introduction to this research theme: Policy-based Networking

Keywords: NGN, Next generation backbone, QoS measurement, QoS guarantee, Diffserv, Bandwidth sharing, WFQ.

November 6, 2005

Simulated Virtual Market Place By Using voiscape Communication Medium

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

[ 日本語のページ ]
[ Paper PDF file ] [ Poster PDF File ]

Abstract: 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 dis-tance 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 vois-cape prototype called VPII is used for realizing such an environ-ment. 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 partici-pants can virtually walk among them and can selectively listen one voice or hear multiple voices at once.

Introduction to this research theme: voiscape

Keywords: voiscape, Demonstration, Virtual communication space, Virtual communication place, Virtual market place, Virtual place, Virtual space, Multi-voice conversation, Voice communication

September 27, 2005

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.

[ 日本語のページ ]
[ Short paper PDF paper ] [ Poster PDF paper ] [ Unpublished full paper PDF v ]

Abstract: 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.

Introduction to this research theme: voiscape

Keywords: SIMPLE, SIP, Session Initiation Protocol, voiscape, Conference room management, Sound room management

June 24, 2005

Computation of Spatialization and Reverberation For A Virtual "Sound Room" Based Communication-Medium Called voiscape

Kanada, Y., Technical Committee on Electrical Acoustics (EA), Information and Communication Engineers (IEICE), June 2005.

[ 日本語のページ ]
[ Paper PDF file ] [ OHP PDF file ]

Abstract: We are developing a communication medium called voiscape, which enables taking to people while selecting persons to talk by moving in a virtual "sound room". In the second prototype of voiscape called VPII, the FIR Method is used for low-delay HRTF filtering, the sound room - the range of motion - is identified with the room in acoustical cal-culation, and early reflections by the sound room walls are simulated. The early reflections produce out-of-head sound lo-calization and sound distance expression. We also implemented motion-tracking and interpolation algorithms into the spatialization method. VPII enabled a voice communication environment, in which speaker identification is easy, multiple conversation-contexts can be created in a room, and motions of users and objects in a sound room are natural and causes only small noises.

Introduction to this research theme: voiscape

Keywords: HRTF, Head-Related Transfer Function, voiscape, Early reflection, Reverberation, Virtual-motion tracking, Feeling of distance, Out-of-head localization, Virtual communication space, Virtual communication place, Virtual place, Voice communication, Spatial audio, 3-D audio, 3D audio, 3-dimensional audio, Three-dimensional audio, Spatial sound, 3-D sound, 3D sound, 3-dimensional sound, Three-dimensional sound

June 13, 2005

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.

[ 日本語のページ ]
[ Paper PDF file ] [ OHP PDF file ]

Abstract: 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 represented 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.

Introduction to this research theme: voiscape

Keywords: Conference room management, Early reflection, Motion tracking, Reverberation, SIMPLE, SIP, Session Initiation Protocol, Sound room management, voiscape, Virtual-motion tracking, Virtual communication space, Virtual communication place, Virtual space, Virtual place, Voice communication, Multi-voice conversation, Spatial audio, 3-D audio, 3D audio, 3-dimensional audio, Three-dimensional audio, Spatial sound, 3-D sound, 3D sound, 3-dimensional sound, Three-dimensional sound

November 8, 2004

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

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

[ 日本語のページ ]
[ Paper PDF file ] [ OHP PDF file ]

Abstract: 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.

Introduction to this research theme: voiscape

Keywords: Conference room management, Sound room management, voiscape, Virtual communication space, Virtual communication place, Virtual space, Virtual place, Multi-voice conversation, Voice communication, Spatial audio, 3-D audio, 3D audio, 3-dimensional audio, Three-dimensional audio, Spatial sound, 3-D sound, 3D sound, 3-dimensional sound, Three-dimensional sound, JMF, Java, Java 3D, Java Media Framework

March 5, 2004

An Implementation of a Virtual "Sound Room" Based Communication-Medium Called Voiscape Using JMF and Java 3D

Kanada, Y., Distributed Processing Systems SIG, Information Processing Society of Japan, March 2004.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ OHP PDF file (in Japanese) ]

Abstract: The author researches toward establishing voice communication media called voiscape which shall replace telephone. A virtual "sound room" that is created by spatial audio technology is used in voiscape. We developed a prototype on PCs, in which 3-D graphic is used for supplementing spatial autio. In this prototype, JMF (Java Media Framework) was used for voice capturing and communication, and Java 3D was used for spatial audio and 3-D graphics. Before the development, the author had believed that the basic functions required for the prototype would be realized by connecting these APIs. However, in fact, they cannot be connected directly, so we used OpenAL through the interface of Java 3D. We also encountered problems of sound quality degradation and delay, but they have been almost solved by refining the program by trial and error.

Introduction to this research theme: voiscape

Keywords: JMF, Java, Java 3D, Java Media Framework, OpenAL, Open AL, voiscape, Sound room, Spatial audio, 3-D audio, 3D audio, 3-dimensional audio, Spatial sound, 3-D sound, 3D sound, 3-dimensional sound, Three-dimensional sound, Voice communication, Multi-voice conversation

October 8, 2003

A Virtual "Sound Room" Based Communication-Medium Called Voiscape

Kanada, Y., Technical Committee on Multimedia and Virtual Environment (MVE), Information and Communication Engineers (IEICE), October 2003.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ OHP PDF file (in Japanese) ]

Abstract: The concept of a new communication medium called voiscape is proposed. A virtual "sound room" that is based on the spatial audio technology is shared among the users in voiscape, and a person can move freely in the room, can meet and depart from other people, and can talk with two or more persons by using voiscape. By enabling transmission of presence and peripheral information, voiscape will cover from a telephone-style one-to-one conversation to a variety of communication types that are impossible in conventional media, and will enable sharing the feeling of connection and releaf and sharing tacit knowledge. This paper describes usage scenes and a procedure of voiscape and also describes a PC-based prototype. In this prototype, the user can confirm the situation in front by 3D graphics, and can move around the room by using a mouse.

Introduction to this research theme: voiscape

Keywords: Conference room management, Sound room management, voiscape, Virtual communication space, Virtual communication place, Virtual space, Virtual place, Multi-voice conversation, Voice communication, Spatial audio, 3-D audio, 3D audio, 3-dimensional audio, Three-dimensional audio, Spatial sound, 3-D sound, 3D sound, 3-dimensional sound, Three-dimensional sound

October 6, 2003

Policy-Based Session Control in a Virtual "Sound Room" Based Communication-Medium Called Voiscape

Kanada, Y., Technical Committee on Internet Architecture (IA), Information and Communication Engineers (IEICE), October 2003.

[ 日本語のページ ]
[ Paper PDF file ] [ OHP PDF file ]

Abstract: As part of research toward establishing voice communication media that shall replace telephone, we developed an architecture and a prototype of a continuously-connected multi-user communication medium called voiscape. A virtual "sound room" that is created by spatial audio technology is used in voiscape. When the user moves within the sound room by using a mouse, the presence information including the position in the room is distributed to other users of the room. If the user becomes closer to or more distant from another user, the communication session begins or ends automatically by using SIP according to predefined policy stored in the terminals. This policy-based session control enables privacy protection and reduction of communication. When a local site requires a session start, the remote site often requires a session start concurrently, so a method of establishing a connection without connecting doubly nor becoming busy was deviced.

Introduction to this research theme: voiscape

Keywords: voiscape, Voice communication, Multi-voice conversation, Virtual presence information, SIP, Session Initiation Protocol, Policy-based session control, Privacy protection, Virtual communication space, Virtual communication place

September 1, 2003

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.

[ 日本語のページ ]
[ JNSM Issue Web Page ] [ Paper PDF file (draft) ]

Abstract: 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 connections 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 control 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 specifying 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 described, and we concluded that there are five advantages of building-block-based policies, i.e., expressibility, uniform 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.

Introduction to this research theme: Policy-based Networking

Keywords: Policy-based networking, Policy-based management, Component-based policy, Policy components, Policy combination, Policy division, Policy fusion, Published paper, QoS policy, Diffserv policy, Network policy

February 1, 2003

Great Works of 20 C.: Robert W. Floyd: Nondeterministic Algorithms

Kanada, Y., Information Processing, vol. 44, No. 2, 2003.


[ 日本語のページ ]

Keywords: Nondeterministic algorithm

June 5, 2002

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.
[ 日本語のページ ]
[ Paper PDF file ] [ OHP PDF file ]
[ IEEExplore Paper page ]

要約: 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.

Introduction to this research theme: Policy-based Networking

Keywords: Policy-based networking, Policy-based management, Extensible policy system, General-purpose policy server, PxP, DEPS

May 14, 2002

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.

[ 日本語のページ ]
[ Paper PDF file ] [ OHP PDF file ]

Abstract: 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.

Introduction to this research theme: Policy-based Networking

Keywords: Policy-based networking, Policy-based management, Component-based policy, Policy components, Policy combination, Policy division, Policy fusion, Component-based policy, Published paper, QoS policy, QoS assurance, QoS guarantee, Virtual flow label

March 27, 2002

Technical Direction of Policy-based Management Focused on IETF Standization

Kanada, Y., Information and Communication Engineers (IEICE) Yearly Conference,2002-3.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ OHP PDF file (in Japanese) ]

Abstract: (Not available)

Introduction to this research theme: Policy-based Networking

Keywords: IETF, Policy-based management, Tutorial

March 1, 2002

Diffserv Policies and Their Combinations in a Policy Server Called PolixyXpert

Kanada, Y., and O'Keefe, B. J., SIG Information Networks & SIG Network Systems, Institute of Electronics, Information and Communication Engineers (IEICE), March 2002.

[ 日本語のページ ]
[ Paper PDF file ] [ OHP PDF file ]

Abstract: In policy-based networking, policies sometimes have to be combined and applied in cooperation to represent such programmable and customizable network functions as Diffserv. For a policy server called PolicyXpert, we have designed and implemented three types of policies and three types of virtual flow labels (VFLs) to connect the policy rules. The policy combination enables the representation of complex Diffserv policies. Policy combination also allows sub-classing of DSCP-based service classes, and the separation of service and subscriber policies. The careful design of Diffserv policies has enabled simple Diffserv policies to be represented in a simple form.

Introduction to this research theme: Policy-based Networking

Note: PolicyXpert is a trademark of Hewlett Packard Company.

Keywords: Diffserv policy, Policy-based management, Published paper, QoS policy, Virtual flow label, Component-based policy, Policy components, Policy combination, General-purpose policy server, Network policy

September 26, 2001

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)

[ 日本語のページ ]
[ Paper PDF file ] [ Unpublished paper PDF file ]

Abstract: 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.

Introduction to this research theme: Policy-based Networking

Note: OpenView and PolicyXpert are trademarks of Hewlett Packard Company. JP1 is a trademark of Hitachi Ltd.

Keywords: Diffserv policy, Policy-based management, Component-based policy, Policy components, Policy combination, Published paper, QoS policy, Virtual flow label, General-purpose policy server

May 14, 2001

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.

[ 日本語のページ ]
[ Paper PDF file ] [ OHP PDF file ]
[ IEEExplore Paper page ]

Abstract: 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.

Introduction to this research theme: Policy-based Networking

Keywords: Policy-based networking, Policy-based management, Policy division, Component-based policy, Policy components, Policy combination, Policy fusion, Policy combination, Policy server, Flow classifier

January 29, 2001

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.

[ 日本語のページ ]
[ Paper PDF file ] [ OHP PDF file ]

Abstract: 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.

Introduction to this research theme: Policy-based Networking

Keywords: Component-based policy, Policy components, Policy combination, Policy-based management

October 20, 2000

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

Kanada, Y., IEICE SIG on Information Network, Technical Reports, 100-378, IN 2000-102, pp. 47-54, October 2000.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ]

Abstract: 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.

Introduction to this research theme: Policy-based Networking

Keywords: Component-based policy, Policy components, Policy combination, Label-connection architecture, Pipe-connection architecture, Policy-based management

October 16, 2000

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.

[ 日本語のページ ]
[ Paper PDF file ] [ OHP PDF file ]

Abstract: 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.

Introduction to this research theme: Policy-based Networking

Keywords: Component-based policy, Policy components, Policy combination, Label-connection architecture, Pipe-connection architecture, Policy-based management

June 5, 2000

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.

[ 日本語のページ ]
[ Paper PDF file ] [ OHP PDF file ]
[ IEEExplore Paper page ]

Abstract: 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.

Introduction to this research theme: Policy-based Networking

Keywords: Component-based policy, Policy components, Policy combination, Policy-based management, QoS policy, Network policy

February 1, 2000

Rule-based Modular Representation of QoS Policies

Kanada, Y., IEICE Networking Architecture Workshop 10th Annual Workshop, pp. 106-113, IEICE, 2000.

[ 日本語のページ ]
[ Paper PDF file ] [ OHP PDF file in Japanese ] [ OHP PDF file in English ]

Abstract: 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.

Introduction to this research theme: Policy-based Networking

Keywords: Policy-based management, Policy-based network management, QoS policy, COPS, Common Open Policy System

November 7, 1999

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.

[ 日本語のページ ]
[ Local textual version ] [ Slides used in 46th IETF: Configuration Management BOF, Diffserv WG, and RAP WG (not recommended) ]

Abstract: 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].

Introduction to this research theme: Policy-based Networking

Keywords: IETF, Internet draft, Management Information Base, QoS MIB, Virtual flow label, SNMP, Simple Network Management Protocol

November 2, 1999

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

[ 日本語のページ ]
[ Paper PDF file (ACM DL)] [ Paper PDF file ]

Abstract: 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.

Introduction to this research theme: Axis-Specified Search (Thematic Search)

Keywords: Text search, Axis-specified search, Encyclopedia search, Thematic mapping search, Thematic geographical name search, Area-axis search, Geographical information extraction, Geographical name extraction, Information organization, Search result organization, Organizing search, Search result structurization, Structurizing search

September 28, 1999

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

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

[ 日本語のページ ]
[ Paper PDF file ] [ Paper PostScript file ]

Abstract: 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.

Introduction to this research theme: Axis-Specified Search (Thematic Search)

Keywords: Text search, Axis-specified search, Thematic chronological search, Year-axis search, Time-axis search, Encyclopedia search, Chronological information extraction, Information organization, Search result organization, Organizing search, Search result structurization, Structurizing search

September 1, 1999

The Functions and Implementation Method of "Thematic Mapping Search" in "Net-de-hyakka"

Kanada, Y., Yamazaki, M., Sawada, M., Hirano, Y., and Fujii, Y., 59th National Conference,3P-9, 1999, Information Processing Society of Japan (published by IPSJ)

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ]

Abstract: In the member's only network called "Net-de-hyakka", a service called the thematic mapping search, in which results of encyclopedia text search is ordered along a geographical axis, is offered. In this search, the statements are searched and sorted by geographical names that occur in the text. A map of one of the geographical names can also be opened. The function and implementation method of this search are summarized here.

Introduction to this research theme: Axis-Specified Search (Thematic Search)

Keywords: Text search, Axis-specified search, Thematic geographical search, Geographical-axis search, Encyclopedia search, Net-de-hyakka, Thematic Mapping Search

A Method of Geographical Name Extraction from Japanese Encyclopedia for Text Search in which the Results are Ordered by Geographical Areas

Kanada, Y., IPSJ SIGNL Technical Report, 99-NL-132-2, 1999, Published by IPSJ (in Japanese).

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper PostScript file (in Japanese) ]

Abstract: A text retrieval method called the thematic mapping search method has been developed for Japanese texts. In this method, the user specifies a search theme using free words, then obtains a sorted list of excerpts and hyperlinks to 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 when applied to the World Encyclopedia. The rules for information extraction 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.

Introduction to this research theme: Axis-Specified Search (Thematic Search)

Keywords: Text search, Axis-specified search, Area-axis search, Thematic mapping search, Thematic geographical name search, Geographical information extraction, Geographical name extraction, Encyclopedia search

June 1, 1999

Methods of Extracting and Representing Year References from an Encyclopedia for Chronological-table-generating Text Searching

Kanada, Y., IPSJ SIGFI Technical Report, 99-FI-?, 1999, Published by IPSJ (in Japanese).

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper PostScript file (in Japanese) ]

Abstract: A method of textual information retrieval, which is called the thematic chronological-table search method, has been developed. In this method, an index is generated by extracting and collecting year references from a text collection, the index and a statement-by-statement full-text index are used for searching for year references and search words when the user inputs the words, and the result items are sorted by year and displayed. The result item contains a year reference, a sentence that contains the year, and a hyperlink to the original text. In this paper, the method of information extraction in the thematic chronological-table searching is explained. This method has been applied to a Japanese encyclopedia. An evaluation shows the precision of extraction is higher than 99% in most cases. An efficient and less error-prone data representation for year expression that may contain several units such as century, year, month, day, and so on, are also explained.

Introduction to this research theme: Axis-Specified Search (Thematic Search)

Keywords: Text search, Axis-specified search, Thematic chronological search, Year-axis search, Time-axis search, Information extraction, Information organization, Encyclopedia search, Search result organization, Organizing search, Search result structurization, Structurizing search

March 1, 1999

A Method of Geographical Name Extraction from Japanese Encyclopedia for Text Search in which the Results are Ordered by Geographical Areas

Kanada, Y., Hirano, Y., Sawada, M., Yamazaki, M., and Fujii, Y., 58th National Conference of the Information Processing Society of Japan, 1J-3, 1999, Published by IPSJ (in Japanese).

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper PostScript file (in Japanese) ]

No abstract available.

Introduction to this research theme: Axis-Specified Search (Thematic Search)

Keywords: Text search, Axis-specified search, Thematic geographical search, Area-axis search, Encyclopedia search, Newspaper article search, Newspaper search, Geographical information extraction, Geographical name extraction, Information organization, Search result organization, Organizing search, Search result structurization, Structurizing search

November 1, 1998

Axis-specified Search: A Full-text Search Method for Extracting and Ordering Excerpts from Documents

Kanada, Y., IPSJ SIGFI Technical Report 98-FI-50-4, pp. 25-32, 1998, Published by IPSJ (in Japanese).

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper PostScript file (in Japanese) ]

Abstract: A full-text search method, which is called an axis-specified search method, is proposed. Excerpts are extracted from documents and ordered by using this method. The user selects an axis, such as year, area or quantity, from a menu, in addition to typing strings to be searched. Then, excerpts related to the axis and strings, and hyperlinks to the original sentences are ordered along the axis and displayed. 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 encyclopedia and a newspaper articles. 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 "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.

Introduction to this research theme: Axis-Specified Search (Thematic Search)

Keywords: Text search, Axis-specified search, Year-axis search, Time-axis search, Area-axis search, Quantity-axis search, Encyclopedia search, Newspaper article search, Newspaper search, Quantity information extraction, Information organization, Search result organization, Organizing search, Search result sorting, Search result structurization, Structurizing search

June 27, 1998

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.

[ 日本語のページ ]
[ Paper PDF file (ACM DL)] [ Paper PDF file ] [ Paper PostScript file ]

Abstract: 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.

Introduction to this research theme: Axis-Specified Search (Thematic Search)

Keywords: Text search, Axis-specified search, Year-axis search, Time-axis search, Area-axis search, Quantity-axis search, Encyclopedia search, Information extraction, Information organization, Search result organization, Organizing search, Search result sorting, Search result structurization, Structurizing search

January 1, 1998

Memory device & I/O device

Articles "Memory device" and "I/O device" in Heibonsha's World Encyclopedia (in Japanese).

[ 日本語のページ ]

Keywords:

November 1, 1997

Web Pages That Reproduce Themselves by JavaScript

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

[ 日本語のページ ]
[ Paper PDF file (updated) ]
[ Paper PDF file (original) ]

Abstract: 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.

Introduction to this research theme: Self-reproduction of Web pages

Keywords: Self-reproduction, Programming language, JavaScript

July 1, 1997

Web Pages That Reproduce Themselves by JavaScript

Kanada, Y., IPSJ Summer Programming Symposium, separated (105-112), July, 1997. (in Japanese)

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ]

Abstract: 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.

Introduction to this research theme: Self-reproduction of Web pages

Keywords: Self-reproduction, Programming language, JavaScript

February 1, 1996

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.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ Paper DVI file (except figures) (in Japanese) ] [ Figures in EPSF format : 1, 2, 3, 4, 5, 6, 7, 8 ]

Abstract : 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.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Constraint satisfaction problem, Parallel processing, Randomized computation, Randomized problem solving

January 1, 1996

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

Kanada, Y., not yet published, 1996.

[ 日本語のページ ]
[ Paper PDF file ] [ Paper postscript file ]

Abstract: 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.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Constraint satisfaction problem, Neural networks, Randomized computation, Randomized problem solving, Annealing, Rule-based computation, Rule-based problem solving, FAM, Frustration accumulation method

Constraint Satisfaction by Parallel Optimization of Local Evaluation Functions with Annealing

Kanada, Y., Unpublished, 1996.

[ 日本語のページ ]
[ Paper PDF file ] [ Paper postscript file ]

[ Several constraint satisfaction problem demos in Java (You can change catalysts, rules, and frustration.) ]

Abstract: 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.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Constraint satisfaction problem, Parallel Processing, Randomized computation, Randomized problem solving, Annealing, Rule-based computation, Rule-based problem solving, Function optimization, Local information, Localized computation, Local evaluation function, FAM, Frustration accumulation method

November 1, 1995

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.

[ 日本語のページ ]
[ Paper PDF file] [ Paper postscript file]
[ IEEExplore Paper page ]

Abstract : 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.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Combinatorial optimization, Integer programming, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Annealing

October 1, 1995

Combinatorial Problem Solving Using Randomized Dynamic Tunneling on A Production System

Kanada, Y., IEEE Systems, Man and Cybernetics '95, (C) Copyright 1995 by IEEE.
[ 日本語のページ ]
[ Paper PDF file] [ Paper postscript file]
[ IEEExplore Paper page ]

Abstract : 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.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Combinatorial optimization, Integer programming, Emergent Computation, Randomized computation, Randomized problem solving, Tunneling, Rule-based computation, Rule-based problem solving

August 1, 1995

Large-scale Constraint Satisfaction Using Local-information-based Annealing and Its Parallel Processing -- An Application of Emergent Computation Model CCM --

Kanada, Y., SWoPP '95 (SIG Note of Artificial Intelligence, Information Processing Society of Japan), AI95-16, pp. 17-24, 1995, Published by IPSJ

[ 日本語のページ ]
[ Paper postscript file]

Abstract: A method for solving large-scale constraint satisfaction problems based on CCM (Chemical Casting Model), which is a model for emergent computation, is proposed in this report. A parallelized version of this method is also shown. Large-scale problems could not be solved using CCM. However, this report shows that, by introducing a method of annealing called FAM (Frustration Accumulation Method) and by adjusting the parameters appropriately, several large-scale graph coloring problems has become solvable with spending the same order of time as GSAT or simulated annealing by sequential processing using CCM. This report also shows that this method can easily be parallelized with restricted amount of mutual exclusion. The performance is almost proportional to the number of processors under certain conditions.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Constraint satisfaction problem, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Local information, Localized computation, Local evaluation function

June 1, 1995

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

Kanada, K., Fuzz-IEEE/IFES '95, pp. 2319-2326, 1995.
[ 日本語のページ ]
[ Paper PDF file. (C) Copyright 1995 by IEEE]
[ Paper postscript file. (C) Copyright 1995 by IEEE]
[ IEEExplore Paper page ]

Abstract: 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.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Fuzzy constraint satisfaction, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving

January 1, 1995

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

Kanada, Y., not yet published, 1995.

[日本語のページ ]
[ Paper PDF file ] [ Paper postscript file ]

Abstract: 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.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Parallel processing, Combinatorial optimization, Constraint satisfaction problem, Traveling salesperson problem, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving

December 1, 1994

CCM: A Model Based on Analogies to Chemical Reaction System for Open and Complex Computation -- Its Relation to the Interlocked Neural Networks --

Kanada, Y., 5th National Conference, Japan Neural Network Society, pp. 36-39, 1994, Published by JNNS.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file: Part 1, Part 2 (in Japanese) ]
[ OHP PDF file: Slides, Handout ] [ OHP postscript file: Slides, handout ]

Abstract: 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.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Emergent Computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving

October 1, 1994

A Method of Independent Parallel Processing of Constraint Satisfaction and Other Problems using CCM: A Model for Emergent Computation

Kanada, Y., 49th National Conference, Information Processing Society of Japan, 4-321 - 322, 1994, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file: Part 1, Part 2 (in Japanese) ]
[ OHP postscript file: Slides, Handout ] [ OHP PDF ファイル: Slides, Handout ]

Abstract: A computation model called CCM was proposed by the author. CCM is developed toward establishing a problem solving methodology based on emergent computation, which is open to continually varying environment. CCM is a production system with evaluation functions, which are computed using only local information, and CCM works randomly. A computational language called SOOC-94 is used for experiments based on CCM. The features and implementation of SOOC-94 are explained using the magic square problem as an example. The features of SOOC-94 are that the automatic computation of evaluation functions and automatic local backtracking are taken place when applying a rule, that the syntax of the patterns in LHS and RHS are almost unified, the existence of two scheduling strategies, especially the random strategy, on the order of rule applications, that the existence of same name elements in a datum (structure) is allowed, and so on.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, SOOC, Computation language, Constraint satisfaction problem, Combinatorial optimization, Emergent Computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Parallel processing

September 1, 1994

The Features and Implementation of SOOC: A Language for Emergent Computation -- Using the Magic Square Problem for An Example --

Kanada, Y., SIG Note of Symbol Processing, Information Processing Society of Japan, 94-SYM-75-5, pp. 31-38, 1994, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ OHP postscript: Slides, Handout ]
[ OHP PDF ファイル: Slides, Handout ]

[ Magic square demo in Java ]

Abstract: A computation model called CCM was proposed by the author. CCM is developed toward establishing a problem solving methodology based on emergent computation, which is open to continually varying environment. CCM is a production system with evaluation functions, which are computed using only local information, and CCM works randomly. A computational language called SOOC-94 is used for experiments based on CCM. The features and implementation of SOOC-94 are explained using the magic square problem as an example. The features of SOOC-94 are that the automatic computation of evaluation functions and automatic local backtracking are taken place when applying a rule, that the syntax of the patterns in LHS and RHS are almost unified, the existence of two scheduling strategies, especially the random strategy, on the order of rule applications, that the existence of same name elements in a datum (structure) is allowed, and so on.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, SOOC, Computation language, Emergent computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Production rule, Production system, Local evaluation function, Magic square

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

Kanada, Y., not yet published, 1994.

[ 日本語のページ ]
[ Paper PDF file] [ Paper postscript file]

Abstract: 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.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, SOOC, Computation language, Emergent computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving

August 1, 1994

Methods of Controling Locality in Problem Solving using CCM: A Model for Emergent Computation

Kanada, Y., SWoPP '94 (SIG Note of Artificial Intelligence, Information Processing Society of Japan), 94-AI-95-4, pp. 29-38, 1994, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ OHP postscript file: Slides, Handout ] [ OHP PDF ファイル: Slides, Handout ]

[ Several constraint satisfaction problem demos in Java (You can change catalysts, rules, and frustration.) ]

Abstract: CCM (Chemical Casting Model) is a model of nondeterministic, or random, computation. CCM is developed toward establishing a problem solving methodology based on emergent computation, which is open to continually varying environment. Computation in CCM is based on local information. However, a solution cannot be found if the locality is at the limit. Thus, the locality of computation, especially computation of the evaluation functions, must be controlled properly, and the locality in the search space must be controlled properly not to fall into local optima. Four methods of controlling locality are shown in this report. They are addition or removal of catalysts, composition of reaction rules (or tunneling), simulated annealing (SA) and frustration accumulation method (FAM). We found that catalysts and FAM are effective in constraint satisfaction, but that the performance is worse than conventional methods when only using these methods in a case. We also found that tunneling, or dynamical composition of reaction rules, is effective in optimization.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Emergent computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Local information, Localized computation, Local evaluation function, Production system, Production rule, Local information, Localized computation, Local evaluation function, Graph coloring

July 1, 1994

The Effects of Randomness in Asynchronous 1D Cellular Automata

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


[ 日本語のページ ]
[ Paper PDF file ] [ Poster in hypertext format (not yet available) ]
[ Unpublished extended paper PDF file ]

Abstract: 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.

Introduction to this research theme: RACA: Randomized Asynchronous Cellular Automata

Keywords: Randomized cellular automaton, Asynchronous cellular automaton, Randomized cellular automata, Asynchronous cellular automata, Randomized computation, Rule-based computation

April 1, 1994

Dynamic Graph Coloring using CCM -- A Model for Emergent Computation

Kanada, Y., SIG Note of Parallel Procesing of Artificial Intelligence, The Society of Artificial Intelligence, SIG-PPAI-9401, pp. 7-12, 1994, Published by JSAI.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file: Part 1, Part 2 (in Japanese) ]
[ Poster postscript file: Part 1, Part 2 ]
[ Poster PDF file : Part 1, Part 2 ]

[ Coloring demo in Java (static coloring) ]

Abstract: Real world computing systems are complex systems that is open to the continually varying environment. Conventional software development methods inherently cannot deal such situations. CCM (Chemical Casting Model) is a model of nondeterministic, or random, computation, which is based on local information. CCM is developed toward establishing a software development methodology based on emergent computation. CCM is a production system with locally computed evaluation functions. A method of coloring vertices of dynamically changing graphs, or a method of radio-wave assignments to moving stations, by using SOOC -- a CCM-based computation language, is explained, and the results of experiments are shown in the present report. Dynamic coloring can be performed using the same production rule and evaluation function as static coloring, and the results can be evaluated using basically the same method and tools.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Dynamic constraint satisfaction problem, Emergent Computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving

Symbolic Random Tunneling Based on Composing Production Rules -- Constraint Satisfaction and Optimization Using Computation Model CCM --

Kanada, Y., SICE 14th SIG Systems Engineering Note, The Society of Instrument and Control Engineers, 45-52, 1994, Published by SICE.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file: Part 1, Part 2 (in Japanese) ]

[English abstract is not available.]

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Constraint satisfaction problem, Combinatorial optimization, Emergent Computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Tunneling

January 1, 1994

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), 82-91, 1994.

[ 日本語のページ ]
[ Paper PDF file, (C) Copyright by IEEE ]
[ Paper in hypertext format (Figures are not available now) ]
[ Paper postscript file, (C) Copyright by IEEE ]
[ OHP postscript file: Slides, Handout ] [ OHP PDF file: Slides, Handout ]
[ IEEExplore Paper page ]

[ N queens problem and sort demo in Java ]

Abstract: 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.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Constraint satisfaction problem, Emergent Computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Local information, Localized computation, Stochastic process, Local evaluation function, Production system, Production rule

November 1, 1993

Various Sorting Methods by CCM, a Computational Model Based on Production Rules and Local Evaluation Functions

Kanada, Y., SIG Notes on Symbol Processing, Information Processing Society of Japan, 93-SYM-71-5, pp. 33-40, 1993, Published by IPSJ

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ OHP postscript file: Slides, Handout ]
[ OHP PDF file: Slides, Handout ]

[ Sort and N queens problem demo in Java (Only one type of sorting) ]

Abstract: The author has proposed the Chemical Casting Model (CCM), which is a stochastic computation model whose elements are production rules and evaluation functions that are computed only using local information, and has proposed a computation language SOOC based on CCM. This model is targeted to apply to problems on open systems in which even specifications cannot be clearly written down. However, it is also important to make experiment on applying this model to conventional problems. Thus, CCM is applied to sorting in this paper, and a new sorting method is presented and several sorting methods based on conventional methods, i.e., insertion sort and exchange sort, are presented. The results of experiments are also shown. By these methods, sorting can be done only using one production rule and one evaluation function both of which only refer to local information. Several interesting phenomena caused by computation only using local information are also mentioned.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Sorting, Emergent computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Production system, Production rule, Local evaluation function

October 1, 1993

Computation Model CCM, Based on Production Rules and Local Evaluation Functions -- Its Extension and Application to 0-1 Integer Programming Problems --

Kanada, Y., 47th National Conference, Information Processing Society of Japan, pp. 1-99-100, 1993, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file: Part 1, Part 2 (in Japanese) ]
[ OHP postscript file: Slides, Handout ]
[ OHP PDF file: Slides, handout ]

Abstract: The author proposed a computation model called Chemical Casting Model (CCM), which is targeted self-organizing computation based on local and partial information. In CCM, a program consists of production rules and evaluation functions that are computed with local information. CCM is applied to 0-1 Knapsack Problems, but near optimal solutions can not be found using a simple program without new mechanisms or with simulated annealing when n > 20. However, optimal solutions are found by the probability of 37% or more using the same rule with rule composition method. If the rule composition is automated, optimal solutions are found by a high probability using very simple rules and evaluation functions only.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Combinatorial optimization, Integer programming, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Local information, Localized computation, Local evaluation function, Production system, Production rule

August 1, 1993

CCM: A Model for Self-organizing Information Processing Based on an Analogy to Chemical Reaction Systems

Kanada, Y., Bussei Kenkyu, February, 1994, Published by IPSJ.


[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ Poster postscript file: Poster, Handout ]
[ Poster PDF file: Poster, Handout ]

[English abstract is not available.]

Presented in August 1993.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Emergent computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Local information, Localized computation, Chimical reaction system

Features of Problem-Solving Method using Computation Model CCM, based on Production Rules and Local Evaluation Functions

Kanada, Y., SWoPP '93 (SIG Notes of Artificial Intelligence), Information Processing Society of Japan, 93-AI-89-2, 11-20, 1993, Published by IPSJ.

[ 日本語のページ ]
[ Paper Update 3 PDF file (in Japanese) ] [ Paper Update 3 postscript file (in Japanese) ]
[ OHP postscript file: Slides, Handout ]
[ OHP PDF file: Slides, Handout ]

[ Coloring demo in Java ]

Abstract: Problem-solving, such as constraint satisfaction or optimization, can be viewed as solution search. Conventional solution search methods in Artificial Intelligence and Operations Research are based on exhaustive and systematic search on tree-structured search space using backtrack. The author proposed a computation model called CCM (Chemical Casting Model), which is based on production rules and local evaluation functions that work in a decentralized and parallel manner, in recent papers. Solution search using CCM can be regarded as random walk on search space, biased by evaluation functions. Several features of this method are that it searches on strongly-connected graphs, that reversible and symmetric rules are used, and that the strength of bias and the locality of rules can be changed by adding or removing so-called catalysts in rules or by composing rules.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Constraint satisfaction problem, Emergent computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Local information, Localized computation, Local evaluation function

March 1, 1993

A Method of Solving Constraint Satisfaction Problems using Production Rules and Local Evaluation Functions

Kanada, Y., and Hirokawa, M.: , SIG Notes of Symbol Processing, Information Processing Society of Japan, 93-SYM-68-2, 1993, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ OHP postscript file: Slides, Handout ]
[ OHP PDF ファイル: Slides, Handout ]

[ N queens problem demo in Java ]

Abstract: The authors have proposed the Chemical Casting Model (CCM), which is a computation model for self-organizing computation. In this model, "programs" consist of a few production rules and evaluation functions (or local order degrees), both of which only refer to local information. A method of solving certain constraint-satisfaction problems, based on this model, is presented in this paper. This method enables to solve constraint-satisfaction problems, such as the N-queens problems or map coloring problems, in a polynomial order time, without using deterministic and procedural constraint propagation, but using a stochastic method, and by a very simple "program." This paper also mentions to the characteristics of the computation by on this method, based on several measurements.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Constraint satisfaction problem, Emergent Computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Local information, Localized computation, Local evaluation function, Production system, N queens problem, Coloring problem

Symbol Processing as Stochastic Processes - Macroscopic Models of Computation Processes --

Kanada, Y., Technical Report of IEICE, COMP92-93 and SS92-40, The Institute of Electronics, Information and Communication Engineers, pp. 1-10, 1993, Published by IEICE.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]
[ OHP postscript file: Slides, Handout ]
[ OHP PDF file: Slides, Handout ]

Abstract: Systems, which perform complex symbol processing, can neigher be understood by understanding the program statically nor by tracking their microscopic behavior. Thus, macroscopic models of the computation processes are necessary to understand the systems. Macroscopic models are also necessary for automatic control of computation and realizing self-organizing computation. This paper examines foundation of macroscopic theory of computation processes, and proposes modeling based on stochastic process theory. This paper also gives an example of a macroscopic model, the Markov chain model of the Chemical Casting Model (CCM), which is a microscopic model, and analizes computation processes of a graph coloring problem based on CCM. This theory realizes a fusion of symbol computation in the microscopic model and pattern computation in the macroscopic model.

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Symbol Processing, Stochastic Process, Emergent computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Stochastic Process, Local information, Localized computation, Self organization, Micro model, Macro model, Symbolcomputation, Pattern computation

February 1, 1993

A Method of Optimization using Production Rules and Local Evaluation Functions and the Macroscopic Behavior during its Computation Processes

Kanada, Y., SICE 11th SIG Systems Engineering Note, The Society of Instrument and Control Engineers, pp. 27-34, 1993, Published by SICE.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper postscript file: Part 1, Part 2 (in Japanese) ]
[ OHP postscript file: Slides, Handout ]
[ OHP PDF file: Slides, Handout ]

[No English abstract is available.]

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Combinatorial optimization, Traveling salesperson problem, Emergent computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Production rule, Production system, Local information, Localized computation

January 1, 1993

A Method of Vector Processing for Shared Symbolic Data

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

[ 日本語のページ ]
[ Paper PDF file (invalid characters contained)]
[ Paper postscript file ]

Abstract: 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.

[No English abstract is available.]

Introduction to this research theme: Logic/Symbolic Vector Processing

Keywords: Vectorization of symbol processing, Vectorized symbol processing, Parallel symbol processing, Supercomputing, Super symbol processing, Parallel processing, Vector processing

Acceleration Method for Non-numerical Processing Using a Vector Merge Function

Torii, S., Kojima, K., Kanada, Y., Sakata, A., Takahashl, M., Journal of Information Processing, Vol. 34, No. 1, pp. 109-119, 1993-1.

[ 日本語のページ ]
[ PDF paper entry (IPSJ) ]
[No English abstract is available.]
[No English abstract is available.]

Introduction to this research theme: Logic/Symbolic Vector Processing

Keywords: Vector processing, Vectorization, Merge operation, Relational database, Integrated Database Processor, IDP, Non-numerical processing, Sorting, N queens problem

July 1, 1992

Computation Systems as Self-organizing Systems -- Two Proposals for Software Research --

Kanada, Y., Summer Programming Symposium, Information Processing Society of Japan, 1992, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper in hypertext format (in Japanese) ]
[ Paper postscript file: Part 1, Part 2 (in Japanese) ]
[ OHP postscript file ]

[No English abstract is available.]

[No English abstract is available.]

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Emergent computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Production rule, Production system, Local information, Localized computation, micro model, Macro model, Stochastic process

March 31, 1992

Vector-processing Methods of Symbol-Processing Programs and Its Application to Logic Language Programs

Kanada, Y., Ph.D Thesis, University of Tokyo Graduate School, 1992.

[ 日本語のページ ]
[ Kindle edition: Vector-processing Methods of Symbol-processing Programs and Its Application to Logic Language Programs ]
[ Contents of PDF Version Paper (Japanese) ]

I developed vector processing methods of symbol-processing programs and automatic vectorization methods of logic language programs (execution on Cray-1 type computers).
-- I believe you can get some knowledge from this paper when thinking of automatic parallelization for SIMD computers.

[No English abstract is available.]

Introduction to this research theme: Logic/Symbolic Vector Processing

Keywords: Logic programming language, Programming language processor, Vectorization of symbol processing, Vectorized symbol processing, Parallel symbol processing, Supercomputing, Super symbol processing, Parallel processing, Vector processing

January 1, 1992

Toward Self-organization by Computers

Kanada, Y., 33rd Programming Symposium, Information Processing Society of Japan, 1992, Published by IPSJ.

[ 日本語のページ ]
[ Paper PDF file (in Japanese) ] [ Paper in hypertext format (in Japanese) ]
[ Paper postscript file: Part 1, Part 2 (in Japanese)]
[ OHP postscript file ]
[ OHP PDF file ]

[ N queens problem and sort demo in Java ]

[No English abstract is available.]

[No English abstract is available.]

Introduction to this research theme: CCM: Chemical-Computation Model

Keywords: CCM, Emergent computation, Randomized computation, Randomized problem solving, Rule-based computation, Rule-based problem solving, Production rule, Production system, Local information, Localized computation

July 1, 1991

"Multi-vector": A Data Structure for Vectorized Symbol-Processing and Its Applications

Kanada, Y., and Sugaya, M., 8th Annual Conference of Software Science Society, 1991.

[ 日本語のページ ]
[ No English abstract is available. ]
[ No English abstract is available. ]

Introduction to this research theme: Logic/Symbolic Vector Processing

Keywords: Programming language processor, Vectorization of symbol processing, Vectorized symbol processing, Parallel symbol processing, Supercomputing, Super symbol processing, Parallel processing, Vector processing, Multi vector
(C) Copyright 2007 by Yasusi Kanada
Powered by
Movable Type 3.36