Load balancing switch protocols

Abstract

A switch to switch protocol for network load balancing which permits parallel redundant paths in a network to be utilized while reducing broadcast or problems inherent in prior switch configuration protocols. In particular, the present invention includes in the protocol a hello packet protocol which serves to exchange load balancing information among switches within a common load balance domain. Further, the hello packet protocol of the present invention enables detection and correction of improperly configured loops outside a load balance domain.

Claims

What is claimed is:

1. A method operable within a network switch for exchanging information among a plurality of network switches within a load balance domain, said method comprising the steps of:

a) exchanging hello packets between corresponding ports on a first switch of said plurality of network switches and a second switch of said plurality of network switches in order to identify switches within the load balance domain and switches outside the load balance domain, said hello packets include identification information identifying a particular port in a switch that generates a hello packet;

b) identifying if said corresponding ports are within said load balance domain in accordance with the exchanged hello packets; and

repeating steps a) and b) for each port on switches of said plurality of switches.

2. The method of claim 1 wherein said hello packets include hello request packets and hello response packets and wherein the step of exchanging includes the steps of:

transmitting a hello request packet from said first switch to said second switch; and

receiving, in said first switch, a hello response packet transmitted from said second switch to said first switch in response to transmission of said hello request packet.

3. The method of claim 2 wherein the step of identifying includes the step of:

identifying the corresponding port on said first switch as within said load balance domain in response to receipt of said hello response packet.

4. The method of claim 2 further comprising the step of:

identifying the corresponding port of said first switch as outside said load balance domain in response to failure to receive said hello response packet in response to transmission of said hello request packet from said first switch to said second switch.

5. The method of claim 4

wherein the step of transmitting hello request packets comprises the step of:

periodically transmitting said hello request packet from said first switch to said second switch, and

wherein the method further comprises the step of:

identifying a dead port within said load balance domain in accordance with said hello request packets.

6. The method of claim 5 wherein said hello request packets include a hello time parameter value and include a dead count parameter value and wherein the step of identifying a dead port includes the steps of:

first detecting, in said second switch, the expiration of a dead period of time equal to said hello time parameter value during which no hello request packet is received from said first switch;

detecting, in response to the step of first detecting, a consecutive number of dead periods during where said consecutive number is equal to said dead count parameter value; and

identifying said corresponding port of said second switch as a dead port in response to the detection of said consecutive dead periods.

7. The method of claim 2 wherein said hello request packets include a hello time parameter value and include a dead count parameter value and wherein the step of exchanging further comprises the steps of:

negotiating said hello time value and said dead count parameter between said first switch and said second switch.

8. The method of claim 7 wherein the step of negotiating includes the step of:

transmitting additional hello request packets with a modified hello time parameter value until a hello response packet is received with an equal hello time parameter value.

transmitting additional hello request packets with a modified dead count parameter value until a hello response packet is received with an equal dead count parameter value.

9. The method of claim 7 wherein the step of negotiating includes the step of:

transmitting additional hello request packets with a modified dead count parameter value until a hello response packet is received with an equal dead count parameter value.

10. The method of claim 2 wherein said hello request packets include a source MAC address value identifying the transmitting switch and identifying the port of the transmitting switch from which the hello request packet is transmitted and wherein the method further comprises the step of:

identifying an illegal configuration of network devices associated with a switch which received an illegal hello request packet.

11. The method of claim 10 wherein the step of identifying an illegal configuration includes the step of:

detecting reception of multiple hello request packets on a port of a switch where each of said multiple hello requests identifies a different source MAC address.

12. The method of claim 10 wherein the step of identifying an illegal configuration includes the step of:

detecting reception of multiple hello request packets on multiple ports of a switch where each of said multiple hello requests identifies an identical source MAC address.

13. A network switch including a computer readable storage medium tangibly embodying a method operable within said network switch for exchanging information among a plurality of network switches within a load balance domain, said method comprising the steps of:

a) exchanging hello packets between corresponding ports on a first switch of said plurality of network switches and a second switch of said plurality of network switches in order to identify switches within the load balance domain and switches outside the load balance domain, said hello packets include identification information identifying a particular port in a switch that generates a hello packet;

b) identifying if said corresponding ports are within said load balance domain in accordance with the exchanged hello packets; and

repeating steps a) and b) for each port on switches of said plurality of switches.

14. The switch of claim 13 wherein said hello packets include hello request packets and hello response packets and wherein the method step of exchanging includes the steps of:

transmitting a hello request packet from said first switch to said second switch; and

receiving, in said first switch, a hello response packet transmitted from said second switch to said first switch in response to transmission of said hello request packet.

15. The switch of claim 14 wherein the method step of identifying includes the step of:

identifying the corresponding port on said first switch as within said load balance domain in response to receipt of said hello response packet.

16. The switch of claim 14 wherein the method further comprises the step of:

identifying the corresponding port of said first switch as outside said load balance domain in response to failure to receive said hello response packet in response to transmission of said hello request packet from said first switch to said second switch.

17. The switch of claim 16

wherein the method step of transmitting hello request packets comprises the step of:

periodically transmitting said hello request packet from said first switch to said second switch, and

wherein the method further comprises the step of:

identifying a dead port within said load balance domain in accordance with said hello request packets.

18. The switch of claim 17 wherein said hello request packets include a hello time parameter value and include a dead count parameter value and wherein the method step of identifying a dead port includes the steps of:

first detecting, in said second switch, the expiration of a dead period of time equal to said hello time parameter value during which no hello request packet is received from said first switch;

detecting, in response to the step of first detecting, a consecutive number of dead periods during where said consecutive number is equal to said dead count parameter value; and

identifying said corresponding port of said second switch as a dead port in response to the detection of said consecutive dead periods.

19. The switch of claim 14 wherein said hello request packets include a hello time parameter value and include a dead count parameter value and wherein the method step of exchanging further comprises the steps of:

negotiating said hello time value and said dead count parameter between said first switch and said second switch.

20. The switch of claim 19 wherein the method step of negotiating includes the step of:

transmitting additional hello request packets with a modified hello time parameter value until a hello response packet is received with an equal hello time parameter value.

transmitting additional hello request packets with a modified dead count parameter value until a hello response packet is received with an equal dead count parameter value.

21. The switch of claim 19 wherein the method step of negotiating includes the step of:

transmitting additional hello request packets with a modified dead count parameter value until a hello response packet is received with an equal dead count parameter value.

22. The switch of claim 14 wherein said hello request packets include a source MAC address value identifying the transmitting switch and identifying the port of the transmitting switch from which the hello request packet is transmitted and wherein the method further comprises the step of:

identifying an illegal configuration of network devices associated with a switch which received an illegal hello request packet.

