Discovery of unknown MAC addresses using load balancing switch protocols

• US 6,456,597 B1
• Filed: 01/11/1999
• Issued: 09/24/2002
• Est. Priority Date: 05/04/1998
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Bare, Ballard C.
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US09/228,169
• Time in Patent Office: 1,352 Days
• Field of Search: 370/329, 370/338, 370/389, 370/390, 370/392, 370/396, 370/401, 370/402, 370/409, 370/410, 370/445, 370/252
• US Class Current: 370/252
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/243 using M+N parallel active paths
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/10 of different types
• CPC Class Codes: H04L 63/083 using passwords cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers

Abstract

A method for discovering addressing information within a network switch for an unknown MAC address received as a destination address of a packet. Where prior techniques flooded the network with the received packet, switch to switch protocols of the present invention reduce the volume of such overhead network traffic required to discover the addressing information. In particular, the present invention propagates query messages through network switches in a load balance domain (a group of switches cooperable in accordance with the protocols described herein). The query messages are propagated using a pruned broadcast tree to reduce the number of transmissions required to reach all switches in the load balance domain. The propagated query message eventual elicits a response from the device which owns the previously unknown destination address. Switches and devices outside the load balance domain are similarly probed for the unknown destination address using link level test messages which elicit a response from the device owning the unknown address without impacting the network higher layer protocols. These techniques reduce the volume of network traffic required to obtain the desired addressing information by forcing the response from the device owning the previously unknown destination address and constructing a unicast path to that device. Creating the unicast path obviates the need to flood the unknown destination address on the network.

Claims

1. A method operable within a network switch for discovering a path to a device owning an unknown destination MAC address comprising the steps of:

receiving a packet on a first port of said network switch wherein said packet has a destination MAC address unknown to said network switch and wherein said network switch is a member of a load balance domain comprising at least one other network switch;

sending a query message on a port of said network switch requesting information regarding said path wherein said query message is of a first type when said first port is within said load balancing domain and wherein said query message is of a second type when said first port is not within said load balancing domain;

receiving a reply message on a port of said network switch in response to sending of said query message wherein said reply message provides addressing information regarding said unknown destination MAC address;

updating addressing tables in said network switch in response to receipt of said reply message to indicate said path provided by said addressing information; and

forwarding said packet to said device via said path.

2. The method of claim 1 wherein said first port is within said load balance domain and

wherein the step of receiving said reply message comprises the step of:

receiving an acknowledgment message on said first port in response to sending said query message.

3. The method of claim 2 wherein the step of sending said query message comprises the step of:

sending a type 2 query message on said first port requesting information regarding said path to said device.

4. The method of claim 1 wherein said first port is not within said load balance domain and

wherein the step of sending said query message comprises the step of:

sending a type 3 query message requesting information regarding said path to said device out at least one port of said network switch other than said first port in accordance with a pruned broadcast tree associated with said network switch, and

wherein the step of receiving said reply message comprises the step of;

receiving a MAC address information packet in response to sending said type 3 query message.

5. The method of claim 4 wherein the step of sending said query message further comprises the step of:

sending a test message out wherein said at least one port of said network switch is not within said load balance domain.

6. The method of claim 5 wherein the step of receiving said reply message further comprises the step of:

receiving said reply message in response to sending of said test message.

7. A method operable within a plurality of network switches for discovering a path to a device owning an unknown destination MAC address wherein at least a portion of said plurality of network switches have ports in a load balance domain, said method comprising the steps of:

receiving a packet on a first port of a first network switch of said network switches wherein said packet has a destination MAC address unknown to said first network switch wherein said first port is not within said load balance domain;

propagating a query message on a port of said first network switch that is within said load balance domain to other network switches of said plurality of network switches wherein said query message requests information regarding said path to said device;

sending test messages on ports of said first network switch that are outside said load balance domain;

receiving a reply message on any port of said first network switch in response to propagation of said query message or in response to sending of said test messages wherein said reply message provides addressing information regarding said unknown destination MAC address;

updating addressing tables in said first network switch in response to receipt of said reply message to indicate said path provided by said addressing information; and

forwarding said packet to said device via said path.

8. The method of claim 7 further comprising the steps of:

