Abstract:
The invention relates to a crossbar switch controller including an input terminal configured to receive a set of service request signals from a set of virtual output queues each comprising a set of packets. The invention also includes a matrix circuit coupled to the input terminal and configured to represent the set of service request signals in the form of a matrix, wherein each service request signal is described by a row position M and a column position N. The invention further includes an output terminal configured to receive a portion of the set of packets during an epoch, an arbiter circuit configured to iteratively scan the matrix during the epoch and issue the set of grant signals to the virtual output queues to determine which service requests are granted, and an arbiter controller configured to initiate the arbiter circuit with an array of non-conflicting matrix elements. Whereby, the arbiter circuit scans the matrix during a first epoch, issues the set of grant signals, allows the set of granted service requests to substantially complete, and if necessary, scans the matrix during subsequent epochs. The invention also relates to a crossbar switch controller including an arbitration pre-processor coupled to the input terminal and the matrix circuit, and configured to represent the set of service request signals in the form of a mapping matrix, and further configured to transform a first mapping position of the service request signal to a second mapping position based, in part, on a mapping algorithm. The invention also includes an arbitration post-processor coupled to the output terminal and the matrix circuit, and further configured to transform the second mapping position of the service request signal back to the first mapping position.

Description:
REFERENCE TO RELATED APPLICATIONS  
       [0001]    This application claims priority to U.S. Prov. No. 60/333,945, filed Nov. 20, 2002, incorporated herein by reference. 
     
    
     
       FIELD  
         [0002]    The invention relates to the field of telecommunications, and more particularly to an advanced telecommunications router and crossbar switch controller.  
         BACKGROUND  
         [0003]    Advances in network communication and switching are moving ahead with great speed. The advent of optical network connections requires the evolution of network switching technologies that can perform at high rates.  
           [0004]    Conventional technology requires a very large number of devices to achieve the high rates and does not provide support for future high data rate switching needs. One of the hindrances of conventional technology is the use of the crossbar switch and associated algorithms for setting the switch. Crossbar switch technology is relatively simple in theory, but can be very complicated to optimize since for each piece of data, there can be a number of switches that need to be set and those switches may conflict with transmission of another piece of data. Some people have attempted to develop techniques that can provide support for high data rates, for example, U.S. Pat. No. 5,734,649 describes a crossbar switch algorithm that attempts to optimize the decision tree, and U.S. Pat. No. 5,500,858 describes another technique. However, such techniques do not provide sufficient bandwidth for future needs.  
           [0005]    What are needed are an advanced telecommunications router and crossbar switch controller that is capable of performing at a level consistent with optical network systems.  
         SUMMARY  
         [0006]    The invention overcomes the identified limitations and provides an advanced telecommunications router and crossbar switch controller. A conventional crossbar switch includes a number of input ports that are switched to a number of output ports. The switches are located at the cross-points of a number of wires. Since the crossbar switch has a large number of paths that the data can flow through to get to its destination, the switches are set in advance of transferring the data. The mechanism for setting the switches is called an arbiter. The invention provides a highly efficient arbiter that includes a number of new technologies for improving speed and switch selection. By servicing the signals in a very efficient manner, the invention supports very high throughput by the router.  
           [0007]    In one embodiment, the invention relates to a crossbar switch controller including an input terminal configured to receive a set of service request signals from a set of virtual output queues each comprising a set of packets. The invention also includes a matrix circuit coupled to the input terminal and configured to represent the set of service request signals in the form of a matrix, wherein each service request signal is described by a row position M and a column position N. The invention further includes an output terminal configured to receive a portion of the set of packets during an epoch, an arbiter circuit configured to iteratively scan the matrix during the epoch and issue the set of grant signals to the virtual output queues to determine which service requests are granted, and an arbiter controller configured to initiate the arbiter circuit with an array of non-conflicting matrix elements. Whereby, the arbiter circuit scans the matrix during a first epoch, issues the set of grant signals, allows the set of granted service requests to substantially complete, and if necessary, scans the matrix during subsequent epochs.  
           [0008]    In another embodiment, the invention relates to a crossbar switch controller including an arbitration pre-processor coupled to the input terminal and the matrix circuit, and configured to represent the set of service request signals in the form of a mapping matrix, and further configured to transform a first mapping position of the service request signal to a second mapping position based, in part, on a mapping algorithm. The invention also includes an arbitration post-processor coupled to the output terminal and the matrix circuit, and further configured to transform the second mapping position of the service request signal back to the first mapping position.  
           [0009]    In another embodiment, the invention relates to a method of optimizing a crossbar switch controller. The method further includes configuring an input terminal to receive a set of service request signals from a set of virtual output queues each comprising a set of packets. The method also includes coupling a matrix circuit to the input terminal, configuring the matrix circuit to represent the set of service request signals in the form of a matrix, and coupling an output terminal to the matrix circuit. The method further includes configuring the output terminal to receive a portion of the set of packets during an epoch, coupling an arbiter circuit to the matrix circuit, and configuring the arbiter circuit to iteratively scan the matrix during the epoch and issue the set of grant signals to the virtual output queues to determine which service requests are granted. The method further includes coupling an arbiter controller to the arbiter circuit, configuring the arbiter controller to initiate the arbiter circuit with an array of non-conflicting matrix elements, scanning the matrix during a first epoch, and issuing the set of grant signals. The method further includes allowing the set of granted service requests to substantially complete; and if necessary, scanning the matrix during subsequent epochs.  
           [0010]    Advantages of the invention include the ability to manage high data rates using a crossbar switch, as well as improving arbitration fairness without substantial detriment to crossbar switch performance. 
       
    
    
     BRIEF DESCRIPTION OF THE FIGURES  
       [0011]    The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:  
         [0012]    [0012]FIG. 1 depicts a crossbar switch for telecommunications switching, such as would be deployed in an Internet router, showing a set of virtual output queues, a switch matrix, a set of output queues and an arbiter according to an embodiment of the invention;  
         [0013]    FIGS.  2 A-F illustrate a matrix of ready virtual output queues according to an embodiment of the invention, and an example of an iterative examination of wavefronts;  
         [0014]    [0014]FIG. 3A is a flowchart showing steps performed during the arbitration and data transfer cycles according to an embodiment of the invention;  
         [0015]    [0015]FIG. 3B is a timeline showing the steps of FIG. 3A performed over time;  
         [0016]    [0016]FIG. 4A depicts an arbiter circuit according to an embodiment of the invention;  
         [0017]    [0017]FIG. 4B depicts an arblet circuit according to an embodiment of the invention;  
         [0018]    [0018]FIG. 4C depicts the internal circuitry of an arblet according to an embodiment of the invention;  
         [0019]    FIGS.  5 A-D depict a simplified matrix of arblets in a crossbar switch according to an embodiment of the invention;  
         [0020]    [0020]FIG. 6 depicts a crossbar switch with the addition of an arbitration pre-processor and an arbitration post-processor according to an embodiment of the invention;  
         [0021]    FIGS.  7 A-D depict a simplified matrix of virtual output queues for an arbitration-preprocessor employing a rotation mapping algorithm according to an embodiment of the invention;  
         [0022]    [0022]FIG. 7E depicts a simplified functional logic diagram for arbitration-preprocessor employing a rotation mapping algorithm according to an embodiment of the invention;  
         [0023]    [0023]FIG. 8 depicts a simplified functional logic diagram for an arbitration-preprocessor employing a hierarchical mapping algorithm according to an embodiment of the invention;  
         [0024]    FIGS.  9 A-D depict a simplified matrix of virtual output queues for an arbitration-preprocessor employing a hierarchical mapping algorithm according to an embodiment of the invention; and,  
         [0025]    [0025]FIG. 10 depicts a simplified functional logic diagram for an arbitration-preprocessor employing a switch network mapping algorithm according to an embodiment of the invention. 
     
    
     DETAILED DESCRIPTION  
       [0026]    The invention is described with reference to specific architectures and protocols. Those skilled in the art will recognize that the description is for illustration and to provide the best mode of practicing the invention. The description is not meant to be limiting. For example, reference is made to Internet Protocol, but any packet protocol is applicable. Moreover, reference is made to chips that contain integrated circuits while other hybrid or meta-circuits combining those described in chip form is anticipated. The exemplary embodiment is provided for a 5×5 switch, but could be any other number consistent with switch technology.  
       A. Crossbar Switch Architecture and Method  
       [0027]    [0027]FIG. 1 depicts a crossbar switch  100  for telecommunications switching, such as would be deployed in an Internet router. The heart of the switch  100  is the crossbar circuitry  110  (sometimes called a switch matrix), which is comprised of a series of rows and columns with switches at the intersections thereof. A set of virtual output queues  120  (VQ- 11  to VQ-MN) are coupled to external data sources and buffer the data to be transferred by the crossbar circuitry  110 . The switch matrix may often be square (M=N), but is not required to be so. A set of output queues  130  are also coupled to the crossbar circuitry and are designed to transfer the outbound data to external circuits. A controller  140  is coupled to the virtual output queues and the switch matrix. Each data transfer is performed during a period of time called an epoch, and the switch is typically set up during the epoch immediately preceding the data transfer.  
         [0028]    FIGS.  2 A-F illustrate a matrix of ready virtual output queues according to an embodiment of the invention. This is referred to as a request matrix. FIG. 2A represents the matrix of virtual output queue service requests. The squares designated as 1 are those making a service request and those designated at 0 are not. A goal of the invention is to set the switch matrix to allow the most data to pass through the switch while preventing data collisions. In order to do this, the invention employs a method that determines non-conflicting data transfer requests and then grants the requests. A request that would conflict prior grant is denied until a subsequent epoch.  
         [0029]    [0029]FIG. 3A is a flowchart showing steps performed during the arbitration and data transfer cycles according to an embodiment of the invention. FIG. 3 will be explained in conjunction with FIGS.  2 B- 2 F. In step  320 , the data is buffered at the virtual output queues and is ready to be transferred by the switch  100 . In step  322 , the controller selects a first group of squares to be tested (called a wavefront). The selection can be made arbitrarily, or based on available information such as the wavefront with the most requests, or other technique. In step  324 , the first wavefront W 0  is tested. Referring to FIG. 2B, the first wavefront W 0  is a group of squares (A 1 , B 2 , C 3 , D 4 , E 5 ). Note that these squares do not share a column or row with one another, which means that granting any request in this group would not cause a data collision. Each square of a wavefront is examined independently and in parallel. In this case, squares C 3  and D 4  are identified as having a 1 in them so the requests will be granted for their respective virtual output queues. In step  326 , the next wavefront (W 1 ) is tested corresponding to FIG. 2C. Note that the group in FIG. 2C also does not have any rows or columns in common. In this case, squares A 2  and E 1  are identified as having a 1 in them so the requests will be granted for their respective virtual output queues. In steps  326  to  328 , the other wavefronts up to WN- 1  are tested. Note that in FIG. 2D, square C 5  is not granted because square C 3  was granted in wavefront W 0  and granting square C 5  would cause a data collision. FIG. 2E tests the next wavefront and identifies square B 5  as having a 1 and not conflicting with any of the previously granted squares. Therefore, the request will be granted for square B 5 . FIG. 2F does have a 1 in square B 1 , but issuing a grant would conflict with square E 1 , which was previously granted.  
         [0030]    Step  330  then compiles the signals from the arbiter login and provides a grant signal to the virtual output queues at the appropriate time to allow the data into the switch matrix  110 . The grant signals is comprised of a number of grant signals i,j representing the row and column of the input port and desired output port. Step  332  represents the data transfer through the switch  100 .  
         [0031]    [0031]FIG. 3B shows the timing of the epochs and the loopback effect from step  330  to step  322 . For each epoch, A represents the decision period and B represents the data transfer period. Since it would be unfair to choose the same initial wavefront W 0 , an aspect of the invention provides that the initial wavefront for a subsequent epoch can be different. For example, referring back to FIGS.  2 A-F, the next epoch might use the FIG. 2C square group as the initial wavefront, then the FIG. 2D square group and so on. This is called a round robin technique. Another technique would be a random selection of the wavefronts represented in FIGS.  2 C-F. Yet another technique would be to determine the array of non-conflicting matrix elements for an epoch P based at least in part on an earlier epoch P-x, where x is a natural number. For example, in testing the first request matrix of FIG. 2A, the controller may learn that there are a number of requests in a certain group that exhibit certain favored characteristics and the controller may then select that wavefront as the initial wavefront.  
       B. Controller and Arbitration Circuitry  
       [0032]    [0032]FIG. 4A depicts an arbiter circuit according to an embodiment of the invention. The arbiter is part of the controller  140  shown in FIG. 1. In the exemplary embodiment, the arbiter  400  has the same dimensions as the switch matrix and request matrix (M×N). As shown, the arbiter includes a number of elements called arblets  450 - 11  to  450 - ij,  which are arranged in rows and columns (i,j) matching the M×N matrix, and which make the grant decisions and issue signals within the arbiter that form the controller&#39;s grant signal. Each arblet includes row input and a row output, a column input and a column output, and a data input and grant output. The controller grant signal is comprised of the collection of arblet grant outputs.  
         [0033]    Note that FIG. 4A shows a set of arblets with their row and column inputs disconnected from the other arblets ( 450 - 1 , 1 ,  450 - 2 , 2 ,  450 - 3 , 3  . . .  450 - i,j ). This represents the logical circuit according an initial wavefront W 0  such as shown in FIG. 2B, and not necessarily the physical structure of the arbiter  400 . Additionally, note that a set of arblets  450 - 1 , 1  . . .  4501 , j  appear to send their output signals to terminals along the top side of FIG. 4A and that a set of arblets  450 - i , 1  . . .  450 - i,j  appear to send their output signals to terminals along the right side of FIG. 4A. Also note that a set of arblets  450 - 2 , 1  . . .  450 - i , 1  appear to receive their input signals from the left side of FIG. 4A and that a set of arblets  450 - i , 1  . . .  450 - i,j  appear to receive their input signals from the bottom side of FIG. 4A. In one aspect of the invention, the arblets are connected to one another by the outputs along the right side of FIG. 4A matching with the inputs along the left side of FIG. 4A, and the outputs along the top side of the FIG. 4A matching with the inputs along the bottom side of FIG. 4A.  
         [0034]    [0034]FIG. 4B depicts an arblet  450  (which is an arbitrary arblet) according to an embodiment of the invention. As shown, the arblet i,j has a row input called Row_i_Busy and a column input Col_j_Busy. The arblet also has a data input D_i_j that represents the data from the request matrix square corresponding to the arblet  450  at position i,j. The arblet generates a signal M_i_j depending on these inputs, according to the following table (x is don&#39;t care).  
                                                           Row_j_Busy   Column_j_Busy   D_i_j   M_i_j                           0   0   0   0           0   0   1   1           1   x   x   0           x   1   x   0                      
 
         [0035]    The output signals Row_i_Busy and Col_j_Busy are the same as their input values ORed with the M_i_j signal. That is, when Row_i_Busy, Col_j_Busy or M_i_j are 1, then the output signals Row_i_Busy and Col_j_Busy become 1.  
         [0036]    The signals propagate through the arbiter circuit  400  through all the arblets. When an arblet decides to grant a virtual output queue access to the switch matrix (M_i_is 1), the remainder of the signals in the same row and column are 1. This avoids data conflict in the switch matrix  110 .  
         [0037]    Once the request matrix has been evaluated by the arbiter, the controller sets to the switches in the switch matrix and issues the grant signal to the virtual output queues. Then data is safely sent through the switch matrix while the request matrix for the next epoch is evaluated.  
         [0038]    As shown in FIG. 4A and described above, the arbiter circuit  400  has the outputs from the right side connected to the inputs at the left, and the outputs from the top side connected to the inputs at the bottom. While this is one potential configuration, there are others. One physical configuration is called a donut, and as the name implies, provides a loopback for the output signals from a set of arblets to the input to another set of arblets.  
         [0039]    [0039]FIG. 4C depicts two slightly different arblets  450   a  and  450   b.  The Row Busy and Column Busy signals propagate from one arblet to the next. To run the arblet at a high speed, the propagation delay of the row (column) busy should be minimized. A review of a typical logic library (example used IBM CU- 11  process) identified two types of gates. AOI and OAI gates are the fastest among all standard gates and have the correct logical function. However, due to the logical inverter at the output of the AOI and OAI gates, they are arranged alternately to cancel out the inverter effect. As a result, two types of arblets are designed: type  0  ( 450   a ) and type  1  ( 450   b ). They are used in a checkerboard fashion, where type  0  arblets are used in the white squares and type  1  arblets are used in the black ones.  
         [0040]    In accordance with another embodiment of the present invention, an arbitration pre-processor is employed to optimize fairness. In general, fairness represents a measure of average resource utilization in comparison to resource demand. In the current invention, fairness refers to the probability that any given arblet will be granted access to a specific output port. In a fair implementation, for example, all arblets would substantially have the same probability of a grant access.  
         [0041]    Referring now to FIGS.  5 A-D, a simplified matrix of arblets in a crossbar switch is illustrated, each with four rows  502  coupled to virtual output queues, and four columns  504  coupled to corresponding output ports. As commonly implemented, the arbiter will arbitrate a wavefront in the same direction  505  during each epoch, normally along a diagonal  505 . This is commonly done to optimize arbitration performance, since varying the wavefront arbitration direction can also substantially increase functional complexity within the arbiter, requiring more logic processing steps. In FIG. 5A, the arbiter begins wavefront arbitration along diagonal  506 , from element  00  to element  33 . In FIG. 5B, the arbiter moves the wavefront to diagonal  508 , from element  01  to element  30 . In FIG. 5C, the arbiter moves the wavefront again to diagonal  510 , from element  02  to element  31 . And finally, in FIG. 5D, the arbiter moves the wavefront to diagonal  512 , from element  03  to element  32 . In this implementation, elements in the initial diagonal  506  will tend to be evaluated first, and hence will be given priority over other elements in the matrix. For example element  00  will always be evaluated before element  01 , and hence will unfairly be given a higher probability of accessing an output port.  
         [0042]    Referring now to FIG. 6, the crossbar switch  500  of FIGS.  5 A-D is shown, with the addition of an arbitration pre-processor  604  and an arbitration post-processor  608 . In a non-obvious fashion, arbitration pre-processor  604  substantially improves the fairness of crossbar switch  500 , by successively re-mapping the virtual output queues  602  to new non-conflicting positions in a mapping matrix, based in part, on a pre-defined mapping algorithm implemented as a series of coupled nodes or logic switches. Crossbar switch  500 , unaware of any change, arbitrates these re-mapped virtual output queues in a normal fashion, and then passes the results to arbitration post-processor  608 , which subsequently re-maps the granted virtual output queues to the appropriate output ports  610 . Furthermore, the pre-defined mapping algorithm can be further configured during crossbar switch  500  operation through the use of mapping algorithm inputs. Advantages of the invention include improving arbitration fairness without substantial detriment to arbiter performance.  
         [0043]    Referring now to FIGS.  7 A-D, a simplified matrix of virtual output queues for arbitration-preprocessor  604  of FIG. 6 is shown, in which a rotation mapping algorithm is employed. Based on the mapping algorithm inputs, rotation mapping algorithm re-maps the virtual output queues  702 , so that wavefront arbitration begins along a different diagonal from the original un-mapped matrix. Referring to FIG. 7A, an un-mapped matrix is shown, in which the arbiter will begin wavefront arbitration along diagonal  706 , from element  00  to element  33 , as in FIG. 5. Referring now to FIG. 7B, the rotation mapping algorithm has re-mapped the virtual output queues so that wavefront arbitration begins along diagonal  708 , from element  01  to element  30 , which is one column offset position to the right of diagonal  706 . Referring now to FIG. 7C, the rotation mapping algorithm has re-mapped the virtual output queues so that wavefront arbitration begins along diagonal  710 , from element  10  to element  03 , which is one row offset position below of diagonal  706 . And referring now to FIG. 7D, the rotation mapping algorithm has re-mapped the virtual output queues so that wavefront arbitration begins along diagonal  712 , from element  11  to element  00 , which is both one row offset position below and column offset position to the right of diagonal  706 . Using the rotation mapping algorithm, for example, up to n statistical combinations can be achieved, where n is the number of virtual output ports. Advantages of the invention include improving arbitration fairness by periodically allowing each virtual output queue be positioned along the initial arbitration wavefront diagonal.  
         [0044]    Referring now to FIG. 7E, a simplified functional logic diagram for arbitration-preprocessor  604  of FIG. 6 is shown, in which a rotation mapping algorithm is employed. Twenty-four logical mux elements  730  are coupled together, with a stage  0  comprising elements  730   a - h,  stage  1  comprising elements  730   i - p,  and stage  2  comprising elements  730   q - x.  Mapping algorithm inputs are shown as c 0 , c 1 , and c 2 , while row or column positions of virtual output queues are shown as inputs  0  or  1  to switches  810   a - h.  Initially in stage  0 , each virtual output queue is coupled to input  0  of a mux element, and input  1  of a mux element that is four positions away. For example, virtual output queue  0  is coupled to input  0  of mux element  730   a,  and input  1  of mux element  730   e,  four positions away. At stage  1 , the output of each mux element of stage  0 , is further coupled to input  0  of a mux element, and input  1  of a mux element that is two positions away. For example, the output from mux element  730   e  is coupled to input  0  of mux element  730   m,  and input  1  of mux element  730   k,  two positions away. And at stage  2 , the output of each mux element of stage  1 , is further coupled to input  0  of a mux element, and input  1  of a mux element that is one position away. For example, the output from mux element  730   k  is coupled to input  0  of mux element  730   s,  and input  1  of mux element  730   r,  one position away.  
         [0045]    In another aspect of the current invention, the arbitration-preprocessor implements a hierarchical mapping algorithm. In one embodiment, a binary tree topology is used. The hierarchical mapping algorithm subsequently re-maps the row or column position of virtual output queues in stages, into successively smaller groups, based on the mapping algorithm inputs. For example, the hierarchical mapping algorithm initially divides the virtual output queue into two halves. If the mapping algorithm input is true at this stage, the row or column position of each element the first group is swapped with the row or column position of the corresponding element of the second group (i.e., the first element in the first group with the first element in the second group, etc.) Each of these groups is then further divided into two smaller groups, and the process is again repeated. Furthermore, the hierarchical mapping algorithm can also allow arbitration pre-processor  604  to swap both row and column position by first processing for one and then subsequently processing for the other.  
         [0046]    Referring now to FIG. 8, a simplified functional logic diagram for arbitration-preprocessor  604  of FIG. 6 is shown, in which a hierarchical mapping algorithm is employed. Four logical switches  810  are coupled together, with a stage  0  comprising switches  810   a - b,  and a stage  1  comprising switches  810   c - d.  Mapping algorithm inputs are shown as c 0 , c 1 , and c 2 , while row or column positions of virtual output queues are shown as inputs  0 - 3  to switches  810   a - b . Initially in stage  0 , inputs  0 - 3  are divided between switches  810   a - b,  with inputs  0  and  2  coupled to switch  810   a,  and inputs  1  and  3  coupled to switch  810   b.  If mapping algorithm input c 0  is true, then no mapping occurs since input  0  and  1  are forwarded to switch  810   c,  and input  2  and  3  are forwarded to switch  810   d.  That is, the two halves of  0 - 1  and  2 - 3  remain in the original sequence of  0 - 3 . If mapping algorithm input c 0  is false, input  2  and  3  are forwarded to switch  810   c,  and input  0  and  1  are forwarded to switch  810   d,  mapping each half&#39;s row or column position to that of the other. At stage  1 , the process is repeated. However, at this stage, there are two independent mapping algorithm inputs as opposed to just one, as in the previous stage. Subsequent stages can have 2 n  mapping algorithm inputs, where n is the stage number.  
         [0047]    Referring now to FIGS.  9 A-D, a simplified matrix of virtual output queues for arbitration-preprocessor  604  of FIG. 6 is shown, employing a hierarchical mapping algorithm. Based on the mapping algorithm inputs, rotation mapping algorithm re-maps the virtual output queues  902  to change the relative position of virtual output queues to each other, as compared to the original un-mapped matrix. Referring to FIG. 9A, an un-mapped matrix is shown, in which the arbiter will begin wavefront arbitration along diagonal  906 , comprising elements  00 ,  11 ,  22 ,  33  to element  33 , as in FIG. 5. Referring now to FIG. 9B, the hierarchical mapping algorithm has re-mapped the virtual output queues by rows so that wavefront arbitration begins along a new diagonal  908 , comprising elements  10 ,  01 ,  32 , and  23 . Referring now to FIG. 9C, the hierarchical mapping algorithm has re-mapped the virtual output queues by columns so that wavefront arbitration begins along a new diagonal  910 , comprising elements  01 ,  10 ,  23 , and  32 . And referring now to FIG. 9D, the hierarchical mapping algorithm has re-mapped the virtual output queues by both rows and columns, so that wavefront arbitration begins along a new diagonal  912 , comprising elements  01 ,  00 ,  33 , and  22 . Using a binary tree topology, for example, up to 2 n-1  statistical combinations can be achieved, where n is the number of virtual output ports. Advantages include improving arbitration fairness by increasing the possible nonconflicting combinations available for changing the relative position of individual elements within virtual output queues.  
         [0048]    In another aspect of the current invention, an arbitration-preprocessor implements a switch network mapping algorithm. In one embodiment, the switch network mapping algorithm uses a butterfly topology. Furthermore, the switch network mapping algorithm remaps pairs of element row or column positions within virtual output queues, in stages based on mapping algorithm inputs. For example, the switch network mapping algorithm initially pairs every element with another element. If the mapping algorithm input is true at this stage, the row or column position of each element is swapped. The process is again repeated until desired The switch network mapping algorithm can also allow arbitration pre-processor  604  to swap both row and column position by first processing in one and then subsequently processing the other. Unlike the hierarchical mapping algorithm, as shown in FIG. 8, the switch network mapping algorithm can have n number mapping algorithm inputs per stage, where n is half the number of coupled virtual output queues. For example, eight virtual output queues can require four mapping algorithm inputs per stage.  
         [0049]    Referring now to FIG. 10, a simplified functional logic diagram for arbitration-preprocessor  604  of FIG. 6 is shown, employing a switch network mapping algorithm. Twelve logical switches  1010  are coupled together using a butterfly topology, with each stage comprising four switches. Furthermore, each switch utilizes a different mapping algorithm input. For example, the first output port of switch  1010   a  is coupled to the first input port of switch  1010   c.  While the second output port of switch  1010   a  is coupled to the second input port of switch  1010   d.  Furthermore, the first output port of switch  1010   b  is coupled to the first input port of switch  1010   c.  While the second output port of switch  1010   b  is coupled to the second input port of switch  1010   c.  Mapping algorithm inputs are shown as c 0  for switch  1010   a,  c 2  for  1010   b,  c 4  for switch  1010   c,  and c 6  for switch  1010   d.  Initially in the first stage, if mapping algorithm input c 0  of switch  10101   a  is true, then input  0  is forwarded to switch  1010   c,  and input  1  is forwarded to switch  1010   d.  If mapping algorithm input c 0  of switch  10101   a  is false, then the reverse happens, input  1  is forwarded to switch  1010   c,  and input  0  is forwarded to switch  1010   d.  Likewise, if mapping algorithm input c 2  is true, then input  4  is forwarded to switch  1010   d,  and input  5  is forwarded to switch  1010   c.  If mapping algorithm input is false, then the reverse happens, input  5  is forwarded to switch  1010   d,  and input  4  is forwarded to switch  1010   c . This process is repeated for each switch in each stage of arbitration-preprocessor  604 . Using a butterfly topology, for example, up to 2 n/2logn  statistical combinations can be achieved, where n is the number of virtual output ports. Advantages include improving arbitration fairness by substantially increasing the possible non-conflicting combinations available for changing the relative position of individual elements within virtual output queues.  
       C. Conclusion  
       [0050]    Advantages of the invention include the ability to manage high data rates using a crossbar switch, as well as improving arbitration fairness without substantial detriment to crossbar switch performance.  
         [0051]    While this invention has been described in terms of several preferred embodiments, there are alterations, permutations, and equivalents which fall within the scope of this invention. For example, although reference is given to binary tree and butterfly topologies, it should be understood that other topologies can be used. It should also be noted that there are many alternative ways of implementing the apparatuses of the present invention. It is therefore intended that the following appended claims be interpreted as including all such alterations, permutations, and equivalents as fall within the true spirit and scope of the present invention.  
         [0052]    Having disclosed exemplary embodiments and the best mode, modifications and variations may be made to the disclosed embodiments while remaining within the subject and spirit of the invention as defined by the following claims.