JPH07122861B2 - Name resolution device - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a name resolution device in a distributed environment in which a plurality of computers are connected via a network.

[0002]

2. Description of the Related Art FIG. 18 is a diagram showing the concept of a distributed system. In FIG. 18, 181, 182, and 183 are computers called nodes, and 184 is a network connecting the nodes. In a distributed system, one distributed operating system manages resources for all nodes in the system. Managed resources such as software and hardware, printers, databases, and storage devices have unique names in the system, and a name server, which is a part of the distributed operating system, manages correspondence between resource names and locations.

When a user process uses a resource, the resource name is sent to the name server, which parses the resource name and returns the location of that resource to the user process.
After that, the user process sends the request to the resource server of the node where the resource is arranged, and processing is performed.

In the system, a resource name is designated by a path name which is a string of element names separated by a boundary symbol '/'. The name server manages a directory in which an entry consisting of a pair of element name and location is registered in order to specify the location of the resource designated by the path name.

The work of extracting the location of a resource from a given pathname, that is, name resolution, is performed by sequentially retrieving the element names specified along the pathname. For example, when the path name '/ a / b / c' is given, the element name a is in the root directory '/' in the first search, and subsequently the element name b is in the directory '/'.
a ', and finally the element name c is the directory' /
The pathname is resolved by searching in a / b '.

FIG. 19 is a conceptual diagram showing a method (A Single Centralized Name Server) of managing all directories by a single name server existing in one node of the system. In FIG. 19, 191 is a name server, 1
Reference numerals 94, 195 and 196 are nodes, 192 is a node where a name server exists, and 193 is a directory which only exists in the system.

FIG. 20 shows a method in which a name server is provided in each node of the system and each name server manages a subset of directories (Several Distributed Name Se
It is a conceptual diagram which shows rver). 20, 201 and 2
01 and 203 are subsets of directories managed by each node, 204, 205 and 206 are nodes that constitute a distributed system, 207, 208 and 209 are name servers provided in each node, 2010, 2011 and 2012 are user processes, 2013 is a network.

[0008]

However, in the conventional method of managing all directories by a single name server existing in one node of the system, the scalability for the scale of the system (scalabilit:
y) is missing, and a method of providing a name server on each node and managing each name server for a subset of the directory solves the scalability problem, but if one node goes down, it is managed by that node. There is a problem in that it is impossible to resolve a pathname including an element name that requires a sufficient reliability.

The present invention is intended to solve the problems relating to scalability and reliability in the above-mentioned prior art, and is a name resolution device which is rich in scalability and in which reliability can be dynamically set according to the needs of the user. The purpose is to provide.

[0010]

A name resolution device according to the present invention for solving the above-mentioned problems is, firstly, a parameter setting means for designating a sub-path which is a path name to be resolved at its own node without inquiring to other nodes. And a parameter provided on each of the directories based on a reliability area for storing information as to whether the directory is a copy and a reference area for storing the number of times the directory is required to satisfy the condition specified by the parameter setting means. The sub path setting means for managing the directory is provided according to the sub path designated by the setting means.

Second, parameter setting means for designating the maximum number of times of migration to another node required in the path for path name resolution and information as to whether or not the directory provided in each directory is a copy are stored. Stage setting means for managing the directory according to the maximum number of times of migration specified by the parameter setting means based on the reliability area and the reference area for storing the number of times the directory is required to satisfy the condition specified by the parameter setting means It is configured with.

Thirdly, parameter setting means for designating the minimum number of paths that can be taken between any two nodes other than the end node among paths for path name resolution, and whether or not the directories provided in each directory are duplicates. Of the total number of nodes in the system and the route specified by the parameter setting means based on the reliability area for storing the information of the information and the reference area for storing the number of times required to satisfy the definition specified by the parameter setting means. Is configured to include a path setting means for managing the directory according to the minimum number of.

Fourth, a sub-path consisting of paths that can be resolved by one's own node without inquiring about other nodes,
A parameter that specifies the maximum number of transitions to other nodes required in the path for path name resolution, and the minimum number of paths that can be taken between any two nodes in the path for path name resolution, excluding the end node. Based on the setting means, a reliability area provided in each directory for storing information as to whether the directory is a copy and a reference area for storing the number of times required to satisfy the definition specified by the parameter setting means, Sub-path setting means for managing the directory according to the sub-path specified by the parameter setting means, and stage setting means for managing the directory according to the maximum number of transitions specified by the parameter setting means based on the reliability area and the reference area. Based on the information stored in the reliability area and the reference area, the total number of nodes in the system and the And it has a configuration that includes a path setting means for managing the directory in accordance with the minimum number.

[0014]

In the above structure, when the sub-path setting means, the stage setting means, and the path setting means duplicate the directory required for the condition related to the reliability set by the parameter setting means to an appropriate node, and when it is no longer necessary. By deleting the directory, the user can dynamically define the reliability without managing unnecessary directories.

[0015]

DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described with reference to the drawings. FIG. 1 is a block diagram showing the configuration of the name resolution device of the present invention. In FIG. 1, 11 is a parameter setting means for setting a user's request, 12 is a replica setting means set by the parameter setting means 11 for duplicating and deleting a directory based on a user's request, and the replica setting means 12 is a sub path. The setting unit 13, the m-stage setting unit 14, and the k-pass setting unit 15 are included.

