CN1331331C

Movatterモバイル変換

Info

Publication number: CN1331331C
Application number: CNB2004100373573A
Authority: CN
Inventors: 黄建华; 李祖鹏; 郭云飞
Original assignee: NATIONAL DIGITAL SWITCH SYSTEM ENGINEERING TECHNOLOGY RESEARCH CENTER
Current assignee: NATIONAL DIGITAL SWITCH SYSTEM ENGINEERING TECHNOLOGY RESEARCH CENTER
Priority date: 2004-04-27
Filing date: 2004-04-27
Publication date: 2007-08-08
Anticipated expiration: 2024-04-27
Also published as: CN1691619A

Abstract

The present invention discloses a method for realizing an ad hoc network, which mainly comprises the following steps that according to a physical topological structure of a network, the network is divided into ad hoc network groupings of different hierarchies, and the clusters of corresponding cluster levels, which correspond to the ad hoc network groupings of different hierarchies, are determined; each cluster corresponds to a hash loop of logical command space; when a network node dynamically joins in or quit the ad hoc network, a corresponding hash loop structure is dynamically adjusted to realize the reorganization of the network. In the present invention, the hash loop used for saving data and querying a route is established and realized on the basis of the physical topological structure of an Internet bottom layer, so the network adjacency and the network local property of the node can be fully utilized so as to make routing performance good and data querying efficiency high; all the advantages of the network routing protocol of a structured P2P covering layer are inherited by using a hash-type routing algorithm based on a DHT so as to ensure the extensibility of the network.

Description

Self-organizing network

Technical field

The present invention relates to Internet technical field, refer to a kind of self-organizing network that is applied in the Internet especially.

Background technology

Internet is a computer interactive network, claims inter-network again.It is a global huge computer network system, and tens thousand of the computer networks in the whole world, tens million of main frames couple together, and have comprised millions of information resources, provide information service to the whole world.Self-organization network technology then is a hot spot technology in NGN (next generation network) technical research field.In self-organizing network, the activity of each node need not manual intervention, they can fast automatic networking, quick-recovery and rebuild network soon when network topology changes, Fig. 1 is the time shaft schematic diagram of self-organization of network process, the self-organization of network process is divided into the netinit state, stable state and network dynamic change state, wherein the netinit state is network struction and the learning phase state when carrying out netinit, stable state is then finished the state in initial self-organizing stage for network, network dynamic change state then is because node motion, the state of network re-organized when node or link failure.Existing self-organizing network is generally based on mobile radio network, MANET (Mobile Ad hoc Network for example, wireless self-organization network), owing to do not possess the infrastructure that is similar to Internet in the self-organizing network, the network bottom layer structure is not considered in the network struction of therefore existing self-organizing network, only when changing, network topology starts network re-organized mechanism, the self-organization network technology scheme of the maturation of still in the Internet, not using at present.

On the other hand, computer equity Internet technology also is a research focus of present International Computer Network technical field.P2P (peer-to-peer network system) system's develop rapidly becomes one of most important applications system among the Internet, and the network traffics that current P2P system produces have surpassed the network traffics that the HTTP visit produces, and become the primary application that occupies the Internet bandwidth.

The P2P network architecture of using has two kinds of typical representatives at present, based on the centralized directory structure with based on the peer-to-peer network model of Distributed localization method, they are representative with Napster and Gnutella respectively, in the Napster model, the address information of all movable reciprocity machines and the directory information of shared resource thereof in the in store network of the high performance central server of a group.When needs were inquired about certain file, reciprocity chance was sent the file polling request to a central server, after central server is retrieved accordingly and inquired about, can return the reciprocity machine address information tabulation that meets search request.There are a lot of problems in this kind model because rely on central server, and its shortcoming mainly shows as follows: the paralysis of central server causes the collapse of whole network easily, and reliability and fail safe are lower.And, central directory server is safeguarded and the expense upgraded will sharply increase that required cost is too high along with the expansion of network size.

Another kind be with the Gnutella model be representative based on distributed peer-to-peer network model, overcome the shortcoming of the peer-to-peer network model of above-mentioned convergence directory structure, in the Gnutella model, do not have central server, information is shared in localizing objects equity machine or inquiry in this model, source equity machine etc. by with adjacent reciprocity machine between be connected and travel through the whole network system.Mode with diffusion when searching data is dispersed in message on the network, and this can cause spreading unchecked of message, also makes the extensibility of system to promote.

