JP3248055B2 - 非同期伝送方法および非同期伝送装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、通信，放送分野に
おいて高効率かつ高品質な通信を実現する非同期伝送方
法および非同期伝送装置に係り、特に、固定長のセルを
通信のユニットとして扱う (１)ＡＴＭ広域ネットワークシステム(ＡＴＭ−ＷＡＮ)
(図２３) (２)ＡＴＭブロードキャスト送信システム(ＡＴＭ多重
放送)(図２４) (３)光ビーコン等によるマルチバンドＡＴＭシステム
(図２５) のような非同期伝送(ＡＴＭ)分野および非同期伝送シス
テムに関する。

【０００２】

【従来の技術】高速ディジタル通信を支える通信技術と
しては、大別して回線交換方式とパケット交換方式が、
従来から実用化されてきた。しかし、近年、通信利用者
が多様化し、それに伴い大容量，高速化のニーズが高ま
るにつれ、従来の回線交換方式またはパケット交換方式
では、このニーズに応えることが困難となってきた。

【０００３】マルチメディア通信等のニーズに対応する
ために、非同期伝送方式(ＡＴＭ：Asynchronous Transf
er Mode)が主流となってきている。例えば、『標準ＡＴ
Ｍ』(1994:アスキー出版局，富永英義／石川宏監修)に
記載されているように、高速 ハードウェアによるＡＴ
Ｍセルフルーティングスイッチを用いると、複数利用者
間において、画像，音声等の異なるメディアの高速，大
容量の同時通信が可能となりつつある。

【０００４】

【発明が解決しようとする課題】図２６は、従来のパケ
ット交換システムの概要を示す系統図である。送出要求
側，，から種々のデータＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ
が発生すると、パケット交換装置は、各々のパケットの
ターゲットユーザ，，の識別情報を各データの先
頭に付加し、伝送路に送出する。この動作をルーティン
グという。パケットのサイズは、可変長であり、データ
の性質や速度に応じて任意に設定できるので、柔軟性が
高い。

【０００５】しかし、様々な種類のデータが同時に発生
した場合は、データの解読やルーティングに時間を要す
るのみならず、重要で少量のデータの到着が、大容量の
データの後になると、データの送信遅れを生じたり、こ
の送信遅れのために、重要で少量のデータがしばしば廃
棄されてしまうという問題があった。

【０００６】図２７は、従来の非同期伝送交換システム
の概要を示す系統図である。非同期伝送方式では、上記
パケット交換方式の問題を回避するため、送信要求デー
タを所定長のパケット(セル)に分割して送信する。図２
７の例では、大容量のデータＡは８分割され、データＢ
は３分割されて、伝送路に送り込まれる。このようにす
ると、分割されたセルに付加するヘッダの数が増加する
が、データの重要度に応じて、様々な組合せや並べ換え
の制御が容易になるので、パケット交換方式で発生する
問題を解決できる。

【０００７】図２８は、具体的な例を用いて、パケット
交換システムと従来の非同期伝送交換システムとの違い
を説明する図である。この例で、データＡは、３８４バ
イトのデータであり、ターゲットユーザは、である。
セルのデータ長を４８バイトとすると、データＡは、８
分割され、Ａ−１〜Ａ−８という形で伝送路に送出され
る。データＢは、データ長が１２０バイトであるから、
３分割され、Ｂ−１，Ｂ−２，Ｂ−３のセル群として送
出される。その場合、端数分のＢ−３の２４バイトに
は、無効データが埋め込まれる。

【０００８】図２９は、パケット交換システムの問題点
を説明する図である。ここでは、物理的な伝送路の遅延
を１０とし、データＡの許容遅延時間を２０、データＢ
の許容遅延時間を１２としている。時刻０でデータＡの
送信要求が発生すると、伝送路の遅延時間１０を経て、
受信ユーザは、時刻１０からデータＡを受信し始め
て、時刻１４で完了する。一方、データＢの送信要求
は、時刻２で発生しているが、時刻１でデータＤの送信
要求が発生してるために、送出順序がＡ→Ｄ→Ｂとな
り、結局、データＢの受信ユーザは、時刻１５になら
ないと、データＢを受信できない。データＢの送信要求
が時刻２であるから、遅延が１３となり、データＢの許
容遅延時間１２を超えてしまうことになる。

【０００９】図３０は、図２９と同じ前提条件で、非同
期伝送交換システムの伝送状況を示す図である。ここで
は、データＡ，Ｄ，Ｂは、それぞれ８分割，２分割，４
分割され、各々異なる許容遅延時間２０，１２，１３を
持っている。これらの条件を最大限に活用して、データ
ＤおよびＢの発生時に、データＡの送信に割込みをか
け、Ａ−１，Ａ−２，Ｄ−１，Ｄ−２，Ｂ−１〜Ｂ−
４，Ｅ−１，Ｅ−２，Ａ−３，Ａ−４，Ｆ−１，Ｆ−
２，Ａ−５〜Ａ−８の順に送信する。このようにする
と、データＢの到着は、時刻１２〜１４の間であり、時
刻２からの遅延時間が最大でも１２となり、結局データ
Ａ，Ｂ，Ｄともに、許容遅延時間を満足できる。

【００１０】非同期伝送交換システムでは、送信要求デ
ータを細分化すると、同一能力の伝送路を有効に活用で
きるメリットがあるが、送信要求量の増大に伴い、次の
ような問題が発生してきている。 (１)送信要求データ量が物理的伝送路容量をオーバーし
た場合、データ廃棄率が増大する。 (２)送信要求データ量が物理的伝送路容量をオーバーし
た場合、同一データのランダムな分割が大量に発生する
ため、同期性が崩れたり、バースト誤りが発生したりし
て、伝送品質が低下する。

【００１１】図３１は、データ廃棄率の増大に対する従
来の対応策を示す図である。これらのグラフにおいて、
横軸は時間推移を示し、縦軸は要求／送出データ量の物
理伝送量との比率を示している。この場合、送信要求デ
ータ量が、時刻ｔ1からｔ2まで、物理伝送量を超えてい
る。

【００１２】対応策(Ａ)は、送信要求データ量が常に物
理量以下になるように、送信要求側の入力を制限してい
る。この方法では、伝送品質は向上するものの、伝送効
率が極めて低下してしまう。

【００１３】対応策(Ｂ)は、物理量を超えた送信要求デ
ータ部分を空いた時間に遅延させ、データ廃棄率を最小
とする方法であり、スムージングといわれている。この
方法では、伝送効率は向上するが、大きな遅延が発生
し、伝送品質が明らかに低下する。

【００１４】対応策(Ｃ)は、ハードウェアによるセルル
ーティングスイッチ装置によくみられる方法であって、
物理量を超えたセルをそのまま破棄してしまう。この方
法では、伝送品質および効率が、大きく低下する。

【００１５】図３２は、非同期伝送交換システムで発生
する送信要求データの種類と伝送路の負荷パターンとの
関係を説明する図である。送信要求データの種類は、大
別すると、定周期型データ，イベント型データ，メモリ
型データとなる。

【００１６】定周期型データとは、時刻通知，交通情
報，天気情報，同期情報等の所定時間毎に発生するデー
タであり、定周期性が重視される。

【００１７】イベント型データとは、非同期的に発生す
るデータであり、時間推移とともに変動する。通常は応
答性が重視され、所定時間遅延した場合は、データの重
要性が失われるものが多い。

【００１８】メモリ型データとは、例えば地図データ，
画像蓄積データ等のデータであり、高速応答性は必ずし
も重視されないが、データ破棄は許されず、一般に膨大
な量である。

【００１９】これらのデータの送信要求が、同一伝送シ
ステムに対して発生すると、図３２の右側に示すよう
に、ある時間帯には、物理的伝送量を超えてしまい、前
述の様々な問題が発生することになる。

【００２０】本発明の目的は、伝送効率および伝送品質
の低下が極めて少ない非同期伝送方法を提供することで
ある。

【００２１】本発明の別の目的は、与えられた問題に対
して計画候補の内容を変更し、最小化または最大化すべ
き計画項目を表わす目的関数の値を最小または最大にす
る計画立案方法を提供することである。

【００２２】本発明の他の目的は、伝送効率および伝送
品質の低下が極めて少ない非同期伝送装置を提供するこ
とである。

【００２３】

【課題を解決するための手段】本発明は、上記目的を達
成するために、ユーザからランダムにまたは周期的に発
生する送信要求データを所定サイズのセルに分割し、保
存する手順と、データ発生密度および送出許容時間によ
り定まる一時保存データをもれなく記憶する手順と、所
定時間(フレーム)毎に保存された送信要求データからセ
ルを読出しセル毎に定められている周期時間，許容変動
幅，許容応答時間，許容セル廃棄率を維持するように並
べ換えて最適なセル割付けを実行し、送信を要求する手
順とを有する非同期伝送方法において、前記最適なセル
割付手順が、並列処理する複数の処理手順からなり、前
記各処理手順が、それぞれ与えられた親割付案から予め
定められた変異操作により新たに子割付案を生成する割
付変更手順と、親割付案と子割付案とを比較評価し更新
する割付評価手順および自律的淘汰手順とを含み、前記
割付評価手順が、親割付案と子割付案との目的関数値の
差分を計算し、前記目的関数値の差分が予め与えられた
最適判断値よりも小さい場合には親割付案を子割付案に
置換する処理を繰り返すとともに、子割付案が並列処理
により得られた複数の割付案の中で最適な場合は子割付
案を最適計画案として登録し、差分が最適判断値よりも
大きい時は当該親割付案を保持し、前記自律的淘汰手順
が、処理手順における親割付案の変更が発生しなかった
時間が予め与えられた自律淘汰世代値と比較して大きい
時は最適割付案を処理手順の新たな親割付案として置換
する非同期伝送方法を提案する。

