PROCESS AND SYSTEM FOR THE DATA DISSEMINATION IN LOOP

Method and system for broadcasting

The invention relates to the broadcasting data in a loop.

More particularly, the invention is advantageously application for data broadcasting loop to a plurality of portable terminals on users in a given area.

The-loop data transmission is conventionally known and has been used in France in the teletext systems.

A problem generally encountered with the loop data broadcasting is that of the access time.

A user, to access a particular page, is to effect waiting for the portion of the file corresponding to what he is looking for is and is acquired by its receptor.

Methods tending to minimize the access time have already been proposed.

In particular, US 5.842.010 patent provides a method for the transmission data loop-which are intended to be displayed on screens of portable terminals receptors-wherein said data are broadcast in an order which is determined according to a statistical analysis on the needs of the users. The statistical analysis may be made requests of information fed back by users on the system that broadcasts the data.

However, the method is not optimal and does incidentally is of interest only so far that the data broadcast system used systematically causes each user experience data broadcast from a same first screen page diffused in the data loop.

Furthermore, it is also known, in particular for the teletext systems above, repeating in the broadcast loop those data blocks which are the most frequently accessed.

It should be noted however that in the teletext systems, the broadcast loop is generally frozen and does not know for change in the time.

The invention provides a method for broadcasting data in a loop with which the access time users are further improved.

To this end, the invention relates to a method for broadcasting by loop of a plurality of data blocks that correspond to objects or fragments or aggregates of objects such as alphanumeric messages and/or of the display pages, and/or graphical objects in pages displays and/or sound sequences, for be rendered by reproduction means available to users, characterized in that the data blocks is distributed by stacking more batteries according to priorities corresponding to different broadcast and repeating the step of taking at the output of each cell a number of data blocks that is a function of the delivery priority of said stack and broadcast the data blocks thus drawn from, the data blocks tapped from of each stack being, at each iteration, re-stacked in inlet thereof.

Such a method is advantageously supplemented by the various following characteristics, taken alone or in all their technically possible combinations:

-is received in real time information regarding the interest shown by the users in the various objects broadcast and modifying the numbers of data blocks sampled from a battery and/or changing the data blocks based on the cell information;

-the number of stacks is 3 or 4;

-the data blocks broadcast have a size of less than 400 bytes useful.

class-is the blocks broadcast data prioritizer consultation, the list thus formed is divided in K stacks of number of data blocks substantially equal and is disseminated data blocks of each stack with a frequency equal to or near

where j denotes the index of the cell, B the diffusion capacity, the battery size and

M

where n_{} =}[...], [...]

/ = I

Pi being the probability of consultation of an object described wholly or partly by the data block i, M is the number of data blocks in a stack.

aj-the numbers of data blocks taken at each iteration are such as to minimize

m-the number of data blocks in each stack is chosen to be a multiple of each of the numbers aj.

-introducing at least one padding data block in at least one stack.

-the number aj is chosen less than or equal to 9.

-objects common to several screens are transmitted once only.

-these objects are transmitted with a home page data block.

The invention also provides a system for broadcasting data in a loop comprising means for the radio broadcasting of data blocks in a given area, a plurality of portable terminals able to receive the data blocks thus radio broadcast, processing means which manage the data broadcast, characterized in that said processing means implement a method of the above type.

Other features and advantages of the invention shall become apparent of the description that follows. This description is purely illustrative and non-limiting. It should be read facing boards appended drawings on which:

-figure 1 is a schematic representation of a system according to a possible embodiment of the invention;

-figure 2 illustrates a possible architecture for this embodiment;

-figure 3 illustrates the optimization mechanism in the broadcast information;

-figure 4 is a graph on which is carried an example probability distribution for a number of objects to be broadcast.

The system which is represented in Figure 1 has a plurality of receiving terminals 1 and 2 for the infrastructure radio broadcasting data in a loop to the terminals 1.

The terminals 1 are, for example, hand-held computers of the type being marketed by the company 3COM under the name "Palm" or the type of those using the operating system EC Windows and marketed by the companies COMPAQ [...] and under the respective denominations "Cassiopeia" and "Aero".