For this reason, (Structured Overlay Network, the P2P algorithm that SON) Routing Protocol such as CAN, Chord, Pastry and Tapestry proposed is suggested for improving the P2P network extensibility structured coverage.It improves the mode that mainly is to utilize hash (Hashing), computing becomes a key assignments (Key) with node with the data in the network, and deposit regular store data according to the network key assignments, also being about to each data key assignments deposits in and breathes out on the western NameSpace (Hash ring) along clockwise direction on the node of first node key assignments greater than this data key assignments, just can effectively finish searching and safeguarding of data by the relation of safeguarding this key assignments and node, and finish searching and locating data resource in the network by query messages being routed to the node that the target data key assignments deposits.But because these P2P computation schemas are not considered the real topology of Internet, even thereby two contiguous nodes but might be because the result of hash in the real topology, must just can obtain data through very long search path, with Chord is example, the survey showed that for network statistics, this system carries out node IP address to the mapping of node Id number (Identifier) by hash algorithm, caused two very contiguous in Hash ring nodes but might be in the real network topology wide apart; And 2 very contiguous points during the node of wide apart encircles through hash algorithm mapping may becoming Hash in real network.The problems referred to above greatly reduce search efficiency and the performance of P2P computation schema in real network is used, and for example cause 2 very contiguous points of physical distance, may can arrive the other side each other around a great circle in Internet.

Summary of the invention

The technical problem that the present invention solves provides the self-organizing network that a kind of routing performance is good, efficiency data query is high, with the performance of the existing self-organizing network of further improvement.

For addressing the above problem, self-organizing network of the present invention mainly comprises the steps:

A, according to the network physical topological structure network is divided into the self-organizing network cohort of different levels;

B, determine the aggregation of the corresponding gathering progression of corresponding described different levels self-organizing network cohort, wherein the corresponding logical naming Hash loop of each aggregation;

C, when network node dynamically adds or withdraws from self-organizing network, dynamically adjust and breathe out western loop structure accordingly to realize the network re-organized.

Wherein, step a specifically comprises:

Determine the self-organizing network cohort number of plies according to actual scale of network and physical topological structure;

The network node that physical distance is nearer is divided into same self-organizing network cohort, and adds the sequencing of self-organizing network and the hierarchical agent that physical location is determined this self-organizing network cohort according to this network node;

Member node that the hierarchical agent and the cohort member thereof of identical level is divided into the last layer cohort and the hierarchical agent of determining corresponding level, if be divided into self-organizing network top layer cohort and determined that the hierarchical agent of corresponding top layer cohort then divides end, otherwise continue to divide.

Wherein, step b specifically comprises:

B1, each hierarchical agent and cohort member thereof are defined as an aggregation;

The logical naming Hash loop of b2, corresponding each aggregation of generation.

Wherein, step b2 specifically comprises:

Adopt to breathe out western algorithm with the tag maps of each network node in the self-organizing network binary sequence NID that to become a length be the M position, and with its unique this network node of distributing to, equally the sign that needs in the self-organizing network to store data is breathed out western computing, with its binary sequence KID that to be mapped to a length be the M position;

The NID of the network node of forming according to each aggregation generates the corresponding western loop of breathing out.

Wherein, step c specifically comprises:

West, the Kazakhstan loop of c1, corresponding each aggregation is set to corresponding loopful territory;

C2, described loopful territory is divided into the privately owned ring territory of each network node in the corresponding aggregation;

C3, the hierarchical routing table of corresponding each network node is set according to the privately owned ring territory of the gathering progression of aggregation and each network node;

C4, when network node adds or withdraws from self-organizing network, dynamically adjust the privately owned ring territory and the hierarchical routing table of respective nodes, and realize routing update.

Wherein, step c4 network node adding self-organizing network specifically comprises:

System is that the new network node M that adds distributes a node NID at random;

The new network node M that adds selects ownership hierarchical agent HA as its guiding node, and adds west, the Kazakhstan loop of this hierarchical agent HA;

Hierarchical agent HA Network Search node M is at the descendant node S that breathes out on the western loop;

This descendant node S is divided into two parts according to the privately owned ring territory of the big young pathbreaker's this section point of node NID of network node M, keep network node M to the privately owned ring territory of the ring domain space between the subsequent node S as subsequent node S, and with the node P that continues before the descendant node S to the ring domain space between the network node M as the new privately owned ring territory of adding network node M;

Network node M is by its descendant node S obtain to continue before it information of node P, network node M sends the message that joins request respectively to P and S respectively then, after S and P receive message, with upgrade respectively oneself before continue and descendant node, wherein, S is updated to M with continuing before oneself, and P is then the follow-up M that is updated to of oneself;

M realizes the initialization to the hierarchical routing table by its descendant node S searches each the hierarchical routing table list item correspondence of oneself successively in breathing out western loop next-hop node;

The descendant node S of M will transfer to new node M according to the data key assignments that the privately owned ring territory of repartitioning will belong to new node;

Start the routing update process, the hierarchical routing table of all other nodes in the update system.

Wherein, step c4 network node withdraws from self-organizing network and specifically comprises:

Withdraw from node Q and at first leave request message with one of the node P transmission that before continues to its descendant node S, after S and P receive message, upgrade respectively oneself before continue and descendant node, wherein, S be updated to continuing before oneself Q before the node P that continues, P is then the follow-up descendant node S that is updated to Q of oneself;

