Broadcasting and Multicasting in Heterogeneous Networks
Date Issued
2009
Date
2009
Author(s)
Su, Yu-Hsuan
Abstract
The thesis concerns the problems related to the broadcasting and multicasting in heterogeneous networks. A heterogeneous network is a network connecting workstations with different operating systems and communication protocols. Thus the times to communicate between any pair of workstations are different. A heterogeneous network is represented by a weighted graph G = (V,E), in which V (G) represents a set of workstations and each edge (u, v) in E(G) represents a connection between two adjacent workstations. The weight of each edge represents the transmission time when transmitting messages between two adjacent workstations. In heterogeneous networks, each communication link may have different message transmission time, and each workstation may have connection time to set up the message transmission. We assume that the message transmission model follows the postal model. The postal model assumes that the sender requires one unit of time to set up the connection with an adjacent vertex. After the sender sets up the connection, the sender is allowed to transmit the messages to set up another connection to the next receiver while the sender is still transmitting the messages to the previous receiver.he message transmission is said to be completed after the sender completes transmitting the messages to the receiver, and the receiver cannot pass the messages until the sender completes the transmission. Moreover, we assume that the message transmission between two adjacent vertices is full-duplex, i.e., the sender and receiver can exchange the messages between them. We consider the broadcasting and multicasting problems in a heterogeneous tree network. The broadcasting problem is to find a broadcast center such that the broadcasting time from the broadcast center to all vertices in T is minimized. The multicasting problem is to broadcast messages from a subset of vertices A in V (T) to another subset of vertices B in V (T) in optimal time such that each vertex in B receives all the messages of the vertices in A. In this thesis, we propose linear-time algorithms for the broadcasting and multicasting problems, respectively, in a heterogeneous tree network following the postal model.
Subjects
algorithm
broadcast
communication protocol
heterogeneous network
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R96943111-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):9c9f8a1260bb10adb246f4d5cdd42a7f