23. The switch of claim 22 wherein the method step of identifying an illegal configuration includes the step of:

detecting reception of multiple hello request packets on a port of a switch where each of said multiple hello requests identifies a different source MAC address.

24. The switch of claim 22 wherein the method step of identifying an illegal configuration includes the step of:

detecting reception of multiple hello request packets on multiple ports of a switch where each of said multiple hello requests identifies an identical source MAC address.

25. A method operable within a network switch for exchanging information among a plurality of network switches within a load balance domain, said method comprising the steps of:

a) exchanging hello packets between corresponding ports on a first switch of said plurality of network switches and a second switch of said plurality of network switches;

b) identifying said corresponding ports as within said load balance domain in accordance with the exchanged hello packets; and

repeating steps a) and b) for each port on switches of said plurality of switches;

wherein said hello packets include hello request packets and hello response packets and wherein the step of exchanging includes the steps of:

transmitting a hello request packet from said first switch to said second switch; and

receiving, in said first switch, a hello response packet transmitted from said second switch to said first switch in response to transmission of said hello request packet;

identifying the corresponding port of said first switch as outside said load balance domain in response to failure to receive said hello response packet in response to transmission of said hello request packet from said first switch to said second switch;

wherein the step of transmitting hello request packets comprises the step of:

periodically transmitting said hello request packet from said first switch to said second switch; and

wherein the method further comprises the step of:

identifying a dead port within said load balance domain in accordance with said hello request packets;

wherein said hello request packets include a hello time parameter value and include a dead count parameter value and wherein the step of identifying a dead port includes the steps of:

first detecting, in said second switch, the expiration of a dead period of time equal to said hello time parameter value during which no hello request packet is received from said first switch;

detecting, in response to the step of first detecting, a consecutive number of dead periods during where said consecutive number is equal to said dead count parameter value; and

identifying said corresponding port of said second switch as a dead port in response to the detection of said consecutive dead periods.

26. A method operable within a network switch for exchanging information among a plurality of network switches within a load balance domain, said method comprising the steps of:

a) exchanging hello packets between corresponding ports on a first switch of said plurality of network switches and a second switch of said plurality of network switches;

b) identifying said corresponding ports as within said load balance domain in accordance with the exchanged hello packets; and

repeating steps a) and b) for each port on switches of said plurality of switches;

wherein said hello packets include hello request packets and hello response packets and wherein the step of exchanging includes the steps of:

transmitting a hello request packet from said first switch to said second switch; and

receiving, in said first switch, a hello response packet transmitted from said second switch to said first switch in response to transmission of said hello request packet;

wherein said hello request packets include a source MAC address value identifying the transmitting switch and identifying the port of the transmitting switch from which the hello request packet is transmitted and wherein the method further comprises the step of:

identifying an illegal configuration of network devices associated with a switch which received an illegal hello request packet.

27. The method of claim 26 wherein the step of identifying an illegal configuration includes the step of:

detecting reception of multiple hello request packets on a port of a switch where each of said multiple hello requests identifies a different source MAC address.

28. The method of claim 26 wherein the step of identifying an illegal configuration includes the step of:

detecting reception of multiple hello request packets on multiple ports of a switch where each of said multiple hello requests identifies an identical source MAC address.

29. A network switch including a computer readable storage medium tangibly embodying a method operable within said network switch for exchanging information among a plurality of network switches within a load balance domain, said method comprising the steps of:

a) exchanging hello packets between corresponding ports on a first switch of said plurality of network switches and a second switch of said plurality of network switches;

b) identifying said corresponding ports as within said load balance domain in accordance with the exchanged hello packets; and

repeating steps a) and b) for each port on switches of said plurality of switches;

wherein said hello packets include hello request packets and hello response packets and wherein the method step of exchanging includes the steps of:

transmitting a hello request packet from said first switch to said second switch; and

receiving, in said first switch, a hello response packet transmitted from said second switch to said first switch in response to transmission of said hello request packet;

wherein the method step further comprises the step of identifying the corresponding port of said first switch as outside said load balance domain in response to failure to receive said hello response packet in response to transmission of said hello request packet from said first switch to said second switch;

wherein the method step of transmitting hello request packets comprises the step of:

periodically transmitting said hello request packet from said first switch to said second switch; and

wherein the method further comprises the step of:

identifying a dead port within said load balance domain in accordance with said hello request packets;

wherein said hello request packets include a hello time parameter value and include a dead count parameter value and wherein the method step of identifying a dead port includes the steps of:

first detecting, in said second switch, the expiration of a dead period of time equal to said hello time parameter value during which no hello request packet is received from said first switch;

detecting, in response to the step of first detecting, a consecutive number of dead periods during where said consecutive number is equal to said dead count parameter value; and

identifying said corresponding port of said second switch as a dead port in response to the detection of said consecutive dead periods.

30. A network switch including a computer readable storage medium tangibly embodying a method operable within said network switch for exchanging information among a plurality of network switches within a load balance domain, said method comprising the steps of:

a) exchanging hello packets between corresponding ports on a first switch of said plurality of network switches and a second switch of said plurality of network switches;

b) identifying said corresponding ports as within said load balance domain in accordance with the exchanged hello packets; and

repeating steps a) and b) for each port on switches of said plurality of switches;

wherein said hello packets include hello request packets and hello response packets and wherein the step of exchanging includes the steps of:

transmitting a hello request packet from said first switch to said second switch; and

receiving, in said first switch, a hello response packet transmitted from said second switch to said first switch in response to transmission of said hello request packet;

wherein said hello request packets include a source MAC address value identifying the transmitting switch and identifying the port of the transmitting switch from which the hello request packet is transmitted and wherein the method further comprises the step of:

identifying an illegal configuration of network devices associated with a switch which received an illegal hello request packet.

31. The switch of claim 30 wherein the method step of identifying an illegal configuration includes the step of:

detecting reception of multiple hello request packets on a port of a switch where each of said multiple hello requests identifies a different source MAC address.

32. The switch of claim 30 wherein the method step of identifying an illegal configuration includes the step of:

detecting reception of multiple hello request packets on multiple ports of a switch where each of said multiple hello requests identifies an identical source MAC address.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to communication networks and more specifically to network switches and associated switch to switch protocols which provide improved bandwidth utilization and load balancing in data processing communication networks having redundant paths between network devices.

2. Discussion of Related Art

It is common in present computing environments to connect a plurality of computing systems and devices through a communication medium often referred to as a network. Such networks among communicating devices permit devices (or users of devices) to easily exchange and share information among the various devices. The Internet is a presently popular example of such networking on a global scale. Individual users attach their computers to the Internet, thereby enabling sharing of vast quantities of data on other computers geographically dispersed throughout the world.

