情報ネットワークのスケジューリングのためのm-バランス列とその拡張に関する研究

信息网络调度的m平衡列及其扩展研究

基本信息

批准号：
13780358
负责人：
三好直人
金额：
$ 1.02万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

项目摘要

本研究の課題は,複数種類の文字を並べて無限に長い文字列を構成する際に,各文字に対して列の中で現れる割合(出現率)が与えられているときに,それを満足しながら如何にバランス良く(なるべく均等に)文字を並べるかという問題への取り組み,ならびにその情報ネットワーク等のスケジューリングや制御への応用についてです.この課題の遂行,およびこれに関連するテーマとして,今年度は以下の研究を行いました.これまでに研究代表者の研究室では,上記の問題に対して「m-バランス列」という概念を提唱しています.これは,mに0以上の整数値を代入することによって,各文字が任意の出現率を持つ任意の(半)無限列に対してバランスの良さの指標を与える(mの値が小さい程バランスが良い)ものです.また,このm-バランス列を生成するアルゴリズムとして,ビリヤード列(billiard sequences)と呼ばれる文字列を生成するものを考え,N種の文字からなるビリヤード列は必ず(N-1)-バランス列になることを示しています.しかし,このアルゴリズムの問題点として,与えられた出現率の組によっては,よりバランスの良い列が存在するかもしれないにもかかわらず,それが実現されない場合がありました.これは,生成される文字列のバランスの良さが,アルゴリズムの初期値に大きく依存することに依ります.この問題に対して,文字の出現率が有理数であるときには,生成される文字列が周期列になることを利用し,確率的なアルゴリズムによって,ビリヤード列を生成するアルゴリズムに良い初期値を与えることに成功しました.尚,この研究成果は現在,海外の学術論文誌に投稿中です.上記に加えて,応用に関する課題として,ネットワークのスケジューリングにおいて重要な待ち行列システムの並列推定に関する研究も行いました.また,インターネットにおける性能や通信品質の推定法に関する研究も行っています.

这项研究的主题是解决如何以平衡的方式（尽可能均匀地）排列角色的问题，同时满足当字符串排列在字符串中并满足它们的比率（出现率），并满足它们，并在信息网络的调度和控制中使用它们等。今年，我们进行了以下研究。迄今为止，研究人员的实验室提出了上述问题的“ M-BALANCE序列”的概念。这是为M为M分配0或以上的整数值，并为任何（半无限）无限序列提供良好平衡的索引，其中每个字符具有任意发生率（M值越小，平衡越好）。此外，作为生成这种M平衡序列的算法，我们使用了台球序列（台球）。考虑到生成一个字符串，称为序列），我们表明由N型字符组成的台球序列总是变为（N-1）平衡的序列。但是，这种算法的问题在于，某些事件可能具有更好的平衡，但这可能无法实现。这取决于生成的字符串的良好平衡在很大程度上取决于算法的初始值。对于这个问题，字符的出现率是当它是一个有理数时，生成的字符串变为周期序列，使用概率算法，我们成功地为生成台球序列的算法给出了良好的初始值。此外，这项研究目前已提交给海外学术期刊。除上述内容外，我们还对排队系统的并行估计进行了研究，这对于网络调度很重要，作为应用程序问题。我们还正在进行有关估计互联网性能和沟通质量的研究。