Ad-hoc on-demand routing through central control

• US 9,906,439 B2
• Filed: 11/01/2013
• Issued: 02/27/2018
• Est. Priority Date: 11/01/2013
• Status: Active Grant

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Inventors: Aldrin, Sam K., Perkins, Charles
• Primary Examiner(s): Yeung, Mang
• Assistant Examiner(s): Solinsky, Peter G
• Application Number:
  US14/069,699
• Publication Number:
  US 20150124625A1
• Time in Patent Office: 1,579 Days
• Field of Search: 370238
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 47/16 in connection oriented networks, e.g. frame relay
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality

Abstract

System and method of ad hoc on-demand routing by virtue of central control. A central controller of a network can communicate directly with a route-requesting network device regarding discovery of a data transmission path and perform route computation. A source network device may query the central controller with a unicast route request. In response, the central controller can identify a feasible route based on the topology information of the network. The central controller may also receive a broadcast route request along with other network nodes. As a result, the source device can be offered to select from two resultant routes, one provided by the central controller in a centralized manner and the other provided by the destination device. Further, the central controller can be used specifically for computation of constrained routes by incorporating global constraints. The central controller may be a software defined network (SDN) controller.

Claims

1. A method of routing data in an ad-hoc communication network comprising a plurality of network nodes and a central controller, said method comprising:

receiving a routing request sent from a first network node in the plurality of network nodes by virtue of unicast to said central controller, wherein said routing request comprises a request to identify a transmission path for routing data from said first network node to a second network node in the plurality of network nodes;

receiving another routing request sent from said first network node by virtue of broadcast to said central controller and said plurality of network nodes;

at said central controller, determining identified transmission paths in an offline and centralized manner based on a topology of the plurality of network nodes in said ad-hoc communication network in response to said routing request and in response to said another routing request, wherein said identified transmission paths are available for data transmission between said first network node and said second network node; and

sending routing responses from the central controller in response to said routing request and said another routing request to said first network node through unicast, wherein said routing responses identify said identified transmission paths for selection by said first network node.

2. The method of claim 1, wherein

said routing request comprises a request to identify at least one of said transmission paths with said route constraint,

said route constraint comprises a global constraint for the topology with respect to said ad hoc communication network, and

said determining comprises determining said at least one identified transmission path by incorporating said route constraints.

3. The method of claim 2,

wherein said second network node sends said another routing response to said first network node in response to said broadcast, and

said another routing response identifies one of said transmission paths available for data transmission between said first network node and said second network node.

4. The method of claim 3, wherein said another routing response is independent of said route constraints.

5. The method of claim 1, wherein

said second network node sends the another routing response to said first network node in response to said broadcast,

said another routing response identifies one of the transmission paths available for data transmission between said first network node and said second network, and

said first network node selects between said identified transmission paths.

6. The method of claim 1, wherein said ad-hoc communication network comprises a software defined network (SDN), and wherein said plurality of network devices comprise routers and network switches.

7. The method of claim 1, wherein said method is a computer implemented method.

8. The method of claim 1, wherein said determining comprises determining said identified transmission paths using one or more of an adaptive routing process, a deflecting routing process, an edge disjoint shortest pair process, a Dijkstra'"'"'s process, a fuzzy routing process, a geographic routing process, a Heuristic routing process, or a hierarchical routing process.

9. A control system within a software defined network (SDN), wherein said control system is coupled to a plurality of network devices within said SDN and accesses topology information of said SDN and intelligently controls data traffic among said plurality of network devices, said control system comprises:

a physical input interface receiving a route request from a first network device in the plurality of network devices within said SDN, wherein

said route request comprises a request to identify a transmission path with route constraints for routing data from said first network device to a second network device in the plurality of network devices within said SDN,

said route request is sent to said control system via unicast,

said route request is sent to said plurality of network devices via broadcast within said SDN, and

the second network device sends another route response to said first network node in response to said route request by virtue of unicast;

a route processor coupled to said input interface and determining a first transmission path based on said topology information of said ad-hoc communication network and based on the route constraints received in said route request, wherein said first transmission path is feasible for data transmission between said first network device and said second network device;

a message generator coupled to said route processor and generating a route response that identifies said first transmission path, and wherein said another route response identifies a second transmission path feasible for data transmission between said first network device and said second network device; and

a physical output interface coupled to said message generator sending said route response and said another route response to said first network device via unicast, wherein one of said route response and said another route response is selected by the first network, which selected route response comprises information used for updating a routing table associated with said first network device.

10. The control system of claim 9, wherein said route request is sent to said control system via broadcast.

11. A method of transmitting data through an ad-hoc communication network comprising a plurality of network nodes and a central controller, said method comprising:

sending a route request to a central controller of said ad-hoc communication network and to said plurality of network nodes by virtue of broadcast, wherein said route request comprises a request to identify a transmission path for routing data from the central controller and a first network device in the plurality of network devices to a second network device in the plurality of network devices within said ad-hoc communication network, wherein said central controller and said first network device determine first and second transmission paths, respectively, based on a topology of said ad-hoc communication network in response to said route request;

receiving a first route response from said central controller via unicast, wherein said first route response identifies the first transmission path linking said first network device and said second network device, and receiving a second route response from said second network device via unicast, wherein said second route response identifies the second transmission path linking said first network device and said second network device; and

selecting one of the first transmission path determined by the central controller and the second transmission path determined by the first network device to link the first network device to the second network device.

12. The method of claim 11, wherein said ad-hoc communication network comprises a software-defined network (SDN), and wherein said central controller is a SDN controller.

13. The method of claim 12, wherein said route request comprises route constraints with respect to data transmission between said first and said second network devices, and wherein said first transmission path is determined by incorporating said route constraints.

14. The method of claim 13 further comprises:

broadcasting the second route request to said SDN; and

receiving the second route response from said second network device, wherein said second route response identifies the second transmission path between said first and said second network devices based on an ad hoc on-demand distance vector routing method.

15. The method of claim 11, wherein

said ad-hoc communication network comprises a SDN, and

said central controller is a SDN controller,

said sending comprises sending the second route request to said SDN controller via broadcast to said SDN, and

said method further comprises:

receiving the second route response from said second network device, wherein said second route response identifies the second transmission path between said first and said second network devices based on an ad hoc on-demand distance vector routing method; and

selecting a resultant transmission path from said first transmission path and said second transmission path.

16. The network device of claim 15, wherein said SDN controller is a centralized controller that is distributed in multiple network devices of said plurality of network devices.