بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارزیابی کارایی مدلهای مارکوف در شبیه سازی شبکه های کامپیوتری
چکیده - شبکه های کامپیوتری به کلاسی از سیستم های فیزیکی تعلق دارند که این سیستم ها می توانند توسط مدلهای شبیه سازی رخداد گسسته به طور موثری مورد مطالعه قرار گیرند. این مقاله به مدلهای مارکوف گسسته زمان برای شبیه سازی شبکه های کامپیوتری با تعداد ثابت دو مشتری می پردازد. مدل مفروض با استفاده از دو روش CTMC و Gordan-Newell حل می شود. سپس معیارهای کارایی عنوان شده و نتایج حاصل از شبیه سازی روش CTMC با نتایج حاصل از مدلسازی روش Gordan-Newell با هم مقایسه می شوند.
کلید واژه- شبیه سازی، زنجیره های مارکوف گسسته زمان، ارزیابی کارایی
-1 مقدمه
شبکه های کامپیوتری به کلاسی از سیستم های فیزیکی تعلق دارند که این سیستم ها می توانند توسط مدلهای شبیه سازی رخداد گسسته به طور موثری مورد مطالعه قرار گیرند.
با توجه به این که حالت شبکه با مقادیر عددی توصیف می شود، شبکه های کامپیوتری در طبقه بندی مدل هایی با رفتار بدون حافظه قرار می گیرند. تعیین رفتار شبکه های کامپیوتری از طریق مدلهای مارکوف امکان پذیر است زیرا زنجیره مارکوف یک فرایند تصادفی خاصی است که رفتار احتمالی آینده فرایند را به صورت منحصر به فردی توسط حالت موجود توصیف می کند.
در این مقاله یک شبکه بسته با تعداد ثابت دو مشتری توسط روش های CTMC و Gordan-Nowell حل شده و سپس معیارهای کارایی محاسبه و در پایان نتایج حاصل از دو روش با هم مقایسه می گردند.
-2 بیان مسئله
شبکه های صفی که تعداد ثابتی مشتری بین صف های مختلف آن در گردش میباشند، را شبکه صفی بسته میگویند. در این سیستم ها کل تعداد بسته ها ثابت بوده و چندین سرویس دهنده وجود دارد به طوری که وقتی یک بسته سیستم را ترک میکند، یک بسته دیگر جایگزین آن میشود.
شبکه شکل 1 با تعداد ثابت n بسته طراحی شده است. در این شبکه تعداد حالات ممکن محدود است. این شبکه از سه گره تشکیل شده است. فرض کنید m تعداد گره ها و n تعداد بسته ها باشد که بین گره های مختلف در حرکت است. N حالت ممکن از طریق فرمول زیر محاسبه می شود:
مجموعه حالت های ممکن برای شبکه ای با سه گره به صورت زیر نشان داده می شود:
i تعداد بسته های قابل دسترس توسط گره 1 با میانگین زمان سرویس 1 1 و j تعداد بسته های قابل دسترس توسط گره 2 با میانگین زمان سرویس 2 1 و k تعداد بسته های قابل دسترس توسط گره 3 با میانگین زمان سرویس 3 1 می باشد.
برا ی سه گره و دو بسته در شبکه تعداد حالت ها برابر خواهد بود با:
اگر X i تعداد بسته های موجود در یک گره باشد بردار X (X1, X 2, X3) مجموعه مشتریان در گره های 1،2 و 3 در شبکه را نشان می دهد. پس کل حالت ها به صورت 1)،1،(0، 2)،0،(0، 1)،0،(1، 0)،2،(0، 0)،1،(1 و 0)،0،(2 خواهند شد.
تعداد کل بسته های قابل دسترس در شبکه مقداری ثابت و برابر با است. بسته های موجود در گره 1 با
احتمال a توسط گره 2 یا با احتمال a-1توسط گره 3 و بسته های موجود در گره 2 و 3 می توانند با احتمال 1 توسط گره 1
قابل دسترس باشند .[1]
دیاگرام حالت برای شبکه مفروض در شکل 2 نشان داده شده است.
-1-2 مدل مارکوف گسسته زمان
یک مدل مارکوف گسسته زمان به صورت مجموعه ای از احتمالات گذر بین حالت های گسسته مدل تعریف می شود. گذرهای بین حالتها وابسته به احتمالات گذر بین حالت ها هستند. پس از نوشتن تمام حالت ها می توان با دو روش CTMC و Gordan-Newell به حل معادلات تشکیل شده اقدام کرد.
-1-1-2 حل حالت پایدار با CTMC
N×N احتمالات گذر بین N حالت، ماتریس احتمال گذر نامیده می شود. اگر 0 بردار احتمال اولیه باشد، احتمال حالت پس از k گام با بردار زیر مشخص می شود:
ماتریس pk از k بار ضرب ماتریس p در خودش حاصل می شود. همچنین در مدل مارکوف بردار احتمال حالت پایدار برایتمامی حالتها از فرمول زیر محاسبه می شود :[3]
معادله ذکر شده با شرط زیر همراه است:
حال می توان دستگاه معادلات جریان را برای شبکه مفروض نوشت.[2]
-2-1-2 حل حالت پایدار با روش Gordan-Newell
قضیه اول: X ، نا محدود، همگن و غیر کاهشی است .[3] قضیه دوم: بردار احتمال حالت پایدار برای هر حالت ( i, j,k ) به صورت زیر بیان می شود :[3]
-3 محاسبه معیارهای کارایی
پس از محاسبه احتمالات حالات پایدار توسط روش های ذکر شده، معیارهای کارایی به صورت:
توان عملیاتی1
بهره وری2
متوسط تعداد مشتریان3
متوسط زمان پاسخ1
متوسط زمان انتظار2
برای شبکه مفروض قابل محاسبه است .[2]
-4 شبیه سازی و مدلسازی
در این مقاله از نرم افزار WinPEPSY برای شبیه سازی [2] و از نرم افزار Matlab برای مدلسازی شبکه مفروض استفاده
