| Corollary 2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| v | Problem: |
|||||||||||||||
| Ø | What is the switching algorithm for a work-conserving DSM router? |
|||||||||||||||
| • | Bus : No algorithm needed, but impractical |
|||||||||||||||
| • | Crossbar : Algorithm needed because only
permutations are allowed |
|||||||||||||||
| v | Corollary
2: (existence) |
|||||||||||||||
| Ø | An edge coloring algorithm can switch packets for a
work-conserving |
|||||||||||||||
| distributed shared memory router |
||||||||||||||||
| v | Proof : |
|||||||||||||||
| Ø | Follows from König’s theorem - Any bipartite graph
with maximum |
|||||||||||||||
| degree D has an edge coloring with D colors |
||||||||||||||||
| 14 |