Rendezvousing resource requests with corresponding resources

(54) Title: CONGREGATION OF RESOURCE REQUESTS WITH CORRESPONDING RESOURCES (30) Unionist Priority: 10/22/2004 us 10 / 971.451: 07/09/2005 US 11 / 220.756 (71) Depositor (s): Microsoft Corporation (US ) (72) Inventor (s): Gopala Krishna R. Kakivaya, Richard L. Hasha, Thomas Lee Rodeheffer (74) Attorney: NellieAnne Daniel-Shores (57) Summary: CONGREGATION OF APPEAL REQUESTS WITH MATCHING RESOURCES. The present invention encompasses methods, systems, and computer program products for bringing together resource requests with corresponding resources. Double linked chained lists are traversed using module arithmetic in both directions. Classified lists can be shared based on a multiple proximity metric. Node routing tables provide a logarithmic index for nodes within the federated infrastructure's ID space to facilitate more efficient routing. Messages can be routed to nodes within a ring and routed proximally to nodes in other shared rings.

<img file="BRPI0504513A_D0001.tif" />

• · • · ·

CONGREGATION OF APPEAL REQUESTS WITH CORRESPONDING RESOURCES

CROSS REFERENCE TO RELATED ORDERS

That application is a continuation of United States Patent Application 10 / 971,451; filed on October 22, 2004, and entitled Rendezvousing Resource Requests With Corresponding Resources, which is incorporated herein in full as a reference.

BACKGROUND OF THE INVENTION 10 1. Field of the Invention

The present invention refers to accessing resources, more specifically, to the gathering of resource requests with corresponding resources.

2. Background and Relevant Technique

Computer systems and related technology affect many aspects of society. In reality, the ability of computer systems to process information has transformed the way we live and work. Computer systems now commonly perform a range of tasks (for example, word processing, programming, and database management) that before the advent of the computer system were performed manually. More recently, computer systems were linked to each other and to other electronic devices to form networks of physically connected as well as wireless networks through which computer systems and other electronic devices can transfer electronic data. As a result, many tasks performed on a computer system (for example, voice communication, access to electronic mail, control of home electronic means, browsing the network, and printing documents) include electronic communication between some computer systems and / or other electronic devices via physically and / or wirelessly connected computer networks.

However, to use a network resource to perform a computerized task, a computer system must have some way of identifying and accessing the network resource. Consequently, resources are typically assigned unique identifiers, for example, network addresses, which uniquely identify resources and can be used to distinguish one resource from other resources. In this way, a computer system that wants to use a resource can connect to the resource using the network address that corresponds to the resource. However, accessing a network resource can be difficult if a computer system does not have prior knowledge of a network address for a network resource. For example, a computer system cannot print a document to a network printer unless the computer system (or another network computer system) knows the network printer's network address.

Consequently, several mechanisms (for example,

Domain Name System (DNS); Active Directory (AD); Distributed File Systems (DFS), were developed for computer systems to identify (and access) previously unknown resources. However, due to the amount and diversity of resources (for example, devices and services) that can be accessed via different computer networks, developers are often required to develop applications that implement a variety of different resource identification and access mechanisms. Each different engine may have different coding requirements and may not provide a developer with all the functionality that is needed in an application.

For example, although DNS has a distributed 10 administration architecture (ie, centralized management is not required), DNS is not sufficiently dynamic or self-organizing, supports a weak data and query model, and has a fixed set of roots . On the other hand, AD is sufficiently dynamic but requires centralized administration by. In addition, aspects of different mechanisms may not be compatible with each other. For example, a resource identified using DNS may not be compatible with DFS routing protocols. In this way, a developer may be forced to choose the most suitable mechanism and forgo the advantages of other mechanisms.

Mechanisms for identifying resources can be particularly problematic in non-hierarchical networks. DNS provides a query service, with host names as keys and IP addresses as values, which is based on a con25 with special root servers to implement query requests. Additionally, DNS requires information management (NS records) to allow clients to navigate the name server hierarchy. From that moment on, the resource must be introduced in DNS before the resource can be identified on a network. In larger scale networks where nodes frequently connect and disconnect from the network, relying on information input is not always practical. Additionally, DNS specializes in the task of finding hosts or services and is not generally applicable to other types of resources.

Consequently, other mechanisms for resource identification and access have been developed to try to address these obstacles. Some mechanisms include distributed query protocols that are more scalable than DNS. These mechanisms use various node arrangements and routing algorithms to route requests to corresponding resources and to store information for consultation.

At least one of these mechanisms uses multi-level local neighbor maps, on each node, in a network, to route messages to a destination node. This essentially results in a file where each node is a root node in a tree of corresponding nodes (the nodes in its neighbor map). Messages are routed incrementally to a digit-by-digit destination ID (for example, *** 6 => ** 46 =>, * 346 => 2346, where * s represents wildcards). The routing efficiency of these types of mechanisms is O (log N) routing hops and requires nodes to maintain a size 0 routing table (log N).

At least one other of these mechanisms assigns the nodes to a unique ID that is taken from a linear ring of numbers. Nodes maintain routing tables that contain indicators for their immediate successor node (according to ID value) and for those nodes whose ID values ​​are the closest successor to the ID + 2 value^L. The routing efficiency of these types of mechanisms is also O (log N) routing hops and requires nodes to maintain a routing table of size O (log N).

At least one additional mechanism requires O (log N^{I / d}) routing hops and requires nodes to maintain an O (D) size routing table. Thus, the routing efficiency of all of these mechanisms depends, at least in part, on the number of nodes in the system.

In addition, since identifiers (for at least some of the mechanisms) can be evenly distributed around a ring, there is always some possibility that routing between the nodes in the ring will result in some inefficiency. For example, routing hops can cross several geographical distances, cross more expensive connections, or pass through unsafe domains, etc. Additionally, when message routing involves multiple hops, there is some chance that such events will occur multiple times. Unfortunately, these mechanisms do not consider how close we are (physically or otherwise) to each other. For example, depending on the distribution of nodes in a ring, routing a message from New York to Boston could involve routing the message from New York to London to Atlanta to Tokyo and then to Boston.

Consequently, at least one more recent mechanism considers proximity by defining proximity as an individual scalar proximity metric (for example, IP routing hops or geo5 graphical distance). These mechanisms use the notion of choice based on proximity to routing table entries. Since there are many correct candidate nodes for each routing table entry, these mechanisms attempt to select a neighboring node proximally from the candidate nodes. For these mechanisms, a function can be provided that allows each node to determine the distance from a node with a given IP address to itself. Messages are routed between nodes in close proximity to make progress towards a destination before routing to a node that is further away. This way, some resources can be conserved and the routing is more efficient.

Unfortunately, these existing mechanisms typically do not provide, among other things, symmetrical relationships between nodes (that is, if a first node considers a second node to be its partner, the second node also considers the first node to be a partner), routing messages in both directions (clockwise and counterclockwise) in a ring, sharing linked lists of nodes based on a plurality of proximity metrics, and routing messages based on a plurality of proximity metrics. Therefore, computer program systems, methods and products that use these mechanisms to pool resource requests with a corresponding resource would be advantageous.

BRIEF SUMMARY OF THE INVENTION

The previously mentioned problems with the prior art are overcome by the principles of the present invention, which refer to methods, systems and computer program products for bringing together resource requests with corresponding resources. In some modalities, the nodes of a federative infrastructure are shared. A sorted linked list, containing the node IDs that have been assigned to the nodes in the federative infrastructure, is accessed. Proximity categories, which represent a plurality of different proximity criteria for partitioning the classified linked list, are accessed. The sorted chained list is shared in one or more first sublists based on a first proximity criterion, each one of one or more first sublists containing at least a subset of the node identifiers from the sorted chained list. A first sublist, selected from one or more first sublist, is shared in one or more second sublist based on a second proximity criterion, each of the one or more second sublist containing at least a subset of node ID contained in the first sublist.

In other modalities, for example, as illustrated in Figure 3, a node routing table is populated. An immediate predecessor node is inserted into the routing table. An immediate successor node is inserted into the routing table. Appropriate neighborhood node identifiers are inserted in the routing table, neighborhood nodes are identified from the linked list classified in the first direction as well as in a second, opposite direction, based on a predetermined or estimated neighborhood range and on neighborhood size. Appropriate routing node identifiers are inserted into the routing table, the routing nodes being identified from the linked list classified in both the first and second directions based on the numerical basis and field size of the ID space for the federative infrastructure , the routing nodes representing a logarithmic index of the linked list classified both in the first and in the second direction.

In still other modalities, a node routing table can be populated considering proximity criteria. A predecessor node for each hierarchically shared routing ring in which the current node participates is inserted into a routing table, each hierarchically shared routing ring being shared according to corresponding proximity criteria and containing at least the subsets of the bi-directional linked list. a parent ring. A successor node for each hierarchically shared routing ring in which the current node participates is inserted in the routing table. Neighborhood nodes appropriate for each hierarchically shared routing ring in which the current node participates are inserted into the routing table. Appropriate routing nodes for each hierarchically shared routing ring in which the current node participates are inserted into the routing table.

In other additional modalities, a message is routed, potentially based on one or more proximity criteria defining one or more corresponding classes of nodes, towards a destination node. A receiving node receives a message along with a destination number indicating a destination node and optionally one or more proximity criteria. 0 receiving node, potentially among nodes in a current class of nodes, determines that it is at least the one numerically more distant from the destination number than a corresponding predecessor node and numerically more distant from the destination number than a corresponding successor node . It is determined that the destination is not in a set of neighborhood nodes, potentially between nodes in the current class of nodes, corresponding to the receiving node.

An intermediate node from a routing table corresponding to the receiving node is identified, the intermediate node being numerically closer to the destination number than other routing nodes in the corresponding routing table. The message is sent to the intermediate node. The intermediate node can continue to route the message. The message eventually reaches the destination node when a node that receives the message is numerically closer to the destination number than its successor or predecessor node. In modalities that perform routing based on one or more proximity criteria, this numerical proximity can be in relation to the nodes in a selected class of nodes.

Thus, routing a message based on proximity criteria includes routing to a destination node (ID) by progressively moving closer to the destination node within a given proximal ring (node ​​class) until no further advances can be made. be done before routing within that ring. The determination that no further progress can be made occurs when the target number is located between the ID of the current node and the IDs of its successor or predecessor nodes. At this point, the current node begins to route via its partner nodes to the next largest proximal ring in which it participates. This process of moving progressively towards the destination node through the action of climbing along the partition path towards the root ring ends when the destination node is reached.

These and other objectives and characteristics of the present invention will become more evident from the description below and the appended claims, or can be learned by practicing the invention as shown below.

BRIEF DESCRIPTION OF THE DRAWINGS

In order to better clarify the advantages and features mentioned above, and others, of the present invention, a more specific description of the invention will be made by reference to its specific modalities which are illustrated in the attached drawings. These drawings are considered to illustrate only typical modalities of the invention and, therefore, should not be considered as limiting their scope. The invention will be described and explained with additional specificity, in detail, using the accompanying drawings in which:

Figure 1 illustrates an example of a federative infrastructure.

Figure 2 illustrates an example of a computer architecture that facilitates request routing indirectly for partners.

Figure 3 illustrates an exemplary binary relationship between nodes in a federative structure in the form of a classified list and corresponding ring.

Figure 4 illustrates an exemplary ring of the rings that facilitate proximal routing.

Figure 5 illustrates an exemplary proximity-induced partition ring tree that facilitates proximal routing.

Figure 6 illustrates an operating environment suitable for the principles of the present invention.

Figure 7 illustrates an exemplary flow chart of a method for populating a node routing table that considers proximity criteria.

Figure 8 illustrates an exemplary flow chart of a method for sharing nodes in a federative infrastructure.

Figure 9 illustrates an exemplary flow chart of a method for populating a node routing table.

Figure 10 illustrates an exemplary flowchart of a method for numerically routing a message towards a destination node.

Figure 11 illustrates an exemplary flowchart of a method for proximally routing a message towards a destination node.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

The previously mentioned problems with the prior art are overcome by the principles of the present invention, which refer to methods, systems and computer program products for bringing together resource requests with corresponding resources. In some modalities, the nodes of an infrastructure made fertile are shared. A sorted linked list, containing the node IDs that have been assigned to the nodes in the federative infrastructure, is accessed. Proximity categories, which represent a plurality of different proximity criteria for partitioning the classified linked list, are accessed. The sorted chained list is shared in one or more first sublists based on a first proximity criterion, each one of one or more first sublists containing at least a subset of the node identifiers from the sorted chained list. A first sublist, selected from one or more first sublist, is shared in one or more second sublist based on a second proximity criterion, each of the one or more second sublist containing at least a subset of node ID contained in the first sublist.

In other modalities, for example, as illustrated in Figure 3, a node routing table is populated. An immediate predecessor node is inserted into the routing table. An immediate successor node is inserted into the routing table. Appropriate neighborhood node identifiers are inserted into the routing table, neighborhood nodes are identified from the linked list classified in the first direction as well as in a second, opposite direction, based on a predetermined or estimated neighborhood range and on neighborhood size. Appropriate routing node identifiers are inserted into the routing table, routing nodes being identified from the en10 padlock list classified in both the first and second directions based on the numerical basis and field size of the ID space for the infrastructure federative, the routing nodes representing a logarithmic index of the linked list classified both in the first and in the second direction.

In still other modalities, a node routing table can be populated considering proximity criteria. A predecessor node for each hierarchically shared routing ring in which the current node participates is inserted into a routing table, each hierarchically shared routing ring being shared according to corresponding proximity criteria and containing at least subsets of the bidirectional linked list of a parent ring. A successor node for each hierarchically shared routing ring in which the current node participates is included in the routing table. Neighborhood nodes appropriate for each hierarchically shared routing ring in which the current node participates are inserted into the routing table. Appropriate routing nodes for each hierarchically shared routing ring in which the current node participates are inserted into the routing table.

In other additional modalities, a message is routed, potentially based on one or more proximity criteria defining one or more corresponding classes of nodes, towards a destination node. A receiving node receives a message along with a destination number indicating a destination node and optionally one or more proximity criteria. The receiving node, potentially among nodes in a current class of nodes, determines that it is at least the one numerically more distant from the destination number than a corresponding predecessor node and numerically more distant from the destination number than a successor node corresponding. It is determined that the destination is not in a set of neighborhood nodes, potentially between nodes in the current class of nodes, corresponding to the receiving node.

An intermediate node from a routing table corresponding to the receiving node is identified, the intermediate node being numerically closer to the destination number than other routing nodes in the corresponding routing table. The message is sent to the intermediate node. The intermediate node can continue to route the message. The message eventually reaches the destination node when a node that receives the message is numerically closer to the destination number than its successor or predecessor node. In modalities that perform routing based on one or more proximity criteria, this numerical proximity can be in relation to the nodes in a selected class of nodes.

Thus, routing a message based on proximity criteria includes routing to a destination node (ID) by progressively moving closer to the destination node within a given proximal ring (node ​​class) until no further advances can be made. done by routing within that ring. The determination that no further progress can be made occurs when the destination number is located between the current node ID and the identifiers of its successor or predecessor nodes. At this point, the current node begins to route via its partner nodes to the next largest proximal ring in which it participates. This process of moving progressively towards the destination node through the action of climbing along the partition path towards the root ring ends when the destination node is reached.

Modalities within the scope of the present invention include computer-readable media for driving or having computer-executable instructions or data structures stored therein. Such computer-readable media can be any available media, which can be accessed by a general-purpose or special-use computer system. As an example, and not as a limitation, such computer-readable media may comprise physical storage media such as RAM, ROM, EPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other media that can be used to drive or store a desired program code medium in the form of computer executable instructions, computer readable instructions, or data structures and which can be accessed through a general purpose or special use computer system.

In this description and in the following claims, a network is defined as one or more data connections (of possibly different speeds) that allow the transport of electronic data between computer systems and / or modules (for example hardware and / or software modules ). When information is transferred or provided over a network or other communication connection (whether physical, wireless, or a combination of physical or wireless) to a computer system, the connection is properly viewed as a computer-readable physical medium.

In this way, any such connection is properly designated as a computer-readable physical medium. Combinations of those mentioned above should also be included in the scope of computer-readable media. Computer-executable instructions comprise, for example, instructions and data that cause a general-purpose computer system, or special-purpose computer system, to perform a certain function or group of functions. Computer executable instructions can be, for example, binary, intermediate format instructions such as assembly language, or even source code. In some embodiments, hardware modules, such as, for example, special-purpose integrated circuits or port arrangements, are optimized to implement the principles of the present invention.

In this description and in the following claims, a node is defined as one or more software modules, one or more hardware modules, or combinations of them, that operate together to perform operations on electronic data. For example, the definition of a node includes the hardware components of a personal computer, as well as software modules, such as the operating system of the personal computer. The physical layout of the modules is not important. A node can include one or more computers coupled over a network. Likewise, a node can include a single physical device (such as a mobile phone or PDA), where internal modules (such as a memory and processor) work together to perform electronic data operations. In addition, a node may include special-purpose hardware, such as, for example, a router that includes special-purpose integrated circuits.

Those skilled in the art will consider that the invention can be practiced in network computing environments with many types and configurations of nodes, including personal computers, laptop computers, handheld devices, multi-processor systems, microprocessor-based consumer electronics or programmable, network PC, minicomputers, large computers, mobile telephones, PDA, radio call devices, routers, gateways, brokers, representatives, protection barriers, redirectors, network address translators, and the like. The invention can also be practiced in distributed system environments where local and remote nodes are connected (either through physical data connections, wireless data connections, or through a combination of data connections via wires wireless) over a network, both perform tasks. In a distributed system environment, program modules can be located on memory storage devices, both local and remote.

Federative Architecture

Figure 1 illustrates an example of a federative infrastructure 100. The federative infrastructure 100 includes nodes 101, 102, 103 that can form different types of federation partnerships. For example, nodes 101, 102, 103 can be federated together as non-hierarchical devices without a root node. Each of nodes 101, 102 and 103 has a corresponding ID 171, 182 and 193, respectively.

Generally, nodes 101, 102, 103 can use federation protocols to form partnerships and exchange information (for example, state information related to interactions with other nodes). The formation of partnerships and exchange of information facilitates more efficient and secure access to resources. Other intermediate nodes (not shown) can exist between nodes 101, 102 and 103 (for example, nodes having IDs between 171 and 193). In this way, a message routed, for example, between node 101 and node 103 can be passed through one or more of the other intermediate nodes.

Nodes in federative infrastructure 100 (including other intermediate nodes) may include stacks of corresponding congregational protocols. For example, nodes 101, 102 and 103 include stacks of corresponding congregation protocols 141, 142 and 143, respectively. Each of the protocol stacks 141, 142 and 143 includes an application layer (for example, application layers 121, 122 and 123) and other lower layers (for example, other corresponding lower layers 131, 132 and 133). Each layer in a stack of congregation protocols is responsible for different functionality related to the congregation of a resource request with a corresponding resource.

For example, other lower layers can include a channel layer, a routing layer, and a function layer. Generally, a channel layer is responsible for securely transporting a message (for example, using WS-ReliableMessaging and Simple Object Access Protocol (SOAP)) from one endpoint to another (for example, the from node 101 to node 103). The channel layer is also responsible for processing incoming and outgoing secure message headers and maintaining the state related to secure messaging sessions.

Usually, a routing layer is responsible for computing the next hop towards a destination. The routing layer is also responsible for processing incoming and outgoing addressing and routing message headers and maintaining the routing state. Generally, a function layer is responsible for sending and processing messages and congregation protocol such as membership and disconnection requests, pings, updates, and other messages, as well as generating responses to those messages. The function layer processes request messages from the routing layer and sends back corresponding response messages, if any, to the originating node using the routing layer. The function layer also initiates request messages and uses the routing layer to have request messages delivered.

Generally, an application layer processes non-congregational protocol-specific data distributed from the function layer (that is, application messages). The function layer can access application data from the application layer and obtain and place application data in congregation protocol messages (for example, pings and updates). That is, the function layer can cause the application data to be confirmed in congregation protocol messages and can cause the application data to be passed back to the application layer when receiving the congregation protocol nodes. In some embodiments, application data is used to identify resources and resource interests. In this way, an application layer can include specific application and state logic that processes data received from and sent to other lower layers for the purpose of identifying resources and resource interests.

Federation mechanisms

Nodes can be fed using a variety of different mechanisms. A first federation mechanism includes non-hierarchical nodes sending information to all other non-hierarchical nodes. When a node is about to join a federative structure, the node uses a broadcast / multicast discovery protocol, such as, for example, WS-Discovery to announce its presence and issues a broadcast / multicast location command to detect others we. The node then establishes a simple sending partnership with other nodes already present in the network and accepts new partnerships with newly added nodes. Subsequently, the node simply sends all application-specific messages to all of its partner nodes.

A second federation mechanism includes non-hierarchical nodes that more efficiently transmit application-specific messages to their destination (s). When a new node is about to join a federated infrastructure, the new node uses a broadcast / multicast discovery protocol, such as, for example, WS-Discovery to announce its presence and issues a broadcast / multicast location command to detect other nodes that are part of the federative infrastructure. Upon detection of another node, the new node establishes a partnership with the other node. From the partnership established, the new node becomes aware of the presence of other nodes that are already participating in the federative structure. He then establishes partnerships with these recently recognized nodes and accepts any new partnership requests that arrive.

Both node arrivals / departures and records of interest in certain specific application messages are flooded through the federative infrastructure resulting in each node having global knowledge of other partner nodes and records of interest in specific application messages. With such global knowledge, any node can send application-specific messages directly to the nodes that have expressed interest in the application-specific message.

A third federation mechanism includes non-hierarchical nodes that indirectly send all application-specific messages to their destinations. In this third mechanism, identifiers (ID) are assigned to the nodes, such as, for example, a 128-bit or 160-bit ID. 0 node responsible for keeping records of interest in a particular application-specific message can be determined to be the one whose ID is closest to that obtained by mapping (for example, conversion) the destination identity (for example, URI) of the application message specific to that 128-bit or 160-bit ID space.

In this third mechanism, the arrivals and departures of nodes are flooded through the entire structure. On the other hand, records of interest in certain specific application messages are sent to the nodes determined to be responsible for maintaining such record information. For resizing capability, load compensation, and fault tolerance, the node receiving a registration of interest in certain specific application messages can safely flood that registration information within its neighborhood set. The neighborhood set for a specified node can be determined to be the set of nodes having IDs within a predefined range on either side of the specified node ID.

Similar to the second mechanism, a newly aggregated node uses a broadcast / multicast discovery protocol, such as, for example, WS-Discovery to announce its presence and issues a local broadcast / multicast location command to detect a node that is already part of the federative infrastructure. The new node establishes a partnership with the discovered node and uses that partnership to learn about the presence of other nodes participating in the federative infrastructure. The new node then establishes additional partnerships with the newly discovered nodes15 and accepts any new partnership requests that arrive. The new node accepts records of interest that arrive at specific application layer resources from its partners for which it is responsible and can flood them over its neighborhood set. In this way, messages can generally be sent to the final destination, via intermediate routing nodes (for example, one with which a newly added node has joined or one of which a partner node is aware).

In response to receiving a specific application message that arrives, the new node sends the message to the partner node that may be responsible for maintaining the registration information for the destination specified in the message. Thus, when using this third mechanism, each node in the federative infrastructure has global knowledge of all the other nodes but the registration information is efficiently shared between the nodes. Application-specific messages are transmitted to the final destination via only partner nodes that may be responsible for maintaining the registration information of interest in those application-specific messages. In this way, indirect routes are performed by sending only to the partner node that has global knowledge of the registration information of interest for the message being processed. This is in contrast to the first mechanism where indirect routes are carried out by sending to all partner nodes.

A fourth federation mechanism includes non-hierarchical nodes that route messages to other non-hierarchical nodes. This fourth mechanism differs from the third mechanism at least in that both the arrivals / departures from nodes and the records of interest in certain specific application messages are all routed instead of being flooded. Routing protocols are designed to ensure congregation between application-specific messages and log messages that express interest in those application-specific messages.

Figure 2 illustrates an example of a computer architecture 200 that facilitates routing requests indirectly to partners. Computer architecture 200 illustrates different types of computer systems and devices potentially spread across multiple scopes of local discovery participating in a federated infrastructure.

Workstation 233 can include a registered PnP provider instance. To inform its partners about the presence of this PnP provider instance, workstation 233 routes the registration request 201 through the federative infrastructure. Registration request 201 is initially sent to laptop 231, which in turn sends registration request 201 to message broker 237, which in turn sends registration request 201 to message gateway 241. Message gateway 241 saves registration request 201 of registration information in its database and returns success message 204 to workstation 233.

Subsequently, another registered provider instance, this time the one performing the services, is activated inside workstation 233. This time the node is aware that message gateway 241 is responsible for registrations and sends registration request 205 directly for message gateway 241. 0 message gateway20 gem 241 saves registration request 205 of registration information in its database and returns success message 206 to workstation 233.

Subsequently, printer 236 (for example, a UPnP printer) is turned on and sends notification 207. Server 234 detects notification 207 and routes registration request 208 to message broker 237. Message broker 237 sends the request registration 208 for message gateway 241. Message gateway 241 saves registration request 208 for registration information in its database and returns success message 210 to server 234.

Subsequently, personal computer 242 issues query request 211 to discover all devices. Since personal computer 242 does not know where to send query request 211, it routes query request 211 through workstation 243. Since query and registration requests are routed to the same destination, the routing protocol essentially ensures congregation between the two requests resulting in workstation 243 sending location request 211 to message gateway 241. Message gateway 241 queries the registration information maintained by him and sends the location request 211 to both workstation 233 and server 234. Workstation 233 and server 234 send reply messages 214 and 216 respectively to the personal computer

242 .

This fourth mechanism operates by routing (instead of flooding) a request to the node (message gateway 241) that has global knowledge of the records specified in a request. This fourth mechanism, as will be described in further detail below, essentially guarantees that routing can be performed in 0 (log N) hops, where N is the number of nodes participating in the federative infrastructure. Since this fourth mechanism efficiently shares registration information as well as a node partnership, it scales to very large networks, even the Internet.

Although some federation mechanisms have been described, it will be evident to those skilled in the art, after analyzing this description, that other federation mechanisms are possible.

Relationship between Nodes in a Federation Consequently, a federation consists of a set of nodes that cooperate with each other to form a dynamic and scalable network in which information can be disseminated and located in a systematic and efficient manner. Nodes are organized to participate in a federation as a classified list using a binary relationship that is reflective, anti-symmetric, transitive, total and defined about the domain of node identities. Both ends of the classified list are joined, thereby forming a ring. This way, each node in the list can see itself as being in the middle of the classified list (as a result of using module arithmetic). Additionally, the list is double linked so that any node can scroll through the list in any direction.

Each federation node can be assigned an ID (for example, through a random number generator with duplicate detection) from a fixed set of ID between zero and some fixed upper limit. Thus, adding 1 to a fixed upper limit ID results in an ID of zero (that is, moving from the end of the linked list back to the beginning of the linked list). In addition, a 1: 1 mapping function is defined from the value domain of the node identities to the nodes themselves.

Figure 3 illustrates an exemplary linked list 304 and corresponding ring 306. Given such a ring, the following functions can be defined:

RouteNumerically (V, Msg): Given a value V from the node identities value domain and an Msg message, distribute the message to node X whose identity can be mapped to V using the mapping function.

Neighborhood (X, S): Neighborhood is the set of nodes on either side of node X with cardinality equal to S.

When each node in the federation has global knowledge of the ring, RouteNumerically (V, Msg) is implemented by sending Msg directly to node X, whose i15 dentity is obtained by applying the mapping function to V. Alternatively, when the nodes have limited knowledge of other nodes (for example, only the nodes immediately adjacent), RouteNumerically (V, Msg) is implemented by sending the message to consecutive nodes along the ring until it reaches the destination node X.

Alternatively (and advantageously), nodes can store enough knowledge about the ring to perform a distributed binary search (without having to have global knowledge or implement routing between nodes immediately adjacent). The amount of ring knowledge can be configured in such a way that maintaining the ring knowledge has a sufficiently small impact on each node but allowing for greater routing performance by reducing the number of routing hops.

As previously described, identifiers can be assigned using the &lt;(less than) ratio defined in relation to a limited, sufficiently extensive set of natural numbers, meaning that their range is above a finite set of numbers between 0 and some value fixed, inclusive. In this way, each node participating in the federation is assigned a natural number, which is between 0 and some upper limit, appropriately chosen, inclusive. The range does not have to be airtight and there may be gaps between numbers assigned to the nodes. The number assigned to a node serves as its identity on the ring. The mapping function considers the intervals in the member space by mapping a number between du15 and the node identities to the node whose identity is numerically closest to the number.

This approach has some advantages. By assigning each node a uniformly distributed number, there is a greater likelihood that all segments of the ring will be populated uniformly. Additionally, successor, predecessor, and neighborhood computations can be done efficiently using module arithmetic.

In some modalities, federation nodes are assigned an ID from within such a large ID space so that the chances of assigning the same ID to both nodes are very unlikely (for example, when generating random numbers is used). For example, a node can be assigned an ID in the range of 0 abⁿ - 1, where b is equal, for example, to 8 or 16 and n is equal, for example, to digits equivalent to 128-bits or 160-bits. Consequently, a node can be assigned an ID, for example, from a range of 0 to 16⁴⁰ - 1 (or approximately 1.461502E48). The range of 0 to 16⁴⁰ - 1 would provide, for example, a sufficient number of IDs to be assigned to each node on the Internet, a unique ID.

In this way, each node in a federation can have:

An ID that is a numeric value evenly distributed in the range of 0 abⁿ - 1; and

A routing table consisting of (all arithmetic is done using module bⁿ) ;

Successor node (s);

Predecessor node (p);

Neighborhood nodes (pk,..., Pi, p, s, Si,..., Sj) such that Sj.s.id> (ld + u / 2), j> v / 2-1, and pk.p.id <(id - u / 2), ek> v / 2 - 1; and

Routing nodes r-_(n.₁₎, ..., r._x, rj, ..., rn-J such that r + = RouteNumerically (id + b¹, Mag).

0 where b is the numeric base, n is the field size in number of digits, u is the neighborhood range, v is the neighborhood size, and arithmetic is performed by module bⁿ. For adequate routing efficiency and fault tolerance, values ​​for u and v can be u = b and v> max (log₂ (N), 4), where N is the total number of nodes physically participating in the federation. N can be estimated from the number of nodes present in a ring segment whose length is greater than or equal to b, for example, when there is a uniform ID distribution. Typical values ​​for ben are b = 8 or 16 and n = digits equivalent to 128-bits or 160-bits.

Consequently, the routing nodes can form a logarithmic index covering a ring. Depending on the locations of the nodes in a ring, an accurate logarithmic index is possible, for example, when there is a node in each number in the set of id ± b¹ where i = (1, 2, ... (n-1)). However, it may happen that there are no nodes in each number in the set. In such cases, a node closer to id ± b¹ it can be selected as a routing node. The resulting logarithmic index is not accurate and may even lack unique routing nodes for some numbers in the set.

With reference again to Figure 3, it illustrates an example of a binary relationship between nodes in a federative infrastructure in the form of classified list 304 and corresponding ring 306. The ID space of classified list 304 is in the range 0 to 2⁸ - 1 (or 255). That is, b = 2 and n = 8. Thus, the nodes illustrated in Figure 3 are assigned IDs in a range from 0 to 255. Classified list 304 uses a binary relationship that is reflective, anti-symmetric, transitive, total, and defined in relation to the domain of node identities. Both ends of classified list 304 are joined together, thereby forming ring 306. This makes it possible for each node in Figure 3 to see itself as being in the middle of classified list 304. The ranked list 304 is doubly chained so that any node can traverse the ranked list 304 in any direction. Arithmetic to go through the classified list 304 (or ring 306) is performed using module 2⁸. Thus, 255 (or the end of the ranked list 304) + 1 = 0 (or the beginning of the ranked list 304).

The routing table indicates that the successor to ID 64 is ID 76 (the ID immediately clockwise from ID 64). The successor can change, for example, when a new node (for example, with an ID of 71) joins or when an existing node (for example, ID 76) leaves the federative infrastructure. Also, the routing table indicates that the predecessor of ID 64 is ID 50 (the ID immediately counterclockwise from ID 64). 0 predecessor can change, for example, when a new node (for example, with an ID of 59) joins or when an existing node (for example, ID 50) leaves the federative infrastructure.

The routing table further indicates that a set of neighborhood nodes for ID 64 has IDs 83, 76, 50 and 46. A set of neighboring nodes can be a specified number of nodes (that is, size v of neighborhood) that are within a specified range (i.e., neighborhood u range) of ID 64. A variety of different neighborhood sizes and neighborhood bands, such as, for example, V = 4 and U = 10, can potentially be used to identify the set of neighborhood nodes. A neighborhood set can change, for example, when nodes are added to or disconnected from the federative infrastructure or when the specified number of nodes, or the specified range, is changed.

The routing table further indicates that ID 64 can route to nodes having ID 200, 2, 30, 46, 50, 64, 64, 64, 64, 76, 83, 98, 135, and 200. This list is generated by identification of the nearest node to each number in the set of id ± 2¹ where i = (1, 2, 3, 4, 5, 6, 7). That is, b = 2 and n = 8. For example, the node having ID 76 can be identified from the calculation of the nearest node 64 + 2³, or

72.

A node can route messages (for example, requests for access to resources) directly to a predecessor node, to a successor node, to any node in a set of neighborhood nodes, or to any routing node. In some embodiments, nodes implement a numerical routing function to route messages. In this way, RouteNumerically (V, Msg) can be implemented on node X to distribute Msg to node Y in the federation whose ID is numerically closest to V, and return the ID of node Y to node X. For example, node having ID 64 can implement RouteNumerically (243, Msg) to cause a message to be routed to the node having ID 250. However, since ID 250 is not a routing node for ID 64, ID 64 can route the message for ID 2 (the routing node closest to 243). 0 knot

0 having ID 2 you can in turn implement RouteNumerically (243, Msg) to cause the message to be routed (directly or through additional intermediate nodes) to the node having ID 250. Thus, it may be that a RouteNumerically function is activated in recursively with each activation routing a message closer to the destination.

Advantageously, other embodiments of the present invention facilitate the partitioning of a ring into a ring ring or tree of rings based on a plurality of proximity criteria of one or more categories of proximity (for example, geographical boundaries, routing characteristics (eg example, IP routing hops), administrative domains, organizational boundaries, etc.). It should be understood that a ring can be shared more than once using the same type of proximity criteria. For example, a ring can be shared based on criteria of proximity to continent and based on criteria of proximity to country (both from a category of proximity to geographical boundaries).

Since identifiers can be distributed evenly across an ID space (a result of generating random numbers) there is a high probability that any jump made from a circular ID space will have nodes that belong to different proximity classes provided that these classes have approximately the same cardinality. The probability further increases when there are enough nodes to obtain significant statistical behavior.

0 In this way, neighborhood nodes of any given node are typically well dispersed from the point of view of proximal state. Since the published application state can be replicated between neighborhood nodes, the published information can also be widely dispersed from the point of view of proximal state.

Figure 4 illustrates a ring of rings 400 that facilitates proximal routing. Ring 401 can be seen as a master or root ring, and contains all nodes in each of rings 402, 403 and 404. Each of rings 402, 403 and 404 contains a subset of nodes from ring 401 that are shared based on a specified proximity criterion. For example, ring 401 can be shared based on geographic location, where ring 402 contains nodes in North America, ring 403 contains nodes in Europe, and ring 404 contains nodes in Asia.

In a numerical space containing 65,536 (2¹⁶) ID, route a message from a North American node having a

ID 5.345 for an Asian node having an ID 23.345 may include routing the message within ring 402 until a neighbor node of the Asian node is identified. The neighboring node can then route the message to the Asian node. In this way, a single jump (as opposed to multiple jumps) is made between an American knot and an Asian knot. Consequently, routing is performed in a resource efficient manner.

Figure 5 illustrates an exemplary partition tree induced by proximity of rings 500 that facilitates proximal routing. As illustrated, the ring partition tree 500 includes a number of rings. Each of the rings represents a partition of a sorted linked list. Each ring includes a plurality of nodes having ID in the classified linked list. However for clarity due to the number of potential nodes, the nodes are not expressly illustrated in the rings (for example, the ID space of the partition tree 500 can be b = 16 and n = 40).

Within the partition tree 500, the ring of rays

501 it is shared in a plurality of sub-rings, including sub-rings 511, 512, 513 and 514, based on criterion 571 (a first administrative domain limit criterion). For example, each component of a DNS name can be considered a criterion of proximity to the partial order between them endo induced by their order of appearance in the DNS name read from left to right. Consequently, sub-ring 511 can be further shared in a plurality of sub-rings, including sub-rings 521, 522 and 523, based on criterion 581 (a second administrative domain limit criterion).

Sub-ring 522 can be further shared in a plurality of sub-rings, including sub-rings 531, 532 and 533, based on criterion 572 (a geographical boundary criterion). Location-based proximity criteria can be partially ordered along lines of continents, countries, postal codes, and so on. Postcodes are themselves organized hierarchically meaning that they can be seen as further inducing a partially ordered sublist of proximity criteria.

Sub-ring 531 can be shared additionally in a plurality of sub-rings, including sub-rings 541, 542,

543 and 544, based on criterion 573 (a first organizational boundary criterion). A partially ordered list of proximity criteria can be induced along the lines.details of how a particular company is structured in an organizational way such as divisions, departments, and product groups. Consequently, sub-ring 543 can be further shared in a plurality of sub-rings, including sub-rings 551 and 552, based on criterion 583 (a second organizational boundary criterion).

Within partition tree 500, each node has a unique ID and participates in rings along a corresponding partition path starting from the root to a leaf. For example, each node participating in sub-ring 552 would also participate in sub-rings 543, 531, 522, 511 and root 501.

Routing to a destination node (ID) can be performed by implementing a RouteProximally function, as follows:

RouteProximally (V, Msg, P): Given a value of V from the domain of node identities and an Msg message, distribute the message to node Y whose identity can be mapped to V among the nodes considered equivalent by the proximity criteria P .

In this way, routing can be carried out by gradually moving closer to the

0 destination within a given ring until no further progress can be made by routing within that ring as determined from the condition that the destination node is located between the current node and its successor or predecessor node. At this point, the current node starts team25 through its partner nodes in the next largest ring in which it participates. This process of progressive displacement towards the destination node by scaling along the partition path towards the root ring ends when the node closest to the destination node is reached within the requested proximal context, as originally specified in the activation of RouteProximally.

Routing hops can remain in the proximal neighborhood of the node that originated the request until no further progress can be made within that neighborhood because the destination node exists outside the neighborhood. At this point, the proximity criterion is relaxed to increase the size of the proximal neighborhood to make further progress. This process is repeated until the proximal neighborhood is sufficiently expanded to include the destination node (ID).

The routing jump made after each successive relaxation of the proximal neighborhood criterion can be a potentially larger jump in proximal space while making a correspondingly smaller jump in the numerical space compared to the previous jump. In this way, only the absolutely required number of such hops (between rings) is made before the destination is reached.

It may be the case that some hops are avoided for query messages since the published application data is replicated downwardly in the partition tree when it is replicated between the target node's neighborhood nodes.

To perform proximal routing, each federation node maintains references to its successor and predecessor nodes in all rings in which it participates as a member (similar to the successor and predecessor to a single ring) - the proximal predecessor, proximal successor, and vizi39 proximal change. To make routing efficient, nodes can also maintain reference to other nearest nodes at an exponentially increasing distance in any one of their half rings as routing partners (similar to single ring routing nodes). In some embodiments, the routing partner nodes that are located between a pair of consecutive successor or predecessor nodes participate in the same lowest ring shared by the current node and the node numerically closest to it among the pairs of successor or predecessor nodes, respectively. In this way, routing hops towards a destination node transit using a relaxed proximity criterion (ie, transit to an upper ring) only when absolutely necessary to make further progress. Consequently, messages can be efficiently brought together with a corresponding federation node.

In some embodiments, nodes implement a proximal routing function to route messages based on relations of equivalence criteria. Thus, given

0 a V number and an Msg message, a node can implement RouteProximally (V, Msg, P) to distribute the message to node Y whose identity can be mapped to V among the nodes considered equivalent by the proximity criterion P. The proximity criterion P identifies the lowest ring in the partition tree that is the common predecessor of all nodes considered by it to be proximally equivalent.

It can be represented as a sequence obtained by concatenating the proximity criterion found along the path from the root ring to the ring identified by it, separated by the path separator character /. For example, the proximity criterion identifying sub-ring 542 can be represented as prox5 mity: /. COM / Corp2 / LocationA / Div2. Each ring in the partition tree 500 can be assigned a unique number, for example, by converting its representative sequence with an algorithm based on SHA. If the number 0 is reserved for the root ring, it can be deduced that RouteNumerically (V,

Msg) = RouteProximally (V, Msg, 0).

For example, a node in sub-ring 544 can implement

RouteProximally to identify a nearest node in sub-ring 531 (for example, for a node in sub-ring 513). In turn, sub-ring 531 can implement RouteProximally to i15 dentify a nearest node in sub-ring 522. Likewise, sub-ring 522 can implement RouteProximally to identify a closer node in sub-ring 511. Likewise, sub-ring 511 can implement RouteProximally to identify a nearest node in ring 501. Thus, it may be that a RouteProximally function is activated recursively with each activation routing a message closer to the destination.

Thus, when proximity criteria are considered, routing hops on a path to the final destination can remain within the proximity of a node originating a request, while making significant progress between the source node and the destination node in one space numeric, until the destination node is reached or no further progress can be made under the chosen proximity criterion at which point it is relaxed just enough to make additional progress towards the destination. For example, the proximity criterion can be relaxed enough that a message is routed from ring 531 to ring 522, etc.

Using the approach above for proximity, it is possible to confine information published in a given ring. For example, organizations may like to ensure that specific organization information is not available to identities outside their trusted domains whether it is (1) implicitly in the form of neighborhood replication for nodes outside their domains or (2) explicitly in the form of fulfillment of consultation requests for such information. 0 first aspect is satisfied by replicating published information only between nodes neighboring the target ID within the specific ring. Because all messages originating from a node are routed by successively scaling the rings to which it belongs towards the root ring, there is a high probability that all query requests originating within an organization will be able to locate the published information confined to it thereby implicitly satisfying the second aspect.

In addition, organizations do not like us au2 5 tacticly federating with us outside their domain of trust. This can happen, for example, when a visiting salesperson connects his laptop computer to the network on the customer's premises. Ideally, the laptop computer belonging to the seller intends to locate information published in his home domain and / or federate with nodes in his home domain starting at his preferred lowest proximity ring. He will typically not be allowed to deal with nodes in the customer's domain. Supporting this scenario requires the ability to locate seed nodes in the domestic domain. Such seed nodes can be used to locate information published in the domestic domain, to join the domestic federation, and selectively import and export information published through the domains. Seed nodes are also sometimes referred to as message gateways.

In other modalities, an entity publishes references to seed nodes in the root ring. Seed nodes can be published in the singular number (such as that obtained by converting their representative sequence) associated with the ring (as a target ID). Seed node information can be additionally cached on demand by the nodes in various rings that are in the path of the corresponding target teeth in the root ring. Such on-demand caching provides improved performance and reduction in hotspots that could occur when semi-static information is consulted very frequently. Seed node information can also be obtained through other means such as DNS.

To provide fault tolerance for confined published information, each node can maintain a neighborhood set of nodes in all rings in which it participates. Given the above, the state maintained by a node can be summarized as follows:

• An ID which is a numerical value distributed evenly in the range of 0 abⁿ-l.

• A routing table consisting of (all a5 rhythm is done per module bⁿ) :

oFor each ring, say ring d, in which the node participates

Successor node (s_d)

Predecessor node (p_d)

Neighborhood nodes (ρω,..., Pid, ​​Pd / s_debt Si_d, · · · ,

Sjd) such that Sj_d.s_d.id> (id + u / 2), j> v / 2-1,

Pkd-Pd-id <(id - u / 2), ek> v / 2-1.

o Routing nodes (r._(n-u, ..., r._x, laugh, ..., r_n-i) such that r * i = RouteProximally (id ± b¹, updateMag, d) such that s_d &lt;id + b¹ &lt;sd + i or pd + i &lt;id - b¹ &lt;pd as appropriate.

where b is the numeric base, n is the field size in number of digits, u is the neighborhood range, and v is the neighborhood size.

0 Note that a subset of neighborhood nodes maintained by a given node in ring d may appear again as neighborhood nodes in child ring d + 1 in which the given node also participates. As such, one can derive the upper limit on the total number of neighborhood nodes maintained by a given node through all D rings in which it participates as D * max (u, v) / 2. This considers that only a reference to a given node is maintained and in the worst case the upper limit is for a balanced tree.

It should be noted that when a ring is shared in several corresponding sibling sub-rings, a specific node is allowed to participate simultaneously in more than one of the plurality of corresponding sibling sub-rings, for example, through cognomination. Cognomination can be implemented to associate a different state, for example, from different sub-rings, to the specific node. Thus, although alternative names for a given node have the same ID, each alternative name may have been distinct as10 associated with them. Cognomination allows the specified node to participate in multiple rings having distinct proximity criteria that are not necessarily common predecessors of more specific proximity criteria. That is, the specified node can participate in multiple branches of the proximity tree.

For example, a dual NIC laptop (both physical and wireless) can be considered to be equivalent proximally to both other wireless and physical nodes sharing the same LAN segments as the laptop. However, these two distinct proximity criteria can be modeled as sub-criteria that are applicable only after applying a different higher priority proximity criterion, such as, for example, one based on organizational member quality. Since the laptop belongs to the same organization, the nodes are named in the two sub-rings representing; 1) membership quality in the physical connection, and 2) membership quality in the wireless LAN segment; they merge into a single node in the ring representing the organization to which the laptop belongs. It should be understood that RouteProximally operates as expected without any changes in the presence of alternative names.

Each proximal ring can be configured according to 5 (potentially different) ring parameters. Ring parameters can be used to define a neighborhood (for example, ring parameters can represent a neighborhood range, a neighborhood size, ping message and start message, timing and distribution patterns for ping and start messages), indicate a specific federation mechanism (for example, from the first to four federation mechanisms described above previously or from other federation mechanisms), or define details of communication between routing partners on the same proximal ring. Some ring parameters can be more general, applying to a plurality of different federation mechanisms, while other ring parameters are more specific and apply to a specific type of federation mechanism.

0 Ring parameters used to configure a top level proximal ring can be inherited, in some embodiments, by the lower level proximal rings. For example, it may be that ring 543 inherits from some of the ring parameters of ring 531 (which in turn inherited from the ring

522, etc.). Thus, a neighborhood size and a neighborhood strip, associated with ring 531, are also associated with ring 541.

However, inherited ring parameters can be changed and / or proximal rings can be individually configured according to different ring parameters. For example, it may be that ring 511 is for an administrative domain that contains a large number of nodes and therefore the fourth federation mechanism described above is more appropriate for ring 511. On the other hand, it may be that ring 521 is for a small company with a relatively smaller number of nodes and therefore the second federation mechanism described above is more appropriate for ring 521. Thus, the ring parameters associated with the ring 521 can be set to (or inherited parameters changed to) values ​​other than the ring parameters associated with ring 511. For example, a ring parameter indicating a specific type of federation mechanism may be different between rings 511 and 521. Similarly, parameters defining a neighborhood may be different between rings 511 and 521. Additionally, ring 521 can be configured according to specific parameters that are specific to the second federation mechanism described above, while the ring

511 it is configured according to additional specific parameters that are specific to the fourth federation mechanism described above.

Consequently, proximal rings can be flexibly configured based on the characteristics (eg number, included features, etc.) of nodes in the proximal rings. For example, an administrator can select ring parameters for proximal rings using a configuration procedure (for example, through a user interface). A configuration procedure can facilitate the configuration of inheritance relationships between proximal rings as well as the configuration of individual proximal rings, such as, for example, canceling otherwise inherited ring parameters.

Figure 8 illustrates an exemplary method 800 flowchart for sharing nodes in a federated infrastructure. Method 800 will be described with respect to the partition rings of a tree 500 in Figure 5. Method 800 includes an action of accessing a classified linked list containing the node identifiers that have been assigned to the nodes in a federative infrastructure (action 801). For example, the classified linked list represented by ring 501 can be accessed. The node identifiers of the classified chained list (the nodes illustrated in ring 501) can represent nodes in a federative infrastructure (for example, federative infrastructure 100).

Method 800 includes an action to access proximity categories that represent a plurality of different proximity criteria to share the classified linked list (action 802). For example, proximity criteria representing domain boundaries 561, geographical boundaries 562, and organizational boundaries 563 can be accessed. However, other proximity criteria, such as confidence domain limits, can also be represented in the accessed proximity criterion. Proximity categories can include previously created partially ordered lists of proximity criteria. A ring can be shared based on partially ordered lists of proximity criteria.

method 800 includes an action of sharing the linked list classified into one or more first sublists based on a first proximity criterion, each of the one or more first sublists containing at least a subset of node identifiers from the classified linked list ( action 803). For example, ring 501 can be shared into sub-rings 511, 512, 513 and 514 based on criterion 571. Each sub-ring 511, 512, 513 and 514 can contain a different subset of node ID from ring 501.

Method 800 includes an action to share a first sublist, selected from one or more first sublists, in one or more second sublists based on a second proximity criterion, each of the one or more second sublists containing at least a subset of Node ID contained in the first sublist (action 804). For example, sub-ring 511 can be shared in sub-rings 521, 522 and 523 based on criterion 581. Each of sub-rings 521, 522 and

523 it may contain a different subset of node ID from sub-ring 511.

Figure 9 illustrates an exemplary flow chart of a 900 method for populating a node routing table. Method 900 will be described with respect to the chained list classified 304 and ring 306 in Figure 3. Method 900 includes an action of inserting a predecessor node in a routing table, the predecessor node preceding a current node in relation to the current node in a first direction of a classified chained list (action 901). For example, the node having ID 50 can be inserted into the routing table as a predecessor to the node having ID 64 (the current node). Moving in a clockwise direction 321 (from end A of the en5 padlock list classified 304 towards end B of the chained list classified 304), the node having ID 50 precedes the node having ID 64. Inserting a predecessor node can establish a symmetric partnership between the current node and the predecessor node in such a way that the current node is a partner of the predecessor node and the predecessor node is a partner of the current node.

Method 900 includes an action of inserting a successor node in the routing table, the successor node succeeding the current node in relation to the current node in the first direction in the classified linked list (action 902). for example, the node having

ID 76 can be inserted in the routing table as a successor to the node having ID 64 (the current node). Moving in a counterclockwise direction 322, the node having ID 76 succeeds the node having ID 64. Inserting a successor node can establish a symmetric partnership between the current node and the successor node of

0 such that the current node is a partner of the successor node and the successor node is a partner of the current node.

Method 900 includes an action of inserting appropriate neighborhood nodes into the routing table, the neighborhood nodes identified from the linked list classified in both the first and opposite directions based on a neighborhood strip and neighborhood size (action 903). For example, nodes having ID 83, 76, 50 and 46 can be inserted in the routing table as neighborhood nodes for the node having ID 64 (the current node). Based on a neighborhood strip of 20 and a neighborhood size of 4, nodes having ID 83 and 76 can be identified in the clockwise direction 321 and nodes having ID 50 and 46 can be identified in the counterclockwise direction 322 (moving from end B of the ranked chain list 304 towards end A of the ranked chain list 03 04). In some environments, it may be that no appropriate neighborhood node is identified. Inserting a neighborhood node can establish a symmetric partnership between the current node and the neighborhood node in such a way that the current node is a partner of the neighborhood node and the neighborhood node is a partner of the current node.

method 900 includes an action of inserting appropriate team nodes in the routing table, the routing nodes identified from the linked list classified in the first as well as in the second direction based on the numerical base and the field size of the ID space for the infrastructure federative, the routing nodes represent a logarithmic index of the linked list classified both in the first and in the second direction (action 904). For example, nodes having ID 200, 2, 30, 46, 50, 64, 64, 64, 64, 64, 76, 83, 98, 135 and 200 can be inserted in the routing table as routing nodes for the node having ID 64. Based on the numerical base 2 and the field size of 8 the nodes having ID 64, 64, 76, 83, 98, 135 and 200 can be identified in the 321 direction and the nodes having ID 64, 64, 50 , 46, 30, 2 and 200 can be identified in direction 322. As illustrated within ring 306, the routing rings represent a logarithmic index of the ranked chained list 304 both clockwise 321 and counterclockwise 322. Inserting a routing node can establish a symmetric partnership between the node current and the routing node such that the current node is a partner of the routing node and the routing node is a partner of the current node.

Figure 7 illustrates an exemplary flowchart of a method 700 for populating a node routing table that considers proximity criteria. Method 700 will be described with respect to the rings in Figure 5. Method 700 includes an action of inserting a predecessor node for each hierarchically shared routing ring in which the current node participates in a routing table (action 701). Each predecessor node precedes the current node in a first direction (for example, clockwise) within each hierarchically shared routing ring in which the current node participates. The hierarchically shared routing rings are shared according to corresponding proximity criteria and contain at least subsets of a bidirectionally linked list (and possibly the integral bidirectionally linked list). For example, it may be that a specified node participates in the root ring 501 and sub-rings 511, 522, 523, 531 and 542. Thus, a predecessor node is selected for the specified node from within each of the 501 rings and sub-rings 511, 522, 523, 531 and 542.

Method 700 includes an action of inserting a successor node for each hierarchically shared routing ring in which the current node participates in the routing table (action 702). Each successor node succeeding the current node in the first direction within each hierarchically shared routing ring in which the current node participates. For example, the successor node is selected for the specified node from within each of rings 501 and sub-rings 511, 522, 523,

531 and 542.

Method 700 includes an action of inserting appropriate neighborhood nodes for each hierarchically shared routing ring10 in which the current node participates in the routing table (action 703). Neighborhood nodes can be identified either in the first direction (for example, clockwise) or in an opposite second direction (for example, counterclockwise) based on a neighborhood strip and neighborhood size from the rings hierarchically shared routing systems in which the current node participates. For example, neighborhood nodes can be identified for the specified node from within each of rings 501 and sub-rings 511, 522, 523, 531 and 542.

0 Method 700 includes an action of inserting appropriate routing nodes for each hierarchically shared routing ring in which the current node participates in the routing table (action 704). For example, routing nodes can be identified for the specified node from within each of rings 501 and sub-rings 511, 522, 523,

531 and 542.

In some modalities, appropriate routing nodes are inserted for each proximity ring d except the leaf ring (or leaf rings in modalities that use alternative names), in which node Y participates. Appropriate routing nodes can be inserted based on the following expression (s):

if Ys_d.id &lt;Y.id + b¹ &lt;Ys_{d +}i.id is true, then use ring d; or if Yp_d.id &lt;Y.id - b¹ &lt;Yp_{d +}i.id is true, then use ring d.

If a ring was not identified in the previous step, use the leaf ring (for example, ring 501) as ring d. Now, ring d is the proximity ring on which node Y should look for the routing partner closest to z.

Figure 10 illustrates an exemplary flowchart of a method 100 0 for routing a message towards a destination node. Method 1000 will be described with respect to the ranked list 304 and ring 306 in Figure 3. The method

1000 includes an action by a receiving node to receive a message along with a number indicating a destination (action 1001). For example, the node having ID 64 can receive a message indicating a destination of 212.

Method 1000 includes an action of determining that the receiving node is at least one node numerically more distant from the destination than a corresponding predecessor node and numerically more distant from the destination than a corresponding successor node (action 1002). For example, in direction 322, ID 64 is further away from destination 212 than ID 50, and in direction 321, ID 64 is further away from destination 212 than ID 76. 0 Method 1000 includes an action to determine if the destination is not within a neighborhood set of nodes corresponding to the receiving node (action 1003). For example, the node with ID 64 can determine that destination 212 is not within the neighborhood set of 83, 76, 50 and 46.

0 method 1000 includes an action of identifying an intermediate node from a routing table corresponding to the receiving node, the intermediate node being numerically closer to the destination than other routing nodes in the corresponding routing table (action

1004). For example, the node having ID 64 can identify the routing node having ID 200 as being numerically closer to destination 212 than other routing nodes. Method 1000 includes an action of sending the message to the intermediate node (action 1005). For example, the node having ID 64 can send the message to the node having ID 200.

Figure 11 illustrates an exemplary flow chart of a method 110 0 to route a message towards the destination node based on the proximity criteria. The 1100 method will be described with respect to the rings in Figure 4 and Figure 5.

Method 1100 includes an action of a receiving node receiving a message along with a number indicating a destination and a proximity criterion (action 1101). The proximity criterion defines one or more classes of nodes. The receiving node receives the message as part of a current class of nodes selected from one or more classes of nodes based on proximity criteria. For example, the node having ID 172 can receive a message indicating a destination of 201 and proximity criteria indicating that the destination node is part of classes represented by ring 401. The node having ID 172 can receive the message as part of the ring 404.

Method 1100 includes an action of determining that the receiving node is at least one of, numerically more distant from the destination than a corresponding predecessor node, and numerically more distant from the destination than a corresponding successor node, among nodes in a selected class of us (action 1102). For example, within ring 404, the node with ID 172 is further from the destination 201 than the node having ID 174 in the clockwise direction is further from the destination 211 than the node having ID 153 in the anti-direction. -schedule.

Method 1100 includes an action to determine that the destination is not within the neighborhood set of the receiving node among the nodes for any one or more classes of nodes defined by the proximity criterion (action 1103). For example, the node having ID 172 may determine that destination 210 is not in a corresponding neighborhood set in ring 404 or ring 401.

Method 1100 includes an action of identifying an intermediate node from the receiving node's routing table, the intermediate node being numerically closer to the destination than other routing nodes in the routing table (action 1104). For example, the node having ID 172 may identify the node having ID 194 as being numerically closer to destination 201 than other routing nodes in ring 404. 0 Method 1100 includes an action of sending the message to the intermediate node (action 1105). For example, the node having ID 172 can send the received message to the node having ID 194. The node having ID 172 can send the received message to the node having ID 194 to respect a partially ordered, previously defined list of proximity criteria. .

Node 194 can be as close to destination 201 as possible within ring 404. In this way, the proximity can be relaxed just enough to allow additional routing towards the destination to be done at a10 level 401 in the next leg. That is, routing is carried over from ring 404 to ring 401 since no further progress towards the destination can be made on ring 404. Alternatively, it may be that the node having ID 201 is within the vicinity of the node having ID 194 in ring 401 resulting in no further routing. Thus, in some modalities, relaxing the proximity criteria to reach the next upper ring is enough to cause additional routing.

However, in other modalities, incremental relaxation of the proximity criteria causing transition to the next upper ring continues until additional routing can occur (or until the root ring is found). That is, several transitions to upper rings occur before further routing progress can be made.

For example, with reference now to Figure 5, when no further routing progress can be made on ring 531, the proximity criteria can be relaxed enough to transition to ring 511 or even to root ring 501.

Figure 6 and the following discussion are intended to provide a brief, generic description of a suitable computing environment in which the invention can be implemented.

Although not required, the invention will be described in the general context of instructions executable by computer, such as program modules, being executed by computer systems. Program modules generally include routines, programs, objects, components, data structures, and the like, which perform specific tasks or implement specific abstract data types. Computer executable instructions, associated data structures, and program modules, represent examples of the program code medium for performing actions of the methods discussed here.

Referring to Figure 6, an exemplary system for implementing the invention includes a general purpose computing device in the form of a computer system 620, including a processing unit 621, a system memory 622, and a system bus 623 that couples various system components including system memory 622 to processing unit 621. The processing unit 621 can execute executable computer instructions designed to implement features of the 620 computer system, including features of the present invention. The system bus 623 can be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. System memory includes 624 read memory (ROM) and random access memory (RAM)

625. A basic input / output system (BIOS) 626, containing the basic routines that assist in transferring information between elements within the computer system 620, such as during startup, can be stored in ROM 624.

The computer system 620 may also include magnetic hard disk drive 627 to read from, and write to the magnetic hard disk 639, magnetic disk drive 628 to read from, or write to the removable magnetic disk 629, and disk drive. optical disk 630 to read from or write to the removable optical disk 631, such as, for example, a CD-ROM or other optical media. The 627 magnetic hard disk drive, magnetic disk drive

628, and optical disk drive 63 0 are connected to the system bus 623 via hard disk interface 632, magnetic disk drive interface 633, and optical drive interface 634, respectively. The drives and their associated computer-readable media provide non-volatile storage of computer-executable instructions, data structures, program modules, and other data for the 620 computer system. Although the exemplary environment described here employs magnetic disk drive 639, removable magnetic disk 629 and removable optical disk 631, other types of computer-readable media for data storage can be used, including magnetic cassettes, flash memory cards, digital versatile disks , Bernoulli cartridges, RAM, ROM, and the like.

Program code means comprising one or more program modules may be stored on hard disk 639, magnetic disk 629, optical disk 631, ROM 624 or

RAM 625, including an operating system 635, one or more application programs 636, other program modules 637, and program data 638. A user can enter commands and information into computer system 620 via keyboard 640, pointing device 642, or other input devices (not shown), such as, for example, a microphone, joystick, gaming table, scanner or the like. These and other input devices can be connected to the processing unit 621 via the input / output interface 646 coupled to the system bus 623. The input / output interface 646 logically represents any of a wide variety of different interfaces, such as, for example, a serial port interface, a PS / 2 interface, a parallel port interface, a Universal Serial Bus interface (USB), or an interface

Institute of Electrical and Electronics Engineers (IEEE) 1394 (ie, a Protection Barrier interface), or it can even logically represent a combination of different interfaces.

A 647 monitor or other video device is also connected to the 623 system bus via the 648 video interface. 669 speakers or another audio output device is also connected to the 623 system bus via the 649 audio interface. Other output peripheral devices (not shown), such as, for example, printers, can also be connected to the 620 computer system.

The computer system 62 0 can be connected to 5 networks, such as, for example, a corporate or office computer network, a home network, an intranet and / or the Internet. The computer system 620 can exchange data with external sources, such as, for example, remote computer systems, remote applications, and / or remote database10 through such networks.

The computer system 620 includes network interface 653, through which the computer system 620 receives data from external sources and / or transmits data to external sources. As illustrated in Figure 6, the network interface 653 facilitates data exchange with the remote computer system 683 via connection 651. The network interface 653 can logically represent one or more software and / or hardware modules, such as, for example, a network interface card and a corresponding Network Trigger Interface Specification (NDIS) stack. Link 651 represents a part of a network (for example an Ethernet segment), and remote computer system 683 represents a node in the network.

Similarly, computer system 620 includes input / output interface 646, through which computer system 620 receives data from external sources and / or transmits data to external sources. The input / output interface 646 is coupled to modem 654 (for example a standard modem, a cable modem, a digital subscriber line modem (DSL)) via connection 659, through which the computer system 620 receives data from from and / or transmit data to external sources. As shown in Figure 6, input / output interface 646 and modem 654 facilitate data exchange with remote computer system 693 via connection 652. Connection 652 represents a part of a network and remote computer system 693 represents a network node.

Although Figure 6 represents a suitable operating environment for the present invention, the principles of the present invention can be employed in any system that is capable of, with appropriate modification, if necessary, implementing the principles of the present invention. The environment illustrated in Figure 6 is only illustrative and in no way represents even a small part of the wide variety of environments in which the principles of the present invention can be implemented.

According to the present invention, nodes, application layers, and other lower layers, as well as associated data, including routing tables and node ID, can be stored and accessed from any of the computer-readable media associated with the 620 computer system. For example, parts of such modules and parts of associated program data can be included in operating system 635, application programs 636, program modules 63 7 and / or program data 63 8, for storage in system memory 622.

When a mass storage device, such as, for example, magnetic hard disk 639, is coupled to the computer system 62 0, such modules and associated program data can also be stored in the mass storage device. In a network environment, program modules illustrated with respect to computer system 62 0, or parts thereof, may be stored on remote memory storage devices, such as system memory storage devices and / or associated with the remote computer system 683 and / or remote computer system 693. The execution of such modules can be performed in a distributed environment as previously described.

The present invention can be incorporated in other specific forms without departing from its spirit or essential characteristics. The described modalities should be considered in all aspects only as illustrative and not restrictive. The scope of the invention is, therefore, indicated by the appended claims more properly than by the previous description. All changes, included in the defined sig20 and equivalence range of the claims, must be included in its scope.

• » ·

<img file="BRPI0504513A_D0002.tif" />