US4862454A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Switching method for multistage interconnection networks with hot spot traffic
Assignee: International Business Machines Corp
•
Filing: 1988-07-15
•
Granted: 1989-08-29
•
Expires: 2008-07-15
Abstract
Abstract A method of switching data packets through a multistage interconnection network (MIN), to prevent hot spot traffic from degrading uniform traffic performance. Each of the address bits in each packet determine the output link at each particular stage of the network to which the packet must be routed. A packet is accepted at an input buffer of the stage only if an acceptance test is met. This acceptance test depends not only on the availability of a buffer at the input buffer at a stage of the network, but also on how the address bits of the packet are related to address bits of other packets in the buffer, and on the stage of the network. If the acceptance test is not met, the packet is retained in the previous stage of the MIN, and is moved to the rear of a queue of packets in the buffer at that stage, or given a lower priority in the queue.
Inventors
- 👤 Daniel M. Dias
- 👤 Manoj Kumar
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 23:31
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L49/00; H04L49/25; H04L49/253; H04L49/254; H04L49/30; H04L49/3018; H04L49/40
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
122 words
A method for switching packets in a multistage interconnection network including a plurality of switching means each having at least one input port and an output port, a buffer coupled to the input port adapted to receive packets from the input port, comprising the steps of: (a) detecting an arrival of a packet at the input port; (b) determining whether the buffer is full; (c) determining as an acceptance test of the packet whether the buffer contains less than a predetermined number of packets directed to a same destination as the packet detected in step (a); (d) moving the packet detected in step (a) into the buffer only if the buffer is not full and also the separate acceptance test is met.
Claim 2
Independent Claim
122 words
A method for switching packets in a multistage interconnection network including a plurality of switching means each having at least one input port and an output port, a buffer coupled to the input port adapted to receive packets from the input port, comprising the steps of: (a) detecting an arrival of a packet at the input port; (b) determining whether the buffer is full; (c) determining as an acceptance test of the packet whether the buffer contains less than a predetermined number of packets directed to a same destination as the packet detected in step (a); (d) moving the packet detected in step (a) into the buffer only if the buffer is not full and also the separate acceptance test is met.
Claim 3
Dependent Claim
86 words
The method of claim 1 wherein each switching means includes a plurality of buffers, one of each input ports, for receiving and queuing said packets and wherein step (a) further comprises the steps of: first, selecting a packet from each buffer of the plurality of buffers; determining if more than one selected packet is directed towards a single output port; second, selecting one of the commonly directed packets; and, forwarding the second selected packet to the input port of a switching means in the next stage.
Claim 4
Dependent Claim
55 words
The method of claim 1 wherein the network further includes a plurality of buffers for receiving and queuing said packets, further comprising the step of moving the forwarded packet to a tail of a buffer if the acceptance test is not met and the forwarded packet is not received into the buffer in step (d).
Claim 5
Dependent Claim
46 words
The method of claim 1 further comprising the steps of: determining the number of packets in the buffer; and performing steps (c) and (d) in at least one stage of the multistage system only if the determined number of packets is greater than a predetermined number.
Claim 6
Dependent Claim
28 words
The method of claim 3 wherein packets that are moved to the tail of a buffer are given lower priority than that for other packets in the buffer.
Claim 7
Independent Claim
144 words
A method for routing a plurality of packets, each including a destination address, through a multistage interconnection network having a plurality of switching means, each having at least one input port and one output port and a buffer coupled to the input port adapted to receive packets from the input port, comprising the steps of: (a) detecting an arrival of a packet at the input port; (b) determining whether the buffer is full; (c) separately determining whether an acceptance test of the packet is met, wherein the acceptance test is a function of the destination address of the packet detected in step (a), the destination addresses of any packets in the buffer, and the stage of the network; (d) moving the packet detected in step (a) into the buffer only if the buffer is not full and also the separate acceptance test is met.
Claim 8
Independent Claim
144 words
A method for routing a plurality of packets, each including a destination address, through a multistage interconnection network having a plurality of switching means, each having at least one input port and one output port and a buffer coupled to the input port adapted to receive packets from the input port, comprising the steps of: (a) detecting an arrival of a packet at the input port; (b) determining whether the buffer is full; (c) separately determining whether an acceptance test of the packet is met, wherein the acceptance test is a function of the destination address of the packet detected in step (a), the destination addresses of any packets in the buffer, and the stage of the network; (d) moving the packet detected in step (a) into the buffer only if the buffer is not full and also the separate acceptance test is met.
References Cited (Backward Citations)
US4449182A
Cited
US4449182B1
Cited
US4475192A
Cited
US4500990A
Cited
US4494230A
Cited
US4551833A
Cited
US4556972A
Cited
US4607363A
Cited
US4727537A
Cited
US4769811A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-08-28 | 1993-02-27 | 1993-08-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-08-28 | 1997-02-27 | 1997-08-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-08-28 | 2001-02-27 | 2001-08-29 | $7700.00 | Window Closed / Lapsed |