Search

This paper introduces a new type of Cayley graphs for building large-scale interconnection networks, namely $\mathit{WG}_{n}^{2m}$ , whose vertex degree is m+3 when n≥3 and is m+2 when n=2. A routing algorithm for the proposed graph is also presented, and the upper bound of the diameter is deduced as ⌊5n/2⌋. Moreover, the embedding properties and maximal fault tolerance are also analyzed. Finally, we compare the proposed networks with some other similar network topologies. It is found that $\mathit{WG}_{n}^{2m}$ is superior to other interconnection networks because it helps to construct large-scale networks with lower cost.

Efficient data processing techniques are needed in Wireless Sensor Networks (WSNs) to handle issues related to limited resources, e.g. energy, memory, bandwidth, as well as limited connectivity. Self-organizing and cooperative algorithms are thought to be the optimal solution to overcome these limitations. In this paper, we present the Virtual Cayley Protocol, a virtual relative position based efficient routing protocol that also provides means for data operation, e.g. insert, get, and delete, as known from typical Distributed Hash Table (DHT) services. The key contributions of this protocol are independence of real location information by relying on relative positions of neighboring nodes, short virtual paths because direct neighbors are in their vicinity, and high scalability because only information about direct neighbors is needed for routing. Furthermore, Cayley inherently prevents dead-ends and it is easy to be implemented. Cayley is a generalization of the Virtual Cord Protocol (VCP) and has more robust and efficient routing.

