Buffer-less virtual routing

• US 10,079,758 B2
• Filed: 04/26/2016
• Issued: 09/18/2018
• Est. Priority Date: 09/03/2013
• Status: Active Grant

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Inventors: Sella, William Thomas, Sella, James Michael
• Primary Examiner(s): Pham, Chi H
• Assistant Examiner(s): Agureyev, Vladislav
• Application Number:
  US15/139,191
• Publication Number:
  US 20160241470A1
• Time in Patent Office: 875 Days
• Field of Search: None
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 43/087 Jitter
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 45/502 Frame based
• CPC Class Codes: H04L 45/566 Routing instructions carried by the data packet, e.g. active networks
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS

Abstract

A network includes a plurality of endpoint routers and intermediate routers. When a new data stream is detected at any endpoint router, the first packet is sent to a virtual routing server with knowledge of the entire network topology. Based on the topology, current usage, and historical usage, the virtual routing server determined a path for the data stream and begins to update the routing tables of the intermediate routers to reflect the determined path. Until the update is complete, all packets in the data stream are routed first to the virtual routing server and then to their destination. Once the update is complete, packets in the data stream are routed directly along the determined path.

Claims

1. A computer-implemented method for virtually routing a first data stream from a source to a destination, comprising:

(a) determining, by an edge router, a first virtual router and a pre-computed path from the edge router to the first virtual router;

(b) in response to receiving a first packet in the first data stream by the edge router, sending, by the edge router, the first packet to the first virtual router along the pre-computed path;

(c) receiving, by the edge router, a first instruction from the first virtual router to configure the edge router to route data such that at least a first portion of the first data stream is routed along a first path determined through a plurality of interconnected routers from the source to the destination; and

(d) configuring the edge router according to the first instruction received in (c).

2. The computer-implemented method of claim 1, further comprising:

(e) after the configuring in (d), receiving a second packet in the first data stream by the edge router; and

(f) in response to the receiving the second packet in (e), sending the second packet along the first path identified in the first instruction received in (c) to the destination.

3. The computer-implemented method of claim 1, wherein the determining in (a) comprises selecting the first virtual router from a plurality of virtual routers.

4. The computer-implemented method of claim 1, wherein the receiving in (c) comprises receiving, by the edge router, the first instruction from the first virtual router to configure the edge router to route data such that at least the first portion of the first data stream is routed along the first path through the plurality of interconnected routers from the source to the destination, and at least a second portion of the first data stream is routed along a second path, different from the first path, through the plurality of interconnected routers from the source to the destination.

5. The computer-implemented method of claim 4, wherein a determination of the first path and the first portion, and the second path and the second portion in (c) is made such that a pre-determined quality-of-service requirement by the first data stream is met.

6. The computer-implemented method of claim 1, wherein the first path is selected from a plurality of different paths connecting the source to the destination based on a relative amount of available capacity on the plurality of different paths.

7. The computer-implemented method of claim 1, wherein the first path is selected from a plurality of different paths connecting the source to the destination based at least on one of a relative latency, jitter, or packet loss on the plurality of different paths.

8. An edge router for virtually routing data streams, comprising:

a routing table specifying a first default path from the edge router to a first virtual router; and

a processor coupled to the routing table, the processor configured to;

(a) in response to receiving a first packet in a first data stream, send the first packet to the first virtual router along the first default path;

(b) in response to receiving a second packet from the first data stream, send the second packet to the first virtual router along the first default path; and

(c) in response to receiving a first instruction from the first virtual router to configure the edge router to route data such that at least a first portion of the first data stream is routed along a first path through a plurality of interconnected routers from a source to a destination, update the routing table with the first path.

9. The edge router of claim 8, wherein the processor is further configured to:

(d) after the update in (c), receive a third packet from the first data stream; and

(e) in response to receiving the third packet from the first data stream, send the third packet along the first path between the source and the destination.

10. The edge router of claim 8, wherein the first virtual router is selected from a plurality of virtual routers.

11. The edge router of claim 8, wherein the first path is selected such that data from the first data stream will pass through a particular machine.

12. A non-transitory computer-readable medium having instructions stored thereon that, when executed by at least one computing device, cause the at least one computing device to perform a method for virtually routing a first data stream from a source to a destination, the method comprising:

(a) determining, by an edge router, a first virtual router and a pre-computed path from the edge router to the first virtual router;