In the parameter setting means 11, as a request from the user, a user node used by the user and a path name to be resolved, and a sub path which is a path name to be resolved at the own node without inquiring to other nodes,
The maximum value (m-stage value) of the number of transitions to another node that occurs in the path of path name resolution and the path that can be taken between any two nodes in the path of path name resolution excluding the end node. The minimum number (k-pass) is set.

A subpath is a pathname to be resolved,
It is a pathname that can be resolved by your own node without referring to other nodes, and the longer the subpath, the higher the reliability. The m-stage value is the number of transitions between nodes required for name resolution processing, and the smaller the m-stage value, the higher the reliability. The k-path is the minimum number of paths that can be taken between any two nodes except the terminal node in the name resolution path, and the larger the k-path value, the higher the reliability.

FIG. 2 shows the pathname to be resolved '/ a / b.
FIG. 6 is a diagram showing a state in which node 1 satisfies subpath '/ a / b' for / c / d '. 202 and 20 in FIG.
Reference numerals 3 and 204 are directories existing on the node 1, respectively. In FIG. 2, the pathname '/ a from node 1
When resolving / b / c / d ', the directory'
Since / ',' / a ', and' / a / b 'exist on the node 1, it is possible to resolve the path name up to' / a / b 'without moving to another node.

FIG. 3 shows the pathname '/ in node 1.
In the resolution of a / b / c / d ', the m-stage value is 2
It is a figure which shows the case where it is. In FIG. 3, 31 indicates a node 1, 32 indicates a node 99, and 33 indicates a node 8. When the path name '/ a / b / c / d' is resolved from node 1 in the state of FIG. 3, node 1 '/'
In the next search for'b ', which moves to the node 99 in which a'exists, since there is no' / a / b 'in the same node 99, there is no need to move between nodes. Transition. Therefore, in this case, it is necessary to transfer between nodes twice, and this transfer count is the m-stage value. In addition,
In node 8, since the existence position of '/ a / b / c / d' is determined, further migration is not necessary, and name resolution is performed by node 8
Complete with. 4A shows a state in which the k-path value is 2 in the resolution of the path name '/ a / b / c' in the node 1, and FIG. 4B shows a state in which the k-path value is 3. Is. In FIG. 4, lines connecting the nodes indicate logical paths between directories.

The replica setting means 12 is suitable for satisfying the user request defined by the parameter setting means 11 using the above parameters, based on the information stored in the reliability area and the reference area provided in each directory. Duplicate directories and delete them.

FIG. 5 is a diagram showing the structure of a directory used in the present invention. In FIG. 5, reference numeral 50 denotes a reliability field indicating whether the original directory, 51
Is a reference count field (RC) indicating the number of times its presence was requested in the same node to satisfy the user's request, and these values in the original directory are: reliability RF = NO, reference count =
It is 0.

The replica setting means 12 manages the directory by using two fields, a reliability field (FR) and a reference count field (RC) provided in each directory. The reliability field (FR) indicates whether or not the directory is a duplicate, and in the case of the original, FR =
No, RF = YES is set in the case of duplication. Further, the reference count field (RC) is a subpath reference count field (SPRC), m corresponding to each of the subpath, m-stage, and k-path.
-Stage Reference Count Field (MSR
C), k-path reference count field (KP
RC) and the directory is duplicated to meet a user's certain parameter requirements, or whenever the directory is needed to meet different user's parameter requirements, one is added to its corresponding RC. If the existence of the directory is no longer needed to satisfy the parameter requirement, then the corresponding RC is decremented by one.

When the directory is duplicated to satisfy the reliability requirement of the user, the replica setting means 12 sets the value of the reliability field (FR) of the duplicated directory to YES and sets the value of the corresponding reference count field to 1 Set to. Further, a directory in which the value of the reliability field is YES and the values of all the reference count fields become zero is deleted from the node.

In the name resolution device configured as described above, the operation of each setting unit will be described with reference to the drawings.
6, 7, and 8 are diagrams showing the flow of processing of the sub-path setting unit 13. The sub-path setting unit 13 inputs from the parameter setting means 11 a path name to be resolved, a user node, and a new sub-path which is a value of the sub-path desired by the user (step 600), and then checks whether the designation of the new sub-path is a sub-path change. Yes (601). This comparison can be realized, for example, by holding a history of parameter designation for each user. Old-su if changed
bpath is the old subpath, new-subpth is the value of the new subpath newly defined by the user (603), tot-dirs-old is the number of directories included in the old subpath, and tot-dirs-new
Is set to the number of directories included in the new subpath (604), and tot-dirs-old and tot-dirs-new are compared (605).

If they are the same, the process is not necessary and the process is terminated (606). If tot-dirs-old <tot-dirs-new, the request for subpath is strengthened, and subpath is the newly defined subpath value and j is tot-dirs-old + 1.
Then, set redeuce to FALSE (607). tot
If -dirs-old <tot-dirs-new, then the subpath requirement is relaxed and subpath is set to the old subpath value.
j is set to tot-dirs-new + 1 and redeuce is set to TRUE (608).

