Space-efficient source routing

Details Space-efficient source routing Space-efficient source routing

1998-06-25

2004-04-06

Hsu, Alpus H. (Department: 2665)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S392000

Reexamination Certificate

active

06717942

ABSTRACT:

FIELD OF THE INVENTION
The invention relates to source routing in which each hop of a route through a network is encoded at a source by port descriptors in a header of a packet.
BACKGROUND OF THE INVENTION
Interconnection networks are used to route packets between terminal nodes in multicomputers, network routers, and other digital systems. Such networks consist of a number of fabric routing nodes arranged in a particular network topology, for example a butterfly or a torus. For a packet to travel from one terminal node A to another terminal B the packet must be routed; that is, it must select an output port at each switch node along the route from the source terminal to the destination terminal. With source routing, these selections are encoded in a routing header which contains a field for each hop along the route.
FIG. 1
shows an example interconnection network, and 8×2×2 three-dimensional torus. This network contains 32 nodes, each of which is identified by a three-digit address, zyx, the digits represent its coordinates in the z, y, and x dimensions, respectively. For example, node A in the figure is at address
001
, and node B is at address
105
. Each node in the figure is connected to six fabric channels, one in the positive and one in the negative direction in each of the three dimensions. The nodes on the boundary of the network have one or more channels that wrap around to the other side of the network. For clarity, the end-around channels in the y and z dimensions are omitted from several nodes.
FIG. 1
also shows a route from node A (
001
) to node B (
105
), denoted by arrows in the figure. This route contains five steps or hops. The source routing header for this route is a string of six port selectors: (+x,+x,+z,+x,+x,e). The first five port selectors specify the output ports to be taken for the five steps of the route. The final port selector, e, directs the packet to exit the network after completing the fifth hop. At each node along the route, starting with node A, the routing header is interpreted by using the first port selector to select the output port at that node and then removing this port selector from the route. For example, at node
002
(just to the right of A), the packet arrives with routing header (+x,+z,+x,+x,e). The first selector (+x) is used to select the +x output port of this node and then removed from the header leaving a header of (+z,+x,+x,e) for node
003
.
In a three dimensional torus, such as shown in
FIG. 1
, there are seven possible output ports at each step (six directions and exit) and thus the port selector can be encoded in a three-bit field with one unused code. One possible encoding is shown in the following table.
Port
Code
+x
000
−x
001
+y
010
−y
011
+z
100
−z
101
e
111
With this encoding, the route shown in
FIG. 1
would be encoded as the 18-bit string; 000 000 100 000 000 111. With the route encoded in this manner, the leftmost three bits are used at each step of the route to select the next output port, and then the encoded route is shifted three-bits left to expose the next port selector for the next step of the route.
The mechanism used to process source routes is illustrated in FIG.
2
. An input route register (IRR)
10
holds the source route from the header of an arriving packet. In the figure, the IRR consists of five three-bit port selectors,
11
-
15
, packed into 15 bits. This small number of fields is used to avoid cluttering the figures. In most routes, considerably longer route registers are used as four hops is insufficient for all but the smallest networks. The IRR is processed to generate the current port selector (CPS) which selects the output port to be used by the packet, and to generate an output route register (ORR)
20
which will be used as the routing header by the router at the next hop. These two functions take place by simple field selection. No logic is required. The leftmost port selector from the IRR is selected as the CPS, and the remaining port selectors are shifted to the left to fill the first four port selectors of the ORR,
21
-
24
. The fifth port selector
25
may be filled with an arbitrary value.
Routers that employ source routing in this manner are similar to those described in U.S. Pat. No. 6,370,145, which issued on Apr. 9, 2002, entitled “Internet Switch Router,” which is incorporated herein by reference in its entirety.
SUMMARY OF THE INVENTION
Encoding source routes using fixed-length port selector fields gives a simple routing descriptor, but one that consumes more space than necessary. In large interconnection networks, the space required by these descriptors can become prohibitive and may limit the scalability of the network. For example, if a routing header for a three-dimensional torus must fit into 32-bits, at most 9 hops can be encoded. Only 10 three-bit fields fit into 32 bits, and one field is required for the exit code at the end of the route.
By using a variable-length routing port descriptor, where the more likely ports are encoded with fewer bits than the less likely ports, we can substantially reduce the required length of a route descriptor. This improves storage efficiency, reduces the overhead of packet headers, and allows us to encode a longer route in a fixed-size descriptor.
In different embodiments, several techniques for space-efficient coding may be used independently or combined:
1. The requirement for an exit descriptor can be eliminated by always shifting in an exit descriptor on the right side of the route when left shifting the route to discard a used port descriptor.
2. Coding for runs of identical port descriptors with run length coding optimizes the common case where a route travels several hops in one direction.
3. More likely ports may be encoded with fewer bits than less likely ports using a variable length code.
4. In variable length coding, a preferred direction can be encoded in the packet header that specifies a set of encoding rules in which the ports that carry a packet in the preferred direction can be encoded with short descriptors while longer descriptors are required to encode a non-preferred direction.
5. The port on which an arriving packet arrives may be used as an implied preferred direction in that dimension thus reducing the length of a preferred direction field by one bit.


REFERENCES:
patent: 4933933 (1990-06-01), Dally et al.
patent: 5088090 (1992-02-01), Yacoby
patent: 5157692 (1992-10-01), Horie et al.
patent: 5181017 (1993-01-01), Frey et al.
patent: 5280480 (1994-01-01), Pitt et al.
patent: 5282270 (1994-01-01), Oppenheimer et al.
patent: 5388213 (1995-02-01), Oppenheimer et al.
patent: 5797035 (1998-08-01), Birrittella et al.
patent: 5841772 (1998-11-01), Daniel et al.
patent: 5963556 (1999-10-01), Varghese et al.
patent: 6052683 (2000-04-01), Irwin
patent: 6137797 (2000-10-01), Bass et al.
patent: 6339595 (2002-01-01), Rekhter et al.
Stunkel, C.B., et al., “The SP2 High-Performance Switch,” IBM Systems Journal, vol. 34, No. 2, 1995, pp. 184-204.
Foley, James D. et al., “Fundamentals of Interactive Computer Graphics,” Addison-Wesley Publishing Company, 1982, pp. 498-499.
McIliece, Robert J., “The Theory of Information and Coding, A Mathematical Framework for Communication,” Addison-Wesley Publishing Company, 1977, Chapter 10, pp. 237-247.
Abali, B., et al., “Routing Algorithms for IBM SP1”, Parallel Computer Routing and Communication, First Int'l Workshop, PCRCW '94, pp. 160-175 (1994).

Affiliated with

Also associated with

Rating

Space-efficient source 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 Space-efficient source routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Space-efficient source routing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3270955