Management of memory units of data streaming server to avoid changing their contents by employing a busy list of allocated units for each content and a free list of non-allocated units

[0002] The invention relates to a procedure for operating a server which supplies subscribers with data streams of different contents, as well as a server and a control unit employing this procedure.

[0003] The invention assumes a Video-on-Demand system as described e.g. in EP 0696872 A2.

[0004] Such a Video-on-Demand system consists of a video server connected to a large number of subscribers via a communication network. Each subscriber is provided with a set-top box connected to a television set. The video server is provided with a large number of memory units, in which video films of different contents are stored. The memory units feature video replay facilities which replay these video data sets and send the stream of video data so generated to a requesting subscriber. The video server is also provided with a control unit which allocates video replay resources to a requesting subscriber, and initiates the transmission of the requested video data stream to the requesting subscriber via the allocated resources. Resources no longer needed for a subscriber are marked as free. The allocation of such free resources is then carried out with the objective of sending a video data stream in parallel to the maximum number of subscribers, thus optimising the utilisation of the allocated resources.

[0005] It is an object of the invention to improve the efficiency of a server which supplies subscribers with data streams of different contents.

[0006] This task is solved by a procedure for operating a server (SERV) which supplies subscribers (SUB1 to SUB8) with data streams of different contents (CONT1 to CONT3), where during the procedure the different contents (CONT1 to CONT3) are each stored in at least one memory unit of the server and in order to supply a subscriber (SUB1 to SUB8) with the data stream of a particular content, the particular content is read back from a memory unit in which it is stored, and sent to the subscriber as a data stream, said method comprising the steps of: setting up a Busy list for each of the contents (CONT1 to CONT3) stored in the memory units (DSD1 to DSD9) of the server (SERV), with each memory unit (DSD1 to DSD4, DSD6 to DSD9) in which a content is stored being allocated to the Busy list of the content stored in it, and each memory unit (DSD5 to DSD9) which at that time is not needed for supplying a subscriber being allocated to a Free list, and selecting one of the memory units allocated to the Free list if a further memory unit becomes necessary for supplying a subscriber with a particular content, while first attempting to select a memory unit allocated to the Free list which is also allocated to the particular content's Busy list.

[0007] This invention is based on the idea of controlling the memory units in which the different contents are stored, with the aid of two kinds of lists: a Busy list set up for each available content and to which are allocated those memory units in which the corresponding content is stored, and a Free list to which are allocated those memory units not needed at that time. Examples of contents are video films, music or other data which might be of interest to a subscriber. If, in order to supply a subscriber with a particular content, further memory units are needed in which the particular content is stored, the first memory units selected for this purpose are those memory units from the Free list which are also allocated to the particular content's Busy list.

[0008] This has the advantage that the content of a memory unit needs to be changed far less often. On the one hand, such content changes are time-and resources-intensive. On the other, the memory unit is blocked whilst the content is changed. Thus, server operation in accordance with the invention significantly increases the server's performance.

[0009] Further advantageous configurations of the invention will be apparent from the description below and the appended claims.

[0010] It is especially advantageous to represent the memory units through objects and to set up the Free list and the Busy lists by concatenating these objects. This results in a data structure which allows the operational procedure to be simply executed.

[0011] In the following, the invention is explained with the aid of several implementation examples and with reference to the attached diagrams.

[0012] FIG. 1 shows a block diagram of a system with a server in accordance with the invention and a control unit in accordance with the invention.

[0013] FIG. 2 shows a functional representation of a section from a data structure used by the server as per FIG. 1.

[0014] FIG. 3 shows a detailed functional representation of the data structure used by the server as per FIG. 1.

[0015] FIG. 1 shows the servers SERV, CS1 and CS2, the communication networks KN1 and KN2 and the subscribers SUB1 to SUB8. The subscribers SUB1 to SUB8 are connected via the communication network KN1 with the server SERV, which in turn is connected via the communication network KN2 with the servers CS1 and CS2.

[0016] The servers SERV, CS1 and CS2 are each made up of specially designed computer workstations. Server SERV stores data sets with different contents, which are read out by server SERV and sent on request, as a continuous data stream, across the communication network KN1 to the subscribers SUB1 to SUB8.

