WO2001019037A1

WO2001019037A1 - Contention resolution element for a device for transmitting a plurality of packet-oriented signals

Info

Publication number: WO2001019037A1
Application number: PCT/EP2000/008598
Authority: WO
Inventors: Andreas KIRSTÄDTER; Matthias Hellwig
Original assignee: Infineon Technologies Ag
Priority date: 1999-09-02
Filing date: 2000-09-01
Publication date: 2001-03-15
Also published as: DE50010357D1; JP2003509907A; JP3657558B2; CN1130055C; DE19941851C2; DE19941851A1; CN1372741A; EP1208678A1; EP1208678B1

Abstract

For contention resolution an allocation vector is passed through a cascade of comparator elements in a contention resolution element. Every comparator unit evaluates a contention request vector supplied to it and allocates only the first possible bit of the allocation vector. A minimum fairness balance is established by following a quota rule. The parallel or semi-parallel processing of the allocation vector in the cascade allows for an extremely high processing speed.

Description

description

Cell conflict resolution unit for a device for switching a plurality of packet-oriented signals

The invention relates to a cell conflict resolution unit for a device for switching a plurality of packet-oriented signals.

In recent years, the transmission capacity or the data transmission rate in networks has increased significantly. This led to the necessity to develop switching devices, in particular switches and routers, which have a data throughput in the multi-gigabit or even terabit range. With such high transmission speeds, the required network protocols can only be implemented as hardware.

Switching devices for these high transmission speeds are implemented as an active backplane using a crossbar architecture. Crossbar switching architectures work completely in parallel, so that the throughput of such devices is only limited by the number of individual ports and the internally used coordination method.

Crossbar architectures usually work with several port chips that are connected to a central crossbar chip via interfaces. Known crossbar chips usually contain buffer memories in order to buffer packets or cells in the event of collisions. The cells result from the segmentation of a packet into cells of a certain length, which is usually carried out, in particular in the case of packets of variable length, which are then further processed within the switching device. This results in the possibility of rationally processing isochronous to realize the cells. In addition, in the event of collisions, ie if several ports of the port chips attempt to transmit to the same port of another port chip, a “fair” transmission of the signals or packets present at the competing ports is facilitated an external contention resolution unit (cell conflict resolution unit) is connected to the crossbar chip, which uses certain algorithms to determine a fair selection of the competing ports.

For example, DE 195 40 160 A1 discloses a method for coordinating serial lines of input-buffered ATM switching devices to avoid output blockings, in which ATM cells competing for an output are already buffered at the input of the corresponding switching device. In principle, this switching device consists of several port chips, each with several ports, the “output ports” of which are connected to one another via a crossbar chip. The freedom from blocking of the device is achieved by using an assignment vector, the individual bits of which are assigned to a (target The assignment vector is passed from port chip to port chip one after the other before the transmission of a cell, with each port chip having the option of a bit of the assignment vector in the order in which the assignment vector is passed on If a bit is occupied, this means that the relevant (source) port chip would like to transmit a cell to the (destination) port chip that corresponds to the respective position of the occupied bit of the occupancy vector. Target) port chip, or this output of the crossbar chip and the respective occupied bit of the occupancy vector is then available to the next port chip which the occupancy vector is passed on, is no longer available for the transmission of a cell in the respective time slot. In this known device, the occupancy vector is processed in the port chips, the occupancy vector being transmitted on a serial connecting line between the port chips.

As a result, external high-speed transmission lines between the port chips are required in the hardware implementation of such a switching unit, which requires a corresponding design effort and hardware effort. In addition, the occupancy vector is clocked and passed on serially from port chip to port chip, the occupancy vector being shifted by only one bit in each clock cycle. In this way, each port unit that already has a bit of the occupancy vector available can only process one bit at a time, preferably the bit that has just been transferred in the respective cycle. If there are N port chips, a total of 2N clock cycles are required to completely process the occupancy vector. With a large number of port chips, this leads to timing problems, since only a very limited period of time is available for this test, which is shorter than the total cycle for the transmission of a cell (timeslot). Thus, either the number of port chips is limited or extremely high clock rates have to be used when processing the occupancy vector. This device has a cell conflict resolution unit with a decentralized structure, which has the disadvantages mentioned.

A fairness compensation with respect to competing transmissions to different (target) port chips can take place in the device according to DE 195 40 160 AI by the sequence of access to the buffer memories assigned to each other port chip of the individual port chips at the beginning of an entire cycle is changed. In principle, this results in a changed assignment of the bit positions of the assignment vector to the port chips, so that the fact that the assignment has been changed makes it possible to compensate for risks. For this purpose, a method for fast and fair, hardware-based random selection of signals is known from DE 195 44 920 C2, the total number of all signals being checked for activity in a pseudo-randomly generated sequence and corresponding to a desired number k of signals to be selected, the k signals first found as active in the test sequence are selected. This procedure enables a very good fairness compensation in a simple way.

