Packet switching network

• US 4,891,803 A
• Filed: 11/07/1988
• Issued: 01/02/1990
• Est. Priority Date: 11/07/1988
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.), Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: American Telephone & Telegraph Company (AT&T, Inc.), AT&T, Inc.
• Inventors: Lin, Sheng L., Ransom, Maurice N., Rutledge, Charles W., Huang, Alan, O'Neill, Jay H., Spanke, Ronald A., Knauer, Scott C.
• Primary Examiner(s): Safourek, Benedict V.
• Assistant Examiner(s): Marcelo, Melvin
• Application Number:
  US07/267,606
• Time in Patent Office: 421 Days
• Field of Search: 370/60, 370/61, 370/94, 370/56
• US Class Current: 370/411
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 49/106 using space switching, e.g. crossbar or matrix
• CPC Class Codes: H04L 49/1553 Interconnection of ATM switching modules, e.g. ATM switching fabrics
• CPC Class Codes: H04L 49/1561 Distribute and route fabrics, e.g. Batcher-Banyan

Abstract

A packet switching network that accommodates the appearance of multiple occurrences of packets addressed to the same destination are accommodated. The network includes a recirculating delay block within the switch, and an expander that includes a modest number of multiple appearances of the same address, followed by memories that accept the packets delivered at those multiple appearances, store the packets, and output the stored packets to the user, one at a time, in accordance with a set priority scheme.

Claims

1. A network for routing packets that contain a destination designation and a priority designation comprising:

a sorter responsive to applied signal packets, for developing a sorted set of packets;

a merge network responsive to said sorted set of packets and to a delayed set of packets;

a trap network responsive to output signals of said merge network (a) for identifying packets sets S(A), with a common destination designation where S designates the set of packets and a designates the address, and (b) for separating each of said packet sets, S(A), into a first subset, S1(A), and a second subset, S2(A), such that the number of packets in said second subset, S2(A), is zero as long as the number of packets in said first subset, S1(A), is less than a preselected number N and the priority designation of packets in said first subset, S1(A), is not lower than the priority designation of packets in said second subset, S2(A);

a delay network responsive to outputs of said trap network, for developing said delayed set of packets;

an expander network having N of appearances of each destination address responsive to output signals of said trap network, for routing packets of said first subsets in accordance with destination addresses of routed packets; and

a plurality of memory means, each having an output and N inputs connected to said appearance of a chosen destination at the output of said expander, for delivering packets to said output.

2. The network of claim 1 where said trap network (a) identifies packets sets with a common destination designation, (b) separates each of said packet sets into said first subset and said second subset, and (c) groups packets of said second subsets at the output of said trap network.

3. The network of claim 1 where said trap network comprises means for adding a tag designation to packets that are destined to said delay network to form tagged packets.

4. The network of claim 3 where said trap network further includes means for sorting tagged packets by priority.

5. The network of claim 4 where said trap network further includes means for identifying a chosen number of highest priority packets among the sorted tagged packets and means for sorting said chosen number of highest priority packets by destination.

6. The network of claim 4 where said delay network comprises:

means for accepting a chosen number of highest priority packets among the sorted tagged packets; and

means for sorting said chosen number of highest priority packets by destination.

7. The network of claim 1 where

said delay means includes means for identifying a selected portion of said packets passing through said delay means as a time-stamp field, and for altering the contents of said time-stamp field to indicate passage of said packets passing through said delay means;

and

said trap network combines priority and time-stamp fields in determining said separating each of said packet sets into a first subset and a second subset.

8. The network of claim 1 wherein each of said memory means delivers packets to its output by order of priority of packets provided to said memory means.

9. A communications switch for switching variable precedence input data messages to respective ones of a plurality of destinations, comprising:

means for aggregating currently received messages with previously received messages that have not been forwarded to their respective destinations, to form a set of aggregated messages;

means for selecting, for each destination, the N messages having the highest precedence from among the aggregated messages having said each destination, where N is a preselected number greater than 1;

means for storing the T highest precedence messages from among the aggregated messages not selected by said means for selecting, where T is another preselected number, thereby making the stored messages available for later aggregating by said means for aggregating; and

means for transmitting the selected messages to respective destinations in order of precedence.