Networked computing systems may be configured and graphically depicted in a wide variety of common topologies. In other words, the particular configurations of network communication links (also referred to as paths) and devices between a particular pair of devices wishing to exchange information may be widely varied. Any particular connection between two computers attached to a network may be direct or may pass through a large number of intermediate devices in the network. In addition, there may be a plurality of alternative paths through the network connecting any two network devices. Present day computing networks are therefore complex and vary in their configurations and topologies.

Most present network communication media and protocols are referred to as packet oriented. A protocol or communication medium may be said to be packet oriented in that information to be exchanged over the network is broken into discrete sized packets of information. A block of information to be transferred over the network is decomposed into one or more packets for purposes of transmission over the network. At the receiving end of the network transmission, the packets are re-assembled into the original block of data.

In general, each packet includes embedded control and addressing information that identifies the source device which originated the transmission of the packet and which identifies the destination device to which the packet is transmitted. Identification of source and destination devices is by means of an address associated with each device. An address is an identifier which is unique within the particular computing network to identify each device associated with the network. Such addresses may be unique to only a particular network environment (i.e., a network used to interconnect a single, self-contained computing environment) or may be generated and assigned to devices so as to be globally unique in co-operation with networking standards organizations.

At the lowest level of network communication, such addresses are often referred to as MAC address (Media ACcess address). Network protocols operable above this lowest level of communication may use other addresses for other purposes in the higher level communication techniques. But in most network low level communication levels, operable on the physical link medium, an address is referred to as a MAC address.

In many present commercially available network environments, the network communication medium is in essence a bus commonly attached to a plurality of devices over which the devices exchange. In a simple networking topology, all devices may be attached to a such a bus structured common network medium. Any particular single network medium has a maximum data exchange bandwidth associated therewith. The maximum data exchange bandwidth of a medium is determined by a number of electrical and physical properties of the medium and protocols used to communicate over that medium. For example, a popular family of related network media and protocols are collectively referred to as Ethernet. Ethernet defines a standard protocol for the exchange of messages over the communication medium. A variety of communication media are also defined as part of the Ethernet family. The communication bandwidth of the Ethernet family of standards range from approximately 10 Mbit (million bits of information) per second to 1 Gbit per second Therefore, a single (slow) Ethernet connection, for example, has a maximum data exchange bandwidth of approximately 10 Mbit per second.

In present network computing environments, a number of devices are used in addition to interconnected computing systems to efficiently transfer data over the network. Routers and switches are in general network devices which segregate information flows over various segments of a computer network. A segment, as used herein, is any subset of the network computing environment including devices and their respective interconnecting communication links. As noted above, a single computer network communication link has a maximum data transfer bandwidth parameter defining the maximum rate of information exchange over that network. Where all devices on a computer network share a common network medium, the maximum bandwidth of the computer network may be rapidly reached. The overall performance of the networked computing environment may be thereby reduced because information exchange requests may have to await completion of earlier information exchange requests presently utilizing the communication link.

It is often the case, however, that particular subsets of devices attached to the network have requirements for voluminous communication among members of the same subset but less of a requirement for information exchange with other devices outside their own subset. Though standard switch features generally do not include identifying such logical groupings of devices, some enhanced switching features do permit such logic to be performed within a switch device. For example, some enhanced switch features include the concept of defining and routing information based on virtual LAN (VLAN) definitions. In a VLAN, a group of devices may be defined as logically being isolated on a separate network although physically they are connected to a larger network of devices. VLAN features of enhanced switches are capable of recognizing such VLAN information and can route information appropriately so that devices in a particular VLAN are logically segregated from devices outside the VLAN.

For example, the financial department of a large corporation may have significant information exchange requirements within the financial department but comparatively insignificant needs for data exchange with other departments. Likewise, an engineering group may have significant needs for data exchange within members (computing systems and devices) of the same engineering group but not outside the engineering group. There may in fact be multiple of such subsets of devices in a typical computing network. It is therefore desirable to segregate such subsets of devices from one another so as to reduce the volume of information exchange applied to the various segments of the computer network.

In particular, a switch device is a device that filters out packets on the network destined for devices outside a defined subset (segment) and forwards information directed between computing devices on different segments of a networked computing environment. The filtering and forwarding of such information is based on configuration information within the switch that describes the data packets to be filtered and forwarded in terms of source and/or destination address information (once address locations are "learned" by the switch(es)).

Network switch devices and protocols associated therewith are also used to manage redundant paths between network devices. Where there is but a single path connecting two network devices, that single path, including all intermediate devices between the source and destination devices, represent a single point of failure in network communications between that source and destination device. It is therefore common in network computing environments to utilize a plurality of redundant paths to enhance reliability of the network. Multiple paths between two devices enhances reliability of network communication between the devices by allowing for a redundant (backup) network path to be used between two devices when a primary path fails.

FIG. 1 shows an exemplary, simple networked computing environment in which multiple paths exist for communication between devices A 100, B 102, and C 104. These exemplary network devices are each attached to one of a plurality of switches (S1106, S2108, S3110, and S4112). Each device has multiple possible paths to each of the other two devices. For example, device A 100 may exchange information with device C 104 through any of three possible paths (via switches S1106 and S4112, respectively). The first exemplary path is a direct path connecting device A 100 directly to device C 104 through a port on switch S1106 and a port on switch S4112. A second path is through switch S1106 to switch S3110 and then through switch S4112. A third path is via switch S1106, switch S2108, and switch S4114. These three paths may be used as redundant communication paths connecting the two devices A 100 and C 104. Where a first path fails, the second path or third may be activated to assume responsibility for exchange of information between devices A and C. In like manner, there are three paths for communication between devices A 100 and B 102 and between devices B 102 and C 104.

Where redundant paths are available in such network computing environments, it remains a problem to effectively utilize the full available bandwidth. It would be desirable to utilize all redundant paths in parallel so as to increase the available communication bandwidth between two communicating devices. Where only a single path is used, the maximum bandwidth for exchange of information is limited to that of a single communication link. Where, on the other hand, all redundant links are used in parallel, the maximum communication bandwidth is increased by the number of links used in parallel. For example, as shown in FIG. 1, the communication bandwidth between any of the devices could, in theory, be increased by up to a factor of three.

However, as presently practiced in the art, protocols used among switch devices (e.g., S1106 through S4112) render such parallel communication paths unusable. Switches 105 through 112 as presently practiced in the art often use a protocol commonly referred to as "spanning tree" to discover the existence of redundant communication paths as known to a network of switches. The spanning tree protocol is described in detail in a proposed IEEE standard P802.1p entitled Standard for Local and Metropolitan Area Networks Supplement to Media Access Control (MAC) Bridges: Traffic Class Expediting and Dynamic Multicast Filtering.