【００２４】本発明は、また、ユーザからランダムにま
たは周期的に発生する送信要求データを所定サイズのセ
ルに分割し、保存する手順と、データ発生密度および送
出許容時間により定まる一時保存データをもれなく記憶
する手順と、所定時間(フレーム)毎に保存された送信要
求データからセルを読出しセル毎に定められている周期
時間，許容変動幅，許容応答時間，許容セル廃棄率を維
持するように並べ換えて最適なセル割付けを実行し、送
信を要求する手順とを有し、前記最適なセル割付手順
が、各々同一時間経過に対して各々自律的にセル割付の
最適化を図りながら自身の最適化進捗の状況を判断し、
所定時間連続して割付結果に変化が無い場合には他の割
付け手順で生成されより優れた割付案を自身に取り込み
自律協調的に最適化する自律淘汰手順とを含む非同期伝
送方法において、前記最適なセル割付手順が、並列処理
する複数の処理手順からなり、前記各処理手順が、それ
ぞれ与えられた親割付案から予め定められた変異操作に
より新たに子割付案を生成する割付変更手順と、親割付
案と子割付案とを比較評価し更新する割付評価手順およ
び自律的淘汰手順とを含み、前記割付評価手順が、親割
付案と子割付案との目的関数値の差分を計算し、目的関
数値の差分が予め与えられた最適判断値よりも小さい場
合には親割付案を子割付案に置換する処理を繰り返すと
ともに、子割付案が並列処理により得られた複数の割付
案の中で最適な場合は子割付案を最適計画案として登録
し、差分が最適判断値よりも大きい時は当該親割付案を
保持し、前記自律的淘汰手順が、処理手順における親割
付案の変更が発生しなかった時間が予め与えられた自律
淘汰世代値と比較して大きい時は最適割付案を処理手順
の新たな親割付案として置換する非同期伝送方法を提案
する。

【００２５】本発明は、さらに、ユーザからランダムに
または周期的に発生する送信要求データを所定サイズの
セルに分割し、保存する手順と、データ発生密度および
送出許容時間により定まる一時保存データをもれなく記
憶する手順と、所定時間(フレーム)毎に保存された送信
要求データからセルを読出しセル毎に定められている周
期時間，許容変動幅，許容応答時間，許容セル廃棄率を
維持するように並べ換えて最適なセル割付けを実行し、
送信を要求する手順とを有する非同期伝送方法におい
て、前記最適なセル割付手順が、送信要求データ毎に予
め定められている送出可能時間帯の時間範囲内でデータ
の過去の送出タイミングに基づいて割付位置を定める非
同期伝送方法を提案する。

【００２６】本発明は、ユーザからランダムにまたは周
期的に発生する送信要求データを所定サイズのセルに分
割し、保存する手順と、データ発生密度および送出許容
時間により定まる一時保存データをもれなく記憶する手
順と、所定時間(フレーム)毎に保存された送信要求デー
タからセルを読出しセル毎に定められている周期時間 ，
許容変動幅，許容応答時間，許容セル廃棄率を維持する
ように並べ換えて最適なセル割付けを実行し、送信を要
求する手順とを有し、前記最適なセル割付手順が、各々
同一時間経過に対して各々自律的にセル割付の最適化を
図りながら自身の最適化進捗の状況を判断し、所定時間
連続して割付結果に変化が無い場合には他の割付け手順
で生成されより優れた割付案を自身に取り込み自律協調
的に最適化する自律淘汰手順とを含む非同期伝送方法に
おいて、前記最適なセル割付手順が、送信要求データ毎
に予め定められている送出可能時間帯の時間範囲内でデ
ータの過去の送出タイミングに基づいて割付位置を定め
る非同期伝送方法を提案する。

【００２７】本発明は、また、ユーザからランダムにま
たは周期的に発生する送信要求データを所定サイズのセ
ルに分割し、保存する手順と、データ発生密度および送
出許容時間により定まる一時保存データをもれなく記憶
する手順と、所定時間(フレーム)毎に保存された送信要
求データからセルを読出しセル毎に定められている周期
時間，許容変動幅，許容応答時間，許容セル廃棄率を維
持するように並べ換えて最適なセル割付けを実行し、送
信を要求する手順とを有する非同期伝送方法において、
前記最適なセル割付手順が、並列処理する複数の処理手
順からなり、前記各処理手順が、それぞれ与えられた親
割付案から予め定められた変異操作により新たに子割付
案を生成する割付変更手順と、親割付案と子割付案とを
比較評価し更新する割付評価手順および自律的淘汰手順
とを含み、前記割付評価手順が、親割付案と子割付案と
の目的関数値の差分を計算し、目的関数値の差分が予め
与えられた最適判断値よりも小さい場合には親割付案を
子割付案に置換する処理を繰り返すとともに、子割付案
が並列処理により得られた複数の割付案の中で最適な場
合は子割付案を最適計画案として登録し、差分が最適判
断値よりも大きい時は当該親割付案を保持し、前記自律
的淘汰手順が、処理手順における親割付案の変更が発生
しなかった時間が予め与えられた自律淘汰世代値と比較
して大きい時は最適割付案を処理手順の新たな親割付案
として置換し、前記最適なセル割付手順が、送信要求デ
ータ毎に予め定められている送出可能時間帯の時間範囲
内でデータの過去の送出タイミングに基づいて割付位置
を定める非同期伝送方法を提 案する。

【００２８】本発明は、上記他の目的を達成するため
に、ユーザからランダムにまたは周期的に発生する送信
要求データを所定サイズのセルに分割し記憶装置に格納
するセルバッファリング装置と、データ発生密度および
送出許容時間により定まる一時保存データをもれなく記
憶する記憶装置と、所定時間(フレーム)毎にタイマによ
り起動され、記憶装置からセルを読出しセル毎に定めら
れている周期時間，許容変動幅，許容応答時間，許容セ
ル廃棄率を維持するように並べ換え、送信装置に送信を
要求する最適セル割付装置とを備えた非同期伝送装置に
おいて、前記最適セル割付装置が、並列処理する複数の
処理装置からなり、前記各処理装置が、それぞれ与えら
れた親割付案から予め定められた変異操作により新たに
子割付案を生成する割付変更手段と、親割付案と子割付
案とを比較評価し更新する割付評価手段および自律的淘
汰手段とを備え、前記割付評価手段が、親割付案と子割
付案との目的関数値の差分を計算し、目的関数値の差分
が予め与えられた最適判断値よりも小さい場合には親割
付案を子割付案に置換する処理を繰り返すとともに、子
割付案が並列処理により得られた複数の割付案の中で最
適な場合は子割付案を最適計画案として登録し、差分が
最適判断値よりも大きい時は当該親割付案を保持する手
段であり、前記自律的淘汰手段が、処理装置における親
割付案の変更が発生しなかった時間が予め与えられた自
律淘汰世代値と比較して大きい時は最適割付案を処理装
置の新たな親割付案として置換する手段である非同期伝
送装置を提案する。

【００２９】本発明は、また、ユーザからランダムにま
たは周期的に発生する送信要求データを所定サイズのセ
ルに分割し記憶装置に格納するセルバッファリング装置
と、データ発生密度および送出許容時間により定まる一
時保存データをもれなく記憶する記憶装置と、所定時間
(フレーム)毎にタイマにより起動され、記憶装置からセ
ルを読出しセル毎に定められている周期時間，許容変動
幅，許容応答時間，許容セル廃棄率を維持するように並
べ換え、送信装置に送信を要求する最適セル割付装置と
を備え、前記最適セル割付装置が、複数の処理装置が各
々同一時間経過に対して各々自律的にセル割付の最適化
を図りながら自身の最適化進捗の状況を判断する割付評
価手段と、所定時間連続して割付結果に変化が無い場合
には他の処理装置で生成されより優れた割付案を自身に
取り込み自律協調的に最適化する自律淘汰手段とを含む
非同期伝送装置において、前記最適セル割付装置が、並
列処理する複数の処理装置からなり、前記各処理装置
が、それぞれ与えられた親割付案から予め定められた変
異操作により新たに子割付案を生成する割付変更手段
と、親割付案と子割付案とを比較評価し更新する割付評
価手段および自律的淘汰手段とを備え、前記割付評価手
段が、親割付案と子割付案との目的関数値の差分を計算
し、目的関数値の差分が予め与えられた最適判断値より
も小さい場合には親割付案を子割付案に置換する処理を
繰り返すとともに、子割付案が並列処理により得られた
複数の割付案の中で最適な場合は子割付案を最適計画案
として登録し、差分が最適判断値よりも大きい時は当該
親割付案を保持する手段であり、前記自律的淘汰手段
が、処理装置における親割付案の変更が発生しなかった
時間が予め与えられた自律淘汰世代値と比較して大きい
時は最適割付案を処理装置の新たな親割付案として置換
する手段である非同期伝送装置を提案する。

【００３０】本発明は、さらに、ユーザからランダムに
または周期的に発生する送信要求データを所定サイズの
セルに分割し記憶装置に格納するセルバッファリング装
置と、データ発生密度および送出許容時間により定まる
一時保存データをもれなく記憶する記憶装置と、所定時
間(フレーム)毎にタイマにより起動され、記憶装置から
セルを読出しセル毎に定められている周期時間，許容変
動幅，許容応答時間，許容セル廃棄率を維持するように
並べ換え、送信装置に送信を要求する最適セル割付装置
とを備えた非同期伝送装置において、前記最適セル割付
装置が、送信要求データ毎に予め定められている送出可
能時間帯の時間範囲内でデータの過去の送出タイミング
に基づいて割付位置を定める手段である非同期伝送装置
を提案する。

【００３１】本発明は、ユーザからランダムにまたは周
期的に発生する送信要求データを所定サイズのセルに分
割し記憶装置に格納するセルバッファリング装置と、デ
ータ 発生密度および送出許容時間により定まる一時保存
データをもれなく記憶する記憶装置と、所定時間(フレ
ーム)毎にタイマにより起動され、記憶装置からセルを
読出しセル毎に定められている周期時間，許容変動幅，
許容応答時間，許容セル廃棄率を維持するように並べ換
え、送信装置に送信を要求する最適セル割付装置とを備
え、前記最適セル割付装置が、複数の処理装置が各々同
一時間経過に対して各々自律的にセル割付の最適化を図
りながら自身の最適化進捗の状況を判断する割付評価手
段と、所定時間連続して割付結果に変化が無い場合には
他の処理装置で生成されより優れた割付案を自身に取り
込み自律協調的に最適化する自律淘汰手段とを含む非同
期伝送装置において、前記最適セル割付装置が、送信要
求データ毎に予め定められている送出可能時間帯の時間
範囲内でデータの過去の送出タイミングに基づいて割付
位置を定める手段である非同期伝送装置を提案する。

