Method and system for transmitting data within a tree structure and receiving a confirmation or status therefor

• US 5,910,179 A
• Filed: 10/25/1996
• Issued: 06/08/1999
• Est. Priority Date: 10/25/1996
• Status: Expired due to Term

• Current Assignee: Pitney Bowes Incorporated (Böwe Systec AG)
• Original Assignee: Pitney Bowes Incorporated (Böwe Systec AG)
• Inventors: Mohseni, Ali Akbar
• Primary Examiner(s): Barry, Esq., Lance Leonard
• Application Number:
  US08/736,861
• Time in Patent Office: 956 Days
• Field of Search: 340/825.02, 370/407, 370/408, 364/229.41, 364/940.92, 364/240.9, 395/200.82
• US Class Current: 709/252
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

Communication of information from a central station, acting as a source node, to a plurality of destination nodes at customer sites is implemented by using various of the destination nodes as intermediary transfer nodes, which receive information from the central station or from other predecessor intermediary nodes and which transfer the information to other intermediary transfer nodes or to final destination nodes. Communication links are established between specified ones of the destination nodes to provide a grouping of nodes in which each node transfers information to no more than a predetermined number of nodes, resulting in a top-down tree structure in which the central station is a top source node of the tree. The destination nodes provide confirmation signals confirming receipt of the transmitted information to the nodes in the immediately preceding level of the tree structure, along the same communication links used to transmit the information. The confirmation signals are received from each of the nodes to which the information was successfully transmitted, thus identifying those nodes in the tree structure which failed to receive data, as well as the nodes at the lowest tree level with confirmed receipt of the information.

Claims

1. In a network of customer stations, including a computer controlled service center having apparatus for transmitting a set of data from the service center to a plurality of N customer stations where N is an integer, wherein each customer station of the network includes at least a receiver, a transmitter, and a storage, the improvement comprising:

(a) configuring means for establishing a tree structure including groups of customer stations and for establishing communication links thereamong, the tree structure including L tree levels where L is an integer,

(b) customer stations at each level n being connected in accordance with said tree structure to receive data signals from at least one customer station at a preceding level n-1 of the tree structure via respectively corresponding ones of said communication links and to transfer data signals to a set of B respective customer stations at a subsequent level n+1 of the tree structure via respectively corresponding ones of said communication links, where n=1, 2, . . . L-1, a level 0 is defined as a level including said service center, and B is an integer less than N;

(c) a transmitter of each customer station at level n of the tree structure being connected to receivers of a respective set of B customer stations at level n+1 of the tree structure for transmitting the set of data to receivers thereof;

(d) a receiver of each customer station at level n of the tree structure being connected to a transmitter of a respective customer station at level n-1 of the tree structure for receiving the set of data therefrom;

(i) said service center connected to a set of B customer stations at level 1 of the tree structure for transmitting the set of data to receivers thereof via respectively corresponding ones of said communication links,

(ii) whereby the set of data is transmitted to said plurality of N customer stations with reduced involvement of said service center, which transmits the set of data only to said set of B customer stations at said level 1 of the tree structure and

(e) confirming means for transmitting confirmation signals whereby said service center receives a confirmation signal identifying each of said customer stations failing to receive the set of data transmitted thereto.

2. Computer controlled apparatus for transmitting a set of data from a source node to a plurality of N destination nodes of a communication network where N is an integer, wherein each node of the communication network includes at least a receiver, a transmitter, and a storage, comprising:

(a) configuring means for establishing a tree structure configuration of said communication network including L tree levels where L is an integer,

(b) nodes at each level n being connected in accordance with said configuring means to receive data signals from at least one node at a preceding level n-1 of the tree structure configuration and to transfer data signals to a set of B respective nodes at a subsequent level n+1 of the tree structure, where n=1, 2, . . . L-1, a level 0 is defined as a level including said source node, and B is an integer less than N;

(c) a transmitter of each node at level n being connected to receivers of a respective set of B nodes at level n+1 of the tree structure configuration of the communication network established by said configuring means for transmitting the set of data to receivers thereof;

(d) a receiver of each node at level n being connected to a transmitter of a respective node at level n-1 of the tree structure configuration of the communication network established by said configuring means for receiving the set of data therefrom;

(i) said source node connected to a set of B nodes at level 1 of the tree structure configuration for transmitting the set of data to receivers thereof,

(ii) whereby the set of data is transmitted to said plurality of N destination nodes with reduced involvement of said source node, which transmits the set of data only to said set of B nodes at said level 1; and

(e) confirming means for transmitting confirmation signals, including;

