Apparatus and Method to Switch Packets Using a Switch Fabric With Memory

Abstract

Packets having at least one cell are switched using input queues, output queues, a switch fabric, and a controller. Each input queue stores cells to be switched, and each output queue stores switched cells. The switch fabric couples the input queues to the output queues and has memory. The switch fabric stores cells moved from the input queues to the switch fabric and stores cells based on the output queues. The controller couples to the input queues and the switch fabric and determines input priorities for cells moving from the input queues to the switch fabric and output priorities for cells moving from the switch fabric to the output queues.

What is claimed is: 
     
         1 . An apparatus to switch packets, each packet including at least one cell, the apparatus comprising:
 a switch fabric having memory; and   a controller coupled to the switch fabric, the controller configured to determine input priorities for cells moving to the switch fabric and output priorities for cells moving from the switch fabric, the controller further configured to update flow-control state information of the switch fabric based on whether or not a cell exists in the memory of the switch fabric with a lower time-to-leave (TTL) than all queued cells being regulated by the flow-control state information.   
     
     
         2 . The apparatus of  claim 1 , further comprising:
 a plurality of input queues, each input queue configured to store cells to be switched; and   a plurality of output queues, each output queue configured to store switched cells, the switch fabric coupling the input queues to the output queues, the switch fabric configured to store cells moved from the input queues to the switch fabric, the switch fabric further configured to store cells based on the output queues.   
     
     
         3 . The apparatus of  claim 2 , wherein the controller is further configured to determine whether cells of the input queues are blocked from moving to the switch fabric, wherein cells of the input queues have respective times of the cells to depart, wherein cells of the switch fabric have respective times of the cells to depart, wherein, in an event cells are blocked from moving to the switch fabric, a cell in the switch fabric has a lower TTL than the cells being blocked. 
     
     
         4 . The apparatus as in  claim 2 , wherein the controller is further configured to determine an input priority for a cell arriving at a respective input queue based on a time of the cell to depart from a respective output queue and times of cells of the respective output queue to depart from the respective output queue. 
     
     
         5 . The apparatus as in  claim 2 , wherein the controller is further configured to determine an availability of a cell, queued at the input queues, for transport to the switch fabric, and further wherein the availability is given by a particular flow control element's state value of the flow-control state information. 
     
     
         6 . The apparatus as in  claim 1 , wherein, to update the flow-control state information, the controller is further configured to transition at least one flow-control element of the flow-control state information from one flow-control state value to another flow-control state value. 
     
     
         7 . The apparatus of  claim 1 , wherein the controller is further configured to order cells stored in the switch fabric based on times of the cells to depart, wherein cells having lower times of the cells to depart have higher output priorities. 
     
     
         8 . The apparatus as in  claim 1 , wherein the controller is further configured to determine the input priorities and the output priorities based on lowest time-to-leave switch fabric scheduling, lowest time-to-leave blocking, and non-negative slackness insertion. 
     
     
         9 . The apparatus as in  claim 1 , wherein the switch fabric is a buffered crossbar switch fabric. 
     
     
         10 . The apparatus as in  claim 1 , wherein the apparatus is configured to emulate at least one of an output queued packet switch, a first-in-first-out output queued packet switch, a general non-first-in-first-out output queued packet switch, and a strict priority output queued packet switch. 
     
     
         11 . A method to switch packets, each packet comprising at least one cell, the method comprising:
 transferring highest priority cells available for transfer in input queues from the input queues to a switch fabric having memory;   transferring highest priority cells in the switch fabric memory to output queues; and   regulating flow of cells between the input queues and the switch fabric memory, the regulating including producing flow-control state information based on whether or not a cell exists in the switch fabric memory with a lower TTL than all queued cells being regulated by the flow-control state information.   
     
     
         12 . The method of  claim 11 , further comprising coupling the input queues to the output queues via the switch fabric, the switch fabric memory storing cells moved from the input queues to the switch fabric, the switch fabric memory storing cells based on the output queues. 
     
     
         13 . The method of  claim 11 , further comprising determining an input priority for a cell arriving at a respective input queue based on a time of the cell to depart from a respective output queue and times of cells of the respective output queue to depart from the respective output queue. 
     
     
         14 . The method of  claim 11 , further comprising determining an availability of a cell, queued at the input queues, for transport to the switch fabric memory, and further wherein the availability is given by a particular flow control element's state value of the flow-control state information. 
     
     
         15 . The method of  claim 11 , further comprising ordering cells stored in the switch fabric memory based on times of the cells to depart, wherein cells having lower times of the cells to depart have higher output priorities. 
     
     
         16 . The method of  claim 11 , further comprising determining input priorities for cells moving to the switch fabric memory and output priorities for cells moving from the switch fabric memory based on lowest time-to-leave switch fabric scheduling, lowest time-to-leave blocking, and non-negative slackness insertion. 
     
     
         17 . The method of  claim 11 , further comprising prioritizing arriving cells in the input queues based on times of the arriving cells to depart. 
     
     
         18 . A method of  claim 11 , further comprising storing cells in the input queues according to input priorities and storing cells in the switch fabric memory according to output priorities. 
     
     
         19 . The method of  claim 11 , further comprising updating cells in the input queues available for transfer to the switch fabric, the updating including updating cells after highest priority cells in the switch fabric are transferred from the switch fabric to the output queues and after highest priority cells available for transfer in the input queues are transferred from the input queues to the switch fabric. 
     
     
         20 . The method of  claim 11 , further comprising emulating at least one of an output queued packet switch, a first-in-first-out output queued packet switch, a general non-first-in-first-out output queued packet switch, and a strict priority output queued packet switch.