Transparent, look-up-free packet forwarding method for optimizing global network throughput based on real-time route status

• US 7,254,138 B2
• Filed: 07/11/2002
• Issued: 08/07/2007
• Est. Priority Date: 02/11/2002
• Status: Active Grant

• Current Assignee: Mark Henrik Sandstrom
• Original Assignee: Optimum Communications Services, Inc.
• Inventors: Sandstrom, Mark Henrik
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US10/192,118
• Publication Number:
  US 20040032856A1
• Time in Patent Office: 1,853 Days
• Field of Search: None
• US Class Current: 370/412
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 69/32 Architecture of open systems interconnection [OSI] 7-layer type protocol stacks, e.g. the interfaces between the data link level and the physical level
• CPC Class Codes: H04L 69/325 in the network layer [OSI layer 3], e.g. X.25 H04L69/16 takes precedence

Abstract

A packet forwarding method for optimizing packet traffic flow across communications networks and simplifying network management. The invention provides look-up-free and packet-layer-protocol transparent forwarding of multi-protocol packet traffic among Layer-N (N=2 or upper in the ISO OSI model) nodes. The invention enables flexible and efficient packet multicast and anycast capabilities along with real-time dynamic load balancing and fast packet-level traffic protection rerouting. Applications include fast and efficient packet traffic forwarding across administrative domains of Internet, such as an ISP'"'"'s backbone or an enterprise virtual private network, as well as passing packet traffic over a neutral Internet exchange facility between different administrative domains.

Claims

1. A packet forwarding method for delivering data packets across a communications network,

wherein the network comprises a set of ingress and egress ports, and provides routes for delivering packets among a set of nodes that interface with the network through the ingress and egress ports, with a set of nodes reachable to each other via the routes across the network referred to as a set of next-hop destinations to each other,

and wherein the network determines whether to deliver a packet arrived on an ingress port to a particular egress port based at least in part on a forwarding identifier included in the packet and on network status,

wherein the network status includes:

i) current reachability of one or more of the set of next-hop destinations; and

ii) current traffic load level on a route or routes across the network to one or more of the set of next-hop destinations, wherein the traffic load level on a route towards a next-hop destination is determined based at least in part on an amount of data currently queued in a data buffer for a future delivery on the route across the network to the next-hop destination associated with the buffer.

2. The packet forwarding method of claim 1, wherein the forwarding identifier includes an indication of to which one or ones of the set of next-hop destinations the packet is intended to be delivered.

3. The packet forwarding method of claim 1, wherein the forwarding identifier includes an individualized indication per at least one next-hop destination of whether the packet is intended to be delivered to that node.

4. The packet forwarding method of claim 1, wherein the forwarding identifier includes an indication of whether the packet is intended to be delivered to a particular next-hop destination individually per each one of the set of next-hop destinations normally reachable through the network from the ingress port on which the packet arrived the network.

5. The packet forwarding method of claim 1, wherein, when a next-hop destination indicated by the forwarding identifier of a packet is not directly reachable from the ingress port on which the packet arrives, the network provides means for routing the packet to the said next-hop destination through one or more intermediate packet forwarding points.

6. The packet forwarding method of claim 1, wherein, when the current amount of data queued in the buffer for a future delivery to its associated next-hop destination is above a pre-definable threshold, the network is able to route the packet to the said next-hop destination through one or more intermediate forwarding points.

7. The packet forwarding method of claim 1, wherein in case the forwarding identifier of a packet indicates that the packet should be forwarded to one of a specified set of two or more alternative next-hop destinations, the network delivers the packet to such currently reachable one of the said set of alternative destinations whose associated current level of traffic load is below a pre-definable threshold, or is the lowest among the said set of alternative destinations.

8. The packet forwarding method of claim 1, wherein the forwarding identifier identifies a set of two or more alternative next-hop destinations out of which the packet is intended to be delivered to a currently suitable one.

9. The packet forwarding method of claim 8, wherein the next-hop destination to which the network delivers the packet is chosen out of the set of alternative next-hop destinations based at least in part on the current levels of traffic load on the routes across the network toward the said set of alternative next-hop destinations.

10. The packet forwarding method of claim 8, wherein the set of alternative next-hop destinations have selection priorities associated with them, and wherein such one of the currently reachable alternative next-hop destinations is selected that has the highest selection priority out of those of the alternative next-hop destinations whose current level of traffic load is below a pre-definable threshold.

11. A process for maximizing throughput of packet traffic across a network, the network comprising a set of interfaces for exchanging data packets between a set of upper-layer nodes interconnected by the network, and a capability to provide a set of alternative routes to deliver a packet arrived into the network to a proper upper-layer next-hop destination node indicated by a forwarding identifier of the packet, the process comprising a set of process steps including:

receiving, by the network, sequences of data packets from the upper-layer nodes it interconnects via their associated interfaces;

monitoring, by a network interface on which a packet arrived, a status of the set of individual alternative routes to deliver the packet, wherein the monitored status of a route includes a traffic load level on the route and reachability of the next-hop destination of the route;

selecting, by the network interface on which the packet arrived, depending on the monitored status of the individual alternative routes, a suitable route of the set of alternative routes to deliver the packet; and

delivering the packet along the selected route across the network to its next-hop destination node, wherein the traffic load level on a route is determined based at least in part on an amount of data queued in a buffer for future delivery on the route.

12. The process of claim 11, wherein the reachability of the next-hop destination of the route is checked periodically.

13. The process of claim 11, wherein the step of selecting a route is done as follows:

out of the routes whose next-hop destination node is reachable, the one having the lowest level of data queued for future delivery is selected.

