T 2227/09 (Allocation of computational jobs/SAP) of 27.3.2014

European Case Law Identifier: ECLI:EP:BA:2014:T222709.20140327
Date of decision: 27 March 2014
Case number: T 2227/09
Application number: 08004547.9
IPC class: G06F 9/50
Language of proceedings: EN
Distribution: D
Download and more information:
Decision text in EN (PDF, 369.318K)
Documentation of the appeal procedure can be found in the Register
Bibliographic information is available in: EN
Versions: Unpublished
Title of application: Multi-objective allocation of computational jobs in client-server or hosting environments
Applicant name: SAP AG
Opponent name: -
Board: 3.5.06
Headnote: -
Relevant legal provisions:
European Patent Convention R 111(2)
European Patent Convention R 103(1)(a)
European Patent Convention 1973 Art 113(2)
European Patent Convention 1973 Art 83
European Patent Convention 1973 Art 111(1)
Rules of procedure of the Boards of Appeal Art 11
European Patent Convention 1973 R 67
Keywords: Basis of decision - substantial procedural violation (yes)
Fundamental procedural defect - (yes)
Remittal to the department of first instance - special reasons for not remitting the case
Remittal to the department of first instance - (yes)
Sufficiency of disclosure - (yes)
Reimbursement of appeal fee - (no)
Catchwords:

-

Cited decisions:
T 0763/04
Citing decisions:
-

Summary of Facts and Submissions

I. This is an appeal against the decision, dispatched on 20 August 2009, by the examining division to refuse European patent application No. 08 004 547.9 for the reasons given in its communication dated 20 February 2009. According to that communication, the application did not comply with Articles 83 and 56 EPC regarding sufficiency of disclosure and inventive step, respectively.

II. In response to the above-cited communication the applicant, with a letter dated 19 March 2009 and received on 20 March 2009, filed a set of amended claims and inter alia provided arguments in support of the sufficiency of disclosure, Article 83 EPC.

III. Following this response the examining division issued a summons to oral proceedings dated 1 July 2009 together with an annex maintaining the previously raised objections under Articles 83 and 56 EPC and discussing the arguments provided by the applicant in the above response.

IV. In a further letter of response, received on 24 July 2009, the applicant stated that it would not attend the oral proceedings and requested a decision according to the state of the file. The oral proceedings were subsequently cancelled.

V. A notice of appeal was received and the appeal fee paid on 8 September 2009. The appellant requested that (a) the appealed decision be set aside, (b) a date be set for oral proceedings if request "a" were not allowed in written proceedings or if the board, for some other reason, intended to issue a decision adverse to the appellant and that (c) an "intermediate Official Action" be issued before setting a date for oral proceedings.

VI. With a statement of grounds of appeal, received on 31 October 2009, the appellant filed a set of amended claims. The appellant requested, as a main request, that the appealed decision be set aside and that a patent be granted on the basis of the claims on file and, as an auxiliary request, grant of a patent based on the claims received with the statement of grounds of appeal. The appellant also made auxiliary requests, prior to any adverse decision by the board, for an informal interview, a telephone conversation and oral proceedings, in that order.

VII. The application documents on file are as follows:

Description:

Pages 1 to 36, as originally filed.

Claims:

Main request: 1 to 19, received on 20 March 2009.

Auxiliary request: 1 to 19, received with the statement of grounds of appeal.

Drawings:

Sheets 1 to 8, as originally filed.

VIII. The claims contain expressions in parentheses using the digit "1" as well as the letter small "L" ("l"), which in some typefaces can appear to be the same. The statement of claims according to the main request comprises three independent claims, claim 1 reading as follows:

