Load sharing over blocked links

• US 6,407,985 B1
• Filed: 06/29/1998
• Issued: 06/18/2002
• Est. Priority Date: 06/29/1998
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Jain, Praveen
• Primary Examiner(s): TON, DANG T
• Application Number:
  US09/106,798
• Time in Patent Office: 1,450 Days
• Field of Search: 370/256, 370/254, 370/252, 370/401, 370/402, 370/403, 370/412, 370/392, 370/407, 370/405, 370/408, 370/428, 370/389, 370/399, 370/409, 370/390, 370/406
• US Class Current: 370/256
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities

Abstract

In order to load share non-configuration message traffic on more than one port of a non-root spanning tree protocol compliant switching node, upon receiving a spanning tree algorithm port-blocking message, the switching node assigns a port filter to each of its non-designated ports. The switching node then directs a spanning tree non-configuration message through a port that has a port filter which corresponds to the non-configuration message. The switching node may be implemented using any learning switch, or equivalent device, which complies with a spanning tree algorithm, has sufficient memory to store the port filters used, a means for applying the port filters to its non-designated ports, and a means for directing at least one spanning tree non-configuration message to a port having a port filter that corresponds to the non-configuration message. The switching node may be implemented on any spanning tree compliant network, such as a IEEE 802.1d network, as long as the network includes at least one other learning switch which is selected as the root switch for the network.

Claims

1. A method for load sharing spanning tree non-configuration message traffic on more than one load sharing port of a non-root spanning tree protocol compliant node, the method comprising the steps of:

assigning a first port filter to a first load sharing port and a second port filter to a second load sharing port in response to a spanning tree protocol port-blocking message; and

directing a non-configuration message through one of said ports having a port filter which corresponds to said non-configuration message.

2. The method of claim 1, wherein said step of directing includes the step of transmitting said non-configuration message through said first load sharing port if said first port filter corresponds to a source address of said non-configuration message.

3. The method of claim 1, wherein said step of directing includes the step of transmitting said non-configuration message through said second load sharing port if said second port filter corresponds to a source address of said non-configuration message.

4. The method of claim 1, wherein said step of directing includes the step of receiving said non-configuration message through said first load sharing port if said first port filter corresponds to a destination address of said non-configuration message.

5. The method of claim 4, further including the steps of:

including an additional bit position within said non-configuration message;

configuring said additional bit position to indicate that said non-configuration message was received by one of the more than one load sharing ports;

learning said non-configuration message and forwarding said non-configuration message to all ports within the node if said non-configuration message had not been previously learned and previously received on a non-load sharing port by the node; and

dropping said non-configuration message if said non-configuration message had been previously learned and previously received on a non-load sharing port by the node.

6. The method of claim 5, wherein said step of learning includes storing in an entry in a forwarding table:

a port designation corresponding to said first port, and a source address of said non-configuration message.

7. The method of claim 6, further including a step of using said forwarding table to determine which of the more than one load sharing ports to use when transmitting a non-configuration message.

8. The method of claim 6, wherein said step of directing includes a step of sending a non-configuration message to all of the more than one load sharing ports, if said forwarding table indicates that said non-configuration message is to be transmitted to one of the more than one load sharing ports.

9. The method of claim 5, further including the steps of:

checking whether said additional bit position in said non-configuration message indicates that said non-configuration message was received by one of the more than one load sharing ports, if said non-configuration message is to be transmitted by one of the more than one load sharing ports;

dropping said non-configuration message if said additional bit position in said non-configuration message signifies that said non-configuration message was received by a non-load sharing port;

transmitting said non-configuration message if said non-configuration message is to be transmitted by a non-load sharing port;

checking whether said non-configuration message corresponds to said first port filter or said second port filter if said additional bit position in said non-configuration message signifies that said non-configuration message was received by a non-load sharing port;

dropping said non-configuration message if said non-configuration message does not correspond to said first port filter or said second port filter;

transmitting said non-configuration message through said first load sharing port if said non-configuration message corresponds to said first port filter; and

transmitting said non-configuration message through said second load sharing port if said non-configuration message corresponds to said second port filter.

10. The method of claim 1, wherein said step of directing includes the step of receiving said non-configuration message through said second load sharing port if said second port filter corresponds to a destination address of said non-configuration message.

11. The method of claim 10, further including the steps of:

including an additional bit position within said non-configuration message;

configuring said additional bit position to indicate that said non-configuration message was received by one of the more than one load sharing ports;

learning said non-configuration message and forwarding said non-configuration message to all ports within the node if said non-configuration message had not been previously learned and previously received on a non-load sharing port by the node; and

dropping said non-configuration message if said non-configuration message had been previously learned and previously received on a non-load sharing port by the node.

12. The method of claim 11, wherein said step of learning includes storing in an entry in a forwarding table:

a port designation corresponding to said second port, and a source address of said non-configuration message.

13. The method of claim 12, further including a step of using said forwarding table to determine which of the more than one load sharing ports to use when transmitting a non-configuration message.

14. The method of claim 11, wherein said step of directing includes a step of sending a non-configuration message to all of the more than one load sharing ports, if said forwarding table indicates that said non-configuration message is to be transmitted to one of the more than one load sharing ports.

15. The method of claim 10, further including the steps of:

checking whether said additional bit position in said non-configuration message indicates that said non-configuration message was received by one of the more than one load sharing ports, if said non-configuration message is to be transmitted by one of the more than one load sharing port;

dropping said non-configuration message if said additional bit position in said non-configuration message signifies that said non-configuration message was received by a non-load sharing port;

transmitting said non-configuration message if said non-configuration message is to be transmitted by a non-load sharing port;

checking whether said non-configuration message corresponds to said first port filter or said second port filter if said additional bit position in said non-configuration message signifies that said non-configuration message was received by a non-load sharing port;

dropping said non-configuration message if said non-configuration message does not correspond to said first port filter or said second port filter;

transmitting said non-configuration message through said first load sharing port if said non-configuration message corresponds to said first port filter; and

transmitting said non-configuration message through said second load sharing port if said non-configuration message corresponds to said second port filter.

16. The method of claim 1, wherein said step of assigning includes the step of generating a filter value and a filter mask for said first port filter.

17. The method of claim 16, wherein said step of directing includes the step of transmitting a non-configuration message through said first port, if said first port filter has a filter value that matches a selected number of bits defined by a source address of said non-configuration message if said non-configuration message is to be transmitted from the node.

18. The method of claim 17, wherein said selected number of bits start from the least significant bit position of said source address and are specified by said filter mask.

19. The method of claim 16, wherein said step of directing includes the step of receiving a non-configuration message on said first port, if said first port filter has a filter mask that matches a selected number of bits defined by a destination address of said non-configuration message if said non-configuration message is to be received by the node.

20. The method of claim 19, wherein said selected number of bits start from the least significant bit position of said destination address and are specified by said filter mask.

21. The method of claim 1, wherein said step of assigning includes the step of generating a filter value and a filter mask for said second port filter.

22. The method of claim 21, wherein said step of directing includes the step of transmitting a non-configuration message through said second port, if said second port filter has a filter value that matches a selected number of bits defined by a source address of said non-configuration message if said non-configuration message is to be transmitted from the node.

23. The method of claim 22, wherein said selected number of bits start from the least significant bit position of said source address and are specified by said filter mask.

24. The method of claim 21, wherein said step of directing includes the step of receiving a non-configuration message on said second port, if said second port filter has a filter mask that matches a selected number of bits defined by a destination address of said non-configuration message if said non-configuration message is to be received by the node.

25. The method of claim 24, wherein said selected number of bits start from the least significant bit position of said destination address and are specified by said filter mask.

26. The method of claim 1, further including a step of sending a topology change notification through a root port in the node when the number of load sharing ports which are available for load sharing changes.

27. The method of claim 1, further including a step of using a forwarding table to indicate when said non-configuration message is received by the node through a non-load sharing port by:

creating an additional field in each forwarding table entry; and

configuring said additional field to indicate that said non-configuration message was received by said non-load sharing port.

28. An apparatus for load sharing message traffic over more than one port, the apparatus comprising:

a network node having a plurality of ports, including a set of load sharing ports and a set of non-load sharing ports;

a memory for storing a port filter for each port within said set of load sharing ports;

means for applying said port filter to said each port in response to a spanning tree protocol port-blocking message; and

means for directing a non-configuration message through one of said each port that has a port filter which corresponds to said non-configuration message.

29. The apparatus of claim 28, wherein said means for directing includes a transmitter that transmits said non-configuration message through said load sharing port having a port filter which corresponds to a source address of said non-configuration message if said non-configuration message is to be transmitted from the network node.

30. The apparatus of claim 29, further including a bit generator responsive to said transmitter, said bit generator setting a bit within a selected bit position within said non-configuration message when said non-configuration message is received through one of said load sharing ports, said selected bit position for signifying when said non-configuration message has been received through said one of said load sharing ports.

31. The apparatus of claim 30, further including a step of dropping a non-configuration message received by said one of said load sharing ports, if said non-configuration message has a selected bit position that signifies that said non-configuration message has been previously received through said one of said load sharing ports.

32. The apparatus of claim 28, wherein said means for directing includes a receiver that receives a non-configuration message through a port having a port filter which corresponds to a destination address of said non-configuration message if said non-configuration message is to be received by the network node.

33. The apparatus of claim 32, further including a forwarding table for learning a source address, and a port address used by said message traffic.

34. The apparatus of claim 33, further including a selection means for using said forwarding table to determine which of the plurality of ports to use when transmitting a non-configuration message.

35. The apparatus of claim 33, wherein said forwarding table includes an additional field in each table entry for indicating whether a learned non-configuration message has been received through one of said non-load sharing ports.

