1,a) 1,b) LTE WiFi WiFi RTT RTT RTT RTT RTT RTT RTT WiFi A station assignment method considering applications being used in a mixed environment of different wireless communication services Kameda Eiichi 1,a) Norihiko Shinomiya 1,b) Abstract: While the LTE has been in widespread use and the line speed for data communications has also been improved, the exploding data traffic that evolving applications require is thought to increase the utilization factor of public WiFi services from now on. The round trip time (RTT), however, might become longer for reasons of throughput degradation on a public WiFi station or increasing heavy network load. On the other hand, the required RTT is totally dependent on the application which a user is working on. This paper defines a RTT gap that is the difference between the required RTT for a user s application and the actual RTT obtained when a mobile terminal gets connected to a station. The paper firstly formulates a problem to assign some mobile terminals with the different communications services by means of graph theory, and it also proposes a method to reduce the RTT gap in the whole system with considering the required RTT for user s applications based on a connection service determination logic by Hungarian method. Keywords: WiFi Service Round-Trip Time Assignment Problem 1. LTE 1 Graduate school of engineering Soka University 1-236 Tangi-cho, Hachioji-city, Tokyo, 192-8577 Japan a) e07d5203@soka.ac.jp b) shinomi@soka.ac.jp 3G LTE WiFi WiFi 1
WiFi WiFi 2 WiFi WiFi WiFi WiFi WiFi WiFi WiFi [1] [2] RTT RTT RTT RTT RTT RTT 2 RTT 3 4 5 6 2. 2.1 RTT RTT RTT RTT RTT RTT RTTRTT RTT RTT (G RT T ) RTT(RT T need ) RTT(RT T link ) 1 G RT T = RT T need RT T link (1) 2.2 RTT RTT RTT 3 RTT 2.2.1 050 400ms [3] RTT 400ms 200ms 2.2.2 1 1, 500kB 2
URL (kb) Yahoo! m.yahoo.co.jp 467 goo www.goo.ne.jp 730 MSN jp.msn.com 580 Infoseek www.infoseek.co.jp 1,390 Excite a.excite.co.jp 1,463 www.hatena.ne.jp 1,480 www.livedoor.com/lite 573 com s.kakaku.com 817 amazon www.amazon.co.jp 608 www.asahi.com 1,073 www.yomiuri.co.jp 1,004 www.nikkei.com 1,147 sp.mainichi.jp 3,337 sankei.jp.msn.com/smp 656 1 1, 500kB Forrester Consulting 2 [4] x[kb] y[ms] T [Mbps] 2 1, 500kB 2, 000ms 6Mbps T = x 8/y (2) TCP 64kB T [Mbps] RTT R[ms] 3 6Mbps RTT 85ms 送信側 推定の仕組み 各パケットを等しい間隔で送信し パケットサイズを徐々に増加 1 2 3 4 N パケットごとの送信レートが徐々に増加する 受信間隔が広がり始めるパケットを探し そのパケットのサイズと受信間隔から通信速度を算出して推定値とする インターネットモバイルネットワーク パケットごとの送信レートが通信速度を上回ると ルータで一時的に蓄積され パケット間の間隔が広がる 1 2 3 4 N 1 PathQuick [5] RTT PathQuick [5] PathQuick 1 PathQuick 3 RTT RTT PathQuick RTT PathQuick RTT RTT PathQuick RTT RT T pq x RTT(RT T link ) 受信側 R = 64/T 8 (3) 2.2.3 RTT RTT 2 RTT 200ms 85ms 2 RTT 2.3 RTT RTT RTT PathQuick RT T link = RT T pq + f(x) (4) f(x) RTT WiFi CSMA/CA f(x) 1 2.4 sa x sb y sc z sa 1 sa 2 sa x sb 1 sb 2 sb y sc 1 sc 2 sc z m = x + y + z t 1 t 2 t n m n n RTT m n 3
基地局 ( 基地局数 3) Sa Sb Sc アクセスポイント この例の組み合わせ数は 端末数分を抽出 端末 ( 端末数 7) ( 収容数制限を考慮しない場合 ) 抽出の組み合わせ数 = 端末数 = n 基地局数 = p 全組み合わせに対して割り当て問題を解くことにより, 端末と基地局の最適な組み合わせを導出 7 つの端末と 3 つのアクセスポイントにおける割り当て問題と捉えることができる 2 RTT n p (n+p 1) C (p 1) 2 [6][7][8][9] 3. WiFi [10][11][12][13] [10] [11] [12] [13] [10][11][12][13] [14] FTP TCP VoIP UDP WiFi HTTP UDP RTT WiFi [15][16] [15] QoS [16] 4. RTT 3 RTT LTE WiFi 4
PathQuick を使用して 定期的に各基地局からアクセス回線までのスループットを測定し スループットから RTT を算出 基地局 LTE WiFi1 WiFi2 スループット 10mbps 30mbps 15mbps RTT 51.2ms 17.0ms 34.1ms 接続先コントロールサーバ 3 接続先から端末数分を抽出 LTE1 WiFi1 WiFi2 sa sb sc sa1 sa2 sa3 sa4 sb1 sb2 sb3 sc1 sc2 sc3 組み合わせ 基地局 1 sa sa sa sa sb sb sb 2 sa sa sa sa sb sb sc 3 sa sa sa sa sb sc sc 2 対象の基地局 および各収容数を決定 RTT ギャップの総和 標準偏差 2.1 2.9 3.5 1.3 2.1 0.8 アクセス回線 4 すべての組み合わせについて 割当てを導出する : : : : : : : 端末 t1 t2 t3 t4 t5 t6 t7 : : 5RTT ギャップの総和が最小, 標準偏差が最小の組み合わせを選択する 1 対象の端末を決定 端末 1 端末 2 端末 3 端末 4 端末 5 端末 6 端末 7 LTE WiFi1 WiFi2 4 PathQuick PathQuick PathQuick 用端末 用端末 用端末 3 PathQuick RTT 4.1 RTT RTT PathQuick RTT PathQuick RTT 3 PathQuick PathQuick (T i ) 3 RTT 4.2 LTE WiFi sa sb sc x y z m 5 m = x + y + z (5) t 1 t 2 t n m n n RTT RTT 2 RTT RTT RTT RTT 4 RTT RTT RTT RTT RTT RTT 0 m n RTT 4 4.3 ( 1 ) 5 1 5 2 5 3 ( 2 ) 0 5 4 3 0 5 4 0 1 ( 3 ) 5 5 5
1スタート 5 4 3 7 各行の最小値 3 9 5 4 3 3 5 3 2 5 2 7 6 4 2 2 2 各行から最小値を引く 2 1 0 4 各列の最小値 2 1 0 0 6 2 1 0 3 1 0 3 5 4 2 0 3 各列から最小値を引く 0 0 0 4 4 1 1 0 1 0 0 3 3 3 2 0 4すべての0を最小本数の線で覆う 0 0 0 4 線の本数(3)< 行列のサイズ (4) なので, 続行 4 1 1 0 線が引かれていないセルの最小値 1 0 0 3 1 3 3 2 0 5 線で覆われていないセルから 最小値を引き, 線が重なるセル に最小値を足す. 0 0 0 5 3 0 0 0 1 0 0 4 2 2 1 0 6すべての0を最小本数の線で覆う 0 0 0 5 線の本数(4) = 行列のサイズ (4) なので, 終了 3 0 0 0 1 0 0 4 2 2 1 0 5 接続先コントロールサーバ 1 端末へ制御情報を送信 アクセス回線 5. 5.1 4 100 1 10 2 RTT RTT 3 4 3 RTT RT T init PathQuick RTT (ms) RTT 1 2 3 (ms) ( ) case1-1-1 20 40 60 1 40 case1-1-2 20 40 60 1 70 case1-1-3 20 40 60 1 100 case1-2-1 40 60 80 1 40 case1-2-2 40 60 80 1 70 case1-2-3 40 60 80 1 100 case1-3-1 60 80 100 1 40 case1-3-2 60 80 100 1 70 case1-3-3 60 80 100 1 100 case1-4-1 80 100 120 1 40 case1-4-2 80 100 120 1 70 case1-4-3 80 100 120 1 100 case2-1-1 20 40 60 2 40 case2-1-2 20 40 60 2 70 case2-1-3 20 40 60 2 100 case2-2-1 40 60 80 2 40 case2-2-2 40 60 80 2 70 case2-2-3 40 60 80 2 100 case2-3-1 60 80 100 2 40 case2-3-2 60 80 100 2 70 case2-3-3 60 80 100 2 100 case2-4-1 80 100 120 2 40 case2-4-2 60 80 100 2 70 case2-4-3 60 80 100 2 100 3 1 LTE WiFi1 端末 1 端末 2 端末 3 端末 4 端末 5 端末 6 2 制御情報を受けて接続先基地局を切り替え 6 WiFi2 端末 7 RTT RTT 4.4 4.2 6 RTT (ms) RTT 1 2 3 (ms) ( ) case3-1-1 100 120 140 1 4 case3-1-2 100 120 140 1 7 case3-1-3 100 120 140 1 10 case3-2-1 120 140 160 1 4 case3-2-2 120 140 160 1 7 case3-2-3 120 140 160 1 10 case3-3-1 140 160 180 1 4 case3-3-2 140 160 180 1 7 case3-3-3 140 160 180 1 10 case3-4-1 160 180 200 1 4 case3-4-2 160 180 200 1 7 case3-4-3 160 180 200 1 10 case4-1-1 100 120 140 2 4 case4-1-2 100 120 140 2 7 case4-1-3 100 120 140 2 10 case4-2-1 120 140 160 2 4 case4-2-2 120 140 160 2 7 case4-2-3 120 140 160 2 10 case4-3-1 140 160 180 2 4 case4-3-2 140 160 180 2 7 case4-3-3 140 160 180 2 10 case4-4-1 160 180 200 2 4 case4-4-2 160 180 200 2 7 case4-4-3 160 180 200 2 10 4 2 6
よって直近に取得された RTT の当該基地局の値 RT Tpa 当該基地局の RTT 関数 f (x) および PathQuick 取得時か らの接続端末数の増減 termdif f により 式 6 で示される 100 90 80 70 60 50 40 30 20 RT Tinit = RT Tpa + f (termdif f ) (6) 10 0 解法23 解法 解法 1 また RTT 増分は 各基地局の RTT 関数 f (x) の傾き に相当する 各端末で使用しているアプリケーションとしては 通 話アプリケーション ブラウザ その他 のうちのいず 図 7 実験 1 における RTT ギャップの平均 グラフ れかをランダムに割り当てた また 各アプリケーション 果として得られる RTT ギャップ平均値は大きくなる こ における必要 RTT は 表 2 の値を使用した れに比べて 解法 1 本提案システム は 取り得るすべて シミュレーションプログラムでは これらの値を元に の組み合わせに対して 割り当て後の RTT 値も考慮して 各基地局の収容数全体から端末数分を抽出しうるすべての 最適な組み合わせを抽出しているため RTT ギャップ平均 組み合わせに対して ハンガリアン法による計算を行い 値は一番小さい値を取ることになる 解法 3 と比べると 全体の中で RTT ギャップの合計が最小になるものの中で すべてのケースで解法 1 のほうが安定的により小さい値を 標準偏差が最小になるものを出力している 取っている これらのことから RTT ギャップの最小化に また本実験では 提案システムでの計算 解法 1 以外 に 以下の 2 つのロジックについても 各ケースにおける おいて本提案システムが有効であることが確認できた しかし現実的には 一度の割り当て計算で対象になる端 計算を行った 末数は 100 台までにはならないと考えられる 次に実験 ( 1 ) 一番短い RTT を必要とする端末から順番に 現時点 2 における各ケース 各解法の RTT ギャップの平均を表 6 で接続時 RTT が一番短い基地局に優先的に割り当て に示す 実験 2 においては 対象台数は 10 台であるが こ る グリーディ法 解法 2 れを見ると 台数が少ない場合でも すべてのケースにお ( 2 ) 各端末をランダムに各基地局に割り当てる 解法 3 いて解法 1 が他の解法よりも短い値を取っている これに より 対象台数が少ない場合でも RTT ギャップの最小化 において本提案システムが有効であることが確認できた 5.2 実験の評価 5.2.1 RTT ギャップの平均 実験 1 における各ケース 各解法の RTT ギャップの平 均を表 5 および図 7 に示す すべてのケースにおいて 3 つの解法のうち解法 1 本 提案システム の RTT ギャップ平均値が 一番小さい値 を取っている 解法 2 は RTT 増分が小さくかつ収容残数が小さいケー スでは RTT ギャップ平均値も小さいが RTT 増分が大き い もしくは収容残数が大きい場合には RTT ギャップ平 均値が大きくなる傾向がある これは 解法 2 が現時点で ケース名 RTT ギャップの平均 (ms) ケース名 RTT ギャップの平均 (ms) 解法 1 解法 2 解法 3 解法 1 解法 2 解法 3 case3-1-1 5.4 5.7 11.5 case4-1-1 6.3 6.9 16.7 case3-1-2 5.4 6.6 9.4 case4-1-2 6.3 8.7 11.1 case3-1-3 5.4 7.5 7.5 case4-1-3 6.3 10.5 16.9 case3-2-1 11.4 11.7 15.6 case4-2-1 12.3 12.9 18.5 case3-2-2 11.4 12.6 11.7 case4-2-2 12.3 14.7 16.3 case3-2-3 11.4 13.5 15.4 case4-2-3 12.3 16.5 14.5 case3-3-1 17.4 17.7 19.3 case4-3-1 18.3 18.9 22.7 case3-3-2 17.4 18.6 23.5 case4-3-2 18.3 20.7 18.9 case3-3-3 17.4 19.5 25.6 case4-3-3 18.3 22.5 22.3 case3-4-1 23.4 23.7 30.3 case4-4-1 24.3 24.9 27.7 case3-4-2 23.4 24.6 28.3 case4-4-2 24.3 26.7 31.7 case3-4-3 23.4 25.5 24.3 case4-4-3 24.3 28.5 33.5 表 6 実験 2 における RTT ギャップの平均 の RTT 値を元に接続先を判断しているからである しか し実際には 接続端末数によって RTT が変動するため 結 5.2.2 基地局割り当てに要する処理時間 実験 1 における解法 1 の計算回数 ハンガリアン法の実 ケース名 RTT ギャップの平均 (ms) ケース名 RTT ギャップの平均 (ms) 解法 1 解法 2 解法 3 解法 1 解法 2 解法 3 case1-1-1 1.44 case2-1-1 0.44 5.40 9.30 case1-1-2 1.80 2.55 case2-1-2 27.00 9.84 case1-1-3 12.60 2.08 case2-1-3 54.60 7.00 case1-2-1 3.31 case2-2-1 6.12 12.60 14.86 case1-2-2 9.00 5.65 case2-2-2 1.40 34.20 15.38 case1-2-3 19.80 4.24 case2-2-3 1.40 67.80 14.76 case1-3-1 2.98 5.40 13.90 case2-3-1 13.32 19.80 22.48 case1-3-2 0.66 16.20 8.98 case2-3-2 11.16 41.40 22.38 case1-3-3 0.66 27.00 8.51 case2-3-3 11.16 81.00 23.10 case1-4-1 10.18 12.60 18.14 case2-4-1 20.52 27.00 29.62 case1-4-2 7.78 23.40 16.56 case2-4-2 20.44 54.60 29.78 case1-4-3 7.78 34.20 17.05 case2-4-3 20.44 94.20 28.98 表 5 実験 1 における RTT ギャップの平均 2015 Information Processing Society of Japan 施回数 は 最大で 5,151 回であり 処理時間はすべての ケースで 1 秒以下であった これらの値は ユーザがある 一定時間以上 同じアプリケーションを使用し続ける状況 においては 充分に有効な値であると考えられる これら のことから 処理時間の観点からも本提案システムが有効 であることが確認できた 6. まとめと今後の課題 ユーザが使用しているアプリケーションを考慮した RTT 7
RTT RTT 2 RTT (B) Vol.J89-B No.4 pp.431-442 (2006). [16] (B) Vol.J89-B No.2 pp.195-203 (2006). [1] LAN Vol.55 No.1 pp.340-353 (2014). [2] Vol.2013-MBL-66 No.24 pp.1-6 (2013). [3] http://www.soumu.go.jp/main content/000158162.pdf. [4] Forrester Consulting ecommerce Web Site Performance Today http://www.damcogroup.com/whitepapers/ecommerce website perf wp.pdf. [5] CQ2013-56 Vol.113 No.293, pp.29-34 (2013). [6] OR (1984). [7] (1995). [8] Alan Doran Joan Aldous (2003). [9] Ravindra K. Ahuja Thomas L. Magnanti James B. Orlin NETWORK FLOWS: Theory, algorithms, and Applications Prentice Hall (1993). [10] LAN NS2003-138 Vol.103 No.386 pp.33-36 (2003). [11] Wireless LAN IN2002-206 Vol.102 No.693 pp.23-28 (2003). [12] Gaurav S. Kasbekar Pavan Nuggehalli Joy Kuri Online Client-AP Association in WLANs Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2006 4th International Symposium on pp.1-8 (2006). [13] Huazhi Gong Nahm, K. JongWon Kim Distributed Fair Access Point Selection for Multi-Rate IEEE 802.11 WLANs Consumer Communications and Networking Conference 5th IEEE pp.528-532 (2008). [14] LAN Vol.50 No.2 pp.750-764 (2009). [15] IEEE802.11e WLAN network 8