Buffer management system

In a general multipoint packet switching network having terminals transmitting data in the form of packets belonging to multiple channels over communication links through a packet switch array, and where the packet switches of the array have means for receiving incoming packets from input data links and memory arrays for temporarily storing said incoming packets for retransmitting said stored packets over output links, a management system for determining whether a packet should be stored, retransmitted, or discarded during an overload condition, said management system comprising:

• means for allocating a predetermined amount of memory in a memory array for the packets of each channel;
• means for identifying each incoming packet as either an excess packet or a nonexcess packet based on a comparison of the number of packets of the same channel as the incoming packet stored in the memory array and the amount of memory allocated to the packets of said channel in the memory array;
• control means for controlling the reading and writing of packets out of and into said memory array, said control means further comprising control slices, a control slice for each location in the memory array for storing packets, each control slice including information identifying;
• (a) whether a packet is stored in the memory location corresponding to said control slice;
• (b) whether a packet stored in the memory location corresponding to said control slice is an excess or nonexcess packet;
• (c) the memory location to which the control slice corresponds;
• and
• (d) the channel of the packet stored in the memory location corresponding to said control slice;
• said control means further comprising means controlling the reading and writing of packets out of and into said memory array in response to said information in said control slices, means for writing an incoming packet into said memory array if said memory array is not full whether or not the incoming packet is an excess or nonexcess packet, and means for writing an incoming nonexcess packet into said memory array when said memory array is full and at least one excess packet is in said memory array and for discarding said excess packet from said memory array.