Node S will upgrade the privately owned ring territory of oneself, the privately owned ring territory of network node Q be integrated with the privately owned ring territory of this node S;

Node S will all transfer to S according to the data key assignments that the privately owned ring territory of repartitioning will belong to node Q;

Wherein, adopt event-triggered routing update mechanism to realize routing update, start route maintenance and renewal process automatically, when node adds and node normally logs off by the source of triggering trigger network, send in network by the application layer program and to withdraw from message, this withdraws from message as the triggering source; When node withdraws from unusually, inform other node by " discovery-broadcasting " mechanism, and serve as the triggering source by this broadcast.

In addition, also comprise:

In the bottom aggregation, carry out the data item backup, according to the repetition rate size, the data item occurrence that has a part of routing procedure of crossing over the bottom gathering of the backup selected to return, and deposit rule according to the network data key assignments it is left in the bottom aggregation on the corresponding home node, when searching the identical data key assignments next time, routing inquiry in the bottom aggregation at this home node place.

In addition, also comprise:

Continue before the increase and the descendant node backup sheet, back up as descendant node breathing out the node of R item node NID the most contiguous on the western loop greater than this node, and R item NID less than the node of this node as before continuing the node backup, when the descendant node of this node collapses, then use the interim descendant node of preserving in the descendant node backup sheet of the second follow-up conduct oneself to breathe out the complete of western loop with maintenance; Equally, when the node that continues before this node collapses suddenly, then use preserve in the adjacency list second before continue and continue node to keep breathing out the complete of western loop before interim as own.

Compared with prior art, the present invention has the following advantages:

1, the present invention is divided into network according to the network physical topological structure self-organizing network cohort of different levels, determine the logical naming Hash loop of corresponding described different levels self-organizing network cohort then, and then realize that by the western loop structure in the described Kazakhstan of dynamic adjustment network node dynamically adds or withdraws from self-organizing network, thereby realize the dynamic network process of self-organization of self-organizing network, owing to set up and realized being used for west, the Kazakhstan loop of data preservation and routing inquiry based on the Internet bottom physical topological structure, can make full use of the network proximity and the network locality characteristic of node, make the routing performance of network better, efficiency data query is higher;

2, further, the present invention is by using the hash formula routing algorithm based on the hierarchical routing table, all advantages of structural P 2 P algorithm network routing protocol have been inherited, solved present main flow P2P system (as Napster, the Gnutella) problem that extensibility is low, and creatively the P2P network technology is applied to self-organizing network structure and route technology field, thereby guaranteed the extensibility of self-organizing network.

Description of drawings

Fig. 1 is the time shaft schematic diagram of prior art self-organization of network process;

Fig. 2 is the network topology layer tree type architectural schematic that self-organizing network of the present invention adopts;

Fig. 3 is the DHT network inquiry layer architecture schematic diagram that self-organizing network of the present invention adopts;

Fig. 4 is the network topology layer cohort partition process schematic diagram that self-organizing network of the present invention adopts;

Fig. 5 is the hierarchical routing list structure schematic diagram that self-organizing network of the present invention adopts;

Fig. 6 is the specific embodiment schematic diagram that has only one deck to assemble in the self-organizing network of the present invention.

Embodiment

The self-organizing network that the present invention realizes is a consolidated entity based on the different framework cover layers of two-stage (Overlay).Define respectively among the present invention this two-stage cover layer be respectively the network topology layer (NetworkTopology Layer, NTL) and the network inquiry layer (Network Discovery Layer, NDL).Wherein, network topology layer (NTL) realizes that mainly the gathering colony (Cluster) of physical topology Network Based divides and tree type architecture constructing function; Main equity point route and the positioning function that realizes based on DHT (hierarchical routing table) algorithm of network inquiry layer (NDL) describes respectively below.

(1). network topology layer (NTL)

The network topology layer mainly comprises two basic modules among the present invention: overall registrar and hierarchical agent.

Overall situation registrar (Global Register Server, GRS): the function class of GRS is a global data base like DNS (Domain Name System, domain name system) root server, mainly is responsible for the IP address of storage and maintenance different brackets HA;

Hierarchical agent (Hierarchical Agent, HA): HA serves as each core of assembling colony (Cluster), what the present invention adopted is complete distributed and self-organizing structures, and the HA major function is to provide guide effect for newly added node initialization routing table.

The self-organizing network that the present invention realizes can be divided into the self-organizing network cohort of different brackets according to the actual scale of network and physical topological structure, in each level of self-organizing network, a large amount of HA are arranged all, each HA itself also is the common reciprocity point of in the network (or being called node), they may be positioned at the diverse location in the world, in the network model that the present invention proposes, hierarchical agent (the HA Level 1 that the nearer equity of physical distance is named a person for a particular job and is merged in groups (i.e. self-organizing network cohort) and is connected to the first order, be called for short HA1), by its unified management, whether wherein said hierarchical agent can add the sequencing of network and physical location and then decision thereof based on it by ordinary node and upgrade and become a hierarchical agent;

