Method for end point identification in computer networks

Computer networks may have many physical or virtual servers interconnected to each other by routers, switches, bridges, or other network nodes via wired or wireless network links. Network nodes can be allowed to communicate between servers by exchanging messages over network links according to one or more network protocols.

One of the difficulties in designing and operating computer networks is scalability. As the number of services increases, so does the amount of resources required and operational complexity. For example, modern routers usually have a routing table in memory to route the network to reach a particular server in the computer network. As the number of servers increases, the size of the routing table and the complexity of calculating network routes to the routing table increase. Therefore, when the number of servers reaches millions or tens of millions, both the hardware cost and operational complexity of the router can increase to unmanageable levels.

This overview provides a simplified introduction to the selection of concepts described in more detail below in the details of the invention. This summary is not intended to identify the important or essential features of the claimed invention-specificity, nor is it intended to be used or intended to limit the scope of the claimed invention-specificity.

Extending a computer network to millions of servers, virtual machines, or other endpoints can be difficult based on existing network technology. As the number of endpoints increases, hardware costs and operational complexity can increase to unmanageable levels. For example, computing a network route between millions of endpoint pairs can require a lot of computing power, resulting in the routing table exceeding the capacity of the router's memory. It could also be. In other examples, it can be difficult to implement network traffic management techniques (eg, traffic engineering or load balancing) on millions or tens of millions of endpoints. For example, calculating network routes (or tunnels) for traffic engineering, allocating network bandwidth to traffic engineering tunnels, or other similar nondeterministic-polynomial. The complete) ("NP-complete") problem can become more difficult as the number of endpoints increases.

Some embodiments of the present technology partition a computer network into separate physical or overlay domains interconnected with each other within a hardware or software-defined hierarchy. Can improve the scalability of computer networks. Control plane functions (eg, network route calculation) and / or forwarding plane functions (eg, routing, forwarding, switching) are partitioned and (1) network configurations for a particular domain (eg,). , Endpoints within a particular domain and / or lower bell domains), and (2) separate on a per-domain basis based on one or more higher level domains connected to a particular domain in a hierarchical structure Is executed. Therefore, a particular domain can manage various network operations of the domain without worrying about endpoints or network nodes in other domains in the hierarchy. As a result, network configurations and operations can be partitioned, reducing hardware costs and operational complexity, even as the size of the entire computer network increases. Other embodiments of the technique are intended to identify endpoints in a computer network based on at least a portion of the physical location where each endpoint is located.

<figref num="1A">It is the schematic explaining the hierarchical partitioning of a computer network by embodiment of this technique.</figref><figref num="1B">It is the schematic explaining the hierarchical partitioning of a computer network by embodiment of this technique.</figref><figref num="2">It is a schematic diagram explaining the application example of the hierarchical partitioning technique shown in FIG. 1A to the computer network for one or more data centers according to the embodiment of this technique.</figref><figref num="3">It is the schematic explaining the operation of the computer network of FIG. 2 using the example of the endpoint identifier by the embodiment of this technique. Part of the computer network in Figure 2 has been omitted for clarity.</figref><figref num="4">It is a block diagram which shows the example of the software component of the network controller of FIG. 3 by embodiment of this technology.</figref><figref num="5A">It is a block diagram explaining an example of an endpoint identifier having a section arranged in a stack by embodiment of this technique.</figref><figref num="5B">It is a block diagram explaining an example of an endpoint identifier having a section arranged in a stack by embodiment of this technique.</figref><figref num="6">It is a block diagram illustrating an example of one of the sections of FIG. 5A or FIG. 5B according to an embodiment of the present technology.</figref><figref num="7">It is the schematic explaining one example of the endpoint identifier using the IP address by embodiment of this technique.</figref><figref num="8">It is a flowchart explaining the embodiment of the process which constitutes the partition computer network by the embodiment of this technique.</figref><figref num="9A">It is a flowchart explaining the embodiment of the process which manages the outbound communication in a domain by the embodiment of this technology.</figref><figref num="9B">It is a flowchart explaining the embodiment of the process which manages the inbound communication in a domain by the embodiment of this technology.</figref><figref num="10">A suitable computing device for the components of the computer network example in Figure 1A.</figref>

Several embodiments of systems, devices, components, modules, routines and processes for configuring and operating a computer network are described below. In the following description, specific details of the components are included to provide a complete understanding of some embodiments of the technique. Those skilled in the art will also understand that the art can have additional embodiments. The technique can also be implemented without some details of the embodiments described below with reference to FIGS. 1A-10.

As used herein, the term "computer network" generally refers to interconnects with multiple network nodes where multiple endpoints are connected to each other and to other networks (eg, the Internet). Refers to the network. The term "network node" generally refers to a network device in a physical or software embroidery transfer path. Examples of network nodes are routers, switches, hubs, bridges, load balancers, security gateways, firewalls, network name translators, or name servers. Each network node can be associated with a network node identifier that has a distinct value within the computer network.

As also used herein, the term "control plane" for computer networks is generally associated with determining where and / or how network traffic is carried within the computer network. Refers to a part of the architecture. The control plane includes the calculation, configuration and / or management of routing or forwarding tables within a centralized controller or network node using distributed routing or forwarding protocols such as BGP, OSPF, ISIS, LDP, RSVP. Other control plane features include bandwidth allocation, traffic management, congestion control, network route protection calculations, disaster recovery, system configuration, management, analytics, and / or other network operations.

