تجزیه و تحلیل قابلیت دسترسی

تجزیه و تحلیل قابلیت دسترسی یک راه حل برای مشکل قابلیت دسترسی در زمینه خاص سیستم های توزیع شده است. برای تعیین اینکه به کدام کشورهای جهانی می توان از طریق یک سیستم توزیع شده متشکل از تعداد مشخصی از نهادهای محلی که با تبادل پیام ارتباط برقرار می کنند ، دسترسی پیدا کرد، استفاده می شود.

بررسی اجمالی

تجزیه و تحلیل قابلیت دسترسی در مقاله ای از سال 1978 برای تجزیه و تحلیل و تأیید پروتکل های ارتباطی معرفی شد . ^[۱] این مقاله با الهام از مقاله ای توسط بارتلت و همکاران ارائه شده است. از 1968 ^[۲] که پروتکل بیت متناوب را با استفاده از مدل سازی حالت محدود موجودیت های پروتکل ارائه داد و همچنین اشاره کرد که پروتکل مشابهی که قبلاً شرح داده شد دارای نقص طراحی است. این پروتکل به لایه پیوند تعلق دارد و تحت برخی مفروضات ، تحویل صحیح داده ها بدون از دست دادن و یا کپی برداری را ، علی‌رغم وجود برخی اوقات خرابی یا از بین رفتن پیام، به عنوان سرویس ارائه می دهد.

برای تجزیه و تحلیل قابلیت دستیابی ، نهادهای محلی با حالت ها و انتقال های خود مدل سازی می شوند. موجودیت با ارسال پیام ، مصرف پیام دریافتی یا انجام تعامل در رابط خدمات محلی خود ، حالت را تغییر می دهد. دولت جهانی $s=(s_{1},s_{2},...,s_{n},medium)$ یک سیستم با n موجودیت ^[۳] توسط ایالات تعیین می شود $s_{i}$ (من = 1 ، ... n) از موجودیت ها و وضعیت ارتباطات $medium$ . در ساده ترین حالت ، محیط بین دو موجودیت توسط دو صف FIFO در جهت مخالف ، که حاوی پیام های در حال انتقال است (که ارسال می شود ، اما هنوز مصرف نشده است) مدل می شود. تجزیه و تحلیل قابلیت دسترسی با تجزیه و تحلیل تمام توالی های احتمالی انتقال حالت موجودیت ها و وضعیت جهانی مربوطه ، رفتار احتمالی سیستم توزیع شده را در نظر می گیرد. ^[۴]

نتیجه تجزیه و تحلیل قابلیت دستیابی ، نمودار انتقال وضعیت جهانی است (همچنین نمودار قابلیت دستیابی نیز نامیده می شود) که تمام حالت های جهانی سیستم توزیع شده را که از حالت اولیه جهانی قابل دسترسی هستند ، و همه توالی های ممکن ارسال ، مصرف و تعاملات خدماتی که توسط محلی انجام می شود را نشان می دهد موجودیت ها. با این حال ، در بسیاری از موارد ، این نمودار انتقال نامحدود است و نمی توان آن را به طور کامل جستجو کرد. نمودار انتقال می تواند برای بررسی نقایص کلی طراحی پروتکل (به زیر را ببینید) ، بلکه همچنین برای بررسی اینکه توالی تعاملات سرویس توسط نهادها با الزامات ارائه شده توسط مشخصات سرویس جهانی سیستم مطابقت دارد. ^[۱]

خصوصیات پروتکل

محدودیت: نمودار انتقال وضعیت جهانی محدود است اگر تعداد پیام هایی که ممکن است در حال انتقال باشند محدود است و تعداد ایالات همه موجودات محدود است. این سوال که آیا تعداد پیام ها در مورد اشخاص محدود دولت محدود باقی می ماند ، به طور کلی مسئله تصمیم‌ناپذیر است . ^[۵] وقتی تعداد پیام های منتقل شده به یک آستانه مشخص می شود ، یکی معمولاً نمودار انتقال را کوتاه می کند.

