Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
2000-05-03
2001-12-04
Kizou, Hassan (Department: 2662)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C370S396000, C370S410000
Reexamination Certificate
active
06327251
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to maintaining and updating routing information in a packet switching network.
2. Description of Related Art
In routing messages in a computer network or in a network of networks (an “internetwork”), protocols for routing message packets generally provide two types of routes to a destination—static routes and dynamic routes. Static routes are reselected and configured before routing in a set of routing tables; typically this is performed manually. Dynamic routes are configured dynamically in response to routing information from other nodes; these routes require periodic updates (i.e., refreshes) of connectivity information, typically involving route refresh, adjacent node refresh, or other means.
One problem which has arisen in the art is that of intermittent connections—connections which are not continuously active, and for which lack of connectivity information refresh does not necessarily indicate that the connection has failed. For example, one type of intermittent connection is a dial-up link, such as used for dial-on-demand routing. For these communication links, it is generally undesirable and sometimes impossible to have routing and connectivity updates transmitted continuously. For example, in dial-on-demand routing, it is not generally possible to communicate routing and connectivity updates when the dial-up link is inactive.
One known method of treating dial-on-demand routing has been to statically configure the remote router with routing information indicating which devices can be located through a particular port (often a serial dial-up link) on the remote router. When a packet arrives at the remote router destined for one or more such devices, then the dial-up link is activated. Because the dial-up link can access a large number of devices at a large number of sites, large static tables are required, static tables must be updated either manually or through periodic downloading of information in response to manual requests. Such manual management of these static tables is a significant task.
Known routing protocols (such as distance vector algorithms or link state algorithms) utilize dynamic routing updates and therefore cannot generally accommodate intermittent connections. These protocols “age” routing or connectivity information—if a device advertising the route is not heard from for a preselected time interval, existing routing protocols presume that the routes through the device are no longer available using that device, and the routing tables are updated accordingly.
Accordingly, it would be advantageous to provide a method and system in which routes including intermittent connections enjoyed the btgt aspects of both dynamic routes and static routes. Ideally, such routes and connectivity information could be dynamically updated using known protocol techniques for dynamic routes, but would not age during times when routing or connectivity information was not available for those connections.
SUMMARY OF THE INVENTION
The invention provides a method and system for maintaining and updating routing and connectivity information in a packet switching network for a set of quasidynamic routes, in which intermittent routing and connectivity updates are permitted, so that routes and connectivity information are no longer “always static” or “always dynamic”, but may change over time between static and dynamic, and are treated accordingly. The change can be in response to input from an external source, or, more generally, from an event noticed ty the routing protocol. 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 and connectivity updates over a communication link, or where transmission over a communication link is not reliable.
In a preferred embodiment, 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 update 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 time, and refreshed periodically so that it eventually reflects actual changes to the network topology.
In a preferred embodiment, the invention is implemented on a router in two component parts: a snapshot engine and a modified routing protocol engine. For two connected routers, the snapshot engine comprises a client for one and a server for the other. The routing protocol engine does not need to know by what criteria the snapshot engine decides the answers to the two questions indicated above; it only needs to be able to get the answers from the snapshot engine. In alternative embodiments, the protocol engine may be modified to incorporate this intelligence and answer these questions itself.
In a preferred embodiment, the client snapshot engine determines a set of “vactive periods” and a set of “quiet periods” for receiving routing updates from the server. During the active period, the communication link is activated, routing and connectivity information is exchanged between the server and client, routing tables are updated at the server and client, and routing information can age at a “normal” rate at the server and client. In this manner, the routing information is automatically periodically refreshed through inherent operation of the protocol, and without packet overhead. During quiet periods, routing information is maintained statically at the server and client without aging, and treated as valid until the next active period for that communication link.
In a preferred embodiment, the client snapshot engine enters active periods at predetermined time intervals, during which it sends updated routing information to the server, and the server responds by sending updated routing information to the client. The server knows the length of the active period. No clock synchronization is necessary. Aging of a route at the client is driven by the reception of packets at the client from the router that originally provided that route to the client. Aging is event-driven. The aging of a route N from router R is triggered only by receipt of new information after a quiet period from router R.
REFERENCES:
patent: Re. 33900 (1992-04-01), Howson
patent: 4131767 (1978-12-01), Weinstein
patent: 4161719 (1979-07-01), Parikh et al.
patent: 4316284 (1982-02-01), Howson
patent: 4397020 (1983-08-01), Howson
patent: 4419728 (1983-12-01), Larson
patent: 4424565 (1984-01-01), Larson
patent: 4437087 (1984-03-01), Petr
patent: 4438511 (1984-03-01), Baran
patent: 4439763 (1984-03-01), Limb
patent: 4445213 (1984-04-01), Baugh et al.
patent: 4446555 (1984-05-01), Devault et al.
patent: 4456957 (1984-06-01), Schieltz
patent: 4464658 (1984-08-01), Thelen
patent: 4499576 (1985-02-01), Fraser
patent: 4506358 (1985-03-01), Montgomery
patent: 4507760 (1985-03-01), Frasner
patent: 4532626 (1985-07-01), Flores et al.
patent: 4644532 (1987-02-01), George et al.
patent: 4646287 (1987-02-01), Larson et al.
patent: 4665518 (1987-05-01), Champlin et al.
patent: 4677423 (1987-06-01), Benvenuto et al.
patent: 4679227 (1987-07-01), Hughes-Hartogs
patent: 4723267 (1988-02-01), Jones et al.
patent: 4731816 (1988-03-01), Hughes-Hartogs
patent: 4750136 (1988-06-01), Arpin et al.
patent: 4757495 (1988-07-01), Decker et al.
patent: 4763191 (1988-08-01), Gordon et al.
patent: 4769810 (1988-09-01), Eckberg, Jr. et al.
patent: 4769811 (1988-09-01), Eckber, Jr. et al.
patent: 4771425 (1988-09-01), Baran et al.
patent: 4819228 (1989-04-01), Baran et al.
patent: 4827411 (1989-05-01), Arrowood et al.
patent: 4833706 (1989-05-01), Hughes-Hartogs
patent: 4835737 (1989-05-01), Herrig et al.
patent: 4879551 (1989-11-01), Georgiou e
Cesari and McKenna LLP
Cisco Technology Inc.
Kizou Hassan
Qureshi Afsar M.
LandOfFree
Snapshot routing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Snapshot routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Snapshot routing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2597403