T 0646/06 (Next hop routing/ASCEND COMMUNICATIONS) of 3.3.2010

Summary of Facts and Submissions

I. This appeal is against the decision of the examining division dispatched 29 November 2005, refusing European patent application No. 00 310 758.8. The decision was based on the ground that the subject-matter of independent claim 1 did not involve an inventive step having regard to the disclosure of

D3: EP 0 551 243

taken in combination with the disclosure of

D2: V. Srinivasan et al.: "Faster IP Lookups using Controlled Prefix Expansion", Performance Evaluation Review, Association for Computing Machinery, New York, US, vol. 26, no. 1, June 1998, pages 1-10, XP001025167, ISSN: 0163-5999.

II. Notice of appeal was submitted on 27 January 2006 and the appeal fee was paid on the same day. The statement setting out the grounds of appeal was submitted on 28 March 2006.

III. The appellant (applicant) requested that the decision under appeal be set aside and a patent be granted.

IV. The board issued an invitation to oral proceedings scheduled to take place on 3 March 2010. The board gave a preliminary opinion that claim 1 of the claims on file did not meet the requirement of Article 84 and 123(2) EPC and that its subject-matter did not involve an inventive step, having regard to the disclosure of D3 taken in combination with D2. The board also gave its reasons why the appellant's arguments were not convincing. Further, the appellant's attention was drawn to Article 13 RPBA relating to amendments to a party's case; the board stated that if amended claims were filed, it would be necessary at the oral proceedings to discuss their admissibility and their compliance with the EPC, including Articles 123(2), 84 and 52(1). Moreover the board stated that, in the light of Article 15(3) RPBA, the board might announce a decision based on new objections arising from such newly submitted amendments even if the appellant chose not to attend.

V. In a letter of response to the summons submitted 3 February 2010, the appellant filed two sets of amended claims according to a Main Claim Set and an Alternative Claim Set, replacing the previous single claim set, together with arguments in support of inventive step of the two claim sets. The appellant also announced that it would not attend the oral proceedings.

VI. Oral proceedings were held on 3 March 2010 in the absence of the appellant.

After deliberation on the basis of the submissions and requests dated 3 February 2010, the board announced its decision.

VII. The appellant requests that the decision under appeal be set aside and that a patent be granted on the basis of the Main Claim Set, or, subsidiarily, on the basis of the Alternative Claim Set, both claim sets as filed with letter dated 3 February 2010.

The text on the basis of which grant of a patent is requested is therefore as follows:

claims 1 to 11 of the Main Claim Set, or, subsidiarily, of the Alternative Claim Set, both claim sets as filed on 3 February 2010;

description

pages 2 to 4 and 7 to 9 as originally filed,

pages 1, 1a, 5 and 6 as filed on 24 February 2005;

drawing sheets 1/4 to 4/4 as originally filed.

VIII. Claim 1 of the Main Claim Set reads as follows:

"A route lookup engine (100) characterized by:

a variable stride trie memory (30) including at least one variable stride trie for at least one network;

a lookup controller (20), in communication with said variable stride trie memory, adapted to perform a multicast lookup by searching said variable stride trie memory from a root node to a leaf node to obtain a next hop index associated with multiple destinations; and

a forwarding processor interface (65), in electrical communication with said lookup controller, adapted to provide a search key to said lookup controller for said lookup controller to begin searching said variable stride trie, and adapted to receive said next hop index from said lookup controller."

IX. Independent claim 1 of the Alternative Claim Set reads as follows:

"A route lookup engine (100) for routing packets to Virtual Private Networks, VPNs, characterized by:

a variable stride trie memory (30) including at least one variable stride trie for each VPN;

a lookup controller (20), in communication with said variable stride trie memory, adapted to search a variable stride trie of a VPN from a root node to a leaf node using a pointer associated with the VPN to obtain a next hop index associated with a single destination or multiple destinations; and

a forwarding processor interface (65), in electrical communication with said lookup controller, adapted to provide the pointer to said lookup controller for said lookup controller to begin searching said variable stride trie, and adapted to receive said next hop index from said lookup controller."

Reasons for the Decision

1. Admissibility

