GB1581061A

GB1581061A - Data storage system

Info

Publication number: GB1581061A
Application number: GB349/77A
Authority: GB
Original assignee: Standard Telephone and Cables PLC
Current assignee: STC PLC
Priority date: 1978-08-30
Filing date: 1978-08-30
Publication date: 1980-12-10
Also published as: AU5019579A; NZ191357A; AU531397B2; AU4113178A; AU519354B2; ZA794213B; DE2848163A1; FR2440135B1; PT70092A; FR2440135A1

Description

(54) IMPROVEMENTS IN OR RELATING TO DATA STORAGE SYSTEMS (71) We, STANDARD TELEPHONES AND CABLES LIMITED, a British Company of 190 Strand, London W.C.2, England, do hereby declare the invention, for which we pray that a patent may be granted to us, and the method by which it is to be performed, to be particularly described in and by the following statement : -- 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 such 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.

An object of the invention is to provide a data storage system suitable for use in such systems or in other systems where large quantities 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 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 arranged to contain information indicating whether its said message cell is in use and the identity of the user port concerned if its said message cell is in use, scanning means adapted to scan the control cells sequentially and when one of said user circuits has a message to be stored to select a free message cell for that message, control means responsive to said selection to route a said message for which storage is needed into the selected free message cell, and means responsive to said routing to amend the contents of the control cell associated with the message cell into which the message has been routed to indicate that that message cell is in use and to identify the user port for which the message cell is in use, in which each said message has a message header which identifies the user port by which the message is to be dealt with plus a priority-indicating code for that message, in which when two or more messages destined for the same user port have been stored in respective ones of the message cells those messages are assembled into one or more queues, each such queue in duding messages of the same priority, in which when a said message is inserted into a said message cell the control word in the control appropriate to that one of said message cells is set to a "message inserted" state appropriate both to the message's priority and the appropriate one of such user ports, thus setting up the said one or more queues, in which if the scanning by said scanning means finds a control store whose content indicate that the message cell associated therewith is in use address selection means causes the user port for which the message in that message cell is destined to be addressed, and in which when a user port is thus addressed control operations take place between the control store, the message store, the control means and the addressed user port, which operations depend on the current status of the user port and the contents of said stores, said operations including, when the user ports' statuses permit, the handling of the stored messages in an order determined by their priorities and by the time at which those messages were inserted into the message store.

An embodiment of the invention will now be described with reference to the drawing accompanying the Provisional Specification.

The present invention is of wide applica tion, 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 destionation 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 systems' message 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. 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 pre- sent 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 storage 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.

Thus the message in a message cell may be a message in any of the input or other queues associated wtih 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 stored 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 information 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 result of the message being scanned, so message elements can be extracted for transmission or retransmission, as required by the user.

The drawing accompanying the Provisional Specification 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 the 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.

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 readwrite control via connection 15 to the message store, which is also accessible via connections such as 16, 17 from message sources. In addition it has access via connections such as 18 to one or more user buffers. Note that many of these connections would in fact be multi-wire connect tions.

The purpose of the control connections are summarised as follows: 8, 9 Control "handshake" with source/buffer 3/4 10 Control "handshake" with user port control 5 11. 12 Message header control infor mation written in the control element of a message.

13 Address, read-write, control information for modification of control element 14 Control element of message 15 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. If the first choice user is unable to process the message, that message is 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 first-in-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 asssociated 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 message number and the message length. 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 message in each of these queues are dealt with in chronological order, i.e. on a FIFO 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 latter case the message control cell effectively belongs to the second choice user.

We now consider the operation ot 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 if 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 "message inserted" 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 operational 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 the user code. A "handshake" 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 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 after 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 FIFO 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 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, er (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 en tered the message store earlier than did the one whose details are in the search register, then the search 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, then 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 queues, 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 7 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 for message housekeeping. These 32 bits of signalling unit 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.

In the 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 sequence' number in the numbering scheme of the user terminal. If this number is n the second element of the message is (n+l), 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 retransmission.

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.

It is often desirable 'that messages of a particular priority can be selected for pre ferential 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. A message numbering range is supplied which is large and is adequate for the determinatidn 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 generatdr, proW vided 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 multiexchange 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 td an overload: hence details of the time out can be routed to a maintenance position.

Because 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 od 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. Mes sages wtih 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.

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 messages are all sent via the other link or links.

WHAT WE CLAIM IS:- 1. A data storage system, which includes a number of ports each associated with a user 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 arranged to contain information indicating whether its said message cell is in use and the identitfy of the user port concerned if its said message cell is in use, scanning means adapted to scan the control cells sequentially and when one of said user circuits has a message to be stored to select a free message cell for that message, control means responsive to said selection to route a said message for which storage is needed into the selected free message cell, and means responsive to said routing to amend the contents of the control cell associated with the message cell into which the message has been routed to indicate that that message cell is in use and to identify the user port for which the message cell is in use, in which each said message has a message header which identifies the user port by which the message is to be dealt with plus a priority-indicating code for that message, in which when two or more messages destined for the same user port have been stored in respective ones of the message cells those messages are assembled into one or more queues, each such queue including messages of the same priority, in which when a said message is inserted into a said message cell the control word in the control appropriate to that one of said message cells is set to a "message inserted" state appropriate both to the message's priority and the appropriate one of such user ports, thus setting up the said one or more queues, in which if the scanning by said scanning means finds a control store whose contents indicate that the message cell associated therewith is in use address selection means causes the user port for which the message in that message cell is destined to be addressed, and in which when a user port is thus addressed control operations take place between the control store, the message store, the control means and the addressed user port, which operations depend on the current status of the user port and the contents of said stores, said operations including, when the user ports' statuses permit, the handling of the stored messages in an order determined by their priorities and by the time at which those messages were inserted into the message store.

2. A system as claimed in claim 1, in which each said message's header on reception includes the identification of first and second users, each corresponding to one of said user ports, for the handling of that message, in which on the first occasion at which the control store cell appropriate to a said received message is scanned after the message has been inserted into its said message store cell, said control means tests the user port for the first choice user to see if it can perform the required message handling, in which if the test indicates that the first choice user can so perform the message is routed thereto, and in which if the test indicates that the first choice user is unable to so perform the message is routed to the port appropriate to the second choice.

3. A system as claimed in claim 2, in which each said user port to which a message can be sent for handling, e.g. for transmission from the system, includes a search register which indicates the message number and priority of the message allotted to that user port on the last scan of the scanning means, in which on said scan of a said control cell the contents of that control cell which contains a control word appropriate to a said user are sent thereto for comparison with the contents of that user's search register, and in which if the control word information thus sent corresponds to a higher priority message or an older message of the same priority than that in the search register, the contents of the search register are modified in accordance therewith, the contents of the search register defining the message to be handled when that user port is free to handle a message.

4. A data storage system as claimed in claim 3, in which when a said user port is free to handle a message a control signal is sent to that message's control word to re move the message from a said queue, but not to delete the message from the message cell, and in which at the same time the search register is reset to its rest condition wherein it can accept information in re spect of another message, and the message thus removed from the queue is sent to the port to be dealt with.

5. A data storage system as claimed in claim 4, in which each said message con sists of one or more multi-bit message blocks to each of which blocks there is ap- pended for transmission from the message

**WARNING** end of DESC field may overlap start of CLMS **.

Claims

**WARNING** start of CLMS field may overlap end of DESC **. sages wtih 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. 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 messages are all sent via the other link or links. WHAT WE CLAIM IS:-

1. A data storage system, which includes a number of ports each associated with a user 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 arranged to contain information indicating whether its said message cell is in use and the identitfy of the user port concerned if its said message cell is in use, scanning means adapted to scan the control cells sequentially and when one of said user circuits has a message to be stored to select a free message cell for that message, control means responsive to said selection to route a said message for which storage is needed into the selected free message cell, and means responsive to said routing to amend the contents of the control cell associated with the message cell into which the message has been routed to indicate that that message cell is in use and to identify the user port for which the message cell is in use, in which each said message has a message header which identifies the user port by which the message is to be dealt with plus a priority-indicating code for that message, in which when two or more messages destined for the same user port have been stored in respective ones of the message cells those messages are assembled into one or more queues, each such queue including messages of the same priority, in which when a said message is inserted into a said message cell the control word in the control appropriate to that one of said message cells is set to a "message inserted" state appropriate both to the message's priority and the appropriate one of such user ports, thus setting up the said one or more queues, in which if the scanning by said scanning means finds a control store whose contents indicate that the message cell associated therewith is in use address selection means causes the user port for which the message in that message cell is destined to be addressed, and in which when a user port is thus addressed control operations take place between the control store, the message store, the control means and the addressed user port, which operations depend on the current status of the user port and the contents of said stores, said operations including, when the user ports' statuses permit, the handling of the stored messages in an order determined by their priorities and by the time at which those messages were inserted into the message store.

store to the user port a further multi-bit portion, and in which each said further multi-bit portion includes sequence number and error-detection information.

6. A data storage system as claimed in claim 5 in which when a message sent to a user port has been dealt with a signal is sent from that user port to the system control means, which thereupon deletes the contents of that message's control cell, so that that control cell and the associated message cell are now available for use for a new message.

7. A data storage system as claimed in any one of the preceding claims, and in which the data storage system forms part of one of the nodes of a multi-node telecommunication system, each said user port being a signalling terminal serving one or a number of links each of which arrives from and/or extends to a remote node of the telecommunication system.

8. A data storage system substantially as described with reference to the drawing accompanying the Provisional Specification.

9. A telecommunication system using a data processing system as claimed in any one of claims 1 to 11.