Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
1998-06-29
2002-06-18
Ton, Dang (Department: 2732)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
Reexamination Certificate
active
06407985
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to communications networks. More particularly, the present invention relates to load of sharing spanning tree non-configuration messages, such as data packets, over more than one port of a switching node within a communications network.
2. The Background Art
FIG. 1
is a schematic diagram of a typical communications network
10
having switches
12
,
14
,
16
and
18
which are interconnected to form a spanning tree (loop-free) topology. System
10
includes switch
12
coupled to switch
14
through link
20
. Switch
14
is coupled to switch
16
through link
22
and switch
18
through link
24
. Switch
18
is coupled to a network
26
, such as the Internet, through link
27
. A link is a connection between two switches and may be provided using any compatible transmission medium, such as a twisted pair, fiber optic, coaxial, wireless or equivalent medium.
A switch is commonly known as a device which receives a packet from another switch or station and transmits the packet to another switch or station. A station may be a personal computer, work station, printer, or similar device, which does not store and forward a packet upon receipt to another switch or station. The switch has at least two forwarding ports for coupling to at least one other switch and/or at least one station, enabling the switch to send or receive packets to each coupled switch or station. For example, switch
12
may have ports
28
a
through
28
n
which are coupled to stations
30
a
through
30
n
. Switch
12
also may have ports
32
a
through
32
n
which are available for receiving or transmitting packets from another switch, such as switch
14
. Switch
14
is similar to switch
12
except that its ports are only coupled to ports of other switches and thus, may be designed to provide high packet throughput through its ports. Port
34
a
is shown coupled to port
32
a
of switch
12
, port
34
n
of switch
14
is shown coupled to port
36
n
of switch
16
, and port
38
a
of switch
14
is shown coupled to port
40
a
of switch
18
. Switch
16
may also include additional ports for coupling with stations, such as ports
44
a
through
44
n
which are shown coupled to stations
46
a
through
46
n
, respectively.
Each switch is a learning switch that promiscuously listens for packets through its ports that either have a link established with another switch or with a station. If the packet has been previously “learned,” i.e., its source address and the port upon which the packet was received by the switch have been previously stored in a forwarding table, the packet is forwarded to the port specified in the forwarding table. (Forwarding tables and their uses in switching networks are well known to those of ordinary skill in the art.) If the packet has not been previously learned, then the switch learns the packet in the forwarding table and forwards the packet on all of its ports except the port upon which the packet was received.
Because a learning switch transmits a packet on all of its ports, except the port upon which the packet was received, a situation may occur where an infinite number of packet copies may be spawned if the switches have more than one link between each other and if the packet received has not been previously learned. This result may be described by the following discussion which is directed to FIG.
2
.
FIG. 2
is a partial schematic diagram of communications network
11
having learning switches
12
,
16
and
14
which are not interconnected to form a spanning tree topology. Switch
12
and switch
14
are coupled through link
20
at ports
32
a
and
34
a
, respectively, and through link
50
at ports
32
n
and
34
b
, respectively. Link
20
and link
50
create a loop between switch
12
and switch
14
.
If switch
12
transmits a packet through link
20
to switch
14
, switch
14
will receive the packet and check to see if the packet has a destination address that has been previously been used. If not, switch
14
sends copies of the packet to all of its ports, except port
34
a
which is the port upon which the packet was received. This results in switch
12
receiving a copy of the packet, checking the destination address of the packet copy, using the destination address as an index in its forwarding table (not shown) to determine which port to use, and transmitting the packet copy to that port, which is port
32
a
. This results in switch
14
receiving the packet copy, using its forwarding table (not shown) to determine which port to use, which in this case, would include more than one port including port
34
b
, making additional copies of the packet copy, and sending the copies to the ports previously used. Thus, packets transmitted on a communications network that uses learning switches which are not interconnected to have a spanning tree topology, may not only infinitely loop between switches but may also infinitely proliferate because for each hop between switches, additional packets are generated.
One known solution to this problem is to impose a spanning tree algorithm (STA) on a network having learning switches so that the network has a loop-free topology, such as communications network
10
shown in FIG.
1
. Spanning tree algorithms are known in the art and typically include a step of selecting a root switch in the network. The STA then calculates a loop-free path between the root switch and all other switches on the network.
The STA creates the loop-free path by dynamically selecting a “forwarding” port as a “root” port and blocking packet traffic from all other forwarding ports (“blocked ports”) in each switch which are not “designated” ports. Those of ordinary skill in the art will recognize that a link connected to a blocked port is precluded from sending packet traffic through that port, rendering the link a blocked link. Forwarding ports are ports configured within a spanning tree to forward or receive packets from a root switch. Designated ports are forwarding ports which cannot be blocked or selected as a root port, such as ports that are connected to another station or to a root switch.
For example, referring again to
FIG. 1
, in response to a STA port blocking message, switch
12
selects a root port, such as port
32
a
, and blocks ports that are non-designated ports, such as ports
32
b
through
32
n
. Ports
30
a
through
30
n
are not blocked because they are designated ports. No packet traffic flows through blocked ports, eliminating the above-described problem of creating an infinite number of packet copies. The only time a blocked port is used is when a link breaks between switches. When this occurs, the original root port is blocked and a blocked port is selected as the new root port. Thus, each switch within the network does not only ultimately link to every switch so that packets can be transmitted or received between every device of communications network
10
but each switch also does not form a loop between any other switch on the network. Such a system is known as a network having a loop-free or spanning tree topology.
However, a network with a loop-free topology suffers from the disadvantage that only one link may be used between switches, even though blocked ports may be available to share the packet traffic with the root port. This prevents sharing the total packet traffic load over non-designated ports which may be otherwise available for transmitting or receiving packets and is thus, not fully utilized or as efficient as possible.
Accordingly, a need exists where at least one blocked port may be utilized to share packet traffic load with a selected root port, while ensuring that packet copies are not infinitely generated and transmitted between learning switches.
SUMMARY OF THE INVENTION
The present invention is directed to load sharing 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
Cisco Technology Inc.
Ritchie David B.
Theeen Reid & Priest LLP
Ton Dang
LandOfFree
Load sharing over blocked links does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Load sharing over blocked links, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Load sharing over blocked links will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2956946