Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
2000-02-15
2004-08-10
Dharia, Rupal (Department: 2141)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C709S242000, C709S224000, C709S228000
Reexamination Certificate
active
06775709
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to routing of messages,in a communication system and, more particularly, to arrangements for issuing network information messages among routers in a communication network.
2. Related Art
In a communication system in which communications among subscribers traverse a network of routers or switches to provide required communication paths, distributed protocols may be used to determine paths through which data messages should be forwarded through the network. The distributed protocols provide an arrangement in which individual routers or switches in the network issue network information update messages on network topology, address information and/or traffic flow pertaining to the individual routers. Messaging is arranged so that each router or switch receives network information messages and network information update messages propagated through the network from other routers or switches and issues its own network information update messages to other routers or switches. The network information updates and/or processing results derived from the network information and updates for each router or switch are stored in databases associated with the router or switch.
An example of a distributed protocol is the Open Shortest Path First (OSPF) routing protocol. As described in U.S. Pat. No. 5,881,246 issued to Eric S, Crawley et al. Mar. 9, 1999, each router running the OSPF protocol maintains an identical database describing the network topology. With the same network topology database, each router is able to generate a routing table by forming a shortest-path tree with itself at the root of the tree. The OSPF protocol detects changes in network topology and recalculates paths based on the changed topology. Using the OSPF protocol, each router generates messages such as link state advertisements (LSA) describing the local state of its links. The message is issued from the router to the other routers of the network via its links to neighboring routers.
Since the network connections change according to communication requirements, the issued network information and updates may only be applicable for relatively short time periods owing to changes in network configuration. In an example, a network of mobile routers or nodes changes its configuration very frequently as the routers move and connections among the routers are established and/or lost. As a result of the changes in network configuration, the stored network information and updates have only a limited lifetime and must be frequently refreshed.
Each individual router or switch in the communication network issues its network information update messages for use by other routers or switches. Generally, the updates from a router are issued periodically. Network information messages are also issued in response to an external event requiring a message with different content or when there is an indication of a change in status of the individual router or switch. Timing of issuance of network information messages in known systems is controlled by internal timers in the individual routers so that the issuance times of each router are independent of the issuance timing of the other network routers. In some arrangements, random jitter is added to the update issuance times to avoid coordination of issuance. As a result of the independently timed update messaging among routers, updating of network information in a network of plural routers may be uncoordinated so that the resulting delays in propagation of update messages may interfere with the proper setup of communication paths.
SUMMARY OF INVENTION
The invention is directed to a communication system in which plural routing devices are coupled together to form a network for communications among plural subscribers. At times that are determined internally in the individual routing devices, a routing device generates and issues an update message that includes network information of the routing device. The network information update message is sent to other routing devices in the network and network information update messages are received from other routing devices. The received network information is processed in the routing device to produce a representation of the network topology and traffic flow is controlled in response to issued messages.
According to the invention, a routing device in the network receiving a network information message from another routing device advances the timing of issuance of its next update message according to the state of the internal timing so that the time of issuance of the next update message is coordinated with the receipt of the network information message from the another router.
According to one aspect of the invention, a routing device includes a timing unit that controls the issuance of network information update messages. When a network information message is received from another routing device, the time of issuance of the next network information update message is determined on the basis of the state of the timer. In this way, the issuance of the next network information update message is synchronized to the incoming network information message.
According to yet another aspect of the invention, the network information message issued by a routing device is received by a plurality of other routing devices. The receipt of the message triggers the issuance of network information update messages by the other routing devices so that the issuance times of the other routing devices is synchronized with respect to the received message.
According to yet another aspect of the invention, the messages received from the plural routing devices by a routing device are processed to form set of parameters that are stored in the receiving routing device. The parameters include a representation of the topology of the network.
According to yet another aspect of the invention, the network information message issued by each routing device is a network information update issued at a time determined by information such as a predetermined network change in a received network information message and the state of the timing unit controlling issuance.
According to yet another aspect of the invention, the network information message issued by a routing device also includes network information of other routing devices.
The invention will be better understood from the following more detailed description taken with the accompanying drawings and the claims.
REFERENCES:
patent: 4718002 (1988-01-01), Carr
patent: 5093824 (1992-03-01), Coan et al.
patent: 5101348 (1992-03-01), Arrowood et al.
patent: 5243592 (1993-09-01), Perlman et al.
patent: 5671357 (1997-09-01), Humblet et al.
patent: 5802316 (1998-09-01), Ito et al.
patent: 5850592 (1998-12-01), Ramanathan
patent: 5881246 (1999-03-01), Crawley et al.
patent: 5884047 (1999-03-01), Aikawa et al.
patent: 5913921 (1999-06-01), Tosey et al.
patent: 6002674 (1999-12-01), Takei et al.
patent: 6574197 (2003-06-01), Kanamaru et al.
“Link-State Routing,” John Moy, Ch. 5, “Routing in Communications Networks,” ed. Martha Steenstrup, Prentice Hall, 1995.
“Packet Radio Routing,” Gregory S. Lauer, Ch. 11, “Routing in Communications Network,” ed. Martha Steenstrup, Prentice Hall, 1995.
“Packet Radio Network Routing Algorithms: A Survey,” J.J. Hahn et al., IEEE Communications Magazine, vol. 22, No. 11, Nov. 1984, pp. 41-47.
“The Organization of Computer Resources into a Packet Radio Network,” R.E. Kahn, IEEE Trans. On Communication, vol. COM-25, No. 1, Jan. 1977, pp. 169-178.
“Analysis of Routing Strategies for Packet Radio Networks,” J.J. Garcia Lune Aceves et al., Proc. Of the IEEE INFOCOM '85, Washington, DC, Mar. 1985, 292-302.
“The DARPA Packet Radio Network Protocols,” J. Jubin et al., Proc. of the IEEE, vol. 75, No. 1, Jan. 1987, pp. 21-32.
Baugh April L
Ropes & Gray LLP
LandOfFree
Message routing coordination in communications systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Message routing coordination in communications systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Message routing coordination in communications systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3358053