Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

CHAPTER 13 Switching > 13.12 EXERCISES - Pg. 337

13.12 Exercises 337 log N is small, even this delay can be pipelined away to run in a minimum packet time. The fundamental lesson is that even algorithms that appear complex, such as matching, can, with randomization and hardware parallelism, be made to run in a minimum packet time. Further scaling in speed can be done using bit slices. Larger port counts are handled by algorithmic techniques based on divide-and-conquer. An understanding of the actual costs of switching shows that even a simple three-stage Clos switch works well for port sizes up to 256. However, for larger switch sizes, the Benes network, with its combination of (2log N) depth Delta networks, is better suited for the job. The main issue in both these scalable fabrics is scheduling. And in both cases, as in PIM, a complex deterministic algorithm is finessed using simple randomization. In both the Clos and Benes networks, the essential similarity of structure allows the use of an initial randomized load-balancing step followed by deterministic path selection from the randomized intermediate destination. Similar ideas are also used to reduce memory needs by either picking a random intermedi- ate line card or a random choice of DRAM bank to send a given packet (cell) to. The knockout switch uses trees of randomized 2-by-2 concentrators to provide k-out-of-N fairness. Thus randomization is a surprisingly important idea in switch implementations. It is interesting to note that almost every new switch idea described in this chapter has led to a company. For example, Kanakia worked on shared-memory switches at Bell Labs and then left to found Torrent. Juniper seems to have been started with Sindhu's idea for a new fabric based, perhaps, on the use of staging via a random intermediate line card. McKeown founded Abrizio after the success of iSLIP. Growth Networks was started by Turner, Parulkar, and Cox to commercialize Turner's Benes switch idea, and was later sold to Cisco. Dally took his ideas for deadlock-free routing on low-dimensional meshes and moved them successfully from Cray Computers to Avici's TSR. Thus if you, dear reader, have an idea for a new folded Banyan or an inverted Clos, you, too, may be the founder of the next great thing in networking. Perhaps some venture capitalist will soon be meeting you in a coffee shop in Silicon Valley to make you an offer you cannot