The spanning tree protocol as implemented in switches broadcasts (more precisely multicasts) information from the switch out to all devices that recognize the selected multicast address connected to paths from the switch. A multicast message is one which is directed to all devices rather than to a particular destination address on the network. The information in the multicast message describes the address forwarding information known to that switch. From such information shared among all the switches, each switch can derive the various paths in the network. Each switch device so attached to the multicasting device receives the information and forwards (multicasts) the message to each device attached to it (except the path from which it directly received the message), and so on. If such a multicast message returns on a path to the originating device, a loop must exist among the paths connecting the various switches. To reduce the number of messages generated on the network by virtue of such multicast messages, the spanning tree protocol requires that redundant paths so discovered be disabled. In a large network without spanning tree protocol to disable redundant paths, received multicast messages can "cascade" from each receiving switch to all other attached switches. The volume of such cascading messages may grow rapidly or even exponentially. Such multicast messages exchanged among the switched may in fact require a substantial portion of the available communication bandwidth of the network. Such conditions are often referred to as "broadcast storms."

The spanning tree protocol therefore requires the disabling of redundant paths to avoid broadcast storms. Only when a path is known to have failed will a redundant path be enabled and used for the exchange of data. The spanning tree protocol therefore precludes aggregation of the available bandwidth to improve communication bandwidth by using multiple redundant paths in parallel. FIG. 2 is a block diagram of the same exemplary network of FIG. 1 where three communication links 114 between the switches have been disabled to prevent loops in the network and the resultant broadcast storm otherwise inherent in the spanning tree protocol.

Another problem with the spanning tree protocol arises from the fact that a preferred path may be unavailable due to the need to disable paths that cause loops among the switches. For example, as shown in FIG. 2, the preferred path between switches S1106 and S4112 may be the direct one which is disabled. To leave this direct communication link enabled would permit loops in the paths among the switches. Rather, a more circuitous route through switches S1, 106, S3110 and S4112 must be used to exchange information between switches S1106 and S4112. The spanning tree protocol does not assure that the best path between two switches will be left enabled. Rather, it merely attempts to assure that some path between switches is available, specifically, a relatively minimal path connecting all switches--a spanning tree.

The spanning tree protocol therefore precludes maximizing use of available bandwidth in a network of switches.

Some switches have provided a partial solution to this problem by using a technique known as "trunking." Where there are multiple paths directly between two switches, the multiple paths serve as redundant communication paths but are trunked by the switches and treated logically as though they were a single path with higher maximum bandwidth. FIG. 3 is a block diagram of the same exemplary network environment of FIG. 2 wherein a plurality of communication paths between switch S1106 and S3110 are trunked. The communication path between switches S1106 and S3110 is therefore capable of using the trunked paths between them as though they were a single connection in terms of the spanning tree protocols. Since the redundant paths are treated as a single path for purposes of the spanning tree protocols, they need not be shut down to preclude broadcast storms,

However, trunking does not address the bandwidth issue in a broad sense. Rather, the trunking technique is only applicable where the multiple paths are between a particular pair of switches. The bandwidth limit is merely shifted from that of a single communication link to that of the number of communication links supported by a single switch.

It is a further problem that by precluding use of redundant links between switches, the spanning tree protocol also precludes the ability to balance communication loads among the redundant paths between switches. Where such multiple paths are allowed to simultaneously operate, it would be desirable for the switches to distribute the packet exchange communication among them over such multiple paths. Such distribution, often referred to as load balancing, further enhances the ability of the network to optimize the utilization of available throughput in the network of switches. Underutilized paths may be used to offload packet communication on overloaded paths.

It is therefore a problem in present networks of switches to simultaneously operate redundant paths between switches of the network to thereby maximize utilization of available bandwidth and to thereby communicate among the switches to balance communication loads over redundant paths.

It is a particular problem to efficiently identify ports of switches in a network which are within a common load balance domain--a common set of switches interconnected so as to permit load balancing of multiple parallel paths between them. Prior techniques, such as the spanning tree protocol, disable redundant paths among the switches so as to avoid "broadcast storms." In so doing, they preclude optimal usage of available bandwidth among the switches of a network.

It is evident from the above discussion that improved switches and associated protocols are needed to manage redundant communication paths while permitting improved bandwidth utilization of all communication links in a network and balancing of loads among such redundant communication paths.

SUMMARY OF THE INVENTION

The present invention solves the above and other problems, thereby advancing the state of useful arts, by providing network switch devices and associated switch to switch protocols which permit the operation of multiple links throughout the network involving multiple switches, and which provide for improved utilization of the aggregate bandwidth of all paths in the network. Further, as compared to prior techniques, the best communication path between any two devices may be utilized as compared to only paths which preclude looping among the switches (as taught by spanning a tree protocol techniques presently practiced).

By permitting parallel use of all communication paths and switches in the network, the present invention improves scalability of network communication bandwidth as compared prior techniques. The aggregate bandwidth capability within the entire network may be increased by simply adding additional communication paths and associated switches.

In particular, the present invention includes a protocol operable between switches designed in accordance with the present invention. The protocol is used to exchange information among the compatible switch devices in the network. The exchange information allows switches implemented in accordance with the present invention to distribute communication loads over multiple paths of the network. A distribution of such communication loads permits the requisite processing to be fairly distributed overall communication paths and switches in the network further, the protocol and switches of the present invention permit recovery from failed communication links by shifting the load to other links still operating in parallel. Where other links are available and still operating in parallel, switches operable in accordance with the present invention recover from the failed link faster than previous techniques.

More specifically, the present invention includes within its switch to switch protocol a "hello" protocol to determine which ports of switches within the network are capable of performing load balancing with other switches of the network. Such sets of switches are referred to as within a load balance domain. Further, the present invention hello protocol is used to detect incorrect configurations outside the load balance domain.

All switches have multiple ports each of which may be attached by a communication link to other switches. A particular switch is therefore within a load balance domain with other switches if at least one of the ports in the switch (operable in accordance with the present invention) is connected to another switch (also operable in accordance with the present invention) within the same load balance domain. Other ports on a given switch may be connected to other devices outside a particular load balance domain.

The hello protocol of the present invention, as noted above, is used for identifying switches within the load balance domain and also is used to discover improper loops and configurations outside the load balance domain. In particular, the hello protocol packets include identification information identifying a particular port on the switch which generates the packet. In normal processing with other switches in a load balance domain operable in accordance with present invention, a hello request packet elicits a hello response packet from an adjacent switch. When a hello request packet containing identification information for the transmitting switch is returned identically to the originating device (i.e., in the identical request format), the condition indicates in improper loop or configuration outside the load balancing domain. The condition is noted so as to allow appropriate reconfiguration by operator.

