Jauna pieeja Vertex savienojamībai varētu maksimāli palielināt tīklu joslas platumu

Datorzinātnieki pastāvīgi meklē veidus, kā izspiest arvien lielāku joslas platumu no sakaru tīkliem.

Tagad jauna pieeja grafu teorijas pamatjēdziena izpratnei, kas pazīstama kā virsotņu savienojamība, galu galā varētu novest pie sakaru protokoliem — noteikumiem, kas nosaka, kā notiek digitālo ziņojumu apmaiņa —, kas pierunā pēc iespējas lielāku joslas platumu no tīkliem.

Grafu teorijai ir galvenā loma matemātikā un datorzinātnēs, un to izmanto, lai aprakstītu attiecības starp dažādiem objektiem. Katrs grafiks sastāv no vairākiem mezgliem vai virsotnēm, kas attēlo objektus, un savienojošām līnijām starp tiem, kas pazīstamas kā malas, kas apzīmē attiecības starp tiem. Piemēram, sakaru tīklu var attēlot kā grafiku, kurā katrs tīkla mezgls ir viena virsotne, un savienojums starp diviem mezgliem ir attēlots kā mala.

Viens no grafu teorijas pamatjēdzieniem ir savienojamība, kurai ir divi varianti: malu savienojamība un virsotņu savienojamība. Tie ir skaitļi, kas nosaka, cik līniju vai mezglu būtu jānoņem no konkrētā grafika, lai to atvienotu. Tāpēc, jo mazāks ir grafa malu savienojamības vai virsotņu savienojamības numurs, jo vieglāk to atvienot vai sadalīt.

Tādā veidā abas koncepcijas parāda, cik izturīgs tīkls ir pret atteici un cik liela plūsma var iet caur to — vai tā ir informācijas plūsma sakaru tīklā, satiksmes plūsma transporta sistēmā vai šķidruma plūsma hidraulikā.

Malu savienojamības malu samazināšana

Tomēr, lai gan matemātikā ir veikts daudz pētījumu, lai atrisinātu problēmas, kas saistītas ar malu savienojamību, ir bijuši salīdzinoši maz panākumu, atbildot uz jautājumiem par virsotņu savienojamību.

Bet ACM-SIAM simpozijā par diskrētiem algoritmiem Portlendā, Oras štatā, janvārī Mohsens Gafari, aspirants Datorzinātnes un mākslīgā intelekta laboratorija MIT prezentēs jaunu tehniku ​​virsotņu savienojamības problēmu risināšanai.

Tas galu galā varētu palīdzēt mums saprast, kā izveidot izturīgākus un ātrākus tīklus, saka Gafari, kurš izstrādāja jauno pieeju kopā ar Kerenu Censoru-Hillelu no Technion un Fabian Kuhn Freiburgas Universitātē.

Sešdesmitajos gados matemātiķi Viljams Tute un Krispins Nešs-Viljamss atsevišķi izstrādāja teorijas par struktūrām, ko sauc par malu nesavienotiem aptverošiem kokiem, kas tagad kalpo kā viens no galvenajiem tehniskajiem instrumentiem daudzās malās savienojamības problēmās.

Aptverošais koks ir apakšgrāfs vai grafs grafikā, kurā visi mezgli ir savienoti ar mazāko malu skaitu. Grafika aptverošu koku kopa tiek saukta par malu disjunktu, ja tiem nav kopīga neviena no šīm savienojošajām līnijām.

Ja tīklā ir, piemēram, trīs malu nesavienoti aptveroši koki, informācija var plūst paralēli pa katru no šiem kokiem vienlaikus, kas nozīmē trīs reizes lielāku joslas platumu, nekā būtu iespējams grafikā, kurā ir tikai viens koks. Gafari saka, ka jo lielāks ir ar malām nesaistīto koku skaits, jo lielāka ir informācijas plūsma. Viņš saka, ka Tutte un Nash-Williams rezultāti liecina, ka katrā grafikā ir gandrīz tikpat daudz aptverošu koku kā tā malu savienojamība.

Tagad komanda ir izveidojusi analogu teoriju par virsotņu savienojamību. Viņi to izdarīja, sadalot grafiku atdalītās mezglu grupās, kas pazīstamas kā saistītās dominējošās kopas. Grafu teorijā mezglu grupu sauc par savienotu dominējošo kopu, ja visas tajā esošās virsotnes ir savienotas viena ar otru un jebkurš cits grafa mezgls atrodas blakus vismaz vienam no grupas iekšienē esošajiem mezgliem.

Tādā veidā informāciju var izplatīt starp kopas mezgliem un pēc tam nodot jebkuram citam tīkla mezglam.

Tātad, līdzīgi kā Tutte un Nesh-Williams rezultāti par malu savienojamību, katrā grafikā ir gandrīz tikpat daudz virsotņu nesavienotu savienotu dominējošo kopu kā tā virsotņu savienojamība, saka Gafari.

Tātad, ja jūs domājat par tādu lietojumprogrammu kā informācijas apraide caur tīklu, mēs tagad varam sadalīt tīklu daudzās grupās, no kurām katra ir viena savienota dominējošā kopa, viņš saka. Katra no šīm grupām būs atbildīga par dažu ziņojumu kopas pārraidīšanu, un visas grupas strādā paralēli, lai pārraidītu visus ziņojumus ātri — gandrīz pēc iespējas ātrāk.

Komanda tagad ir izstrādājusi algoritmu, kas var rūpīgi sadalīt tīklu daudzās savienotās dominējošās kopās. Tādā veidā tā var strukturēt tā sauktos bezvadu ad hoc tīklus, kuros atsevišķi mezgli maršrutē datus, nododot tos no viena uz nākamo, lai nodrošinātu iespējami labāko informācijas plūsmas ātrumu. Mēs vēlamies, lai varētu izplatīt pēc iespējas vairāk informācijas laika vienībā, lai izveidotu ātrākus un ātrākus tīklus, saka Gaffari. Un, ja grafikam ir labāka virsotņu savienojamība, tas nodrošina lielāku [informācijas] plūsmu, viņš piebilst.

Pielietojumi robustuma novērtēšanā

Pētnieki var arī izmantot savu jauno pieeju, lai analizētu tīkla noturību pret nejaušām kļūmēm. Šīs jaunās metodes arī ļauj mums analizēt, vai tīkls, visticamāk, paliks savienots, ja tā mezgli nejauši neizdodas ar noteiktu varbūtību, saka Gafari. Viņš piebilst, ka uzticamība pret nejaušām malu kļūmēm ir labi saprotama, taču mēs par to zinājām daudz mazāk par mezglu kļūmēm.

Telavivas universitātes matemātikas un datorzinātņu profesore Noga Alona saka, ka Gafari un viņa kolēģi ir identificējuši jēdzienu, kas nosaka lielāko sasniedzamo plūsmu, pārraidot ziņojumus, izmantojot maršrutēšanu sakaru tīklos.

Viņš saka, ka šī jēdziena, virsotņu nesavienotu dominējošo kopu izpēte šajā rakstā ir aplūkota ar elegantu kombinatorisko, varbūtības un algoritmisko paņēmienu kombināciju.

paslēpties