Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-04-07
2004-08-24
Patel, Ajit (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S394000, C370S395100, C370S395700
Reexamination Certificate
active
06781998
ABSTRACT:
BACKGROUND
1. Field of Invention
This invention relates to a random reordering system/method. In certain embodiments, the random reordering system/method may be utilized in the context of an asynchronous transfer mode (ATM) switching apparatus in a telecommunications network.
2. Related Art and Other Considerations
The increasing interest for high band services such as multimedia applications, video on demand, video telephone, cellular telephone applications, and teleconferencing has motivated development of the
B
roadband
I
ntegrated
S
ervice
D
igital
N
etwork (B-ISDN). B-ISDN is based on a technology know as
A
synchronous
T
ransfer
M
ode (ATM), and offers considerable extension of telecommunications capabilities.
ATM is a packet-oriented transfer mode which uses asynchronous time division multiplexing techniques. Packets are called cells and have a fixed size. An ATM cell may consist e.g., of 53 octets or bytes, five of which form a header and forty-eight of which constitute a payload or information portion of the cell. The header of the ATM cell includes two quantities which are used to identify a connection in an ATM network over which the cell is to travel, particularly the VPI (Virtual Path Identifier) and VCI (Virtual Channel Identifier). In general, the virtual path is a principal path defined between two switching nodes of the network; and the virtual channel is one specific connection on the respective principal path.
At its termination points, an ATM network is connected to terminal equipment, e.g., ATM network users. Between ATM network termination points are a plurality of switching nodes having ports which are connected together by physical transmission paths or links. In traveling from an origin terminal equipment (i.e., source) to a destination terminal equipment (i.e., destination), ATM cells forming a message may travel through several switching nodes.
A switching node includes at least one switching apparatus having a plurality of ports, each of which is connected by a link circuit and a link to another node. The link circuit performs packaging of the cells according to the particular protocol in use on the link. A cell incoming to a switching apparatus may enter the switching apparatus at an ingress port and exit from an egress port via a link circuit onto a link connected to another node. Each link can carry cells for a plurality of connections.
ATM switches are known in the art. For example, see U.S. Pat. Nos. 5,983,386, 5,901,147, 5,583,861, and 5,467,347, the disclosures of which are all hereby incorporated herein by reference.
ATM switches typically have several functional parts, a primary of which is a switch core(s) or fabric(s). The switch core(s) essentially functions like a cross-connect between ports of the switch. Paths internal to the switch core or fabric are selectively controlled so that particular ports of the switch are connected together to allow a message ultimately to travel from an ingress side of the switching apparatus to an egress side thereof, and ultimately from the originating terminal equipment to the destination terminal equipment.
Two primary tasks are generally accomplished by an ATM switching apparatus: (a) translation of VPI/VCI information, and (b) transport of ATM cells from an ingress port to an egress port(s). Certain aspects of this invention relate to task (b), namely, how the cells are tagged and/or ordered as they are routed through the switch fabric and transported to egress ports of the switching apparatus. Generally, the network device which generates a given ATM cell has no knowledge of the specific output port to which the switch will send the cell. Rather, this internal switch routing decision is made by the switch based on then current translation tables within or accessed by the switch.
When an ATM cell is received by a switching apparatus, the cell is typically 53 bytes long. At the switching apparatus, a routing tag may be added to each cell so that each cell in the switch includes 54 to e.g., 59 to 64 bytes. This tag is typically added at an ingress switchboard (also known as a traffic management board or function) of the switching apparatus. The tag assigned to a cell is used by the switch core to route the cell through each switch stage in the core circuit (e.g., up to six stages may be supported in certain embodiments), and determines the switch egress port that the cell is transported to through the switch fabric or core. After a routing tag is added to a cell, the cell is stored in an appropriate ingress queue and thereafter transferred in some order (e.g., Quality of Service, or QoS, order) towards the switch core when a corresponding fabric cross-point is free. Upon reaching an appropriate egress port, by way of the switching core or fabric, the ATM cell is transmitted further along the network to another node based upon its VPI/VCI.
There exists a need in the art to randomize or quasi-randomize cells as they are forwarded through an ATM switching apparatus. Otherwise, certain cells may get preferential treatment.
SUMMARY OF THE INVENTION
A system and corresponding method for randomly reordering a plurality or sequence of elements is provided. In certain embodiments, ATM cells received by a switching apparatus (tagged or untagged) are randomly reordered as they are forwarded through the switch core. This enables cells from different ingress ports/channels to be treated in a more equal manner by the switching apparatus.
In certain embodiments, a sequence of numbers (e.g., 0 through 31) is randomly arranged. The sequence is then output to a switching device in order to control the device outputs to which particular ATM cells are forwarded. In such a manner, the ordering or transmission of ATM cells may be randomized within an ATM switching apparatus.
In one exemplary embodiment, at least one number or value within a first range(s) is randomly generated for each element E (e.g., ATM cell, switch output, number, or tag value) in a sequence or group to be randomly reordered. Each element is shifted through a number of empty logic units (e.g., buffer locations or queues) determined by one of the randomly generated numbers for that element, until the element is finally stored in one such unit.
In certain exemplary embodiments, if none of the randomly generated number(s) for an element fall within a second range, a reserve number may be used to indicate how many empty logic units the element should be shifted through before being stored. Since use of the reserve number makes the randomness less perfect, when a retry flag is set use of the reserve number may be delayed until another attempt has been made at generating a random number falling within the second range. In order to set a maximum number of iterations (akin to a time or iteration limit) for the process of randomly reordering the elements, the number of retries may be limited and the retry flag canceled as a function of time and/or the iteration being performed.
While the random reordering processes and techniques described herein are preferably used in the context of an ATM switching apparatus, the invention is not so limited. Random reordering techniques herein may be used in non-ATM environments where it is desired to randomly reorder a set or sequence of elements.
REFERENCES:
patent: 5102134 (1992-04-01), Smyth
patent: 5130975 (1992-07-01), Akata
patent: 5367520 (1994-11-01), Cordell
patent: 5583861 (1996-12-01), Holden
patent: 5737252 (1998-04-01), Hollmann et al.
patent: 5862136 (1999-01-01), Irwin
patent: 5871400 (1999-02-01), Yfantis
patent: 5923656 (1999-07-01), Duan et al.
patent: 5930291 (1999-07-01), Hines
patent: 6011779 (2000-01-01), Wills
patent: 6563837 (2003-05-01), Krishna et al.
patent: 0 412 343 (1991-02-01), None
Book, “The Art of Computer Programming”, 1969, Knuth, Donald E, pp 24-27 100-103 82-85, 1965.*
PMC-Sierra, Inc. brochure, “PM3748 8 QSE 5 Gbit/s ATM Switch Fabric Element”Datasheet, Issue 3, Jun. 3, 1999 (pp. 1-135).
“A Simple and Fast Scheduler for Input Queued ATM Switches”, Song et al., 1997 IEEE, pp. 26
Blount Steven A
Nixon & Vanderhye P.C.
Patel Ajit
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Random reordering system/method for use in ATM switching... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Random reordering system/method for use in ATM switching..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random reordering system/method for use in ATM switching... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3357015