Their They are provided with means for receiving the radio data continuously broadcasted by the infrastructure 2 and transmission of data to the infrastructure.

These means include an antenna for reception of radio-frequency signals, a modem standard 802,11 and software adapted to the system and whose functionalities will comprise is to the reading of the following.

The infrastructure 2 comprises a plurality of broadcast terminals 3 which together define, in an area where it is desired that the services offered by the system are accessible, one or more cells cover 4 optionally partially overlapping.

Diffusion The different terminals 3 are interconnected by a wired network 5 (Figure 2) Ethernet type and are provided with means of radio frequency broadcast, which process the information received from the network by said terminals to spread it into the aforementioned standard 802,11.

The data to be continuously broadcasted in particular are transmitted to said terminals 3 via one or more broadcast servers 6, connected to the network 5, transmitting on power "multicast" the data to be broadcast.

The system further includes one or more transactional servers 7 which transmit and receive, via the network 5, data "unicast" that correspond to transactions between the terminals 1 and the system, the terminals 3 comprising means for receiving radio data-scattered by the terminals 1 and further transmitted over the network 5.

Furthermore, the system also includes an administration server 8-also connected to the network 5-that oversees the functioning of the different servers terminals 3 and 6 and 7 and configures them.

If a dynamic IP addressing mode is retained, the system can also have an addressing server complementary.

The spraying process implemented by the diffusion or servers 6 consists of the periodic transmission by the terminals 3 to the receiver terminals 1 of data blocks, that correspond to objects that are to be rendered at the terminals 1 and which are for example alphanumeric messages and/or of the display pages, and/or graphical objects in pages displays and/or sound sequences.

The data blocks broadcast have a maximum size of 400 useful bytes, reducing the chance of transmission errors.

A fragmentation process/defragmentation may optionally be implemented for the transmission of objects whose description requires a number of upper bytes.

The sequence of data blocks scattered is updated in real time under the control of the broadcast server 6 taking into account a statistic is, for example, a statistic on the frequency of consultation the different pages of screen by users, the purpose of this control is to enable to deliver the users as quickly as possible the alphanumeric messages, screen pages, sound sequences, etc, which are likely to be of interest to them.

The statistic is established from look-up ratios are periodically transmitted by the terminal to the broadcast servers via the terminals 3. These ratios that give the list screens searched by the user of the terminal from sending the last report allow the broadcast servers know in real time the statistic look-up screens.

Each portable terminal 1 stores and updates the different data blocks as they are received. It powers down its radio modem as soon as all data blocks has been properly received and stored.

The broadcast server 6 receives, of editing stations 9 (Figure 1), which

it is for example connected via the network 5, a series of blocks of data (files) that describe the objects to be broadcast, and a file editing and instructions.

The server 6 distributes the data blocks to be broadcast according to more batteries that each correspond to a different priority class.

To each of the priority classes corresponds a nominal frequency of diffusion.

The initialization values-which are for example statistical functions prior-are given by the administrator of the service to these broadcast frequencies, and the broadcast frequencies are managed dynamically from the consultation reports transmitted by the terminals, if the dynamic mode has been selected.

After distributed the data blocks by classes, the server, within each class to aggregation blocks having the size is less than 80% of the maximum size to reduce the relative weight of the header UDP/IP or TCP/IP in the transmission. This aggregation includes encapsulating two or more objects in a same data block (same frame UDP). It does not extend to and management control messages which are transmitted with the data blocks, for example in the form of a prefix at the beginning of each frame sent.

Therefore, in each of the stacks corresponding to different priority classes is stored a sequence of data blocks, each of these blocks corresponding to objects or fragments or aggregate. The different data blocks of a same pile are broadcast to the frequency of the priority class to which said stack corresponds.

To be the diffusion cell which is emptied regularly broadcast to terminals 3, the server 6 takes successively in each class a number of data blocks. This operation is repeated continuously.

The number of sample into a class is different from a class to the other; it is all the greater as the priority of the class is high.

Figure 3 summarizes this mechanism. In the example selected, the data block numbers chosen for each loop are the following:

As aforesaid, to initialize the system, the broadcast frequencies target of the classes are set by the administrator, according to a predefined pattern which takes into account previous statistics for example.