"A method of processing a computational job with a plurality of processors, the method comprising: defining a number (l, 1<=l) of different priority levels that can be assigned to different computational jobs; defining a subset (c, 1<=c<=l) of processors for each priority level that can be assigned to a job; receiving a request to process a job, wherein a priority level (u, 1<=u<=l) is associated with the job; designating a first group of the processors as being available to process the job, wherein the first group of processors comprises all processors in subsets (c, c>=u) of processors which are defined for priority levels (c) greater than or equal to the priority level (u) associated with the job; designating a second group of the processors as being available to process the job, wherein the second group of processors comprises processors in subsets of processors which are defined for priority levels lower than the priority level associated with the job (c<u) and wherein for each processor in the second group a current utilization rate (UciM) of the processor is less than a second predetermined utilization rate (Ucu) for the processor, wherein the second predetermined utilization rate (Ucu) for the processor is stored in a database and is based on a combination of the priority level of the job (u, 1<=u<=l) and the subset of processors (c, 1<=c<=l) to which the processor belongs, the second predetermined utilization rate being predefined for all processors in the subset of processors to which the processor belongs; and processing the job with one or more of the processors selected from the first group of processors and the second group of processors."

Independent claim 9 reads as follows:

"A method of processing a computational job with a plurality of processors, the method comprising: defining a number (l, 1<=l) of different priority levels that can be assigned to different computational jobs; defining a subset (c, 1<=c<=l) of processors for each priority level that can be assigned to a job; processing a plurality of computational jobs with the plurality of processors; designating a first group of the processors as being available to process a first job, wherein the first group of processors comprises all processors in subsets (c, c>=u) of processors which are defined for priority levels greater than or equal to a priority level (u, 1<=u<=l) associated with the first job; designating a second group of the processors as being available to process the first job, wherein the second group of processors comprises processors in subsets of processors which are defined for priority levels lower than the priority level associated with the job (c<u) and wherein for each processor in the second group an initial current utilization rate (UciM) of the processor is less than or equal to a predetermined utilization rate (Ucu) for the processor wherein the predetermined utilization rate (Ucu) for the processor is stored in a database and is based on a combination of the priority level of the first job (u, 1<=u<=l) and the subset of processors (c, 1<=c<=l) to which the processor belongs, the second predetermined utilization rate being predefined for all processors in the subset of processors to which the processor belongs; and processing the first job with a plurality of processors selected from the first group of processors and from the second group of processors; determining that a processor in the second group that is processing the first job has an updated utilization rate that is greater than the predetermined utilization rate; and then in response to the determination, processing the first job with a plurality of processors selected from the first group of processors and the second group, not including the processor that had a utilization rate greater than the first predetermined utilization rate."

Independent claim 11 sets out a system for processing a computational job, the features of the system corresponding to the method features set out in method claim 1.

IX. The wording of the claims according to the auxiliary request is immaterial to the present decision.

Reasons for the Decision

1. The admissibility of the appeal

In view of the facts set out at points I, V and VI above, the appeal fulfills the admissibility criteria under the EPC and is consequently admissible.

2. The context of the alleged invention

2.1 The application relates to assigning computational jobs from different customers to physical computing resources comprising many processors in a client-server or hosting environment.

2.2 The application acknowledges as prior art that it is known to make the processing of customer requests as independent as possible from the actual hardware resources; see paragraphs [0002 to 0003]. To do this the hardware is treated as a plurality of "virtual machines", these being defined as "collections of individual physical resources". It is also known for a scheduler to allocate computational jobs to predefined virtual machines and for a load balancer to distribute currently running tasks by moving virtual machines so that all resources within the system have a similar utilization, thus maximizing the overall throughput of computational jobs within the system.

2.3 The alleged invention as claimed however relates to processing computational jobs with a plurality of "processors". According to paragraph [0023], the processors may contain a processing core and have access to memory and can be any type of processing device adapted for performing a computational job, for instance server computers, blade servers, personal computers and individual processors. The processors can also be realized as a multi-core system on a chip ("SOC"); see figure 3 and paragraph [0028].

2.4 Customers are typically seeking high availability of computing resources and short response times, and the service provider seeks to provide different levels of service, set out in a service agreement, in terms of resource availability and response time depending on the amount the customer is willing to pay. Hence the jobs for the highest paying customers receive the greatest availability of computational resources, whilst the jobs for other customers receive less, but still adequate, availability of computational resources, unless resources are heavily used.