On the basis of this prior art, the object of the invention is to create a cell conflict resolution unit for a device for switching a plurality of packet-oriented signals, with which a switching device can be implemented in a simple manner and with little external hardware expenditure, and which one characterized by a high processing speed when determining a sufficiently fair non-blocking combination of simultaneously possible transmission authorizations between a plurality of ports of a switching device for packet-oriented signals.

The invention achieves this object with the features of patent claim 1.

The invention is based on the knowledge that by providing a cascade of N comparator units, an extremely high speed can be achieved in determining a non-blocking combination of simultaneously permissible transmission paths between the N ports of a central switching device while ensuring sufficient fairness that an occupancy vector is passed in parallel in the cascade of the comparator units, the processing of the occupancy vectors and thus the generation of the authorization information in the comparator units being carried out in parallel or semi-parallel. According to the preferred embodiment of the invention, the assignment vector is processed in and the transfer of the assignment vector is clocked between the comparator units, whereby the signaling vector and switching times of the hardware involved can also be processed in one or more clock cycles in one or more comparator units. This enables an extreme increase in processing speed.

In the preferred embodiment, each availability vector that is transferred from a specific port unit to a specific comparator unit has N bits, the position of a bit in the availability vector containing the assignment of the information contained in this bit to a specific port unit and wherein the one logical state of the bit signals whether a packet or a cell is available in the port unit supplying the availability vector and is to be transmitted to the port unit which corresponds to the position of the respective bit in the availability vector, and wherein each other logical state signals the lack of availability of a packet or a cell. This enables simple selection of packets or cells that can be transmitted without blocking at the same time.

Although only N-1 bits were required as an availability vector for each port unit, this had the consequence that processing was made more difficult by the different assignment of the bits to the (receiving) port units.

In the same way, the occupancy vector in the preferred embodiment also comprises N bits, the position of a bit in the occupancy vector making the assignment of the information contained in this bit to a specific port unit. tet and wherein the one logical state of the bit signals the occupancy of the relevant port unit for receiving a packet or a cell from another port unit, and the other logical state indicates the readiness of the relevant port unit.

The control unit transfers an initial occupancy vector to the first comparator unit at the beginning of a processing cycle. This can already have assignments, e.g. if a port unit is not assigned to each port of the cell conflict resolution unit or if the transmission to a port unit is to be deliberately prevented for certain reasons.

Within a comparator unit, the authorization information, which is to be transmitted to the port unit connected to the comparator unit, is determined in compliance with a predetermined sequence with respect to the port units or the individual bits of the occupancy vector.

In order to create a fairness compensation with regard to the receiving port units, the order at the beginning of a cycle of the determination of the authorization information by the N comparator units can be selected from a predetermined number of pseudo-randomly generated sequences.

Instead of changing the processing sequence within the comparator units after each or after a certain number of cycles, each comparator unit can always determine the authorization information for the port unit in question in the order of the bits of the occupancy vector. Each comparator unit can then be preceded by a permutation unit, to which the availability vector can be supplied and which re-arranges the bits of the availability vector in accordance with a predetermined rule. Each comparator unit can then also have a metric permu- tationse unit which, taking into account the permutation of the sequence of the bits of the availability vector from the information supplied to the comparator unit, whether and which position of the occupancy vector was occupied, determine which authorization information to transmit to the port unit connected to the respective comparator unit is.

According to one embodiment of the invention, the selection authorization for the transmission of the respective packet or the respective cell to a different port unit in each comparator unit can be given by Nl quota numbers provided for each of the other N1 port units or by N quota numbers provided for each bit of the occupancy vector - be trolled. The payer status (quote) of a quote payer is incremented or decremented after each selection of the assigned port unit or after each assignment of the associated bit of the assignment vector. After a predetermined number of payer has been reached, the selection authorization for the port unit concerned or the assignment authorization for the relevant bit of the assignment vector is blocked.

The provision of N numbers again represents the more easily realizable option if the bits of the availability vector are permuted at the same time, since otherwise the information had to be additionally passed to the respective comparator unit, which of the N bits must not be used anyway, because this would mean sending the packet or cell back to the respective sending port unit. This would be theoretically possible, but the

Mediation of signals between different ports of one and the same port unit preferably regulated within the respective port unit.

However, it would be readily possible to provide only Nl quota numbers within a comparator unit if the processing sequence of the bits of the occupancy vector were within of a comparator unit remains constant, since then one and the same bit must not or must not be used.

According to one embodiment of the invention, the odds numbers (21) of a comparator unit (13) can each be assigned to a specific bit of the occupancy vector (CRres). In this case, the control unit (11) can set all quota numbers (21) of all the comparator units (13) which are assigned to a specific bit of the occupancy vector (CRres) to an initial value (initial quota) if no comparator unit (13) there is more in which the relevant quota payer (21) still has a quota and at the same time the relevant bit of the permuted availability vector (CRreq ^* ) indicates a packet to be transmitted or a cell to be transmitted.

