Method and apparatus for priority-based load balancing for use in an extended local area network

• US 20030193959A1
• Filed: 07/26/2002
• Published: 10/16/2003
• Est. Priority Date: 01/20/2002
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: General Instrument Corporation (CommScope Holding Company, Inc.)
• Inventors: Lee, Whay Chiou, Lui, King-Shan
• Granted Patent: US 6,717,950 B2
• Time in Patent Office: Days
• US Class Current: 370/401
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• 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/12 Shortest path evaluation

Abstract

Bridges (10, 12, 14) are used to interconnect local area networks transparently. In the IEEE 802.1D standard for bridges, a spanning tree is built among the bridges for loop-free frame forwarding (FIG. 10). Although this approach is simple, it does not support all-pair shortest paths. A novel bridge protocol is employed that attempts to find and forward frames over alternate paths that are shorter than their corresponding tree paths on the standard spanning tree, and makes use of the standard spanning tree for default forwarding. The protocol, referred to as the Spanning Tree Alternate Routing (STAR) Bridge Protocol, is backward compatible with the IEEE 802.1D standard and has a complexity that is comparable to that of the standard and other existing protocols and further includes an ability to prioritize the forwarding of frames over at least two different paths responsive to a priority value carried by a frame to be forwarded.

Claims

1. Apparatus for determining paths for forwarding frames among end stations in a system of interconnected local area networks, comprised of:

first and second groups of frame forwarding devices comprising bridges, which are used to interconnect local area networks;

said first and second groups of bridges each having first means for creating tree paths for loop-free frame forwarding to an end station;

said second group of bridges each having second means cooperating with said first group of bridges and all other bridges of said second group of bridges to create an enhanced path for loop-free forwarding of a frame to an end station, wherein said enhanced path is an alternate path that is shorter than any tree path to said end station; and

said second group of bridges each having third means for selecting one of a tree path and an alternate path responsive to at least one of a parameter contained in a received frame and a number of hops a frame has made over a tree path between an agent bridge and the bridge of the second group of bridges receiving the frame.

2. The apparatus of claim 1 wherein said parameter value is a priority value identifying a priority assigned to a frame.

3. The apparatus of claim 2 wherein said third means includes means for selecting a path whereby a higher priority of a frame, a smaller number of hops over a tree path a frame makes before being forwarded over an enhanced path.

4. The apparatus of claim 2 wherein said third means includes means for selecting a path whereby a greater number of hops made by a frame over a tree path, a greater is the likelihood that the frame will be forwarded over an enhanced path.

5. The apparatus of claim 1 wherein said second group of bridges are backward compatible with said first group of bridges, wherein the operation of said first group of bridges is unaltered by the presence of said second group of bridges, and

said second group of bridges inter-operate with said first group of bridges when at least one bridge of the latter group is present in the system, and

said second group of bridges can perform their functions in the absence of said first group of bridges in order to operate.

6. The apparatus of claim 1 wherein said first group of bridges include means for performing a spanning tree bridge protocol (STBP) to determine a loop-free tree path for forwarding a frame to an end station;

said second group of bridges include means for performing a spanning tree alternate routing bridge protocol (STAR BP) for determining said alternate path; and

said second group of bridges include means for determining said number of hops the frame has made over the tree path.

7. The apparatus of claim 6 wherein said means for performing said spanning tree alternate routing bridge protocol includes means for performing said spanning tree bridge protocol.

8. The apparatus of claim 1 wherein said end stations are distributed among said local area networks that are interconnected;

and

said first and second groups of bridges selectively forward frames from end stations in one of said local area networks to end stations in another one of said local area networks.

9. The apparatus of claim 1 wherein each bridge of the second group of bridges further comprises means for selecting a tree path when said means for selecting receives a frame originated by a source bridge and having a priority value falling within a first range of priority values including a lowest priority.

10. The apparatus of claim 9 wherein said first range of priority values decreases with said number of hops.

11. The apparatus of claim 1 wherein selected ones of bridges of said second group are arranged along different tree paths and are joined by cross-links;