【００３２】本発明は、また、ユーザからランダムにま
たは周期的に発生する送信要求データを所定サイズのセ
ルに分割し記憶装置に格納するセルバッファリング装置
と、データ発生密度および送出許容時間により定まる一
時保存データをもれなく記憶する記憶装置と、所定時間
(フレーム)毎にタイマにより起動され、記憶装置からセ
ルを読出しセル毎に定められている周期時間，許容変動
幅，許容応答時間，許容セル廃棄率を維持するように並
べ換え、送信装置に送信を要求する最適セル割付装置と
を備えた非同期伝送装置において、前記最適セル割付装
置が、並列処理する複数の処理装置からなり、前記各処
理装置が、それぞれ与えられた親割付案から予め定めら
れた変異操作により新たに子割付案を生成する割付変更
手段と、親割付案と子割付案とを比較評価し更新する割
付評価手段および自律的淘汰手段とを備え、前記割付評
価手段が、親割付案と子割付案との目的関数値の差分を
計算し、目的関数値の差分が予め与えられた最適判断値
よりも小さい場合には親割付案を子割付案に置換する処
理を繰り返すとともに、子割付案が並列処理により得ら
れた複数の割付案の中で最適な場合は子割付案を最適計
画案として登録し、差分が最適判断値よりも大きい時は
当該親割付案を保持する手段であり、前記自律的淘汰手
段が、処理装置における親割付案の変更が発生しなかっ
た時間が予め与えられた自律淘汰世代値と比較して大き
い時は最適割付案を処理装置の新たな 親割付案として置
換する手段であり、前記最適セル割付装置が、送信要求
データ毎に予め定められている送出可能時間帯の時間範
囲内でデータの過去の送出タイミングに基づいて割付位
置を定める手段である非同期伝送装置を提案する。

【００３３】本発明においては、ある時点での送信要求
データを１つの組合せ計画問題の１要素と考える。しか
も、データそのものの優先度だけではなく、伝送上の品
質評価指標である許容周期変動幅，許容遅延時間，許容
セル廃棄率を最大限活用し、伝送品質および伝送効率を
最適化する。

【００３４】本発明の基本的方針は、以下の通りであ
る。 (１)セルを割付ける複数の処理装置を備える。 (２)各処理装置にそれぞれ割付案を与える。 (３)各処理装置は、与えられた割付案を複製して新たな
割付案を生成し、新たな割付案に対し微小変異を与え
る。 (４)極値に陥らぬように注意しながら、割付案を選択
し、最適解か否かを決定する。

【００３５】この時、ある同一セル割付処理装置内で、
定められた回数または定められた時間に割付案が更新さ
れない場合、 (５)他の処理装置での最適解候補を自身の割付案として
自律的に取り込む。

【００３６】複数の割付案が最小の遺伝的操作により自
己増殖を繰り返すと、概念的には各々最適値に近づいて
ゆくが、最適化の進捗の度合いはまちまちである。そこ
で、本発明においては、最適化の進捗の度合いを各々が
自律的に観察し、進捗が鈍った場合、他の優れた割付案
に自律的に置換してゆく。

【００３７】上記過程で、最終的に最適解に到達させる
には、時間(世代)経過に従って、最適の度合いを判定す
る上限値を徐々に変少させ、自律的に他の個体に置換す
るか否かの判定時間(世代)を増大させるように制御すれ
ばよい。

【００３８】上記処理装置では、各々の処理手順が自律
的に自身を淘汰する場合、全時空間で最適な割付案を自
身に取り込むようにしているが、他の方法としては、自
身の存在する位置により定まる特定の局所地域内での最
適な割付案を取り込む方法も考えられる。このようにす
ると、割付案の進化は、ランダムな離散的拡張ではな
く、連続した地域の拡張の形で実行されるようになる。

【００３９】また、上記処理装置では、各々の処理装置
が自律的に自身を淘汰する場合、他のより優れた割付案
を淘汰されるべき割付案に置き換えるようにしたが、他
の方法としては、２種類の割付案のそれぞれの要素を継
承するように交配(交叉)させ、得られた第３の割付をセ
ルプロセッサが処理対象とする親割付案としてもよい。

【００４０】２個以上の親の構成要素を互いに交換して
子を生成する交配，１個の親の要素を予め定められた突
然変異率に従って変化させる突然変異操作，１個の親の
要素並びを逆転させる逆位操作等の遺伝子オペレータ
(操作)により、所定の数の子個体が生成される。次に、
親個体と子個体について、予め定められた手順で、予め
定められた数の個体を生存させ、次世代処理に移行する
ような処理を繰り返す。

【００４１】以上のようないくつかの本発明による方法
を実行すると、割付の初期段階では、活発な個体の置き
換え(軍拡競争)がなされ、比較的良い値を有する個体が
揃い、中〜後期では、各々の個体(割付案)は、最小の変
異で漸化的に最適解に確実に収束してゆく。

【００４２】本発明は、直接的なニューラルネットワー
ク構造や従来の遺伝子アルゴリズムにおける交配や突然
変異等の冗長な最小化手段を採用しないので、極めて明
確な最適化方法および最適化装置を提供できる。

【００４３】特に重要なことは、従来の遺伝的アルゴリ
ズムの初期の高い最適化速度を保持したまま、最適解が
所定の処理後に得られるようにした点である。すなわ
ち、よく知られているように、従来の遺伝的アルゴリズ
ムは、立ち上がりの最適性に優れるが、最適解が得られ
ない場合がある。さらに、最適解が得られる従来のニュ
ーラルネットワークのボルツマンマシンまたはシミュレ
ーテット・アニーリングは、常時１種類の割付案を変更
し、変更前の割付と比較しながら最適値に近づいてゆく
ため、逐次実行の処理しかできなかった。

【００４４】これに対し、本発明では、複数の割付案を
同時に検討して並列処理できるため、処理速度が飛躍的
に向上する。

【００４５】従来の遺伝的アルゴリズムでは、交配また
は突然変異の遺伝子操作を繰り返しても、最適値には到
達しないことがある。また、遺伝子操作，人口制限，淘
汰，評価等の処理は、割付要素数をｎとすると、少なく
ともｎ⁵回の処理ステップを要していた。

【００４６】本発明では、以下のようにして、最適解が
高速に得られる。

【００４７】《超並列制御プロセッサの処理》 与えられた割付問題に対して、それぞれ複数の処理装置
に複数の割付案を１個ずつ割り当てた後に、全てのプロ
セッサを起動し、以下の処理を少なくともｎ^２／Ｐｍ回
繰り返す。ここで、ｎは割付対象要素数、Ｐｍはセルプ
ロセッサの数である。

【００４８】以下、全てのプロセッサは、非同期並行に
独立して処理する。

【００４９】〈第１のセルプロセッサの処理〉 ステップ１：時刻ｔiの推移とともに減少してゆく範囲
に一様に分布する最適判断値Ａ(ｔi)を演算する。 Ａ(ｔi)＝{Ｃ₁・ａ(ｔi)}／log(ｔi＊Ｐｍ) Ｃ₁は定数であり、ａは一様乱数である。

【００５０】ステップ２：時刻ｔiの推移とともに増大
してゆく自律淘汰世代値Ｂ(ｔi)を演算する。 Ｂ(ｔi)＝Ｃ_２×{１−１／log(ｔi＊Ｐｍ)} Ｃ_２は定数である。

【００５１】〈第２の並列セルプロセッサ群の処理〉 ステップ１：割り当てられた割付案(親割付)と同一の割
付を複製し、最小の変異操作を施し、子割付を生成す
る。

【００５２】ステップ２：生成された子割付の目的関数
値を求め、親割付の目的関数値との差分値を求める。

【００５３】ステップ３：ステップ２で得られた目的関
数差分値を、第１セルプロセッサが時刻ｔiで定めた最
適判断値Ａ(ｔi)と比較し、目的関数差分値がＡ(ｔi)よ
りも小さい場合は、子割付が最適割付に近いと判断し、
親割付を子割付で置換し、次に共有メモリ上に記憶され
ている最適割付の評価値とその子割付の評価値とを比較
し、子割付が優れている場合(最大値を求めるときは大
であり、最小値を求めるときは小である場合)に、子割
付を共有メモリ上の最適割付案として、子割付の評価値
を最適割付評価値としてそれぞれ置換し、淘汰世代カウ
ンタをリセットする。一方、目的関数差分値が最適判断
値Ａ(ｔi)より大きい場合は、淘汰世代カウンタ値を更
新し、更新した淘汰世代カウンタ値が、第１セルプロセ
ッサのステップ２で定められている該時刻ｔiにおける
自律淘汰世代値Ｂ(ｔi)より大きい場合、自律的に自身
の親割付案を淘汰すべきと判断し、共有メモリに記憶さ
れている最適割付を自ローカルメモリ上の親割付案に、
共有メモリに記憶されている最適計画評価値を自ローカ
ルメモリ上の親割付評価値にそれぞれ置き換え、淘汰世
代カウンタ値をリセットする。淘汰世代カウンタ値が自
律淘汰世代値Ｂ(ｔi)よりも小である場合は、そのまま
次のステップに進む。

【００５４】他の処理方法として、ステップ３におい
て、セルプロセッサが自律的に自身の親割付案を淘汰す
べきと判断した場合、自身の存在位置によって定まる局
所的な範囲内のプロセッサ群の有する親割付案の中から
最適なものを自身の親割付案として取り込んでもよい。

【００５５】また、ステップ３の処理方法において、自
身の親割付案を他の最適な割付案に置き換えるのではな
く、前記２種の割付案のそれぞれの要素を継承するよう
に交配(交叉)させ、得られた第３の割付案をセルプロセ
ッサの処理対象親割付案としてもよい。

【００５６】本発明による上記処理方法を用いると最適
解が短時間で得られる。この場合、最適解を得るための
処理時間は、次のようにして評価できる。

【００５７】第１セルプロセッサの処理は、他のセルプ
ロセッサ群と非同期に独立してなされ、しかも他のプロ
セッサより明らかに短時間で処理を終了できる。割付開
始を時刻ｔ_０とすると、ｔ_０以降の時刻ｔiでの最適判
断値Ａ(ｔi)と自律淘汰世代値Ｂ(ｔi)は、予め定めるこ
とができるからである。したがって、割付の立案に要す
る処理時間の評価において、第１のセルプロセッサの処
理時間は、評価不要である。