موارد زیر نقایص طراحی است:

بن بست جهانی: اگر همه موجودات منتظر مصرف پیام باشند و هیچ پیغامی در حال انتقال نباشد ، این سیستم در بن بست جهانی قرار دارد. عدم وجود بن بست های جهانی را می توان با بررسی اینکه هیچ حالتی در نمودار قابلیت دستیابی به بن بست جهانی رسیده است ، تأیید کرد.
بن بست های جزئی: یک موجود در حالت بن بست است اگر منتظر مصرف پیام است و سیستم در یک وضعیت جهانی است که چنین پیامی در حال انتقال نیست و هرگز در هر کشور جهانی که می تواند در آن برسد ارسال نخواهد شد. آینده. چنین ویژگی غیر محلی را می توان با انجام وارسی مدل در نمودار قابلیت دسترسی تأیید کرد.
استقبال نامشخص: درصورتی که انتظار پیام بعدی برای مصرف توسط مشخصات رفتار موجودیت در وضعیت فعلی آن وجود نداشته باشد ، واحد تجاری دارای استقبال نامشخص است. عدم وجود این شرایط را می توان با بررسی همه حالت ها در نمودار قابلیت دسترسی تأیید کرد.

یک مثال

به عنوان مثال ، ما سیستم دو موجود پروتکل را در نظر می گیریم که پیام های ma ، mb ، mc و md را با یکدیگر مبادله می کنند ، همانطور که در نمودار اول نشان داده شده است. پروتکل با رفتار دو موجودیت تعریف می شود ، که در نمودار دوم به صورت دو ماشین حالت ارائه می شود. در اینجا نماد "!" به معنای ارسال پیام است ، و "؟" به معنای مصرف پیام دریافتی است. حالتهای اولیه حالتهای "1" هستند.

نمودار سوم نتیجه تجزیه و تحلیل قابلیت دستیابی برای این پروتکل را در قالب یک ماشین حالت جهانی نشان می دهد. هر دولت جهانی دارای چهار م componentsلفه است: وضعیت نهاد پروتکل A (چپ) ، حالت نهاد B (راست) و پیام های در حال انتقال در وسط (قسمت بالایی: از A به B ؛ قسمت پایین: از B به A ) هر انتقال این دستگاه حالت جهانی مربوط به یک انتقال موجودیت پروتکل A یا نهاد B است. حالت اولیه [1 ، - - ، 1] است (بدون ارسال پیام در حال انتقال).

یکی می بیند که این مثال دارای یک فضای جهانی محدود است - حداکثر تعداد پیام هایی که ممکن است همزمان حمل و نقل شوند دو پیام است. این پروتکل دارای یک بن بست جهانی است که این حالت است [2 ، - - ، 3]. اگر کسی انتقال A را در حالت 2 برای مصرف پیام mb حذف کند ، در ایالات جهانی [2 ، ma mb ، 3] و [2 ، - mb ، 3] استقبال نامشخصی صورت می گیرد.

انتقال پیام

طراحی یک پروتکل باید با خواص محیط ارتباطی زمینه ای ، با احتمال عدم موفقیت شریک ارتباطی و سازوکار مورد استفاده توسط نهادی برای انتخاب پیام بعدی برای مصرف ، سازگار شود. رسانه ارتباطی برای پروتکل ها در لایه پیوند به طور معمول قابل اعتماد نیست و امکان دریافت اشتباه و از دست دادن پیام را فراهم می کند (به عنوان انتقال حالت رسانه مدلسازی می شود). پروتکل های استفاده شده از سرویس IP اینترنت نیز باید امکان تحویل خارج از سفارش را داشته باشند. پروتکل های سطح بالاتر معمولاً از یک سرویس حمل و نقل جلسه محور استفاده می کنند که به این معنی است که رسانه انتقال FIFO قابل اطمینان از پیام ها را بین هر جفت موجودیت فراهم می کند. با این حال ، در تجزیه و تحلیل الگوریتم های توزیع شده ، اغلب این احتمال وجود دارد که برخی موجودیت ها به طور کامل از کار بیفتند ، که به طور معمول (از دست دادن پیام در رسانه) با رسیدن یک پیام مورد انتظار توسط مکانیزم مهلت شناسایی نمی‌شود.

