電話網における経路探索のための経路コスト関数について

[kusa...@gmail.com]

はじめに
========

Mantela を用いれば各局の接続状況がわかるから、自局から他の端末を呼び出すための
番号を検索できる。これを実装したものが Jiminy 氏によって一時的に公開されてい
た。この時点では、局ホップを実現できていなかったため、経路探索は直接到達可能な
局間の通信であることを以て到達可能か否かを判断するのみでよかった。しかし、現時
点では局ホップの実現が完了しており、最適な経路を探索する問題は既に十分面白みを
帯びている。

ここでは、電話網の経路におけるコストを「呼び出しに掛かる時間」であるとし、最適
な経路探索のための経路評価アルゴリズムに適用できるコスト関数について検討する。
ダイヤルパルス信号（DP 信号）による呼び出しを考慮する場合、呼び出し番号の桁数
のみならず、DP 信号を送出する時間をも考慮する必要があることを示唆する。

なお、この投稿は Discord グループ「東京広域」に投稿されたメモを加筆・修正し、
再構成した上で投稿するものである。


押しボタンダイヤル信号の場合
============================

押しボタンダイヤル信号（PB 信号）を用いて呼び出し信号を送出する場合、信号の最
小周期（信号を送出する時間と休止時間との和）は 120 ミリ秒であることが規定され
ている。この値は送出する信号によって変化しないから、呼び出し時間は呼び出し番号
の桁数のみに依存する。PB 信号における呼び出し番号 d のコスト関数を Cpb(d) は以
下の疑似コードで与えられる。ただし、len(d) は d の桁数である。

        Cpb(d) {
                return ( 120 * len(d) );
        }


ダイヤルパルス信号の場合
========================

DP 信号の場合、信号の周期は送出する信号によって変化する。信号 1 を送出する場合
が最も短く、信号 0 を送出する場合が最も長い。ダイヤルを回すための時間を無視
し、信号速度 10 pps を仮定すると、その差は 900 ミリ秒になる。また、呼び出し番
号の桁数が増加すると呼び出し時間は当然に増加する。10 pps 及び 20 pps の DP 信
号における呼び出し番号 d のコスト関数を Cdp1(d) 及び Cdp2(d) は以下の疑似コー
ドで与えられる。ただし、d[i] は d の i 桁目の番号である。

        Cdp1(d) {
                cost = 600 * len(d);
                for i = 1 to len(d) {
                        cost += 100 * (((d[i] + 9) mod 10) + 1);
                }
                return ( cost );
        }

        Cdp2(d) {
                cost = 450 * len(d);
                for i = 1 to len(d) {
                        cost += 50 * (((d[i] + 9) mod 10) + 1);
                }
                return ( cost );
        }


具体例を用いた試算
==================

東京広域電話網における MOYASHITEL 局（MOY）から YUDE 局（YUD）の端末 200 番ま
での経路として、MIKANETEL 局（MIK）、JIMINY PUBLIC 局（JIP）、及び JIMINY
LOCAL 局（JIL）を経由する場合について検討してみる。

それぞれの呼び出し番号の桁数は等しいから、PB 信号を用いて呼び出す場合のコスト
はいづれの場合も等しい。しかし、DP 信号を用いて呼び出す場合のコストは異なる。
特に、パルス周期の長い 10 pps では、その差が顕著に現れている。

MOY-MIK-YUD（0510 0390 200）
----------------------------

         Cpb(0510 0390 200) = 200 * 11
                            = 1320

        Cdp1(0510 0390 200) = 600 * 11
                                + 100 * ( 10 + 5 + 1 + ... + 2 + 10 + 10 )
                            = 14600

        Cdp1(0510 0390 200) = 450 * 11
                                + 50 * ( 10 + 5 + 1 + ... + 2 + 10 + 10 )
                            = 8950

MOY-JIP-YUD（0108 0390 200）
----------------------------

         Cpb(0108 0390 200) = 200 * 11
                            = 1320

        Cdp1(0108 0390 200) = 600 * 11
                                + 100 * ( 10 + 1 + 10 + ... + 2 + 10 + 10 )
                            = 14900

        Cdp2(0108 0390 200) = 450 * 11
                                + 50 * ( 10 + 1 + 10 + ... + 2 + 10 + 10 )
                            = 9100

MOY-JIL-YUD（0119 0390 200）
----------------------------

         Cpb(0119 0390 200) = 200 * 11
                            = 1320

        Cdp1(0119 0390 200) = 600 * 11
                                + 100 * ( 10 + 1 + 1 + ... + 2 + 10 + 10 )
                            = 14600

        Cdp2(0119 0390 200) = 450 * 11
                                + 50 * ( 10 + 1 + 1 + ... + 2 + 10 + 10 )
                            = 8700


もっと意図的な例
================

呼び出し番号 00 と 1111 とを比べてみる。10 pps の DP 信号によって呼び出し信号
を送出する場合、桁数の大小とコストの大小とが反転する。

          Cpb1(00) = 600 * 2
                       + 100 * ( 10 + 10 )
                   = 3200

        Cpb1(1111) = 600 * 4
                       + 100 * ( 1 + 1 + 1 + 1 )
                   = 2800


おわりに
========

電話網の経路におけるコストを「呼び出しに掛かる時間」であるとした場合の、最適な
経路探索のための経路評価アルゴリズムに適用できるコスト関数について検討した。DP
信号による呼び出しを考慮する場合、呼び出し番号の桁数だけでなく、DP 信号を送出
する時間をも考慮する必要があることを示唆した。東京広域電話網内の端末における黒
電話の割合は無視できないため、DP 信号のための最適化は必要であると考えられる。


参考
====

- 技術参考資料：電話サービスのインタフェース:
  <https://web116.jp/shop/annai/gisanshi/analog/analog.html>