Patent US5459725A successfully refreshed from Google Patents.
US5459725A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Reliable multicasting over spanning trees in packet communications networks
Assignee: Intergraph Corp
•
Filing: 1994-03-22
•
Granted: 1995-10-17
•
Expires: 2014-03-22
Abstract
Abstract A packet communications network in which multicast transmissions are made reliable by transmitting acknowledgements to all neighbors of every receiving node, including the source node. This allows the relinquishment of message holding buffers as soon as all near neighbors acknowledge receipt of the message after only tile longest round trip time to the nearest neighbors, rather than the round trip to the furthest destination. Moreover, highly reliable ancillary point-to-point transmission facilities can be used to retransmit multicast messages indicated as being lost by failure of acknowledgment. Finally, network partitions occurring during the multicast procedure do not necessarily lose the multicast message to the remote partitions since any node receiving the message can insure delivery to all other nodes in that partition.
Inventors
- 👤 Rachel A. Bodner
- 👤 Chee-Seng Chow
- 👤 Israel Cidon
- 👤 John G. Dudley
- 👤 Allan K. Edwards
- 👤 Inder S. Gopal
- 👤 Chandra P. Immanuel
- 👤 Marc A. Kaplan
- 👤 Shay Kutten
- 👤 Theodore E. Tedijanto
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 04:30
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/02; H04L12/16; H04L12/18; H04L12/1863; H04L12/1868; H04L1/00; H04L1/12; H04L1/16; H04L1/1607; H04L1/1685; H04L1/18; H04L1/1867; H04L1/188; H04L12/1854; H04L2001/0092; H04L2001/0093; H04L2001/125
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
120 words
A packet transmission network comprising a plurality of nodes, a plurality of transmission links for interconnecting said nodes to each other, and multicast transmission means for transmitting the same multicast message to a plurality of said nodes, the interconnection between said nodes being represented by a spanning tree, means at each said node for transmitting an acknowledgment of the receipt of said multicast message at said each node interconnected by said spanning tree to all nodes immediately adjacent to said each node on said spanning tree, and means at each said node for retransmitting said multicast message when acknowledgments of the reception of said multicast message are not received from all of said immediately adjacent nodes on said spanning tree.
Claim 2
Dependent Claim
120 words
A packet transmission network comprising a plurality of nodes, a plurality of transmission links for interconnecting said nodes to each other, and multicast transmission means for transmitting the same multicast message to a plurality of said nodes, the interconnection between said nodes being represented by a spanning tree, means at each said node for transmitting an acknowledgment of the receipt of said multicast message at said each node interconnected by said spanning tree to all nodes immediately adjacent to said each node on said spanning tree, and means at each said node for retransmitting said multicast message when acknowledgments of the reception of said multicast message are not received from all of said immediately adjacent nodes on said spanning tree.
Claim 3
Dependent Claim
30 words
The packet transmission network according to claim 1 further comprising reliable point-to-point transmission means between each adjacent pair of said nodes, said retransmitting means utilizing said reliable point-to-point transmission means.
Claim 4
Dependent Claim
36 words
The packet transmission network according to claim 1 further comprising means for generating a list of all near neighbors of .a given node whenever said multicast message is received by or transmitted from said given node.
Claim 5
Dependent Claim
37 words
The packet transmission network according to claim 3 further comprising means for removing from said list all of said near neighbors which have already returned acknowledgements to said given node at the time said list is generated.
Claim 6
Dependent Claim
67 words
The packet transmission network according to claim 1 further comprising timing means for timing out a predetermined period of time after the transmission of said multicast message for the receipt of acknowledgments from all near neighbors of said node, and means for retransmitting said multicast message, after the timing out of said timing means, to all of said near neighbors from which acknowledgments have not been received.
Claim 7
Dependent Claim
43 words
The packet transmission network according to claim 2 further comprising means for retransmitting said multicast message, immediately after the receipt of said multicast message over said reliable point-to-point transmission means, to all of said near neighbors from which acknowledgments have not been received.
Claim 8
Dependent Claim
44 words
The packet transmission network according to claim 2 further comprising means responsive to the receipt of an unexpected acknowledgement message for transmitting a non-acknowledgment message to that one of said near neighbors of said each node from which said unexpected acknowledgement message was received.
Claim 9
Independent Claim
112 words
A method for reliably transmitting multicast messages over a packet transmission network, said method comprising interconnecting a plurality of nodes in said network to each other over a plurality of transmission links, and transmitting the same multicast message on a spanning tree in said network, transmitting, from each said node on said spanning tree, an acknowledgment of the receipt of said multicast message at said each node to all nodes immediately adjacent to said each node on said spanning tree, and retransmitting said multicast message from said each node when acknowledgments of the reception of said multicast message are not received from all of said immediately adjacent nodes on said spanning tree.
Claim 10
Independent Claim
112 words
A method for reliably transmitting multicast messages over a packet transmission network, said method comprising interconnecting a plurality of nodes in said network to each other over a plurality of transmission links, and transmitting the same multicast message on a spanning tree in said network, transmitting, from each said node on said spanning tree, an acknowledgment of the receipt of said multicast message at said each node to all nodes immediately adjacent to said each node on said spanning tree, and retransmitting said multicast message from said each node when acknowledgments of the reception of said multicast message are not received from all of said immediately adjacent nodes on said spanning tree.
Claim 11
Dependent Claim
38 words
The method according to claim 8 further comprising the steps of interconnecting each adjacent pair of said nodes with reliable point-to-point transmission means, and utilizing said reliable point-to-point transmission means for said step of retransmitting said multicast message.
Claim 12
Dependent Claim
35 words
The method according to claim 8 further comprising the step of generating a list of all near neighbors of a given node whenever said multicast message is received by or transmitted from said given node.
Claim 13
Dependent Claim
36 words
The method according to claim 8 further comprising the step of removing from said list all of said near neighbors which have already returned acknowledgements to said given node at the time said list is generated.
Claim 14
Dependent Claim
63 words
The method according to claim 8 further comprising the steps of timing out a predetermined period of time after the transmission of said multicast message for the receipt of acknowledgments from all near neighbors of said node, and retransmitting said multicast message, after the timing out of said predetermined period, to all of said near neighbors from which acknowledgments have not been received.
Claim 15
Dependent Claim
44 words
The method according to claim 10 further comprising the step of retransmitting said multicast message from each node immediately after the receipt of said reliable point-to-point transmission of said multicast message to all of said near neighbors from which acknowledgments have not been received.
Claim 16
Dependent Claim
37 words
The method according to claim 8 further comprising transmitting a non-acknowledgment message to a near neighbor of said each node in response to the receipt of an unexpected acknowledgment message from that one of said near neighbors.
Claim 17
Dependent Claim
89 words
A reliable multicast message delivery system for a multinode packet transmission network utilizing spanning trees to identify nodes to which multicast messages are to be delivered, said delivery system comprising, means at each said node for receiving and retransmitting multicast messages from and to other members of the same multicast tree, and means at each said node for sending and receiving acknowledgment messages to and from all immediate neighbors of said each node on said spanning tree to which and from which said multicast messages are sent or received.
Claim 18
Dependent Claim
89 words
A reliable multicast message delivery system for a multinode packet transmission network utilizing spanning trees to identify nodes to which multicast messages are to be delivered, said delivery system comprising, means at each said node for receiving and retransmitting multicast messages from and to other members of the same multicast tree, and means at each said node for sending and receiving acknowledgment messages to and from all immediate neighbors of said each node on said spanning tree to which and from which said multicast messages are sent or received.
Claim 19
Dependent Claim
35 words
The reliable multicast message delivery system according to claim 15 further comprising reliable point-to-point transmission means between each adjacent pair of said nodes for retransmission of said multicast messages when an acknowledgment is not received.
Claim 20
Dependent Claim
67 words
The reliable multicast message delivery system according to claim 15 further comprising means at each said node for creating a list of near neighbors of said each node on said spanning tree only when a multicast message is received at that node, and utilizing said list to insure that said multicast message is retransmitted to all of said near neighbors from which an acknowledgment is not received.
Claim 21
Dependent Claim
119 words
In a packet transmission network including a plurality of nodes, a plurality of transmission links for connecting said nodes to each other, and multicast transmission means utilizing a spanning tree for transmitting a multicast message to a plurality of said nodes, improved multicasting means at a selected node capable of receiving and transmitting multicast messages, said improved multicasting means comprising means for transmitting an acknowledgement of a multicast message, received from another node, to all nodes immediately adjacent to the given node on said spanning tree, and means for retransmitting a multicast message when acknowledgements of the reception of the original transmission of the message are not received from all of the immediately adjacent nodes of said spanning tree.
Claim 22
Dependent Claim
119 words
In a packet transmission network including a plurality of nodes, a plurality of transmission links for connecting said nodes to each other, and multicast transmission means utilizing a spanning tree for transmitting a multicast message to a plurality of said nodes, improved multicasting means at a selected node capable of receiving and transmitting multicast messages, said improved multicasting means comprising means for transmitting an acknowledgement of a multicast message, received from another node, to all nodes immediately adjacent to the given node on said spanning tree, and means for retransmitting a multicast message when acknowledgements of the reception of the original transmission of the message are not received from all of the immediately adjacent nodes of said spanning tree.
Claim 23
Dependent Claim
36 words
The packet transmission network according to claim 18 further comprising reliable point-to-point transmission means between said selected node and each said immediately adjacent one of said nodes, said retransmitting means utilizing said reliable point-to-point transmission means.
Claim 24
Dependent Claim
35 words
The packet transmission network according to claim 18 further comprising means for generating a list of all near neighbors of said selected node whenever multicast message is received by or transmitted from said selected node.
Claim 25
Dependent Claim
37 words
The packet transmission network according to claim 20 further comprising means for removing from said list all of said near neighbors which have already returned acknowledgements to said given node at the time said list is generated.
Claim 26
Dependent Claim
76 words
The packet transmission network according to claim 18 further comprising timing means for timing out a predetermined period of time after the transmission of said multicast message from said selected node for the receipt of acknowledgments from all near neighbors of said selected node, and means in said selected node for retransmitting said multicast message, after the timing out of said timing means, to all of said near neighbors from which acknowledgments have not been received.
Claim 27
Dependent Claim
47 words
The packet transmission network according to claim 19 wherein said means for retransmitting comprises means for retransmitting said multicast message, immediately after the receipt of said multicast message over said reliable point-to-point transmission means, to all of said near neighbors from which acknowledgments have not been received.
Claim 28
Dependent Claim
44 words
The packet transmission network according to claim 19 further comprising means responsive to the receipt of an unexpected acknowledgement message for transmitting a non-acknowledgment message to that one of said near neighbors of said each node from which said unexpected acknowledgement message was received.
Claim 29
Dependent Claim
147 words
For use in a packet transmission network including a plurality of nodes and a plurality of transmission links for interconnecting said nodes, said nodes having a capability of transmitting multicast messages to nodes, the interconnection of which is represented by a spanning tree, an improved multicasting method practiced in a selected node of said network, said method comprising the steps of receiving a multicast message from another node, transmitting the multicast message to all nodes immediately adjacent the selected node on the spanning tree except the node from which the message was received, transmitting an acknowledgement of the multicast message to all nodes immediately adjacent the selected node on the spanning tree, and retransmitting the multicast message when acknowledgements of the receipt of the original transmission of said message are not received at the selected node from all of the immediately adjacent nodes on said spanning tree.
Claim 30
Dependent Claim
147 words
For use in a packet transmission network including a plurality of nodes and a plurality of transmission links for interconnecting said nodes, said nodes having a capability of transmitting multicast messages to nodes, the interconnection of which is represented by a spanning tree, an improved multicasting method practiced in a selected node of said network, said method comprising the steps of receiving a multicast message from another node, transmitting the multicast message to all nodes immediately adjacent the selected node on the spanning tree except the node from which the message was received, transmitting an acknowledgement of the multicast message to all nodes immediately adjacent the selected node on the spanning tree, and retransmitting the multicast message when acknowledgements of the receipt of the original transmission of said message are not received at the selected node from all of the immediately adjacent nodes on said spanning tree.
Claim 31
Dependent Claim
42 words
The method according to claim 25 further comprising the steps of interconnecting said selected node with each adjacent one of said nodes with reliable point-to-point transmission means, and utilizing said reliable point-to-point transmission means for said step of retransmitting said multicast message.
Claim 32
Dependent Claim
35 words
The method according to claim 25 further comprising the step of generating a list of all near neighbors of said selected node whenever said multicast message is received by or transmitted from said selected node.
Claim 33
Dependent Claim
36 words
The method according to claim 27 further comprising the step of removing from said list all of said near neighbors which have already returned acknowledgements to said selected node at the time said list is generated.
Claim 34
Dependent Claim
65 words
The method according to claim 25 further comprising the steps of timing out a predetermined period of time after the transmission of said multicast message for the receipt of acknowledgments from all said immediately adjacent neighbors of said node, and retransmitting said multicast message, after the timing out of said predetermined period, to all of said near neighbors from which acknowledgments have not been received.
Claim 35
Dependent Claim
46 words
The method according to claim 26 further comprising the step of retransmitting said multicast message from said selected node immediately after the receipt of said reliable point-to-point transmission of said multicast message to all of said immediately adjacent neighbors from which acknowledgments have not been received.
Claim 36
Dependent Claim
41 words
The method according to claim 25 further comprising transmitting a non-acknowledgment message to an immediately adjacent near neighbor of said selected node in response to the receipt of an unexpected acknowledgment message from that one of said immediately adjacent near neighbor.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-10-16 | 1999-04-17 | 1999-10-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-10-16 | 2003-04-17 | 2003-10-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-10-16 | 2007-04-17 | 2007-10-17 | $7700.00 | Window Closed / Lapsed |