2.5 The known job allocation methods acknowledged in paragraph [0005] result in sub-optimal system resource utilization. These methods divide the hosting environment into different logical partitions having different processing bandwidths. Such an approach suffers from the drawback that idle resources in one partition cannot be used to process jobs assigned to other partitions, even if this means that there are no resources available to serve a customer request in another partition. According to the same paragraph, it is also known to allocate each customer a certain quota of system time per time period. However this can lead to resources remaining idle, and thus a sub-optimal system resource utilization, if the customers making the requests have already exhausted their quotas.

2.6 The application proposes that each job has an associated priority (u), there being l (i.e. little "L") priority levels, and is processed by one or more processors selected from a first and a second group. The size of the first group (c) depends on the job priority, this being resource allocation according to the service agreement, while the processors in the second group are those having a current or "momentary" utilization rate (UciM) below a predetermined threshold rate (Ucu), this being resource allocation according to current resource utilization.

2.7 As shown in figure 1, computational jobs are generated by a plurality of clients connected via a network to a data centre, for instance a server, comprising multiple processors, also known as "processing nodes". One or more scheduling servers, also termed "scheduling nodes", distribute the jobs to the processors taking into account the job priority level. The method and corresponding system according to claims 1 and 11, respectively, of the main request are directed to these embodiments. The scheduling servers can determine the job priority using a database which links data identifying each user to a priority level.

2.8 As shown in figure 5, a scheduling server comprises a processor grouping engine (see paragraphs [0043 to 0045]), a scheduling engine, a utilization rate service engine (which polls the processors to determine their utilization) and a queue for holding jobs until they can be processed.

2.9 As shown in figure 6, the processor grouping engine uses different utilization rate threshold values depending on the priority level of the job and the subset of the processors on which the job runs. For the most urgent jobs (job priority level 1) the utilization rate threshold values are all set to 100%. This means that all four processor subsets belong to the claimed "first group" of processors for the most urgent jobs, the "second group" of processors being empty. As the jobs become less urgent (i.e. the "job priority level" increases) the claimed "first group" shrinks as the claimed "second group" grows, assuming that the processor utilization is sufficiently low. For instance, taking the next, less urgent, priority level (job priority level 2), the "first group" of processors only contains processor subsets 2, 3 and 4, while processor subset 1 is allocated to the "second group" with a utilization rate threshold value of 50%; see the algorithm in paragraph [0051].

2.10 The scheduling servers can monitor the current utilization rate of the resources used by different jobs and dynamically reallocate jobs to processors to maximise the availability of resources for the highest priority jobs; see paragraph [0054] and figure 8. Method claim 9 of the main request is directed to these embodiments.

3. The appealed decision

3.1 As requested by the applicant, the examining division issued a decision on the state of the file set out on EPO form 2061. As explained below, the board finds that neither the grounds given for the decision nor the version of the application documents on which the decision was based are unambiguously derivable from the decision. These deficiencies stem to some extent from the fixed general formulations used in form 2061.

3.2 The fact that the appellant was nevertheless able to respond substantively to the appealed decision in the statement of grounds of appeal does not affect the board's assessment of the decision, although it is relevant to the questions of a possible immediate remittal of the case to the first instance under Article 11 RPBA and the equity of a possible refund of the appeal fee under Rule 67 EPC 1973, as discussed below.

3.3 According to form 2061, entitled "Decision to refuse a European patent application (Art. 97(2) EPC)", which was sent to the applicant by registered letter with advice of delivery, the grounds for the decision were as follows. In the "communication(s)" dated 20 February 2009 the applicant had been given the reasons why the application did not meet the requirements of the EPC. As far as it goes, this statement is correct; the communication dated 20 February 2009 raised objections under Articles 83 and 56 EPC against the application (as it was then). There is however no mention of the later communication, namely the annex dated 1 July 2009 to the summons to oral proceedings, this communication relating to the application with the amended claims received on 20 March 2009 and setting out inter alia the examining division's reasons for not accepting the applicant's arguments under Article 83 EPC. The reader of the decision has no way of knowing whether the examining division intended not to base the appealed decision partially on its arguments made in the annex dated 1 July 2009.

