بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بررسی ارزیابی کارایی شبکه های کامپیوتری به کمک مدل های مخفی مارکوف
چکیده
ارزیابی کارایی برای تحقیق کیفیت شبکه های کامپیوتری و سیستم های ارتباطی سود می جوید. ارزیابی می تواند به صورت کیفی و یا کمی باشد. روش های احتمالی مانند زنجیره مارکوف و یا دیاگرام بلوکی قابلیت اطمینان (RBD) برای ارزیابی استفاده می شوند. از نتایج پیش بینی اشکال می توان نقاط ضعف را ارزیابی کرد و سپس به کمک روش های دیگر با آن مقابله کرد. در این مقاله، معیارهای ارزیابی کارایی شبکه از جمله قابلیت اطمینان و دسترس پذیری بررسی می شود. و با استفاده از مدل های مخفی مارکوف به ارزیابی کارایی شبکه ها پرداخته ایم.
واژه های کلیدی: ارزیابی کارایی، قابلیت اطمینان، دسترس پذیری، مدل مخفی مارکوف.
-1 مقدمه
در این مقاله به بررسی روش های افزایش تحمل پذیری اشکال در سیستم های کامپیوتری و ارزیابی قابلیت اطمینان آنها اشاره می کنیم. تحمل پذیری اشکال به قابلیتی از سیستم اشاره دارد که سیستم را توانا می سازد تا حتی در صورت بروز اشکال در آن بتواند آن اشکال را پوشش داده و از خرابی سیستم جلوگیری کند. این قابلیت در بسیاری از سیستم ها در زمره مهمترین ملزومات غیرکارکردی سیستم است.[7] از جمله روشهایی که برای ارزیابی کارایی شبکه می توان مطرح کرد: CRAM، مدل BNF و استفاده از مدل مخفی مارکوف است.
مدل سازی های گذشته شبکه با تمرکز بر روی رفتار از دست دادن و با استفاده از مدل زمان گسسته بود که از مدل مارکوف مرتبه kام برای وابستگی های زمانی گذرا در فقدان بسته استفاده می شود. Salamatian و [3] Vaton از مدل HMM زمان گذرا برای فقدان بسته در کانال های شبکه و نمایش اعدادی که از نیازمندی های حالتهاست بطور قابل ملاحظه ای از مدل مارکوف مرتبه kام استفاده کرده اند. برای مفهوم شبیه سازی کاربرد یا پروتکل شبکه، ویژگیهای تأخیر نیز باید مدل شوند. علاوه بر این، تخصیص تأخیر یا از بین رفتن بسته در زمان اختیاری ضروری است. مدل زمان گذرا نمی تواند ارائه شود.[1]
-2 قابلیت اطمینان
قابلیت اطمینان1 یا R(t)، احتمال شرطی این است که سیستم در بازه زمانی [t0,t] به درستی کار کند، به شرط این که سیستم در ابتدای بازه (t0) درست بوده باشد. عدم اطمینان2 یا Q(t)، احتمال شرطی این است که سیستم در بازه زمانی [t0,t] به درستی کار نکرده است، به شرط این که سیستم در ابتدای بازه (t0) درست بوده باشد .[9] در نتیجه وقفه های کوتاه و بازه های زمانی حتی کوتاه مدت عدم کارکرد س یستم و سپس تعمیر آن در رابطه با قابلیت اطمینان قابل قبول نمی باشد. نکته مهمی که می توان اشاره کرد تحمل پذیری اشکال روشی برای افزایش قابلیت اطمینان است. اما یک سیستم تحمل پذیری اشکال الزاما بسیار قابل اطمینان نیست.
قابلیت دسترسی3 یا A(t)، احتمال این است که سیستم در زمان t در حال کار درست و در دسترس باشد و کارکرد خود را انجام دهد. توجه شود که قابلیت اطمینان در بازه زمانی تعریف می شود ولی قابلیت دسترسی در لحظه زمان تعریف شود. در ضمن قابلیت تعمیر شدن سیستم در قابلیت اطمینان سیستم تأثیری ندارد اما در قابلیت دسترسی سیستم بسیار مهم است.[7]
-3 روش های پیشنهادی
روشهای جدیدی برای ارزیابی کارایی قابلیت اطمینان ارائه شده است. از وقتی که کارایی ترافیک در لینکها و مسیرها توانسته در قابلیت اطمینان تاثیر گذارد، کارایی داده های نمونه روی لینک از طریق چگونگی کارایی ارزیابی می شود که در اینجا شیوه مطرح شده شامل لینک کاربردی، مسیر کاربردی، شبکه و کاربرد است که می توان توسط مدل BNF تعریف کرد. همچنین ایندکس قابلیت اطمینان
چند لایه ای پیشنهاد شده است که توسط پارامترهای گوناگون کارایی و معیار خرابی مشخص شده است. از ویژگی های این مدل: عامل تعیین کننده مسیر و لینک، وضوح توصیف تأثیرات خرابی و اندازه گیری براساس محاسبات ترکیبی است.[5]
یک روش ارزیابی کارایی جدید برای شبکه های گسترده، محلی و star ارائه شده است. از دلایل اصلی ارائه آن طول یک رویداد شبکه است. در گذشته برای ارزیابی شبکه از متدهای شبکه صف stochastic و MVA ، توصیف متد پیچیدگی استفاده می شد که در حال حاضر برای شبکه های فعلی مناسب نیستند. با استفاده از CRAM وضعیت شبکه ها بهتر بررسی می شود. این متد بر پایه فرضیات است و با موجودیت هایی از اعداد اختیاری قابل محاسبه است که برای تمام مسیرهای نزدیک با معادلات به اثبات رسیده، در CRAM فقط یک موجودیت در یک زمان از مسیر بسته وجود دارد که با اندازه گیری کنترل جریان بدست می آید.[4]
-4 بررسی مدل های مخفی مارکوف
مدل مخفی مارکوف در اواخر دهه 1960 میلادی معرفی گردید و در حال حاضر به سرعت در حال گسترش دامنه کاربردها می باشد. دو دلیل مهم برای این مساله وجود دارد: اول اینکه این مدل از لحاظ ساختار ریاضی بسیار قدرتمند است و به همین دلیل مبانی نظری بسیاری از کاربردها را شکل داده است. دوم اینکه مدل مخفی مارکوف اگر به صورت مناسبی ایجاد شود می تواند برای کاربردهای بسیاری مورد استفاده قرار گیرد2]،.[8
مدل های مخفی مارکوف (HMM) درکاربردهای بسیاری شامل تشخیص گفتار4، پردازش های سیگنال5، هوش مصنوعی6، زیست شناسی محاسباتی7، امور مالی8، پردازش تصویر9، و تشخیص بیماری10 و ... استفاده می شود. اولین کاربرد اصلی و موفق HMM ها در تشخیص گفتار بود، که یک مجموعه ی گسترده ای از زمینه های کاربردی را به همراه داشت. اساس HMM بر پایه تئوری های غنی است که می تواند ابعاد مختلفی از کاربردها را بپذیرد. ولی استفاده از آن در ارزیابی کارایی و ارتباطات کامپیوتری نسبتاً جدید است .[9]
در مدل سازی کارایی، معمولاً تحلیلگر مفهوم شفافی از چگونگی کارهای آنالیز سیستم ارائه می دهد. اگر یک مدل مارکوفی الگوی انتخابی است، وظیفه اصلی انتخاب متغیرهای حالت سیستم مناسب و طیفی از مقادیر ممکن برای هر کدام می باشد .[10] به عنوان مثال، اگر سیستمی توسط یک صف تک سرور مدل شود و هدف از پیش بینی زمان وقفه برای نرخ ورودی باشد، متغیر حالت انتخاب شده تعدادی از مشتریان صف برای سرویس است. ممکن است متغیرهای حالت دیگری ارائه شده باشد. نوع دیگری از اجتماع مدلها در این دسته بندی، مدل سازی در دسترس اس ت. در این مورد، عامل ارائه شده ی متغیرهای حالت می تواند قابل استفاده یا مدل های مختلف ضعیفی باشند.
معمولاً، مدل هایی شبیه به سیستم صف بندی ساده یا مدل قابل اعتماد، پارامترهایی از برخی دانش های قبلی از رفتار سیستم دارند. یک نکته کلیدی در اهمیت دادن به این مدل، گرفتن یک ویژگی از حالت سیستم که بصورت مستقیم قابل مشاهده می باشد. برعکس، با
HMMحالت سیستم از پردازش زمینه ای اساسی در مشاهده مستقیم در نظر گرفته نمی شود. تقریباً برخی مقادیر مشاهده شده می تواند یک تابع احتمالاتی از حالت مشاهده فرایند مارکوف زمینه ای باشد (بنابراین منشأ نام مدل مخفی مارکوف است). اگر پارامترهای HMM شناخته شده باشد، به راحتی می توان دنباله ای از نمونه های مشاهده شده را تولید کرد:
–1 انتخاب حالت اولیه بر طبق . π(0)
- 2 تنظیم . t = 1
–3 انتخاب Ot = vk با توجه به توزیع احتمال شرطی برای حالت . qt یعنی اگر qt = si باشد، انتخاب vk با احتمال bi(k) است.
4 – انتخاب حالت بعدی با توجه به حالت احتمالات گذر یا انتقال.
5 – مجموعه t = t+1 اگر t < T باشد، در غیر اینصورت خاتمه می یابد. اگر مدل شناخته شده باشد، چهار مسئله اساسی را می توانیم شناسایی کنیم:
مسئله .1 با توجه به دنباله مشاهدات OT = O1O2 . . .OT و مدل M ، محاسبه احتمال مشاهده دنباله خروجی OT با توجه به مدل مخفی (زیرین) M ، انجام می گیرد. یعنی . P[OT|M]
مسئله .2 با توجه به توالی مشاهدات OT = O1O2 . . .OT و مدل M ، بهترین دنباله حالت QT = q1, q2, . . . , qT با بهترین دنباله خروجی OT مشخص می شود. به بیان دیگر، ما می خواهیم نموداری از حالت های مخفی را در مدل داشته باشیم. در اینجا ما نیاز به تعریف رسمی تری که منظور بهترین حالت است داریم، به عنوان مثال تعریف خاصی از تابع هدف. دو احتمال وجود دارد: (i) برای هر زمان حالتt حداکثر احتمال از MC مخفی یا زمینه ای چقدر است، و ( ii) حداکثر دنباله احتمال حالتها چقدر است. توجه شود که اینها بطورکلی متفاوت هستند. به عنوان مثال، پاسخ (i) می تواند st = si و st+1 = sj باشد اما اگر pi,j ، 0 شود دنباله ای از حالتهای >si , sj< هرگز نمی تواند رخ دهد.
مسئله .3 با توجه به اینکه توالی مشاهدات OT = O1O2 . . .OT است، مدل M مخفی زیرین ایجاد می شود، به طوریکه P[OT |M] بیشترین حد است.
مسئله .4 با توجه به برخی مدل های ممکن M i 1 ≤ i ≤ K و توالی مشاهده شده، مقداری از احتمالات Mj در مدل واقعی است، .P[Mj |O]
- 4-1 توضیح کوتاهی از الگوریتم برای حل انواع مشکلات پایه ای
مسئله :P[OT |M] -4-1-1 ایجاد یک الگوریتم تکراری برای محاسبه P[OT |M] که در آن N2T پیچیدگی است . تعریف:
که OT = O1O2 . . .Ot است، به عنوان مثال، اولین t مقدار مشاهده شده است. بنابراین t(ot, qt si) احتمالاتی از اولین مشاهدات t و پایان حالت Si در زمان t است. برای راحتی علائم را بصورت مختصر استفاده می کنیم: t(Ot, qt si)و یا . t(Ot, Si) سپس:
با 1(O1, Si) (0)[Si]bi(O1) شروع می شود، در عبارت بالا از محاسبه مقادیری از زمان t+1 در مقداری برای زمان t استفاده شده است. که باید بصورت روشن بیان شود:
پیچیدگی محاسباتی را برای هر افزایش زمانی بدست می آید که به وضوح N2 در جاییکه مقادیر N وجود دارد در هر افزایش محاسبه ی هر مقداری در ترتیب محاسبات N طول می کشد. به همین ترتیب یک الگوریتم رو به عقب تکراری با استفاده از توابع کمکی وجود دارد.
که در آن Ot+1=Ot+1Ot+2 …OT استفاده می شود، به عنوان مثال مقادیر مشاهده از t + 1 به T است.
مسئله - 4-1-2 الگوریتمی برای نسخه های خاص از مسئله 2 وجود دارد: محاسبه . P[qT si | M ,O]
چگونگی محاسبه راه حل مسئله 1 را می دانیم، P [qT = Si | M,O] از آنجا که:
برای بیان P[O |M] به خوبی استفاده شده. پس:
در شرایط T (OT, Si)از توابعی که قبلاً معرفی شده اند، فرض زیر را داریم:
