US5361255A — Method and apparatus for a high speed asynchronou…

Claim 1

Independent Claim 199 words

Switching circuitry for asynchronous transfer mode switching of digital information packets between a plurality of inputs and a plurality of outputs, comprising: input buffers coupled to said plurality of inputs for receiving a plurality of packets therefrom, queuing packets from each input, and retaining a copy of first ones of said queued packets; a sorter coupled to said input buffers for receiving first ones of said queued packets, and ranking said packets responsive to addresses associated with said packets, said sorter ranking packets having the same associated address according to priority data associated with said packets, and further ranking packets having the same associated address and priority data according to age data associated with said packets, said age data being generated in dependence upon the number of times a packet fails to reach its addressed destination and being updated in the copy of unrouted packets stored in said input buffers; compare circuitry coupled to said sorter and receiving said ranked packets from said sorter and simultaneously passing more than one packet up to a maximum number of packets having identical addresses; and routing circuitry for routing the packets passed by said compare circuitry in response to the associated addresses.

Claim 2

Dependent Claim 199 words

Switching circuitry for asynchronous transfer mode switching of digital information packets between a plurality of inputs and a plurality of outputs, comprising: input buffers coupled to said plurality of inputs for receiving a plurality of packets therefrom, queuing packets from each input, and retaining a copy of first ones of said queued packets; a sorter coupled to said input buffers for receiving first ones of said queued packets, and ranking said packets responsive to addresses associated with said packets, said sorter ranking packets having the same associated address according to priority data associated with said packets, and further ranking packets having the same associated address and priority data according to age data associated with said packets, said age data being generated in dependence upon the number of times a packet fails to reach its addressed destination and being updated in the copy of unrouted packets stored in said input buffers; compare circuitry coupled to said sorter and receiving said ranked packets from said sorter and simultaneously passing more than one packet up to a maximum number of packets having identical addresses; and routing circuitry for routing the packets passed by said compare circuitry in response to the associated addresses.

Claim 3

Dependent Claim 28 words

The switching circuitry of claim 1 wherein said compare circuitry passes one of said ranked packets which are not adjacent to a higher ranked packet having identical addresses.

Claim 4

Dependent Claim 15 words

The switching circuitry of claim 1 wherein the number of simultaneously passed packets is selectable.

Claim 5

Dependent Claim 25 words

The switching circuitry of claim 1 wherein said routing circuitry includes circuitry for receiving packets passed by said compare circuitry and sequencing said passed packets.

Claim 6

Dependent Claim 19 words

The switching circuitry of claim 4, and further comprising a banyan topology routing circuit for routing said sequenced packets.

Claim 7

Dependent Claim 23 words

The switching circuitry of claim 1 wherein said router includes circuitry for passing up to a predetermined number of packets for each destination.

Claim 8

Dependent Claim 171 words

A switching circuit coupled to external communication lines comprising: input buffer circuits coupled to respective external communication lines for receiving and temporarily queuing packets from said external communication lines; a switch comprising multiple planes having a plurality of inputs coupled to said input buffer circuits for switching first ones of said queued packets from said input buffer circuits to outputs of the switch corresponding to address data associated with each packet, said address data including an age data, said switch operable to send an acknowledgment signal to a sending input buffer circuit responsive to a packet being received at one of said outputs, said input buffer circuits updating age data of respective packets when a corresponding acknowledgment signal is not received, said input buffer circuits further being operable to send a packet on one of said planes and re-send the packet on another of said planes if an acknowledgment signal is not received in a predetermined time; and output buffer circuits for coupling said switch outputs to respective external communication lines.

Claim 9

Dependent Claim 171 words

A switching circuit coupled to external communication lines comprising: input buffer circuits coupled to respective external communication lines for receiving and temporarily queuing packets from said external communication lines; a switch comprising multiple planes having a plurality of inputs coupled to said input buffer circuits for switching first ones of said queued packets from said input buffer circuits to outputs of the switch corresponding to address data associated with each packet, said address data including an age data, said switch operable to send an acknowledgment signal to a sending input buffer circuit responsive to a packet being received at one of said outputs, said input buffer circuits updating age data of respective packets when a corresponding acknowledgment signal is not received, said input buffer circuits further being operable to send a packet on one of said planes and re-send the packet on another of said planes if an acknowledgment signal is not received in a predetermined time; and output buffer circuits for coupling said switch outputs to respective external communication lines.

Claim 10

Dependent Claim 49 words

The switching circuitry of claim 7 wherein said one or more planes each comprise a plurality of switching elements interconnected such that each plane is capable of delivering packets from any of said inputs to any of said outputs, such that the throughput of said switching circuitry is enhanced.

Claim 11

Dependent Claim 46 words

The switching circuitry of claim 8 wherein each of said switching elements comprises a plurality of inputs and respective outputs, each switching element operable to transfer a packet from any of its inputs to any of its outputs responsive to an address associated with the packet.

Claim 12

Dependent Claim 46 words

The switching circuitry of claim 9 wherein ones of said switching elements are operable to simultaneously transfer a plurality of packets having the same address to a plurality of outputs associated with said same address in order to reduce the number of collisions in said switch.

Claim 13

Dependent Claim 14 words

The switching circuitry of claim 8 wherein said switching elements include collision resolution circuitry.

Claim 14

Dependent Claim 112 words

The switching circuitry of claim 11 wherein each of said switching elements comprises: a sorter for receiving first ones of said queued packets, sorting said packets responsive to address data associated therewith, and ranking said packets; a comparator receiving said ranked packets and invalidating certain packets from said sorter having identical address data such that only a predetermined number of packets having identical address data are simultaneously transferred; said invalidated packets being deleted, such that said switching element does not send an acknowledgment signal in response to said invalidated packets; and routing circuitry for routing packets from said comparator to outputs of said switching element responsive to said address data associated therewith.

Claim 15

Dependent Claim 24 words

The switching circuitry of claim 7 wherein said predetermined time comprises the time between the start of a switching cycle on two successive planes.

Claim 16

Dependent Claim 52 words

The switching circuitry of claim 7 wherein said input buffer circuits each comprises: queuing circuitry for storing packets; a memory for storing a next packet from said queuing circuitry to be output to said switch; and control circuitry for transferring a new packet to said memory responsive to receiving said acknowledgement signal.

Claim 17

Dependent Claim 28 words

The switching circuitry of claim 7 wherein said control circuitry is operable to switch the packet with the highest priority to said memory responsive to said acknowledgement signal.

Claim 18

Dependent Claim 31 words

The switching circuitry of claim 7 wherein said switch comprises two or more planes, and said circuitry for coupling to said switch outputs further comprises control circuitry for switching between planes.

Claim 19

Dependent Claim 32 words

The switching circuitry of claim 7 and further comprising circuitry for appending routing information, priority information and age information to incoming packets, and outputting said incoming packets to said input buffer circuits.

Claim 20

Dependent Claim 37 words

The switching circuitry of claim 17 wherein said routing information includes one or more addresses for routing the associated packet through the switch and one or more addresses for routing the acknowledgement signal to the input buffer.

Claim 21

Dependent Claim 36 words

The switching circuitry of claim 7 wherein said input buffer circuits comprise means for increasing the age indication of a packet which was sent and for which an acknowledgement is not received within a predetermined time.

Claim 22

Dependent Claim 36 words

The switching circuitry of claim 7 wherein said acknowledgement signal is transmitted through said switch through a path topologically identical to the path originally taken by the packet, from said output to said input buffer circuits.

Claim 23

Independent Claim 107 words

A method of switching digital information packets between a plurality of inputs and a plurality of outputs, comprising the steps of: receiving and queuing the packets; sorting first ones of the queued packets responsive to addresses associated with the packets by ranking packets having the same associated address according to priority data associated with the packets and further ranking packets having the same associated address and priority data according to age data associated with the packets; comparing the sorted packets and simultaneously passing more than one packet up to a maximum number of packets having identical addresses; and routing the passed packets responsive to the associated addresses.

Claim 24

Independent Claim 107 words

A method of switching digital information packets between a plurality of inputs and a plurality of outputs, comprising the steps of: receiving and queuing the packets; sorting first ones of the queued packets responsive to addresses associated with the packets by ranking packets having the same associated address according to priority data associated with the packets and further ranking packets having the same associated address and priority data according to age data associated with the packets; comparing the sorted packets and simultaneously passing more than one packet up to a maximum number of packets having identical addresses; and routing the passed packets responsive to the associated addresses.

Claim 25

Dependent Claim 28 words

The method of claim 21 wherein said sorting step comprises the step of ranking packets having the same associated address according to priority data associated with the packets.

Claim 26

Dependent Claim 27 words

The method of claim 21 wherein said comparing step comprises the step of passing those packets which are not adjacent to higher ranked packet having identical addresses.

Claim 27

Dependent Claim 28 words

The method of claim 21 wherein said comparing step comprises the step of comparing the sorted packets and passing a selectable number of packets having the same address.

Claim 28

Dependent Claim 24 words

The method of claim 21 wherein said routing step comprises the step of passing up to a predetermined number of packets for each destination.

Claim 29

Independent Claim 116 words

A method of switching packets between a plurality of inputs and a plurality of outputs comprising the steps of: queuing the packets in a plurality of input buffer circuits; assigning an age to the first queued packets; transferring the first queued packets simultaneously from the input buffer circuits through a switch having one or more planes in response to the age and addresses associated with the packets; sending an acknowledge signal to a sending input buffer circuit responsive to a packet being received at one of said outputs; updating the age of packets responsive to not receiving a corresponding acknowledge signal; and retransmitting packets for which an acknowledge signal is not received within a predetermined time.

Claim 30

Independent Claim 116 words

A method of switching packets between a plurality of inputs and a plurality of outputs comprising the steps of: queuing the packets in a plurality of input buffer circuits; assigning an age to the first queued packets; transferring the first queued packets simultaneously from the input buffer circuits through a switch having one or more planes in response to the age and addresses associated with the packets; sending an acknowledge signal to a sending input buffer circuit responsive to a packet being received at one of said outputs; updating the age of packets responsive to not receiving a corresponding acknowledge signal; and retransmitting packets for which an acknowledge signal is not received within a predetermined time.

Claim 31

Dependent Claim 55 words

The method of claim 26 wherein said transferring step comprises the step of switching packets over one or more switching planes each comprising a plurality of switching elements interconnected such that each plane is capable of delivering a packet from any input of said plurality of inputs to any output of said plurality of outputs.

Claim 32

Dependent Claim 59 words

The method of claim 27 wherein said transferring step comprises the step of alternately transferring packets over one or more planes each comprising a plurality of switching elements, wherein the switching elements are operable to simultaneously transfer a plurality of packets having identical addresses to a plurality of outputs associated with said same address in order to increase throughput.

Claim 33

Dependent Claim 79 words

The method of claim 27 wherein said step of transferring the packets through one or more planes each comprising a plurality of switching elements comprises the steps of: sorting the packets responsive to address information associated therewith at each switching element; comparing the sorted packets and passing only a predetermined number of packets having the same address; and routing the packets passed by said comparator to outputs of the switching elements responsive to the addresses associated with the packets.

Claim 34

Dependent Claim 45 words

The method of claim 26 wherein said retransmitting step comprises the step of retransferring a packet if an acknowledgement signal is not received in a predetermined time less than or equal to the time between the starts of the switching cycles of two successive planes.

Claim 35

Dependent Claim 53 words

The method of claim 26 wherein said storing step comprises the steps of: storing packets in a first memory; storing the next packet to be output from the input buffer circuit to said switch in a second memory; and transferring a new packet to said second memory responsive to receiving the acknowledge signal.

Claim 36

Dependent Claim 30 words

The method of claim 31 wherein said transfer step comprises the step of transferring a packet with the highest priority and longest time spent by said packet in a queue.

Claim 37

Dependent Claim 32 words

The method of claim 26 and further comprising the step of appending routing information, priority information and age information to incoming packets, and outputting said incoming packets to said input buffer circuits.

Claim 38

Dependent Claim 64 words

The method of claim 33 wherein said step of appending routing information comprises the step of appending addresses for routing the associated packet to an output of the switch and for routing the acknowledge signal from an output of the switch through a path topologically identical to the path originally taken by the packet to the input buffer from which the packet was sent.

Claim 39

Dependent Claim 49 words

The method of claim 26 wherein said storing step comprises the steps of: storing a first packet in a first memory; transmitting said first packet through a first plane; and if an acknowledge signal does not arrive for said first packet, retransmitting said first packet through a second plane.

Claim 40

Dependent Claim 72 words

The method of claim 26 wherein said storing step comprises the steps of: storing packets in a first memory; transmitting ones of said packets through a first plane; storing the next packet to be output from the input buffer circuit to said switch in a second memory; transferring said next packet from said second memory to a second plane in response to receiving the acknowledge signal for said ones of said packets.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1997-10-31	1998-05-02	1998-11-01	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2001-10-31	2002-05-02	2002-11-01	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2005-10-31	2006-05-02	2006-11-01	$7700.00	Window Closed / Lapsed

Method and apparatus for a high speed asynchronous transfer mode switch

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag