Routing system and route update method

• US 20070165543A1
• Filed: 12/08/2006
• Published: 07/19/2007
• Est. Priority Date: 01/19/2006
• Status: Abandoned Application

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Joo, Hong-Don
• Application Number:
  US11/635,672
• Publication Number:
  US 20070165543A1
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/52 Multiprotocol routers
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

A route update method includes: storing information on route insertion sequence by each routing protocol in respective entries in a routing table; performing a prefix search according to the stored route insertion sequence upon a restart of a routing module, and updating a corresponding routing entry upon a prefix matching occurring as a result of the prefix search, and performing a search according to a general Trie structure upon a prefix matching failure to succeed occurring as a result of the prefix search. Accordingly, the route search time is reduced upon a route update.

Claims

1. A method of updating a routing table with a Trie structure, the method comprising:

storing information on a route insertion sequence by each routing protocol in respective entries in the routing table;

performing a prefix search according to the stored route insertion sequence upon a restart of a routing module; and

updating a corresponding routing entry upon a prefix matching occurring as a result of the prefix search.

2. The method according to claim 1, further comprising performing a search according to the Trie structure upon a prefix matching failure to succeed occurring as a result of the prefix search.

3. The method according to claim 1, wherein the routing protocols include at least one of a Routing Information Protocol (RIP), an Open Shortest Path First (OSPF) protocol, and a Border Gateway Protocol (BGP).

4. The method according to claim 1, wherein the respective entries in the routing table include connection information with entries before and after the corresponding insertion sequence by each protocol.

5. The method according to claim 4, wherein the connection information is expressed in the form of a double linked list.

6. The method according to claim 1, wherein the Trie structure is one of a binary Trie, a Patricia Trie, a path compressed Trie, a multi-bit Trie, and an LC-Trie.

7. A method of updating a routing table with a Trie structure, the method comprising:

storing information on a route insertion sequence by each routing protocol in respective entries in the routing table;

performing a prefix search according to the stored route insertion sequence upon a restart of a routing module; and

updating a corresponding routing entry upon a prefix matching occurring as a result of the prefix search, and performing a search according to the Trie structure upon a prefix matching failure to succeed occurring.

8. The method according to claim 7, wherein respective entries in the routing table include connection information with entries before and after the corresponding insertion sequence by each protocol.

9. A routing system, comprising:

a routing table adapted to store information on a route insertion sequence by each protocol in a Trie structure for each entry; and

a routing module adapted to perform a prefix search according to the stored route insertion sequence upon a restart thereof, and updating a corresponding routing entry upon a prefix matching occurring as a result of the prefix search.

10. The system according to claim 9, wherein the routing module comprises:

a Routing Information Protocol (RIP) routing module adapted to perform an update for respective entries in the routing table according to the RIP;

an Open Shortest Path First (OSPF) routing module adapted to perform an update for the respective entries in the routing table according to an OSPF protocol; and

a Border Gateway Protocol (BGP) routing module adapted to perform an update for the respective entries in the routing table according to the BGP.

11. The system according to claim 9, wherein the routing module performs a search according to the Trie structure upon a prefix matching failure to succeed occurring as a result of the prefix search.

12. The system according to claim 9, wherein the routing table includes at least one entry having connection information with entries before and after the corresponding insertion sequence by each routing protocol.

13. The system according to claim 12, wherein the connection information is expressed in the form of a double linked list.

14. The system according to claim 9, wherein the Trie structure is one of a binary Trie, a Patricia Trie, a path compressed Trie, a multi-bit Trie, and an LC-Trie.