Output buffered packet switch with a flexible buffer management scheme

An output-buffered packet switch with priority packet transmission and a flexible buffer management scheme is disclosed. The switch consists of a sorting network at the input, a nonblocking routing network at the output, and multiple modules of column-fill networks together with the storage elements connected in series to provide a novel buffer management scheme. Each module provides one dedicated buffer for each output port, except the last module where the storage is shared by all the outputs. The combination of dedicated and shared buffering gives high performance for a wide range of traffic conditions. The switch is expandable in the sense that its performance can be enhanced by simply adding more modules. The switch design is distributed and has self-routing capabilities, so it can operate at very high data rates. The output-buffered packet switch can be used to implement a centralized control for another packet switch of higher speed but same functionality.

FIELD OF INVENTION 
The present invention relates in general to packet switching systems, and 
more particularly to an output-buffered packet switch that has a plurality 
of inputs and outputs, implements a hybrid of shared and dedicated 
buffering, uses distributed architecture, provides priority transmission, 
guarantees packet sequence, is expandable, and can serve as a central 
control for a packet switch of higher speed. 
BACKGROUND OF THE INVENTION 
High performance packet switches that interconnect a plurality of input 
ports to a plurality of output ports are critical components in 
communication networks requiring high transmission speeds. These switches 
can be used to transfer packets carrying a variety of services such as 
video, image, voice, and data services. Because of the high transfer 
rates, these switches are typically implemented using highly distributed, 
self-routing interconnection networks. In order to ease hardware 
implementation, these switches usually operate in a time-slotted fashion 
where the time slot is equal to the transmission time of one packet. 
Packet switches traditionally incorporate buffers in order to deal with 
temporary surges in traffic. The placement of buffers in a packet switch 
strongly influences the packet loss, packet delay, and throughput 
performance. Packet switches having buffers at the switch input ("input 
buffered switches") and that transfer packets on a First-In-First-Out 
(FIFO) basis suffer from head-of-line blocking which results in reduced 
throughput performance (see J. Y. Hui and E. Arthurs, "A broadband packet 
switch for integrated transport," IEEE J. Select. Areas in Commun., vol. 
SAC-5, pp. 1264-1273, Dec. 1987). On the other hand, packet switches 
having buffers at the switch output ("output buffered switches") can 
achieve maximum throughput close to 100% (see Y. S. Yeh, M. G. Hluchyj and 
A. S. Acampora, "The Knockout switch: A simple, modular architecture for 
high-performance packet switching," IEEE J. Select. Areas Commun., 
vol.SAC-5, pp. 734-743, Oct. 1987). Since an output buffer must be able to 
accept simultaneous packet arrivals (up to the number of input lines for 
no packet loss), the switch interconnection fabric normally provides 
multiple, and up to N.sup.2, disjoint paths from its N inputs to its N 
outputs. As a result, a straightforward implementation of an 
output-buffered switch can lead to hardware complexity of up to N.sup.2 in 
the case where a hardware unit is dedicated to each path. 
In addition to the placement of buffers, buffer allocation is also an 
important consideration in packet switch design. When buffers are 
dedicated to packets destined to each output of a switch, a large buffer 
size is required to attain a low packet loss rate. At the other extreme, 
when buffers are completely shared by all the outputs, significant buffer 
reductions can be achieved under certain traffic conditions. Examples of 
shared-buffer switches with a centralized control can be found in the 
Prelude and Hitachi proposals (see M. Devault, J. Cochennec, and M. 
Servel, "The Prelude ATD experiment: assessments and future prospects," 
IEEE J. Select. Areas in Commun., vol.SAC-6, pp. 1528-1537, Dec. 1988 and 
H. Kuwuhara, N. Endo, M. Ogino, and T. Kozaki, "Shared buffer memory 
switch for an ATM exchange," Proc. ICC, Boston, MA, pp. 4.4.1-4.1.5, Jun, 
1989). An example of a packet switch with distributed control is the 
Starlite switch (see A. Huang and S. Knauer, "Starlite: A Wideband Digital 
Switch," Proc. GLOBECOM'84, Atlanta, GA, pp.121-125, Dec. 1984, and U.S. 
Pat. Nos. 4,516,238 and 4,542,497 (Huang et al)). Since a shared storage 
buffer can be accessed by any input and any output, some inputs that 
coincidentally send packets to a specific group of outputs can consume all 
of the buffer space, thereby preventing (or "locking out") other packets 
destined for other outputs to access the buffer space. This phenomenon in 
turn degrades the performance of the switch. In view of the lock-out 
problem, it is thus more desirable to allocate only a partial amount of 
the buffer space as a shared storage and dedicate parts of the remaining 
buffer space to each output. 
A variety of packet switches based on the combination of Batcher sorting 
and banyan routing networks have been proposed. One example is the 
Starlite switch discussed above, which is based on the Batcher sorting 
network, a trap network, and a banyan routing network. The Batcher network 
sorts the incoming packets according to the destination addresses (See K. 
Batcher, "Sorting Networks and their Applications," Proc. AFIPS, pp. 
307-314, 1968). The trap network identifies packets with repeated 
addresses and recirculates them to the input of the Batcher network. The 
packets that are not recirculated by the trap network are routed to the 
output ports in nonblocking fashion by a banyan network. Unfortunately, to 
achieve high performance, the size of the Batcher network needs to be a 
large multiple of the input lines. This increases the hardware complexity. 
The Starlite switch also suffers from the buffer lock-out problem 
discussed above because of its full buffer sharing configuration. The 
Sunshine switch disclosed in J. Giacopelli, M. Littlewood, and W. D. 
Sincoskie, "Sunshine: A high performance self-routing broadband packet 
switch architecture," Proc. ISS, Stockholm, Sweden, pp. 123-129, May 1990, 
and in U.S. Pat. No. 4,893,304 (Giacopelli, et al ), overcomes some of the 
difficulties of the Starlite switch through a combination of output 
queuing and packet recirculation. The trap network operation in the 
Starlite system is modified in the Sunshine system so that up to K packets 
can be transferred to each output buffer through K parallel banyan routing 
networks. The trap network recirculates those packets that cannot be 
transferred to the output buffers. 
An object of an aspect of this invention is to realize an exact 
implementation of an output-buffered packet switch that overcomes the 
complexity problems associated with implementations that use multiple 
disjoint paths through the use of multiple but shared interconnection 
paths, and that provides both shared and dedicated buffering, thus 
achieving buffer efficiency while avoiding the lockout problem. 
SUMMARY OF THE INVENTION 
According to an aspect of the present invention, there is provided an 
output-buffered packet switch implementing a novel buffer management 
scheme. The switch design is fully distributed and has self-routing 
capabilities, so it can achieve high transfer rates. The switch preserves 
the sequence of the packets flowing between each input-output pair. 
Priority transfer of packets can also be supported with almost no 
additional cost. 
The switch of the present invention provides output buffering without 
resorting to faster internal circuits, through the application of a 
column-fill operation. This operation guarantees that packet losses occur 
only from the shared buffer. This operation also prevents the lockout 
phenomenon that can occur in fully shared buffer switches. Each 
column-fill operation is implemented by an identical module, and the 
number of dedicated buffers is equal to the number of such modules. The 
buffer sharing operation is implemented by the same module, except that it 
can be of a different size. The size of the dedicated and shared buffers 
can be selected so that the switch packet loss rate can be kept within 
desired levels under a broad range of traffic conditions.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
With reference first to FIG. 1a, a description of the general operation of 
an output-buffered switch is provided. The switch receives a plurality of 
packets in an input column 10 and then routes the received packets via an 
interconnection fabric 20 to a two-dimensional array 30. The output queues 
are organized in the two-dimensional array 30 with B columns labelled from 
right to left, and N rows labelled from top to bottom (for concreteness, 
the figure shows the case for which N=8 and B=6). Each entry in the array 
can store exactly one packet. Each row represents an output queue with the 
number of columns equal to the depth of the queue, which is assumed to be 
of equal size B for all output queues. Thus, row i stores the packets that 
are destined for output port i. 
During each time slot, the interconnection fabric 20 accepts an input 
column of arriving packets 10 and places them in the array 30. The maximum 
number of packets in an input column need not be the same as the number of 
output ports N. For example, in multicast applications a packet arrival at 
an input line can be destined for several output ports. In this scenario 
these packets will have already been duplicated and will appear in the 
input column to the interconnection fabric zo. In the case where there is 
only one priority class and where packets are handled on a FIFO basis, 
each input packet is stored in the rightmost available column of the row 
corresponding to its destination output port. In the event that input 
packets cannot be placed in the array because the corresponding rows are 
full, these packets are temporarily held in the input column 10. The 
packets in the first column of array 30 (ie. j=1). are then transferred to 
the corresponding output ports. As packets in the first column j=1 are 
transferred out, all packets stored behind them (ie. j=2, 3, 4 . . . etc.) 
synchronously move to the right by one column. In the final step, packets 
in the input column 10 that have not already been placed in the array are 
offered to the newly vacated Bth column. Any packets that cannot be placed 
in column B are lost. The switch is then ready to receive packets in the 
next time slot. 
According to the present invention it has been recognized that since the 
output addresses of the packets stored in each column of array 30 are not 
repeated and since an arriving packet is offered to a given column before 
being offered to any other column to its left, it can be concluded that at 
all time slots the number of packets in any given column is greater than 
or equal to the number of packets in the column to its immediate left. In 
fact, if a given column contains a packet destined for a particular 
output, then every column to its right must also contain a packet destined 
for the same output. 
Therefore according to an important aspect of the present invention the 
placement of packets from the input column 10 into the array 30 is 
implemented by multiple applications of the following column-fill 
operation, with reference to the illustrative example shown schematically 
in FIG. 1a. Step 1: Route the packets from input column 10 to the empty 
entries in the first column (j=1) of array 30, if the input column 10 
contains packets with the appropriate addresses. If there is more than one 
packet with an address corresponding to an empty entry, select only one of 
the packets to fill the entry. Step 2: The packets in the input column 
that were not placed in the first column (j=1) are routed to the second 
column (j=2) array 30 using the same procedure as in Step 1. The process 
of placing packets from the input column 10 in each successive array 
column is continued until all packets have been placed, or until the last 
or left-most column B in array 30 is reached. The last column-fill 
operation takes place after the columns in the array have been shifted to 
the right. Packets that cannot be placed in the last column B are lost. 
Therefore, according to the present invention the process of placing input 
packets in an output buffered switch is implemented by a series of 
column-fill operations. 
The column-fill operation needs to be modified in the case where there are 
several classes of priority service. Each time an input column is offered 
(i.e. routed) to the array, an input packet with a given destination 
address is placed in the rightmost entry in the corresponding row not 
already occupied by a packet of equal or higher priority. Any displaced 
lower priority packet and all packets to its left, if any, are then 
shifted to the left by one column in the same row. In terms of the 
column-fill operation, each time that an input column is offered to an 
array column, an entry in the array column is filled with an input packet 
that has a destination address corresponding to the entry, that has a 
priority higher than that of the packet currently in the array column, and 
that has priority higher than that of any other input packet with the same 
destination address. When a higher priority packet from the input column 
displaces a lower priority packet in the array column, the displaced lower 
priority packet is placed in the input column. In order for the displaced 
packet to be able to subsequently push back those packets that were to its 
left in its output queue, the system of the present invention provides 
that an ageing field be incorporated into the packet header. 
Before describing a generalized embodiment for realizing the column-fill 
operation discussed above with reference to FIG. 1a, it is necessary to 
consider the packet header structure. The packet header, shown in FIG. 2, 
consists of a split bit, an activity bit, an address field, a priority 
field, and an age field. The split bit is normally set to zero, except 
briefly during part of the column-fill operation. The activity bit is used 
to determine whether an entry contains a packet (represented by a zero 
bit) or is empty (represented by a one bit). The address field contains 
the address of the output to which the packet is destined. For a switch 
fabric with N output ports, the address field requires n= log.sub.2 N 
bits. The priority field is optional and can be used to divide the 
arriving packets into several service classes. Packets having priority 
value i will be referred to herein as class-i packets. Class 0 has the 
highest priority, class 1 has the second highest priority, etc. The age 
field is used to maintain sequence within each priority class for each 
input-output port pair. This is done by giving packets that have stayed in 
the switch fabric for t time slots, t levels lower in the age value over 
the new packets belonging to the same input-output pair. The binary number 
determined by the packet header, with the split bit as the most 
significant bit, can be interpreted as defining a larger set of priority 
classes. With this interpretation, empty packets normally constitute the 
lowest priority class. 
The generalized embodiment of the column-fill network according to the 
present invention for effecting the column-fill operation described above, 
is shown in FIG. 3. The column-fill network 50 is composed of a sort 
network 60, a trap network 70, a sort network 80, a routing network 90, 
and a delay circuit 96. The column-fill network 50 operates on two columns 
of packets a.sub.1, a.sub.2, . . . , a.sub.N and b.sub.1, b.sub.2, . . . , 
b.sub.K. The packets a.sub.1, a.sub.2, . . . , a.sub.N and b.sub.1, 
b.sub.2, . . . , b.sub.K enter the network simultaneously, and the packets 
f.sub.1, f.sub.2, . . . , f.sub.N and g.sub.1, g.sub.2, . . . , g.sub.K 
exit the network simultaneously after a fixed latency time T.sub.L sec. 
Packet a.sub.m corresponds to the nth entry of a column in array 30 (FIG. 
1a), and b.sub.k corresponds to the kth entry in an input column. The two 
columns may contain empty entries. In this case, an empty entry is 
represented by a packet with the activity bit set to one. Column f.sub.1, 
f.sub.2, . . . , f.sub.N corresponds to the array column after the 
column-fill operation has been carried out. Therefore, f.sub.n is equal to 
a.sub.n unless a higher-priority packet with destination n is found in the 
input column. If one or more such higher priority packets are found, then 
f.sub.n is equal to the input packet that has a destination address 
corresponding to the entry and has priority higher than that of any other 
input packet with the same destination address. When a higher priority 
packet from the input column displaces a lower priority packet in the 
array column, the displaced lower priority packet is placed in the input 
column. In the discussion above empty packets are treated as belonging to 
the lowest priority class. The packets in g.sub.1, g.sub.2, . . . , 
g.sub.K consist of all the packets in a.sub.1, a.sub.2, . . . , a.sub.N 
and b.sub.1, b.sub.2, . . . , b.sub.K that do not appear in f.sub.1, 
f.sub.2, . . . , f.sub.N , and their order of appearance does not matter. 
The sort network 60 receives the packets a.sub.1, a.sub.2, . . . , a.sub.N 
and b.sub.1, b.sub.2, . . . , b.sub.K and sorts them in ascending order 
according to the split bit (which is set to zero), activity bit, 
destination address bits, priority bits, and age bits to produce the 
packets c.sub.1, c.sub.2, . . . , c.sub.N+K in FIG. 3. Active packets 
appear in the first part of c.sub.1, c.sub.2, . . . , c.sub.N+K and empty 
packets appear in the latter part. Within the active packets, packets are 
ordered according to destination, and for each destination according to 
priority and age. 
Among the packets destined for output port n, the trap network 70 selects 
the packet of highest priority, and if there is more than one such packet, 
it picks the packet having the lowest age value. The first packet in the 
sequence c.sub.1, c.sub.2, . . . , c.sub.N+K with destination address n 
satisfies the condition for selection. The trap network identifies the 
first appearance of an address through an address comparator circuit 71 
that compares the destination fields in the headers of adjacent packets in 
the sequence c.sub.1, c.sub.2, . . . , c.sub.N+K, and it modifies the 
split bit according to the result of the comparison to produce the packets 
d.sub.1, d.sub.2, . . . , d.sub.N+K. There is no comparator circuit 
associated with c.sub.1 but a delay circuit 72 is inserted to compensate 
for the delay introduced in the other comparator circuits 71. The 
comparator circuit with inputs c.sub.j and c.sub.j+1 is defined as being 
associated with packet c.sub.j+1. When a comparator circuit 71 identifies 
that the two addresses are the same, the split bit of the packet 
associated with the comparator is set to one, the activity bit is left at 
"0", and each bit in the destination, priority, and age fields is 
complemented. Thus the header field of such packets begin with the bits 
"10". When the comparator circuit determines that the two addresses are 
different, the associated packet is identified as the first occurrence of 
a particular destination address in the sequence c.sub.1, c.sub.2, . . . , 
c.sub.N+K, the split bit is left at zero, and all other header bits are 
left unchanged. Thus the header field of such packets begin with the bits 
"00". The split bit in empty packets is left at zero, so their header 
fields begin with the bits "01". 
The sort network 80 in FIG. 3 sorts the packets d.sub.1, d.sub.2, . . . , 
d.sub.N+K in ascending order according to split bit, activity bit, 
destination address bits, priority bits, and age bits. At the output of 
the sort network 80, the split bits of all packets are reset to zero, and 
the bits of the destination, priority, and age fields of all packets 
exiting the lower K outputs of the sorter, which include all the packets 
which previously had a split bit=1, are complemented in order to recover 
the original destination addresses. In the sequence e.sub.1, e.sub.2, . . 
. , e.sub.N+K, packets that entered the sort network 80 with the prefix 
"00" appear first in increasing order of destination address, followed by 
the empty packets that entered the network 80 with the prefix "01", 
followed finally by packets that entered the network 80 with the prefix 
"10", in decreasing order of destination address. Therefore the sequence 
e.sub.1, e.sub.2, . . . , e.sub. N+K forms a circular bitonic list, as 
described in J. Y. Hui, "Switching and Traffic Theory for Integrated 
Broadband Networks" Kluwer Academic Publishers, Boston, 1990. Thus the 
packets that are to be stored in the array column appear in the upper 
portion of e.sub.1, . . . , e.sub.N. Packets that are to be placed in the 
input column appear in the lower portion of e.sub.N+1, e.sub.N+2, . . . , 
e.sub.N+K. 
A non-blocking routing network 90 takes the packets e.sub.1, e.sub.2, . . . 
, e.sub.N and routes them to the appropriate outputs f.sub.1, f.sub.2, . . 
. , f.sub.N specified by the destination address field of each packet. 
The packets e.sub.N+1, e.sub.N+2, . . . , e.sub.N+K are transferred through 
a delay circuit 96 directly to the outputs g.sub.1, g.sub.2, . . . , 
g.sub.K. The delays in the circuit are designed so that packets f.sub.1, 
f.sub.2, . . . , f.sub.N and g.sub.1, g.sub.2, . . . , g.sub.K appear 
simultaneously at the output of the column-fill network 50. 
The packets in e.sub.1, e.sub.2, . . . , e.sub.N are ordered according to 
destination address and all empty packets appear in the later portion of 
the sequence. The packets can therefore be routed in non-blocking fashion 
by the banyan routing network of the type shown in FIG. 4. 
The sort networks 60 and 80 can be implemented using (N+K).times.(N+K) 
Batcher network (see K. Batcher, "Sorting Networks and their 
Applications," Proc. AFIPS, pp. 307-314, 1968, and U.S. Pat. No. 3,428,946 
(Batcher)). 
The description to this point completes the implementation of the 
generalized column-fill network according to the present invention. 
The column-fill network 50 developed above can be simplified significantly 
as described below. Firstly, it may be appreciated that the routing 
network 90 is only required when the column-fill operation involves the 
first column. If the first column j=1 is not involved, then it is not yet 
necessary to route the packets to their corresponding destination 
addresses. Therefore the routing network 90 and the delay circuit 96 can 
be removed. If this is done, then in subsequent column-fill networks, the 
array column a.sub.1, a.sub.2, . . . , a.sub.N and the input column 
b.sub.1, . . . , b.sub.K will form a circular bitonic list. It is 
well-known that a circular bitonic list can be sorted by a banyan network 
for which the nodes are 2.times.2 sorters (see J. Y. Hui, "Switching and 
Traffic Theory for Integrated Broadband Networks" Kluwer Academic 
Publishers, Boston, 1990, page 148). The sort network 60 in FIG. 3 can 
therefore be replaced by such a banyan network. When the column-fill 
network 50 is implemented with the sort network 60 using a banyan sorter, 
and without the routing network 90 and the delay circuit 96, the resulting 
simplified column-fill will be henceforth called the "streamlined 
column-fill network." 
An alternative implementation of the streamlined column-fill network is as 
follows. 
The trap network 70 and the sort network 80 in FIG. 3 can also be 
simplified by replacing them with a modified trap network, a running adder 
network (see the Huang reference cited above), and a reverse banyan 
network. The modified trap network performs as above except that the bit 
complement operation is omitted. The running adder network uses the 
results of the comparator circuits to steer the selected packets to 
e.sub.1, . . . , e.sub.N, and to steer the remaining packets to e.sub.N+1, 
. . . , e.sub.N+K. The packets will appear in the same order as in the 
above streamlined column-fill networks. 
FIG. 5 is a block diagram of the packet switch according to the preferred 
embodiment of the present invention. The switch comprises a pre-sorting 
network 200, a nonblocking routing network 400, B-1 identical modules 
300.sub.-- 1 to 300.sub.-- B-1 each consisting of a delay element 
350.sub.-- 1 to 350.sub.-- B-1 and a column-fill network 310.sub.-- 1 to 
310.sub.-- B-1 and one module 300.sub.-- B consisting of a delay element 
350.sub.-- B and a column-fill network 310.sub.-- B that implements buffer 
sharing. Illustratively, the delay elements can be implemented using shift 
registers. Alternative embodiments may use RAM devices or FIFO buffers. 
The switch in FIG. 5 implements the column-fill operations described in the 
previous section in pipelined and distributed fashion. The presorting 
network 200 and the routing network 400 are used only when the streamlined 
column-fill network is adopted. When streamlined column-fill networks are 
not used, the switch operates in the following way. At the beginning of 
each time slot, the switch accepts up to K packets from its input lines. 
These packets correspond to an input column 10 in FIG. 1. This input 
column is offered to column 1 of array 30 in FIG. 1 which corresponds to 
delay element 350.sub.-- 1 in FIG. 5. The column-fill operation is carried 
out and after a latency of T.sub.L seconds the packets selected for 
transmission to the output ports appear at output O.sub.11. At the same 
time, the remaining packets appear at output O.sub.21 for another 
column-fill operation with the next module 300.sub.-- 2. Each time a 
packet enters a delay element its age field is decremented by one, unless 
the age field is already zero. The process is continued until module 
300.sub.-- B-1 which offers the remaining input packets to the last 
module. 
The last module 300.sub.-- B in FlG. 5 for each destination selects the 
highest priority packets from both inputs I.sub.1B and I.sub.2B, and then 
forwards them to the (B-1)th module. The remaining packets are 
recirculated through its delay element for contention in the next time 
slot. Any excess packets that cannot be accommodated in the last module 
will be dropped. 
Packets are dropped in the following way. FIG. 6 shows that the shared 
buffer module can differ from a column-fill module in that the size of the 
input column and array column are not necessarily the same as those at the 
output. The sort network 60, sorts the packets a.sub.1 ', a.sub.2 ', . . 
., a.sub.M ' and b.sub.1 ', b.sub.2 ', . . . , b.sub.K ' in ascending 
order according to split bit (which is set to zero), activity bit, 
destination address bits, priority bits, and age bits to produce the 
packets c.sub.1 ', c.sub.2 ', . . . , c.sub.M+K '. The trap network 70' 
operates in the same manner as trap network 70 in FIG. 3. The Sort network 
80' operates as follows: first the packets d.sub.1 ', d.sub.2 ', . . . , 
d.sub.M+K ' are sorted to produce a circular bitonic list of packets 
e.sub.1 ', e.sub.2 ', . . . , e.sub.N, e.sub.N+1, . . . e.sub.M+K ' in 
which packets with the prefix 00 appear first in increasing order of 
destination address, followed by the empty packets with the prefix 01, 
followed finally by packets with the prefix 10, in decreasing order of 
original destination address. It is possible for packets with index 10 to 
appear in the lower part of e.sub.1 ', e.sub.2 ', . . . , e.sub.N ' which 
in the normal column-fill network would be transferred to the delay 
element. The remove stage 85, replaces all packets with split bit equal to 
one with empty packets, and forwards these packets to a banyan routing 
network 90'. This requires changing the split bit to zero and the activity 
bit to one. Packets with the prefix 10 that are replaced by empty packets 
are lost. The packets f.sub.1 ', f.sub.2 ', . . . , f.sub.N ' are then 
forwarded to column-fill network B-1. The complement stage 86' sets the 
split bit to zero, and complements the destination, priority, and age 
fields to recover the original destination addresses, and forwards the 
packets to the delay circuit 96'. The resulting packets g.sub.1 ', g.sub.2 
', . . . , g.sub.M+K-N ' form the array column that constitutes the shared 
buffer because packets may have repeated addresses. When K=N all the lines 
from the delay circuit 96' are connected to the input of module B. When K 
is greater than N, packets g.sub.1 ', . . . ,g.sub.K-N ' in FIG. 6 are 
lost, and packets g.sub.K-N+1 ', g.sub.K-N+2 ' . . . , g.sub.M+K-N ' are 
recirculated back to the input a.sub.M ', a.sub.M-1 ', . . . , a.sub.1 ' 
of sort network 60'. Note that the bottom output line from delay network 
96' is connected to the top input line of sort network 60'. When K is less 
than N packets g.sub.M+K-N ', . . . , g.sub.1 ' in FIG. 6 are recirculated 
back to inputs a.sub.1 ', . . . , a.sub.M+K-N ' of sort network 60', and 
empty packets are input into a.sub.M+K-N+1 ', . . . , a.sub.M '. 
Since a fixed delay, say T.sub.L, is incurred traversing a module, the time 
slots among the modules have to be staggered. FIG. 7 shows the space-time 
diagram of the staggered operation of the switching modules. 
The switch according to the preferred embodiment of FIG. 5 implements the 
required column-fill operation during the first B-1 modules, thus 
implementing an output buffered switch with B-1 buffers dedicated to each 
output port. The last module implements buffer sharing. 
When the switch in FIG. 5 uses streamlined column-fill networks, the 
presorting network 200 and the routing network 400 are required. The 
presorting network accepts K incoming packets and sorts them in ascending 
order based on the packet header values. In order to present a circular 
bitonic list to the first streamlined column-fill network, it is necessary 
to connect the outputs of the presorting network 200 to inputs of the 
streamlined column-fill I.sub.21 in reverse order. The streamlined 
column-fill networks then operate as desired in modules 1 up to B-1. The 
output packets from O.sub.11 in the first module are routed to their 
appropriate destination output ports by the routing network 400. This 
routing network can be implemented using a banyan routing network. When 
streamlined column-fill networks are used, the shared buffer module B can 
also be simplified. The routing network 90' and the delay circuit 96' in 
FIG. 6 can be omitted. The resulting outputs are connected to module B-1 
and to the input of module B in the same manner as above. The inputs to 
the column-fill network in module B now form a circular bitonic list so 
sort network 60' can be replaced by a banyan sorting network. When using 
streamlined column-fill networks packets are stored in the delay elements 
in FIG. 5 as shown in FIG. 1b. 
The trap network 70' and the sort network 80' in FIG. 6 can also be 
simplified by replacing them with a modified trap network, a running adder 
network and a reverse banyan network. The modified trap network performs 
as above except that the bit complement operation is omitted. The running 
adder network uses the results of the comparator circuits to produce the 
circular bitonic list e.sub.1 ', e.sub.2 ', . . . , e.sub.N ', e.sub.N+1 
', . . . e.sub.M+K '. The remove stage 85' replaces all packets with split 
bit equal to one with empty packets. The complement stage 86' is not 
required. 
A switch is said to maintain packet sequence if packets belonging to each 
input-output port combination and within the same priority class exit the 
switch in the same order as they enter, except for possible "gaps" at the 
output due to packet loss. To see how packet sequence is maintained within 
the same priority class, one may consider the situation where an input 
packet destined for a particular output enters the first module 300.sub.-- 
1 in FIG. 5. If there is a packet destined for the same output in the 
delay element of the first module, then the sort network 60 in FIG. 3 will 
place the packet from the delay element 350.sub.-- 1 in FIG. 5 on a higher 
output line than the input packet. This is because the packet from the 
delay element has a lower age value (i.e. has been present in the switch 
longer). Whenever the outputs of the sort network 60 in FlG. 3 contain 
duplicates, the column-fill network 310.sub.-- 1 in FIG. 5 sends the 
packet located at the highest line to O.sub.11, and the rest to O.sub.21. 
In this example, the (old) packet from the delay element 350.sub.-- 1 will 
be transmitted to the routing network 400 if any while the other (new) 
packet will be sent to the second module 300.sub.-- 2 to undergo another 
column-fill process. If there is another packet with the same output 
address found in the second module, that packet will be forwarded to the 
first module 300.sub.-- 1 while the new packet will be forwarded to the 
third module 300.sub.-- 3. Hence, this new packet must wait until all 
previous packets with the same address have exited the switch before it 
can be transmitted out. Therefore, packet sequencing is guaranteed as long 
as the age value does not reach zero. 
The basic switch architecture of the preferred embodiment shown in FIG. 5 
consists of multiple identical modules connected in series. One 
contemplated alternative embodiment of the invention utilizes only one 
column-fill network 800 and uses time sharing as shown in FIG. 8. The 
presorter 200 and the routing network 400 still run at the same speed as 
the external clock rate, consistent with the preferred embodiment of FIG. 
5. However, the column-fill network 800 is adapted to run B times faster 
than any one of the networks 310.sub.-- 1 to 310.sub.-- B in the preferred 
embodiment, where B is the depth of the buffer module. A buffer module 801 
is used to store the results of successive column-fill operations as 
performed by successive ones of the modules 300.sub.-- 1 to 300.sub.-- B 
in the embodiment of FIG. 5. A holding buffer 802 is used to temporarily 
hold residual input packets for processing in the column-fill network 800 
(ie. corresponding to the packets applied to the inputs I.sub.22 to 
I.sub.2B in the preferred embodiment). In the embodiment shown, it is 
assumed that the shared memory delay element (the rightmost element in 
801) and holding buffer 802 are also of size N. 
Suppose the duration of a time slot at the external rate is T sec. Then at 
the beginning of every time slot, S.sub.1 connects to its upper pole for 
T/B seconds. Note that the rate adaptation circuit 803 is necessary to 
provide rate matching between the external rate and the column-fill 
network rate. At this point S.sub.2 is in the position such that the 
packets in the leftmost element 801 with unique addresses will be sent to 
the routing network (as shown in FIG. 8). During the next T-T/B sec., 
S.sub.1 connects to the lower pole. S.sub.2 slides to the next storage 
element on the right, each for T/B sec. The column-fill operation is 
executed at this phase. At the end of a time slot, S.sub.1 moves back the 
upper pole, S.sub.2 returns to the far left, and the whole process 
repeats. 
As an alternative time sharing of a single column-fill network 800, when 
the column-fill network operates at B/n times faster then n synchronized 
column-fill networks may be used. 
In traditional stored program control telephone switching the switch fabric 
control and the information transfer parts are separate. A central control 
sets the connections required to effect the flow of information from the 
input of the switch to the output. The packet switch architecture 
presented above does not follow this approach in that the control add 
transfer are realized by the same hardware. This involves inefficient use 
of resources much like in-band signalling is inefficient relative to 
out-of-band signalling in telephone networks. According to a further 
embodiment of the invention, a packet switch is provided which separates 
the control and packet transfer functions. 
FIG. 9 shows a packet switch architecture with centralized control 500. 
Packets that arrive from the switch interface are stored in memory 600. 
Henceforth, such packets will be referred to as full packets. The memory 
location of a full packet is appended to a replica of its header to create 
a new minipacket. An input column consisting of minipackets is offered to 
central control 500 which consists of the packet switch with the preferred 
architecture shown in FIG. 5. The output of the central control 500 is a 
column of minipackets specifying the locations of the full packets that 
are to be transmitted at a given time slot. These output columns of 
minipackets are used to control the reading out of packets to the output 
of the packet switch by memory controller 530. In order to operate 
synchronously with the input packets, the central control needs to produce 
one output column per full packet transmission time, i.e. one time slot. 
If R is the ratio of the number of bits in a full-packet to those in a 
minipacket, then the packet switch 510 (see FlG. 10) inside the central 
control 500 can operate R times slower than the switch input line speed. 
FIG. 10 shows a possible embodiment of the memory structure 600. Incoming 
full packets on K input lines are first shifted into the shift registers 
610. Each shift register 610 stores one full packet. The input full 
packets are written to a central random access memory 620 sequentially one 
at a time, and the corresponding address location is produced on line 630 
and copies to the minipacket corresponding to that line. This particular 
embodiment requires that full packets are offered to the memory input in 
staggered fashion, with each packet being staggered by the full packet 
length divided by K. During each time slot, the central control 500 
produces a column of minipackets via minipacket generator 520 that are 
used to select the address of the memory locations of the full packets 
that are to be read out. The memory controller 530 supplies the locations 
to the RAM 620 so that the full packets can be retrieved and read out one 
packet at a time. The packets are read out in staggered fashion to an 
output interface comprising shift registers 615, which aligns the packets 
for synchronous transmission if necessary. 
Other alternative embodiments and variations of the invention are possible 
within the sphere and scope of the claims appended hereto.