3.4 Form 2061 goes on to state that "The applicant filed no comments or amendments in reply to the latest communication but requested a decision according to the state of the file by a letter received in due time on 19.03.2009." (Emphasis by the board). In the board's view the expression "the latest communication" is ambiguous in this context. By using the expression "communication(s)", form 2061 provides for the possibility that several communications by the examining division can be referred to regarding the reasons for the decision. Consequently one possible interpretation of the expression "the latest communication" in this context can be "the latest communication in the above list", in the present case that of 20 February 2009. On this interpretation, the examining division overlooked the applicant's arguments and the amended claims received on 20 March 2009 in taking the appealed decision. Another possible interpretation of the expression "the latest communication" in this case is "the latest communication in the file", the reader of the decision being left to consult the file to establish which communication is meant, it not being unambiguously clear from the decision itself. In this case the latest communication from the examining division in the file is the annex to the summons dated 1 July 2009.

3.5 Hence the reader of the decision is left in doubt as to whether the reasons set out in the annex dated 1 July 2009 form reasons for the appealed decision and whether the examining division took the amended claims and the applicant's arguments regarding Article 83 EPC into account in reaching its decision.

3.6 Form 2061 also refers erroneously to a request for a decision according to the state of the file received on 19 March 2009. In fact, this request was received later, namely on 24 July 2009, the letter dated 19 March 2009 being the applicant's response to the communication of 20 February 2009. The board takes the view that the applicant and third parties would have readily resolved the inconsistency between form 2061 and the rest of the first instance file regarding the date of the request for a decision according to the state of the file, since only one such request was made by the applicant.

3.7 According to Rule 111(2) EPC, first sentence, decisions of the EPO which are open to appeal shall be reasoned. In the light of the above deficiencies regarding the reasons for the decision and the version of the application documents on which the decision was based, the board finds that the appealed decision was not adequately reasoned within the meaning of Rule 111(2) EPC.

3.8 According to Article 113(1) EPC 1973, the decisions of the EPO may only be based on grounds or evidence on which the parties concerned have had an opportunity to present their comments. According to established jurisprudence of the boards of appeal (see, for instance, T 763/04, not published in OJ EPO; reasons 4.3), Article 113(1) EPC 1973 is contravened where facts and arguments, which from the appellant's submissions are clearly central to his case and which may speak against the decision taken, are completely disregarded in the decision in question. In the present case, the reasons for the decision do not establish that the applicant's arguments made in the response received on 20 March 2009 were taken into account. Hence the board finds that the decision does not comply with Article 113(1) EPC 1973.

3.9 According to Article 113(2) EPC 1973, the EPO shall consider and decide upon the European patent application only in the text submitted to it, or agreed, by the applicant. In the present case it is not clear from the decision that the examining division considered and decided on the application including the amended claims received on 20 March 2009. Consequently the board finds that the decision does not comply with Article 113(2) EPC 1973.

3.10 Under these circumstances the board finds that the deficiencies in the reasons given for the appealed decision constitute a substantial procedural violation.

3.11 The first instance file contains a further inconsistency as to the reasons for the appealed decision. EPO form 2048.2, which was signed by all members of the examining division and is open to public file inspection but was apparently not sent to the applicant, refers to a different communication by the examining division to that referred to in form 2061. Form 2048.2 refers, in giving the reasons for the appealed decision, to the annex to the summons dated 1 July 2009, the communication dated 20 February 2009 not being mentioned. The form however correctly states that the request for a decision according to the state of the file was received on 24 July 2009. It would appear that the contents of form 2048.2 were what the examining division should have sent - and probably intended to send - to the applicant instead of the contents of form 2061. The documents in the first instance file do not indicate how this inconsistency occurred.

4. The possibility of immediate remittal to the first instance, Article 11 RPBA

4.1 According to Article 11 RPBA (OJ EPO 2007, 536), a board shall remit a case to the department of first instance if fundamental deficiencies are apparent in the first instance proceedings, unless special reasons present themselves for doing otherwise.

4.2 In the present case the board finds that the substantial procedural violation explained above constitutes a fundamental deficiency in the first instance proceedings.

