WWW2003 Poster 45

Noroshi
A Distributed Schedule Management System using P2P Wireless, Ad-hoc Networking

Mitsutaka Watanabe
Nihon Unisys, Ltd.
1-1-1 Toyosu, Koto-ku, Tokyo, Japan
Mitsutaka.Watanabe@unisys.co.jp
Koji Minegishi
Nihon Unisys, Ltd.
1-1-1 Toyosu, Koto-ku, Tokyo, Japan
Koji.Minegishi@unisys.co.jp
Akishi Seo
Nihon Unisys, Ltd.
1-1-1 Toyosu, Koto-ku, Tokyo, Japan
Akishi.Seo@unisys.co.jp
Akira Mori
National Institute of Advanced Industrial Science and Technology (AIST)
2-41-6 Aomi, Koto-ku, Tokyo, Japan
amori@carc.aist.go.jp

ABSTRACT

"Noroshi" is a schedule coordination system based on P2P architecture in wireless ad-hoc networking. This system coordinates collaboration activities like a conference with no central management server. Each node exchanges its information with others and finds out if requested time is available by using XML message. As a solution for foreseeable problem in ad-hoc network environment, we developed two mechanisms, One-Writing method and the "policy" mechanism sent within request messages. One-Writing method is a message delivering protocol to handle efficient schedule coordination. A message sent under One-Writing method is delivered to every participant node twice: on forward and backward path. Each single message has two functions of both collecting nodes' available time and announcing fixed schedule to every node. The "policy" enables participant nodes to fix schedule autonomically. We have implemented this system on MS PocketPC and IEEE 802.11b.

Keywords

P2P, ad-hoc network, message delivery method, autonomic decision

1. INTRODUCTION

We have devised architecture for distributed schedule management systems using P2P wireless, ad-hoc networking . We have also implemented a prototype system which based on the architecture that does not have a central schedule control server, and is running under Wireless P2P communication environment.

Fig.1 Japanese Traditional Noroshi

Noroshi, a Japanese word meaning smoking signals(shown as Fig.1) used by the ancient Japanese samurais to communicate with a comrade sited at a distant place where any other communication means like voice could not reach, is a good metaphor to tackle managing a schedule of the groups or communities whose members are frequently moving. In a case we can not send a message directly to a remote node, if we send the message to a nearby node and the message could be forwarded, we could send the message to the destination node.

Noroshi, as a scheduler engine can also;

  1. build the network dynamically, even if the information about other members (i.e. ID, node-address) is not available in advance
  2. build a community at any time, and add members dynamically
  3. protect schedule information from non-community members
  4. adjust and delete the schedules among community members

2. ARCHITECTURE

The basic architecture of Noroshi consists of two layers. The lower layer is a message delivery layer providing a One-Writing method. This method is a protocol devised to enable message delivery even if link is not always established to every node in a mobile, ad-hoc wireless network. This protocol manages message delivery status and routing information in XML.

The upper layer handles schedule coordination with the One-Writing method and "policy". Policy is a set of conditions to process a schedule coordination automatically. When a policy attached within coordination request messages is satisfied, a target schedule is fixed.

2.1 One-Writing Method

The One-Writing method offers the three types of services suitable to different usage.

ROUND_TRIP

Every node reads messages two times forward and backward. This service is used when multiple nodes negotiate about schedule coordination. This Two-time communications, schedule information gathering and coordination result notice can be done with one ROUND_TRIP message. (Fig.2)

ROUND_TRIP Message Delivery
Fig.2 ROUND_TRIP Message Delivery

GO_AROUND

All specified nodes read message only once and the message is returned to the sender. This service is mainly used for gathering each nodes' information. (Fig.3)

GO_AROUND Message Delivery
Fig.3 GO_AROUND Message Delivery

ONEWAY

All specified nodes read message only once. This service is used mainly for delivering information. (Fig.4)

ONEWAY Message Delivery
Fig.4 ONEWAY Message Delivery

2.2 Policies for coordination

On schedule coordination, a request message is delivered as a ROUND_TRIP message. A policy is attached to the message by means of which each node can determine autonomically whether the requested scheduling condition is satisfied. At the time each participant node receives the message, the node reads the policy and decide if the schedule can be fixed.

By adding policy mechanism, we achieve reduction of unnecessary message delivery. When the schedule is fixed in the way of ROUND_TRIP, the role of the original message change into a notification role to inform the schedule is fixed to remaining nodes. On the other hand, if a node finds the schedule can not be fixed, the message delivery is interrupted immediately and the on-going process is rolled back.

Noroshi currently provides three policies;

Examples

Here are some examples of policy application. Figure 5 shows typical coordination of schedules. The policy is specified as "At least 3 persons MUST participate." In the situation that C does not have free time for requested meeting, the ROUND_TRIP message(with PREPARE state) for arrangement of a meeting is passed to participant nodes in order A,B,C and D. On receiving the message every node checks its free time for the meeting and reads attached policy.

In the way of ROUND_TRIP, each node behaves as following;

  1. A and B are available for the meeting. Each node makes temporary reservation in its scheduling table and pass the request to next node.
  2. C is not free. Therefore the schedule coordination process does not have enough evidences to judge the result of this process.
  3. D is free. At this point D finds that A, B and D participate in the meeting. In other words, the policy is satisfied. Then the message turns into the schedule notification message(with COMMIT state) and go back to C,B and A for fixing the temporarily reserved time.

Another case shown in the figure 6 is the policy "C MUST participate." in the same situation as the former case. A and B pass the request message. At the time C receive the message, it becomes clear that the coordination results in failure. So C turns back the message immediately with ROLLBACK state. Then A and B free its temporarily reserved time.

Fig.5 Typical case of schedule coordination
Fig.6 Rollback case of schedule coordination

3. IMPLEMENTATION

Our system consists of two modules. One is the Noroshi library dealing with the One-Writing Method and wireless P2P communications. This corresponds to the above-mentioned message delivery layer. The other is the Noroshi scheduler running over the Noroshi library, corresponding to the schedule coordination layer. The Noroshi library has been developed as a COM-library for the reuse in other applications. The details of the two modules are presented in the following figures (Fig.7). The Noroshi library also provides wireless multihop message delivery and member discovery mechanism for unstable ad-hoc networking.

This time we have implemented Noroshi, consisting of Microsoft's Pocket PC and IEEE802.11b stacks. (Fig.8)

Fig.7 Noroshi System Architecture of Implementation
Fig.8 Screenshots

3. ACKNOWLEDGEMENTS

This work was done under the contract (130-25) with Telecommunications Advancement Organization of Japan (TAO)

4. REFERENCES

  1. Andy Oram. PEER-TO-PEER Harnessing the Power of Disruptive Technologies, O'Reilly & Associates, Inc., 2001
  2. Michel Raynal, DISTRIBUTED ALGORITHMS AND PROTOCOLS, JOHN WILLY & SONS, 1998
  3. Nick Grattan and Marshall Brain, Windows CE3.0: Application Programming, PRENTICE HALL, INC., 2001