Method of packet routing in torus networks with two buffers per

Details Method of packet routing in torus networks with two buffers per Method of packet routing in torus networks with two buffers per

1992-10-29

1995-08-22

Marcelo, Melvin

Multiplex communications

Wide area network

Packet switching

390 8512, 390 943, H04L 1242

Patent

active

054447011

ABSTRACT:
A method is for routing packets in parallel computers with torus interconnection networks of arbitrary size and dimension having a plurality of nodes, each of which contains at least 2 buffers per edge incident to the node. For each packet which is being routed or which is being injected into the communication network, a waiting set is specified which consists of those buffers to which the packet can be transferred. The packet can be transferred to any buffer in its waiting set which has enough storage available to hold the packet. This waiting set is specified by first defining a set of nodes to which the packet is allowed to move and then defining a candidate set of buffers within the defined set of nodes. Then, defining an ordering of the nodes across the network from smallest to largest. The buffers in each node are then classified into four classes. After the buffers in each node have been classified, a set of rules for placing into the waiting set those classes of candidate buffers to which the packet can move is provided such that the routing method is free of deadlock, livelock, and starvation.

REFERENCES:
patent: 4742511 (1988-05-01), Johnson
patent: 4805091 (1989-02-01), Thiel et al.
patent: 4814980 (1989-03-01), Peterson et al.
patent: 4933933 (1990-06-01), Dally et al.
patent: 4984235 (1991-01-01), Hillis et al.
patent: 5008815 (1991-04-01), Hillis
patent: 5105424 (1992-04-01), Flaig et al.
patent: 5151900 (1992-09-01), Snyder et al.
patent: 5157692 (1992-10-01), Horie et al.
Y. Tamir and G. L. Frazier, "Dynamically--Allocated Multi-Queue Buffers for VLSI Communication Switches", IEEE Transactions on Computers, vol. 41, No. 6, pp. 725-737, Jun. 1992.
R. Cypher and L. Gravano, "Adaptive, Deadlock-Free Packet Routing in Torus Networks with Minimal Storage", IBM RJ 8571 (77350), Jan. 15, 1992.
Dally, William J., "Deadlock-Free Message Routing in Multiprocessor Interconnection Networks", IEEE Transactions on Computers, vol. C-36, No. 5, May 1987.
Dally, William J., "The torus routing chip", Distributed Computing (1986) 1:187-196.
Hayes, John P., "Computer Architecture and Organization", Second Edition (1988), pp. 645-664.
Hwang, Kai, "Computer Architecture and Parallel Processing", (1984), Chapter Five, pp. 325-392.
Konstantinidou, S., "Chaos Router: A Practical Application of Randomization in Network Routing", 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, Jul. 2-6, 1990, Island of Crete, Greece.
Tamir, Yuval, "Dynamically--Allocated Multi-Queue Buffers for VLSI Communication Switches", IEEE Transactions of Computers, vol. 41, No. 6 Jun. 1992.
Tanenbaum, Andrew S., "Computer Networks", Second Edition (1988), Chapter 1, pp. 6-21.
Van De Goor, A. J., "Computer Architecture and Design", (1989), Chapter 16, pp. 473-506.

Affiliated with

Also associated with

Rating

Method of packet routing in torus networks with two buffers per does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of packet routing in torus networks with two buffers per , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of packet routing in torus networks with two buffers per will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2147262