According to another embodiment of the invention, the quota counters (21) of a comparator unit (13) can each be assigned to a specific port unit (3). In this case, the control unit (11) can set all quota counters (21) of all comparator units (13) which are assigned to a specific port unit (3) to an initial value (initial quota) if there is no longer a comparator unit (13) in which the relevant quota counter (21) still has a quota and at the same time a packet or a cell is to be transmitted from the port unit connected to the comparator unit (13) to the relevant port unit.

The permutation information can be fed to the comparator units (13), the comparator units (13) permuting the quota counters in their order and the information whether a cell is available for transmission from the permuted availability vectors CRreq *.

If the control unit assigns one or more quota payers a higher initial quota than others Quotenzahler, this way a Pπoπsierung certain transmission paths or nodes of the switching device can be realized.

According to one embodiment of the invention, the comparator units can each be implemented using an N-stage Pπoπty encoder, each of the N inputs of the Prioπty encoder being connected to the output of an AND gate, and a first input of the AND gate speaking bit of the possibly permuted availability vector is supplied, a second input of the AND gate the relevant bit of the occupancy vector which is present at the output of the preceding comparator unit and a third input of the AND gate the information of the associated quota number, which is logical ONE is when there is still a selection right and logically ZERO when there is no longer a selection right.

The cell conflict resolution unit according to the invention can be designed as a separate integrated circuit. However, such a unit can also be integrated into a central switching device (a crossbar chip) which has N ports for connecting a maximum of N port units.

Further embodiments of the invention result from the subclaims.

The invention is explained in more detail below with reference to an exemplary embodiment shown in the drawing. The drawing shows:

1 shows the schematic architecture of a switching device with a simultaneous schematic representation of the data flow with a cell conflict resolution unit integrated in the crossbar chip according to the invention; FIG. 2 shows the schematic representation of the central switching unit and a port unit in FIG. 1, with simultaneous representation of the information flow in the collision resolution;

3 shows the schematic structure of the data blocks transmitted from the port units to the central switching unit (FIG. 3a) and from the central switching unit to the portals (FIG. 3b);

4 shows the schematic structure of the central switching unit in FIGS. 1 and 2;

Fig. 5 shows the schematic structure of the cell conflict resolution unit according to the invention and

FIG. 6 shows the schematic structure of the core piece of a comparator unit in FIG. 5.

Fig. 1 shows the architecture schematically shows a switching device 1 according to the invention, which standardize a total of N port units 3ι to 3 _N, and a central Vermittlungsem- 5 consists. Each of the N port units 3ι 3 _N has n ports 7 _X to 7 _n, to each of which a signal S _1D can be supplied, where: l≤i≤n and l≤j≤N. The port units are usually designed so that bidirectional communication is possible at each port. Of course, the principle of the present invention can, however, also be applied to systems in which certain or all ports are designed for unidirectional communication only. In practice, however, this will rarely be the case.

The port units 3 shown in FIG. 1 are preferably designed as integrated port modules or separate modules. The same applies to the central mediation effort 5. This achieves a modular structure, which in turn enables simple scaling, ie adaptation of the switching device to the number of data lines to be switched, which is required in each case.

As shown in Fig. 1, the port units 3 and the central switching unit 5 are connected via interface units. The interface units provided in port units 3 are referred to as "CB-IF" (crossbar interface) and the interface units provided in central switching unit 5 are referred to as "port IF" (port interface). In this case, a separate interface unit Port IF is provided in the central switching unit 5 for each port unit 3. Each interface unit Port IF and CB-IF can, as from F g. 4 for the central switching unit, can be connected to the transmission lines between the port units 3 and the central switching unit 5 via a low-voltage differential signaling unit (LVDS). This enables the number of connecting lines to be reduced, for example 16-bit data lines between the interface units Port IF or CB-IF and the LVDS units and 4-bit data lines (each with differential signals) between the LVDS units on a total of 8 physical lines).

The central switching unit 5 takes on the function of a crossbar switch, so that a completely temporally parallel internal data transmission of a maximum of N (crossbar internal) signals is possible (when realizing full duplex transmission via LVDS units). The data inputs / outputs of the interface units Port IF are connected to the actual Switchmg-Matπx (matrix). Furthermore, a port IF can switch through the switching matrix in the manner communicated to it, so that the desired path from one port IF to another port IF is available within the central switching unit for data transmission. is available. In order to prevent several ports 7 of different port units 3 from simultaneously accessing a port 7 of another port unit - this would mean cell loss or internal blocking - a collision resolution unit 8 is provided, which is also referred to below as a contention resolution. Resolution unit (CR) is called. The CR unit 8 is preferably provided within the central switching unit and is designed together with the latter as an integrated circuit. Since the CR unit 8, as can be seen from the following description, has to exchange data very quickly between it and the interface units port IF, the integration of the CR unit results in the advantage of very short high-speed transmission lines.