4.3 However, notwithstanding the deficiencies in the decision, it is evident from the file that the examining division had, in fact, taken into account the applicant's amendments and arguments received on 20 March 2009, and informed the applicant in the annex dated 1 July 2009 about its reasons for maintaining the objections. That the decision was deficient was evident for the applicant at least as regards the incorrect date given for the applicant's request for a decision according to the state of the file. The presumably intended version of the decision on form 2048.2 was available to the applicant from the electronic file. The board finds that these circumstances, in combination with the facts that the appellant was able to respond substantively and appropriately to the appealed decision, in particular regarding sufficiency of disclosure, in the statement of grounds of appeal and has not requested immediate remittal of the case, constitute special reasons justifying not immediately remitting the case to the first instance.

5. Sufficiency of disclosure, Article 83 EPC 1973

5.1 The communication by the examining division dated 20 February 2009 raised the objection, which was maintained in the annex dated 1 July 2009, that, although the "utilization rate threshold values" Ucu (termed the "second predetermined utilization rate" in claim 1) played an essential role in determining the claimed "second group" of processors, the description did not specify how these parameters were calculated. Depending on the value of the threshold values, the second group could comprise from 0 to 100% of all the processors. In other words, the selection of the second group of processors depended on undisclosed parameters, namely Ucu and, as was stated in the annex dated 1 July 2009, "the existence of a technical effect fully depended on the parameter selection" by the "system designer". Merely the concept of "introducing parameters" was too abstract and general to be a sufficient disclosure.

5.2 The "utilization rate threshold values" Ucu are set out (as the "second predetermined utilization rate" in claims 1 and 11 and the "predetermined utilization rate" in claim 9) not only in the claims on file when the communication dated 20 February 2009 was issued but also in the amended claims received on 20 March 2009 which now form the main request.

5.3 The appellant has argued that the idea underlying the invention is sufficiently disclosed, even if no explicit calculation scheme for the utilization rate threshold values is given, and that the threshold values could be determined by the skilled person, a system designer, for each specific case. According to the appellant, the idea is that if the processor subsets allocated to urgent jobs are under-utilized then they can be used for less urgent jobs; see figure 6. These processors are used to process more and more of the less urgent jobs as their utilization falls. As figure 6 shows, the utilization rate threshold value falls for processor subsets for jobs of increasing urgency.

5.4 According to Article 83 EPC 1973, the European patent application must disclose the invention in a manner sufficiently clear and complete for it to be carried out by a person skilled in the art. The board disagrees with the position taken by the examining division that the application can only comply with Article 83 EPC 1973 by disclosing how the utilization rate threshold values are calculated, which indeed the application does not.

5.5 In the light of the drawbacks in the prior art summarized in paragraph [0005] of the description, the alleged invention seeks to improve the overall utilization of hardware resources, such as the multi-core processors disclosed on page 16, lines 16 to 18, while maintaining resource availability for jobs having the lowest priority level, meaning the most urgent jobs; see the definition of "priority" on page 20, lines 3 to 7. The board regards an improvement in the utilization of such hardware resources as a technical problem whose solution involves a technical effect, since it allows either more jobs to be processed with the same hardware or the same work load to be mastered by simpler hardware. In the board's view, both the claimed definition of the "first group" of processors and the definition of the claimed "second group" of processors, the definition of these groups being disclosed in paragraphs [0047, 0048 and 0051], contribute to the solution of the technical problem which the application sets out to solve over the prior art discussed in the description. An example of the utilization rate threshold values is set out in figure 6.

5.6 If a similar table to that shown in figure 6 were to be drawn up for the prior art in paragraph [0005], its elements would all be zero except for a line of elements set to 100% on the major diagonal, i.e, from top left to bottom right. Resource utilization is already improved, if only slightly, when a job with a given priority level can, if need be, processed by a processor normally allocated to jobs of a different priority level, meaning that an element off the major diagonal in figure 6 has a non-zero value. This is already made possible by the provision of the "first group" of processors set out in all the independent claims according to the main request, namely all processors in subsets of processors which are defined for priority levels greater than or equal to (i.e. urgency less than or equal to) the priority level associated with the job.