An appropriate hello response packet received in response to a hello request packet identifies the port of the transmitting switch as within a load balance domain with other switches. Switches within the load balance domain thereafter exchange further information to allow management of the load balance domain and to effectively utilize the communication bandwidth represented thereby.

The above, and other features, aspects and advantages of the present invention will become apparent from the following descriptions and attached drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of a typical switch network having redundant paths connecting a network of switches and associated hosts all of which may be simultaneously operable in accordance with the present invention.

FIG. 2 is a block diagram of a switch network similar to that of FIG. 1 but wherein the spanning tree protocol has disabled redundant links.

FIG. 3 is a block diagram of a switch network similar to that of FIG. 1 but in which one path between two switches uses trunked lines to improve throughput.

FIG. 4 is a diagram of the loop balance protocol header associated with all loop balance protocol packets of the present invention.

FIG. 5 is a diagram of a hello packet used in the hello protocol of the present invention to identify ports in a load balance domain.

FIG. 6 is a diagram of the dead count/flags field of a hello packet as in FIG. 5.

FIG. 7 is a diagram of an illegal switch network configuration detected by the hello protocol of the present invention.

FIG. 8 depicts the hello protocol state machine operable in the protocols of the present invention to detect other ports in the load balance domain and to detect illegal loop configurations in the network.

FIG. 9 is a diagram of a loop bit negotiation packet used in the loop bit negotiation protocol of the present invention.

FIG. 10 depicts the loop bit negotiation protocol state machine operable in the protocols of the present invention to assign a short, unique identifier to each port in the load balance domain.

FIG. 11 is a diagram of a cost packet used in the cost propagation protocol of the present invention.

FIG. 12 is a diagram of a flags field of the cost packet of FIG. 11.

FIG. 13 depicts a switch network in which trunked lines require cost protocols of the present invention to resolve the preferred path for packet exchange between switches of the network.

FIG. 14 is a diagram of a speed (throughput) field of a cost packet in accordance with the present invention.

FIG. 15 is a diagram of a cost packet acknowledgment packet used in the cost propagation protocol of the present invention.

FIG. 16 is a diagram of an update cost packet used in the cost propagation protocol of the present invention.

FIG. 17 is a diagram of an update cost acknowledgment packet used in the cost propagation protocol of the present invention.

FIG. 18 depicts an exemplary pruned broadcast tree determined in accordance with the protocols of the present invention.

FIG. 19 is a diagram of a broadcast add packet used in determining a pruned broadcast tree in accordance with the present invention.

FIG. 20 is a diagram of a broadcast delete packet used in determining a pruned broadcast tree in accordance with the present invention.

FIG. 21 depicts the broadcast path determination protocol state machine operable in the protocols of the present invention to determine a pruned tree broadcast path for switches operable in accordance with the present invention.

FIG. 22 is a diagram of a MAC address information packet used in MAC address learning and discovery protocols in accordance with the present invention.

FIG. 23 is a diagram of a VLAN tag field in a MAC address information packet as in FIG. 22.

FIG. 24 is a diagram of a MAC address query packet used in MAC address learning and discovery protocols in accordance with the present invention.

FIG. 25 depicts an exemplary path between switches determined in accordance with the protocols of the present invention.

FIG. 26 depicts an exemplary present state for a network of switches operable in accordance with the present invention prior to link recovery triggered by a line failure.

FIG. 27 depicts a second exemplary state for the network of switch of FIG. 26 wherein an alternate path has been selected in accordance with a first embodiment of failure recovery of the present invention.

FIG. 28 depicts a second exemplary state for the network of switch of FIG. 26 wherein an alternate path has been selected in accordance with a second embodiment of failure recovery of the present invention.

FIG. 29 depicts a network of switches operable in accordance with the present invention and host systems wherein VLAN standard switching techniques are integrated with the load balancing protocols of the present invention.

FIG. 30 depicts a network of switches operable in accordance with the present invention and host systems wherein VLAN standard switching techniques are integrated with the load balancing protocols of the present invention.

FIG. 31 depicts a typical connection of multiple load balancing domains through a common non-load balancing switch.

FIG. 32 is a block diagram of the design of an exemplary packet switch operable in accordance with the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

While the invention is susceptible to various modifications and alternative forms, a specific embodiment thereof has been shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that it is not intended to limit the invention to the particular form disclosed, but on the contrary, the invention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention as defined by the appended claims.

1. Introduction

The invention of this application is a new switch-to-switch protocol for controlling switches operable in accordance with the protocol. The protocol enables load balancing communication traffic over multiple active switches in a network. As compared to prior techniques, such as the spanning tree protocol, the load balancing protocols of the present invention permit more efficient utilization of available bandwidth in the communication network. Such switches operable in accordance with the present invention are referred to herein simply as "switch" or "load balancing switch." A preferred embodiment of this protocol is discussed in detail below. The goals of load balancing addressed by this preferred embodiment, together with those not addressed, are summarized below:

1. To distribute packet loads fairly across all the load-balancing switch paths.

2. To allow any arbitrary interconnection of switches to automatically load balance across all the links for all traffic. Each source-destination pair will use a single path, and the larger the number of source-destination pairs, the better the load balancing. Broadcast and Multicast packets will also cross multiple links, although loading will not change the path with time. Failure of a link, recovery of a failed link, or discovery of a newly activated switch, will force a choice of new broadcast paths.

3. To recover from any link failure by shifting the load to links that are still up, but without the delay incurred with the standard spanning-tree protocol.

4. To require no user configuration other than on or off.

5. To be completely compatible with layer 3 switching, VLANs, VLAN tagging and legacy switches, and switches running spanning-tree protocol.

6. To be completely independent of any level 3 protocol.

2. Concept Overview

FIG. 1 depicts a simple example of a meshed switch topology. In this example, if Host 100 sends out broadcast packets to find Host 104, the broadcasts will very quickly start looping and duplicating as the broadcasts are repeated out each port. This broadcast storm is prevented with spanning-tree protocol by shutting down all but one path through this network.

When the preferred embodiment protocol is used, packet streams will be fairly distributed across all possible paths, with an effort to keep latency the same across all paths. The path picked will be based on cost. Those paths with lowest cost will have more traffic added than those with higher cost. The cost determination will be defined based on latency and throughput. The alternate paths and cost information will be discovered and passed between the switches using the preferred embodiment protocol.

Flooded packets (those generally sent out all available port such as broadcast and multicast packets) will also flow down potentially different paths based on the edge switch from which they initially entered the load-balance domain. These broadcast paths are normally set up as links are initialized in the load balance domain, and once setup, do not change unless a link break occurs. This simplifies the protocol and hardware requirements on the switches but still uses all the links for these packets. Broadcast control features such as layer 3 proxy replies and RIP/SAP filtering will complement this feature by preventing the need for many of the broadcasts from crossing the load balance domain in the first place. Unicast packets with an unknown destination MAC address are handled with a MAC address discovery procedure and are not broadcast through the switch domain.

