Method for avoiding broadcast deadlocks in a mesh-connected network
AssigneeCompaq Information Technologies Group, L.P.
InventorsMartin Abadi, Thomas Lee Rodeheffer
Life of this patent
Estimating the term…
Abstract
A method for broadcasting packets in a network that includes a plurality of switches. The network can logically be represented by a spanning tree plus cross-links. In order to avoid deadlock during a broadcast, a broadcast packet is sent from an originating switch to a root switch of the network, and a copy of the packet is sent from a current switch to all descendant switches when all copies of the packet have been received in the current switch.
Claims24
A method for broadcasting packets in a network with a plurality of switches, links and cross-links, the network being logically represented by a spanning tree, wherein the spanning tree identifies a root switch and one or more descendant switches, the method comprising the steps of:
- sending copies of a broadcast packet of a broadcast from the root switch to all descendant switches;
- and
- at each descendant switch considered as the current switch,
- waiting to receive at the current switch a copy of the broadcast packet of the broadcast from each switch for which the current switch is a descendent switch,
- then selecting one of the copies of the broadcast packet of the broadcast, and
- forwarding copies of the selected copy of the broadcast packet of the broadcast to all descendents of the current switch.
A method for broadcasting packets in a network with switches one of which being a root switch and others of which being descendent switches connected via links capable of having upward and downward orientation and cross-links capable of having loop-avoiding-arbitrary orientation, the method comprising the steps of:
- flooding, from the root switch down the spanning tree, the packet of a particular broadcast received by the root switch, wherein broadcasts received by the root switch are serialized in order to start descending the respective packet of only one broadcast at a time;
- and
- at each descendant switch considered as the current switch,
- waiting until the current switch receives a replica of the packet of the particular broadcast at each of the downward oriented links leading to it, and
- forwarding to each descendent switch of the current switch, if any exists, one or more replicas of a selected packet replica from the packet replicas received at the current switch for the particular broadcast.
A network for avoiding packet broadcast deadlocks, comprising:
- switches one of which being a root switch that functions as an initial current switch for each incoming broadcast packet, the root switch being configured to serialize the incoming broadcast packets, and any of the switches in the network other than the root switch being a descendant switch that functions as a current switch for one or more replicas of each broadcast packet that descends to it from the root switch;
- links capable of having upward and downward orientation;
- and
- cross-links capable of having loop-avoiding-arbitrary orientation,
- wherein each of the current switches is a direct descendant of one or more switches from which it received replicas of descending broadcast packets via downward-oriented links and/or cross-links, and
- wherein each current switch is configured, upon receiving packet replicas on all of the downward-oriented links and/or cross-links leading to it, not to forward any packet replicas until there is a match between a particular broadcast packet and all the packet replicas received by it, whereby packet broadcast deadlocks are avoided.
Dependencies are inferred from the claim text.