Table of Figures:

Figure 1. Wavelength routing in optical layer............................................................... 7

Figure 2. A simple network sample (transfers)............................................................. 9

Figure 3. The pictograms representing the 25 transfers from all sending nodes to all receiving nodes of the network of Figure 2..................................................................................................... 10

Figure 4. Example of a traffic comprising 25 transfers carried out over the network shown in Figure 2 12

Figure 5. An initial category before fission, where symbol , represents any transfer that is in congestion with x and symbol represents any transfer which is simultaneous with x................... 15

Figure 6. Fission of the category of Figure 5 into its positive and negative sub categories 15

Figure 7. Proportion of the number of transfers within a skeleton, compared with the number of transfers of the corresponding traffic.................................................................................. 17

Figure 8. Optimized algorithm for retrieving all full teams of a traffic........................... 18

Figure 9. Search space reduction obtained by idle+skeleton+blank optimization steps 19

Figure 10. Time frames of a liquid schedule of the collective traffic shown in Figure 4... 20

Figure 11. There exists a traffic of three transmissions across this network that has no team and therefore no liquid schedule.................................................................................................... 21

Figure 12. A traffic consisting of thee transmissions to be carried across the network shown in Figure 11 21

Figure 13. Liquid schedule construction tree: denotes a reduced subtraffic at the layer of the tree and denotes a candidate for the time frame ; the operator applied to a subtraffic yields the set of all possible candidates for a time.................................................. 22

Figure 14. Architecture of the Swiss-T1 cluster supercomputer interconnected by a high performance wormhole switch fabric......................................................................................................... 25

Figure 15. The routing table of the Swiss-Tx supercomputer shown in Figure 14.......... 25

Figure 16. For a given number contributing nodes all possible allocation of nodes yielding different liquid throughputs 27

Figure 17. The 362 topologies of Figure 16 yielding different liquid throughput values placed along one axis, sorted first by the number of contributing nodes and then by their liquid throughputs...... 27

Figure 18. Theoretical liquid throughput and measured round-robin schedule throughput for 362 network sub topologies.................................................................................................. 28

Figure 19. Predicted liquid throughput and measured throughput according to the computed liquid schedule 29

Figure 20. Liquid schedule construction and the relevant optimizations......................... 30

Figure 21. The overall throughputs of hundreds of different traffic patterns carried out according a liquid schedule and according a topology unaware schedule, comparison with a theoretical upper limit 31

Figure 22. Congestion graph corresponding to the traffic pattern of Figure 3 across the network of Figure 2: the vertices of the graph represent the 25 transfers, the edges represent congestions between the transfers 32

Figure 23. Number of edges in the 362 congestion graphs corresponding to the traffic patterns of Figure 16 and Figure 17 33

Figure 24. Dsatur graph coloring heuristic algorithm..................................................... 34

Figure 25. Loss in throughput induced by schedules computed with the Dsatur heuristic algorithm 34

Figure 26. Running times for computing liquid schedules by MILP Cplex method and by liquid schedule construction algorithm................................................................................................... 36

* * *