پایان نامه طراحی الگوریتم های تخصیص نرخ بهینه بر مبنای تابع سودمندی در شبکه های داده

فهرست:

عنوان                                                                                                                                              صفحه

فهرست مطالب.............................................................................................................................................................. هشت

چکیده.................................................................................................................................................................................1

فصل اول : مقدمه

1-1 مقدمه ...........................................................................................................................................................................2

1-3 تبیین موضوع.................................................................................................................................................................5

1-2 ترتیب ارائه مطالب........................................................................................................................................................6

فصل دوم : بررسی مفهوم کیفیت سرویس در شبکه های داده

2-1 مقدمه............................................................................... .........................................................................................7

2-2 مکانیسم های موجود در شبکه برای ایجاد QoS .........................................................................................................8

2-3 روش های صف بندی با کار مداوم..............................................................................................................................9

        2-3-1 روش صف بندی FIFO.................................................................................................................................10

        2-3-2 روش صف بندی با اولویت مطلق.....................................................................................................................10

       2-3-3 روش GPS....................................................................................................................................................11

       2-3-4 روش صف بندی Round Robin ...............................................................................................................12

       2-3-5 روش Bitwise Round Robin ...............................................................................................................13

       2-3-6 روش عملی صف بندی عادلانه Bitwise Round Robin ........................................................................13

       2-3-7 روش WRR ................................................................................................................................................13

       2-3-8 روش Deficit Round Robin (DRR) .................................................................................................14

       2-3-9 روش بهبود یافته DRR (DRR+) ...............................................................................................................15

       2-3-10 روش صف بندی عادلانه وزن دهی شده (WFQ) .......................................................................................15

       2-3-11 روش WF2Q ............................................................................................................................................15

       2-3-12 روش های Delay-EDD و Jitter-EDD ..............................................................................................16

2-4 روش های صف بندی با کار غیر مداوم .....................................................................................................................17

       2-4-1 روش Leaky Bucket ...............................................................................................................................18

      2-4-2 روش Token Bucket ................................................................................................................................18

2-5 روشهای استفاده شده برای حذف کردن بسته ها .........................................................................................................18

       2-5-1 Tail Dropping ........................................................................................................................................19

       2-5-2 Random Early Detection (RED) ..................................................................................................19

       2-5-3 Weighted Random Early Detection (WRED) ........................................................................19

2-6 انواع کلاسهای سرویس در شبکه های داده ...............................................................................................................20

2-7 سرویس های مجتمع .................................................................................................................................................21

2-8 RSVP.....................................................................................................................................................................23

2-9 سرویس های تفکیک شده ........................................................................................................................................24

2-10 نتیجه گیری ............................................................................................................................................................25

فصل سوم:کنترل نرخ و مفهوم عدالت در شبکه های داده

3-1 مقدمه.........................................................................................................................................................................26

3-2  مفهوم کنترل نرخ و اهداف آن....................... ...........................................................................................................27

       3-2-1 روشهای  بر اساس پنجره ................................................................................................................................27

       3-2-2 روشهای بر اساس نرخ ....................................................................................................................................28

3-3  تقسیم بندی ترافیک های موجود در سطح شبکه .......................................................................................................29

3-4  مفهوم عدالت در تخصیص نرخ در شبکه های داده ...................................................................................................31

       3-4-1 مدل شبکه .....................................................................................................................................................32

       3-4-2 معیار عدالت حداکثر- حداقل.........................................................................................................................33

       3-4-3 معیار عدالت تناسبی .......................................................................................................................................34

      3-4-4 معیار عدالت حداقل تأخیر بالقوه .....................................................................................................................36

       3-4-5 تخصیص پهنای باند وزن دهی شده ................................................................................................................36

       3-4-6 معیار عدالت تناسبی(W,a) ...........................................................................................................................37

3-5  نتیجه گیری ..............................................................................................................................................................38

فصل چهارم: بررسی روشهای تخصیص نرخ بهینه به کاربرهای سطح شبکه براساس دیدگاه جریان سیال

4-1 مقدمه.........................................................................................................................................................................39

4-2 طرح مسئله کنترل نرخ بصورت یک مسئله بهینه سازی عمومی.....................................................................................42

        4-2-1 الگوریتم گسترده و تکرری برای پاسخ............................................................................................................45

