T 0318/10 (Load Distribution/CLUB IT) 02-09-2014
Download and more information:
SERVER/CLIENT SYSTEM, LOAD DISTRIBUTION DEVICE, LOAD DISTRIBUTION METHOD, AND LOAD DISTRIBUTION PROGRAM
Inventive step - (yes)
"Non-technical mathematical formulation" - (no)
I. The appeal is against the decision of the examining division, the reasons for which were dispatched on 9 November 2009, to refuse European patent application No. 03 780 885.4 for lack of inventive step, Article 56 EPC 1973, of the main and first, second and third auxiliary requests over the documents:
D1: EP 0 384 339 A2
D2: Leinberger W. et al., "Job Scheduling in the presence of Multiple Resource Requirements", Proceedings of the 1999 ACM/IEEE Conference on Supercomputing (SC'99), Article No. 47, New York, NY, USA, November 1999, ISBN 1-58113-091-0, XP010892825.
II. A notice of appeal was received on 16 December 2009, the appeal fee being paid on the same day. The appellant requested that the decision be set aside and also made an auxiliary request for oral proceedings.
III. In a statement of grounds of appeal, received on 5 February 2010, the appellant requested that the decision be set aside and a patent be granted on the basis of the claims of the main request on file. It further requested that the appeal fee be refunded, "since the Decision is not supported by the EPC", and an intermediate preliminary opinion be issued before any oral proceedings. Oral proceedings were conditionally requested in the event that the board could not grant the above requests.
IV. The board issued a summons to oral proceedings, giving in an annex its preliminary opinion that, although claim 1 of the main request seemed to meet the requirements of Article 56 EPC 1973 in view of the combination of D1 and D2, it was doubtful whether the application complied with Article 84 and Rules 29(2) and 35(13) EPC 1973 regarding conciseness and consistency of reference signs. It further did not appear that the conditions set out in Rule 103 EPC regarding the refund of the appeal fee were fulfilled, given that a different conclusion on inventive step, being a matter of substance rather than procedure, could not justify an allegation of a substantial procedural violation.
V. With a letter received on 30 July 2014 the appellant submitted amended claims and a complete amended description according to a new main request. The appellant requested that the appealed decision be set aside and that a patent be granted based on the documents of the main request. The auxiliary request for oral proceedings was maintained.
VI. In a further letter dated 26 August 2014 the appellant withdrew its request for refund of the appeal fee and requested that the board cancel the oral proceedings. The oral proceedings were subsequently cancelled by the board.
VII. The application documents according to the main request are as follows:
Claims:
1 to 6, received on 30 July 2014.
Description:
Pages 1 to 43, as received on 30 July 2014.
Drawings:
Sheets 1 to 15, as originally filed.
VIII. Claim 1 of the main request reads as follows:
"A server/client system in which a plurality of servers (101a, 101b to l0ln) and a plurality of clients (102) are connected through a network (100), and the servers (101b to l0ln) execute a process based on a process request from the clients (102) and transmit a process result to the clients (102), wherein at least one of the servers (101a) includes a process information receiving unit (401) configured to receive information on the process from the clients (102) through the network (100); a determining unit (402) configured to determine a server (101b to 101n) to execute the process from among the servers (101b to l0ln) based on the information on the process; and a server information transmitting unit (403) configured to transmit information on determined server (101b to 101n) to the clients (102), and each of the clients (102) includes a server information receiving unit (412) configured to receive the information on the server (101b to l0ln); and a process request transmitting unit (413) configured to transmit the process request to the determined servers (101b to 101n); characterised in that the determining unit (402) includes a first calculating unit (404) configured to calculate, for each of the servers, a first distance from an estimation point indicating an estimated consumption to an ideal consumption line, the estimated consumption obtained by adding an amount of resource to be consumed by execution of the process to a point indicating an amount of resource that has been consumed by each of the servers (101b to l0ln), the ideal consumption line being a straight line that connects an origin and a point indicating a maximum resource capacity of each of the servers (101b to l0ln) expressed in a space having parameters of resources as axes; and the determining unit (402) is configured to determine the server (101b to 101n) with the shortest first distance."
The claims according to this request also comprise corresponding independent method and program claims 3 and 5.
1. The admissibility of the appeal
In view of the facts set out at points I, II and III above, the appeal is admissible, since it complies with the EPC formal admissibility requirements.
2. The admittance of the main request
The main request was submitted in reply to the board's summons to oral proceedings and hence, according to Article 13(1) RPBA (Rules of Procedure of the Boards of Appeal; see OJ EPO 2007, 536), constitutes an amendment to the appellant's case. The board thus has a discretion whether or not to admit the request into the proceedings. Given that the amendments to the claims according to the main request address the board's doubts under Article 84 and Rules 29(2) and 35(13) EPC 1973 raised in the annex to the summons, the main request is admitted into the procedure.
3. The context of the invention
3.1 The application relates to a method of load distribution to assign a server from amongst a plurality of servers (figure 1, 101a to 101n) connected through a network (figure 1, 100) to a plurality of clients (figure 1, 102, 103) for the execution of a processing request from one of said clients (page 8, line 31, to page 9, line 5). The load distribution function can be installed on any server in the network (page 8, lines 19 to 30).
3.2 The load distribution method is illustrated in figures 5, 14 and 15 and explained on pages 14 to 15 and 29 to 34, where server 101a acts as the load distributor to processing servers 101b to 101n. Accordingly the load distribution device receives a request for the execution of a process from the client through the network (page 13, lines 2 to 4; page 14, lines 14 to 17; 501 in figure 5; page 30, lines 13 to 17; S1405 in figure 14; page 32, lines 29 to 33; (5) and 1502 in figure 15). A determining unit (402 in figure 4) within the load distribution device (page 12, lines 25 to 28) uses the results, calculated by its distance calculating unit (404 in figure 4; page 12, lines 29 to 30) based on the estimated resource consumption of the process, to determine the server to which the execution of the incoming process is to be assigned (page 13, lines 4 to 15; page 14, lines 17 to 25; 502 in figure 5; page 30, lines 13 to 27; S1407 in figure 14; page 33, lines 1 to 22).
3.3 Subsequently the load distribution device requests the selected server to process the request (page 14, lines 25 to 29; page 31, lines 10 to 18; S1408 in figure 14; page 33, lines 23 to 31; (8) and 1501a in figure 15). Figures 12 and 13 illustrate an example calculation based on two resources, namely CPU and memory, carried out by the distance calculating unit 404; see page 22, line 25, to page 24, line 31. Resources other than CPU and memory can also be used; see page 29, lines 8 to 10. In figures 12 and 13 the x-axis represents the CPU consumption and the y-axis the memory consumption (page 22, line 31, to page 23, line 4). The amount of resources used by processes, already assigned to and executing on servers 101b (figure 12, 1202) and 101c (figure 12, 1203), are depicted as steps of rectangles (figure 12, 1204, 1205, 1210 and 1211; page 23, lines 9 to 11 and 16 to 17). A straight line connecting the origin of the graph for each server with the intersection of the maximum possible values of CPU and memory consumption on that server yields the "resource consumption optimal line" (figure 12, 1206 and 1212) along which processes are distributed without any waste of either resource. For the selection of the optimal server for the process request 1201, its estimated resource consumption is added to processes already executing on each server (figure 12, dashed rectangles), thus shifting the total resource consumption for servers 101b and 101c to points 1209 and 1215, respectively.
3.4 The process is assigned to the server which has the shortest length for the normal (figure 12, 1208, 1214) drawn from the shifted coordinates 1209 and 1215 to the resource consumption optimal line 1206 and 1212 which indicates a more balanced resource consumption; see page 24, lines 19 to 31.
4. Conciseness of the claims and consistency of reference signs, Article 84 and Rules 29(2) and 35(13) EPC 1973
4.1 In the annex to the summons to oral proceedings the board expressed doubts under Article 84 EPC 1973 in combination with Rule 29(2) EPC 1973, regarding conciseness. In particular, the main request then on file had two independent claims in the apparatus category. This objection was addressed by the appellant by the deletion of one of the independent apparatus claims together with its dependent claim. The claims of the current main request comprise three independent claims each of which is in a different claim category. Thus the provisions of Rule 29(2) EPC 1973 are complied with.
4.2 In the annex to the summons to oral proceedings the board raised further doubts under Rule 35(13) EPC 1973, regarding the consistency of signs throughout the application. In particular, claim 1 of the main request then on file used the reference sign (411) for the "process request transmitting unit" which elsewhere in the description and figures was represented by the reference sign (413). This objection was addressed by the appellant by amending the reference sign (411) in claim 1 to (413). Thus the provisions of Rule 35(13) EPC 1973 are complied with.
5. Inventive step, Article 56 EPC 1973
5.1 In the appealed decision D1 was regarded as the closest prior art. The appellant has not disputed this.
5.2 D1 discloses a broker mechanism for allocating servers to clients to deliver services (see D1, figure 2: B is the broker; Si are the servers each providing a set of services Ai; Ci are the clients) based on a "network policy" and resource capacities of servers; see D1, abstract.
5.3 The following features of present claim 1 were identified in the appealed decision as differences over the disclosure of D1:
the determining unit includes
a first calculating unit configured to calculate, for each of the servers, a first distance from an estimation point indicating an estimated consumption to an ideal consumption line, the estimated consumption obtained by adding an amount of resource to be consumed by execution of the process to a point indicating an amount of resource that has been consumed by each of the servers, the ideal consumption line being a straight line that connects an origin and a point indicating a maximum resource capacity of each of the servers expressed in a space having parameters of resources as axes; and
the determining unit is configured to determine the server with the shortest first distance.
5.4 According to the reasons for the appealed decision, the examining division considered these differences to have the technical effect of allocating servers more efficiently. The problem to be solved by the invention was identified as how to allocate servers in a more efficient manner.
5.5 D1 mentions a "network policy" for allocating servers to clients, but does not disclose any specific allocation policy. According to the appealed decision, the skilled person knows that optimisation algorithms are commonly used for resource allocation and load balancing, thus the skilled person, starting from D1, would routinely look for a policy to efficiently allocate servers and would choose any optimisation algorithm providing this effect. As D2 discloses the idea of balanced resource utilisation, the skilled person would find document D2 and adapt its teaching, in particular the so-called "Backfill Balanced algorithm" (see below), to the context of D1.
5.6 D2 discloses improved heuristics for selecting backfilling jobs in First-Come-First-Serve (FCFS) scheduling algorithms. Backfilling allows, in the event that the job at the head of a FCFS job queue cannot be scheduled immediately, smaller jobs waiting further down in the queue to be scheduled immediately (see §2.1, second paragraph). A "greedy" approach, termed First-Fit (FF) backfilling, might create imbalances in resource usage (see §2.1, first paragraph and §2.2, last paragraph), so D2 proposes (see §3) two different heuristics, Backfill Lowest (BL) and Backfill Balanced (BB). BL looks only at the single lowest used resource (see §3, first and second paragraphs), whereas BB uses a balance measure to score each backfill job candidate and then selects the job which achieves the best resource utilization (see §3, third paragraph).
5.7 The board is not convinced that the skilled person would consult a document on optimal backfilling in FCFS scheduling when looking for a "network policy" for allocating servers to clients in the context of D1. Even if, for the sake of argument, the skilled person were to do so, in the board's view the combination of these two documents would more likely lead the skilled person to a load distribution policy based on FCFS-scheduling which could additionally implement backfilling using either the BL or the BB algorithm disclosed in D2, rather than that set out in claim 1.
5.8 However, assuming that the skilled person were to combine D1 and D2 in the manner argued in the decision, the board agrees with the appealed decision that the subject-matter of claim 1 would still differ from the combined disclosure of D1 and D2. In particular, the calculation of a distance between the estimated consumption point and the ideal consumption line, as defined in claim 1, is neither disclosed in D1 nor in D2.
5.9 The decision states that these "remaining differences refer only to non-technical mathematical formulation of the optimisation function". The appellant argued in the statement of grounds of appeal that this was a "clear misinterpretation of Art. 52(2)(c) in combination with Art. 56 EPC". As it is Article 52(2)(a) EPC which refers to mathematical methods, and not Article 52(2)(c), the board understands the appellant's criticism as referring to Article 52(2)(a) EPC. The board does not agree with the appealed decision that the mathematical formulation of the optimisation function used in a load distribution method in a computer network is non-technical, or, put another way, without technical effects. As stated in T 208/84 (Reasons, point 5) ("Computer-related invention/VICOM"; see OJ EPO 1987, 14), a basic difference between a mathematical method and a technical process can be seen in the fact that a mathematical method is carried out on numbers and provides a result also in numerical form, the mathematical method being only an abstract concept prescribing how to operate on the numbers and producing no direct technical result as such. In contrast thereto, if a mathematical method (in the present case the optimisation function) is used in a technical process (in the present case assigning a server from among a plurality of servers to process a client request), that process is carried out on a physical entity by some technical means implementing the method and provides as its result a certain change in that entity. In the present case the optimisation function as defined by claim 1 results in a change in the resource consumption of the server system which is a technical effect.
6. Hence the board is not convinced by the reasons for the finding in the decision that the subject-matter of claim 1 does not involve an inventive step.
7. Furthermore neither D2, nor common general knowledge, would lead the skilled person to supplement the teachings of D1 with the distance calculation and process request allocation techniques according to the present invention.
8. Consequently the board finds that the subject-matter of claim 1 involves an inventive step in the sense of Article 56 EPC 1973 in view of the combination of D1 and D2. The subject-matter of independent claims 3 and 5, which set out a corresponding load distribution method and load distribution program, respectively, is thus also considered to involve an inventive step.
9. Finally, the board does not see any remaining objections under other articles of the EPC, its doubts under Article 84 having been obviated, and no new objections caused, by the appellant's amendments.
For these reasons it is decided that:
1. The appealed decision is set aside.
2. The case is remitted to the first instance with the order to grant a patent on the basis of the main request.