Self-routing multicast network architecture

Details Self-routing multicast network architecture Self-routing multicast network architecture

1998-03-27

2001-03-13

Kizou, Hassan (Department: 2662)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

Reexamination Certificate

active

06201808

ABSTRACT:

BACKGROUND OF INVENTION
A. Field of Invention
The present invention relates to the field of communication networks, and more particularly to a self-routing multicast network architecture based on recursive network decompositions of reverse banyan multicast networks.
B. Description of Related Art
Multicast, or one-to-many, communication is one of the most important collective communication operations and is highly demanded in parallel applications as well as in other communication environments. Multicast, for example, is required to make updates in replicated and distributed databases. In addition, multiprocessor systems use multicasting for cache coherency to aid message passing, and multicasting is a critical operation for video/tele-conference calls and video-on-demands services in telecommunication environments. Those skilled in the art will recognize that providing multicast support at the hardware interconnection network level is the most efficient way support such communication operations. Generally, switching networks that realize these types of arbitrary multicast communications without any blocking, or multiple rerouting, are referred to as multicast networks.
Another notable feature in multicast network design is self-routing. Self-routing is a routing scheme that permits switch settings to take place during the routing sequence. This allows designers to create a network with faster switch settings, scalability, and less hardware complexity. Conventionally, however, most self-routing network designs relate to permutation networks, and not multicast networks. W. J. Cheng and W. T. Chen, “A New Self-Routing Permutation Network,”
IEEE Trans. Computers
, Vol. C-45, No. 5, pp. 630-636, 1996 [hereinafter Cheng and Chen] for example, discloses a self-routing permutation network constructed of reverse banyan networks, and is herein incorporated by reference. Permutation networks, as described by Cheng and Chen, do not provide a one to many broadcast output, but can only route n distinct input packets to n distinct output ports.
Others have attempted to implement multicast networks using recursive designs, but these previous attempts resulted in high propagation delays and expensive hardware costs. In an article by D. Nassimi and S. Sahni entitled, “Parallel Permutation and Sorting Algorithms and a New Generalized Connection Network,”
Journal of the Association for Computing Machinery
, Vol. 29, No. 3, pp. 642-667, July 1982, for example, the authors proposed a n×n multicast network that used O(k n
1+l/k
log n) 2×2 switches. This network had O(k log n) depth and O(k log n) set-up time for any k, where 1≦k≦log n. Nassimi and Sahni also disclosed a routing algorithm that relied on a cube or a perfect shuffle connected parallel computer consisting of O(n
1+l/k
) processors, which in turn caused the routing process to have a gate delay of O(k log
2
n). In another article entitled “Design of Efficient and Easily Routable Generalized Connectors,”
IEEE Trans. Communications
, Vol. COM-43, No. 2/3/4, pp. 646-650, 1995, C. Lee and A. Y. Oruc disclosed a multicast network with a special built-in routing circuit, and is herein incorporated by reference. This network used O(n log
2
n) logic gates, and had O(log
2
n) gate delay and O(log
3
n) set-up time (where the unit of time is a gate delay). Each of these proposed networks had high gate delays and more substantial hardware costs than are generally desired by network designers.
Therefore, a need exists for a network architecture capable of handling multicast connections in a self-routing manner without the gate delays and hardware costs of conventional designs. Additionally, a need exists for a multicast network with the modularity and scalability not offered by conventional designs.
SUMMARY OF THE INVENTION
Systems and methods consistent with the present invention meet these goals by providing a new multicast network based on the binary radix sorting concept with all functional components of the network recursively constructed with reverse banyan networks. In addition, a self-routing scheme and mechanism permits automatic switch settings that allow O(n log
2
n) cost (logic gates), O(log
2
n) gate delay, and O(log
2
n) set-up time (where the unit of time is a gate delay), and a feedback version that reduces network costs to O(n log n).
Specifically, the invention provides a self-routing multicast network that allows multicast broadcasting without blocking. The network comprises a first sub-network receiving multicast inputs having a destination set and configured to divide the destination set into an upper output subset and a lower output subset; and a second sub-network, coupled to the first sub-network, configured to route the upper output subset and lower output subset to an output destination. The second sub-network includes an upper binary radix sorting multicast network (BRSMN) coupled to an upper half of the first sub-network and configured to receive the upper output subset, and a lower BRSMN coupled to a lower half of the first sub-network and configured to receive the lower output subset.
The self-routing multicast network also includes a self-routing mechanism that permits the network to be configured for one pass routing of the multicast packets. The mechanism includes means for determining a number of tag value occurrences; means for determining an initial switch setting of a plurality of switches residing in network, wherein the initial switch setting is derived from the determined number of tag value occurrences; and a switch setting means for setting a switch position of a switch in the plurality of switches, wherein the position is derived from the initial switch setting. The self-routing mechanism is also recursively distributed throughout the sub-networks within the larger network.
The invention also provides for a method for implementing the aforementioned self-routing multicast network.
The summary and the following detailed description should not restrict the scope of the claimed invention. Both provide examples and explanations to enable others to practice the invention.


REFERENCES:
patent: 5648957 (1997-07-01), Lee et al.
patent: 5671222 (1997-09-01), Chen et al.
patent: 5856977 (1999-01-01), Yang et al.
patent: 5987028 (1999-11-01), Yang et al.
Y. Yang & G.M. Masson, “Broadcast Ring Sandwich Networks”, IEEE Trans. on Computers, vol. 44, No. 10, p. 1169-1180, Oct. 1995.
S. Lee & M. Lu, “BNB Self-Routing Permutation Network”, Proc. of INFOCOM '91, p. 574-581, 1991.
D. K. Panda, “Issues in Designing Efficient and Practical Algorithms for Collective Communication on Wormhole-routed Systems”, ICPP'95 Workshop on Challenges for Parallel Processing, p. 8-15, 1995.
L.M. Li, “Should Scalable Parallel Computers Support Efficient Hardware Multicast?” ICPP'95, Workshop on Challenges for Parallel Processing, p. 2-7, 1995.
D. Nassimi and S, Sahni, “Parallel Permutation and Sorting Algorithms and a New Generalizes Connection Network,” Journal of the Association for Computing Machinery, vol. 29, No. 3, p. 642-667, Jul. 1962.
J. Turner, “Design of a Broadcast Packet Switching Network,” IEEE Trans. Communication, vol., COM-36, No. 6, p. 734-743, 1988.
T.T. Lee, “Nonblocking Copy Networks for Multicast Packet Switching,” IEEE Journal on Selected Areas in Communication, vol. 6, No. 9, p. 1455-1467, 1988.
C.T. Lea, “A New Broadcast Switching Network,” IEEE Trans. Communications. vol. COM=36, No. 10, p. 1128-1137, 1988.
C. Lee and A.Y. Oruc, “Design of Efficient and Easily Routable Generalized Connectors,” IEEE Trans. Communications, vol. COM-43, No. 2/3/4 p. 646-650, 1995.
Y. Yang and G.M. Masson, “Nonblocking Broadcast Switching Network,” IEEE Trans. Computers, vol. C-40, p. 1005-1015, 1991.
D.M. Koppelman and A. Y. Oruc, “A self-routing Permutation Network,” Journal of Parallel and Distributed Computing, vol. 10, p. 140-151, Oct. 1990.
C.Y. Jan and A. Y. Oruc, “Fast Self-routing Permutation Switching on an Asymptotically Minimum Cost Network.” IEEE Tran

Affiliated with

Also associated with

Rating

Self-routing multicast network architecture does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Self-routing multicast network architecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Self-routing multicast network architecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2499461