Identical principle, the nearer HA1 of physical distance will be merged in groups and be connected to partial hierarchical agent (HA Level 2 is called for short HA2), by its unified management, hierarchical agent definite same as described above, the rest may be inferred, divides up to the cohort of top hierarchical agent and management thereof to finish.

With reference to figure 2, Fig. 2 has illustrated a kind of NTL tree type architecture of Three Estate, and the HA1 of the first order assembles down a plurality of reciprocity machines, assembles the reciprocity machine that a plurality of HA1 and gathering thereof are arranged under the HA2 of the second layer respectively, equally, under the 3rd layer HA3, assemble the reciprocity machine that three HA2 and gathering thereof are arranged.

Illustrate NTL layer cohort partition process below, the schematic diagram referring to Fig. 4 cohort partition process of the present invention mainly comprises the steps:

HA all in A1, the network send registration message (Register Message) to GRS, carry out identity registration;

B1, when a new node wishes to add network, at first to get in touch, and obtain this node address information with a known member node in the network, this node will serve as the guiding node (Bootstrap Node) of newly added node;

C1, new node calculate the physical network distance of Bootstrap node, and the simplest method can be used Ping message.If the physical distance of calculating is less than the threshold value (Threshold) of default, then new node will send message and join in the residing gathering of the Bootstrap node colony end of cohort partition process by the ownership HA to the Bootstrap node; Otherwise, enter D1;

D1, new node will obtain the address information of all first order hierarchical agent HAi (i=1) from global server GRS, and will calculate the physical network distance of each HAi respectively.If the physical network that calculates distance is less than the threshold T (T is a system parameters, is provided with according to concrete network size) of default, then new node will join in this HAi subordinate's the gathering colony, and the cohort partition process finishes; Otherwise, enter E1;

E1, new node will obtain the address information of the upper level hierarchical agent HA (i+1) of current measurement HAi from global server GRS, and will calculate the physical network distance of each HA (i+1) respectively.If the physical network that calculates distance is less than the threshold T of default, then new node will join in this HA (i+1) subordinate's the gathering colony, and become its next stage hierarchical agent HAi automatically, and register in GRS, and the cohort partition process finishes; Otherwise, repeat the E process, till adding certain one-level HA or arriving top HA (be i=H-1, H is the height of NTL tree).

(2). network inquiry layer (NDL)

The network inquiry layer mainly is based upon on network topology layer (NTL) basis among the present invention, system will realize route to message by setting up network inquiry layer (NDL), in NDL, defined aggregation levels (Cluster Level), each HA of NTL layer and subordinate's equity thereof are named a person for a particular job and are divided into a gathering of NDL layer, the level of this gathering is corresponding to the rank of this HA, for example, certain HA1 and all child nodes thereof will constitute a CL_0 level and assemble (Cluster Level 0), and certain HA2 and all child nodes thereof will constitute a CL_1 level gathering (Cluster Level 1), and the rest may be inferred.Being defined as follows of aggregation levels:

The n level is assembled (Cluster Level k is called for short CLk): the different brackets in the corresponding self-organizing network is assembled colony.Wherein, the sub reciprocity machine under each HA1 will be formed zero level and assemble colony (ClusterLevel 0, CL0); All HA1 will form a first order gathering colony, and (Cluster Level 1, CL1), the rest may be inferred.

The full gathering (Full Cluster is called for short FC): all nodes in the corresponding self-organizing network.

Corresponding above-mentioned aggregation, the present invention generates the logical naming Hash loop of corresponding each aggregation according to the western algorithm in distributed Kazakhstan, like this according to the method for foregoing self-organizing network classification, suppose that current NTL tree height is H, then can adopt following flow process in NDL, to inquire about:

A2, for a node among the CLi, the inquiry that its is initiated is at first carried out in the ring of the Hash in CLi, if find destination node and corresponding data key value Key, then returns response message and gives source node, query script finishes, otherwise enters B2.

B2, this node will assemble query expansion in CL (i+1) to (i+1) level under its ownership HAi and carry out, if find destination node and corresponding data key value Key, then return response message and will give source node, and query script finishes, otherwise enters C2.

If FC (be i＜(H-1)) is assembled in C2 no show still entirely, return B after then i being added 1, query script finishes, otherwise returns the inquiry failure.

How to set up NDL network inquiry layer with the specific embodiment explanation below.

Present embodiment adopts based on the western algorithm in distributed Kazakhstan of Consistent Hashing the sign (as IP address, domain name etc.) of each node in the network is mapped to the binary sequence NID that a length is M position (bit), and with its unique this node of distributing to; The sign (filename, ObjectId etc.) that needs to store data in the system is breathed out western computing, it is mapped to the binary sequence KID that a length is M position (bit) (Key Id), wherein M value size need satisfy N≤2^M(network node adds up to N).The NID of node will be used for specifying the position of this node in the Hash ring like this.When node added self-organizing network for the first time, system will be randomly for it distributes a NID, and the NID span is 0～2^M-1.The corresponding binary sequence thatusefulness 0,1 character string is represented of each NID, the pairing numerical value of the NID of each node is mutually different, for the NID that a total length is M, its pairing numerical value is:

(NID) = Σ_{r = 1}^{M} {NID}_{i} \times 2^{r}

Like this, for the aggregation of above-mentioned division, the NID of the network node that will form according to each aggregation generates the corresponding western loop of breathing out.

(Global Ring Zone is GRZ) with privately owned ring territory (Individual Ring Zone, notion IRZ) also to have introduced the loopful territory in this routing algorithm.(GRZ) is [0,2 in the loopful territory^M-1) the pairing numerical space of 0,1 character string of all between (M is generally 128).Each node in the system dynamically is divided into GRZ independently privately owned one by one subspace, and with the privately owned ring territory (IRZ) of this subspace as oneself, IRZ can be expressed as (NID_Predecessor, NID), wherein to be this node encircle the NID of the node of going forward to continue at Hash to NID to be system the be ID value that this node distributes, NID_Predecessor.

According to the definition in above-mentioned loopful territory and privately owned ring territory, west, Kazakhstan loop that can corresponding each aggregation among the present invention is set to corresponding loopful territory; Then described loopful territory is divided into the privately owned ring territory of each network node in the corresponding aggregation.

Further, each node among the present invention also will be preserved H hierarchical routing table (HierarchicalRouting Table, HRT), wherein H will be the self-organized network topology layer height.Suppose that the i level has n node in assembling, then the corresponding i level HRT size safeguarded of each child node is O (log n) magnitude.At first provide a node hierarchy routing table related definition under the NameSpace of M position below:

Current gathering progression (Current Cluster Level, CCL): the gathering progression under the hierarchical routing table lower node among the NTL, wherein 1≤k≤H;

Before the node (Predecessor) that continues: first node that this node runs on the Hash ring in the counterclockwise direction;

Descendant node (Successor): first node that this node runs on the Hash ring along clockwise direction;

K item route ring territory starting point (HRTEntry[K] .start): K route table items institute cover ring domain space original position, wherein

HRTEntry[K].start＝(n+2^k-1)mod2^M 1≤K≤M (3)

Ring domain space scope (Next Hop Ring Interval, NRI): the ring domain space range size that route table items K is covered, wherein

NRI[k]＝[HRTEntry[K].start，HRTEntry[K+1].start) 1≤K≤M (4)

(Next Hop IRZ, NIRZ): the privately owned ring domain space of first active node G along clockwise direction in ring domain space scope NRI, promptly G satisfies the privately owned ring domain space of next-hop node

HRTEntry[K].start∈IRZ(G) 1≤K≤M (5)

The substance of hierarchical routing table (HRT) has: current topological layer is assembled progression (CCL), K item route ring territory starting point (HRTEntry[K] .start), the privately owned ring domain space of next-hop node (NIRZ), wherein, K is the routing table sequence number, and the structure of hierarchical routing table is referring to shown in Figure 5.

The above-mentioned purpose of introducing privately owned ring territory in self-organizing network is, take the routing table that size can dynamic change to compare flexible more with the routing table of taking fixed size, when node adds the fashionable random-number distribution that random function produced that adopts enough evenly the time, node can come the total number of node in the estimating system according to its IRZ size, total linear inverse relation of interstitial content in its IRZ size and the system in theory, promptly when node IRZ in the network distributes enough evenly, the total N=O (GRZ/IRZ) of system node.In addition, when the query aim node, query script directly just can judge effectively by the scope that compares KID value and destination node IRZ whether destination node arrives, thereby has simplified query script, describes with specific embodiment below.

With reference to figure 6, Fig. 6 is a self-organizing network that has only one-level to assemble, and the Hash loop that constitutes the NDL layer in this self-organizing network comprises 4 node A, B, C and D, wherein

The routing table of Node B under the first order is assembled be as shown in Table 1:

Table one

Sequence number K	CC L	HRTE ntry[K ].start	NIRZ
Sequence number K	CC L	HRTE ntry[K ].start	NIRZ	1	1	100	C＝(011,100]
2	1	101	D＝(100,000]	1	1	100	C＝(011,100]
2	1	101	D＝(100,000]	3	1	111	D＝(100,000)

The routing table of node D under the first order is assembled be as shown in Table 2:

Table two

Sequence number K	CC L	HRTE ntry[K ].start	NIRZ
Sequence number K	CC L	HRTE ntry[K ].start	NIRZ	1	1	001	A＝(000,001]
2	1	010	B＝(001,011]	1	1	001	A＝(000,001]
2	1	010	B＝(001,011]	3	1	100	C＝(011,100)