receiving said query message within an intermediate network switch of said plurality of network switches; and

propagating said query message on a port of said intermediate network switch within said load balance domain to other network switches of said plurality of network switches.

9. The method of claim 8 further comprising the steps of:

determining within said intermediate network switch whether said unknown destination MAC address is known to said intermediate network switch; and

sending test messages on ports of said intermediate network switch that are outside said load balance domain in response to a determination that said unknown destination MAC address is not known to said intermediate network switch.

10. The method of claim 7 further comprising the steps of:

receiving said query message within an edge network switch of said plurality of network switches wherein said edge network switch is adjacent said device; and

returning said reply message to said first network switch containing MAC address information regarding said unknown destination MAC address.

11. A network switch including a computer readable storage medium tangibly embodying a method operable within said network switch for discovering a path to a device owning an unknown destination MAC address comprising the steps of:

receiving a packet on a first port of said network switch wherein said packet has a destination MAC address unknown to said network switch and wherein said network switch is a member of a load balance domain comprising at least one other network switch;

sending a query message on a port of said network switch requesting information regarding said path wherein said query message is of a first type when said first port is within said load balancing domain and wherein said query message is of a second type when said first port is not within said load balancing domain;

receiving a reply message on a port of said network switch in response to sending of said query message wherein said reply message provides addressing information regarding said unknown destination MAC address;

updating addressing tables in said network switch in response to receipt of said reply message to indicate said path provided by said addressing information; and

forwarding said packet to said device via said path.

12. The switch of claim 11 wherein said first port is within said load balance domain and

wherein the method step of receiving said reply message comprises the step of:

receiving an acknowledgment message on said first port in response to sending said query message.

13. The switch of claim 12 wherein the method step of sending said query message comprises the step of:

sending a type 2 query message on said first port requesting information regarding said path to said device.

14. The switch of claim 11 wherein said first port is not within said load balance domain and

wherein the method step of sending said query message comprises the step of:

sending a type 3 query message requesting information regarding said path to said device out at least one port of said network switch other than said first port in accordance with a pruned broadcast tree associated with said network switch, and

wherein the method step of receiving said reply message comprises the step of;

receiving a MAC address information packet in response to sending said type 3 query message.

15. The switch of claim 14 wherein the method step of sending said query message further comprises the step of:

sending a test message out wherein said at least one port of said network switch is not within said load balance domain.

16. The switch of claim 15 wherein the method step of receiving said reply message further comprises the step of:

receiving said reply message in response to sending of said test message.

17. A system including a plurality of network switches each of said switches including a computer readable storage medium tangibly embodying a method operable within said plurality of network switches for discovering a path to a device owning an unknown destination MAC address wherein at least a portion of said plurality of network switches have ports in a load balance domain, said method comprising the steps of:

receiving a packet on a first port of a first network switch of said network switches wherein said packet has a destination MAC address unknown to said first network switch wherein said first port is not within said load balance domain;

propagating a query message on a port of said first network switch that is within said load balance domain to other network switches of said plurality of network switches wherein said query message requests information regarding said path to said device;

sending test messages on ports of said first network switch that are outside said load balance domain;

receiving a reply message on any port of said first network switch in response to propagation of said query message or in response to sending of said test messages wherein said reply message provides addressing information regarding said unknown destination MAC address;

updating addressing tables in said first network switch in response to receipt of said reply message to indicate said path provided by said addressing information; and

forwarding said packet to said device via said path.

18. The system of claim 17 wherein the method further comprises the steps of:

receiving said query message within an intermediate network switch of said plurality of network switches; and

propagating said query message on a port of said intermediate network switch within said load balance domain to other network switches of said plurality of network switches.

19. The system of claim 18 wherein the method further comprises the steps of:

determining within said intermediate network switch whether said unknown destination MAC address is known to said intermediate network switch; and

sending test messages on ports of said intermediate network switch that are outside said load balance domain in response to a determination that said unknown destination MAC address is not known to said intermediate network switch.

20. The system of claim 17 wherein the method further comprises the steps of:

receiving said query message within an edge network switch of said plurality of network switches wherein said edge network switch is adjacent said device; and

returning said reply message to said first network switch containing MAC address information regarding said unknown destination MAC address.