Method for scalable computer network partitioning

• US 9,819,573 B2
• Filed: 09/11/2014
• Issued: 11/14/2017
• Est. Priority Date: 09/11/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Fang, Luyuan, Cox, Jeff, Elaawar, Nasser, Loher, Darren, Nkposong, Edet, Ratterree, Gary, Chiussi, Fabio
• Primary Examiner(s): Sefcheck, Gregory
• Assistant Examiner(s): ULYSSE, JAEL M
• Application Number:
  US14/484,169
• Publication Number:
  US 20160080245A1
• Time in Patent Office: 1,160 Days
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

Various techniques for partitioning a computer network is disclosed herein. In certain embodiments, control plane functions (e.g., computation of network routes) and/or forwarding plane functions (e.g., routing, forwarding, switching) may be partitioned and performed individually on per domain basis based on (1) a network configuration of a particular domain (e.g., end points and/or lower-level domains in the particular domain); and (2) one or more higher-level domains connected to the particular domain in the hierarchy. Thus, a particular domain can manage various network operations of the domain without concerns regarding end points or network nodes in other domains of the hierarchy. Thus, network configuration and operation may be partitioned to reduce hardware costs and operational complexity even as the size of the overall computer networks increases.

Claims

1. A method of transmitting packets in a computer network having a hierarchy of domains individually having one or more network nodes interconnected with one or more end points, the method comprising:

at a first network node in a first domain of the hierarchy, receiving a plurality of packets with corresponding end point identifiers individually having a stack with a first section containing a value corresponding to a higher-level domain that is above the first domain in the hierarchy and a second section containing another value corresponding to a second domain, the higher-level domain being different from the second domain;

determining a first network route from the first network node to the higher level domain by performing a comparison of the value of the first section of the end point identifiers with entries in a forwarding table in the first network node, one of the entries of the forwarding table specifying a network path from the first network node to the higher-level domain as a destination corresponding to all end points in the second domain; and

forwarding the packets to a second network node in the higher-level domain based on the determined first network route; and

at the second network node in the higher-level domain,

removing the first section from the stack;

determining a second network route from the second network node to the end points in the second domain based on the another value in the second section of the end point identifiers; and

forwarding the packets from the second network node to the end points in the second domain based on the determined second network route.

2. The method of claim 1 wherein:

the hierarchy of domains includes a lower level domain that is lower in the hierarchy than the first domain; and

the method further includes receiving the plurality of packets from the lower level domain along a network route independently determined by a network node in the lower level domain.

3. The method of claim 1 wherein:

the hierarchy of domains includes a lower level domain that is lower in the hierarchy than the first domain; and

the method further includes receiving the plurality of packets from the lower level domain along a network route independently determined by a network node in the lower level domain based on the value of the first section of the stack.

4. The method of claim 1 wherein:

the hierarchy of domains includes a lower level domain that is lower in the hierarchy than the first domain; and

the method further includes receiving the packets from the lower level domain along a network route independently determined by a network node in the lower level domain based on a value of a third section of the stack, wherein the third section is removed from the stack before the plurality of packets are forwarded from the lower level domain to the first domain.

5. The method of claim 1 wherein:

the hierarchy of domains includes a lower level domain that is lower in the hierarchy than the second domain; and

forwarding the plurality of packets from the second network node includes;

removing the second section from the stack; and

forwarding the plurality of packets with the second section removed to a network node in the lower level domain.

6. The method of claim 1 wherein:

the hierarchy of domains includes a lower level domain that is lower in the hierarchy than the second domain; and

forwarding the plurality of packets from the second network node includes;

determining a third network route from the second domain to the lower level domain based on the another value of the second section;

subsequent to determining the third network route, removing the second section from the stack; and

forwarding the plurality of packets with the second section removed to a network node in the lower level domain along the determined third network route.

7. The method of claim 1 wherein the

forwarding table in the first network node of the first domain includes entries corresponding to at least some of the end points in the first domain and the second network node in the higher-level domain.

8. The method of claim 1 wherein:

the higher-level domain includes a group of network nodes having a same forwarding state, the group of network nodes including the second network node; and

forwarding the packets includes forwarding the packets to the second network node as one of the network nodes in the group based on the determined first network route.

9. The method of claim 1 wherein:

the hierarchy of domains includes a lower level domain that is lower in the hierarchy than the second domain; and

forwarding the packet from the second network node includes;

removing the second section from the stack; and

forwarding the packet with the second section removed to a network node in the lower level domain.

10. The method of claim 1 wherein:

the hierarchy of domains includes a lower level domain that is lower in the hierarchy than the second domain; and

forwarding the packet from the second network node includes;

determining a third network route from the second domain to the lower level domain based on the second value of the second section;

subsequent to determining the third network route, removing the second section from the stack; and

forwarding the packet with the second section removed to a network node in the lower level domain along the determined third network route.

11. A method of transmitting packets in a computer network having a hierarchy of domains individually having one or more network nodes interconnected with one or more end points, the method comprising:

at each domain in the hierarchy, independently performing;

receiving a request to transmit a packet from a first end point in a domain to a second end point in the computer network, the packet having an end point identifier having a stack with a first section containing a value corresponding to a higher-level domain that is above the first domain in the hierarchy and a second section containing another value corresponding to a second domain;

determining whether the second end point is in the same domain as the first end point;

in response to determining that the second end point is not in the same domain as the first end point, determining a first network route to the higher-level domain as a destination for the packet based on the value in the first section of the stack, the higher-level domain being immediately above the domain in the hierarchy of domain and being the destination corresponding to all end points that are not in the domain;

forwarding the packets to a network node in the higher-level domain based on the determined first network route; and

at the network node in the higher-level domain,

removing the first section from the stack;

determining a second network route from the network node to the second domain based on the another value in the second section of the end point identifiers; and

transmitting the packet from the first end point in the domain to second end point via the higher-level domain by forwarding the packet from the network node to the second domain based on the determined second network route.

12. The method of claim 11, wherein the method further includes, in response to determining that the second end point is in the same domain as the first end point, transmitting the packet to the second end point in the same domain without transmitting the packet to the higher-level domain.

13. The method of claim 11 wherein:

each domain in the hierarchy includes an edge node; and

the method further includes, at each domain in the hierarchy, independently performing;

receiving a packet having a corresponding end point identifier at the edge node;

determining an end point in the domain based on the end point identifier; and

forwarding the packet to the determined end point.

14. The method of claim 11 wherein:

each domain in the hierarchy includes an edge node; and

the method further includes, at each domain in the hierarchy, independently performing;

receiving a packet having a corresponding end point identifier at the edge node, the end point identifier including a plurality of sections in a stack;

removing one of the sections from a top of the stack;

subsequently, determining an end point based on a value in one of the section in the stack, the one section being on top of the stack; and

forwarding the packet to the determined end point.

15. The method of claim 11 wherein:

each domain in the hierarchy includes an edge node; and

the method further includes, at each domain in the hierarchy, independently performing;

receiving a packet having a corresponding end point identifier at the edge node, the end point identifier including a plurality of sections in a stack;

removing one of the sections from a top of the stack;

subsequently, determining an end point based on a value in one of the section in the stack, the one section being on top of the stack;

determining if the end point is in the domain; and

in response to determining that the end point is not in the domain, forwarding the packet to a lower-level domain in the hierarchy.

16. The method of claim 11 wherein:

the stack includes a plurality of sections, the individual sections corresponding to levels of hierarchy in the computer network.

17. A method of transmitting packets in a computer network having a hierarchy of domains individually having one or more network nodes interconnected with one or more end points, the method comprising:

at a first network node in a first domain of the hierarchy, receiving a packet with an end point identifier having a stack with a first section containing a first value and a second section containing a second value;

determining a first network route from the first network node to a higher level domain by performing a comparison of the first value of the first section with entries in a forwarding table in the first network node, one of the entries of the forwarding table specifying a network path from the first network node to the higher-level domain as a destination corresponding to all end points in the second domain;

forwarding the packet to a second network node in the higher-level domain based on the determined first network route; and

at the second network node in the higher-level domain,

removing the first section from the stack;

determining a second network route from the second network node to the second domain based on the second value in the second section of the stack; and

forwarding the packet from the second network node to the second domain based on the determined second network route.

18. The method of claim 17 wherein:

the hierarchy of domains includes a lower level domain that is lower in the hierarchy than the first domain; and

the method further includes receiving the packet from the lower level domain along a network route independently determined by a network node in the lower level domain.

19. The method of claim 17 wherein:

the hierarchy of domains includes a lower level domain that is lower in the hierarchy than the first domain; and

the method further includes receiving the packet from the lower level domain along a network route independently determined by a network node in the lower level domain based on the first value of the first section of the stack.

20. The method of claim 17 wherein:

the hierarchy of domains includes a lower level domain that is lower in the hierarchy than the first domain; and

the method further includes receiving the packets from the lower level domain along a network route independently determined by a network node in the lower level domain based on a third value of a third section of the stack, wherein the third section is removed from the stack before the packet is forwarded from the lower level domain to the first domain.