IPA


開発成果一覧へ





2004年度第2回未踏ソフトウェア創造事業  採択案件評価書


 



1.担当PM

 

 伊知地 宏 (ラムダ数学教育研究所 代表)



2.採択者氏名


 代表者

 服部 健太 (株式会社システム計画研究所)

共同開発者

 数馬 洋一 (株式会社システム計画研究所)



3.プロジェクト管理組織


 株式会社システム計画研究所



4.委託金支払額

 

 6,670,756円



5.テーマ名

 

 やさしい仕様記述による通信プログラム自動生成系の開発



6.関連Webサイト


 http://preccs.isp.jp (公開準備中)



7.テーマ概要


 本プロジェクトは,通信プロトコル仕様の宣言的な記述から,C言語のコードを自動的に生成する通信プロトコルコンパイラPreccsを開発すること目標としている.
 通信プロトコルの仕様は主に (1) メッセージの形式と (2) メッセージ送受信手順から構成されているが,Preccsでは拡張した正規表現によってメッセージ形式を記述し,プロセス代数の考え方にもとづいて送受信手順を記述する.これによって,通信プロトコルをわかりやすく記述することが可能となる.さらに,これらの仕様記述から通信プロトコルの処理を行うC言語のコードを自動生成することによって,信頼性の高い通信プログラムを短期間で開発することが可能となる.



8.採択理由

 

 通信プログラムを独自の手法で宣言的に仕様を記述し,そこから自動的に実用性の高いプログラムを生成しようという,未踏性もそれなりにあり,実用性もある面白い提案である.実装においてもプロセス代数をベースにするなど,知識と技術力のレベルもかなり高いと感じている.しかし,根幹にかかわる部分ではまだ検討が行われていない所が多々あり,開発期間内で本当に全ての機能が実現できるのか不安に感じる面もあるが,もしちゃんと完成すれば実用性の高いソフトウェアであるので採択と判断する.



9.開発目標


 記述がやさしく実用的である通信プロトコル仕様の宣言的記述言語Preccs を設計し,C言語へのコンパイラを作成することが開発目標である.




10.進捗概要


 開発者は開発当初にはプロセス代数に対する理解が十分でなかったので,理論関係の学会に連れて行って刺激を与え,並列計算の理論 (プロセス代数など) の専門家と議論する機会を作った.開発者の仕事の都合から,ソフトウェアの本格的な開発は4月頃から始まったが,順調に開発が進んだ.



11.成果


 (1) Preccsの全体構成
 図 1にPreccsを用いた通信プロトコルの実装の流れを示す.
  

図 1 Preccsを用いた実装の流れ

  

 プログラマーはRFC(Requst for Comment)など自然言語で記述された通信プロトコル仕様にもとづいて,メッセージ形式や送受信手順をPreccsのソースとして記述する.PreccsコンパイラはPreccsソースから,パタンマッチに用いる状態遷移表やプロセス動作を実現するための処理をC のコードとして出力する.ここで出力されたコードはPreccs実行時ライブラリと協調しながら,プロトコルの中核的な処理をインタプリティブに実行するものである.Preccs実行時ライブラリは,パタンマッチやチャネル通信,プロセス管理などを実現するためのルーチンから構成される.

  
 (2) 仕様記述言語Preccs

 (2-1) メッセージ形式の記述例
 Preccsでは正規表現を用いることが可能である.例えば,通信プロトコルによく見られるメッセージ形式の例を図 2に示す.
  

図 2 メッセージ形式の例

  

 ここに示したメッセージは1オクテットと4オクテットの二つの固定長フィールドの後に0個以上のオプションが続き,最後は0xFFで終わるという形式である.また,オプションも構造を持ち,オプション種別を表すフィールドtagとオプションのデータ長を表すフィールドlen,さらにオプションデータのフィールドdataからなる.これをPreccsで記述すると図 3のようになる.

  

図 3 Preccsによるメッセージ形式の定義例

  

 ここで,Message ::= ・・・;の部分でメッセージ形式Messageを定義している.Messageの各フィールドにはラベル名を付与することができる.例えば,type, idはラベル名であり,それぞれ,octet, octet[4]というフィールドが対応している.フィールドの間を区切るコンマ「,」は,正規表現の連接に相当し,各フィールドが連続していることを意味している.optsラベルで指定されるフィールドOption*はメッセージ形式Optionが0個以上連続することを意味しており,アスタリスク「*」は正規表現における閉包である.Preccsではこのほかにも選択「|」,1回以上の繰り返し「+」,0回か1回のパタン「?」といった正規表現の記法を使用することができる.
  
 (2-2) 送受信手順の記述
  
 ここでは,一般的なコネクション確立の手法である3ウェイハンドシェイクを例にとって説明する.図 4は,3ウェイハンドシェイクにおけるコネクションのサーバー側の状態遷移を示したものである.これをPreccsで記述したものが図 5である.
 図 5のInit() ::= ・・・;ではInitプロセスを定義している.Initプロセスではsockinチャネルからメッセージを受信し,rpkt変数に代入する.rpkt変数の内容について,次にメッセージ形式によるパタンマッチを行い,Synパケットとマッチした場合にはSynAckパケットを生成し(それをspkt変数に代入したのちに)sockoutチャネルに出力する.sockoutチャネルに出力されるとパケットの内容がネットワークに送信される.
  

  