در مورد اینکه آیا یک نهاد می تواند پیام خاصی را برای مصرف انتخاب کند ، وقتی چندین پیام از راه رسیده و آماده مصرف است ، فرض های مختلفی ارائه شده است. مدل های اصلی به شرح زیر است:

صف ورودی تک: هر موجودیت دارای یک صف FIFO منفرد است که پیام های ورودی تا زمان مصرف در آنها ذخیره می شود. در اینجا نهاد قدرت انتخاب ندارد و مجبور است اولین پیام را در صف مصرف کند.
صف های متعدد: هر نهاد دارای چندین صف FIFO است ، یکی برای هر شریک ارتباطی. در اینجا موجودیت بسته به وضعیت خود ، تصمیم دارد که پیام ورودی بعدی را از کدام صف (یا صف ها) مصرف کند ، تصمیم بگیرد.
استخر پذیرش: هر نهاد دارای یک استخر واحد است که پیامهای دریافت شده تا زمان مصرف در آنها ذخیره می شود. در اینجا نهاد قدرت تصمیم گیری دارد ، بسته به حالت خود ، در مورد نوع پیام بعدی استفاده کند (و اگر هنوز پیام دریافت نشده است منتظر پیام باشید) ، یا احتمالاً یکی را از مجموعه انواع پیام مصرف کند (به منظور برخورد با گزینه های دیگر).

مقاله اصلی که مشکل پذیرایی های نامشخص را مشخص می کند ، ^[۶] و بیشتر کارهای بعدی ، یک صف ورودی واحد در نظر گرفته است. ^[۷] بعضی اوقات ، پذیرش های نامشخص توسط یک وضعیت رقابتی ای معرفی می شوند ، به این معنی که دو پیام دریافت می شود و ترتیب آنها تعریف نمی‌شود (که این امر معمولاً در صورت دریافت از طرف شرکای مختلف صورت می گیرد). با استفاده از صف های مختلف یا استخرهای پذیرایی ، بسیاری از این نقایص طراحی از بین می روند. ^[۸] با استفاده منظم از استخرهای پذیرش ، تجزیه و تحلیل قابلیت دسترسی باید بن بست های جزئی و پیام هایی را که برای همیشه در استخر باقی مانده اند بررسی کند (بدون اینکه توسط نهاد مصرف شود) ^[۹]

مسائل عملی

بیشتر کارها در زمینه مدل سازی پروتکل از مدلهای ماشین حالات متناهی (FSM) برای مدل سازی رفتار موجودات توزیع شده استفاده می شود (همچنین به برقراری ارتباط ماشینهای حالت محدود مراجعه کنید). با این حال ، این مدل برای مدل سازی پارامترهای پیام و متغیرهای محلی به اندازه کافی قدرتمند نیست. بنابراین اغلب به اصطلاح از مدلهای FSM توسعه یافته استفاده می شود ، مانند پشتیبانی از زبانهایی مانند ماشین حالت یو.ام.ال یا SDL . متأسفانه ، تجزیه و تحلیل قابلیت دستیابی برای چنین مدلهایی بسیار پیچیده تر می شود.

