Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Համակարգչային ցանցերում ինֆորմացիայի տարածման օպտիմալ կառուցվածքների նախագծման մեթոդների և ալգորիթմների մշակում

Հովնանյան, Վիլյամ Հակոբի (2018) Համակարգչային ցանցերում ինֆորմացիայի տարածման օպտիմալ կառուցվածքների նախագծման մեթոդների և ալգորիթմների մշակում. PhD thesis, ՀՀ ԳԱԱ Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ.

[img]
Preview
PDF (Thesis)
Available under License Creative Commons Attribution.

Download (15Mb) | Preview
    [img]
    Preview
    PDF (Abstract)
    Available under License Creative Commons Attribution.

    Download (4Mb) | Preview

      Abstract

      Վերջին տասնամյակում միջին ու մեծ չափերի հասնող ցանցային հաշվողական համակարգերի (կլաստերային համակարգեր, գրիդ) կիրառությունը լայն տարածում է ստացել գիտության, տնտեսության տարբեր ճյուղերի առջև դրված խնդիրների լուծման տեսանկյունից: Արդի սերնդի տարաբնույթ հաշվողական ցանցերում, ինչպիսիք են, մասնավորապես՝ սենսորային, ad-hoc, ինչպես նաև բազմահամակարգչային կամ բազմապրոցեսորային ցանցերում համակարգի հանգույցների միջև ինֆորմացիայի օպտիմալ և/կամ վթարակայուն փոխանակման ու տարածման ապահովումը կարևորագույն նշանակություն ունի: Ի տարբերություն հայտնի դասական հեռախոսային ցանցերի, այսպիսի ցանցերի հիմնական նպատակը ոչ միայն համակարգի տարբեր բաղադրիչների միջև արդյունավետ հաղորդակցության ապահովումն է, այլ նաև հաշվողական և ինֆորմացիայի տարածման ալգորիթմների իրականացման համար դրանց համապատասխանության ապահովման խնդիր է առաջանում: Օրինակ, սենսորային ցանցերի էֆեկտիվության և ֆունկցիոնալության ապահովման համար անհրաժեշտություն է առաջանում իրադարձությունների հայտնաբերման և արձանագրման ապակենտրոն օպտիմալ ալգորիթմների մշակման՝ հաշվի առնելով սենսորի դիտարկումները: Մեկ այլ օրինակ են հանդիսանում անօդաչու թռչող սարքերը, որոնք կարիք ունեն ապակենտրոն օպտիմալ վթարակայուն հաղորդակցության ալգորիթմների, որպեսզի կոորդինացնեն իրենց գործողությունները: Որպես կանոն, նման ցանցերը գործում են այնպիսի միջավայրում, որտեղ կան հաշվողական, հաղորդակցային կամ էներգետիկ ռեսուրսային որոշակի սահմանափակումներ, ինչպես նաև ցանցի տոպոլոգիան ինքնին ենթակա է փոփոխության` ժամանակից կախված: Հաշվի առնելով նման ցանցերի յուրահատկությունները, մասնավորապես նաև բավականին մեծ չափերը ու դրանց առջև դրված խնդիրները, կարևորություն է ձեռք բերում այդպիսի ցանցերում գործող ալգորիթմների պարզ, տարաբաշխված, կայուն՝ ցանցի դինամիկայի նկատմամբ, որևէ միակ խափանման կետից զուրկ և ապակենտրոն բնույթը ապահովելը: Վերոնշյալ պահանջները հիմք հանդիսացան այսպես կոչված “gossip” ալգորիթմների մշակման համար. սխեմաներ, որոնցում հաշվողական հզորությունը տարաբաշխված է համակարգի տարբեր հանգույցների միջև, և որոնցից յուրաքանչյուրն ունի միայն տեղայնացված պատկերացում համակարգի մասին, ուստի հաղորդակցվում է միայն հանգույցների որոշակի ենթաբազմության հետ: Նման հաղորդակցային սխեմաները, որպես կանոն, օժտված են վթարակայունությամբ և ինֆորմացիայի օպտիմալ տարածման հատկություններով: Բացի այդ, “gossip” արձանագրություններն օգտագործվում են բաշխված տվյալների հենքերի կայունության (consistency) ապահովման, դինամիկ հարափոփոխ ցանցերի հանգույցների քանակի որոշման, ցանցում ինֆորմացիայի անխափան տարածման ապահովման, բաշխված համակարգերում որոշ ագրեգացիոն հաշվարկների կատարման, գլխավոր հանգուցների ընտրության, և այլ նպատակներով: Այս համատեքստում մեծ կարևորություն է ներկայացնում ինֆորմացիայի տարածման/փոխանակման ստոխաստիկ և քվազի-ստոխաստիկ պրոցեսների մոդելների հետազոտությունը: Մյուս կողմից, ինֆորմացիայի լրիվ փոխանակման ցանցերի հիմնական բնութագրիչների օպտիմալ արժեքների վերաբերյալ հստակ պատկերացում ստանալու համար անհրաժեշտ է իրականացնել վերոնշյալ ցանցերում ինֆորմացիայի փոխանակման դետերմինացված պրոցեսների հետազոտություն: Այսպիսի ցանցերի հիմնական բնութագրիչներից են՝ ցանցում լրիվ ինֆորմացիայի փոխանակման համար անհրաժեշտ ժամանակը, կանչերի թիվը, կապուղիների թիվը, և այլն։ Այս բնութագրիչների հետազոտությունը, ինչպես նաև ինֆորմացիայի տարածման համապատասխան ալգորիթմների մշակումը կնպաստեն նաև ստոխաստիկ պրոցեսներով նկարագրվող մոդելների հետազոտմանը: Չնայած “gossip” խնդիրներին վերաբերող գիտական աշխատությունների մեծ թվին, այնուամենայնիվ, գոյություն ունի բաց խնդիրների դաս: Մասնավորապես, մինչ այժմ տրված չեն վթարակայուն “gossip” խնդիրներում մեծ կարևորություն ներկայացնող կանչերի մինիմալ քանակի և կանչերի մինիմալ ժամանակի վերաբերյալ հստակ գնահատականներ, ինչպես նաև բաց է մնացել NOHO տեսակի “gossip” սխեմաների համապատասխան բնութագրիչների հստակ գնահատականների ստացման խնդիրը: Հաշվի առնելով վերոնշյալ հանգամանքները, արդիական է դառնում ինֆորմացիայի լրիվ փոխանակման/տարածման օպտիմալ ալգորիթմների կամ սխեմաների մշակումը, որոնց հիմնական նպատակը կլինի այդ պրոցեսի իրականացումը նվազագույն հնարավոր կանչերի թվի, նվազագույն հնարավոր ժամանակի կամ նվազագույն հնարավոր կապուղիների թվի պարագայում։ За последнее десятилетие применение вычислительных сетевых систем (кластерная система, грид), достигших средних и больших размеров, получило широкое распространение с точки зрения решения проблем, поставленных перед разными отраслями экономики и науки. Обеспечение оптимального и/или отказоустойчивого обмена и распространения информации между узлами в разнохарактерных вычислительных сетях современного поколения, таких как, в частности, сенсорный, ad-hoc, как и в много-компьютерных и многопроцессорных сетях имеет важнейшее значение. В отличие от классических телефонных сетей, основная цель таких сетей заключается не только в обеспечении эффективной связи между различными компонентами системы, но и в обеспечении того, чтобы их алгоритмы вычисления и распространения информации были соблюдены. Как правило, такие сети действуют в такой среде, где имеются определенные вычислительные и энергетические ресурсные ограничения, как и топология сети сама по себе подвергается изменению в зависимости от времени. Учитывая своеобразность данных сетей, в частности, довольно большие размеры, а также задачи, поставленные перед ними, приобретает важность обеспечения простых, распределенных, устойчивых по отношению к динамике сетей, лишенных единственной точки отказа и децентрализованных алгоритмов, действующих в данных сетях. Вышеуказанные требования послужили основой для разработки так называемых “gossip” алгоритмов: схемы, в которых вычислительная мощность распределена между разными узлами системы, и каждая из них имеет только локализованное понимание относительно системы, поэтому и сообщается только с подмножеством определенных узлов. Данные коммуникационные схемы, как правило, наделены особенностями оптимального распространения информации и отказоустойчивостью. Учитывая вышеуказанные обстоятельства, актуальной становится разработка оптимальных схем или алгоритмов полной передачи/распространения информации, основной целью которых станет осуществление данного процесса при минимальном количестве вызовов, минимальном количестве времени и минимальном количестве путей связи. В течение исследования получены следующие результаты: минимальные gossip схемы применены в качестве основной сетевой топологии в системах, достигающих больших размеров, для того чтобы оптимальным методом организовать децентрализованную коммуникацию между компонентами системы. С этой точки зрения предлагаемые отказоустойчивые gossip схемы также являются значимым результатом, применение которых может рассматриваться в многокомпонентных децентрализованных системах, действующих в неустойчивой среде. Спроектированная Graph Plotter система имеет применимое значение для моделирования вышеуказанных сетей. Она позволяет спроектировать такие сети (при малом количестве вершин), выполнить структурные изменения в их разных фрагментах, проверить уровень отказоустойчивости и др. During the last decades, the application of medium and large-scale network computing systems (clusters, grids) has become widespread in various areas (research, economics, social, etc.). Parallel to their dissemination, the construction of optimal network structures has become actual to ensure fast information exchange among the nodes of the network. For their investigation, new approaches have been developed based on discrete mathematics, graph theory, parallel programming and probability theory. Organization of optimal and fault-tolerant exchange of the information between the nodes of the sensor, ad-hoc or multicomputer networks is of a crucial importance. For example, there is a need for distributed fault-tolerant optimal communication algorithms (provided the sensor observations) for preserving functionality and efficiency of sensor network. Normally, the above mentioned networks are operating under computational or energy resource constraints, sometimes in a volatile environments. Thus, considering the peculiarities of such networks and, also, a relatively large scale, it is required that the algorithms operating within them are simple, distributed, tolerant against dynamics of the network and without any single point of failure. The above mentioned requirements lead to the design of “gossip” algorithms - schemes where the computational power is distributed among components of the network. Meanwhile, each of these components has only local knowledge about the structure of the system, thus can interact only with its several neighbours. This kind of communication schemes are naturally fault-tolerant and optimal for information dissemination. Anyway, the implementation of communication processes using minimum possible number of calls, shortest possible time or minimum possible number of channels is still actual. Provide network structures for gossip communication with optimal or near optimal values for the main properties of gossiping process (number of calls, number of channels and gossiping time). The results obtained in this research, namely, minimum gossip graphs are applicable as an underlying communication topology for large scale distributed systems and can provide optimal communication between components of the systems. From this perspective, it is also worth mentioning fault-tolerant gossip schemas that can be applicable in a multicomponent decentralized systems operating in a non-stable environment. On the other hand, designed Graph Plotter software package has a practical value in terms of modeling of the above mentioned schemas. It allows us to construct such networks (for small number of vertices), also to make some structural changes to them and to verify the level of fault-tolerance, etc.

      Item Type: Thesis (PhD)
      Additional Information: Համակարգչային ցանցերում ինֆորմացիայի տարածման օպտիմալ կառուցվածքների նախագծման մեթոդների և ալգորիթմների մշակում: Разработка алгоритмов и методов проектирования оптимальных структур по распространению информации в компьютерных сетях.
      Uncontrolled Keywords: Հովնանյան Վիլյամ Հակոբի, Овнанян Вильям
      Subjects: Informatics and Computer Systems
      Divisions: UNSPECIFIED
      Depositing User: NLA Circ. Dpt.
      Date Deposited: 04 Sep 2018 16:04
      Last Modified: 04 Sep 2018 16:04
      URI: http://etd.asj-oa.am/id/eprint/7593

      Actions (login required)

      View Item