US4630258A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Packet switched multiport memory NXM switch node and processing method
Assignee: Raytheon Co
•
Filing: 1984-10-18
•
Granted: 1986-12-16
•
Expires: 2004-10-18
Abstract
Abstract A packet switching node which processes applied data packets containing routing tag signals indicative of the output port destination to which the data packets are to be applied. The invention comprises an N×M switch node that accepts data packets at any of N input ports and routes each to any of M output ports. The output selected is determined by the routing tag signal in the packet. The node comprises a multiport memory having a predetermined number of memory locations available for storage of data packets applied to each of a plurality of input ports. Control logic coupled to the input and output ports and memory is designed so that the data packets are effectively sorted according to their desired output port destination. The control logic comprises arbitration logic which randomly, in a statistical sense, chooses among any data packets that are directed to the same output port. The algorithm implemented by the arbitration logic is designed so that data packets will not wait indefinitely to be routed from the switch node. A method in accordance with the present invention comprises sorting and storing the data packets based upon the output port destination and then arbitrating among the data packets. The final step involves routing the data packets selected during the arbitration processes to the output ports identified in the routing tag signals.
Inventors
- 👤 Robert J. McMillen
- 👤 Andrew Rosman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 15:05
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; H04L49/00; H04L49/10; H04L49/103; H04L49/30; H04L49/3009; H04L49/40
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
115 words
A packet switching node which processes applied data packets containing routing tag signals indicative of the output port destination to which said data packets are to be applied, said packet switching node comprising: a plurality of input ports; a plurality of output ports; a multiport memory coupled between said input and output ports, said memory having a predetermined number of memory locations available for storage of said data packets applied to each of said input ports; and control logic coupled to said input and output ports and said multiport memory for controlling the storage of data packets in said memory and the routing thereof to said output ports in accordance with said routing tag signals.
Claim 2
Dependent Claim
115 words
A packet switching node which processes applied data packets containing routing tag signals indicative of the output port destination to which said data packets are to be applied, said packet switching node comprising: a plurality of input ports; a plurality of output ports; a multiport memory coupled between said input and output ports, said memory having a predetermined number of memory locations available for storage of said data packets applied to each of said input ports; and control logic coupled to said input and output ports and said multiport memory for controlling the storage of data packets in said memory and the routing thereof to said output ports in accordance with said routing tag signals.
Claim 3
Dependent Claim
46 words
The packet switching node of claim 1 wherein said control logic comprises: a status register coupled to said input ports and said memory for storing said routing tag signals and status signals indicative of the full/empty status of each of the memory locations in said memory.
Claim 4
Dependent Claim
61 words
The packet switching node of claim 2 wherein said control logic further comprises: priority encoder logic coupled to said input ports, said memory and said status register for monitoring the full/empty status of said memory locations, writing said routing tag signals into registers of said status register and writing data packets corresponding to said routing tag signals into selected memory locations.
Claim 5
Dependent Claim
56 words
The packet switching node of claim 3 wherein said control logic further comprises: arbitration logic coupled to said status register, said memory and said output ports for reading said data packets from said memory locations and applying them to the output ports identified in the corresponding routing tag signals based upon a predetermined priority arbitration scheme.
Claim 6
Dependent Claim
85 words
The packet switching node of claim 4 wherein said arbitration logic further comprises: buffer arbitration logic which arbitrates among routing tags entering the same input port that contend for output from the same output port and randomly selects a particular routing tag therefrom; and port arbitration logic coupled to said buffer arbitration logic which arbitrates among all routing tags transmitted by said buffer arbitration logic which contend for the same output port and selects one routing tag therefrom for output from that particular output port.
Claim 7
Dependent Claim
47 words
The packet switching node of claim 5 wherein said arbitration logic further comprises: address generation logic which generates read addresses that control the output of data packets through the appropriate output port for data packets corresponding to those routing tag signals selected by said port arbitration logic.
Claim 8
Dependent Claim
36 words
The packet switching node of claim 6 which further comprises: status update logic which generates signals which reset the full/empty status of the registers corresponding to the data packets applied to any of the output ports.
Claim 9
Dependent Claim
143 words
A packet switching node which processes applied data packets containing routing tag signals indicative of the output port destination to which said data packets are to be applied, said packet switching node comprising: a plurality of input ports; a plurality of output ports; a multiport memory coupled between said input and output ports, said memory having a predetermined number of memory locations available for storage of said data packets applied to each of said input ports; control logic coupled to said input and output ports and said multiport memory for controlling the storage of data packets in said memory and the routing thereof to said output ports in accordance with said routing tag signals, said control logic comprising a storage register for storing said routing tag signals and arbitration logic for determining the output priority of data packets stored in said multiport memory.
Claim 10
Dependent Claim
143 words
A packet switching node which processes applied data packets containing routing tag signals indicative of the output port destination to which said data packets are to be applied, said packet switching node comprising: a plurality of input ports; a plurality of output ports; a multiport memory coupled between said input and output ports, said memory having a predetermined number of memory locations available for storage of said data packets applied to each of said input ports; control logic coupled to said input and output ports and said multiport memory for controlling the storage of data packets in said memory and the routing thereof to said output ports in accordance with said routing tag signals, said control logic comprising a storage register for storing said routing tag signals and arbitration logic for determining the output priority of data packets stored in said multiport memory.
Claim 11
Dependent Claim
186 words
A packet switching node which processes applied data packets containing routing tag signals indicative of the output port destinations to which said data packets are to be applied, said packet switching node comprising: a plurality of input ports; a plurality of output ports; a multiport memory coupled between said input and output ports, said memory having a predetermined number of memory locations available for storage of said data packets applied to each of said input ports; a status register for storing said routing tags signals associated with each of said data packets; buffer arbitration logic coupled to said status register which arbitrates among routing tags corresponding to data packets entering the same input port that contend for output from the same output port and which randomly selects a particular routing tag therefrom; and port arbitration logic coupled to said buffer arbitration logic which arbitrates among all routing tags transmitted by the buffer arbitration logic whose data packets contend for the same output port and which selects one routing tag therefrom that corresponds to the data packet which is selected for output from that particular output port.
Claim 12
Dependent Claim
186 words
A packet switching node which processes applied data packets containing routing tag signals indicative of the output port destinations to which said data packets are to be applied, said packet switching node comprising: a plurality of input ports; a plurality of output ports; a multiport memory coupled between said input and output ports, said memory having a predetermined number of memory locations available for storage of said data packets applied to each of said input ports; a status register for storing said routing tags signals associated with each of said data packets; buffer arbitration logic coupled to said status register which arbitrates among routing tags corresponding to data packets entering the same input port that contend for output from the same output port and which randomly selects a particular routing tag therefrom; and port arbitration logic coupled to said buffer arbitration logic which arbitrates among all routing tags transmitted by the buffer arbitration logic whose data packets contend for the same output port and which selects one routing tag therefrom that corresponds to the data packet which is selected for output from that particular output port.
Claim 13
Independent Claim
117 words
A method of processing applied data packets containing routing tag signals indicative of the output port destination to which said data packets are to be applied in order to route said data packets to the appropriate output ports, said method comprising the steps of: storing said data packets arriving at each of said input ports in predetermined memory locations in accordance with said routing tag signals; selecting among data packets that have entered the same input port and contend for the same output port; selecting among data packets that have entered different input ports that contend for the same output port; and applying said selected data packet to the output port identified in said routing tag signal.
Claim 14
Independent Claim
117 words
A method of processing applied data packets containing routing tag signals indicative of the output port destination to which said data packets are to be applied in order to route said data packets to the appropriate output ports, said method comprising the steps of: storing said data packets arriving at each of said input ports in predetermined memory locations in accordance with said routing tag signals; selecting among data packets that have entered the same input port and contend for the same output port; selecting among data packets that have entered different input ports that contend for the same output port; and applying said selected data packet to the output port identified in said routing tag signal.
Claim 15
Independent Claim
121 words
A method of processing applied data packets containing routing tag signals indicative of the output port destinations to which said data packets are to be applied in order to route said data packets to the appropriate output ports, said method comprising the steps of: sorting said data packets based upon the output port destination thereof contained in said routing tag signals; arbitrating among data packets which have entered the same input port and which are destined for the same output port; arbitrating among data packets that have entered different input ports and which are destined for the same output port; and routing the data packets selected during the two arbitration processes to said output ports identified in said routing tag signals.
Claim 16
Independent Claim
121 words
A method of processing applied data packets containing routing tag signals indicative of the output port destinations to which said data packets are to be applied in order to route said data packets to the appropriate output ports, said method comprising the steps of: sorting said data packets based upon the output port destination thereof contained in said routing tag signals; arbitrating among data packets which have entered the same input port and which are destined for the same output port; arbitrating among data packets that have entered different input ports and which are destined for the same output port; and routing the data packets selected during the two arbitration processes to said output ports identified in said routing tag signals.
Claim 17
Independent Claim
134 words
A method of processing applied data packets containing routing tag signals indicative of the output port destinations to which said data packets are to be applied in order to route said data packets to the appropriate output ports, said method comprising the steps of: storing said data packets in predetermined memory locations; sorting said data packets based upon the output port destination thereof contained in said routing tag signals; arbitrating among those data packets which have entered the same input port and which are destined for the same output port; arbitrating among those data packets that have entered different input ports and which are destined for the same output ports; and routing the data packets selected during the arbitration process from said memory locations to said output ports identified in said routing tag signals.
Claim 18
Independent Claim
134 words
A method of processing applied data packets containing routing tag signals indicative of the output port destinations to which said data packets are to be applied in order to route said data packets to the appropriate output ports, said method comprising the steps of: storing said data packets in predetermined memory locations; sorting said data packets based upon the output port destination thereof contained in said routing tag signals; arbitrating among those data packets which have entered the same input port and which are destined for the same output port; arbitrating among those data packets that have entered different input ports and which are destined for the same output ports; and routing the data packets selected during the arbitration process from said memory locations to said output ports identified in said routing tag signals.
References Cited (Backward Citations)
US3629846A
Cited
US3962706A
Cited
US4145733A
Cited
US4149240A
Cited
US4153932A
Cited
FR2305907A1
Cited
US3979733A
Cited
US4074233A
Cited
US4128882A
Cited
US4130885A
Cited
US4201890A
Cited
US4229790A
Cited
EP0014152A1
Cited
EP0020255A1
Cited
US4365292A
Cited
US4314233A
Cited
US4450554A
Cited
WO1984001077A1
Cited
JPS59135953A
Cited
FR2549673A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1989-12-15 | 1990-06-16 | 1990-12-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1993-12-15 | 1994-06-16 | 1994-12-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1997-12-15 | 1998-06-16 | 1998-12-16 | $7700.00 | Window Closed / Lapsed |