【００５８】第２のセルプロセッサ群の処理は、互いに
非同期に独立して自律的になされるので、処理時間は、
任意のセルプロセッサの処理の最長パスについてのみ検
討すればよい。

【００５９】ここで、ｎを割付対象要素数とし、Ｃ₁,Ｃ
₂,Ｃ₃をｎに依存しない定数とすると、第２のセルプロ
セッサ群が最適解を得るまでの実時間の処理回数オーダ
ーＯ(ｎ)は、 Ｏ(ｎ)＝(全体繰り返し回数) ×{(ステップ１)＋(ステップ２)＋(ステップ３)} ＝ｎ²／Ｐｍ×(Ｃ₁＋Ｃ₂×ｎ＋Ｃ₃) ＝Ｃ₄×ｎ³／Ｐｍ ここで、Ｐｍ＝ｎとすると、すなわちセルプロセッサを
割付対象数だけ備えると、 Ｏ(ｎ)＝Ｃ₄×ｎ³／(Ｐｍ＝ｎ)＝Ｃ₄×ｎ² となる。

【００６０】この結果、本発明によれば、高々ｎ²のオ
ーダーで、最適割付が得られる。従来の遺伝的アルゴリ
ズム等の方法では、最適解に準ずる解しか得られないの
に対して、本発明では、最適解が得られる点が重要であ
る。さらに、本発明の上記ステップ２では、多くのクラ
スの割付でｎに依存しない目的関数差分を得る方法が含
まれている。したがって、このクラスの多くの割付問題
においては、 Ｏ(ｎ)＝ｎ²／Ｐｍ×(Ｃ₁＋Ｃ₂＋Ｃ₃)＝Ｃ₄×ｎ で最適解が得られる。

【００６１】非同期伝送交換システムでは、今後一層の
大容量，高速性が強く求められるのは確実であり、本発
明による高効率，高速性が重要になってくる。

【００６２】

【発明の実施の態様】次に、図１〜図２２を参照して、
本発明による非同期伝送方法および非同期伝送装置の実
施例を説明する。

【００６３】図１は、本発明による非同期伝送装置の一
実施例の基本構成を示すブロック図である。非同期伝送
装置１は、様々なユーザからランダムにまたは同期的に
発生する送信要求データを所定サイズのセルに分割し、
記憶装置５に格納するセルバッファリング装置２と、デ
ータ発生密度および送出許容時間により定まる一時保存
データをもれなく記憶する記憶装置５と、タイマ３と、
このタイマ３により所定時間(フレーム)毎に起動され、
記憶装置５からセルを読出し、セル毎に定められている
周期時間，許容変動幅，許容応答時間，許容セル廃棄率
等を維持するようにセルを並べ換え、送信装置６に送信
要求する最適セル割付装置４とからなる。

【００６４】図２は、最適セル割付装置４の一実施例の
構成を示すブロック図である。最適セル割付装置４は、
入力制御ユニット４８と、出力制御ユニット４７と、超
並列制御ユニット４４と、相互に結合された複数のセル
プロセッサ４５と、共有メモリ４６とからなる。

【００６５】入力制御ユニット４８は、記憶装置５から
データを取り出し、共有メモリ４６に転送する。出力制
御ユニット４７は、セル割付結果を送信装置６に転送
し、送信要求を出す。

【００６６】超並列制御ユニット４４は、複数のセルプ
ロセッサ４５を並列処理動作を制御し、外部とのデータ
の入出力を制御し、共有メモリ４６を制御して、数値演
算をさせる装置である。

【００６７】図３は、１つのセルプロセッサ４５の構成
の一例を示すブロック図である。本実施例では、セルプ
ロセッサ４５が６４個並列に接続されているが、要求さ
れる処理能力や与えられる問題の複雑さに応じて、セル
プロセッサ４５の数を増減してもよいことはいうまでも
ない。各セルプロセッサ４５は、整数演算や実数演算等
の処理を実行する主演算装置(ＣＰＵ)４５９と、セルプ
ロセッサ自身が主に利用するが他のプロセッサからもア
クセス可能なローカルメモリ４５１０と、超並列制御ユ
ニット４４，共有メモリ４６，他のセルプロセッサ４５
とデータを交換するための複数のチャネル制御装置４５
１２と、ＣＰＵ４５９とローカルメモリ４５１０とチャ
ネル制御装置４５１２とを結合するバス４５１３とから
なる。このようなセルプロセッサ４５を採用すると、他
のセルプロセッサ４５との交信により動作を中断される
ことなく、主な論理処理を実行できる。

【００６８】図４は、最適セル割付装置４の処理手順を
示すフローチャートである。この処理手順は、ステップ
Ａとして、与えられた割付問題から、複数の初期案を生
成し、各々の目的関数値を演算し、複数のセルプロセッ
サ内に初期割付案と目的関数値を転送し、ステップＢ，
Ｃの並列処理を同時に起動する初期処理ステップを有す
る。

【００６９】ステップＢと複数のステップＣ₁〜₆₃は、
時間的に並列に、すなわち同時に処理するが、相互に抑
止または同期して処理することは無い。これにより、各
セルプロセッサの稼働率は、常に１００％が保証され
る。すなわち、各セルプロセッサの処理は、各セルプロ
セッサ自身で自律的になされる。

【００７０】図５は、図４のステップＢの最適判断／淘
汰制御の処理手順を示すフローチャートである。ステッ
プＢは、ステップＣの最適化処理において参照される最
適判断と自律淘汰世代値を離散的な時刻ｔi(ｉ＝１、２
……)毎に計算し、共有メモリ上にそれぞれＡ(ｔi)，Ｂ
(ｔi)として格納する。

【００７１】最適判断値は、ある親割付とその親割付か
ら生成された子割付とを比較して、いずれが最適案解に
近いかを判断するためのデータである。ここでは、最適
判断値を、例えば、 Ａ(ｔi)＝{Ｃ₁・ａ(ｔi)}／log(ｔi＊Ｐｍ) で定める。ただし、Ｃ₁は定数、ａ(ｔi)は時刻ｔiで生
成した０.０〜１.０に一様に分布する実乱数である。こ
れは図５に示されるように、時間の経過とともに小さく
なるような値と０.０の間に一様に分布する値の時系列
データとなる。本例では、Ｃ₁＝１００.０に選ばれてい
る。

【００７２】自律淘汰世代値は、親割付から子割付を生
成して最適解に近い割付を生存させる過程で参照される
もので、自律淘汰世代値から長期間改善(進化)が無かっ
た場合に他の優れた割付に置き替わる「軍拡競争」を模
擬するためのデータである。ここでは例えば、 Ｂ(ｔi)＝Ｃ₂×{１−１／log(ｔi)} で定める。ただし、Ｃ₂は定数であり、図５ではＣ₂＝１
０００に選ばれている。Ｂ(ｔi)は、時間ｔiの進捗とと
もに増大する値であり、割付立案の初期段階では各セル
プロセッサに割り当てられている割付案同志の生存のた
めの争い、すなわち「軍拡競争」が激しくなされ、一方
割付立案が進むと各割付案の改善(進化)には十分な時間
(チャンス)が与えられるようにするものである。

【００７３】以上の方法は、生物の進化は、急激な突然
変異や無理な交叉(交配)によりなされるのではなく、非
常にゆっくりと確実に最小の変異による増殖が複数の個
体(割付案)でなされることにより徐々に改善され、更に
進化が進み、適応度が高まると、一層進化の速度は低く
なるが、異なるグループまたは種の間では、生存競争が
残存し、一層適応度の高い個体が得られてゆくことを模
擬するものである。

【００７４】従来の遺伝的アルゴリズム手法において
は、交配，突然変異，淘汰の操作のみであり、しかも余
りに性急に割付案を変更してしまうため、進化の初期段
階で改善が停止してしまうという重大な問題があった。

【００７５】これに対して、本発明は、高効率の自律協
調型並列データ処理の基本的方法により、この問題を解
決している。

【００７６】図６は、図４のステップＣのセル割付けの
処理手順を示すフローチャートである。各ステップは、
以下のような処理を実行する。

【００７７】ステップＣ１０：与えられている親割付案
を複写し、最小の変異を与え子割付案を生成する。次
に、子割付案の目的関数値を演算し、子割付評価値とす
る。割付の詳細については、後述する。

【００７８】ステップＣ２０：親割付評価値と子割付評
価値との差分値と、上記ステップＢで共有メモリ上に記
憶されている最適判断値Ａ(ｔi)とを比較し、差分値が
Ａ(ｔi)より小さい場合は、子割付が親割付案よりも最
適解に近いものとして、ステップＣ７０に進む。

【００７９】差分値がＡ(ｔi)より大きい場合は、親割
付案が最適解に近く、進化なしとして、ステップＣ３０
に進む。

【００８０】ステップＣ３０：ローカルメモリ上の淘汰
世代カウンタを正に更新する。

【００８１】ステップＣ４０：上記ステップＢで共有メ
モリ上に記憶されている自律淘汰世代値Ｂ(ｔi)と淘汰
世代カウンタ値とを比較し、淘汰世代カウンタ値がＢ
(ｔi)より大きい場合は、自律淘汰が必要と判断し、ス
テップＣ５０に進む。そうでない場合は、ステップ１０
に戻る。

【００８２】ステップＣ５０：共有メモリに記憶されて
いる最適割付案および最適割付評価値をそれぞれローカ
ルメモリの親割付案および親割付評価値のエリアに複写
する。この処理は、セルプロセッサが自律的に自身の割
付案を淘汰したものと考えてよい。「軍拡競争」の勝者
として、他のセルプロセッサで得られている最適な割付
案が生存個体(割付案)数を増加させたのである。この処
理は、全てセルプロセッサでの最適割付が「軍拡」の権
利を有するものとしているが、例えば該当プロセッサか
ら有限のエリア内の最適割付としてもよい。このように
すると、生物進化のより厳密な模擬となる。割付対象数
ｎが大きくなった場合については、後者が有効である。

【００８３】次に、ステップＣ６０に進む。

【００８４】ステップＣ６０：淘汰世代カウンタを０に
リセットする。

【００８５】ステップＣ７０：子割付を構築し、割付の
目的関数値を演算し、子割付評価値とし、ステップＣ８
０に進む。