The appeal complies with the provisions of Article 106 to 108 EPC 1973. Therefore it is admissible (see Facts and Submissions, points II and III).

2. Non-attendance of oral proceedings

The appellant was duly summoned, but did not appear in the oral proceedings. According to Article 15(3) RPBA the board shall not be obliged to delay any step in the proceedings, including its decision, by reason only of the absence at the oral proceedings of any party duly summoned who may then be treated as relying only on its written case. Further the appellant was informed in the board's communication that if amendments to the appellant's case were filed, it would be necessary at the oral proceedings to discuss their admissibility and their compliance with the EPC, including Articles 123(2), 84 and 52(1), see point IV above. In deciding not to attend the oral proceedings the appellant chose not to make use of the opportunity to comment at the oral proceedings on any such objections but, instead, chose to rely on the arguments as set out in the written submissions, which the board duly considers below.

In view of the above and for the reasons set out below, the board was in a position to give at the oral proceedings its decision.

3. Main Claim Set

3.1 Closest prior art

D3 discloses an address recognition engine coupled to a lookup database organized as a trie memory, for use in a router of a packet communication network. The embodiment described in relation with figure 4 uses a multi-bit trie with a fixed stride of 4, having 4 bits of the network address examined at one step (column 8, lines 39-47).

Using the wording of claim 1, D3 discloses a route lookup engine (figure 1, address recognition card 10) comprising:

- a trie memory (fig. 1, database 300) including at least one trie for at least one network;

- a lookup controller (fig. 1, address recognition engine 100), in communication with said trie memory, adapted to perform a lookup by searching said trie memory from a root node (fig. 4, root node 305A) to a leaf node (fig. 4, termination node 305B) to obtain a next hop index associated with a destination (column 4, lines 28-32: information necessary for the router to direct the data transmission to its intended destination); and

- a forwarding processor interface (fig. 1, request/response RAM 101) in electrical communication with said lookup controller, adapted to provide a search key (column 8, lines 8-19: network address) to said lookup controller for said lookup controller to begin searching said trie, and adapted to receive said next hop index from said lookup controller.

3.2 Inventive step- Article 56 EPC

The only apparent differences between the subject-matter of claim 1 and the disclosure of D3 are thus that:

a) the lookup is a multicast look up and the next hop index is associated with multiple destinations; and

b) the trie memory is a variable stride trie memory.

In respect of allegedly distinguishing feature a), the board notes that the route lookup engine according to the single embodiment of the description and drawings of the application (in particular figure 3) uses IP addresses. The only identified distinguishing feature of the treatment of a multicast packet vis-à-vis a unicast packet is that a lookup is carried out on both IP source and destination addresses if the packet is a multicast but only for the destination address of a unicast packet (see paragraph 17 of the published application). This is not a feature of the route lookup engine as described in the application (and embodied in e.g. figure 3); it is rather a feature of the use of the lookup engine. The address recognition apparatus of D3 also works with IP packets (see on column 1, lines 29-34, column 7, lines 10-16 and column 17, lines 38-44). The board judges therefore that the address recognition apparatus of D3 is just as adapted to deal with both unicast and multicast lookups as is the claimed "route lookup engine".

Therefore feature a) does not actually distinguish the subject-matter of claim 1 from D3.

With respect to distinguishing feature b), the technical effect achieved by using a variable stride instead of a 4-bits fixed stride as in D3 is the possibility to examine more than 4 bits in one step for some trie levels, thus reducing the height of the search trie. The objective technical problem solved by this feature may thus be defined as how to increase the speed of the search. D2 relates to IP address lookup for communication routers and identifies the speed of search in a trie as a major problem; several techniques are disclosed for improving the trie search, in particular the use of a varying stride in paragraph 5.3 and figure 5. It is obvious for the skilled person to apply the teaching of D2 in respect of a variable stride trie to the route lookup engine of D3.

Therefore the subject-matter of claim 1 lacks an inventive step having regard to the combination of documents D3 and D2.

3.3 The appellant argued that D3 does not relate to searching next hop indexes associated with destination addresses but appears to be directed at the storage and retrieval of network addresses only. In particular, he argued that the "outgoing transmission lines" in D3 are not related to a next hop index.