یک مسئله عملی تجزیه و تحلیل قابلیت دسترسی به اصطلاح "حالت انفجار فضای" است. اگر دو موجودیت یک پروتکل هر کدام 100 حالت داشته باشند ، و محیط ممکن است شامل 10 نوع پیام باشد که در هر جهت حداکثر دو مورد را نشان می دهد ، بنابراین تعداد حالت های جهانی در نمودار قابلیت دسترسی به عدد 100 100 100 x محدود می شود (10x10) x (10 x 10) که 100 میلیون است. بنابراین تعدادی ابزار برای انجام خودکار تجزیه و تحلیل قابلیت دستیابی و بررسی مدل در نمودار قابلیت دستیابی تولید شده است. ما فقط به دو نمونه اشاره می کنیم: جستجوگر مدل SPIN و یک جعبه ابزار برای ساخت و تحلیل فرایندهای توزیع شده .

بیشتر خواندن

پروتکل های ارتباطی
جرالد هولزمن: طراحی و اعتبارسنجی پروتکل های رایانه ای ، Prentice Hall ، 1991.
Gv بوخمان ، دی راینر و CH وست: برخی یادداشت ها در مورد تاریخچه مهندسی پروتکل ، مجله شبکه های کامپیوتری ، 54 (2010) ، صفحات 3197-3209.

منابع

↑ ^۱٫۰ ^۱٫۱ Bochmann, G.v. "Finite State Description of Communication Protocols, Computer Networks, Vol. 2 (1978), pp. 361-372". {{cite journal}}: Cite journal requires |journal= (help)
↑ K.A. Bartlett, R.A. Scantlebury and P.T. Wilkinson, A note on reliable full-duplex transmission over half- duplex links, C.ACM 12, 260 (1969).
↑ Note: In the case of protocol analysis, there are normally only two entities.
↑ Note: The corruption or loss of a message is modeled as a state transition of the $medium$ .
↑ M.G.Gouda, E.G.Manning, Y.T.Yu: On the progress of communication between two finite state machines, doi
↑ P. Zafiropulo, C. West, H. Rudin, D. Cowan, D. Brand : Towards analyzing and synthesizing protocols, IEEE Transactions on Communications ( Volume: 28, Issue: 4, Apr 1980 )
↑ Note: The SAVE construct of SDL can be used to indicate that certain types of messages should not be consumed in the current state, but saved for future processing.
↑ M.F. Al-hammouri and G.v. Bochmann : Realizability of service specifications, Proc. System Analysis and Modelling (SAM) conference 2018, Copenhagen, LNCS, Springer
↑ C. Fournet, T. Hoare, S. K. Rajamani, and J. Rehof : Stuck-free Conformance, Proc. 16th Intl. Conf. on Computer Aided Verification (CAV’04), LNCS, vol. 3114, Springer, 2004

[Boch78-1] ۱٫۰ ^۱٫۱ Bochmann, G.v. "Finite State Description of Communication Protocols, Computer Networks, Vol. 2 (1978), pp. 361-372". {{cite journal}}: Cite journal requires |journal= (help)

[2] K.A. Bartlett, R.A. Scantlebury and P.T. Wilkinson, A note on reliable full-duplex transmission over half- duplex links, C.ACM 12, 260 (1969).

[3] Note: In the case of protocol analysis, there are normally only two entities.

[4] Note: The corruption or loss of a message is modeled as a state transition of the $medium$ .

[5] M.G.Gouda, E.G.Manning, Y.T.Yu: On the progress of communication between two finite state machines, doi

[6] P. Zafiropulo, C. West, H. Rudin, D. Cowan, D. Brand : Towards analyzing and synthesizing protocols, IEEE Transactions on Communications ( Volume: 28, Issue: 4, Apr 1980 )

[7] Note: The SAVE construct of SDL can be used to indicate that certain types of messages should not be consumed in the current state, but saved for future processing.

[8] M.F. Al-hammouri and G.v. Bochmann : Realizability of service specifications, Proc. System Analysis and Modelling (SAM) conference 2018, Copenhagen, LNCS, Springer

[9] C. Fournet, T. Hoare, S. K. Rajamani, and J. Rehof : Stuck-free Conformance, Proc. 16th Intl. Conf. on Computer Aided Verification (CAV’04), LNCS, vol. 3114, Springer, 2004

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]