Service-oriented routing in software-defined MANETs

• US 10,172,068 B2
• Filed: 01/22/2014
• Issued: 01/01/2019
• Est. Priority Date: 01/22/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Mosko, Marc E., Garcia-Luna-Aceves, Jose J.
• Primary Examiner(s): Rutkowski, Jeffrey M
• Assistant Examiner(s): Li, Ning
• Application Number:
  US14/161,406
• Publication Number:
  US 20150208318A1
• Time in Patent Office: 1,805 Days
• Field of Search: None
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]
• CPC Class Codes: H04L 41/40 using virtualisation of network functions or resources, e.g. SDN or NFV entities
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04W 40/04 based on wireless node resources
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

One embodiment provides a mobile ad-hoc network (MANET). The MANET includes a plurality of mobile nodes and a centralized controller node. The controller node includes a receiving mechanism configured to receive, from a source mobile node, a request for a service, with the request including an identifier associated with the requested service; an identification mechanism configured to identify a destination mobile node that provides the service associated with the identifier; a path-computation mechanism configured to compute a path between the source mobile node and the destination mobile node using a network graph for the mobile nodes; and a path-sending mechanism configured to send the computed path to at least the destination mobile node, which facilitates establishing a route between the source mobile node and the destination mobile node.

Claims

1. A computer-implemented method for providing service-oriented routing in a mobile ad-hoc network (MANET) that includes a centralized controller node and a plurality of ad-hoc mobile nodes, comprising:

at the centralized controller node;

receiving an update message from a first mobile node of the plurality of the ad-hoc mobile nodes, wherein the update message includes an update to neighborhood metrics and an update to a name list specifying names of content items cached in the first mobile node, wherein the neighborhood metrics include a list of neighbor nodes of the plurality of the ad-hoc mobile nodes and connectivity metrics for respective neighbor nodes of the list of neighbor nodes, and wherein the connectivity metrics include a channel reliability, a residual bandwidth, and a queueing latency;

receiving, from a source mobile node of the plurality of the ad-hoc mobile nodes, a request for a service, wherein the request includes an identifier associated with the requested service;

identifying a node of the plurality of the ad-hoc mobile nodes that provides the service based at least on the update to the name list;

updating a network graph for the plurality of ad-hoc mobile nodes based on the update to the neighborhood metrics of the first mobile node;

computing a path between the source mobile node and the node using the updated network graph, wherein the path includes one or more mobile nodes of the plurality of the ad-hoc mobile nodes;

selecting the node as a destination mobile node when the path is a least-cost path based on the neighborhood metrics for the one or more mobile nodes; and

sending the path to the destination mobile node to cause the destination mobile node to send one or more destination mobile node packets via the path to the source mobile node, wherein when the source mobile node receives the one or more destination mobile node packets from one of the one or more mobile nodes, the source mobile node is caused to send one or more source mobile node packets to the one of the one or more mobile nodes such that the destination mobile node receives the one or more source mobile node packets via the path.

2. The method of claim 1, further comprising:

receiving from the first mobile node one or more of;

a list of multicast groups to which the first mobile node is subscribed; and

names of one or more services provided by the first mobile node.

3. The method of claim 1, wherein:

identifying the node involves identifying a group of mobile nodes of the plurality of the ad-hoc mobile nodes capable of providing the service; and

selecting the node includes selecting the node from the group of mobile nodes.

4. The method of claim 1, wherein the service includes one or more of:

a computational service and a piece of content.

5. The method of claim 1, wherein the identifier includes at least one of:

a hierarchical name;

a hierarchical name prefix;

a flat name;

a fixed-length name;

an arbitrary-length name; and

a label.

6. The method of claim 1, wherein sending the path facilitates establishing the path between the source mobile node and the destination mobile node.

7. The method of claim 1, wherein the first mobile node determines the channel reliability of a link to a particular neighbor node of the neighbor nodes by calculating a ratio of a number of hello packets received at the first mobile node with at least a threshold measure of clarity to a total number of hello packets sent by the particular neighbor node.

8. The method of claim 1, wherein the first mobile node determines the residual bandwidth based on an amount of bandwidth available across a link to a particular neighbor node of the neighbor nodes, and based on free time slots available in a set of scheduled time slots.

9. The method of claim 1, wherein the first mobile node determines the queueing latency from an average time that packets spend in a media access control queue before being transmitted.

10. A non-transitory computer-readable storage medium storing instructions that, when executed by a centralized controller node, cause the centralized controller node to perform a method for providing service-oriented routing in a mobile ad-hoc network (MANET) that includes the centralized controller node and a plurality of ad-hoc mobile nodes, the method comprising:

at the centralized controller node;