[0017] Each data set consists of video data which describe a particular content, for example the video data of a special video film. However, it is also possible for a data set to be put together from multimedia data, audio data or other data, which are transmitted essentially synchronously by the terminal devices of subscribers SUB1 to SUB8 via the appropriate output method to the relevant subscriber.

[0018] The number of servers CS1 to CS2 is chosen arbitrarily in this example. Servers CS1 to CS2 store a large number of data sets with different contents, of which each individual content can be downloaded on request across the communication network KN2 into the server SERV or into other servers, similarly constructed.

[0019] The number of subscribers SUB1 to SUB8 is chosen arbitrarily in this example. Each of the subscribers SUB1 to SUB8 has a terminal device for communicating with the server SERV in the form of a video replay set, for example a television set, equipped with a set-top box for accessing the server SERV. Such a terminal device and an associated communication network which connects this terminal device with the server SERV is described, for example, in the paper “The IVOD Berlin Project: Access Technology for Service Provisioning, R. Heidemann, Alcatel Telecommunications Review, 3rd Quarter 1996, pp. 196 to 200.

[0020] It is also possible for the subscribers SUB1 to SUB8 to have a terminal device in the form of a computer workstation, provided with peripheral modules for communicating via the communication network KN1 and for outputting contents supplied by the server SERV. Such terminal devices are, for example, networked computers, personal computers or information terminals.

[0021] The communication network KN1 consists of an access network, across which the terminal devices of subscribers SUB1 to SUB8 are connected via hybrid fibre coax, via cable modems, via ISDN (Integrated Service Digital Network) or via ADSL (Asymmetrical Digital Subscriber Line). In particular, if a large number of subscribers are connected to the communication network KN1, it is advantageous for the communication network KN1 to be provided with several access networks, under certain circumstances of different types, and with a backbone network that connects the access networks with each other and with the server SERV. A suitable choice for a backbone network would be, for example, an ATM (Asynchronous Transfer Mode) or an SDH (Synchronous Digital Hierarchy) network.

[0022] It is also possible for the terminal devices of subscribers SUB1 to SUB8 to be connected to the communication network KN1 across an ATM interface. Where the terminal device is a computer workstation, it is of further advantage if the communication network KN2 is an IP network (IP=Internet protocol), for example a so-called Fast Internet.

[0023] The communication network KN2 is a broad-band data network, for example an ATM, FDDI or DQDB network (FDDI=Fibre Distributed Data Interface, DQDB=Distributed Queue Dual Bus).

[0024] From a functional viewpoint, the server SERV features several memory units, of which FIG. 1 shows as an example the memory units DSD1 to DSD5, and a control unit CONTR, which in turn features a memory control unit MCONTR and a loading unit LOAD.

[0025] Each of the memory units DSD1 to DSD5 is provided with a memory for storing a content. It is advantageous for the memory units DSD1 to DSD5 to have physically separate memory modules, each of which has sufficient capacity to store a content, e.g. a video film, preferably in digital form. Thus, for example, they may each be provided with a disc drive or digital memory chips permanently allocated to them. It is, of course, also possible for the memory units DSD1 to DSD5 to have allocated to them logical memory domains in a common memory module.

[0026] In each of the memory units DSD1 to DSD4 there is stored, for example, a content CONT1, CONT2, CONT3 or CONT3, and no content is stored in the memory unit DSD5. The memory units DSD1 to DSD5 are accessed by replay resources. When these are activated, they read out the content stored in the relevant memory unit, reproduce it and send the continuous data stream so generated across the communication network KN1 to one of the subscribers SUB1, or in parallel to several of them. It is advantageous for replay resources to be permanently allocated to a memory unit, each memory unit thus being provided with its own replay resources. The content of a memory unit is so stored that multiple parallel read-out is possible. Hence, several subscribers can be served simultaneously by one memory unit. Thus, for example, memory unit DSD1 supplies subscribers SUB1 and SUB2 with the content CONT1, memory unit DSD2 supplies subscriber SUB3 with the content CONT2 and memory units DSD3 and DSD4 supply subscribers SUB4 to SUB8 with the content CONT3.