14. The process of claim 11, wherein the alternative routes have pre-definable selection priorities associated with them, and wherein the step of selecting a route is done as follows:

out of the routes whose next-hop destination node is reachable and whose associated amount of data queued for future delivery is below a pre-definable threshold, the one having the highest selection priority is selected.

15. The process of claim 11, wherein at least one of the alternative routes involves one or more intermediate packet forwarding points.

16. The process of claim 15, wherein an intermediate packet forwarding point along an alternative route is able to forward a data packet arriving to it on the alternative route either i) toward the primary next-hop destination, or ii) to an alternative next-hop destination of the packet, each of which next-hop destinations being indicated, explicitly or implicitly, by a forwarding instruction within the packet.

17. The process of claim 16, wherein the intermediate packet forwarding point forwards the packet toward its primary next-hop destination in case the primary next-hop destination is reachable from it when it makes its forwarding decision for the packet.

18. A network system for delivering data packets among a set of upper-layer nodes, the network system providing:

a set of external interfaces for passing packets between the upper-layer nodes and the network system;

a set of routes for delivering packets across the network system between the external interfaces; and

a capability to deliver a packet arrived on an external interface to the other external interfaces for transmitting the packet to their associated upper-layer nodes, with such set of upper-layer nodes referred to as a set of next-hop destinations to the upper-layer node where the packet arrived from,

wherein the network system determines to which individual one or ones of the set of next-hop destinations it delivers a packet based at least in part on a set of one or more forwarding instructions carried within the packet, and on a route status information of the routes leading to the set of next-hop destinations,

and wherein the route status information includes i) reachability of its next-hop destination, and ii) traffic load level on the route, wherein the traffic load level on a route is determined based at least in part on an amount of data queued on a buffer for a future transmission on the route.

19. The network system of claim 18, further providing a capability deliver data packets among the set of upper-layer nodes without any modification of the packets.

20. The network system of claim 18, further providing a capability deliver data packets among the set of upper-layer nodes without modifying any information fields of the packets, except for a time-to-live decrement.

21. The network system of claim 18, further providing a capability deliver data packets among the upper-layer nodes without modifying, including adding or deleting, any upper-layer protocol information fields of the packets.

22. The network system of claim 18, wherein the individual next-hop destination or destinations to which the network system forwards a packet is determined by the network system without using a forwarding, switching or routing table, or other forwarding, switching or routing information database.

23. The network system of claim 18, wherein the reachability of the next-hop destinations of the routes across the network is automatically checked on a periodic basis.

24. The network system of claim 18, wherein the set of forwarding instructions of a packet includes an indication of two or more alternative next-hop destinations,

and wherein the network system forwards the packet out of the reachable alternative next-hop destinations to the one that has the lowest traffic load level on its associated route.

25. The network system of claim 18, wherein the set of forwarding instructions of a packet includes an indication of a primary next-hop destination and an indication of an alternative next-hop destination,

and wherein, when both the primary and the alternative next-hop destinations are reachable, the network system forwards the packet to the primary next-hop destination if

i) the amount of data queued in the buffer associated with the primary next-hop destination is below a pre-definable threshold, or

ii) the amount of data queued in the buffer associated with the alternative next-hop destination is above a pre-definable threshold;

otherwise, the network system forwards the packet to the alternative next-hop destination.

26. The network system of claim 18, wherein the set of forwarding instructions of a packet includes an indication of a primary next-hop destination and an indication of an alternative next-hop destination,

and wherein, when the primary next-hop destination is reachable or when the alternative next-hop destination is not reachable, the network system forwards the packet to the primary next-hop destination, and otherwise to the alternative next-hop destination.

27. The network system of claim 18, wherein a packet is delivered to a reachable next-hop destination based at least in part on whether forwarding the packet to the said next-hop destination is explicitly enabled by the set of forwarding instructions of the said packet.

28. The network system of claim 18, wherein the set of forwarding instructions of a packet includes an explicit forwarding enable indicator per one or more of the set of next-hop destinations,

and wherein the network system delivers the packet to each such reachable next-hop destination to which forwarding of the packet was enabled by the explicit forwarding enable indicator associated with that particular next-hop destination.

29. The network system of claim 28, wherein the set of forwarding instructions of a packet includes an explicit forwarding enable indicator per each one of the set of next-hop destinations.

30. The network system of claim 18, further providing a capability to deliver a packet to a next-hop destination indicated by the set of forwarding instructions of the packet via at least two alternative routes across the network system.

31. The network system of claim 30, wherein the network system selects the alternative route along which to forward the packet to its indicated next-hop destination based at least in part on the reachability of that next-hop destination via the individual alternative routes.

32. The network system of claim 30, wherein the network system selects the alternative route along which to forward the packet to its indicated next-hop destination based at least in part on the traffic load level on the individual alternative routes.

33. The network system of claim 30, wherein one or more of the alternative routes includes at least one intermediate packet forwarding point.

34. The network system of claim 33, wherein an intermediate packet forwarding point along an alternative route provides a capability to re-forward the packet to an appropriate next-hop destination, which it determines based at least in part on the forwarding instructions of the packet and on the external interface from where it received the packet.

35. A cluster of network systems of claim 18 containing at least two member network systems, wherein the member network systems further provide interfaces for passing packets between the member network systems of the cluster.

36. The network system cluster of claim 35, wherein the set of forwarding instructions of a packet includes a dedicated forwarding instruction for at least one of the member network systems along an intended route of the packet across the cluster of network systems.

37. The network system cluster of claim 35, wherein the set of forwarding identifiers of a packets include a dedicated forwarding instruction per each member network system along an intended route of the packet across the cluster of network systems.