Sawl blwyddyn yn ôl, grŵp rhyngwladol o wyddonwyr o brifysgolion Massachusetts, Pennsylvania a Munich, yr Almaen ymchwil i effeithiolrwydd dirprwyon traddodiadol fel arf gwrth-sensoriaeth. O ganlyniad, cynigiodd gwyddonwyr ddull newydd o osgoi blocio, yn seiliedig ar theori gêm. Rydym wedi paratoi cyfieithiad wedi'i addasu o brif bwyntiau'r gwaith hwn.
Cyflwyniad
Mae dull offer ffordd osgoi bloc poblogaidd fel Tor yn seiliedig ar ddosbarthiad preifat a dethol o gyfeiriadau IP dirprwyol ymhlith cleientiaid o ranbarthau sy'n destun blocio. O ganlyniad, rhaid i gleientiaid aros heb eu canfod gan sefydliadau neu awdurdodau sy'n gosod blociau. Yn achos Tor, gelwir y dosbarthwyr dirprwyol hyn yn bontydd.
Y broblem allweddol gyda gwasanaethau o'r fath yw ymosodiad gan bobl fewnol. Gall asiantau blocio ddefnyddio dirprwyon eu hunain i ddarganfod eu cyfeiriadau a'u rhwystro. Er mwyn lleihau'r tebygolrwydd o gyfrifiadau dirprwyol, mae offer dargyfeiriol bloc yn defnyddio amrywiol fecanweithiau aseiniad cyfeiriad.
Yn yr achos hwn, defnyddir yr hyn a elwir yn ddull heuristics ad hoc, y gellir ei osgoi. I ddatrys y broblem hon, penderfynodd gwyddonwyr gyflwyno'r frwydr rhwng gwasanaethau sy'n ymwneud â blocio a gwasanaethau i'w hosgoi fel gêm. Gan ddefnyddio theori gêm, fe wnaethant ddatblygu'r strategaethau ymddygiadol gorau posibl ar gyfer pob un o'r partïon - yn benodol, roedd hyn yn ei gwneud hi'n bosibl datblygu mecanwaith dosbarthu dirprwyol.
Sut mae systemau ffordd osgoi clo traddodiadol yn gweithio
Mae offer dargyfeiriol bloc fel Tor, Lantern, a Psiphon yn defnyddio cyfres o ddirprwyon y tu allan i'r rhanbarth gyda chyfyngiadau ar waith a ddefnyddir i ddargyfeirio traffig defnyddwyr o'r rhanbarthau hynny a'i ddosbarthu i adnoddau sydd wedi'u blocio.
Os daw sensoriaid yn ymwybodol o gyfeiriad IP dirprwy o'r fath - er enghraifft, ar ôl iddynt ei ddefnyddio eu hunain - gellir ei roi ar restr ddu a'i rwystro'n hawdd. Felly, mewn gwirionedd, nid yw cyfeiriadau IP dirprwyon o'r fath byth yn cael eu datgelu, ac mae defnyddwyr yn cael un dirprwy neu'r llall gan ddefnyddio amrywiol fecanweithiau. Er enghraifft, mae gan Tor system bont.
Hynny yw, y brif dasg yw rhoi mynediad i ddefnyddwyr at adnoddau sydd wedi'u blocio a lleihau'r tebygolrwydd o ddatgelu cyfeiriad dirprwy.
Nid yw datrys y broblem hon yn ymarferol mor hawdd - mae'n anodd iawn gwahaniaethu'n gywir rhwng defnyddwyr cyffredin a sensoriaid yn ffugio oddi wrthynt. Defnyddir mecanweithiau hewristig i guddio gwybodaeth. Er enghraifft, mae Tor yn cyfyngu nifer y cyfeiriadau IP pont sydd ar gael i gleientiaid i dri fesul cais.
Nid oedd hyn yn atal yr awdurdodau Tsieineaidd rhag nodi holl bontydd Tor mewn amser byr. Bydd cyflwyno cyfyngiadau ychwanegol yn effeithio'n ddifrifol ar ddefnyddioldeb y system ffordd osgoi bloc, hynny yw, ni fydd rhai defnyddwyr yn gallu cyrchu'r dirprwy.
Sut mae theori gêm yn datrys y broblem hon
Mae’r dull a ddisgrifir yn y gwaith yn seiliedig ar yr hyn a elwir yn “gêm derbyn coleg”. Yn ogystal, rhagdybir y gall asiantau sensro Rhyngrwyd gyfathrebu â'i gilydd mewn amser real a defnyddio tactegau cymhleth - er enghraifft, peidio â rhwystro dirprwyon ar unwaith neu ei wneud yn syth yn dibynnu ar amodau amrywiol.
Sut mae derbyn i goleg yn gweithio?
Gadewch i ni ddweud bod gennym ni n myfyrwyr ac m colegau. Mae pob myfyriwr yn gwneud ei restr ei hun o ddewisiadau ymhlith sefydliadau addysgol yn seiliedig ar feini prawf penodol (hynny yw, dim ond colegau y mae dogfennau wedi'u cyflwyno iddynt sy'n cael eu rhestru). Ar y llaw arall, mae colegau hefyd yn rhestru myfyrwyr sydd wedi cyflwyno dogfennau yn seiliedig ar eu dewisiadau eu hunain.
Yn gyntaf oll, mae'r coleg yn torri oddi ar y rhai nad ydynt yn bodloni'r meini prawf dethol - ni fyddant yn cael eu derbyn hyd yn oed os oes prinder. Yna dewisir ymgeiswyr gan ddefnyddio algorithm sy'n ystyried y paramedrau angenrheidiol.
Mae'n bosibl y bydd "derbyniadau ansefydlog" - er enghraifft, os oes dau fyfyriwr 1 a 2 a gafodd eu derbyn i golegau a a b yn y drefn honno, ond byddai'r ail fyfyriwr yn hoffi astudio mewn prifysgol a. Yn achos yr arbrawf a ddisgrifiwyd, dim ond cysylltiadau sefydlog rhwng gwrthrychau a ystyriwyd.
Algorithm Derbyn Oedi
Fel y dywedwyd eisoes, mae nifer arbennig o fyfyrwyr na fydd y coleg yn eu derbyn o dan unrhyw amgylchiadau. Felly, mae'r algorithm derbyn gohiriedig yn rhagdybio na chaniateir i'r myfyrwyr hyn wneud cais i'r sefydliad hwnnw. Yn yr achos hwn, mae pob myfyriwr yn ceisio mynd i mewn i'r colegau y maent yn eu hoffi fwyaf.
Mae sefydliad sydd â chapasiti o q myfyrwyr yn rhestru'r q person sydd â'r safle uchaf yn seiliedig ar ei feini prawf, neu'r cyfan os yw nifer yr ymgeiswyr yn llai na nifer y lleoedd sydd ar gael. Mae'r gweddill yn cael eu gwrthod, ac mae'r myfyrwyr hyn yn gwneud cais i'r brifysgol nesaf ar eu rhestr o ddewisiadau. Mae'r coleg hwn hefyd yn dewis y myfyrwyr sydd â'r sgôr uchaf o blith y rhai a ymgeisiodd ar unwaith a'r rhai na chawsant eu derbyn i'r coleg cyntaf. Hefyd, eto nid yw nifer penodol o bobl yn mynd heibio.
Daw'r drefn i ben os yw pob myfyriwr ar restr aros rhyw goleg neu wedi cael ei wrthod gan bob sefydliad addysgol lle gallai gofrestru. O ganlyniad, mae colegau o'r diwedd yn derbyn pawb oddi ar eu rhestrau aros.
Beth sydd gan ddirprwy i'w wneud ag ef?
Trwy gyfatebiaeth â myfyrwyr a cholegau, roedd gwyddonwyr wedi neilltuo dirprwy penodol i bob cleient. Y canlyniad oedd gêm o'r enw gêm aseiniad dirprwyol. Mae cleientiaid, gan gynnwys asiantau sensro posibl, yn gweithredu fel myfyrwyr sydd eisiau gwybod cyfeiriad dirprwyon, sy'n chwarae rôl colegau - mae ganddynt led band cyfyngedig hysbys ymlaen llaw.
Yn y model a ddisgrifir mae yna n defnyddiwr (cleientiaid) A =
{a1, a2, …, a}, sy'n gofyn am fynediad i'r dirprwy i osgoi blocio. Felly, ai yw dynodwr y cleient “cyfanswm”. Ymhlith y defnyddwyr n hyn, mae m yn asiantau sensro, a ddynodir fel J = {j1, j2, ..., jm}, mae'r gweddill yn ddefnyddwyr cyffredin. Mae pob asiant m yn cael ei reoli gan awdurdod canolog ac yn derbyn cyfarwyddiadau ganddo.
Tybir hefyd bod set o ddirprwyon P = {p1, p2, ..., pl}. Ar ôl pob cais, mae'r cleient yn derbyn gwybodaeth (cyfeiriad IP) am k dirprwyon o'r gwrthrych dosbarthwr. Rhennir amser yn gyfnodau cyfyng, wedi'u dynodi fel t (mae'r gêm yn dechrau ar t=0).
Mae pob cleient yn defnyddio'r swyddogaeth sgorio i werthuso'r dirprwy. Defnyddiodd gwyddonwyr y swyddogaeth 
i nodi’r sgôr a neilltuwyd gan y defnyddiwr i px dirprwy ar gam t. Yn yr un modd, mae pob dirprwy yn defnyddio swyddogaeth i werthuso cleientiaid. Hynny yw yw'r sgôr y dirprwy px a neilltuwyd i'r cleient ai ar gam t.
Mae'n bwysig cofio bod y gêm gyfan yn rhithwir, hynny yw, mae'r “dosbarthwr” ei hun yn ei chwarae ar ran y dirprwy a chleientiaid. I wneud hyn, nid oes angen iddo wybod y math o gleient na'u hoffterau o ran dirprwyon. Ar bob cam mae gêm, a defnyddir algorithm derbyn oedi hefyd.
Canfyddiadau
Yn ôl y canlyniadau efelychu, dangosodd y dull gan ddefnyddio theori gêm effeithlonrwydd uwch o'i gymharu â systemau ffordd osgoi clo hysbys.
Cymhariaeth â gwasanaeth rBridge VPN
Ar yr un pryd, mae gwyddonwyr wedi nodi sawl pwynt pwysig a all effeithio ar ansawdd gweithrediad systemau o'r fath:
- Waeth beth fo'r strategaeth sensoriaid, rhaid diweddaru'r system ar gyfer goresgyn blocio yn gyson gyda dirprwyon newydd, fel arall bydd ei heffeithiolrwydd yn lleihau.
- Os oes gan sensoriaid adnoddau sylweddol, gallant gynyddu effeithlonrwydd blocio trwy ychwanegu asiantau chwilio dirprwyol a ddosberthir yn ddaearyddol.
- Mae'r cyflymder y mae dirprwyon newydd yn cael eu hychwanegu yn hanfodol i effeithiolrwydd y system ar gyfer goresgyn blocio.
Dolenni a deunyddiau defnyddiol o :
Ffynhonnell: hab.com