4-3  کنترل نرخ در شبکه های کامپیوتری با استفاده ازمفهوم هزینه .....................................................................................46

       4-3-1  الگوریتم Kelly برای حل مسئله شبکه..........................................................................................................49

       4-3-2  الگوریتم Kelly برای حل مسئله کاربر .........................................................................................................50

       4-3-3  بررسی پایداری سراسری الگوریتم ها ............................................................................................................50

       4-3-4  سرعت همگرائی ...........................................................................................................................................51

       4-3-5  تأخیرهای زمانی ............................................................................................................................................52

       4-3-6  تطبیق کاربرها ...............................................................................................................................................54

       4-3-7 بهینه سازی همزمان مسیر و نرخ کاربرها .........................................................................................................55

       4-3-8  بررسی مسئله ورود و خروج کاربرها در سیستم ..............................................................................................57

4-4 نتیجه گیری................................................................................................................................................................60

فصل پنجم : روشهائی برای حل مسائل بهینه سازی محدب مقید
5-1 مقدمه ........................................................................................................................................................................61

5-2 بهینه سازی محدب مقید .............................................................................................................................................62

        5-2-1  روش تصویر گرادیان ...................................................................................................................................63

        5-2-2 الگوریتمهای تصویر گرادیان وزن دهی شده و نیوتن ......................................................................................65

        5-2-3 بررسی همگرائی با استفاده از روش شیب .......................................................................................................66

         5-2-4 لم شیب ........................................................................................................................................................67

        5-2-5 مفهوم سرعت همگرائی و مقایسه سرعت همگرائی الگوریتم ها ......................................................................68

        5-2-6 روش لاگرانژ ................................................................................................................................................70

        5-2-7 روش تابع جریمه ...........................................................................................................................................71

        5-2-8 روش تابع سد ................................................................................................................................................71

5-3 نتیجه گیری................................................................................................................................................................72

فصل ششم : طراحی و پیشنهاد الگوریتمهای تخصیص نرخ بهینه بهبود یافته

6-1  مقدمه .......................................................................................................................................................................73

6-2 معیار عدالت تناسبی(W,a) .......................................................................................................................................74

6-3  الگوریتمهای پیشنهادی ..............................................................................................................................................76

        6-3-1  الگوریتم  I ...................................................................................................................................................82

        6-3-2  الگوریتم II  .................................................................................................................................................84

        6-3-3 الگوریتم III  ................................................................................................................................................96

       6-3-4  الگوریتم IV  .............................................................................................................................................100

6-4  پایداری الگوریتم های با عدالت تناسبی در حضور تأخیر زمانی ...............................................................................102

6-5 نتیجه گیری..............................................................................................................................................................118

فصل هفتم : شبیه سازی کامپیوتری

7-1 مقدمه ......................................................................................................................................................................119

7-2 مقایسه الگوریتم های I الی IV با الگوریتمهای متعارف  ...........................................................................................119

        7-2-1 مثال اول .....................................................................................................................................................120

        7-2-2 مثال دوم .....................................................................................................................................................129

        7-2-3 مثال سوم ....................................................................................................................................................140

        7-2-4 مثال چهارم .................................................................................................................................................151

        7-2-5 مثال پنجم (بررسی اثر متقابل گلوگاه ها)......................................................................................................158

7-3  شبیه سازی ورود و خروج کاربرها ..........................................................................................................................161

7-4 شبیه سازی معیارهای عدالت دیگر در الگوریتم فازی ...............................................................................................165

7-5 شبیه سازی واقعه گسسته...........................................................................................................................................166

      7-5-1 بخش اول......................................................................................................................................................168

      7-5-2 بخش دوم......................................................................................................................................................177

      7-5-3 شبیه سازی الگوریتم سلسله مراتبی II در حضور ترافیک زمینه .......................................................................178

      7-5-4 مقایسه الگوریتم فازی با Kelly.....................................................................................................................179

7-6 نتیجه گیری..............................................................................................................................................................179

فصل هشتم : نتیجه گیری و پیشنهادات

8-1  نتیجه گیری ............................................................................................................................................................181

8-2  پیشنهادات ..............................................................................................................................................................184

فهرست علائم اختصاری ............................................................................................................................................186

مراجع ..........................................................................................................................................................................188

پیوستها

الف-ن) شکلهای تکمیلی مربوط به شبیه سازی کامپیوتری.............................................................. ................... CD ضمیمه

س) برخی برنامه های کامپیوتری مورد استفاده در شبیه سازی............................................................................... CD ضمیمه

منبع:

[1] Tanenbaum, A.S., Computer Networks, 3rd edition, Prentice Hall, New Jersey, 1996.

[2] Brakmo, L.,  TCP Vegas Release 0.8, Nov. 1994.

http://www.cs.arizona.edu/protocols