The basic idea of the preferred embodiment protocol is that all switches pass information between themselves so that they can learn the cost to one another of handling additional traffic. All links between the switches must be point-to-point. A point-to-point link is one which connects exactly two devices, one at each end of the link. A multi-point link, by contrast, acts more as a bus where all devices are attached to a common link and monitor for their specific assigned address If non-point-to-point links are used, the protocol will discover this and shut down all but one link, in much the same way as the spanning-tree protocol. Each switch will keep a table of the costs for all paths to a given switch. The cost associated with a path is with respect to packets transmitted from a first switch, a source switch, to a second switch, a destination switch, via zero or more intervening switches and communication links. The MAC address of the source switch is referred to as the source address and the address of the destination switch is referred to as the destination address.

When a new source address is learned on a switch at the edge of the network (edge of the load balance domain), it will inform all the other switches of this new host address and the fact that the switch can get there. All the switches in the domain then load this new MAC address into their respective switching tables and use the their cost calculations for the given edge switch to determine on which port to send any packets destined for this new address.

Since the cost to get to a given edge switch will vary with time, the preferred embodiment protocol updates the costs periodically so that new sources learned may take a different path than those learned earlier. When source addresses time-out and are relearned, they may take a different path than during their previous instantiation depending on link loads at the current time. The load balancing aspects therefore occur when a statistically large sample of source-destination pairs have paths set up through the network.

As an example assume that all the links in FIG. 1 have the same cost. Using the preferred embodiment protocol the following link paths would be used as the different hosts communicate:

Host 100 to Host 102 . . . in port 4 switch 106, out port 1 switch 106, in port 1 switch 110, out port 4 switch 110.

Host 100 to Host 104 . . . in port 4 switch 106, out port 2 switch 106, in port 2 switch 112, out port 4 switch 112.

Host 102 to Host 104 . . . in port 4 switch 110, out port 3 switch 110, in port 1 switch 112, out port 4 switch 112.

This path sequence would be impossible with the spanning-tree protocol because the links traversed would define a loop, forcing the protocol to shut one of them down. Spanning-tree would force all the traffic on a single link for at least part of the path.

In the preferred embodiment protocol, flooded packets with a given source MAC address are sent out a pruned tree such that all switches in the domain will receive the packets once via a single best path. The protocol will create the single best path.

There are many subtleties in the preferred embodiment protocol to prevent out-of-sequence packets when links go down and to insure convergence of the paths chosen before they are used. All this and much more is discussed in the following sections. The preferred embodiment protocol is intended to be used on high-speed LAN switches (10 megabit links or greater). If it is used on WAN links or links with very high latency (point-to-point round trip latency >0.5 seconds), some of the time values defined below would need to be changed. The protocol also is intended for use in a LAN backbone build with 2 to 200 switches. The protocol leverages previous experiences with OSPF, RIP and serves to obviate the difficulties and limitations that routing protocols impose.

Packet switches, in general, use a general purpose microprocessor (CPU) to perform management of switch addressing information and to perform the requisite packet forwarding to move received packets to an intended destination. To perform at the required speeds in high performance networks, switches also incorporate custom circuits specifically designed to assist the CPU in performing its packet switching.

FIG. 32 is a block diagram of a packet switch 3200 operable in accordance with the present invention to permit load balancing over redundant, simultaneously active, paths between switches of a network. CPU 3202 performs overall configuration and control of the switch 3200 operation. As noted however, CPU 3202 operates in cooperation with switch control 3204, an application specific integrated circuit (ASIC) designed to assist CPU 3202 in performing packet switching at high speeds required by modern networks. Switch control 3204 includes inbound and outbound high speed FIFOs (3206 and 3208, respectively) for exchanging data over switch bus 3252 with port modules. Memory 3210 includes a high and low priority inbound queue (3212 and 3214, respectively) and outbound queue 3216. High priority inbound queue 3212 is used to hold received switch control packets (i.e., load balance packets in accordance with the present invention) awaiting processing by CPU 3202 while low priority inbound queue 3214 holds other packets awaiting processing by CPU 3202. Outbound queue 3216 holds packets awaiting transmission to switch bus 3250 via switch control 3204 through its outbound FIFO 3208. CPU 3202, switch control 3204 and memory 3210 exchange information over processor bus 3252 largely independent of activity on switch bus 3250.

The ports of the switch are preferably embodied as plug-in modules that connect to switch bus 3250. Each such module may be, for example, a multi-port module 3218 having a plurality of ports in a single module or may be a single port module 3236. A multi-port module provides an aggregate packet switch performance capable of handling a number of slower individual ports. For example, in the preferred embodiment, both the single port module 3236 and the multi-port module 3218 provide approximately 1 Gbit per second packet switching performance. The single port module 3236 therefore can process packet switching on a single port at speeds up to 1 Gbit per second. The multi-port module 3218 provides similar aggregate performance but distributes the bandwidth over, preferably, eight ports each operating at speeds up to 100 Mbit persecond.

Each port includes high speed FIFOs for exchanging data over its respective port. Specifically, each port, 3220, 3228, and 3237, preferably includes an inbound FIFO 3222, 3230, and 3238, respectively for receiving packets from the network medium connected to the port. Further, each port 3220, 3228, and 3237, preferably includes a high priority outbound FIFO 3224, 3232, and 3240, respectively, and a low priority outbound FIFO 3226, 3234, and 3242, respectively. The low priority outbound FIFOs are used to queue data associated with transmission of normal packets while the high priority outbound FIFO is used to queue data associated with transmission of control packets including load balance packets of the present invention as well as spanning tree protocol packets.

Each module (318 and 3236) includes circuits (not specifically shown) to connect its port FIFOs to the switch bus 3250.

As packets are received from a port, the packet data is applied to the switch bus 3250 in such a manner as to permit monitoring of the packet data by switch control 3204. Switch control 3204 processes each packet by performing one of three functions as the packet passes over switch bus 3250, namely, steal, copy or forward. The steal function absorbs the packet information (through inbound FIFO 3206 of switch control 3204) thereby providing the packet only to CPU 3202 for processing. As noted above, the packet data is stored either in the high priority inbound queue 3212 or the low priority inbound queue 3216 in memory 3219 to await processing by CPU 3202. When the packet is so stolen, switch control 3204 prevents the other switch modules on switch bus 3250 from receiving the stolen packet. A copy function is similar, but the packet is copied to an appropriate queue by switch control 3204 and the packet is routed to appropriate other port in a module connected to the switch bus 3250. The forward function routes the received packet to the identified destination port without retaining a copy in memory 3210 and without intervention by CPU 3202.

