Network with efficient message routing

• US 6,201,794 B1
• Filed: 08/21/1997
• Issued: 03/13/2001
• Est. Priority Date: 03/07/1997
• Status: Expired due to Fees

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Stewart, Brett B., Teich, Paul R.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Pezzlo, John
• Application Number:
  US08/915,767
• Time in Patent Office: 1,300 Days
• Field of Search: 370/248, 370/249, 370/254, 370/255, 370/351, 370/389, 370/400, 370/401, 370/408, 370/237, 370/260, 370/376, 709/238, 709/243, 379/201, 379/221, 379/34, 379/136, 707/8
• US Class Current: 370/248
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04Q 2213/13092 Scanning of subscriber lines, monitoring
• CPC Class Codes: H04Q 2213/13138 Least cost routing, LCR
• CPC Class Codes: H04Q 2213/1316 Service observation, testing
• CPC Class Codes: H04Q 2213/13164 Traffic (registration, measurement,...)
• CPC Class Codes: H04Q 2213/13352 Self-routing networks, real-time routing
• CPC Class Codes: H04Q 2213/13353 Routing table, map memory
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

Pilot messages are transmitted between communicating nodes on a network either periodically or as a continuous background process in order to determine the most efficient path for transmitting a message from a node to every other node in a network depending on prevailing message traffic conditions. Each node can transmit pilot messages at predetermined intervals or in response to commands from a master riding node. A master riding node can monitor message traffic and alter the sequence in which pilot messages are transmitted, thereby more frequently monitoring traffic between nodes with heavy communication requirements. By routing messages from a source node to a destination over a predetermined efficient path, it is no longer necessary for the system to determine a next destination point as messages traverse the network.

Claims

1. An information communication network comprising:

a plurality of nodes;

a plurality of links;

a plurality of transfer points each of which is connected to at least three different ones of said plurality of links, said plurality of transfer points each providing connectivity between a first of said at least three different ones and a second of said at least three different ones of said plurality of links so as to provide a part of a network connection between a first of said plurality of nodes and a second of said plurality of nodes, and

a routing bus that couples said plurality of nodes to each other without usage of any of said transfer points;

at least one node of said plurality of nodes transmitting a pilot signal recognizable by another node of said plurality of nodes, said one node recording a path taken by said pilot signal to said another node and routing subsequent messages to said another node over said path,

said one node recording the path taken by said pilot signal based on a route determining message sent over said routing bus from said another node to said one node, said routing bus being a bus dedicated for passing said route determining message between said plurality of nodes,

wherein said pilot signal acquires routing tags indicative of points on a route through said network taken by said pilot signal from said one node to said another node, said routing tags being stored in a memory so that a subsequent message from said one node to said another node is passed through said points indicated by said routing tags,

wherein said one node transmitting said pilot signal comprises said memory,

wherein said one node comprises a master routing node, and

wherein all others of said plurality of nodes operate as backup master routing nodes in a particular hierarchical order, such that when said one node fails, one of said all others of said plurality of nodes having a highest priority is selected as a new master routing node.

2. An information communication network as recited in claim 1, wherein said memory in said master routing node stores routing information for all nodes of said network.

3. An information communication network as recited in claim 2, wherein said master routing node comprises a network message traffic monitor.

4. An information communication network as recited in claim 3, wherein said network message traffic monitor comprises message transmitting circuiting transmitting messages to specified other nodes of said networks and message receiving circuiting receiving corresponding responses indicative of said route taken as a background process.

5. An information communication network as recited in claim 4, wherein said master routing node updates information stored in said memory based on said background process.

6. An information communication network as recited in claim 5, wherein said background process is performed at predetermined times.

7. An information communication network as recited in claim 5, wherein said background process is repeated for predetermined ones of said nodes at predetermined times.

8. An information communication network as recited in claim 7, wherein said master routing node selects said predetermined ones of said nodes depending on selected message traffic statistics.

9. An information communication network as recited in claim 8, wherein said selected message traffic statistics include one of throughput, error rate, and up time.

10. An information communication network as recited in claim 5, wherein said background process is performed continuously.

11. An information communication network as recited in claim 10, wherein said background process is repeated for predetermined ones of said nodes at predetermined times.

12. An information communication network as recited in claim 11, wherein said master routing node selects said predetermined ones of said nodes depending on selected message traffic statistics.

13. An information communication network as recited in claim 1, wherein said route determining message is recognizably distinct from an information transferring message.

14. An information communication network as recited in claim 1, wherein said route determining message comprises an information transferring message.

15. An information communication network as recited in claim 1, wherein each individual node of said plurality of nodes transmits said route determining message.

16. An information communication network as recited in claim 15, wherein each individual node transmits said route determining message at a time determined by said individual node and receives an updated response indicative of said route.

17. An information communication network as recited in claim 16, wherein each said node updates said memory based on said updated response.

18. An information communication network as recited in claim 17, wherein said time is periodic.

19. An information communication network as recited in claim 15, wherein each individual node begins transmission of said Pilot signal simultaneously.

20. An information communication network as recited in claim 16, wherein said time is determined by said individual node based on message traffic of said node.

21. An information communication network as recited in claim 1, wherein said master routing node determines if said routing bus is currently operational, and if not, wherein said route determining message is sent from said another node to said one node along a same path as the pilot signal.