【００８６】ステップＣ８０：演算された子割付評価値
と共有メモリ上の最適割付評価値とを比較し、子割付評
価値が最適割付値よりも良好である場合は、ステップＣ
９０に進み、そうでない場合は、ステップＣ６０に戻
る。

【００８７】ステップＣ９０：上記子割付案と子割付評
価値をそれぞれ共有メモリ上の最適割付案、最適割付評
価値として複写する。これにより、該当プロセッサで生
成したし割付案が新たに「軍拡」の権利を得たことにな
る。次に、ステップＣ６０に進む。

【００８８】以上のように、図４のステップＣの最適化
処理は、許容された時間内に、自己増殖，最小の変異，
淘汰，評価，軍拡登録等の進化処理を自律的に無駄時間
無く繰り返す。

【００８９】図７は、定周期型，イベント型，メモリ型
の送信要求データの例を示す図である。某日の１８時１
０分３１秒００ｍ秒時点での送信要求データを示してい
る。既に述べたように、通信においては、大別して３種
のデータがある。

【００９０】(１)定周期型データとしては、Ａ，Ｂ，Ｃ
というデータがある。各々のデータは、属性が定められ
ており、例えばデータＡは５秒周期で、１回の送信に２
セル必要であり、周期に対する許容値は、先行が１秒，
遅れが３秒である。これは、１回送信した後４秒後から
８秒までの間にデータを送出すればよいことを示してい
る。また廃棄率は８.３％であるから、１,０００回のう
ち８３回の廃棄が許されている。

【００９１】(２)イベント型データとしては、Ｄ〜Ｈの
５種類のデータがある。例えばデータＤは、１８時１０
分２８秒２１ｍ秒で要求が発生しており、量としては１
セルで、遅れ時間は６秒まで許容されているので、１８
時１０分３４秒２１ｍ秒までに送信すればよい。

【００９２】(３)メモリ型データとしては、ＩとＪがあ
る。例えばデータＩは、１２時０分０秒０ｍ秒で要求が
発生しており、量としては１５６０セルで、既に８５セ
ルが送信済である。また、遅れ時間は、８時間が許容さ
れているので、２０時０分０秒０ｍ秒までに送信すれば
よい。ただし、許容セル廃棄率が０.０％であるため、
全てのデータをもれなく送信する必要がある。図７中の
優先度は、従来の方法で私用するものであり、番号が小
さいものほど優先度が高いことを示している。

【００９３】図８は、図７の送信要求データの時間上の
関係を示すタイムチャートである。横軸が時間であり、
縦軸がデータ種別である。また、送出単位(フレーム)
は、５秒としている。データＡは、前回フレームの後端
すなわち１８時１０分３０秒００に送出されている。本
例では、理解を容易にするため、データ伝送速度を小さ
くしてあり、１セルに０.５秒を要するものとしてい
る。データＡの周期は、５秒であるため、本来１８時１
０分３５秒に送出されるべきであり、このタイミングを
黒い逆三角形の記号で示している。しかし、他のデータ
との競合解消のため−１秒、＋３秒が許容されているの
で、前述の通り、１８時１０分３４秒から１８時１０分
３７秒の間に送出すればよい。この時間幅を実線で示し
てある。イベント型データＤは、発生時点を白い逆三角
形で示してあり、許容応答時間範囲を実線で示してい
る。既に発生から３秒が経過しているため、残りは３秒
である。

【００９４】以上のように、本問題は、伝送路という装
置に対するジョブショップスケジューリング問題に近似
している。

【００９５】図９は、従来のセル割付方法の一例を示す
フローチャートである。従来の方法では、要求データ毎
の優先度を重視し、送出対象フレーム内で優先度に従っ
てセルを並べるように動作する。本例でＳを並び順とす
ると、図９の処理ステップＡで Ｘ＝(Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ) を生成する。次に、各々のセルをこの順にステップＢで
並べて配置する。

【００９６】図１０は、図９のセル割付方法による送信
要求データの送信順序を示すタイムチャートである。該
当フレームには、Ａ₁，Ａ₂，Ｂ，Ｃ₁，Ｃ₂，Ｃ₃，Ｄ，
Ｅ，Ｆ，Ｇがセットされる。１フレームでは全部で１０
セルしか送出できないため、データＨは、配置されない
ことになる。

【００９７】ところが、データＨは、図８に示す通り、
このフレームで送出しないと、許容時間を維持できない
ため、結局廃棄されてしまう。これはステップＥでなさ
れる。次フレームでは空があるので、記憶装置５からメ
モリ型のデータＩが読出され、セットされる。

【００９８】このような優先度を主体に割付けると、セ
ルの廃棄がひんぱんに発生するようになる。

【００９９】また、図１０に示されるように、周期型デ
ータＡは、前回フレームの終端で送出されているのに、
今回のフレームでは先頭に配置されているため、周期変
動が大となり、品質の低下を招いている。さらに、デー
タＥ，Ｆは、許容応答時間を維持できていない。

【０１００】図１１は、本発明によるセル割付方法の一
例を示すフローチャートである。本発明では、図１１に
示すような割付を繰り返し遺伝的に実行するため、上記
課題を解決できる。この処理は、図４のステップＣの中
のステップＣ１０の詳細に示したものである。

【０１０１】まず、ステップ１０では、与えられている
割付検討順 Ｘ＝(Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｈ，Ｇ，Ｃ) の８つのデータ要素に対し、１から８まで一様に分布す
る乱数ｉ，ｊを生成し、ｉ番目とｊ番目のデータを入れ
替える。ここでは、ｉ＝２，ｊ＝６のため、該当位置に
あるＢとＨとを入れ替え、 Ｘ′＝(Ａ，Ｈ，Ｄ，Ｅ，Ｆ，Ｂ，Ｇ，Ｃ) を得る。この操作を突然変異という。また、Ｓを親割付
案Ｓ′をＳの子割付案という。

【０１０２】次にステップ２０で、上記Ｓ′の並び順に
従い、以下の割付を実行する。

【０１０３】ステップ２５で、データを取り出し、その
データが周期型の場合、前回または過去の送出タイミン
グに対して周期変動を最小にししかも遅れも小さくなる
位置に割付ける。一方、イベント型である場合は、最も
早く送出できる位置を探し、割付ける。これらは、図８
に示す送信可能時間帯の範囲でなされる。

【０１０４】図１２は、図１１のセル割付方法による送
信要求データの送信順序を示すタイムチャートである。
Ｓ′の先頭のデータはＡであるから、ステップ３０の処
理が実行され、１８時１０分３５秒の位置にデータＡの
２つのセルＡ₁，Ａ₂が割付けられる。前回のデータＡ
は、１８時１０分３０秒に送出されており、５秒の周期
性を維持するためである。もちろん、この位置が既に専
有されている場合は、図８に示す送信可能時間帯の範囲
で最も良い位置が選択される。さらに、現在の要求デー
タ量から２フレーム分の検討が必要なため、１８時１０
分４０秒にもデータＡ₁，Ａ₂が割付けられている。

【０１０５】次に、データＨを取り出し、ステップ３５
で最早時刻である１８時１０分３１秒に、５つのセルＨ
１〜Ｈ５が割付けられる。以下、同様にして、Ｄ，Ｅ，
Ｆ，Ｂ，Ｇ，Ｃが割付けられた後に、メモリ型データで
あるＩが空きに埋め込まれてゆく。この方法では、従来
の方法で廃棄されてしまっていたデータＨは、所定の応
答時間で送出され、また、他の周期型データやイベント
型データも、適正な位置に割付けられている。

【０１０６】Ｓ′の全ての要素について割付が完了し、
メモリ型データの埋め込みが終わると、ステップ４５
で、割付案Ｘ′に対する目的関数Ｆ(Ｘ′)が計算され
る。

【０１０７】目的関数としては、伝送効率や伝送品質が
考えられるので、ここでは、 Ｆ(Ｘ′)＝Ｃ₁×(廃棄セル数) ＋Ｃ₂×(遅れ時間の総計算) ＋Ｃ₃×(同期変動率) と定義する。ここでＣ₁，Ｃ₂，Ｃ₃は重ね定数であり、
伝送系の目的や状況により定める。例えば、Ｃ₁＝１，
Ｃ₂＝Ｃ₃＝０とすると、 Ｆ(Ｘ′)＝(廃棄セル数)＝０ となる。一方、親割付案であるＸでは、データＨの５つ
のセルが廃棄されるとすると、 Ｆ(Ｘ)＝５ となる。ここでは、廃棄セル数はできるだけ少なくした
いため、明らかに、割付案Ｘ′は、Ｘよりも優れている
といえる。

【０１０８】図１３は、目的関数値推移に含まれている
特有な性質を説明する図である。図１３の上段は、横軸
に立案回数ｉ毎に定まる割付順ベクトルＸ(i)を示し、
縦軸にその目的関数値を定義した図である。

【０１０９】割付順ベクトルの並びを少しずつ変化さ
せ、その時の目的関数値を比較しながら適正に、最適解
に近い割付順ベクトルに置換していく。この場合、図に
示すように、例えば、Ｘ(i)のような極点(本実施例で
は、極小点)になる場合でも次のベクトルに移行し、十
分な回数だけ立案した後に、最適解ベクトルＸoptに達
することがわかる。したがって、このように毎回新しい
割付Ｘi＋１を作成し、その目的関数値Ｆ(Ｘi＋１)を演
算し、前回の割付Ｘiの目的関数値Ｆ(Ｘi)と比較して、
より小さいまたは大きなものを最適割付候補としていく
処理を実行すればよい。

【０１１０】図１３の下段は、親割付案の目的関数値Ｆ
(Ｘi)と子割付案の目的関数Ｆ(Ｘi＋１)の差分ＡＦ(Ｘ
i)＝Ｆ(Ｘi＋１)−Ｆ(Ｘi)の検討回数に対する推移を示
している。上下の振動はあるが、最適割付案Ｘoptに近
づいてゆく。

【０１１１】厳密な実験によると、一般的な割付問題に
おいては、問題の内容に関わらず、このような形とな
り、Ｘiを時刻と考えた場合の振幅の減衰度合いは、例
えば、Ｃ／log(ｉ＋２)(本実施例では、Ｃ＝１００)の
相似形になることがわかった。

