Traffic routing management system using the open shortest path first algorithm

• US 7,099,341 B2
• Filed: 05/03/2002
• Issued: 08/29/2006
• Est. Priority Date: 05/03/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lingafelt, Charles Steven, Noel, Francis Edward Jr., Rincon, Ann Marie
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US10/137,785
• Publication Number:
  US 20030206528A1
• Time in Patent Office: 1,579 Days
• Field of Search: None
• US Class Current: 370/401
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/22 Alternate routing

Abstract

A network processor is used for the routing of objects in non-data networking applications. The processor utilizes the Open Shortest Path First (OSPF) algorithm to capitalize on the benefits of data control for object traffic control and costs. A network processor is used at each point in a grid represented by intersecting paths. One or more routing tables are embedded in each network processor. Each routing table describes links with other network processors in the grid to which the network processor is interconnected. A cost factor is associated with each link and is constantly updated by the OSPF as new information becomes available. If a link or route becomes unavailable, the cost is set at infinity. The system then creates an alternative path for the object between a source and the desired destination that bypasses the unavailable link or route.

Claims

1. A system for moving an object along a path in a network grid from a source to a destination according to the OSPF routing algorithm, comprising:

a) network processing capabilities at each node in the grid represented by intersecting paths, wherein the processing capabilities at each node comprise a network processor, one or more of the network processors is represented by a software simulator in a CPU, and the entire collection of network processor simulators and the common control point are within a single CPU or a CPU complex;

b) a routing table for each of the network processing capabilities, the routing table comprising links with other nodes in the grid to which each of the network processing capabilities is interconnected;

c) a cost factor associated with each link included in the table of each network processor;

d) a procedure for setting a cost of infinity for any intersection that becomes unavailable; and

e) the ability to build an alternative path for the object between the source and the destination that bypasses the unavailable intersection using the OSPF routing algorithm.

2. The system according to claim 1 further including additional links in the routing table with endpoint locations in the grid to which the network processor is interconnected.

3. A method of moving a non-data object along a path in a network grid from a source to a destination according to the OSPF routing algorithm, comprising the steps of:

a) establishing network processing capabilities at each node in the grid represented by intersecting paths, wherein the processing capabilities at each node comprise a network processor, one or more of the network processors is represented by a software simulator in a CPU, and the entire collection of network processor simulators and the common control point are within a single CPU or a CPU complex;

b) creating a routing table for each of the network processing capabilities, the routing table comprising links with other nodes in the grid to which each of the network processing capabilities is interconnected;

c) inserting data by a common control point into the table of each network processor, said data representing a cost factor associated with each link that is created in step b;

d) setting a cost of infinity for any intersection that becomes unavailable; and

e) building at least one alternative path for the object between the source and the destination that bypasses the unavailable intersection using said routing algorithm.

4. The method according to claim 3 wherein the network processing capabilities at each node are handled by a network processor.

5. The method according to claim 4 including the further steps of creating additional links in the routing table with endpoint locations in the grid to which each of the network processors is interconnected, and inserting into the table of each network processor a cost factor associated with each link that is thus created.

6. The method according to claim 3 wherein the object being routed comprises mail, packages, or articles of manufacture.

7. The method according to claim 3 wherein the object being routed comprises electricity, crude oil, or natural gas.

8. The method according to claim 3 wherein the object being routed comprises a person.

9. The method according to claim 8 wherein the person is being routed on a mode of transportation selected from the group consisting of aircraft, trains, automobiles, buses and water vessels.

10. An object routing system including a network processor for use with an OSPF routing algorithm to move the object along a path in a grid from a source to a destination, said network processor including:

a) at least one MAC layer;

b) wide bandwidth busses for delivering information between said MAC layer and one or more physical layer devices supported by the network processor;

c) an embedded Processor Complex (EPC) using one or more routing tables generated by the OSPF algorithm;

d) an enqueue-dequeue up scheduler (EDS-UP) to process data packets received by said MAC layer from the physical layer devices, to store the headers from the packets and to forward the packets to a switch fabric to prioritize the export of the packet data;

e) an enqueue-dequeue down scheduler (EDS-DN) to receive data packets from a switch fabric, said scheduler utilizing a traffic management function.

11. The system according to claim 10 wherein the traffic management function serves to route the packets received from a switch fabric through the other of the MAC layer to one or more output ports according to priority as directed by a switch fabric.

12. The system according to claim 11 including a scheduling data manager that delivers packets from the EDS-UP through a serial port to a switch fabric, and a scheduling data manager that receives packets from a switch fabric and delivers the packets to the EDS-DN.

13. The system according to claim 10 wherein the embedded processor complex is supported by SRAM and DRAM storage.

14. The system according to claim 13 wherein the network processor is embedded in a semiconductor chip, and the SRAM and DRAM are off-chip.

15. The system according to claim 10 wherein the network processor further includes a scheduling data manager function for resolving conflict of packet addresses going to a switch fabric, and for rerouting of packets from a switch fabric to the enqueue-dequeue down scheduler.