Interconnect fabric providing connectivity between an input and arbitrary output(s) of a group of outlets

Abstract

This invention is an inventive N input by L output interconnect fabric. In operation, packets comprising an information field and an address are received at the N inputs to the interconnect fabric, and the address in each packet is mapped to a group of outputs, rather than to any particular output. Each packet is then routed to any available one of the interconnect fabric outputs associated with the group to which the packet is mapped. If a number of packets destined for the same group simultaneously arrive at the interconnect fabric inputs and the group to which they are all destined does not comprise enough outputs to accept them, then all packets in excess of the number that the destined group can accept are simply discarded. The probability of lost .[.jackets.]. .Iadd.packets .Iaddend.due to such discarded packets is acceptably small. In one exemplary embodiment, the invention can be utilized to build arbitrarily large packet switches.

We claim: .[.1. An interconnect fabric comprising: 
     
        communications path for each data packet..]. 5. .[.In an interconnect fabric comprising a plurality of interconnect fabric input ports, each input port being arranged for receiving data packets concurrent with data packets being received at others of the plurality of interconnect fabric input ports, and a plurality of groups of output ports, each group comprising a separate number of output ports, where the separate number of output ports comprised in a group of output ports may be the same as or different from the number of output ports comprised in other groups of output ports, at least one group of output ports comprising a plurality of output ports, a method of conveying each packet received at an interconnect fabric input port to an available interconnect fabric output port of a group of output ports for which the packet is destined, comprising the steps of: (a) mapping each received data packet to a destined group of output ports;   (b) establishing a separate communications path from each separate input port at which a data packet is received to a separate available output port of the destined group of output ports to which the data packet is mapped;   (c) transmitting each data packet over the separate established communications path; and   (d) discarding, or storing until a later time slot, packets received during a given time slot in excess of the separate number of output ports comprised in a group of output ports to which the excess packets are   
     
     
        mapped..]. .[.6.  A method according to claim 5 wherein the plurality of interconnect fabric input ports are arranged into separate groups of one or more interconnect fabric input ports: in step (a), performing the steps of; (a1) assigning each group of interconnect fabric input ports to a separate group of interconnect fabric output ports,   (a2) determining which data packets received at each group of interconnect fabric input ports are destined for the separate group of interconnect fabric output ports assigned in step (a1),   (a3) reserving a separate previously unreserved communications path between an interconnect fabric input post of each group of interconnect fabric input ports and its assigned group of interconnect fabric output ports from step (al) for each packet determined in step (a2) to be destined for the assigned group of interconnect fabric output ports,   (a4) assigning each group of interconnect fabric inputs to a separate different group of interconnect fabric output ports and repeating steps (a2) and (a3),   (a5) reiterating step (a4) until each group of interconnect fabric input ports has been assigned to each group of interconnect fabric output   
     
     
        ports..]. 7. A method according to claim .[.6.]. .Iadd.2 .Iaddend.wherein said interconnect fabric comprises a plurality of input modules, and a plurality of intermediate modules, each intermediate module being arranged to receive data from at least one input module via at least one first communications path, and to transmit the received data to at least one of the groups of interconnect fabric output ports via at least one second communications path, wherein step (a3) includes: reserving a previously unreserved first communications path to a particular intermediate module and reserving a previously unreserved second communications path from that same intermediate module to the assigned   
     
     
        group of interconnect fabric output ports. .Iadd.8.  An interconnect fabric comprising: a plurality of input ports for receiving data packets;   a plurality of groups of output ports, each group comprising a separate number of one or more output ports, each of said output ports for supplying data packets as an output and each output port of a particular group being assigned to a common destination which is different from a destination assigned to output ports of at least another group, where the separate number of output ports comprised in a group of output ports may be the same as or different from the number of output ports comprised in other groups of output ports, at least one of the groups comprising more than one output port; and   means for mapping each received data packet to a group of output ports and for mapping concurrently received data packets destined for a particular one of said destinations to respective output ports in a particular group assigned to the particular destination, said meawns for mapping including means for establishing a separate communications path from each separate input port at which each data packet is received to a separate output port of the group of output ports to which the data packet is mapped and for transmitting each data packet over the separate established communications path, (a) a plurality of input modules, each input module comprising (1) at least one input, each input being coupled to a separate interconnect fabric input port, (2) a plurality of outputs and (3) means for selectively connecting any input to any output for forming a first portion of the established communications path for each data packet, (b) a plurality of intermediate modules, each intermediate module comprising (1) a plurality of inputs, each input is coupled to a separate input module output, (2) a plurality of outputs, each output being coupled to a separate interconnect fabric output port of a predetermined number of groups of interconnect fabric output ports, and (3) means for selectively connecting any intermediate module input to any intermediate module output for forming a second portion of the established communications path for   
     
     
        each data packet. .Iaddend. .Iadd.9.  An interconnect fabric as defined in claim 8 wherein said plurality of input ports includes a first number of input ports and said plurality of output ports includes a second number of output ports larger than said first number of input ports. .Iaddend. .Iadd.10. An interconnect fabric as defined in claim 9 wherein said data packets are transported through said interconnect fabric on a circuit switched basis. .Iaddend. .Iadd.11. An interconnect fabric as defined in claim 8 further including means for discarding those data packets received during a current time slot and in excess of the separate number of output ports comprised in a particular group of output ports for which those excessive packets are destined. .Iaddend. .Iadd.12. An interconnect fabric as defined in claim 8 further including means for storing until a subsequent time slot, those data packets received during a current time slot and in excess of the separate number of output ports comprised in a particular group of output ports for which those excessive packets are 
     
     
        destined. .Iaddend. .Iadd.13.  An interconnect fabric comprising: a plurality of input ports for receiving data packets;   a plurality of groups of output ports, each group comprising a separate number of one or more output ports, each of said output ports for supplying data packets as an output and each output port of a particular group being assigned to a common destination which is different from a destination assigned to output ports of at least another group, where the separate number of output ports comprised in a group of output ports may be the same as or different from the number of output ports comprised in other groups of output ports, at least one of the groups comprising more than one output port; and   means for mapping each received data packet to a group of output ports and for mapping concurrently received data packets destined for a particular one of said destinations to respective output ports in a particular group assigned to the particular destination, said means for mapping including means for establishing a separate communications path from each separate input port at which each data packet is received to a separate output port of the group of output ports to which the data packet is mapped and for transmitting each data packet over the separate established communications path, said means for establishing and for transmitting including (a) a plurality of input modules, each input module comprising (1) at least one input, each input being coupled to a separate interconnect fabric input port, (2) a plurality of outputs, and (3) means for selectively connecting any input to any output for forming a first portion of the established communications path for each data packet, and (b) a plurality of intermediate modules, each intermediate module comprising (1) a plurality of inputs, where each input is coupled to a separate input module output, (2) a plurality of outputs, each output being coupled to a separate interconnect fabric output port of a predetermined number of groups of interconnect fabric outputs and (3) means for selectively connecting any intermediate module input to any intermediate module output for forming a second portion of the established communications path for each data packet. .Iaddend. .Iadd.14. In an interconnect fabric comprising a plurality of interconnect fabric input ports, each input port being arranged for receiving data packets concurrent with data packets being received at others of the plurality of interconnect fabric input ports and being arranged into separate groups of one or more input ports, and a plurality of groups of output ports, each of said output ports for supplying data packets as an output, each group comprising a separate number of output ports and each output port of a particular group being assigned to a common destination which is different from a destination assigned to output ports of at least another group, where the separate number of output ports comprised in a group of output ports may be the same as or different from the number of output ports comprised in other groups of output ports, at least one group of output ports comprising a plurality of output ports, a method of conveying each packet received at an interconnect fabric input port to an available interconnect fabric output port of a group of output ports for which the packet is destined, comprising the steps of:   (a) mapping each received data packet to a destined group of output ports and mapping concurrently received data packets destined for a particular one of said destinations to respective output ports of a particular group assigned to said particular destination;   (b) establishing a separate communications path from each separate input port at which a data packet is received to a separate available output port of the destined group of output ports to which the data packet is mapped; and   (c) transmitting each data packet over the separate established communications path for it, the step (a) including   (a1) assigning each group of interconnect fabric input ports to a separate group of interconnect fabric output ports,   (a2) determining which data packets received at each group of interconnect fabric input ports are destined for the separate group of interconnect fabric output ports assigned in step (a1),   (a3) reserving a separate previously unreserved communications path between an interconnect fabric input port of each group of interconnect fabric input ports and its assigned group of interconnect fabric output ports from step (a1) for each packet determined in step (a2) to be destined for the assigned group of interconnect fabric output ports,   (a4) assigning each group of interconnect fabric inputs to a separate different group of interconnect fabric output ports and repeating steps (a2) and (a3),   (a5) reiterating step (a4) until each group of interconnect fabric input ports has been assigned to each group of interconnect fabric output ports. ports and said plurality of output ports includes a second number of output ports larger than said first number of input ports. .Iaddend.   
     
     
        .Iadd.5.  A method as defined in claim 14 wherein said plurality of input ports includes a first number of input ports and said plurality of output ports includes a second number of output ports larger than said first number of input ports. .Iaddend. .Iadd.16. A method as defined in claim 15 wherein said data packets are transported through said interconnect fabric on a circuit switched basis. .Iaddend. .Iadd.17. A method as defined in claim 14 further including the step of discarding those data packets received during a current time slot and in excess of the separate number of output ports comprised in a particular group of output ports for which those excessive packets are destined. .Iaddend. .Iadd.18. A method as defined in claim 14 further including the step of storing until a subsequent time slot, those data packets received during a current time slot and in excess of the separate number of output ports comprised in a particular group of output ports for which those excessive packets are destined. .Iaddend.