(b) in response to receiving a first packet in the first data stream by the edge router, sending, by the edge router, the first packet to the first virtual router along the pre-computed path;

(c) receiving, by the edge router, a first instruction from the first virtual router to configure the edge router to route data such that at least a first portion of the first data stream is routed along a first path determined through a plurality of interconnected routers from the source to the destination; and

(d) configuring the edge router according to the first instruction received in (c).

13. The computer-readable medium of claim 12, the method further comprising:

(e) after the configuring in (d), receiving a second packet in the first data stream by the edge router; and

(f) in response to the receiving the second packet in (e), sending the second packet along the first path identified in the first instruction received in (c) to the destination.

14. The computer-readable medium of claim 12, wherein the determining in (a) comprises selecting the first virtual router from a plurality of virtual routers.

15. The computer-readable medium of claim 12, wherein the receiving in (c) comprises receiving, by the edge router, the first instruction from the first virtual router to configure the edge router to route data such that at least the first portion of the first data stream is routed along the first path through the plurality of interconnected routers from the source to the destination, and at least a second portion of the first data stream is routed along a second path, different from the first path, through the plurality of interconnected routers from the source to the destination.

16. The computer-readable medium of claim 15, wherein a determination of the first path and the first portion, and the second path and the second portion in (c) is made such that a pre-determined quality-of-service requirement by the first data stream is met.

17. The computer-readable medium of claim 12, wherein the first path is selected from a plurality of different paths connecting the source to the destination based on a relative amount of available capacity on the plurality of different paths.

18. The computer-readable medium of claim 12, wherein the first path is selected from a plurality of different paths connecting the source to the destination based at least on one of a relative latency, jitter, or packet loss on the plurality of different paths.

19. A computer-implemented method for virtually routing a first data stream from a source to a destination through a plurality of interconnected routers, comprising:

(a) receiving a first packet in the first data stream at a virtual router;

(b) transmitting the first packet to the destination on a pre-computed path from the virtual router to the destination;

(c) determining, by the virtual router, a first path through the plurality of interconnected routers from the source to the destination; and

(d) configuring each router in the first path to route data from the first data stream along the first path;

(e) receiving a message from a router along the first path indicating that the router that sent the message has not received data from the first data stream for a predetermined period of time;

(f) for each respective router along the first path, determining, by the virtual router a routing table that does not indicate where to route data from the first data stream; and

(g) for each of the respective routers, transmitting the routing table determined in (f) to configure the respective router.

20. The computer-implemented method of claim 19, wherein the configuring in (d) is performed repeatedly starting with configuring a last router in the first path and ending with configuring a first router in the first path, wherein the last router is closest to the destination, and the first router is closest to the source.

21. The computer-implemented method of claim 19, further comprising:

(h) receiving, at a virtual routing server, a second packet from the first data stream from the source at the virtual router; and

(i) transmitting the second packet over the pre-computed path from the virtual router to the destination.

22. The computer-implemented method of claim 19, wherein the determining in (c) comprises selecting the first path from a plurality of different paths connecting the source to the destination based on a relative amount of available capacity on the plurality of different paths.

23. The computer-implemented method of claim 19, wherein the determining in (c) comprises selecting the first path from a plurality of different paths connecting the source to the destination based at least on one of a relative latency, jitter, or packet loss on the plurality of different paths.

24. The computer-implemented method of claim 19, wherein the determining in (c) comprises determining the first path such that data from the first data stream will pass through a particular machine.

25. The computer-implemented method of claim 24, wherein the determining in (c) further comprises selecting the particular machine from a plurality of machines having a particular class.

26. A computer-implemented method for virtually routing a first data stream from a source to a destination through a plurality of interconnected routers, comprising:

(a) receiving a first packet in the first data stream at a virtual router;

(b) transmitting the first packet to the destination on a pre-computed path from the virtual router to the destination;

(c) determining, by the virtual router, a first path through the plurality of interconnected routers from the source to the destination and determining, by the virtual router, a second path through the plurality of interconnected routers from the source to the destination such that at least the a first portion of the first data stream is routed along the first path through the plurality of interconnected routers from the source to the destination, and at least a second portion of the first data stream is routed along a second path, different from the first path, through the plurality of interconnected routers from the source to the destination;

(d) configuring each router in the first path to route data from the first data stream along the first path.