WO2007034407A1

WO2007034407A1 - Packet dropping at the input queues of a switch-on-chip

Info

Publication number: WO2007034407A1
Application number: PCT/IB2006/053360
Authority: WO
Inventors: Theodorus J. J. Denteneer; Ronald Rietman; Santiago Gonzalez Pestana; Paul Beekhuizen
Original assignee: Koninklijke Philips Electronics NV
Current assignee: Koninklijke Philips NV
Priority date: 2005-09-26
Filing date: 2006-09-19
Publication date: 2007-03-29
Anticipated expiration: 2008-03-26

Abstract

Packets with data are transmitted between sub-circuits (12) of a circuit (10) via a network (16) that contains a router circuit (16). The router circuit (16) has a plurality of input queue circuits (22), coupled to receive packets from the sub-circuits (12) and to buffer the packets for forwarding. The router circuit (16) has output ports (26) for forwarding the packets. Conflicts are detected wherein at least two conflicting packets from different ones of the input queue circuits (22) that are due for transmission in a same time slot are destined a same one of the output ports (26). In case of a conflict only part of the conflicting packets is transmitted in the time slot. Remaining packets from the input queue circuits (22), are dropped according to a selected drop action, so that the dropped packets will not be forwarded after the time slot, but not-dropped packets may be dropped. State information about queue states of the input queue circuits (22) in the time slot is determined, e.g. in terms of how many conflicting packets remain at the heads of the queues. The drop action are selected dependent on the state information, so that only for a sub-set of possible queue states drop actions will be selected wherein one or more packets will be dropped.

Description

PACKET DROPPING AT THE INPUT QUEUES OF A SWITCH-ON-CHIP

The invention relates to a circuit with a plurality of sub-circuits interconnected by a network and preferably to an integrated circuit with a "network on a chip" to pass information between sub-circuits of the integrated circuit. The invention also relates to methods of operating such a circuit. With the increase in size of integrated circuits data communication between different sub-circuits of the integrated circuit requires more and more overhead. When integrated circuits were small, sub-circuits were connected directly by dedicated signal conductors. However, the required number of dedicated connections would increase with a power of the number of sub-circuits as the number of sub-circuits increases, ultimately dominating the entire circuit. As an alternative busses have been used, that is, connection conductors to which a plurality of sub-circuits are connected, so that they can use the conductors on a time-share basis. However, with the continuing increase of the number of sub-circuits this too has become impractical.

The current trend is to use a network to connect the sub-circuits. A network provides for a large number of connection paths, which can be connected in different configurations to establish composite paths between selectable pairs of sub-circuits. Efficient use of connection paths can be realized because each connection path can successively be made part of a large number of different composite paths for communication between different pairs of sub-circuits. Networks of this type contain router circuits to connect the connection paths in changing configurations. A router circuit has a plurality of input ports (e.g. four) and a plurality of output ports (e.g. also four). There is no permanent one-to-one connection between input and output ports. The routing port operates in successive "slots" (routing time cycles). In a slot the router circuit is able to route data from respective ones of its input ports to respective, selectable ones of the output ports. The combination of input and output ports can be made different in each slot. The network is realized by using a large number of such routing circuits, with their ports connected to each other via connection paths and, at the edges of the network, to the sub-circuits. One problem with this type of network is that conflicts may arise between different input ports of a router circuit, if data from different ports must be routed to the same output port in the same slot. This problem can be mitigated by providing queue buffers at the input ports, so that data from an input port that is destined for an output port can be made to wait while data from another input port is transmitted to that output port. However, if too much data, or data from too many ports is destined for the same output port, the risk is that the queue buffers will overflow.

When overflow occurs it is necessary to drop data, by removing it from the queue buffer without transmitting it to the output port or simply by not writing the data into the queue buffer at all. Obviously, the design of the sub-circuit will have to be able to suffer the loss of data that is the result of dropping, e.g. by verifying the arrival of data and using retries for critical data, substituting default data at the destination if data does not derive, using data redundancy etc. However, the form of robustness is not the subject of the present invention. Data dropping, or packet dropping (data being transmitted in packets) is a known technique to resolve conflicts at routing circuits. An "overview of lecture notes" found at http://www.stanford.edii/class/ee384x/Handouts/H08.pdfat, or about at July 15, 2005 discusses "head of line" (HoL) blocking, which concerns the case that packets from different queue buffers that are due to be transmitted are destined for the same output port. This document mentions the possibility of "flushing" all blocked packets from the head of line at the end of a slot.