36. The apparatus of claim 33, wherein said means for directing includes a transmitter that sends a non-configuration message to all of said load sharing ports, if said memory store indicates that said non-configuration message is to be transmitted to one of said load sharing ports.

37. The apparatus in claim 28, wherein said port filter includes:

a filter mask for specifying a number of bits within an address to monitor; and

a filter value for specifying a value to use to match with said address.

38. The apparatus of claim 37, wherein said means for directing includes a transmitter that transmits a non-configuration message through a port corresponding to a port filter having a filter value that matches a selected number of bits defined by a source address of said non-configuration message if said non-configuration message is to be transmitted from the network node.

39. The apparatus of claim 38, wherein said selected number of bits start from the least significant bit position of said source address and are specified by said filter mask.

40. The apparatus of claim 37, wherein said means for directing includes a receiver that receives a non-configuration message through a port corresponding to a port filter having a filter mask that matches a selected number of bits defined by a destination address of said non-configuration message if said non-configuration message is to be received by the network node.

41. The apparatus of claim 40, wherein said selected number of bits start from the least significant bit position of said destination address and are specified by said filter mask.

42. A communications network, comprising:

a first node and a second node, said first node having;

at least a first port and a second port,

a memory for storing at least a first port filter, and a second port filter,

a filter device responsive to a spanning tree algorithm port-blocking message, said filter device applying said first port filter to said first port, and said second port filter to said second port when a spanning tree algorithm port-blocking message is received,

means for directing message traffic over said first port when said message traffic corresponds to said first port filter, and over said second port when said message traffic corresponds to said second port filter; and

said second node having at least a first port and a second port, said first port of said second node coupled to said first port of said first node, said second node selected as a root node for the communications network.

43. The communications network of claim 42, wherein said first node includes a third port, said third port coupled to a station.

44. The communications network claim 42, wherein said second node includes a third port, said third port coupled to a third node.

45. The communications network of claim 42, wherein said means for directing includes a transmitter that transmits a non-configuration message through said first port if said first port filter corresponds to a source address of said non-configuration message and if said non-configuration message is to be transmitted from the first node.

46. The communications network of claim 42, wherein said means for directing includes a transmitter that transmits a non-configuration message through said second port if said second port filter corresponds to a source address of said non-configuration message and if said non-configuration message is to be transmitted from the first node.

47. The communications network of claim 42, wherein said means for directing includes a receiver that receives a non-configuration message through said first port if said first port filter corresponds to a destination address of said non-configuration message if said non-configuration message is to be received by the first node.

48. The communications network of claim 42, wherein said means for directing includes a receiver that receives a non-configuration message through said second port if said second port filter corresponds to a destination address of said non-configuration message if said non-configuration message is to be received by the first node.

49. The communications network in claim 42, wherein said first port filter and said second port filter each include:

a filter mask for specifying a number of bits within a address to monitor; and

a filter value for specifying a value to use to match with said address.

50. The apparatus of claim 42, wherein said first node further includes a forwarding table for learning a source address and a port address used by said message traffic.

51. The apparatus of claim 50, further including a selection means for using said forwarding table to determine which of the plurality of ports to use when transmitting a non-configuration message.

52. The apparatus of claim 50, wherein said forwarding table includes an additional field in each table entry for indicating whether a learned non-configuration message has been received through one of a plurality of non-load sharing ports of said first node.

53. A method for providing an apparatus for load sharing message traffic over more than one port, the method comprising:

providing a network node having a plurality of ports, including a set of load sharing ports and a set of non-load sharing ports;

providing a memory for storing a port filter for each port within said set of load sharing ports;

providing means for applying said port filter to said each port in response to a spanning tree protocol port-blocking message; and

providing means for directing a non-configuration message through one of said each port that has a port filter which corresponds to said non-configuration message.

54. The method of claim 53, further including a step of providing a forwarding table having a table entry comprised of a field for storing a source address, a field for storing a port address, and an additional field for indicating whether a non-configuration message corresponding to said entry w as received through one of said non-load sharing ports.

55. A method for load sharing non-configuration message traffic on more than one load sharing port of a node, the node being within a loop free communication network, the method comprising the steps of:

assigning a port filter to each operative load sharing port of the node in response to a spanning tree port-blocking message, said step of assigning including a step of generating a filter value and a filter mask for said port filter assigned to said each operative load sharing port of the node; and

directing non-configuration message traffic by transmitting a non-configuration message from a load sharing port corresponding to a port filter having a filter value that matches a selected number of bits defined by a source address of said non-configuration message if said non-configuration message is to be transmitted from the node, and receiving a non-configuration message on a load sharing port corresponding to a port filter having a filter mask that matches a selected number of bits defined by a destination address of said non-configuration message if said non-configuration message is to be received by the node.

56. The method of claim 55, wherein said selected number of bits defined by said source address start from the least significant bit position of said source address and are specified by said filter mask.

57. The method of claim 56, wherein said selected number of bits defined by said destination address start from the least significant bit position of said destination address and are specified by said filter mask.