Login | Register

On Near Optimal Time and Dynamic Delay and Delay Variation Multicast Algorithms

Title:

On Near Optimal Time and Dynamic Delay and Delay Variation Multicast Algorithms

Terzian, Meghrig (2017) On Near Optimal Time and Dynamic Delay and Delay Variation Multicast Algorithms. PhD thesis, Concordia University.

[img]
Preview
Text (application/pdf)
Terzian_PhD_S2018.pdf - Accepted Version
Available under License Spectrum Terms of Access.
7MB

Abstract

Multicast is one of the most prevalent communication modes in computer networks. A plethora of systems and applications today rely on multicast communication to disseminate traffic including but not limited to teleconferencing, videoconferencing, stock exchanges, supercomputers, software update distribution, distributed database systems, and gaming.

This dissertation elaborates and addresses key research challenges and problems related to the design and implementation of multicast algorithms. In particular, it investigates the problems of (1) Designing near optimal multicast time algorithms for mesh and torus connected systems and (2) Designing efficient algorithms for Delay and Delay Variation Bounded Multicast (DVBM).

To achieve the first goal, improvements on four tree based multicast algorithms are made: Modified PAIR (MPAIR), Modified DIAG (MDIAG), Modified MIN (MMIN), and Modified DIST (MDIST). The proof that MDIAG generates optimal or optimal plus one multicast time in 2-Dimensional (2D) mesh networks is provided. The hybrid version of MDIAG (HMDIAG) is designed, that gives a 3-additive approximation algorithm on multicast time in 2D torus networks. To make HMDIAG applicable on systems using higher dimensional meshes and tori, it is extended and the proof that it gives a (2n-1)-additive approximation algorithm on multicast time in nD torus networks is given.

To address the second goal, Directional Core Selection (DCS) algorithm for core selection and DVBM Tree generation is designed. To further reduce the delay variation of trees generated by DCS, a k-shortest-path based algorithm, Build Lower Variation Tree (BLVT) is designed. To tackle dynamic join/leave requests to the ongoing multicast session, the dynamic version of both algorithms is given that responds to requests by reorganizing the tree and avoiding session disruption. To solve cases where single-core based algorithms fail to construct a DVBM tree, a dynamic three-phase algorithm, Multi-core DVBM Trees (MCDVBMT) is designed, that semi-matches group members to core nodes.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Terzian, Meghrig
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science
Date:16 October 2017
Thesis Supervisor(s):Harutyunyan, Hovhannes A.
ID Code:983358
Deposited By: MEGHRIG TERZIAN
Deposited On:05 Jun 2018 15:02
Last Modified:05 Jun 2018 15:02
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top