The method and the function of the switching device according to the invention are explained in more detail below with reference to the figures:

1, the ports 7 _X to 7 _{n of} the port units 3 ₁ to 3 _{N are} each supplied with a signal S _1; The signals are each a stream of data packets, which can have different lengths.

First, the data packets of the individual signals S _{13 are} segmented by the port units 3, that is to say divided into individual cells of constant length. The cells are stored in a buffer memory 9, which can be integrated in the port units 3 or designed as an external memory. The segmentation is carried out by a control unit (not shown in detail) in each port unit 3, which organizes the buffer memory 9 in such a way that for each of the other port units 3 a separate virtual buffer memory (9a) is created, which contains the cells to be transferred to the other port unit in question are. For this purpose, each port unit 3 or its control unit evaluates the ad address information of each received packet, and uses this information to determine whether the packet or the corresponding cells have to be transmitted to another port unit 3 or not and assigns the corresponding cells to the respective virtual (9a) memory. The assignment of the cells of a data packet to one another can be maintained by providing pomters. Of course, a separate memory can also be provided for each of the other port units.

The separate or virtual memories (9a) are of the FIFO type because the sequence of the cells should be preserved when the cells are read in and out.

If the port unit determines that no transfer to another port unit is required, the port unit takes over the port-internal switching process. Of course, buffering of the data packets will usually also be necessary for this, but not necessarily segmenting them. Since this port-internal switching function of the switching device 1 is not relevant to the present invention, a more detailed explanation can be dispensed with.

Such a buffer memory 9 per port unit 3 is necessary in any case, since only one cell can be transferred internally from one port unit to the central switching unit. In addition, in the case of asynchronous transmission of the signals S _13, buffering is required in order to intercept transmission peaks. This is the case, for example, in ATM and Ethernet systems, since different services and different ports work with different data transmission rates and the header evaluation time is very scattered, particularly in the case of IP traffic.

In principle, segmentation of the packets for internal transmission and transmission are also not necessary of the data packets within the switching device 1 as a whole. However, segmentation has the advantage that clock-synchronous transmission can take place within the switching device regardless of the respective length of the packets. In addition, fair treatment of the individual (exits of) port units becomes easier.

The cells within the switching device 1 are transmitted isochronously, i.e. In a timeslot, one or more cells are transmitted from the port units 3 to the central switching unit 5 and vice versa. With an internal transmission speed of 2 Gbit / s (on each connection between the port units and the central switching unit and within the central switching unit) and a cell length or size of 70 bits, an timeslot can have a duration of 280 ns, for example.

In order to avoid blocking within the switching device, each port unit 3 first transmits availability information to the central switching unit 5. The availability information contains for which other port units there are currently cells for transmission in the respective port unit. In the above-mentioned model of the virtual separate buffer stores (9a) provided in the port units for the respective other port units, the availability information thus includes whether the individual virtual buffer stores contain no or at least one cell.

The availability information can, as shown in FIG. 3a, be transmitted in the header of the cells transmitted from the port units 3 to the central switching unit 5 in order to avoid a separate transmission step and the associated higher protocol effort. The availability formations can be summarized as a contention request vector (CRreq), the vector consisting of N bits corresponding to the number of port units. The position of each bit within the CRreq vector indicates the number j (l≤j≤N) of port unit 3, and the assignment of the bit concerned, whether in the respective port unit for port unit 3, a cell for transmission is available stands.

The CRreq vector does not necessarily have to be linked to the cell that is actually to be transmitted in the next timeslot, but can be directed to one or more timeslots in the future. That is, the respective availability information relates to cells that are only in two or more timeslots may be transmitted in the future, this time shift having to be constant for all port units 3.

The central switching unit 5 or the interface units port IF read out the availability information contained therein after receiving the possibly several cells transmitted simultaneously by the port units and transmit this together with the information from which port unit the availability information was transmitted to CR-Emheit 8. The CR-Emheit 8 determines a possible combination of admissible, ie., According to a given contention-resolution algorithm collision-free transmission options from corresponding send port units to corresponding receive port units.

The combination determined in this way is transmitted in the form of authorization information CRgnt at least to those port units 3 which are to be given transmission authorization for the relevant timeslot.

This authorization information, as can be seen in FIG. 3b, is preferably transmitted again in the header of cells. For example, the respective interface unit Port IF can write the coded chip ID of the port unit to which transmission from the port unit connected to the respective interface unit Port IF has been released into the header of a cell to be transmitted if the one with the respective port IF connected port unit for the relevant timeslot a transfer authorization (for the relevant cell) is to be granted. If no authorization is to be granted to the port unit in question, the header in the area reserved for the authorization information can contain a defined assignment which is interpreted by the port units as "no authorization granted".