In step 601, when the subpath is not changed, that is, when the subpath is set for the first time, subpath is set to the value of the newly defined subpath, j is set to 1, and redeuce is set.
Is set to FALSE (602), and the process goes to 609. At 609, a check is made to see if the user-defined subpath is appropriate for the pathname, and if not, the user is alerted and exited (610).
Number of directories contained in subpath, if appropriate tot-d
Find irs, decompose the directories contained in subpath, and i =
From 1 to tot-dirs, dir (i) is set to the i-th directory of subpath (612).

In 701 of FIG. 7, the value of reduce is FA.
In the case of LSE, i.e. no reduction of subpaths is required, the user node needs to duplicate at least one directory in order to satisfy the request of the new subpath. In this case, from the jth directory of subpath (702), it is checked whether or not each directory already exists in the user node (703) (704) (70
5). FR of the directory that exists in the user node
If = YES (707), the SPRC value of the directory is incremented by 1 (708). If the directory does not exist in the user node, the directory is copied to the user node and FR = YES, SPRC = 1, and other RCs are set to 0 (706).

When reduce is TRUE in 703 of FIG. 7, the directories from dir (j) to dir (tot-dirs) are not necessary for the user's request for the subpath, so the loop of 801 to 807 in FIG. From dir (j) to dir (tot-di
1) is subtracted from the SPRC value of the directory until r) (803). If all RC values become 0 (804), the directory is deleted from the user node (805). 9 to 13 are diagrams showing the flow of processing of the m-stage setting unit 14. After inputting the path name, the user node, and the new m stage value (901), the m-stage setting unit 14 checks whether or not the m stage is changed (902). Old_m_stage if it is a change
= Old m stage value, new_m_stage = new m stage value (903), and both are compared (904). If they are the same, the process is not necessary and the process is terminated (905). old_
If m_stage <new_m_stage, m_stage = new m stage value is set (907).

In 902, when the m stage is not changed, that is, when the user specifies the m stage for the first time, m_stage = new m stage value is set (908), 9
The process starts from 10.

At 910, the total number of directories included in the pathname is set to tot_dirs, the directories in the pathname are decomposed, and dir (i) is set to the i-th directory of the pathname from i = 1 to tot_dirs. Then hpps = t
Set pt_dirs-1, repeat = FASE (91
1), the values of m_satege and hops are compared (912). If they are equal, it is not necessary to perform the process, and the process is terminated (913).
If they are not equal, i = 1, j = 2, node (i) = user node is set (914).

In the loop from 1001 to step 1009 in FIG. 10, when two consecutive directories in the pathname exist in the same node (1002), the current system status is reduced by subtracting 1 from hops (1006). Find out. This process continues only during hops> m_stage (1007).

If the system is already hops≤m_stage, then the directory needed to satisfy the user's m_staege request must be identified by adding 1 to its MSRC (1005). This process
Control by setting the value of repeat to TRUE (1
010) (1012). The value of SPRC is calculated in step 10.
Only if the repeat value in 03 is TRUE and the directory is duplicated (1004), 1 is added.

In loops 1102 to 1107 of FIG. 11,
It is checked whether all directories from the second directory of the path name exist in the user node (1103). It exists in the user node and FR = Y
For the ES directory (1104), its MSR
1 is added to the value of C (1105).

If the directory does not exist in the user node in 1103, the node in which the directory exists is checked in 1201 of FIG. 12, the directory is copied to the user node, and FR = YES, MSRC = 1, other RC Set the value of to 0. Next, the location of the next directory connected to the directory just copied is checked (1202) (1203) (1204).

If the directory exists in the user node (1205) and FR = YES (1206), 1 is added to MSRC of the directory.

If it exists not in the user node but in the same node as the copied node, the directory is copied from that node to the user node, and FR = YES, MS
Set RC = 1 and other RC = 0. If it does not exist in the user node and it does not exist in the copied node,
1 is subtracted from the value of hops (1211) and compared with the value of m_stage (1212). j if larger than m_stage
1 is added to the value of and the same process is repeated from step 100.

At 904 in FIG. 9, old_m_stage> new_m_sta
In case of ge, hops_to_reduce = old_m_stage−new_m_stage
Then, tot_dirs is set to the total number of directories in the pathname (909), and the processing of FIG. 13 is performed. 13 of FIG.
At 32 to 1306, the second directory of the pathname is searched for the first directory (1303) that does not exist in the user node in the pathname, or the first directory that has not been replicated to the user node for the m stage request. (1304). Then, in a loop from 1308 to 1313, from the terminal directory existing in the user node (1307) until the value of hops_to_reduce becomes 0 (1312), or for all directories existing in the user node (1313), the MSR
1 is subtracted from the value of C (1308), and 1 is subtracted from the value of hops_to_reduce (1311). If all RC = 0 when 1 is subtracted from the value of MSRC, (1
039) and delete that directory from the user node (1310).