[3] Mitra, D. and Seery, J.B., “Dynamic adaptive window for high-speed data networks,” in Proc. ACM SIGCOMM’90 Conf., pp. 30-40, 1990.

[4] Mitra, D. and Seery, J.B., “Dynamic adaptive windows for high-speed data networks with multiple paths and propagation delays,” Computer Networks and ISDN Systems, (25), pp. 663-679, 1993.

[5] Floyd, S., “TCP and explicit congestion notification,” ACM Computer Communications Review, Vol. 24, No. 5, pp. 10-23, Oct. 1994.

[6] Fall, K. and Floyd, S., “Simulation-based comparison tahoe, reno and sack TCP,” ACM Compu. Commun. Rev., Vol. 26, No. 3, pp. 5-21, July 1996.

[7] Kelly, F.P., Maulloo, A.K. and Tan, D.K.H., “Rate control for communication networks: shadow prices, proportional fairness and stability,” J. Oper. Res. Soc., Vol. 49, No. 3, pp. 237-252, Mar. 1998.

[8] Kunniyur, S. and Srikant, R., “End-to-End Congestion Control Schemes: Utility Functions, Random Losses and ECN Marks,” IEEE INFOCOM  Mar. 2000.

[9] Fendick, K.W., Rodriguez, M.A. and Weiss, A., “Analysis of a rate-based feedback control strategy for long-haul data transport.” Performance Evaluation, Vol. 16, pp. 67-84, 1992.

[10] Tan, D.K.H., Mathematical Models of Rate Control for Communication Networks, Ph.D. dissertation, pp. 35-61, Cambridge university, Aug. 1999.

[11] Johari, R. and Tan, D., “End-to-End congestion control for the Internet: Delays and Stability,” IEEE Trans. On Networking, Vol.9, No.6, pp. 818-832, Dec. 2001.

[12] Massoulié, L. and Roberts, J., “Bandwidth sharing: objectives and algorithms,” in Proc. IEEE INFOCOM, Vol.3, 1999, pp. 1395-1403.

[13] Mo, J. and Walrand, J., “Fair End-to-End Window-Based Congestion Control,” IEEE Transactions on Networking, Vol. 8, No. 5, pp. 556-567, Oct. 2000.

[14] Hurley, P., Le Boudec, J.Y. and Thiran, P., “A note on the fairness of additive increase and multiplicative decrease,” in Proc. ITC-16, Edinburg, Scotland, pp. 467-478, June 1999.

[15] Bertsekas, D. and Tsitsiklis, J., Parallel and Distributed Computation. Englewood Cliffs, NJ: Prentice-Hall, 1989.

[16] Gallager, R.G. and Bertsekas, D., Data Networks, Prentice-Hall, NJ 1987.[17] Golestani, S.J., A Unified Theory of Flow Control and Routing in Data Communication Networks, Ph.D Dissertation, MIT, Jan. 1980.

[18] Low, S.H. and Lapsley, D.E., “Optimization flow control, I: basic algorithm and convergence.” IEEE/ACM Transcations on Networking, Vol. 7, No. 6, pp. 861-874, Dec. 1999.

http://www.ee.mu.oz.au./staff/slow/research/.

[19] Lapsley, D.E. and Low, S.H., “An optimization approach to ABR control.” In Proceedings of  the ICC, June 1998.

[20] Rohrs, C.E., Berry, R.A. and O’Halek, S.J., “A control engineer’s look at ATM congestion avoidance.” In Proc. IEEE Globecom’95, pp. 1089-94, Singapore, Nov. 1995.

[21] Sathaye, S., Traffic Management Specification version 4.0. ATM Forum Traffic Management Group, Oct. 1996.

[22] Golestani, S.J. and Bhattacharyya, S., “End-to-End Congestion Control for the Internet: A global optimization framework.” In Proc. Of International Conf. On Network Protocols(ICNP), Oct. 1998.

[23] Kelly, F.P., “Charging and rate control for elastic traffic.” European Transactions on Telecommunications, 8:33-37, 1997. http://www.statslab.cam.ac.uk/frank/elastic.html.

[24] La, R.J. and Anantharam, V., “Utility-Based Rate Control in the Internet for Elastic Traffic.” IEEE Trans. On Networking, Vol. 10, No. 2, pp. 272-286, Apr. 2002.

[25] Altman, E., Başar, T. and Srikant, R., “Nash Equilibria for Combined Flow Control and Routing in Networks: Asymptotic Behavior for a Large Number of Users,” IEEE  Transactions on Automatic Control, Vol. 47, No. 6, June 2002.

[26] Jacobson, V., “Congestion avoidance and control,” Comput. Commun.n Rev., Vol.18, No. 4, pp. 314-329, Aug. 1988.

