The BFStar.py Manual

Last modified: Fri Feb 11 03:07:39 EST 2005

BFStar.py is a program that reads in WSDL files based on a format specified by the EEE. The WSDL files are then converted to data structures that can be compared using a bloom filter. The program also requires a GOAL WSDL file that defines what the output is desired by the user. BFStar.py then searches through the available web service data structures to 1)discover a single web service that matches the GOAL service or 2)composes a service out of the available services that meets the end requirements of the GOAL service. This program uses different versions of the A* algorithm and uses the bloom filter to create succinct data structures from the web service information.

Installation

• The bfstar.py program requires that Python version 2.3 or greater be installed. You can download Python for:
  • Windows XP: Use this installer, and follow the GUI instruction.
  • Linux: Use this RPM packages

• Download our BFStar package (zip file). When unzipped, it will create a directory BFStar that has:

        BFStar -+-- bfstar.py : main program for BF* algorithms
                |
                +-- WebServicesPath.py, Path.py, bloom.py : additional implementation files
                |
                +-- WSDL_Repos : directory containing EEE's official test WSDL files
                |
                +-- WSDL_Repos.xml : example goal file following EEE format
                |
                +-- goal1.xml - goal5.xml : example goal files for our own testing data
  

  To test that everything is installed, you can try:

        c:\Python24\python bfstar.py -h
  

  This should display a help message.

• TROUBLE SHOOTING: If it doesn't show any message or returns errors, make sure Python was installed correctly and the executable was added to your Path. If everything looks alright with your path, make sure you are in the directory of the bfstar.py file. Any other problem please contact us:

        Eric J. Larson  : ejl175@psu.edu  (Lead developer)
        Seog-Chan Oh    : sxo160@psu.edu
        Dongwon Lee     : dongwon@psu.edu
  

  The next section will start you off on using the bfstar.py program!

BFStar.py - Intro

The BFStar.py program uses the common unix command line format for accepting input. It only requires that Python (>= 2.3) is installed. To invoke the program, simple enter:

      c:\Python24\python.exe bfstar.py [options]

To see the options available simply enter:

      c:\Python24\python.exe bfstar.py -h        or
      c:\Python24\python.exe bfstar.py --help

This will show a list of options that can be given to bfstar.py in order to use different algorithms and tracks.

Basic Usage

Note: We will assume that python is located in the users path and that the user is running the application in the same directory as bfstar.py

A basic example of running bfstar.py is:

      c:\Python24\python.exe bfstar.py -i foo -g goal.xml -d

This runs the program in debug mode in order to show more output. It uses the WSDL files in the "foo" directory as input, and "goal.xml" file as the goal. It is important that this "goal.xml" file is of the SAME format as the one given in EEE web page. Here is an example of a valid GOAL wsdl file.

      goal.xml

Typically, in real testing, we used the following options.

      c:\Python24\python.exe bfstar.py -i foo -g goal.xml

where

1. "c:\Python24\python.exe bfstar.py" runs the program!
2. The "-i foo" says "foo" is the directory to look for to find WSDL files to use discovery/composition
3. The "-g goal.xml" says what file we are using for the GOAL

It is all pretty simple! In the next section we will go through each flag to see what is available and how each option works.

Available Options

      c:\Python24\python.exe bfstar.py -h

• Debug (-d or --debug) This simply outputs more information as the program runs.

        c:\Python24\python.exe bfstar.py -d        or
        c:\Python24\python.exe bfstar.py --debug
  

• Input (-i or --input) This specifies the directory that contains WSDL files for testing. For instance, if input WSDL files are stored in "foo\bar\test" directory, then:

        c:\Python24\python.exe bfstar.py -i test           or    
        c:\Python24\python.exe bfstar.py --input=foo\bar\test
  

• Goal (-g or --goal) This specifies the "goal.xml" conforming EEE's format that contains Request and Response. For instance,

        c:\Python24\python.exe bfstar.py -g goal.xml      or
        c:\Python24\python.exe bfstar.py --goal=goal.xml  
  

• Algorithm (-a or --algo) We have "four" algorithms implemented, each having different pros and cons, and here users can choose different algorithms depending on the applications..

        Flooding        : f
        BF*             : bf
        Lookahead BF*   : l
        Adaptive BF*    : a   (This is the default algorithm used)
  

  So, for instance,

        c:\Python24\python.exe bfstar.py -a f       : run flooding algorithm
        c:\Python24\python.exe bfstar.py --algo=bf  : run bloom-filter algorithm
  

• ALL TOGETHER For instance, to do "using WSDL files in test directory and request/response in the goal.xml file, find the composition using the lookahead algorithm", following will do the job:

         c:\Python24\python.exe bfstar.py -i test -g goal.xml -a l
  

Further Testing for Large-Scale Data

In addition to the sample with dozen WSDL files, BFStar was also extensively tested against truly "large-scale" data set with 650, 1,300, 3,250, 4,850, and 6,500 web services, and each case in three distribution model -- uniform, normal and skewed.

• In the skewed distribution, 90% of web services have only one input and output parameters, and 4%, 3%, 2% and 1% of web services have 2, 3, 4 and 5 input and output parameters, respectively.
• In the normal distribution, 50% of web services have 3 input and output parameters, and 20%, 20%, 10% and 10% of web services have 1, 2, 4 and 5 input and output parameters, respectively.
• Finally, in the uniform distribution, the same ratio of web services have the same number of parameters in a uniform way.

More details are described in the technical document below. Each test case can be downloaded here:

 
       650expo.zip : 650 web services in exponential (i.e., skewed) distribution model 
       650norm.zip : 650 web services in normal distribution model 
       650uni.zip  : 650 web services in uniform distribution model

And similarly for other sizes:

 
       1300expo.zip, 1300norm.zip, 1300uni.zip 
       3250expo.zip, 3250norm.zip, 3250uni.zip 
       4850expo.zip, 4850norm.zip, 4850uni.zip 
       6500expo.zip, 6500norm.zip, 6500uni.zip 

All cases (15 = 3 size X 5 distributions) were tested against 5 "composition" test queries of Track B that were specified as the following 5 goal files ("discovery" of Track A was easy, so omitted):

       goal1.xml : provided:{a1}, resultant:{j5}
       goal2.xml : provided:{d4,e1}, resultant:{j5}
       goal3.xml : provided:{a3}, resultant:{h2,h5}
       goal4.xml : provided:{e4,b4}, resultant:{h1,h2,j2,j5} 
       goal5.xml : provided:{c5,f2}, resultant:{d4,j5} 

Further Documentation

Full version of technical report is downloadable HERE.