Abstract-Delivering delay-sensitive data till en grupp mottagare med minimal latency är ett grundläggande problem för olika distribuerade applikationer. I detta dokument studerar vi multicast routing med minsta end-to-end fördröjning till mottagarna. Fördröjningen till varje mottagare i en multicast träd består av den tid som data spenderar i overlay länkar samt latens uppstår vid varje overlay node, som måste skicka ut en bit data flera gånger över en ändlig kapacitet nätverksanslutning. Den senare delen av förseningen, som är proportionell mot graden av noder i trädet, kan vara en betydande del av den totala förseningen som vi visar i tidningen. Ändå är det ofta ignoreras eller endast delvis tas upp av tidigare multicast algoritmer. Vi formulerar den faktiska fördröjningen till mottagarna i ett multigjutet träd och överväga att minimera genomsnittet och den maximala fördröjningen i trädet. Vi visar NP-hårdheten av dessa problem och visar att de inte kan approximeras i polynom tid till inom någon rimlig approximation förhållande. Vi presenterar sedan ett antal effektiva algoritmer för att bygga ett multicast träd där genomsnittet eller den maximala fördröjningen minimeras. Dessa algoritmer täcker ett brett utbud av overlay storlekar för båda versionerna av vårt problem. Effektiviteten hos våra algoritmer demonstreras genom omfattande experiment på olika verkliga datauppsättningar och med hjälp av olika overlay-nätverksmodeller. Resultaten bekräftar att våra algoritmer kan uppnå mycket lägre fördröjningar (upp till 60% mindre) och upp till storleksordningar snabbare drifttider (dvs. stödja större skalor) än tidigare minimal-fördröjning multicast metoder.
Multicast routing med minsta end-to-end fördröjning studeras i REF.
Minimum-delay overlay multicast
{'venue': '2013 Proceedings IEEE INFOCOM', 'journal': '2013 Proceedings IEEE INFOCOM', 'mag_field_of_study': ['Computer Science']}