[27] Massoulié, L., Stability of distributed congestion control with heterogenous feedback delays, Technical Report.

[28] Deb, S. and Srikant, R., Global Stability of Congestion Controllers for the Internet, Technical  Report, University of  Illinois at Urbana-Champaign.

[29] Gibbens, R.J. and Kelly, F.P., “Resource pricing and the evolution of congestion control,” Automatica, 1999.

[30] Mackie-Mason, J.K. and Varian, J.K., “Pricing Congestible Network Resources.” IEEE JSAC, Vol. 13, No. 7, pp. 1141-49, Sept. 1995.

[31] Paschalidis, I.C. and Tsitsiklis, J.N., “Congestion-Dependent Pricing of Network Services.” IEEE/ACM Trans. On Networking, Vol. 8, No. 2, pp. 171-184, Apr. 2000.

[32] Shenker, S., “Fundamental design issues for the future Internet,” IEEE J Selected Areas Commun., Vol.13, No.7, pp.1176-1188, Sept. 1995.

[33] Blake, S., Black, D., Carlson, M., Davies, E., Wang, Z. and Weiss, W., “An Architecture for Differentiated Services.” Dec. 1998, [RFC 2475].

[34] Key, P.B., “Resource Pricing for Differentiated Services.” Microsoft Research, St. George House, Cambridge, U.K. Online available at:

http://research.microsoft.com/users/pbk/

[35] Kelly, F.P., “Effective bandwidth at multi-class queues.” Queueing Systems, Vol. 9, pp. 5-16, 1991.

[36] Nagle, J., “On Packet Switches with Infinite Storage.” IEEE Transactions on Communications, Vol. 35, pp. 435-438, 1987.

[37] Demers, A., Keshav, S. and Shenker, S., “Analysis and Simulation of a Fair Queuing Algorithm.” SIGCOMM CCR 19, No. 4 (1989), pp. 1-12.

[38] Keshav, S., Engineering Approach to Computer Networking, An: ATM Networks, the Internet and the Telephone Network, Addison Wesley Professional, 1st Edition, 1997.

[39] Stiliadis, D. and Varma, A., “Latency-Rate Servers: A General Model for Analysis of Traffic Scheduling Algorithms” IEEE Transactions on Networking, Vol. 6, No. 3, pp. 611-624, 1996.

[40] Shreedhar, M. and Varghese, G., “Efficient Fair Queuing using Deficit Round Robin.” SIGCOMM CCR 25, No. 4, 1995.

[41] Ferrari, D. and Verma, D., “A scheme for real-time channel establishment in Wide Area Networks.” IEEE journal on selected areas in communications, Vol. 8, No. 3, pp. 368-379, 1990.

[42] Verma, D., Zhang, H. and Ferrari, D., “Guaranteeing delay jitter bounds in packet switching networks.” Tricomm’91, 1991.

[43] Floyd, S. and Jacobson, V., “Random Early Detection Gateways for Congestion Avoidance.” IEEE/ACM Transactions on Networking, Vol. 1, No. 4, pp. 397-413, 1993.

[44] RFC 1633, Braden, R., Clark, D. and Shenker, S., “Integrated Services in the Internet Architecture: an Overview.” June 1994.

[45] Bernet, Y., Networking Quality of Service and Windows Operating Systems, New Riders Publishing and Microsoft Corporation, 2001.

[46] Gerla, M. and Kleinrock, L., “Flow Control: A Comparative Study”, IEEE Trans. Commun. , Vol. COM-28, pp.553-574, Apr. 1980.

[47] Chiu, D.M. and Jain, R., “Analysis of the increase and decrease algorithms for congestion avoidance in computer networks.” Computer Networks and ISDN Systems , No. 17, pp. 1-14, 1989.

[48] Arulambalam, A. and Chen, X.Q., “Allocating fair rates for available bit rate service in ATM networks.” IEEE Communication Magazine, 1996, pp. 92-100.

[49] Hernandez-Valencia, E.J., Benmohamed, L., Chong, S. and Nagarajan, R., “Rate Control Algorithms for the ATM ABR Service.” Europ. Trans. Telecom. Vol. 8, pp. 7-20, 1997.

[50] Charny, A., An algorithm for rate allocation in packet-switching networks with feedback, Master’s thesis, MIT, Cambridge, MA, 1994.

[51] Jain, R., “Congestion control and traffic management in ATM networks: Recent advances and a survey,” Comput. Networks ISDN Syst. , Vol. 28, No. 13, pp. 1723-28, Oct. 1996.