In general, switch control 3204 manages access to switch bus 3250 by all port modules (i.e., 3218 and 3236). All port modules "listen" to packets as they are received and applied by a receiving port module to switch bus 3250. If the packet is to be forwarded to another port, switch control 3204 applies a trailer message to switch bus 3250 following the end of the packet to identify which port should accept the received packet for forwarding to its associated network link.

Switch control 3204 controls the "forwarding" of received packets to appropriate locations within the switch for further processing and/or for transmission out another switch port. In the preferred embodiment, switch control 3204 performs the following operations:

recognize packets of the load balance protocol and pass them only to CPU 3202. Switch control 3204 must be careful not to be confused regarding this function when ACK packets are returned having a source MAC address of the switch receiving the packets.

transmit load balance protocol packets to selected ports in the switch.

determine the number of bytes queued on the inbound and outbound queues associated with each port (this is preferably performed in conjunction with ASIC interface devices operable within the port).

recognize packets addressed to the switch MAC address as directed to CPU 3202 for processing as a load balance protocol packet.

maintain tables (under control of CPU 3202) which direct packets for particular destination MAC addresses to a selected port or ports.

drop a received packet directed to a specific destination MAC address in accordance with information entered in the addressing table (alternatively, the MAC address could be removed from the addressing table so that the packet will be passed to CPU 3202 and discarded there). This feature is needed when packets must be sent to the "bit bucket" when a new path is being created after a link failure.

receive a load balance protocol packet with a specific source MAC address to be received on one port and forwarded to another specified port using the same source MAC address (e.g., for load balance protocol cost packets and associated ACKs).

maintain a broadcast path (under control of CPU 3202) for a given MAC address, however, the broadcast path for all MAC addresses from a given edge switch can use the same broadcast path. Preferably this pruned tree path is maintained as a bit mask field with a bit representing each switch in the pruned tree path and the mask may be the same for all MAC addresses from a given switch.

pass to CPU 3202 any received packet from and unknown source MAC address.

pass to CPU 3202 any received packet destined for an unknown destination address. Optionally, under control of switch control 3204, the packet may be flooded to all non-load balance ports of the switch.

block ports from packet exchange other than control packets (i.e., processing and passing load balance and spanning tree control packets to CPU 3202 as required but blocking data packets from or to identified blocked ports).

not interrupt CPU 3202 to indicate that a MAC address has moved when a source MAC address is received on a load balance port other than the load balance port it was programmed to transmit out of.

Those skilled in the art will recognize many other functions that may be performed in an ASIC assist device such as switch control 3204. Similarly, those skilled int he art will recognize that the above and other functions may be performed by a suitable programmed general purpose processor having adequate performance or where the packet switching performance is a less critical factor.

3. Protocol Definition

The detailed discussion of the preferred embodiment protocol that follows is based on the following definitions:

1. Load Balance Domain--This is a group of switches exchanging load-balance protocol packets. There may or may not be redundant links within the domain. A given switch may have some links in the domain and some outside the domain. A switch port is only in the domain if it sends load- balance protocol packets and another switch sends back load balance protocol packets. Load-balancing links must be point-to-point switch links. Hub links between the load balancing switch links are not permitted.

2. Edge Switch--This is a switch which has at least one port within the load balance domain and at least one port outside the domain connected to, for example, a host device. Ports outside the load balance domain learn about such hosts via packets sent by the hosts themselves. By contrast, ports inside the load balance domain learn about hosts connected to edge switches via MAC information packets (as described further herein below in section 3.5). A switch that has all ports inside the load balance domain cannot be an edge switch. Those skilled in the art will understand this definition to be different than a similar term used in Asynchronous Transmission Mode communication standards (ATM).

3. Non Edge Adjacent Port--This term refers to a port that goes through another switch(es) before it connects to the edge switch in question. A port may be edge adjacent to 1 switch and non-edge adjacent to 1 or more switches.

4. Edge Adjacent Port--This term is used to refer to a switch port that has a direct connection to an edge switch. At most, a port can be edge adjacent to only one switch at a time, but may be non-edge adjacent to many switches.

5. Adjacent Switch--This is a switch that a given port is connected to. A port can be connected to at most one adjacent switch. If more than one adjacent switch is connected to a given port (e.g., via a hub), then this port is removed from the load balance domain.

6. Switch ID--This is the identifier for a given switch. It is 6 bytes long and is typically the MAC address for the switch (as opposed to the port MAC address). This value must be unique to every switch in the domain.

7. Convergence Period--This is the time allowed for convergence of a given set of paths to a given edge switch. After the initial convergence of the paths, there is always one set of paths converged that are actively used, while another set is converging. The smallest convergence period is defined to be 30 seconds.

8. Trunked Ports--These are multiple ports directly connected to the same adjacent switch.

3.1. Load Balance Packet header

To be as unobtrusive as possible, all the load balancing switch-to-switch packets use the unicast packet format shown in FIG. 4. This packet has the generic Ethernet format with an Ethernet type 406 of 0x8859 (0x8859 is the Hewlett Packard Switch to Switch protocol Ethernet type). The packet is sent to a unique destination MAC address 402 (0x080009f5852A).

By using a globally known but unique unicast destination MAC address 402, only switches that recognize that address will see the packet. In a few select cases, the destination address will be a specific switch. The source address 404 is a MAC address unique to a given switch (or a given port in the case of the hello packet described later). In some cases the preferred embodiment protocol (or "load balance protocol") uses the source MAC address 404 as an identifier for an edge switch, so this value must not only be unique to a given switch, but also must be the same for all ports within the switch when used as a switch identifier.

Following the Ethernet type 406 are reserved bytes 408 (reserved for future use in the protocols of the present), a 1 byte version number 410, protocol type 412, and authentication type 414. Reserved bytes 408 are reserved for general use in the protocol where particular special cases need be handled.

For example, a first bit of the reserved bytes 408 has been allocated as a flag associated with a type 1 query (described below). A type 1 query is used in special circumstances to update cost and path information in an edge switch when failure recovery techniques of the present invention chose an alternate path in response to sensing failure of a presently preferred path between switches. Details of this processing are discussed herein below.

A second bit in the reserved bytes 408 is allocated as a flag in the protocols of the present invention operating in conjunction with the spanning tree protocols. It is necessary in some conditions associated with the spanning tree protocols to temporarily alter timeout values associated with spanning tree protocols to force the spanning tree protocols to remove (flush) old MAC addresses left pointing to ports that are blocked upstream. This bit is set on cost packets transmitted among the switches in accordance with the protocols of the present invention. Details of this feature are discussed herein below with respect to operation in conjunction with spanning tree protocols.