receiving an update message from a first mobile node of the plurality of the ad-hoc mobile nodes, wherein the update message includes an update to neighborhood metrics and an update to a name list specifying names of content items cached in the first mobile node, wherein the neighborhood metrics include a list of neighbor nodes of the plurality of the ad-hoc mobile nodes and connectivity metrics for respective neighbor nodes of the list of neighbor nodes, and wherein the connectivity metrics include a channel reliability, a residual bandwidth, and a queueing latency;

receiving, from a source mobile node of the plurality of the ad-hoc mobile nodes, a request for a service, wherein the request includes an identifier associated with the requested service;

identifying a node of the plurality of the ad-hoc mobile nodes that provides the service based at least on the update to the name list;

updating a network graph for the plurality of ad-hoc mobile nodes based on the update to the neighborhood metrics of the first mobile node;

computing a path between the source mobile node and the node using the updated network graph, wherein the path includes one or more mobile nodes of the plurality of the ad-hoc mobile nodes;

selecting the node as a destination mobile node when the path is a least-cost path based on the neighborhood metrics for the one or more mobile nodes; and

sending the path to the destination mobile node to cause the destination mobile node to send one or more destination mobile node packets via the path to the source mobile node, wherein when the source mobile node receives the one or more destination mobile node packets from one of the one or more mobile nodes, the source mobile node is caused to send one or more source mobile node packets to the one of the one or more mobile nodes such that the destination mobile node receives the one or more source mobile node packets via the path.

11. The storage medium of claim 10, wherein the method further comprises:

receiving from the first mobile node one or more of;

a list of multicast groups to which the first mobile node is subscribed; and

names of one or more services provided by the first mobile node.

12. The storage medium of claim 10, wherein:

identifying the node involves identifying a group of mobile nodes of the plurality of the ad-hoc mobile nodes capable of providing the service; and

selecting the node involves selecting the node from the group of mobile nodes.

13. The storage medium of claim 10, wherein the service includes one or more of:

a computational service and a piece of content.

14. The storage medium of claim 10, wherein the identifier includes at least one of:

a hierarchical name;

a hierarchical name prefix;

a flat name;

a fixed-length name;

an arbitrary-length name; and

a label.

15. The storage medium of claim 10, wherein sending the path facilitates establishing the path between the source mobile node and the destination mobile node.

16. A mobile ad-hoc network (MANET), comprising:

a plurality of mobile nodes; and

a centralized controller node, wherein the centralized controller node comprises a processor and a storage device coupled to the processor, wherein the storage device stores instructions which, when executed by the processor, cause the processor to perform a method, the method comprising;

receiving an update message from a first mobile node of the plurality of the ad-hoc mobile nodes, wherein the update message includes an update to neighborhood metrics and an update to a name list specifying names of content items cached in the first mobile node, wherein the neighborhood metrics include a list of neighbor nodes of the plurality of the ad-hoc mobile nodes and connectivity metrics for respective neighbor nodes of the list of neighbor nodes, and wherein the connectivity metrics include a channel reliability, a residual bandwidth, and a queueing latency;

receiving, from a source mobile node of the plurality of the ad-hoc mobile nodes, a request for a service, wherein the request includes an identifier associated with the requested service;

identifying, in response to the request, a node of the plurality of the ad-hoc mobile nodes that is capable of providing the service based at least on the update to the name list;

updating a network graph for the plurality of mobile nodes based on the update to the neighborhood metrics of the first mobile node;

computing a path between the source mobile node and the node using the updated network graph, wherein the path includes one or more mobile nodes of the plurality of the ad-hoc mobile nodes;

selecting the node as a destination mobile node when the path is a least-cost path based on the neighborhood metrics for the one or more mobile nodes; and

sending the path to the destination mobile node to cause the destination mobile node to send one or more destination mobile node packets via the path to the source mobile node, wherein when the source mobile node receives the one or more destination mobile node packets from one of the one or more mobile nodes, the source mobile node is caused to send one or more source mobile node packets to the one of the one or more mobile nodes such that the destination mobile node receives the one or more source mobile node packets via the path.

17. The MANET of claim 16, wherein the method further comprises receiving from the first mobile node one or more of:

a list of multicast groups to which the first mobile node is subscribed; and

names of one or more services provided by the first mobile node.

18. The MANET of claim 16, wherein:

identifying the destination mobile node involves identifying a group of mobile nodes of the plurality of the ad-hoc mobile nodes capable of providing the service; and

selecting the node includes selecting the node from the group of mobile nodes.

19. The MANET of claim 16, wherein the service includes one or more of:

a computational service and a piece of content.

20. The MANET of claim 16, wherein the identifier includes at least one of:

a hierarchical name;

a hierarchical name prefix;

a flat name;

a fixed-length name;

an arbitrary-length name; and

a label.

21. The MANET of claim 16, wherein the sending the path facilitates establishing the path between the source mobile node and the destination mobile node.