Snapshot routing with route aging

• US 6,097,718 A
• Filed: 01/02/1996
• Issued: 08/01/2000
• Est. Priority Date: 01/02/1996
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bion, Joel P.
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): Qureshi, Afsar M.
• Application Number:
  US08/582,075
• Time in Patent Office: 1,673 Days
• Field of Search: 370/351, 370/406, 370/400, 370/399, 370/229, 370/319, 370/403, 370/385, 370/402, 370/410, 370/409, 370/396, 370/404, 370/389, 370/254, 370/401, 370/446, 370/248, 370/352, 395/200.72, 395/200.68, 395/200.73, 395/200.79, 379/273
• US Class Current: 370/351
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

A method and system for maintaining and updating routing information in a packet switching network for a set of quasidynamic routes, in which intermittent routing updates are permitted, so that routes are no longer "always static" or "always dynamic", but may change over time between static and dynamic, and are treated accordingly. The invention is particularly applicable to dial-on-demand serial communication links, but is also useful in any situation where it is desired to reduce the overhead from routing updates over a communication link, or where transmission over a communication link is not reliable. A protocol manager for a dynamic routing protocol is modified to determine, for each route, (1) whether to send updated routing information for that route (at the time it would otherwise send an up-date for a particular route), and (2) whether to age that route in its routing tables (at the time it would otherwise age that route). The modified protocol manager thus prevents automatic aging of routes, while avoiding the use of manually configured static routing tables. Routing information is thus learned automatically and dynamically at appropriate times, and refreshed periodically so that it eventually reflects actual changes to the network topology.

Claims

1. A method for routing messages in a network, comprising the steps of

following a routing protocol, said routing protocol comprising transmitting updated connectivity information between routers and aging a route in a routing table;

making a first determination whether to transmit said updated connectivity information between routers, and transmitting said updated connectivity information responsive to said first determination wherein said first determination to transmit is synchronized between routers;

making a second determination independent of said first determination whether to age said route, and aging said route responsive to said second determination.

2. A method as in claim 1, wherein said step of making a first determination is responsive to a first event detected by said routing protocol.

3. A method as in claim 1, wherein said step of making a second determination is responsive to a second event detected by said routing protocol.

4. A method as in claim 1, wherein said step of making a second determination is responsive to an active period or a quiet period for said route.

5. A method as in claim 4, wherein said active period is a preselected duration and said quiet period is a preselected minimum duration.

6. A method as in claim 1, wherein said route comprises a telephone connection and said step of making a first determination is responsive to a condition of said telephone connection.

7. A method as in claim 1, wherein said route comprises a telephone connection and said step of making a second determination is responsive to a condition of said telephone connection.

8. A system comprising

a protocol engine disposed for following a routing protocol comprising transmitting updated connectivity information between routers and aging a route in a routing table;

means for making a first determination whether to transmit said updated connectivity information between routers and for making a second determination whether to age said route;

wherein said protocol engine is disposed for requesting said means to make said first determination and for transmitting updated connectivity information responsive to said first determination wherein said first determination to transmit is synchronized between routers, and to make said second determination independent of said first determination and for aging said route responsive to said second determination.

9. A system as in claim 8, wherein said means is responsive to an event detected by said routing protocol.

10. A system as in claim 8, wherein said means is responsive to an active period or a quiet period for said router.

11. A system as in claim 10, wherein said active period is a preselected duration and said quiet period is a preselected minimum duration.

12. A system as in claim 8, wherein said route comprises a telephone connection and said means is responsive to a condition of said telephone connection.

14. A system as in claim 8 wherein said routing table further comprises:

at least one quasidynamic route, said quasidynamic route comprising information regarding at least one destination reachable from said second device;

wherein said means for making a first determination is a snapshot engine coupled to said protocol engine, said snapshot engine disposed for making a first determination whether to transmit said updated connectivity information and for making a second determination whether to age said route;

wherein said protocol engine is disposed for requesting said snapshot engine to make said first determination and for transmitting updated connectivity information responsive to said first determination, and to make said second determination and for aging said route responsive to said second determination.

13. In a system having a communication link and first and second devices coupled to said communication link, a method comprising

maintaining a routing table at said first device, said routing table comprising at least one quasidynamic route, said quasidynamic route comprising information regarding at least one destination reachable from said second device;

following a dynamic routing protocol, said dynamic routing protocol comprising transmitting updated connectivity information between routers and aging a route in said routing table;

making a first determination whether to transmit said updated connectivity information

making a second determination independent of said first determination whether to age said route;

modifying said dynamic routing protocol by transmitting updated connectivity information responsive to said first determination; and

modifying said dynamic routing protocol by aging said route responsive to said second determination.