通信ネットワークにおける OR の問題
橋田温1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111II1111111111111111111111111UIIIIIIIIIIII
川111
附111
聞H肌11川川u川川11川川川11H川111
川川
H聞川川
11川
川
11111
川川
11川1111川111
川川
11川H川川川11川11H肌111川
H山川
11川
11H川
111
川川
H聞川
11川川
111111111111川1111
川1111
川
H聞H聞川
11川
11H聞川
11111川
H聞111
川11111111111111111111111111111111111111111

1. はじめに通信ネットワークのライフサイクルは，図 1 に示すように計画，設計，製造，設置，運用のフェーズから成るプロセスを繰り返す.これら通信ネットワークのライフサイクルの各フェーズにおいて，OR の問題は随所に見られる.たとえば，計画フェーズでは需要予測，トラヒ

ック予測，ザーピス品質の規格決定が，設計フェーズではネットワーク構成評価，性能評価，パラメタ最適化，運用アルゴリズムの評価，全システムの総合評価などがある.また運用フェーズでは，トラヒック条件にもとづいたシステム構成要素の設備数・パラメタの設計，品質

図 1

通信ネ

図 2

一般のネットワークトポロジー

ッワークのライフサイクルとトラヒックの測定，幅稜に対するトラヒック昔話l 御があ(5) ネットワークトポロジー，る.

ここでは典型的な OR 手法と関係の深い問題として，接続経路の選択方法)，(6) ルーティング(通信呼の(7)構成要素のコスト関数，(8) サ設計フェーズにおける， (1) ネットワークトポロジーの設ービス品質，などがある.入力条件として与えられるも計と， (2)サービス性能評価，を取り上げる.前者は数理のもあるが，計画法に，後者は待ち行列理論に関係が深い.などは通常設計目標である.それらをすべて独立変数と2. ネットワークトポロジーの設計
ネットワークのトポロジー(接続形態)は，トラヒッ

トポロジー，ルーティング，サービス品質して問題を解くことは現実的に不可能であるため，どれかを独立変数とし残りを制約条件として最適化問題を解くこととなる.

ク，サービス種類，サーピス品質，コスト/料金などに2.
1 中継ネ '1 トワークの設計よって定まる.一般には，ある制約条件下で広義の総合

中継ネットトワークは交換機であるノードと伝送路でコストを最小にする問題に定式化される.通信ネットワあるリンクからなる.

ークは，基本的にはユーザーが用いる端末，交換機，おは，よび伝送路から成る.端末を集めて交換機(または集線

ネットワークトポロジーとしてノードに区別がない非階層形(または分散型)ネッ

トワークとノードの機能に階層がある階層型ネットワー

装置)へ収容するネットワークをローカルアクセスネッ

クがあり，問題の定式化が異なる.ほとんどの公衆電話

トワーク，交換機間を伝送路で結んだネットワークを中網が前者の例であり，米国のコンピュータネットワーク継ネットワークと呼ぶ(図 2 ).

ARPANET は後者の例である.

ネットワークトポロジーのパラメタとしては， (1)端末の地理的分布， (のトラヒック要求行列(発着対地聞の交流トラヒック量)，(3) リソースの種類と容量，ック特性(通信呼の発生過程，(4) トラヒ

サービス時間分布等)，

1) 分散型ネットワークの設計与えられた入力条件下で，サービス品質などの制約条件を満たす総コスト最小のネットワークトポロジーを求めるいわゆるリンク容量割付問題であり，以下のように定式化される.
はしだおん筑波大学大学院経営システム科学専攻〒 112 文京区大塚 3-29ー 1〔入力条件 J: ノード位置，ンク容量，

1990 年 3 月号
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

トラヒック要求行列，最大リコスト関数

(5) 1
39

[目的関数 J :総ネットワークコスト機への収容方法)と， (2)すでに各端末の収容区域が定ま[独立変数] :(i)トラヒックアロー， (且)リング容量っているときに各区域で端末を交換機へツリー状(多重[制約条件] :(i)トラヒッタフロー孟最大リンク容量化装置を用いる)で接続する問題(端末接続ネットワー(ü)総合平均遅延 T~五 T max

クのトポロジー)がある.

(iü)信頼性(たとえば連結度孟 2)1) 交換機への収容方法の設計