If Node B is initiated the data key assignments inquiry to KID=001, because 001 ∈ [HRTEntry[3] is .start, HRTEntry[1] .start], i.e. [111,100] (annotating: circulates in this zone) is so directly navigate to node D, because IRZ (D)=(100,000), B can judge this data key assignments not on node D, therefore needs to continue the hierarchical routing table of inquiry D; Hierarchical routing table according to D, because 001 ∈ [HRTEntry[1] is .start, HRTEntry[2] .start], i.e. [001,010], query script will continue to navigate to node A, because the IRZ=(000,001) of node A, then B is by relatively KID and IRZ can find KID ∈ IRZ (D), therefore directly decision node A is destination node, and need not message is continued to transmit.

When network size enlarges, because the node number increases, one of hierarchical routing table is jumped and may be crossed over the most nearly 2M/2 node, thereby can directly judge whether destination node and whether need query messages is continued to transmit of present node, thereby greatly improve search efficiency by IRZ and KID relation relatively.

For a system, satisfy relation of plane down between the IRZ of its each node with N node:

IRZ₁ U IRZ₂ U IRZ₃...U IRZN＝GRZ

IRZ_i I IRZ_j＝φ i≠j，1≤i，j≤N (2)

All nodes connect and compose loopful territory GRZ by its privately owned ring domain space IRZ in the network.Adopt this simple node adjacency relation, each node only need be preserved its follow-up nodal information, and the communication between the node can realize by the mode of passing before descendant node carries out message.Though the method for passing before this message is simple, but efficient is very low, because two nodes in the network are jumped (N is a node number in the network) in order to find the other side need pass through O (N), source node may need message could be arrived destination node around ring transmission one circle under the worst case.Just be based on this reason, in order to quicken query script and raising search efficiency, the present invention has introduced hierarchical routing table HRT for each node, and the route finding process that the present invention is adopted is described below below:

A3, when certain node M need be initiated routing inquiry (or receive through transmitting route messages), it will at first check (or extracting in the message) data query key assignments D, and data key assignments D compared with the privately owned ring domain space (IRZ) of this node, if D ∈ is IRZ, then route finding process stops, M structure and echo reply message; If D  is IRZ, then enter B3;

B3, node M will be assembled the progression size according to hierarchical routing table (HRT), data query key assignments D step by step, in each grade HRT, M compares data query key assignments D successively with the hierarchical routing list item, seeking the privately owned ring domain space of next-hop node (NIRZ) comprises the route table items of data key assignments D and forwards the packet to corresponding next-hop node, each transmission of message all will be selected NIRZ and the pairing next-hop node of the immediate route table items of data key assignments D in route table items, and message sent to this node, this node is passed before receiving and proceeding according to above-mentioned rule equally after the message; If the routing inquiry failure at current rank HRT then enters higher leveled HRT, the rest may be inferred.

If the C3 route finding process has arrived highest HRT (being CCL=H-1), and does not still inquire the destination node that comprises data query key assignments D, then route finding process finishes, and returns the inquiry failed message.

Below the dynamic adding of node and the process that withdraws from self-organizing network are described.

In order to support the self-organizing network characteristic, the self-organizing network that the present invention realizes also must support node dynamically enters at any time and logs off.Because adopting hash algorithm is that each node distributes a unique identification NID in the self-organizing network, and divides its privately owned ring domain space (IRZ).When a new node will add system, system will the IRZ of certain member node comes to distribute a new IRZ for this node on the Hash ring territory by cutting apart; When a node will log off, system will merge the IRZ of this node and certain member node of system to reclaim this ring domain space.

The following introduction earlier realizes that node dynamically adds the process of self-organizing network, and flow process is as follows:

A4, new node M at first divide according to above-mentioned cohort and select its ownership HA;

A member node H in B4, the M selective system is as its guiding node (Bootstrap Node), and in native system, M will choose its ownership HA as guiding node under the default situations.Because what the Hash ring adopted among the present invention is the clockwise direction inquiry mechanism, therefore node M will find its descendant node S (S=Successor (M)) on the Hash ring by guiding node H, this descendant node S is then according to the big young pathbreaker's of NID oneself of M IRZ ((NID (S.Predecessor), NID (S))) be divided into two parts, keep (NID (M), NID (S)) that part ring territory at place is as the privately owned ring territory of this node, then with the IRZ of another part (NID (S.Predecessor), NID (M)) ring territory as newly added node M.

C4, M are by its descendant node S obtain to continue before it information of node P (P=Predecessor (S)).M sends the message that joins request to P and S respectively then, after S and P receive message, with upgrade respectively oneself before continue and descendant node, wherein, S is updated to M with continuing before oneself, and P is then the follow-up M that is updated to of oneself, like this, the integrality of Hash ring is guaranteed.

D4, M search each own hierarchical routing table list item (HRTEntry) to deserved next-hop node successively by its descendant node S in Hash ring, realization is to the initialization of hierarchical routing table (HRT).

The descendant node S of E4, M will transfer to new node M according to the data key value Key that the IRZ that repartitions should belong to new node.

F4, system start-up routing update (Route Update) process (hereinafter will describe in detail), the routing table of all other nodes (HRT) in the update system makes its variation that can adapt to network configuration, and whole network is restrained again.

In addition, at the height dynamic characteristic of self-organizing network, what self-organizing network of the present invention also must support node dynamically leaves.The detailed process that node normally withdraws from self-organizing network is described below:

A5, node Q at first to its descendant node S and before the node P that continues send one and leave request message, after S and P receive message, with upgrade respectively oneself before continue and descendant node, wherein, S be updated to continuing before oneself Q before continue (node P), P is then follow-up follow-up (the node S) that is updated to Q of oneself.So far, the integrality of Hash ring is guaranteed.

B5, node S will upgrade the IRZ of oneself, and promptly the IRZ to node Q merges, and the IRZ of Q is (NID (P), NID (Q)) before merging, and the IRZ of S is (NID (Q), NID (S)), and after merging finishes, the IRZ of S will become (NID (P), NID (S)).

C5, node S will all transfer to S according to the data key value Key that the IRZ that repartitions will belong to node Q.

D5, system start-up routing update process, the hierarchical routing table (HRT) of all other nodes makes its variation that can adapt to network configuration in the update system, and whole network is restrained again.

The following describes and how to realize routing update.

For self-organizing network, routing update mechanism is a kind of automatic Restoration Mechanism that routing algorithm starts, its major function is to add owing to some nodes in network or when reason such as withdrawing from and causing network topology to change, the hierarchical routing table (HRT) of all associated nodes in the update system, make its variation that can adapt to network configuration, and make the convergence again rapidly of whole network.Routing update mechanism at present commonly used adopts usually is event-triggered, periodic and routing update mode that both combine.For large scale network, periodically routing update mechanism needs cost higher cost (as bandwidth, power supply, CPU disposal ability etc.) so that routing table can be got caught up in the current network changes of topology structure, but the routing table content that the topological structure of dynamic change may make high cost obtain again becomes invalid information, especially when network topology changes at a high speed, whole system will be in not convergence state all the time.Though this mode has directly guaranteed maintenance costs and has been proportional to the routing table size that only just feasible when routing table is little, in case routing table reaches certain scale, its expense can't be born.(for example, for the routing table that contains 10,000 list items, if surveyed once in per 50 seconds, then per second need send 200 message).Therefore, consider the height dynamic characteristic of self-organizing network, the present invention adopts event-triggered routing update mechanism.With regard to routing update triggered the source, when node adding and node normally logged off (normally closing the P2P program as the user), this node can send by application layer program interdependent node in network withdraw from message, and this withdraws from message and triggers the source exactly; And when node withdrawed from (going offline or deadlock etc. as node) unusually under without any the tendency situation, other node was generally informed by " discovery-broadcasting " mechanism by system, and at this moment this broadcast is just served as the triggering source.At withdrawing from unusually of node absence of aura, whether the node that must regularly continue before it of each node in the network sends KeepAlive message and survives to survey this node, node withdraws from unusually in case continue before finding, then starts the routing update process by this descendant node that withdraws from node unusually.

Routing update process with new node adding system describes below:

A6, routing update process are by Event triggered, initiate by newly added node M, renewal process will take to recall the mode of (retrieval), promptly from current triggering node M, counterclockwise upgrade one by one along Hash ring, and find successively and upgrade associated nodes according to the order i of hierarchical routing table list item (HRTEntry), that recalls is spaced apart 2i-1 at every turn, i=1,2..M.

B6, the routing update process that adding triggers for new node, when dating back to i node, the next-hop node NID value of i route table items correspondence of this node will be searched, if current NID value is greater than the NID of newly added node, then use NID (M) to replace current list item value, enter C, otherwise continue to recall the i+1 hop node.

C6, recall current more new node before the node that continues, and search the next-hop node NID value of i list item correspondence of this node, if current NID value is greater than the NID of newly added node, then use NID (M) to replace current list item value, node continues before continuing to recall last one, otherwise recall the i+1 hop node up to as i=M the time, the routing update process finishes.

The routing update process that logs off of node is similar substantially with the routing update process that node adds system in addition, and difference has 2 points: the routing update process that (1) node logs off is to be initiated by the descendant node S (S=Successor (Q)) that withdraws from node Q or withdraw from node; (2) the node routing update process that withdraws from triggering also adopts the method for recalling to upgrade the routing table of other nodes, but in the trace-back process, only search whether next jumping NID value of recalling node route list item correspondence is the NID that withdraws from node, be NID (Q), if, then with the current list item value of follow-up replacement that withdraws from node.

For making self-organizing network transmission of the present invention rapider faster, also take further routing optimality measure, specifically describe as follows:

A. data item back mechanism (Data Item Replication)

