Granted Patent B1

US 7,187,672 · App. 10/147,446 · Granted Mar 6, 2007

Abstract

Claims (84)

1. A method of controlling operation of a communication switch, the method comprising:

reducing a problem of setting up a new connection through the communication switch into an NP-complete problem;

wherein the act of reducing comprises transforming into a vertex of a graph, each connection in a set comprising:

a plurality of connections existing in the communication switch; and

said new connection;

wherein the act of reducing further comprises adding an edge between two vertices in said graph if and only if two connections corresponding thereto share at least one input port or share at least one output port;

applying a heuristic to the NP-complete problem; and

setting up the new connection using a solution from the heuristic, if the heuristic is successful.

2. The method of claim 1 wherein each time slot is treated as a color and the heuristic is Brélaz's heuristic.

3. The method of claim 1 wherein:

the heuristic assigns to each connection a time slot during which a portion of the communication switch can be used for the connection.

4. The method of claim 1 wherein the communication switch operates with a plurality of time slots, the method further comprising:

checking if all ports to be used by the new connection are unused in any time slot;

wherein the acts of reducing, applying and setting up are performed only if no time slot is found during the checking; and

if a specific time slot is found during checking, setting up the new connection in the specific time slot.

5. The method of claim 1 wherein at least one of the connections is a multicast connection.

6. The method of claim 1 wherein at least one of the connections is between multiple input ports and multiple output ports (MIMO).

7. A method of controlling operation of a communication switch, the method comprising:

reducing a problem of setting up a new connection through the communication switch into an NP-complete problem;

applying a heuristic to the NP-complete problem; and

setting up the new connection using a solution from the heuristic, if the heuristic is successful;

wherein the act of applying comprises:

initializing a set P c , of time slots that a connection can be set up in, to all time slots available in the communication switch; and

while there are connections with no assigned time slot doing the following: finding a connection having the smallest set P c ;

assigning to the connection a time slot with the least index in the smallest set P c ; and

removing the time slot just assigned from set P c of each connection that shares a port with the connection having the smallest set P c .

8. The method of claim 7 wherein the heuristic is Brélaz's heuristic.

9. The method of claim 7 wherein a graph is used implicitly.

10. The method of claim 7 further comprising:

checking if all ports to be used by the new connection are unused in any time slot;

wherein the acts of reducing, applying and setting up are performed only if no time slot is found during the checking; and

if a specific time slot is found during checking, setting up the new connection in the specific time slot.

11. A method of setting up a new connection through a communication switch, the method comprising:

for each connection “c” in a set of (the new connection and a plurality of connections existing in the communication switch), initializing a set Pc of time slots that connection “c” can be set up in, to all time slots available in the communication switch; and

while there are connections with no assigned time slot:

finding a connection “s” having the smallest set Ps;

assigning, to connection “s”, a time slot with the least index in set Ps; and

removing the assigned time slot, from set P of each connection that has no assigned time slot and that shares a port with connection “s”.

12. The method of claim 11 wherein at least one of the connections is a multicast connection.

13. The method of claim 11 wherein at least one of the connections is between multiple input ports and multiple output ports (MIMO).

14. A method of controlling operation of a communication switch, the method comprising:

reducing a problem of setting up a new connection through the communication switch into an NP-complete problem;

wherein the act of reducing comprises transforming into an edge of a graph, each connection in a set comprising:

a plurality of connections existing in the communication switch; and

said new connection;

wherein the act of reducing further comprises adding a vertex between two edges in said graph if and only if two connections corresponding thereto share at least one input port or share at least one output port;

applying a heuristic to the NP-complete problem; and

setting up the new connection using a solution from the heuristic, if the heuristic is successful.

15. The method of claim 14 wherein each time slot is treated as a color and the heuristic is Brélaz's heuristic.

16. The method of claim 14 wherein:

the heuristic assigns to each connection a time slot during which a portion of the communication switch can be used for the connection.

17. The method of claim 14 wherein at least one of the connections is a multicast connection.

18. The method of claim 14 wherein at least one of the connections is between multiple input ports and multiple output ports (MIMO).

19. An apparatus comprising:

a communication switch;

a processor coupled to the communication switch; and

a computer readable storage medium coupled to the processor and encoded with a set of computer instructions that:

reduce a problem of setting up a new connection through the communication switch into an NP-complete problem;

wherein the computer instructions to reduce comprise instructions to transform into a vertex of a graph, each connection in a set comprising:

a plurality of connections existing in the communication switch; and

said new connection;

wherein the computer instructions to reduce further comprise instructions to add an edge between two vertices in said graph if and only if two connections corresponding thereto share at least one input port or share at least one output port;

apply a heuristic to the NP-complete problem; and

set up the new connection using a solution from the heuristic, if the heuristic is successful.

20. An apparatus comprising:

a communication switch;

a processor coupled to the communication switch; and

a computer readable storage medium coupled to the processor and encoded with a set of computer instructions that:

reduce a problem of setting up a new connection through the communication switch into an NP-complete problem;

wherein the computer instructions to reduce comprise instructions to transform into an edge of a graph, each connection in a set comprising:

a plurality of connections existing in the communication switch; and

said new connection;

wherein the computer instructions to reduce further comprise instructions to add a vertex between two edges in said graph if and only if two connections corresponding thereto share at least one input port or share at least one output port;

apply a heuristic to the NP-complete problem; and

set up the new connection using a solution from the heuristic, if the heuristic is successful.

21. An apparatus comprising:

a communication switch;

a processor coupled to the communication switch; and

a computer readable storage medium coupled to the processor and encoded with a set of computer instructions that:

for each connection “c” in a set of (the new connection and a plurality of connections existing in the communication switch), initialize a set Pc of time slots that connection “c” can be set up in, to all time slots available in the communication switch; and

while there are connections with no assigned time slot:

find a connection “s” having the smallest set Ps;

assign, to connection “s”, a time slot with the least index in set Ps; and

remove the assigned time slot, from set P of each connection that has no assigned time slot and that shares a port with connection “s”.

Assignments (8)