Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
1999-05-27
2003-05-13
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S380000, C370S411000
Reexamination Certificate
active
06563819
ABSTRACT:
CLAIM OF PRIORITY
This application makes reference to, incorporates the same herein, and claims all benefits accruing under 35 U.S.C. §119 from an application for AUGMENTED RING-BANYAN NETWORK AND METHOD OF CONTROLLING ROUTING THEREOF earlier filed in the Korean Industrial Property Office on the 14th day of October 1996 and there duly assigned Serial No. 1996-45749, a copy of which application is annexed hereto.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the switching fabric in a B-ISDN switching system, and more particularly to an enhanced ring-banyan network and a method for controlling routing in such a network.
2. Description of the Related Art
A class of multiple interconnection network (MIN) architectures with considerable commercial potential for fast, broadband switching applications is the banyan network architecture defined by Goke and Lipovski. The banyan architecture provides parallel connections between processors and storage device modules and is a good substitute for the crossbar switch in terms of effectiveness in contradistinction to cost. Enhancements of the basic banyan structure have been proposed to provide further improvements in performance by taking advantage of the underlying relationships between the nodes and links in such networks.
A banyan network as so defined provides unique paths between processors and storage device modules. More particularly, the set of paths destined for a switch element (SE) constitutes a spanning tree, and the set of paths from the switch element also forms a spanning tree. However, only a certain class of spanning trees, from among all such spanning trees, is important in this regard. This class is defined by the property that all switch elements belonging to the class can deliver a packet through the same output port by using a basic self-routing control method for the network. Thus, the performance of the banyan network may be considered in terms of the relationships between and limitations on equivalence classes of paths.
Commercial systems implementing banyan networks have already been introduced, but their performance has in practice been rather low. This is because each pair of the input/output ports (one input port and one output port) has only a single path between the ports. The absence of alternative paths between input ports and output ports has the consequence that, when random internal collisions occur between two data units being transmitted across the network, one of these data units will be lost. These collisions, therefore, deteriorate the overall performance of the network.
Enhancements of the basic banyan architecture, as represented by the delta network, offer improvements upon its performance. For example, “augmented” banyan networks can provide improved performance by supplementing the spanning trees of the basic network with alternative paths. In one type of augmented banyan network, such alternative paths arise through additional links that chain together various switch elements corresponding to the same stage of the network tree. When a collision occurs at a selected output link of a switch element, a data unit (such as a. packet) being transmitted across the network can be delivered from that switch element to another switch element at the same level within the tree. Thus redirected, the data unit being transmitted across the network (hereinafter referred to as a “data transmission”) can be properly delivered to its intended destination port by means of the existing self-routing control algorithm corresponding to the network.
In a load-sharing banyan network (or B-network), on the other hand, additional links may provide alternative paths by connecting switch elements in a given stage to other switch elements in adjacent stages. The adjacent stage, relative to a switch element of which the additional link connects a switch element of the given stage, may either precede or succeed the given stage. This arrangement enables the network to avoid loss of transmissions, which otherwise would arise from collisions at switch element output links, in a manner essentially similar to the redirection that occurs in an augmented banyan network.
The B-network and the intrastage augmented network both provide robustness against processing malfunctions arising from collision-engendered transmission losses. Their success derives from the existence of supplemental links that permit data transmissions to proceed over additional, alternative paths in the event of collisions. They in fact have improved reliability relative to the basic banyan network; however, they too can suffer degraded performance due to data loss. In particular, if a collision at an output port of the penultimate stage causes a data transmission to be redirected to an alternate switching element of the final stage, then the supplemental links may not suffice to provide a path to the switching element of the destination port. In such a case the transmission must be discarded, just as any collision in the basic banyan network causes the discard of a transmission.
A promising type of augmented banyan network has been proposed and termed the “ring-banyan” network. See J. Park, et al.,
The Ring
-
Banyan Network: A Fault Tolerant Multistage Interconnection Network with an Adaptive Self
-
Routing,
Proc. 1992 Int'l Conf. Parallel & Distributed Systems, December 1992, at 196-203. A ring-banyan network comprises a basic banyan structure augmented by additional links between successive switch elements within each stage, so that each stage of the network comprises a closed chain of switching elements. Such a structure can significantly decrease the frequency of data loss due to collisions between transmissions traversing the network simultaneously.
The ring-banyan structure shares the limitation of other augmented banyan networks that a data transmission arriving at the final stage in the wrong switching element may not be deliverable to its intended output port and thus may be discarded. The authors of the cited paper, however, recognized and focused their efforts upon a separate issue. In particular, they noticed that the failure in the ring-banyan structure of the final stage output link connected with the designated output port would result in the loss of the data transmission intended for that port. A failure of any one of the intrastage links in the final stage would similarly prevent a data transmission misdirected at the final stage from reaching its designated destination port.
The paper's authors addressed these related problems by modifying the basic ring-banyan topology to include a final stage made up of a series of interconnected switch element pairs, instead of a series of single switch elements. In this way, the failure of any one intrastage link or output link in the final stage would not cause the network itself to malfunction. This modified ring-banyan structure included, as well as an additional set of final-stage switch elements and a mesh of links between the final-stage switch element pairs, two sets of supplementary 1×2 switches positioned after the final stage of switch elements. The supplementary switches allowed each switch element of each switch element pair in the final stage to connect with either of the two output ports corresponding to that switch element pair.
The cited reference provided a complex but insightful solution to the problem addressed therein. However, it did not consider the more fundamental problem that misdirected data transmissions may be lost in the final stage, even without a link failure. This “no-fault” data loss problem has appeared to constitute an intrinsic weakness of augmented banyan networks, including the ring-banyan network.
We have, therefore, found that a need continues to exist for an enhanced MIN architecture and associated self-routing method that provide greater robustness against transmission losses than is provided by existing link-augmented banyan networks. A network with such an architecture should comprise the same node and li
Bushnell , Esq. Robert E.
Kizou Hassan
Samsung Electronics Co,. Ltd.
Tsegaye Saba
LandOfFree
Augmented ring-banyan network and method for controlling... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Augmented ring-banyan network and method for controlling..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Augmented ring-banyan network and method for controlling... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3051839