14-15 November 2018
|European Case Law Identifier:||ECLI:EP:BA:2015:T090012.20150416|
|Date of decision:||16 April 2015|
|Case number:||T 0900/12|
|IPC class:||H04L 12/56|
|Language of proceedings:||EN|
|Download and more information:||
|Title of application:||Search engine architecture for a high performance multi-layer switch element|
|Applicant name:||Oracle America, Inc.|
|Relevant legal provisions:||
|Keywords:||Admission of late-filed request - (yes)
Inventive step - (yes, after amendment)
Summary of Facts and Submissions
I. The appeal is against the decision of the examining division, posted on 9 November 2011, to refuse European patent application No. 98932909.9 on the grounds of lack of inventive step (Article 56 EPC) with respect to the claims of a main request and an auxiliary request, having regard to the disclosure of
D5: J. Delgado-Frias et al.: "A VLSI Interconnection Network Router Using a D-CAM with Hidden Refresh", Proceedings of IEEE VLSI 1996, pp. 246-251, 22 March 1996,
combined with the skilled person's common general knowledge as exemplified by
D8: "Cisco 7500 Series", Cisco Documentation, pp. 1-26, 20 December 1996 and
D1: US-A-5 509 006.
II. Notice of appeal was received on 15 December 2011. The appeal fee was paid on the same day. With the statement setting out the grounds of appeal, received on 9 March 2012, the appellant filed amended sets of claims as a main and an auxiliary request. It requested that the decision of the examining division be set aside and that a patent be granted on the basis of the main or the auxiliary request.
III. A summons to oral proceedings scheduled for 16 April 2015 was issued on 12 December 2014. In an annex to this summons, the board gave its preliminary opinion on the appeal pursuant to Article 15(1) RPBA. In particular, it raised objections under Article 84 EPC 1973 and Article 123(2) EPC, and stated in relation to the assessment of novelty and inventive step that the present invention appeared to include subject-matter which was not disclosed or hinted at by the prior-art documents relied upon in the decision under appeal.
IV. By letter of reply dated 9 March 2015, the appellant submitted amended claims according to a new main request, replacing the former main and auxiliary requests on file, alongside counter-arguments on the objections raised in the board's communication under Article 15(1) RPBA.
V. Oral proceedings were held as scheduled on 16 April 2015, during which the appellant filed a new main request (claims 1 to 12), replacing the former main request, in response to objections raised under Article 84 EPC 1973 by the board and discussed during the oral proceedings.
The appellant's final request was that the decision under appeal be set aside and that a patent be granted on the basis of the main request filed at the oral proceedings before the board.
At the end of the oral proceedings, the decision of the board was announced.
VI. Claim 1 of the main (sole) request reads as follows:
"A subsystem (110) comprising a switching element (100) and a forwarding database memory (140),
wherein the switching element comprises a switch fabric (210) and a plurality of input ports (205, 215, 225),
wherein the switch fabric comprises:
a search engine (370) coupled to the forwarding database memory (140) and a plurality of input ports, the search engine configured to schedule and perform accesses to the forwarding database memory (140) and to transfer forwarding decisions to the plurality of input ports; and
a header processing unit (305) coupled to the search engine and having an arbitrated interface coupled to the plurality of input ports,
wherein the header processing unit (305) is configured to receive a packet header of a packet from an input port of the plurality of input ports and to extract information from the packet header based upon predetermined portions of the packet header, the search engine being coupled to the header processing logic and using the extracted information for constructing first and second search keys to access the forwarding database memory (140), the predetermined portions of the packet header being selected based upon a class of a plurality of classes with which the packet header is associated,
wherein the first search key is a Layer 2, "L2", search key for retrieving an L2 entry from the forwarding database memory and the second search key is a Layer 3, "L3", search key for retrieving an L3 entry from the forwarding database memory, and
wherein the header processing unit is implemented as a pipeline comprising multiple stages, whereby multiple packet headers are processed simultaneously by the header processing unit, each stage in the pipeline being configured to operate on a corresponding portion of the packet header to extract information from the packet header; and
wherein the forwarding database memory (140) includes one or more associative content addressable memories, "CAMs", (610, 620) coupled to a random access memory, "RAM" (630), the one or more CAMs having stored therein associative data with which the first and second search keys are matched and the RAM having stored therein associated data corresponding to the associative data that indicates output port(s) to which packets are to be forwarded."
Reasons for the Decision
1. The appeal is admissible.
2. MAIN REQUEST
In spite of the fact that this request was submitted during the oral proceedings before the board, i.e. at a very late stage of the overall procedure, the board admitted it into the appeal proceedings under Article 13(1) and (3) RPBA, since it was regarded as a legitimate and successful reaction to overcome all the outstanding objections raised, and since the board could deal with it without having to adjourn the oral proceedings.
The main request differs from the auxiliary request underlying the appealed decision essentially in that claim 1 is now directed to a "subsystem" (rather than to a "network device") and further specifies that (emphasis added by the board)
A) the subsystem comprises a switching element, including a switch fabric and input ports, and a forwarding database memory;
B) the header processing unit is configured to extract information from the received packet header based upon the predetermined portions of the packet header;
C) the search engine uses the extracted information for constructing first and second search keys to access the forwarding database memory;
D) the first search key is a Layer-2 search key for retrieving an L2 entry and the second search key is a Layer-3 search key for retrieving an L3 entry from the forwarding database memory;
E) the header processing unit is implemented as a pipeline comprising multiple stages, whereby multiple packet headers are processed simultaneously by the header processing unit, each stage in the pipeline being configured to operate on a corresponding portion of the packet header to extract information from the packet header;
F) the forwarding database memory includes one or more associative content addressable memories (CAMs) storing associative data and a random access memory (RAM) storing associated data;
G) the associative data is data with which the first and second search keys are matched and the associated data indicates output port(s) to which packets are to be forwarded.
Feature A) is supported e.g. by Figs. 1 and 2, whilst features B) and C) are in particular based on page 14, line 22 to page 15, line 2 and page 15, lines 22-24 of the application as filed. Features D) and E) find their support e.g. in Fig. 5 in conjunction with page 19, line 13 to page 21, line 22 of the description as filed, while features F) and G) are based in particular on page 22, lines 18-20, page 24, lines 10-24 and page 25, lines 1-3 of the original application.
Hence, the board is satisfied that the above amendments comply with Article 123(2) EPC.
2.1 Article 52(1) EPC: Novelty and inventive step
In the board's judgment, claim 1 of the sole request meets the requirements of Article 52(1) EPC in conjunction with Articles 54 and 56 EPC 1973, for the following reasons:
2.1.1 The present invention concerns a multi-layer network switch essentially made up of a switch fabric, a header processing unit for evaluating the incoming packet headers, a search engine for looking up the appropriate switch output port based on the packet header data, and a packet forwarding database for retrieving the respective switch output ports. According to the application, the problem to be solved by claim 1 is to provide a network switch which generates packet forwarding decisions as fast as possible to keep the delay through the switch low and to achieve wire-speed switching on all ports (cf. page 13, lines 2-5 of the application as filed).
2.1.2 The examining division considered document D5 to be the closest prior art for the subject-matter of former claim 1 (cf. appealed decision, item 27). D5 relates to a VLSI-based implementation of a programmable network router based on memory partitioning via split CAMs supporting bit masking along with a priority-based data matching scheme (see e.g. D5, abstract and Fig. 1).
2.1.3 The board agrees with the finding in the decision under appeal (see in particular items 16 and 29) that D5 fails to disclose the following features of present claim 1:
i) the search engine being configured to use extracted packet header information for constructing search keys to access the forwarding database memory, to schedule and perform accesses to the forwarding database memory and to transfer forwarding decisions to the plurality of input ports;
ii) the predetermined portions of the packet header to be extracted being selected based upon a class of a plurality of classes with which the packet header is associated.
In addition, the board finds that D5 also fails to anticipate (at least) the above-identified added features D) and E), i.e. relating to simultaneous L2 and L3 header processing at the header processing unit, namely that
iii) a first search key is an L2 search key for retrieving an L2 entry from the forwarding database memory and a second search key is an L3 search key for retrieving an L3 entry from the forwarding database memory;
iv) the header processing unit is implemented as a pipeline comprising multiple stages, whereby multiple packet headers are processed simultaneously, each stage in the pipeline being configured to operate on a corresponding portion of the packet header to extract information from the packet header.
Consequently, the subject-matter of claim 1 is found to be novel over D5 (Article 54 EPC 1973).
2.1.4 The board accepts that distinguishing features i) to iv) credibly contribute to an overall synergistic effect consisting in the real-time generation of packet forwarding decisions based on packet data relating to both the second layer (i.e. data-link layer, L2) and the third layer (i.e. network layer, L3), such as a packet's MAC address and IP address. The board is also satisfied that the above effect can be derived from the application as filed (see e.g. page 13, lines 5-9 and page 19, line 13 to page 21, line 15 in conjunction with Fig. 5).
2.1.5 Hence, the objective problem to be solved by claim 1 may be formulated as "how to provide a network device which enables a combined switching and routing decision-making process substantially in real time".
2.1.6 Setting out from the teaching of D5, the skilled person would notice that D5 similarly addresses the technical problem of making fast packet forwarding decisions. This problem is substantially solved by matching the incoming packet's destination address via a CAM-based bit-pattern matching unit (see e.g. D5, Fig. 1 and section 2). Furthermore, the board concurs with the finding in the decision under appeal that header processing through extracting header information, though not explicitly shown, must inherently be comprised in D5 (cf. appealed decision, items 15.2 and 28.2) and that distinguishing feature ii), taken alone, would be rendered obvious by the teaching of D5 combined with the skilled person's common general knowledge (cf. appealed decision, items 21 and 35).
However, the packet forwarding decisions of D5 are exclusively related to the routing functionality, i.e. the network layer, of a CAM-based router (see e.g. D5, abstract, Fig. 1 and section 6, second paragraph). There is no hint in D5 which would lead the skilled person in the field of telecommunication networks to even think about the problem or necessity of extending the typical routing functionalities of the proposed router to include switching decisions made at the data link layer. Rather, the sole aim of D5 resides in the optimisation of the underlying CAM-based router device based exclusively on layer-3 data such as the packet's destination address (typically implying an IP address).
Nor is any motivation or incentive discernible in D5 towards the solution according to features i) to iv) of claim 1, i.e. selecting the most suitable output port of a multi-layer network device based on layer-2 and layer-3 data associated with the incoming data packet via parallel and concurrent header processing. On the contrary, only a network node's destination address, i.e. a network-layer address, is utilised as a single search key for address matching purposes (see e.g. D5, page 246, right-hand column, penultimate paragraph, items 1 to 4) and consequently there is neither a need nor a desire for simultaneous L2/L3 header processing, let alone for processing different corresponding portions of the received packet header via distinct processing stages at the same time, as mandated by claim 1. Rather, it is apparent to the board that D5 is completely silent as to the actual treatment of more than one search key. In other words, providing packet forwarding decisions based on header data at different layers in one go is of no concern at all in D5. Accordingly, the board sees no reason why the skilled person, starting from D5, would come up with a solution according to claim 1 which credibly provides a synergistic effect going beyond the sum of the individual effects of its distinguishing features.
2.1.7 Moreover, the board finds that the other documents relied upon in the decision under appeal, which were cited as evidence of the skilled person's common general knowledge as regards distinguishing feature ii) and the use of switching routers (cf. appealed decision, items 21, 35 and 39), i.e. D8 and D1, do also not render the subject-matter of claim 1 obvious, whether taken alone or in combination with the disclosure of D5.
Document D8 represents a technical manual about a commercial router supporting multiple telecommunication protocols implying the use of different packet classes, without however conveying any details on header processing at all. Document D1, though apparently also addressing a possible combination of switching and routing functionalities in a packet switching device (see D1, column 13, lines 39-43), by no means discloses or hints at simultaneous processing of L2 and L3 header data to enable real-time generation of L2/L3 search keys and obtaining packet forwarding results from a CAM-based database using memory partitioning for speedy searching.
2.1.8 As a consequence, having regard to the prior-art documents on file, the subject-matter of the sole independent claim of the main request, claim 1, is held to be new and to involve an inventive step within the meaning of Articles 54 and 56 EPC 1973.
3. Since all the other requirements of the EPC are also found to be fulfilled, the board decides to grant a patent on the basis of claims 1 to 12 according to the main request.
For these reasons it is decided that:
1. The decision under appeal is set aside.
2. The case is remitted to the department of first instance with the order to grant a patent on the basis of
- claims 1 to 12 submitted as new main request at the oral proceedings before the board;
- description, pages 1, 2, 4 to 37 as originally filed and page 3 as submitted at the oral proceedings before the board and
- drawings, sheets 1/9 to 9/9 as originally filed.