Multiplex communications – Channel assignment techniques – Messages addressed to multiple destinations
Reexamination Certificate
1998-05-15
2002-11-12
Nguyen, Steven (Department: 2664)
Multiplex communications
Channel assignment techniques
Messages addressed to multiple destinations
C370S254000, C370S390000
Reexamination Certificate
active
06480502
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to broadcasting packets in a communications network including switches, and more particularly to avoiding deadlock during a broadcast of packets.
BACKGROUND OF THE INVENTION
One type of local area mesh-connected network that can be used to broadcast message packets is called a cut-through network. In a cut-through network, switches forward packets from sources to destinations without necessarily storing complete packets in switch buffers at any point in time. Cut-through networks are contrasted with traditional store-and-forward networks where each packet is fully buffered in each switch through which the packet passes.
Cut-through networks offer advantages in performance and cost. A cut-through network is logically represented by a spanning tree. A spanning tree can be represented as a graph of nodes and edges, where the nodes represent the switches and the edges represent the links between the switches. Point-to-point packets can be forwarded both on links and on cross-links. Cross-links are links that are not part of the spanning tree. The use of all links, including cross-links, offers advantages in utilization for point-to-point communication.
One cut-through network is the “AN1” network, originally known as “Autonet.” This cut-through network is a high-speed self-configuring local area network. This cut-through network is described by Schroeder et al. in “Autonet: A High-speed, Self-configuring Local Area Network Using Point-to-Point Links,” SRC Research Report 59, Apr. 30, 1990. See also, Schroeder et al., “High-speed Mesh-connected Local Area Network,” U.S. Pat. No. 5,088,091, issued Feb. 11, 1992.
In a cut-through network such as the Autonet, broadcast packets are directly forwarded “up” the spanning tree to the root switch, and from there the broadcast packet is “flooded” “down” the spanning tree to all destinations. Cross-links are not used. Here, flooding means that the broadcast packet is replicated on all spanning tree links leading “downward” out of a switch. The terms up and down are used to indicate that the links in the spanning tree have some determinable ordering.
The AN1 or Autonet network avoids deadlocks by placing restrictions on when broadcast packet can be stopped, and ensuring that the buffers are big enough to hold all of any broadcast packet. For non-broadcast packets it may be inconvenient or impractical to place a limit on their lengths. The prior approach limits the maximum length of broadcast packets to no more than ½ of the buffer size at switches. The limit on broadcast packets complicates host and bridge network software, especially if the maximum length of a broadcast packet is less than the maximum length of a non-broadcast packet. The minimum requirement of buffer space can make the switches more expensive. The deadlock problems of the prior art network are described in detail in Section 6.6.6 of SRC Research Report 59.
Therefore, there is a need for a network that avoids deadlock during the broadcast of packets without having any size restrictions on buffers used in the network to store the packets during the broadcast.
SUMMARY OF THE INVENTION
The invention provides a method for broadcasting packets in a network including a plurality of switches. The network is a cut-through network that can logically be represented by a spanning tree and cross-links.
A broadcast packet is directly sent from an originating switch to the root switch of the network. At this point the root switch can be considered the current switch.
Copies of the packet are sent from the current switch to all descendant switches when all copies of the packet have been received in the current switch to avoid deadlock during the broadcasting of the packets. Descendant switches are those switches that are connected by downward directed links from the current switch. A downward directed link can be a spanning tree link or a cross-link.
In one aspect of the invention, the current switch simultaneously sends the copies of the packet to the descendant switches. In another aspect, the copies of the packet sent on cross-links are represented by tokens identifying the packet.
In case of a network failure the network is initialized by propagating an initialization state to all switches, collecting the network topology, distributing the network topology to all switches, and waiting until all switches are initialized before resuming operation.
REFERENCES:
patent: 5056085 (1991-10-01), Vu
patent: 5088091 (1992-02-01), Schroeder et al.
patent: 5138615 (1992-08-01), Lamport et al.
patent: 5179558 (1993-01-01), Thacker et al.
patent: 5245607 (1993-09-01), Caram
Schroeder er al.; “Autonet: A High-Speed, Self-Configuring Local Area Network Using Point-to-Point Links” Apr. 1990.
Abadi Martin
Rodeheffer Thomas Lee
Compaq Information Technologies Group L.P.
Nguyen Steven
Sherry Leah
LandOfFree
Method for avoiding broadcast deadlocks in a mesh-connected... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for avoiding broadcast deadlocks in a mesh-connected..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for avoiding broadcast deadlocks in a mesh-connected... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2967793