The board accepts that D3 does not use the wording "next hop index". However, the board considers that D3 unambiguously relates to the field of packet routing in a packet transmission network and that the address recognition engine disclosed in D3 delivers information where a received packet should be forwarded next, based on the destination address contained in its header. This corresponds to the definition of the next hop, which is the term usually used in the field. The outgoing transmission lines in D3 correspond to the egress interfaces of a router, which is the terminology usually employed in the packet communication field.

In particular, the following passages of D3 support this analysis: column 2, lines 31-38; column 4, lines 28-32; column 7, lines 42-45; column 8, lines 13-19.

3.4 The appellant further argued that D3 appears to be explicitly directed at the forwarding of a packet from one router to another router, not to multiple routers/destinations and that D3 does not state or imply that the address recognition engine is capable of completing multicast lookups since D3 appears to be mostly directed at router-to-router, packet transmissions within a Local Area Network (LAN).

The board is however not convinced by these arguments:

- D3, on column 2, lines 27-30 and on column 7, lines 10-15, explicitly discloses the routing of packets between source and destination belonging to different LANs.

- moreover, the application does not mention any other substantial difference between a unicast lookup and a multicast lookup other than the subsequent search on the source address which is performed in case of a multicast lookup (see paragraph 17 of the published application). The board judges that the address recognition engine of D3 is capable of performing source and destination addresses lookups and therefore multicast lookups to the same extent as it is described in the application.

3.5 The present independent claim 1 specifies that the next hop index is "associated with multiple destinations", and in the appellant's final submissions this feature is argued not to be disclosed in D3. However nothing in the application gives any hint to the distinction between a next hop index associated with a single destination and one associated with multiple destinations. Moreover whether the route lookup engine delivers a next hop index associated with single or multiple destinations is not a feature of the engine as claimed, but again only of the way in which it is used.

3.6 The main request is therefore not allowable.

4. Alternative Claim Set

4.1 Article 123(2) EPC

Claim 1 defines that the variable stride trie memory includes at least one variable stride trie for each Virtual Private Network VPN. This implies that the trie memory may include more than one trie for a given VPN. The application documents as originally filed however clearly describe that for each VPN a single variable stride trie is maintained in the trie memory (see paragraph 20 of the published application), and that each VPN is used as pointer to the root of a table specific to that VPN (see paragraph 14).

The amendment therefore contravenes Article 123(2) EPC and the subsidiary request is not allowable.

4.2 Inventive step - Article 56 EPC

The board notes moreover that even if claim 1 were amended to specify that the variable stride trie memory included a single variable stride trie for each VPN, in order to overcome the above-mentioned Article 123(2) objection, its subject-matter would not involve an inventive step for the following reasons.

Claim 1 substantially adds to the subject-matter of claim 1 according to the Main Claim Set that the route lookup engine is for routing packets to VPNs and uses a pointer associated with each VPN to search in the trie associated with that VPN.

A Virtual Private Network VPN is a communication network wherein data transmissions within the network are generally secured. In the board's judgement, applying the teaching of D3 and D2 in respect of routing between networks to routing between VPNs is an obvious step for the skilled person since D2 and D3 are not restricted to a particular kind of communication network and since the claimed route lookup engine does not make use of network characteristics which are specific to a VPN. Moreover, the use of a pointer associated with a VPN for searching a variable stride trie of said VPN represents an obvious feature for the designation of the trie to search in.

4.3 The appellant argued that neither the network address segments, specifiers or pointers discussed in D3 relate to a VPN so that the databases in D3 are not searched using a variable stride trie of a VPN. He further argued that neither the primary nor secondary databases discussed in D3 are configured to dedicate a variable stride trie for each VPN.

The board does not find these arguments convincing. As stated above, D3 and D2 are not restricted to a particular kind of communication network and their teaching may be also applied to VPNs. Further, the board notes that the claimed route lookup engine using a variable stride trie memory does not require for its implementation specific features of the networks.

5. In the absence of an allowable request the appeal must be dismissed.

ORDER

For these reasons it is decided that:

The appeal is dismissed.