【０１１２】これは、ΔＦが正になった場合、つまり、
新しい割付の目的関数値が前回の計画より悪くなった時
でも(すなわち、最小化問題の場合には増加した時，最
大化問題の場合には減少した時)、Ｃ／log(ｉ＋２)より
小さな場合には、新しい割付を最適解候補に置換してゆ
くと、十分大きなｉに対応する順ベクトルＸiでは、必
ず最適解に達することを示している。

【０１１３】図１４は、最適割付案に達するまでの様子
を説明する図である。図１４の下段に示されるＡ(ｔi)
は、目的関数の差分値ΔＦｘｙと比較するための定数で
あり、ｔi＝１からｎ²まで、例えば、次のような値が、
最適判断／淘汰制御処理により、共有メモリに設定され
ている。ｔiは時刻(世代)である。

【０１１４】 Ａ(ｔi)＝{Ｃ₁・ａ(ｔi)}／log(ｔi＊Ｐｍ) ただし、log は、自然対数、ａ(ｔi)は、「０.０」から
「１.０」に分布する一様乱数である。すなわち、時間
(世代)ｔiの増加により、分布するレンジが小さくなる
ような値であればよい。Ｃ₁は、ΔＦにより容易に定め
ることができる。図１４は、Ｃ₁＝１００とした場合の
Ａ(ｔi)の分布エリアの推移を示す。Ａ(ｔi)は、存斜線
内に存在することになる。

【０１１５】以上の説明は、図４内の処理Ｃが各処理装
置毎になされる最適化についての説明である。

【０１１６】図１５は、図６のセル割付の処理が複数の
処理装置で並列的になされ、図５の最適判断／淘汰制御
により、分散協調的に全体として最適化がなされてゆく
様子を示す図である。横軸に時間(世代)推移ｔiを、縦
軸にステップＢにより定められる最適判断値Ａ(ｔi)、
自律淘汰世代値Ｂ(ｔi)セルプロセッサ毎の処理結果お
よび最適個体(割付案)と最適個体の評価値を定義したも
のである。

【０１１７】初期状態(ｔi＝１)ではセルプロセッサＣ
Ｐ１からセルプロセッサＣＰ８に、それぞれ初期割付案
(親割付案)として、ａ₁1，ｂ₁2，ｃ₁3，Ｄ₁4，Ｅ₁5，Ｆ
₁6，Ｇ₁7，Ｈ₁8がそれぞれ割り当てられている。時刻が
２になると、ＣＰ３の割付は、時刻２における淘汰世代
数連続して進化すなわち評価値の更新がなかったため、
時刻２までの最適割付案(ＢＥＳＴ個体)であるＤ₁4に置
換されてしまっている。

【０１１８】図１６は、図１５の処理の状況を時刻(世
代)毎の割付案の祖先(時刻＝１で各セルプロセッサに割
当られた割付案を示す)を根とするツリーで示す図であ
る。祖先を同一とする割付案群を「種」という。生物学
における「種」とは異なる。むしろ族に近い。ある
「種」が拡張(軍拡)する場合、最適化するセルプロセッ
サの数は一定であるから、他の計画案(個体)が消滅(淘
汰)する。本発明では、これは各セルプロセッサが、自
律的に淘汰すべきか判断し、他のより優れた割付案を自
身に取り込むように工夫している。後述するが、この場
合、図６の処理では、他の優れた割付案をそのまま、淘
汰されるべき割付案を消滅させ置き換えているが、両者
の要素がともに残るように交配することも考えられる。
図１６は、時刻１２において、ａ種が５個，ｂ種が１
個，ｄ種が２個だけ生存し、進化している状況を示す図
である。

【０１１９】図１７は、第１軸を時間経過(時刻)とし、
第２軸をセルプロセッサ番号とし、第３軸を各セルプロ
セッサ内の割付案の該当時刻における評価値として、図
１５の処理の推移を示す図である。時刻１では、各々に
個別の割付案が割付けられ、それぞれ異なる評価値を持
っている。１つのセルプロセッサに注目すると、評価値
が改善される場合とわずかに悪化する場合とがあるが、
変化を継続していくと、長期的には、明らかに改善され
る。

【０１２０】自律淘汰世代値の変化が所定時間無い場合
は、他のセルプロセッサで処理中の割付案で優れたもの
があると、それを取り込むようにしているので、進化が
一気に促進される。このように並列に協調しながら最適
化していくと、短時間で最適解に到達できる。

【０１２１】図１８は、第１軸を時間の推移(時刻)と
し、第２軸を全てのセルプロセッサの割付案評価値のう
ちで最適な評価値(最小値)として、従来例による処理の
推移と本発明による処理の推移とを比較して示す図であ
る。

【０１２２】従来の逐次実行型の最適化方法および最適
化装置を用いた場合に比べ、本発明による最適化方法お
よび最適化装置を用いると、極めて短時間に最適値に到
達できる。同一の計画許容時間が与えられている場合、
本発明では、従来方法と比較して、より複雑な問題すな
わち要素数が大きい問題を解けることを示している。

【０１２３】図１９は、本発明による最適化状況につい
て、セルプロセッサのマトリックス上に時刻毎のセルプ
ロセッサ内の割付案評価値を示すとともに、各評価値を
棒グラフとして鳥瞰的に示す図である。

【０１２４】図１９の左側は、縦横とも１６分割とし、
各交差矩形をセルプロセッサでの評価値度合いシンボル
としている。本実施例では、２５６個のセルプロセッサ
としている。

【０１２５】図１９の右側は、評価値を下降方向に定義
したものであり、したがって、棒グラフ先端が高いもの
ほど最適解に近いことを示している。

【０１２６】時刻ｔi＝１では、散発的に良い解が存在
しているが、ｔi＝ｍでは、各プロセッサ毎の最適化処
理により全体的に改善され、また、最適解に近い割付案
グループが形成されている。時刻ｔiが十分大きいｎに
なると、全体が大きく改善され、最適解が出現してい
る。

【０１２７】以上は、各セルプロセッサ内の割付案を１
つの個体とした「人工生命」と考え、この場合の淘汰の
方向が各個体の身長増加と考えればよい。ここでの身長
とは、もちろん「セル割付」での目的関連数値の減少の
軸方向である。

【０１２８】本発明の第２の要点は、このように従来実
験的になされていた「人工生命」の早期育成の手法を提
供し、かつ「人工生命」技術を産業に応用する手法で提
供できることにある。

【０１２９】図２０は、従来の最適化手法と本発明の最
適化手法とを同一の時間軸上に示す図である。図２０の
上段の図は、全ての存在する解をランダムに探すランダ
ム探索法によるもので、例えば、「巡回セールスマン問
題」での都市の数を１００とした場合、最適解到達に必
要な最悪値としては、１００！≒１０¹⁵⁷の検討回数が
必要である。

【０１３０】図２０の中段の図は、従来の遺伝的アルゴ
リズム(ＧＡ)とシミュレーテッドアニーリング等の最適
化手法による結果を示している。ＧＡは、初期段階で比
較的に良い値に収束しているが、検討回数が増加して
も、改善が無くなり、最適解に到達しない。この傾向
は、計画の要素数ｎが大きくなるほど顕著となり、厳密
な最適問題には、ＧＡを適用し難い。

【０１３１】シミュレーテッド・アニーリング等の手法
は、徐々にではあるが確実に最適解に近づいてゆきｎ³
〜ｎ⁵程度の検討回数で最適解に到達する。ランダム検
索に比べると、ｎ！からｎ⁵に大きく高速化されてい
る。しかし、ｎが１０,０００を超える大規模な問題の
場合は、現在の逐次実行型のコンピュータの最高の処理
速度のものを用いたとしても、現実的には、やはり実現
が困難である。また、将来的にも、既に処理速度が限界
に近づいているため、実用化できないことになる。

【０１３２】図２０の下段の図は、本発明による最適化
状況を示したものである。最適化は原理的にはｎ／Ｐｍ
すなわち並列度数分だけ高速化される。現実的には１０
０％の並列効率は、困難なので、本実施例では、Ｐｍ＝
ｃ．ｎ(ｃは１より大である制定数)として、ｎ²オーダ
ーの検討回数で最適解に到達している。今後のコンピュ
ータのアーキテクチャは検討回数で最適解に到達してい
る。今後のコンピュータのアーキテクチャは膨大な数の
セルプロセッサを超並到に仮想ハイパー接続したものに
なると予想される。このようなコンピュータを用いれ
ば、各々のセルプロセッサでは、確実に最適化処理し、
しかも時間の推移により自律的な淘汰，交配等を実行す
る本発明の方法は、有利である。

【０１３３】図２１は、送信要求データが物理的伝送容
量をオーバーした場合の従来の取扱いの様子と本発明に
よる取扱いの様子とを比較して示す図である。従来の方
法では、データの廃棄や応答遅れが発生しているのに対
して、本発明では、各データの許容範囲を最大限に活用
できるため、データ廃棄や応答遅れが大きく減少してい
る。さらに、応答遅れの減少により、伝送効率が向上し
ている。

【０１３４】図２２は、実データを用いて、所定時間伝
送した場合の従来の伝送の結果と本発明による伝送の結
果とを定量的に示す図である。実線が本発明による結果
であり、破線が従来の方法による結果である。各評価
は、 (伝送効率％)＝(送出量／要求量)×１００ (廃棄セル数(セル個)) (変動幅％) ＝(周期型データの周期時間に対する変動標準偏差比) (応答性率％)＝(イベント型データの発生〜送出までの時間／許容時間) ×１００ で定義している。本発明による結果は、全ての項目にお
いて優れている。

【０１３５】現在実用化されまたは計画されているデー
タ通信ネットワークは、伝送量／伝送速度が従来の概念
を超える規模となってきているが、本発明による非同期
伝送方法および非同期伝送装置は、規模が増大するほ
ど、その効果が大きくなる。

【０１３６】

【発明の効果】本発明によれば、ユーザからランダムに
または周期的に発生する送信要求データを所定サイズの
セルに分割して記憶装置に格納するセルバッファリング
と、データ発生密度および送出許容時間により定まる一
時保存データをもれなく記憶する記憶装置と、所定時間
(フレーム)毎にタイマにより起動され記憶装置からセル
を読出しセル毎に定められている周期時間，許容変動
幅，許容応答時間，許容セル廃棄率を維持するように遺
伝的アルゴリズムにより並べ換え送信装置に送信要求す
る最適セル割付装置とを備え、伝送効率および伝送品質
の低下が極めて少ない非同期伝送装置および非同期伝送
方法が得られる。

