Recovery of distributed hierarchical data access routing system upon detected failure of communication between nodes
First Claim
1. A recovery method for a data access system for accessing data elements stored in a distributed data structure, wherein the system comprises a hierarchy of nodes having communication links there between, the hierarchy extending from a root node to a plurality of end nodes, said plurality of end nodes providing the distributed data structure, and wherein routes through the hierarchy to specific data elements stored at the end nodes are identifiable by pointers stored in nodes along each route, and further wherein a request to access a specific data element triggers a search message which passes through the hierarchy from an end node towards the root node until it reaches a node having a pointer relevant to the specific data element, whereafter the search message is passed along the associated route to the end node containing the data element, said recovery method comprising the steps of:
- (a) detecting a failure of part of the hierarchy affecting communication between at least one respective child node and respective parent node of the hierarchy;
(b) establishing a first further communication link between the child node and a further node, the further node then becoming a second respective parent node to the respective child node;
(c) establishing a second further communication link between the second parent node and the first parent node;
(d) instructing the first parent node to send messages destined for the child node to the second parent node from which node they are passed to the child node; and
(e) the second parent node periodically updating the other nodes of the hierarchy as to the new location of the child node in the hierarchy.
1 Assignment
0 Petitions
Accused Products
Abstract
Data elements stored in a distributed data structure are accessible by means of a hierarchical routing network in which routes through the network to individual data elements are flagged. The network includes communicating links between nodes extending from a "root node" to a plurality of end nodes. The end nodes contain the data elements. To find a data element, a search message entering the network at an end node passes through the network towards the root node until it encounters a flagged route to the relevant data element. Thereafter it passes along the route to the end node containing the relevant data element. The invention is relevant to personal numbering services in a communications network. In this case, the data elements each comprise hardware addresses for users of the network. If a user moves in relation to the network, their hardware address will change and, in many cases, the relevant end node will also change. However, the flagged route consequently changes and the routing network therefore provides automatic tracing of the user. In the case of communication failure between a child and parent node, special system recovery techniques are used to establish a new parent node and to efficiently communicate the hierarchical change to other nodes as needed.
-
Citations
20 Claims
-
1. A recovery method for a data access system for accessing data elements stored in a distributed data structure, wherein the system comprises a hierarchy of nodes having communication links there between, the hierarchy extending from a root node to a plurality of end nodes, said plurality of end nodes providing the distributed data structure, and wherein routes through the hierarchy to specific data elements stored at the end nodes are identifiable by pointers stored in nodes along each route, and further wherein a request to access a specific data element triggers a search message which passes through the hierarchy from an end node towards the root node until it reaches a node having a pointer relevant to the specific data element, whereafter the search message is passed along the associated route to the end node containing the data element, said recovery method comprising the steps of:
-
(a) detecting a failure of part of the hierarchy affecting communication between at least one respective child node and respective parent node of the hierarchy; (b) establishing a first further communication link between the child node and a further node, the further node then becoming a second respective parent node to the respective child node; (c) establishing a second further communication link between the second parent node and the first parent node; (d) instructing the first parent node to send messages destined for the child node to the second parent node from which node they are passed to the child node; and (e) the second parent node periodically updating the other nodes of the hierarchy as to the new location of the child node in the hierarchy. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A recovery apparatus for a data access system accessing data elements stored in a distributed data structure, wherein the system comprises a hierarchy of nodes having communication links therebetween, the hierarchy extending from a root node to a plurality of end nodes, said plurality of end nodes providing the distributed data structure, and wherein routes through the hierarchy to specific data elements stored at the end nodes are identifiable by pointers stored in nodes along each route, and further wherein a request to access a specific data element triggers a search message which passes through the hierarchy from an end node towards the root node until it reaches a node having a pointer relevant to the specific data element, whereafter the search message is passed along the associated route to the end node containing the data element, said recovery apparatus comprising:
-
(a) means for detecting a failure of part of the hierarchy affecting communication between at least one respective child node and respective parent node of the hierarchy; (b) means for establishing a first further communication link between the child node and a further node, the further node then becoming a second respective parent node to the respective child node; (c) means for establishing a second further communication link between the second parent node and the first parent node; (d) means for instructing the first parent node to send messages destined for the child node to the second parent node from which node they are passed to the child node; and (e) means for causing the second parent node periodically updating the other nodes of the hierarchy as to the new location of the child node in the hierarchy. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
Specification