بررسي پايداري الگوريتم کنترل ازدحام اوليه-دوگان در حضور اغتشاش خارجي
محورهای موضوعی : مهندسی برق و کامپیوترعلی معرفيان‌پور 1 , وحيد جوهری مجد 2
1 - دانشگاه تربیت مدرس
2 - دانشگاه تربیت مدرس
کلید واژه: اغتشاش خارجيالگوريتم اوليه - دوگانپايداري ورودي - حالتشبکه‌هاي کامپيوتريکنترل ازدحام,
چکیده مقاله :
در اين مقاله به بررسي اثرات اغتشاش خارجي بر سيستم حلقه بسته مسأله کنترل ازدحام در يک شبكه با ساختار عمومي مي‌پردازيم. بررسي اثرات اغتشاش از اين جنبه حائز اهميت است که بسياري از جريان‌هاي داده در شبکه اينترنت به‌عنوان جريان‌هاي مدل‌نشده در نظر گرفته مي‌شوند. برخلاف کارهاي گذشته، در اينجا هر دو بخش فرستنده‌ها و لينک‌هاي شبکه داراي ديناميک فرض مي‌شوند. هر فرستنده نرخ ارسال خود را به‌گونه‌اي محاسبه مي‌کند که تابع هزينه خود را کمينه نمايد. شبکه با استفاده از تقريب جريان سيال و انتخاب يک مدل غير خطي براي ديناميک لينک مدل‌سازي مي‌شود. در اين تحقيق، ابتدا شرايط وجود نقطه تعادل را با در نظر گرفتن مجموعه محدوديت‌هاي حاکم بر مسأله استخراج مي‌نماييم. سپس پايداري ورودي - حالت براي سيستم حلقه بسته مسأله کنترل ازدحام به‌ازاي اغتشاش‌هاي موجود در ورودي و خروجي لينک‌هاي شبکه اثبات مي‌کنيم. به‌علاوه نشان خواهيم داد در صورتي که ماتريس مسيريابي شبکه تغييرات کند باز هم نتايج به‌دست آمده براي سيستم حلقه بسته مسأله کنترل ازدحام، برقرار خواهد بود. در انتها دستاوردهاي تئوري مقاله را با استفاده از شبيه‌سازي دو شبکه چندلينک مورد ارزيابي قرار مي‌دهيم.
In this paper, we consider the effects of exogenous disturbances on the closed-loop system of the congestion control problem in a network with general structure. This investigation is important since many of data flows in internet network are considered as unmodeled flows. In contrast to previous works, we suppose that both senders and links in the network have dynamics. Each sender updates its sending rate to minimize its own cost function. The network is modeled based on fluid flow approximation with nonlinear dynamics for the links. In this research, we first derive the conditions for the existence of the system equilibrium point taking into account the constraint sets of the problem. Then, we prove input-to-state stability (ISS) of the closed-loop system for the congestion control problem with input and output disturbances in the network links. We further show that the obtain results are valid even when the routing matrix of the network varies. Finally, we verify the theoretical results by simulation on two different multi-link networks.
[1]C. Q. Yang and A. V. S. Reddy, "A taxonomy for congestion control algorithms in packet switching networks," IEEE Networks, vol. 9,no. 4, pp. 34-45, Jul./Aug. 1995.
[2]L. Massoulie, "Stability of distributed congestion control with heterogeneous feedback delays,"IEEE Trans. on Automatic Control,vol. 47, no. 6, pp. 895-902, Jun. 2002.
[3]F. Paganini, Z. Wang, J. C. Doyle, and S. H. Low, "Congestioncontrol for high performance, stability, and fairness in general networks,"IEEE/ACM Trans. on Networking, vol. 13, no. 1, pp. 43-56, Feb. 2005.
[4]C. V. Hollot, V. Misra, D. Towsley, and W. Gong, "Analysis anddesign of controllers for AQM routers supporting TCP flows," IEEETrans. on Automatic Control, vol. 47, no. 6, pp. 945-959, Jun. 2002.
[5]S. H. Low, F. Paganini, J. Wang, S. A. Adlakha, and J. C. Doyle,"Dynamics of TCP/RED and a scalable control," in Proc. IEEEINFOCOM, vol. 1, pp. 239-248, Jun. 2002.
[6]S. H. Low, F. Paganini, and J. C. Doyle, "Internet congestion control,"IEEE Control Systems Magazine, vol. 22, no. 1, pp. 28-43,Feb.. 2002.
[7]J. Cheng, D. Wei, S. H. Low, J. Bunn, H. D. Choe, J. C. Doyle,H. Newman, S. Ravot, S. Singh, F. Paganini, G. Buhrmaster, L. Cottrell, O. Martin, and W. C. Feng, "FAST TCP: from theory to experiments,"IEEE Network, vol. 19, no. 1, pp. 4-11, Jan. 2005.
[8]F. P. Kelly, "Charging and rate control for elastic traffic,"EuropeanTrans. on Telecommunications, vol. 8, no. 1, pp. 33-37, Jan. 1997.
[9]F. Kelly, A. Maulloo, and D. Tan, "Rate control in communication networks: shadow prices, proportional fairness, and stability,"J. of the Operational Research Society, vol. 49, no. 3, pp. 237-252,Mar. 1998.
[10]S. H. Low and D. E. Lapsely, "Optimization flow control. I. Basic algorithm and convergence,"IEEE/ACM Trans. on Networking,vol. 7, no. 6, pp. 861-874, Dec. 1999.
[11]S. H. Low, L. L. Peterson, and L. Wang, "Understanding Vegas: aduality model,"J. of the ACM, vol. 49, no. 2, pp. 207-235, Mar. 2002.
[12]S. H. Low, "A duality model of TCP and queue management algorithms,"IEEE/ACM Trans. on Networking , vol. 11, no. 4,pp. 525-536, Aug. 2003.
[13]E. Altman, T. Boulogne, R. El-Azouzi, T. Jiménez, and L. Wynter,"A survey on networking games in telecommunications," Computers& Operations Research, vol. 33, no. 2, pp. 286-311, Feb. 2006.
[14]Y. A. Korilis and A. A. Lazar, "On the existence of equilibria in noncooperative optimal flow control,"J. of the ACM , vol. 42, no. 3,pp. 584-613, May 1995.
[15]F. Paganini, "A global stability result in network flow control,"Systems & Control Letters, vol. 46, no. 3, pp. 165-172, Jul. 2002.
[16]C. Hyojeong, S. H. Low, and J. S. Lee, "Global stability of Vegas -like TCP flow," inProc. of American Control Conf. , vol. 2,pp. 1679-1682, Jul. 2004.
[17]J. Wang, A. Tang, and S. H. Low, "Local stability of FAST TCP," in Proc. IEEE Conf. on Decision and Control , vol. 1, pp. 1023-1028,Dec. 2004.
[18]J. T. Wen and M. Arcak, "A unifying passivity framework for network flow control,"IEEE Trans. on Automatic Control , vol. 49,no. 2, pp. 162-174, Feb. 2004.
[19]T. Alpcan and T. Basar, "A globally stable adaptive congestion control scheme for internet - style networks with delay," IEEE/ACM Trans. on Networking , vol. 13, no. 6, pp. 1261-1274, Dec. 2005.
[20]R. Johari and D. Tan, "End-to-end congestion control for the internet: delays and stability,"IEEE/ACM Trans. on Networking ,vol. 9, no. 6, pp. 818-832, Dec. 2001.
[21]X. F. Wang, G. Chen, and K. T. Ko, "A stability theorem for Internet congestion control,"Systems & Control Letters , vol. 45, no. 2,pp. 81-85, Feb. 2002.
[22]S. Deb and R. Srikant, "Global stability of congestion controllers for the internet,"IEEE Trans. on Automatic Control , vol. 48, no. 6,pp. 1055-1060, Jun. 2003.
[23]Y. P. Tian and H. Y. Yang, "Stability of the internet congestion control with diverse delays,"Automatica, vol. 40, no. 9, pp. 1533-1541, Sep. 2004.
[24]Y. P. Tian, "A general stability criterion for congestion control with diverse communication delays,"Automatica , vol. 41, no. 7, pp 1255-1262, Jul. 2005.
[25]Y. P. Tian, "Stability analysis and design of the second -ordercongestion control for networks with heterogeneous delays," IEEE/ACM Trans. on Networking, vol. 13, no. 5, pp. 1082-1093,Oct. 2005.
[26]X. Fan, M. Arcak, and J. T. Wen, "Robustness of network flow control against disturbances and time-delay,"Systems & Control Letters, vol. 53, no. 1, pp. 13-29, Sep. 2004.
[27]H. K. Khalil, Nonlinear Systems, 2nd Edition, Prentice-Hall,Englewood Cliffs, NJ, 1996.
[28]E. D. Sontag, "On the input-to-state stability property,"European J.of Control, vol. 1, no. 1, pp. 24-36, 1995.
[29]A. Frommer, B. Lang, and M. Schnurr, "A comparison of the moore and miranda existence tests,"Computing , vol. 72, no. 3, pp. 349-354,May 2004.
[30]D. Tipper and M. K. Sundareshan, "Numerical methods for modeling computer networks under nonstationary conditions," IEEE J. on Selected Areas in Communications, vol. 8, no. 9, pp. 1682-1695,Dec. 1990.
[31]S. Sharma and D. Tipper, "Approximate models for the study of nonstationary queues and their applications to communication networks," in Proc. IEEE Int. Conf. on Communications, vol. 1,pp. 352-358, May 1993.
[32]A. Pitsillides, P. Ioannou, M. Lestas, and L. Rossides, "Adaptive nonlinear congestion controller for a differentiated-services framework,"IEEE/ACM Trans. on Networking , vol. 13, no. 1,pp. 94-107, Feb. 2005.
[33]J. Wang, D. X. Wei, and S. H. Low, "Modelling and stability of FAST TCP," in Proc. IEEE INFOCOM , vol. 2, pp. 938-948, Mar. 2005.
