Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-03-07
2004-08-17
Nguyen, Steven H D (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S389000, C370S395320, C711S216000
Reexamination Certificate
active
06778539
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method for routing data cells in a multi-node communication network, and to a programmable, distributed network routing system for routing data cells in a multi-node communication network.
BACKGROUND OF THE INVENTION
To use lookup tables have for some time been considered to be the best way to do routing in a SAN (System Area Network). A typical address space in a SAN is usually very large (e.g. 64 k nodes, i.e. 16-bit addresses). However, with current technology it is not feasible to have on-chip routing tables that are big enough to directly support topologies that use the full address space of 64 k, and at the same time keep the routing table lookup latency minimal. A reasonable table size would be in the range 256 to 1024 entries, using respectively 8 or 10 bits of a (e.g.) 16-bits DestinationID for routing. According to current thinking, this will limit the size of the SAN network to respectively 256 or 1024 SAN nodes.
U.S. Pat. No. 5,721,819 describes a method for routing data cells in a computer network based on two routing tables. The first routing table is used to route cells to local nodes while the second routing table is used to route cells to remote nodes.
U.S. Pat. No. 5,574,849 discloses a method for routing data cells in a computer network using a routing table in combination with algorithmic routing.
The disadvantage with the routing method In U.S. Pat. No. 5,721,819 is the requirement of two routing tables, which consumes expensive chip area. Although the routing solution in U.S. Pat. No. 5,574,849 reduces the chip area, it is not a very flexible solution because fixed parts of the cell's destination address is used for routing table lookup and algorithmic routing decisions. This enforces topology restrictions.
In ordinary table routing the routing table must have at least as many entries as the size of the topology. If a topology needs to have as many as 64 k nodes, a lookup table with 64 k entries is required. This is the most flexible solution. The disadvantage-of this would be, as mentioned, that the size of the routing table is large and hence consumes valuable chip area, and that the latency for routing table lookup increases proportionally.
The object of the present invention is to provide a solution to the problems presented above.
SUMMARY OF THE INVENTION
In accordance with a first aspect the invention provides a method for routing data cells in a multi-node communication network, comprising a plurality of routers including respective router tables, forming a top topology and at least one sub-topology, each sub-topology being strictly hierarchical dependent on a parent node in the top topology, the number of sub-topologies being 2
N−n
, the destination address of the data cell being N bits, and the size of the router tables being 2
n
bits, the method comprising the following steps:
comparing a first group of N−n bits of the destination address of the data cell with a router mask, to determine whether the data cell is in a correct or a wrong sub-topology with regard to destination, and then
performing one of the two following steps:
provided the data cell is in the correct sub-topology, routing the cell to its destination within the sub-topology by using a remaining group of bits of the data cell destination address for routing table look-up,
provided the data cell is in a wrong sub-topology, forwarding the cell to the top topology, wherein the routers within the top-topology use the first group of N−n bits of the destination address of the data cell for routing table look-up hereby routing the cell to its correct top node/sub-topology.
In a preferred embodiment a comparator of size N−n may be used for determining whether the data cell is in the correct sub-topology. Routing control may, in another preferred embodiment, be performed in a router by a register, the register indicating whether a router belongs to a top topology or a sub-topology, and controlling which group of the destination address to be used for router table look-up.
The method may include, provided the data cell is in a wrong sub-topology, forwarding the cell to the top topology by utilizing a configuration bit included in the register, indicating the path to the top topology.
In another preferred embodiment the method comprises using a mask for sub-topology determination increasing the number of paths between the sub-topologies.
In accordance with a second aspect the invention provides a programmable, distributed network routing system for routing data cells in a multi-node communication network, the network comprising a plurality of routers, the routers forming a top topology and at least one sub-topology, each sub-topology being strictly hierarchical dependent on the parent node in the top topology, the number of sub-topologies being 2
N−n
, the destination address of a data cell being N bit, each router comprising a router table having a size of 2
N−n
bit, and a register operative to performing routing control indicating whether the router belongs to a top topology or a sub-topology, and controlling which part of the destination address to be used for table lookup, the register further including means for determining whether the data cell is in a correct or a wrong sub-topology with regard to destination.
In another preferred embodiment of the invention the determining means includes a comparator of size N−n. A configuration bit indicating the path to a top topology may be included in the register.
The determining means may further comprise a mask for sub-topology determination providing a plurality of paths between sub-topologies. The register may then further include a configuration bit indicating the path to a top topology or another sub-topology.
With some topology restrictions, a routing table of 2
n
entries, where n<N, and with a SAN DestinationID that consists of N bits, routing SANs using the full address space can be made by partitioning the network topology into 2
(N−n)
sub-topologies (levels).
Each sub-topology will have a fixed maximum size, and the routing table must have at least as many entries as the size of the biggest of these. If a topology needs to have as many as 512 nodes on one level, a lookup table with 512 entries is required. Partitioning a topology into just one level, i.e. ordinary table routing, would give the most flexible solution. The disadvantage of this would be, as mentioned, that the size of the topology would be very limited. Having several levels will reduce the flexibility, but will make it possible to use the whole SAN address space with reasonable table sizes, and at the same time keep lookup latency very low.
The decision on which part of the DestinationID to be used (i.e. e.g. DestinationID[(N−1):((N−1−n)] or DestinationID[n−1:0]) for table lookup can e.g. be based on configuration bits. In addition to the table, there is need for a n-bit comparator for the bits not used for the table lookup. The output from the comparator is used by the routing units, not being on the top level, to accommodate traffic between different sub-topologies. A configuration bit saying whether the routing unit will bring a packet to a higher level if the comparator says its destination is in another sub-topology, is also required.
The invention combines a relatively small routing table with a routing mask in a way that makes it possible to use the whole network address space, keeping both routing table latency minimal and chip area small.
The method and apparatus according to the invention also provide a more optimal way of using routing-tables. The routing differs from ordinary table routing in that the part of the destination address (DestinationID) used for table lookup is variable.
REFERENCES:
patent: 4864559 (1989-09-01), Perlman
patent: 5305305 (1994-04-01), Harper et al.
patent: 5633858 (1997-05-01), Chang et al.
patent: 5721819 (1998-02-01), Galles et al.
patent: 6061350 (2000-05-01), Min
pa
Nguyen Steven H D
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Multilevel table routing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multilevel table routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multilevel table routing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3346509