As the consultation reports arrive at the server, it can, if the dynamic mode has been selected:

-change the class objects or blocks of data if their frequency of consultation is very different from that of the other data blocks constituting the class,

-changing the broadcast frequency classes to optimize the access time.

These modifications are performed after filtering for ensuring as the progress of the frequency look-up is a phenomenon and durable non-statistical a random variable.

An example detailed optimization processing possible can now be described.

The numbers of removal of the different priority classes are obtained by searching the integer solution giving frequencies for broadcasting messages, the closer to the theoretical values to optimize the time access means.

More specifically, optimization implemented by the system according to the invention release each data block i with a frequency as close as possible to a theoretical frequency f which checks:

where N is the number of service messages

L the size of the data block i in K0,

Pi the probability of consultation of an object described wholly or partly by the data block i,

and where B is the K0/s capacity of the portion of the channel assigned to the diffusion (PSC).

It is shown that this probability fj optimizes the time access means on the set of screens in the constrained to lie within the broadcast capacity available on the network.

Optimized The time access means is then

With a probability distribution typical consultation as that of the graph of Figure 4 (probability distribution by decile), an average size of the data describing the screens 15 K0, improving the average time access to a uniform diffusion is about 25%, this improvement reaches 60% for the first decile screens most accessed.

The price to be paid when the optimization strategy is used alone is the increase in the access time to the screens least accessed.

The following table summarizes the results of the simulations for a service of one hundred screens and for a network throughput 100 K0/s.

In practice, the data blocks to be broadcast are prioritized look-up.

The list thus classified is then divided into equal K cell (or sizes adjacent also as possible). Therefore, if N is the number of data blocks to be broadcast, E the function for the integer part, the [...] (Ν / [...] ) first blocks of the list are combined in a first stack, and the [...] (Ν / [...] ) following blocks are grouped together in a second cell, etc.

All the blocks of a same pile thus formed are then broadcast with a repetition frequency so close as possible to the theoretical frequency corresponding to the average probability of consultation of the objects of the stack.

For the stack j, this probability corresponds to the probability of consultation of any block, is:

M

= [...] :

i=1

wherein pj is the probability of consultation i-th block of the stack and where M is the number of blocks in a stack.

The theoretical frequency broadcast is to be be moved closer together to

the stack j is:

where t is the size (in K0) of each of the stacks.

The time look-up means of a block of the broadcast loop

is then given by:

the time T_{s being} an approximation of the time T_{op given time} higher.

The table below indicates deviations optimization report

at average time to the example given above (values obtained by simulation and the time means without optimization).

The table shows that the reduction in performance due to the limited number of cell remains very moderate compared to the simplification permitted in the broadcast server capable of being restricted the number of cells to three or four.

Furthermore, this distribution in stacks limit excessive access times for the objects or screens accessed which will have the least access times of the last stack.

At each iteration, the server takes ai data blocks in the stack 1, a2 data blocks in the stack 2, ... aj data blocks in the stack j, ... .,_{-k data blocks} in the stack K.

It is shown that the optimal solution would be obtained with:

equation that was generally not exact solution integer.

However, aj is selected numbers that are not too large so as:

-not to too disperse the data blocks likely to match a same object (screen for example);

-to permit creation of a diffusion length script of a packless acceptable excessive (see further).

In practice, nine is restricted in the number of data blocks taken at each cycle on the most accessed cell.

In order to achieve approximate resolution, is tested a table of possible values of K-tuples giving approximate values and probabilities 7tj minimizing the variation of the access means actually obtained:

T 2B VJ Σ-, -^{1° Σ [...] J}J TC,

and the desired value, which tends to minimize

The implementation of the diffusion algorithm is considerably simplified if can be replaced the pickup mechanism on the stacks by a script comprising the list of data blocks to be broadcast cyclically, the control messages being then broadcasted general and urgent priority in temporary interruption of the script.

For this purpose, it is necessary that in the course of the algorithm, all cells periodically return to the same position. This is thus possible that if the number m of each stack is a multiple of a-i, a2, aj, ... ak. If this is not the case, is added to each of them jam messages to reach the number searched.