図 4 3ウェイハンドシェイクにおけるサーバーの状態遷移

  

  

図 5 3ウェイハンドシェイクにおけるサーバ側の動作記述例

  

 図 5にあるSynやSynAckなどのパタンは,先に説明したPreccsのメッセージ形式の記述方法に従って定義されているものとする.また,timerチャネルはタイムアウトのための特別なチャネルで,引数で指定した秒数だけ待つという意味である.Waitプロセスでは,ソケットから入力があるとパタンマッチを試み,10秒間入力がなければ,タイムアウトして初期状態(Init)に戻るという選択的な動作を行う.
  
 (2-3) Preccsコンパイラ
  
 Preccsコンパイラは,仕様記述言語Preccsで記述されたソースコードからC言語のコードを自動的に生成する.Preccsのメッセージ形式の記述部分から,メッセージ解析用のNFAが参照するための状態遷移表とメッセージ組み立てに使用するデータ定義が生成される.また,送受信手順の記述部分からは,プロセスのディスパッチコードが生成される.ディスパッチコードは一つの巨大なswitch〜case文として実現され,各case文単位でプロセスの切り替えが行われる.

  
 (3) 性能評価
  
 実際の通信プロトコルの適用例として,Preccsを用いてDHCPクライアントの実装を行った.また,比較対象としてC言語で同等の機能を有するDHDPクライアントをスクラッチから実装した.
  
 (3-1) 記述量の評価
  
 図6に,DHCPクライアントの記述量の比較結果を示す.グラフの縦軸は記述に要した行数である.

  

  

図 6 DHCPクライアントの記述量の比較

  

 これを見ると,Preccsによる記述はCに比較して,約3分の1に短くなっている.特に送受信処理とメッセージ組み立て,解析処理の記述量が大幅に削減されている.このことから,Preccsにおけるメッセージ形式と送受信手順の記述方式は非常に有効であることがわかる.
  
 (3-2) オーバーヘッドの評価
  
 Preccsによる実行時のオーバーヘッドを見るために,DHCPクライアントの実行時間の比較を行った.ここでは,プログラムの起動からIPアドレスを取得,設定するまでの時間を計測した.評価のために,同一のLANセグメント内に接続されたクライアントとサーバーの計2台のマシンを用意した.ここで使用した各マシンの諸元を表1に示す.
  

           表1 評価に用いた各マシン

  

 図7にDHCPクライアントの実行時間の比較結果を示す.実行時間はtimeコマンドを用いて測定し,10回の平均値を算出した.グラフの縦軸の単位はミリ秒である.

  

  

図7 DHCPクライアントの実行時間比較

  

 結果を見ると,DHCPクライアントにおいては,Preccsによる実行時間のオーバーヘッドは高々25%程度に過ぎないことがわかる.DHCPのようにシビアな処理性能を求めないプロトコルに関しては,このオーバーヘッドは十分に許容範囲内に収まっている.また,待ち時間(Idle)を除く,CPU使用時間(Sys+User)のオーバーヘッドでも2倍程度に抑えられている.



12.プロジェクト評価


 ただソフトウェアをただ開発するだけでなく,例題を解き性能評価も行っている点は大いに評価できる.仕様記述言語も関数型言語MLのような感じで書きやすくなっていると感じる.しかし,今回の開発ではコード生成で最適化が全く行われておらず,アイドル状態があまりない時間的に厳しいプロトコルに対して,本システムが使えるかどうかわからない.

 ・未踏性: B+
  通信プロトコルの仕様記述とコード生成についてはある程度先行研究があり,そんなに未踏性が高いとは言えない.ある程度プロトコルを絞った対象に対して実用的なコードを出す物も存在した.
 ・先進性: B+
  プロセス代数を用いた点にある程度先進性を認めるが,もっと先進的なプロセス代数を用いると,同期機能のある並列処理が書けて仕様記述言語がもっと綺麗になったのではないかと思う.
 ・実用性: A-
  まだ対象が限定されると思うが,開発現場においてはかなり実用的であると感じる.
 ・社会への影響: A-
  ちゃんとソフトウェアを流通させると,通信プログラムを開発している所への影響が大きいように思う.特に,コードの最適化が行われると影響力は大きいと思う.
  (A: 高い,B: 並,C: 低い)



13.今後の課題


 是非とも生成コードの最適化を実現してもらいたい.さらに,ソフトウェアを広く配布するか,あるいはちゃんとした製品に仕上げて,多くの通信ソフトウェア開発者が使えるようにし,そのフィードバックを得て,より良いソフトウェアに仕上げてもらいたい.



  ページトップへ   





  Copyright(c) Information-technology Promotion Agency, Japan. All rights reserved 2004