said means for determining said alternate paths including means for determining if a path including one of said cross-links provides a path shorter than a tree path; and

said selecting means selecting said one of said cross-links responsive to receipt of a frame having a given priority value and said number of hops the frame has made over the tree path.

12. The apparatus of claim 1 wherein each bridge of said first and second groups include:

means for assigning a weighted metric to each port of the bridge;

means for exchanging said weighted metrics with other bridges in the system;

means for electing a root bridge responsive to the exchanged information;

means for determining a distance between each bridge and said root bridge;

means for building a unique spanning tree rooted at the root bridge in a distributed manner;

means for learning and remembering which port to forward a frame over said spanning tree to a given end station; and

means for storing said data.

13. The apparatus of claim 1 wherein each bridge of said second group of bridges includes means for sending an announcement frame to every other bridge of said second group of bridges over said tree path for identifying a tree forwarding port, a next hop bridge of said second group of bridges and a number of bridges of said second group between a source and the bridge sending the announcement.

14. The apparatus of claim 12 wherein each bridge of said second group of bridges is further provided with means for conveying to other bridges of said second group information representing topology known to the conveying bridge;

means for conveying to other bridges of the second group information identifying bridges of the second group which are a source for frames and a destination for frames;

means for conveying to other bridges of the second group topology information known to bridges of the second group other than the conveying bridge; and

means for storing information received from other bridges of said second group for determining, if possible, an alternate path shorter than a corresponding tree path.

15. The apparatus of claim 1 wherein each bridge of said second group is further provided with means for determining if another bridge of said second group is directly connected thereto by a cross-link which is a link that is not used to form any tree path;

said means for determining an alternate path further including means for examining valid cross-links for use as segments of an alternate path, wherein a valid cross-link is one whose end terminals are connected to bridges of said second group; and

one whose end terminals are joined to bridges of said second group wherein a tree path of one of the bridges of said second group connected to one end terminal of a cross-link is not a segment of a tree path of the other bridge of the second group connected to another end terminal said cross-link, and wherein the tree path of the other bridge of the second group is not a segment of the tree path of said one bridge of said second group.

16. The apparatus of claim 1 wherein each bridge of said second group of bridges further includes;

means for storing an end station location (ESL) table associating each end station with bridges in the second group near each end station;

means for storing a bridge address (BA) table associating each bridge of said second group with a medium access control (MAC) address;

means for storing a bridge forwarding (BF) table for indicating a path of the associated bridge that leads to a next hop along a best path found for forwarding a frame; and

means responsive to a received frame and information stored in said BA, ESL and BF tables for selecting a path to an end station identified in destination information incorporated as part of said received frame.

17. Apparatus for determining a path for forwarding a frame received at a bridge in a system comprised of a plurality of interconnected local area networks (LANs) each having a plurality of end stations, and a spanning tree incorporating a plurality of bridges of first and second groups for loop-free forwarding a frame from a source end station to a destination end station wherein said source and destination end stations may reside in different LANs, said bridges of said first and second groups having means for determining a tree path for loop-free forwarding of said frame;

and

said second group of bridges further having means for determining if an alternate path exists for loop-free forwarding of said frame which has at least one non-tree path segment; and

means for utilizing one of said alternate path and tree path responsive to a priority number carried by said received frame topological criteria including;

a shorter physical path;

a less costly path;

a path having less delay and a smaller number of hops between source and destination.

18. The apparatus of claim 17 including means for determining said alternate path is according to a group of topological criteria including:

a shorter path;

a less costly path;

a path having less delay; and

a smaller number of hops between a source and a destination.

19. A method for determining a path for forwarding a frame in a system having a plurality of end stations interconnected by first and second types of bridges which create a loop-free spanning tree for transferring frames between end stations, comprising:

a) storing, at each of the second type of bridges, data representing cross-links between bridges of said second type and a number of hops between each second type bridge and every other second type bridge;

b) transferring, at a second type of bridge, a received frame over a first path having a smallest number of hops to a destination end station responsive to a priority number of a given value and a destination end station carried by the received frame.

20. The method of claim 19 further comprising:

c) transferring, at a second type of bridge, a received frame over a path having a greater number of hops than said first path responsive to a priority number of lesser priority and a destination end station carried by the received frame.

21. A method for prioritizing the forwarding of frames among end stations in a system of local area networks interconnected by a first and second types of bridges, comprising:

a) creating a loop-free tree path for the transfer of frames employing the first and second types of bridges;

b) forming cross-links between bridges of said second type to provide enhanced forwarding paths;

c) storing tree path information at said first and second types of bridges;

d) storing information of the cross-links at each of the second types of bridges; and

e) forwarding a frame received by a second type of bridge along a path having a smallest number of hops of said second type bridges between a second type bridge receiving the frame and an end station designated to receive the frame and carried by said frame, responsive to a priority number carried by said frame, said path being determined based on the data stored at steps (c) and (d).

22. The method of claim 21 further comprising forwarding a frame received by said second type bridge along a path having a larger number of hops of the second type bridge between the said second type bridge receiving the frame and an end station designated to receive the frame according to data carried by said frame, responsive to a priority number of lower importance than said first mentioned priority number, employing the data stored at steps (c) and (d).

23. A method for establishing a protocol for prioritizing forwarding of frames among end stations in a system of local area networks interconnected by first and second types of bridges, comprising:

a) every second type of bridge broadcasting an announcement frame over a loop-free tree path to other bridges of said second type during a path finding process, each announcement frame carrying an identity of the second type of bridge that originates the frame and a count value, which represents a number of bridges of the second type traversed by the frame; and

b) at least another one of said second type of bridges receiving an announcement from another one of said second type of bridges at a given port thereof incrementing the count value by one, and forwarding a modified announcement frame over all tree ports except said given port.

24. A method of claim 23 further comprising providing in an announcement frame an identity of a second type of bridge that last transferred the announcement frame enabling a second type of bridge to know the next tree hop leading to a second type of bridge that originates the announcement frame.

25. The method of claim 23 wherein each of the second type of bridges decides only the next forwarding hop in place of an entire forwarding path from an agent bridge of the source end station to an agent bridge of the destination end station.

26. The method of claim 23 wherein a second type of bridge receiving a frame from another second type of bridge decides only the next forwarding hop in place of an entire forwarding path from an agent bridge of the source end station to an agent bridge of the destination end station, independently of a decision made by the said another second type of bridge transferring said frame.

27. The method of claim 23 wherein a second type of a bridge receives a frame that is being forwarded downstream on a tree path, said second type of bridge selecting a tree path thereafter.

28. The method of claim 23 wherein a second type of a bridge receives a frame that is being forwarded upstream on a tree path, said second type of bridge selecting either an enhanced path, or a tree path responsive to a priority number carried by the received frame and a number of hops the frame has made over the tree path.

29. The method of claim 23 wherein a second type of a bridge receives a frame on a tree an enhanced path, said second type of bridge selecting either an enhanced path, or a tree path responsive to an availability of an enhanced path thereafter.

30. A method for determining paths for forwarding frames among end stations in a system of interconnected local area networks, comprising first and second groups of frame forwarding devices comprising bridges, for interconnecting local area networks, comprising:

a) said first and second groups of bridges determining tree paths for loop-free frame forwarding to an end station;

b) said second group of bridges determining an alternate path for loop-free forwarding of a frame to an end station, which alternate path is shorter than corresponding tree path to said end station; and

c) said second group of bridges selecting one of a tree path and an alternate path responsive to at least one of a parameter contained in a received frame and a number of hops a frame has made over a tree path between an agent bridge and the bridge of the second group of bridges receiving the frame.

31. The method of claim 30 comprising providing a parameter value which is a priority value identifying a priority assigned to a frame.

32. The method of claim 31 wherein said second group of bridges select a path such that a higher priority of a frame, a smaller a number of hops over a tree path a frame makes before being forwarded over an enhanced path.

33. The method of claim 31 wherein said second groups of devices select a path such that a greater a number of hops made by a frame over a tree path, a greater is the likelihood that the frame will be forwarded over an enhanced path.