Programmable, distributed network routing

• US 5,721,819 A
• Filed: 05/05/1995
• Issued: 02/24/1998
• Est. Priority Date: 05/05/1995
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Newhall, Robert E., Galles, Michael B.
• Primary Examiner(s): Harvey, Jack B.
• Assistant Examiner(s): Etienne, Ario
• Application Number:
  US08/435,452
• Time in Patent Office: 1,026 Days
• Field of Search: 395/200.15, 395/200.03, 395/200.02, 395/200.06, 395/200.1, 395/200.09, 395/200.04, 395/200.14, 395/200.16, 395/200.13
• US Class Current: 709/243
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/34 Source routing

Abstract

A programmable, distributed network routing system and method uses routing tables which are distributed throughout the network. Routing tables are programmed to route packets to the target device by the preferred route. When a packet is injected into the network for delivery to a particular node each router along the path taken by the packet consults its local routing table and sends the packet along the preferred route. In one implementation the router tables contained in each router contain hierarchical information about the network. For nodes that are near the subject router, a complete local table entry exists. For nodes which are more distant, several of these distant nodes share a single remote table entry. When a router receives a packet, it reads the egress port ID from the packet header and begins arbitrating for that egress port so that the packet can be sent to the next router. At the same time, the router accesses the router table to determine the egress port ID for the next router. This ID is inserted into the header before the packet is transferred to this next router.

Claims

1. A distributed routing system for routing messages along a preferred route in a multi-node network, comprising:

a plurality of routers distributed among the nodes of the network, each router having a plurality of ports, said ports having routers connected thereto, wherein a message is received by a current router via one of said plurality of ports and sent along a preferred route to a next router via a second one of said plurality of ports; and

each router comprising a router table associated with each said port out of which a message can be routed to a next router, each said router table comprising means for determining a port of said next router out of which to route said message, wherein said determination is made based on a destination address of said message.

2. The distributed routing system of claim 1, wherein said router table comprises:

a first table having a plurality of first entries, each first entry identifying one of said plurality of ports of said next router out of which said message is to be routed;

wherein said destination address of said message is applied to said first table to select the appropriate one of said plurality of first entries that corresponds to said destination address to route said message to said next router along the preferred route.

3. The distributed routing system of claim 2, wherein the network nodes are divided into two or more groups of nodes, and wherein said router table further comprises:

a second table having a plurality of second entries, each second entry identifying one of said plurality of ports of said next router out of which said message is to be routed;

wherein said destination address of said message is applied to said second table to select the appropriate one of said plurality of second entries, and wherein each said second entry corresponds to a plurality of destination addresses that each address a node within a single one of said two or more groups of nodes; and

means for selecting one of said plurality of first entries where said destination address identifies a destination that is in the same group of nodes as said current router and for selecting one of said plurality of second entries where said destination address identifies a destination that is in a different group from said current router.

4. The distributed routing system of claim 3, wherein said router table further comprises means for determining whether said destination address indicates a destination for said message that is in the same group of nodes as said current router.

5. The distributed routing system of claim 1, wherein each of said means for determining a port of said next router out of which to route said message comprises:

means for retrieving one of a plurality of entries from said router table, wherein said retrieved entry comprises a next egress port ID that identifies said port of said next router out of which to route said message, and wherein said entry is retrieved based on a destination address of said message received by said current router; and

means for inserting said next egress port ID into said message as a current egress port ID for said next router before said message is routed to said next router.

6. The distributed routing system of claim 5, wherein each of said plurality of routers further comprises:

means for reading said next egress port ID from said received message said read next egress port ID indicating a specific one of said ports out of which to route said message;

means for initiating a send process for said indicated port while said means for determining determines said next egress port ID for said next router.

7. The distributed routing system of claim 6, wherein said means for initiating a send process comprises means for arbitrating for said indicated port.

8. The distributed routing system of claim 2, wherein said plurality of first entries are written to said first table when the multi-node network is configured, and said plurality of first entries are further updated by when the network configuration changes.

9. A hierarchical distributed routing system for routing messages along a preferred route in a multi-node hierarchical network to a destination node designated by a destination address, where the hierarchical network comprises a plurality of groups of nodes connected together at a metalevel, comprising:

a plurality of routers to route messages from a current router in a first node to a next router in a second node along the preferred route, wherein each router comprises a plurality of ports;

a hierarchical router table for each current router, said hierarchical router table comprising

a first table having a plurality of first entries, each said first entry identifying one of said plurality of router ports out of which said message is to be routed wherein said first entries correspond to a destination node that is within the same group of nodes as the router in which said first table resides; and

a second table having a plurality of second entries, each second entry identifying one of said plurality of router ports but of which said message is to be routed, wherein each said second entry corresponds to a plurality of destination addresses that each address a node within a single one of said plurality of groups of nodes;

wherein said pluralities of first and second entries each correspond to an egress port in the next router out of which said message is to be routed to follow the preferred route to the destination node.

10. The hierarchical distributed routing system of claim 9, further comprising means for determining whether the destination node is in the same group of nodes as the current router and for selecting an appropriate entry from said first and second table based on this determination.

11. A method for distributed routing of messages in a multi-node network comprising a plurality of routers, the method comprising the steps of:

receiving a message in a current router, the message comprising a destination address indicating a destination node for said message; and

determining an egress port out of which to route said message, said determination based on said destination address;

wherein said step of determining an egress port comprises the step of applying said destination address to a router table to determine an egress port of a next router, said egress port being a port out of which to route said message from said next router.

12. The method according to claim 11, wherein said step of determining an egress port comprises the step of applying said destination address to a router table to determine an egress port of said current router out of which to route said message to a next router.

13. The method according to claim 11, further comprising the steps of:

said current router reading a current egress port ID from a header of said message, said current egress port ID indicating an egress port of said current router out of which to route said message;

said current router arbitrating for said egress port of said current router while said current router applies said destination address to said router table to determine said egress port of said next router; and

said current router inserting said egress port of said next router into said message before routing said message to said next router.

14. In a multi-node network having a plurality of nodes connected by a plurality of edges and further having a plurality of routers for routing messages from a current node to a next node, a method of dynamically routing messages between node pairs in the network, the method comprising the steps of:

determining preferred routes between the node pairs of the network;

programming router tables to route a message from a current router to a next router along a preferred route between a node pair; and

routing a message from a current router to a next router along the preferred route wherein the message comprises a destination address indicating a destination node for said message and wherein said routing step comprises the step of determining an egress port of said next router out of which to route said message, said determination based on said destination address.

15. The method according to claim 14, wherein said step of determining an egress port comprises the step of applying said destination address to a router table to determine an egress port of said current router out of which to route said message to a next router.

16. The method according to claim 14, wherein said step of determining an egress port comprises the step of applying said destination address to a router table to determine an egress port of a next router, said egress port being a port out of which to route said message when said message reaches said next router.

17. The method according to claim 16, further comprising the steps of:

said current router reading a current egress port ID from a header of said message, said current egress port ID indicating an egress port of said current router out of which to route said message;

said current router arbitrating for said egress port of said current router while said current router applies said destination address to said router table to determine said egress port of said next router; and

said current router inserting said egress port of said next router into said message before routing said message to said next router.