(12) United States Patent
`Hegde
`
`(10) Patent N0.:
`
`(45) Date of Patent:
`
`US 6,876,654 B1
`Apr. 5, 2005
`
`US006876654B1
`
`(54) METHOD AND APPARATUS FOR
`MULTIPROTOCOL SWITCHING AND
`
`OTHER PUBLICATIONS
`
`ROUTING
`
`(75)
`
`InVem0r3 G0P3l Dattaray Hegde, San -1059, CA
`(US)
`
`Acharya, Arup; et al.; “IP Switching over Fast ATM Cell
`P
`g
`Trans ortation IPSOFACTO : Switchin multicast flows,”
`Global Telecommunications Conf.
`1997, vol. 3, pp.
`1850-1856.
`
`73
`
`)
`
`(
`
`:
`
`AS .
`Slgnee
`
`Intel Cor oration’ S
`(US)
`P
`
`t C1
`an a
`
`am
`
`, CA
`
`Stevens, W. Richard; “TCP/IP illustrated vol. 1,” 1994,
`2A2d5di:%r%—Wesley Professional Computing Series,
`PP-
`
`( ,1 ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`USC. 154(b) by 0 days.
`
`Comer and David L. Stevens, Adress Discovery
`Douglas
`and .Bl}’ldlI’lg(ARP), Internetworking with TCP/IP, vol. II:
`ggesgggn, Implementation, and Internals, Chapter 4, 1994, pp.
`
`(21) Appl, N0.: 09/058,335
`,
`AP“ 10: 1998
`F1190:
`(22)
`Int. Cl.7 ........................... .. H04L 12/28; H04] 3/16
`(51)
`(52) U.S. Cl.
`...................................... .. 370/392; 370/466
`(58) Field of Search ............................... .. 370/392, 393,
`370/401, 466, 378, 379, 382, 400, 402,
`
`Douglas E. Comer and David L. Stevens,RIP.'Active Route
`Propagation and Passive Acquisition, Internetworking with
`TCP/IP, vol.
`II: Design, Implementation, and Internals,
`ha ter 18 1994
`. 355-379.
`C P
`>
`>PP
`.
`.
`* ‘med by °"*‘“““‘°"
`
`(59)
`
`_
`References Clted
`
`465: 467
`
`Primary Examiner—Chau Nguyen
`Assistant Examiner—Andy Lee
`(74) Attorney, Agent, or Firm—Pillsbury Winthrop LLP
`
`(57)
`ABSTRACT
`packet forwarding method and apparatus performs mul-
`tiprotocol routing (for IP and IPX protocols) and switching.
`Incoming data packets are examined and the flow (i.e.,
`source and destination addresses and source and destination
`socket numbers) with which they are associated is deter-
`mined. A flow table contains forwarding information that
`can be a
`1, d
`-
`-
`pp ie
`to the flow. If an entry is not present in the
`.
`.
`table for the particular flow, the packet 1S forwarded to the
`CPU to be processed, The CPU can then update the table
`with new forwarding information to be applied to all future
`packets belonging to the same. flow. When the forwarding
`information is already present in the table, packets can thus
`be forwarded at wire speed. Adedicated ASIC is preferably
`employed to contain the table, as well as the engine for
`examining the packets and forwarding them according to the
`stored information. Decision-making tasks are thus more
`efficiently partitioned between the switch and the CPU so as
`to minimize processing overhead.
`
`U.S. PATENT DOCUMENTS
`A
`12 1993 Bh d
`'
`A
`5/1994 pefifnzfieet at
`5,390,173 A
`2/1995 Spinney et a1.
`5,426,637 A
`6/1995 Derby etal.
`5,430,727 A
`7/1995 Callqn
`5,517,620 A *
`5/1999 Hashlmoto et a1~
`5>539>736 A
`7/1996 Johnson .et 91' """""" " 370/402
`5,555,543 A
`9/1996 Grohoski et 211.
`5,572,533 A
`11/1996 Sunada et al.
`............ .. 714/712
`5,610,905 A
`3/1997 Murthy et al.
`............ .. 370/401
`5,640,399 A
`6/1997 Rostoker et at
`5,715,250 A *
`2/1998 watanabe
`5,757,795 A *
`5/1998 Schnell . . . . . . . . . . . .
`5,920,566 A *
`7/1999 Hendel et al.
`5,920,699 A :
`7/1999 Bare ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ -
`5949786 2 *
`?e.Hentge1r
`’ ’ ’ " 709/242
`A *
`4/2000 Ka11:,:b‘:fl3a'r
`370/414
`6’094’435 A *
`7/2000 Hoffman et at
`tttttttttt N 370/392
`6’128’298 A * 10/2000 Wootton et at
`’
`’
`FOREIGN PATENT DOCUMENTS
`
`
`
`’ ’ ’ ’
`
`*
`*
`
`370/395
`. . . .. 370/392
`370/401
`- - - -- 370/351
`
`EP
`
`0 465 201 A2
`
`1/1992
`
`16 Claims, 8 Drawing Sheets
`
`
`
`ARISTA 1112
`
`1
`
`ARISTA 1112
`
`

`

`U.S. Patent
`
`Apr. 5,2005
`
`Sheet 1 of 8
`
`US 6,876,654 B1
`
`WAN
`
`I0
`
`_,_
`,
`, —::———:— :3 5"" 20
`"" ‘D -o o- —— o -- " "
`
`Q .............
`
`W
`
`FIGURE 1
`
`(PRIOR ART)
`
`2
`
`

`

`U.S. Patent
`
`Apr. 5,2005
`
`Sheet 2 of 8
`
`US 6,876,654 B1
`
`WAN
`
`MW.
`
`FIGURE 2
`
`3
`
`

`

`3U
`
`tnet
`
`Apr. 5, 2005
`
`Sheet 3 of 8
`
`8.,6SU
`
`1B4569
`
`--a...........................................................-..PW....................
`
`
`
`
`=o_.a..=uc=oU
`
`2.3.
`
`|.
`
`II.0!\\I
`
`|lIIIIIIIIIIIII
`
`2.
`
`II
`
`8
`
`.,mM5505
`
`IIIIIIII|nIIIIIIIIIIIIIIIIIIIIIIIIIII|IIIIIIIIIIIIIIIIIIDIIlIIIIIIIIIIII
`
`4
`
`
`

`

`U.S. Patent
`
`Apr. 5,2005
`
`Sheet 4 of 8
`
`US 6,876,654 B1
`
`60
`
`100
`
`Address
`
`Registers
`
`CPU I6terfa.ce
`
`IOItUIItIIIIIIIIIIIIIIIIIIIIIIII
`
`Port Interface
`14-!
`
`Port Interface N
`
`no
`
`’
`
`1 0
`
`130
`
`Memory Interface
`
`To 70
`
`To 75
`
`To 80
`
`I|IIIIIIIOIIUIIIIIOIIIIIIlIIIIIIIllIInIIIIIDlIII|IIIIIIIIIIIIIIIIIIIIIIIIIIICIIII
`
`I
`
`.-----cu--.—-----------.--——-------_--- -----------------cu--o--coo-
`
`To 90
`
`FIGURE 4
`
`5
`
`
`

`

`U.S. Patent
`
`Apr. 5,2005
`
`Sheet 5 of 8
`
`US 6,876,654 B1
`
`
`
`5.......:.£_¢
`
`mmo..E.<
`
`..o_u...omoM
`
`m_...ooo.m
`
`ano.._:.<
`
`.:._u.._cuom
`
`:2:
`
`
`
`
`
`.3:o283...53..5_s.3e._32.5.
`
`
`
`
`
`..3._2.E:Z
`
`.
`
`..._=8§
`
`
`
`fi.—O0oM—:o_.:_33_
`
`IOIIUIIIIIIIOIOItIII1III3IIQIU8IIIIIIIOCII!GUOII|IIIIIIIIIIIIIUIIIIIIISOIIIIlIIIIlDIIIIIIIIIIIIIIIIIII
`
`mHMDGE
`
`6
`
`
`
`
`

`

`U.S. Patent
`
`Apr. 5,2005
`
`Sheet 6 of 8
`
`US 6,876,654 B1
`
`S10
`
`S20
`
`Extract Protocol Type
`From Packet Header
`
`IP or IPX
`protocol?
`
`N
`
`S60
`
`S30
`
`
`
`Packet Needs to
`be Switched?
`
`S40
`
`Switch at
`Layer 3
`
`Route at
`Layer 3
`
`Switch at
`Layer 2
`
`FIGURE 6
`
`7
`
`

`

`U.S. Patent
`
`Apr. 5,2005
`
`Sheet 7 of 8
`
`US 6,876,654 B1
`
`Get Source
`Information
`
`5100
`
`Notify CPU
`
`
`S140
`
`s13o '
`
`S1 70
`
`S180
`
`N
`
`Forward
`Packet On All
`Ports
`
`Sl90
`
`IPIIPX or
`-RRWRARP
`P333“?
`
`FIGURE 7
`
`8
`
`

`

`U.S. Patent
`
`Apr. 5,2005
`
`Sheet 8 of 8
`
`US 6,876,654 B1
`
`Ge! Flow
`
`Does Entry For
`Flow Exist In
`Flow Table?
`
`Information
`
`
`
`8400
`
`Notify CPU
`
`S3 10
`
`
`
`Forward Packet on
`
`Port Designated by
`
`Flow Table
`
`' 3440
`
`FIGURE 8
`
`
`
`9
`
`

`

`US 6,876,654 B1
`
`1
`METHOD AND APPARATUS FOR
`MULTIPROTOCOL SWITCHING AND
`ROUTING
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`invention relates to packet switches and
`The present
`routers, and more particularly, to a switching and routing
`method and apparatus capable of performing wire-speed
`switching and routing of data packets associated with a
`variety of network traffic protocols.
`2. Description of the Related Art
`Conventional network traffic is formatted into packets that
`are sent
`through the network according to destination
`addresses programmed in the packet header. The networking
`equipment used to forward such packets through a network
`includes routers, Layer 2 switches and Layer 3 switches.
`Each of these different types of equipment operate at dif-
`ferent layers in the seven-layer OSI model. That is, for
`example, Layer 2 switches examine the Ethernet (MAC)
`addresses embedded in the packet
`to make forwarding
`decisions, while Layer 3 or “IP” switches examine the IP
`addresses embedded in the packet
`to make forwarding
`decisions. Both of these types of switches are good for the
`specific operation for which they are designed, but they can
`not be used to interconnect routed networks and network
`segments r11nning multiple protocols s11 ch as IP and IPX that
`are fairly common on networks today.
`Meanwhile, in the overall network, data must be routed
`and switched over different segments. Routers are used to
`interconnect different routed segments on the network. Con-
`ventional state-of-the-art routers employ general purpose
`CPU’s to examine packet headers and to route the packets to
`their destinations appropriately. Although such CPU-
`assisted routers are able to handle the various routing
`protocols encountered, the processing overhead they require
`is substantial and this limits the rate at which traffic can be
`sent over the network.
`
`A conventional network configuration is illustrated in
`FIG. 1. In such a configuration, Ethernet switch 10 provides
`a mechanism whereby dedicated 10 or 100 Mbps bandwidth
`is made available to nodes attached to ports 20 of switch 10.
`Most Ethernet switches today use Layer 2 switching. In this
`scheme, the switch builds a database containing the Ethernet
`addresses of the nodes and the ports to which they are
`attached. It then matches the destination Ethernet address in
`
`the packet (Layer 2 address in the seven layer OSI model)
`with addresses in the database to forward the packet on the
`port
`to which the destination node is connected. Most
`switches use some kind of hardware assistance to perform
`the lookup and forwarding operations at 10 or 100 Mbps
`wire speed.
`Since Layer 2 switches use Ethernet addresses only, they
`are unable to provide connectivity between multiple IP or
`IPX networks or subnets. Nodes on IP networks are identi-
`
`fied by IP addresses and subnet masks. Nodes on IPX
`networks are identified by IPX network and IPX node
`addresses. Since these addresses are at the network layer
`(Layer 3) of the seven layer OSI model, they are referred to
`as network addresses. Unlike Ethernet addresses that are
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`assigned by network interface card vendors, system admin-
`istrators or Internet Service Providers (ISPs) typically assign
`IP and IPX network addresses.
`
`65
`
`Routers such as router 30 are therefore required to con-
`nect multiple networks or subnets. Unlike switches, routers
`
`10
`
`2
`
`use Layer 3 addresses (network addresses) to forward pack-
`ets. Routers also learn about other routers and thereby
`determine the different networks to which they are con-
`nected and the costs associated in reaching them. They
`forward the packets along the path with the lowest cost.
`Since routers have to look deeper into packets and have to
`support different protocols with different packet formats,
`routing functions have been traditionally implemented
`mostly in software. Routers therefore can forward packets at
`rates of only about a tenth of those provided by Layer 2
`switches. To improve performance, some routers use very
`high-speed processors, and some also use multiple proces-
`sors and large amounts of high-speed memory. Therefore
`they are much more expensive than layer 2 switches. A
`typical routers costs per port are about seven to eight times
`the per port costs of a comparable Layer 2 switch.
`Conventional routers, moreover, do not perform switch-
`ing operations and therefore can not be used to connect
`networks that run non-routable protocols such as NetBios,
`DLC/LLC and LAT. Routers also can not be used to connect
`multiple nodes belonging to the same IP or IPX networks
`since each router interface must belong to a different IP or
`IPX network. Therefore, both routers and switches must be
`used together to form a switched internetwork, as illustrated
`in FIG. 1.
`
`Recently, some switch vendors have attempted to marry
`the intelligence of routers with the speed of switches by
`adding some level of Layer 3 intelligence to their switch
`products, creating so-called Layer 3 switches. See, e.g.,
`Keith Turner, “Is It A Switch Or Is It A Router,” PC
`Magazine, Nov. 18, 1997, pp. 269-70. However,
`these
`schemes typically support only limited numbers of
`protocols, may require reconfiguration of end stations and
`still may require external routers.
`Accordingly, there remains a need in the art for a switch
`that can switch and route network data packets associated
`with a variety of protocols at high rates with substantially
`less processing overhead, is inexpensive, does not require
`any external routers to operate, and does not require any
`reconfiguration of end stations. The present invention fulfills
`this need.
`
`SUMMARY OF THE INVENTION
`
`An object of the invention is to provide a method and
`apparatus that can forward packets to their destination at
`high throughput rates with substantially less processing
`overheads.
`
`Another object of the 'nvention is to provide a method and
`apparatus that can both switch and route packets with the
`same minimal processing overhead.
`Another object of the 'nvention is to provide a method and
`apparatus that
`is capable of both switching and routing
`packets at wire speed.
`Another object of the 'nvention is to provide a method and
`apparatus that is capable of wire-speed switching and rout-
`ing of packets that belong to all possible network protocols.
`Another object of the 'nvention is to provide a method and
`apparatus that provides wire-speed switching and routing
`functionality in a swi ched internetwork, but does not
`require reconfiguration of existing end stations or network
`infrastructure.
`
`Another object of the 'nvention is to provide a method and
`apparatus capable of multiprotocol wire-speed switching
`and routing that is inexpensive to implement.
`The present invention fulfills these objects, among others,
`by providing a method and apparatus for performing mul-
`
`10
`
`

`

`US 6,876,654 B1
`
`3
`tiprotocol switching and routing. Incoming data-packets are
`examined and the flow (i.e., source node, the application
`running on the source node that is initiating the connection
`and generating the packets, destination node and the appli-
`cation on the destination node to which the traffic is
`
`destined) with which they are associated is determined. A
`flow table contains forwarding information that can be
`applied to the flow. If an entry is not present in the table for
`the particular flow, the packet is forwarded to the CPU to be
`processed. The CPU extracts the flow information from the
`packet and updates the table with forwarding information to
`be applied to all future packets belonging to the same flow.
`When the forwarding information is already present in the
`table, packets can thus be forwarded in hardware with no
`processor intervention at wire-speed. A dedicated ASIC is
`preferably employed to contain the table, as well as the
`engine for examining the packets and forwarding them
`according to the information stored in the flow tables.
`Decision-making tasks are thus more efficiently partitioned
`between the switch and the CPU so as to minimize process-
`ing overhead, while providing an inexpensive multiprotocol
`solution.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`These and other objects and advantages of the present
`invention will become apparent to those skilled in the art
`after considering the following detailed specification,
`together with the accompanying drawings wherein:
`FIG. 1 is a block diagram illustrating conventional packet
`switching architecture.
`FIG. 2 is a block diagram illustrating packet switching
`architecture in accordance with the present invention.
`FIG. 3 is a block diagram illustrating a multiprotocol
`switch of the present invention in an architecture such as that
`illustrated in FIG. 2.
`
`FIG. 4 is a block diagram illustrating a switch module of
`the present invention in a multiprotocol switch such as that
`illustrated in FIG. 3.
`
`FIG. 5 is a block diagram illustrating a flow table of the
`present invention in a multiprotocol switch such as that
`illustrated in FIG. 3.
`
`FIG. 6 is a flowchart illustrating a method used to forward
`data packets in a multiprotocol switch according to the
`present invention.
`FIG. 7 is a flowchart illustrating a method used to switch
`data packets in a multiprotocol switch according to the
`present invention.
`FIG. 8 is a flowchart illustrating a method used to route
`data packets in a multiprotocol switch according to the
`present invention.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`FIG. 2 is a block diagram illustrating an architecture for
`performing multiprotocol routing in accordance with the
`principles of the invention.
`It
`includes a multiprotocol
`switch 40 having N input/output ports 50-1 .
`.
`. 50-N. In
`accordance with an object of the invention, as illustrated in
`FIG. 2, the input/output ports can be attached to nodes or
`they can be attached to different network segments or
`different networks in a local area network (LAN) directly or
`via routers. The novel ability of the multiprotocol switch of
`the present invention to forward packets among and between
`local nodes and external networks attached to it will be
`described below.
`
`4
`FIG. 3 further illustrates a multiprotocol switch 40 in
`accordance with the principles of the invention. In addition
`to input/output ports 50, it includes a switch module 60 and
`a flow table 70. Switch module 60 further communicates
`with a packet buffer 75, a CPU 80 and a shared memory 90.
`Flow table 70 and shared memory 90 are mapped memory
`spaces that are accessible by both switch module 60 and
`CPU 80. CPU 80 also communicates with a configuration
`table 85 and a system administrator 45.
`Although shown separately for clarity, switch module 60
`and flow table 70 are preferably implemented together as an
`application specific integrated circuit (ASIC). Such an
`implementation permits data packets to be switched between
`ports 50 at wire speed in accordance with flows specified in
`flow table 70. However, other specific implementations of
`switch module 60 and flow table 70 in accordance with the
`
`invention will be apparent to those skilled in the art after
`being taught by the following disclosures of their logical
`functions and data structures, for example. CPU 80 can be
`implemented by a MC680x0 microprocessor made by
`Motorola, Inc. of Schaumburg, Ill., and shared memory 90
`can be implemented by a fast static RAM (SRAM) such as
`that manufactured by Samsung Inc. Packet buffer 75 for
`storing packets can be implemented using Synchronous
`DRAM (SDRAM) such as that manufactured by Samsung,
`Inc. CPU 80 programs the partitions for packet buffer 75 on
`a per port basis. The amount of memory allocated to each
`partition depends on port speed. So, for example, a gigabit
`port is allocated more memory than a 10/100 Mbps port.
`Although not shown for clarity, it should be understood
`that CPU 80 can include program and data memory for
`storing programs that are executed by CPU 80 and data
`needed by those programs. Such data can include routing
`tables and the like. Programs executed by CPU 80 can
`include conventional routing update and costing functions
`implemented with known protocols such as Routing Infor-
`mation Protocol (RIP). Such conventional processes are in
`addition to the novel processes performed by the multipro-
`tocol switch of the present invention that will be described
`in more detail below. However, a detailed description of
`such conventional processes will not be given so as not to
`obscure the invention.
`
`Programs executed by CPU 80 also include processes for
`setting and maintaining system configuration information
`for the network in configuration table 85 in accordance with
`commands by system administrator 45, which system con-
`figuration information can include routing domains and
`gateway settings. If just layer 2 operation (where the packets
`are switched based on source and destination Ethernet
`
`addresses) is desired, no system configuration is required.
`The switch in this case becomes a true plug and play switch.
`For layer 3 routing operations, system administrators need to
`group ports into routing domains. Each routing domain
`represents a network segment. Administrators assign an IP
`address and subnet mask to each of the IP routing domains.
`All the ports that belong to a routing domain have the same
`IP address and different routing domains belong to different
`IP subnets. Administrators assign IPX network address to
`each of the IPX routing domains. All the ports that belong
`to a routing domain have the same IPX network address.
`Administrators can also assign unique IPX node addresses to
`each of the routing domains. By default,
`the Ethernet
`address of the first port in the routing domain is used as the
`IPX node address for that routing domain. As will be
`explained in more detail below, the multiprotocol switch of
`the invention switches IP and IPX traffic between the nodes
`
`that belong to the same routing domain at wire speed at layer
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`11
`
`11
`
`

`

`US 6,876,654 B1
`
`5
`3. IP and IPX traffic between nodes that belong to different
`routing domains is routed at wire speed.
`In addition to these routing domain settings, a base
`Ethernet address is assigned to the switch, which address is
`stored in a register when the switch is manufactured. Each
`of the ports 50-1 .
`.
`. 50-N have an Ethernet address
`associated therewith. The Ethernet address of port N is
`computed as a combination of the base Ethernet address and
`the number N of the port.
`Ports 50 are preferably RJ45 10/100 Mb ports, and can
`include port modules such as, for example, a 8><10/100 Mb
`port module (100 Base TX), a 1-Gigabit port module, or a
`6><100 Base FX port module. Ports 50 can also include a
`WAN module, for example, one that is capable of frame
`relay or ATM data transfer at T1/T3/E1/E3/OC-3 data rates:
`In the architecture shown in FIG. 3; data packets arrive at
`ports 50-1 .
`.
`. 50-N. As will be described in more detail
`below, switch module 60 continually monitors each of the
`ports for incoming traffic. When an IP/IPX data packet
`arrives, it is buffered in packet buffer 75. While the data is
`flowing into packet buffer 75, the switch module 60 checks
`the packet header information, including source and desti-
`nation addresses, and source and destination sockets
`(sockets identify applications communicating on the hosts
`associated with the source and destination addresses). If the
`packet header information matches a flow entry found in
`flow table 70, switch module 60 forwards the packet to the
`appropriate port 50-1 .
`.
`. 50-N. If no entry is found, the
`packet is buffered in shared memory 90 and CPU 80 is
`notified. CPU. 80 determines the flow information for the
`
`packet, and updates flow table 70 with a new rule for all
`future received packets associated with the same flow. CPU
`80 then forwards the packet buffered in shared memory 90
`on the appropriate port 50-1 .
`.
`. 50-N via switch module 60.
`Since an entry for the flow exists in the flow table 70 now,
`switch module 60 forwards all packets belonging to this flow
`in hardware to the appropriate port 50-1 .
`.
`. 50-N with no
`CPU intervention.
`FIG. 4 further illustrates a switch module 60 in accor-
`dance with the architecture illustrated in FIG. 3. As can be
`
`seen, it includes switch engine 100, address registers 105,
`CPU interface 110, port interfaces 120-1 .
`.
`. 120-N, and
`memory interface 130. As is further apparent from the
`figure, switch engine 100 accesses information contained in
`flow table 70 and address registers 105, and manages
`packets buffered in packet buffer 75. CPU interface 110
`communicates with CPU 80, thereby providing means of
`communication between CPU 80 and switch engine 100,
`address registers 105, port interfaces 120-1 .
`.
`. 120-N, and
`memory interface 130. Port interfaces 120-1 .
`.
`. 120-N
`respectively communicate with ports 50-1 .
`.
`. 50-N, and
`memory interface 130 manages access to shared memory 90.
`It should be noted that in this configuration, both switch
`engine 100 and CPU 80 (via CPU interface 110 and memory
`interface 130) can forward packets on ports 50-1 .
`.
`. 50-N
`via port interfaces 120-1 .
`.
`. 120-N, although switch engine
`100 can forward packets at wire speeds while CPU 80 can
`do so only with processing overhead.
`Switch engine 100 performs the flow extraction and
`determination operations for packets received via port inter-
`faces 120-1 .
`.
`. 120-N. It accesses flow table 70 to look up
`the forwarding information associated with the flows to
`which packets belong. Address registers 105 provide address
`information to assist switch engine 100 in locating appro-
`priate flow information in flow table 70. The contents of
`these registers can be configured by CPU 80 via CPU
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`12
`
`6
`interface 110, and can also include the base Ethernet address
`of the switch described above.
`
`. 120-N send and receive packets
`.
`Port interfaces 120-1 .
`between the nodes to which they are attached. Packcts
`received from attached nodes are buffered in packet buffer
`75 and as they are coming into the switch, the flow infor-
`mation in the packet is processed by switch engine 100. If
`switch engine 100 can resolve the flow, received packets are
`immediately forwarded to the appropriate port via its cor-
`responding port interface 120-1 .
`.
`. 120-N. If the flow is
`unresolved, switch engine 100 causes the packets to be
`stored in shared memory 90 via memory interface 130 and
`signals the CPU for assistance via CPU interface 110.
`As is known, data packets traversing through a typical
`network have headers including the source and destination
`Ethernet addresses of the packets, and for IP/IPX networks,
`IP/IPX source and destination addresses. Ethernet addresses
`identify nodes in a non-IP/IPX network and IP/IPX
`addresses identify nodes within an IP/IPX network, as well
`as the networks to which they belong The packets may also
`contain source and destination socket numbers that uniquely
`identify host applications communicating via these nodes.
`Accordingly, information that uniquely identifies a flow of
`packets back and forth between two nodes and/or applica-
`tions in any network can be derived from data packet
`headers. Once the flow information is learned and stored in
`
`flow table 70, any data packet belonging to such a flow can
`be immediately forwarded in hardware with minimal pro-
`cessing.
`Switch engine 100 handles packets in accordance with the
`flows with which the packets are associated, as derived from
`the packet headers. An example of an Ethernet data packet
`header is shown below, having what is known as an Ethernet
`Type II format. As can be seen,
`it
`includes a six-byte
`destination address, a six-byte source address and a two-byte
`type field.
`
`Destination Address
`(6 bytes)
`
`Source Address
`(6 bytes)
`
`Type Field
`(2 bytes)
`
`Other known formats include Ethernet 802.3, Ethernet 802.2
`LLC and Ethernet SNAP.
`
`The type field identifies the Layer 3 protocol used by the
`hosts communicating via the packet. For Ethernet Type II
`packets, some of the values in the type field are shown in the
`following table.
`
`Type Field Value (hex)
`0x600
`0x800
`0x806
`0x8035
`OXS137
`
`Protocol
`XNS
`IP
`ARP
`RARP
`IPX
`
`In addition to these explicit type identifiers, it is known
`that different protocols use different Ethernet frame formats.
`IP uses Ethernet II and SNAP packet formats. IPX uses all
`four of the above-mentioned formats. AppleTalk uses the
`SNAP packet format and NetBios typically uses the Ethernet
`802.2 LLC format.
`
`Packets associated with IP and IPX protocols have addi-
`tional header information following the Ethernet header. An
`example of an IP header format is shown below.
`
`12
`
`

`

`US 6,876,654 B1
`
`Vers
`(4 bits)
`
`Service Type
`(8 bits)
`
`HLEN
`(4 bits)
`Identification
`(16 bits)
`Time to Live
`(8 bits)
`
`Total Length
`(16 bits)
`Fragment Olfset
`Flags
`(12 bits)
`(4 bits)
`Header Checksum
`(16 bits)
`
`Padding
`(8 bits)
`
`Protocol
`(8 bits)
`Source IP Address
`(32 bits)
`Destination IP Address
`(32 bits)
`IP Options (if any)
`(24 bits)
`
`Transmission Control Protocol (TCP) and User Datagram
`Protocol (UDP) use IP. In addition to the information above,
`the headers for these protocols further contain source and
`destination socket numbers, which can identify individual
`applications running on top of TCP/UDP such as FTP,
`Telnet, e-mail, and HTTP. TCP and UDP are at Layer 4 of
`the OSI model. As seen above, the portion of packet headers
`for the IP layer provides source and destination IP addresses
`to identify the end-to-end hosts through which the individual
`applications (identified by socket numbers) are communi-
`cating.
`An example of an IPX header format is shown below.
`
`Checksum (2 bytes)
`Packet Length (2 bytes)
`Transport Control (1 byte)
`Packet Type (1 byte)
`Destination Network (4 bytes)
`Destination Node (6 bytes)
`Destination Socket (2 bytes)
`Source Network (4 bytes)
`Source Node (6 bytes)
`Source Socket (2 bytes)
`
`The IPX protocol is at Layer 3 of the OSI model. Most
`Novell NetWare (trademark of Novell, Inc. of Provo, Utah)
`applications run on top of IPX. As seen above, IPX headers
`contain source and destination socket numbers, which iden-
`tify host applications running on the nodes, in addition to
`IPX source and destination network and IPX source and
`
`destination node addresses, which identify the end-to-end
`IPX nodes by which the applications are communicating.
`Packets associated with IP and IPX protocols can thus be
`identified with flows between IP and IPX node and/or
`network addresses and sockets (Layer 3), and those associ-
`ated with other protocols can be identified with flows
`between Ethernet addresses (Layer 2).
`Switch engine 100 forwards packets to the appropriate
`port based on flow information stored in flow table 70. FIG.
`5 illustrates the tables comprising flow table 70. In this
`example, flow table 70 includes address resolution hash 140
`and address resolution record table 150. As will be explained
`in more detail below, address resolution record table 150
`contains a list of address resolution records that provide
`forwarding information for each node that is communicating
`via the attached switched internetwork, and address resolu-
`tion hash 140 contains pointers to records in address reso-
`lution record table 150. The locations of address resolution
`hash 140 and address resolution record table 150 within the
`
`memory space of switch engine 100 are programmed in
`address registers 105.
`As seen above, Ethernet addresses are six bytes long. The
`first three bytes contain vendor identification and are typi-
`
`8
`cally fixed for different Ethernet products built by the same
`vendor. The last three bytes vary between these different
`products. As further seen above, IP and IPX addresses are
`four bytes long. The most commonly used IP addresses are
`Class C addresses, where within a single network, the first
`three bytes of the IP address are fixed and only the last byte
`varies.
`The present invention uses bucket hashing for sorting the
`flow information to enable searching through the list of
`address resolution records faster. As seen above, for both
`IP/IPX and non-IP/IPX networks, the last one to three bytes
`are fairly unique for each node. Accordingly, the chance that
`the last twelve bits of a node address will be unique within
`any network is fairly high. Therefore, the last twelve (least
`significant) bits (0-11) of an IP address (for IP hosts), or IPX
`address (for IPX hosts) or Ethernet address (for hosts using
`other protocols) of the data packet header are used as a hash
`into flow table 70. This identifies the starting point of an
`address resolution record associated with the node. Address
`
`resolution hash 140 can store entries for 212 possible hashes
`(4096). Actually, there are three separate hash areas of 4096
`entries apiece, one each for non-IP/IPX flows, IP flows, and
`IPX flows. Each hash entry is 32 bits long and has a format
`as shown below (bit positions of each field shown in
`parentheses):
`
`Hash
`Accessed
`
`Offset
`Address
`
`Number of
`Records
`
`Record Link
`Valid
`
`No Entries
`Valid
`
`(31)
`
`(27-10)
`
`(9-2)
`
`(1)
`
`(0)
`
`Where:
`Hash Accessed—This bit indicates whether this hash has
`
`been accessed by switch engine 100. This can be used
`to age out hashes using the Least Recently Used (LRU)
`algorithm. Aging software on CPU 80 initially sets this
`bit on all the hash entries. When a node associated with
`
`this hash entry sends data on the network, switch
`engine 100 accesses the hash entry and clears this bit.
`The aging software can then come along later and
`delete all those hash entries that do not have the Hash
`Accessed bit cleared.
`Record Offset—The address offset from the Base Record
`
`Address at which the first record entry for the group of
`records at this hash is stored. The first record entry will
`thus reside at location (Base Record Address+Record
`Offset). The Base Record Address is stored in address
`registers 105.
`Number of Records—The number of records stored in the
`
`group of records, minus one. Therefore, if there are ten
`records stored in the group of records at this hash, this
`entry will contain a nine.
`Record Link Valid—If this bit is set, then the data stored
`at
`location (Base Record Address+Record Offset+
`(Number of Records><2)+2) is actually a Link Entry.
`Since each hash can only point to 128 address resolu-
`tion record entries (because of the number of bits in the
`Number of Record field),
`this bit can be used to
`increase the number of records for this hash value up to
`two-fold with Link Entries. If this bit is not set, and the
`No Entries Valid bit is also not set, then the data stored
`at (Base Record Address+Record Offset+(Number of
`Records><2))
`is the last possible address resolution
`record for this particular hash entry.
`No Entries Valid—If this bit is set, then there are no hash
`entries that match at this hash value.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`13
`
`13
`
`

`

`US 6,876,654 B1
`
`9
`Quite often, the hash derived from the least significant
`twelve bits of the Ethernet or IP/IPX address will, by itself,
`uniquely identify the flow with which the packet is associ-
`ated. Accordingly, the Number of Records will be one, and
`the switch