Programmable, distributed network routing
First Claim
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.
12 Assignments
0 Petitions
Accused Products
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.
-
Citations
17 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10)
-
-
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. - View Dependent Claims (12, 13)
-
-
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. - View Dependent Claims (15, 16, 17)
-
Specification