14 to 17 are diagrams showing the processing of the k-path setting unit 15. The k-path setting unit inputs the total number of nodes tot_nodes of the system in addition to the path name, new k-path value, and user node. The total number of nodes is a number determined when the distributed system is constructed or when the nodes of the distributed system are changed, and is set as a value unique to the system.

After the input (1401), it is checked whether or not the k-path is changed (1402), and if it is changed, old_k_ppath = old k
-Path value, new_k_path = new k-path value, k_path = new k-
Set to path value (1403), old_k_path and new_k_path
The values of are compared (1405). If they are equal, the process ends (1406).

If new_k_path> old_k_ppath, reduce
Set e = FALSE (1408), new_k_path <old
If _k_ppath, path_to_reduce = old_k_ppath-new
Set _k_path, reduce = TRUE (140
7).

When the k-path is not changed in 1401, that is, when the k-path is set for the first time, after setting k-path = new k-path value and reduce = FALSE (1404),
The process starts from 1409. In 1409, the value of k-path is checked to see if it is an appropriate value.
Set path = tot-nodes-1 (1410). Then k-pat
Check whether h is already 1 or less (1411), 1
And if reduce = FALSE (1412),
Since processing is not necessary, the process ends (1413).

If processing is required, 1414 sets tot_dirs as the total number of directories in the pathname, decomposes the directories in the pathname, and dir (i) from i = 1 to tot_dirs.
= Set to the i-th directory in the pathname. Further, if k-path = 0, set k_path = 1. In step 1415, initial values of i, j, node (i), total (i) are set.

In the loop of 1501 to 1512 of FIG. 15, processing is performed from the second directory of the path name to the first directory that does not exist in the user node (1502). For directories that exist in the user node (discovered on the user node) and have FR or YES, the value of reduce is TRUE or FA.
Depending on whether it is LSE, processing of adding 1 to the value of KPRC or subtracting 1 is performed (1503) (1505) (150).
7). All directories whose RC values are 0 when 1 is subtracted from KPRC are deleted from the user node (1508) (1509).

When a directory which does not exist in the user node is found in 1502, the processing shifts to 1601 shown in FIG. In the process shown in FIG. 16, the number of paths between two contiguous directories that do not exist in the same node is adjusted so as to satisfy the new k_path. In 1601, the total number of paths existing between two directories, total_path, is calculated and compared with the value of k_path (1062).

If total_path ≧ k_path, it is not necessary to increase the path between two directories. In this case, delete the path within the range that satisfies the new k_path, or tota
Marking that a directory is required for k_path is performed according to the value of reduce by adding the value of KPRC to k in l_path.

When redeuce = FALSE, marking is performed. In this case, the number m to be marked in 1064 is calculated, and 1 is added to the m KPRC values in total (j) (1605). If total_path <k_path in 1062, it is necessary to create some new paths to satisfy k_path. A new path is created by copying the concatenated second directory to m new nodes. The number of m is calculated in 1607, the m directories are copied in 1608, and the copied FR is YES, K
PRC = 1 and other RC = 0 are set, and tota
Add 1 to the l (j) KPRC values.

