Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
2000-07-20
2004-11-09
Rao, Seema S. (Department: 2666)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S358000, C370S360000, C370S380000
Reexamination Certificate
active
06816487
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
This is the first application filed for the present invention.
MICROFICHE APPENDIX
Not applicable.
TECHNICAL FIELD
The present invention relates to multi-stage switches, and in particular to a method and apparatus for mapping high bandwidth connections through a multi-stage switch.
BACKGROUND OF THE INVENTION
Synchronous Optical Network (SONET)/Synchronous Digital Hierarchy (SDH) protocol is widely used for physical-layer data transport. SDH is the European equivalent of the SONET standard. A reference in this document to SONET is therefore intended to refer to SDH as well as SONET. Under the SONET protocol, signals are forwarded section-by-section across a network along an end-to-end connection (i.e. a SONET path), which is established (nailed up) prior to a communications session, and which remains nailed-up for at least the duration of the session.
As is well known in the art, it is highly desirable to successfully complete every request for a path through a telecommunications network. A path that cannot be completed successfully, for example because a connection between sections of the path cannot be found, is said to be “blocked”. It is also well known that a plurality of switch nodes can be interconnected in a multi-stage architecture to provide a Clos network. Application Specific Integrated Circuits (ASICs) can also be interconnected in a Clos network pattern within a SONET switch to provide a versatile switching node.
It is also known that a Clos network may be designed to be non-blocking by providing sufficient hardware resources. For example, a three-stage Clos-type network can be made non-blocking by providing a sufficiently large number of nodes in the center stage. In particular, a three-stage Clos network supporting P input connections into the ingress stage, and M connections through the center stage, can be made completely non-blocking by providing that M≧2P−1. However, as the required number of input connections increases, the number of connections through the center stage required for a non-blocking network (and the associated cost) becomes prohibitive. Accordingly, various techniques have been employed to reduce the probability of blocking in a switch that is of a manageable size. The primary techniques include “packing” and “re-ordering”.
“Packing” refers to a technique of mapping connections through a switch (between an ingress node and an egress node) in which the system attempts to map each new connection through the most heavily utilized center stage node. If that attempt fails (due to inadequate idle capacity in the selected center stage node), then successive attempts are made to map the new connection through progressively less utilized center stage nodes, until either a center stage node with sufficient idle capacity is found, or it is determined that the new connection cannot be mapped through the network (in which case the connection is “blocked”). This technique has proven satisfactory for low-bandwidth connections (i.e. having an STS-1 granularity, for example). However, the probability of blocking increases rapidly as the connection bandwidth increases.
Re-ordering refers to a method of mapping connections through a switch network in which, if a new connection is initially blocked (e.g. following a packing algorithm described above), it may nevertheless still be mapped through the network if previously-mapped connections can be rearranged. An example of this method is provided in U.S. Pat. No. 5,987,027, which issued to Park et al. on Nov. 16, 1999. Re-ordering connections can reduce the probability of blocking of new connections, even in cases where the granularity exceeds STS-1. However, a significant amount of system overhead is required to re-order existing connections without interrupting associated communications sessions. As a result, the time required to map new connections increases dramatically as each successive connection is mapped through the switch network.
An alternative method of mapping connections through a switch network is referred to as “bit-slicing”, in which a signal is divided into a number of fixed-size units that are evenly distributed across the center stage. Every center stage node handles its respective unit in an identical manner to map the signal to the egress node, and thus a connection map of each center stage node of the switch network is identical. This arrangement tends to simplify the control signaling within the switch network, but dramatically reduces the routing flexibility. Additionally, because the number of units must be equal to the number of center stage nodes (or an integer multiple thereof), the size of each unit must necessarily vary with the signal bandwidth. For example, a switch network having 12 center stage nodes can map an STS-12 signal by slicing that signal into 12 units, each of which having an STS-1 granularity. An STS-48 signal can also be mapped by slicing into 12 units, but in this case each unit must have an STS-4 granularity. Since modern networks commonly carry signal traffic having varying bandwidths, the ingress stage must have some means of controlling the slicing of incoming signals to produce and route units of the appropriate size. This requirement greatly increases the complexity and cost of the switch network.
Accordingly, a method and apparatus that enables connections for high bandwidth signals to be rapidly mapped through a Clos network, with a low probability of blocking and high utilization efficiency of network resources, remains highly desirable.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a method an apparatus for mapping high bandwidth connections through a Clos network or a Clos-type versatile switch.
Accordingly, an aspect of the present invention provides method of mapping a connection for a high bandwidth signal through a Clos network between an ingress node and an egress node via a center stage comprising a plurality of center stage nodes. A number of units in the high bandwidth signal is determined. Each of the units has an equal predetermined size. A number of available connections through the Clos network equal to the number of units is then located. Finally, each unit is mapped to a respective one of the available connections across a center stage node to the egress node of the Clos network mapping each unit to a respective one of the identified available connections, so that the units are generally unequally distributed across each center stage node, but a sum of all signals switched through the Clos network from the ingress node to the egress node at any given time is substantially equally distributed across the center stage nodes of the Clos network.
A further aspect of the present invention provides a Clos network adapted to map a connection for a high bandwidth signal between an ingress node and an egress node via a center stage having a plurality of center stage nodes. The Clos network comprises: means for determining a number of units of the high bandwidth signal, each of the units having an equal predetermined size; locating means adapted to locate a number of available connections through the Clos network equal to the number of units; and, means for mapping each unit to a respective one of the identified available connections, wherein the units are unequally distributed across the center stage nodes, but a sum of all signals switched through the Clos network from said ingress to said egress at any one time is substantially equally distributed across the center stage nodes of the Clos network.
In embodiments-of the invention, the high bandwidth signal is a SONET/SDH signal. The SONET/SDH signal is an STS-N signal comprising N STS-1 frames, and the number of units of the high bandwidth signal corresponds with the number of frames of the STS-N signal. The value of N may be two or more.
The Clos network may be represented by a matrix of connections between the ingress node and the center stage. Each column of the matrix represents a link between the ingress node and a res
Mehrvar Hamid R.
Roberts Kim B.
Sciascia Andrew
Nortel Networks Limited
Rao Seema S.
Scheibel Robert C
LandOfFree
Mapping of high bandwidth connections in a multi-stage switch does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Mapping of high bandwidth connections in a multi-stage switch, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mapping of high bandwidth connections in a multi-stage switch will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3341324