After receiving a cell, the central switching unit 5 or the interface units Port IF not only read out the availability vector CRreq, but also at least the address information (in FIG. 3 labeled “destination”) that is required for the port unit to determine to which the cell in question is to be transferred.

Instead of such an address evaluation, each interface unit Port IF can also use the authorization information supplied to it by the CR unit to switch the Switchmg matrix in the relevant timeslot in such a way that the respective cell still transmits to the correct port unit in the same timeslot becomes.

Since no CRreq vector has to be contained in the header of the cells which are transmitted from the central switching unit 5 to the respective port units 3, this space in the header can be used for the transmission of other information, for example for status information of the portals 3. After receiving a cell, the authorization information CRgnt is read out in the port units 3 and it is determined whether an authorization (corresponding to the availability information previously sent to the central switching unit 5) has been issued for the relevant timeslot

The port unit or the corresponding control unit which, after receiving a cell, determines that authorization information is available, makes the relevant cell, for which availability information was previously transmitted to the central switching unit, available for transmission in the relevant timeslot. For this purpose, the cell in question is read from the memory 9 and transferred to the interface unit CB-IF.

After receipt of a cell by a port unit 3, the control unit of the port unit reads the address information in the header of the cell and assigns the cell to the respective output port or the respective media access control (MAC) (not shown). In addition, the individual cells are reassembled into the original data packets in the port unit or the respective MAC of the individual ports and transmitted to the respective addressees.

After receiving a cell by the interface unit CB-IF of a port unit and reading and evaluating the authorization information, a new availability information CRreq must be determined immediately and inserted into the next cell to be transmitted to the central switching unit 5. This process is extremely time-critical.

5 shows the schematic internal structure of the content resolution unit 8, which has a control unit 11 and a cascade of N comparators 13 (13 1 to 13 _N ). In the embodiment shown in FIG. 5, each comparator unit 13 is preceded by a permutation unit 15 (15 _× to 15 _N ), each of which is connected to the interface lenemorten PORT IF of the central switching unit 5 are connected. The permutation units 15 are acted upon by a payer 16. The comparators are connected within the cascade via parallel connection lines 17, via which the occupancy vector CRres (see below) can be transferred from one comparator unit to the next comparator unit within the cascade. Each comparator unit 13 is followed by an inverse permutation unit 19 (19 1 to 19 _N ) in the Contenction Resolution unit shown in FIG. The control unit 11 controls the counter 16 and is also connected to each of the comparators 13. In addition, the control unit 11 is connected via connection lines 17 to the first comparator 13ι of the cascade.

The contention resolution unit shown in FIG. 5 operates as follows:

In each timeslot, the contention resolution unit runs through an entire cycle, within which the authorization information CRgnt for each port unit is determined, which are then transmitted to the respective port units via the interface units PORT IF.

The authorization information CRgnt is ascertained in a clocked manner, the clock in the contention resolution unit 8 preferably being the same as the clock in the other central switching unit.

At the beginning of an overall cycle, the permission request vectors CRreq, that is to say the availability vectors of the individual port units, are transmitted to the permutation units 15. A certain number of pseudo-randomly generated sequences are stored in the permutation units 15, of which the same sequence is active in all permutation units. By applying the permutation units 15 through the output of the payer 16 is in each case activated a certain one of the orders. Of course, the sequence of the sequences can also be defined in the permutation units, so that the next sequence can be activated by simply supplying a "step-by-step pulse".

The order can be changed after a certain number of total cycles. In practice, however, one will preferably switch to a different order after each overall cycle.

The permutation unit uses the active sequence in each case to reorder the bits of the CRreq vector accordingly. This ensures that none of the port units 3 (as receiving port units) are positioned within the

Occupancy vector is preferred. The rearranged CRreq vectors are transferred to the comparator units 13.

The control unit 11 transfers an initial occupancy vector CRres to the first comparator unit 13χ. A quota number 21 (FIG. 6) is also provided in each comparator unit 13 for each bit of the occupancy vector. Each quota counter determines how often the relevant bit of the occupancy vector has already been selected by the relevant comparator unit 13. If a predetermined maximum number is exceeded, the authorization to re-select this bit is blocked in the comparator unit.

For this purpose, the odds counter 21 can be designed, for example, as a backward counter that can be reset by the control unit (by resetting the counter is set to a predefined fixed value). If a prioritization of a port unit (as a sending port unit) is to be deliberately generated, the quota payer can be designed as payer that can be loaded by the control unit with predefined values. The odds counters preferably have a binary output, a logic state (for example logic ONE) signaling selection authorization and the other state (for example logic ZERO) the absence of the selection authorization.