Let @C be a connected simple graph, let V(@C) and E(@C) denote the vertex-set and the edge-set of @C, respectively, and let n=|V(@C)|. For 1@?i@?n, let e"i be the element of elementary abelian group Z"2^n which has 1 in the ith coordinate, and 0 in all other coordinates. Assume that V(@C)={e"i|1@?i@?n}. We define a set @W by @W={e"i+e"j|{e"i,e"j}@?E(@C)}, and let Cay"@C denote the Cayley graph over Z"2^n with respect to @W. It turns out that Cay"@C contains @C as an isometric subgraph. In this paper, the relations between the spectra of @C and Cay"@C are discussed. Some conditions on the existence of Hamilton paths and cycles in @C are obtained.

Metacyclic graphs, which include supertoroids as a subclass, have been shown to possess interesting properties and potential applications in implementing moderate-to large-size parallel processors with fairly small node degrees. Wu, Lakshmivarahan, and Dhall (J. Parallel Distrib. Comput. 60 (2000), pp. 539-565) have described a deterministic, distributed routing scheme for certain subclasses of metacyclic graphs. However, they offer no proof that the scheme is a shortest-path routing algorithm and do not indicate whether or how their scheme may be extended to the entire class of metacyclic graphs. In this paper, we provide a near-shortest-path, deterministic routing algorithm that is applicable to any metacyclic graph and derive a bound for the diameter of such graphs.

A number of low degree and, thus, low complexity, Cayley-graph interconnection structures, such as honeycomb and diamond networks, are known to be derivable by systematic pruning of 2D or 3D tori. In this paper, we extend these known pruning schemes via a general algebraic construction based on commutative groups. We show that, under certain conditions, Cayley graphs based on the constructed groups are pruned networks when Cayley graphs of the original commutative groups are kD tori. Thus, our results offer a general mathematical framework for synthesizing and exploring pruned interconnection networks that offer lower node degrees and, thus, smaller VLSI layout and simpler physical packaging. Our constructions also lead to new insights, as well as new concrete results, for previously known interconnection schemes such as honeycomb and diamond networks

Alternating group graphs AGn, studied by Jwo and others, constitute a class of Cayley graphs that possess certain desirable properties compared with other regular networks considered by researchers in parallel and distributed computing. A different form, AN n, of such graphs, proposed by Youhou and dubbed alternating group networks, has been shown to possess advantages over AGn. For example, ANn has a node degree that is smaller by a factor of about 2 while maintaining a diameter comparable to that of AGn, is maximally fault-tolerant, and shares some of the positive structural attributes of the well-known star graph. In this paper, we characterize the distance between any two nodes in ANn and present an optimal (shortest-path) routing algorithm for this class of networks

The paper proposes a new routing algorithm for the Rotation-Exchange (RE n ) network. The length of the path between any two nodes given by the algorithm is not more than (3/8)n2+O(n), that is, the diameter of REnis not more than (3/8)n2+O(n). This improves on a (1/2)n2+O(n) routing algorithm proposed earlier.

We consider the relationships between Cayley digraphs and their coset graphs with respect to subgroups and obtain some general results on homomorphism and broadcasting between them. We also derive a general factorization theorem on subgraphs of Cayley digraphs by their automorphism groups. We discuss the applications of these results to well-known interconnection networks such as the butterfly network, the de Bruijn network, the cube-connected cycles network and the shuffle-exchange network.

"For original paper see R. Melhem, ibid., vol.56, p.502-10, (2007)". Recently, Melhem presented a "new" class of low-diameter interconnection (LDI) networks, (IEEE Trans. computers, Vol. 56, No. 4, pp. 502-510). We note that LDI networks are the same as the previously known generalized de Bruijn graphs, point out an error in the decomposition of LDI networks into permutations, and find that the correct decomposition scheme is an instance of arc coloring for coset graphs. Hence, we pursue a number of general results on arc coloring of coset graphs that can be applied to this particular decomposition problem as well as within many other contexts, including complete arc coloring and normality of coset graphs.

Many real networks, including those in social, technological, and biological realms, are small-world networks. The two distinguishing characteristics of small-world networks are high local clustering and small average internode distance. A great deal of previous research on small-world networks has been based on probabilistic methods, with a rather small number of researchers advocating deterministic models. In this paper, we further the study of deterministic small-world networks and show that Cayley graphs may be good models for such networks. Small-world networks based on Cayley graphs possess simple structures and significant adaptability. The Cayley-graph model has pedagogical value and can also be used for designing and analyzing communication and the other real networks.

Almost all recent researches on P2P systems focus on how to build a highly usable P2P overlay network. Researchers include small routing table, short query path and good robustness into their design objectives of overlay topology. In this paper, we present a general group theory method and define a new Cayley graph. Based on this Cayley graph, we propose a novel P2P overlay network called CHC, which has simple routing (searching) scheme and many other excellent properties such as short query path, high clustering and good robustness because of its symmetry. The performance is evaluated by simulation to show that CHC possesses shorter query path length and higher clustering and better robustness than several popular P2P overlay networks such as Chord and Ulysses.

A number of Cayley-graph interconnection structures, such as cube-connected cycles, butterfly and biswapped networks, are known to be derivable by unified group semidirect product construction. In this paper, we extend these known group semidirect product constructions via a general algebraic construction based on group semidirect product. We show that under certain conditions, graphs based on the constructed groups are also Cayley graphs when graphs of the original groups are Cayley graphs. Thus, our results present a general mathematical framework-symmetry for synthesizing and exploring interconnection networks that offer many excellent properties such that lower node degrees, and thus smaller VLSI layout and simpler physical packaging of the same size and lower diameters, and thus lower delay of networks . Our constructions also lead to new insights, as well as new concrete results, for previously known interconnection schemes such as cube-connected cycles and biswapped networks.

A number of Cayley-graph interconnection structures, such as cube-connected cycles, butterfly and biswapped networks, are known to be derivable by unified group semidirect product construction. In this paper, we extend these known group semidirect product constructions via a general algebraic construction based on group semidirect product. We show that under certain conditions, graphs based on the constructed groups are also Cayley graphs when graphs of the original groups are Cayley graphs. Thus, our results present a general mathematical framework for synthesizing and exploring interconnection networks that offer many excellent properties such that lower node degrees, and thus smaller VLSI layout and simpler physical packaging of the same size and lower diameters, and thus lower delay of networks . Our constructions also lead to new insights, as well as new concrete results, for previously known interconnection schemes such as cube-connected cycles and biswapped networks.

Many real-life networks, such as the WWW, biological realms, and social networks are small-world networks. Most previous researches on small-world networks have been based on probabilistic methods. In this paper, we present a general method by using Cayley graph to build deterministic small-world networks. We also analyze the cluster topology of the Cayley graph with small world properties by constructing its left Coset graph. This method has great value in constructing interconnection networks model and analyzing many other real network models.

Almost all recent researches on P2P system focus on how to build a highly usable P2P overlay network. Small routing table, short query path and robustness are included into their design objectives of overlay topology. In this paper, we define a new Cayley graph and propose a novel P2P overlay network CayleyChord based on it. The new overlay network has many excellent properties such as small routing table and short query path and high clustering and robustness. Our system has simpler routing (searching) and many other excellent properties than the most former systems such as Chord and Ulysses because of its symmetry. The performance is evaluated in this paper, indicating that CayleyChord can reach low routing table size and query path length. Furthermore, the robustness of CayleyChord based on the new Cayley graph model is also better than most the P2P overlay networks recently proposed.

Almost all recent researches on P2P system focus on how to build a highly usable P2P overlay network. In this paper, we present a general group theory method and define a new Cayley graph, and based on this Cayley graph, a novel P2P overlay network EBu is proposed and has many excellent properties such as small routing table and short query path and high clustering. Our system has simpler routing (search) and many other properties than the most former systems because of its symmetry. The performance is also evaluated in this paper.

Nodes in the hexagonal mesh and torus network are placed at the vertices of a regular triangular tessellation, so that each node has up to six neighbors. The routing algorithm for the Hexagonal Torus is very complicated, and it is an open problem by now. Hexagonal mesh and torus are known to belong to the class of Cayley digraphs. In this paper, we use Cayley-formulations for the hexagonal torus, along with some result on subgraphs and Coset graphs, to develop the optimal routing algorithm for the Hexagonal Torus, and then we draw conclusions to the network diameter of the Hexagonal Torus.

In addition to searching, browsing is yet another requirement of P2P file sharing systems. Nevertheless, none of the recent P2P DHTs can closely connect peers with the same interests together so that it is not practical to provide browsing service in such systems. In this paper, we define a new cayley graph to support logical grouping, and based on this cayley graph, a set of P2P DHT protocols which is suitable for providing file browsing service is also designed. Performance evaluation indicates that the new protocols can reach the theoretical lower bound of routing table size and query path length. Furthermore, the robustness of ComNET is also better than most of the P2P DHTs recently proposed.

As interconnection architectures, the regular six-degree hexagonal networks and the regular three-degree honeycomb networks have been widely investigated. For the lack of a proper addressing schema, some published routing algorithms are very complicated and the topological properties of some complex hexagonal and honeycomb related architectures are not well known. In this paper, a unified addressing schema for hexagonal and honeycomb meshes is proposed; two Cayley graphs isomorphic to the two meshes are presented as a formal foundation for the addressing schema. Using the suggested addressing schema, simple distance formulas and concise shortest-path routing algorithms of the two meshes are developed. The routing algorithms may be directly applied in real interconnection networks such as cellular networks. The models based on the unified addressing schema and the two isomorphic Caylay graphs established a concise and elegant foundation to investigate complex hexagonal and honeycomb related networks

In this short communication, we extend the known relationships between Cayley digraphs and their subgraphs and coset graphs with respect to subgroups and obtain some general results on homomorphism and distance between them. Intuitively, our results correspond to synthesizing alternative, more economical, interconnection networks by reducing the number of dimensions and/or link density of existing networks via mapping and pruning. We discuss applications of these results to well-known and useful interconnection networks such as hexagonal and honeycomb meshes.

In this note we obtain a simple expression of any finite group by means of its generating set. Applying this result we partly solve a conjecture on diameters of Cayley graphs proposed by Babai and Seress. We also obtain some other conclusions on diameters on Cayley graphs.

Despite numerous interconnection schemes proposed for distributed multicomputing, systematic studies of classes of interprocessor networks, that offer speed-cost tradeoffs over a wide range, have been few and far in between. A notable exception is the study of Cayley graphs that model a wide array of symmetric networks of theoretical and practical interest. Properties established for all, or for certain subclasses of, Cayley graphs are extremely useful in view of their wide applicability. In this paper, we obtain a number of new relationships between Cayley (di)graphs and their subgraphs and coset graphs with respect to subgroups, focusing in particular on homomorphism between them and on relating their internode distances and diameters. We discuss applications of these results to well-known and useful interconnection networks such as hexagonal and honeycomb meshes as well as certain classes of pruned tori.

Recent wireless systems research has focused on building highly usable data searching in wireless overlay networks. Short query paths, small routing tables, and robustness constitute the most prominent design objectives for the overlay topology. In this paper, we introduce a general group theoretic method and define a new Cayley graph. We then use these constructs to derive a novel wireless overlay structure. WCayleyCCC, our proposed overlay network, has many desirable features, including short query paths, compact routing tables, high clustering, and robustness. Because of its symmetry, our design offers simpler routing (searching) and several other desirable properties compared with many previously proposed wireless overlay networks, such as MChord. Performance evaluation results, reported in this paper, quantify the advantages of WCayleyCCC in terms of query path length, routing table size, clustering, and robustness relative to some recent proposals. WCayleyCCC is particularly useful in distributed computing under relatively stable conditions such as wireless mesh networks.