Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
2000-03-24
2004-11-02
Olms, Douglas (Department: 2661)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S381000
Reexamination Certificate
active
06813265
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a system for and a method of determining the order of departure (or of service) of temporarily stored information or objects.
It relates in particular to the evacuation of a flow of information or objects arriving at a particular location where they are stored temporarily and from which they must be evacuated in an order that depends on various criteria.
Such evacuation or “service” gives rise to difficult problems, in particular if the incoming bit rate and the evacuation bit rate are high.
These problems arise more particularly in telecommunication networks in which digital information signals are transmitted in the form of cells or packets and are stored temporarily in buffers. The cells or packets support calls with different grades of service and it is therefore standard practice to allocate them different bit rates and different relative priorities of service. To control the output of packets or cells from the buffer according to their relative priority, the order of service (or evacuation) of the packets or cells in the buffer must therefore be determined continuously.
Similar problems of establishing an order of distribution can also arise in other technical fields, for example aircraft arriving at and departing from an airport or trains arriving at and departing from a train station.
Generally speaking, buffer service disciplines are classified into two categories according to the time at which the order of service is determined, namely:
first-in-first-out (FIFO) queues, in which the order of service is determined when the packets or cells arrive at the buffer, and
schedulers, in which the order of service is determined when the packets or cells depart from the buffer.
2. Description of the Prior Art
U.S. Pat. No. 4,005,391 describes a system for determining the interrupt priority order of a processor which several peripheral devices can access, but not simultaneously. The values of the interrupt request signals to be processed are stored in an input-output device. The priority information is stored in the elements of a memory: the position of a bit at 1 in a series of bits at 0 determines the service priority for a peripheral device. The address counter scans the content of the buffer to transcode, as it were, the regularly incremented value supplied by the counter. The buffer has eight outputs, only one of which supplies the value 1, the content of the memory being chosen so that all the peripheral devices have different priority levels. Each output of the memory supplies the value 1 in succession to enable AND gates in succession.
An AND gate enabled at one input transmits any interrupt request that it receives on its other input. Scanning is stopped as soon as an AND gate has transmitted an active interrupt request signal. This scanning enables the interrupt requests to be considered in succession and in a particular priority order by enabling gates in succession, but there is no provision for defining the priorities dynamically.
The present invention relates to a scheduler which continuously takes account of the respective relative priorities of the various packets or cells stored in the buffer of an ATM switch, for example.
The order of service is determined in a scheduler of this kind by a selection algorithm taking account of time parameters associated with the packets or cells stored in the buffer. Until now these time parameters have been managed using either random access memory organized in the form of tables or chained lists or content-addressable memory. The processing times of such systems can be incompatible with operation at high bit rates, when the time allocated to each service is very short.
The invention provides a system which can schedule dynamically and very fast.
For simplicity, in the following description, the term “object” is sometimes used to refer to information or an object processed in the system.
SUMMARY OF THE INVENTION
The invention provides a system for determining an order of service of temporarily stored objects, at least one priority flag being attached to certain objects, the system including:
a set of storage units disposed in a matrix organized into C subsets of elements, where C is the number of objects stored temporarily, each of said subsets corresponding to an object and all the subsets including the same number P of elements corresponding to P time positions, each element including a memory which can receive at least one time priority flag, and
first time position selector means for determining, within the matrix, and from all the subsets, the element(s) marked by a particular time priority flag and corresponding to the time position having the lowest value, and
means for writing a time priority flag for a given object into a random access memory element corresponding to a time position allocated to that object.
The priority flags can therefore be written dynamically into a matrix of storage elements, each row corresponding to a subset, for example, i.e. to an object, and each column to a particular time position. The highest priority is assigned to the row(s) with an element containing a priority flag whose flag is at the lowest rank.
In one embodiment, object priority selector means are provided for selecting, in the matrix, only one of the subsets preselected by the first time position selector means. Alternatively, a predetermined number of objects to be serviced simultaneously is selected from the objects that have been preselected.
In these embodiments, the system includes object priority selector means for selecting at least one of the subsets preselected by the first time position selector means.
In one embodiment, to allow for the advancing clock time, at each clock time an offset of one time position is introduced between the time priority flags of each subset and the rank corresponding to their time position so that their new rank corresponds to the next lower time position.
The offset by one time position is effected at the end of each object service time if the service is periodic at each clock time. This time position shift is effected, for example, by transferring the content of the memory of each element to the next element corresponding to the next lower time position.
Alternatively, the contents of the memories of the elements are not modified but instead their ranks are shifted, each rank of an element being reduced by one unit.
In one embodiment, the object priority selector means are connected to the memory elements by means of one incoming conductor per subset transmitting a selected object signal and effect the final choice of at least one object to be serviced from the objects corresponding to the subsets transmitting a selected object signal.
In one embodiment, the first time position selector means are connected to the memory elements by two common conductors for each of the P time positions, namely an incoming common conductor for receiving a time position signal that is a candidate for selection, and an outgoing common conductor for transmitting a retained time position signal. In this case, the first time position selector means identify, among the P signals received on the incoming common conductors, the first time position signal which is a candidate for selection corresponding to the time position having the smallest value and indicate the selected first time position by transmitting a retained time position signal on the outgoing common conductor corresponding to the selected first time position.
In one embodiment, for each subset, the time position of the element containing a time priority flag represents the required time of servicing the object corresponding to that subset relative to the other objects, the first time position selector means giving priority to selecting the object(s) whose priority flag is in an element corresponding to the time position with the lowest value.
In one embodiment, each memory element:
activates the corresponding incoming common conductor of the first time position selector mea
Alcatel
Olms Douglas
Pizarro Ricardo M.
Sughrue & Mion, PLLC
LandOfFree
Method and system for controlling the order of departure of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for controlling the order of departure of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for controlling the order of departure of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3355933