A third bit in reserved bytes 408 is used to distinguish between different uses of type 2 queries. A first usage of a type 2 query is when attempting to discover path information regarding a previously unknown source MAC address. A type 2 query is also used when attempting to discover path information regarding a previously unknown destination MAC address. This third bit is used to distinguish which of the two usages of a type 2 query is intended for a particular instance of the query packet. Details on learning/discovery of path information is presented herein below.

The version number is set to 0 but may be updated in the future if and when more features are added to the protocol. The protocol type of 1 indicates that it is for load balancing. Protocol type 0 is reserved for automatic broadcast control used by Hewlett Packard switches. The next field is the authentication type 414 and defines the meaning of the next 11 bytes, which are the authentication data.

Table 1 shows the currently defined authentication types and the meaning of the authentication data. This authentication method was leveraged from RFC 1583 OSPF (version 2) but increased to 11 bytes to improve 4 byte boundary alignment. The authentication data also starts on a 32 bit boundary to help improve the speed and ease of parsing packets. In general all major packet structures start on 4 byte boundaries in order to make the implementation easier and to speed up processor access. When authentication is used, some level of user configuration will be required (i.e., the password must be set). However, use of authentication is not required.

                             TABLE 1
                    Authentication Field Type
          Authentication
               Type            Description
                0              No Authentication
                               Authentication Data ignored
                1              Simple Password
                               Up to 8 bytes of Password in the
                               Authentication Data
              2-255            Reserved for future use

                             TABLE 2
                    Load Balance Packet Types
       Value (Hex)
    Request/Response
    Info/Acknowledge  Description
          0/80        Reserved
          0/81        Hello Packet (Request/Response) used to locate the
                      Load Balance Domain Boundary and detect broken
                      links
          2/82        Loop Bit offset Negotiation Packet
                      (request/negative/positive-acknowledge). Used to
                      negotiate the loop detection bit offset for each load
                      balance switch
          3/83        Switch Cost Packet (information/Acknowledge)
                      used to periodically update the network on the cost
                      to a given edge switch.
          4/84        Switch Update Cost packet (information/
                      acknowledge) Information packet sent out at link up
                      to trigger the exchange of current topology cost
                      information. Also triggered by a query packet.
                      Acknowledgment only used on the directed form
                      of the packet.
          5/85        Broadcast Add Packet (information/Acknowledge)
                      used to inform an adjacent switch that it should
                      send broadcast packets from a given edge switch on
                      this port.
          6/86        Broadcast Delete Packet (information/Acknowledge)
                      used to inform an adjacent switch that the edge
                      switch broadcast path should be deleted on this port.
          7/87        MAC Address inform (information/Acknowledge)
                      used to inform adjacent switches about new source
                      MAC addresses and associated edge switch.
          8/88        Switch Query packet (Request/acknowledge. 4 types
                      of query packets used to find a new path to a switch
                      when a link goes down. Also use to trigger MAC
                      address finds)
       A/8A-7F/FF     Reserved for future use

                             TABLE 3
              Legal and Default Hello packet Values
                Value              Description
                2-360              Legal hello times
                   15              Default Hello time
                 2-15              Legal Dead Counts
                   3               Default Dead Count

                             TABLE 4
                     Hello Event/State Table
                                             Not         MAC
                                 Disab Init  Estab Estab Error
    Events/States                (800) (802) (804) (806) (808)
    1. Load Balance Port Enabled Init  NA    NA    NA    NA
    2. Receive Hello Packet with Loop NA    Estab Estab Estab NA
    Bit negotiation not done. Inform                         (see
    remote side that no Broadcast paths                         events
    exits on this link with a general                         7, 8)
    Broadcast delete packet
    3. No hellos received after initial 5 NA    Not   NA    NA    NA
    hellos sent                        Estab
    4. Dead Count expired without NA    NA    NA    Init  NA
    receiving a Hello Packet, or
    Maximum retransmission value
    reached on the cost packet,
    broadcast add packet, broadcast
    delete packet, MAC address
    information packet or query packet
    5. Receive hello with hello  NA    Init  Init  Estab NA
    time > configured time. In all cases                         (see
    a hello request is sent immediately                         events
    after the response to confirm that                         7, 8)
    the other side has changed its hello
    time down.
    6. Port Disabled             NA    Disab Disab Disab Disab
    7. Multiple hellos from different NA    MAC   NA    MAC   MAC
    switches received, or a switch       Error       Error Error
    receives its own hello packet.
    8. Multiple MAC address condition NA    NA    NA    NA    Init
    cleared
    9. Receive Hello Packet with Loop NA    Estab Estab Estab NA
    bit negotiation done. Inform                         (see
    remote side that no Broadcast paths                         events
    exits on this link with a general                         7, 8)
    Broadcast delete packet
    10. Receive Hello Packet with NA    MAC   MAC   MAC   MAC
    Loop Block Flag set                Error Error Error Error
    11. Timer expires to send hello NA    Init  Not   Estab MAC
    packet (timer value depends on the             Estab       Error
    state. For Estab, MAC Error and
    Init state a Hello request is sent.
    For Not Estab state a Hello
    response is sent

                                      TABLE 5
                      Loop Bit Negotiation Event/State Table
                                                                         Hello
                                 Init-wait Un-neg    Neg-wait  Neg       Estab
    Event                        (1002)    (1004)    (1006)    (1008)    (1000)
    1. First port has entered hello NA        NA        NA        NA
     Init-wait
    established state
    2. 5 second wait timer Expired Un-neg    NA        NA        NA        NA
    from Init-wait state
    3. Xmit of Loop bit packet   NA        Neg-wait  NA        NA        NA
    4. Timer expired and no NAKs NA        NA        Neg       NA        NA
    received
    5. Positive acknowledgments  Init-wait Un-neg    Neg-wait  Neg       NA
    received.
    6. Reception of loop bit packet Init-wait Un-neg    Neg-wait  Neg       NA
    with identical loop bit offset.
    Source has smaller MAC address
    7. Reception of loop bit packet Init-wait Un-neg    Init-wait Neg       NA
    with identical loop bit offset.
    Source has larger MAC address
    8. Reception of Cost packet with Init-wait Un-neg    Un-neg    Un-neg    NA
    identical loop bit offset to receiver.
    Source has larger MAC address
    9. Reception of Cost packet with Init-wait Un-neg    Neg-wait  Neg       NA
    identical loop bit offset to receiver.
    Source has smaller MAC address
    10. Entered from hello state NA        NA        NA        NA        Neg
    machine with loop bit negotiation
    completed previously
    11. Reception of a NAK       Init-wait Un-neg    Init-wait Un-neg    Un-neg