Background technology
In recent years, content class service became the main flow of Internet service, and content class service generally comprises internet television, IPTV, mobile TV, file download, web page browsing, Web2.0 etc.
For content class service, user's request content and the process of obtaining content can be abstracted into flow process shown in Figure 1.
Fig. 1 is user's request content and obtain the flow chart of content in existing content class service.
As shown in Figure 1, this flow process comprises following step:
Step 101: the content requests that receives the user.
Step 102: a plurality of positional informations of storing content, the node with content positioning function cooperatively interact, and search the node address of having stored the content that the user asks.
Step 103: return to the node address of having stored the content that the user asks.
Step 104: according to the node request content of the address of returning to memory contents.
Step 105: the node of memory contents sends content to the user.
Point-to-point (Peer-to-peer, P2P) system relies on it to support large-scale application, has the characteristics such as enhanced scalability, load balancing, in the system of content class service, especially in file-sharing and information search system, obtains a wide range of applications.
In fairly large P2P shared file system, the stock number that need to carry out index and location is larger, and user's scale is also larger, so centralized LIST SERVER (tracker) is in the situation that a large number of users request is easy to occur "bottleneck".Tracker wherein is the positional information that records content, searches the node of content memory node list (peerlist) for the user.
The content locate mode that most of P2P networks are taked is based on the content positioning method of dynamic Hash table (Distributed Hash Table, DHT).Based on the content positioning method of DHT, can effectively content indexing be distributed to a plurality of nodes in network, simultaneously user's content Location Request is distributed to a plurality of nodes and effectively carries out load balancing.
In the shared file system of P2P, the process of content location comprises above-mentioned steps 101 to step 103, and at the P2P network based on DHT, the node in DHT overlay has been stored the positional information of content, the node with content positioning function exactly.
The below is to come concrete grammar and the process of description location as example based on the content positioning method in the P2P network of DHT.
At first be that each node in network distributes virtual address (VID) based on the P2P network of DHT, each node maintenance one sub spaces, each client is responsible for a route among a small circle, and is responsible for storage sub-fraction data, thereby realizes addressing and the storage of whole DHT network.
In the P2P network based on DHT, data are with the form of keyword and keyword value, and namely the form with (KEY, Value) is stored in node.Wherein, keyword (KEY) is used for representing the available shared content of node, and this keyword generally comes from filename or the content itself of content, by a hash function H, converts KEY to a cryptographic Hash H (KEY) and comes sign content.The memory location that keyword value (Value) has been pointed out content.
Wherein, filename or content itself according to content, obtain the keyword KEY of this content, this keyword KEY is converted to cryptographic Hash H (KEY), utilize this cryptographic Hash H (KEY) sign content, because cryptographic Hash H (KEY) is a structureless character string, therefore be called as the flattening sign of content.
Based on the P2P network strict difinition of DHT the topological structure that connects of network, each file must be placed on certain position in pre-specified KEY space, can guarantee like this to search for step number and be in some levels.Different DHT algorithms has determined the logical topology of P2P network, and such as CAN is exactly a N gt, and CHORD is a ring topology, and TAPESTRY is a netted topology.
Network based its topological structure of P2P, when content distributed storage information, with (KEY, Value) two tuples are published to the node that has with cryptographic Hash H (KEY) close address and get on, when content was located, the cryptographic Hash H (KEY) of the content of location, obtained two tuple (KEY to the node close with this cryptographic Hash H (KEY) as required, Value), thus obtain fast the memory location of content.
Fig. 2 is based on the content positioning flow figure in the P2P network of DHT.
As shown in Figure 2, this flow process comprises:
Step 201 receives based on the arbitrary node of the P2P network of DHT the query word that the user proposes, and this query word is generally the keyword KEY of institute's request content.
Step 202 after each node is received query word, checks the local contents storage address information of mating with this query word that whether exists, if exist, and execution in step 203, otherwise, execution in step 204.
Step 203 is returned to response message.
Step 204, node continue forwarding inquiries message to the neighbor node of oneself, carry described query word in this query messages.
Wherein, node is selected suitable neighbor node according to routing algorithm, and selected neighbor node can be one, a plurality of, perhaps whole neighbor nodes.
As seen, prior art is transmitted query word in the DHT ring successively between adjacent node, and each node is inquired about the search target respectively, until certain node finds contents storage address information corresponding to described query word, returns to response message.
Wherein, routing algorithm has determined the order that query word transmits, i.e. searching route between adjacent node.
This shows, in the P2P network based on DHT, the major function that each node is born is matching inquiry and routing forwarding.
The below analyzes the existing problem that exists based on the content positioning method in the P2P network of DHT:
In the P2P network based on DHT, the content resource index is distributed in a plurality of nodes in network, after the distribution of content location node has determined that the content search request message generally need to forward through multiple spot, just can find the position at content place, therefore, the efficient of content location is lower.
And bandwidth of network between the query processing ability of each content location node and each node all can produce larger impact to the efficient of inquiry, might further reduce the efficient of content location.
For the query requests of content class, having is much Stream Media Application from real-time, to delay sensitive, therefore requires high to search efficiency.Existing method is difficult to satisfy this efficiency requirements, and particularly under the trend that the Web content amount increases gradually, this method will the more and more difficult requirement of satisfying user's access time delay.Even in the content class service of some non-delay sensitive, excessive content is located time delay also can bring the reduction of satisfaction to the user.
Except the lower problem of efficient, existing content positioning method based on DHT, also there is the excessive problem of interaction message quantity: present content positioning method based on DHT, usually need to be between node forwarding inquiries message repeatedly, the location that just can complete content is when a large number of users requesting query content, to there be a large amount of query messages in network, to the forwarding of these a large amount of query messages, not only consume a large amount of network bandwidth resources, also will increase the computing cost of querying node and forwarding.
In order to address the above problem, need to be to improving based on the content positioning method in the P2P network of DHT.
Embodiment
Fig. 3 is content positioning method flow chart provided by the invention.
As shown in Figure 3, the method comprises:
Step 301 is in the local memory contents of routing node and/or content locating information.
Wherein, for the ease of the content of the local storage of retrieval routing node, can also be at the local content information of routing node storage, described content information comprises the sign ID of content and the corresponding relation between the memory location of this content in this routing node.
Wherein, described content locating information comprises the ID of content and the corresponding relation between down hop routing node address information, store the storage address information of this content in described down hop routing node, described storage address information is the address information of having stored the network node of this content.
Wherein, when a routing node receives content acquisition request from other routing nodes, if store the storage address information of the content of described content acquisition request institute acquisition request in this routing node, this routing node to receive the initial routing node of described content acquisition request from user node, returns to the address information of this routing node.
Step 302, routing node receive content acquisition request, according to the content of storing in this routing node and/or content locating information, the content of described content acquisition request institute acquisition request are positioned.
Wherein, routing node is stored in routing node when local in the content of determining described content acquisition request institute acquisition request, and this routing node returns to the content of described content acquisition request institute acquisition request to user node.
In the present invention, the ID of content is by the cryptographic Hash that partly or entirely calculate of hash function to content, is therefore a kind of content identification of flattening.
Method shown in Figure 3 can make the significantly raising of distribution efficient acquisition of content service system, increase the function of content caching and the function of route-caching by the routing node in existing content service system, content Search and Orientation process is optimized, shorten the path of request message routing forwarding, make at most and can navigate to content in jumping, thereby improve the efficient of content location.
Described content and content locating information according to storing in this routing node, content to described content acquisition request institute acquisition request positions, generally first to carry out content according to content information to locate, if can't navigate to the content of acquisition request, then carry out content according to the content locating information and locate.Also may only position according to content information in some cases or only position according to the content locating information or first position according to the content locating information, then position according to content information.
Wherein, carry out content location according to content information and specifically comprise: inquire about the content information of storing in this routing node, it is local whether the content of determining described content acquisition request institute acquisition request is stored in this routing node.
Carrying out content location according to the content locating information specifically comprises: inquire about the content locating information of storing in this routing node, if store the locating information of the content of described content acquisition request institute acquisition request in this routing node, this content acquisition request is transmitted to the down hop routing node of described locating information appointment, obtains the storage address information of the content of described content acquisition request institute acquisition request from described down hop routing node.
Routing node in the present invention carries out content location except content information and content locating information according to self storage, in order to carry out compatibility with localization method of the prior art, can also further carry out content according to the contents storage address index information of storing in routing node of the prior art with the forwarding index information and locate.
When routing node according to content information, content locating information, the contents storage address index information of this locality storage with when forwarding index information and carrying out the content location, the general first query contents information of routing node, content locating information and contents storage address index information, if can't navigate to content according to Query Result, forward index information by inquiry again, content acquisition request is transmitted to the down hop routing node that forwards appointment in index information carries out the content location.Wherein, search order to content information, content locating information and contents storage address index information can be changed, as a kind of preferred mode, and first query contents information, query contents locating information again, query contents memory address index information, can reduce the change to existing route node and content positioning method afterwards, as another kind of preferred mode, first query contents information, query contents memory address index information again, the query contents locating information, can improve locating speed afterwards.
The below is elaborated to above-mentioned two kinds of preferred mode, specifically sees also Fig. 4 and Fig. 5.
Fig. 4 is the first method flow diagram that the content of content acquisition request institute acquisition request is positioned provided by the invention.
As shown in Figure 4, this flow process comprises:
Step 401 is inquired about the content information of storing in this routing node, and it is local whether the content of determining described content acquisition request institute acquisition request is stored in this routing node, if so, and execution in step 402, if not, execution in step 403.
Step 402 is obtained the stored position information of described content, process ends from this routing node.
Step 403 is inquired about the content locating information of storing in this routing node, determines whether to store the locating information of described content in this routing node, if so, and execution in step 404, if not, execution in step 405.
Step 404 is transmitted to this content acquisition request the down hop routing node of described locating information appointment, obtains the storage address information of the content of described content acquisition request institute acquisition request from described down hop routing node, process ends.
Step 405, whether inquiry has stored the storage address information of described content in this routing node, if so, execution in step 406, if not, execution in step 407.
Step 406 is obtained the storage address information of this content, process ends from this routing node this locality.
Step 407, this content acquisition request is transmitted to the down hop routing node of appointment in forwarding concordance list in this routing node,, according to content information and the content locating information of storing in described content acquisition request and this down hop routing node the content of described content acquisition request institute acquisition request is positioned by described down hop routing node.
Fig. 5 is the second method flow diagram that the content of content acquisition request institute acquisition request is positioned provided by the invention.
As shown in Figure 5, this flow process comprises:
Step 501 is inquired about the content information of storing in this routing node, and it is local whether the content of determining described content acquisition request institute acquisition request is stored in this routing node, if so, and execution in step 502, if not, execution in step 503.
Step 502 is obtained the stored position information of described content, process ends from this routing node.
Step 503, whether inquiry has stored the storage address information of described content in this routing node, if so, execution in step 504, if not, execution in step 505.
Step 504 is obtained the storage address information of this content, process ends from this routing node this locality.
Step 505 is inquired about the content locating information of storing in this routing node, determines whether to store the locating information of described content in this routing node, if so, and execution in step 506, if not, execution in step 507.
Step 506 is transmitted to this content acquisition request the down hop routing node of described locating information appointment, obtains the storage address information of the content of described content acquisition request institute acquisition request from described down hop routing node, process ends.
Step 507, this content acquisition request is transmitted to the down hop routing node that forwards appointment in concordance list,, according to content information and the content locating information of storing in described content acquisition request and this down hop routing node the content of described content acquisition request institute acquisition request is positioned by described down hop routing node.
In order to save the memory space of routing node, accelerate the speed of search routing node local content and content locating information, routing node number of times requested according to content determined Hot Contents, the locating information of only storing Hot Contents and Hot Contents in routing node this locality.
Wherein, routing node receives content acquisition request, can according to the content ID that carries in this content acquisition request, upgrade the requested number of times of content corresponding to this content ID.
Routing node number of times requested according to content determines that Hot Contents specifically can comprise:
Judge content the first predetermined length in the time period requested number of times whether greater than the first predetermined threshold, if so, content corresponding to this content ID is defined as main Hot Contents, at this main Hot Contents of the local storage of routing node; If content requested number of times in the first scheduled time segment length is not more than the first predetermined threshold, but greater than the second predetermined threshold, content corresponding to this content ID is defined as the secondary hot spots content, the corresponding relation between routing node local storage secondary hot spots content and down hop routing node address information.When definite secondary hot spots content, can judge that also content requested number of times in the second scheduled time segment length whether greater than the second predetermined threshold, if so, is defined as the secondary hot spots content with content corresponding to this content ID.
Specifically can be at the main Hot Contents of the local storage of routing node, the corresponding relation between routing node local storage secondary hot spots content and down hop routing node address information.
Because the overwhelming majority's user request concentrates on the content of some focus, therefore improve the location efficiency of Hot Contents and can improve most users' Quality of Service Experience.
The present invention can be applied in the scene of plurality of kinds of contents location, for example is applied in to add on a large scale in point-to-point (P2P) content share system.Use the hop count that the present invention can shorten the required process in content location, thereby improve location efficiency.
According to localization method provided by the invention, the present invention also provides a kind of routing device, specifically asks for an interview Fig. 6.
Fig. 6 is routing device structure chart provided by the invention.
As shown in Figure 6, this routing device comprises content storage module 601, content indexing module 602, content locating information index module 603 and locating module 604.
Content storage module 601 is used for memory contents.
Content indexing module 602 is for ID and the corresponding relation of this content between the memory location of this routing device of memory contents.
Content locating information index module 603 is used for the ID of memory contents and the corresponding relation between down hop routing node address information, stores the storage address information of this content in described down hop routing address.
Locating module 604 be used for to receive content acquisition request, according to the corresponding relation in content indexing module and content locating information index module, the content of described content acquisition request institute acquisition request is positioned.
Locating module 604 wherein can comprise local content enquiry module and content locating information enquiry module.
Described local content enquiry module is used for inquiring about the content information that described content indexing module is stored, and it is local whether the content of determining described content acquisition request institute acquisition request is stored in this routing node.
Described content locating information enquiry module, inquire about the content locating information of storing in described content locating information index module, if store the locating information of the content of described content acquisition request institute acquisition request in this routing node, this content acquisition request is transmitted to the down hop routing node of described locating information appointment, obtains the storage address information of the content of described content acquisition request institute acquisition request from described down hop routing node.
Described routing device can also comprise contents storage address index module and forwarding index module, and locating module 604 can also comprise contents storage address enquiry module and forwarding inquiries module.
Described contents storage address index module is used for the ID of memory contents and stores corresponding relation between the address of network node of this content.
Described forwarding index module, the address information that is used for storing the down hop routing node.
Described contents storage address enquiry module, be used for inquiring about the corresponding relation that described contents storage address index module is stored, if stored the memory address corresponding to content of described content acquisition request institute acquisition request in described contents storage address index module, obtain the memory address of described content from described contents storage address index module.
Described forwarding inquiries module, be used for described content acquisition request being transmitted to the down hop routing node of described forwarding index module appointment when local content enquiry module, content locating information enquiry module and contents storage address enquiry module all fail to locate the content of described content acquisition request institute acquisition request.
Described routing device can also comprise the Hot Contents determination module.
Described Hot Contents determination module, for the requested number of times of content ID update content that carries according to content acquisition request, number of times requested according to content determined Hot Contents.
Content storage module 601 is used for the storage Hot Contents.
Content locating information memory module 603 is used for the ID of storage Hot Contents and the corresponding relation between down hop routing node address information, stores the storage address information of this Hot Contents in described down hop routing address.
Wherein, the corresponding relation of the requested number of times of content and content ID can be stored in content information memory module 602, also can be stored in other positions, in the time of in being stored in content information memory module 602, can safeguard in content information memory module 602 and specifically see also table one by meaningful storage concordance list.
Table one
Content ID |
The memory location |
Request number of times |
SDJFOE |
/dev/cache/movie |
40 |
In Table 1, store content ID, content position and the requested number of times of content in local memory device.
Described Hot Contents determination module, be used for judging content the first predetermined length in the time period requested number of times whether greater than the first predetermined threshold, if so, content corresponding to this content ID is defined as main Hot Contents; If content requested number of times in the first scheduled time segment length is not more than the first predetermined threshold, but greater than the second predetermined threshold, content corresponding to this content ID is defined as the secondary hot spots content, perhaps, judge content in the second scheduled time segment length requested number of times whether greater than the second predetermined threshold, if so, content corresponding to this content ID is defined as the secondary hot spots content.
Content storage module 601 is used for storing main Hot Contents.
Content locating information memory module 603 is used for the ID of storage secondary hot spots content and the corresponding relation between down hop routing node address information, stores the storage address information of this secondary hot spots content in described down hop routing address.
Wherein, the ID of content is by the cryptographic Hash that partly or entirely calculate of hash function to content.
Content locating information memory module 603 wherein can with the form memory contents ID of table two and the corresponding relation between down hop routing node address information, specifically see also table two.
Table two
Content ID |
The next-hop node sign |
The next-hop node address |
Request number of times |
SDJFOE |
Node13 |
164.244.45.6 |
33 |
Wherein, in content information memory module and content locating information memory module, may there be the buffer memory to two kinds of information of identical content, in other words, both stored certain content in routing device, also store the locating information of this certain content in this routing device, this design, to become the heat spot content in order to guarantee, and be buffered the file of content, after being eliminated into non-Hot Contents, can guarantee still that to the buffer memory of its location of content this content is found fast, still larger because these contents become the possibility of Hot Contents.And, to compare with the buffer memory of content, the shared memory space of the buffer memory of content locating information is much smaller, can the memory space of location of content buffer memory not taken too much.
Can also comprise in described routing device that the address returns to module.
Module is returned in described address, be used for receiving the content acquisition request that other routing nodes send and determining this locating module place routing device when storing the storage address information of content of described content acquisition request institute acquisition request at described locating module, return to the address information of this locating module place routing device to described other routing nodes.
Described routing device can also comprise the content uploading service module.
Described content uploading service module is used for orienting when described content storage module stores the content of described content acquisition request institute acquisition request at described locating module, returns to described content to the user node that sends described content acquisition request.
The above is only preferred embodiment of the present invention, and is in order to limit the present invention, within the spirit and principles in the present invention not all, any modification of making, is equal to replacement, improvement etc., within all should being included in the scope of protection of the invention.