First, in the first comparator 13arat, based on the initial occupancy vector, the rearranged CRreq vector and the outputs of the quotas for each bit of the occupancy vector, it is checked whether it is already occupied or still free. The initial occupancy vector can also have bits already occupied. For example, the control unit can pre-assign corresponding bits if not all interface units PORT IF of the central switching unit 5 are connected to port units 3.

If an em bit is found to be occupied, no further testing is necessary. If, on the other hand, a bit is recognized as free, it is checked whether the relevant bit (with the same position) of the rearranged CRreq vector signals the presence of a cell to be transmitted. If this is the case and a selection authorization is recognized on the basis of the output of the relevant quota number, the comparator unit 13ι occupies the relevant bit of the occupancy vector. This completes the test process, since only one cell can be transferred to the corresponding port unit at a time. If a missing selection authorization is recognized for this bit of the occupancy vector CRres or if the CRreq vector does not indicate a cell to be transmitted, the checking process is continued. This test method is carried out until a bit of the CRres vector has been occupied by the comparator unit 13ι or until all bits of the vector have been checked.

In the embodiment shown in FIG. 5, this check is preferably carried out in the order of the bits of the CRres vector. In principle, however, it would also be possible to change the check sequence of the bits of the CRres vector in the comparator units instead of rearranging the CRreq vectors in the permutation units 15.

After the CRres vector has been checked in the comparator unit 13ι, it is transferred to the comparator unit 13 ₂ . In this test procedure is then carried out again according to the scheme explained above. These steps are repeated until the assignment vector has been checked by all comparator units and, if appropriate, corresponding free bits have been assigned. The entire cycle is now complete.

At the end of each overall cycle, the authorization information present at the output of each reverse permutation unit 19 is transmitted to the relevant port unit 3 via the respective interface unit PORT IF. Each inverse permutation unit 19 receives from the relevant comparator unit 13 the information as to whether and which bit of the occupancy vector has been occupied. The inverse permutation unit knows the reordering applied by the permutation units and determines the original bit position from the bit position that was occupied again.

For this purpose, inverse sequences can be stored in the mvers permutation units 19, by using which the rearrangement carried out in the permutation units 15 is reversed. As in the case of permutation units 15, the inverse permutation units 19 can also be selected or switched through the inverse sequences by the output of the payer 13 supplied to them.

In addition, each inverse permutation unit 19 can, after swapping back the respective occupancy vector CRres and the known assignment of the port units 3 to the positions of the CRreq vector, as authorization information CRgnt, the ID number of that port unit 3 to that with the respective one Communicator unit connected port unit to which the latter can transmit a cell.

Before the start of the test of the CRres vector in the cascade of the comparator units 13 (or after the end of the test of the CRres vector in the previous overall cycle), the control unit 11 determines whether at least one quota number 21 of a comparator unit 13 is still one for a specific bit within the CRres vector Quote and at the same time the relevant bit of the permuted CRreq vector supplied to this comparator unit (designated CRreq *) indicates a cell to be transmitted to the relevant port unit 3. If this is not the case, the control unit 11 causes all the quota numbers 21 of the comparator units 13 responsible for the relevant bit of the CRres vector to be reset to the initial quota.

While with the possibility described above, the quota numbers 21 were assigned in a simple manner to a specific bit of the CRres vector, in another embodiment the quota numbers 21 can be assigned to the outputs of the central switching unit 5 or to the port units. However, since the permuted vector CRreq * is always supplied to the comparators 13, in this case the permutation information must also be communicated to the comparator units 13. This information can then be used to check whether certain payers have to be set to an initial quota, either to rearrange the order of the quota payers or to reverse the assignment of the bits of the CRreq * vectors.

According to another embodiment, it is also possible to pass the non-permuted CRreq vectors to the comparator units 13 in addition to the CRreq * vectors. The quota numbers 21 assigned to the port units 2 can thus immediately determine whether there is still a cell to be transferred to the relevant port unit 3. If a prioritization of the respective sending port units 3 is dispensed with, then in the simplest case the quota one can be used, in which case the quota numbers can be implemented by a bit, in terms of hardware, for example by a flip-flop. The quota counters can then also be combined to form a vector with N bits and implemented, for example, by a register of length N. A set bit can then indicate an existing quota, for example, and a bit that is not set can indicate a missing quota.

6 shows the basic structure of the core of an embodiment for a comparator unit 13. This comprises an N-stage priority encoder 23, the behavior of which can be described as follows: Each output 0 _± (l≤i≤N) is set to logic ONE , if all previous inputs Iχ- _{1 are} at logic ZERO and the associated input I _{x is} at logic ONE. In other words, only that output is set to logical ONE whose associated input is the first to be logical ONE in the order of the N stages of the priority encoder.

6 shows only the first four stages A, B, C, D, of the priority encoder 23 with the input states a, b, c, d and logic connections which generate the corresponding output states.

