Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1997-03-13
2002-06-25
Chin, Wellington (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S229000, C370S415000, C709S229000
Reexamination Certificate
active
06411627
ABSTRACT:
FIELD OF THE INVENTION
This invention is in the field of digital asynchronous transfer mode (ATM) networking. It is related to network capability and network utilization and is of a switching method for realizing a specific capability.
BACKGROUND OF THE INVENTION
One class (Class I) of ATM connections, already known through the Recommendations of the International Telecommunications Union (ITU), in relation to the Broadband Integrated Services Digital Network, and the Specifications of the ATM Forum, is that for which specific per connection resource provisions, in terms of bandwidth and switch-buffer allocation, are made and on which delivery is assured in occurrence and in specified or lesser time. Bandwidth or rate descriptors already recommended for Class I connections by the ITU or ATM Forum are Peak Cell Rate and Sustained Cell rate. The other class (Class II), brought into possible existence by our invention, is of ATM connections for which no specific, per connection, resource provisions are made, on which delivery is assured in occurrence and assurance on time of delivery is in a statistical sense only, and which are subject to control, originating within the switching element of the switch, which control is based only on the aggregate switch buffer utilization of the Class's traffic.
An example of an ATM switch which can support Class I connections is the Prelude switch of France Telecom CNET (e.g. J.-P. Coudreuse and M. Servel “Prelude—an asynchronous time-division switched network”. ICC'87, Seattle, 1987; French Patent no 82 22 226, Dec. 29, 1982 “Systeme de Commutation de paquets synchrones de longeur fixe”, Publication no 2 538 976).
The Prelude is a 16 port switch, switching at 260 Mbps rate. Writing from each input port is effectively in turn, with cells being written into consecutive locations of a (circular) buffer. The pointer to each written-in cell is placed into the FIFO stack(s) of the one (or more) output(s) that is (are) meant to receive it. The reading is also effectively in turn by each output port, taking the next cell pointer from its FIFO stack and outputting the pointed cell. The fill of a FIFO stack at a given time represents the backlog of cells still to be read by the given output port. The capacity of a FIFO stack could typically be for, say, 50 pointers. To accommodate the worst case, the capacity of the (circular) buffer would be for 50×16=800 cells.
The Prelude switch can switch only ‘resourced’ connections, or what we here call Class I ATM connections. The connections are resourced in the sense that all connections C
ijk
, where subscript i signifies that the connection enters on input port i, subscript j signifies that it is to be switched to output port j, and k signifies that it is the k-th connection that goes from i to j, have individual peak cell rate limits r
ijk
such that
∑
i
∑
k
r
ijk
<
R
j
(
1
-
m
)
(
EQ
1
)
where R
j
is the maximum rate at which cells can be output by port j, and m is a safety margin. The size of the safety margin depends on the number of connections, the capacity of the FIFO stack, and the magnitude of the tolerable probability that the stack should overflow. A typical size of margin would be 0.15, corresponding to a tolerable probability of overflow of less than 10
−13
.
We note that with service for Class I ATM connections only, the total network capacity is per force underutilized, minimally by the extent of the safety margin. A potentially much larger underutilization will be associated with the observation that a large proportion of the connections will not at all times, or continually send cells into the network at their given peak rates r
ijk
, but instead exhibit random intervals of inactivity. The average cell flow &mgr;
ijk
on C
ijk
will in a significant percentage of cases be much smaller than r
ijk
, and in consequence
∑
i
∑
k
μ
ijk
<
∑
i
∑
k
r
ijk
<
R
j
(
1
-
m
)
(
EQ
2
)
All the capacity that cannot be, or is not utilized, is wasted. With a measure of foresight, it has been called ‘available capacity’. As explained in greater detail below, an embodiment of the present invention has the effect of making the ‘available’ capacity in fact available.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a method of switching in an ATM network which, when used in conjunction with known methods of dynamic flow control on the network links, gives the network the capability of supporting two classes of ATM connections.
The dynamic flow control on the network links applies only to traffic cells on Class II connections and is credit based. Within Class II, control is exercised on the whole class of cells rather than on a per connection basis within the class. Class II cells may only be transmitted for which transmit credits are available. Credit(s) is (are) returned to the transmit end of the link, to replenish those available at initialization, whenever a Class II cell is read into the switching element of the switch from the Input Port Controller (IPC) Board. Return of credits is made possible by the assumption that the links comprise two-way pairs of unidirectional elements with one element in each direction.
An embodiment of the switching method, by the switching element of the switch, is by immediate transfer to a common shared memory of every traffic cell offered to the switching element by the IPC Board, and appendance of a pointer (pointing to that cell), to the Class I or Class II queue (as appropriate) for the output port(s) for which the cell is destined. These queues form part of the switching element. At a read-out opportunity for an output port, pointers are read from the Class I queue in first-in-first-out (FIFO) order at link rate, they are read from the Class II queue also in FIFO order and at link rate, but only while the Class I queue is empty and the Output Port Controller (OPC) will accept a Class II cell. A signal from the OPC to the switching element, indicating it cannot accept a Class II cell, implies that the output port has exhausted its supply of credits. Given a pointer, the cell is read from the pointed location, and output to the OPC Board.
When a cell has been read by an output, or in the case of a multicast cell when it has been read by all concerned outputs, its location is returned to the pool of free shared memory locations. With each input port there is associated a Backlog number, being the number of Class I cells resident in the shared memory which were received into the switch by that input port. While that Backlog number is at or above the quota value for that input, the switching element sends a Stop signal to the IPC Board in every cell period, by which the IPC controls the transferral of Class II cells from the IPC Board to the switching element.
Alternative embodiments of the invention exist—one such embodiment is similar to the embodiment described above, but lacks a common shared memory within the switching element of the switch. Instead, cells which are accepted by the switching element are transferred physically to the appropriate FIFO output queues, which hence are queues of cells, rather than of pointers. In this alterative embodiment the Backlog number associated with an input port is the total number of cells in the Class II FIFO output queues which were received into the switch by that input port Whether all copies or only one copy of any multicast cells are counted in the Backlog number is optional.
The maintenance of two classes of switch queues, with absolute service priority for Class L at output ports, and the keeping of Backlog number and quota value for input ports are of key significance to the embodiment of the invention. Separation of queues makes service and service quality on Class I connections independent of traffic on Class II connections, and queueing specifically at output makes the service quality the best possible for any given traffic shape and intensity and the servic
Budrikis Zigmantas Leonas
Cantoni Antonio
Hullett John Leslie
Wittorff Vaughan William
Curtin University of Technology
Larson & Taylor PLC
Nguyen Steven
LandOfFree
Switching protocol providing controlled access to available... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Switching protocol providing controlled access to available..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Switching protocol providing controlled access to available... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2952820