Of course, it is desirable to retain preferably combinations which the least common multiple is as low as possible because the filler leads to a loss of efficiency.

With the example probability distribution of Figure 4, the values of %-_{s for} three and four stacks (Κ=3,4) would be the following:

K = 3 7 ¾ e {0.08; 0.18 ; 0.74}

K = 4 7ij e {0.04; 0.10 ; 0.24; 0.62}

The calculation of the function ε for these values give the triplet and the quadruple to be retained for the establishment of the diffusion or script:

K = 3 {2 ; 3 ; 6} ppcm = 6

K = 4 {2 ; 4 ; 6 ; 9} ppcm = 36

Some graphical objects as images or logos are often present in multiple screens. A strategy involves diffusing the data blocks their corresponding, often large, only once.

If for example a block of size t_{c is common to} two screens broadcast with the frequencies fi f2 (fi > h), is broadcast the common block with the greatest frequency fi thereby saving scattering ability [...] -

It should be noted however that, except for the screen most accessed with which the common object would be broadcast, this leads to an increase in the access time for the other screens using the block of data.

The use of common data blocks is therefore effective for screens different broadcast frequency but it remains disadvantageous for screens same frequency if no other action is taken.

This can, however, be compensated by using properly the structure sequences of pages of screens provided to users on a given site to cover one or more services for which the user has access.

When she connects to a site, any user first receives the home page of the site, followed by the site menu allowing the user to access homepages menus and different services present on the site.

To avoid increasing the access time due to common block, diffuses them at the same time that the graphical objects describing the entry page of the service concerned is it is (more likely) objects related to a single service, at the same time that the items of the home page of the site if it is objects used by more services.

The terminal will store the objects until the user leaves the service in the first case, the site in the other case.

When the terminal has sufficient memory, which is normally the case with handheld computers the type of the "Palm" or "Windows EC", can be improved significantly the quality of service using a cache.

When a user is viewing a screen, it can, usually by buttons or sensitive areas, navigate to other screens:

-the screen previously accessed;

-the menu of the current service and the site;

-the screens which the current screen accessible by links associated with the actions (buttons, etc).

It is easy to form a cover to gain instant access to the screens already accessed. For the last category of screens, the terminal determines, by exploiting the links actions, the list screens "contiguous downstream" of the current screen. By then multi-tasking capabilities of the operating system, the terminal screens charged while the user is browsing the current screen. Since a time look-up (5 to 10 seconds at minimum) is of the same order as the average time access to the screens, which is the case with services for over one hundred screens on a local area network, access to the contiguous downstream screens will appear nearly instantaneous to the user.

The terminal employs parallel a purge process of the cover to remove the descriptions of more screens which belong to the categories above assigned to the cache when the capacity is exceeded.

Furthermore, the broadcast server 6 is not supplying the access points that constitute the terminals 3 at a rate greater than their ability and diffusion is to allowing a sufficient time to the traffic caused by the transaction services, which result in exchanges between the transactional server 7 and the receiving terminals 1.

The ratio between broadcast services transaction services and is fixed by the administrator.

One will now describe the service implemented by the transactional server.

In the service, a number of displays and messages are common to all users; and these screens messages are transmitted in broadcast mode as described in paragraphs. The messages were integrated into the set of broadcast messages.

A terminal 3 between transactional mode when it detects the emission by a terminal 1 of a sequence for the transaction server 7 (sending an order form, purchase, request, etc).

The data exchange is effected "unicast" mode with the server 7 whose IP address is provided. It can be preceded by an exchange of control messages and in particular by the terminal providing its identifier.

The transaction services use the same protocol for the description of the screens that the broadcast services and its interactive portion for transactions.

The structure of the transactional servers is bonded to the nature of the services provided. The server software provides the programming interfaces required to perform the application section of the software. This can be performed on a remote machine while the transactional portion executes on a local machine.

In some cases simple it may coexist with the broadcast server on the same machine.

A specific transactional server manages the associated services: updating the list of users and their internet address, collecting on the distribution network services (DS) actually broadcast, Internet latest versions sending services to users with fixed periodicity.

Many applications may be contemplated for the method and system that just described.

The following table summarizes a number of examples of possible advantageous applications: