Source: http://www.google.com/patents/US7984182?dq=6,249,089
Timestamp: 2016-12-09 10:52:18
Document Index: 787907499

Matched Legal Cases: ['art 11', 'art 11', 'art 20', 'art 11', 'art 11', 'art 20', 'art 11', 'art 20']

Patent US7984182 - Node device, information transfer processing program, and network ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsA node device which participates in an overlay network formed by participation of all or part of a plurality of node devices which are connected to each other via a communication device. The node device includes a search information transmission device, a reply information receiving device, a communication...http://www.google.com/patents/US7984182?utm_source=gb-gplus-sharePatent US7984182 - Node device, information transfer processing program, and network participation processing method and the likeAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS7984182 B2Publication typeGrantApplication numberUS 11/822,388Publication dateJul 19, 2011Filing dateJul 5, 2007Priority dateJan 7, 2005Fee statusPaidAlso published asEP1841141A1, EP1841141A4, US20070258389, WO2006073046A1Publication number11822388, 822388, US 7984182 B2, US 7984182B2, US-B2-7984182, US7984182 B2, US7984182B2InventorsHiroaki Suzuki, Yoshihiko Hibino, Yuji Kiyohara, Kentaro Ushiyama, Koichi IijimaOriginal AssigneeBrother Kogyo Kabushiki Kaisha, Xing Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (11), Non-Patent Citations (2), Referenced by (4), Classifications (35), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetNode device, information transfer processing program, and network participation processing method and the like
Non-patent Document 1: “Lightweight Load Balancing for Distributed Hash Table”. Technical Report of the Institute of Electronics, Information, and Communication Engineers.
In the present embodiment, the overlay network 9 configured by an algorithm using DHT is a premise and node devices n1 to n15 which are located in the overlay network 9 (in the upper rectangular frame 100 in FIG. 1) are referred to as node devices participating in the overlay network 9 (hereinafter, such node devices n1 to n15 are referred to as “participating node(s) nn” as a general term). In other words, the overlay network 9 is configured by participation of the participating nodes nn. Participation into such overlay network 9 is performed when node devices n16 to n21 (hereinafter referred to as “non-participating node(s) nm” as a general term) transmits participation request information indicating participation request to any of an arbitrary participating nodes nn.
Moreover, location information (for example, IP address and manufacturing number of a participating node nn in which the content data is saved) indicating location of content data thus distributed and saved is also distributed and saved in a plurality of participating nodes nn. For example, a content name of certain content data (or first a few bytes of the content data) is hashed by the hash function, which is commonly used when the node ID is obtained (that is, located in the same ID space as hashed value of IP address of participating node nn), and location information of the content data is saved in a participating node nn having a node ID which is closest to the hashed value (the hashed value becomes content ID). That is, even when the one same content data (having same content ID) is saved in a plurality of participating nodes nn, location information indicating the location of such content data (IP address or the like of the plurality of participating nodes nn) can be managed by one participating node nn (hereinafter, such a participating node which manages location of content data will be referred to as “route node”). Note that in the present embodiment, in a route node of 1, location information of content data corresponding to content ID of 1 is saved (that is, route node and the location information have a 1:1 relationship). However, the present invention is not limited thereto.
FIG. 3 is a view showing an example of a routing table of DHT retained by a participating node n1 and FIG. 4 is a conceptual diagram showing an example of a node ID space of DHT. Note that in FIGS. 3 and 4, for the convenience of explanation, bit length of node ID is set to be 2 bits×3 digits=6 bits and each digit is expressed by a number system of base-4 (integers from 0 to 4) (actually, longer bit length is used and each digit is, for example, divided by 4 bits and expressed by hexadecimal number system using 0 to f).
In an example of FIG. 3, a routing table of DHT includes tables level 1 to 3 and in the table of each level, a node ID and IP address of a participating node nn corresponding to the node ID are related and registered for each area. Each area of a table of each level is an area obtained by dividing a node ID space of DHT. For example, as shown in FIG. 4, in level 1, node ID space is divided into four, including a 0xx area where node IDs of “100” to “133” exist, a 1xx area where node IDs of “000” to “033” exist, a 2xx area where node IDs of “200” to “233” exist, and a 3xx area where node IDs of “300” to “333” exist. Moreover, in level 2, an area of the level 1 (that is, areas of 0xx to 3xx) is further divided into four, including a 10x area where node IDs of “100” to “103” exist, a 11x area where node IDs of “110” to “113” exist, a 12x area where node IDs of “120” to “123” exist, and a 13x area where node IDs of “130” to “133” exist.
Then, for example, when a node ID of a participating node n1 is “123”, as shown in FIG. 3, on a table of an area of 1xx in level 1 of such a participating node n1 (where the node exists), node ID and IP address of the participating node n1 (since IP address belongs to the participating node n1, it is not needed to be registered on the routing table) are registered and in other areas where the participating node n1 does not exist (that is, areas of 0xx, 2xx, and 3xx) node IDs and IP addresses of other arbitrary participating nodes nn are registered respectively.
Note that in the examples of FIGS. 3 and 4, bit length of node ID is assumed to be 3 digits×2 bits. Therefore, it is possible to cover in use of a 3-level table having levels 1 to 3. However, when the bit length of node ID is increased, a larger table is required as much (for example, when it is assumed that bit length of node ID is 16 digits×4 bits, a table for 16 levels is required).
For example, as shown in FIG. 5, the non-participating node n16 generates a node ID by hashing an IP address of itself by the hash function (for example, “333”) and transmits participation request information to which the node ID and the IP address of itself have been attached to a participating node n1.
The participating node n1 receives the participation request information, refers to a routing table 51 of DIIT, obtains an IP address of a participating node n11 which has a node ID “303” which is closest to the node ID “333” attached to the participation request information, and based on this, transfers participation request Information to which the node ID “333” and IP address of the non-participating node n16 have been attached to the participating node n11.
The participating node nil receives the participation request information, refers to a routing table 52 of DHT, obtains an IP address of a participating node n9 which has a node ID “332” which is closest to the node ID “333” attached to the participation request information, and based on this, transfers participation request information to which the node ID “333” and IP address of the non-participating node n16 have been attached to the participating node n9.
The participating node n9 receives the participation request information, relates the participation request information to node ID “333” in a table of level 3 in a routing table 53 of DHT, and registers the IP address of the non-participating node n16. That is, the participating node n9 manages the node ID “333”.
The non-participating node n16 receives part of a transmitted routing table of DHT and based on them, generates a routing table 54 of DHT of the non-participating node n16 itself (for example, a routing table 54 including the table 51 a of level 1 for the participating node n1 (node ID “301” and an IP address corresponding thereto is replaced with the node ID “333” and IP address corresponding thereto of the non-participating node n16 itself) and the table 52 a of level 2 for the participating node n11 (node ID “332” and an IP address corresponding thereto is replaced with the node ID “333” and IP address corresponding thereto of the node n16 itself) and the table 53 a of the level 3 for the participating node n9 is generated).
Next, the control part 11 of the non-participating node n16 generates a search packet which is search information for searching for a participating node nn to which participation request information indicating participation request to the overlay network 9 (hereinafter referred to as “participation request packet”) is to be transmitted. Sender's address of the search packet is the IP address of the non-participating node n16 while destination address thereof is the IP address of the management server SA. The control part 11 transmits the search packet thus generated to the management server SA as search information transmission means via the communication part 20 and the network 8 (Step S2: FIG. 8 (A)). Thus, the control part 11 of the non-participating node n16 waits for reply information from an arbitrary participating node nn.
Next, in the processing in FIG. 7 (C), when the control part 11 of a participating node nn receives the search packet transmitted (transferred) from the management server SA (Step S6), generates reply information of which sender's address is set to be an IP address of the participating node nn's and destination address is set to be the IP address of the non-participating node n16 (hereinafter referred to as “reply packet”) and transmits (replies) the reply packet to the non-participating node n16 via the communication part 20 and the network 8 (Step S7: FIG. 8 (B)) to finish the processing.
Note that there is a case where TTL indicating expiry period of the packet is included in the reply packet or the like. The TTL is expressed by an integer value of which maximum value is “225” and is decreased by 1 when the packet passes (is transferred) through a router or the like. When TTL becomes “0”, the packet is disposed at that point of time and a disposal notification is transmitted to the sender of the packet. Therefore, the larger value of TTL of the packet means the smaller number of the packet being transferred (HOP number) and which means effect to the communication load in the communication route of the network 8 is small.
In Step S15, the control part 11 of the participating node nn generates transfer destination information of which sender's address is the IP address of the participating node nn and destination address is IP address of the non-participating node n16 (hereinafter referred to as “transfer destination packet”) and includes part of a routing table of DHT, transmits the transfer destination packet to the non-participating node n16 through the communication part 20 and the network 8 (FIG. 9(E)), and finishes the processing.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS6389448 *May 5, 2000May 14, 2002Warp Solutions, Inc.System and method for load balancingUS20020029287 *Feb 1, 2001Mar 7, 2002Yechiam YeminiMethod and apparatus for dynamically addressing a circuits based networkUS20020073075 *Dec 7, 2000Jun 13, 2002Ibm CorporationMethod and system for augmenting web-indexed search engine results with peer-to-peer search resultsUS20030101278 *Sep 10, 2002May 29, 2003J.J. Garcia-Luna-AcevesSystem and method for directing clients to optimal servers in computer networksUS20040054807 *Feb 3, 2003Mar 18, 2004Microsoft CorporationSystem and method for creating improved overlay network with an efficient distributed data structureUS20040064556 *Oct 1, 2002Apr 1, 2004Zheng ZhangPlacing an object at a node in a peer-to-peer system based on storage utilizationUS20050076137 *Sep 19, 2003Apr 7, 2005Chungtang TangUtilizing proximity information in an overlay networkUS20050198286 *Jan 30, 2004Sep 8, 2005Zhichen XuSelecting nodes close to another node in a network using location information for the nodesUS20050243722 *Apr 30, 2004Nov 3, 2005Zhen LiuMethod and apparatus for group communication with end-to-end reliabilityUS20060120411 *Dec 7, 2004Jun 8, 2006Sujoy BasuSplitting a workload of a nodeUS20060239207 *May 19, 2005Oct 26, 2006Nokia CorporationCombined load balancing for overlay and ad hoc networks* Cited by examinerNon-Patent CitationsReference1Oka T. et al., "Lightweight Load Balancing for Distributed Hash Tables," Feb. 5, 2004, The Institute of Electronics, Information and Communication Engineers, vol. 103, No. 650, pp. 7-12.2Rowstron A. et al., "Pastry: Scalable, Decentralized Object Location and Routing for Large-scale Peer-to-Peer Systems," Nov. 12-16, 2001, Microsoft Research Ltd, vol. 2218.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS8230063 *Jul 2, 2010Jul 24, 2012Huawei Technologies Co., Ltd.User data server system, method and apparatusUS20100185753 *Aug 30, 2007Jul 22, 2010Hang LiuUnified peer-to-peer and cache system for content services in wireless mesh networksUS20100268820 *Jul 2, 2010Oct 21, 2010Huawei Technologies Co., Ltd.User data server system, method and apparatusUS20140379877 *Jun 25, 2014Dec 25, 2014Foundation Of Soongsil University-Industry CooperationCircle-mesh overlay network construction and maintain method* Cited by examinerClassifications U.S. Classification709/241, 709/226, 370/236, 370/400, 709/229International ClassificationH04L12/18, G06F13/00, G06F15/16Cooperative ClassificationH04L67/1065, H04L67/101, H04L67/104, H04L67/1068, H04L67/1063, H04L67/1002, H04L67/1021, H04L67/1046, H04L47/122, H04L45/54, H04L47/11, H04L45/125, H04L12/1886, H04L45/745, H04L47/10European ClassificationH04L29/08N9A, H04L12/18T, H04L29/08N9P, H04L29/08N9A1C, H04L29/08N9A1H, H04L29/08N9P1A1, H04L47/12A, H04L47/10, H04L45/125, H04L47/11, H04L45/54, H04L45/745Legal EventsDateCodeEventDescriptionJul 5, 2007ASAssignmentOwner name: BROTHER KOGYO KABUSHIKI KAISHA, JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:SUZUKI, HIROAKI;HIBINO, YOSHIHIKO;KIYOHARA, YUJI;AND OTHERS;REEL/FRAME:019553/0194;SIGNING DATES FROM 20070625 TO 20070702Owner name: XING INC., JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:SUZUKI, HIROAKI;HIBINO, YOSHIHIKO;KIYOHARA, YUJI;AND OTHERS;REEL/FRAME:019553/0194;SIGNING DATES FROM 20070625 TO 20070702Owner name: BROTHER KOGYO KABUSHIKI KAISHA, JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:SUZUKI, HIROAKI;HIBINO, YOSHIHIKO;KIYOHARA, YUJI;AND OTHERS;SIGNING DATES FROM 20070625 TO 20070702;REEL/FRAME:019553/0194Owner name: XING INC., JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:SUZUKI, HIROAKI;HIBINO, YOSHIHIKO;KIYOHARA, YUJI;AND OTHERS;SIGNING DATES FROM 20070625 TO 20070702;REEL/FRAME:019553/0194Dec 29, 2014FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services