Buffer-less virtual routing

• US 8,611,355 B1
• Filed: 09/03/2013
• Issued: 12/17/2013
• Est. Priority Date: 09/03/2013
• Status: Active Grant

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: TW Telecom Holdings Incorporated (Lumen Technologies, Inc.)
• Inventors: Sella, William Thomas, Sella, James Michael
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): HYUN, SOON D
• Application Number:
  US14/016,969
• Time in Patent Office: 105 Days
• Field of Search: None
• US Class Current: 370/392
• 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 through a plurality of interconnected routers, comprising:

(a) receiving, at a virtual routing server, an initial packet in the first data stream;

in response to receipt of the initial packet of the first data stream;

(b) transmitting the initial packet with routing instructions indicating, to downstream routers from the virtual routing server to the destination, how to route the initial packet to the destination;

(c) determining a first path through plurality of interconnected routers from the source to the destination;

(d) for respective routers along the first path, determining a routing table indicating which port of the router to route data from the first data stream along the first path determined in (c);

(e) for each of the respective routers, transmitting the routing table determined in (d) to configure the router;

repeatedly until the respective routers are configured to route data from the first data stream along the first path;

(f) receiving an additional packet from the first data stream; and

(g) transmitting the additional packet with the routing instructions indicating to the downstream routers how to route the additional packet to the destination.

