et preparerad virtuell miljö (NVE) [1, 2], även känd som distribuerad virtuell miljö, är ett relativt nytt fält som kombinerar 3D-grafik med nätverk för att ge simulerade men ändå uppslukande upplevelser för människor över hela världen. NVEs har sitt ursprung på 1980-talet med militära simulatorer [3] och har sedan dess utvecklats till dagens Massively Multiplayer Online Games (MMOGs) [4], där hundratusentals människor interagerar samtidigt i fantasivärldar. I början av 2006 har den mest populära titeln, World of Warcraft, lockat mer än sex miljoner abonnenter inom två år, medan spelet Lineage också har mer än fyra miljoner abonnenter över hela världen. MMOG genren har vuxit snabbt sedan starten i mitten av 1990-talet, vilket gör den till en multimiljard dollar verksamhet och en stor Internet ansökan [5]. Mer än 100.000 topp samtidiga användare rapporteras ofta för stora MMOGs, vilket gör skalbarhet en definierande egenskap. NVE skalbarhet är i grunden en resursfråga och avgörs av om systemet har tillräckliga resurser för att kontinuerligt kunna ta emot nya deltagare. Befintliga serverbaserade arkitekturer utgör dock inneboende skalbarhetsbegränsningar och betydande kostnader. Även om stora ansträngningar har gjorts för att förbättra skalbarheten, finns det ännu inget verkligt system som skulle kunna stödja mer än en miljon samtidiga användare. Storskaliga NVE:s popularitet och snabba tillväxt, såsom MMOG:s, kommer sannolikt att innebära allvarliga utmaningar för befintliga nätverk och arkitekturer inom den närmaste framtiden. Å andra sidan har en ny klass av peer-to-peer-tillämpningar (P2P) som försöker förverkliga storskaliga NVEs nyligen framträtt som ett alternativ. P2P-tillämpningar distribueras system där varje nod kör samma programvara [6]. De skiljer sig från rutnäts databehandling i och med att de grundläggande enheterna är varudatorer i stället för välförsedda anläggningar. Även om de tidiga P2P-system som antogs punkt-till-punkt topologier som skalas dåligt, P2P fildelning gjord av miljontals noder (t.ex., Gnutella och Kazaa) har offentliggjort skalbara P2P-system, som också inkluderar betydande ny forskning på distribuerad hash tabell (DHT) [6], där en given nyckel kartläggs till en nod och kan sökas effektivt (till exempel, filer att hittas utan några centraliserade kataloger). P2P-system lovar skalbarhet och överkomlighet genom att föra användarresurser till systemet och består av hårdvara. Men de skapar också nya utmaningar som topologi underhåll (som noder kan gå med eller lämna när som helst) och effektiv innehållssökning (som den globala topologin är okänd för varje nod). Denna artikel utökar vårt tidigare arbete [7] och identifierar ett framväxande fält som tillämpar P2P-teknik för att förverkliga NVEs på skalor som inte går att uppnå genom befintliga arkitekturer. En enkel och effektiv design baserad på Voronoi diagram [8], som kallas Voronoi-baserade Overlay Network (VON), presenteras också. VON utnyttjar lokala användarintressen för att upprätthålla P2P topologin med små overhead, och uppnår hög skalbarhet genom att begränsa resursanvändning vid varje deltagande nod. Denna artikel ger en analys av NVE skalbarhetsproblem, identifierar den framväxande P2P-baserade NVE (P2P-NVE) forskning, och presenterar en beskrivning av VON. I följande avsnitt ger vi först bakgrunden till NVE-systemen och förklarar skalbarhetsproblemet när det gäller P2P-anpassning, följt av granskningar av de senaste P2P-NVE-förslagen. Därefter förklarar vi VON:s designmotiv och procedurer och demonstrerar dess skalbarhet, överensstämmelse och tillförlitlighet med simuleringar. Diskussioner om Vons egenskaper och jämförelser med andra system görs innan vi avslutar denna artikel med en sammanfattning och några framtidsperspektiv. NVE är syntetiska världar där varje användare antar en virtuell identitet (kallas avatar) för att interagera med andra mänskliga eller datorspelare. Användare kan utföra olika åtgärder såsom att flytta till nya platser, titta runt i omgivningen, använda objekt, eller engagera sig i samtal och N Shun-Yun Hu, Institute of Physics, Academia Sinica, Taiwan Jui-Fa Chen och Tsu-Han Chen, Tamkang University Skalbarheten av storskaliga nätverkade virtuella miljöer (NVEs) såsom dagens Massively Multiplayer Online Games (MMOGs) står inför inneboende begränsningar som åläggs av klient-server arkitekturer. Vi identifierar en framväxande forskningsriktning som tillämpar peer-to-peer (P2P) nätverk för att förverkliga mer skalbara och prisvärda NVEs. Den centrala frågan för P2P-baserade NVE (P2P-NVE) system är att korrekt och effektivt upprätthålla topologin för alla deltagande kamrater genom att lösa grannen upptäckt problem. Vi föreslår också Voronoi-baserade Overlay Network (VON), en enkel och effektiv design som upprätthåller P2P-topologin på ett fullt distribuerat, låglatent och meddelandeeffektivt sätt. Simuleringsresultat visar att genom att begränsa pernoden resursförbrukning kan VON i grunden vara mer skalbar än befintliga metoder samtidigt som man uppnår hög topologikonsistens och tillförlitlighet. Ett antal frågor är involverade i byggandet av ett NVE-system; flera beskrivs på följande sätt. Överensstämmelse - Eftersom NVE är gemensamma miljöer är det viktigt att varje deltagare uppfattar samma tillstånd och händelser. Överensstämmelse i NVE:er avser vanligtvis konsekventa objekttillstånd och händelsebeställningar [1], som upprätthålls genom överföring av händelsemeddelanden. Händelsemeddelanden kan dock försenas eller gå förlorade, vilket gör konsekvensen till en utmanande fråga. Responsiveness -För att ge en känsla av naturliga interaktioner, fördröjningen mellan en användares åtgärder och observerbara konsekvenser bör minimeras trots nätverkslatens. NVE-system har således ett realtidskrav. Latenttoleransen kan dock vara beroende av tillämpningen [9]. Responsibilitet och konsekvens brukar ses som kompromisser, eftersom väntan på sent eller återsändning av saknade paket resulterar i förseningar. Skalbarhet -Den verkliga potentialen hos NVEs ligger i att nätverka ett stort antal människor, vilket gör skalbarhet en viktig aspekt för framtida NVEs. Det är också viktigt när det gäller tjänstetillgänglighet (dvs. om systemen kan upprätthålla snabb användningsökning) och innehållsmöjligheter (dvs. stor deltagarstorlek möjliggör nya typer av konstruktioner och interaktioner). Persistency -Innehåll inom NVEs (t.ex. virtuella objekt och datatecken) kan behöva existera ihållande för att ge en känsla av realism. Nuvarande MMOGs ger ihållande-världsupplevelser som fungerar 24 timmar om dygnet, där användare kan hålla virtuella objekt och spelarprofiler mellan inloggningssessioner via centraliserad databaslagring. Tillförlitlighet -När NVEs blir skalbara och ihållande, kommer de också att behöva upprätthålla hårdvara eller programvara misslyckanden, för att säkerställa tjänstetillgänglighet och smidiga användarupplevelser. Tillförlitliga och feltoleranta system kommer att öka i betydelse i takt med att NVE blir mer serviceorienterade. Säkerhet -Många typer av NVE underhåller användarkonton och tillåter tävlingar mellan användare. Säkerhet är därför viktigt för att säkerställa rättvisa under interaktion och integritet av användarinformation. Det betonas särskilt i kommersiella system. Vårt fokus ligger på skalbarhet, eftersom det möjliggör nya designmöjligheter. Ansvarsfullhet och tillförlitlighet diskuteras också, men konsekvens beaktas endast för användarpositioner, medan uthållighet och säkerhet ligger utanför vår räckvidd. Två huvudsakliga typer av resurser i NVE-system är processkraft och bandbredd [1]. Eftersom bandbredd tenderar att vara den viktigaste resurs flaskhals, kommer det att vara vårt fokus (se [4], s. 228). MMOG är en viktig och utan tvekan den mest framgångsrika undergruppen av NVE. För att ge en underhållande upplevelse fokuserar MMOGs mer på speldesign, kontinuerliga leveranser av spelinnehåll och säkerhet än andra typer av NVEs [2, 4]. Speltillstånd för användare, virtuella objekt, terräng och datorstyrda tecken upprätthålls på servrarna. Typiska nätverksmeddelanden inkluderar miljöförändringar (t.ex. dörröppning), rörelser, interaktioner (t.ex. chatt, handel eller kamp) och systemtjänster (t.ex. inloggning, vänsökning, programvara eller innehållsuppdateringar) [4, 9]. Men i denna artikel fokuserar vi på positionsuppdateringar, eftersom de representerar den mest grundläggande och största andelen av meddelandetrafik [10] (se även [4], s. 278). Skalbarhet i denna artikel avser huruvida ett NVE-system kan rymma ett brett spektrum av samtidiga användare utan att äventyra viss servicekvalitet (t.ex. tillräckliga uppdateringar av meddelanden som säkerställer enhetlighet eller lyhördhet). Frågan i centrum är om systemets resurser inte utarmas när nya användare ansluter sig. I en generaliserad NVE kan användarna konceptuellt ses som koordinatpunkter på ett 2D-plan (som noder), var och en med ett synlighetsområde som kallas intresseområde (AOI). AOI är en grundläggande NVE koncept, som även om många användare och händelser kan finnas i systemet, varje användare - som i den verkliga världen - bara påverkas av närliggande användare eller händelser. AOI anger således ett utrymme för information som systemet bör ge varje användare. För enkelhetens skull antar vi att AOI är en cirkel centrerad på användaren, och noder rör sig på diskreta tidssteg. Det centrala kommunikationsproblemet är alltså: hur får varje nod relevanta meddelanden (genererade av andra noder) inom sin AOI när de rör sig runt? Den tidigaste lösningen på detta problem är att helt enkelt sända uppdateringar, eller ansluta alla på ett punkt-till-punkt sätt. är de klassiska exemplen. Sändning är endast tillämplig på LAN, medan punkt-till-punkt inte är skalbar när anslutningar växer på O(n 2 ) med användarstorlek. Kund-server arkitekturer förbättra situationen, där varje användare kommunicerar med en centraliserad server (t.ex. ). Relevanta meddelanden vidarebefordras av servern, vilket minskar meddelandetrafiken till O(n) (Fig. 1a).............................................................................................. Servern blir dock flaskhalsen och dess resurstillgänglighet dikterar systemets skala. För att öka serversidans resurser utformas serverkluster för att kombinera flera servrar på ett höghastighetsLAN med stor bandbredd för extern anslutning (t.ex. [12], RING [13] ). I motsats till metoder för "öka resurser" försöker strategierna för "minska konsumtionen" minska meddelandeöverföringar genom paketkomprimering eller aggregation (dvs. att kombinera flera meddelanden till en grov representation [14] ), eller genom räntehantering [15], som försöker filtrera bort irrelevanta meddelanden (dvs. de som genereras utanför en användares AOI bör inte tas emot). Räntornas förvaltning är av särskild betydelse, som kom- ) var och en med en förspecificerad flersändningsadress. En nod skickar meddelanden till adressen till sin bosatta grupp, och prenumererar på grupper som sammanfaller med dess AOI. Helst varje nod skulle då bara bearbeta en ändlig mängd relevanta meddelanden, vilket gör systemet mer skalbart (Fig. 1b)................................................................................................ Olika mönster skiljer sig huvudsakligen i grupperingsmetoder och abstraktion som tilldelas en adress (t.ex., NPSNET delar upp världen i sexkantiga celler, medan VELVET tilldelar varje användare en multicast adress). Multicast har två stora fördelar: meddelanden skickas bara en gång till nätverket, och filtreras av infrastrukturen utan värdbehandling. De mottagna meddelandena kan dock vara irrelevanta eller otillräckliga om gruppdefinitionerna är felaktigt definierade [21]. Det allvarligaste problemet är dock att multicast inte har använts i stor utsträckning och att relativt få adresser finns tillgängliga för storskaliga tillämpningar. Multicast i flera lager [22] har föreslagits för att ta itu med bristen på multisändning i flera lager genom att bygga överlagrade nät. Noder självorganisera till multicast träd och leverera meddelanden till många mottagare via nodreläer. Det är dock fortfarande svårt att definiera lämpliga multicast-grupper, medan latensen på grund av reläer kanske inte är lämplig för NVE:s realtidskrav. Dagens MMOGs antar överväldigande serverkluster på grund av väl understötta säkerhets- och ihärdighetsmekanismer. De står dock inför tre skalbarhetsproblem: otillräckliga totala resurser, hög användartäthet och överdriven kommunikation mellan servrar. Den första frågan behandlas genom att tillhandahålla mer hårdvara. MMOG:s trafikanalys [10] visar dock att mänskliga beteenden orsakar sprickbildning i trafiken på ett sådant sätt att omedelbar resursanvändning kan vara mycket högre än genomsnittet. Det är därför troligt att det kommer att ske en alltför stor föranstaltning. Även med tillräckliga totala resurser, brukade användare ofta koncentrera sig på hotspots där intressanta händelser inträffar (kallas användare trängsel eller flockning), och överbelasta servrar som hanterar hotspots. Även server-kluster belastningsbalansering har föreslagits [23], kan migrera användare till andra servrar framkalla den tredje frågan om överdriven interserver kommunikation som förbrukar bandbredd och införa latens (t.ex., när överföra användarprofiler över servrar, eller när stödja interaktioner mellan användare på olika servrar). P2P-konstruktioner kan lindra dessa problem av följande skäl: • Resurser förs in i systemet med varje ytterligare nod sammanfogad. • Noder kan individuellt bestämma och minska sina meddelanden omfattning när användarens densitet ökar. • Meddelandeutbyte endast med relevanta (dvs. AOI) grannar kan effektivt begränsa internode trafik. På grund av NVEs unika krav hävdar vi att P2P-NVE utgör en ny klass av P2P-system värda att studera. En anmärkningsvärd skillnad mellan P2P-NVE och DHT eller fildelning är att problemet med innehållssökning förenklas avsevärt: eftersom varje nods AOI är begränsad, är det önskade innehållet lokaliserat och lätt identifieras som meddelanden som genereras av andra noder inom AOI. Detta skiljer sig från fildelning, där önskat innehåll kan vara på någon nod. Den centrala innehållssökningen i P2P-system blir därmed en granne upptäckt problem, och kan anges som: givet en nod position och AOI, hitta alla angränsande noder inom AOI. NVE:s konstruktionskriterier omvandlas också till följande frågor och mått. Överensstämmelse -Som konsekvens frågor andra än användarpositioner är utanför vår räckvidd, här fokuserar vi på topologi konsistens [24], som kan definieras som procentandelen av korrekt kända AOI grannar (t.ex., för en nod som är medveten om fyra av fem AOI grannar, topologi konsistens är 80 procent). Ett annat användbart mått är drivavstånd [19], definierat som avståndet (i absolut värde) mellan de observerade och faktiska koordinaterna för en nod. Två nära relaterade begrepp är global konnektivitet (dvs. om överlagringen är helt ansluten) och lokal medvetenhet (dvs. om varje nod är fullt medveten om sina AOI-grannar) [25]. Att säkerställa dessa egenskaper utgör en utmaning för alla P2P-NVE. Responsiveness -För att uppfylla kravet i realtid, meddelande latency bör minimeras medan bandbredden bör vara effektiv. Helst bör noder ansluta direkt till sina AOI grannar för att minimera latens. Skalbarhet -I en P2P-miljö är de viktigaste skalbarhetsfrågorna huruvida resursanvändning begränsas vid varje nod och om potentiella trafiksprickor kan hanteras. De genomsnittliga och maximala överföringsstorlekarna på varje nod inom en period är därför användbara indikatorer. Tillförlitlighet -Som paketförlust, fördröjning och nodfel kan negativt påverka topologikonsistensen, är robusthet mot dessa problem den viktigaste tillförlitlighetsfrågan. Återhämtning steg, definieras som antalet tidssteg för att återhämta sig till 100 procent topologi konsistens, kan vara en användbar metriska. P2P-NVEs kan potentiellt vara mer skalbara, lyhörda och tillförlitliga än serverbaserade lösningar, medan det återstår för framtida forskningsområden att ge tillräckligt stöd för konsekvens, uthållighet och säkerhet i en P2P-miljö. Vi beskriver och kategoriserar nu några nya P2P-NVE-förslag enligt följande. Förbättrad punkt-till-punkt -Nya meddelande-filtrering tekniker har utformats för punkt-till-punkt arkitektur, där alla noder känner varandra. Tanken är att tillåta överföring endast under ömsesidig synlighet. Uppdateringsfria regioner [26] definierar par av ömsesidigt osynliga regioner i NVE. Meddelandeutbyte behövs inte om två noder stannar inom sina respektive UFR, och återupptas endast om en av dem kliver ut. Sedan omförhandlas antingen UFR (om visibiliteten fortfarande är blockerad) eller så börjar positionsbytet. UFR skalas dock inte, eftersom varje nod måste förhandla med alla andra noder. Dessutom kan överdrivna budskap utbytas om många grannar är ömsesidigt synliga (t.ex. när sevärdheter inte blockeras eller trängsel förekommer). Gränser [27] ger en förbättrad strategi för UFR, men lider av samma begränsningar. DHT-baserad – betydande forskningsinsatser har ägnats åt intressehantering via multicast. Eftersom multicast inte används i stor utsträckning ger multicast i flera lager en lösning. SimMud [9] använder Scribe, en multi-lager multicast byggd på DHT Pastry, och delar NVE i vissa regioner med fast storlek. Varje region förvaltas av en befordrad supernode, som fungerar som roten till ett multigjutet träd. regionen och vidarebefordrar uppdateringarna till dem. Kopplingar upprätthålls mellan supernoder för att underlätta användarövergångar mellan olika regioner. Men, en super-node kan överväldigas av trängsel i regionen, och meddelande latens kan vara upp till flera sekunder på grund av reläer. För att minska latensen använder Zoned Federation [28] endast DHT för topologianslutning, medan vanliga noder ansluter direkt till regionens supernode. Men trängsel kan fortfarande vara en angelägenhet. Grann-List Exchange -Att upptäcka grannar utan att tillgripa centraliserade servrar eller super-nodes, kunskap från befintliga grannar kan utnyttjas. Kawahara m.fl. Beskriv ett fullständigt distribuerat system [24] där varje nod direkt ansluter med ett fast antal närmaste grannar och ständigt utbyter grannlistor för att upptäcka nya noder. Även om direkta anslutningar minimerar latency, konstant list utbyter ådrar överföring overheads. När de separeras av stora avstånd, noder kan också förlora ömsesidiga kontakter och orsaka overlay partitioner [24]. För att säkerställa global konnektivitet håller meddelandeutväxlingsprotokollet (MIP) [29] åtminstone en granne i var och en av de fyra kurvtagningsriktningarna på en nod. Men frekvensen av list utbyte är fortfarande en känslig kompromiss mellan granne upptäckt aktualitet och bandbredd användning. Ömsesidig anmälan -Neighbor-list utbyte kanske inte är bandbredd effektiv, eftersom en stor del av överföringen är överflödig. Ett bättre tillvägagångssätt är att meddela nya grannar endast när det är nödvändigt. Solipsis [25] är ett annat fullt distribuerat system, där varje nod ansluter till alla grannar inom sitt AOI. Grannar noder fungerar som "väktare" för annalkande utländska noder och granne upptäckt uppnås genom meddelanden från kända grannar. Eftersom Solipsis upprätthåller direkta förbindelser mellan grannar, minimeras latensen. För att säkerställa global konnektivitet måste varje nod finnas inuti polygonen (dvs. ett konvext skrov) som bildas av dess yttersta grannar. Men, granne upptäckt är ibland ofullständig, som inkommande noder kan vara okänd till direkt anslutna grannar. I andra fall krävs aktiva frågor när den inom-konvexa-hull egendom kränks, vilket saktar ner grannen upptäckt [30]. är en hybrid mellan klientserver och P2P-arkitektur. Noder organisera sig i olika grupper och hanteras av provisionerad hårdvara som kallas multicast reflektorer. Grupper skapas eller ändras av styrservrar, från vilka deltagande noder få kartläggningar mellan grupperna och multicast reflektorer. Noder prenumerera och skicka uppdateringar till multicast reflektorer av enskilda intressen, och upptäcka grannar via meddelanden förmedlas av multicast reflektorer. Strängt taget, klient-server hybrider är server-kluster varianter där den kombinerade bandbredden av specialiserade servrar bestämmer skalbarhetsgränsen. [32] är en intressant blandning av DHT, grannlista utbyte, och direkt överföring. NVE är uppdelad i sexkantiga celler (som NPSNET), och DHT används för att säkerställa global anslutning. Inom varje cell, en master nod upprätthåller en lista över slav noder och utbyter listan periodvis med angränsande mästare. Slavnoder meddelas om nya grannar av mästarna. För att undvika latens utbyter slavnoder meddelanden direkt mellan sig. Men valet av lämpliga mästare är en angelägenhet, särskilt när trängsel övervägs. Frekvensen av slav-node list utbyte är också en svår balans mellan bandbredd användning och granne upptäckt aktualitet, som i andra granne-lista utbytesprogram. Kund-Server Hybrid Olika P2P-NVE system skiljer sig i sin grad av decentralisering. I allmänhet, desto mer distribuerad design, desto mer lyhörd blir systemet, men detta sker på bekostnad av ökad bandbredd utnyttjande. Supernoder kan använda mindre bandbredd på bekostnad av sämre tolerans mot nodfel och trängsel. Andra skillnader inkluderar granne-upptäckt aktualitet och händelse-ordning stöd. Även om dessa konstruktioner är potentiellt mer skalbara än klient-server, korrekt och läglig grann upptäckt och användaren trängsel tolerans är fortfarande de vanligaste frågorna. Vi föreslår användningen av Voronoi diagram [8] för att lösa grannen upptäckt problem på ett fullt distribuerat, bandbreddseffektivt, och låg-latency sätt. Våra designmål är: skalbarhet, uppnås genom att begränsa per-node överföring, och lyhördhet, uppnås genom att kräva direkta anslutningar för alla datautbyten. Med tanke på ett antal punkter (kallas platser) på ett 2D-plan, en Voronoi diagram delar planet i samma antal Voronoi regioner (eller helt enkelt regioner), så att varje region innehåller alla punkter närmare regionens plats än någon annan plats (Fig. 2a)................................................................................................ Voronoi diagrammet definierar en rumslig relation mellan olika noder och kan användas för att hitta k-nearest granne på alla platser effektivt. Eftersom Voronoi-diagram har studerats i stor utsträckning och tillämpats på olika fält (t.ex. beräkningsgeometri och mobil databehandling), tar vi inte hänsyn till detaljerna i Voronoi-konstruktionen utan utgår från att det finns bra algoritmer. För vårt syfte är varje nod i VON representerad som en plats i Voronoi-diagrammet. För en given nod, definierar vi AOI grannar som de noder vars positioner är inom dess AOI. Omslutande grannar är noder vars regioner omedelbart omger den givna noden, och gränsgrannar är AOI grannar vars omslutande grannar kan delvis ligga utanför AOI (Fig. 2b)........................................................................................................... Varje nod upprätthåller en Voronoi diagram över alla AOI grannar och direkt ansluter dem för att minimera latens. Som bara några få grannar hålls, kostnaden för att upprätthålla en Voronoi diagram vid varje nod är låg. För att förhindra överläggning partition (dvs. grupper av noder blir ömsesidigt omedvetna om varandra), kräver vi också att varje nod att minimalt hålla sina omgivande grannar (som kan vara utanför AOI när angränsande noder är glesa). När en nod rör sig skickas positionsuppdateringar till alla anslutna grannar (dvs. AOI-grannar plus eventuella omgivande grannar utanför AOI). Grannen upptäckt görs via meddelanden från gränsgrannar, som de känner både den rörliga noden och andra noder utanför AOI (som råkar vara deras omslutande grannar). På detta sätt, potentiella AOI grannar upptäcks med ömsesidiga samarbeten. När en nod rör sig runt, kommer den ständigt att upptäcka nya noder och koppla bort dem som har lämnat sin AOI (såvida de inte omsluter grannar). En nod begränsar således kommunikationen med mestadels de verkliga AOI-grannarna, oberoende av systemets omfattning. Att hålla bandbreddsförbrukningen vid varje nod avgränsad är nyckeln till VON:s skalbarhet. En potentiell oro är att när trängsel inträffar (dvs., användare insamlingar som orsakar höga densiteter i noder, se centrum för justerbar AOI [20], så att noder med olika bandbredder kan individuellt bestämma sina optimala AOI radier. Vi tillämpar även dynamiska AOI-justeringar enligt tre enkla regler: • En nod krymper sin AOI när antalet anslutna grannar överskrider en förspecificerad anslutningsgräns. • AOI återställer till önskad storlek om antalet anslutna grannar återigen faller under gränsen. • För att säkerställa ömsesidig medvetenhet mellan noder, en nod kommer inte att koppla bort en granne vars AOI fortfarande täcker det, även om den grannen är utanför sin egen AOI. Vi beskriver nu VON:s tre huvudprocedurer (se [30] för pseudokoder). GÅ MED Förfarande - En anslutning nod först kontaktar gateway-servern (dvs. den första bootstrapping noden i VON) för ett unikt ID, sedan skickar en fråga med dess sammanfogande koordinater till någon befintlig nod (som kan vara gateway). Med hjälp av girig framåt kommer frågan så småningom att nå acceptorn (dvs. noden vars region innehåller den sammanfogande nodens koordinater, se bild. 3a ), som svarar genom att skicka en lista över gå nodes AOI och omsluta grannar. Samgående noden ansluter sedan till varje granne på listan och organiserar sina koordinater i en Voronoi diagram. Grannarna uppdaterar också sina Voronoi diagram för att redogöra för anslutning noden (Fig. 3b).................................................................. MOVE Procedure -När en nod rör sig, skickas positionsuppdateringar till alla för närvarande anslutna grannar. Om mottagaren är en gräns granne, det kommer att kontrollera om någon av dess omslutande grannar är nu synlig för, eller har blivit omslutande granne till, den rörliga noden (Fig. 4a)................................................................ Om nya grannar identifieras, skickas meddelanden till den rörliga noden för att initiera anslutningar. Under handskakningar med en ny granne sänder den rörliga noden också sin kunskap om den nya grannens omslutande grannar, som skulle bekräfta och meddela den rörliga noden om alla saknade. Den rörliga noden kommer också att koppla bort alla gräns grannar som har lämnat sin AOI (Fig. 4b)............................................................... Under varje tidssteg uppdateras Voronoidiagram vid alla noder för att återspegla den aktuella topologin. LEAVE Procedur -Den utgående noden kopplar helt enkelt bort (ingen skillnad görs mellan riktiga och onormala avvikelser från överlagsnätet, se bild. Detta anslag är avsett att täcka utgifter för tjänstemän och tillfälligt anställda som arbetar inom politikområdet rättsliga frågor och inrikes frågor. Berörda grannar kommer att uppdatera sina Voronoi diagram. Vid gränsgrannars avgångar lär man sig ersättningar via andra gränsgrannar som fortfarande är anslutna (Fig. 5b)................................................................................................ Betydande arbete har utförts med hjälp av Delaunay triangulation (den dubbla strukturen i Voronoi-diagram [8]) för att konstruera överlägg för applikationslager multicast (DT-overlay) [22]. DToverlay tillhandahåller ett skalbart protokoll där noderna endast använder lokal information för paket vidarebefordring. Kraven på multicast och NVE i applikationslager skiljer sig dock åt i viktiga aspekter: det förstnämnda syftar till att skicka data till potentiellt många mottagare, så att meddelandeleveransen kännetecknas av reläer mellan noder, men NVE:s egenskap i realtid kräver minimal latens (dvs. reläer bör undvikas om möjligt). Voronoi-diagrammet (eller Delaunay triangulation) används alltså annorlunda i VO (dvs. för att upptäcka nya grannar) än i DToverlay (dvs. för att härleda routingvägar). VON skiljer sig också från DT-överföring i minst två avseenden: • Den saknar DT-överföringens huvudsakliga nackdelar med hög latens från end till end och flera överföringar av samma data över en fysisk länk [22], eftersom alla överföringar är direkta. • Den tar hänsyn till konstanta nodrörelser, medan det inte finns någon motsvarighet till VON:s MOVE-förfarande i DT-overlays protokoll. VON liknar DT-overlay endast om alla noder bara ansluta med sina omslutande grannar och inte flytta. Voronoi diagram förenklar två svåra identifieringar i grannen upptäckt: noderna gör upptäckten beslut och den minimala uppsättningen anslutna grannar för att säkerställa com-plete upptäckt. Den förra löses av gränsgrannar, medan den senare genom att innesluta grannarna. För att utvärdera VON:s egenskaper utförs simuleringar med både fast och dynamisk AOI (kallas den grundläggande och dynamiska AOI, respektive dAOI-modellen, se tabell 1). Simuleringarna sker i mer än 3000 diskreta tidssteg, där noderna rör sig slumpmässigt med konstant hastighet. Eftersom användare i verkliga NVE inte distribuerar jämnt, placerar vi upp till 2000 noder inom ett 1200 × 1200 område för att simulera högdensitetsscenarier. Efter att ha gjort det möjligt för systemet att stabilisera för 200 steg, mäter vi överföringsstorleken per nod per sekund, förutsatt att 10 rörelser per sekund (för jämförelse är typiska uppdateringshastigheter för MMOGs 1-5 gånger/s [10], och 10-20 gånger/s för snabbspel). För enkelhetens skull antar vi konstant latens för alla simuleringar (dvs. meddelanden som skickas behandlas i nästa steg). Simuleringsresultaten presenteras med 95 procent konfidensintervall; VON:s egenskaper diskuteras enligt nedan. Skalbarhet - Figur 6 visar att de genomsnittliga transmissionerna per nod per sekund växer linjärt för den grundläggande och sublinjärt för dAOI-modellen. Överföringarna är dock avstängda om
Voronoi diagram är en matematisk konstruktion sådan att givet n noder på ett 2-D plan; dessa n noder kan partitionera planet till n icke-överlappande Voronoi regioner REF.
VON: a scalable peer-to-peer network for virtual environments
{'venue': 'IEEE Network', 'journal': 'IEEE Network', 'mag_field_of_study': ['Computer Science']}