The inputs I _{x of} the individual stages of the priority encoder 23 are each connected to the output of an AND gate 25, which logically AND-links three signals, namely the respective bit CRreq [i] of the CRreq vector, the respective bit CRres [i] of the occupancy vector Crres supplied to the comparator unit 13 and the output of the respective quota counter 21. Thus, the desired goal is achieved that the respective bit of the occupancy vector is only occupied if it was still empty and if a corresponding cell closed is transferred and at the same time an assignment authorization is given.

The control unit 11 can receive a start pulse CR _3ta rt for starting a contention resolution cycle. The checking of the occupancy authorization, including the generation of the authorization information CRgnt, if necessary, can be carried out cyclically for security reasons. In this case, for example, only the actions required in one comparator unit 13 are carried out in one clock cycle. The processed CRres vector can then be transferred to the next comparator unit of the cascade using an output register (not shown).

Let there be the switching times of the individual components

Signal propagation times etc., several comparator units 13 can also be combined. For this purpose, in the embodiment according to FIG. 6, the outputs of the priority encoder 23 of a comparator unit 13 are each connected directly to the inputs, for example the relevant inputs of the AND gates 25. With this measure, the actions of several or even all of the comparator units can be processed within one clock cycle, as a result of which an enormous increase in processing speed can be achieved.

LIST OF REFERENCE NUMBERS

I switching device 3 port unit (3 _x 3 _N )

5 central switching unit

7 ports of the port units (7 _X to 7 _n )

8 Collision resolution unit (contention resolution unit)

9 buffer memory

9a virtual buffer memory

II control unit

13 comparator unit (13ι to 13 _N )

15 permutation unit (15ι to 15 _N )

16 counters

17 connecting lines

19 inverse permutation unit (19χ to 19 _N )

21 odds counter

23 priority encoder

25 AND gates

a, b, c, d logic states

A, B, C, D Levels 1 to 4 of the priority encoder

I _x , Oi inputs and outputs of the priority encoder

(L≤i≤N)

CRgnt authorization information

CRreq contention request vector,

Availability information

CRres occupancy vector

CRsart start signal for contention resolution cycle

N number of port units

Port IF interface units in 5

CB-IF interface unit in 3

LVDS low voltage differential signaling

S _{1: J} signals at ports 7 (indices i, j)

Claims

claims

1. cell conflict resolution unit for a device for switching a plurality of packet-oriented signals,

a) wherein the switching device (1) consists of a central switching unit (5) and a maximum of N port units (3) connected to it, each with n ports (7), to each of which a signal can be fed,

b) the cell conflict resolution unit (8) has N inputs, each of which can be supplied with an availability vector (CRreq) with availability information from one of the N port units (3), which contain whether and to which other port units (3) a packet of a signal or a cell of a segmented packet of a signal is to be transmitted,

each Verfugbarkeitsvektor (CRreq) each have a comparator unit (13) of a cascade of N comparator units (13ι to 13 _N) can be fed to, which are connected to a control unit (11), and

d) wherein each comparator unit (13) using the respective availability vector (CRreq), an occupancy information (CRres) generated by the respective previous comparator (13) or the control unit (11) in relation to the transmission of the respective

Packet or the respective cell to the port units and using a selection authorization information for the transmission of the respective packet or the respective cell to the port units (3) an authorization information (CRgnt) is determined and transmitted to the port unit (3) connected to it, which contains, to which other port unit (3) the with the respective comparator unit (13) connected port unit (3) is authorized to transmit a corresponding packet or a corresponding cell, as a result of which a non-blocking combination of packets or cells which can be transmitted simultaneously between the port units (3) is determined,

e) the occupancy information (CRres) generated by a comparator unit (13) in each case parallel to the next in the form of an occupancy vector (CRres)

Comparator unit (13) and processed in the comparator units in parallel or semi-parallel.

2. Cell conflict resolution unit according to claim 1, wherein the processing of the occupancy vector (CRres) and the transfer of the occupancy vector (CRres) between the comparator units (13) is carried out in a clocked manner, the occupancy vector (CRres) in at least one comparator unit (13) in each clock cycle. processed and made available for transfer to the following comparator unit (13).

3. Cell conflict resolution unit according to claim 2, in which the occupancy vector (CRres) is processed in several or all comparator units (13) in each clock cycle.

4. Cell conflict resolution unit according to one of the preceding claims, in which each availability vector (CRreq) has N bits, the position of a bit in the availability vector (CRreq) including the assignment of the information contained in this bit to a specific port unit (3) and wherein the one logical state of the bit signals the availability of a packet or a cell intended for the relevant port unit (3) and the other logical state indicates the lack of availability of a packet or a cell.