5.7 As to the claimed "second group" of processors, any non-zero threshold values above and to the right of the major diagonal in figure 6 would allow some flexibility in resource utilization and thus produce an improvement at least in some situations. Whilst it is true that the degree to which resource utilization is improved in any individual case may depend on undisclosed factors relating to that specific case, the board is satisfied that the skilled person could, in each specific case, determine threshold values without undue experimentation which would improve the resource utilization at least to some degree. In other words, the board is satisfied that the invention exhibits at least some technical effect over the prior art discussed in the description which does not depend on the disclosure of a specific calculation scheme for the claimed parameters.

5.8 Hence the board finds that the application does disclose the invention in a manner sufficiently clear and complete for it to be carried out by a person skilled in the art and thus satisfies Article 83 EPC 1973.

6. Inventive step, Article 56 EPC 1973

6.1 The communication by the examining division dated 20 February 2009 stated that if the processing (the board understands this to mean the processing of jobs) depended on undisclosed parameters, then a possible technical effect also depended on these parameters, since the application did not disclose how the utilization threshold values were calculated, a technical effect could not be recognised over the whole range of these undisclosed parameters so that claim 1 lacked inventive step.

6.2 In the annex dated 1 July 2009 the examining division further speculated that if it could be convinced that "routine methods would be enough, then this would be a strong pointer that the invention lacks inventive step since the use of these parameters constitutes the core of the invention."

6.3 The board is not convinced by this reasoning. Firstly, as explained above, the technical effect of the alleged invention is not solely reliant on the values of the utilization threshold values; a technical effect already accrues due to the provision of the "first group" of processors set out in all independent claims according to the main request.

6.4 Secondly, as stated above, the board is satisfied that the skilled person could, in each specific case, determine threshold values without undue experimentation which would improve the resource utilization at least to some degree. Moreover the application discloses one example of the utilization rate threshold values in figure 6.

6.5 Thirdly, whether the definition of the "first group" and "second group" of processors had to be considered to require only the application of "routine methods" was not decided by the examining division. Moreover the examining division merely suggested that the potential need for only routine methods "was a strong pointer" against an inventive step, but did not fully argue this point.

6.6 Fourthly, since the examining division has not assessed the claimed subject-matter vis-à-vis any specific piece of prior art, it is not yet possible to know the extent to which the question of inventive step depends on the features relating to the utilization of threshold values at all. They could, for instance, be known from the closest prior art and would in this case not constitute the "core of the invention".

6.7 Hence the board does not agree with the reasons given in the appealed decision for the finding that the subject-matter of claim 1 lacks inventive step, Article 56 EPC 1973.

7. Remittal, Article 111(1) EPC 1973

7.1 Since the application according to the main request overcomes the reasons for the appealed decision and a full examination of novelty and inventive step has not yet taken place, the board exercises its discretion to remit the case to the first instance for further prosecution.

7.2 Remittal will also give the first instance an opportunity to consider whether the claims according to the main and auxiliary requests satisfy Article 84 EPC 1973 regarding clarity even though they lack an explicit definition of the expression "priority level". It could be argued that the skilled person would be surprised by the definition that the lower the "priority level" the more urgent the job; see page 20, lines 3 to 7. The question also arises whether the two independent method claims according to each request satisfy Article 84 and Rule 29(2) EPC 1973 regarding conciseness and multiple independent claims in the same category.

7.3 Since the board is deciding to set aside the appealed decision and the board's decision is not adverse for the appellant, the appellant's auxiliary requests for inter alia oral proceedings do not come into play.

7.4 According to Rule 67 EPC 1973, the reimbursement of the appeal fee shall be ordered where the board of appeal deems an appeal to be allowable, if such reimbursement is equitable by reason of a substantial procedural violation. In the present case the appeal is being allowed and a substantial procedural violation has been identified in the first instance proceedings. However the board finds that it would not be equitable to refund the appeal fee, since in view of the circumstances set out under point 4.3 above, the board finds that there was no causal link between the procedural violation and the need for the applicant to file the present appeal, namely Article 83 EPC 1973.

Order

For these reasons it is decided that:

1. The decision under appeal is set aside.

2. The case is remitted to the first instance for further prosecution.

Quick Navigation