[0027] The control unit CONTR controls the preparation of contents and the supply of subscribers with contents. It is also possible for the control unit to be responsible not for one server but for several servers, and to exercise these functions for all these servers centrally. In this event, such a control unit can also form part of a central control node that controls the preparation of contents via a whole group of servers.

[0028] The memory control unit MCONTR controls the allocation of memory units DSD1 to DSD5 to subscribers. If the memory control unit MCONTR receives a request message from a subscriber in which the latter requests a particular content, the memory control unit MCONTR selects one of the memory units DSD1 to DSD5 and causes it to supply the requesting subscriber with the requested content. If it is necessary, for this purpose, to load a new content into the selected memory unit, it sends an appropriate control message to the loading control unit LOAD.

[0029] The loading control unit LOAD loads contents into the memory units DSD1 to DSD5. For this purpose it requests the contents from the central servers CS1 to CS2, receives them via the broad-band network KN2 and then loads them into the appropriate memory unit. If the content that needs to be loaded is already stored in another memory unit of server SERV, it copies the content from this memory unit into the memory unit that needs to be loaded. It is also possible for the loading control unit LOAD to be provided with a database in which copies of contents are stored, and contents are copied from this database into memory units.

[0030] The detailed operating method of the memory control unit MCONTR will now be explained with reference to FIG. 2.

[0031] The memory control unit MCONTR allocates memory units to subscribers, and for this purpose carries out essentially the following functions: it selects a memory unit whose task it is to supply the requested content to the requesting subscriber. The objective of this selection is to optimise the utilisation of the memory units' capacity. It also ascertains which memory units are free at that time and are not supplying a subscriber with a content, in order to store in these free memory units new contents or further copies of contents. The objective of selecting between free memory units is to avoid, as far as possible, changing the content of memory units.

[0032] In order to carry out these functions, the memory control unit MCONTR maintains two types of lists. The first is a Busy list for each content available in the server SERV. The Busy lists hold a record of those memory units in which the relevant content is stored at that time. The second is a Free list, to which a memory unit is added as soon as it no longer supplies any subscribers with contents. It is advantageous to implement these lists as a data structure in which objects are concatenated into lists, as shown in FIG. 2. Of course, it is also possible to implement these lists in some other way, for example as separate lists in a database.

[0033] FIG. 2 shows a content database CDB and two objects DO1 and DO2.

[0034] Each of the objects DO1 and DO2 represents a memory unit. For each of the memory units of server SERV, such an object is controlled by the memory control unit MCONTR. The structure of these objects will now be explained, using object DO1 as an example.

[0035] Object DO1 features seven data fields CIP, MB, UB, PAT, FF, PODL and PFDL. The data field CIP contains a content identification password that describes the content stored in the memory unit. The data field MB contains a value that describes the maximum memory unit's bandwidth, i.e. the maximum number of parallel data streams it can provide. The data field UB contains a value that describes how much of the maximum bandwidth is being used at the time. The data field PAT contains a value that describes the projected time till the arrival of another request for the content stored in the memory unit. The data field PODL and PFDL contain pointers that indicate other objects. If no such object is present, these data fields contain a null pointer. The data field PODL contains a pointer to a Busy list and the data field PFDL contains a pointer to the Free list. The data field FF contains a status variable that indicates whether the memory unit stores a content or not.

[0036] The content database CDB consists of a list of data sets. Such a data set is stored in this list for each content stored in the server SERV. FIG. 2 shows the data set DS1 as an example of such data sets. Data set DS1 features, inter alia, the data fields CIP and PODL.

[0037] Thus, the Busy lists are formed as follows: a data set, for example the data set DS1, is held in the content database CDB for each available content. The data set always points to the first object of the allocated Busy list, which in turn points to the second object etc. The last object in the list contains a null pointer in its data field PODL.

[0038] When an additional copy of the content of a memory unit is stored, the associated object is removed from its current Busy list and attached to the Busy list of this content. The pointer in the data field PODL of the old Busy list's preceding object is overwritten with the object's corresponding pointer. The null pointer of the last object in the new Busy list is overwritten with a pointer to this object, and the null pointer is written into the data field PODL of this object, so that this object now becomes the new last object in this Busy list.