The purpose that the present invention proposes cohort division and hierarchical structure is in order to take into full account meshed network propinquity feature (Network Proximity Character), the method node that physical distance is nearer that hope is divided by cohort is classified as one group, to guarantee that the routing procedure between adjacent node is all finished in cohort inside in the network, thereby Routing Protocol problem such as Chord have been avoided, the problem includes: (Detouring) problem that detours has reduced system's route time expense and reduced the transmission message number.

But in real network, still there is the routing-events of a lot of leap cohorts to take place.Suppose to exist one 3 grades classification network W, CL1 is certain campus local area network (LAN) net (LAN), CL2 is this university metropolitan area network of living in (MAN), CL3 is a city more senior Wide Area Network of living in (WAN), though the ratio at the inner generation of CL1 level campus network message communicating is very big, but still has the message route of significant proportion must pass through CL2 level network even CL3 level network.Statistics shows that the repetition rate of data query process is very high under the particular subnet, and this is because there be high popular node and the hot information of some rates of people logging in the network.The route matrix that adopts with regard to the present invention all needs to enter into CL2 level even CL3 level Hash ring territory if the CL1 level is assembled the same key assignments of the each inquiry of lower node itself, then will cause bigger route time expense.

At this problem, repeat to stride the time overhead that grade routing procedure causes for reducing node, can assemble the mechanism of carrying out the data item backup in (being CL1 level ring territory) at bottom, its basic fundamental measure is exactly according to the repetition rate size, have and select a backup part to cross over the data item occurrence (DataItem) that CL1 level routing procedure returns, and deposit rule according to the data key assignments of system definition and leave it in CL1 and assemble down on the corresponding home node.Like this, when searching identical data key assignments, routing procedure just can be finished in the CL1 level is assembled, and does not need to enter into more higher leveled network inquiry layer, thereby has improved router efficiency greatly next time.Need to prove, though improving router efficiency by the data item back mechanism is to be based upon to increase on the node storage overhead basis, but in fact system's backed up data item on CL1 collection node is not the real data object, and only be a data item occurrence (DataItem) of corresponding certain data object memory address, promptly therefore the IP address of Cha Xun data key assignments and destination node can not increase too much storage overhead to node.

B. loop keeps mechanism (Hash Ring Preserving)

For the distributed routing protocol based on DHT, how to keep Hash loop integrality when network topology structure changes is a very crucial problem.Hash loop integrality is a necessary condition of guaranteeing that whole network route discovery and route maintenance procedure are normally carried out, and the imperfect network that will cause of loop is in not convergence state.Though native system provides the routing update mechanism at network topology change, but in the dynamic self-organization network, the frequent adding of node or withdraw from still might cause not finishing as yet in system's routing update data key assignments query manipulation has just taken place, and the imperfect of Hash loop will cause inquiry to interrupt or failure.

At this problem, the present invention has introduced loop and has kept mechanism, the technical measures of taking mainly are to continue and the descendant node backup sheet before increasing, R item NID the most contiguous on the Hash ring is backed up as descendant node greater than the node of this node, and R item NID less than the node of this node as before continuing the node backup, and set R=O (log N).In case the descendant node of this node collapse just uses preserve in the descendant node backup sheet second follow-up (second NID is greater than the node of this node) as own interim descendant node, to keep the complete of Hash loop immediately; Equally, the node that continues before this node collapses suddenly, then use preserve in the adjacency list second before continue (second NID is less than the node of this node) as the node that continues before own interim, to keep the complete of Hash loop.Therefore in native system, only when continuing before the R item backup corresponding in the node backup sheet and descendant node when collapsing simultaneously, the situation that the Hash loop just may occur interrupting, and this probability is very little, the probability of supposing each backup node collapse is 1/2, then P (R backup node collapses simultaneously)=O (1/N).

To sum up, main feature of the present invention is in conjunction with self-organization network technology and P2P technology.Each user node in self-organizing network all has both independent route and host function, there is not a network center control point, status between the user node is an equality, therefore self-organizing network itself just has reciprocity architected features, on the other hand, the network routing protocol of self-organizing network adopts distributed control mode usually, has very strong robustness and survivability.Therefore, on Internet physical topology basis, set up a virtual topological structure that is called P2P cover layer network, can set up a self-organizing network effectively, and have the following advantages based on Internet by using the P2P computation schema:

Guarantee the property obtained of data resource in the network, promptly as long as data resource is present in the network, just necessarily can be found;

Internet resources are inquired about complexity be controlled to be O (logN);

Effectively realize Network Load Balance, promptly the data key assignments in the network is assigned on the network node in approaching average mode, thereby makes each node equilibrium share network service and storage burden;

Effectively support the self-organizing network characteristic, promptly support node dynamically adds and exits network; When node failure or when going offline, P2P cover layer network will start automatic Restoration Mechanism, and network is restrained again.

The above only is a preferred implementation of the present invention, does not constitute the qualification to protection range of the present invention.Any any modification of being done within the spirit and principles in the present invention, be equal to and replace and improvement etc., all should be included within the claim protection range of the present invention.