Asynchronous time division multiplex switching system

#1. Field of the Invention

#The invention relates to an asynchronous time division multiplex (ATDM) switching system.

#2. Description of Related Art

#The invention will now be further described by way of example with reference to the accompanying drawings in which:

#FIG. 1 and 1A show a `Linked List` structure implementing four first in/first out queues during a sequence of packet arrivals and departures;

#FIG. 2, 2A and 3 show results from simulations of the ATDM switching system which illustrate how a discarded packet at the head of the longest queue in order to accommodate an incoming packet can significantly reduce packet losses;

#FIG. 1 and 1A illustrate the changing structure of this `linked list` queuing system during a typical sequence of packet arrivals and departures. Four separate queues, labeled A, B, C & D are implemented. The rectangular boxes represent the following physical areas of storage: "Data" is an 8 RAM (Random Access Memory) where each word can hold one packet of information, Pointers is an 8 word RAM where each word holds a 3 bit value that refers to the addresses alongside the `Data` RAM, `Head` is a file of 5.times.3 bit registers that holds the RAM address of the element at the head of each queue (including the `Free List` ), `Tail` is a file of 5.times.3 bit registers that holds the RAM address of the element at the tail of each queue, `Count` is a file of 5.times.4 counters that holds the number of elements in each queue and `Longest Queue` is a 2 bit register that indicates which of the four data queues is currently the longest. In addition, each stage of the diagram also includes a pictorial representation of the queues in existence at that point in time. The symbol `X` is used wherever the actual contents of a RAM location or register is irrelevant.

#FIGS. 2, 2A show the results obtained by a Pascal simulation of the switching system described here. Two versions of the algorithm used to handle the queuing of packets were tested. In algorithm 1, when the memory is full, incoming packets are simply discarded, whilst with algorithm 2 they are accommodated by sacrificing the element at the head of the longest queue. The distribution of traffic across the queues is given by traffic density ratios which specify the relative amount of traffic going to each output. For example, in the case of FIG. 2A, for every 16 packets that are destined for output port 0, there will be 17 for port 1, 18 for port 2 and so on up to port 15 which will receive 31. The `total occupancy` value specifies what percentage of the input packets are valid, leaving the rest to be marked in their header field as invalid (i.e. empty). From FIG. 2A it can be seen that, whilst losses from the busiest queue (port 15) are largely unaffected by the choice of algorithm, those from queues with less traffic are drastically reduced to the extent that the overall loss of data is cut by over 64%. FIG. 3 shows that this improvement applies to evenly distributed traffic as well and that it is consistent over a whole range of levels of occupancy. Whilst it is to be expected that the emptier queues lose less data (after all, only the longer and hence busier queues get overwritten), it is not immediately apparent why the busier queues are not affected adversely. The explanation relies on the fact that, during any given period when a packet arrives, the memory will only fill up if another packet does not leave, a situation which only arises when the queue for the currently selected output port is empty. The queues most likely to become empty will be the shortest ones and, by ensuring that these never lose data, the risk of them emptying, and consequently, that of the memory filling, is reduced. As long as the memory does not fill up, no packets are lost from any queue, and so, in the long term, sacrificing data on busier channels is of benefit, not just to traffic in the smaller queues, but to the whole system.

#FIG. 4 illustrates the top level architecture of the ATDM switching system. The main components are a 16 input.times.160 bit serial to parallel converter 100, two blocks of 256.times.160 bit Random Access Memory (RAM) 101 & 102 that are used to store separate halves of data packets in First In/First Out queues associated with each of the switch's output lines, a 256.times.8 bit RAM 103 that holds, for each corresponding location in the `data` RAMs, the address of the next location in the associated queue, a queue processor 104, a 16 output.times.160 bit parallel to serial converter 105 and a 4 bit counter 106 that is used to cycle through the input ports.