Free Trial

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

Share this Page URL

CHAPTER 10 Exact-Match Lookups > 10.1 CHALLENGE 1: ETHERNET UNDER FIRE - Pg. 222

222 CHAPTER 10 Exact-Match Lookups Number P15 P5 P15 P2a P5 Principle Use efficient data structures: binary search table Hardware FPGA for lookup only Used In First bridge Use efficient data structure: perfect hashing Gigaswitch Precompute hash function with bounded collisions FDDI bridge Pipeline binary search F I G U R E 10.1 Principles used in the various exact-match lookup techniques discussed in this chapter. This chapter is organized around a description of the history of bridges. This is done for one chapter in the book, in the hope of introducing the reader to the process of algorithmics at work in a real product that changed the face of networking. This chapter also describes some of the stimuli that lead to innovation and introduces some of the people responsible for it. Arnold Toynbee [TC72] describes history using a challenge­response theory, in which civilizations either grow or fail in response to a series of challenges. Similarly, the history of bridges can be described as a series of three challenges, which are described in the three sections of this chapter: Ethernets Under Fire (Section 10.1), Wire Speed Forwarding (Section 10.2), and Scaling Lookups to Higher Speeds (Section 10.3). The responses to these challenges led to what is now known as 802.1 spanning tree bridges [IEE97]. The techniques described in this chapter (and the corresponding principles) are summa- rized in Figure 10.1. Quick Reference Guide The implementor interested in fast exact-match schemes should consider either parallel hashing