[0039] When a memory unit no longer makes its content available to subscribers, the object representing it is inserted into the Free list. Insertion into the Free list does not mean here that the content stored in the memory unit is deleted, but that the memory unit is a potential candidate for having the content stored in it replaced by another content. As soon as the memory unit is again allocated to a subscriber and makes its content available to him, it is removed once again from the Free list.

[0040] The adding and deleting of objects to and from the Free list and Busy lists will now be explained with reference to FIG. 3:

[0041] FIG. 3 shows the content database CDB with the data set DS1 and data sets DS2 and DS3, as well as nine objects DO which represent the memory units DSD1 to DSD5 and the memory units DSD6 to DSD9 of the server SERV, not shown in FIG. 1. Memory units DSD6 to DSD9 store the contents CONT1, CONT2, CONT2 or CONT3, however at this time the contents are not supplied to any subscribers.

[0042] The data sets DS1, DS2, and DS3 are allocated to the contents CONT1, CONT2, or CONT3. The data set DS1 points to the object representing the memory unit DSD1, which in turn points to the object representing the memory unit DSD6. This forms the Busy list for the content CONT1, to which the memory units DSD1 and DSD6 are thus allocated. In the same way, data sets DSD2 and DSD3 are concatenated with objects representing the memory units DSD2, DSD7 and DSD8, OR DSD3, SD4 and DSD9, which forms the Busy lists for the contents CONT2 and CONT3. No content has yet been loaded into memory unit DSD5, thus it is not allocated to any of the Busy lists. The free list is formed by concatenating the objects allocated to memory units DSD5, DSD8, DSD6, DSD7, and DSD9 between a starting point ST and an end point EN.

[0043] Objects such as those of memory unit DSD5, allocated to the Free list and to no Busy list, for example because they do not yet store any content, are arranged at the beginning of the Free list.

[0044] The following two possibilities exist for memory units allocated to the Free list and to one of the Busy lists:

[0045] They are instructed to supply a subscriber with their content, and are thus removed from the Free list.

[0046] They are required to supply a subscriber with a content other than the one stored in them. Hence another content is loaded into them, thus they are allocated to a different Busy list and are removed from the Free list.

[0047] It is also possible for memory units to be loaded by the memory control unit MCONTR with other contents on the basis of statistical calculations, which estimate in advance the bandwidth demanded by a particular content; hence they are allocated to another Busy list but remain in the Free list. Thus it is possible to respond very rapidly to subscribers' requests.

[0048] When a subscriber requests a content to be supplied, the control unit MCONTR first selects the first object from the Busy list allocated to the requested content. If the available bandwidth of the memory unit represented by this object is insufficient to meet the request, the next object in the Busy list is selected and so on. This achieves full utilisation of the bandwidth available to a memory unit, before the next memory unit in the Busy list is used. In this way, the maximum number of free memory units are available to the next request.

[0049] If a selected object is one that is also allocated to the Free list, it is removed from the Free list. If no further object is contained in the requested content's Busy list, the first object in the Free list is selected and the requested content loaded into the memory unit represented by this object. The object is attached to the end of the Busy list and removed from the Free list. If the memory units which already supply subscribers with the content have no more free capacity, the result is that the objects that are automatically selected first from the Free list are also allocated to the content's Busy list. Only then is an object selected from the Free list, for which a change of content is necessary. This minimises the number of content changes.

[0050] It is an advantage not to allocate memory units which become free to the end of the Free list, but to determine their position within the Free list in accordance with the following calculations:

[0051] If a memory unit is not allocated to any Busy list, it is placed at the beginning of the Free list. Such a situation is indicated by the status variable recorded in the data field FF. The beginning of the Free list is thus constituted from the objects that represent such memory units.

[0052] The remaining objects in the Free list are sorted in accordance with the probability that the content of the memory units represented by them would be needed next or not. If this probability is high, then the associated object is placed at the end of the Free list. Insertion in the Free list is controlled here via the parameter recorded in the data field PAT, which is a measure of accessing probability. This parameter is recalculated each time the object in which it is recorded is allocated to the Free list.