Migration of Tasks in Interconnection networks Based on the Star Graph

Document Type

Article

Publication Date

12-1995

Publication Title

Journal of Parallel and Distributed Computing

Volume

31

First page number:

166

Last page number:

173

Abstract

The hierarchy of the star graph allows the assignment of its special subgraphs (substars), which have the same topological features as the original graph, to a sequence of incoming tasks. The procedure for task allocation in the star graph can be done using the star code and the allocation tree constructed based on this code. In this paper, the optimal set of codes which can collectively recognize a set of distinct substars is derived. It is shown that using only (n − 1) codes, almost half of the existing substars in an n-dimensional star is recognizable for n ≤ 9. When relinquishment of tasks is considered, task migration could potentially improve the utilization of network resources by reducing/eliminating the fragmentation caused as a result of task deallocation. A deadlock-free procedure is presented to migrate a task, distributed over the nodes of one substar, to the nodes of the other substar wherein: (i) subtasks travel in parallel via disjoint paths; (ii) the adjacency among the mapped nodes is preserved. The procedure can be made distributed with a slight modification. The work can be extended to other hierarchical networks based on permutation group.

Keywords

Cayley graphs; Computer algorithms; Computer network resources; Computer networks; Distributed operating systems (Computers); Routing (Computer network management)

Disciplines

Digital Communications and Networking | Electrical and Computer Engineering | Engineering | Signal Processing | Systems and Communications

Language

English

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

UNLV article access

Search your library

Share

COinS