High performance fault tolerant switching system for multimedia satellite and terrestrial communications networks

A method for routing a plurality of cells in a switching system having a plurality of inputs and a plurality of outputs, the method comprising:

• receiving the plurality of cells at the plurality of inputs, wherein each cell within the plurality of cells includes a destination such that the plurality of cells have a plurality of destinations and each destination within the plurality of destinations is associated with an output within the plurality of outputs;
• routing each cell within the plurality of cells through a plurality of switching elements within the switching system towards the plurality of outputs using the plurality of destinations, said switching elements including a TRAP network modified to include an arbitration unit for determining priority among a plurality of data packets routed to the same output port simultaneously, and a double destination switch, and wherein a portion of cells within the plurality of cells are correctly routed through the plurality of switching elements to the plurality of outputs and wherein another portion of the cells within the plurality of cells are misrouted, forming a plurality of misrouted cells;
• identifying cells as bus routable cells within the plurality of misrouted cells, wherein the bus routable cells are cells misrouted from the correct outputs by a selected amount and routing an identified cell to an output associated with the destination for the cell using a bus connected to the plurality of switching elements to route the misrouted cells to the correct outputs.

A switch unit comprising:

• a plurality of input port controllers having a plurality of inputs and outputs, wherein a plurality of cells are received at the plurality of inputs, each input port controller within the plurality of input port controllers, responsive to receiving a cell within the plurality of cells at an input within the plurality of inputs associated with the input port controller, attaching a header to the cell, the header containing routing information including a destination for the cell;
• a batcher sorting network having a plurality of inputs connected to the outputs of the plurality of input port controllers and a plurality of outputs, wherein the batcher sorting network sorts the cells using the routing information within the header attached to each cell within the plurality of cells, generating a plurality of sorted cells;
• an output contest network having a plurality of inputs connected to the plurality of outputs of the batcher sorting network for receiving the plurality of sorted cells and a plurality of outputs, wherein the output contest network contains a TRAP network modified to include a plurality of arbitration units which resolves contention for destinations and in response to a number of cells being routed to the same destination, marking a first portion of the number of cells for routing to the destination and a second portion of the number of cells for recirculation forming a plurality of marked cells;
• a concentrator network having an input for receiving the plurality of marked cells and a first output connected to the batcher sorting network and a second output, wherein the concentrator network sends the first portion of cells to the second output and recirculates the second portion of cells to the batcher sorting network through the first output;
• and
• a plurality of switching networks, each switching network having a plurality of inputs connected to the second output of the concentrator network, each switching network including:
• a single path switching matrix connected to the plurality of inputs and having a plurality of outputs;
• a dual bus having a plurality of inputs connected to the plurality of outputs in the single path switching matrix and having a plurality of outputs;
• wherein the first portion of the plurality of cells are received from the output of the concentrator network and routed through the single path switching network to the plurality of outputs, and wherein cells correctly routed through the single path switching network are sent to the plurality of outputs and cells misrouted through the single path switching network to an output adjacent to a correct output are routed through the dual bus to the correct output;
• and
• a plurality of output port controllers, each output port controller having an input connected to an output from the plurality of outputs from each switching network within the plurality of switching networks.

An apparatus for routing cells comprising:

• a plurality of inputs;
• a batcher sorting network connected to the plurality of inputs and having an output;
• an output contest network having an input connected to the output of the batcher sorting network and having an output, said output contest network consisting of a TRAP network modified to include a plurality of arbitration units;
• a plurality of switching networks connected to the output of the output contest network, each switching network within the plurality of switching networks including:
• a plurality of inputs;
• a single path switching matrix connected to the input, wherein cells are received from the output of the batcher sorting network;
• a double destination switch;
• a bus system;
• and
• a plurality of outputs connected to the bus system.

A communication system comprising:

• a plurality of switches, wherein at least one of the plurality of switches includes:
• a plurality of inputs;
• a batcher sorting network connected to the plurality of inputs and having an output;
• an output contest network having an input connected to the output of the batcher sorting network, said output contest network having an output and further comprising a modified TRAP network having a number of sub-elements including:
• a plurality of arbitration units;
• and
• a plurality of NOR gates and demultiplexers connected to said arbitration units;
• a plurality of switching networks connected to the output of the output contest network, each switching network within the plurality of switching networks including:
• a plurality of inputs;
• a single path switching matrix connected to the input, wherein cells are received from the output of the batcher sorting network;
• a double destination switch;
• a dual bus system;
• a plurality of outputs connected to the dual bus system;
• a plurality of redundant elements utilized for dynamic failure correction;
• a plurality of group links, wherein each group link represents a finite group of output port addresses;
• a plurality of communications links, wherein the plurality of switches are connected to each other by the plurality of communications links and wherein data is transferred between the plurality of switches through the plurality of communications links;
• and
• a plurality of data processing systems located within different portions of the communication system, wherein data is sent from a first data processing system within the plurality of data processing systems to a second data processing system within the plurality of data processing systems using a portion of the plurality of switches and a portion of the plurality of communications links.