Control device discovery in networks having separate control and forwarding devices
A Software Defined Network (SDN) includes a plurality of forwarding devices and a routing control device located separate from the forwarding devices. The routing control device, establishes paths to and from the network forwarding devices. Using such paths, forwarding devices send the routing control device information reflecting the topology if the network. Embodiments disclosed herein enable automatic discovery of the topology of the network and the paths to and from the routing control device.
1. A computer implemented method comprising:
(a) sending, from a routing control device, to a forwarding device of a plurality of forwarding devices, a control packet, wherein the control packet includes an address of the routing control device, a serial number of the control packet, and a performance metric, wherein the forwarding device sends the control packet to another forwarding device in the plurality of forwarding devices, and wherein the forwarding device updates the performance metric to indicate an estimated time to route a packet from the forwarding device to the routing control device;
(b) periodically receiving, on the routing control device, messages from the forwarding device, each message identifying the forwarding device and other forwarding devices in the plurality of forwarding devices that the forwarding device is connected to;
(c) constructing a topology database representing a topology of the network based on the messages received in (b);
(d) constructing a default path based on the messages received in (b);
(e) receiving, on the routing control device, a message, wherein the message requests the routing control device to determine a path through the plurality of forwarding devices to forward packets of a data stream;
(f) receiving, on the routing control device, at least one packet of the data stream;
(g) prior to determining the path through the plurality of forwarding devices, routing the at least one packet using the default path;
(h) determining the path through the plurality of forwarding devices, based at least on the topology database, the determined path comprising a subset of the plurality of forwarding devices and connecting a source of the data stream to a destination of the data stream; and
(i) sending configuration messages to each forwarding device in the subset of the plurality of forwarding devices to instruct each forwarding device to forward packets of the data stream along the determined path.
2. The method of claim 1 , wherein the sending (i) comprises:
sending a configuration message to another forwarding device in the subset of the plurality of forwarding devices and directly connected to the destination of the data stream, and
repeatedly sending configuration messages to other forwarding devices in the subset of the plurality of forwarding devices in the reverse order of the path from the source of the data stream to the destination of the data stream.
3. The method of claim 1 , wherein the determining (h) comprises:
determining the path to route through a destination server.
4. The method of claim 1 , wherein the control packet further includes a metric indicating one or more of congestion information, latency, packet loss rate, and jitter, encountered in routing a packet from the forwarding device or the other forwarding devices to the routing control device.
5. The method of claim 1 , wherein the forwarding device sends a label to another forwarding device in the subset of the plurality of forwarding devices, wherein the label, when attached to a packet received at the forwarding device indicates to the forwarding device to forward the packet toward the routing control device.
6. The method of claim 1 , wherein the forwarding device adds an address of the forwarding device to the control packet prior to sending the control packet to the another forwarding device.
7. A program storage device tangibly embodying a program of instructions executable by at least one machine to perform a method for discovering routes between a plurality of forwarding devices in a network via a routing control device, the method comprising:
(a) sending, from routing control device, to a forwarding device from a plurality of forwarding devices, a control packet, wherein the control packet includes an address of the routing control device, a serial number of the control packet, and a performance metric, wherein the forwarding device sends the control packet to another forwarding device in the plurality of forwarding devices, and wherein the forwarding device updates the performance metric to indicate an estimated time to route a packet from the forwarding device to the routing control device;
(b) periodically receiving, on the routing control device, messages from the forwarding device, each message identifying the forwarding device and other forwarding devices in the plurality of forwarding devices that the forwarding device is connected to;
(c) constructing a topology database representing a topology of the network based on the messages received in (b);
(d) constructing a default path based on the messages received in (b);
(e) receiving, on the routing control device, a message, wherein the message requests the routing control device to determine a path through the plurality of forwarding devices to forward packets of a data stream;
(f) receiving, on the routing control device, at least one packet of the data stream;
(g) prior to determining the path through the plurality of forwarding devices, routing the at least one packet using the default path;
(h) determining the path through the plurality of forwarding devices, based at least on the topology database, the determined path comprising a subset of the plurality of forwarding devices and connecting a source of the data stream to a destination of the data stream; and
(i) sending configuration messages to each forwarding device in the subset of the plurality of forwarding devices to instruct each forwarding device to forward packets of the data stream along the determined path.
8. The program storage device of claim 7 , wherein the sending (i) comprises:
sending a configuration message to another forwarding device in the subset of the plurality of forwarding devices and directly connected to the destination of the data stream, and
repeatedly sending configuration messages to other forwarding devices in the subset of the plurality of forwarding devices in the reverse order of the path from the source of the data stream to the destination of the data stream.
9. The program storage device of claim 7 , wherein the determining (h) comprises:
determining the path to route through a destination server.
10. The program storage device of claim 7 , wherein the control packet further includes a metric indicating one or more of congestion information, latency, packet loss rate, and jitter, encountered in routing a packet from the forwarding device or another forwarding device of the other forwarding devices to the routing control device.
11. The program storage device of claim 7 , wherein the forwarding device sends a label to another forwarding device in the subset of the plurality of forwarding devices, wherein the label, when attached to a packet received at the forwarding device indicates to the forwarding device to forward the packet toward the routing control device.
12. The program storage device of claim 7 , wherein the forwarding device adds an address of the forwarding device to the control packet prior to sending the control packet to the another forwarding device.