Browse Prior Art Database

The Sneptree A Versatile Interconnection. Network

IP.com Disclosure Number: IPCOM000127942D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 18 page(s) / 51K

Publishing Venue

Software Patent Institute

Related People

Pey-yun Peggy Li: AUTHOR [+4]

Abstract

connection patterns are presented. The riiapping of a complete binary tree onto the Sneptree is proven to be optimal in section 3. Like a binary tree, the Sneptree can be laid out into an H-structure plane nicely. Section 4 presents a recursive method to construct the H-structure Sneptree. In section 5, a routing algorithm which routes a message from a leaf node to another leaf node is presented. At last, the comparison of the Sneptree and other similar networks and future research direction are discussed in the conclusion.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 18

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

The Sneptree A Versatile Interconnection. Network

wwte

Pey-yun Peggy Li and Alain J. Martin Computer Science Department Cal iforn~ia 1 nst.i.tute of Technology

51'94.: T R, :.85 .

The: research. described in this paper was sponsored by the Defense. Advanced Research Projects Agency., ARPA Order No. 3771, and mon~itared by the Office of Naval Research under contract number N00014-79-C.-0597

California Institute of Technology, connection patterns are presented. The riiapping of a complete binary tree onto the Sneptree is proven to be optimal in section 3. Like a binary tree, the Sneptree can be laid out into an H-structure plane nicely. Section 4 presents a recursive method to construct the H-structure Sneptree. In section 5, a routing algorithm which routes a message from a leaf node to another leaf node is presented. At last, the comparison of the Sneptree and other similar networks and future research direction are discussed in the conclusion.

2. Definition of the Sneptree

Definition: An n-level Sneptree is a complete binary tree of 2" - 1 nodes, links directed from root to leaves, augmented with 2' additional Snep links directed out of the leaves, such that each node has 4 incident links: 2 directed in and 2 directed out. Each node in the tree has an incoming Sneplink, except for the root, which has 2 incoming Sneplinks.

Notice that the Sneptree is defined to be a directed graph here for easier understanding. In the real implementation, the links should be bidirectional. Furthermore, we call the outgoing link which points to the left descendant of a node the "left link" and the one pointing to the right descendant the "right link" .

(Image Omitted: Figure 1. A three-level Sneptree)

There are many possible ways to connect those 2n Sneplinks. One example of a planar connec- tion is shown in Figure 1. This connection is not of particular interest because it ends up with a very unbalanced mapping for a highly unbalanced binary tree, such as a left skewed tree. Another type of Sneptree whose Sneplinks are connected to form two spanning cycles (i.e., Hamiltonian Cycles) (51 renders an optimal mapping for a left(right) skewed tree of any size
(i.e., a linear array). This special type of Sneptree is called cyclic Sneptree.

Definition: A cyclic Sneptrte is a Sneptree containing two link-disjoint spanning cycles. The "left cycle" contains only left links and the "right cycle" contains only right links.

Theorem 1. There are ((2ri-1 - 1)!12 connection patterns for the n-level cyclic Sneptree.

From Theorem 1, we prove that there are [(2n-1 - 1)!]Z connection patterns for the cyclic Sneptree. The interested readers are referred to the proof in Appendix A. Notice that many of

California Institute of Technology Page 1 Dec 31, 1985

Page 2 of 18

The Sneptree A Versatile Interconnection. Network

those connection patterns are isomorphic because the left and the right links are indisti...