[52] Mayer, A., Ofek, A. and Yung, M., “Approximating max-min fair rates via distributed local scheduling with partial information,” in IEEE Infocom’96, San Francisco, CA, USA, Mar. 1996, pp. 926-936.

[53] Hahne, E., “Round-robin scheduling for max-min fairness in data networks,” IEEE J. Select. Areas Commun., Vol. 9, pp. 1024-39, Sept. 1991.

[54] Floyd, S. and Jacobson, V., “Connection with multiple congested gateways in packet-switched networks, Part 1: One-way traffic,” ACM Comput. Commun. Rev., Vol. 21, No. 5, pp. 30-47, Aug. 1991.

[55] Mankin, A., “Random drop congestion control,” in Proc. SIGCOMM’90, Philadelphia, PA, pp. 1-7, Sept. 1990.

[56] Floyd, S. and Jacobson, V., “On traffic phase effects in packet switched gateways,” Internetworking: Res. and Experience, Vol. 3, No. 3, pp. 115-156, Sept. 1993.

[57] Jaffe, J.M., “Flow control power is non-decentralizable,” IEEE Trans. Commun., Vol. COM-29, pp. 1301-06, Sept. 1981.

[58] Shenker, S., “A theoretical analysis of feedback flow control,” in ACM SIGCOMM’90, Philadelphia, PA, pp. 156-165, Sept. 24-27, 1990.

[59] Jain, R., “Myths about congestion management in high-speed networks,” Internetworking: Res. and Experience, Vol. 3, pp. 101-113, 1992.

[60] Boutremans, C., Vojnovic, M. and Le Boudec, J.Y., “Global fairness of additive-increase and multiplicative-decrease with heterogenous round-trip times,” in IEEE Infocom’00, Tel Aviv, Israel, pp. 1303-12, Mar. 2000.

[61] Ramakrishnan, K.K. and Jain, R., “A binary feedback scheme for congestion avoidance in computer networks with a connectionless network layer,” in Proc. ACM SIGCOMM’88 Conf., pp. 303-313, 1988.

[62] Keshav, S., “A control theoretic approach to flow control,” in Proc. ACM SIGCOMM’91 Conf., pp. 3-15, Sept. 1991.

[63] Mitra, D., “Asymptotically optimal design of congestion control for high- speed data networks.” IEEE Transactions on Communications, Vol. 40, No. 2, pp. 301-311, Feb. 1992.

[64] Zhang, L., Deering, S., Estring, D., Shenker, S. and Zappala, D., “RSVP: A new resource reservation protocol,” IEEE Networks, Vol. 7, No. 5, Sept. 1993.

[65] Braden, B., et al. “Recommendations on queue management and congestion avoidance in the Internet. Internet Draft, March 1997.

[66] Bolot, J.C. and Shankar, A.U., “Dynamic behavior of rate-based flow control mechanisms.” ACM  SIGCOMM Comp. Commun. Rev., Vol. 20, pp. 35-49, 1990.

[67] Bonomi, F., Mitra, D. and Seery, J.B., “Adaptive algorithms for feedback-based flow control in high-speed wide-area networks.” IEEE J. Selected Areas Commun. , Vol. 13, pp. 1267-1283, 1995.

[68] Luenberger, D.G., Linear and Nonlinear Programming, 2nd Ed. Addison-Wesley Publishing Company, 1984.

[69] Zadeh, L.A., “Fuzzy Sets”, Inform. Control, pp.338-353, 1965.

[70] Takagi, T. and Sugeno, M., “Fuzzy Identification of Systems and its Applications to Modeling and Control.” IEEE Trans. on Systems Man and Cybernetics, Vol. 15, pp. 116-132, 1985.

[71] Lee, C.C., “Fuzzy Logic in Control Systems: Fuzzy Logic Controller-Part I”, IEEE Trans. On System, Man and Cybernetics , Vol.20, No.2, pp.404-418, Mar.1990.

[72] Bertsekas, D., Gafni, E. and Gallager, R.G., “Second Derivative Algorithms for Minimum Delay Distributed Routing in Networks.” IEEE Trans. On Communication, Vol. COM-32, No. 8, Aug. 1984, pp. 911-919.

[73] Papoulis, A., Probability, Random Variables, and Stochastic Processes, McGraw-Hill Series in Electrical Engineering, Second Edition, 1984.

[74] Vinnicombe, G., “On the stability of end-to-end congestion control for the Internet”, Technical Report CUED/F-INFENG/TR.398, Engineering Department,University of Cambridge, 2000. http://wwwcontrol.eng.cam.ac.uk/gv/internet.