(i) a connection from transmitters of nodes at the final level L of the tree structure configuration to receivers of the respective nodes connected thereto at immediately preceding level L-1;

(ii) for n=1, 2, . . . L-1, receivers of each node at level n of said tree structure connected for receiving confirmation signals from the transmitters of B nodes at level n+1 of the tree structure to which said each node had transmitted the set of data; and

(iii) transmitters of each said node at said level n connected for transmitting a further confirmation signal, including confirmation data from each of said B nodes at said level n+1, to the respective node transmitting the set of data thereto from level n-1;

whereby said source node receives a confirmation signal identifying nodes failing to receive the set of data transmitted thereto.

3. Apparatus according to claim 2, wherein said configuring means comprises programmed computer means transmitting configuration data to said N nodes of the communication network for establishing said L tree levels, for establishing respective position identifications of said N nodes in said L levels, and for establishing connections of nodes identified as positioned in level n to respective nodes in levels n-1 and n+1, wherein each node comprises configuration storage means for storing said configuration data.

4. Apparatus according to claim 2, wherein said configuring means comprises configuration storage means in each node for storing tree structure configuration data identifying a respective position of said each node as being in a particular one of said L levels, and for storing connection information to respective nodes identified as positioned in levels n-1 and n+1.

5. A method for transmitting a set of data from a transferor source node to a plurality of N destination transferee nodes of a communication network, where N is an integer, comprising the steps of:

(a) transmitting the set of data from the transferor node to a set of B intermediate transferee nodes at a particular level n of a tree structure configuration of the communication network, where n is an integer, said set of B intermediate transferee nodes is a subset of said set of N destination transferee nodes and B is an integer smaller than N;

(b) each of said intermediate transferee nodes at said particular level of said tree structure thereafter operating as a subsidiary transferor node and transferring the set of data to an additional subset of B intermediate transferee nodes at a next level of the tree structure configuration of the communication network;

(c) iteratively repeating said step of transferring the set of data from intermediate transferee nodes operating as subsidiary transferor nodes to additional sets of intermediate transferee nodes at a next level of the tree structure configuration so that at a K^th iteration intermediate transferee nodes at a present level n+K of the tree structure configuration transfer the set of data to sets of nodes at a next level n+K+1 of the tree structure configuration where K is an iteration index successively taking values K=1, 2, 3, . . . until the present level of the tree structure configuration of the communication network is a final level P of the tree structure configuration, where P is an integer;

(d) whereby the set of data is transmitted to said plurality of N remote destination transferee nodes with reduced involvement of said transferor node, which transmits the set of data only to said single subset of B intermediate transferee nodes at said step 6(a);

(e) transmitting confirmation signals by implementing the steps of;

(i) transmitting a confirmation signal from a transferee node at the final level P of the tree structure configuration to the intermediate transferor node therefor at a particular immediately preceding level P-1; and

wherein each of said intermediate transferor nodes at said particular immediately preceding level of said tree structure performing the steps of;

(ii) receiving confirmation signals from the subset of B transferee nodes at said next level of the tree structure to which it had transmitted the set of data;

(iii) generating a further confirmation signal including confirmation data from each of said subset of B transferee nodes at said next level; and

(iv) transmitting said further confirmation signal to the transferor node therefor at the level preceding thereof; and

(f) iteratively repeating said steps of receiving confirmation signals, generating a further confirmation signal and transmitting said further confirmation signal to next preceding level of the tree structure configuration so that at an R^th iteration intermediate transferee nodes at a level P-R of the tree structure configuration transfer the confirmation signals to nodes at a preceding level P-R-1 of the tree structure configuration where R is an iteration index successively taking values R=1, 2, 3, . . . until the next preceding level of the tree structure configuration of the communication network includes the transferor source node.

6. A method for transmitting the set of data in accordance with claim 5, comprising the further step of establishing said tree structure configuration of the communication network by transmitting tree structure information to said subset of B intermediate transferee nodes of said set of N destination transferee nodes.

7. A method for transmitting the set of data in accordance with claim 5, wherein said step 6(a) of transmitting the set of data comprises transmitting first update information to second update information stored in said N nodes.

8. A method for transmitting the set of data in accordance with claim 5, wherein said step 6(a) of transmitting the set of data further comprises transmitting tree structure information to said subset of B intermediate transferee nodes of said set of N destination transferee nodes and said step 6(b) further comprises the step of transferring the tree structure information from said subset of B intermediate transferee nodes at said particular level of the tree structure configuration of the communication network to an additional subset of B intermediate transferee nodes at said next level of the tree structure configuration of the communication network.