広義のコストとしての総合の品質評価尺度を考える場
合もある.

m{困の端末を n 個の交換機候補地に接続収容する問題として，以下のように定式化される.

トラヒックフローとリンク容量を同時に変数としてこ[入力条件 J :端末の位置，交換機候補位置，交換機容量の問題を厳密に解くことは，制約条件の性質，コスト関

コスト関数

数の非線形性，伝送路の種類が多 L 、，などの理由により[目的関数 J :総合コスト非常に困難である.したがって，ヒューリスティックな[制約条件 J :交換機容量制限

方法として，初期トポロジーから出発してリンクを追加したり，削除したりしてコストを逓減していく

Local

問題としていろいろな解法が提案されている.大規模なネットワークを対象に，ここでもいわゆる貧欲解法の範Transform 法が各種提案されている.
問題を少し簡単にすると，

この問題は混合 0 ー 1 整数計画問題であり，施設配置トラヒッタフローのみを変数とした最適ノレーティング問題がある.ここで言うルー

鴎に含まれるようなヒューリスティックな解法が提案されている[3J.

ティングとは，トラヒッタフロー(発着対の平均トラヒッ2) 端末接続トポロジーの設計ク量)をどうリンクに割当てるかという問題であり，個1 台の交換機へ端末をツリー状に接続する問題であ々の通信要求に対応した動的なノL ート選択方法(通信呼り，以下のように定式化される.のルーティング)は除いてある.後者も非常に重要な問[入力条件 J :端末の位置，交換機の位置，求行列，題であり，与えられたネットワークトポロジーに対し，リンク容量，トラヒッグ要

コスト関数

通信呼が発生した時ネットワークの負荷状態に応じてス[目的関数 J :総リンクコスト

ループット対遅延特性の観点から望ましい接続ノL ートを[制約条件] :(i)最大リンク容量， (首)信頼性(たとえばリンク断により接続不能となる端末数)選択するアルゴリズムが求められる.

最適ルーティング問題は以下のように定式化される.
[入力条件] :ネットワークトポロジー，トラヒック要求

この問題は上述の問題と同様に混合 0 ー 1 整数計画問

題であるが，制約付き最小木問題としてヒューリスティ
ックな解法が提案されている.

行列，コスト関数[目的関数] :(a)総コスト， (防総合平均遅延3.

[変数] :トラヒッタフロー

サービス性能評価[制約条件] :(i) フロー保存則， (ü) リンク容量， (叫総合平

現在通信ネットワークは，大規模化かっ複雑化，コス均遅延豆 T皿 ax (目的関数(同)，ト効果の追求，サービスの高度化・高信頼化へと向かっ

コスト三 Cている.

血ax ("(b)) ，制信頼性

具体的な傾向としては，(l)CATV , LAN ,この問題は凸制約条件のある非線形計画問題であり，MAN などの専用網の発展， (2)音声，データ，画像など

主に Feasible Direction 法に属するヒューリスティッの通信サービスが共通のディジタル技術と共用リソースクな解法が提案されている [IJ.

で提供される十一ピス総合ディジタル網 (ISDN) (図 3 )2) 階層型ネットワークの設計の発展， (3)通信サーピス提供者の+ーピス追加・変更を

通常基本とするトポロジーはスター状であり，スター容易にするとともに，ユーザのコスト効果のよいネット状の基幹回線に対し，パイパス回線をどのように設けるかという問題である.公衆電話網の設計法として古くから検討されてきた [2J.

2.
2 ローカルアクセスネヴトワークの設計
端末と交換機候補の地理的分布が与えられたとき， (1)各端末を適当な突換機へスター状で接続する問題(焚換14
0 (6)

ii許可;
図 3

-Ij-ーピス総合ディジタノレ網のイメージ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

ワーク構築を可能とするネットワークのインテリジェン

ト化， (4) ネットワーク構築側のマルチベンダー化の要求と分散処理・分散データベース技術に対応したソフトウ
エア・ハードウエアのモジュラー型アーキテクチャ化，「手トj イケゥ!ーナウゲドウ CÎや+スロット(a) マルチウインドウ方式などがあげられる.

性能評価に影響が大きい傾向として， ISDN で実現さ〈ーフレーム

れる共用リソースによるマルチサーピスと，インテリジエントネットワークやモジュラーアーキテクチャにおける分散処理・分散データベースを取り上げる.

3.1 共局リソースによるマルチサービス

l U , , , , b , , b , , c , ,c , , c ,ノ
通信 a(b) マルチスロット方式

ISDN で、は，その理念からユーザがネットワークにア

パケットクセスするところ(ユーザ・網インタフェース)では各種通信サービスのアクセスが統合されているが，中継ネ, 1

仁ノ\エメ
通信 b
通伝 c

問一I

ー
I分間

/

1

ットワークの中でも交換機や伝送路において複数のサーヘッダー情報ピスがリソースを共用する場合がある.それらはサービ(c) 非同期伝達モード

l4・tス機能が異なるのは当然であるが，サーピス品質要求，要求の発生過程，リソースの占有時間，など性能に影響の大きい要因が異なっている.たとえば，音声トラヒッ
クに比べてデータ伝送の要求発生はパースト的であり，《一一一一一一一一一一一フレーム「でーτ拝二[デ1 タ用「さらに動画像通信の情報発生は周期性はあるが情報量の変動が大きい.音声情報の伝送では遅延は亦常にきびしいが，データ伝送では比較的緩い.また音声と画像では通信路での情報紛失はある程度許容できるが，データ伝送ではそれが致命的となる場合が多く，誤り制御の導入が必須である.これらを共用リソースでサービスするマ
ルチサーピスの問題点としては， (1)共用リソースでサーピスする範閤(共用にしない方が有利な場合がある)，(2)各サーピスに対し異なるサービス品質を確保するための制御アルゴリズム， (3) リソースの設計方法，などがある [4J.

(d) 音声・データ統合 7 レーム(可変境界)

図 4

時分割多重化方式

プレーム内に各速度専用のウインドウと呼ばれるスロット群(スロット長は速度対応に定められる)を設け，速度毎にそれぞれのウインドウで+ーピスする(図 4 (a)).
マルチスロット方式ではフレームを基本伝送速度に対応したスロットで分割し，基本速度より遅い通信は 1スロットを使用し，基本速度より速い通信は速度に応じて複数個のスロットを使用する方法である(図 4(扮).

この場合のサーピス品質(たとえば呼損率)を求める問

例として本の高速回線を複数の通信サーピスで共用する場合を考えてみよう.ディジタル通信では l 本の題は，呼種により同時使用回線数が異なる多元トラヒッグの問題となる.

高速回線を時間をずらして複数の通信に用いる時分割多上述の時分割多重方式は，回線のフレームや基本速度重方式が用いられている.すなわち，同一速度の端末 Nを固定し要求発生に応じてスロットを割当てる方式であ台が通信をする場合，時間をフレームと呼ばれる一定のり，同期伝達モードと呼ばれる.これらの方法は統合さ長さに区切り，その聞に各端末が 1 回ずつスロットと呼れる通信レートの需要予測に大きく依存するとともに，ばれる時間の間伝送路を使用する.効率の面から ， N台

通信レートの数が多くなるとフレームの決定方法やスロより多い端末群に同じ伝送路を共用させ，伝送要求の発ット割当方法が複雑になるなどの問題がある.それらに生に応じて N個のスロットを l順次割当てる要求時割当て

対する解決案として，フレームを用いない非同期伝達モ方式が用いられる.

ードが提案されている(図 4(c)).

これは，もとのディジ異なる伝送速度(レート)の通信サーピスを統合するマタル情報をパケットまたはセルと呼ばれる定められた長ルチレート伝送の場合は，マルチウインドウ方式とマルさの信号に分割して順次伝送路に送出する方法であり，チスロット方式がある.マルチウィ γ ドウ方式では競合が発生した場合は他のパケットの送信が終了するま1990 年 3 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(7) 1
4
1

で待ち合わせることとなる.待ち合わせを含んだ情報のT， 実行

T2 実行

7 山→夕 J 、プ

伝達遅延を求める問題は，待ち行列理論またはシミュレーションにより検討される.

特に，遅延に厳しい音声通信と紛失に厳しいデータ通

HEAD 残高[￥ 500 ， 000)
READ 残高(￥ 500 ， 000)

信が共用する場合は，主なサーピス品質がそれぞれ呼損率と伝達遅延のため複雑な問題となる.音声サービスでADD ￥ 1 ， 000 ， ∞o(￥ 1 ， 500 ， 000)

は，遅延がきびしいため使用できる時間が周期的に割当W HlT日子千百|

ADD ￥ 2 ， 000 ， 000(￥ 2 ， 500 ， 000)

てられる同期伝達モードを用いる固定長フレームを考WRITEú~1

え，データサーピスには非同期伝達モードを用いるとする.

図 S

フレームを音声とデータで共用するには，フレーム内に境界を設けてそれぞれ専用的に使用する固定境界方式と，音声用のスロット群を定め，データは残りのスロットおよび未使用の音声用スロットも使用できる可変境界方式がある(図 4 (d)). この場合，データの遅延特性は音声通信の接続状況に影響されるため，複雑な待ち行列モデルとなる [5J.

データベースにおける更新の紛失

ケーションプロセスによって協調して実行される分散処理では，トランザクションの応答時間の評価には待ち行列ネットワークモデルが有効である.

分散データベースでは，複数のユーザがほぼ同時に同じデータベースの部分をアクセス(読み書き)したときに生じる問題がある.すなわち，普通の共用リソースの場

さらに，音声，データ，画像を境界を分けずに統合し合とは異なり，ユーザからのアグセスの順番を制御しなて同じ伝送路で伝送するために，すべてのディジタル情いと，更新の紛失や検索の不一致などの矛盾が生じる.

報を同じ形のセルにして非同期伝達モードでサービスす図 5 は同じ銀行口座に 2 つのトランザクション T" T 2 がる方式が研究されており，より高速の情報伝送を対象とほぼ同時にアクセスするときに生じる矛盾(更新の紛失)した広帯域 ISDN の技術として有望視されている.そのを示している.無矛盾を達成するために同時実行制御が場合の問題としては，異なったサービス品質を与えるた行なわれる.

めの制御方法，各種通信サーピスに対するリソースの割

同時実行制御には，ロック法，時間刻印法，仮想リン

当て方法つの通信要求の異常が他の通信サービスにグトークン法，楽観的制御法などがあるが，影響をおよぼさないようにするトラヒック制御方法，な最もよく用いられる.

どがある [6J.

かのユーザが使用できないように必要なデータをロック伊)

分散処理・データベースの問題

ロック法がロック法は，アクセスする前にほし，アクセスが終了するにつれてロックを解除する方法

広域の公衆網では交換機能は交換機に集中することがである.特に，トランザクションの処理途中でも必要なコスト効率上有利である.しかし，システム構成要素のデータを逐次ロックする動的ロッグ法の場合は，コスト効率特性が技術の進歩により大きく変わってきたザクションの処理の流れをロックを追加するフェーズとために，限られた地域を対象とした地域網 (LAN) で解除するフェーズに分ける 2 相ロック法が望ましい.性は交換機能が地域的に分散した形態が可能となった.た

能上は，他のユーザがロックしているデータへのアクセとえば，構内に張りめぐらされた 1 本の伝送路から成るスに待ち合わせが生じ，それが通信ネットワークのサーLAN では，各端末が独立に伝送路にアクセスする場合ピス品質に影響をおよぽす [8].

が発生する.したがって，ほぼ同時に発生した伝送要求のユーザのアグセス要求との競合によりデッドロックがが互いに衝突するのを制御する方式{媒体アクセス制御)発生する可能性があり，その検出および解消法を必要ととして，

CSMA/CD ,トークンパッシング，スロ y ト

化リング，などが提案されている.集中型の制御方式と異なり，地犠的に離れた端末が独立にアクセスを行なう
ために異なった性能評価モデルとなり，待ち行列モデルとしては解析がむずかしい[打.

また，

トランロック法では他する.

4. おわりに通信ネットワークはますます大規模で複雑になり，ま1 つのトランザタショ

たそれを構成している部分システムのシステムライフ+ンの処理がネットワーク上に分散している複数のアプリイグルが短くなる傾向にある.通信+ーピスを受けるユ1
42 (8)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーショ γ ズ・リサーチ

Computing and Communications (Y. Temini

ーザーの要求も多様化し，不確定要素が多くなっている.それらに対して，通信ネットワークでは，共通リソ(ed.)) , ComputerSciencePress , 1987ースによる効率的なマルチサービスやネットワーク内の[4J K.Kodaira and K. Kawashima , “ Traffic

多くの場所に情報処理技術や AI 技術を持ち込んだ分散StudiesRelatedt
otheJapaneseISDN ," ITC

インテリジェンス化，交換機や伝送装置などの各種装置

SpecialistsSeminaronISDNT
raffic Issues ,BrusseIs , May5-7 , 1
986のモジュラー構成化，システム構築の融通性を狙ったマルチベンダー化などで対応しようとしている.このよう[5J M.Schwartz , TelecommunicationNetworks:

な不確定要素が多くかっ多面的な評価が必要となる問題

Protocols , ModelingandAnalysis , Addisonｭに対しては，

Wesley , 1
987OR の手法のみならず、ンステム制御理論，A I，ニューロンネッ[6J J.Y. Hui ,“ Network , Transport , andSwitｭ

トワークなどあらゆるアプローチからの試みが必要であchingIntegratio且 for BroadbandCommunicaｭ

ろう.また，一般にシステム工学で強調されているようtions ," IEEE NetworkMagazine , pp. 4O -51 ,多属性効用理論，ファジ一理論，

1989に，個々のネットワーク構成要素に関する詳細な検討よりも，通信ネットワーク全体としてパランスのとれた検[7] J.L. HammondandP.J.P.O' Re ilI y , Perｭ
formance Analysis of Local Computer Netｭ討が重要であり，構造的アプロ一千も要求される [9J.

works , Addison-Wesley , 1
986参芳文献[8J Y. C. Tay , N.Goodman and R. Suri ,[1J D.Bertsekas and R.Gallager , Data Net‑

“Locking Performance inCentralized Data‑

works , Prentice‑Hall International , 1
987bases ," ACM Trans. on Database Systems ,[2J C.W. Pratt , “ The Concept of Marginal
OverflowinAIternatingRouting ," Australian

10 , pp.415-462 , 1
985[9J O. Hashida , “Systems Engineering andTelecommunications Research , 1, pp.76-82 ,TrafficEngineering ," TeletrafficSciencefor

1967Cost‑
Effective Systems. Networks and Ser‑

[3J A. Kershenbaum , “ CapacitatedFacilityLocation ," CurrentAdvancesinDistributedv
ices (M. Bonatti(ed.)) , North-Holland , pp.
1582-1588, 1989「論文・事例研究」の原稿募集!
OR の特徴は実践にあるといわれています.実践的な応用をぬきにした理論ということは OR では考えられません.本誌でも以前から会員の皆様からの事例研究の報告をお願いしてきましたが，まだ十分な成果をあげているとはし、えません.

「論文・事例研究 J は企業，研究所，大学等で実際に行なった事例を論文としてまとめたものを広く会員の皆様に紹介することを目的として作られた欄です.この論文は 2 人のレフリーによって正式に審査されますが，マネジメント，行政，工学等の広い分野において適用対象の新しさ，適用方法の新しさ，適用範聞の広さ等が論理的，科学的に論じられたものでありますならば，積極的に採用する方針です.皆様のご投稿をお願い申し上げます.

投稿要領:学会原稿用紙 36枚 (25字 x 12行)以内(図・表を含む)(ワープロ可)投稿先は OR 学会事務局 OR 誌編集委員会宛.
なお，原稿の他コピーを 2 部添付してください.

レフリ一審査の結果，改訂をお願いしたり，採択されない場合があることをご了解ください.また，原稿は，採択・不採択にかかわらず，原本，コピーともお返しできません(OR 誌編集委員会)

l...・・-一一一一一..一一一一一一一一一一一..........・.....・..・....・.......・.....四....・.....一一-一・・四一四・・・・.....・.......・-四四回

1990 年 3 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(9) 143