The performance of router circuits that use packet dropping can be characterized by throughput efficiency (the fraction of packets that is not dropped). The "overview of lecture notes" discloses how mathematical formulas for predicting this measure of performance can be computed.

Among others, it is an object of the invention to improve the throughput efficiency in a circuit with a network wherein data packets are dropped to combat overflow of queue buffers for router circuits.

According to one aspect of the invention a circuit, preferably an integrated circuit, is provided wherein sub-circuit communicate via a network that contains a router circuit and a decision strategy is used that selects drop decisions for the router circuit dependent on information about queue states of input buffer queues in the router circuit, other than whether the input queue circuits are full. By deciding whether or not to drop dependent on this information queue state average throughput (the average number of packets transmitted between sub-circuits) can be optimized. As used herein, the information other than whether the input queue circuits are full may include information whether the input queue circuits are full, but should at least contain other information; it does not exclude information whether the input queue circuits are full. The router circuit may be equipped with a look-up table to look up drop decisions on the basis of queue state information. A set of assignments of drop decision for different queue states may be selected in advance, for example when the circuit is designed, so that a computed or simulated, expected average throughput will be optimized.

In an embodiment only packets at the heads of the input buffer queue circuits are dropped when they are blocked in a time slot, because a packet from another input buffer queue circuit destined for the same output port was forwarded in the time slot. The drop decision strategy determines whether these packets, and if so optionally which of these packets, that remain after a conflict should be dropped. When the queues are in certain states the decision will be not to drop these packets and when the queues are in other states the decision will be to drop all of these packets, or selected ones of these packets. By dropping packets that were involved in a conflict an efficient optimization of throughput can be realized.

In an embodiment, the decision strategy assigns a decision to drop or not to drop to each queue state dependent on a number of input queue circuits that contain packets destined to a same output port. It has been found that making selective drop decisions based on this information provides most room for optimizing average throughput. Preferably, a plurality of numbers of input queue circuits that contain packets destined to respective output ports is used. This is even more effective room for optimizing average throughput. In one embodiment, this is the only information about the queue state that is used to decide whether or not to drop. This simplifies the router circuits. In addition, or alternatively, information about the number of queued packets in respective input buffer queues may be used as a criterion whether or not to drop packets. This provided for further optimization.

In a further embodiment the router circuit applies different drop decision strategies dependent on a selection signal. Preferably the selection signal is indicative of the probability that new packets arrive. Thus, different strategies may be used to optimize throughput when different probabilities occur. The selection signal may be generated for example dependent on a mode of operation of the sub-circuits or on run-time measurements of packet statistics. In an embodiment the network comprises a plurality of interconnected router circuits that make drop decisions dependent on the states of their respective queues. In this case the drop decision strategies of different router circuits may differ, so as to optimize the throughput under different conditions.

These and other objects and advantageous aspects of the invention will become apparent from a description of exemplary embodiments using the following figures.

Figure 1 shows an integrated circuit with a network on a chip. Figure 2 shows a router circuit with input queue buffers

Figure 3 shows an embodiment of part of a control circuit Figure 4 shows an alternative embodiment of part of a control circuit Figure 5 shows an alternative embodiment of part of a control circuit

Figure 1 shows an integrated circuit 10, comprising sub-circuits 12 (only some indicated explicitly) interconnected by a network 14 that comprises router circuits 16 interconnected by connection paths 18 (only some of the router circuits 16 and connection paths 18 shown explicitly). The circuit is shown functionally: although a large block for network 14 is shown with small sub-circuits 12 at the periphery of network 14, it should be appreciated that at a layout level these components may be intermingled and the size of sub- circuits vary so that the sub-circuits often exceed router circuits 16 in size. Also the circuit is no limited to a matrix of router circuits 16.

