Method for end point identification in computer networks

• US 9,544,225 B2
• Filed: 09/16/2014
• Issued: 01/10/2017
• Est. Priority Date: 09/16/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Loher, Darren, Fang, Luyuan, Cox, Jeff, Elaawar, Nasser, Nkposong, Edet, Ratterree, Gary, Chiussi, Fabio
• Primary Examiner(s): Nguyen, Brian D
• Application Number:
  US14/488,018
• Publication Number:
  US 20160080258A1
• Time in Patent Office: 847 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 2212/00 Encapsulation of packets
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/583 Stackable routers
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 45/72 Routing based on the source address
• CPC Class Codes: H04L 45/74 Address processing for 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 one or more network nodes interconnecting one or more end points, the method comprising:

receiving, at a network node, a packet identified with an end point identifier, wherein the end point identifier includes a first section holding a first value and a second section holding a second value, wherein the first and second values individually correspond to at least a portion of a physical location of an end point in the computer network;

determining at least a portion of a forwarding path to forward the packet to the end point based on at least one of the first value or the second value of the end point identifier; and

forwarding, from the network node, the packet to the end point along the determined at least a portion of the forwarding path.

2. The method of claim 1 wherein:

the first value identifies at least one of a data center, a building in the data center, a room in the building, a row in the room, or a rack in the row in which the end point is located; and

the second value identifies at least one of a logical location of a virtual machine or a physical location of a server on which the virtual machine is hosted.

3. The method of claim 1 wherein the first and second sections are arranged in a stack.

4. The method of claim 1 wherein:

the first and second sections are arranged in a stack; and

determining at least a portion of the forwarding path includes comparing at least the first value with entries in a forwarding table in a memory of the network node, the forwarding table having an entry corresponding to the first value, the entry specifying at least a portion of the forwarding path to the end point.

5. The method of claim 4 wherein forwarding includes forwarding, from the network node, the packet to the end point along the determined at least a portion of the forwarding path without modifying the first value in the first section.

6. The method of claim 4, further comprising modifying at least the first value in the first section of the stack in conjunction of forwarding, from the network node, the packet to the destination end point.

7. The method of claim 1, further comprising removing at least the first section from the stack in conjunction with forwarding, from the network node, the packet to the end point along the determined at least a portion of the forwarding path.

8. The method of claim 1 wherein:

the first and second sections are arranged in a stack;

determining at least a portion of the forwarding path includes comparing at least the first value with entries in a forwarding table at the network node, the forwarding table having an entry corresponding to the first value, the entry specifying at least a portion of the forwarding path to the end point; and

the method further includes removing the first section from the stack in conjunction with forwarding, from the network node, the packet to the destination end point along the determined at least a portion of the forwarding path.

9. The method of claim 1 wherein:

the first and second sections are arranged in a stack;

the network node is a first network node;

determining at least a portion of the forwarding path includes comparing the first value with entries in a forwarding table at the first network node, the forwarding table having an entry corresponding to the first value, the entry specifying at least a portion of the forwarding path to the end point via a second network node;

the method further includes;

removing the first section from the stack in conjunction with forwarding, from the first network node, the packet to the end point along the determined at least a portion of the forwarding path;

determining another portion of the forwarding path to the end point by comparing the second value to entries of a forwarding table at the second network node; and

forwarding, from the second network node, the packet along the determined another portion of the network path to the end point.

10. The method of claim 1 wherein:

the first and second sections are arranged in a stack;

the network node is a first network node;

determining at least a portion of the forwarding path includes comparing the first value with entries in a forwarding table at the first network node, the forwarding table having an entry corresponding to the first value, the entry specifying at least a portion of the forwarding path to the end point via a second network node;

the method further includes;

removing the first section from the stack in conjunction with forwarding, from the first network node, the packet to the end point along the determined at least a portion of the forwarding path;

determining another portion of the forwarding path to the end point by comparing the second value to entries of a forwarding table at the second network node;

removing the second section from the stack; and

forwarding, from the second network node, the packet without the second section along the determined another portion of the network path to the end point.

11. A method of transmitting packets in a computer network having one or more end points, the method comprising:

at a first end point, identifying a second end point as a destination for a packet;

based on the identified second end point, at the first end point, appending an end point identifier associated with the identified second end point to the packet, wherein the end point identifier includes;

a first section having a first value; and

a second section having a second value, wherein the first and second values individually corresponding to at least a portion of a physical address of the identified second end point; and

transmitting, from the first end point to the identified second end point, the packet with the appended end point identifier having the first and second values in the first and second sections, respectively.

12. The method of claim 11 wherein:

the first value identifies at least one of a data center, a building in the data center, a room in the building, a row in the room, or a rack in the row in which the end point is located; and

the second value identifies at least one of a logical location of a virtual machine or a physical location of a server on which the virtual machine resides.

13. The method of claim 11 wherein the first and second sections are arranged in a stack, a queue, a list, or a set.

14. The method of claim 11 wherein the first value of the first section is associated with a first portion of a forwarding path from the first end point to the second end point, and wherein the second value of the second section is associated with a second portion of the forwarding path from the first end point to the second end point.

15. The method of claim 11 wherein:

each of the first or second section includes a first portion and a second portion;

the first portion containing a traffic engineering identifier; and

the second portion containing a destination identifier.

16. A computing device in a computer network having one or more end points, the computing system comprising:

a processor operatively coupled to a memory containing instructions that when executed by the processor, cause the processor to perform a process comprising;

identifying a destination end point in the computer network with an end point identifier, the end point identifier having one or more sections each holding a value, wherein the values individually correspond to at a portion of a physical location of the destination end point in the computer network;

associating at least one of the values of the sections of the end point identifier with at least a portion of a forwarding path for transmitting packets to the destination end point;

storing the forwarding path and the associated values of the sections of the end point identifier in a forwarding table in a network node of the computer network; and

transmitting packets from the end points in the computer network to the destination end point based on the stored forwarding path in the forwarding table.

17. The computing device of claim 16 wherein:

the one or more sections include a plurality of sections arranged in a stack; and

associating at least one of the values of the sections includes associating the value of a top section in the stack with a forwarding path for transmitting packets to the identified destination end point identified by the end point identifier.

18. The computing device of claim 16 wherein:

the one or more sections include a plurality of sections arranged in a stack; and

associating at least one of the values of the sections includes associating a first value of the one of the sections with a first forwarding path and associated a second value of another one of sections with a second forwarding path that is in series with the first forwarding path.

19. The computing device of claim 16 wherein:

the one or more sections include a plurality of sections arranged in a stack; and

associating at least one of the values of the sections includes associating a first value of the one of the sections in the stack with a first forwarding path and associating a second value of another one of the sections in the stack with a second forwarding path that is different than the first forwarding path.

20. The computing device of claim 16 wherein:

the one or more sections include a plurality of sections arranged in a stack; and

associating at least one of the values of the sections includes;

associating a first value of the one of the sections in the stack with a first forwarding path to a network node in a data center; and

associating a second value of another one of the sections in the stack with a second forwarding path from the network node of the data center to at least one of a logical location of a virtual machine or a physical location of a server on which the virtual machine resides, the server being located in the data center.