Note: Descriptions are shown in the official language in which they were submitted.
BACKGROUND OF THE INVENTION:
This invention relates to a data storage system which serves a
number of user circuits each of which provides one of the ports to the
system and over which messages may be received either for transmission or
retransmission~ or for temporary storage, or for processing at the user
circuits.
Each s-~ch message includes signalling information and address
information, and the system is applicable to, but by no means restricted to,
a message transmission system included in a digital telecommunication
system having many system nodes, which in one example of such a system
are telephone exchanges or system administration centres.
SUMMARY OF TH~ INVENTION:
An object of the invention is to provide a data storage system
suitable for use in such systems or in other systems where large q~lantities
of data have to be handled and in which queuing facilities are needed.
According to the present invention, there is provided a data
storage system which includes a number of ports each associated with a
user circuit of the system, messages being received and/or sent via said
ports, a message store having a number of message cells in each of which
one of said messages can be stored, a control store having a number of
control cells each associated with one of said message cells and each
containing stored information indicating whether its said message cell is in
use and the identity of the user port concerned if its message cell is in use,
scanning means which scans the control cells sequentially and, when one of
said user circuits has a message to be stored, selects a free message cell
for that message, and control means responsive to said detection which
routes a said message for which storage is required into a free message
cell, the contents OI the control cell associated with the message cell into
which a message has been routed being amended to indicate that
-.~
,, . ~=
that message cell is in use and to indicate the identity of the user port for
which the message ceLI is in use.
BRIEF DESCRIPTION OF THE DRAWINCI:
= _ _ . ...
An embodiment of the invention will now be described with
reference to the accompanying drawing which illustrates in block form a
data storage system.
DETAILED DESCRIPTION OF THE DRAWING:
The present invention is of wîde application, as indicated above,
and is thus a general system tool, but it is described herein as applied to a
message transmission system forming part of a multi-exchange digital
telecommunication network. The system under discussion is used to
transfer messages conveying call processing and other information between
nodes of the telecommunication network, and has a number of so-called
user ports each of which is a signal channel serving a number of message-
conveying links in common channel manner. Each message contains
information which identifies the call or other operation to which it relates,
this including destination information. In the present arrangement, the
sources, i.e., input ports, are used to enter messages into the message store
from the system processors.
Each input port has its own buffer storage into which an
incoming message is placed until it can be transferred to one of the storage
system's rmessage cells. Each message which is entered into the storage
system occupies part or all of a message cell and only one message may be
present in a message cell at any one time. All message cells are identical,
and each of them consists of a number of sub-sections each capable of
storing a single message element.
-- 3 --
;
Each such message element is a multi-bit combination which in the present
case consists of 48 bits of message information. As will be seen later, 32
bits of "housekeeping" information may be added by the user circuit for
transmission therefrom. A message may consist of a minimum of one
element, the maximum number of elements depending on the data to be
dealt with. The message cell in the present case can accommodate the
maximum number of elements in the type of message to be catered for.
Alternatively, if the majority of the messages to be dealt with are short,
with a few long messages, each of the latter can be split into two or more
"sub-messages" which are handled separately.
As stated above, the system also has a control store which
includes a number of store elements each associated with one of the
message cells. Each such control store cell contains data relating to its
message cell, and in operation of the system these control cells are scanned
sequentially. When a control cell is scanned its contents indicate whether
it is available for use, in which case its contents, known as a control word,
indicates that the cell is free. In the present case the free indication is an
all-zeroes word. If the control word indicates that its memory cell is in
use, it includes a busy status code plus the identity of the destination user
port for which it is in use. When such a message store is in use, the
message therein may be a message for any of the user ports, any one or
more of which may have a queue of messages awaiting attention - this
follows from the fact that these control channels are used for common
signalling.
SJ7~
Thus the message in a message ~all may be a message in any of
the input or other queues associated with that user port, or may be stored
for other temporary purposes by that user. In the application of the data
storage system described herein, a single message store -a dynamic store -
provides three input queues for each of 124 signalling terminals, and serves,
after a message has been accepted from a source (e.g. from a processor), to
retain that message in normal operation until such time as the signalling
terminal has received in~ormation from a distant receiver indicating that
the message has been received correctly. The user port has access to the
stored message every time the message polls the user as a resu~t of the
message being scanned, so message elements can be extracted for
transmission or retransmission, as required by the user.
The accompanying Fig. 1 indicates schematically the operation
of the data storage system, its main parts being the store control logic 1,
the control store 2 and the message store 7. Associated with these are, for
a source terminal served, a source buffer control unit 3 plus source buffer
message store 4, and for signalling terminals a user port control 5 plus
buffer 6. Terminals may have units 3 and 4 as well as units 5 and 6, but
terminals may also have 3 and 4 or 5 and 6 only. In this system described
herein, units 3 and 4 at a single port are associated with the input of
messages from a processor, while units 5 and 6 are associated with outputs
to signalling links (124 ports). In other systems, a user may have both an
input port, units 3 and 4, and an output port, units 5 and 6. As the
connections indicate the terminals have access to the three main parts of
the system.
7f~.3~L
The store control logic 1 has both-way communication for
control purposes with the source buffer control 3 section of a number of
message-sources, as indicated at 8, 9. It also has both way access for
control purposes, via connections such as 10 to at least one user port
control 5.
The control store 2 is accessible from the source buffer
message stores via connections such as 11,12, and is also accessible via the
connection 13, with access in the reverse direction via connection 14. The
store control logic 1 has access for address read-write control via
connection 15 to the message store, which is also accessible via connection
such as 16, 17 from message sources. In addition it has access via
connection such as 18 to one or more user buffers. Note that many of these
connections would in fact be multi-wire connections.
The purpose of the control connections are summarised as
follows:-
8, 9 Control "handshake" with source/buffer 3/4
Control "handshake" with user port control S
11,12 Message header control information written in
the control element of a message
13 Address, read-write, control information for
modification of control element
14 Control element of message
Address read-write control.
As used in a telephone switching network, the cells of the
control store 2 may have accommodation for a second user identity. This
identifies a user to which the message for that control cell's control word is
to be routed should the normal user be unsuitable for accepting the
message.
.-- .~
~? 6
~ ~
If the first choice user is unable to process the message, that message then
transferred by operation of the logic 1 to an input for an input queue
appropriate to the second choice user. This transfer involves manipulation
of the status bits of the control word used.
A corresponding set of states exists for processing the message
by the second choice user as exists for processing it by the first choice
user. In the present example the message numbers assigned to all messages
of the same priority intended for either the first or the second choice user
are generated by the same message number. This is so that the firstin-
first-out (FIFO) mode of operation may be preserved as regards the input
queues, there being one input queue per user per priority level in normal
operation.
Usually, as already indicated, messages may be of variable
length, in which case the length of the message in number of message
elements is recorded in the associated control store element when the
message is transferred from the source to the store.
At this point the structure of a control word will be explained.
This contains in a first portion the first choice user number, the second
choice user number, the message priority, the rnessage number and the
message lengthO These items of information are derived via the connection
such as 11 or 12 from the message header. A second portion of the control
word contains message status information and time out information,
supplied by the control store 2, and the user sequence number and such
other user information as is needed, these being supplied by the user.
The message status bits of a control word in the store 2 are set
to the "message inserted" states when a message is inserted into the
message store 7. The input queue which now contains the inserted message
is defined by the first choice user code and the priority code allotted to
that message, as indicated by the appropriate bits of the message's control
word. That is, for each user circuit a number of queues is set up, one per
priority level, each of which contains all messages in the message store for
that user and for one of the priority levels. In general the messages in each
of these queues are dealt with in chronological order, i.e., on a ~IFO basis.
When a message is accepted for processing by a user, it is
removed from one input queue, and transferred functionally to a functional
sub-store of the user. However the message remains physically in the same
message cell. To do this the status bits of the control word (supplied by the
control store) are altered, and in addition in the present system a user
addressing reference is provided. This is the user sequence number
mentioned above, which comes from the user, and specifies the first
message element in the message as assigned by the user.
When a message control cell, i.e. one of the cells of the store 2,
has any other status than idle, it effectively belongs to the first choice
user, unless as a result of a prior decision that message has been
transferred from control by the first choice user to control by the second
choice user, with the appropriate change in the status bits. In this ladder
case the message control cell effectively belongs to the second choice user.
We now consider the operation of the dynamic store in more
detail. This operation is based on the cyclic scanning at a suitably rapid
rate of the control words in the store 2, each of which is associated with
one of the message cells in the store 7. When this scan finds a control cell
whose contents indicate that the associated cell of the store 7 is idle, the
input port or ports is or are polled to see of there is a message awaiting
insertion into the dynamic store 7. If such a message is found, the store
control logic (which, of course, includes the control store scanner and the
polling circuitry) controls the transfer of control "information" to the
control store cell found to be idle and the transfer of the message to the
associated cell of the memory store 7. The status of the control store cell
is specified as l'message insertedll before the scan is restarted for the logic
to test the next control store cell.
If the next control store cell which is scanned is found not to be
idle, the oper~tion user code, which is the first or second choice user code
as specified by the status bits, is used to address the user port identified by
that user code. A llhandshakell control can now take place between the
control store logic 1 and the user port control such as 5. This causes the
control word to be modified as and when required, and information to be
transferred from the message cell to that user's buffer such as 6 when this
is required by the user. This, of course, takes place at a time defined by
the scanning circuit.
When a message first enters the dynamic store its control word
is put into the "message inserted" state assigned to one of the user's input
queues, the choice of queue depending on the priority of the message. The
control store cell associated with that message is scanned at the scanner's
scan rate, and it may occur that when it is first scanned aIter it has
assumed the "message inserted" state, the first choice user is found to be
unsuitable for servicing the message. If this is so, the message may be re-
assigned for servicing by the second choice user by changing the status bits
to specify "message inserted, for second choice user". Thus when the first
choice is found to be unavailable, the message is sent out using the second
choice user.
During normal operation a busy control store cell and its
controls when scanned cause the user port to be supplied with (a) the phase
(e.g. stage of message transfer obtained), (b) the message number, and (c)
the input queue identity defined by the priority number. As already
mentioned when a control word is found to be busy, the user for which the
appropriate message is intended is polled on each scan on which that word
is busy, and that user is required to accept messages according to the
message priority, with each priority queue dealt with on a FI~O basis. To
implement this the user port control includes a search register which
determines the next message to be serviced by the user, by the use of the
message number and the priority number.
When a control store cell in the "message inserted" state is
scanned, the logic causes the user port concerned to be supplied, via
connections 14 and 10, with the message number, the priority and an
indication that the control word is in the "message inserted" state. At the
--10--
~Lr~7~
user port control 5, a comparison is made between the message number and
priority details recorded in the search register and the corresponding
details as supplied to the user port on each such access due to a control cell
in the "message inserted" state. If the comparison determines that either:
(a) the polling message in the message store has a higher
priority than the message whose details are recorded in
the search register, or
(b) The polling message has the same priority as the message
whose details are in the search register but whose
message number indicates that it entered the message
store earlier than did the one whose details are in the
search register,
then the second register is over-written so that it now contains the details
of the polling message.
If the details of the polling message are found to be identical
with the details in the user's search register, than a complete scan of the
control store has been carried out during which there has been found no
message for that user which is of higher priority than the one whose details
are in the search register.
If the user is ready to accept a message from its input queue,
the user port's control 5 causes the status of the message as indicated on
its control word to be changed by a "handshake" control between the store
control logic 1 and the control 5. This removes the message from the user's
input queue - because it is about to be dealt with - while retaining it in the
same message store cell. At the same time as these operations occur, the
search register is reset and any message information which the user needs
is transferred from the message store ~ to the user port. The data transfer
is effected without deletion from the message store. Note that this
transfer may, in other applications of systems such as described herein, if
desired be effected with deletion. As the user is now in control of this
message, it may at this scan time or at a subsequent scan time insert into
the control store cell a label which enables the user to identify the message
element concerned.
As mentioned earlier, the messages contain 48-bit elements for
the message information: when a message is to be sent from a user
terminal, each of its elements has 32 bits of "housekeeping" information
added to it. This includes, inter alia, sequence numbers and error detection
information. These 32 bit housekeeping portions are generated locally in
the multiterminal user ports, each with 31 users. The generation uses time
divided logic. If a message element is retransmitted all but 7 of its 32
housekeeping bits may differ from what was previously sent. The
unchanged bits refer to the message's former sequence number, and in this
case it is the function of the user port's store to separate such bits from
the message elements from message housekeeping. These 32 bits of
signalling unit housekeeping are not passed on to the actual message user at
the far end of the signalling link.
When the search register is reset as described above, it is
available for determining the next message, if one is available, which
should be assigned for processing by that user.
- 12 -
~ r~
In ths system described herein, the user is assumed to be a
signalling terminal from which messages are sent to remote locations
(assumed to be telephone exchanges or administration centres). When a
message is assigned to be transmitted by such a terminal the first of the
message elements is given a seguence number in the numbering scheme of
the user terminal. If this number is n the second element of the message is
( n + 1), a cyclic code of seven bits being used. Thus when a control store
word which is not in the idle condition is scanned, it can, by virtue of the
control store logic - user port control interconnection cause the supply of
any requested one of the message elements to the user (signalling
terminal). Message elements are extracted from the message store 7 in
this manner both for transmission and for re-transmission.
In normal operation, a message remains in the message store 7
until a "handshake" control interconnection between the logic 1 and the user
5/6 results in the logic 1 taking the decision that the message whose control
word is being scanned has been processed by the user specified. When this
happens the message is functionally removed from the message store cell
by the erasure of the message's control word, which releases the message
cell for other use. Note that the message itself is not deleted since the
storage media used are such that when a new message is inserted into a
memory cell it over-writes (and thus in effect deletes) what is already in
that cell. If the memory medium used is such that deletion is necessary
before writing a new message in, then deletion of the message would be
effected either in response to the deletion of the contents of the control
store cell in use for that message or just before the insertion of a new
message.
--13 --
It is often desirable that messages of a particular priority can
be selected for preferential treatment. In the present system this is
catered for by the use of a message number to define the sequence in which
messages are entered into the dynamic store. ~ message numbering range
is supplied which is large and is adequate for the determination of the
sequence of messages as required.
The messages may be entered into the message store from many
sources each having its own message number generator, provided that all
messages which enter a particular queue are referenced by the same
message number generator. It is acceptable for a dynamic store to be used
to enable one source to feed a group of users, and another source to feed a
different group of users. This principle can be extended to cover as many
groups of users and associated sources with their own message number
generators as required.
In other applications than the multi-exchange network referred
to, the message number may be inserted by the dynamic store logic when a
message is accepted from one of a number of input ports.
In the telecommunication system application for which the data
storage system has been described, a message should only spend a relatively
short time in the dynamic store before being accessed and removed by the
user (or one of the users). Hence a time out facility is provided whereby
messages which have remained in the store beyond a designed limit are
removed. This time out would normally operate as a result of a
malfunction by one of the users or due to an overload: hence details of the
time out can be routed to a maintenance position.
'
~ - 14 -
7~
~ 3ecause of the large number of messages which may be handled
and assembled into queues by a single store, failure is undesirable, so the
complete dynamic store is engineered using triplicated logic and majority
voting techniques.
From the preceding description it will be appreciated that the
status of the user port is significant to the operation: the status is
transferred to the control logic 1 during the "handshake" control operation
so that it is available for use as required, e.g. for controlling change-over
from first choice user to second choice user.
In the system described herein, the data storage and message
queueing techniques are used only for messages outgoing from the system
processor to other distinct processors over common channel links. This is
actually, in the telecommunication network for which the system was
developed, part of a super-module unit which also serves to assemble and
despatch incoming messages via a message assembler and a FIFO queue
common to all 124 terminals. This in effect provides a separate channel for
messages going the opposite way to those dealt with by the queueing
technique referred to.
In one network using the system there is only one input port per
storage system, i.e. the inputs 9, 12, 17 in the drawing are not present.
However, another network has two input ports, and in those networks each
signalling link user port has one input queue per priority level per source.
Messages with a higher priority have precedence over those with a lower
priority, but within the same priority level messages are alternately
selected from each source of the same priority.
- 15 -
. . . ~.
Systems using the present techniques may have two or more
signalling links between a given pair of exchanges in addition to the speech
circuits therebetween. In such a case if one of the links fails the message
are all sent via the other link or links.