5. Cell conflict resolution unit according to one of the preceding claims, in which the occupancy vector (CRres) has N bits, the position of a bit in the occupancy vector (CRres) including the assignment of the information contained in this bit to a specific receiving port unit (3), and wherein the a logical state of the bit signals the occupancy of the relevant port unit (3) for receiving a packet or a cell from another port unit (3) and the other logical state indicates the readiness of the relevant port unit.

6. Cell conflict resolution unit according to claim 5, in which the control unit (11) transfers an initial occupancy vector (CRres) to the first comparator unit (13 _x ) of the cascade of N comparator units (13).

7. The cell conflict resolution unit as claimed in claim 6, in which those bits of the occupancy vector (CRres) which correspond to those port units (3) which are not available for reception or are not available are preset with the corresponding logic state.

8. Cell conflict resolution unit according to one of the preceding claims, in which each comparator unit (13) contains the authorization information for the relevant port unit

(3) determined in a predetermined order with respect to the port units (3) or the individual bits of the occupancy vector (CRres).

9. Cell conflict resolution unit according to claim 8, in which the sequence at the beginning of a cycle of determining the authorization information (CRgnt) is selected by the N comparator units (13) from a predetermined number of pseudo-randomly generated sequences.

10. Cell conflict resolution unit according to one of claims 1 to 8, in which each comparator unit (13) determines a possible assignment of bits of the assignment vector (CRres) in the order of the bits of the assignment vector (CRres), in which each comparator unit (13) has a permutation unit (15) is connected upstream, to which the availability vector (CRreq) can be supplied and which rearranges the order of the bits of the availability vector (CRreq) in accordance with a specified regulation and in which each comparator unit (13) is followed by an inverse permutation unit (19) is which, taking into account the permutation of the sequence of the bits of the availability vector (CRreq) from the information supplied to it by the comparator unit (13), whether and which position of the occupancy vector (CRres) was occupied, which authorization information (CRgnt) is assigned to the the relevant comparator unit (13) connected port unit (3) is to be transmitted.

11. Cell conflict resolution unit according to one of the preceding claims, in which the selection authorization for the transmission of the respective packet or the respective cell to a different port unit (3) in each comparator unit (13) by N1 for each of the other N1 port units (3) or by N provided for each bit of the occupancy vector (CRres) quota payer (21), the payer status (quota) of a quota payer (21) after each selection of the assigned port unit (3) or after each occupancy of the associated bits of the occupancy vector (CRres) is incremented or decremented and when a predetermined number of payer is reached, the selection authorization for the relevant port unit (3) or the occupancy authorization for the relevant bit of the occupancy vector (CRres) is blocked.

12. Cell conflict resolution unit according to claim 11, in which the quota numbers (21) of a comparator unit (13) are each assigned to a specific bit of the occupancy vector (CRres) and in which the control unit (11) all quota numbers (21) of all comparator units (13) are assigned to a specific bit of the occupancy vector (CRres), sets to an initial value (initial quota) if there is no longer a comparator unit (13) in which the relevant quota payer (21) still has a quota and at the same time the relevant bit of the permuted availability vector (CRreq ^* ) e indicates the packet or cell to be transferred.

13. Cell conflict resolution unit according to claim 11, in which the quota counters (21) of a comparator unit (13) are each assigned to a specific port unit (3) and in which the control unit (11) all quota counters (21) of all comparator units (13) that a specific one Port unit (3) are assigned an initial value (initial quota) if there is no longer a comparator unit (13), which quota payer in question (21) still has a quota and at the same time has a packet or a cell from which the comparator unit ( 13) connected port unit is to be transferred to the relevant port unit.

14. The cell conflict resolution unit according to claim 13, in which the comparator units (13) are supplied with the permutation information, in which the comparator units (13) permute the quota numbers and the information as to whether a cell is available for transmission is taken from the permuted availability vectors CRreq *.

15. The cell conflict resolution unit as claimed in one of claims 12 to 14, in which one or more quota payers (21) are assigned a higher initial quota than other quota payers (21).

16. Cell conflict resolution unit according to one of the preceding claims, in which the comparator units (13) each have an N-stage Pπority encoder (23), each of the N inputs (Ii to I _N ) of the priority encoder (23) with the output an AND gate (25) is connected and a corresponding input (CRreq [ι]) of the availability vector or the permuted availability vector (CRreq * [ι]) is fed to a first input of the AND gate, a second input of the AND Gates (25) the relevant bit of the occupancy vector (CRres [l]), which is present at the output of the preceding comparator unit (13) and a third input of the AND gate (25) the information of the associated quota number (21), which is logically ONE if there is another

Authorization to select is given, and logically NULL if there is no longer an authorization to select.

17. Cell conflict resolution unit according to one of the preceding claims, which is designed as an integrated circuit.

18. Central switching device with N ports for connecting a maximum of N port units (3), which is designed as an integrated circuit that contains a cell conflict resolution unit (8) according to one of Claims 1 to 14.