The term "forwarding plane" in a computer network generally refers to another part of the network architecture that carries network traffic. The forwarding plane forwards network traffic to the next hop along a network route or forwarding path established according to control plane logic or protocol. Forwarding plane packets travel through network nodes and use the tables established by the control plane to route, switch, and forward messages such as packets at each network node.

The term "end point" generally refers to physical or software embroidery computing devices. Examples of endpoints include network servers, network storage devices, personal computers, mobile computing devices (eg, smartphones), or virtual machines. Each endpoint can be associated with an endpoint identifier that can have a separate value in the computer network. An example of an endpoint identifier (or network node identifier) is Multiprotocol Label Switched (MPLS). switched) ") Some of the labels used in the network, the stack of labels used in the MPLS network, one or more addresses according to the Internet Protocol (" IP "), one or more virtual IP addresses, virtual local area networks Includes one or more tags in, one or more media access control addresses, one or more lambda identifiers, one or more connection paths, one or more physical interface identifiers, or one or more packet headers or envelopes.

The term "domain" generally refers to the physical or logical partition of a computer network. A domain can include a selected number of network nodes in a computer network that are interconnected to each other and / or interconnected with many endpoints. Domains can also connect to one or more higher level domains, including many additional network nodes that connect a particular domain to other domains, at the same or different levels within the domain hierarchy. In the following description, a software defined network (SDN) using one or more SDN controllers is used to describe an embodiment of computer network partitioning. However, in another embodiment, one or more domains of the computer network is a distributed computer network that uses distributed routing and / or forwarding protocols, at least in part.

Individual network nodes and endpoints within a domain can individually contain a forwarding table that specifies the method of forwarding messages (eg, data packets) to another endpoint in the computer network. In certain embodiments, the forwarding table contains a plurality of entries that separately identify a network route, a forwarding path, a physical interface, or a logical interface that correspond to a particular value of the endpoint identifier. be able to. An example entry can have an appropriate value for each identifier, as shown below.<tables num="1"><img file="JP6628792B2_D0001.tif" /></tables>In certain embodiments, the incoming identifier and the outgoing identifier can have different values. In this way, at least one part of the endpoint identifier can be changed in conjunction with message forwarding from the network node. In another embodiment, the receive and send identifiers may have the same value, and an example entry can be shown below instead:<tables num="2"><img file="JP6628792B2_D0002.tif" /></tables>In a further embodiment, the forwarding table can include multiple entries that individually reference entries in one or more other tables based on a particular value of the endpoint identifier.

Extending a computer network to interconnect many endpoints can be difficult or even impossible based on existing network technology. For example, network routing calculations between millions of endpoint pairs in a computer network can result in a routing table that exceeds the memory capacity of any existing router. In another example, it can be difficult to perform traffic engineering techniques because the calculation of the traffic engineering tunnel is NP-complete.

In some embodiments of the present technology, the scalability of a computer network can be improved by partitioning the computer network into separate domains interconnected with each other in the hierarchy. Each domain can include a manageable number of endpoints (eg, 256, 512, 1024, or any other suitable number) that are individually identified by the endpoint identifier. In certain embodiments, the endpoint identifier can have a particular domain and a separate value corresponding to the endpoint within one or more higher level domains to which the particular domain is connected. An example of an endpoint identifier is described below with reference to FIGS. 5-7.

Control plane functions (eg, network route calculation) and / or forwarding plane functions (eg, routing, forwarding, switching) are: (1) network configurations for a particular domain (eg, endpoints and / / within a particular domain. Or lower level domains), and (2) one or more higher level domains connected to a particular domain in the hierarchy, which can be partitioned and executed separately on a per-domain basis. it can. For example, the destination end point of a packet is the originating end. If in the same domain as point), the packet can be forwarded directly to the destination endpoint in the same domain according to a pre-computed network route. For packets destined for endpoints that are not in the same domain, the packet can be forwarded to one or more higher level domains, where in turn independently, based on the endpoint identifier, the packet is further Route designation, transfer, or other processing is performed. Therefore, a particular domain may (1) endpoint and within a particular domain (including any lower level domain) to independently perform various control plane and / or forwarding plane functions. (2) You only need to be aware of one or more higher level domain endpoints. As a result, the source domain can manage various network behaviors in that domain without worrying about the network behaviors of other domains in the hierarchy. Therefore, the network configuration and / or behavior in each partitioned domain can remain manageable as the size of the overall computer network increases.

FIG. 1A is a schematic diagram illustrating hierarchical partitioning of the computer network 100 into multiple domains of the hierarchy according to an embodiment of the present technology. As shown in Figure 1A, computer network 100 is interconnected with one or more Level 1 domains 104 (identified as D1-1 and D1-2, respectively) and core domain 102 (identified as D0). ) Can be included. The level 1 domain 104 can include one or more level 2 domains 106 (identified as D2-1 and D2-2, respectively), which in turn can contain one or more endpoints 108 (identified as EP). Can include) and one or more network nodes 112. In Figure 1A, three domain levels and a specific number of domains at each level are shown for illustration purposes. In another embodiment, the computer network 100 can be partitioned into any suitable level domain with an appropriate number of domains and / or endpoints at each level.

The core domain 102 can include one or more network nodes 112 that are interconnected to each other. Two network nodes 112 are shown in Figure 1A for illustration purposes. In another embodiment, the core domain 102 can include any suitable number of network nodes 112 and / or other suitable components. Network node 112 can include various computing and / or communication components to facilitate communication between pairs of endpoints 108 in lower level domains. For example, network node 112 in core domain 102 is a label switched router, a long haul dense wavelength division multiplexing module, a dynamic context router, an interface message. Processor (interface message) It can contain one or more processors) and / or other suitable components.

Computer network 100 is one or more edge nodes between a pair of domains at adjacent levels in the hierarchy. It can also include node). As used herein, an edge node generally refers to a network node between a lower level domain and an interconnected higher level domain. Edge nodes include both (1) destinations to higher level domains and (2) entry points for lower level domains, and vice versa. For example, level 1 domain D1-1 can include level 1 edge node 114 (identified as EN1) that interfaces with core domain 102. The Level 1 domain D1-1 has a Level 2 edge node 114 (identified as EN2-1) that interfaces with the Level 2 domain D2-1 and another Level 2 edge node 114 (identified as EN2-1) that interfaces with the Level 2 domain D2-2. (Identified as EN2-2) can also be included. Level 1 domain D1-2 is identified as Level 1 edge node 114 (identified as EN1-2) that interfaces with core domain D0 and Level 2 edge node 114 (identified as EN2-3) that interfaces with level 2 domain D2-3. Can include).

As discussed in more detail below, any endpoint 108 in a particular domain of the hierarchy is one or more edge nodes at a lower level of the hierarchy and one at a higher level of the hierarchy of a particular domain. By identifying one or more edge nodes, it is possible to reach other endpoints 108 in other domains. For example, endpoint 108 in level 1 domain D1-1 can be any in the hierarchy by recognizing (1) level 1 edge nodes EN1-1 and (2) level 2 edge nodes EN2-1 and EN2-2. Other endpoints 108 can be reached.

Only one edge node 114 is shown between pairs of domains at adjacent levels in Figure 1A, but in certain embodiments, the individual edge nodes 114 are in the same forwarding state (eg, computer network 100). Can include a group of edge nodes 114 with a destination hop or forwarding path in. For example, as shown in Figure 1B, level 1 domain D1-1 contains a group of edge nodes 114 identified as EN1-1-1 to EN1-1-X. Level 1 domain D1-2 contains a group of edge nodes 114 identified as EN1-2-1 through EN1-2-Y. In another example, Level 2 Edge Nodes EN2-1, EN2-2 and EN2-3 may each contain a group of Edge Nodes (not shown). In certain embodiments, packets from a particular domain can reach a desired destination through any one of the edge nodes 114 in the edge node group. For example, endpoint 108 in level 1 domain D1-1 reaches any endpoint 108 in level 2 domain D2-3 through any one of edge nodes EN1-1-1 to EN1-1-X. can do. In another embodiment, packets from a particular domain can be passed through a particular one of the edge nodes 114 in the edge node group, utilizing techniques such as traffic engineering. In a further embodiment, packets from a particular domain can be passed through edge nodes 114 in the edge node group in other suitable ways.

Returning to FIG. 1A, each domain of the computer network 100 has control plane functions (eg, network routing calculations) and / or forwarding plane functions (eg, routing, forwarding, switching), (1) specific. It can be managed independently based on the network configuration of the domain endpoint 108 and (2) the location and connectivity of the domains in the hierarchy. For example, the forwarding table for level 2 domain D2-1 is (1) the configuration of endpoint 108 for level 2 domain D2-1 and (2) the identity of its higher level domain (ie, level 1 domain D1). It can be calculated based on -1 and the core domain D0). For example, the forwarding table is one or more network routes from the source endpoint 108 of domain D2-1 to the destination endpoint 108 of the same domain (eg, via network node 112 or via other network nodes not shown). Can contain entries that specify. In one embodiment, the forwarding table at edge node 114 can include network routes for all endpoints 108 in a particular domain, while the forwarding table at other network nodes 112 in that domain is for endpoint 108. It may only include network routes for some. In another embodiment, the forwarding table at all edge nodes 114 and network nodes 112 can include network routes for all endpoints 108 within a particular domain.

Continuing with the previous example, the forwarding table can also contain one or more entries that specify a network route for all destination endpoints 108 that are not in the level 2 domain D2-1. For example, all destination endpoints 108 in level 2 domain D2-2 can have the same network path in level 2 domain D2-1 pointing to level 2 edge node EN2-1. All destination endpoints 108 in level 2 domain D2-3 can have the same network path pointing to one of level 2 edge node EN2-1, level 1 edge node EN1-1, or network node 112. Therefore, by specifying one network route for multiple destination endpoints 108 in other domains, multiple destination endpoints 108 are "aggregated" into a single (or limited number) destinations. Can be considered. Therefore, the forwarding table for Level 2 domain D2-1 can contain a manageable number of entries (eg, less than 3,000 entries). As a result, expensive equipment for network nodes in the first level 2 domain D2-1 can be avoided and operational complexity can be reduced compared to prior art.

Level 1 domain D1-1 can also include a similar forwarding table in its own network node (eg, level 1 edge node 114). The forwarding table is one or more networks from a lower level domain of origin (eg Level 2 domain D2-1) to a lower level domain of the same domain destination (eg Level 2 domain D2-2). It can contain entries that specify the route. If the lower level domain of the destination is not Level 1 Domain D1-1, Level 1 Domain D1-1 can specify a network route, for example, to Edge Node EN1-1 to Core Domain 102. The core domain 102 can also include another forwarding table at network node 112, each with an entry specifying a network route to a lower level domain in a similar manner as level 1 domain D1-1.

The forwarding table for a domain of computer network 100 can also include an entry that specifies the network route for incoming messages to a particular destination endpoint 108 for a particular domain. For example, the forwarding table in level 1 domain D1-2 contains an entry that specifies the network route from level 1 edge node EN1-2 to level 2 edge node EN2-3 for all endpoints 108 in level 2 domain D2-3. Can include. The forwarding table in Level 2 domain D2-3 can then contain one or more network routes for each of the endpoints 108 in that domain. Some examples are considered below to illustrate examples of computer network 100 operations. In another embodiment, the computer network 100 can have other suitable behaviors, sequences, states, and / or other features.

During operation, network node 112 (or edge node 114) in the domain may receive packets from source endpoint 108 (eg, endpoint 108 in level 2 domain D2-1) with the associated destination endpoint identifier. it can. The network node 112 (or edge node EN2-1) compares the value of the destination endpoint identifier with the entry in its forwarding table to determine the network route for forwarding the packet. If the destination (eg, endpoint 108') is in the same domain (ie, level 2 domain D2-1), one of the entries will send a message directly to endpoint 108', eg, through network node 112. You can specify the network route for transfer.

If the destination (eg, endpoint 108'' for domain D2-3) is not in the same domain as the source endpoint 108, then the entry points to a network that points to a higher level domain (eg, level 1 domain D1-1). You can specify the route. As a result, network node 112 forwards the packet to edge node EN2-1. At level 1 domain D1-1, edge node EN2-1 compares the value of the destination endpoint identifier with an entry in its forwarding table to determine the network route to edge node EN1-1 in core domain 102. In core domain 102, edge node EN1-1 compares the value of the destination endpoint identifier with an entry in its forwarding table to provide a network path to edge node EN1-2 through one or more network nodes 112. decide. Edge node EN1-2, in turn, determines the network route to edge node EN2-3, and then determines the route to forward the message to endpoint 108''.

As mentioned above, the lower level domains associated with each domain in computer network 100 can manage their own network operations independently. For example, each domain may independently manage control plane and / or forward plane functionality based on the network configuration of a particular domain and one or more higher level domains connected to a particular domain. it can. Therefore, the network operation of a particular domain does not depend on the network state information of the entire computer network, but instead depends on the network state of that particular domain. "Network state (network) The term "state)" refers to the identification (ID) and connection of network nodes and / or endpoints, the current operating state of network nodes and / or endpoints (eg, link up / down, etc.), bandwidth within the computer network. Generally refers to other suitable data related to allocation and / or computer network status and / or characteristics. As a result, the expansion of the computer network 100 has no limited or no impact on the complexity of the operation of existing domains. For example, if computer network 100 is extended to include another level 2 domain D2-4 (shown with a thin line for clarity), the operation of the other level 2 domain 106 is limited. Only adjustment is needed. For example, the forwarding tables for level 2 domains D2-1, D2-2, and D2-3 may need to be updated to recognize endpoints 108 added to the new level 2 domain D2-4. However, the number of entries in the forwarding table does not effectively increase because the additional endpoints in the new domain D2-4 are "integrated" with other endpoints that are not in separate domains. As a result, the computer network 100 can be extended to include millions, tens of millions of endpoints 108, while generally maintaining a similar level of operational complexity in each domain.

FIG. 2 is a schematic diagram illustrating an application example of the hierarchical partitioning technique of FIG. 1A to the computer network 100 for one data center or a plurality of data centers according to the embodiment of the present technology. As shown in FIG. 2, the computer network 100 can include a core domain 102 having one or more network nodes 112. The computer network 100'can also include one or more Level 1 Domains 104. For illustration purposes, two Level 1 domains 104, individually identified as domains D1-1 and D1-2, are shown in Figure 2. In the illustrated embodiment, the level 1 domain D1-1 comprises two level 2 domains 106, which are separately identified as D2-1 and D2-2. The level 1 domain D1-2 includes one level 2 domain D2-3. In other embodiments, the level 1 domain 104 can include any other suitable number of domains and / or endpoints.

The level 2 domain 106 can separately include one or more endpoints 108, one or more edge nodes 114, and one or more network nodes 112 that connect endpoints 108 to 114 to edge nodes. In one embodiment, each network node 112 can include a top-of-the-box (TOR) router or switch. In another embodiment, network node 112 may include a bridge, gateway, or other suitable communication device. In the illustrated embodiment, each of the Level 2 domains 106 includes two edge nodes 114 (eg, edge nodes EN2-1 and EN2-1') that form an edge node group. In certain embodiments, the edge nodes 114 in the edge node group can randomly access, for example, non-traffic engineering type packets. In another embodiment, one edge node 114 in the edge node group may be individually identified and specified, for example, to process traffic engineering type packets. In a further embodiment, the edge node 114 can be accessed in other suitable ways based on any other suitable criteria. In any of the embodiments described above, the same endpoint identifier can be used with reference to FIG. 3, as discussed in more detail below.

As shown in FIG. 2, individual domains of computer network 100'are adapted to configure, monitor, and / or control network operations for a particular domain. ) , As referred to herein). In the illustrated embodiment, the network controller 110 is shown as a separate computing device. In another embodiment, the network controller 110 can be a server or virtual machine at one of the endpoints 108. In a further embodiment, multiple domains (eg, Level 2 domains D2-1 and D2-2) can share a common network controller 110. An example of controller 110 is discussed in more detail below with reference to FIG.

The hierarchical partitioning shown in Figure 2 can cover one or more data centers in various ways. For example, in one embodiment, the hierarchical partitioning shown in FIG. 2 can cover a data center having a core domain 102 that includes one or more T3 broadband switches in the data center. The level 1 domain 106 can include a T2 switch connected to the level 2 domain 106 having a T1 and / or TOR switch. In another embodiment, the level 1 domain 104 can include both a T2 switch and a T1 switch, while the level 2 domain 106 includes a TOR switch. In another example, the hierarchical partitioning shown in Figure 2 can also cover multiple data centers. For example, core domain 102 can include core networks interconnected to multiple data centers and T3 broadband switches. Within each data center, a level 1 domain can include a T2 switch, while a level 2 domain can include a T1 and / or TOR switch. In a further example, the partitioning computer network 100'can include additional and / or different partitioning levels.

In certain embodiments, each endpoint 108 in computer network 100'can be clearly identified by the value of endpoint identifier 120, which has multiple sections located on the stack. Each section can correspond to the physical or logical location of endpoint 108. For example, as shown in Figure 3, the destination endpoint 108'' in level 2 domain D2-3 is a stack with four sections 122a-122d, each corresponding to the physical or logical location of endpoint 108''. Can be clearly identified by. In the examples described, each level domain in the hierarchy is associated with a section of endpoint identifier 120 and can be used to reach one or more of the corresponding edge nodes 114 associated with a particular domain. For example, the first section 122a has a value corresponding to core domain 102 with an example value of 38. The second section 122b has a value corresponding to level 1 domain D1-2 with an example value of 63. The third section 122c has values corresponding to level 2 domain D2-3. The fourth section 122d has a value corresponding to the server or virtual machine at endpoint 108'' with an example value of 14. In other embodiments, the endpoint identifier can also include a compound endpoint identifier having a single section or multiple endpoint identifiers, as shown in FIG. 5A or FIG. 5B. In a further embodiment, endpoint 108 can be specified by other suitable methods and / or values, and FIG. 7 shows an example using an IP address.

The following discussion provides an example of an operation for forwarding packets from endpoint 108 in level 2 domain D2-1 to endpoint 108'' in different level 2 domain D2-3. During operation, endpoint 108 may generate a packet with endpoint identifier 120 payload 124 based on, for example, an IP address or other suitable identifier for destination endpoint 108'' in domain D2-3. .. The endpoint identifier 120 can include the respective values of sections 122a-122d as described above. In the embodiments described, the endpoint 108 forwards the generated packet to the network device 112. Network node 112 compares the value in the top section of endpoint identifier 120 (ie, first section 122a) with the entry in the forwarding table (not shown) of network node 112 and is the forwarding path for forwarding the packet. Or determine the next hop. For example, in one embodiment, the value "38" can specifically correspond to the forwarding path to the level 2 edge node EN2-1, which in turn is the top section of endpoint identifier 120 own forwarding table. Is compared to determine another transfer path to Level 1 Edge Node EN1-1. In another embodiment, the value "38" can correspond to an edge node group that includes edge nodes EN2-1 and EN2-1. In such an embodiment, one of the edge nodes EN2-1 and EN2-1'can be selected to randomly forward the packet, for example by a hash function, or other suitable method.

Level 1 edge node EN1-1 then forwards the message to one or more of network nodes 112 in core domain 102. One or more network nodes 112 compare the top section with the entries in its forwarding table, delete the top section (ie, first section 122a), and forward the message to level 1 edge node EN1-2. .. Level 1 edge node EN1-2 then compares the top section (ie, second section 122b) with the entries in its forwarding table, removes the top section (ie section 122b), and levels the message. 2 Transfer to the edge node group including edge node EN2-3 or edge nodes EN2-3 and EN2-3'. The level 2 edge node EN2-3 (or EN2-3') then compares the top section (ie, third section 122c) with its own forwarding table and top section (ie, third section 122c). And forward the message to network node 112'in domain D2-3. Network node 112'then then compares the top section (ie, fourth section 122d) with the entries in its forwarding table, removes the top section (ie, fourth section 122d), and deletes the message payload. To endpoint 108''.

In the above embodiments, network node 112, edge nodes EN2-1, EN1-1, EN1-2, EN2-3 do not change the top section of endpoint identifier 120 during network processing. In another embodiment, at least one of the above components can swap the value of the top section of endpoint identifier 120 before forwarding the packet along the determined network path. Swapping is recorded and stored on each component. In a further embodiment, the endpoint 108 can forward the message directly to the edge node 114 without passing through the network node 112. Moreover, in a further embodiment, edge nodes EN1-2, EN2-3 and network node 112'depend on, for example, which section of the endpoint identifier 120 corresponding to a particular domain and associated edge node 114. Each transfer function can be performed without removing the top section of endpoint identifier 120.

In another example, endpoint 108 in level 2 domain D2-1 can also send packets to endpoint 108'in the same domain in a similar manner. For example, endpoint 108 in level 2 domain D2-1 can generate a packet with endpoint identifier 120 and payload 124. The endpoint identifier 120 can include only one section (eg, fourth section 122d) with a value (eg, 22) corresponding to endpoint 108'. Endpoint 108 then sends a packet with endpoint identifier 120 and payload to network node 112. Network node 112 compares the value of the top section of endpoint identifier 120 (ie, fourth section 122d) with the entry in the forwarding table, removes the top section of endpoint identifier 120, and follows the determined forwarding path. Forward the packet to endpoint 108'.

FIG. 4 is a block diagram showing an example of software components of the controller 110 of FIG. 3 according to an embodiment of the present technology. In Figure 4 and other figures below, individual software components, modules, and routines are written as source code in C, C ++, C Sharp, Java®, and / or other suitable programming languages. It can be a program, procedure, or process. A computer program, procedure, or process is compiled into object or machine code and presented to be executed by the processor of a personal computer, network server, laptop computer, smartphone, and / or other suitable computing device. .. Various implementations of source and / or object code and related data include computer memory including read-only memory, random access memory, magnetic disk storage media, optical storage media, flash memory devices, and / or other suitable storage media. Can be saved in.

In certain embodiments, the controller may include or be operably connected to a database or network storage device that contains a record of the network state of one or more layered domains. Network state records include network node identification, network node and / or endpoint connections, current operating state of network nodes and / or endpoints (eg, link up / down, etc.), bandwidth distribution within a domain. It can include related data and / or data related to other suitable network data. As mentioned above, the partitioning of the control plane function and / or the forwarding plane function can simplify the monitoring of the network state of each domain when compared with the prior art.

As shown in FIG. 4, the controllers 110 are operably connected to each other, with route calculation component 130, endpoint identifier allocation component 132, endpoint identifier server 134, endpoint identifier manager 136, and optional traffic engineering. It can include component 131. Although specific components of controller 110 are shown in FIG. 4, in other embodiments, controller 110 may also include one or more input / output components and / or other suitable types of components.

The route calculation component 130 can be configured to calculate network routes within a particular domain based on the inputs of domain configuration 140. Domain configuration 140 can include information about endpoints, network nodes, and edge nodes within a particular domain and within one or more domains higher in the hierarchy. Domain configuration 140 can automatically communicate with controller 110 using network communication protocols, manual operator input, or other suitable method. The route calculation component 130 can be implemented by various route calculation techniques. For example, in one embodiment, network routes can be calculated based on the shortest route from one endpoint to the other. In another embodiment, the route can be calculated on the basis of equal cost multiple path routing, which is a forwarding equivalent class. A group of paths in class) can be specified by a single entry (or multiple entries). In a further embodiment, the route can be calculated in conjunction with a distributed route protocol and / or other suitable technique.

The optional traffic engineering component 131 can be configured to calculate additional routes within the domain based on traffic engineering techniques. In certain embodiments, the traffic engineering component 131 can calculate additional routes within a domain based on the nature of network traffic, traffic measurement or simulation, domain topology, and / or other suitable criteria. In another embodiment, controller 110 receives a request for network bandwidth from the source endpoint to the destination and provides a request to traffic engineering component 131 that determines the allocation and forwarding path that satisfies the request. Distribution components (not shown) can also be included. The traffic engineering component 131 in a further embodiment can be omitted.

The endpoint identifier distribution component 132 can be configured to calculate and distribute the value of the endpoint identifier for each endpoint in the domain based on the input of domain configuration 140. In certain embodiments, the endpoint identifier value can include multiple sections in the stack, respectively. In another embodiment, the endpoint identifier value may also include other suitable data schemes. The endpoint identifier distribution component 132 can also be configured to associate a particular value of the endpoint identifier with the network route calculated by the route calculation component 130 and / or the optional traffic engineering component 131.

Endpoint Identifier Manager 136 can be adapted to configure forwarding table 137 within network node 112 (and / or edge node 114) within the domain. Although not shown in FIG. 4, the endpoint identifier manager 136 and network node 112 can also include suitable interfaces that facilitate communication (eg, application program interfaces (API)). In certain embodiments, the entries in forwarding table 137 can be statically generated. Therefore, the entry in forwarding table 137 can be calculated once. In another embodiment, the entries in forwarding table 137 can be updated periodically, continuously, or in another suitable way.

The endpoint identifier server 134 can be configured to provide the value of the endpoint identifier 120 when queried by the endpoint 108. The value of endpoint identifier 120 is used by edge node 114 (FIG. 1A) to determine the forwarding path for the passage of individual packets through edge node 114. For example, in one embodiment, the source endpoint 108 queries the endpoint identifier server 134 for the value of the endpoint identifier 120 associated with the destination endpoint 108 via an appropriate interface (eg, API). Can be done. In response, the endpoint identifier server 134 provides the requested value to the source endpoint 108. The requested value corresponds to one of the entries in forwarding table 137 on network node 112. The source endpoint 108 then appends or otherwise modifies the received value of the endpoint identifier associated with the destination endpoint 108 and networks for forwarding. Send a message to node 112.

FIG. 5A is a block diagram illustrating an example of an endpoint identifier with sections 122a-122d arranged according to embodiments of the present technology. As shown in FIG. 5A, endpoint identifier 120 contains four sections 122a-122d within endpoint identifier 120, identified as ID0, ID1, ID2, and ID3, respectively, and arranged according to the hierarchy of the computer network. Will be done. For example, in the embodiments described, sections ID0, ID1, ID2, and ID3 respectively have core domain D0 (FIG. 1A), level 1 domain D1 (FIG. 1A), and level in computer network 100 shown in FIG. 1A. Two domains D2 (Fig. 1A) and endpoint 108 can be configured to contain corresponding values, respectively. In another embodiment, at least one of sections ID0, ID1, ID2, and ID3 can correspond to different and / or additional domains. In a further embodiment, the endpoint identifier 120 may include two, three, five, or any other suitable number of sections. Moreover, in a further embodiment, the endpoint identifier 120 can also be arranged in a queue, list, set, or other suitable data structure. Moreover, in another embodiment, sections ID0, ID1, ID2, and ID3 can correspond to the physical location associated with the endpoint in the computer network, which will be described in more detail with reference to FIG. 5B.

FIG. 5B is a block diagram illustrating another example of an endpoint identifier having sections 122a-122d according to an embodiment of the present technology. As shown in Figure 5B, sections ID0, ID1, ID2, and ID3 can each correspond to a physical location associated with the endpoint. For example, sections ID0, ID1, ID2, and ID3 can correspond to network server data center ID162, building ID164, room ID166, and server ID168, respectively. The network server identified by the server ID can be physically located in the room identified by room ID 166 in the building identified by the building ID 164 of the data center identified by data center ID 162. In another example, one of sections ID0, ID1, ID2, and ID3 can also correspond to a row ID that identifies the column where the network server is located or a rack ID that identifies the column where the network server is located. it can. Moreover, in a further example, section ID3 can also correspond to, for example, a virtual machine ID that identifies a virtual machine on a network server, as identified by server ID 168. Moreover, in another example, the endpoint identifier 120 can have any other suitable number of sections 122 and / or can correspond to a physical location ID.

FIG. 6 is a block diagram showing one embodiment of sections 122a-122d of FIG. 5 according to an embodiment of the present technology. As shown in FIG. 6, section 122 may include an optional traffic engineering identifier 152 and destination identifier 154. The traffic engineering identifier 152 can be configured to include a value indicating that section 122 is associated with the route calculated by the optional traffic engineering component 132 (FIG. 4). The destination identifier 154 can be configured to include a value corresponding to a domain, physical location, group of physical locations, a particular network node, a group of network nodes, an endpoint, or other suitable item. In a further embodiment, the traffic identifier 152 can be omitted.

FIG. 7 is a schematic diagram illustrating an example of an endpoint identifier using the IP address 200 according to the embodiment of the present technology. As shown in the embodiments described in FIG. 7, the endpoint identifier 120 can include an IP address 200 having four sections 202, each with a few bits (8 bits are shown for illustration purposes). .. Each of Section 202 represents and can correspond to domains D0, D1, and D2 or endpoint 108 of computer network 100 shown in FIG. In another embodiment, the unassigned original IP address as shown in FIG. 7 can be processed corresponding to the virtual IP address as shown in FIG. In a further embodiment, the IP address 200 can include other suitable formats such as conforming to IPv6.

FIG. 8 is a flowchart illustrating an embodiment of a process for forming a partitioned computer network according to an embodiment of the present technology. As shown in FIG. 8, at stage 302, process 300 provides the configuration data for a particular domain and one or more higher level domains in the hierarchically partitioned computer network shown in FIG. 1A in each domain. Including receiving. The configuration data can include the number and ID of endpoints in the domain, and the connectivity of the endpoints. The configuration data can also include connectivity data for higher level domains, such as edge node identities to higher level domains.

Process 300 can also include generating a network route at stage 304 based on the received configuration data. In certain embodiments, routes can be calculated between pairs of endpoints in a domain. In another embodiment, one or more routes can be calculated for edge nodes for higher level domains for endpoints that are not in the domain. The calculated route can then be stored at stage 306 with the endpoint identifier in the forwarding table for the domain.

FIG. 9A is a flowchart illustrating an embodiment of Process 400 for managing outbound communication in the domain according to the embodiment of the present technology, and FIG. 9B is a flowchart for managing inbound communication in the domain according to the embodiment of the present technology. It is a flowchart explaining process 500. As described below, a particular domain manages inbound and outbound communications independently of the other domain, i.e., regardless of routing, forwarding, or other network activity in the other domain. As shown in FIG. 9A, process 400 receives an outbound message to the destination endpoint at stage 402, for example, at network node 112 (FIG. 1A) or edge node 114 (FIG. 1A) in a particular domain. Can be included. Process 400 can also include at stage 404 comparing the endpoint identifier associated with the received message with an entry in the forwarding table of network node 112 or edge node 114. If the destination endpoints are in the same domain, the forwarding table contains an entry that specifies the network route to forward the message directly to the destination endpoint. Process 400 then involves forwarding the message to the destination endpoint according to the specified network route. If the destination endpoint is not in the same domain, the forwarding table contains an entry that specifies another network route to forward the message to a higher level domain. Process 400 then involves forwarding the message to a higher level domain in stage 408.

FIG. 9B is a flowchart illustrating an embodiment of the process 500 that independently manages inbound communication in the domain according to the embodiment of the present technology. As shown in FIG. 9B, at stage 502, process 500 involves receiving incoming messages, for example, at the edge node 114 of the domain (FIG. 1A). Process 500 also includes, at stage 504, comparing the value of the endpoint identifier associated with the message with the entry in the forwarding table at edge node 114. In one embodiment, the top section of the endpoint identifier The value in section) is compared to the entry in the forwarding table. In other embodiments, additional and / or different sections of the endpoint identifier can be used instead. If the destination is in that domain, the forwarding table contains an entry that specifies the network route to the endpoint, and process 500 includes in stage 506 forwarding the message to the endpoint according to the network route. If the destination is not in that domain, the forwarding table contains an entry that specifies another network route to the lower level domain, and at stage 508, process 500 forwards the message to the lower level domain. Including. In certain embodiments, process 500 optionally includes removing the top section of the endpoint identifier before forwarding the message to a lower level domain. In another embodiment, the top section can be swapped, maintained, and / or otherwise modified. The lower level domain (and the lower level domain of the lower level domain, if any) performs a behavior similar to that of Process 500 in general until the message is forwarded to the destination endpoint. be able to.

The forwarding table is used as an example of a technique for determining the network route of FIGS. 9A and 9B, but in another embodiment the network route can be determined on an ad hoc basis. For example, in one embodiment, a determination may be performed in response to receiving an inbound or outbound message to determine if the destination endpoint associated with the message is in a particular domain. In other embodiments, the determination can be performed on a continuous basis, on a regular basis, or on any other suitable basis.

FIG. 10 is a computing device 600 suitable for a component of the computer network 100 of FIGS. 1A-3. For example, the computing device 600 may be suitable for endpoint 108 in FIG. 1A or controller 110 in FIGS. 2 and 3. In a very basic configuration 602, the computing device 600 typically includes one or more processors 604 and system memory 606. Memory bus 608 can be used for communication between processor 604 and system memory 606.

Depending on the desired configuration, the processor 604 can be any type, including without limitation a microprocessor (μP), a microcontroller (μC), a digital signal processor (DSP), or any combination thereof. Processor 604 can include one or more levels of cache, such as level 1 cache 610, level 2 cache 612, processor core 614, and register 616. Examples of processor core 614 can include arithmetic units (ALUs), floating point units (FPUs), digital signal processing cores (DSP cores), or any combination thereof. The example of the memory controller 618 can also be used with the processor 604, or in some implementations the memory controller 618 can be an internal component of the processor 604.

Depending on the desired configuration, the system memory 606 can be of any type, including without limitation volatile memory (such as RAM), non-volatile memory (such as ROM, flash memory) or any combination thereof. The system memory 606 can include an operating system 620, one or more applications 622, and program data 624. This described basic configuration 602 is illustrated in FIG. 10 by these components within the dashed line inside.

The computing device 600 can have additional features or functionality and an additional interface that facilitates communication between the basic configuration 602 and other devices and interfaces. For example, the bus / interface controller 630 can be used to facilitate communication between the base configuration 602 and one or more data storage devices 632 via the storage interface bus 634. The data storage device 632 can be a removable storage device 636, a non-removable storage device 638, or a combination thereof. Examples of removable and non-removable storage devices include flexible disk drives and magnetic disk drives such as hard disk drives (HDD), compact disk (CD) drives or digital versatile disks (DVD), to name a few. Includes optical disk drives, solid state drives (SSDs), and tape drives. Examples of computer storage media are volatile and non-volatile media, removable and non-volatile, implemented in any way or technique for storing information such as computer-readable instructions, data structures, program modules, or other data. It can include removable media.

System memory 606, removable storage device 636, and non-removable storage device 638 are examples of computer-readable storage media. Computer-readable storage media are not limited, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disk (DVD) or other optical storage, magnetic cassette, magnetic tape, magnetic disk. Includes storage or other magnetic storage device, or any other media that stores the desired information and is accessible by the computing device 600. Such computer-readable storage media can be part of the computing device 600. The term "computer readable storage medium" does not include propagated signal and communication media.

The computing device 600 is a basic configuration (basic) from various interface devices (eg, output device 642, peripheral interface 644, and communication device 646) via the bus / interface controller 630. It can also include an interface bus 640 that facilitates communication to configuration) 602. An example of an output device 642 includes a graphics processing unit 648 and an audio processing unit 650 so that they communicate with various external devices, such as a display or speaker, via one or more A / V ports 652. Can be configured in. Examples of peripheral interface 644 include serial interface controller 654 or parallel interface controller 656, which are via one or more I / O ports 658, eg, input devices (eg, keyboard, mouse, pen, voice). It can be configured to communicate with external devices such as input devices, touch input devices, etc.) or other peripheral devices (eg, printers, scanners, etc.). An example of a communication device 646 includes a network controller 660, which is arranged to facilitate communication with one or more other computing devices 662 through a network communication link via one or more communication ports 664. can do.

Network communication links can be an example of communication media. Communication media are embodied by computer-readable instructions such as carrier waves or other transmission mechanisms, data structures, program modules, or other data in modulated data signals, and may also include information distribution media. A "modulated data signal" may be a signal in which one or more of its properties have been set or modified to encode information in the signal. By way of example, without limitation, communication media includes wired media such as wired networks or direct wired connections, and wireless media such as acoustic, radio frequency (RF), microwave, infrared (IR) and other radio media. As used herein, the term computer readable media can include both storage and communication media.

The computing device 600 is as small as a mobile phone, personal data assistant (PDA), personal media player device, wireless web watch device, personal headset device, application-specific device, or hybrid device that includes some of the features described above. It can be implemented as part of a form factor portable (or mobile) electronic device. The computing device 600 can be implemented as a personal computer that includes both laptop and non-laptop computer configurations.

Specific embodiments of the present technology have been described above for purposes of explanation. However, various changes can be made without departing from the above disclosure. Moreover, multiple elements of one embodiment can be added to, or instead combined with, other elements of another embodiment. As a result, the technology is not limited except as provided in the appended claims.