Tuesday, June 12, 2007

Using Occam to Simulate p2p Web Services

About a year ago I gave a paper at an IEEE E-Commerce conference that described how I used the latest pi-calculus enhanced version of the old Inmos Transputer language Occam to build a very efficient massively threaded simulator for large scale p2p web services that ran on my laptop.

I blogged this at the time, but The paper itself is subject to the rules IEEE sets out for peer-reviewed conference papers and you need to be a member or pay a fee to get it from http://doi.ieeecomputersociety.org/10.1109/CEC-EEE.2006.81

However, I wanted to share this more widely and have just posted a pdf of the presentation slides for my IEEE paper. Here are the first few slides, and a description of the Tools section:

Simulation of Skype Peer-to-peer Web Services Choreography Using Occam-Pi

Complex web services are very difficult to test and verify before deployment on a large scale.
A semantically equivalent in-memory simulation can be built using Occam-pi that runs up to 100,000 nodes about a million times faster than real life.
Rapid protocol development and detailed behavioral analysis using simulation supports the development of robust services that can scale.
The implementation of a simulator that models centralized web services and application to application messaging over the Skype Peer to Peer network is described.


  • The Landscape
  • The Problem
  • The Tools
  • The Solution
  • Implementation
  • Running the Simulation
  • Conclusion
  • References

The Tools – Pi Calculus

  • WS-BPEL, SSDL and WS-CDL are based on Pi-Calculus
  • Pi-Calculus is based on Communicating Sequential Processes (CSP)
  • Pi-Calculus provides a formal model of parallel message based computing
  • Occam-Pi
  • The Occam language is based on CSP, and has been extended to add the Pi-Calculus extensions to form the Occam-Pi language.
  • The primary implementation of this language is known as KROC, the Kent Re-targetable Occam Compiler
  • KROC is freely available from the University of Kent at Canterbury, UK
  • Runs on Intel architecture Linux, MacOS X, and Microsoft Windows/Cygwin platforms. Older versions exist for SPARC, PPC etc.

The Tools – Occam Language Constructs

  • The constructs that are used in Web Services choreography map directly to Occam language constructs
  • The Occam language has direct support for sequential, parallel and alternate processing blocks, complex protocols, and channel based communications
  • Occam-Pi adds more dynamic constructs to the language
  • Mobile channels - pass a channel end over another channel
  • Mobile processes - suspend a process, pass it over a channel and resume it in a new context
  • Dynamic process forking with barrier synchronization
  • Rigorous Occam-Pi Compile-time Checks
  • Processes or expressions are not allowed to have any “side effects”
  • Syntax and usage of all protocols, data and constructs is checked
  • Occam is designed to allow very comprehensive static analysis

The Tools – Occam Runtime Characteristics

  • There is no need to use XML message encoding or namespaces
  • since the compiler can check that a protocol is being communicated correctly
  • At runtime, the Occam-Pi language is fast small compiled code
  • with its own threading model, in a single process
  • The Occam-Pi runtime detects and reports deadlock
  • including the line number in the code at which each process was stalled
  • Occam-Pi is very efficient
  • All communication takes place in a single address space at memory bus speeds
  • Basic process creation takes 20 nanoseconds on an 800MHz PC
  • Basic channel communications takes 70 nanoseconds
  • Compared to typical web services transactions over the internet these transactions are about a million times faster
  • The language is also very compact, and one hundred thousand to one million threads can be created within a 2 GByte address space.
Works Cited
  • [Cygwin] “GNU + Cygnus + Windows”, http://www.cygwin.com/
  • [GraphML] “Graph Modeling Language “, http://graphml.graphdrawing.org/
  • [Hoare78] C. A. R. Hoare. “Communicating Sequential Processes.” Communications of the ACM 1978.
  • [Hoare85] C. A. R. Hoare. Communicating Sequential Processes. Prentice Hall, 1985.
  • [KROC]. “Kent Retargetable Occam Compiler” http://www.cs.kent.ac.uk/projects/ofa/kroc/
  • [Occam2] Inmos Ltd, Occam 2 Reference Manual. Prentice Hall, 1988.
  • [Milner99] Robin Milner, “Communicating and Mobile Systems: the Pi-Calculus”, Cambridge University Press, 1999.
  • [Skype]. “Skype Developers API” https://developer.skype.com
  • [SSDL] Webber et al. “Asynchronous Messaging between Web Services using SSDL.” IEEE Internet Computing Vol10, No1 2006.
  • [WS-BPEL]. “OASIS Web Services Business Process Execution Language” http://www.oasis-open.org
  • [WS-CDL] “Web Services Choreography Description Language”, http://www.w3.org
  • [yEd] “Graph visualization and editing tool”, http://www.yworks.com/

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.