Method for scalable computer network partitioning

Patent metadata

Field	Value
Publication number	US-9819573-B2
Application number	US-201414484169-A
Country	US
Kind code	B2
Filing date	Sep 11, 2014
Priority date	Sep 11, 2014
Publication date	Nov 14, 2017
Grant date	Nov 14, 2017

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.

First claim

We claim:

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 packe

Assignees

• Microsoft Corp
• Microsoft Technology Licensing Llc

Inventors

• Fang Luyuan
• Cox Jeff
• Elaawar Nasser
• Loher Darren
• Nkposong Edet
• Ratterree Gary
• Chiussi Fabio

Classifications

• H04L45/04 Primary

  Interdomain routing, e.g. hierarchical routing · CPC title

• H04L45/745

  Address table lookup; Address filtering · CPC title