Figure 2 shows an example of a router circuit, comprising input queue buffer circuits 22, switching circuits 24 and a control circuit 28. The router circuit has input ports 20 coupled to input queue buffer circuits 22. Input queue buffer circuits 22 have outputs coupled to inputs of switching circuit 24. Switching circuit 24 has outputs coupled to output ports 26. Control circuit 28 has inputs coupled to outputs of input queue buffer circuits 22 and outputs coupled to control inputs of switching circuit 24 and input queue buffer circuits 22. In operation sub-circuits 12 apply various data processing functions to data. At least some sub-circuits 12 receive the data for use by the data processing functions via network 14 and/or transmit results of application of the data processing functions via network 14. Data is transmitted through network 14 in packets that are associated with destination addresses. Sub-circuits 12 may form the packets, or network interface circuits (not shown) may be provided between sub-circuits 12 and networkl4. If so, the term sub-circuit 12 will be used as including these network interface circuits. Typically, each packet contains its destination address and the data that is transmitted by the packet. However, alternatively other ways of associating the destination address with a packet may be used, such as associating destination addresses with periodic time slot at particular network ports where the packets arrive and storing the destination addresses for the time slots in router circuits 16.

The circuit operates in successive time intervals called "slots" or transmission cycles. In each slot a packet is transmitted from one router circuit 16 to a selected adjacent router circuit 16, or to a sub-circuit 12 next to a router circuit 16 or from a sub-circuit 12 to a router circuit 16 next to the sub-circuit 12. The selections made by router circuits 16 may be different for each slot. After a succession of slots router circuits 16 will have transmitted each packet to a sub-circuit 12 according to the destination address that is associated with the packet.

In each slot router circuits 16 receive packets from other router circuits 16 or from sub-circuits 12 at their input ports 20. Each input port 20 is associated with a first in first out queue, for example in the form of an input queue buffer circuit 22. It should be understood that separate queue buffer circuits 22 are shown, in other embodiment a shared memory may be used for the different input queue buffer circuits 22. Also, it may be noted that the input queue buffer circuits 22 buffer data between pairs of router circuits, so that they could also be termed output queue buffers.

For each slot control circuit 28 of the router circuit detects whether packets are buffered in the different input queue buffer circuits 22 the router circuit. If so, control circuit determines the destination addresses of the packets at the head of the queues (the first packets that will be output) in the slot. The destination addresses are obtained e.g. from the packets themselves. From the destination addresses control circuit 28 determines the output ports 26 to which the packets from respective input queue buffer circuits 22 should be sent in the slot. In one embodiment, each destination address contains a series of groups of bits that identify output ports for respective router circuits 16 along a path to the destination. In this case, control circuit 28 only needs to extract the relevant bits from the packet. But alternatively other methods of specifying addresses may be used, which may require control circuit to look-up an output port address on the basis of the destination address for example.

Next control circuit 28 controls switching circuits 24 to transmit the packets from the input queue buffer circuits 22 to the selected output ports 26 during the slot. Typically, switching circuits provide for parallel switched connections during the slot that allow simultaneous transmission between pairs of input-output ports during the slot. Alternatively, some form of time division multiplexing may be used, to transmit packet to successive output ports during successive parts of the slot. The transmitted packet is functionally removed from the corresponding queue buffer circuit 22, to move a next packet to the head of the queue (functional removal may correspond to physical overwriting, but alternatively it may involve making a storage location that stores the packet or part of it available for overwriting).

Control circuit 28 detects whether there are conflicts between the destination addresses for packets from different input ports 20. A conflict is said to exist if the destination addresses of the packets at the head of the queues imply that packets from different input ports 20 should be transmitted to the same output port 26. In this case these input queues are said to be conflicting. In the case of a conflict control circuit 28 selects one of the conflicting queues and transmits the packet at the head of that queue.

Various service strategies for selecting one of the conflicting queues may be used. It has been found that a longest queue first (LQF) service strategy generally produces the best results in terms of average throughput. With this service strategy, when the packets at the head of a plurality of the input queues are destined to the same output ports (i.e. there are conflicting queues) the packet from the input queue that contains the most waiting packets is transmitted to the output port. Other service strategies include (pseudo-) randomly selecting one of the conflicting queues, or selecting from the conflicting queues on a fixed priority basis, or selecting from the conflicting queues on a changing priority basis (e.g. circularly changing priorities).

In addition, control circuit 28 decides whether or not to drop the remaining one or more packets that were involved in the conflict. If the decision is not to drop, then these packets may be transmitted in a subsequent slot. If the decision is to drop, then these packets are functionally removed from their corresponding queue buffer circuits 22.

In various embodiments the decision whether or not to drop may be based on respective different criteria. In a first set of embodiments packets are either not dropped or dropped at the head of all the unserviced input queues (the queues from which no packet was forwarded to an output port 26 in the slot).

