Верификация коммуникационных структур гиперкуба параметрическими сетями Петри

Побудовано модель комунікаційної структури гіперкуба довільного розміру з довільною кількістю вимірювань в формі параметричної сіті Петрі. Розроблено методику обчислення лінійних інваріантів параметричних сітей Петрі, яка дозволяє проаналізувати процеси передачі інформації в гіперкубі. Вивчено струк...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2010
Автори:	Зайцев, Д.А., Шмелёва, Т.Р.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2010
Назва видання:	Кибернетика и системный анализ
Теми:	Системный анализ
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/45132
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Верификация коммуникационных структур гиперкуба параметрическими сетями Петри / Д.А. Зайцев, Т.Р. Шмелёва // Кибернетика и системный анализ. — 2010. — № 1. — С. 119–128. — Бібліогр.: 9 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-45132
record_format	dspace
spelling	irk-123456789-451322013-06-08T03:23:56Z Верификация коммуникационных структур гиперкуба параметрическими сетями Петри Зайцев, Д.А. Шмелёва, Т.Р. Системный анализ Побудовано модель комунікаційної структури гіперкуба довільного розміру з довільною кількістю вимірювань в формі параметричної сіті Петрі. Розроблено методику обчислення лінійних інваріантів параметричних сітей Петрі, яка дозволяє проаналізувати процеси передачі інформації в гіперкубі. Вивчено структуру складних тупиків, зумовлених ланцюгом (циклом) блокувань та ізоляцією пристроїв. В реальних мережах подані тупики приводять до суттєвого зниження продуктивності і можуть бути викликані зловмисним трафіком. A model of a hypercube communication structure of arbitrary size with an arbitrary number of dimensions is constructed in the form of a parametric Petri net. A technique for the calculation of linear invariants for parametric Petri nets is developed that allows for the analysis of information transmission processes in such a hypercube. The structure of complicated deadlocks caused by both a chain (cycle) of blockings and device isolation is studied. In real-life networks, the mentioned deadlocks lead to a considerable decrease in performance and can be inflicted by an ill-intentioned traffic. 2010 Article Верификация коммуникационных структур гиперкуба параметрическими сетями Петри / Д.А. Зайцев, Т.Р. Шмелёва // Кибернетика и системный анализ. — 2010. — № 1. — С. 119–128. — Бібліогр.: 9 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/45132 621.39, 004.7 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Системный анализ Системный анализ
spellingShingle	Системный анализ Системный анализ Зайцев, Д.А. Шмелёва, Т.Р. Верификация коммуникационных структур гиперкуба параметрическими сетями Петри Кибернетика и системный анализ
description	Побудовано модель комунікаційної структури гіперкуба довільного розміру з довільною кількістю вимірювань в формі параметричної сіті Петрі. Розроблено методику обчислення лінійних інваріантів параметричних сітей Петрі, яка дозволяє проаналізувати процеси передачі інформації в гіперкубі. Вивчено структуру складних тупиків, зумовлених ланцюгом (циклом) блокувань та ізоляцією пристроїв. В реальних мережах подані тупики приводять до суттєвого зниження продуктивності і можуть бути викликані зловмисним трафіком.
format	Article
author	Зайцев, Д.А. Шмелёва, Т.Р.
author_facet	Зайцев, Д.А. Шмелёва, Т.Р.
author_sort	Зайцев, Д.А.
title	Верификация коммуникационных структур гиперкуба параметрическими сетями Петри
title_short	Верификация коммуникационных структур гиперкуба параметрическими сетями Петри
title_full	Верификация коммуникационных структур гиперкуба параметрическими сетями Петри
title_fullStr	Верификация коммуникационных структур гиперкуба параметрическими сетями Петри
title_full_unstemmed	Верификация коммуникационных структур гиперкуба параметрическими сетями Петри
title_sort	верификация коммуникационных структур гиперкуба параметрическими сетями петри
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2010
topic_facet	Системный анализ
url	http://dspace.nbuv.gov.ua/handle/123456789/45132
citation_txt	Верификация коммуникационных структур гиперкуба параметрическими сетями Петри / Д.А. Зайцев, Т.Р. Шмелёва // Кибернетика и системный анализ. — 2010. — № 1. — С. 119–128. — Бібліогр.: 9 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT zajcevda verifikaciâkommunikacionnyhstrukturgiperkubaparametričeskimisetâmipetri AT šmelëvatr verifikaciâkommunikacionnyhstrukturgiperkubaparametričeskimisetâmipetri
first_indexed	2025-07-04T03:45:46Z
last_indexed	2025-07-04T03:45:46Z
_version_	1836686504452161536
fulltext	ÓÄÊ 621.39, 004.7 Ä.À. ÇÀÉÖÅÂ, Ò.Ð. ØÌÅË¨ÂÀ ÂÅÐÈÔÈÊÀÖÈß ÊÎÌÌÓÍÈÊÀÖÈÎÍÍÛÕ ÑÒÐÓÊÒÓÐ ÃÈÏÅÐÊÓÁÀ ÏÀÐÀÌÅÒÐÈ×ÅÑÊÈÌÈ ÑÅÒßÌÈ ÏÅÒÐÈ1 Êëþ÷åâûå ñëîâà: êîììóíèêàöèîííàÿ ñòðóêòóðà, ãèïåðêóá, ìàðøðóòèçàòîð, ïà- ðàìåòðè÷åñêàÿ ñåòü Ïåòðè, ëèíåéíûé èíâàðèàíò, òóïèê . ÂÂÅÄÅÍÈÅ Ïîñêîëüêó ÷èñëî êîììóíèêàöèîííûõ óñòðîéñòâ è òîïîëîãèÿ ñåòè ñóùåñòâåííî âàðüèðóþòñÿ â ðåàëüíûõ òåëåêîììóíèêàöèîííûõ ñåòÿõ, íåîáõîäèìà ìåòîäèêà, ïðèìåíèìàÿ ê ïðîèçâîëüíîìó ÷èñëó óñòðîéñòâ, êîòîðûå îáðàçóþò íåêîòîðóþ ïðîèçâîëüíóþ ñòðóêòóðó. À. Ìàðøàí [1] íà÷àë èçó÷åíèå ñåòåé Ïåòðè, ïîñòðîåííûõ êàê ïîâòîðåíèå áàçî- âîãî êîìïîíåíòà äëÿ îöåíêè ïðîèçâîäèòåëüíîñòè CSMA/CD ñåòåé ñ îáùåé øèíîé. Èì ïîñòðîåíà ëèíåéíàÿ ñòðóêòóðà, íî ìåòîäèêà àíàëèçà äëÿ ïðîèçâîëüíîãî ÷èñëà êîìïîíåíòîâ íå áûëà ïðåäñòàâëåíà. Â [2] ïàðàìåòðè÷åñêàÿ êîìïîçèöèÿ ôóíêöèî- íàëüíûõ ñåòåé Ïåòðè [3] ïðèìåíåíà äëÿ àíàëèçà ëèíåéíûõ ñòðóêòóð âçàèìîäåé- ñòâóþùèõ óñòðîéñòâ. Áîëåå ïðîñòîé ïîäõîä [4] ïðèìåíåí ê äðåâîâèäíûì ñòðóêòó- ðàì äëÿ âåðèôèêàöèè ïðîòîêîëîâ êîììóòèðóåìîé Ethernet. Öåëü íàñòîÿùåé ñòàòüè — îáîáùåíèå ïîäõîäà [4] íà êîììóíèêàöèîííûå ñòðóêòóðû ãèïåðêóáà ïðîèçâîëüíîãî ðàçìåðà ñ ïðîèçâîëüíûì ÷èñëîì èçìåðåíèé. Â [4] ïîñòðîåíà òèïîâàÿ ìîäåëü Ethernet êîììóòàòîðà ñ ïðèíóäèòåëüíîé áóôåðèçà- öèåé êàäðîâ (store-and-forward), êîòîðàÿ èñïîëüçîâàíà äëÿ êîìïîçèöèè äðåâîâèä- íîé ñòðóêòóðû. Ïîñêîëüêó òàáëèöû êîììóòàöèè (ìàðøðóòèçàöèè) íå ïðåä- ñòàâëåíû â ìîäåëè [4], îäíà è òà æå ìîäåëü ìîæåò îïèñûâàòü êàê êîììóòàòîðû, òàê è ìàðøðóòèçàòîðû. Â íàñòîÿùåé ñòàòüå èñïîëüçîâàíà åå ìîäèôèêàöèÿ â êà÷åñòâå îáîáùåííîé ìîäåëè êîììóíèêàöèîííîãî óñòðîéñòâà äëÿ êîìïîçèöèè êîììóíèêà- öèîííîé ñòðóêòóðû ãèïåðêóáà (ÊÑÃÊ). Îòëè÷èå ñîñòàâëÿåò êîëè÷åñòâî ïîðòîâ è ðàçìåùåíèå ïîðòîâ íà ãðàíÿõ ãèïåðêóáà äëÿ ïîñëåäóþùåé êîìïîçèöèè êîììóíèêà- öèîííûõ ñòðóêòóð ãèïåðêóáà. Íàïðàâëåíèåì äàëüíåéøèõ èññëåäîâàíèé ÿâëÿåòñÿ îáîáùåíèå ïîëó÷åííûõ ðåçóëüòàòîâ íà ïðîèçâîëüíûå ñòðóêòóðû è ìîäåëèðîâàíèå óñòðîéñòâ ñ ïðÿìîé ïåðåäà÷åé êàäðîâ ìåæäó ïîðòàìè (cut-through). Îáëàñòüþ ïðè- ëîæåíèÿ ðåçóëüòàòîâ ÿâëÿþòñÿ âû÷èñëåíèÿ íà ðåøåòêàõ. Ïðåäâàðèòåëüíî ðåçóëüòà- òû ïðåäñòàâëåíû íà ñåìèíàðå UKPEW2008 [5]. Äëÿ àíàëèçà ñâîéñòâ ïàðàìåòðè÷åñêèõ ñåòåé Ïåòðè èñïîëüçîâàíû ëèíåéíûå èíâà- ðèàíòû [6]. Â ñîîòâåòñòâèè ñ [7, 8] èäåàëüíàÿ ìîäåëü òåëåêîììóíèêàöèîííîé ñèñòåìû äîëæíà áûòü îãðàíè÷åííîé, æèâîé è êîíñåðâàòèâíîé ñåòüþ Ïåòðè. Îäíàêî t-èíâàðè- àíòû íå ïîçâîëÿþò äîêàçàòü æèâîñòü ñåòè. Ïîýòîìó äëÿ äîêàçàòåëüñòâà òîãî, ÷òî ìî- äåëü íåæèâàÿ èç-çà âîçíèêíîâåíèÿ òóïèêîâ, ââåäåíû ñïåöèàëüíûå ãðàôû. 1. ÌÎÄÅËÜ ÊÎÌÌÓÍÈÊÀÖÈÎÍÍÎÃÎ ÓÑÒÐÎÉÑÒÂÀ Êîììóíèêàöèîííîå óñòðîéñòâî ñåòè ñ êîììóòàöèåé ïàêåòîâ, òàêîå êàê êîììóòà- òîð èëè ìàðøðóòèçàòîð, ñîñòîèò èç êîíå÷íîãî ÷èñëà ïîðòîâ è îñóùåñòâëÿåò ïå- ðåíàïðàâëåíèå ïðèáûâøåãî (÷åðåç íåêîòîðûé ïîðò) ïàêåòà â ïîðò íàçíà÷åíèÿ. Äëÿ âû÷èñëåíèÿ íîìåðà ïîðòà íàçíà÷åíèÿ èñïîëüçóåòñÿ èíôîðìàöèÿ èç çàãîëîâ- êà ïàêåòà è àäðåñíûõ òàáëèö ìàðøðóòèçàöèè (êîììóòàöèè). Óñòðîéñòâî ðåàëèçó- åò ïðèíóäèòåëüíóþ áóôåðèçàöèþ ïàêåòîâ â ñâîåì âíóòðåííåì áóôåðå ëèáî ïðÿ- ìóþ ïåðåäà÷ó ïàêåòîâ ìåæäó ïîðòàìè. Äàæå óñòðîéñòâà ñ ïðÿìîé ïåðåäà÷åé èñ- ïîëüçóþò áóôåðèçàöèþ, êîãäà ïîðò íàçíà÷åíèÿ çàíÿò. Ïîðò ðàáîòàåò â ïîëíîäóïëåêñíîì ðåæèìå, îáåñïå÷èâàÿ äâà êàíàëà: äëÿ ïîëó÷åíèÿ è äëÿ îòïðàâ- êè ïàêåòîâ. Êðîìå òîãî, ïîðòû èìåþò ñâîè ñîáñòâåííûå áóôåðû äëÿ êàæäîãî êà- íàëà, êàê ïðàâèëî, ñ åìêîñòüþ, íåîáõîäèìîé äëÿ õðàíåíèÿ îäíîãî ïàêåòà. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 119 1 Ðàáîòà ïîääåðæàíà ãðàíòîì HATO ICS.NUKR.CLG982698. © Ä.À. Çàéöåâ, Ò.Ð. Øìåë¸âà, 2010 Íàñòîÿùàÿ ñòàòüÿ àáñòðàãèðóåòñÿ îò çàãîëîâêîâ ïàêåòîâ è àäðåñíûõ òàáëèö è ðàññìàòðèâàåò òîëüêî óñòðîéñòâà ñ ïðèíóäèòåëüíîé áóôåðèçàöèåé ïàêåòîâ. Âñå åì- êîñòè íàêîïèòåëåé èçìåðÿþòñÿ êîëè÷åñòâîì ïàêåòîâ. Ðàññìîòðèì ïðîñòðàíñòâî ðàçìåðíîñòè d, ãäå d � 12, ,... Êàæäîå êîììóíèêàöè- îííîå óñòðîéñòâî ïðåäñòàâëåíî ãèïåðêóáîì åäèíè÷íîãî ðàçìåðà â d-ìåðíîì ïðî- ñòðàíñòâå. Êîììóíèêàöèîííàÿ ñòðóêòóðà, îáðàçîâàííàÿ ñîåäèíåííûìè êîììóíèêà- öèîííûìè óñòðîéñòâàìè, ïðåäñòàâëÿåò ñîáîé ãèïåðêóá ðàçìåðà k , ãäå k � 1 2, ,... Ñëåäîâàòåëüíî, îáùåå ÷èñëî óñòðîéñòâ ñîñòàâëÿåò N k d dev � . Êàæäîå óñòðîéñòâî R i i id1 2, � �� èìååò ñâîé èíäåêñ ( , )i i id1 2 � �� , ãäå i ku � 1, , u d� 1, . Ìîäåëü êîììóíè- êàöèîííîé ñòðóêòóðû ãèïåðêóáà îáîçíà÷åíà Hd k, . Äàëåå îïèøåì ìîäåëü óñòðîé- ñòâà â âèäå ñåòè Ïåòðè, à çàòåì êîìïîçèöèþ ìîäåëè êîììóíèêàöèîííîé ñòðóêòóðû ÷åðåç ñîåäèíåíèÿ óñòðîéñòâà ñî ñâîèìè ñîñåäÿìè. Ìîäåëü óñòðîéñòâà ãèïåðêóáà îáîçíà÷èì Hd ,1 (êîëè÷åñòâî èçìåðåíèé ðàâ- íî d , à ðàçìåð ñòðóêòóðû ðàâåí åäèíèöå). Íà êàæäîé ãðàíè óñòðîéñòâà R i i id1 2, � �� â d-ìåðíîì ïðîñòðàíñòâå ðàçìåùåí ïîðò. Ñëåäîâàòåëüíî, êàæäîå óñòðîéñòâî èìååò N dport � �2 ïîðòîâ; äâà ïîðòà äëÿ êàæäîãî èçìåðåíèÿ ðàçìåùåíû íà ïðîòèâîïî- ëîæíûõ ãðàíÿõ ãèïåðêóáà. Äëÿ îáîçíà÷åíèÿ ïðîòèâîïîëîæíûõ ãðàíåé èçìåðåíèÿ j ( j d� 1, ) èñïîëüçîâàí íîìåð íàïðàâëåíèÿ. Íàïðàâëåíèå îáîçíà÷åíî ïåðåìåííîé n ; çíà÷åíèå n � 1èñïîëüçîâàíî äëÿ íàïðàâëåíèÿ ê íóëþ ïî ñîîòâåòñòâóþùåìó èçìåðå- íèþ, à çíà÷åíèå n � 2 èñïîëüçîâàíî äëÿ ïðîòèâîïîëîæíîãî íàïðàâëåíèÿ ê áåñêîíå÷- íîñòè. Ñëåäîâàòåëüíî, ïîðòû ìîãóò áûòü îáîçíà÷åíû ñ ïîìîùüþ ñëåäóþùèõ èí- äåêñîâ port j n i i id , ,1 2� �� , ãäå i ku � 1, , u d� 1, , j d� 1, , n � 1 2, . Êàæäûé ïîðò ïðåäñòàâ- ëåí äâóìÿ êàíàëàìè (âõîäíîé, âûõîäíîé), êàæäûé êàíàë ïðåäñòàâëåí ïàðîé ïîçèöèé: îäíà — äëÿ áóôåðà ïàêåòîâ, äðóãàÿ — äëÿ åìêîñòè áóôåðà. Ñëåäîâàòåëü- íî, êàæäûé ïîðò óñòðîéñòâà R i i id1 2, � �� ïðåäñòàâëåí ÷åòûðüìÿ ñëåäóþùèìè êîí- òàêòíûìè ïîçèöèÿìè: pi j n i i id , ,1 2� �� — âõîäíîé áóôåð ïàêåòîâ; pil j n i i id , ,1 2� �� — åìêîñòü âõîäíîãî áóôåðà (ðàâíà åäèíèöå); po j n i i id , ,1 2� �� — âûõîäíîé áóôåð ïàêåòîâ; pol j n i i id , ,1 2� �� — åìêîñòü âûõîäíîãî áóôåðà (ðàâíà åäèíèöå). Âíóòðåííÿÿ ÷àñòü óñòðîéñòâà ñîäåðæèò N port � 1ñëåäóþùèõ ïîçèöèé. Ïàêåòû, ïåðåíàïðàâëåííûå â ïîðò port j n i i id � � � � , ,1 2 � , õðàíÿòñÿ â ñîîòâåòñòâóþùåé ïîçèöèè pb j n i i id � � � � , ,1 2 � , è îäíà ïîçèöèÿ pbl i i id1 2, � �� ñîäåðæèò åìêîñòü âíóòðåííåãî áóôåðà, ãäå j d� � 1, , n� � 1 2, . Çàìåòèì, ÷òî âíóòðåííèé áóôåð ïðåäñòàâëåí ìíîæåñòâîì ïîçèöèé pb j n i i id � � � � , ,1 2 � (îäíà ïîçèöèÿ äëÿ êàæäîãî ïîðòà) äëÿ ðàçëè÷èÿ íîìåðà ïîðòà íàçíà÷å- íèÿ, êîòîðûé çàäàåòñÿ j n� �, . Ïåðåõîäû ìîäåëè óñòðîéñòâà R i i id1 2, � �� îáåñïå÷èâàþò ïåðåíàïðàâëåíèå âõîä- íûõ ïàêåòîâ èç ïîçèöèè âõîäíîãî áóôåðà ïîðòà pi j n i i id , ,1 2� �� â îäíó èç ïîçèöèé âíóò- ðåííåãî áóôåðà pb j n i i id � � � � , ,1 2 � , j j� � , n n� � , à çàòåì ïåðåäà÷ó ïàêåòîâ èç ïîçèöèè âíóòðåííåãî áóôåðà pb j n i i id � � � � , ,1 2 � â ïîçèöèþ âûõîäíîãî áóôåðà ïîðòà íàçíà÷åíèÿ po j n i i id � � � � , ,1 2 � . Êðîìå òîãî, ñëåäóåò ó÷èòûâàòü åìêîñòè áóôåðîâ: ïðîâåðèòü è óìåíü- øèòü ðàçìåð áóôåðà ïðè çàïèñè ïàêåòà â áóôåð; óâåëè÷èòü ðàçìåð áóôåðà ïðè èç- âëå÷åíèè ïàêåòà èç áóôåðà. Ñëåäîâàòåëüíî, êàæäûé ïîðò port j n i i id , ,1 2� �� óñòðîéñòâà R i i id1 2, � �� ñîäåðæèò N Nport port� � �( )1 1ïåðåõîäîâ, îäèí èç êîòîðûõ ïðåäíàçíà÷åí äëÿ âûõîäíîãî êàíàëà to j n i i id , ,1 2� �� ñ âõîäíûìè äóãàìè èç ïîçèöèé pb j n i i id , ,1 2� �� , 120 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 pol j n i i id , ,1 2� �� è âûõîäíûìè äóãàìè â ïîçèöèè po j n i i id , ,1 2� �� , pbl i i id1 2, � �� ; N port �1 ïå- ðåõîäîâ ti j n j n i i id , , , , � � � �1 2 � , j d� � 1, , n � � 1 2, , j j� � , n n� � , ïðåäíàçíà÷åíû äëÿ âõîäíîãî êàíàëà ñ âõîäíûìè äóãàìè èç ïîçèöèé pi j n i i id , ,1 2� �� , pbl i i id1 2, � �� è âûõîäíûìè äóãà- ìè â ïîçèöèè pb j n i i id � � � � , ,1 2 � , pil j n i i id , ,1 2� �� . Ôîðìàëüíîå ïàðàìåòðè÷åñêîå îïèñàíèå ìîäåëè Hd ,1 ñëåäóþùåå: ( : , , ), , , , , , , , ,ti pi pbl pb pil j d n j n j n j n j n j n� � � � � � � �1 1, , , ; ( : , , ), , , , 2 j j n n to pb pol po pblj n j n j n j n � � � � � � � � � � � � � � � � � � � � � � � � � � , , , ,j d n1 1 2 . (1) ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 121 Ðèñ. 1. Ïðèìåðû ïàðàìåòðè÷åñêèõ ìîäåëåé H a2 1, ( ) è H á3 1, ( ) a b Åñëè Hd ,1 ðàññìàòðèâàåòñÿ êàê ìîäåëü óñòðîéñòâà R i i id1 2, � �� â ñòðóêòóðå ãè- ïåðêóáà, òî ñëåäóåò äîáàâèòü èíäåêñû ñîîòâåòñòâóþùåé ÿ÷åéêè ãèïåðêóáà: ( : , , , , , ,..., , , ,..., , ti pi pbl j n j n i i i j n i i i i id d � � 1 2 1 2 1 2 1 2 1 2,..., , , ,..., , , ,..., , ), i j n i i i j n i i id d dpi pil j � � � � � � � � � �1 1 2 1 2 1 , , , , , ; ( : , , ,..., , , d n j j n n to pb j n i i i j n id i i j n i i i j n i i id d dpol po pbl2 1 2 1 2,..., , , ,..., , , ,..., , , i i id j d n 1 2 1 1 2 , ,..., ) , , , , � � � � � � � � � � � � � � � � � � � � � � � � � � . Îáîçíà÷èì ïåðåõîäû â âèäå t px px py pyu v: , , , ,1 1� � , øèðîêî èñïîëüçóåìîì äëÿ ñåòåé Ïåòðè, íàïðèìåð â ñèñòåìå Tina [9]. Ýòî îçíà- ÷àåò, ÷òî ïåðåõîä t èìååò âõîäÿùèå äóãè èç ïîçèöèé px pxu1 ,... , è èñõîäÿùèå äóãè â ïîçèöèè py pyv1 ,... , , ãäå u v, — ÷èñëî âõîäíûõ è âûõîäíûõ ïîçèöèé ñî- îòâåòñòâåííî. Â ñëó÷àå íåîáõîäèìîñòè ìîãóò áûòü äîáàâëåíû êðàòíîñòè äóã ñ èñïîëüçîâàíèåì îáîçíà÷åíèé âèäà p li � , ãäå l — êðàòíîñòü ñîîòâåòñòâóþùèõ äóã, ñîåäèíÿþùèõ pi è t . Ìîäåëü, ïðåäñòàâëåííàÿ ôîðìóëîé (1), íàçâàíà ïàðàìåòðè÷åñêîé ñåòüþ Ïåòðè, ïîñêîëüêó åå îïèñàíèå ñîäåðæèò ïàðàìåòð d äëÿ âû÷èñëåíèÿ èíäåêñîâ ýëåìåíòîâ. ×èñëî èçìåðåíèé ìîäåëè Hd ,1 íåîãðàíè÷åíî è ïðåäñòàâëåíî ïàðàìåòðîì d . Ïàðàìåòðè÷åñêàÿ ìîäåëü Hd ,1 ïðîèëëþñòðèðîâàíà ïðèìåðàìè, ïðåäñòàâëåí- íûìè íà ðèñ. 1, äëÿ êîíêðåòíûõ ÷èñåë èçìåðåíèé d � 2 3, . Ïðåäñòàâèòü âèçóàëèçà- öèþ ìîäåëè äëÿ áîëüøåãî ÷èñëà èçìåðåíèé äîñòàòî÷íî ñëîæíî. 2. p-ÈÍÂÀÐÈÀÍÒÛ ÌÎÄÅËÈ ÊÎÌÌÓÍÈÊÀÖÈÎÍÍÎÃÎ ÓÑÒÐÎÉÑÒÂÀ Èñïîëüçóÿ ïàðàìåòðè÷åñêîå îïèñàíèå (1) ìîäåëè êîììóíèêàöèîííîãî óñòðîéñòâà Hd ,1 , ïîëó÷åííîå â ðàçä. 1, áûëà ïîñòðîåíà ñëåäóþùàÿ ñèñòåìà äëÿ âû÷èñëåíèÿ p-èíâàðèàíòîâ: to xpb xpol xpo xpbl ti xpi j n j n j n j n j n j n j , , , , , , , , : , : � � � � � n j n j nxpbl xpb xpil j d n j d n � � � � � � � � � � �, , , , , , , , , , ,1 1 2 1 1 2 j j n n� � � � � � � � � , . (2) Çàìåòèì, ÷òî ýòà ñèñòåìà èìååò ïàðàìåòðè÷åñêóþ ôîðìó. Åå ïàðàìåòðîì ÿâëÿåò- ñÿ ÷èñëî èçìåðåíèé d . Ñèñòåìà ïîñòðîåíà íåïîñðåäñòâåííî ïî îïèñàíèþ (1) ñ èñïîëüçîâàíèåì ïðàâèëà [6], ñîãëàñíî êîòîðîìó êàæäîå óðàâíåíèå ñîîòâåòñòâóåò ïåðåõîäó è ñîäåðæèò ðàâíûå ñóììû äëÿ åãî âõîäÿùèõ è èñõîäÿùèõ äóã. Ñóììû äîëæíû áûòü âû÷èñëåíû ñ èñïîëüçîâàíèåì êðàòíîñòåé äóã, íî âñå äóãè (1) èìå- þò êðàòíîñòü, ðàâíóþ åäèíèöå. Îáùåå ÷èñëî óðàâíåíèé ñèñòåìû (2) ñîñòàâëÿåò N d d t ,1 24� � è îáùåå ÷èñëî ïåðåìåííûõ ñèñòåìû (2) ñîñòàâëÿåò N d d p ,1 10 1� � � . Äëÿ èçó÷åíèÿ p-èíâàðèàíòîâ ìîäåëè äëÿ ïðîèçâîëüíîãî ÷èñëà èçìåðåíèé ñèñ- òåìà (2) äîëæíà áûòü ðåøåíà â ïàðàìåòðè÷åñêîé ôîðìå. Ïîëó÷åííîå ïàðàìåòðè÷åñ- êîå ðåøåíèå ñèñòåìû (2) èìååò âèä ( , ), , , , ; ( , ), , , , , , , pi pil j d n po pol j d n j n j n j n j n � � � � 1 1 2 1 1 2 1 1 2 , ; ( , ( , , , , )); (( , , ) , , , , pbl pb j d n pb pi po j n j n j n j n � � , , , , ); ( , (( , ), , , , )), , j d n pbl pil pol j d nj n j n � � � � 1 1 2 1 1 2� � � � � � � � � � � � � � � � � � . (3) 122 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 Ñïîñîá ïðåäñòàâëåíèÿ ðåøåíèé ÿâëÿåòñÿ äîñòàòî÷íî ðàñïðîñòðàíåííûì äëÿ ðàçðåæåííûõ âåêòîðîâ, îñîáåííî â òåîðèè ñåòåé Ïåòðè. Â (3) óêàçàíû òîëüêî íåíó- ëåâûå êîìïîíåíòû ïîñðåäñòâîì èìåí ñîîòâåòñòâóþùèõ ïîçèöèé. Íåíóëåâîé ìíî- æèòåëü åäèíèöà îïóùåí. Â ñëó÷àå, åñëè ìíîæèòåëü íå ðàâåí åäèíèöå, èñïîëüçóåòñÿ îáîçíà÷åíèå âèäà p x� , ãäå x — çíà÷åíèå èíâàðèàíòà ïîçèöèè p . Òàêèå îáîçíà÷å- íèÿ ïðèíÿòû â ñèñòåìå Tina [9], êîòîðàÿ èñïîëüçîâàíà äëÿ ïîëó÷åíèÿ èçîáðàæåíèé ñåòåé Ïåòðè â íàñòîÿùåé ñòàòüå. Ñòðîêà ìàòðèöû (3) çàäàåò ìíîæåñòâî ñòðîê â ñî- îòâåòñòâèè ñî çíà÷åíèÿìè èñïîëüçîâàííûõ èíäåêñîâ j, n, çà èñêëþ÷åíèåì ïîñëåä- íèõ òðåõ ñòðîê, êîòîðûå ñîäåðæàò ïåðåìåííîå ÷èñëî êîìïîíåíòîâ, çàäàííûõ èíäåêñàìè. Äëÿ ïîñòðîåíèÿ ìàòðèöû (3) ïðèìåíÿåòñÿ ýâðèñòè÷åñêèé àëãîðèòì, íî äàëåå ïðåäñòàâëåíî äîêàçàòåëüñòâî òîãî, ÷òî (3) ÿâëÿåòñÿ ðåøåíèåì (1). Òîò ôàêò, ÷òî (3) ÿâëÿåòñÿ áàçèñíûì ðåøåíèåì, íå òðåáóåòñÿ äëÿ âûâîäà îòíîñèòåëüíî p-èíâàðèàíò- íîñòè Hd ,1 . Îáùåå ÷èñëî ðåøåíèé (ñòðîê) â ìàòðèöå (3) ðàâíî N d d pinv ,1 4 3� � . Ëåììà 1. Êàæäàÿ ñòðîêà ìàòðèöû (3) ÿâëÿåòñÿ ðåøåíèåì ñèñòåìû (2). Äîêàçàòåëüñòâî. Ïîäñòàâèì êàæäóþ ïàðàìåòðè÷åñêóþ ñòðîêó ìàòðèöû (3) â êàæäîå ïàðàìåòðè÷åñêîå óðàâíåíèå ñèñòåìû (2), â ðåçóëüòàòå ïîëó÷èì êîððåêòíûå ðàâåíñòâà. Ïðè ïîäñòàíîâêå âûáðàíû ðàçëè÷íûå èìåíà èíäåêñîâ. Íàïðèìåð, ïîä- ñòàâèì ÷åòâåðòóþ ñòðîêó (3) (( , , ), , ,pb pi pol m l m l m , l d� 1, , m � 1 2, ) âî âòîðîå óðàâíåíèå (2) xpi xpbl xpb xpilj n j n j n, , ,� � �� , j d� 1, , n � 1 2, , j d� � 1, , n � � 1 2, , j j� � , n n� � . Äëÿ êàæäîãî êîíêðåòíîãî óðàâíåíèÿ, çàäàííîãî äîïóñòèìûì êîðòåæåì ( , , , )j n j n� � , ðåøåíèå ñîäåðæèò pi j n, ïðè l j� , m n� è pb j n� �, ïðè l j m n� � � �, (äðóãèå ïåðåìåí- íûå óðàâíåíèÿ xpbl, xpil j n� �, íå óêàçàíû â ðåøåíèè). Ïîëó÷èì 1 0 1 0� � � è äàëåå 1 1� äëÿ êàæäîãî óðàâíåíèÿ. Äâà ïåðâûõ ðåøåíèÿ (3) èìåþò íåçíà÷èòåëüíîå îòëè÷èå: îíè ïðåäñòàâëÿþò ñî- áîé ïîñëåäîâàòåëüíîñòè ñòðîê, çàäàííûõ èõ èíäåêñàìè. Ïîäñòàâèì ïåðâóþ ïàðàìåòðè÷åñêóþ ñòðîêó (3) ( , ), ,pi pill m l m , l d� 1, , m � 1 2, , âî âòîðîå ïàðàìåòðè÷åñêîå óðàâíåíèå (2) xpi xpbl xpb xpil j dj n j n j n, , , , ,� � � �� 1 , n � 1 2, , j d� � 1, , n � � 1 2, , j j� � , n n� � . Òàê, ïðè l j� èëè m n� ïîëó÷èì 0 0 0 0� � � è äàëåå 0 0� , à ïðè l j� è m n� ïîëó÷èì 1 0 0 1� � � è äàëåå 1 1� . Àíàëîãè÷íûì ñïîñîáîì ïðîâåðåíû âñå 5 2� êîìáèíàöèè. Òåîðåìà 1. Ñåòü Hd ,1 ÿâëÿåòñÿ p-èíâàðèàíòíîé ñåòüþ Ïåòðè äëÿ ïðîèçâîëüíî- ãî íàòóðàëüíîãî ÷èñëà d . Äîêàçàòåëüñòâî. Ðàññìîòðèì ñóììó ÷åòâåðòîé (( , , ), , ,pb pi poj n j n j n , j d� 1, , n � 1 2, ) è ïÿòîé ( , (( , ), , , , )), ,pbl pil pol j d nj n j n � �1 1 2 ñòðîê ìàòðèöû (3), êîòîðûå ïðåäñòàâëÿþò ñîáîé ðåøåíèÿ ñèñòåìû (2) â ñîîòâåòñòâèè ñ ëåììîé 1. Ïîëó÷èì ( , (( , , , , ), , , , ,pbl pil pol pb pi poj n j n j n j n j n , j d� 1, , n � 1 2, )) . (4) Ïîñêîëüêó âñå N d d p ,1 10 1� � � ïîçèöèé ïåðå÷èñëåíû â ýòîì èíâàðèàíòå, òî ñåòü Hd ,1 ÿâëÿåòñÿ p-èíâàðèàíòíîé ñåòüþ Ïåòðè äëÿ ëþáîãî íàòóðàëüíîãî ÷èñëà d . Áî- ëåå òîãî, òàê êàê êàæäûé êîìïîíåíò (4) ðàâåí åäèíèöå, òî ñåòü Hd ,1 ÿâëÿåòñÿ êîí- ñåðâàòèâíîé (è îãðàíè÷åííîé) ñåòüþ Ïåòðè äëÿ ëþáîãî íàòóðàëüíîãî ÷èñëà d. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 123 3. ÊÎÌÏÎÇÈÖÈß ÊÑÃÊ Ñîåäèíåíèå êîììóíèêàöèîííûõ óñòðîéñòâ â ãèïåðêóáå âûïîëíåíî ñîâìåùåíèåì (îáúåäèíåíèåì) ñîîòâåòñòâóþùèõ êîíòàêòíûõ ïîçèöèé ñîñåäíèõ óñòðîéñòâ. Ðàññìîòðèì íåêîòîðîå âíóòðåííåå êîììóíèêàöèîííîå óñòðîéñòâî R i i ij d1 , , , ,� � , i ku � �2 1, , u d� 1, , j d� 1, : • ïîçèöèè port j i i ij d , , , , , 1 1 � � ñîâìåùàþòñÿ ñ ïîçèöèÿìè port j i i ij d , , , , , 2 11 � �� óñòðîé- ñòâà R i i ij d1 1, , , ,� �� òàêèì îáðàçîì, ÷òî ïîçèöèÿ po j i i ij d , , , , , 1 1 � � ñîâìåùàåòñÿ ñ pi j i i ij d , , , , , 2 11 � �� , ïîçèöèÿ pol j i i ij d , , , , , 1 1 � � — ñ pil j i i ij d , , , – , , 2 11 � � , ïîçèöèÿ pi j i i ij d , , , , , 1 1 � � — ñ po j i i ij d , ,... 2 11� � �� , ïîçèöèÿ pil j i i ij d , ,... 1 1� �� — ñ pol j i i ij d , ,... 2 11� � �� ; • ïîçèöèè port j i i ij d ,2 1� � � �� ñîâìåùàþòñÿ ñ ïîçèöèÿìè port j i i ij d , ,..., 1 11� � �� óñòðîé- ñòâà R i i ij d1 1,... ,...,� òàêèì îáðàçîì, ÷òî ïîçèöèÿ po j i i ij d , ,... 2 1� �� ñîâìåùàåòñÿ c pi j i i ij d ,1 11� � � � �� , ïîçèöèÿ pol j i i ij d , ,... 2 1� �� — ñ pil j i i ij d , ,... 1 11� � �� , ïîçèöèÿ pi j i i ij d , ,... 2 1� �� — ñ po j i i ij d , ,... 1 11� � �� , ïîçèöèÿ pil j i i ij d , ,... 2 1� �� — ñ pol j i i ij d , ,... 1 11� � �� . Âî èçáåæàíèå äâîéíîãî èìåíîâàíèÿ îáîçíà÷å- íèÿ ïîçèöèé äëÿ ïîðòîâ íàïðàâëåíèÿ ê íóëþ n � 1 ðàññìàòðèâàþòñÿ îòíîñèòåëüíî òåêóùåãî óñòðîé- ñòâà, äëÿ ïîðòîâ íàïðàâëåíèÿ ê áåñêîíå÷íîñòè n � 2 — îòíîñèòåëüíî ñîñåäíèõ óñòðîéñòâ è èõ ïîðòîâ íà- ïðàâëåíèÿ ê íóëþ n � 1. Òàêèì îáðàçîì, èìåíà ñîâ- ìåùåííûõ ïîçèöèé èìåþò òîëüêî èíäåêñû ïîðòîâ íàïðàâëåíèÿ ê íóëþ n � 1. Êðîìå òîãî, äëÿ óïðîùå- íèÿ ïîñëåäóþùèõ îáîçíà÷åíèé ïîçèöèè ñ èíäåêñà- ìè ïîðòîâ íàïðàâëåíèÿ ê áåñêîíå÷íîñòè n � 2 íà ãðà- íÿõ (ãðàíèöàõ) êîììóíèêàöèîííîãî ãèïåðêóáà ïî- èìåíîâàíû îòíîñèòåëüíî íåñóùåñòâóþùèõ óñòðîéñòâ ñ èíäåêñàìè, ðàâíûìè k � 1. Òàêèì îáðà- çîì, èìåíà ïîðòîâ ñ èíäåêñàìè íàïðàâëåíèÿ ê áåñêî- íå÷íîñòè n � 2 îòñóòñòâóþò â ãèïåðêóáå. Îïèñàííàÿ âûøå êîììóíèêàöèîííàÿ ñòðóêòóðà ãèïåðêóáà îáîçíà÷åíà êàê Hd k, . Ïðèìåð êîìïîçèöèè Hd k, äëÿ d � 3, k � 4 ïðåäñòàâëåí íà ðèñ. 2. Ôîðìàëüíîå îïèñàíèå êîìïîçèöèè Hd k, ïðåäñòàâëåíî â ñëåäóþùåì âèäå: pi po pi j i i i j i i i j ij d j d , ,... , ,... , : 1 1 2 1 1 1 1� � � � � � � � � � �� i i j i i i j i i j d j d jpil pol 1 1 1 2 1 1 ,... , ,... , ,.. : � � . , ,... , ,... : i j i i i j i i i j d j d j d pil po pi � � � � � � � � 1 1 1 1 1 1 � � , ,... , ,... , 2 1 1 1 1 1 1 i i i j i i i j i i j d j d j po pol � � � � � � � � � � � � 1 2 1 11 1,... , ,... , ,... : i j i i i j i i id j d j dpil pol� � � � � � �� , , , , , ,i k u d j du 1 1 1 1 � � � � � � � � � � , pi po pil j i i i j i i i j i j d j d , ,... , ,... , : 1 1 2 1 1 1 1 � � � � � � � � � �� i i j i i i j i i j d j d j pol po 1 2 1 1 1 1 ,... , ,... , ,... : � � i j i i i j i i i j d j d j d pi pol pil : : , ,... , ,... , � � � � � � � 2 1 1 1 1 � � 2 1 1 1 1 i i i u j d i k u d � � � � � � � � � � � � � � � � � � � � � � � � ,... , , , , , j d u j i kj� � � � � � � � � � � � � � � � � � � � � 1, , , . 124 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 Ðèñ. 2. Ñõåìà êîììóíèêàöèîííîé ñòðóêòóðû ãèïåðêóáà H 3 4, X 3 X 2 X 1 R 3 2 1, , Çíàê îáúåäèíåíèÿ � îáîçíà÷àåò ñîâìåùåíèå ïîçèöèé; ëåâûé ñòîëáåö çàäàåò íî- âûå èìåíà ïîçèöèé. 4. p-ÈÍÂÀÐÈÀÍÒÛ ÊÑÃÊ Íà îñíîâå àáñòðàêòíîãî îïèñàíèÿ ìîäåëè êîììóíèêàöèîííîãî ãèïåðêóáà Hd k, , ïîëó÷åííîãî â ðàçä. 3, ïîñòðîåíà ñëåäóþùàÿ ñèñòåìà äëÿ âû÷èñëåíèÿ p-èíâàðè- àíòîâ: to xpb xpol xpo j i i j i i j i i j id d d , , , , , , , , , , : 1 1 1 1 1 1 1 1� � �� , , , , , , , , , , , , , : � � � � i i i j j n i i j i i d d d d xpbl ti xpi � � � 1 1 1 1 1 � � � � � xpbl xpb xpil to i i j n i i j i i j d d d1 1 1 1 5 , , , , , , , , , ( ) � � � , , , ,..., , , , ,..., , , , : 2 2 1 1 1 1i i i j i i i j ij d j dxpb xpil � � � � i i j i i i i ij d j d jxpi xpbl � � � � 1 1 11 1,..., , , , ,..., , , ,...� � , , , , , , ,..., , , , ,..., , : i j j n i i i j i i d j d jti xpo 2 1 11 1 � � �� i i i i j n i i i j d j d j dxpbl xpb xpol� � � � � 1 1, , ,..., , , , ,...,� � , , , ,..., , , , , , , , , , 1 11 1 1 1 2 i i ij d j d j d n j j n n i � � � � � � � � � � � u k u d� � � � � � � �� 1 1, , , . Îáùåå ÷èñëî óðàâíåíèé ñèñòåìû (5) ðàâíî N d k d k t d , � � �4 2 . Îáùåå ÷èñëî ïå- ðåìåííûõ ñèñòåìû (5) ðàâíî N d k d k d k p d d , ( )� � � � � � � �6 1 4 1 . Ïîëó÷åííîå ïàðàìåòðè÷åñêîå ðåøåíèå èìååò ñëåäóþùèé âèä: ( , ) , , , ( , , pi pil j d i j i i i j i i i u j d j d 1 1 1 1 1 1 � � � � � � � � � � � � � � , , , , ), , ; ( , , , k u d u j i k po pol j j i i i j ij d � � � � � � � � 1 1 1 1 1 1 1� � ,... ) , , , ( , , , , ), , ; ( i i u j j d j d i k u d u j i k pb � � � � � � � � � 1 1 1 1 1 l pb j d n i k u d i i j n i i u d d1 1 1 1 2 1 1 , , , ( , , , , )), , , , ; � �� (( , , , , , , , , ), (( , , pb n j d i k u d pi j n i i u j id1 112 1 1 1 1 � � � � � �� i j i i u j i d dpo j d i k u d pi , ), , , , , , ), (( , , 1 1 1 1 1 1 1 � � � �� i i j i i i u j d j dpo j d i k u d u, ), , , , , , , ,1 1 1 1 1 j i k pbl pil pol j i i j i i j id d , )) (( , (( , , , � � � � � � � � 1 1 1 1 1 1 � � � i u j i i i j d j d j d i k u d pil pol ), , ), , , , ), (( , , � � � � � � � 1 1 1 1 1 � � , ), , , , , , , , )) 1 1 1 1 1 1 i i i u j j d j d i k u d u j i k � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � . (6) Îáùåå ÷èñëî ðåøåíèé ñîñòàâëÿåò N d k d kd k d d , ( )� � � � � � � ��1 2 2 21 . Ëåììà 2. Êàæäàÿ ñòðîêà ìàòðèöû (6) ÿâëÿåòñÿ ðåøåíèåì ñèñòåìû (5). Òåîðåìà 3. Ñåòü Hd k, ÿâëÿåòñÿ p-èíâàðèàíòíîé ñåòüþ Ïåòðè äëÿ ëþáûõ íàòó- ðàëüíûõ d, k . Äîêàçàòåëüñòâà ëåììû 2 è òåîðåìû 3 ïîëó÷åíû òàêèì æå ñïîñîáîì, êàê è äëÿ ñåòè Hd ,1 (ðàçä. 2). 5. ÌÎÄÅËÈ ÒÅÐÌÈÍÀËÜÍÛÕ ÓÑÒÐÎÉÑÒÂ Ïðèñîåäèíåííûå îäèí ê äðóãîìó êîììóíèêàöèîííûå óñòðîéñòâà îáðàçóþò êîììó- íèêàöèîííóþ ñòðóêòóðó, ñîçäàííóþ ëèøü â öåëÿõ ïåðåäà÷è ïàêåòîâ ìåæäó òåðìè- íàëüíûìè óñòðîéñòâàìè: ðàáî÷èìè ñòàíöèÿìè è ñåðâåðàìè. Â íàñòîÿùåé ñòàòüå òåõíîëîãèÿ âçàèìîäåéñòâèÿ êëèåíò–ñåðâåð íå èçó÷àåòñÿ, ïîýòîìó òèïû òåðìèíàëü- íûõ óñòðîéñòâ íå ðàçëè÷àþòñÿ. Àáñòðàêòíîå òåðìèíàëüíîå óñòðîéñòâî îáåñïå- ÷èâàåò ïî êðàéíåé ìåðå äâå îñíîâíûå ôóíêöèè: îòïðàâèòü ïàêåò è ïîëó÷èòü ïà- êåò. Óêàçàííûå ôóíêöèè ðåàëèçîâàíû â ìîäåëè, ïðåäñòàâëåííîé íà ðèñ. 3 (âûáðà- íî ïÿòü ñîîáùåíèé, íàõîäÿùèõñÿ â áóôåðå). Ìîäåëü ñîäåðæèò âíóòðåííèé áóôåð ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 125 ïàêåòîâ qb ; ïåðåõîä si ìîäåëèðóåò ïî- ëó÷åíèå ïàêåòîâ, à ïåðåõîä so ìîäåëè- ðóåò îòïðàâêó ïàêåòîâ. Ìîäåëü ñîõðàíÿ- åò áàëàíñ êîëè÷åñòâà ïîëó÷åííûõ è îò- ïðàâëåííûõ ïàêåòîâ; îãðàíè÷åíèå ðàçìåðîâ áóôåðà qb íå ðàññìàòðèâàåòñÿ. Òåðìèíàëüíûå óñòðîéñòâà, ïðåäñòàâëåííûå íà ðèñ. 3, ïðèñîåäèíåíû ê ãðàíè÷íûì ïî- ðòàì ñòðóêòóðû ãèïåðêóáà; ñîîòâåòñòâóþ- ùàÿ ìîäåëü îáîçíà÷åíà êàê HTd k, . Òåð- ìèíàëüíîå óñòðîéñòâî â ñòðóêòóðå ãèïåðêóáà îáîçíà÷åíî êàê A i i ij d1 ,... � �� , ãäå i ku � 1, , u d� 1, , j d� 1, , u j� , i j �{1, k}, è ïðèñîåäèíåíî ê êîììóíèêàöèîííîìó óñòðîéñòâó R i i ij d1 ,... � �� . Ôîðìàëüíîå îïèñàíèå êîìïîçèöèè HTd k, íà îñíîâå Hd k, , A i i ij d1 ,... � �� ïðåäñòàâëåíî â ñëåäóþùåì âèäå: pi qo pi j i i i i i i j i ij d j d j , ,... ,... , ,. : 1 1 1 1 1� � � � � � � � � � � .. , ,... ,... , : i j i i i i i i j i d j d j dpil qol pil 1 1 1 1 1� � � � � � � � � � � � � � � � � � � i i j i i i i i i j j d j d j dpo qi po ,... , ,... ,... : 1 1 1 , ,... , ,... ,... : 1 1 1 1 1 i i i j i i i i i j d j d jpol qil � � � � � � � � � � i j i i i u d j dpol i k � � � � � � � � � � � � � � � � � � � � � � , ,... , , , 1 1 1 � u d j d u j i j� � � � � � � � � � � � � � � � � � � � � � 1 1 1, , , , , , pi qi pi j i i i i i i j i ij d j d j , ,... ,... , : 1 1 1 1 1 1� � � � � � � � � � � � � � � � � � � � 1 1 11 1 ,... , ,... ,... : i j i i i i i i d j d j dpil qil pi � � l po qo j i i i j i i i i i j d j d j , ,... , ,... : 1 1 1 1 1 1 1 � � � � � � � � � � � � ,... , ,... , ,... : i j i i i j i i i d j d j d po pol � � � � � � � � 1 1 1 1 1 1 � � qol pol i i i j i i ij d j d1 1 1 1� � � � � � � � � � � � � � � � � �,... , ,... � � � � � � � � � � � � � � � � � � � � � � � � � , , , , , , , ,i k u d j d u j i ku j1 1 1 � � � � � � � � � � . Êàê è â ðàçä. 4, äîêàçàíî, ÷òî HTd k, ÿâëÿåòñÿ p-èíâàðèàíòíîé ñåòüþ Ïåòðè äëÿ ëþáûõ íàòóðàëüíûõ ÷èñåë d, k . 6. t-ÈÍÂÀÐÈÀÍÒÛ È ÒÓÏÈÊÈ ÊÑÃÊ Äëÿ âû÷èñëåíèÿ t-èíâàðèàíòîâ ïðèìåíåí ïîäõîä, àíàëîãè÷íûé èñïîëüçîâàííîìó äëÿ âû÷èñëåíèÿ p-èíâàðèàíòîâ. Åäèíñòâåííûì îòëè÷èåì ÿâëÿåòñÿ òî, ÷òî äëÿ t-èíâàðèàíòîâ êàæäîå óðàâíåíèå ñîîòâåòñòâóåò ïîçèöèè, à ïåðåìåííûå ñîîòâåò- ñòâóþò ïåðåõîäàì. Óñòàíîâëåíî, ÷òî ñåòü Ïåòðè Hd k, íå ÿâëÿåòñÿ t-èíâàðèàíò- íîé, íî ýòî äîñòàòî÷íî òðèâèàëüíûé ôàêò, òàê êàê ìîäåëèðóåìàÿ ñèñòåìà ÿâëÿ- åòñÿ îòêðûòîé, ïîñêîëüêó íå ïðèñîåäèíåíû òåðìèíàëüíûå óñòðîéñòâà. Äîêàçàíî, ÷òî ìîäåëü çàêðûòîé ñèñòåìû ñ ïðèñîåäèíåííûìè òåðìèíàëüíûìè óñòðîéñòâàìè HTd k, ÿâëÿåòñÿ t-èíâàðèàíòíîé ñåòüþ Ïåòðè äëÿ ïðîèçâîëüíûõ íàòóðàëüíûõ ÷è- ñåë d, k . Îäíàêî t-èíâàðèàíòíîñòü ìîäåëè íå ïîäðàçóìåâàåò åå æèâîñòü. Êàæäàÿ ïàðà ñîñåäíèõ êîììóíèêàöèîííûõ óñòðîéñòâ ìîæåò ïîïàñòü â ëîêàëüíûé òóïèê, íàïðèìåð, êîãäà óñòðîéñòâî R i i ij d1� � � �� ñîäåðæèò l ïàêåòîâ, ïåðåíàïðàâëåííûõ â óñòðîéñòâî R i i ij d1 1� � �� ,..., , à óñòðîéñòâî R i i ij d1 1� � �� ,..., ñîäåðæèò l ïàêåòîâ, ïåðåíàï- ðàâëåííûõ â óñòðîéñòâî R i i ij d1� �� ,..., , è, êðîìå òîãî, âõîäíîé è âûõîäíîé áóôåðû èõ îá- ùåãî ïîðòà çàíÿòû ïàêåòàìè, ãäå l — îãðàíè÷åíèå ðàçìåðà âíóòðåííåãî áóôåðà (ìàðêè- ðîâêà ïîçèöèé pbl i i ij d1� � � �� , pbl i i ij d1 1� � �� ,..., ). Èçëîæåííàÿ ñèòóàöèÿ ïðåäñòàâëÿåò ñî- áîé t-òóïèêîâóþ ìàðêèðîâêó äëÿ ïåðåõîäîâ äâóõ óñòðîéñòâ, â òî âðåìÿ êàê äðóãèå ïåðåõîäû ñåòè HTd k, ÿâëÿþòñÿ ïîòåíöèàëüíî æèâûìè. 126 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 Ðèñ. 3. Ìîäåëü òåðìèíàëüíîãî óñòðîéñòâà Îäíàêî ñòðóêòóðà âñåõ âîçìîæíûõ òóïèêîâ ÿâëÿåòñÿ áîëåå ñëîæíîé. Ïîêàæåì, ÷òî òóïèêè ïðîèñõîäÿò ëèáî â öèêëàõ (öåïÿõ) áëîêèðîâîê, âîâëåêàþùèõ íåñêîëüêî êîììóíèêàöèîííûõ óñòðîéñòâ (ãäå ïàðà ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì), ëèáî â ðåçóëü- òàòå èçîëÿöèè óñòðîéñòâà îêðóæàþùèìè òóïèêàìè. Äëÿ îïèñàíèÿ ñëîæíûõ òóïèêîâ ñåòè HTd k, ïîñòðîåí ãðàô ñîåäèíåíèé GHd k, , â êî- òîðîì êàæäàÿ âåðøèíà ñîîòâåòñòâóåò êîììó- íèêàöèîííîìó óñòðîéñòâó è èìååò äóãè, íà- ïðàâëåííûå ê ñîñåäÿì. Ïðèìåð ñâÿçåé âíóò- ðåííåé âåðøèíû äëÿ GH k3, ïðåäñòàâëåí íà ðèñ. 4. Ëèíèÿ ñ äâóìÿ ñòðåëêàìè îáîçíà÷àåò ïàðó äóã ïðîòèâîïîëîæíûõ íàïðàâëåíèé. Íàïðàâëåííûé ïðîñòîé öèêë ãðàôà GHd k, ïðåäñòàâëÿåò òóïèê êîììóíèêàöèîííîãî ãè- ïåðêóáà HTd k, . Â òóïèêîâîì öèêëå êàæäàÿ äóãà, ñîåäèíÿþùàÿ ïàðó ñîñåäíèõ óñòðîéñòâ R i i iu d1� � � �� , R i i iu d1� � � � �� , \| \|i iu u� � � 1, îçíà- ÷àåò, ÷òî R i i iu d1� � � �� áëîêèðóåò ñåáÿ òîãäà è òîëüêî òîãäà, êîãäà îíî ñîäåðæèò l ïàêåòîâ, ïåðåíàïðàâëåííûõ â R i i iu d1� � � � �� . Åãî âûõîäíîé áóôåð ïîðòà, ñîåäèíÿþ- ùåãî R i i iu d1� � � �� ñ R i i iu d1� � � � �� , ñîäåðæèò ïàêåò, è óñòðîéñòâî R i i iu d1� � � � �� òàêæå çàáëîêèðîâàíî. Êîãäà öèêë çàâåðøàåòñÿ, åãî ïîñëåäíåå óñòðîéñòâî áëîêèðóåò ñåáÿ, ïîñêîëüêó ïåðâîå óñòðîéñòâî çàáëîêèðîâàíî è íå ìîæåò ïîëó÷àòü ïàêåòû. Äîêàæåì, ÷òî âñå ïåðåõîäû çàáëîêèðîâàííîãî óñòðîéñòâà R i i iu d1� � � �� ìåðòâû. Äëÿ îïðåäåëåííîñòè îáîçíà÷èì r i i i i u u u u � � � � � � � � � � � 1 1 2 1 , , , . Âñå ïåðåõîäû ti j n j n i id , , ,� � � �1 � ìåðòâû, òàê êàê ìàðêèðîâêà èõ âõîäíîé ïîçèöèè pbl i id1� �� ðàâíà íóëþ, ò.å. óñòðîéñòâî íå ìîæåò ïîëó÷àòü ïàêåòû. Âñå ïåðåõîäû to j n i id , 1� �� , n r� , ìåðòâû, òàê êàê êàæäàÿ âõîäíàÿ ïîçèöèÿ pb j n i id , 1� �� èìååò íóëåâóþ ìàðêèðîâêó. Ïåðåõîä tou r i id , 1� �� ìåðòâ, ïîñêîëüêó ìàðêèðîâêà åãî âõîäíîé ïîçè- öèè polu r i id , 1� �� íóëåâàÿ, ò.å. óñòðîéñòâî íå ìîæåò ïîñûëàòü ïàêåòû. Çàìåòèì, ÷òî ìàðêèðîâêà polu r i id , 1� �� íå ìîæåò áûòü èçìåíåíà, òàê êàê R i i iu d1� � � � �� áëîêèðîâàíî. Íåïðîñòûå öèêëû GHd k, òàêæå ïðåäñòàâëÿþò òóïèêè. Òàê, åñëè óñòðîéñòâî R i i i iu v d1� � � � � �� ïðèíàäëåæèò äâóì ïðîñòûì öèêëàì è èìååò äâå âûõîäíûå äóãè, íà- ïðàâëåííûå â R i i i iu v d1� � � � � � �� è R i i i iu v d1� � � � � � �� , òî ýòî îçíà÷àåò, ÷òî R i i i iu v d1� � � � � �� áëîêèðóåò ñåáÿ è óñòðîéñòâà R i i i iu v d1� � � � � � �� , R i i i iu v d1� � � � � � �� òàêæå áëîêèðîâàíû. Â ýòîì ñëó÷àå R i i i iu v d1� � � � � �� áëîêèðóåò ñåáÿ, èìåÿ au ïàêåòîâ, ïåðåíàïðàâëåííûõ â R i i i iu v d1� � � � � � �� , è av ïàêåòîâ, ïåðåíàïðàâëåííûõ â R i i i iu v d1� � � � � � �� , ãäå a a lu v� � , è, êðîìå òîãî, áóôåð êàæäîãî ñîîòâåòñòâóþùåãî âûõîäíîãî ïîðòà R i i i iu v d1� � � � � �� ñîäåðæèò ïàêåò â ñëó÷àå, êîãäà au � 0 (av � 0). Èíäóêòèâíûå ðàññóæäåíèÿ ïîçâîëÿþò ïîëó÷èòü äîêàçàòåëüñòâî äëÿ d ïðîñòûõ öèêëîâ. Äðóãàÿ ðàçíîâèäíîñòü òóïèêîâ âûçâàíà èçîëÿöèåé íåêîòîðîãî óñòðîéñòâà òóïèêà- ìè, ñîäåðæàùèìè âñå åãî ñîñåäíèå óñòðîéñòâà. Òàêàÿ èçîëÿöèÿ òàêæå ìîæåò áûòü ïî- ëó÷åíà îäíèì ïðîñòûì öèêëîì. Íàïðèìåð, â ãðàôå GH k3, ñëåäóþùèé öèêë R i i i1 2 31� , , , R i i i1 2 31 1� �, , , R i i i1 2 31, ,� , R i i i1 2 31 1, ,� � , R i i i1 2 3 1, , � , R i i i1 2 31 1� �, , , R i i i1 2 31� , , , R i i i1 2 31 1� �, , , R i i i1 2 31, ,� , R i i i1 2 31 1, ,� � , R i i i1 2 3 1, , � , R i i i1 2 31 1� �, , , R i i i1 2 31� , , ñîäåðæèò âñå ñîñåäíèå âåðøèíû R i i i1 2 3, , ( R i i i1 2 31� , , , R i i i1 2 31, ,� , R i i i1 2 3 1, , � , R i i i1 2 31� , , , R i i i1 2 31, ,� , R i i i1 2 3 1, , � ), ïîýòîìó óñòðîéñòâî R i i i1 2 3, , áëîêèðîâàíî â ðåçóëüòàòå èçîëÿöèè. Èçîëÿ- öèÿ âåðøèíû ìîæåò áûòü îáîáùåíà íà áëîêèðîâêó ïðîñòîé öåïè èçîëÿöèåé åå ïî- ñëåäíåé âåðøèíû. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 127 Ðèñ. 4. Ñâÿçè âåðøèíû ãðàôà GH k3, Òàêèì îáðàçîì, òóïèê ïðåäñòàâëÿåò ñîáîé öåïü áëîêèðîâîê, ãäå ïîñëåäíÿÿ âåðøè- íà áëîêèðîâàíà â ðåçóëüòàòå òîãî, ÷òî îíà ñîâïàäàåò ñ ïåðâîé âåðøèíîé, îíà ïðèíàä- ëåæèò äðóãîé öåïè áëîêèðîâîê èëè îíà èçîëèðîâàíà äðóãèìè öåïÿìè áëîêèðîâîê. Ñëåäóåò îòìåòèòü, ÷òî îáðàçîâàííûå òóïèêè ñîçäàþò áîëüøå âîçìîæíîñòåé äëÿ ïîÿâëåíèÿ íîâûõ òóïèêîâ. Òàêèì îáðàçîì, ïðîöåññ èìååò ëàâèíîîáðàçíûé õà- ðàêòåð. Ïîëíûé òóïèê, ñîäåðæàùèé âñå óñòðîéñòâà (è âñå ïåðåõîäû), ïðîèñõîäèò, êîãäà öèêëû (öåïè) ñîäåðæàò âñå óñòðîéñòâà â ãèïåðêóáå. Ýòî òðåáóåò, ïî êðàéíåé ìåðå, ( )l k d� �1 ïàêåòîâ, îáåñïå÷åííûõ òåðìèíàëüíûìè óñòðîéñòâàìè. Îäíàêî åñëè ïðîèñõîäèò èçîëÿöèÿ óñòðîéñòâ, òî òðåáóåòñÿ ìåíüøåå ÷èñëî ïàêåòîâ. Íåñìîòðÿ íà òî, ÷òî èçó÷åíû äîñòàòî÷íî ñëîæíûå êîììóíèêàöèîííûå ñòðóêòó- ðû ãèïåðêóáà, îïèñàííûå òóïèêè â öåïÿõ (öèêëàõ) áëîêèðîâîê è â ðåçóëüòàòå èçîëÿ- öèè ïðèñóùè ðåàëüíûì êîììóíèêàöèîííûì ãðàôàì, ãäå èñïîëüçóþòñÿ óñòðîéñòâà ñ ïðèíóäèòåëüíîé áóôåðèçàöèåé ïàêåòîâ. Áîëåå òîãî, ýòè òóïèêè ìîãóò áûòü ïðåäíà- ìåðåííî âûçâàíû ñïåöèàëüíî ðàçìåùåííûìè ãåíåðàòîðàìè îïðåäåëåííîãî òðàôèêà. Â ðåàëüíûõ ñåòÿõ áëîêèðîâàíèå óñòðîéñòâà ïðåîäîëåâàåòñÿ ñ ïîìîùüþ ìåõàíèçìà òàéìàóòà, âûçûâàþùåãî î÷èñòêó áóôåðà â ðåçóëüòàòå ñòàðåíèÿ çàïèñåé, íî ýòî ïðè- âîäèò ê ñóùåñòâåííîìó ñíèæåíèþ ïðîèçâîäèòåëüíîñòè ñåòè, ïîñêîëüêó ñèòóàöèÿ ìîæåò áûòü ïîâòîðåíà ñïåöèàëüíûìè ãåíåðàòîðàìè çëîíàìåðåííîãî òðàôèêà. ÇÀÊËÞ×ÅÍÈÅ Ïðåäñòàâëåíàÿ ìåòîäèêà âû÷èñëåíèÿ ëèíåéíûõ èíâàðèàíòîâ ïàðàìåòðè÷åñêèõ ñåòåé Ïåòðè ñ ðåãóëÿðíîé ñòðóêòóðîé èçó÷åíà íà ïðèìåðå êîììóíèêàöèîííîãî ãèïåðêóáà ïðîèçâîëüíîãî ðàçìåðà ñ ïðîèçâîëüíûì ÷èñëîì èçìåðåíèé. Ïðèìåíåíèå ìåòîäèêè ïîçâîëèëî âûïîëíèòü àíàëèç êîììóíèêàöèîííûõ ïðîöåññîâ, îáðàçîâàííûõ ïðîèç- âîëüíûì ÷èñëîì âçàèìîäåéñòâóþùèõ êîììóíèêàöèîííûõ óñòðîéñòâ. Ñìîäåëèðîâà- íî êîììóíèêàöèîííîå óñòðîéñòâî, ïðåäñòàâëÿþùåå ñîáîé îáîáùåííûé ìàðøðóòèçà- òîð (êîììóòàòîð) ñ ïðèíóäèòåëüíîé áóôåðèçàöèåé ïàêåòîâ. Òàêèå ïîëîæèòåëüíûå ñâîéñòâà êîììóíèêàöèîííîé ñòðóêòóðû, êàê êîíñåðâàòèâíîñòü è êîíñèñòåíòíîñòü äîêàçàíû ñ ïîìîùüþ ëèíåéíûõ èíâàðèàíòîâ áåñêîíå÷íûõ ñåòåé Ïåòðè. Îáîñíîâàíî, ÷òî ïðèíóäèòåëüíàÿ áóôåðèçàöèÿ ïàêåòîâ íåèçáåæíî ïðèâîäèò ê áëîêèðîâàíèþ êîììóíèêàöèîííûõ óñòðîéñòâ. Èçó÷åíà ñòðóêòóðà ñëîæíûõ òóïè- êîâ, âîâëåêàþùèõ ïðîèçâîëüíîå ÷èñëî êîììóíèêàöèîííûõ óñòðîéñòâ, âûçâàííûõ êàê öåïÿìè (öèêëàìè) áëîêèðîâîê, òàê è èçîëÿöèåé óñòðîéñòâ. Íåñìîòðÿ íà òî, ÷òî â ðåàëüíûõ òåëåêîììóíèêàöèîííûõ ñåòÿõ òóïèêè ïðåîäî- ëåâàþòñÿ î÷èñòêîé áóôåðà ÷åðåç ìåõàíèçì òàéìàóòà, ýòî ïðèâîäèò ê ñóùåñòâåííî- ìó ñíèæåíèþ ïðîèçâîäèòåëüíîñòè ñåòè è, êðîìå òîãî, ìîæåò áûòü âûçâàíî çëîíà- ìåðåííûì òðàôèêîì. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. M a r s a n A . M . , C h i o l a G . , F u m a g a l l i A . An accurate performance model of CSMA/CD Bus LAN // Advances in Petri Nets, LNCS. — 1987, 266. — P. 146–161. 2. Z a i t s e v D . A . , Z a i t s e v I . D . Verification of Ethernet protocols via parametric composition of Petri net // INCOM’2006: 12th IFAC/IFIP/IFORS/IEEE/IMS Symposium Information Control Problems in Man- ufacturing, May 17–19 2006, Saint-Etienne, France. — P. 261–267. 3. Z a i t s e v D . A . Functional Petri nets. Universite Paris-Dauphine, Cahier du Lamsade 224, Avril 2005. — 62 p. (www.lamsade.dauphine.fr/cahiers.html) 4. S h m e l e v a T . R . Verification of switched Ethernet protocols using infinite Petri nets // COMINFO’2007: Third International conference on Modern information-communication technologies, September 24–28, 2007, Levadia, Ukraine. — P. 161–163. 5. Z a i t s e v D . A . , S h m e l e v a T . R . Hypercube communication structures analysis via parametric Petri nets // Proceedings of 24th UK Performance Engineering Workshop (UKPEW 2008), 3–4 July 2008, De- partment of Computing, Imperial College London. — P. 358–371. 6. Mura ta T. Petri nets: Properties, analysis and applications // Proceedings of the IEEE, April 1989, 77. — P. 541–580. 7. B e r t h e l o t G . , T e r r a t R . Petri nets theory for the correctness of protocols // IEEE Trans. on Communi- cations. — 1982. — 30, N 12. — P. 2497–2505. 8. D i a z M . Modelling and analysis of communication and cooperation protocols using Petri net based model // Computer Network. — 1982. — N 6. — P. 419–441. 9. B e r t h o m i e u B . , R i b e t O . - P . , V e r n a d a t F . The tool TINA-construction of abstract state space for Petri nets and time Petri nets // International Journal of Production Research. — 2004. — 42, N 4 (http://www.laas.fr/tina). Ïîñòóïèëà 22.12.2008 128 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1

Верификация коммуникационных структур гиперкуба параметрическими сетями Петри

Репозитарії

Схожі ресурси