If reduce = TRUE in 1603, it means that reduction of the path is required, and 170 in FIG.
The process moves to 1. There are two ways to reduce the path between two concatenated directories. 1702
The loop from 1 to 1706 is a process for deleting the copy of the adjacent first directory. In this case, each time one copy is deleted, the number of the second directory is equal to the total number (total (j)). The number of passes is reduced (1706). 170
The loop from 8 to 1712 is a process for deleting the copy of the concatenated second directory. In this case, every time one copy is deleted, the number of the first directory (total (i) The number of passes is reduced (1712). In either case, path reduction is done by subtracting one from the KPRC value for that directory (170
3) (1709), when all RC = 0, the directory is deleted from the node (1704) (1705) (1710) (1711).

Next, the operation of this apparatus will be described using a specific example. The total number of nodes is 6, and the resource information specified by the path name '/ a / b / c / d / e' is stored in node 6, and the root directory 'is stored in node 1.
/ ', Directory 2 for node' / a / b / c ', node 3 for directory' / a ', node 4 for directory' / a / b / c / d ', node 5 for directory' / '
A description will be given of the flow of processing in the case where a / b ′ exists as the original directories and the respective designations are made by the parameter setting means in the following order.

(1) User 1 is' (user node = node 1, pathname = '/ a / b / c / d / e', subpath = '/ a', 'm-stage = 2', k-path = 2)
Specify.

(2) User 2 (user node = node 1, path name = '/ a / b / c / d / e', sub path = '/ a / b', m-stage = 3, k-path = Specify 3).

(3) User 1 (user node = node 1, pathname = '/ a / b / c / d / e', subpath = '/', m-stage = 0 ', k-path = 0)
Specify.

(4) User 2 (user node = node 1, pathname = '/ a / b / c / d /
e ', sub-path =' / ', m-stage = 0, k-path = 0) is specified.

Table 1 shows the states of the reliability field and the reference counter field of the directory on each node in the initial state. The respective parameter values in this state are (sub path = '/', m-stage = 4, k-path = 1).

[0054]

[Table 1]

Table 2 shows a state in which the processing of the sub-path setting unit in response to the instruction (1) is completed. In response to the instruction of (1), the sub-path setting unit executes su at step 602 in FIG.
bpath = '/ a', j = 1, reduce = FALSE, tot_dirs = 2 is set in step 162, and step 7 in FIG.
In the loop from 03 to step 709, it is found that only '/' exists in the user node and the second directory '/ a' does not exist in the user node (node-1) (step 705). 'Is duplicated from node 3 to node 1, which is the user node, and the respective values are set (step 706). After the duplication, the value of i is incremented to 3 and the process ends by the branch of step 703. The respective parameter values in the state where the processing of the sub-path setting unit is completed are (sub-path = '/ a', m-stage =
3, k-pass = 1).

[0056]

[Table 2]

Table 3 shows a state in which the processes of the sub-path setting unit and the m-stage setting unit have been completed in response to the instruction (1). After the processing of the sub-path setting unit is completed, the processing of the m-stage setting unit is started. In the m-stage setting unit, m_stage = 2 in step 908 of FIG. 9 and step 911.
Is set to hops = 4, repeat = FALSE. Figure 10
In the loop from step 1002 to step 1009, since '/' and '/ a' exist in the same node, hops
Changes from 4 to 3. One more hops needs to be subtracted to meet the user's m-stage requirements. In steps 1102 to 1107 of FIG. 11, 1 is added to the value of the MSRC of all directories from the second directory existing in node 1 and the first directory not existing in node 1 is searched (1103). ). Therefore, here is the MSRC of '/ a'
1 is added to the first directory that does not exist in node 1.
BR> retrieving '/ a / b' existing in the node 5 is searched. Next, in step 1201 of FIG. 12, the node 5
'/ A / b' is copied from node 1 to node 1 and the initial value of that directory is set. K in step 1202
Is the next directory existing in node 2 '/ a / b /
Point to c '. Node 2 and node 1 and node 5
Since they are not equal to each other, 1 is subtracted from hops in step 1211 to change to 2 and m-
As a result of comparison with the stage, processing ends.

The respective parameter values in this state are (subpath = '/ a / b', m-stage = 2, k-path =
1).

[0059]

[Table 3]

Table 4 shows a state in which the processes of the sub-path setting unit, the m-stage setting unit, and the k-path setting unit have been completed, that is,
This is a state in which the instruction of (1) is completed.

In step 1404 of FIG. 14, k_path = 2,
reduce = FALSE, tot_dirs = 5 in step 1414
Is set to. In the loop from step 1501 to step 1512 in FIG. 15, the KPRC for all directories from the second directory existing in node 1
1 is added to the value of and the first directory that does not exist in node 1 is searched (1502). Therefore, in this case, '/ a'. 1 is added to the KPRC value of '/ a / b', and '/ a / b / c' existing in node 2 is searched as the first directory not existing in node 1. Figure 1
In step 1601 of 6, 1 is calculated as the total_path between the directory '/ a / b' specified by i and the directory '/ a / b / c' specified by j. Therefore, in order to satisfy the user's request, it is necessary to add the path of m = 1 calculated in step 1607. In step 1608, the directory '/ a / b / c'
Is copied from node 2 onto node 3 as a new node, its KPRC is set to 1, step 1609
So total (j) = 2. In the next step 1610, i
= 4, total (i) = 2, node (i) = node 2, j = 5, and j is smaller than total_dirs, loop 1610
To step 1613 are repeated. This time, total_path = 2 is calculated in step 1601, and step 160
In 2, it is judged that the value is equal to k_path. reduce = FALS
Since it is E, m = 0 is calculated in step 1604, j = 6 is set in step 1610, and the processing is ended by the determination in step 1611. The respective parameter values in this state are (sub-path = '/ a / b', m-stage =
2, k-pass = 2).

[0062]

[Table 4]

Next, Table 5, Table 6, and Table 7 show from this state to the instruction completion of (2).

[0064]

[Table 5]

In response to the instruction of (2), the sub-path setting unit executes sub-path = '/ a / b', j = 1, step 602 in FIG.
reduce = FALSE, tot_dirs = 3 is set in step 162. Steps 703 to 709 of FIG.
Loop, it is found that '/ a' and '/ a / b' already exist in the user node, and 1 is added to the respective SPRC values. When the SPRC value of '/ a / b' is added, i = 4, which is larger than tot_dirs, so the process ends in accordance with step 703.

The respective parameter values in this state are (sub-path = '/ a / b', m-stage = 2, k-path =
2). In Table 5, SP of '/ a' of node 1
Since RC = 2, it can be seen that this directory is needed by two users to satisfy the sub-path condition. Table 6 shows a state in which the processing of the m-stage setting unit is completed.

[0067]

[Table 6]

In the m-stage setting section, step 9 in FIG.
08, m_stage = 3, step 911: hops = 4, repeat
It is set to at = FALSE. Step 100 of FIG.
In the loop from 2 to step 1009, '/' and '/ a'
Exists in the same node, so hops changes from 4 to 3. Then, according to the branch of step 1007, step 10
In step 12, repeat = TRUE is set, and step 9 in FIG.
The processing shifts to 14. Step 10 shown in FIG. 10 again
The processing from 01 to step 1009 is performed. This time re
Since peat = TRUE, 1 is added to the value of MSRC of the connected directories existing in the same node. As a result, the MSRC value of '/ a' becomes 2. After this hops =
The number is reduced to 3, and the process ends through steps 1007 and 101.

The respective parameter values in this state are (sub-path = '/ a / b', m-stage = 2, k-path =
2). Table 7 shows a state in which the processing of the next k-path setting unit is completed.

[0070]

[Table 7]

In step 1404 of FIG. 14, k_path = 3,
reduce = FALSE, tot_dirs = 5 in step 1414
Is set to. In the loop from step 1501 to step 1512 in FIG. 15, the KPRC for all directories from the second directory existing in node 1
1 is added to the value of and the first directory that does not exist in node 1 is searched (1502). Therefore, '/
a '. 1 is added to the KPRC value of '/ a / b' to become 2, and '/ a / b / c' existing in node 2 and node 3 is searched as the first directory not existing in node 1. In step 1601 of FIG. 16, total_path between the directory '/ a / b' specified by i and the directory '/ a / b / c' specified by j
Is calculated as 2. Therefore, in order to satisfy the user's request, it is necessary to add the path of m = 1 calculated in step 1607. Directory '/ in step 1608
a / b / c 'is copied from node 2 onto node 4 as a new node, its KPRC is set to 1, and the other KPRC values of' / a / b / c 'are incremented by 1 except for the original. It That is, the KPRC value of “/ a / b / c” of the node 3 is set to 2.

Subsequently, in step 1609, total (j) = 3
Is set in step 1610, i = 4, total (i) =
3, node (i) = node 2, j = 5, j is total
It is smaller than _dirs, so loop 1610 to step 16
13 is repeated. This time in step 1601 total_
It is calculated that path = 3, and it is judged to be larger than k_path in step 1602. Since reduce = FALSE, step 1
In step 604, m = 0 is calculated, and in step 1610, j = 6.
Then, the process is terminated by the judgment in step 1611.

In this state, that is, in the state in which the instructions (1) and (2) have been completed, the respective parameter values are (subpath = '/
a / b ', m-stage = 2, k-pass = 3).

Next, the change in the state in which the operation of each setting unit is performed in response to the instruction of the change command (3) from the user 1 will be described with reference to Tables 8, 9, and 10. Table 8 is a diagram showing a state in which the process of the sub-path setting unit in response to the instruction (3) is completed.
When the user 1 changes the sub path from '/ a' to '/', in step 603 of FIG. 6, old_subpat = '/ a', new
_subpat = '/' in step 604, tot_dirs_old = 2, tot
_dirs_new = 1 is set, and in step 605 tot_dirs_o
ld = 2 and tot_dirs_new = 1 are compared. Step 608
After setting reduce = TRUE, subpat = '/ a', j = 2 in step 612 and tot_dirs = 2 in step 612, step 80 in FIG.
The process moves to 1. Steps 801 to 8 in FIG.
At 07, the SPRC value of '/ a' is reduced by 1,
j = 3 and the process ends. The parameter value in this state is (sub-path = '/ a / b', m-stage = 2, k-
Path = 3).

[0075]

[Table 8]

Table 9 shows the state after the processing of the m-stage processing unit is continued for (3). When the user 1 changes the m-stage value from 2 to 0, old_m_stage = 2 and new_m_stage = 0 in step 903 of FIG.
, And compared in step 904. old_m_stag
Since e> new_m_stage, hops_to_re in step 909.
duce = 2 and tot_dirs = 5 are set, and the process proceeds to step 1301 shown in FIG.

Steps 1302 to 1 in FIG.
In the loop of 306, '/ a / b / corresponding to j = 4 as the first directory that does not exist in the user node
c ′ is searched, and steps 1308 to 131 are performed.
In the loop of 3, the user nodes' / a / b ',' /
Subtract 1 from the SPRC value of a '. hops_to_reduce ＝
The process ends when the value becomes 0. Finally, the SPRC of '/ a / b' on node 1 becomes 0, and the SPRC of '/ a'
Becomes 1. The parameter value in this state is (subpath = '
/ A / b ', m-stage = 2, k-pass = 3).

[0078]

[Table 9]

Table 10 shows the state after the processing of the k-path setting section has been carried out for (3). If user 1 changes the value of k-pass from 2 to 0,
Step 1403, old_k_path = 2, new_k_path =
0, k_path = 0 is set, and old_k_p is set in step 1405.
ath and new_k_path are compared. old_k_path> new_k_pat
Since it is h, in step 1407 path_to_reduce = 2,
reduce = TRUE, in step 1414 k_path = 1, tot_
dirs = 5, i = 1, node (i) = node 1, total (i) = 1, j = 2 in step 1415 are set, and in steps 1501 to 1512 of FIG. From the directory, subtract 1 from the value of its KPRC for all directories and the first directory that does not exist in node 1 is searched (1502). As a result, KPRC of '/ a' and '/ a / b' on node 1
Is reduced to 1 and the first directory is' / a
/ B / c 'is searched. Next, step 160 in FIG.
1 = total_path = between '/ a / b' and '/ a / b / c'
After calculating 3, the process proceeds to step 1701 shown in FIG. 17 via step 1603. Since node (i) = user node, the process proceeds to step 1708, and step 17
In the loop from 08 to step 1712, node 3 '/
The value of KPRC for a / b / c 'is reduced by 1, and total_pa
th = 2 and total (j) = 2 are calculated. Next step 17
The process moves to step 1610 of FIG. 16 via 08. Here, i = 4, total (i) = 2, node (i) = node 2, j =
It is 5. In step 1631, since the directory '/ a / b / c / d' specified by j exists only in the node 5, total (j) = 1. In step 1601 total_pa
After th = 2 is calculated, the process again moves to step 1701 shown in FIG. 17 via step 1603. This time,
Step 1701, Step 1702, Step 170
All 8 are No, and the process moves to step 1610 in FIG. Here, i = 5, total (i) = 1, node (i) = node 4, j = 6, and the process ends via step 1611.

In this state, that is, the parameter value after executing the instruction (3) of the user 1 is (subpath = '/ a /
b ′, m-stage = 2, k-pass = 3).

[0081]

[Table 10]

Tables 11, 12, and 13 show the respective processes and the states thereof for the change instruction (4) of the user 2.

User 2 changes the sub-path from '/ a / b' to '
When changed to / ', in step 603 of FIG. 6, old_subp
at = '/ a / b', new_subpat = '/' in step 604
Tot_dirs_old = 3 and tot_dirs_new = 1 are set, and in step 605, tot_dirs_old = 3 and tot_dirs_new = 1 are compared. In step 608, reduce = TRUE, subpat = '/
a / b ′, j = 2, and in step 612
After setting tot_dirs = 3, the process proceeds to step 801 in FIG. 8 via step 701 in FIG. 7. In steps 801 to 807 of FIG. 8, '/ a / b'
And the SPRC value of '/ a' is decremented by 1, j = 4, and the process ends. The parameter value in this state is (sub path = '/ a / b', m-stage = 2, k-path = 3).

[0084]

[Table 11]

Table 12 shows the state after the processing of the m-stage processing unit is continued for (4).
If user 2 changes the m-stage value from 3 to 0,
In step 903 of FIG. 9, old_m_stage = 3, new_m_stage =
It is set to 0 and compared in step 904. old_m_st
age> new_m_stage, so in step 909 hops_to_
After setting reduce = 3 and tot_dirs = 5, the process moves to step 1301 shown in FIG.

Steps 1302 to 1 in FIG. 13
In the loop of 306, since the MSRC of the directory '/ a / b' corresponding to j = 3 is not larger than 0, the process proceeds from step 1304 to step 1307,
j = 2. In the next process, the MSRC value of '/ a' is decremented by 1, and the process ends via step 1313.

The parameter value in this state is (subpath = '
/ A / b ', m-stage = 2, k-pass = 3).

[0088]

[Table 12]

Table 13 shows the state after the process of the k-path setting unit is continued for (4). If user 2 changes the value of k-pass from 3 to 0, FIG.
Step 1403, old_k_path = 3, new_k_path =
0, k_path = 0 is set, and old_k_p is set in step 1405.
ath and new_k_path are compared. old_k_path> new_k_pat
Since it is h, in step 1407 path_to_reduce = 3,
reduce = TRUE, in step 1414 k_path = 1, tot_
dirs = 5, i = 1, node (i) = node 1, total (i) = 1, j = 2 in step 1415 are set, and in steps 1501 to 1512 of FIG. From the directory, subtract 1 from the value of its KPRC for all directories and the first directory that does not exist in node 1 is searched (1502). As a result, KPRC of '/ a' and '/ a / b' on node 1
These directories are deleted from node 1 since the value of is reduced to 0 and all RC = 0 (150).
9). Also, as the first directory, '/ a / b /
c'is searched.

Next, in step 1601 of FIG. 16, '/ a /
After calculating total_path = 3 between b'and '/ a / b / c', the step 1 shown in FIG.
Move to 701. Since node (i) = user node, the process proceeds to step 1708, and in the loop from step 1708 to step 1712, node 3 '/ a / b / c'
The value of KPRC of is reduced by one. At this time all RC
= 0, so in step 1711 the directory '/ a
/ B / c 'is deleted from node 3. Then total_path
= 2, total (j) = 2 is calculated, and FIG.
6 to step 1610. Where i = 4, total
(i) = 2, node (i) = node 2, j = 5. In step 1631, the directory specified by j '/ a / b /
Since c / d ′ exists only in the node 5, total (j) = 1. After total_path = 2 is calculated in step 1601, the process again moves to step 1701 shown in FIG. 17 via step 1603. At this time, since Step 1701 is No and Step 1702 is Yes, the KPRC value of the directory '/ a / b / c' of the node 4 is decremented by 1 in Step 1703. As a result, all RC = 0
Therefore, this directory is deleted from node 4. After that, in step 1706, total_path = 1, total
(i) = 1 is set. Next, the process proceeds to step 610 in FIG. 16 via steps 1702 and 1708. Here, i = 5, total (i) = 1, node (i) = node 4, j
= 6, the process ends via step 1611.

The parameter value in this state is (subpath = '
/ ', M-stage = 4, k-pass = 1), which is equal to the initial state.

[0092]

[Table 13]

As is apparent from the state in which the instructions (1) to (4) are followed, this apparatus can realize the copying of an appropriate directory dynamically satisfying the user's request without leaving a wasteful directory. .

In the present embodiment, the connection of the setting units is made up of the sub-path setting unit, the m-stage setting unit, and the k-path setting unit in this order, but the present invention is not limited to this order. It is also possible to realize in any combination.

[0095]

As described above, according to the present invention, in the name resolution in the distributed network environment, the problems concerning the scalability and the reliability in the prior art are solved,
It is possible to provide a name resolution device which is highly scalable and whose reliability can be dynamically set according to the needs of the user.

[Brief description of drawings]

FIG. 1 is a block diagram of a name resolution device according to an embodiment of the present invention.

FIG. 2 is a directory diagram of node 1 that satisfies subpath'a / b '.

FIG. 3 is a layout diagram of directories satisfying m-stage 2.

4A is a layout diagram of a directory of k-path 2; FIG. 4B is a layout diagram of a directory of k-path 3;

FIG. 5 is a schematic diagram of a directory used in an embodiment of the present invention.

FIG. 6 is a flowchart showing the processing of the sub-path setting unit in the embodiment of the present invention.

FIG. 7 is a flowchart showing the processing of the sub-path setting unit in the embodiment of the present invention.

FIG. 8 is a flowchart showing a process of a sub-path setting unit in the embodiment of the present invention.

FIG. 9 is a flowchart showing the processing of the m-stage setting unit in the embodiment of the present invention.

FIG. 10 is a flowchart showing the processing of the m-stage setting unit in the embodiment of the present invention.

FIG. 11 is a flowchart showing the processing of the m-stage setting unit in the embodiment of the present invention.

FIG. 12 is a flowchart showing the processing of the m-stage setting unit in the embodiment of the present invention.

FIG. 13 is a flowchart showing the processing of the m-stage setting unit in the embodiment of the present invention.

FIG. 14 is a flowchart showing the processing of the k-path setting unit in the embodiment of the present invention.

FIG. 15 is a flowchart showing the processing of the k-path setting unit in the embodiment of the present invention.

FIG. 16 is a flowchart showing the processing of the k-path setting unit in the embodiment of the present invention.

FIG. 17 is a flowchart showing the processing of the k-path setting unit in the embodiment of the present invention.

FIG. 18 is a schematic diagram of a distributed system.

FIG. 19 is a conceptual diagram showing a name resolution method using a single server in the related art.

FIG. 20 is a conceptual diagram showing a name resolution method using a distributed single server in the related art.

[Explanation of symbols]

 1 node 11 parameter setting unit 12 replica setting unit 13 sub-path setting unit 14 m-stage setting unit 15 k-path setting unit 201 node 1 31 node 1 32 node 99 33 node 8 50 reliability field 51 reference count field 181 node 182 node 183 node 184 network 191 name server 192 node 193 directory 194 node 195 node 196 node 197 network 201 directory subset 207 name server 208 name server 209 name server 2010 process 2011 process 2012 process

Claims (4)

[Claims] Claim: What is claimed is: 1. Parameter setting means for designating a sub-path which is a path name to be resolved at its own node without inquiring other nodes, and a reliability area for storing information on whether or not a directory provided in each directory is a copy. A name resolution device having subpath setting means for managing a directory according to a subpath specified by the parameter setting means based on a reference area for storing the number of times the directory is required to satisfy the condition specified by the parameter setting means. . 2. Parameter setting means for designating a maximum number of times of migration to another node required in a path for path name resolution, and reliability of storing information on whether or not a directory provided in each directory is a copy. Stage setting means for managing the directory according to the maximum number of transitions designated by the parameter setting means on the basis of a region and a reference area for storing the number of times the directory is required to satisfy the condition designated by the parameter setting means Name resolution device. 3. Parameter setting means for designating the minimum number of paths that can be taken between any two nodes other than terminal nodes among paths for path name resolution, and information as to whether or not the directory provided in each directory is a copy. Based on a reliability area for storing the number of times required to satisfy the definition specified by the parameter setting means, and a minimum number of nodes in the system and a route specified by the parameter setting means based on the reference area. A name resolution device having path setting means for managing directories according to the number. 4. A sub-path consisting of paths that can be resolved by one's own node without inquiring about other nodes, the maximum number of transitions to other nodes required in the path for path name resolution, and a path for path name resolution. Parameter setting means for designating the minimum number of routes that can be taken between any two nodes excluding the end node, a reliability area for storing information on whether or not a directory provided in each directory is a duplicate, and the parameter. A subpath setting means for managing a directory according to a subpath specified by the parameter setting means based on a reference area storing the number of times required to satisfy the definition specified by the setting means; the reliability area and the reference; A stage setting for managing the directory according to the maximum number of migrations designated by the parameter setting means based on the area Determining means, and path setting means for managing a directory according to the total number of nodes in the system and the minimum number of paths based on the information stored in the reliability area and the reference area. Name management device.