In one simple embodiment the decision to drop is based on an "conflict count", that is, a count of the number of input queues that was involved in a conflict in the time slot, wherein packets at the heads of these input queues addressed an output port that was also addressed by the packet at the head of another queue. Alternatively the maximum number of input queues with packets at their head that addressed the same output port may be used as conflict count. In this embodiment, when the conflict count exceeds a threshold, which is typically greater than zero, router circuit 16 drops all packets that were involved in the conflict in a time slot that were not transmitted in the time slot. Otherwise, these packets are not dropped.

In another embodiment the decision is based on "combined conflict counts", that is, a plurality of counts of respective numbers of queues that were involved in a conflict in the time slot. In the case of four input ports 20 for example, there may be a conflict involving four input queues 20, a conflict involving three input queues 22, a pair of conflicts, each involving two input queues 22 or only a conflict involving one pair of input queues 22. Router circuit 16 may have a greater number of input queues 22 (e.g. six or eight input ports). In this case a greater number of different types of conflict may arise, each of which may be associated with its own decision to drop or not to drop. Alternatively, output port occupation counts may be used (respective counts for each of the output ports 26 of the number of queues that have a packet at their head that address that output port 26).

In this embodiment router circuit 16 may be designed to implement a specific decision to drop or not to drop for each type of conflict (e.g. don't drop in case of one pair and drop for all other type of conflict) based on the combined conflict counts or the output port occupation counts. Figure 3 shows a typical embodiment of a circuit part of a control circuit of a router circuit. This circuit part has inputs 30 that receive output port addresses for different queues that have been determined by the control circuit, counting circuits 32, for determining a respective occupation count for each output port 26 of the number of packets that address the output port 26, and a look-up table circuit 34 that outputs a drop/not drop decision signal as a function of the counts.

In more advanced embodiments control circuit 28 may adapt the counts for which a decision to drop is taken, dependent on information like the number of packets queued in queue buffer circuits 22 and/or rates of arrival of packets at queue buffer circuits 22. The drop decision strategy i.e. the relation between the counts and the decisions to drop or not to drop is preferably selected to optimize expected average throughput (e.g. to minimize the average number of packets dropped, while preventing that queue buffer circuits 22 overflow). The average throughput can be mathematically analyzed or simulated as a function of the probability that new packets arrive and the drop decision strategy. Thus, different decision strategies can be evaluated and a strategy that corresponds to a better calculated or simulated average throughput than others may be selected for implementation in router circuit 16.

For the analysis and definition of the switching strategy preferably a state space of possible states Q of the queues in router circuit 16 is defined. Each state Q corresponds to a possible combined conflict count and a combination of numbers of packets buffered in the different input buffer queues. The drop decision strategy assigns a decision to drop or not to drop to each state Q. Thus each state also has an associated number D(Q) of dropped packets. Given the drop decision strategy and possible new arrivals of packets in a slot, all possible new states Q' can be determined that can be reached in a next slot from a state Q. Each new state Q' can be associated with a transition probability P(Q'|Q), given probabilities that new packets arrive in the respective queue buffer circuits 22 and probabilities of respective destination addresses.

For example, consider probability of a state Q' with four conflicting packets for a router circuit with four input ports for which nl', n2', n3', n4' packets are queued. The only states Q that can precede this state are:

States Q with no conflicting packets and nl=nl' or nl'+l, n2=n2' or n2'+l, n3= n3' or n3'+l, n4=n4' or n4'+l queued packets, (nl equals nl' if a new packet arrives in the first queue and a packet from the queue is transmitted; nl equals nl'+l if no new packet arrives and a packet from the queue is transmitted etc.).

States Q with one conflict between two queues

States Q with one conflict between three queues - States Q with one conflict between four queues

States Q with two conflicts, each between two queues

In each case the state Q precedes the state Q' can only have certain numbers of packets in nl, n2, n3, n4 in the input queues, given the fact that only one or no packet can arrive at the input of each queue and that one packet is removed from the queue, if the number of packets is greater than zero and there is no conflict, or the drop decision strategy for the state Q is to drop a packet from the queue.

The probability of the state Q' following the state Q is computed from the probability of the arrival of the appropriate number of packets required by the values of nl, n2, n3, n4 and nl', n2', n3'and n4' for the given drop decision strategy. The probability also depends on the probability that as many packets as required by Q' are destined for the same output port, given the number of remaining conflicting packets after the state Q.

Thus a probability matrix P(Q' | Q) is determined, of the probability of occurrence of the states Q' in a next slot, given the state Q in a current slot, a drop decision strategy and a number of packet probabilities. From this matrix P(Q'|Q) the probabilities of occurrence P(Q', n) of the different states Q' in a time slot labelled by "n" (n=l,2,3...) can be determined from

P(Q',n)=sum over all Q P(Q]Q) P(Q,n-l)

The probabilities of the states Q can be used to weight the numbers of dropped packets D(Q) that the drop decision strategy assigns to the states Q. Thus, the average throughput rate for a drop decision strategy can be computed. Methods which are known per se from the so-called Markov decision theory may be used for this purpose. From different possible decision strategies, which yield different probability matrixes P(Q',Q), the strategy is selected that yields the least average number of dropped packets. This strategy is implemented in control circuit 28, for example by defining a look up table circuit which has identifications of different states as inputs and as output decision signals to drop or not to drop. Approximate probabilities determined by simulation may be used instead. In this case different decision strategies are evaluated by randomly choosing whether to add packets to the input buffer queues for a slot with a corresponding probability and randomly choosing the destined output port, also with a corresponding probability, and subsequently dropping packets dependent on the resulting state according to the strategy under evaluation. The average throughput for the simulation can be measured to evaluate the drop decision strategy.

In addition, the probability matrix may depend on the service strategy of the router circuit, i.e. the criterion used to select the queues from which the packets will be transmitted. Accordingly an optimal service strategy may also be selected. In general it has been found that an LQF strategy (select packet from queue with most queued packets) performs best in terms of average throughput.

After evaluation of different drop decision strategies a strategy is selected that result in a better average throughput than others, or at least in one that is not worse. It has been found that some decision strategies that use packet dropping only in some selected states outperform other decision strategies. Table I shows a comparison of average throughputs for different strategies for router circuits 16 with different numbers of inputs N, when the probability "p" of arrival of new packets in the input buffer queues equals one. This representative for all situations where there are always queued packets in all queues, even if p is less than one.

By way of example, it was assumed that the input buffer queues have infinite capacity. Of course this is not realistic. In practice finite capacity will be used, in combination with some method of preventing overflow, such as dropping incoming packets in case of a lull buffer, or dropping packets at the head of the buffer in case of a full buffer. This can easily be accounted for by using a slightly different probability matrix, which may result in slightly different results. However, infinite capacity has been used to provide a simple example.

The first column shows the number of inputs N of the router circuit for which the throughput is computed. The second column shows average throughputs for a strategy without dropping (assuming buffers of infinite size), the third column shows average throughput when packets are always dropped and the fourth column shows average throughput for the optimal drop decision strategy, which drops packets only in selected states.

Table I

It will be noted that a significant improvement of average throughput can be realized by using a drop decision strategy that selectively drops packets only in certain states.

Table II illustrates the optimal decision strategies for routing circuits with different numbers of input ports N for the case of p=l.

Table II

Herein the states wherein packets should not be dropped are denoted by lists (ql ₅q2,q3....) of output port occupation counts for respective output ports 26, each occupation count indicating the number of packets that are addressed to the corresponding output port 26. Because the probabilities have been assumed to be the same for all ports the decision strategies do not depend on permutation between the ports. Each time only one representative of a class of permutations is shown that are permutation is shown (e.g. (2,2,0,0) stands for (2,0,2,0), (2,0,0,2), (0,2,2,0), (0,2,0,2) and (0,0,2,2) as well). In the states that are not mentioned explicitly or implicitly as a member of a class of permutation the packets are dropped (e.g. for N=4 packets are dropped in states (4,0,0,0). (3,1,0,0) and permutations thereof).

The column Keep states II lists states in which packers may be dropped without any or any significant loss of average throughput.

The previous examples have been given for the simple case where p=l, i.e. where a new packet arrives at each input port 20 in each slot. In practice lower probabilities must often be used, with values dependent on the integrated circuit in which the router circuits are used. However, this does not affect the principle of the evaluation of decision strategies.

It has been found that the optimal drop decision strategy varies with the probability p of arrival. In general, drop decision strategies that are optimal for p near one are not optimal for significantly lower p values) e.g. p near 0.7. Of course, when p becomes very small it is usually not necessary to drop packets, since the router circuit will probably not run into conflicts when it waits for another slot to transmit a blocked packet. On the other hand when p approaches one dropping packets is more often advantageous. Preferably, an accurate estimate of the p values in the integrated circuit should be obtained to select the optimal drop decision strategy. Typically a drop decision strategy that is optimal for one p value is also optimal over a range of p- values near that p- value and near optimal over an even wider range. Thus, even if the estimated p-value is not completely accurate a good strategy results from the optimization process. In an embodiment the p-values may change in the course of time, for example if the integrated circuit switches between different modes of operation (e.g. a mode in which one video data stream is processed to a mode wherein two such streams are processed, or a mode in which a computer graphics image is computed). Figure 4 shows a further embodiment wherein the control circuit of the router circuit is arranged to adapt the drop decision strategy according to the mode. For example, a routing mode selection circuit 40 may be provided that receives mode selection signals from the sub-circuits (not shown) and sends control signals to the router circuits dependent on the selected mode. The control circuit of a router circuit may provide for a plurality of look up tables, which are activated by different control signal values at a probability selection input 42 of look up table circuit 44.

In one embodiment only two look up tables, may be provided. But alternatively a larger number may be provided, to be selected under control of a multi-bit selection signal at selection input 42. In a further embodiment router circuits 16 or a routing mode selection circuit 40 monitor run-time statistics of packet transmission (e.g. packet frequency or frequency of conflicts) and generate a selection signal dependent on the runtime statistics. Preferably look up tables are provided for a limited number of decisions strategies and one of these is selected dependent on the measured run-time statistical data. In the examples that were given in the preceding only the output port occupation counts for the respective output ports 26 where used as a decision criterion to drop or not to drop. Accordingly, an optimal strategy was selected from optimal strategies that used only this information.

Figure 5 shows a part of the control circuit for a more advanced embodiment. In this more advanced embodiment, a look-up table circuit 54 is used to also receive information about queue occupations, i.e. the numbers of packets that are waiting in the different input buffer queues. These queue occupations are also used as part of the criterion for deciding whether or not to drop packets. To select optimal decision strategies in this case, the states Q of the router circuit also specify these queue occupations. This increases the number of states Q and state transitions that must be considered, but it does not alter the principle of evaluation and selection of decision strategies. Optionally in this case the drop decision strategy may be selected dependent on the probability p, as in figure 4.

By way of example Table III illustrates optimal drop decision strategies that can be determined in this way for a predetermined p=0.75 and N=4 using criteria that include both information about output port occupation and queue occupation. Table III

Here the "post HOL state" column refers to the packets destined for respective output ports after packets have been transmitted but before new packets have been moved to the head of line (which are the HOL states shown in table II). Typically a post HOL state corresponds to a plurality of possible HOL states, For example, a post HOL state of (1,1,0,0) can be reached from HOL states of (2,2,0,0), (2,1,1,0), (1,1,1,1). But the optimal dropping strategy can be realized on the basis of the post HOL state, so that a more efficient implementation can be realized by looking up the drop decision on the basis of the post HOL state. The first column lists all possible configurations of post HOL states, with the understanding that one representative is mentioned each time for a set of post HOL state that differ only by permutations.

The "queues" column describes the numbers of packets (queue occupations) in the queues that contain packets that were not sent due to a conflict, for each conflict (each port where the HOL state defined a number greater than one). So for example if there where two remaining packets according to the post HOL state (1,1,0,0), then queue occupations for two queues are given, "rest" indicates all possible queue occupations that have not been mentioned.

The "strategy" column describes whether a packet should be dropped (indicated by 1) or not dropped (indicated by 0) from the queues that contain packets that were not sent due to a conflict. Here the sequence in which drop/no drop indications are given for respective queues corresponds to the sequence in the "queues" column: e.g. in the second row with post HOL state (3,0,0,0) a packet should be dropped from the queue with two remaining packets. The X in the "free state" column indicates that dropping should only occur if the queue from which the conflicting packet was sent is not empty.

As a typical example, the row with a post HOL state (1,1,0,0) corresponds to a situation where there were two queues with a packet at their head for a first output port and two queues with a packet at their head for a second output port, so that one packet remains in the queues from each conflict. The strategy column indicates that these packets should not be dropped. As another example, the post HOL states (3,0,0,0) correspond to a situation where there were four queues with a packet at their head for the same output port, so that three packets remain in the unserviced queues. In the second row with post HOL state (3,0,0,0) a state of the queue is identified wherein two packets are queued in a first one of the unserviced queues, and one in each of the other unserviced queues. The strategy column indicates that in this case a packet from the first one of the unserviced queues should be dropped but not from the other unserviced queues.

The look-up table circuits may be implemented using a ROM memory, that is addressed by state information and that stores control signals for the different possible values of the state information. However, alternatively instead of the ROM a logic circuit may be used that is configured to realize the same input-output relation as the ROM. Often, this will result in a considerable reduction in circuit size because of the high symmetry between different states that result in the same control signals, as can be noted from the examples (e.g. permutations of the ports).

It is not necessary that the same drop decision strategy should be used for all router circuits 16. In general, simulation or analysis of the functions performed by the sub- circuits 12 may show that the arrival of packets at different ones of router circuit 16 may occur at different probability. In this case different drop decision strategies may be selected for different router circuits 16. For example router circuits 16 located in network 14 near very frequently receiving or transmitting sub-circuits 12 may have a different drop decision strategy than other router circuits that are further away (coupled to the very frequently receiving or transmitting sub-circuits 12 only via a greater number of router circuits 16). In a predetermined circuit, especially in an integrated circuit if definite different probabilities p can be determined so that different drop decision strategies may be found to be optimal at different positions in the network.

Furthermore, it is not necessary to assume the same probability of packet arrival at all input ports 20. The appropriate probabilities can be used in the evaluation of different strategies, which may result in a different optimal drop decision strategy than for equal probabilities. Typically, this removes the symmetry between states that differ only by permutation of the input ports. Preferably the implemented drop decision strategy is adapted accordingly.

Also, the probabilities of conflicts between packets can be different for different output ports or for packets from different combinations of input ports. These probabilities too can be used in the evaluation of different strategies, which may result in a different optimal drop decision strategy than for equal probabilities. Typically, this removes the symmetry between states that differ only by permutation of the input ports and output ports. Preferably the implemented drop decision strategy is adapted accordingly.

Furthermore, as noted the optimal drop decision strategy may depend on the capacity of the input buffer queues. In one embodiment the capacity of the queues at each input port is the same. This makes it possible to use standardized router circuits, with a simplified lay-out. In other embodiments, mutually different capacities may be used for different ports and/or for different router circuits. This too may be accounted for in the selection of the optimal drop decision strategy.

Furthermore, although embodiments have been shown wherein a drop decision strategy is always used, alternatively dropping can be switched on and off. For example in one embodiment the circuit has a first mode of operation where no packets are dropped and a second mode where packets are dropped according to one or more drop decision strategies. In this embodiment the circuit initially operates in the first mode, but it switches to the second mode when queue filling reaches a first threshold condition (e.g. when at least one of the input queue buffers has become full, or filled above a predetermined capacity). Subsequently the circuit switches back to the first mode when queue filling reaches a second threshold condition (for example when all input queue buffers are filled less than to a further predetermined capacity). Where the term "optimal" strategy is used it should be understood that this term refers to optimal within the set of drop decision strategies that is considered. For example, an strategy may be selected that is optimal among a set of strategies that use only output port occupation numbers to decide whether or not to drop. Such a strategy may be less optimal than a strategy that also uses queue occupations. Nevertheless, such a strategy will be called optimal. In general, an "optimal" strategy is defined to mean that worse strategies exists for deciding on the basis of the same state information.

Although strategies have been considered that involve dropping packets in some queues and not in others, it will be understood that alternatively only strategies may be considered that involve dropping packets in all queues. Furthermore, strategies may be considered that drop more than one packet from a queue and/or not packets at the head of the queues. Each strategy of a number of strategies under consideration may be evaluated and an optimal one chosen for implementation in the router circuits.

Also, although deterministic strategies have been considered that involve always dropping or always not dropping given a specific state (output port occupation, queue occupation), it should be realized that alternatively probabilistic strategies may be used, which involve dropping or not dropping with a probability that is controlled by the state. Thus a more refined optimization is possible. Similarly, periodically changing strategies may be used, more or less to simulate the effects of probabilistic strategies. Evaluation of such strategies presents no particular problem. Alternatively, or in addition, state information about previous states may be used to select the drop decision, in addition to the information about the current state of the router circuit

Claims

CLAIMS:

1. A circuit (10) comprising a plurality of sub-circuits (12) and a network (14) interconnecting the sub-circuits (12), the network (14) comprising at least one routing circuit (16), the routing circuit (16) comprising a plurality of input queue circuits (22), coupled to receive packets from the sub-circuits, each packet having an associated destination address; a plurality of output ports (26); a switching circuit (24) for forwarding packets from respective ones of the input queue circuits (22) to respective ones of the output ports (26), under control of the destination addresses of the packets at heads of the respective input queue circuits (22); - a drop control circuit (28), having outputs coupled to the input queue circuits

(22), to control dropping of packets from the heads of the respective input queue circuits (22), the drop control circuit (28) having inputs coupled to receive state information about queue states of the input queue circuits (22) other than whether the input queue circuits are full, the drop control circuit (28) being arranged to select a drop action whether or not to drop packets from the queue circuits dependent on the information about the queue states.

2. A circuit according to Claim 1, wherein the state information that is used to select the drop action comprises information indicative of a number of input queue circuits (22) that contain packets destined to a same output port (26).

3. A circuit according to Claim 1, wherein the state information that is used to select the drop action comprises information indicative of numbers of input queue circuits (22) that contain packets destined to respective output ports (26).

4. A circuit according to Claim 3, wherein the state information that is used to select the drop action comprises information indicative of numbers of packets buffered in the respective input queued circuits (22).

5. A circuit according to Claim 3, wherein the state information that is used to select the drop action comprises only said information indicative of numbers of input queue circuits (22) that contain packets destined to respective output ports.

6. A circuit according to Claim 1, wherein the state information that is used to select the drop action comprises information indicative of numbers of packets buffered in the respective input queued circuits (22).

7. A circuit according to Claim 1, wherein the router circuit (26) has a selection input (42), the router circuit (16) adapting the selection of the drop action dependent on the state information under control of a signal from the selection input (42).

8. A circuit according to Claim 1 comprising a packet statistics monitoring circuit (40) with an output for supplying a signal selected dependent on packet statistics to the selection input (22).

9. A circuit according to Claim 1, wherein the drop control circuit comprises a look-up table circuit (34, 44, 54) having inputs coupled to receive the state information and outputs coupled to the input queue circuits (22) to control the drop action.

10. A circuit according to Claim 1, wherein the drop action indicates whether or not to drop one or more packets whose transmission was blocked due to the presence of a further packet that was destined for a same output port as the one or more packets.

11. A circuit according to Claim 10, wherein the drop action indicates whether or not to drop all packets whose transmission was blocked due to the presence of a further packet that was destined for a same output port as the one or more packets.

12. A circuit according to Claim 1, wherein the network (14) contains a plurality of interconnected router circuits (16), each with its own drop control circuit, respective dependences of the drop action on the queue states being different for at least two of the router circuits (16) at mutually different positions in the network (14).

13. A circuit according to Claim 1, wherein the router circuit (16) comprises a control circuit (28) arranged to select from which one of a plurality of conflicting input buffer queues (22) that contain packets at their head that are destined for a same one of the output port (26) should be forwarded in a time slot, the control circuit (28) being arranged to determine a most filled one of the conflicting input buffer queues (22), which is not filled less near to its full capacity than any other ones of the conflicting input buffer queues (22) in the time slot, and to cause the packet from the head of the most filled one of the conflicting input buffer queues (22) to be forwarded in the time slot.

14. A circuit according to Claim 1, wherein the sub-circuits (12) and the network

(14) are integrated together on an integrated circuit chip (10).

15. A method of transmitting packets with data between sub-circuits ( 12) of a circuit (10) via a network (16) that contains a router circuit (16) comprising a plurality of input queue circuits (22), coupled to receive packets from the sub-circuits (12) and to buffer the packets for forwarding, and output ports (26) for forwarding the packets, the method comprising detecting a conflict wherein at least two conflicting packets from different ones of the input queue circuits (22) that are due for transmission in a same time slot are destined a same one of the output ports (26); selectively transmitting only part of the conflicting packets in the time slot; selectively dropping remaining packets from the input queue circuits (22), according to a selected drop action, so that the dropped packets will not be forwarded after the time slot; - determining state information about queue states of the input queue circuits

(22) in the time slot, other than whether the input queue circuits are full; selecting the drop action dependent on the state information, so that only for a sub-set of possible queue states drop actions will be selected wherein one or more packets will be dropped.