【図面の簡単な説明】

【図１】本発明による非同期伝送装置の一実施例の基本
構成を示すブロック図である。

【図２】最適セル割付装置４の一実施例の構成を示すブ
ロック図である。

【図３】１つのセルプロセッサ４５の構成の一例を示す
ブロック図である。

【図４】最適セル割付装置４の処理手順を示すフローチ
ャートである。

【図５】図４のステップＢの最適判断／淘汰制御の処理
手順を示すフローチャートである。

【図６】図４のステップＣのセル割付けの処理手順を示
すフローチャートである。

【図７】定周期型，イベント型，メモリ型の送信要求デ
ータの例を示す図である。

【図８】図７の送信要求データの時間上の関係を示すタ
イムチャートである。

【図９】従来のセル割付方法の一例を示すフローチャー
トである。

【図１０】図９のセル割付方法による送信要求データの
送信順序を示すタイムチャートである。

【図１１】本発明によるセル割付方法の一例を示すフロ
ーチャートである。

【図１２】図１１のセル割付方法による送信要求データ
の送信順序を示すタイムチャートである。

【図１３】目的関数値推移に含まれている特有な性質を
説明する図である。

【図１４】最適割付案に達するまでの様子を説明する図
である。

【図１５】図６のセル割付の処理が複数の処理装置で並
列的になされ、図５の最適判断／淘汰制御により、分散
協調的に全体として最適化がなされてゆく様子を示す図
である。

【図１６】図１５の処理の状況を時刻(世代)毎の割付案
の祖先(時刻＝１で各セルプロセッサに割当られた割付
案を示す)を根とするツリーで示す図である。

【図１７】第１軸を時間経過(時刻)とし、第２軸をセル
プロセッサ番号とし、第３軸を各セルプロセッサ内の割
付案の該当時刻における評価値として、図１５の処理の
推移を示す図である。

【図１８】第１軸を時間の推移(時刻)とし、第２軸を全
てのセルプロセッサの割付案評価値のうちで最適な評価
値(最小値)として、従来例による処理の推移と本発明に
よる処理の推移とを比較して示す図である。

【図１９】本発明による最適化状況について、セルプロ
セッサのマトリックス上に時刻毎のセルプロセッサ内の
割付案評価値を示すとともに、各評価値を棒グラフとし
て鳥瞰的に示す図である。

【図２０】従来の最適化手法と本発明の最適化手法とを
同一の時間軸上に示す図である。

【図２１】送信要求データが物理的伝送容量をオーバー
した場合の従来の取扱いの様子と本発明による取扱いの
様子とを比較して示す図である。

【図２２】実データを用いて、所定時間伝送した場合の
従来の伝送の結果と本発明による伝送の結果とを定量的
に示す図である。

【図２３】本発明の適用分野であるＡＴＭ広域ネットワ
ークシステム(ＡＴＭ−ＷＡＮ)の系統構成の一例を示す
図である。

【図２４】本発明の適用分野であるＡＴＭブロードキャ
スト送信システム(ＡＴＭ多重放送)の系統構成の一例を
示す図である。

【図２５】本発明の適用分野である光ビーコン等による
マルチバンドＡＴＭシステムの系統構成の一例を示す図
である。

【図２６】従来のパケット交換システムの概要を示す系
統図である。

【図２７】従来の非同期伝送交換システムの概要を示す
系統図である。

【図２８】具体的な例を用いて、パケット交換システム
と従来の非同期伝送交換システムとの違いを説明する図
である。

【図２９】パケット交換システムの問題点を説明する図
である。

【図３０】図２９と同じ前提条件で非同期伝送交換シス
テムの伝送状況を示す図である。

【図３１】データ廃棄率の増大に対する従来の対応策を
示す図である。

【図３２】非同期伝送交換システムで発生する送信要求
データの種類と伝送路の負荷パターンとの関係を説明す
る図である。

【符号の説明】

１ 非同期伝送装置 ２ セルバッファリング装置 ３ タイマ ４ 最適セル割付装置 ５ 記憶装置 ６ 送信装置

───────────────────────────────────────────────────── フロントページの続き (72)発明者 中村 兼一 茨城県日立市幸町三丁目２番１号 日立 エンジニアリング株式会社内 (72)発明者 佐野 豊 茨城県日立市大みか町五丁目２番１号 株式会社 日立製作所 大みか工場内 (72)発明者 伊藤 芳三 茨城県日立市大みか町五丁目２番１号 株式会社 日立製作所 大みか工場内 (72)発明者 八尋 正和 茨城県日立市大みか町五丁目２番１号 株式会社 日立製作所 大みか工場内 (72)発明者 阿部 登 茨城県日立市大みか町五丁目２番１号 株式会社 日立製作所 大みか工場内 (72)発明者 佐藤 良幸 茨城県日立市大みか町五丁目２番１号 株式会社 日立製作所 大みか工場内 (56)参考文献 特開 平７−170270（ＪＰ，Ａ) 特開 平６−309408（ＪＰ，Ａ) 特開 平７−141318（ＪＰ，Ａ) 1994信学春大Ｂ521「ＶＰシェーパー におけるＶＣ−ＱＯＳコントロール方 式」 ＳＳＥ95−157「ニューラルネットワ ークを用いたトラヒックシェーピング方 式」 (58)調査した分野(Int.Cl.⁷，ＤＢ名) H04L 12/56

Claims (10)

(57)【特許請求の範囲】
1. 【請求項１】 ユーザからランダムにまたは周期的に発
   生する送信要求データを所定サイズのセルに分割し、保
   存する手順と、データ発生密度および送出許容時間によ
   り定まる一時保存データをもれなく記憶する手順と、所
   定時間(フレーム)毎に保存された送信要求データから前
   記セルを読出しセル毎に定められている周期時間，許容
   変動幅，許容応答時間，許容セル廃棄率を維持するよう
   に並べ換えて最適なセル割付けを実行し、送信を要求す
   る手順とを有する非同期伝送方法において、 前記最適なセル割付手順が、並列処理する複数の処理手
   順からなり、 前記各処理手順が、それぞれ与えられた親割付案から予
   め定められた変異操作により新たに子割付案を生成する
   割付変更手順と、前記親割付案と前記子割付案とを比較
   評価し更新する割付評価手順および自律的淘汰手順とを
   含み、 前記割付評価手順が、前記親割付案と前記子割付案との
   目的関数値の差分を計算し、前記目的関数値の差分が予
   め与えられた最適判断値よりも小さい場合には前記親割
   付案を前記子割付案に置換する処理を繰り返すととも
   に、前記子割付案が前記並列処理により得られた複数の
   割付案の中で最適な場合は前記子割付案を最適計画案と
   して登録し、前記差分が最適判断値よりも大きい時は当
   該親割付案を保持し、 前記自律的淘汰手順が、前記処理手順における親割付案
   の変更が発生しなかった時間が予め与えられた自律淘汰
   世代値と比較して大きい時は最適割付案を前記処理手順
   の新たな親割付案として置換する ことを特徴とする非同
   期伝送方法。
2. 【請求項２】 ユーザからランダムにまたは周期的に発
   生する送信要求データを所定サイズのセルに分割し、保
   存する手順と、データ発生密度および送出許容時間によ
   り定まる一時保存データをもれなく記憶する手順と、所
   定時間(フレーム)毎に保存された送信要求データから前
   記セルを読出しセル毎に定められている周期時間，許容
   変動幅，許容応答時間，許容セル廃棄率を維持するよう
   に並 べ換えて最適なセル割付けを実行し、送信を要求す
   る手順とを有し、前記最適なセル割付手順が、各々同一
   時間経過に対して各々自律的にセル割付の最適化を図り
   ながら自身の最適化進捗の状況を判断し、所定時間連続
   して割付結果に変化が無い場合には他の割付け手順で生
   成されより優れた割付案を自身に取り込み自律協調的に
   最適化する自律淘汰手順とを含む非同期伝送方法におい
   て、 前記最適なセル割付手順が、並列処理する複数の処理手
   順からなり、 前記各処理手順が、それぞれ与えられた親割付案から予
   め定められた変異操作により新たに子割付案を生成する
   割付変更手順と、前記親割付案と前記子割付案とを比較
   評価し更新する割付評価手順および自律的淘汰手順とを
   含み、 前記割付評価手順が、前記親割付案と前記子割付案との
   目的関数値の差分を計算し、前記目的関数値の差分が予
   め与えられた最適判断値よりも小さい場合には前記親割
   付案を前記子割付案に置換する処理を繰り返すととも
   に、前記子割付案が前記並列処理により得られた複数の
   割付案の中で最適な場合は前記子割付案を最適計画案と
   して登録し、前記差分が最適判断値よりも大きい時は当
   該親割付案を保持し、 前記自律的淘汰手順が、前記処理手順における親割付案
   の変更が発生しなかった時間が予め与えられた自律淘汰
   世代値と比較して大きい時は最適割付案を前記処理手順
   の新たな親割付案として置換する ことを特徴とする非同
   期伝送方法。
3. 【請求項３】 ユーザからランダムにまたは周期的に発
   生する送信要求データを所定サイズのセルに分割し、保
   存する手順と、データ発生密度および送出許容時間によ
   り定まる一時保存データをもれなく記憶する手順と、所
   定時間(フレーム)毎に保存された送信要求データから前
   記セルを読出しセル毎に定められている周期時間，許容
   変動幅，許容応答時間，許容セル廃棄率を維持するよう
   に並べ換えて最適なセル割付けを実行し、送信を要求す
   る手順とを有する非同期伝送方法において、 前記最適なセル割付手順が、送信要求データ毎に予め定
   められている送出可能時間帯の時間範囲内で前記データ
   の過去の送出タイミングに基づいて割付位置を定めるこ
   とを特徴とする非同期伝送方法。
4. 【請求項４】 ユーザからランダムにまたは周期的に発
   生する送信要求データを所定サイズのセルに分割し、保
   存する手順と、データ発生密度および送出許容時間によ
   り定まる一時保存データをもれなく記憶する手順と、所
   定時間(フレーム)毎に保存された送信要求データから前
   記セルを読出しセル毎に定められている周期時間，許容
   変動幅，許容応答時間，許容セル廃棄率を維持するよう
   に並べ換えて最適なセル割付けを実行し、送信を要求す
   る手順とを有し、前記最適なセル割付手順が、各々同一
   時間経過に対して各々自律的にセル割付の最適化を図り
   ながら自身の最適化進捗の状況を判断し、所定時間連続
   して割付結果に変化が無い場合には他の割付け手順で生
   成されより優れた割付案を自身に取り込み自律協調的に
   最適化する自律淘汰手順とを含む非同期伝送方法におい
   て、 前記最適なセル割付手順が、送信要求データ毎に予め定
   められている送出可能時間帯の時間範囲内で前記データ
   の過去の送出タイミングに基づいて割付位置を定めるこ
   とを特徴とする非同期伝送方法。
5. 【請求項５】 ユーザからランダムにまたは周期的に発
   生する送信要求データを所定サイズのセルに分割し、保
   存する手順と、データ発生密度および送出許容時間によ
   り定まる一時保存データをもれなく記憶する手順と、所
   定時間(フレーム)毎に保存された送信要求データから前
   記セルを読出しセル毎に定められている周期時間，許容
   変動幅，許容応答時間，許容セル廃棄率を維持するよう
   に並べ換えて最適なセル割付けを実行し、送信を要求す
   る手順とを有する非同期伝送方法において、 前記最適なセル割付手順が、並列処理する複数の処理手
   順からなり、 前記各処理手順が、それぞれ与えられた親割付案から予
   め定められた変異操作により新たに子割付案を生成する
   割付変更手順と、前記親割付案と前記子割付案とを比較
   評価し更新する割付評価手順および自律的淘汰手順とを
   含み、 前記割付評価手順が、前記親割付案と前記子割付案との
   目的関数値の差分を計算し、前記目的関数値の差分が予
   め与えられた最適判断値よりも小さい場合には前記親割
   付案を前記子割付案に置換する処理を繰り返すととも
   に、前記子割付案 が前記並列処理により得られた複数の
   割付案の中で最適な場合は前記子割付案を最適計画案と
   して登録し、前記差分が最適判断値よりも大きい時は当
   該親割付案を保持し、 前記自律的淘汰手順が、前記処理手順における親割付案
   の変更が発生しなかった時間が予め与えられた自律淘汰
   世代値と比較して大きい時は最適割付案を前記処理手順
   の新たな親割付案として置換し、 前記最適なセル割付手順が、送信要求データ毎に予め定
   められている送出可能時間帯の時間範囲内で前記データ
   の過去の送出タイミングに基づいて割付位置を定めるこ
   とを特徴とする非同期伝送方法。
6. 【請求項６】 ユーザからランダムにまたは周期的に発
   生する送信要求データを所定サイズのセルに分割し記憶
   装置に格納するセルバッファリング装置と、データ発生
   密度および送出許容時間により定まる一時保存データを
   もれなく記憶する記憶装置と、所定時間(フレーム)毎に
   タイマにより起動され、前記記憶装置から前記セルを読
   出しセル毎に定められている周期時間，許容変動幅，許
   容応答時間，許容セル廃棄率を維持するように並べ換
   え、送信装置に送信を要求する最適セル割付装置とを備
   えた非同期伝送装置において、 前記最適セル割付装置が、並列処理する複数の処理装置
   からなり、 前記各処理装置が、それぞれ与えられた親割付案から予
   め定められた変異操作により新たに子割付案を生成する
   割付変更手段と、前記親割付案と前記子割付案とを比較
   評価し更新する割付評価手段および自律的淘汰手段とを
   備え、 前記割付評価手段が、前記親割付案と前記子割付案との
   目的関数値の差分を計算し、前記目的関数値の差分が予
   め与えられた最適判断値よりも小さい場合には前記親割
   付案を前記子割付案に置換する処理を繰り返すととも
   に、前記子割付案が前記並列処理により得られた複数の
   割付案の中で最適な場合は前記子割付案を最適計画案と
   して登録し、前記差分が最適判断値よりも大きい時は当
   該親割付案を保持する手段であり、 前記自律的淘汰手段が、前記処理装置における親割付案
   の変更が発生しなかった時間が予め与えられた自律淘汰
   世代値と比較して大きい時は最適割付案を前記 処理装置
   の新たな親割付案として置換する手段である ことを特徴
   とする非同期伝送装置。
7. 【請求項７】 ユーザからランダムにまたは周期的に発
   生する送信要求データを所定サイズのセルに分割し記憶
   装置に格納するセルバッファリング装置と、データ発生
   密度および送出許容時間により定まる一時保存データを
   もれなく記憶する記憶装置と、所定時間(フレーム)毎に
   タイマにより起動され、前記記憶装置から前記セルを読
   出しセル毎に定められている周期時間，許容変動幅，許
   容応答時間，許容セル廃棄率を維持するように並べ換
   え、送信装置に送信を要求する最適セル割付装置とを備
   え、前記最適セル割付装置が、複数の処理装置が各々同
   一時間経過に対して各々自律的にセル割付の最適化を図
   りながら自身の最適化進捗の状況を判断する割付評価手
   段と、所定時間連続して割付結果に変化が無い場合には
   他の処理装置で生成されより優れた割付案を自身に取り
   込み自律協調的に最適化する自律淘汰手段とを含む非同
   期伝送装置において、 前記最適セル割付装置が、並列処理する複数の処理装置
   からなり、 前記各処理装置が、それぞれ与えられた親割付案から予
   め定められた変異操作により新たに子割付案を生成する
   割付変更手段と、前記親割付案と前記子割付案とを比較
   評価し更新する割付評価手段および自律的淘汰手段とを
   備え、 前記割付評価手段が、前記親割付案と前記子割付案との
   目的関数値の差分を計算し、前記目的関数値の差分が予
   め与えられた最適判断値よりも小さい場合には前記親割
   付案を前記子割付案に置換する処理を繰り返すととも
   に、前記子割付案が前記並列処理により得られた複数の
   割付案の中で最適な場合は前記子割付案を最適計画案と
   して登録し、前記差分が最適判断値よりも大きい時は当
   該親割付案を保持する手段であり、 前記自律的淘汰手段が、前記処理装置における親割付案
   の変更が発生しなかった時間が予め与えられた自律淘汰
   世代値と比較して大きい時は最適割付案を前記処理装置
   の新たな親割付案として置換する手段である ことを特徴
   とする非同期伝送装置。
8. 【請求項８】 ユーザからランダムにまたは周期的に発
   生する送信要求データを所定サイズのセルに分割し記憶
   装置に格納するセルバッファリング装置と、 データ発生
   密度および送出許容時間により定まる一時保存データを
   もれなく記憶する記憶装置と、所定時間(フレーム)毎に
   タイマにより起動され、前記記憶装置から前記セルを読
   出しセル毎に定められている周期時間，許容変動幅，許
   容応答時間，許容セル廃棄率を維持するように並べ換
   え、送信装置に送信を要求する最適セル割付装置とを備
   えた非同期伝送装置において、 前記最適セル割付装置が、送信要求データ毎に予め定め
   られている送出可能時間帯の時間範囲内で前記データの
   過去の送出タイミングに基づいて割付位置を定める手段
   である ことを特徴とする非同期伝送装置。
9. 【請求項９】 ユーザからランダムにまたは周期的に発
   生する送信要求データを所定サイズのセルに分割し記憶
   装置に格納するセルバッファリング装置と、データ発生
   密度および送出許容時間により定まる一時保存データを
   もれなく記憶する記憶装置と、所定時間(フレーム)毎に
   タイマにより起動され、前記記憶装置から前記セルを読
   出しセル毎に定められている周期時間，許容変動幅，許
   容応答時間，許容セル廃棄率を維持するように並べ換
   え、送信装置に送信を要求する最適セル割付装置とを備
   え、前記最適セル割付装置が、複数の処理装置が各々同
   一時間経過に対して各々自律的にセル割付の最適化を図
   りながら自身の最適化進捗の状況を判断する割付評価手
   段と、所定時間連続して割付結果に変化が無い場合には
   他の処理装置で生成されより優れた割付案を自身に取り
   込み自律協調的に最適化する自律淘汰手段とを含む非同
   期伝送装置において、 前記最適セル割付装置が、送信要求データ毎に予め定め
   られている送出可能時間帯の時間範囲内で前記データの
   過去の送出タイミングに基づいて割付位置を定める手段
   であることを特徴とする非同期伝送装置。
10. 【請求項１０】 ユーザからランダムにまたは周期的に
    発生する送信要求データを所定サイズのセルに分割し記
    憶装置に格納するセルバッファリング装置と、データ発
    生密度および送出許容時間により定まる一時保存データ
    をもれなく記憶する記憶装置と、所定時間(フレーム)毎
    にタイマにより起動され、前記記憶装置から前記セルを
    読出しセル毎に定められている周期時間，許容変動幅，
    許容応 答時間，許容セル廃棄率を維持するように並べ換
    え、送信装置に送信を要求する最適セル割付装置とを備
    えた非同期伝送装置において、 前記最適セル割付装置が、並列処理する複数の処理装置
    からなり、 前記各処理装置が、それぞれ与えられた親割付案から予
    め定められた変異操作により新たに子割付案を生成する
    割付変更手段と、前記親割付案と前記子割付案とを比較
    評価し更新する割付評価手段および自律的淘汰手段とを
    備え、 前記割付評価手段が、前記親割付案と前記子割付案との
    目的関数値の差分を計算し、前記目的関数値の差分が予
    め与えられた最適判断値よりも小さい場合には前記親割
    付案を前記子割付案に置換する処理を繰り返すととも
    に、前記子割付案が前記並列処理により得られた複数の
    割付案の中で最適な場合は前記子割付案を最適計画案と
    して登録し、前記差分が最適判断値よりも大きい時は当
    該親割付案を保持する手段であり、 前記自律的淘汰手段が、前記処理装置における親割付案
    の変更が発生しなかった時間が予め与えられた自律淘汰
    世代値と比較して大きい時は最適割付案を前記処理装置
    の新たな親割付案として置換する手段であり、 前記最適セル割付装置が、送信要求データ毎に予め定め
    られている送出可能時間帯の時間範囲内で前記データの
    過去の送出タイミングに基づいて割付位置を定める手段
    であることを特徴とする非同期伝送装置。