Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Routing data updating
Reexamination Certificate
1999-06-01
2003-04-29
Geckil, Mehmet B. (Department: 2142)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Routing data updating
C709S238000
Reexamination Certificate
active
06557044
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field networking and, more particularly, to the field of routers in networks.
2. Description of the Related Art
Networks provide for transmission of information from a source to a destination over a particular route. The information is transmitted along the route through routers. Typically, each router has knowledge of various routes available in the network and this knowledge is stored in a route database or route table. The information is transmitted in accordance with a particular protocol and routers in the network may support any of a number of protocols. Thus, the router may store multiple routes which are available using multiple protocols.
An example of a routing table is shown in
FIG. 1
which illustrates a table
100
having a plurality of entries, one for each of routes R
1
to R
5
,
101
. Each entry includes a sequence number
103
and other information
102
. The other information may include, for example, next hop information (i.e., identification of the next router in the route), various metrics which describe the route (e.g., number of hops, bandwidth), and route preference information.
The sequence number
103
is changed each time there is a change to the route. Further, each time any route in the table changes, a table sequence number
105
is updated. In this way, as will be seen, it can be easily determined whether any route in the table has changed since the last time the table was examined. If there has been a change, individual routes are examined to determine which routes changed.
It is desirable to exchange routes between the various protocols. This is typically done via the central routing table
100
using either a polling or interrupt mechanism. For example, using the polling method, periodically, the table is queried by each protocol to determine if there have been changes to the various routes from other protocols which are of interest (in the interrupt type mechanism, an interrupt occurs when routes are changed). Initially, the table sequence number
105
is checked to see if it has changed since the last time the table was polled. If it has not changed, no changes have been made to the routes of interest. If the table sequence number
105
has changed, then sequence numbers of the individual routes of interest are checked to determine if they have changed.
Unfortunately, if just one route has changed, even one that is not of interest, all routes must still be checked. This can, in a typical implementation having thousands (even hundreds of thousands) of routes, be computationally burdensome. The burden is increased because in a typical implementation, the polling process may be required to take place quite frequently (e.g., every several seconds).
Thus, it would be desirable to develop a system in which the overhead burden of determining which routes in routing table have changed is reduced.
SUMMARY OF THE INVENTION
A route table providing a list of pointers to checksum values computed across routes of interest to a particular protocol is described. When the protocol wishes to determine whether routes in the table have changed since the last time the table was examined, the checksum value may be examined to determine if it has changed since the last time the table was examined. If the checksum value has changed, individual routes of interest are examined to determine which route or routes of interest have changed.
REFERENCES:
patent: RE31182 (1983-03-01), Crager et al.
patent: 5473603 (1995-12-01), Iwata
patent: 5530806 (1996-06-01), Condon et al.
patent: 5633858 (1997-05-01), Chang et al.
patent: 5751971 (1998-05-01), Dobbins et al.
patent: 5764741 (1998-06-01), Barak
patent: 5914953 (1999-06-01), Krause et al.
patent: 5987521 (1999-11-01), Arrowood et al.
patent: 5991388 (1999-11-01), Sonnenberg
patent: 5999536 (1999-12-01), Kawafuji et al.
patent: 6014380 (2000-01-01), Hendel et al.
patent: 6023563 (2000-02-01), Shani
patent: 6064726 (2000-05-01), Whited
patent: 6069895 (2000-05-01), Ayandeh
patent: 6075852 (2000-06-01), Ashworth et al.
patent: 6081524 (2000-06-01), Chase et al.
Moy, J.; “OSPF 2”, Request for Comments (RFC) 1583, Mar. 1994.
Cain Brad
Hardjono Thomas
Blakely , Sokoloff, Taylor & Zafman LLP
Geckil Mehmet B.
Nortel Networks Limited
Thompson Marc D.
LandOfFree
Method and apparatus for exchange of routing database... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for exchange of routing database..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for exchange of routing database... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3063024