日時：6月21日（月） 15:00〜17:30 場所：京都大学 本部構内 工学部総合校舎 総合213講義室 講演題目と講演者： ・ 田中 啓之（京都大学大学院情報学研究科システム科学専攻 修士課程１年） 「リアルタイム・ハイブリッド FEC/ARQのモデル化と性能解析」講演要旨 ・ 前田 繁章（京都大学大学院情報学研究科数理工学専攻 修士課程１年） 「相関のある到着過程を持つ離散時間待ち行列モデルの解析」講演要旨 ・ 山本 勝樹（大阪大学大学院 基礎工学研究科システム創成専攻 修士課程１年） 「環状ネットワークにおけるロードプライシング」講演要旨 ・ 石口 文男（大阪大学大学院 基礎工学研究科システム創成専攻 修士課程１年） 「TVPI連立線形不等式問題に対するAspvall-Shiloachのアルゴリズムの実装とその実験」講演要旨 ・ 今村 友和（京都大学大学院情報学研究科 通信情報システム専攻 博士課程１年） 「Approximation Algorithms for the Vertex Cover Problem （最小頂点被覆問題の近似アルゴリズム）」講演要旨
リアルタイム・ハイブリッド FEC/ARQのモデル化と性能解析
田中 啓之（京都大学大学院情報学研究科数理工学専攻 修士課程１年）
インターネットを利用したライブ中継やテレビ会議システム等のリアルタイム コンテンツサービスでは，ネットワークの輻輳に起因するパケットロスを，限 られた時間内で効率よく修復する通信方式が求められている．従来，一般的に 利用されてきた通信方式は二つに大別される．一つはロスしたパケットを再送 する ARQ (自動再送要求) と呼ばれる方式であり，もう一つは伝送するデータ に冗長性を持たせ，ある程度のパケットロスが起こっても元のデータを復号で きる FEC（前方誤り訂正) と呼ばれる方式である．近年，この両者の長所を組 み合わせたハイブリッド FEC/ARQ 通信方式が提案されたが、その性能評価は 十分になされてはいない．そこで本研究では，このハイブリッド FEC/ARQ を 用いた通信システムの確率モデルを構築し，その性能評価指標として，許容遅 延までの全パケット受信確率と，復号化のための冗長性を含む全送信パケット 数分布を解析的に導出した．また，数値計算を行った結果，これら二つの性能 評価指標間の興味深い関係が明らかになった．
相関のある到着過程を持つ離散時間待ち行列モデルの解析
前田 繁章（京都大学大学院情報学研究科数理工学専攻 修士課程１年）
インターネットにおける通信トラヒックには長期依存性や自己相似性と呼ばれ る長期間にわたる強い相関があることが知られており，このような長期にわた る相関がシステムに及ぼす影響を量的に評価することが重要な課題となってい る．しかしながら，従来提案されてきたトラヒックモデルはそうした長期間に わたる強い相関を表現できないものや，たとえ表現できたとしても解析が困難 なものが大半を占めており，解析的な結果に基づいた性能指標の定量的考察は 十分になされていない．本研究で考察する到着過程は，自己相関関数の特徴が 捉えやすいことに加えて，短期依存性から長期依存性にわたる幅広い性質の相 関を表現可能なモデルとなっている．さらに，本研究で考察する到着過程を入 力とする待ち行列モデルは，シミュレーションに頼らず解析的に性能指標を得 られるため，通信ネットワークの性能評価のための基礎モデルとして非常に魅 力的であると言える．本研究では，通信システムにおいて最も重要な性能指標 の一つであるパケット呼損率に注目し，数値計算を通して通信トラヒックが持 つ相関構造がシステムに及ぼす影響について考察している．
環状ネットワークにおけるロードプライシング
山本 勝樹（大阪大学大学院 基礎工学研究科システム創成専攻 修士課程１年）
ロードプライシング（道路課金）とは, 利用の集中する道路に対し課金を行うことで, 交通混雑の緩和や環境への負荷軽減を図ることなどを目的としており, 国内では首都高速や阪神高速で導入されている. 本研究では, 環状道路に対して, 目標として設定された交通量を達成するような課金を決定する問題を扱う. Dial [1999,2000] は, 類似の課金問題を一種の多品種フロー問題に帰着させて解く手法を提案しているが, 計算量の上界は示されていない. 本研究では, Shepherd-Zhang [2001] の多品種フロー問題に対するアルゴリズムを応用することで, 環状道路上の課金問題を強多項式時間で解く組合せアルゴリズムを提案する.
TVPI連立線形不等式問題に対するAspvall-Shiloachのアルゴリズムの実装とその実験
石口 文男（大阪大学大学院 基礎工学研究科システム創成専攻 修士課程１年）
本研究では，各不等式に高々２つの変数を含むTVPI連立線形不等式問題を考察する． 一般連立線形不等式問題は弱多項式時間で解けることが知られているが，強多項式で解けるかどうか未解決であり， TVPI連立線形不等式は，強多項式時間で解けることが知られている． 本研究では，TVPI連立線形不等式問題に対するAspvall-Shiloachのアルゴリズムを実装し，実験的考察をおこなう．