2. The method of claim 1, wherein the determining (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.

3. The method of claim 1, wherein the determining (c) comprises selecting the first path from a plurality of different paths connecting the source to the destination based on a relative latency, jitter, or packet loss on the plurality of different paths.

4. The method of claim 1, wherein the determining (c) comprises determining the first path such that data from the first data stream will pass through a particular machine.

5. The method of claim 4, wherein the determining (c) further comprises selecting the particular machine from a plurality of machines having a particular class.

6. The method of claim 1, wherein each packet in the first data stream has an identifier and wherein the routing table determined in (d) indicates which port the router will route data having the identifier.

7. The method of claim 1, wherein each packet in the first data stream has a first identifier, and further comprising:

(h) receiving an initial packet from a second data stream, the second data stream having been transmitted from a different source to the destination and having a second identifier; and

(i) determining a second path through the plurality of interconnected routers the from the different source to the destination, the second path converging with the first path determined in (c) at a particular router;

(j) for respective routers along the second path upstream from the particular router, determining a routing table indicating which port the router will route data having the second identifier such that data from the second data stream will be routed along the second path;

(k) for respective routers along the first path determined in (c) upstream from the particular router, determining a routing table indicating which port the router will route data having the first identifier such that data from the first data stream will be routed along the first path;

(l) for the particular router, determining a routing table indicating to the particular router to re-label data from the first or second data streams such that both the first and second streams have a common identifier;

(m) for respective routers along the first and second paths downstream from the particular router, determining a routing table indicating which port the router will route data having the common identifier such that data from the second data stream will be routed along the first and second paths to the destination; and

(n) transmitting the routing tables determined in (i)-(m) to configure the respective routers along the first and second paths.

8. The method of claim 1, further comprising:

(h) 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 particular period of time;

(i) for each of the respective routers along the first path, determining a new routing table that does not indicate where to route data from the first data stream; and

(j) for each of the respective routers, transmitting the new routing table determined in (i) to configure the router.

9. A system for virtually routing a first data stream from a source to a destination through a plurality of interconnected routers, comprising:

a data stream module that receives, at a virtual routing server, packets in the first data stream;

a path determination module that determines a first path through the plurality of interconnected routers from the source to the destination;

a data forward module that repeatedly, until the plurality of interconnected routers are configured to route data from the first data stream along the first path, transmits the packets with routing instructions indicating, to downstream routers from the virtual routing server to the destination, how to route the packets to the destination; and

a routing table module that, for respective routers along the first path, determines a routing table indicating which port of the router to route data from the first data stream along the first path and transmits the respective routing tables to configure the respective routers along the first path.

10. The system of claim 9, wherein the path determination module selects 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.

11. The system of claim 10, wherein the path determination module projects availability of capacity using historical analysis to determine the relative amount of available capacity.

12. The system of claim 9, wherein the path determination module selects the first path from a plurality of different paths connecting the source to the destination based on a relative latency, jitter, or packet loss on the plurality of different paths.

13. The system of claim 9, wherein the path determination module determines the first path such that data from the first data stream will pass through a particular machine.

14. The system of claim 9, wherein each packet in the first data stream has an identifier and wherein the routing table indicates which port the router will route data having the identifier.

15. The system of claim 9, wherein each packet in the first data stream has a first identifier, and

wherein the first data stream module receives an initial packet from a second data stream, the second data stream having been transmitted from a different source to the destination and having a second identifier,

wherein the path determination module determines a second path through the plurality of interconnected routers from the different source to the destination, the second path converging with the first path at a particular router, and

wherein the routing table module:

(i) for respective routers along the second path upstream from the particular router, determines a routing table indicating which port the router will route data having the second identifier such that data from the second data stream will be routed along the second path,

(ii) for respective routers along the first path upstream from the particular router, determines a routing table indicating which port the router will route data having the first identifier such that data from the first data stream will be routed along the first path;

(iii) for the particular router, determines a routing table indicating to the particular router to re-label data from the first or second data streams such that both the first and second streams have a common identifier;

(iv) for respective routers along the first and second paths downstream from the particular router, determines a routing table indicating which port the router will route data having the common identifier such that data from the second data stream will be routed along the first and second paths to the destination; and

(v) transmits the routing tables determined in (i)-(iv) to configure the respective routers along the first and second paths.

16. The system of claim 9, and further comprising:

a path expiration module that receives a message from any router along the first path indicating that the router that sent the message has not received data from the first data stream for a particular period of time,

wherein, for each of the respective routers along the first path, the routing table module determines a new routing table that does not indicate where to route data from the first data stream, and transmits the new routing table to configure the router.

17. A program storage device tangibly embodying a program of instructions executable by at least one machine to perform a method for virtually routing a first data stream from a source to a destination through a plurality of interconnected routers, the method comprising:

(a) receiving, at a virtual routing server, an initial packet in the first data stream;

in response to receipt of the initial packet of the first data stream;

(b) transmitting the initial packet with routing instructions indicating, to downstream routers from the virtual routing server to the destination, how to route the initial packet to the destination;

(c) determining a first path through the plurality of interconnected routers from the source to the destination;

(d) for respective routers along the first path, determining a routing table indicating which port of the router to route data from the first data stream along the first path determined in (c);

(e) for each of the respective routers, transmitting the routing table determined in (d) to configure the router;

repeatedly until the respective routers are configured to route data from the first data stream along the first path;

(f) receiving an additional packet from the first data stream; and

(g) transmitting the additional packet with the routing instructions indicating to the downstream routers how to route the additional packet to the destination.

18. The program storage device of claim 17, wherein the determining (c) comprises selecting the first path from a plurality of different paths connecting the source to the destination based on the relative amount of available capacity on the plurality of different paths.

19. The program storage device of claim 17, wherein the determining (c) comprises selecting the first path from a plurality of different paths connecting the source to the destination based on the relative latency, jitter, or packet loss on the plurality of different paths.

20. The program storage device of claim 17, wherein the determining (c) comprises determining the fist path such that data from the first data stream will pass through a particular machine.

21. The program storage device of claim 17, wherein each packet in the first data stream has an identifier and wherein the routing table determined in (d) indicates which port the router will route data having the identifier.

22. The program storage device of claim 17, wherein each packet in the first data stream has a first identifier, and the method further comprising:

(h) receiving an initial packet from a second data stream, the second data stream having been transmitted from a different source to the destination and having a second identifier; and

(i) determining a second path through the plurality of interconnected routers from the different source to the destination, the second path converging with the first path determined in (c) at a particular router;

(j) for respective routers along the second path upstream from the particular router, determining a routing table indicating which port the router will route data having the second identifier such that data from the second data stream will be routed along the second path;

(k) for respective routers along the first path determined in (d) upstream from the particular router, determining a routing table indicating which port the router will route data having the first identifier such that data from the first data stream will be routed along the first path;

(l) for the particular router, determining a routing table indicating to the particular router to re-label data from the first or second data streams such that both the first and second streams have a common identifier;

(m) for respective routers along the first and second paths downstream from the particular router, determining a routing table indicating which port the router will route data having the common identifier such that data from the second data stream will be routed along the first and second paths to the destination; and

(n) transmitting the routing tables determined in (i)-(m) to configure the respective routers along the first and second paths.

23. A system for routing a data stream from a source to a destination, comprising:

a plurality of physical routing devices interconnected such that the physical routing devices are able to communicate with each other using a routing protocol; and

a virtual router that makes the plurality of physical routing devices appear to the source as a single device, comprising;

a virtual backplane that represents how the plurality of physical routing devices are interconnected;

a data stream module that receives packets in the data stream;

a path determination module that determines a path through the plurality of interconnected routers the from the source to the destination;

a data forward module that repeatedly, until the plurality of interconnected routers are configured to route data from the data stream along the path, transmits the packets with routing instructions indicating to downstream routers how to route the packets to the destination; and

a routing table module that, for respective routers along the path, determines a routing table indicating which port of the router to route data from the data stream along the path and transmits the respective routing tables to configure the respective routers along the path.